{-# LANGUAGE BangPatterns #-}
-- |
-- Module         : Data.ByteString.Lazy.Search.KarpRabin
-- Copyright      : (c) 2010 Daniel Fischer
-- Licence        : BSD3
-- Maintainer     : Daniel Fischer <daniel.is.fischer@googlemail.com>
-- Stability      : Provisional
-- Portability    : non-portable (BangPatterns)
--
-- Simultaneous search for multiple patterns in a lazy 'L.ByteString'
-- using the Karp-Rabin algorithm.
--
-- A description of the algorithm for a single pattern can be found at
-- <http://www-igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050>.
module Data.ByteString.Lazy.Search.KarpRabin ( -- * Overview
                                               -- $overview

                                               -- ** Caution
                                               -- $caution

                                               -- * Function
                                               indicesOfAny
                                             ) where

import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import Data.ByteString.Unsafe (unsafeIndex)

import qualified Data.IntMap as IM

import Data.Array
import Data.Array.Base (unsafeAt)

import Data.Word (Word8)
import Data.Int (Int64)
import Data.Bits
import Data.List (foldl')

-- $overview
--
-- The Karp-Rabin algorithm works by calculating a hash of the pattern and
-- comparing that hash with the hash of a slice of the target string with
-- the same length as the pattern. If the hashes are equal, the slice of the
-- target is compared to the pattern character by character (since the hash
-- function generally isn't injective).
--
-- For a single pattern, this tends to be more efficient than the na&#239;ve
-- algorithm, but it cannot compete with algorithms like
-- Knuth-Morris-Pratt or Boyer-Moore.
--
-- However, the algorithm can be generalised to search for multiple patterns
-- simultaneously. If the shortest pattern has length @k@, hash the prefix of
-- length @k@ of all patterns and compare the hash of the target's slices of
-- length @k@ to them. If there's a match, check whether the slice is part
-- of an occurrence of the corresponding pattern.
--
-- With a hash-function that
--
--   * allows to compute the hash of one slice in constant time from the hash
--     of the previous slice, the new and the dropped character, and
--
--   * produces few spurious matches,
--
-- searching for occurrences of any of @n@ patterns has a best-case complexity
-- of /O/(@targetLength@ * @lookup n@). The worst-case complexity is
-- /O/(@targetLength@ * @lookup n@ * @sum patternLengths@), the average is
-- not much worse than the best case.
--
-- The functions in this module store the hashes of the patterns in an
-- 'IM.IntMap', so the lookup is /O/(@log n@). Re-hashing is done in constant
-- time and spurious matches of the hashes /should be/ sufficiently rare.
-- The maximal length of the prefixes to be hashed is 32.

-- $caution
--
-- Unfortunately, the constant factors are high, so these functions are slow.
-- Unless the number of patterns to search for is high (larger than 50 at
-- least), repeated search for single patterns using Boyer-Moore or DFA and
-- manual merging of the indices is faster. /Much/ faster for less than 40
-- or so patterns.
--
-- 'indicesOfAny' has the advantage over multiple single-pattern searches that
-- it doesn't hold on to large parts of the string (which is likely to happen
-- for multiple searches), however, so in contrast to the strict version, it
-- may be useful for relatively few patterns already.
--
-- Nevertheless, this module seems more of an interesting curiosity than
-- anything else.

-- | @'indicesOfAny'@ finds all occurrences of any of several non-empty strict
--   patterns in a lazy target string. If no non-empty patterns are given,
--   the result is an empty list. Otherwise the result list contains
--   the pairs of all indices where any of the (non-empty) patterns start
--   and the list of all patterns starting at that index, the patterns being
--   represented by their (zero-based) position in the pattern list.
--   Empty patterns are filtered out before processing begins.
{-# INLINE indicesOfAny #-}
indicesOfAny :: [S.ByteString]  -- ^ List of non-empty patterns
             -> L.ByteString    -- ^ String to search
             -> [(Int64,[Int])]   -- ^ List of matches
indicesOfAny :: [ByteString] -> ByteString -> [(Int64, [Int])]
indicesOfAny [ByteString]
pats
    | [ByteString] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [ByteString]
nepats   = [(Int64, [Int])] -> ByteString -> [(Int64, [Int])]
forall a b. a -> b -> a
const []
    | Bool
otherwise     = [ByteString] -> [ByteString] -> [(Int64, [Int])]
lazyMatcher [ByteString]
nepats ([ByteString] -> [(Int64, [Int])])
-> (ByteString -> [ByteString]) -> ByteString -> [(Int64, [Int])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> [ByteString]
L.toChunks
      where
        nepats :: [ByteString]
nepats = (ByteString -> Bool) -> [ByteString] -> [ByteString]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (ByteString -> Bool) -> ByteString -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> Bool
S.null) [ByteString]
pats

------------------------------------------------------------------------------
--                                 Workers                                 --
------------------------------------------------------------------------------

{-# INLINE rehash1 #-}
rehash1 :: Int -> Int -> Word8 -> Word8 -> Int
rehash1 :: Int -> Int -> Word8 -> Word8 -> Int
rehash1 Int
out Int
h Word8
o Word8
n =
    (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n

{-# INLINE rehash2 #-}
rehash2 :: Int -> Int -> Word8 -> Word8 -> Int
rehash2 :: Int -> Int -> Word8 -> Word8 -> Int
rehash2 Int
out Int
h Word8
o Word8
n =
    (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n

{-# INLINE rehash3 #-}
rehash3 :: Int -> Int -> Word8 -> Word8 -> Int
rehash3 :: Int -> Int -> Word8 -> Word8 -> Int
rehash3 Int
out Int
h Word8
o Word8
n =
    (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
3 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n

{-# INLINE rehash4 #-}
rehash4 :: Int -> Int -> Word8 -> Word8 -> Int
rehash4 :: Int -> Int -> Word8 -> Word8 -> Int
rehash4 Int
out Int
h Word8
o Word8
n =
    (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n

lazyMatcher :: [S.ByteString] -> [S.ByteString] -> [(Int64,[Int])]
lazyMatcher :: [ByteString] -> [ByteString] -> [(Int64, [Int])]
lazyMatcher [ByteString]
pats = Int -> Int -> ByteString -> [ByteString] -> [(Int64, [Int])]
forall {t}.
Num t =>
Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
0 Int
hLen ByteString
S.empty
  where
    !hLen :: Int
hLen = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum (Int
32 Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: (ByteString -> Int) -> [ByteString] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map ByteString -> Int
S.length [ByteString]
pats)
    !shDi :: Int
shDi = case Int
32 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
hLen of
              Int
q | Int
q Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
4 -> Int
q
                | Bool
otherwise -> Int
4
    !outS :: Int
outS = Int
shDiInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
hLen
    !patNum :: Int
patNum = [ByteString] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [ByteString]
pats
    !patArr :: Array Int ByteString
patArr = (Int, Int) -> [ByteString] -> Array Int ByteString
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0, Int
patNum Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [ByteString]
pats
    {-# INLINE rehash #-}
    rehash :: Int -> Word8 -> Word8 -> Int
    rehash :: Int -> Word8 -> Word8 -> Int
rehash = case Int
shDi of
                Int
1 -> Int -> Int -> Word8 -> Word8 -> Int
rehash1 Int
hLen
                Int
2 -> Int -> Int -> Word8 -> Word8 -> Int
rehash2 Int
outS
                Int
3 -> Int -> Int -> Word8 -> Word8 -> Int
rehash3 Int
outS
                Int
_ -> Int -> Int -> Word8 -> Word8 -> Int
rehash4 Int
outS
    hash :: S.ByteString -> Int
    hash :: ByteString -> Int
hash = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
h Word8
w -> (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
shDi) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
0 (ByteString -> Int)
-> (ByteString -> ByteString) -> ByteString -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ByteString -> ByteString
S.take Int
hLen
    !hashMap :: IntMap [Int]
hashMap =
        (IntMap [Int] -> (Int, Int) -> IntMap [Int])
-> IntMap [Int] -> [(Int, Int)] -> IntMap [Int]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntMap [Int]
mp (Int
h,Int
i) -> ([Int] -> [Int] -> [Int])
-> Int -> [Int] -> IntMap [Int] -> IntMap [Int]
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IM.insertWith (([Int] -> [Int] -> [Int]) -> [Int] -> [Int] -> [Int]
forall a b c. (a -> b -> c) -> b -> a -> c
flip [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
(++)) Int
h [Int
i] IntMap [Int]
mp) IntMap [Int]
forall a. IntMap a
IM.empty ([(Int, Int)] -> IntMap [Int]) -> [(Int, Int)] -> IntMap [Int]
forall a b. (a -> b) -> a -> b
$
                                [Int] -> [Int] -> [(Int, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip ((ByteString -> Int) -> [ByteString] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map ByteString -> Int
hash [ByteString]
pats) [Int
0 :: Int .. ]
    search :: Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
_ Int
_ ByteString
_ [] = []
    search !Int
h !Int
rm !ByteString
prev (!ByteString
str : [ByteString]
rest)
      | Int
strLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
rm =
          let !h' :: Int
h' = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
o Word8
w -> (Int
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
h ByteString
str
              !prev' :: ByteString
prev' = ByteString -> ByteString -> ByteString
S.append ByteString
prev ByteString
str
          in Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
h' (Int
rm Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
strLen) ByteString
prev' [ByteString]
rest
      | Bool
otherwise =
          let !h' :: Int
h' = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
o Word8
w -> (Int
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
h
                                                (Int -> ByteString -> ByteString
S.take Int
rm ByteString
str)
          in if ByteString -> Bool
S.null ByteString
prev
                then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
forall {t}.
Num t =>
t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
0 [ByteString]
rest ByteString
str Int
h'
                else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
forall {t}.
Num t =>
t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
0 [ByteString]
rest ByteString
prev Int
0 ByteString
str Int
rm Int
h'
        where
          !strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str

    noPast :: t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast !t
prior [ByteString]
rest !ByteString
str Int
hsh = Int -> Int -> [(t, [Int])]
go Int
hsh Int
0
      where
        !strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str
        !maxIdx :: Int
maxIdx = Int
strLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen
        {-# INLINE strAt #-}
        strAt :: Int -> Word8
strAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
str Int
i
        go :: Int -> Int -> [(t, [Int])]
go !Int
h Int
sI =
          case Int -> IntMap [Int] -> Maybe [Int]
forall a. Int -> IntMap a -> Maybe a
IM.lookup Int
h IntMap [Int]
hashMap of
            Maybe [Int]
Nothing ->
              if Int
sI Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxIdx
                then case [ByteString]
rest of
                        [] -> []
                        (ByteString
nxt : [ByteString]
more) ->
                          let !h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
strAt Int
sI) (ByteString -> Int -> Word8
unsafeIndex ByteString
nxt Int
0)
                              !prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
strLen
                              !prev :: ByteString
prev = Int -> ByteString -> ByteString
S.drop (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) ByteString
str
                          in if Int
hLen Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
                                then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
more ByteString
nxt Int
h'
                                else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
prior' [ByteString]
more ByteString
prev Int
0 ByteString
nxt Int
1 Int
h'
                else Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
strAt Int
sI) (Int -> Word8
strAt (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hLen))) (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
            Just [Int]
ps ->
              let !rst :: ByteString
rst = Int -> ByteString -> ByteString
S.drop Int
sI ByteString
str
                  !rLen :: Int
rLen = Int
strLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
sI
                  {-# INLINE hd #-}
                  hd :: Word8
hd = Int -> Word8
strAt Int
sI
                  {-# INLINE more #-}
                  more :: [(t, [Int])]
more =
                    if Int
sI Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxIdx
                      then case [ByteString]
rest of
                            [] -> []
                            (ByteString
nxt : [ByteString]
fut) ->
                              let !h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h Word8
hd (ByteString -> Int -> Word8
unsafeIndex ByteString
nxt Int
0)
                                  !prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
strLen
                              in if Int
hLen Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
                                    then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
fut ByteString
nxt Int
h'
                                    else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
prior' [ByteString]
fut ByteString
rst Int
1 ByteString
nxt Int
1 Int
h'
                      else Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h Word8
hd (Int -> Word8
strAt (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hLen))) (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
                  okay :: ByteString -> Bool
okay ByteString
bs
                    | Int
rLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< ByteString -> Int
S.length ByteString
bs = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
rst ByteString
bs Bool -> Bool -> Bool
&&
                            ByteString -> [ByteString] -> Bool
checkFut (Int -> ByteString -> ByteString
S.drop Int
rLen ByteString
bs) [ByteString]
rest
                    | Bool
otherwise = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
bs ByteString
rst
              in case (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (ByteString -> Bool
okay (ByteString -> Bool) -> (Int -> ByteString) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Array Int ByteString
patArr Array Int ByteString -> Int -> ByteString
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt`)) [Int]
ps of
                    [] -> [(t, [Int])]
more
                    [Int]
qs -> Int -> [(t, [Int])] -> [(t, [Int])]
seq ([Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
qs) ([(t, [Int])] -> [(t, [Int])]) -> [(t, [Int])] -> [(t, [Int])]
forall a b. (a -> b) -> a -> b
$
                            (t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sI,[Int]
qs) (t, [Int]) -> [(t, [Int])] -> [(t, [Int])]
forall a. a -> [a] -> [a]
: [(t, [Int])]
more

    past :: t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past !t
prior [ByteString]
rest !ByteString
prev !Int
pI !ByteString
str !Int
sI !Int
hsh
      | Int
strLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
4040 =
        let !prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
- t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen)
            !curr :: ByteString
curr   = ByteString -> ByteString -> ByteString
S.append (Int -> ByteString -> ByteString
S.drop Int
pI ByteString
prev) ByteString
str
        in t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
rest ByteString
curr Int
hsh
      | Bool
otherwise = Int -> Int -> Int -> [(t, [Int])]
go Int
hsh Int
pI Int
sI
        where
          !strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str
          {-# INLINE strAt #-}
          strAt :: Int -> Word8
strAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
str Int
i
          {-# INLINE prevAt #-}
          prevAt :: Int -> Word8
prevAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
prev Int
i
          go :: Int -> Int -> Int -> [(t, [Int])]
go !Int
h !Int
p !Int
s
            | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hLen = t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior [ByteString]
rest ByteString
str Int
h
            | Bool
otherwise =
              case Int -> IntMap [Int] -> Maybe [Int]
forall a. Int -> IntMap a -> Maybe a
IM.lookup Int
h IntMap [Int]
hashMap of
                Maybe [Int]
Nothing ->
                  let {-# INLINE h' #-}
                      h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
prevAt Int
p) (Int -> Word8
strAt Int
s)
                  in Int -> Int -> Int -> [(t, [Int])]
go Int
h' (Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
                Just [Int]
ps ->
                  let !prst :: ByteString
prst = Int -> ByteString -> ByteString
S.drop Int
p ByteString
prev
                      {-# INLINE more #-}
                      more :: [(t, [Int])]
more = Int -> Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
prevAt Int
p) (Int -> Word8
strAt Int
s)) (Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
                      okay :: ByteString -> Bool
okay ByteString
bs = ByteString -> [ByteString] -> Bool
checkFut ByteString
bs (ByteString
prst ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: ByteString
str ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
rest)
                  in case (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (ByteString -> Bool
okay (ByteString -> Bool) -> (Int -> ByteString) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Array Int ByteString -> Int -> ByteString
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt Array Int ByteString
patArr)) [Int]
ps of
                        [] -> [(t, [Int])]
more
                        [Int]
qs -> Int -> [(t, [Int])] -> [(t, [Int])]
seq ([Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
qs) ([(t, [Int])] -> [(t, [Int])]) -> [(t, [Int])] -> [(t, [Int])]
forall a b. (a -> b) -> a -> b
$
                                (t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen), [Int]
qs) (t, [Int]) -> [(t, [Int])] -> [(t, [Int])]
forall a. a -> [a] -> [a]
: [(t, [Int])]
more

{-# INLINE checkFut #-}
checkFut :: S.ByteString -> [S.ByteString] -> Bool
checkFut :: ByteString -> [ByteString] -> Bool
checkFut ByteString
_ [] = Bool
False
checkFut !ByteString
bs (!ByteString
h : [ByteString]
t)
    | Int
hLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< ByteString -> Int
S.length ByteString
bs = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
h ByteString
bs Bool -> Bool -> Bool
&& ByteString -> [ByteString] -> Bool
checkFut (Int -> ByteString -> ByteString
S.drop Int
hLen ByteString
bs) [ByteString]
t
    | Bool
otherwise = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
bs ByteString
h
      where
        !hLen :: Int
hLen = ByteString -> Int
S.length ByteString
h