{-# LANGUAGE CPP #-}
-- |
-- Module      : Streamly.Internal.Data.Stream.StreamD.Eliminate
-- Copyright   : (c) 2018 Composewell Technologies
--               (c) Roman Leshchinskiy 2008-2010
-- License     : BSD-3-Clause
-- Maintainer  : streamly@composewell.com
-- Stability   : experimental
-- Portability : GHC

-- A few functions in this module have been adapted from the vector package
-- (c) Roman Leshchinskiy.
--
module Streamly.Internal.Data.Stream.StreamD.Eliminate
    (
    -- * Running a 'Fold'
      fold

    -- -- * Running a 'Parser'
    , parse
    , parseD
    , parseBreak
    , parseBreakD

    -- * Stream Deconstruction
    , uncons

    -- * Right Folds
    , foldrM
    , foldr
    , foldrMx
    , foldr1

    -- * Left Folds
    , foldlM'
    , foldl'
    , foldlMx'
    , foldlx'

    -- * Specific Fold Functions
    , drain
    , mapM_ -- Map and Fold
    , null
    , head
    , headElse
    , tail
    , last
    , elem
    , notElem
    , all
    , any
    , maximum
    , maximumBy
    , minimum
    , minimumBy
    , lookup
    , findM
    , find
    , (!!)
    , the

    -- * To containers
    , toList
    , toListRev

    -- * Multi-Stream Folds
    -- ** Comparisons
    -- | These should probably be expressed using zipping operations.
    , eqBy
    , cmpBy

    -- ** Substreams
    -- | These should probably be expressed using parsers.
    , isPrefixOf
    , isInfixOf
    , isSuffixOf
    , isSuffixOfUnbox
    , isSubsequenceOf
    , stripPrefix
    , stripSuffix
    , stripSuffixUnbox
    )
where

#include "inline.hs"

import Control.Exception (assert)
import Control.Monad.IO.Class (MonadIO(..))
import Foreign.Storable (Storable)
import GHC.Exts (SpecConstrAnnotation(..))
import GHC.Types (SPEC(..))
import Streamly.Internal.Data.Parser (ParseError(..))
import Streamly.Internal.Data.SVar.Type (defState)
import Streamly.Internal.Data.Unboxed (Unbox)

import Streamly.Internal.Data.Maybe.Strict (Maybe'(..))

import qualified Streamly.Internal.Data.Array.Type as Array
import qualified Streamly.Internal.Data.Fold as Fold
import qualified Streamly.Internal.Data.Parser as PR
import qualified Streamly.Internal.Data.Parser.ParserD as PRD
import qualified Streamly.Internal.Data.Stream.StreamD.Generate as StreamD
import qualified Streamly.Internal.Data.Stream.StreamD.Nesting as Nesting
import qualified Streamly.Internal.Data.Stream.StreamD.Transform as StreamD

import Prelude hiding
       ( all, any, elem, foldr, foldr1, head, last, lookup, mapM, mapM_
       , maximum, minimum, notElem, null, splitAt, tail, (!!))
import Streamly.Internal.Data.Stream.StreamD.Type

#include "DocTestDataStream.hs"

------------------------------------------------------------------------------
-- Elimination by Folds
------------------------------------------------------------------------------

------------------------------------------------------------------------------
-- Right Folds
------------------------------------------------------------------------------

{-# INLINE_NORMAL foldr1 #-}
foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m (Maybe a)
foldr1 :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> a) -> Stream m a -> m (Maybe a)
foldr1 a -> a -> a
f Stream m a
m = do
     Maybe (a, Stream m a)
r <- forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (a, Stream m a))
uncons Stream m a
m
     case Maybe (a, Stream m a)
r of
         Maybe (a, Stream m a)
Nothing   -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
         Just (a
h, Stream m a
t) -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just (forall (m :: * -> *) a b.
Monad m =>
(a -> b -> b) -> b -> Stream m a -> m b
foldr a -> a -> a
f a
h Stream m a
t)

------------------------------------------------------------------------------
-- Parsers
------------------------------------------------------------------------------

-- Inlined definition. Without the inline "serially/parser/take" benchmark
-- degrades and parseMany does not fuse. Even using "inline" at the callsite
-- does not help.
{-# INLINE splitAt #-}
splitAt :: Int -> [a] -> ([a],[a])
splitAt :: forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [a]
ls
  | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 = ([], [a]
ls)
  | Bool
otherwise          = forall a. Int -> [a] -> ([a], [a])
splitAt' Int
n [a]
ls
    where
        splitAt' :: Int -> [a] -> ([a], [a])
        splitAt' :: forall a. Int -> [a] -> ([a], [a])
splitAt' Int
_  []     = ([], [])
        splitAt' Int
1  (a
x:[a]
xs) = ([a
x], [a]
xs)
        splitAt' Int
m  (a
x:[a]
xs) = (a
xforall a. a -> [a] -> [a]
:[a]
xs', [a]
xs'')
          where
            ([a]
xs', [a]
xs'') = forall a. Int -> [a] -> ([a], [a])
splitAt' (Int
m forall a. Num a => a -> a -> a
- Int
1) [a]
xs

-- GHC parser does not accept {-# ANN type [] NoSpecConstr #-}, so we need
-- to make a newtype.
{-# ANN type List NoSpecConstr #-}
newtype List a = List {forall a. List a -> [a]
getList :: [a]}

-- | Run a 'Parse' over a stream.
{-# INLINE_NORMAL parseD #-}
parseD
    :: Monad m
    => PRD.Parser a m b
    -> Stream m a
    -> m (Either ParseError b)
parseD :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parseD Parser a m b
parser Stream m a
strm = do
    (Either ParseError b
b, Stream m a
_) <- forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD Parser a m b
parser Stream m a
strm
    forall (m :: * -> *) a. Monad m => a -> m a
return Either ParseError b
b

-- | Parse a stream using the supplied 'Parser'.
--
-- Parsers (See "Streamly.Internal.Data.Parser") are more powerful folds that
-- add backtracking and error functionality to terminating folds. Unlike folds,
-- parsers may not always result in a valid output, they may result in an
-- error.  For example:
--
-- >>> Stream.parse (Parser.takeEQ 1 Fold.drain) Stream.nil
-- Left (ParseError "takeEQ: Expecting exactly 1 elements, input terminated on 0")
--
-- Note: @parse p@ is not the same as  @head . parseMany p@ on an empty stream.
--
{-# INLINE [3] parse #-}
parse :: Monad m => PR.Parser a m b -> Stream m a -> m (Either ParseError b)
parse :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parse = forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parseD

-- XXX It may be a good idea to use constant sized chunks for backtracking. We
-- can take a byte stream but when we have to backtrack we create constant
-- sized chunks. We maintain one forward list and one backward list of constant
-- sized chunks, and a last backtracking offset. That way we just need lists of
-- contents and no need to maintain start/end pointers for individual arrays,
-- reducing bookkeeping work.

-- | Run a 'Parse' over a stream and return rest of the Stream.
{-# INLINE_NORMAL parseBreakD #-}
parseBreakD
    :: Monad m
    => PRD.Parser a m b
    -> Stream m a
    -> m (Either ParseError b, Stream m a)
parseBreakD :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD (PRD.Parser s -> a -> m (Step s b)
pstep m (Initial s b)
initial s -> m (Step s b)
extract) stream :: Stream m a
stream@(Stream State StreamK m a -> s -> m (Step s a)
step s
state) = do
    Initial s b
res <- m (Initial s b)
initial
    case Initial s b
res of
        PRD.IPartial s
s -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
state (forall a. [a] -> List a
List []) s
s
        PRD.IDone b
b -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, Stream m a
stream)
        PRD.IError String
err -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), Stream m a
stream)

    where

    -- "buf" contains last few items in the stream that we may have to
    -- backtrack to.
    --
    -- XXX currently we are using a dumb list based approach for backtracking
    -- buffer. This can be replaced by a sliding/ring buffer using Data.Array.
    -- That will allow us more efficient random back and forth movement.
    go :: SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go !SPEC
_ s
st List a
buf !s
pst = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> do
                Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
                case Step s b
pRes of
                    PR.Partial Int
0 s
pst1 -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s (forall a. [a] -> List a
List []) s
pst1
                    PR.Partial Int
1 s
pst1 -> SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
                    PR.Partial Int
n s
pst1 -> do
                        forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List []) (forall a. [a] -> List a
List [a]
src) s
pst1
                    PR.Continue Int
0 s
pst1 -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s (forall a. [a] -> List a
List (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) s
pst1
                    PR.Continue Int
1 s
pst1 -> SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s List a
buf (forall a. [a] -> List a
List [a
x]) s
pst1
                    PR.Continue Int
n s
pst1 -> do
                        forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let ([a]
src0, [a]
buf1) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List [a]
buf1) (forall a. [a] -> List a
List [a]
src) s
pst1
                    PR.Done Int
0 b
b -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    PR.Done Int
n b
b -> do
                        forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        -- XXX This would make it quadratic. We should probably
                        -- use StreamK if we have to append many times.
                        forall (m :: * -> *) a. Monad m => a -> m a
return
                            ( forall a b. b -> Either a b
Right b
b,
                              forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append (forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
                    PR.Error String
err ->
                        forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
            Skip s
s -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s List a
buf s
pst
            Step s a
Stop -> forall {m :: * -> *}.
Applicative m =>
SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst

    go1 :: SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
_ s
s a
x !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s (forall a. [a] -> List a
List []) s
pst1
            PR.Partial Int
1 s
pst1 -> do
                SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
            PR.Partial Int
n s
_ ->
                forall a. (?callStack::CallStack) => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Partial n = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
n
            PR.Continue Int
0 s
pst1 ->
                SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s (forall a. [a] -> List a
List [a
x]) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
            PR.Continue Int
n s
_ -> do
                forall a. (?callStack::CallStack) => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Continue n = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
n
            PR.Done Int
0 b
b -> do
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
            PR.Done Int
1 b
b -> do
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a.
Applicative m =>
a -> Stream m a -> Stream m a
StreamD.cons a
x (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
            PR.Done Int
n b
_ -> do
                forall a. (?callStack::CallStack) => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Done n = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
n
            PR.Error String
err ->
                forall (m :: * -> *) a. Monad m => a -> m a
return
                    ( forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err)
                    , forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append (forall (m :: * -> *) a. Applicative m => a -> Stream m a
fromPure a
x) (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    )

    gobuf :: SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf !SPEC
_ s
s List a
buf (List []) !s
pst = SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s List a
buf s
pst
    gobuf !SPEC
_ s
s List a
buf (List (a
x:[a]
xs)) !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List []) (forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Partial Int
n s
pst1 -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0 forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List []) (forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Continue Int
0 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s List a
buf (forall a. [a] -> List a
List (a
xforall a. a -> [a] -> [a]
:[a]
xs)) s
pst1
            PR.Continue Int
n s
pst1 -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0 forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s (forall a. [a] -> List a
List [a]
buf1) (forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
n b
b -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append (forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
            PR.Error String
err ->
                forall (m :: * -> *) a. Monad m => a -> m a
return
                    ( forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err)
                    , forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append (forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList (a
xforall a. a -> [a] -> [a]
:[a]
xs)) (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    )

    -- This is simplified gobuf
    goExtract :: SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract !SPEC
_ List a
buf (List []) !s
pst = SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst
    goExtract !SPEC
_ List a
buf (List (a
x:[a]
xs)) !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC (forall a. [a] -> List a
List []) (forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Partial Int
n s
pst1 -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0 forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC (forall a. [a] -> List a
List []) (forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Continue Int
0 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC (forall a. [a] -> List a
List (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC List a
buf (forall a. [a] -> List a
List (a
xforall a. a -> [a] -> [a]
:[a]
xs)) s
pst1
            PR.Continue Int
n s
pst1 -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0 forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC (forall a. [a] -> List a
List [a]
buf1) (forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
n b
b -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xforall a. a -> [a] -> [a]
:forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)
            PR.Error String
err -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList (a
xforall a. a -> [a] -> [a]
:[a]
xs))

    -- This is simplified goExtract
    -- XXX Use SPEC?
    {-# INLINE goStop #-}
    goStop :: SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
_ List a
buf s
pst = do
        Step s b
pRes <- s -> m (Step s b)
extract s
pst
        case Step s b
pRes of
            PR.Partial Int
_ s
_ -> forall a. (?callStack::CallStack) => String -> a
error String
"Bug: parseBreak: Partial in extract"
            PR.Continue Int
0 s
pst1 -> SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst1
            PR.Continue Int
n s
pst1 -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC (forall a. [a] -> List a
List [a]
buf1) (forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
0 b
b -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a. Applicative m => Stream m a
StreamD.nil)
            PR.Done Int
n b
b -> do
                forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
<= forall (t :: * -> *) a. Foldable t => t a -> Int
length (forall a. List a -> [a]
getList List a
buf)) (forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = forall a. Int -> [a] -> [a]
Prelude.take Int
n (forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = forall a. [a] -> [a]
Prelude.reverse [a]
src0
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. b -> Either a b
Right b
b, forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)
            PR.Error String
err ->
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), forall (m :: * -> *) a. Applicative m => Stream m a
StreamD.nil)

-- | Parse a stream using the supplied 'Parser'.
--
{-# INLINE parseBreak #-}
parseBreak :: Monad m => PR.Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreak :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreak = forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD

------------------------------------------------------------------------------
-- Specialized Folds
------------------------------------------------------------------------------

-- benchmark after dropping 1 item from stream or using unfolds
{-# INLINE_NORMAL null #-}
null :: Monad m => Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
null = fold Fold.null
#else
null :: forall (m :: * -> *) a. Monad m => Stream m a -> m Bool
null = forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
_ m Bool
_ -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False) (forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True)
#endif

{-# INLINE_NORMAL head #-}
head :: Monad m => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
head = fold Fold.one
#else
head :: forall (m :: * -> *) a. Monad m => Stream m a -> m (Maybe a)
head = forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m (Maybe a)
_ -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
x)) (forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing)
#endif

{-# INLINE_NORMAL headElse #-}
headElse :: Monad m => a -> Stream m a -> m a
headElse :: forall (m :: * -> *) a. Monad m => a -> Stream m a -> m a
headElse a
a = forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m a
_ -> forall (m :: * -> *) a. Monad m => a -> m a
return a
x) (forall (m :: * -> *) a. Monad m => a -> m a
return a
a)

-- Does not fuse, has the same performance as the StreamK version.
{-# INLINE_NORMAL tail #-}
tail :: Monad m => Stream m a -> m (Maybe (Stream m a))
tail :: forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (Stream m a))
tail (UnStream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m (Maybe (Stream m a))
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m (Maybe (Stream m a))
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
_ s
s -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
            Skip  s
s   -> SPEC -> s -> m (Maybe (Stream m a))
go SPEC
SPEC s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing

-- XXX will it fuse? need custom impl?
{-# INLINE_NORMAL last #-}
last :: Monad m => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
last = fold Fold.last
#else
last :: forall (m :: * -> *) a. Monad m => Stream m a -> m (Maybe a)
last = forall (m :: * -> *) b a.
Monad m =>
(b -> a -> b) -> b -> Stream m a -> m b
foldl' (\Maybe a
_ a
y -> forall a. a -> Maybe a
Just a
y) forall a. Maybe a
Nothing
#endif

-- XXX Use the foldrM based impl instead
{-# INLINE_NORMAL elem #-}
elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
elem e = fold (Fold.elem e)
#else
-- elem e m = foldrM (\x xs -> if x == e then return True else xs) (return False) m
elem :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
elem a
e (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
x forall a. Eq a => a -> a -> Bool
== a
e -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
              | Bool
otherwise -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
#endif

{-# INLINE_NORMAL notElem #-}
notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
notElem :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
notElem a
e Stream m a
s = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bool -> Bool
not (forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
elem a
e Stream m a
s)

{-# INLINE_NORMAL all #-}
all :: Monad m => (a -> Bool) -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
all p = fold (Fold.all p)
#else
-- all p m = foldrM (\x xs -> if p x then xs else return False) (return True) m
all :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m Bool
all a -> Bool
p (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a -> Bool
p a
x -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
              | Bool
otherwise -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
#endif

{-# INLINE_NORMAL any #-}
any :: Monad m => (a -> Bool) -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
any p = fold (Fold.any p)
#else
-- any p m = foldrM (\x xs -> if p x then return True else xs) (return False) m
any :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m Bool
any a -> Bool
p (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a -> Bool
p a
x -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
              | Bool
otherwise -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
#endif

{-# INLINE_NORMAL maximum #-}
maximum :: (Monad m, Ord a) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
maximum = fold Fold.maximum
#else
maximum :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
Stream m a -> m (Maybe a)
maximum (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
state
  where
    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
acc forall a. Ord a => a -> a -> Bool
<= a
x  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
              | Bool
otherwise -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL maximumBy #-}
maximumBy :: Monad m => (a -> a -> Ordering) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
maximumBy cmp = fold (Fold.maximumBy cmp)
#else
maximumBy :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> Ordering) -> Stream m a -> m (Maybe a)
maximumBy a -> a -> Ordering
cmp (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
state
  where
    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> case a -> a -> Ordering
cmp a
acc a
x of
                Ordering
GT -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
                Ordering
_  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL minimum #-}
minimum :: (Monad m, Ord a) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
minimum = fold Fold.minimum
#else
minimum :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
Stream m a -> m (Maybe a)
minimum (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
state

    where

    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
acc forall a. Ord a => a -> a -> Bool
<= a
x  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
              | Bool
otherwise -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL minimumBy #-}
minimumBy :: Monad m => (a -> a -> Ordering) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
minimumBy cmp = fold (Fold.minimumBy cmp)
#else
minimumBy :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> Ordering) -> Stream m a -> m (Maybe a)
minimumBy a -> a -> Ordering
cmp (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
state

    where

    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> case a -> a -> Ordering
cmp a
acc a
x of
                Ordering
GT -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
s
                Ordering
_  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL (!!) #-}
(!!) :: (Monad m) => Stream m a -> Int -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
stream !! i = fold (Fold.index i) stream
#else
(Stream State StreamK m a -> s -> m (Step s a)
step s
state) !! :: forall (m :: * -> *) a. Monad m => Stream m a -> Int -> m (Maybe a)
!! Int
i = forall {t}. (Ord t, Num t) => SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC Int
i s
state

    where

    go :: SPEC -> t -> s -> m (Maybe a)
go !SPEC
_ !t
n s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s | t
n forall a. Ord a => a -> a -> Bool
< t
0 -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
                      | t
n forall a. Eq a => a -> a -> Bool
== t
0 -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just a
x
                      | Bool
otherwise -> SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC (t
n forall a. Num a => a -> a -> a
- t
1) s
s
            Skip s
s -> SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC t
n s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
#endif

{-# INLINE_NORMAL lookup #-}
lookup :: (Monad m, Eq a) => a -> Stream m (a, b) -> m (Maybe b)
#ifdef USE_FOLDS_EVERYWHERE
lookup e = fold (Fold.lookup e)
#else
lookup :: forall (m :: * -> *) a b.
(Monad m, Eq a) =>
a -> Stream m (a, b) -> m (Maybe b)
lookup a
e = forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\(a
a, b
b) m (Maybe b)
xs -> if a
e forall a. Eq a => a -> a -> Bool
== a
a then forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just b
b) else m (Maybe b)
xs)
                   (forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing)
#endif

{-# INLINE_NORMAL findM #-}
findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
findM p = fold (Fold.findM p)
#else
findM :: forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Stream m a -> m (Maybe a)
findM a -> m Bool
p = forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m (Maybe a)
xs -> a -> m Bool
p a
x forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Bool
r -> if Bool
r then forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
x) else m (Maybe a)
xs)
                   (forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing)
#endif

{-# INLINE find #-}
find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
find :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m (Maybe a)
find a -> Bool
p = forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Stream m a -> m (Maybe a)
findM (forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

{-# INLINE toListRev #-}
toListRev :: Monad m => Stream m a -> m [a]
#ifdef USE_FOLDS_EVERYWHERE
toListRev = fold Fold.toListRev
#else
toListRev :: forall (m :: * -> *) a. Monad m => Stream m a -> m [a]
toListRev = forall (m :: * -> *) b a.
Monad m =>
(b -> a -> b) -> b -> Stream m a -> m b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) []
#endif

------------------------------------------------------------------------------
-- Transformation comprehensions
------------------------------------------------------------------------------

{-# INLINE_NORMAL the #-}
the :: (Eq a, Monad m) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
the = fold Fold.the
#else
the :: forall a (m :: * -> *).
(Eq a, Monad m) =>
Stream m a -> m (Maybe a)
the (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m (Maybe a)
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m (Maybe a)
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
x s
s
            Skip s
s    -> SPEC -> s -> m (Maybe a)
go SPEC
SPEC s
s
            Step s a
Stop      -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
    go' :: SPEC -> a -> s -> m (Maybe a)
go' !SPEC
_ a
n s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s | a
x forall a. Eq a => a -> a -> Bool
== a
n -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
n s
s
                      | Bool
otherwise -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Skip s
s -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
n s
s
            Step s a
Stop   -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
n)
#endif

------------------------------------------------------------------------------
-- Map and Fold
------------------------------------------------------------------------------

-- | Execute a monadic action for each element of the 'Stream'
{-# INLINE_NORMAL mapM_ #-}
mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
#ifdef USE_FOLDS_EVERYWHERE
mapM_ f = fold (Fold.drainBy f)
#else
mapM_ :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
mapM_ a -> m b
m = forall (m :: * -> *) a. Monad m => Stream m a -> m ()
drain forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> Stream m b
mapM a -> m b
m
#endif

------------------------------------------------------------------------------
-- Multi-stream folds
------------------------------------------------------------------------------

-- | Returns 'True' if the first stream is the same as or a prefix of the
-- second. A stream is a prefix of itself.
--
-- >>> Stream.isPrefixOf (Stream.fromList "hello") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
{-# INLINE_NORMAL isPrefixOf #-}
isPrefixOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isPrefixOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isPrefixOf (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m Bool
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa'    -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop        -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa s
sb'
                    else forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop     -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False

-- | Returns 'True' if all the elements of the first stream occur, in order, in
-- the second stream. The elements do not have to occur consecutively. A stream
-- is a subsequence of itself.
--
-- >>> Stream.isSubsequenceOf (Stream.fromList "hlo") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
{-# INLINE_NORMAL isSubsequenceOf #-}
isSubsequenceOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isSubsequenceOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isSubsequenceOf (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m Bool
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa s
sb'
                    else SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop -> forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False

-- | @stripPrefix prefix input@ strips the @prefix@ stream from the @input@
-- stream if it is a prefix of input. Returns 'Nothing' if the input does not
-- start with the given prefix, stripped input otherwise. Returns @Just nil@
-- when the prefix is the same as the input stream.
--
-- Space: @O(1)@
--
{-# INLINE_NORMAL stripPrefix #-}
stripPrefix
    :: (Monad m, Eq a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa'    -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop        -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just (forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
stepb s
sb)

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC forall a. Maybe' a
Nothing' s
sa s
sb'
                    else forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC (forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop     -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing

-- | Returns 'True' if the first stream is an infix of the second. A stream is
-- considered an infix of itself.
--
-- >>> s = Stream.fromList "hello" :: Stream IO Char
-- >>> Stream.isInfixOf s s
-- True
--
-- Space: @O(n)@ worst case where @n@ is the length of the infix.
--
-- /Pre-release/
--
-- /Requires 'Storable' constraint/
--
{-# INLINE isInfixOf #-}
isInfixOf :: (MonadIO m, Eq a, Enum a, Storable a, Unbox a)
    => Stream m a -> Stream m a -> m Bool
isInfixOf :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Enum a, Storable a, Unbox a) =>
Stream m a -> Stream m a -> m Bool
isInfixOf Stream m a
infx Stream m a
stream = do
    Array a
arr <- forall (m :: * -> *) a b.
Monad m =>
Fold m a b -> Stream m a -> m b
fold forall (m :: * -> *) a. (MonadIO m, Unbox a) => Fold m a (Array a)
Array.write Stream m a
infx
    -- XXX can use breakOnSeq instead (when available)
    Bool
r <- forall (m :: * -> *) a. Monad m => Stream m a -> m Bool
null forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. Monad m => Int -> Stream m a -> Stream m a
StreamD.drop Int
1 forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a b.
(MonadIO m, Storable a, Unbox a, Enum a, Eq a) =>
Array a -> Fold m a b -> Stream m a -> Stream m b
Nesting.splitOnSeq Array a
arr forall (m :: * -> *) a. Monad m => Fold m a ()
Fold.drain Stream m a
stream
    forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Bool
not Bool
r)

-- Note: isPrefixOf uses the prefix stream only once. In contrast, isSuffixOf
-- may use the suffix stream many times. To run in optimal memory we do not
-- want to buffer the suffix stream in memory therefore  we need an ability to
-- clone (or consume it multiple times) the suffix stream without any side
-- effects so that multiple potential suffix matches can proceed in parallel
-- without buffering the suffix stream. For example, we may create the suffix
-- stream from a file handle, however, if we evaluate the stream multiple
-- times, once for each match, we will need a different file handle each time
-- which may exhaust the file descriptors. Instead, we want to share the same
-- underlying file descriptor, use pread on it to generate the stream and clone
-- the stream for each match. Therefore the suffix stream should be built in
-- such a way that it can be consumed multiple times without any problems.

-- XXX Can be implemented with better space/time complexity.
-- Space: @O(n)@ worst case where @n@ is the length of the suffix.

-- | Returns 'True' if the first stream is a suffix of the second. A stream is
-- considered a suffix of itself.
--
-- >>> Stream.isSuffixOf (Stream.fromList "hello") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
-- Space: @O(n)@, buffers entire input stream and the suffix.
--
-- /Pre-release/
--
-- /Suboptimal/ - Help wanted.
--
{-# INLINE isSuffixOf #-}
isSuffixOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isSuffixOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isSuffixOf Stream m a
suffix Stream m a
stream =
    forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
suffix forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
`isPrefixOf` forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
stream

-- | Much faster than 'isSuffixOf'.
{-# INLINE isSuffixOfUnbox #-}
isSuffixOfUnbox :: (MonadIO m, Eq a, Unbox a) =>
    Stream m a -> Stream m a -> m Bool
isSuffixOfUnbox :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Unbox a) =>
Stream m a -> Stream m a -> m Bool
isSuffixOfUnbox Stream m a
suffix Stream m a
stream =
    forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
suffix forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
`isPrefixOf` forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
stream

-- | Drops the given suffix from a stream. Returns 'Nothing' if the stream does
-- not end with the given suffix. Returns @Just nil@ when the suffix is the
-- same as the stream.
--
-- It may be more efficient to convert the stream to an Array and use
-- stripSuffix on that especially if the elements have a Storable or Prim
-- instance.
--
-- See also "Streamly.Internal.Data.Stream.Reduce.dropSuffix".
--
-- Space: @O(n)@, buffers the entire input stream as well as the suffix
--
-- /Pre-release/
{-# INLINE stripSuffix #-}
stripSuffix
    :: (Monad m, Eq a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffix :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffix Stream m a
m1 Stream m a
m2 =
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse
        forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
m1) (forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
m2)

-- | Much faster than 'stripSuffix'.
{-# INLINE stripSuffixUnbox #-}
stripSuffixUnbox
    :: (MonadIO m, Eq a, Unbox a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffixUnbox :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Unbox a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffixUnbox Stream m a
m1 Stream m a
m2 =
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox
        forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
m1) (forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
m2)