{-# LANGUAGE BangPatterns, MagicHash, Rank2Types, PartialTypeSignatures #-}
{-# OPTIONS_GHC -Wno-partial-type-signatures #-}
-- |
-- Module      : Data.Text.Internal.Fusion.Common
-- Copyright   : (c) Bryan O'Sullivan 2009, 2012
--
-- License     : BSD-style
-- Maintainer  : bos@serpentine.com
-- Stability   : experimental
-- Portability : GHC
--
-- /Warning/: this is an internal module, and does not have a stable
-- API or name. Functions in this module may not check or enforce
-- preconditions expected by public modules. Use at your own risk!
--
-- This module provides a common stream fusion interface for text.
-- The stream interface allows us to write text pipelines which
-- do not allocate intermediate text values. For example, we could
-- guarantee no intermediate text is allocated by writing the following:
--
-- @
--   getNucleotides :: 'Data.Text.Internal.Text' -> 'Data.Text.Internal.Text'
--   getNucleotides =
--         'Data.Text.Internal.Fusion.unstream'
--       . 'filter' isNucleotide
--       . 'toLower'
--       . 'Data.Text.Internal.Fusion.stream'
--     where
--       isNucleotide chr =
--         chr == \'a\' ||
--         chr == \'c\' ||
--         chr == \'t\' ||
--         chr == \'g\'
-- @

module Data.Text.Internal.Fusion.Common
    (
    -- * Creation and elimination
      singleton
    , streamList
    , unstreamList
    , streamCString#

    -- * Basic interface
    , cons
    , snoc
    , append
    , head
    , uncons
    , last
    , tail
    , init
    , null
    , lengthI
    , compareLengthI
    , isSingleton

    -- * Transformations
    , map
    , intercalate
    , intersperse

    -- ** Case conversion
    -- $case
    , toCaseFold
    , toLower
    , toTitle
    , toUpper

    -- ** Justification
    , justifyLeftI

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

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

    -- * Construction
    -- ** Scans
    , scanl

    -- ** Generation and unfolding
    , replicateCharI
    , replicateI
    , unfoldr
    , unfoldrNI

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

    -- * Predicates
    , isPrefixOf

    -- * Searching
    , elem
    , filter

    -- * Indexing
    , findBy
    , indexI
    , findIndexI
    , countCharI

    -- * Zipping and unzipping
    , zipWith
    ) where

import Prelude (Bool(..), Char, Eq, (==), Int, Integral, Maybe(..),
                Ord(..), Ordering(..), String, (.), ($), (+), (-), (*), (++),
                (&&), fromIntegral, otherwise)
import qualified Data.List as L
import qualified Prelude as P
import Data.Bits (shiftL, shiftR, (.&.))
import Data.Char (isLetter, isSpace)
import GHC.Int (Int64(..))
import Data.Text.Internal.Encoding.Utf8 (chr2, chr3, chr4, utf8LengthByLeader)
import Data.Text.Internal.Fusion.Types
import Data.Text.Internal.Fusion.CaseMapping (foldMapping, lowerMapping, titleMapping,
                                     upperMapping)
import Data.Text.Internal.Fusion.Size
import GHC.Exts (Char(..), Char#, chr#)
import GHC.Prim (Addr#, indexWord8OffAddr#)
import GHC.Stack (HasCallStack)
import GHC.Types (Int(..))
import Data.Text.Internal.Unsafe.Char (unsafeChr8)
import GHC.Word

-- | /O(1)/ Convert a character into a 'Stream'
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'singleton' = 'Data.Text.singleton'@
singleton :: Char -> Stream Char
singleton :: Char -> Stream Char
singleton Char
c = (Bool -> Step Bool Char) -> Bool -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Bool -> Step Bool Char
next Bool
False (Int -> Size
codePointsSize Int
1)
    where next :: Bool -> Step Bool Char
next Bool
False = Char -> Bool -> Step Bool Char
forall s a. a -> s -> Step s a
Yield Char
c Bool
True
          next Bool
True  = Step Bool Char
forall s a. Step s a
Done
{-# INLINE [0] singleton #-}

-- | /O(n)/ Convert a list into a 'Stream'.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'streamList' = 'Data.Text.pack'@
streamList :: [a] -> Stream a
{-# INLINE [0] streamList #-}
streamList :: forall a. [a] -> Stream a
streamList [a]
s  = ([a] -> Step [a] a) -> [a] -> Size -> Stream a
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream [a] -> Step [a] a
forall {a}. [a] -> Step [a] a
next [a]
s Size
unknownSize
    where next :: [a] -> Step [a] a
next []       = Step [a] a
forall s a. Step s a
Done
          next (a
x:[a]
xs)   = a -> [a] -> Step [a] a
forall s a. a -> s -> Step s a
Yield a
x [a]
xs

-- | /O(n)/ Convert a 'Stream' into a list.
--
-- __Properties__
--
-- @'unstreamList' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.unpack'@
unstreamList :: Stream a -> [a]
unstreamList :: forall a. Stream a -> [a]
unstreamList (Stream s -> Step s a
next s
s0 Size
_len) = s -> [a]
unfold s
s0
    where unfold :: s -> [a]
unfold !s
s = case s -> Step s a
next s
s of
                        Step s a
Done       -> []
                        Skip s
s'    -> s -> [a]
unfold s
s'
                        Yield a
x s
s' -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: s -> [a]
unfold s
s'
{-# INLINE [0] unstreamList #-}

{-# RULES "STREAM streamList/unstreamList fusion" forall s. streamList (unstreamList s) = s #-}

-- | Stream the UTF-8-like packed encoding used by GHC to represent
-- constant strings in generated code.
--
-- This encoding uses the byte sequence "\xc0\x80" to represent NUL,
-- and the string is NUL-terminated.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.Fusion.unstream' . 'streamCString#' addr# = 'Data.Text.Show.unpackCString#' addr#@
streamCString# :: Addr# -> Stream Char
streamCString# :: Addr# -> Stream Char
streamCString# Addr#
addr = (Int -> Step Int Char) -> Int -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Int -> Step Int Char
step Int
0 Size
unknownSize
  where
    step :: Int -> Step Int Char
step !Int
i
        | Word8
b Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== Word8
0    = Step Int Char
forall s a. Step s a
Done
        | Bool
otherwise = Char -> Int -> Step Int Char
forall s a. a -> s -> Step s a
Yield Char
chr (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
l)
      where b :: Word8
b = Int -> Word8
at# Int
i
            l :: Int
l = Word8 -> Int
utf8LengthByLeader Word8
b
            next :: Int -> Word8
next Int
n = Int -> Word8
at# (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n)
            chr :: Char
chr = case Int
l of
              Int
1 -> Word8 -> Char
unsafeChr8 Word8
b
              Int
2 -> Word8 -> Word8 -> Char
chr2 Word8
b (Int -> Word8
next Int
1)
              Int
3 -> Word8 -> Word8 -> Word8 -> Char
chr3 Word8
b (Int -> Word8
next Int
1) (Int -> Word8
next Int
2)
              Int
_ -> Word8 -> Word8 -> Word8 -> Word8 -> Char
chr4 Word8
b (Int -> Word8
next Int
1) (Int -> Word8
next Int
2) (Int -> Word8
next Int
3)
    at# :: Int -> Word8
at# (I# Int#
i#) = Word8# -> Word8
W8# (Addr# -> Int# -> Word8#
indexWord8OffAddr# Addr#
addr Int#
i#)
{-# INLINE [0] streamCString# #-}

-- ----------------------------------------------------------------------------
-- * Basic stream functions

data C s = C0 !s
         | C1 !s

-- | /O(n)/ Adds a character to the front of a Stream Char.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.Fusion.unstream' . 'cons' c . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.cons' c @
cons :: Char -> Stream Char -> Stream Char
cons :: Char -> Stream Char -> Stream Char
cons !Char
w (Stream s -> Step s Char
next0 s
s0 Size
len) = (C s -> Step (C s) Char) -> C s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream C s -> Step (C s) Char
next (s -> C s
forall s. s -> C s
C1 s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Int -> Size
codePointsSize Int
1)
    where
      next :: C s -> Step (C s) Char
next (C1 s
s) = Char -> C s -> Step (C s) Char
forall s a. a -> s -> Step s a
Yield Char
w (s -> C s
forall s. s -> C s
C0 s
s)
      next (C0 s
s) = case s -> Step s Char
next0 s
s of
                          Step s Char
Done -> Step (C s) Char
forall s a. Step s a
Done
                          Skip s
s' -> C s -> Step (C s) Char
forall s a. s -> Step s a
Skip (s -> C s
forall s. s -> C s
C0 s
s')
                          Yield Char
x s
s' -> Char -> C s -> Step (C s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> C s
forall s. s -> C s
C0 s
s')
{-# INLINE [0] cons #-}

data Snoc a = N
            | J !a

-- | /O(n)/ Adds a character to the end of a stream.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.Fusion.unstream' . 'snoc' c . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.snoc' c @
snoc :: Stream Char -> Char -> Stream Char
snoc :: Stream Char -> Char -> Stream Char
snoc (Stream s -> Step s Char
next0 s
xs0 Size
len) Char
w = (Snoc s -> Step (Snoc s) Char) -> Snoc s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Snoc s -> Step (Snoc s) Char
next (s -> Snoc s
forall a. a -> Snoc a
J s
xs0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Int -> Size
codePointsSize Int
1)
  where
    next :: Snoc s -> Step (Snoc s) Char
next (J s
xs) = case s -> Step s Char
next0 s
xs of
      Step s Char
Done        -> Char -> Snoc s -> Step (Snoc s) Char
forall s a. a -> s -> Step s a
Yield Char
w Snoc s
forall a. Snoc a
N
      Skip s
xs'    -> Snoc s -> Step (Snoc s) Char
forall s a. s -> Step s a
Skip    (s -> Snoc s
forall a. a -> Snoc a
J s
xs')
      Yield Char
x s
xs' -> Char -> Snoc s -> Step (Snoc s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> Snoc s
forall a. a -> Snoc a
J s
xs')
    next Snoc s
N = Step (Snoc s) Char
forall s a. Step s a
Done
{-# INLINE [0] snoc #-}

data E l r = L !l
           | R !r

-- | /O(n)/ Appends one Stream to the other.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.Fusion.unstream' ('append' ('Data.Text.Internal.Fusion.stream' t1) ('Data.Text.Internal.Fusion.stream' t2)) = 'Data.Text.append' t1 t2@
append :: Stream Char -> Stream Char -> Stream Char
append :: Stream Char -> Stream Char -> Stream Char
append (Stream s -> Step s Char
next0 s
s01 Size
len1) (Stream s -> Step s Char
next1 s
s02 Size
len2) =
    (E s s -> Step (E s s) Char) -> E s s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream E s s -> Step (E s s) Char
next (s -> E s s
forall l r. l -> E l r
L s
s01) (Size
len1 Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
len2)
    where
      next :: E s s -> Step (E s s) Char
next (L s
s1) = case s -> Step s Char
next0 s
s1 of
                         Step s Char
Done        -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. r -> E l r
R s
s02)
                         Skip s
s1'    -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. l -> E l r
L s
s1')
                         Yield Char
x s
s1' -> Char -> E s s -> Step (E s s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> E s s
forall l r. l -> E l r
L s
s1')
      next (R s
s2) = case s -> Step s Char
next1 s
s2 of
                          Step s Char
Done        -> Step (E s s) Char
forall s a. Step s a
Done
                          Skip s
s2'    -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. r -> E l r
R s
s2')
                          Yield Char
x s
s2' -> Char -> E s s -> Step (E s s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> E s s
forall l r. r -> E l r
R s
s2')
{-# INLINE [0] append #-}

-- | /O(1)/ Returns the first character of a 'Stream' 'Char', which must be non-empty.
-- This is a partial function, consider using 'uncons'.
--
-- __Properties__
--
-- @ 'head' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.head' @
head :: HasCallStack => Stream Char -> Char
head :: HasCallStack => Stream Char -> Char
head (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Char
loop_head s
s0
    where
      loop_head :: s -> Char
loop_head !s
s = case s -> Step s Char
next s
s of
                      Yield Char
x s
_ -> Char
x
                      Skip s
s'   -> s -> Char
loop_head s
s'
                      Step s Char
Done      -> Char
forall a. HasCallStack => a
head_empty
{-# INLINE [0] head #-}

head_empty :: HasCallStack => a
head_empty :: forall a. HasCallStack => a
head_empty = String -> String -> a
forall a. HasCallStack => String -> String -> a
streamError String
"head" String
"Empty stream"
{-# NOINLINE head_empty #-}

-- | /O(1)/ Returns the first character and remainder of a 'Stream'
-- 'Char', or 'Nothing' if empty.
--
-- __Properties__
--
-- @ 'Data.Functor.fmap' 'Data.Tuple.fst' . 'uncons' . 'Data.Text.Internal.Fusion.stream' = 'Data.Functor.fmap' 'Data.Tuple.fst' . 'Data.Text.uncons' @
--
-- @ 'Data.Functor.fmap' ('Data.Text.Internal.Fusion.unstream' . 'Data.Tuple.snd') . 'uncons' . 'Data.Text.Internal.Fusion.stream' = 'Data.Functor.fmap' 'Data.Tuple.snd' . 'Data.Text.uncons' @
uncons :: Stream Char -> Maybe (Char, Stream Char)
uncons :: Stream Char -> Maybe (Char, Stream Char)
uncons (Stream s -> Step s Char
next s
s0 Size
len) = s -> Maybe (Char, Stream Char)
loop_uncons s
s0
    where
      loop_uncons :: s -> Maybe (Char, Stream Char)
loop_uncons !s
s = case s -> Step s Char
next s
s of
                         Yield Char
x s
s1 -> (Char, Stream Char) -> Maybe (Char, Stream Char)
forall a. a -> Maybe a
Just (Char
x, (s -> Step s Char) -> s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream s -> Step s Char
next s
s1 (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
codePointsSize Int
1))
                         Skip s
s'    -> s -> Maybe (Char, Stream Char)
loop_uncons s
s'
                         Step s Char
Done       -> Maybe (Char, Stream Char)
forall a. Maybe a
Nothing
{-# INLINE [0] uncons #-}

-- | /O(n)/ Returns the last character of a 'Stream' 'Char', which must
-- be non-empty.
--
-- __Properties__
--
-- @ 'last' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.last' @
last :: HasCallStack => Stream Char -> Char
last :: HasCallStack => Stream Char -> Char
last (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Char
loop0_last s
s0
    where
      loop0_last :: s -> Char
loop0_last !s
s = case s -> Step s Char
next s
s of
                        Step s Char
Done       -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"last"
                        Skip s
s'    -> s -> Char
loop0_last  s
s'
                        Yield Char
x s
s' -> Char -> s -> Char
loop_last Char
x s
s'
      loop_last :: Char -> s -> Char
loop_last !Char
x !s
s = case s -> Step s Char
next s
s of
                         Step s Char
Done        -> Char
x
                         Skip s
s'     -> Char -> s -> Char
loop_last Char
x  s
s'
                         Yield Char
x' s
s' -> Char -> s -> Char
loop_last Char
x' s
s'
{-# INLINE[0] last #-}

-- | /O(1)/ Returns all characters after the head of a 'Stream' 'Char', which must
-- be non-empty. This is a partial function, consider using 'uncons'.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'tail' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.tail' @
tail :: HasCallStack => Stream Char -> Stream Char
tail :: HasCallStack => Stream Char -> Stream Char
tail (Stream s -> Step s Char
next0 s
s0 Size
len) = (C s -> Step (C s) Char) -> C s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream C s -> Step (C s) Char
next (s -> C s
forall s. s -> C s
C0 s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
codePointsSize Int
1)
    where
      next :: C s -> Step (C s) Char
next (C0 s
s) = case s -> Step s Char
next0 s
s of
                      Step s Char
Done       -> String -> Step (C s) Char
forall a. HasCallStack => String -> a
emptyError String
"tail"
                      Skip s
s'    -> C s -> Step (C s) Char
forall s a. s -> Step s a
Skip (s -> C s
forall s. s -> C s
C0 s
s')
                      Yield Char
_ s
s' -> C s -> Step (C s) Char
forall s a. s -> Step s a
Skip (s -> C s
forall s. s -> C s
C1 s
s')
      next (C1 s
s) = case s -> Step s Char
next0 s
s of
                      Step s Char
Done       -> Step (C s) Char
forall s a. Step s a
Done
                      Skip s
s'    -> C s -> Step (C s) Char
forall s a. s -> Step s a
Skip    (s -> C s
forall s. s -> C s
C1 s
s')
                      Yield Char
x s
s' -> Char -> C s -> Step (C s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> C s
forall s. s -> C s
C1 s
s')
{-# INLINE [0] tail #-}

data Init s = Init0 !s
            | Init1 {-# UNPACK #-} !Char !s

-- | /O(1)/ Returns all but the last character of a 'Stream' 'Char', which
-- must be non-empty.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'init' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.init' @
init :: HasCallStack => Stream Char -> Stream Char
init :: HasCallStack => Stream Char -> Stream Char
init (Stream s -> Step s Char
next0 s
s0 Size
len) = (Init s -> Step (Init s) Char) -> Init s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Init s -> Step (Init s) Char
next (s -> Init s
forall s. s -> Init s
Init0 s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
codePointsSize Int
1)
    where
      next :: Init s -> Step (Init s) Char
next (Init0 s
s) = case s -> Step s Char
next0 s
s of
                         Step s Char
Done       -> String -> Step (Init s) Char
forall a. HasCallStack => String -> a
emptyError String
"init"
                         Skip s
s'    -> Init s -> Step (Init s) Char
forall s a. s -> Step s a
Skip (s -> Init s
forall s. s -> Init s
Init0 s
s')
                         Yield Char
x s
s' -> Init s -> Step (Init s) Char
forall s a. s -> Step s a
Skip (Char -> s -> Init s
forall s. Char -> s -> Init s
Init1 Char
x s
s')
      next (Init1 Char
x s
s)  = case s -> Step s Char
next0 s
s of
                            Step s Char
Done        -> Step (Init s) Char
forall s a. Step s a
Done
                            Skip s
s'     -> Init s -> Step (Init s) Char
forall s a. s -> Step s a
Skip    (Char -> s -> Init s
forall s. Char -> s -> Init s
Init1 Char
x s
s')
                            Yield Char
x' s
s' -> Char -> Init s -> Step (Init s) Char
forall s a. a -> s -> Step s a
Yield Char
x (Char -> s -> Init s
forall s. Char -> s -> Init s
Init1 Char
x' s
s')
{-# INLINE [0] init #-}

-- | /O(1)/ Tests whether a 'Stream' 'Char' is empty or not.
--
-- __Properties__
--
-- @ 'null' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.null' @
null :: Stream Char -> Bool
null :: Stream Char -> Bool
null (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Bool
loop_null s
s0
    where
      loop_null :: s -> Bool
loop_null !s
s = case s -> Step s Char
next s
s of
                       Step s Char
Done      -> Bool
True
                       Yield Char
_ s
_ -> Bool
False
                       Skip s
s'   -> s -> Bool
loop_null s
s'
{-# INLINE[0] null #-}

-- | /O(n)/ Returns the number of characters in a string.
lengthI :: Integral a => Stream Char -> a
lengthI :: forall a. Integral a => Stream Char -> a
lengthI (Stream s -> Step s Char
next s
s0 Size
_len) = a -> s -> a
forall {t}. Num t => t -> s -> t
loop_length a
0 s
s0
    where
      loop_length :: t -> s -> t
loop_length !t
z s
s  = case s -> Step s Char
next s
s of
                           Step s Char
Done       -> t
z
                           Skip    s
s' -> t -> s -> t
loop_length t
z s
s'
                           Yield Char
_ s
s' -> t -> s -> t
loop_length (t
z t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) s
s'
{-# INLINE[0] lengthI #-}

-- | /O(n)/ Compares the count of characters in a string to a number.
--
-- This function gives the same answer as comparing against the result
-- of 'lengthI', but can short circuit if the count of characters is
-- greater than the number or if the stream can't possibly be as long
-- as the number supplied, and hence be more efficient.
compareLengthI :: Integral a => Stream Char -> a -> Ordering
compareLengthI :: forall a. Integral a => Stream Char -> a -> Ordering
compareLengthI (Stream s -> Step s Char
next s
s0 Size
len) a
n
    -- Note that @len@ tracks code units whereas we want to compare the length
    -- in code points. Specifically, a stream with hint @len@ may consist of
    -- anywhere from @len/2@ to @len@ code points.
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0 = Ordering
GT
  | Just Ordering
r <- Size -> Size -> Maybe Ordering
compareSize Size
len Size
n' = Ordering
r
  | Bool
otherwise = a -> s -> Ordering
loop_cmp a
0 s
s0
    where
      n' :: Size
n' = Int -> Size
codePointsSize (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ a -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n
      loop_cmp :: a -> s -> Ordering
loop_cmp !a
z s
s  = case s -> Step s Char
next s
s of
                         Step s Char
Done       -> a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
z a
n
                         Skip    s
s' -> a -> s -> Ordering
loop_cmp a
z s
s'
                         Yield Char
_ s
s' | a
z a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
n     -> Ordering
GT
                                    | Bool
otherwise -> a -> s -> Ordering
loop_cmp (a
z a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) s
s'
{-# INLINE[0] compareLengthI #-}

-- | /O(n)/ Indicate whether a string contains exactly one element.
--
-- __Properties__
--
-- @ 'isSingleton' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.isSingleton' @
isSingleton :: Stream Char -> Bool
isSingleton :: Stream Char -> Bool
isSingleton (Stream s -> Step s Char
next s
s0 Size
_len) = Int -> s -> Bool
loop Int
0 s
s0
    where
      loop :: Int -> s -> Bool
loop !Int
z s
s  = case s -> Step s Char
next s
s of
                     Step s Char
Done            -> Int
z Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (Int
1::Int)
                     Skip    s
s'      -> Int -> s -> Bool
loop Int
z s
s'
                     Yield Char
_ s
s'
                         | Int
z Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
1    -> Bool
False
                         | Bool
otherwise -> Int -> s -> Bool
loop (Int
zInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) s
s'
{-# INLINE[0] isSingleton #-}

-- ----------------------------------------------------------------------------
-- * Stream transformations

-- | /O(n)/ 'map' @f @xs is the 'Stream' 'Char' obtained by applying @f@
-- to each element of @xs@.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'map' f . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.map' f @
map :: (Char -> Char) -> Stream Char -> Stream Char
map :: (Char -> Char) -> Stream Char -> Stream Char
map Char -> Char
f (Stream s -> Step s Char
next0 s
s0 Size
len) = (s -> Step s Char) -> s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream s -> Step s Char
next s
s0 Size
len
    where
      next :: s -> Step s Char
next !s
s = case s -> Step s Char
next0 s
s of
                  Step s Char
Done       -> Step s Char
forall s a. Step s a
Done
                  Skip s
s'    -> s -> Step s Char
forall s a. s -> Step s a
Skip s
s'
                  Yield Char
x s
s' -> Char -> s -> Step s Char
forall s a. a -> s -> Step s a
Yield (Char -> Char
f Char
x) s
s'
{-# INLINE [0] map #-}

{-#
  RULES "STREAM map/map fusion" forall f g s.
     map f (map g s) = map (\x -> f (g x)) s
 #-}

data I s = I1 !s
         | I2 !s {-# UNPACK #-} !Char
         | I3 !s

-- | /O(n)/ Take a character and place it between each of the
-- characters of a 'Stream Char'.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'intersperse' c . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.intersperse' c @
intersperse :: Char -> Stream Char -> Stream Char
intersperse :: Char -> Stream Char -> Stream Char
intersperse Char
c (Stream s -> Step s Char
next0 s
s0 Size
len) = (I s -> Step (I s) Char) -> I s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream I s -> Step (I s) Char
next (s -> I s
forall s. s -> I s
I1 s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
unknownSize)
    where
      next :: I s -> Step (I s) Char
next (I1 s
s) = case s -> Step s Char
next0 s
s of
        Step s Char
Done       -> Step (I s) Char
forall s a. Step s a
Done
        Skip s
s'    -> I s -> Step (I s) Char
forall s a. s -> Step s a
Skip (s -> I s
forall s. s -> I s
I1 s
s')
        Yield Char
x s
s' -> I s -> Step (I s) Char
forall s a. s -> Step s a
Skip (s -> Char -> I s
forall s. s -> Char -> I s
I2 s
s' Char
x)
      next (I2 s
s Char
x)  = Char -> I s -> Step (I s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> I s
forall s. s -> I s
I3 s
s)
      next (I3 s
s) = case s -> Step s Char
next0 s
s of
        Step s Char
Done       -> Step (I s) Char
forall s a. Step s a
Done
        Skip s
s'    -> I s -> Step (I s) Char
forall s a. s -> Step s a
Skip    (s -> I s
forall s. s -> I s
I3 s
s')
        Yield Char
x s
s' -> Char -> I s -> Step (I s) Char
forall s a. a -> s -> Step s a
Yield Char
c (s -> Char -> I s
forall s. s -> Char -> I s
I2 s
s' Char
x)
{-# INLINE [0] intersperse #-}

-- ----------------------------------------------------------------------------
-- ** Case conversions (folds)

-- $case
--
-- With Unicode text, it is incorrect to use combinators like @map
-- toUpper@ to case convert each character of a string individually.
-- Instead, use the whole-string case conversion functions from this
-- module.  For correctness in different writing systems, these
-- functions may map one input character to two or three output
-- characters.

-- | Map a 'Stream' through the given case-mapping function.
caseConvert :: (Char# -> _ {- unboxed Int64 -})
            -> Stream Char -> Stream Char
caseConvert :: (Char# -> Int64#) -> Stream Char -> Stream Char
caseConvert Char# -> Int64#
remap (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (CC s -> Step (CC s) Char) -> CC s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream CC s -> Step (CC s) Char
next (s -> Int64 -> CC s
forall s. s -> Int64 -> CC s
CC s
s0 Int64
0) (Size
len Size -> Size -> Size
`unionSize` (Size
3Size -> Size -> Size
forall a. Num a => a -> a -> a
*Size
len))
  where
    next :: CC s -> Step (CC s) Char
next (CC s
s Int64
0) =
        case s -> Step s Char
next0 s
s of
          Step s Char
Done       -> Step (CC s) Char
forall s a. Step s a
Done
          Skip s
s'    -> CC s -> Step (CC s) Char
forall s a. s -> Step s a
Skip (s -> Int64 -> CC s
forall s. s -> Int64 -> CC s
CC s
s' Int64
0)
          Yield c :: Char
c@(C# Char#
c#) s
s' -> case Int64# -> Int64
I64# (Char# -> Int64#
remap Char#
c#) of
            Int64
0 -> Char -> CC s -> Step (CC s) Char
forall s a. a -> s -> Step s a
Yield Char
c (s -> Int64 -> CC s
forall s. s -> Int64 -> CC s
CC s
s' Int64
0)
            Int64
ab -> let (Char
a, Int64
b) = Int64 -> (Char, Int64)
chopOffChar Int64
ab in
              Char -> CC s -> Step (CC s) Char
forall s a. a -> s -> Step s a
Yield Char
a (s -> Int64 -> CC s
forall s. s -> Int64 -> CC s
CC s
s' Int64
b)
    next (CC s
s Int64
ab) = let (Char
a, Int64
b) = Int64 -> (Char, Int64)
chopOffChar Int64
ab in Char -> CC s -> Step (CC s) Char
forall s a. a -> s -> Step s a
Yield Char
a (s -> Int64 -> CC s
forall s. s -> Int64 -> CC s
CC s
s Int64
b)

chopOffChar :: Int64 -> (Char, Int64)
chopOffChar :: Int64 -> (Char, Int64)
chopOffChar Int64
ab = (Int -> Char
chr Int
a, Int64
ab Int64 -> Int -> Int64
forall a. Bits a => a -> Int -> a
`shiftR` Int
21)
  where
    chr :: Int -> Char
chr (I# Int#
n) = Char# -> Char
C# (Int# -> Char#
chr# Int#
n)
    mask :: Int64
mask = (Int64
1 Int64 -> Int -> Int64
forall a. Bits a => a -> Int -> a
`shiftL` Int
21) Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- Int64
1
    a :: Int
a = Int64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64 -> Int) -> Int64 -> Int
forall a b. (a -> b) -> a -> b
$ Int64
ab Int64 -> Int64 -> Int64
forall a. Bits a => a -> a -> a
.&. Int64
mask

-- | /O(n)/ Convert a string to folded case.  This function is mainly
-- useful for performing caseless (or case insensitive) string
-- comparisons.
--
-- A string @x@ is a caseless match for a string @y@ if and only if:
--
-- @'toCaseFold' x == 'toCaseFold' y@
--
-- The result string may be longer than the input string, and may
-- differ from applying 'toLower' to the input string.  For instance,
-- the Armenian small ligature men now (U+FB13) is case folded to the
-- bigram men now (U+0574 U+0576), while the micro sign (U+00B5) is
-- case folded to the Greek small letter letter mu (U+03BC) instead of
-- itself.
toCaseFold :: Stream Char -> Stream Char
toCaseFold :: Stream Char -> Stream Char
toCaseFold = (Char# -> Int64#) -> Stream Char -> Stream Char
caseConvert Char# -> Int64#
foldMapping
{-# INLINE [0] toCaseFold #-}

-- | /O(n)/ Convert a string to upper case, using simple case
-- conversion.  The result string may be longer than the input string.
-- For instance, the German eszett (U+00DF) maps to the two-letter
-- sequence SS.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'toUpper' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.toUpper' @
toUpper :: Stream Char -> Stream Char
toUpper :: Stream Char -> Stream Char
toUpper = (Char# -> Int64#) -> Stream Char -> Stream Char
caseConvert Char# -> Int64#
upperMapping
{-# INLINE [0] toUpper #-}

-- | /O(n)/ Convert a string to lower case, using simple case
-- conversion.  The result string may be longer than the input string.
-- For instance, the Latin capital letter I with dot above (U+0130)
-- maps to the sequence Latin small letter i (U+0069) followed by
-- combining dot above (U+0307).
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'toLower' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.toLower' @
toLower :: Stream Char -> Stream Char
toLower :: Stream Char -> Stream Char
toLower = (Char# -> Int64#) -> Stream Char -> Stream Char
caseConvert Char# -> Int64#
lowerMapping
{-# INLINE [0] toLower #-}

-- | /O(n)/ Convert a string to title case, using simple case
-- conversion.
--
-- The first letter of the input is converted to title case, as is
-- every subsequent letter that immediately follows a non-letter.
-- Every letter that immediately follows another letter is converted
-- to lower case.
--
-- The result string may be longer than the input string. For example,
-- the Latin small ligature &#xfb02; (U+FB02) is converted to the
-- sequence Latin capital letter F (U+0046) followed by Latin small
-- letter l (U+006C).
--
-- /Note/: this function does not take language or culture specific
-- rules into account. For instance, in English, different style
-- guides disagree on whether the book name \"The Hill of the Red
-- Fox\" is correctly title cased&#x2014;but this function will
-- capitalize /every/ word.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'toTitle' . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.toTitle' @
toTitle :: Stream Char -> Stream Char
toTitle :: Stream Char -> Stream Char
toTitle (Stream s -> Step s Char
next0 s
s0 Size
len) = (CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char)
-> CC (PairS Bool s) -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
next (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
False Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s0) Int64
0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
unknownSize)
  where
    next :: CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
next (CC (Bool
letter :*: s
s) Int64
0) =
      case s -> Step s Char
next0 s
s of
        Step s Char
Done            -> Step (CC (PairS Bool s)) Char
forall s a. Step s a
Done
        Skip s
s'         -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. s -> Step s a
Skip (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
letter Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
0)
        Yield c :: Char
c@(C# Char#
c#) s
s'
          | Bool
nonSpace, Bool
letter -> case Int64# -> Int64
I64# (Char# -> Int64#
lowerMapping Char#
c#) of
            Int64
0 -> Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
c (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
nonSpace Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
0)
            Int64
ab -> let (Char
a, Int64
b) = Int64 -> (Char, Int64)
chopOffChar Int64
ab in
              Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
a (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
nonSpace Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
b)
          | Bool
nonSpace    ->  case Int64# -> Int64
I64# (Char# -> Int64#
titleMapping Char#
c#) of
            Int64
0 -> Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
c (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
letter' Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
0)
            Int64
ab -> let (Char
a, Int64
b) = Int64 -> (Char, Int64)
chopOffChar Int64
ab in
              Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
a (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
letter' Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
b)
          | Bool
otherwise   -> Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
c (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC (Bool
letter' Bool -> s -> PairS Bool s
forall a b. a -> b -> PairS a b
:*: s
s') Int64
0)
          where nonSpace :: Bool
nonSpace = Bool -> Bool
P.not (Char -> Bool
isSpace Char
c)
                letter' :: Bool
letter'  = Char -> Bool
isLetter Char
c
    next (CC PairS Bool s
s Int64
ab) = let (Char
a, Int64
b) = Int64 -> (Char, Int64)
chopOffChar Int64
ab in Char -> CC (PairS Bool s) -> Step (CC (PairS Bool s)) Char
forall s a. a -> s -> Step s a
Yield Char
a (PairS Bool s -> Int64 -> CC (PairS Bool s)
forall s. s -> Int64 -> CC s
CC PairS Bool s
s Int64
b)
{-# INLINE [0] toTitle #-}

data Justify i s = Just1 !i !s
                 | Just2 !i !s

justifyLeftI :: Integral a => a -> Char -> Stream Char -> Stream Char
justifyLeftI :: forall a. Integral a => a -> Char -> Stream Char -> Stream Char
justifyLeftI a
k Char
c (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (Justify a s -> Step (Justify a s) Char)
-> Justify a s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Justify a s -> Step (Justify a s) Char
next (a -> s -> Justify a s
forall i s. i -> s -> Justify i s
Just1 a
0 s
s0) (Size -> Size -> Size
larger (a -> Size
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
k Size -> Size -> Size
forall a. Num a => a -> a -> a
* Char -> Size
charSize Char
c Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
len) Size
len)
  where
    next :: Justify a s -> Step (Justify a s) Char
next (Just1 a
n s
s) =
        case s -> Step s Char
next0 s
s of
          Step s Char
Done       -> Justify a s -> Step (Justify a s) Char
next (a -> s -> Justify a s
forall i s. i -> s -> Justify i s
Just2 a
n s
s)
          Skip s
s'    -> Justify a s -> Step (Justify a s) Char
forall s a. s -> Step s a
Skip (a -> s -> Justify a s
forall i s. i -> s -> Justify i s
Just1 a
n s
s')
          Yield Char
x s
s' -> Char -> Justify a s -> Step (Justify a s) Char
forall s a. a -> s -> Step s a
Yield Char
x (a -> s -> Justify a s
forall i s. i -> s -> Justify i s
Just1 (a
na -> a -> a
forall a. Num a => a -> a -> a
+a
1) s
s')
    next (Just2 a
n s
s)
        | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k       = Char -> Justify a s -> Step (Justify a s) Char
forall s a. a -> s -> Step s a
Yield Char
c (a -> s -> Justify a s
forall i s. i -> s -> Justify i s
Just2 (a
na -> a -> a
forall a. Num a => a -> a -> a
+a
1) s
s)
        | Bool
otherwise   = Step (Justify a s) Char
forall s a. Step s a
Done
    {-# INLINE next #-}
{-# INLINE [0] justifyLeftI #-}

-- ----------------------------------------------------------------------------
-- * Reducing Streams (folds)

-- | foldl, applied to a binary operator, a starting value (typically the
-- left-identity of the operator), and a 'Stream', reduces the 'Stream' using the
-- binary operator, from left to right.
--
-- __Properties__
--
-- @ 'foldl' f z0 . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldl' f z0 @
foldl :: (b -> Char -> b) -> b -> Stream Char -> b
foldl :: forall b. (b -> Char -> b) -> b -> Stream Char -> b
foldl b -> Char -> b
f b
z0 (Stream s -> Step s Char
next s
s0 Size
_len) = b -> s -> b
loop_foldl b
z0 s
s0
    where
      loop_foldl :: b -> s -> b
loop_foldl b
z !s
s = case s -> Step s Char
next s
s of
                          Step s Char
Done -> b
z
                          Skip s
s' -> b -> s -> b
loop_foldl b
z s
s'
                          Yield Char
x s
s' -> b -> s -> b
loop_foldl (b -> Char -> b
f b
z Char
x) s
s'
{-# INLINE [0] foldl #-}

-- | A strict version of foldl.
--
-- __Properties__
--
-- @ 'foldl'' f z0 . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldl'' f z0 @
foldl' :: (b -> Char -> b) -> b -> Stream Char -> b
foldl' :: forall b. (b -> Char -> b) -> b -> Stream Char -> b
foldl' b -> Char -> b
f b
z0 (Stream s -> Step s Char
next s
s0 Size
_len) = b -> s -> b
loop_foldl' b
z0 s
s0
    where
      loop_foldl' :: b -> s -> b
loop_foldl' !b
z !s
s = case s -> Step s Char
next s
s of
                            Step s Char
Done -> b
z
                            Skip s
s' -> b -> s -> b
loop_foldl' b
z s
s'
                            Yield Char
x s
s' -> b -> s -> b
loop_foldl' (b -> Char -> b
f b
z Char
x) s
s'
{-# INLINE [0] foldl' #-}

-- | foldl1 is a variant of foldl that has no starting value argument,
-- and thus must be applied to non-empty Streams.
--
-- __Properties__
--
-- @ 'foldl1' f . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldl1' f @
foldl1 :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldl1 :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldl1 Char -> Char -> Char
f (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Char
loop0_foldl1 s
s0
    where
      loop0_foldl1 :: s -> Char
loop0_foldl1 !s
s = case s -> Step s Char
next s
s of
                          Skip s
s' -> s -> Char
loop0_foldl1 s
s'
                          Yield Char
x s
s' -> Char -> s -> Char
loop_foldl1 Char
x s
s'
                          Step s Char
Done -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"foldl1"
      loop_foldl1 :: Char -> s -> Char
loop_foldl1 Char
z !s
s = case s -> Step s Char
next s
s of
                           Step s Char
Done -> Char
z
                           Skip s
s' -> Char -> s -> Char
loop_foldl1 Char
z s
s'
                           Yield Char
x s
s' -> Char -> s -> Char
loop_foldl1 (Char -> Char -> Char
f Char
z Char
x) s
s'
{-# INLINE [0] foldl1 #-}

-- | A strict version of foldl1.
--
-- __Properties__
--
-- @ 'foldl1'' f . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldl1'' f @
foldl1' :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldl1' :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldl1' Char -> Char -> Char
f (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Char
loop0_foldl1' s
s0
    where
      loop0_foldl1' :: s -> Char
loop0_foldl1' !s
s = case s -> Step s Char
next s
s of
                           Skip s
s' -> s -> Char
loop0_foldl1' s
s'
                           Yield Char
x s
s' -> Char -> s -> Char
loop_foldl1' Char
x s
s'
                           Step s Char
Done -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"foldl1"
      loop_foldl1' :: Char -> s -> Char
loop_foldl1' !Char
z !s
s = case s -> Step s Char
next s
s of
                             Step s Char
Done -> Char
z
                             Skip s
s' -> Char -> s -> Char
loop_foldl1' Char
z s
s'
                             Yield Char
x s
s' -> Char -> s -> Char
loop_foldl1' (Char -> Char -> Char
f Char
z Char
x) s
s'
{-# INLINE [0] foldl1' #-}

-- | 'foldr', applied to a binary operator, a starting value (typically the
-- right-identity of the operator), and a stream, reduces the stream using the
-- binary operator, from right to left.
--
-- __Properties__
--
-- @ 'foldr' f z0 . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldr' f z0 @
foldr :: (Char -> b -> b) -> b -> Stream Char -> b
foldr :: forall b. (Char -> b -> b) -> b -> Stream Char -> b
foldr Char -> b -> b
f b
z (Stream s -> Step s Char
next s
s0 Size
_len) = s -> b
loop_foldr s
s0
    where
      loop_foldr :: s -> b
loop_foldr !s
s = case s -> Step s Char
next s
s of
                        Step s Char
Done -> b
z
                        Skip s
s' -> s -> b
loop_foldr s
s'
                        Yield Char
x s
s' -> Char -> b -> b
f Char
x (s -> b
loop_foldr s
s')
{-# INLINE [0] foldr #-}

-- | foldr1 is a variant of 'foldr' that has no starting value argument,
-- and thus must be applied to non-empty streams.
--
-- __Properties__
--
-- @ 'foldr1' f . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.foldr1' f @
foldr1 :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldr1 :: HasCallStack => (Char -> Char -> Char) -> Stream Char -> Char
foldr1 Char -> Char -> Char
f (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Char
loop0_foldr1 s
s0
  where
    loop0_foldr1 :: s -> Char
loop0_foldr1 !s
s = case s -> Step s Char
next s
s of
      Step s Char
Done       -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"foldr1"
      Skip    s
s' -> s -> Char
loop0_foldr1  s
s'
      Yield Char
x s
s' -> Char -> s -> Char
loop_foldr1 Char
x s
s'

    loop_foldr1 :: Char -> s -> Char
loop_foldr1 Char
x !s
s = case s -> Step s Char
next s
s of
      Step s Char
Done        -> Char
x
      Skip     s
s' -> Char -> s -> Char
loop_foldr1 Char
x s
s'
      Yield Char
x' s
s' -> Char -> Char -> Char
f Char
x (Char -> s -> Char
loop_foldr1 Char
x' s
s')
{-# INLINE [0] foldr1 #-}

-- | intercalate str strs interts the stream str in between the streams strs and
-- concatenates the result.
--
-- __Properties__
--
-- @ 'intercalate' s = 'concat' . 'L.intersperse' s @
intercalate :: Stream Char -> [Stream Char] -> Stream Char
intercalate :: Stream Char -> [Stream Char] -> Stream Char
intercalate Stream Char
s = [Stream Char] -> Stream Char
concat ([Stream Char] -> Stream Char)
-> ([Stream Char] -> [Stream Char]) -> [Stream Char] -> Stream Char
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Stream Char -> [Stream Char] -> [Stream Char]
forall a. a -> [a] -> [a]
L.intersperse Stream Char
s)
{-# INLINE [0] intercalate #-}

-- ----------------------------------------------------------------------------
-- ** Special folds

-- | /O(n)/ Concatenate a list of streams.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'concat' . 'Data.Functor.fmap' 'Data.Text.Internal.Fusion.stream'  = 'Data.Text.concat'@
concat :: [Stream Char] -> Stream Char
concat :: [Stream Char] -> Stream Char
concat = (Stream Char -> Stream Char -> Stream Char)
-> Stream Char -> [Stream Char] -> Stream Char
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
L.foldr Stream Char -> Stream Char -> Stream Char
append Stream Char
forall a. Stream a
empty
{-# INLINE [0] concat #-}

-- | Map a function over a stream that results in a stream and concatenate the
-- results.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'concatMap' ('Data.Text.Fusion.stream' . f) . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.concatMap' f@
concatMap :: (Char -> Stream Char) -> Stream Char -> Stream Char
concatMap :: (Char -> Stream Char) -> Stream Char -> Stream Char
concatMap Char -> Stream Char
f = (Char -> Stream Char -> Stream Char)
-> Stream Char -> Stream Char -> Stream Char
forall b. (Char -> b -> b) -> b -> Stream Char -> b
foldr (Stream Char -> Stream Char -> Stream Char
append (Stream Char -> Stream Char -> Stream Char)
-> (Char -> Stream Char) -> Char -> Stream Char -> Stream Char
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Stream Char
f) Stream Char
forall a. Stream a
empty
{-# INLINE [0] concatMap #-}

-- | /O(n)/ any @p @xs determines if any character in the stream
-- @xs@ satisfies the predicate @p@.
--
-- __Properties__
--
-- @'any' f . 'Data.Text.Fusion.stream' = 'Data.Text.any' f@
any :: (Char -> Bool) -> Stream Char -> Bool
any :: (Char -> Bool) -> Stream Char -> Bool
any Char -> Bool
p (Stream s -> Step s Char
next0 s
s0 Size
_len) = s -> Bool
loop_any s
s0
    where
      loop_any :: s -> Bool
loop_any !s
s = case s -> Step s Char
next0 s
s of
                      Step s Char
Done                   -> Bool
False
                      Skip s
s'                -> s -> Bool
loop_any s
s'
                      Yield Char
x s
s' | Char -> Bool
p Char
x       -> Bool
True
                                 | Bool
otherwise -> s -> Bool
loop_any s
s'
{-# INLINE [0] any #-}

-- | /O(n)/ all @p @xs determines if all characters in the 'Text'
-- @xs@ satisfy the predicate @p@.
--
-- __Properties__
--
-- @'all' f . 'Data.Text.Fusion.stream' = 'Data.Text.all' f@
all :: (Char -> Bool) -> Stream Char -> Bool
all :: (Char -> Bool) -> Stream Char -> Bool
all Char -> Bool
p (Stream s -> Step s Char
next0 s
s0 Size
_len) = s -> Bool
loop_all s
s0
    where
      loop_all :: s -> Bool
loop_all !s
s = case s -> Step s Char
next0 s
s of
                      Step s Char
Done                   -> Bool
True
                      Skip s
s'                -> s -> Bool
loop_all s
s'
                      Yield Char
x s
s' | Char -> Bool
p Char
x       -> s -> Bool
loop_all s
s'
                                 | Bool
otherwise -> Bool
False
{-# INLINE [0] all #-}

-- | /O(n)/ maximum returns the maximum value from a stream, which must be
-- non-empty.
--
-- __Properties__
--
-- @'maximum' . 'Data.Text.Fusion.stream' = 'Data.Text.maximum'@
maximum :: HasCallStack => Stream Char -> Char
maximum :: HasCallStack => Stream Char -> Char
maximum (Stream s -> Step s Char
next0 s
s0 Size
_len) = s -> Char
loop0_maximum s
s0
    where
      loop0_maximum :: s -> Char
loop0_maximum !s
s   = case s -> Step s Char
next0 s
s of
                             Step s Char
Done       -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"maximum"
                             Skip s
s'    -> s -> Char
loop0_maximum s
s'
                             Yield Char
x s
s' -> Char -> s -> Char
loop_maximum Char
x s
s'
      loop_maximum :: Char -> s -> Char
loop_maximum !Char
z !s
s = case s -> Step s Char
next0 s
s of
                             Step s Char
Done            -> Char
z
                             Skip s
s'         -> Char -> s -> Char
loop_maximum Char
z s
s'
                             Yield Char
x s
s'
                                 | Char
x Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
> Char
z     -> Char -> s -> Char
loop_maximum Char
x s
s'
                                 | Bool
otherwise -> Char -> s -> Char
loop_maximum Char
z s
s'
{-# INLINE [0] maximum #-}

-- | /O(n)/ minimum returns the minimum value from a 'Text', which must be
-- non-empty.
--
-- __Properties__
--
-- @'minimum' . 'Data.Text.Fusion.stream' = 'Data.Text.minimum'@
minimum :: HasCallStack => Stream Char -> Char
minimum :: HasCallStack => Stream Char -> Char
minimum (Stream s -> Step s Char
next0 s
s0 Size
_len) = s -> Char
loop0_minimum s
s0
    where
      loop0_minimum :: s -> Char
loop0_minimum !s
s   = case s -> Step s Char
next0 s
s of
                             Step s Char
Done       -> String -> Char
forall a. HasCallStack => String -> a
emptyError String
"minimum"
                             Skip s
s'    -> s -> Char
loop0_minimum s
s'
                             Yield Char
x s
s' -> Char -> s -> Char
loop_minimum Char
x s
s'
      loop_minimum :: Char -> s -> Char
loop_minimum !Char
z !s
s = case s -> Step s Char
next0 s
s of
                             Step s Char
Done            -> Char
z
                             Skip s
s'         -> Char -> s -> Char
loop_minimum Char
z s
s'
                             Yield Char
x s
s'
                                 | Char
x Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
< Char
z     -> Char -> s -> Char
loop_minimum Char
x s
s'
                                 | Bool
otherwise -> Char -> s -> Char
loop_minimum Char
z s
s'
{-# INLINE [0] minimum #-}

-- -----------------------------------------------------------------------------
-- * Building streams
--
-- | /O(n)/ 'scanl' is similar to 'foldl', but returns a stream of
-- successive reduced values from the left. Conceptually, if we
-- write the input stream as a list then we have:
--
-- > scanl f z [x1, x2, ...] == [z, z 'f' x1, (z 'f' x1) 'f' x2, ...]
--
-- __Properties__
--
-- @'head' ('scanl' f z xs) = z@
-- 
-- @'last' ('scanl' f z xs) = 'foldl' f z xs@
scanl :: (Char -> Char -> Char) -> Char -> Stream Char -> Stream Char
scanl :: (Char -> Char -> Char) -> Char -> Stream Char -> Stream Char
scanl Char -> Char -> Char
f Char
z0 (Stream s -> Step s Char
next0 s
s0 Size
len) = (Scan s -> Step (Scan s) Char) -> Scan s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Scan s -> Step (Scan s) Char
next (Char -> s -> Scan s
forall s. Char -> s -> Scan s
Scan1 Char
z0 s
s0) (Size
lenSize -> Size -> Size
forall a. Num a => a -> a -> a
+Size
1) -- HINT maybe too low
  where
    {-# INLINE next #-}
    next :: Scan s -> Step (Scan s) Char
next (Scan1 Char
z s
s) = Char -> Scan s -> Step (Scan s) Char
forall s a. a -> s -> Step s a
Yield Char
z (Char -> s -> Scan s
forall s. Char -> s -> Scan s
Scan2 Char
z s
s)
    next (Scan2 Char
z s
s) = case s -> Step s Char
next0 s
s of
                         Yield Char
x s
s' -> let !x' :: Char
x' = Char -> Char -> Char
f Char
z Char
x
                                       in Char -> Scan s -> Step (Scan s) Char
forall s a. a -> s -> Step s a
Yield Char
x' (Char -> s -> Scan s
forall s. Char -> s -> Scan s
Scan2 Char
x' s
s')
                         Skip s
s'    -> Scan s -> Step (Scan s) Char
forall s a. s -> Step s a
Skip (Char -> s -> Scan s
forall s. Char -> s -> Scan s
Scan2 Char
z s
s')
                         Step s Char
Done       -> Step (Scan s) Char
forall s a. Step s a
Done
{-# INLINE [0] scanl #-}

-- -----------------------------------------------------------------------------
-- ** Generating and unfolding streams

-- | /O(n)/ 'replicateCharI' @n@ @c@ is a 'Stream' 'Char' of length @n@ with @c@ the
-- value of every element.
replicateCharI :: Integral a => a -> Char -> Stream Char
replicateCharI :: forall a. Integral a => a -> Char -> Stream Char
replicateCharI !a
n !Char
c
    | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0     = Stream Char
forall a. Stream a
empty
    | Bool
otherwise = (a -> Step a Char) -> a -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream a -> Step a Char
next a
0 (a -> Size
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n) -- HINT maybe too low
  where
    next :: a -> Step a Char
next !a
i | a
i a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
n    = Step a Char
forall s a. Step s a
Done
            | Bool
otherwise = Char -> a -> Step a Char
forall s a. a -> s -> Step s a
Yield Char
c (a
i a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)
{-# INLINE [0] replicateCharI #-}

data RI s = RI !s {-# UNPACK #-} !Int64


-- | /O(n*m)/ 'replicateI' @n@ @t@ is a 'Stream' 'Char' consisting of the input
-- @t@ repeated @n@ times.
replicateI :: Int64 -> Stream Char -> Stream Char
replicateI :: Int64 -> Stream Char -> Stream Char
replicateI Int64
n (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (RI s -> Step (RI s) Char) -> RI s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream RI s -> Step (RI s) Char
next (s -> Int64 -> RI s
forall s. s -> Int64 -> RI s
RI s
s0 Int64
0) (Int64 -> Size
int64ToSize (Int64 -> Int64 -> Int64
forall a. Ord a => a -> a -> a
max Int64
0 Int64
n) Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
len)
  where
    next :: RI s -> Step (RI s) Char
next (RI s
s Int64
k)
        | Int64
k Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Int64
n = Step (RI s) Char
forall s a. Step s a
Done
        | Bool
otherwise = case s -> Step s Char
next0 s
s of
                        Step s Char
Done       -> RI s -> Step (RI s) Char
forall s a. s -> Step s a
Skip    (s -> Int64 -> RI s
forall s. s -> Int64 -> RI s
RI s
s0 (Int64
kInt64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+Int64
1))
                        Skip s
s'    -> RI s -> Step (RI s) Char
forall s a. s -> Step s a
Skip    (s -> Int64 -> RI s
forall s. s -> Int64 -> RI s
RI s
s' Int64
k)
                        Yield Char
x s
s' -> Char -> RI s -> Step (RI s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> Int64 -> RI s
forall s. s -> Int64 -> RI s
RI s
s' Int64
k)
{-# INLINE [0] replicateI #-}

-- | /O(n)/, where @n@ is the length of the result. The unfoldr function
-- is analogous to the List 'unfoldr'. unfoldr builds a stream
-- from a seed value. The function takes the element and returns
-- Nothing if it is done producing the stream or returns Just
-- (a,b), in which case, a is the next Char in the string, and b is
-- the seed value for further production.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'unfoldr' f z = 'Data.Text.unfoldr' f z@
unfoldr :: (a -> Maybe (Char,a)) -> a -> Stream Char
unfoldr :: forall a. (a -> Maybe (Char, a)) -> a -> Stream Char
unfoldr a -> Maybe (Char, a)
f a
s0 = (a -> Step a Char) -> a -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream a -> Step a Char
next a
s0 Size
unknownSize
    where
      {-# INLINE next #-}
      next :: a -> Step a Char
next !a
s = case a -> Maybe (Char, a)
f a
s of
                 Maybe (Char, a)
Nothing      -> Step a Char
forall s a. Step s a
Done
                 Just (Char
w, a
s') -> Char -> a -> Step a Char
forall s a. a -> s -> Step s a
Yield Char
w a
s'
{-# INLINE [0] unfoldr #-}

-- | /O(n)/ Like 'unfoldr', 'unfoldrNI' builds a stream from a seed
-- value. However, the length of the result is limited by the
-- first argument to 'unfoldrNI'. This function is more efficient than
-- 'unfoldr' when the length of the result is known.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' ('unfoldrNI' n f z) = 'Data.Text.unfoldrN' n f z@
unfoldrNI :: Integral a => a -> (b -> Maybe (Char,b)) -> b -> Stream Char
unfoldrNI :: forall a b.
Integral a =>
a -> (b -> Maybe (Char, b)) -> b -> Stream Char
unfoldrNI a
n b -> Maybe (Char, b)
f b
s0 | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<  a
0    = Stream Char
forall a. Stream a
empty
                 | Bool
otherwise = (PairS a b -> Step (PairS a b) Char)
-> PairS a b -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream PairS a b -> Step (PairS a b) Char
next (a
0 a -> b -> PairS a b
forall a b. a -> b -> PairS a b
:*: b
s0) (Int -> Size
maxSize (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ a -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (a
na -> a -> a
forall a. Num a => a -> a -> a
*a
2))
    where
      {-# INLINE next #-}
      next :: PairS a b -> Step (PairS a b) Char
next (a
z :*: b
s) = case b -> Maybe (Char, b)
f b
s of
          Maybe (Char, b)
Nothing                  -> Step (PairS a b) Char
forall s a. Step s a
Done
          Just (Char
w, b
s') | a
z a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
n    -> Step (PairS a b) Char
forall s a. Step s a
Done
                       | Bool
otherwise -> Char -> PairS a b -> Step (PairS a b) Char
forall s a. a -> s -> Step s a
Yield Char
w ((a
z a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) a -> b -> PairS a b
forall a b. a -> b -> PairS a b
:*: b
s')
{-# INLINE unfoldrNI #-}

-------------------------------------------------------------------------------
--  * Substreams

-- | /O(n)/ @'take' n@, applied to a stream, returns the prefix of the
-- stream of length @n@, or the stream itself if @n@ is greater than the
-- length of the stream.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'take' n . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.take' n@
take :: Integral a => a -> Stream Char -> Stream Char
take :: forall a. Integral a => a -> Stream Char -> Stream Char
take a
n0 (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (PairS a s -> Step (PairS a s) Char)
-> PairS a s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream PairS a s -> Step (PairS a s) Char
forall {a}. (Ord a, Num a) => PairS a s -> Step (PairS a s) Char
next (a
n0' a -> s -> PairS a s
forall a b. a -> b -> PairS a b
:*: s
s0) (Size -> Size -> Size
smaller Size
len (Int -> Size
codePointsSize (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ a -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n0'))
    where
      n0' :: a
n0' = a -> a -> a
forall a. Ord a => a -> a -> a
max a
n0 a
0

      {-# INLINE next #-}
      next :: PairS a s -> Step (PairS a s) Char
next (a
n :*: s
s) | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
0    = Step (PairS a s) Char
forall s a. Step s a
Done
                     | Bool
otherwise = case s -> Step s Char
next0 s
s of
                                     Step s Char
Done -> Step (PairS a s) Char
forall s a. Step s a
Done
                                     Skip s
s' -> PairS a s -> Step (PairS a s) Char
forall s a. s -> Step s a
Skip (a
n a -> s -> PairS a s
forall a b. a -> b -> PairS a b
:*: s
s')
                                     Yield Char
x s
s' -> Char -> PairS a s -> Step (PairS a s) Char
forall s a. a -> s -> Step s a
Yield Char
x ((a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1) a -> s -> PairS a s
forall a b. a -> b -> PairS a b
:*: s
s')
{-# INLINE [0] take #-}

data Drop a s = NS !s
              | JS !a !s

-- | /O(n)/ @'drop' n@, applied to a stream, returns the suffix of the
-- stream after the first @n@ characters, or the empty stream if @n@
-- is greater than the length of the stream.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'drop' n . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.drop' n@
drop :: Integral a => a -> Stream Char -> Stream Char
drop :: forall a. Integral a => a -> Stream Char -> Stream Char
drop a
n0 (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (Drop a s -> Step (Drop a s) Char)
-> Drop a s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Drop a s -> Step (Drop a s) Char
forall {a}. (Ord a, Num a) => Drop a s -> Step (Drop a s) Char
next (a -> s -> Drop a s
forall a s. a -> s -> Drop a s
JS a
n0' s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
codePointsSize (a -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n0'))
  where
    n0' :: a
n0' = a -> a -> a
forall a. Ord a => a -> a -> a
max a
n0 a
0

    {-# INLINE next #-}
    next :: Drop a s -> Step (Drop a s) Char
next (JS a
n s
s)
      | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
0    = Drop a s -> Step (Drop a s) Char
forall s a. s -> Step s a
Skip (s -> Drop a s
forall a s. s -> Drop a s
NS s
s)
      | Bool
otherwise = case s -> Step s Char
next0 s
s of
          Step s Char
Done       -> Step (Drop a s) Char
forall s a. Step s a
Done
          Skip    s
s' -> Drop a s -> Step (Drop a s) Char
forall s a. s -> Step s a
Skip (a -> s -> Drop a s
forall a s. a -> s -> Drop a s
JS a
n    s
s')
          Yield Char
_ s
s' -> Drop a s -> Step (Drop a s) Char
forall s a. s -> Step s a
Skip (a -> s -> Drop a s
forall a s. a -> s -> Drop a s
JS (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1) s
s')
    next (NS s
s) = case s -> Step s Char
next0 s
s of
      Step s Char
Done       -> Step (Drop a s) Char
forall s a. Step s a
Done
      Skip    s
s' -> Drop a s -> Step (Drop a s) Char
forall s a. s -> Step s a
Skip    (s -> Drop a s
forall a s. s -> Drop a s
NS s
s')
      Yield Char
x s
s' -> Char -> Drop a s -> Step (Drop a s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> Drop a s
forall a s. s -> Drop a s
NS s
s')
{-# INLINE [0] drop #-}

-- | 'takeWhile', applied to a predicate @p@ and a stream, returns the
-- longest prefix (possibly empty) of elements that satisfy @p@.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'takeWhile' p . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.takeWhile' p@
takeWhile :: (Char -> Bool) -> Stream Char -> Stream Char
takeWhile :: (Char -> Bool) -> Stream Char -> Stream Char
takeWhile Char -> Bool
p (Stream s -> Step s Char
next0 s
s0 Size
len) = (s -> Step s Char) -> s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream s -> Step s Char
next s
s0 (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
unknownSize)
    where
      {-# INLINE next #-}
      next :: s -> Step s Char
next !s
s = case s -> Step s Char
next0 s
s of
                  Step s Char
Done    -> Step s Char
forall s a. Step s a
Done
                  Skip s
s' -> s -> Step s Char
forall s a. s -> Step s a
Skip s
s'
                  Yield Char
x s
s' | Char -> Bool
p Char
x       -> Char -> s -> Step s Char
forall s a. a -> s -> Step s a
Yield Char
x s
s'
                             | Bool
otherwise -> Step s Char
forall s a. Step s a
Done
{-# INLINE [0] takeWhile #-}

-- | @'dropWhile' p xs@ returns the suffix remaining after @'takeWhile' p xs@.
--
-- __Properties__
--
-- @'Data.Text.Internal.Fusion.unstream' . 'dropWhile' p . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.dropWhile' p@
dropWhile :: (Char -> Bool) -> Stream Char -> Stream Char
dropWhile :: (Char -> Bool) -> Stream Char -> Stream Char
dropWhile Char -> Bool
p (Stream s -> Step s Char
next0 s
s0 Size
len) = (E s s -> Step (E s s) Char) -> E s s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream E s s -> Step (E s s) Char
next (s -> E s s
forall l r. l -> E l r
L s
s0) (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
unknownSize)
    where
    {-# INLINE next #-}
    next :: E s s -> Step (E s s) Char
next (L s
s)  = case s -> Step s Char
next0 s
s of
      Step s Char
Done                   -> Step (E s s) Char
forall s a. Step s a
Done
      Skip    s
s'             -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. l -> E l r
L s
s')
      Yield Char
x s
s' | Char -> Bool
p Char
x       -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. l -> E l r
L s
s')
                 | Bool
otherwise -> Char -> E s s -> Step (E s s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> E s s
forall l r. r -> E l r
R s
s')
    next (R s
s) = case s -> Step s Char
next0 s
s of
      Step s Char
Done       -> Step (E s s) Char
forall s a. Step s a
Done
      Skip    s
s' -> E s s -> Step (E s s) Char
forall s a. s -> Step s a
Skip    (s -> E s s
forall l r. r -> E l r
R s
s')
      Yield Char
x s
s' -> Char -> E s s -> Step (E s s) Char
forall s a. a -> s -> Step s a
Yield Char
x (s -> E s s
forall l r. r -> E l r
R s
s')
{-# INLINE [0] dropWhile #-}

-- | /O(n)/ The 'isPrefixOf' function takes two 'Stream's and returns
-- 'True' iff the first is a prefix of the second.
--
-- __Properties__
--
-- @ 'isPrefixOf' ('Data.Text.Internal.Fusion.stream' t1) ('Data.Text.Internal.Fusion.stream' t2) = 'Data.Text.isPrefixOf' t1 t2@
isPrefixOf :: (Eq a) => Stream a -> Stream a -> Bool
isPrefixOf :: forall a. Eq a => Stream a -> Stream a -> Bool
isPrefixOf (Stream s -> Step s a
next1 s
s1 Size
_) (Stream s -> Step s a
next2 s
s2 Size
_) = Step s a -> Step s a -> Bool
loop (s -> Step s a
next1 s
s1) (s -> Step s a
next2 s
s2)
    where
      loop :: Step s a -> Step s a -> Bool
loop Step s a
Done      Step s a
_ = Bool
True
      loop Step s a
_    Step s a
Done = Bool
False
      loop (Skip s
s1')     (Skip s
s2')     = Step s a -> Step s a -> Bool
loop (s -> Step s a
next1 s
s1') (s -> Step s a
next2 s
s2')
      loop (Skip s
s1')     Step s a
x2             = Step s a -> Step s a -> Bool
loop (s -> Step s a
next1 s
s1') Step s a
x2
      loop Step s a
x1             (Skip s
s2')     = Step s a -> Step s a -> Bool
loop Step s a
x1          (s -> Step s a
next2 s
s2')
      loop (Yield a
x1 s
s1') (Yield a
x2 s
s2') = a
x1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x2 Bool -> Bool -> Bool
&&
                                           Step s a -> Step s a -> Bool
loop (s -> Step s a
next1 s
s1') (s -> Step s a
next2 s
s2')
{-# INLINE [0] isPrefixOf #-}

-- ----------------------------------------------------------------------------
-- * Searching

-------------------------------------------------------------------------------
-- ** Searching by equality

-- | /O(n)/ 'elem' is the stream membership predicate.
--
-- __Properties__
--
-- @ 'elem' c . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.elem' c@
elem :: Char -> Stream Char -> Bool
elem :: Char -> Stream Char -> Bool
elem Char
w (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Bool
loop_elem s
s0
    where
      loop_elem :: s -> Bool
loop_elem !s
s = case s -> Step s Char
next s
s of
                       Step s Char
Done -> Bool
False
                       Skip s
s' -> s -> Bool
loop_elem s
s'
                       Yield Char
x s
s' | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
w -> Bool
True
                                  | Bool
otherwise -> s -> Bool
loop_elem s
s'
{-# INLINE [0] elem #-}

-------------------------------------------------------------------------------
-- ** Searching with a predicate

-- | /O(n)/ The 'findBy' function takes a predicate and a stream,
-- and returns the first element in matching the predicate, or 'Nothing'
-- if there is no such element.
--
-- __Properties__
--
-- @ 'findBy' p . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.find' p@
findBy :: (Char -> Bool) -> Stream Char -> Maybe Char
findBy :: (Char -> Bool) -> Stream Char -> Maybe Char
findBy Char -> Bool
p (Stream s -> Step s Char
next s
s0 Size
_len) = s -> Maybe Char
loop_find s
s0
    where
      loop_find :: s -> Maybe Char
loop_find !s
s = case s -> Step s Char
next s
s of
                       Step s Char
Done -> Maybe Char
forall a. Maybe a
Nothing
                       Skip s
s' -> s -> Maybe Char
loop_find s
s'
                       Yield Char
x s
s' | Char -> Bool
p Char
x -> Char -> Maybe Char
forall a. a -> Maybe a
Just Char
x
                                  | Bool
otherwise -> s -> Maybe Char
loop_find s
s'
{-# INLINE [0] findBy #-}

-- | /O(n)/ Stream index (subscript) operator, starting from 0.
--
-- __Properties__
--
-- @ 'indexI' ('Data.Text.Internal.Fusion.stream' t) n = 'Data.Text.index' t n@
indexI :: (HasCallStack, Integral a) => Stream Char -> a -> Char
indexI :: forall a. (HasCallStack, Integral a) => Stream Char -> a -> Char
indexI (Stream s -> Step s Char
next s
s0 Size
_len) a
n0
  | a
n0 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0    = String -> String -> Char
forall a. HasCallStack => String -> String -> a
streamError String
"index" String
"Negative index"
  | Bool
otherwise = a -> s -> Char
forall {a}. (Eq a, Num a) => a -> s -> Char
loop_index a
n0 s
s0
  where
    loop_index :: a -> s -> Char
loop_index !a
n !s
s = case s -> Step s Char
next s
s of
      Step s Char
Done                   -> String -> String -> Char
forall a. HasCallStack => String -> String -> a
streamError String
"index" String
"Index too large"
      Skip    s
s'             -> a -> s -> Char
loop_index  a
n    s
s'
      Yield Char
x s
s' | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0    -> Char
x
                 | Bool
otherwise -> a -> s -> Char
loop_index (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1) s
s'
{-# INLINE [0] indexI #-}

-- | /O(n)/ 'filter', applied to a predicate and a stream,
-- returns a stream containing those characters that satisfy the
-- predicate.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.unstream' . 'filter' p . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.filter' p @
filter :: (Char -> Bool) -> Stream Char -> Stream Char
filter :: (Char -> Bool) -> Stream Char -> Stream Char
filter Char -> Bool
p (Stream s -> Step s Char
next0 s
s0 Size
len) =
    (s -> Step s Char) -> s -> Size -> Stream Char
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream s -> Step s Char
next s
s0 (Size
len Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
unknownSize) -- HINT maybe too high
  where
    next :: s -> Step s Char
next !s
s = case s -> Step s Char
next0 s
s of
                Step s Char
Done                   -> Step s Char
forall s a. Step s a
Done
                Skip    s
s'             -> s -> Step s Char
forall s a. s -> Step s a
Skip    s
s'
                Yield Char
x s
s' | Char -> Bool
p Char
x       -> Char -> s -> Step s Char
forall s a. a -> s -> Step s a
Yield Char
x s
s'
                           | Bool
otherwise -> s -> Step s Char
forall s a. s -> Step s a
Skip    s
s'
{-# INLINE [0] filter #-}

{-# RULES
  "STREAM filter/filter fusion" forall p q s.
  filter p (filter q s) = filter (\x -> q x && p x) s
  #-}

-- | The 'findIndexI' function takes a predicate and a stream and
-- returns the index of the first element in the stream satisfying the
-- predicate.
--
-- __Properties__
--
-- @'findIndexI' p . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.findIndex' p @
findIndexI :: Integral a => (Char -> Bool) -> Stream Char -> Maybe a
findIndexI :: forall a. Integral a => (Char -> Bool) -> Stream Char -> Maybe a
findIndexI Char -> Bool
p Stream Char
s = case (Char -> Bool) -> Stream Char -> [a]
forall a. Integral a => (Char -> Bool) -> Stream Char -> [a]
findIndicesI Char -> Bool
p Stream Char
s of
                  (a
i:[a]
_) -> a -> Maybe a
forall a. a -> Maybe a
Just a
i
                  [a]
_     -> Maybe a
forall a. Maybe a
Nothing
{-# INLINE [0] findIndexI #-}

-- | The 'findIndicesI' function takes a predicate and a stream and
-- returns all indices of the elements in the stream satisfying the
-- predicate.
findIndicesI :: Integral a => (Char -> Bool) -> Stream Char -> [a]
findIndicesI :: forall a. Integral a => (Char -> Bool) -> Stream Char -> [a]
findIndicesI Char -> Bool
p (Stream s -> Step s Char
next s
s0 Size
_len) = a -> s -> [a]
forall {a}. Num a => a -> s -> [a]
loop_findIndex a
0 s
s0
  where
    loop_findIndex :: a -> s -> [a]
loop_findIndex !a
i !s
s = case s -> Step s Char
next s
s of
      Step s Char
Done                   -> []
      Skip    s
s'             -> a -> s -> [a]
loop_findIndex a
i     s
s' -- hmm. not caught by QC
      Yield Char
x s
s' | Char -> Bool
p Char
x       -> a
i a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> s -> [a]
loop_findIndex (a
ia -> a -> a
forall a. Num a => a -> a -> a
+a
1) s
s'
                 | Bool
otherwise -> a -> s -> [a]
loop_findIndex (a
ia -> a -> a
forall a. Num a => a -> a -> a
+a
1) s
s'
{-# INLINE [0] findIndicesI #-}

-------------------------------------------------------------------------------
-- * Zipping

-- | Strict triple.
data Zip a b m = Z1 !a !b
               | Z2 !a !b !m

-- | zipWith generalises 'zip' by zipping with the function given as
-- the first argument, instead of a tupling function.
--
-- __Properties__
--
-- @ 'Data.Text.Internal.Fusion.unstream' ('zipWith' f ('Data.Text.Internal.Fusion.stream' t1) ('Data.Text.Internal.Fusion.stream' t2)) = 'Data.Text.zipWith' f t1 t2@
zipWith :: (a -> a -> b) -> Stream a -> Stream a -> Stream b
zipWith :: forall a b. (a -> a -> b) -> Stream a -> Stream a -> Stream b
zipWith a -> a -> b
f (Stream s -> Step s a
next0 s
sa0 Size
len1) (Stream s -> Step s a
next1 s
sb0 Size
len2) =
    (Zip s s a -> Step (Zip s s a) b) -> Zip s s a -> Size -> Stream b
forall a s. (s -> Step s a) -> s -> Size -> Stream a
Stream Zip s s a -> Step (Zip s s a) b
next (s -> s -> Zip s s a
forall a b m. a -> b -> Zip a b m
Z1 s
sa0 s
sb0) (Size -> Size -> Size
smaller Size
len1 Size
len2)
    where
      next :: Zip s s a -> Step (Zip s s a) b
next (Z1 s
sa s
sb) = case s -> Step s a
next0 s
sa of
                          Step s a
Done -> Step (Zip s s a) b
forall s a. Step s a
Done
                          Skip s
sa' -> Zip s s a -> Step (Zip s s a) b
forall s a. s -> Step s a
Skip (s -> s -> Zip s s a
forall a b m. a -> b -> Zip a b m
Z1 s
sa' s
sb)
                          Yield a
a s
sa' -> Zip s s a -> Step (Zip s s a) b
forall s a. s -> Step s a
Skip (s -> s -> a -> Zip s s a
forall a b m. a -> b -> m -> Zip a b m
Z2 s
sa' s
sb a
a)

      next (Z2 s
sa' s
sb a
a) = case s -> Step s a
next1 s
sb of
                             Step s a
Done -> Step (Zip s s a) b
forall s a. Step s a
Done
                             Skip s
sb' -> Zip s s a -> Step (Zip s s a) b
forall s a. s -> Step s a
Skip (s -> s -> a -> Zip s s a
forall a b m. a -> b -> m -> Zip a b m
Z2 s
sa' s
sb' a
a)
                             Yield a
b s
sb' -> b -> Zip s s a -> Step (Zip s s a) b
forall s a. a -> s -> Step s a
Yield (a -> a -> b
f a
a a
b) (s -> s -> Zip s s a
forall a b m. a -> b -> Zip a b m
Z1 s
sa' s
sb')
{-# INLINE [0] zipWith #-}

-- | /O(n)/ The 'countCharI' function returns the number of times the
-- query element appears in the given stream.
--
-- __Properties__
--
-- @'countCharI' c . 'Data.Text.Internal.Fusion.stream' = 'Data.Text.countChar' c @
countCharI :: Integral a => Char -> Stream Char -> a
countCharI :: forall a. Integral a => Char -> Stream Char -> a
countCharI Char
a (Stream s -> Step s Char
next s
s0 Size
_len) = a -> s -> a
forall {t}. Num t => t -> s -> t
loop a
0 s
s0
  where
    loop :: t -> s -> t
loop !t
i !s
s = case s -> Step s Char
next s
s of
      Step s Char
Done                   -> t
i
      Skip    s
s'             -> t -> s -> t
loop t
i s
s'
      Yield Char
x s
s' | Char
a Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
x    -> t -> s -> t
loop (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1) s
s'
                 | Bool
otherwise -> t -> s -> t
loop t
i s
s'
{-# INLINE [0] countCharI #-}

streamError :: HasCallStack => String -> String -> a
streamError :: forall a. HasCallStack => String -> String -> a
streamError String
func String
msg = String -> a
forall a. HasCallStack => String -> a
P.error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
"Data.Text.Internal.Fusion.Common." String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
func String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
": " String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
msg

emptyError :: HasCallStack => String -> a
emptyError :: forall a. HasCallStack => String -> a
emptyError String
func = String -> String -> a
forall a. HasCallStack => String -> a
internalError String
func String
"Empty input"

internalError :: HasCallStack => String -> a
internalError :: forall a. HasCallStack => String -> a
internalError String
func = String -> String -> a
forall a. HasCallStack => String -> String -> a
streamError String
func String
"Internal error"

int64ToSize :: Int64 -> Size
int64ToSize :: Int64 -> Size
int64ToSize = Int64 -> Size
forall a b. (Integral a, Num b) => a -> b
fromIntegral