{-# LANGUAGE BangPatterns, ScopedTypeVariables #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnliftedFFITypes #-}
module Data.Text.Internal.Search
(
indices
) where
import qualified Data.Text.Array as A
import Data.Word (Word64, Word8)
import Data.Text.Internal (Text(..))
import Data.Bits ((.|.), (.&.), unsafeShiftL)
import Data.Text.Internal.ArrayUtils (memchr)
data T = {-# UNPACK #-} !Word64 :* {-# UNPACK #-} !Int
indices :: Text
-> Text
-> [Int]
indices :: Text -> Text -> [Int]
indices needle :: Text
needle@(Text Array
narr Int
noff Int
nlen)
| Int
nlen Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = Word8 -> Text -> [Int]
scanOne (Array -> Int -> Word8
A.unsafeIndex Array
narr Int
noff)
| Int
nlen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = [Int] -> Text -> [Int]
forall a b. a -> b -> a
const []
| Bool
otherwise = Text -> Text -> [Int]
indices' Text
needle
{-# INLINE indices #-}
indices' :: Text -> Text -> [Int]
indices' :: Text -> Text -> [Int]
indices' (Text Array
narr Int
noff Int
nlen) (Text harr :: Array
harr@(A.ByteArray ByteArray#
harr#) Int
hoff Int
hlen) = Int -> [Int]
loop (Int
hoff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nlen)
where
nlast :: Int
nlast = Int
nlen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
!z :: Word8
z = Int -> Word8
nindex Int
nlast
nindex :: Int -> Word8
nindex Int
k = Array -> Int -> Word8
A.unsafeIndex Array
narr (Int
noffInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
k)
buildTable :: Int -> Word64 -> Int -> T
buildTable !Int
i !Word64
msk !Int
skp
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
nlast = (Word64
msk Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.|. Word8 -> Word64
swizzle Word8
z) Word64 -> Int -> T
:* Int
skp
| Bool
otherwise = Int -> Word64 -> Int -> T
buildTable (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Word64
msk Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.|. Word8 -> Word64
swizzle Word8
c) Int
skp'
where !c :: Word8
c = Int -> Word8
nindex Int
i
skp' :: Int
skp' | Word8
c Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Word8
z = Int
nlen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2
| Bool
otherwise = Int
skp
!(Word64
mask :* Int
skip) = Int -> Word64 -> Int -> T
buildTable Int
0 Word64
0 (Int
nlenInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2)
swizzle :: Word8 -> Word64
swizzle :: Word8 -> Word64
swizzle !Word8
k = Word64
1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`unsafeShiftL` (Word8 -> Int
word8ToInt Word8
k Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
0x3f)
loop :: Int -> [Int]
loop !Int
i
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
hlen Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hoff
= []
| Array -> Int -> Word8
A.unsafeIndex Array
harr (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Word8
z
= if Array -> Int -> Array -> Int -> Int -> Bool
A.equal Array
narr Int
noff Array
harr (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
nlen) Int
nlen
then Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
nlen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hoff Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: Int -> [Int]
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nlen)
else Int -> [Int]
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
skip Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
| Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hlen Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hoff
= []
| Word64
mask Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word8 -> Word64
swizzle (Array -> Int -> Word8
A.unsafeIndex Array
harr Int
i) Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0
= Int -> [Int]
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nlen Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
| Bool
otherwise
= case ByteArray# -> Int -> Int -> Word8 -> Int
memchr ByteArray#
harr# Int
i (Int
hlen Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hoff Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) Word8
z of
-1 -> []
Int
x -> Int -> [Int]
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
{-# INLINE indices' #-}
scanOne :: Word8 -> Text -> [Int]
scanOne :: Word8 -> Text -> [Int]
scanOne Word8
c (Text Array
harr Int
hoff Int
hlen) = Int -> [Int]
loop Int
0
where
loop :: Int -> [Int]
loop !Int
i
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
hlen = []
| Array -> Int -> Word8
A.unsafeIndex Array
harr (Int
hoffInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Word8
c = Int
i Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: Int -> [Int]
loop (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
| Bool
otherwise = Int -> [Int]
loop (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
{-# INLINE scanOne #-}
word8ToInt :: Word8 -> Int
word8ToInt :: Word8 -> Int
word8ToInt = Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral