    {-# 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 a. [a] -> 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 {a}.
    Num a =>
    Int -> Int -> ByteString -> [ByteString] -> [(a, [Int])]
    search Int
    0 Int
    hLen ByteString
    S.empty
      where
        !hLen :: Int
    hLen = [Int] -> Int
    forall a. Ord a => [a] -> a
    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 a. [a] -> 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 b a. (b -> a -> b) -> b -> [a] -> b
    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] -> [(a, [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] -> [(a, [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 a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    forall {a}.
    Num a =>
    a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast a
    0 [ByteString]
    rest ByteString
    str Int
    h'
                    else a
    -> [ByteString]
    -> ByteString
    -> Int
    -> ByteString
    -> Int
    -> Int
    -> [(a, [Int])]
    forall {a}.
    Num a =>
    a
    -> [ByteString]
    -> ByteString
    -> Int
    -> ByteString
    -> Int
    -> Int
    -> [(a, [Int])]
    past a
    0 [ByteString]
    rest ByteString
    prev Int
    0 ByteString
    str Int
    rm Int
    h'
            where
              !strLen :: Int
    strLen = ByteString -> Int
    S.length ByteString
    str

        noPast :: a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast !a
    prior [ByteString]
    rest !ByteString
    str Int
    hsh = Int -> Int -> [(a, [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 -> [(a, [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' :: a
    prior' = a
    prior a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    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 a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast a
    prior' [ByteString]
    more ByteString
    nxt Int
    h'
                                    else a
    -> [ByteString]
    -> ByteString
    -> Int
    -> ByteString
    -> Int
    -> Int
    -> [(a, [Int])]
    past a
    prior' [ByteString]
    more ByteString
    prev Int
    0 ByteString
    nxt Int
    1 Int
    h'
                    else Int -> Int -> [(a, [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 :: [(a, [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' :: a
    prior' = a
    prior a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    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 a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast a
    prior' [ByteString]
    fut ByteString
    nxt Int
    h'
                                        else a
    -> [ByteString]
    -> ByteString
    -> Int
    -> ByteString
    -> Int
    -> Int
    -> [(a, [Int])]
    past a
    prior' [ByteString]
    fut ByteString
    rst Int
    1 ByteString
    nxt Int
    1 Int
    h'
                          else Int -> Int -> [(a, [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 i. Ix i => Array i ByteString -> Int -> ByteString
    forall (a :: * -> * -> *) e i.
    (IArray a e, Ix i) =>
    a i e -> Int -> e
    `unsafeAt`)) [Int]
    ps of
                        [] -> [(a, [Int])]
    more
                        [Int]
    qs -> Int -> [(a, [Int])] -> [(a, [Int])]
    forall a b. a -> b -> b
    seq ([Int] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [Int]
    qs) ([(a, [Int])] -> [(a, [Int])]) -> [(a, [Int])] -> [(a, [Int])]
    forall a b. (a -> b) -> a -> b
    $
                                (a
    prior a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    sI,[Int]
    qs) (a, [Int]) -> [(a, [Int])] -> [(a, [Int])]
    forall a. a -> [a] -> [a]
    : [(a, [Int])]
    more

        past :: a
    -> [ByteString]
    -> ByteString
    -> Int
    -> ByteString
    -> Int
    -> Int
    -> [(a, [Int])]
    past !a
    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' :: a
    prior' = a
    prior a -> a -> a
    forall a. Num a => a -> a -> a
    - a
    1 a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    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 a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast a
    prior' [ByteString]
    rest ByteString
    curr Int
    hsh
          | Bool
    otherwise = Int -> Int -> Int -> [(a, [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 -> [(a, [Int])]
    go !Int
    h !Int
    p !Int
    s
                | Int
    s Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    hLen = a -> [ByteString] -> ByteString -> Int -> [(a, [Int])]
    noPast a
    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 -> [(a, [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 :: [(a, [Int])]
    more = Int -> Int -> Int -> [(a, [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 i. Ix i => Array i 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
                            [] -> [(a, [Int])]
    more
                            [Int]
    qs -> Int -> [(a, [Int])] -> [(a, [Int])]
    forall a b. a -> b -> b
    seq ([Int] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [Int]
    qs) ([(a, [Int])] -> [(a, [Int])]) -> [(a, [Int])] -> [(a, [Int])]
    forall a b. (a -> b) -> a -> b
    $
                                    (a
    prior a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    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) (a, [Int]) -> [(a, [Int])] -> [(a, [Int])]
    forall a. a -> [a] -> [a]
    : [(a, [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