{-# LANGUAGE BangPatterns, FlexibleContexts #-}
{-# OPTIONS_HADDOCK hide, prune #-}
module Data.ByteString.Search.Internal.Utils ( kmpBorders
, automaton
, occurs
, suffShifts
, ldrop
, ltake
, lsplit
, release
, keep
, strictify
) where
import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import Data.ByteString.Unsafe (unsafeIndex)
import Data.Array.Base (unsafeRead, unsafeWrite, unsafeAt)
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad (when)
import Data.Bits
import Data.Word (Word8)
{-# INLINE automaton #-}
automaton :: S.ByteString -> UArray Int Int
automaton :: ByteString -> UArray Int Int
automaton !ByteString
pat = (forall s. ST s (STUArray s Int Int)) -> UArray Int Int
forall i e. (forall s. ST s (STUArray s i e)) -> UArray i e
runSTUArray (do
let !patLen :: Int
patLen = ByteString -> Int
S.length ByteString
pat
{-# INLINE patAt #-}
patAt :: Int -> b
patAt !Int
i = Word8 -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteString -> Int -> Word8
unsafeIndex ByteString
pat Int
i)
!bord :: UArray Int Int
bord = ByteString -> UArray Int Int
kmpBorders ByteString
pat
STUArray s Int Int
aut <- (Int, Int) -> Int -> ST s (STUArray s Int Int)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Int
0, (Int
patLen Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
256 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
0
STUArray s Int Int -> Int -> Int -> ST s ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
aut (Int -> Int
forall {b}. Num b => Int -> b
patAt Int
0) Int
1
let loop :: Int -> m (STUArray s Int Int)
loop !Int
state = do
let !base :: Int
base = Int
state Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
8
inner :: Int -> m (STUArray s Int Int)
inner Int
j
| Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = if Int
state Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
patLen
then STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
aut
else Int -> m (STUArray s Int Int)
loop (Int
stateInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
| Bool
otherwise = do
let !i :: Int
i = Int
base Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall {b}. Num b => Int -> b
patAt Int
j
Int
s <- STUArray s Int Int -> Int -> m Int
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> m e
unsafeRead STUArray s Int Int
aut Int
i
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) (STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
aut Int
i (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))
Int -> m (STUArray s Int Int)
inner (UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt UArray Int Int
bord Int
j)
if Int
state Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
patLen
then Int -> m (STUArray s Int Int)
inner (UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt UArray Int Int
bord Int
state)
else Int -> m (STUArray s Int Int)
inner Int
state
Int -> ST s (STUArray s Int Int)
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> m (STUArray s Int Int)
loop Int
1)
{-# INLINE kmpBorders #-}
kmpBorders :: S.ByteString -> UArray Int Int
kmpBorders :: ByteString -> UArray Int Int
kmpBorders ByteString
pat = (forall s. ST s (STUArray s Int Int)) -> UArray Int Int
forall i e. (forall s. ST s (STUArray s i e)) -> UArray i e
runSTUArray (do
let !patLen :: Int
patLen = ByteString -> Int
S.length ByteString
pat
{-# INLINE patAt #-}
patAt :: Int -> Word8
patAt :: Int -> Word8
patAt Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
pat Int
i
STUArray s Int Int
ar <- (Int, Int) -> ST s (STUArray s Int Int)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> m (a i e)
newArray_ (Int
0, Int
patLen)
STUArray s Int Int -> Int -> Int -> ST s ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
0 (-Int
1)
let dec :: Word8 -> Int -> m Int
dec Word8
w Int
j
| Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Word8
w Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Word8
patAt Int
j = Int -> m Int
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$! Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1
| Bool
otherwise = STUArray s Int Int -> Int -> m Int
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> m e
unsafeRead STUArray s Int Int
ar Int
j m Int -> (Int -> m Int) -> m Int
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Word8 -> Int -> m Int
dec Word8
w
bordLoop :: Int -> Int -> m (STUArray s Int Int)
bordLoop !Int
i !Int
j
| Int
patLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
i = STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
ar
| Bool
otherwise = do
let !w :: Word8
w = Int -> Word8
patAt (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
Int
j' <- Word8 -> Int -> m Int
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Word8 -> Int -> m Int
dec Word8
w Int
j
if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
patLen Bool -> Bool -> Bool
&& Int -> Word8
patAt Int
j' Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Word8
patAt Int
i
then STUArray s Int Int -> Int -> m Int
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> m e
unsafeRead STUArray s Int Int
ar Int
j' m Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i
else STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i Int
j'
Int -> Int -> m (STUArray s Int Int)
bordLoop (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
j'
Int -> Int -> ST s (STUArray s Int Int)
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> Int -> m (STUArray s Int Int)
bordLoop Int
1 (-Int
1))
{-# INLINE occurs #-}
occurs :: S.ByteString -> UArray Int Int
occurs :: ByteString -> UArray Int Int
occurs ByteString
pat = (forall s. ST s (STUArray s Int Int)) -> UArray Int Int
forall i e. (forall s. ST s (STUArray s i e)) -> UArray i e
runSTUArray (do
let !patEnd :: Int
patEnd = ByteString -> Int
S.length ByteString
pat Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
{-# INLINE patAt #-}
patAt :: Int -> Int
patAt :: Int -> Int
patAt Int
i = Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteString -> Int -> Word8
unsafeIndex ByteString
pat Int
i)
STUArray s Int Int
ar <- (Int, Int) -> Int -> ST s (STUArray s Int Int)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Int
0, Int
255) Int
1
let loop :: Int -> m (STUArray s Int Int)
loop !Int
i
| Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
patEnd = STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
ar
| Bool
otherwise = do
STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar (Int -> Int
patAt Int
i) (-Int
i)
Int -> m (STUArray s Int Int)
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Int -> ST s (STUArray s Int Int)
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> m (STUArray s Int Int)
loop Int
0)
{-# INLINE suffShifts #-}
suffShifts :: S.ByteString -> UArray Int Int
suffShifts :: ByteString -> UArray Int Int
suffShifts ByteString
pat = (forall s. ST s (STUArray s Int Int)) -> UArray Int Int
forall i e. (forall s. ST s (STUArray s i e)) -> UArray i e
runSTUArray (do
let !patLen :: Int
patLen = ByteString -> Int
S.length ByteString
pat
!patEnd :: Int
patEnd = Int
patLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
!suff :: UArray Int Int
suff = ByteString -> UArray Int Int
suffLengths ByteString
pat
STUArray s Int Int
ar <- (Int, Int) -> Int -> ST s (STUArray s Int Int)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Int
0,Int
patEnd) Int
patLen
let preShift :: Int -> Int -> m ()
preShift !Int
idx !Int
j
| Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
| UArray Int Int
suff UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
idx Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 = do
let !shf :: Int
shf = Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
idx
fillToShf :: Int -> m ()
fillToShf !Int
i
| Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
shf = () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
| Bool
otherwise = do
STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i Int
shf
Int -> m ()
fillToShf (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Int -> m ()
forall {m :: * -> *}. MArray (STUArray s) Int m => Int -> m ()
fillToShf Int
j
Int -> Int -> m ()
preShift (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
shf
| Bool
otherwise = Int -> Int -> m ()
preShift (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
j
sufShift :: Int -> m (STUArray s Int Int)
sufShift !Int
idx
| Int
idx Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
patEnd = STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
ar
| Bool
otherwise = do
STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar (Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt UArray Int Int
suff Int
idx) (Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
idx)
Int -> m (STUArray s Int Int)
sufShift (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Int -> Int -> ST s ()
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> Int -> m ()
preShift (Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
0
Int -> ST s (STUArray s Int Int)
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> m (STUArray s Int Int)
sufShift Int
0)
{-# INLINE suffLengths #-}
suffLengths :: S.ByteString -> UArray Int Int
suffLengths :: ByteString -> UArray Int Int
suffLengths ByteString
pat = (forall s. ST s (STUArray s Int Int)) -> UArray Int Int
forall i e. (forall s. ST s (STUArray s i e)) -> UArray i e
runSTUArray (do
let !patLen :: Int
patLen = ByteString -> Int
S.length ByteString
pat
!patEnd :: Int
patEnd = Int
patLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
!preEnd :: Int
preEnd = Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
{-# INLINE patAt #-}
patAt :: Int -> Word8
patAt Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
pat Int
i
!pe :: Word8
pe = Int -> Word8
patAt Int
patEnd
dec :: Int -> Int -> Int
dec !Int
diff !Int
j
| Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int -> Word8
patAt Int
j Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
/= Int -> Word8
patAt (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
diff) = Int
j
| Bool
otherwise = Int -> Int -> Int
dec Int
diff (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
STUArray s Int Int
ar <- (Int, Int) -> ST s (STUArray s Int Int)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> m (a i e)
newArray_ (Int
0, Int
patEnd)
STUArray s Int Int -> Int -> Int -> ST s ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
patEnd Int
patLen
let noSuff :: Int -> m (STUArray s Int Int)
noSuff !Int
i
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
ar
| Int -> Word8
patAt Int
i Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Word8
pe = do
let !diff :: Int
diff = Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i
!nextI :: Int
nextI = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
!prevI :: Int
prevI = Int -> Int -> Int
dec Int
diff Int
nextI
if Int
prevI Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
nextI
then STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i Int
1 m () -> m (STUArray s Int Int) -> m (STUArray s Int Int)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m (STUArray s Int Int)
noSuff Int
nextI
else do STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
prevI)
Int -> Int -> Int -> m (STUArray s Int Int)
suffLoop Int
prevI Int
preEnd Int
nextI
| Bool
otherwise = do
STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
i Int
0
Int -> m (STUArray s Int Int)
noSuff (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
suffLoop :: Int -> Int -> Int -> m (STUArray s Int Int)
suffLoop !Int
pre !Int
end !Int
idx
| Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = STUArray s Int Int -> m (STUArray s Int Int)
forall (m :: * -> *) a. Monad m => a -> m a
return STUArray s Int Int
ar
| Int
pre Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
idx =
if Int -> Word8
patAt Int
idx Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
/= Word8
pe
then STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
idx Int
0 m () -> m (STUArray s Int Int) -> m (STUArray s Int Int)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> Int -> Int -> m (STUArray s Int Int)
suffLoop Int
pre (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
else do
Int
prevS <- STUArray s Int Int -> Int -> m Int
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> m e
unsafeRead STUArray s Int Int
ar Int
end
if Int
pre Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
prevS Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
idx
then do STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
idx Int
prevS
Int -> Int -> Int -> m (STUArray s Int Int)
suffLoop Int
pre (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
else do let !prI :: Int
prI = Int -> Int -> Int
dec (Int
patEnd Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
idx) Int
pre
STUArray s Int Int -> Int -> Int -> m ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
unsafeWrite STUArray s Int Int
ar Int
idx (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
prI)
Int -> Int -> Int -> m (STUArray s Int Int)
suffLoop Int
prI Int
preEnd (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
| Bool
otherwise = Int -> m (STUArray s Int Int)
noSuff Int
idx
Int -> ST s (STUArray s Int Int)
forall {m :: * -> *}.
MArray (STUArray s) Int m =>
Int -> m (STUArray s Int Int)
noSuff Int
preEnd)
{-# INLINE strictify #-}
strictify :: L.ByteString -> S.ByteString
strictify :: ByteString -> ByteString
strictify = [ByteString] -> ByteString
S.concat ([ByteString] -> ByteString)
-> (ByteString -> [ByteString]) -> ByteString -> ByteString
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> [ByteString]
L.toChunks
{-# INLINE ldrop #-}
ldrop :: Int -> [S.ByteString] -> [S.ByteString]
ldrop :: Int -> [ByteString] -> [ByteString]
ldrop Int
_ [] = []
ldrop Int
k (!ByteString
h : [ByteString]
t)
| Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
l = Int -> ByteString -> ByteString
S.drop Int
k ByteString
h ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
t
| Bool
otherwise = Int -> [ByteString] -> [ByteString]
ldrop (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) [ByteString]
t
where
!l :: Int
l = ByteString -> Int
S.length ByteString
h
{-# INLINE ltake #-}
ltake :: Int -> [S.ByteString] -> [S.ByteString]
ltake :: Int -> [ByteString] -> [ByteString]
ltake Int
_ [] = []
ltake !Int
k (!ByteString
h : [ByteString]
t)
| Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
k = ByteString
h ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: Int -> [ByteString] -> [ByteString]
ltake (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) [ByteString]
t
| Bool
otherwise = [Int -> ByteString -> ByteString
S.take Int
k ByteString
h]
where
!l :: Int
l = ByteString -> Int
S.length ByteString
h
{-# INLINE lsplit #-}
lsplit :: Int -> [S.ByteString] -> ([S.ByteString], [S.ByteString])
lsplit :: Int -> [ByteString] -> ([ByteString], [ByteString])
lsplit Int
_ [] = ([],[])
lsplit !Int
k (!ByteString
h : [ByteString]
t)
= case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
k Int
l of
Ordering
LT -> ([Int -> ByteString -> ByteString
S.take Int
k ByteString
h], Int -> ByteString -> ByteString
S.drop Int
k ByteString
h ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
t)
Ordering
EQ -> ([ByteString
h], [ByteString]
t)
Ordering
GT -> let ([ByteString]
u, [ByteString]
v) = Int -> [ByteString] -> ([ByteString], [ByteString])
lsplit (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) [ByteString]
t in (ByteString
h ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
u, [ByteString]
v)
where
!l :: Int
l = ByteString -> Int
S.length ByteString
h
{-# INLINE release #-}
release :: Int -> [S.ByteString] -> [S.ByteString]
release :: Int -> [ByteString] -> [ByteString]
release !Int
deep [ByteString]
_
| Int
deep Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = []
release !Int
deep (!ByteString
x:[ByteString]
xs) = let !rest :: [ByteString]
rest = Int -> [ByteString] -> [ByteString]
release (Int
deepInt -> Int -> Int
forall a. Num a => a -> a -> a
-ByteString -> Int
S.length ByteString
x) [ByteString]
xs in ByteString
x ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
rest
release Int
_ [] = [Char] -> [ByteString]
forall a. HasCallStack => [Char] -> a
error [Char]
"stringsearch.release could not find enough past!"
{-# INLINE keep #-}
keep :: Int -> [S.ByteString] -> ([S.ByteString],[S.ByteString])
keep :: Int -> [ByteString] -> ([ByteString], [ByteString])
keep !Int
deep [ByteString]
xs
| Int
deep Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 = ([],[ByteString]
xs)
keep Int
deep (!ByteString
x:[ByteString]
xs) = let (![ByteString]
p,[ByteString]
d) = Int -> [ByteString] -> ([ByteString], [ByteString])
keep (Int
deep Int -> Int -> Int
forall a. Num a => a -> a -> a
- ByteString -> Int
S.length ByteString
x) [ByteString]
xs in (ByteString
xByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
:[ByteString]
p,[ByteString]
d)
keep Int
_ [] = [Char] -> ([ByteString], [ByteString])
forall a. HasCallStack => [Char] -> a
error [Char]
"Forgot too much"