<commit_before>{-# LANGUAGE ExistentialQuantification, BangPatterns, MagicHash #-}

-- |
-- Module      : Data.Text.Fusion
-- Copyright   : (c) <NAME> 2008-2009,
--               (c) <NAME> 2009,
--               (c) <NAME> 2009
--
-- License     : BSD-style
-- Maintainer  : <EMAIL>, <EMAIL>,
--               <EMAIL>
-- Stability   : experimental
-- Portability : GHC
--
-- Text manipulation functions represented as fusible operations over
-- streams.
module Data.Text.Fusion
    (
    -- * Types
      Stream(..)
    , Step(..)

    -- * Creation and elimination
    , stream
    , unstream

    -- * Basic interface
    , cons
    , snoc
    , append
    , uncons
    , head
    , tail
    , last
    , init
    , null
    , length
    , eq

    -- * Transformations
    , map
    , intercalate
    , intersperse
    , reverse

    -- * Folds
    , foldl
    , foldl'
    , foldl1
    , foldl1'
    , foldr
    , foldr1

    -- ** Special folds
    , concat
    , concatMap
    , any
    , all
    , maximum
    , minimum

    -- * Construction
    -- ** Scans
    , scanl

    -- ** Generation and unfolding
    , replicate
    , unfoldr
    , unfoldrN

    -- * Substrings
    -- ** Breaking strings
    , take
    , drop
    , takeWhile
    , dropWhile

    -- * Searching
    , elem
    , filter

    -- * Indexing
    , find
    , index
    , findIndex
    , elemIndex

    -- * Zipping and unzipping
    , zipWith
    ) where

import Prelude (Bool(..), Char, Either(..), Eq(..), Maybe(..), Monad(..),
                Num(..), Ord(..), String, ($), (++), (.), (&&), error,
                fromIntegral, fst, otherwise, snd)
import Data.Char (ord)
import Control.Monad (liftM2)
import Control.Monad.ST (runST, ST)
import Data.Bits (shiftR, (.&.))
import qualified Data.List as L
import Data.Word (Word16)
import GHC.Exts (Int(..), (+#))
import Data.Text.Internal (Text(..), empty)
import Data.Text.UnsafeChar (unsafeChr)
import qualified Data.Text.Array as A
import qualified Data.Text.Utf16 as U16

default(Int)

infixl 2 :!:
data PairS a b = !a :!: !b

data Switch = S1 | S2

data Stream a = forall s. Stream (s -> Step s a) !s {-# UNPACK #-}!Int

data Step s a = Done
              | Skip !s
              | Yield !a !s

-- | /O(n)/ Convert a Text into a Stream Char.
stream :: Text -> Stream Char
stream (Text arr off len) = Stream next off len
    where
      end = off+len
      {-# INLINE next #-}
      next !i
          | i >= end = Done
          | n >= 0xD800 && n <= 0xDBFF = Yield (U16.chr2 n n2) (i + 2)
          | otherwise = Yield (unsafeChr n) (i + 1)
          where
            n  = A.unsafeIndex arr i
            n2 = A.unsafeIndex arr (i + 1)
{-# INLINE [0] stream #-}

-- | /O(n)/ Convert a Stream Char into a Text.
unstream :: Stream Char -> Text
unstream (Stream next0 s0 len) = Text (fst a) 0 (snd a)
    where
      a = runST (A.unsafeNew len >>= (\arr -> loop arr 0 len s0))
      loop arr !i !top !s
          | i + 1 >= top = case next0 s of
                            Done -> liftM2 (,) (A.unsafeFreeze arr) (return i)
                            _    -> do
                              arr' <- A.unsafeNew (top*2)
                              copy arr arr' >> loop arr' i (top*2) s
          | otherwise = case next0 s of
               Done       -> liftM2 (,) (A.unsafeFreeze arr) (return i)
               Skip s'    -> loop arr i top s'
               Yield x s'
                   | n < 0x10000 -> do
                        A.unsafeWrite arr i (fromIntegral n)
                        loop arr (i+1) top s'
                   | otherwise   -> do
                        A.unsafeWrite arr i       l
                        A.unsafeWrite arr (i + 1) r
                        loop arr (i+2) top s'
                   where
                     n = ord x
                     m = n - 0x10000
                     l = fromIntegral $ (m `shiftR` 10) + 0xD800
                     r = fromIntegral $ (m .&. 0x3FF) + 0xDC00
{-# INLINE [0] unstream #-}
{-# RULES "STREAM stream/unstream fusion" forall s. stream (unstream s) = s #-}


copy :: A.MArray s Word16 -> A.MArray s Word16 -> ST s ()
copy src dest = copy_loop 0
    where
      len = A.length src
      copy_loop i
          | i > len   = return ()
          | otherwise = do A.unsafeRead src i >>= A.unsafeWrite dest i
                           copy_loop (i+1)

-- | /O(n)/ Determines if two streams are equal.
eq :: Ord a => Stream a -> Stream a -> Bool
eq (Stream next1 s1 _) (Stream next2 s2 _) = cmp (next1 s1) (next2 s2)
    where
      cmp Done Done = True
      cmp Done _    = False
      cmp _    Done = False
      cmp (Skip s1')     (Skip s2')     = cmp (next1 s1') (next2 s2')
      cmp (Skip s1')     x2             = cmp (next1 s1') x2
      cmp x1             (Skip s2')     = cmp x1          (next2 s2')
      cmp (Yield x1 s1') (Yield x2 s2') = x1 == x2 &&<commit_msg>Fix bounds check in copy code<commit_after>{-# LANGUAGE ExistentialQuantification, BangPatterns, MagicHash #-}

-- |
-- Module      : Data.Text.Fusion
-- Copyright   : (c) <NAME> 2008-2009,
--               (c) <NAME> 2009,
--               (c) <NAME> 2009
--
-- License     : BSD-style
-- Maintainer  : <EMAIL>, <EMAIL>,
--               <EMAIL>
-- Stability   : experimental
-- Portability : GHC
--
-- Text manipulation functions represented as fusible operations over
-- streams.
module Data.Text.Fusion
    (
    -- * Types
      Stream(..)
    , Step(..)

    -- * Creation and elimination
    , stream
    , unstream

    -- * Basic interface
    , cons
    , snoc
    , append
    , uncons
    , head
    , tail
    , last
    , init
    , null
    , length
    , eq

    -- * Transformations
    , map
    , intercalate
    , intersperse
    , reverse

    -- * Folds
    , foldl
    , foldl'
    , foldl1
    , foldl1'
    , foldr
    , foldr1

    -- ** Special folds
    , concat
    , concatMap
    , any
    , all
    , maximum
    , minimum

    -- * Construction
    -- ** Scans
    , scanl

    -- ** Generation and unfolding
    , replicate
    , unfoldr
    , unfoldrN

    -- * Substrings
    -- ** Breaking strings
    , take
    , drop
    , takeWhile
    , dropWhile

    -- * Searching
    , elem
    , filter

    -- * Indexing
    , find
    , index
    , findIndex
    , elemIndex

    -- * Zipping and unzipping
    , zipWith
    ) where

import Prelude (Bool(..), Char, Either(..), Eq(..), Maybe(..), Monad(..),
                Num(..), Ord(..), String, ($), (++), (.), (&&), error,
                fromIntegral, fst, otherwise, snd)
import Data.Char (ord)
import Control.Monad (liftM2)
import Control.Monad.ST (runST, ST)
import Data.Bits (shiftR, (.&.))
import qualified Data.List as L
import Data.Word (Word16)
import GHC.Exts (Int(..), (+#))
import Data.Text.Internal (Text(..), empty)
import Data.Text.UnsafeChar (unsafeChr)
import qualified Data.Text.Array as A
import qualified Data.Text.Utf16 as U16

default(Int)

infixl 2 :!:
data PairS a b = !a :!: !b

data Switch = S1 | S2

data Stream a = forall s. Stream (s -> Step s a) !s {-# UNPACK #-}!Int

data Step s a = Done
              | Skip !s
              | Yield !a !s

-- | /O(n)/ Convert a Text into a Stream Char.
stream :: Text -> Stream Char
stream (Text arr off len) = Stream next off len
    where
      end = off+len
      {-# INLINE next #-}
      next !i
          | i >= end = Done
          | n >= 0xD800 && n <= 0xDBFF = Yield (U16.chr2 n n2) (i + 2)
          | otherwise = Yield (unsafeChr n) (i + 1)
          where
            n  = A.unsafeIndex arr i
            n2 = A.unsafeIndex arr (i + 1)
{-# INLINE [0] stream #-}

-- | /O(n)/ Convert a Stream Char into a Text.
unstream :: Stream Char -> Text
unstream (Stream next0 s0 len) = Text (fst a) 0 (snd a)
    where
      a = runST (A.unsafeNew len >>= (\arr -> loop arr 0 len s0))
      loop arr !i !top !s
          | i + 1 >= top = case next0 s of
                            Done -> liftM2 (,) (A.unsafeFreeze arr) (return i)
                            _    -> do
                              arr' <- A.unsafeNew (top*2)
                              copy arr arr' >> loop arr' i (top*2) s
          | otherwise = case next0 s of
               Done       -> liftM2 (,) (A.unsafeFreeze arr) (return i)
               Skip s'    -> loop arr i top s'
               Yield x s'
                   | n < 0x10000 -> do
                        A.unsafeWrite arr i (fromIntegral n)
                        loop arr (i+1) top s'
                   | otherwise   -> do
                        A.unsafeWrite arr i       l
                        A.unsafeWrite arr (i + 1) r
                        loop arr (i+2) top s'
                   where
                     n = ord x
                     m = n - 0x10000
                     l = fromIntegral $ (m `shiftR` 10) + 0xD800
                     r = fromIntegral $ (m .&. 0x3FF) + 0xDC00
{-# INLINE [0] unstream #-}
{-# RULES "STREAM stream/unstream fusion" forall s. stream (unstream s) = s #-}


copy :: A.MArray s Word16 -> A.MArray s Word16 -> ST s ()
copy src dest = copy_loop 0
    where
      len = A.length src
      copy_loop i
          | i >= len   = return ()
          | otherwise = do A.unsafeRead src i >>= A.unsafeWrite dest i
                           copy_loop (i+1)

-- | /O(n)/ Determines if two streams are equal.
eq :: Ord a => Stream a -> Stream a -> Bool
eq (Stream next1 s1 _) (Stream next2 s2 _) = cmp (next1 s1) (next2 s2)
    where
      cmp Done Done = True
      cmp Done _    = False
      cmp _    Done = False
      cmp (Skip s1')     (Skip s2')     = cmp (next1 s1') (next2 s2')
      cmp (Skip s1')     x2             = cmp (next1 s1') x2
      cmp x1             (Skip s2')     = cmp x1          (next2 s2')
      cmp (Yield x1 s1') (Yield x2 s2') = x1 == x2 &&
{'fraction_non_alphanumeric': 0.1281265952016335, 'fraction_numerical': 0.024093925472179683, 'mean_word_length': 1.4271555996035679, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 65, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3054866', 'n_tokens_mistral': 3440, 'n_tokens_neox': 3185, 'n_words': 1029}