{-# 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 Foreign.C.Types
import GHC.Exts (ByteArray#)
import System.Posix.Types (CSsize(..))
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 forall a. Eq a => a -> a -> Bool
== Int
1 = Word8 -> Text -> [Int]
scanOne (Array -> Int -> Word8
A.unsafeIndex Array
narr Int
noff)
| Int
nlen forall a. Ord a => a -> a -> Bool
<= Int
0 = 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 forall a. Num a => a -> a -> a
+ Int
nlen)
where
nlast :: Int
nlast = Int
nlen 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
noffforall a. Num a => a -> a -> a
+Int
k)
buildTable :: Int -> Word64 -> Int -> T
buildTable !Int
i !Word64
msk !Int
skp
| Int
i forall a. Ord a => a -> a -> Bool
>= Int
nlast = (Word64
msk 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
iforall a. Num a => a -> a -> a
+Int
1) (Word64
msk 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 forall a. Eq a => a -> a -> Bool
== Word8
z = Int
nlen forall a. Num a => a -> a -> a
- Int
i 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
nlenforall a. Num a => a -> a -> a
-Int
2)
swizzle :: Word8 -> Word64
swizzle :: Word8 -> Word64
swizzle !Word8
k = Word64
1 forall a. Bits a => a -> Int -> a
`unsafeShiftL` (Word8 -> Int
word8ToInt Word8
k forall a. Bits a => a -> a -> a
.&. Int
0x3f)
loop :: Int -> [Int]
loop !Int
i
| Int
i forall a. Ord a => a -> a -> Bool
> Int
hlen forall a. Num a => a -> a -> a
+ Int
hoff
= []
| Array -> Int -> Word8
A.unsafeIndex Array
harr (Int
i forall a. Num a => a -> a -> a
- Int
1) 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 forall a. Num a => a -> a -> a
- Int
nlen) Int
nlen
then Int
i forall a. Num a => a -> a -> a
- Int
nlen forall a. Num a => a -> a -> a
- Int
hoff forall a. a -> [a] -> [a]
: Int -> [Int]
loop (Int
i forall a. Num a => a -> a -> a
+ Int
nlen)
else Int -> [Int]
loop (Int
i forall a. Num a => a -> a -> a
+ Int
skip forall a. Num a => a -> a -> a
+ Int
1)
| Int
i forall a. Eq a => a -> a -> Bool
== Int
hlen forall a. Num a => a -> a -> a
+ Int
hoff
= []
| Word64
mask forall a. Bits a => a -> a -> a
.&. Word8 -> Word64
swizzle (Array -> Int -> Word8
A.unsafeIndex Array
harr Int
i) forall a. Eq a => a -> a -> Bool
== Word64
0
= Int -> [Int]
loop (Int
i forall a. Num a => a -> a -> a
+ Int
nlen forall a. Num a => a -> a -> a
+ Int
1)
| Bool
otherwise
= case ByteArray# -> CSize -> CSize -> Word8 -> CSsize
memchr ByteArray#
harr# (Int -> CSize
intToCSize Int
i) (Int -> CSize
intToCSize (Int
hlen forall a. Num a => a -> a -> a
+ Int
hoff forall a. Num a => a -> a -> a
- Int
i)) Word8
z of
-1 -> []
CSsize
x -> Int -> [Int]
loop (Int
i forall a. Num a => a -> a -> a
+ CSsize -> Int
cSsizeToInt CSsize
x 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 forall a. Ord a => a -> a -> Bool
>= Int
hlen = []
| Array -> Int -> Word8
A.unsafeIndex Array
harr (Int
hoffforall a. Num a => a -> a -> a
+Int
i) forall a. Eq a => a -> a -> Bool
== Word8
c = Int
i forall a. a -> [a] -> [a]
: Int -> [Int]
loop (Int
iforall a. Num a => a -> a -> a
+Int
1)
| Bool
otherwise = Int -> [Int]
loop (Int
iforall a. Num a => a -> a -> a
+Int
1)
{-# INLINE scanOne #-}
word8ToInt :: Word8 -> Int
word8ToInt :: Word8 -> Int
word8ToInt = forall a b. (Integral a, Num b) => a -> b
fromIntegral
intToCSize :: Int -> CSize
intToCSize :: Int -> CSize
intToCSize = forall a b. (Integral a, Num b) => a -> b
fromIntegral
cSsizeToInt :: CSsize -> Int
cSsizeToInt :: CSsize -> Int
cSsizeToInt = forall a b. (Integral a, Num b) => a -> b
fromIntegral
foreign import ccall unsafe "_hs_text_memchr" memchr
:: ByteArray# -> CSize -> CSize -> Word8 -> CSsize