1{-# OPTIONS_GHC -Wno-orphans #-}
4-- Module : Streamly.Internal.Data.Parser
5-- Copyright : (c) 2020 Composewell Technologies
6-- License : BSD-3-Clause
7-- Maintainer : streamly@composewell.com
8-- Stability : pre-release
11-- Fast backtracking parsers with stream fusion and native streaming
14-- 'Applicative' and 'Control.Applicative.Alternative' type class based
15-- combinators from the
16-- <http://hackage.haskell.org/package/parser-combinators parser-combinators>
17-- package can also be used with the 'Parser' type. However, there are two
18-- important differences between @parser-combinators@ and the equivalent ones
19-- provided in this module in terms of performance:
21-- 1) @parser-combinators@ use plain Haskell lists to collect the results, in a
22-- strict Monad like IO, the results are necessarily buffered before they can
23-- be consumed. This may not perform optimally in streaming applications
24-- processing large amounts of data. Equivalent combinators in this module can
25-- consume the results of parsing using a 'Fold', thus providing a scalability
26-- and a composable consumer.
28-- 2) Several combinators in this module can be many times faster because of
29-- stream fusion. For example, 'Streamly.Internal.Data.Parser.many' combinator
30-- in this module is much faster than the 'Control.Applicative.many' combinator
31-- of 'Control.Applicative.Alternative' type class.
35-- Failing parsers in this module throw the 'D.ParseError' exception.
39-- As far as possible, try that the names of the combinators in this module are
42-- * <https://hackage.haskell.org/package/base/docs/Text-ParserCombinators-ReadP.html base/Text.ParserCombinators.ReadP>
43-- * <http://hackage.haskell.org/package/parser-combinators parser-combinators>
44-- * <http://hackage.haskell.org/package/megaparsec megaparsec>
45-- * <http://hackage.haskell.org/package/attoparsec attoparsec>
46-- * <http://hackage.haskell.org/package/parsec parsec>
48module Streamly.Internal.Data.Parser
54 -- * Downgrade to Fold
57 -- First order parsers
75 -- | Parsers chained in series, if one parser terminates the composition
78 -- | Grab a sequence of input elements without inspecting them
80 -- , take -- takeBetween 0 n
81 , takeEQ -- takeBetween n n
82 , takeGE -- takeBetween n maxBound
84 -- Grab a sequence of input elements by inspecting them
101 , groupByRollingEither
106 -- , prefixOf -- match any prefix of a given string
107 -- , suffixOf -- match any suffix of a given string
108 -- , infixOf -- match any substring of a given string
111 -- Second order parsers (parsers using parsers)
112 -- * Binary Combinators
114 -- ** Sequential Applicative
118 -- ** Parallel Applicatives
122 -- , teeTill -- like manyTill but parallel
124 -- ** Sequential Interleaving
125 -- Use two folds, run a primary parser, its rejected values go to the
129 -- ** Sequential Alternative
132 -- ** Parallel Alternatives
137 -- * N-ary Combinators
138 -- ** Sequential Collection
142 -- ** Sequential Repetition
154 -- | TODO: traditional implmentations of these may be of limited use. For
155 -- example, consider parsing lines separated by @\\r\\n@. The main parser
156 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
157 -- can apply the "sep" parser.
159 -- We can instead implement these as special cases of deintercalate.
172 -- | A simple and stupid impl would be to just convert the stream to an
173 -- array and give the array reference to all consumers. The array can be
174 -- grown on demand by any consumer and truncated when nonbody needs it.
176 -- ** Distribute to collection
177 -- ** Distribute to repetition
179 -- ** Interleaved collection
186 -- ** Collection of Alternatives
192 -- , fastestN -- first N successful in time
193 -- , choiceN -- first N successful in position
195 , choice -- first successful in position
197 -- ** Repeated Alternatives
204import Control.Monad.Catch (MonadCatch, MonadThrow)
206 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
208import Streamly.Internal.Data.Fold.Type (Fold(..))
209import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
211import qualified Streamly.Internal.Data.Fold.Type as FL
212import qualified Streamly.Internal.Data.Parser.ParserD as D
213import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
218-- >>> :set -package streamly
219-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
220-- >>> import qualified Streamly.Prelude as Stream
221-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
222-- >>> import qualified Streamly.Data.Fold as Fold
223-- >>> import qualified Streamly.Internal.Data.Parser as Parser
225-------------------------------------------------------------------------------
226-- Downgrade a parser to a Fold
227-------------------------------------------------------------------------------
229-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
230-- parser fails or tries to backtrack.
232-- This can be useful in combinators that accept a Fold and we know that a
233-- Parser cannot fail or failure exception is acceptable as there is no way to
239toFold :: MonadThrow m => Parser m a b -> Fold m a b
240toFold p = D.toFold $ D.fromParserK p
242-------------------------------------------------------------------------------
243-- Upgrade folds to parses
244-------------------------------------------------------------------------------
246-- | Make a 'Parser' from a 'Fold'.
250{-# INLINE fromFold #-}
251fromFold :: MonadCatch m => Fold m a b -> Parser m a b
252fromFold = D.toParserK . D.fromFold
254-------------------------------------------------------------------------------
255-- Terminating but not failing folds
256-------------------------------------------------------------------------------
258-- This is the dual of stream "fromPure".
260-- | A parser that always yields a pure value without consuming any input.
264{-# INLINE [3] fromPure #-}
265fromPure :: MonadCatch m => b -> Parser m a b
266fromPure = D.toParserK . D.fromPure
267{-# RULES "fromPure fallback to CPS" [2]
268 forall a. D.toParserK (D.fromPure a) = K.fromPure a #-}
270-- This is the dual of stream "fromEffect".
272-- | A parser that always yields the result of an effectful action without
273-- consuming any input.
277{-# INLINE fromEffect #-}
278fromEffect :: MonadCatch m => m b -> Parser m a b
279fromEffect = K.fromEffect -- D.toParserK . D.fromEffect
281-- This is the dual of "nil".
283-- | A parser that always fails with an error message without consuming
288{-# INLINE [3] die #-}
289die :: MonadCatch m => String -> Parser m a b
290die = D.toParserK . D.die
291{-# RULES "die fallback to CPS" [2]
292 forall a. D.toParserK (D.die a) = K.die a #-}
294-- This is the dual of "nilM".
296-- | A parser that always fails with an effectful error message and without
297-- consuming any input.
302dieM :: MonadCatch m => m String -> Parser m a b
303dieM = D.toParserK . D.dieM
305-------------------------------------------------------------------------------
307-------------------------------------------------------------------------------
309-- | Peek the head element of a stream, without consuming it. Fails if it
310-- encounters end of input.
312-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
316-- peek = lookAhead (satisfy True)
322peek :: MonadCatch m => Parser m a a
323peek = D.toParserK D.peek
325-- | Succeeds if we are at the end of input, fails otherwise.
327-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
333eof :: MonadCatch m => Parser m a ()
334eof = D.toParserK D.eof
336-- | Returns the next element if it passes the predicate, fails otherwise.
338-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
343{-# INLINE satisfy #-}
344satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
345satisfy = D.toParserK . D.satisfy
347-- | Return the next element of the input. Returns 'Nothing'
348-- on end of input. Also known as 'head'.
353next :: MonadCatch m => Parser m a (Maybe a)
354next = D.toParserK D.next
356-- | Map a 'Maybe' returning function on the next element in the stream. The
357-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
363maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
364maybe = D.toParserK . D.maybe
366-- | Map an 'Either' returning function on the next element in the stream. If
367-- the function returns 'Left err', the parser fails with the error message
368-- @err@ otherwise returns the 'Right' value.
373either :: MonadCatch m => (a -> Either String b) -> Parser m a b
374either = D.toParserK . D.either
376-------------------------------------------------------------------------------
378-------------------------------------------------------------------------------
380-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
381-- elements and folds them using the supplied fold.
383-- Stops after @n@ elements.
384-- Fails if the stream ends before @m@ elements could be taken.
390-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
391-- where prsr = Parser.takeBetween low high Fold.toList
396-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
399-- >>> takeBetween' 2 4 [1, 2]
402-- >>> takeBetween' 2 4 [1]
403-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
405-- >>> takeBetween' 0 0 [1, 2]
408-- >>> takeBetween' 0 1 []
411-- @takeBetween@ is the most general take operation, other take operations can
412-- be defined in terms of takeBetween. For example:
415-- take = takeBetween 0 n -- equivalent of take
416-- take1 = takeBetween 1 n -- equivalent of takeLE1
417-- takeEQ = takeBetween n n
418-- takeGE = takeBetween n maxBound
423{-# INLINE takeBetween #-}
424takeBetween :: MonadCatch m =>
425 Int -> Int -> Fold m a b -> Parser m a b
426takeBetween m n = D.toParserK . D.takeBetween m n
428-- | Stops after taking exactly @n@ input elements.
430-- * Stops - after consuming @n@ elements.
431-- * Fails - if the stream or the collecting fold ends before it can collect
432-- exactly @n@ elements.
434-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
435-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
440takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
441takeEQ n = D.toParserK . D.takeEQ n
443-- | Take at least @n@ input elements, but can collect more.
445-- * Stops - when the collecting fold stops.
446-- * Fails - if the stream or the collecting fold ends before producing @n@
449-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
450-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
452-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
458takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
459takeGE n = D.toParserK . D.takeGE n
462-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
464-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
465-- input. The combinator stops when the condition fails or if the collecting
468-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
469-- implemented in terms of this:
472-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
475-- Stops: when the condition fails or the collecting parser stops.
476-- Fails: when the collecting parser fails.
480{-# INLINE takeWhileP #-}
481takeWhileP :: -- MonadCatch m =>
482 (a -> Bool) -> Parser m a b -> Parser m a b
483takeWhileP _cond = undefined -- D.toParserK . D.takeWhileP cond
485-- | Collect stream elements until an element fails the predicate. The element
486-- on which the predicate fails is returned back to the input stream.
488-- * Stops - when the predicate fails or the collecting fold stops.
491-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
494-- We can implement a @breakOn@ using 'takeWhile':
497-- breakOn p = takeWhile (not p)
502{-# INLINE takeWhile #-}
503takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
504takeWhile cond = D.toParserK . D.takeWhile cond
506-- | Like 'takeWhile' but takes at least one element otherwise fails.
510{-# INLINE takeWhile1 #-}
511takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
512takeWhile1 cond = D.toParserK . D.takeWhile1 cond
514-- | Drain the input as long as the predicate succeeds, running the effects and
515-- discarding the results.
517-- This is also called @skipWhile@ in some parsing libraries.
521{-# INLINE drainWhile #-}
522drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
523drainWhile p = takeWhile p FL.drain
525-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
526-- @cond@ succeeds or the parser stops.
528-- This is a generalized slicing parser which can be used to implement other
532-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
533-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
538{-# INLINE sliceSepByP #-}
541 (a -> Bool) -> Parser m a b -> Parser m a b
542sliceSepByP cond = D.toParserK . D.sliceSepByP cond . D.fromParserK
544-- | Like 'sliceSepBy' but does not drop the separator element, instead
545-- separator is emitted as a separate element in the output.
548{-# INLINE sliceSepWith #-}
549sliceSepWith :: -- MonadCatch m =>
550 (a -> Bool) -> Fold m a b -> Parser m a b
551sliceSepWith _cond = undefined -- D.toParserK . D.sliceSepBy cond
553-- | Collect stream elements until an elements passes the predicate, return the
554-- last element on which the predicate succeeded back to the input stream. If
555-- the predicate succeeds on the first element itself then the parser does not
556-- terminate there. The succeeding element in the leading position
557-- is treated as a prefix separator which is kept in the output segment.
559-- * Stops - when the predicate succeeds in non-leading position.
562-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
567-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
568-- where prsr = Parser.sliceBeginWith odd Fold.toList
572-- >>> sliceBeginWithOdd [2, 4, 6, 3]
573-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
576-- >>> sliceBeginWithOdd [3, 5, 7, 4]
579-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
582-- >>> sliceBeginWithOdd []
587{-# INLINE sliceBeginWith #-}
590 (a -> Bool) -> Fold m a b -> Parser m a b
591sliceBeginWith cond = D.toParserK . D.sliceBeginWith cond
593-- | Like 'sliceSepBy' but the separator elements can be escaped using an
594-- escape char determined by the second predicate.
597{-# INLINE escapedSliceSepBy #-}
598escapedSliceSepBy :: -- MonadCatch m =>
599 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
600escapedSliceSepBy _cond _esc = undefined
601 -- D.toParserK . D.escapedSliceSepBy cond esc
603-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
604-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
605-- element to escape the occurrence of the framing elements within the frame.
606-- Nested frames are allowed, but nesting is removed when parsing.
611-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
614-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
617-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
620-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
621-- ParseError "Unterminated '{'"
626{-# INLINE escapedFrameBy #-}
627escapedFrameBy :: -- MonadCatch m =>
628 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
629escapedFrameBy _begin _end _escape _p = undefined
630 -- D.toParserK . D.frameBy begin end escape p
632-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
633-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
634-- @["a","b"]@. In other words, its like parsing words from whitespace
637-- * Stops - when it finds a word separator after a non-word element
641-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
645wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
646wordBy f = D.toParserK . D.wordBy f
648-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
649-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
650-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
651-- then @c@ is also assigned to the same group and so on. When the comparison
652-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
653-- the result of the fold is the result of the parser.
655-- * Stops - when the comparison fails.
661-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
665-- >>> runGroupsBy (<) []
668-- >>> runGroupsBy (<) [1]
671-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
672-- [[3,5,4],[1,2],[0]]
676{-# INLINE groupBy #-}
677groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
678groupBy eq = D.toParserK . D.groupBy eq
680-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
681-- successive elements in the input stream. Assuming the input stream to the
682-- parser is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
683-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
684-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
685-- then @c@ is also assigned to the same group and so on. When the comparison
686-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
687-- the result of the fold is the result of the parser.
689-- * Stops - when the comparison fails.
693-- runGroupsByRolling eq =
695-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
699-- >>> runGroupsByRolling (<) []
702-- >>> runGroupsByRolling (<) [1]
705-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
706-- [[3,5],[4],[1,2],[0]]
710{-# INLINE groupByRolling #-}
711groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
712groupByRolling eq = D.toParserK . D.groupByRolling eq
714-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
715-- the first fold as long as the predicate holds 'True', if the predicate is
716-- 'False' collects using the second fold as long as it remains 'False'.
717-- Returns 'Left' for the first case and 'Right' for the second case.
719-- For example, if we want to detect sorted sequences in a stream, both
720-- ascending and descending cases we can use 'groupByRollingEither (<=)
721-- Fold.toList Fold.toList'.
724{-# INLINE groupByRollingEither #-}
725groupByRollingEither :: MonadCatch m =>
726 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser m a (Either b c)
727groupByRollingEither eq f1 = D.toParserK . D.groupByRollingEither eq f1
729-- | Match the given sequence of elements using the given comparison function.
731-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
733-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
734-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
739eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
740eqBy cmp = D.toParserK . D.eqBy cmp
742-------------------------------------------------------------------------------
744-------------------------------------------------------------------------------
746-- | Sequential parser application. Apply two parsers sequentially to an input
747-- stream. The input is provided to the first parser, when it is done the
748-- remaining input is provided to the second parser. If both the parsers
749-- succeed their outputs are combined using the supplied function. The
750-- operation fails if any of the parsers fail.
752-- Note: This is a parsing dual of appending streams using
753-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
756-- This implementation is strict in the second argument, therefore, the
757-- following will fail:
759-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
760-- *** Exception: Prelude.undefined
763-- Compare with 'Applicative' instance method '<*>'. This implementation allows
764-- stream fusion but has quadratic complexity. This can fuse with other
765-- operations and can be faster than 'Applicative' instance for small number
766-- (less than 8) of compositions.
768-- Many combinators can be expressed using @serialWith@ and other parser
769-- primitives. Some common idioms are described below,
772-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
773-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
777-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
778-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
782-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
783-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
788{-# INLINE serialWith #-}
789serialWith :: MonadCatch m
790 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
792 D.toParserK $ D.serialWith f (D.fromParserK p1) (D.fromParserK p2)
794-- | Sequential parser application ignoring the output of the first parser.
795-- Apply two parsers sequentially to an input stream. The input is provided to
796-- the first parser, when it is done the remaining input is provided to the
797-- second parser. The output of the parser is the output of the second parser.
798-- The operation fails if any of the parsers fail.
800-- This implementation is strict in the second argument, therefore, the
801-- following will fail:
803-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
804-- *** Exception: Prelude.undefined
807-- Compare with 'Applicative' instance method '*>'. This implementation allows
808-- stream fusion but has quadratic complexity. This can fuse with other
809-- operations, and can be faster than 'Applicative' instance for small
810-- number (less than 8) of compositions.
815split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
816split_ p1 p2 = D.toParserK $ D.split_ (D.fromParserK p1) (D.fromParserK p2)
818-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
819-- of them succeed or anyone of them fails and combines their output using @f@.
820-- The parser succeeds if both the parsers succeed.
824{-# INLINE teeWith #-}
825teeWith :: MonadCatch m
826 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
828 D.toParserK $ D.teeWith f (D.fromParserK p1) (D.fromParserK p2)
830-- | Like 'teeWith' but ends parsing and zips the results, if available,
831-- whenever the first parser ends.
835{-# INLINE teeWithFst #-}
836teeWithFst :: MonadCatch m
837 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
839 D.toParserK $ D.teeWithFst f (D.fromParserK p1) (D.fromParserK p2)
841-- | Like 'teeWith' but ends parsing and zips the results, if available,
842-- whenever any of the parsers ends or fails.
846{-# INLINE teeWithMin #-}
847teeWithMin :: MonadCatch m
848 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
850 D.toParserK $ D.teeWithMin f (D.fromParserK p1) (D.fromParserK p2)
852-- | Sequential alternative. Apply the input to the first parser and return the
853-- result if the parser succeeds. If the first parser fails then backtrack and
854-- apply the same input to the second parser and return the result.
856-- Note: This implementation is not lazy in the second argument. The following
859-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
862-- Compare with 'Alternative' instance method '<|>'. This implementation allows
863-- stream fusion but has quadratic complexity. This can fuse with other
864-- operations and can be much faster than 'Alternative' instance for small
865-- number (less than 8) of alternatives.
870alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
871alt p1 p2 = D.toParserK $ D.alt (D.fromParserK p1) (D.fromParserK p2)
873-- | Shortest alternative. Apply both parsers in parallel but choose the result
874-- from the one which consumed least input i.e. take the shortest succeeding
879{-# INLINE shortest #-}
880shortest :: MonadCatch m
881 => Parser m x a -> Parser m x a -> Parser m x a
882shortest p1 p2 = D.toParserK $ D.shortest (D.fromParserK p1) (D.fromParserK p2)
884-- | Longest alternative. Apply both parsers in parallel but choose the result
885-- from the one which consumed more input i.e. take the longest succeeding
890{-# INLINE longest #-}
891longest :: MonadCatch m
892 => Parser m x a -> Parser m x a -> Parser m x a
893longest p1 p2 = D.toParserK $ D.longest (D.fromParserK p1) (D.fromParserK p2)
895-- | Run a parser without consuming the input.
899{-# INLINE lookAhead #-}
900lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
901lookAhead p = D.toParserK $ D.lookAhead $ D.fromParserK p
903-- | Takes at-most @n@ input elements.
905-- * Stops - when the collecting parser stops.
906-- * Fails - when the collecting parser fails.
908-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
911-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
912-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
916takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
917takeP i p = D.toParserK $ D.takeP i $ D.fromParserK p
919-------------------------------------------------------------------------------
921-------------------------------------------------------------------------------
923-- To deinterleave we can chain two parsers one behind the other. The input is
924-- given to the first parser and the input definitively rejected by the first
925-- parser is given to the second parser.
927-- We can either have the parsers themselves buffer the input or use the shared
928-- global buffer to hold it until none of the parsers need it. When the first
929-- parser returns Skip (i.e. rewind) we let the second parser consume the
930-- rejected input and when it is done we move the cursor forward to the first
931-- parser again. This will require a "move forward" command as well.
933-- To implement grep we can use three parsers, one to find the pattern, one
934-- to store the context behind the pattern and one to store the context in
935-- front of the pattern. When a match occurs we need to emit the accumulator of
936-- all the three parsers. One parser can count the line numbers to provide the
939-- | Apply two parsers alternately to an input stream. The input stream is
940-- considered an interleaving of two patterns. The two parsers represent the
943-- This undoes a "gintercalate" of two streams.
947{-# INLINE deintercalate #-}
950 Fold m a y -> Parser m x a
951 -> Fold m b z -> Parser m x b
953deintercalate = undefined
955-------------------------------------------------------------------------------
956-- Sequential Collection
957-------------------------------------------------------------------------------
959-- | @concatSequence f t@ collects sequential parses of parsers in the
960-- container @t@ using the fold @f@. Fails if the input ends or any of the
963-- This is same as 'Data.Traversable.sequence' but more efficient.
967{-# INLINE concatSequence #-}
970 Fold m b c -> t (Parser m a b) -> Parser m a c
971concatSequence _f _p = undefined
973-- | Map a 'Parser' returning function on the result of a 'Parser'.
975-- Compare with 'Monad' instance method '>>='. This implementation allows
976-- stream fusion but has quadratic complexity. This can fuse with other
977-- operations and can be much faster than 'Monad' instance for small number
978-- (less than 8) of compositions.
982{-# INLINE concatMap #-}
983concatMap :: MonadCatch m
984 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
985concatMap f p = D.toParserK $ D.concatMap (D.fromParserK . f) (D.fromParserK p)
987-------------------------------------------------------------------------------
988-- Alternative Collection
989-------------------------------------------------------------------------------
991-- | @choice parsers@ applies the @parsers@ in order and returns the first
994-- This is same as 'asum' but more efficient.
1000 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
1001choice ps = D.toParserK $ D.choice $ D.fromParserK <$> ps
1003-------------------------------------------------------------------------------
1004-- Sequential Repetition
1005-------------------------------------------------------------------------------
1008-- TODO "many" is essentially a Fold because it cannot fail. So it can be
1009-- downgraded to a Fold. Or we can make the return type a Fold instead and
1010-- upgrade that to a parser when needed.
1012-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1013-- results. Parsing stops or fails if the collecting parser stops or fails.
1018manyP :: -- MonadCatch m =>
1019 Parser m a b -> Parser m b c -> Parser m a c
1020manyP _p _f = undefined -- D.toParserK $ D.manyP (D.fromParserK p) f
1022-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1023-- input stream and push the parse results to a downstream fold.
1025-- Stops: when the downstream fold stops or the parser fails.
1026-- Fails: never, produces zero or more results.
1028-- Compare with 'Control.Applicative.many'.
1033many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1034many p f = D.toParserK $ D.many (D.fromParserK p) f
1035-- many = countBetween 0 maxBound
1037-- Note: many1 would perhaps be a better name for this and consistent with
1038-- other names like takeWhile1. But we retain the name "some" for
1041-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1042-- input stream and push the parse results to a downstream fold.
1044-- Stops: when the downstream fold stops or the parser fails.
1045-- Fails: if it stops without producing a single result.
1047-- @some fld parser = manyP (takeGE 1 fld) parser@
1049-- Compare with 'Control.Applicative.some'.
1054some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1055some p f = D.toParserK $ D.some (D.fromParserK p) f
1056-- some p f = manyP p (takeGE 1 f)
1057-- many = countBetween 1 maxBound
1059-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1060-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1061-- the input ends or the parser fails before @m@ results are collected.
1065{-# INLINE countBetween #-}
1068 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1069countBetween _m _n _p = undefined
1070-- countBetween m n p f = manyP (takeBetween m n f) p
1072-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1073-- the fold @f@. Fails if the input ends or the parser fails before @n@
1074-- results are collected.
1081 Int -> Parser m a b -> Fold m b c -> Parser m a c
1082count n = countBetween n n
1083-- count n p f = manyP (takeEQ n f) p
1085-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1086-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1088-- We can implemnent parsers like the following using 'manyTillP':
1091-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1096{-# INLINE manyTillP #-}
1097manyTillP :: -- MonadCatch m =>
1098 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1099manyTillP _p1 _p2 _f = undefined
1100 -- D.toParserK $ D.manyTillP (D.fromParserK p1) (D.fromParserK p2) f
1102-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1103-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1104-- tried again and so on. The parser stops when @test@ succeeds. The output of
1105-- @test@ is discarded and the output of @collect@ is accumulated by the
1106-- supplied fold. The parser fails if @collect@ fails.
1108-- Stops when the fold @f@ stops.
1112{-# INLINE manyTill #-}
1113manyTill :: MonadCatch m
1114 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1116 D.toParserK $ D.manyTill f (D.fromParserK p1) (D.fromParserK p2)
1118-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1119-- collects the output in the supplied fold. If the the parser @collect@ fails,
1120-- parser @recover@ is run until it stops and then we start repeating the
1121-- parser @collect@ again. The parser fails if the recovery parser fails.
1123-- For example, this can be used to find a key frame in a video stream after an
1128{-# INLINE manyThen #-}
1129manyThen :: -- (Foldable t, MonadCatch m) =>
1130 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1131manyThen _parser _recover _f = undefined
1133-------------------------------------------------------------------------------
1134-- Interleaving a collection of parsers
1135-------------------------------------------------------------------------------
1137-- | Apply a collection of parsers to an input stream in a round robin fashion.
1138-- Each parser is applied until it stops and then we repeat starting with the
1139-- the first parser again.
1143{-# INLINE roundRobin #-}
1144roundRobin :: -- (Foldable t, MonadCatch m) =>
1145 t (Parser m a b) -> Fold m b c -> Parser m a c
1146roundRobin _ps _f = undefined
1148-------------------------------------------------------------------------------
1149-- Repeated Alternatives
1150-------------------------------------------------------------------------------
1152-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1153-- fails the input consumed till now is dropped and the new instance is tried
1154-- on the fresh input.
1158{-# INLINE retryMaxTotal #-}
1159retryMaxTotal :: -- (MonadCatch m) =>
1160 Int -> Parser m a b -> Fold m b c -> Parser m a c
1161retryMaxTotal _n _p _f = undefined
1163-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1167{-# INLINE retryMaxSuccessive #-}
1168retryMaxSuccessive :: -- (MonadCatch m) =>
1169 Int -> Parser m a b -> Fold m b c -> Parser m a c
1170retryMaxSuccessive _n _p _f = undefined
1172-- | Keep trying a parser until it succeeds. When the parser fails the input
1173-- consumed till now is dropped and the new instance is tried on the fresh
1179retry :: -- (MonadCatch m) =>
1180 Parser m a b -> Parser m a b
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list