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 -- First order parsers
71 -- | Parsers chained in series, if one parser terminates the composition
74 -- | Grab a sequence of input elements without inspecting them
76 -- , take -- takeBetween 0 n
77 , takeEQ -- takeBetween n n
78 , takeGE -- takeBetween n maxBound
80 -- Grab a sequence of input elements by inspecting them
101 -- , prefixOf -- match any prefix of a given string
102 -- , suffixOf -- match any suffix of a given string
103 -- , infixOf -- match any substring of a given string
106 -- Second order parsers (parsers using parsers)
107 -- * Binary Combinators
109 -- ** Sequential Applicative
113 -- ** Parallel Applicatives
117 -- , teeTill -- like manyTill but parallel
119 -- ** Sequential Interleaving
120 -- Use two folds, run a primary parser, its rejected values go to the
124 -- ** Sequential Alternative
127 -- ** Parallel Alternatives
132 -- * N-ary Combinators
133 -- ** Sequential Collection
137 -- ** Sequential Repetition
149 -- | TODO: traditional implmentations of these may be of limited use. For
150 -- example, consider parsing lines separated by @\\r\\n@. The main parser
151 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
152 -- can apply the "sep" parser.
154 -- We can instead implement these as special cases of deintercalate.
167 -- | A simple and stupid impl would be to just convert the stream to an
168 -- array and give the array reference to all consumers. The array can be
169 -- grown on demand by any consumer and truncated when nonbody needs it.
171 -- ** Distribute to collection
172 -- ** Distribute to repetition
174 -- ** Interleaved collection
181 -- ** Collection of Alternatives
187 -- , fastestN -- first N successful in time
188 -- , choiceN -- first N successful in position
190 , choice -- first successful in position
192 -- ** Repeated Alternatives
199import Control.Monad.Catch (MonadCatch)
201 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
203import Streamly.Internal.Data.Fold.Type (Fold(..))
204import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
206import qualified Streamly.Internal.Data.Fold.Type as FL
207import qualified Streamly.Internal.Data.Parser.ParserD as D
208import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
213-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
214-- >>> import qualified Streamly.Prelude as Stream
215-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
216-- >>> import qualified Streamly.Data.Fold as Fold
217-- >>> import qualified Streamly.Internal.Data.Parser as Parser
219-------------------------------------------------------------------------------
220-- Upgrade folds to parses
221-------------------------------------------------------------------------------
223-- | Make a 'Parser' from a 'Fold'.
227{-# INLINE fromFold #-}
228fromFold :: MonadCatch m => Fold m a b -> Parser m a b
229fromFold = K.toParserK . D.fromFold
231-------------------------------------------------------------------------------
232-- Terminating but not failing folds
233-------------------------------------------------------------------------------
235-- This is the dual of stream "fromPure".
237-- | A parser that always yields a pure value without consuming any input.
241{-# INLINE [3] fromPure #-}
242fromPure :: MonadCatch m => b -> Parser m a b
243fromPure = K.toParserK . D.fromPure
244{-# RULES "fromPure fallback to CPS" [2]
245 forall a. K.toParserK (D.fromPure a) = K.fromPure a #-}
247-- This is the dual of stream "fromEffect".
249-- | A parser that always yields the result of an effectful action without
250-- consuming any input.
254{-# INLINE fromEffect #-}
255fromEffect :: MonadCatch m => m b -> Parser m a b
256fromEffect = K.fromEffect -- K.toParserK . D.fromEffect
258-- This is the dual of "nil".
260-- | A parser that always fails with an error message without consuming
265{-# INLINE [3] die #-}
266die :: MonadCatch m => String -> Parser m a b
267die = K.toParserK . D.die
268{-# RULES "die fallback to CPS" [2]
269 forall a. K.toParserK (D.die a) = K.die a #-}
271-- This is the dual of "nilM".
273-- | A parser that always fails with an effectful error message and without
274-- consuming any input.
279dieM :: MonadCatch m => m String -> Parser m a b
280dieM = K.toParserK . D.dieM
282-------------------------------------------------------------------------------
284-------------------------------------------------------------------------------
286-- | Peek the head element of a stream, without consuming it. Fails if it
287-- encounters end of input.
289-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
293-- peek = lookAhead (satisfy True)
299peek :: MonadCatch m => Parser m a a
300peek = K.toParserK D.peek
302-- | Succeeds if we are at the end of input, fails otherwise.
304-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
310eof :: MonadCatch m => Parser m a ()
311eof = K.toParserK D.eof
313-- | Returns the next element if it passes the predicate, fails otherwise.
315-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
320{-# INLINE satisfy #-}
321satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
322satisfy = K.toParserK . D.satisfy
324-- | Map a 'Maybe' returning function on the next element in the stream. The
325-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
331maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
332maybe = K.toParserK . D.maybe
334-- | Map an 'Either' returning function on the next element in the stream. If
335-- the function returns 'Left err', the parser fails with the error message
336-- @err@ otherwise returns the 'Right' value.
341either :: MonadCatch m => (a -> Either String b) -> Parser m a b
342either = K.toParserK . D.either
344-------------------------------------------------------------------------------
346-------------------------------------------------------------------------------
348-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
349-- elements and folds them using the supplied fold.
351-- Stops after @n@ elements.
352-- Fails if the stream ends before @m@ elements could be taken.
358-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
359-- where prsr = Parser.takeBetween low high Fold.toList
364-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
367-- >>> takeBetween' 2 4 [1, 2]
370-- >>> takeBetween' 2 4 [1]
371-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
373-- >>> takeBetween' 0 0 [1, 2]
376-- >>> takeBetween' 0 1 []
379-- @takeBetween@ is the most general take operation, other take operations can
380-- be defined in terms of takeBetween. For example:
383-- take = takeBetween 0 n -- equivalent of take
384-- take1 = takeBetween 1 n -- equivalent of takeLE1
385-- takeEQ = takeBetween n n
386-- takeGE = takeBetween n maxBound
391{-# INLINE takeBetween #-}
392takeBetween :: MonadCatch m =>
393 Int -> Int -> Fold m a b -> Parser m a b
394takeBetween m n = K.toParserK . D.takeBetween m n
396-- | Stops after taking exactly @n@ input elements.
398-- * Stops - after consuming @n@ elements.
399-- * Fails - if the stream or the collecting fold ends before it can collect
400-- exactly @n@ elements.
402-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
403-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
408takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
409takeEQ n = K.toParserK . D.takeEQ n
411-- | Take at least @n@ input elements, but can collect more.
413-- * Stops - when the collecting fold stops.
414-- * Fails - if the stream or the collecting fold ends before producing @n@
417-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
418-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
420-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
426takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
427takeGE n = K.toParserK . D.takeGE n
430-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
432-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
433-- input. The combinator stops when the condition fails or if the collecting
436-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
437-- implemented in terms of this:
440-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
443-- Stops: when the condition fails or the collecting parser stops.
444-- Fails: when the collecting parser fails.
448{-# INLINE takeWhileP #-}
449takeWhileP :: -- MonadCatch m =>
450 (a -> Bool) -> Parser m a b -> Parser m a b
451takeWhileP _cond = undefined -- K.toParserK . D.takeWhileP cond
453-- | Collect stream elements until an element fails the predicate. The element
454-- on which the predicate fails is returned back to the input stream.
456-- * Stops - when the predicate fails or the collecting fold stops.
459-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
462-- We can implement a @breakOn@ using 'takeWhile':
465-- breakOn p = takeWhile (not p)
470{-# INLINE takeWhile #-}
471takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
472takeWhile cond = K.toParserK . D.takeWhile cond
474-- | Like 'takeWhile' but takes at least one element otherwise fails.
478{-# INLINE takeWhile1 #-}
479takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
480takeWhile1 cond = K.toParserK . D.takeWhile1 cond
482-- | Drain the input as long as the predicate succeeds, running the effects and
483-- discarding the results.
485-- This is also called @skipWhile@ in some parsing libraries.
489{-# INLINE drainWhile #-}
490drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
491drainWhile p = takeWhile p FL.drain
493-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
494-- @cond@ succeeds or the parser stops.
496-- This is a generalized slicing parser which can be used to implement other
500-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
501-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
506{-# INLINABLE sliceSepByP #-}
509 (a -> Bool) -> Parser m a b -> Parser m a b
510sliceSepByP cond = K.toParserK . D.sliceSepByP cond . K.fromParserK
512-- | Like 'sliceSepBy' but does not drop the separator element, instead
513-- separator is emitted as a separate element in the output.
516{-# INLINABLE sliceSepWith #-}
517sliceSepWith :: -- MonadCatch m =>
518 (a -> Bool) -> Fold m a b -> Parser m a b
519sliceSepWith _cond = undefined -- K.toParserK . D.sliceSepBy cond
521-- | Collect stream elements until an elements passes the predicate, return the
522-- last element on which the predicate succeeded back to the input stream. If
523-- the predicate succeeds on the first element itself then the parser does not
524-- terminate there. The succeeding element in the leading position
525-- is treated as a prefix separator which is kept in the output segment.
527-- * Stops - when the predicate succeeds in non-leading position.
530-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
535-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
536-- where prsr = Parser.sliceBeginWith odd Fold.toList
540-- >>> sliceBeginWithOdd [2, 4, 6, 3]
541-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
544-- >>> sliceBeginWithOdd [3, 5, 7, 4]
547-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
550-- >>> sliceBeginWithOdd []
555{-# INLINABLE sliceBeginWith #-}
558 (a -> Bool) -> Fold m a b -> Parser m a b
559sliceBeginWith cond = K.toParserK . D.sliceBeginWith cond
561-- | Like 'sliceSepBy' but the separator elements can be escaped using an
562-- escape char determined by the second predicate.
565{-# INLINABLE escapedSliceSepBy #-}
566escapedSliceSepBy :: -- MonadCatch m =>
567 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
568escapedSliceSepBy _cond _esc = undefined
569 -- K.toParserK . D.escapedSliceSepBy cond esc
571-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
572-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
573-- element to escape the occurrence of the framing elements within the frame.
574-- Nested frames are allowed, but nesting is removed when parsing.
579-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
582-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
585-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
588-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
589-- ParseError "Unterminated '{'"
594{-# INLINABLE escapedFrameBy #-}
595escapedFrameBy :: -- MonadCatch m =>
596 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
597escapedFrameBy _begin _end _escape _p = undefined
598 -- K.toParserK . D.frameBy begin end escape p
600-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
601-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
602-- @["a","b"]@. In other words, its like parsing words from whitespace
605-- * Stops - when it finds a word separator after a non-word element
609-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
613wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
614wordBy f = K.toParserK . D.wordBy f
616-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
617-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
618-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
619-- then @c@ is also assigned to the same group and so on. When the comparison
620-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
621-- the result of the fold is the result of the parser.
623-- * Stops - when the comparison fails.
629-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
633-- >>> runGroupsBy (<) []
636-- >>> runGroupsBy (<) [1]
639-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
640-- [[3,5,4],[1,2],[0]]
644{-# INLINABLE groupBy #-}
645groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
646groupBy eq = K.toParserK . D.groupBy eq
648-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
649-- successive elements in the input stream. Assuming the input stream to the
650-- parser is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
651-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
652-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
653-- then @c@ is also assigned to the same group and so on. When the comparison
654-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
655-- the result of the fold is the result of the parser.
657-- * Stops - when the comparison fails.
661-- runGroupsByRolling eq =
663-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
667-- >>> runGroupsByRolling (<) []
670-- >>> runGroupsByRolling (<) [1]
673-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
674-- [[3,5],[4],[1,2],[0]]
678{-# INLINABLE groupByRolling #-}
679groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
680groupByRolling eq = K.toParserK . D.groupByRolling eq
682-- | Match the given sequence of elements using the given comparison function.
684-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
686-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
687-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
692eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
693eqBy cmp = K.toParserK . D.eqBy cmp
695-------------------------------------------------------------------------------
697-------------------------------------------------------------------------------
699-- | Sequential parser application. Apply two parsers sequentially to an input
700-- stream. The input is provided to the first parser, when it is done the
701-- remaining input is provided to the second parser. If both the parsers
702-- succeed their outputs are combined using the supplied function. The
703-- operation fails if any of the parsers fail.
705-- Note: This is a parsing dual of appending streams using
706-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
709-- This implementation is strict in the second argument, therefore, the
710-- following will fail:
712-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
713-- *** Exception: Prelude.undefined
716-- Compare with 'Applicative' instance method '<*>'. This implementation allows
717-- stream fusion but has quadratic complexity. This can fuse with other
718-- operations and can be faster than 'Applicative' instance for small number
719-- (less than 8) of compositions.
721-- Many combinators can be expressed using @serialWith@ and other parser
722-- primitives. Some common idioms are described below,
725-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
726-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
730-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
731-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
735-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
736-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
741{-# INLINE serialWith #-}
742serialWith :: MonadCatch m
743 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
745 K.toParserK $ D.serialWith f (K.fromParserK p1) (K.fromParserK p2)
747-- | Sequential parser application ignoring the output of the first parser.
748-- Apply two parsers sequentially to an input stream. The input is provided to
749-- the first parser, when it is done the remaining input is provided to the
750-- second parser. The output of the parser is the output of the second parser.
751-- The operation fails if any of the parsers fail.
753-- This implementation is strict in the second argument, therefore, the
754-- following will fail:
756-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
757-- *** Exception: Prelude.undefined
760-- Compare with 'Applicative' instance method '*>'. This implementation allows
761-- stream fusion but has quadratic complexity. This can fuse with other
762-- operations, and can be faster than 'Applicative' instance for small
763-- number (less than 8) of compositions.
768split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
769split_ p1 p2 = K.toParserK $ D.split_ (K.fromParserK p1) (K.fromParserK p2)
771-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
772-- of them succeed or anyone of them fails and combines their output using @f@.
773-- The parser succeeds if both the parsers succeed.
777{-# INLINE teeWith #-}
778teeWith :: MonadCatch m
779 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
781 K.toParserK $ D.teeWith f (K.fromParserK p1) (K.fromParserK p2)
783-- | Like 'teeWith' but ends parsing and zips the results, if available,
784-- whenever the first parser ends.
788{-# INLINE teeWithFst #-}
789teeWithFst :: MonadCatch m
790 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
792 K.toParserK $ D.teeWithFst f (K.fromParserK p1) (K.fromParserK p2)
794-- | Like 'teeWith' but ends parsing and zips the results, if available,
795-- whenever any of the parsers ends or fails.
799{-# INLINE teeWithMin #-}
800teeWithMin :: MonadCatch m
801 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
803 K.toParserK $ D.teeWithMin f (K.fromParserK p1) (K.fromParserK p2)
805-- | Sequential alternative. Apply the input to the first parser and return the
806-- result if the parser succeeds. If the first parser fails then backtrack and
807-- apply the same input to the second parser and return the result.
809-- Note: This implementation is not lazy in the second argument. The following
812-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
815-- Compare with 'Alternative' instance method '<|>'. This implementation allows
816-- stream fusion but has quadratic complexity. This can fuse with other
817-- operations and can be much faster than 'Alternative' instance for small
818-- number (less than 8) of alternatives.
823alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
824alt p1 p2 = K.toParserK $ D.alt (K.fromParserK p1) (K.fromParserK p2)
826-- | Shortest alternative. Apply both parsers in parallel but choose the result
827-- from the one which consumed least input i.e. take the shortest succeeding
832{-# INLINE shortest #-}
833shortest :: MonadCatch m
834 => Parser m x a -> Parser m x a -> Parser m x a
835shortest p1 p2 = K.toParserK $ D.shortest (K.fromParserK p1) (K.fromParserK p2)
837-- | Longest alternative. Apply both parsers in parallel but choose the result
838-- from the one which consumed more input i.e. take the longest succeeding
843{-# INLINE longest #-}
844longest :: MonadCatch m
845 => Parser m x a -> Parser m x a -> Parser m x a
846longest p1 p2 = K.toParserK $ D.longest (K.fromParserK p1) (K.fromParserK p2)
848-- | Run a parser without consuming the input.
852{-# INLINE lookAhead #-}
853lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
854lookAhead p = K.toParserK $ D.lookAhead $ K.fromParserK p
856-- | Takes at-most @n@ input elements.
858-- * Stops - when the collecting parser stops.
859-- * Fails - when the collecting parser fails.
861-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
864-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
865-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
869takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
870takeP i p = K.toParserK $ D.takeP i $ K.fromParserK p
872-------------------------------------------------------------------------------
874-------------------------------------------------------------------------------
876-- To deinterleave we can chain two parsers one behind the other. The input is
877-- given to the first parser and the input definitively rejected by the first
878-- parser is given to the second parser.
880-- We can either have the parsers themselves buffer the input or use the shared
881-- global buffer to hold it until none of the parsers need it. When the first
882-- parser returns Skip (i.e. rewind) we let the second parser consume the
883-- rejected input and when it is done we move the cursor forward to the first
884-- parser again. This will require a "move forward" command as well.
886-- To implement grep we can use three parsers, one to find the pattern, one
887-- to store the context behind the pattern and one to store the context in
888-- front of the pattern. When a match occurs we need to emit the accumulator of
889-- all the three parsers. One parser can count the line numbers to provide the
892-- | Apply two parsers alternately to an input stream. The input stream is
893-- considered an interleaving of two patterns. The two parsers represent the
896-- This undoes a "gintercalate" of two streams.
900{-# INLINE deintercalate #-}
903 Fold m a y -> Parser m x a
904 -> Fold m b z -> Parser m x b
906deintercalate = undefined
908-------------------------------------------------------------------------------
909-- Sequential Collection
910-------------------------------------------------------------------------------
912-- | @concatSequence f t@ collects sequential parses of parsers in the
913-- container @t@ using the fold @f@. Fails if the input ends or any of the
916-- This is same as 'Data.Traversable.sequence' but more efficient.
920{-# INLINE concatSequence #-}
923 Fold m b c -> t (Parser m a b) -> Parser m a c
924concatSequence _f _p = undefined
926-- | Map a 'Parser' returning function on the result of a 'Parser'.
928-- Compare with 'Monad' instance method '>>='. This implementation allows
929-- stream fusion but has quadratic complexity. This can fuse with other
930-- operations and can be much faster than 'Monad' instance for small number
931-- (less than 8) of compositions.
935{-# INLINE concatMap #-}
936concatMap :: MonadCatch m
937 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
938concatMap f p = K.toParserK $ D.concatMap (K.fromParserK . f) (K.fromParserK p)
940-------------------------------------------------------------------------------
941-- Alternative Collection
942-------------------------------------------------------------------------------
944-- | @choice parsers@ applies the @parsers@ in order and returns the first
947-- This is same as 'asum' but more efficient.
953 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
954choice ps = K.toParserK $ D.choice $ K.fromParserK <$> ps
956-------------------------------------------------------------------------------
957-- Sequential Repetition
958-------------------------------------------------------------------------------
961-- TODO "many" is essentially a Fold because it cannot fail. So it can be
962-- downgraded to a Fold. Or we can make the return type a Fold instead and
963-- upgrade that to a parser when needed.
965-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
966-- results. Parsing stops or fails if the collecting parser stops or fails.
971manyP :: -- MonadCatch m =>
972 Parser m a b -> Parser m b c -> Parser m a c
973manyP _p _f = undefined -- K.toParserK $ D.manyP (K.fromParserK p) f
975-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
976-- input stream and push the parse results to a downstream fold.
978-- Stops: when the downstream fold stops or the parser fails.
979-- Fails: never, produces zero or more results.
981-- Compare with 'Control.Applicative.many'.
986many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
987many p f = K.toParserK $ D.many (K.fromParserK p) f
988-- many = countBetween 0 maxBound
990-- Note: many1 would perhaps be a better name for this and consistent with
991-- other names like takeWhile1. But we retain the name "some" for
994-- | Collect one or more parses. Apply the supplied parser repeatedly on the
995-- input stream and push the parse results to a downstream fold.
997-- Stops: when the downstream fold stops or the parser fails.
998-- Fails: if it stops without producing a single result.
1000-- @some fld parser = manyP (takeGE 1 fld) parser@
1002-- Compare with 'Control.Applicative.some'.
1007some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1008some p f = K.toParserK $ D.some (K.fromParserK p) f
1009-- some p f = manyP p (takeGE 1 f)
1010-- many = countBetween 1 maxBound
1012-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1013-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1014-- the input ends or the parser fails before @m@ results are collected.
1018{-# INLINE countBetween #-}
1021 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1022countBetween _m _n _p = undefined
1023-- countBetween m n p f = manyP (takeBetween m n f) p
1025-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1026-- the fold @f@. Fails if the input ends or the parser fails before @n@
1027-- results are collected.
1034 Int -> Parser m a b -> Fold m b c -> Parser m a c
1035count n = countBetween n n
1036-- count n p f = manyP (takeEQ n f) p
1038-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1039-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1041-- We can implemnent parsers like the following using 'manyTillP':
1044-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1049{-# INLINE manyTillP #-}
1050manyTillP :: -- MonadCatch m =>
1051 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1052manyTillP _p1 _p2 _f = undefined
1053 -- K.toParserK $ D.manyTillP (K.fromParserK p1) (K.fromParserK p2) f
1055-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1056-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1057-- tried again and so on. The parser stops when @test@ succeeds. The output of
1058-- @test@ is discarded and the output of @collect@ is accumulated by the
1059-- supplied fold. The parser fails if @collect@ fails.
1061-- Stops when the fold @f@ stops.
1065{-# INLINE manyTill #-}
1066manyTill :: MonadCatch m
1067 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1069 K.toParserK $ D.manyTill f (K.fromParserK p1) (K.fromParserK p2)
1071-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1072-- collects the output in the supplied fold. If the the parser @collect@ fails,
1073-- parser @recover@ is run until it stops and then we start repeating the
1074-- parser @collect@ again. The parser fails if the recovery parser fails.
1076-- For example, this can be used to find a key frame in a video stream after an
1081{-# INLINE manyThen #-}
1082manyThen :: -- (Foldable t, MonadCatch m) =>
1083 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1084manyThen _parser _recover _f = undefined
1086-------------------------------------------------------------------------------
1087-- Interleaving a collection of parsers
1088-------------------------------------------------------------------------------
1090-- | Apply a collection of parsers to an input stream in a round robin fashion.
1091-- Each parser is applied until it stops and then we repeat starting with the
1092-- the first parser again.
1096{-# INLINE roundRobin #-}
1097roundRobin :: -- (Foldable t, MonadCatch m) =>
1098 t (Parser m a b) -> Fold m b c -> Parser m a c
1099roundRobin _ps _f = undefined
1101-------------------------------------------------------------------------------
1102-- Repeated Alternatives
1103-------------------------------------------------------------------------------
1105-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1106-- fails the input consumed till now is dropped and the new instance is tried
1107-- on the fresh input.
1111{-# INLINE retryMaxTotal #-}
1112retryMaxTotal :: -- (MonadCatch m) =>
1113 Int -> Parser m a b -> Fold m b c -> Parser m a c
1114retryMaxTotal _n _p _f = undefined
1116-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1120{-# INLINE retryMaxSuccessive #-}
1121retryMaxSuccessive :: -- (MonadCatch m) =>
1122 Int -> Parser m a b -> Fold m b c -> Parser m a c
1123retryMaxSuccessive _n _p _f = undefined
1125-- | Keep trying a parser until it succeeds. When the parser fails the input
1126-- consumed till now is dropped and the new instance is tried on the fresh
1132retry :: -- (MonadCatch m) =>
1133 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