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
74 -- | Parsers chained in series, if one parser terminates the composition
77 -- | Grab a sequence of input elements without inspecting them
79 -- , take -- takeBetween 0 n
80 , takeEQ -- takeBetween n n
81 , takeGE -- takeBetween n maxBound
83 -- Grab a sequence of input elements by inspecting them
104 -- , prefixOf -- match any prefix of a given string
105 -- , suffixOf -- match any suffix of a given string
106 -- , infixOf -- match any substring of a given string
109 -- Second order parsers (parsers using parsers)
110 -- * Binary Combinators
112 -- ** Sequential Applicative
116 -- ** Parallel Applicatives
120 -- , teeTill -- like manyTill but parallel
122 -- ** Sequential Interleaving
123 -- Use two folds, run a primary parser, its rejected values go to the
127 -- ** Sequential Alternative
130 -- ** Parallel Alternatives
135 -- * N-ary Combinators
136 -- ** Sequential Collection
140 -- ** Sequential Repetition
152 -- | TODO: traditional implmentations of these may be of limited use. For
153 -- example, consider parsing lines separated by @\\r\\n@. The main parser
154 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
155 -- can apply the "sep" parser.
157 -- We can instead implement these as special cases of deintercalate.
170 -- | A simple and stupid impl would be to just convert the stream to an
171 -- array and give the array reference to all consumers. The array can be
172 -- grown on demand by any consumer and truncated when nonbody needs it.
174 -- ** Distribute to collection
175 -- ** Distribute to repetition
177 -- ** Interleaved collection
184 -- ** Collection of Alternatives
190 -- , fastestN -- first N successful in time
191 -- , choiceN -- first N successful in position
193 , choice -- first successful in position
195 -- ** Repeated Alternatives
202import Control.Monad.Catch (MonadCatch, MonadThrow)
204 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
206import Streamly.Internal.Data.Fold.Type (Fold(..))
207import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
209import qualified Streamly.Internal.Data.Fold.Type as FL
210import qualified Streamly.Internal.Data.Parser.ParserD as D
211import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
216-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
217-- >>> import qualified Streamly.Prelude as Stream
218-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
219-- >>> import qualified Streamly.Data.Fold as Fold
220-- >>> import qualified Streamly.Internal.Data.Parser as Parser
222-------------------------------------------------------------------------------
223-- Downgrade a parser to a Fold
224-------------------------------------------------------------------------------
226-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
227-- parser fails or tries to backtrack.
229-- This can be useful in combinators that accept a Fold and we know that a
230-- Parser cannot fail or failure exception is acceptable as there is no way to
236toFold :: MonadThrow m => Parser m a b -> Fold m a b
237toFold p = D.toFold $ K.fromParserK p
239-------------------------------------------------------------------------------
240-- Upgrade folds to parses
241-------------------------------------------------------------------------------
243-- | Make a 'Parser' from a 'Fold'.
247{-# INLINE fromFold #-}
248fromFold :: MonadCatch m => Fold m a b -> Parser m a b
249fromFold = K.toParserK . D.fromFold
251-------------------------------------------------------------------------------
252-- Terminating but not failing folds
253-------------------------------------------------------------------------------
255-- This is the dual of stream "fromPure".
257-- | A parser that always yields a pure value without consuming any input.
261{-# INLINE [3] fromPure #-}
262fromPure :: MonadCatch m => b -> Parser m a b
263fromPure = K.toParserK . D.fromPure
264{-# RULES "fromPure fallback to CPS" [2]
265 forall a. K.toParserK (D.fromPure a) = K.fromPure a #-}
267-- This is the dual of stream "fromEffect".
269-- | A parser that always yields the result of an effectful action without
270-- consuming any input.
274{-# INLINE fromEffect #-}
275fromEffect :: MonadCatch m => m b -> Parser m a b
276fromEffect = K.fromEffect -- K.toParserK . D.fromEffect
278-- This is the dual of "nil".
280-- | A parser that always fails with an error message without consuming
285{-# INLINE [3] die #-}
286die :: MonadCatch m => String -> Parser m a b
287die = K.toParserK . D.die
288{-# RULES "die fallback to CPS" [2]
289 forall a. K.toParserK (D.die a) = K.die a #-}
291-- This is the dual of "nilM".
293-- | A parser that always fails with an effectful error message and without
294-- consuming any input.
299dieM :: MonadCatch m => m String -> Parser m a b
300dieM = K.toParserK . D.dieM
302-------------------------------------------------------------------------------
304-------------------------------------------------------------------------------
306-- | Peek the head element of a stream, without consuming it. Fails if it
307-- encounters end of input.
309-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
313-- peek = lookAhead (satisfy True)
319peek :: MonadCatch m => Parser m a a
320peek = K.toParserK D.peek
322-- | Succeeds if we are at the end of input, fails otherwise.
324-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
330eof :: MonadCatch m => Parser m a ()
331eof = K.toParserK D.eof
333-- | Returns the next element if it passes the predicate, fails otherwise.
335-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
340{-# INLINE satisfy #-}
341satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
342satisfy = K.toParserK . D.satisfy
344-- | Map a 'Maybe' returning function on the next element in the stream. The
345-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
351maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
352maybe = K.toParserK . D.maybe
354-- | Map an 'Either' returning function on the next element in the stream. If
355-- the function returns 'Left err', the parser fails with the error message
356-- @err@ otherwise returns the 'Right' value.
361either :: MonadCatch m => (a -> Either String b) -> Parser m a b
362either = K.toParserK . D.either
364-------------------------------------------------------------------------------
366-------------------------------------------------------------------------------
368-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
369-- elements and folds them using the supplied fold.
371-- Stops after @n@ elements.
372-- Fails if the stream ends before @m@ elements could be taken.
378-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
379-- where prsr = Parser.takeBetween low high Fold.toList
384-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
387-- >>> takeBetween' 2 4 [1, 2]
390-- >>> takeBetween' 2 4 [1]
391-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
393-- >>> takeBetween' 0 0 [1, 2]
396-- >>> takeBetween' 0 1 []
399-- @takeBetween@ is the most general take operation, other take operations can
400-- be defined in terms of takeBetween. For example:
403-- take = takeBetween 0 n -- equivalent of take
404-- take1 = takeBetween 1 n -- equivalent of takeLE1
405-- takeEQ = takeBetween n n
406-- takeGE = takeBetween n maxBound
411{-# INLINE takeBetween #-}
412takeBetween :: MonadCatch m =>
413 Int -> Int -> Fold m a b -> Parser m a b
414takeBetween m n = K.toParserK . D.takeBetween m n
416-- | Stops after taking exactly @n@ input elements.
418-- * Stops - after consuming @n@ elements.
419-- * Fails - if the stream or the collecting fold ends before it can collect
420-- exactly @n@ elements.
422-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
423-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
428takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
429takeEQ n = K.toParserK . D.takeEQ n
431-- | Take at least @n@ input elements, but can collect more.
433-- * Stops - when the collecting fold stops.
434-- * Fails - if the stream or the collecting fold ends before producing @n@
437-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
438-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
440-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
446takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
447takeGE n = K.toParserK . D.takeGE n
450-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
452-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
453-- input. The combinator stops when the condition fails or if the collecting
456-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
457-- implemented in terms of this:
460-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
463-- Stops: when the condition fails or the collecting parser stops.
464-- Fails: when the collecting parser fails.
468{-# INLINE takeWhileP #-}
469takeWhileP :: -- MonadCatch m =>
470 (a -> Bool) -> Parser m a b -> Parser m a b
471takeWhileP _cond = undefined -- K.toParserK . D.takeWhileP cond
473-- | Collect stream elements until an element fails the predicate. The element
474-- on which the predicate fails is returned back to the input stream.
476-- * Stops - when the predicate fails or the collecting fold stops.
479-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
482-- We can implement a @breakOn@ using 'takeWhile':
485-- breakOn p = takeWhile (not p)
490{-# INLINE takeWhile #-}
491takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
492takeWhile cond = K.toParserK . D.takeWhile cond
494-- | Like 'takeWhile' but takes at least one element otherwise fails.
498{-# INLINE takeWhile1 #-}
499takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
500takeWhile1 cond = K.toParserK . D.takeWhile1 cond
502-- | Drain the input as long as the predicate succeeds, running the effects and
503-- discarding the results.
505-- This is also called @skipWhile@ in some parsing libraries.
509{-# INLINE drainWhile #-}
510drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
511drainWhile p = takeWhile p FL.drain
513-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
514-- @cond@ succeeds or the parser stops.
516-- This is a generalized slicing parser which can be used to implement other
520-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
521-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
526{-# INLINABLE sliceSepByP #-}
529 (a -> Bool) -> Parser m a b -> Parser m a b
530sliceSepByP cond = K.toParserK . D.sliceSepByP cond . K.fromParserK
532-- | Like 'sliceSepBy' but does not drop the separator element, instead
533-- separator is emitted as a separate element in the output.
536{-# INLINABLE sliceSepWith #-}
537sliceSepWith :: -- MonadCatch m =>
538 (a -> Bool) -> Fold m a b -> Parser m a b
539sliceSepWith _cond = undefined -- K.toParserK . D.sliceSepBy cond
541-- | Collect stream elements until an elements passes the predicate, return the
542-- last element on which the predicate succeeded back to the input stream. If
543-- the predicate succeeds on the first element itself then the parser does not
544-- terminate there. The succeeding element in the leading position
545-- is treated as a prefix separator which is kept in the output segment.
547-- * Stops - when the predicate succeeds in non-leading position.
550-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
555-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
556-- where prsr = Parser.sliceBeginWith odd Fold.toList
560-- >>> sliceBeginWithOdd [2, 4, 6, 3]
561-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
564-- >>> sliceBeginWithOdd [3, 5, 7, 4]
567-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
570-- >>> sliceBeginWithOdd []
575{-# INLINABLE sliceBeginWith #-}
578 (a -> Bool) -> Fold m a b -> Parser m a b
579sliceBeginWith cond = K.toParserK . D.sliceBeginWith cond
581-- | Like 'sliceSepBy' but the separator elements can be escaped using an
582-- escape char determined by the second predicate.
585{-# INLINABLE escapedSliceSepBy #-}
586escapedSliceSepBy :: -- MonadCatch m =>
587 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
588escapedSliceSepBy _cond _esc = undefined
589 -- K.toParserK . D.escapedSliceSepBy cond esc
591-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
592-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
593-- element to escape the occurrence of the framing elements within the frame.
594-- Nested frames are allowed, but nesting is removed when parsing.
599-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
602-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
605-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
608-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
609-- ParseError "Unterminated '{'"
614{-# INLINABLE escapedFrameBy #-}
615escapedFrameBy :: -- MonadCatch m =>
616 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
617escapedFrameBy _begin _end _escape _p = undefined
618 -- K.toParserK . D.frameBy begin end escape p
620-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
621-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
622-- @["a","b"]@. In other words, its like parsing words from whitespace
625-- * Stops - when it finds a word separator after a non-word element
629-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
633wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
634wordBy f = K.toParserK . D.wordBy f
636-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
637-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
638-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
639-- then @c@ is also assigned to the same group and so on. When the comparison
640-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
641-- the result of the fold is the result of the parser.
643-- * Stops - when the comparison fails.
649-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
653-- >>> runGroupsBy (<) []
656-- >>> runGroupsBy (<) [1]
659-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
660-- [[3,5,4],[1,2],[0]]
664{-# INLINABLE groupBy #-}
665groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
666groupBy eq = K.toParserK . D.groupBy eq
668-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
669-- successive elements in the input stream. Assuming the input stream to the
670-- parser is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
671-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
672-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
673-- then @c@ is also assigned to the same group and so on. When the comparison
674-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
675-- the result of the fold is the result of the parser.
677-- * Stops - when the comparison fails.
681-- runGroupsByRolling eq =
683-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
687-- >>> runGroupsByRolling (<) []
690-- >>> runGroupsByRolling (<) [1]
693-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
694-- [[3,5],[4],[1,2],[0]]
698{-# INLINABLE groupByRolling #-}
699groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
700groupByRolling eq = K.toParserK . D.groupByRolling eq
702-- | Match the given sequence of elements using the given comparison function.
704-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
706-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
707-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
712eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
713eqBy cmp = K.toParserK . D.eqBy cmp
715-------------------------------------------------------------------------------
717-------------------------------------------------------------------------------
719-- | Sequential parser application. Apply two parsers sequentially to an input
720-- stream. The input is provided to the first parser, when it is done the
721-- remaining input is provided to the second parser. If both the parsers
722-- succeed their outputs are combined using the supplied function. The
723-- operation fails if any of the parsers fail.
725-- Note: This is a parsing dual of appending streams using
726-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
729-- This implementation is strict in the second argument, therefore, the
730-- following will fail:
732-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
733-- *** Exception: Prelude.undefined
736-- Compare with 'Applicative' instance method '<*>'. This implementation allows
737-- stream fusion but has quadratic complexity. This can fuse with other
738-- operations and can be faster than 'Applicative' instance for small number
739-- (less than 8) of compositions.
741-- Many combinators can be expressed using @serialWith@ and other parser
742-- primitives. Some common idioms are described below,
745-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
746-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
750-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
751-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
755-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
756-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
761{-# INLINE serialWith #-}
762serialWith :: MonadCatch m
763 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
765 K.toParserK $ D.serialWith f (K.fromParserK p1) (K.fromParserK p2)
767-- | Sequential parser application ignoring the output of the first parser.
768-- Apply two parsers sequentially to an input stream. The input is provided to
769-- the first parser, when it is done the remaining input is provided to the
770-- second parser. The output of the parser is the output of the second parser.
771-- The operation fails if any of the parsers fail.
773-- This implementation is strict in the second argument, therefore, the
774-- following will fail:
776-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
777-- *** Exception: Prelude.undefined
780-- Compare with 'Applicative' instance method '*>'. This implementation allows
781-- stream fusion but has quadratic complexity. This can fuse with other
782-- operations, and can be faster than 'Applicative' instance for small
783-- number (less than 8) of compositions.
788split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
789split_ p1 p2 = K.toParserK $ D.split_ (K.fromParserK p1) (K.fromParserK p2)
791-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
792-- of them succeed or anyone of them fails and combines their output using @f@.
793-- The parser succeeds if both the parsers succeed.
797{-# INLINE teeWith #-}
798teeWith :: MonadCatch m
799 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
801 K.toParserK $ D.teeWith f (K.fromParserK p1) (K.fromParserK p2)
803-- | Like 'teeWith' but ends parsing and zips the results, if available,
804-- whenever the first parser ends.
808{-# INLINE teeWithFst #-}
809teeWithFst :: MonadCatch m
810 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
812 K.toParserK $ D.teeWithFst f (K.fromParserK p1) (K.fromParserK p2)
814-- | Like 'teeWith' but ends parsing and zips the results, if available,
815-- whenever any of the parsers ends or fails.
819{-# INLINE teeWithMin #-}
820teeWithMin :: MonadCatch m
821 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
823 K.toParserK $ D.teeWithMin f (K.fromParserK p1) (K.fromParserK p2)
825-- | Sequential alternative. Apply the input to the first parser and return the
826-- result if the parser succeeds. If the first parser fails then backtrack and
827-- apply the same input to the second parser and return the result.
829-- Note: This implementation is not lazy in the second argument. The following
832-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
835-- Compare with 'Alternative' instance method '<|>'. This implementation allows
836-- stream fusion but has quadratic complexity. This can fuse with other
837-- operations and can be much faster than 'Alternative' instance for small
838-- number (less than 8) of alternatives.
843alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
844alt p1 p2 = K.toParserK $ D.alt (K.fromParserK p1) (K.fromParserK p2)
846-- | Shortest alternative. Apply both parsers in parallel but choose the result
847-- from the one which consumed least input i.e. take the shortest succeeding
852{-# INLINE shortest #-}
853shortest :: MonadCatch m
854 => Parser m x a -> Parser m x a -> Parser m x a
855shortest p1 p2 = K.toParserK $ D.shortest (K.fromParserK p1) (K.fromParserK p2)
857-- | Longest alternative. Apply both parsers in parallel but choose the result
858-- from the one which consumed more input i.e. take the longest succeeding
863{-# INLINE longest #-}
864longest :: MonadCatch m
865 => Parser m x a -> Parser m x a -> Parser m x a
866longest p1 p2 = K.toParserK $ D.longest (K.fromParserK p1) (K.fromParserK p2)
868-- | Run a parser without consuming the input.
872{-# INLINE lookAhead #-}
873lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
874lookAhead p = K.toParserK $ D.lookAhead $ K.fromParserK p
876-- | Takes at-most @n@ input elements.
878-- * Stops - when the collecting parser stops.
879-- * Fails - when the collecting parser fails.
881-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
884-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
885-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
889takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
890takeP i p = K.toParserK $ D.takeP i $ K.fromParserK p
892-------------------------------------------------------------------------------
894-------------------------------------------------------------------------------
896-- To deinterleave we can chain two parsers one behind the other. The input is
897-- given to the first parser and the input definitively rejected by the first
898-- parser is given to the second parser.
900-- We can either have the parsers themselves buffer the input or use the shared
901-- global buffer to hold it until none of the parsers need it. When the first
902-- parser returns Skip (i.e. rewind) we let the second parser consume the
903-- rejected input and when it is done we move the cursor forward to the first
904-- parser again. This will require a "move forward" command as well.
906-- To implement grep we can use three parsers, one to find the pattern, one
907-- to store the context behind the pattern and one to store the context in
908-- front of the pattern. When a match occurs we need to emit the accumulator of
909-- all the three parsers. One parser can count the line numbers to provide the
912-- | Apply two parsers alternately to an input stream. The input stream is
913-- considered an interleaving of two patterns. The two parsers represent the
916-- This undoes a "gintercalate" of two streams.
920{-# INLINE deintercalate #-}
923 Fold m a y -> Parser m x a
924 -> Fold m b z -> Parser m x b
926deintercalate = undefined
928-------------------------------------------------------------------------------
929-- Sequential Collection
930-------------------------------------------------------------------------------
932-- | @concatSequence f t@ collects sequential parses of parsers in the
933-- container @t@ using the fold @f@. Fails if the input ends or any of the
936-- This is same as 'Data.Traversable.sequence' but more efficient.
940{-# INLINE concatSequence #-}
943 Fold m b c -> t (Parser m a b) -> Parser m a c
944concatSequence _f _p = undefined
946-- | Map a 'Parser' returning function on the result of a 'Parser'.
948-- Compare with 'Monad' instance method '>>='. This implementation allows
949-- stream fusion but has quadratic complexity. This can fuse with other
950-- operations and can be much faster than 'Monad' instance for small number
951-- (less than 8) of compositions.
955{-# INLINE concatMap #-}
956concatMap :: MonadCatch m
957 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
958concatMap f p = K.toParserK $ D.concatMap (K.fromParserK . f) (K.fromParserK p)
960-------------------------------------------------------------------------------
961-- Alternative Collection
962-------------------------------------------------------------------------------
964-- | @choice parsers@ applies the @parsers@ in order and returns the first
967-- This is same as 'asum' but more efficient.
973 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
974choice ps = K.toParserK $ D.choice $ K.fromParserK <$> ps
976-------------------------------------------------------------------------------
977-- Sequential Repetition
978-------------------------------------------------------------------------------
981-- TODO "many" is essentially a Fold because it cannot fail. So it can be
982-- downgraded to a Fold. Or we can make the return type a Fold instead and
983-- upgrade that to a parser when needed.
985-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
986-- results. Parsing stops or fails if the collecting parser stops or fails.
991manyP :: -- MonadCatch m =>
992 Parser m a b -> Parser m b c -> Parser m a c
993manyP _p _f = undefined -- K.toParserK $ D.manyP (K.fromParserK p) f
995-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
996-- input stream and push the parse results to a downstream fold.
998-- Stops: when the downstream fold stops or the parser fails.
999-- Fails: never, produces zero or more results.
1001-- Compare with 'Control.Applicative.many'.
1006many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1007many p f = K.toParserK $ D.many (K.fromParserK p) f
1008-- many = countBetween 0 maxBound
1010-- Note: many1 would perhaps be a better name for this and consistent with
1011-- other names like takeWhile1. But we retain the name "some" for
1014-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1015-- input stream and push the parse results to a downstream fold.
1017-- Stops: when the downstream fold stops or the parser fails.
1018-- Fails: if it stops without producing a single result.
1020-- @some fld parser = manyP (takeGE 1 fld) parser@
1022-- Compare with 'Control.Applicative.some'.
1027some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1028some p f = K.toParserK $ D.some (K.fromParserK p) f
1029-- some p f = manyP p (takeGE 1 f)
1030-- many = countBetween 1 maxBound
1032-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1033-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1034-- the input ends or the parser fails before @m@ results are collected.
1038{-# INLINE countBetween #-}
1041 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1042countBetween _m _n _p = undefined
1043-- countBetween m n p f = manyP (takeBetween m n f) p
1045-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1046-- the fold @f@. Fails if the input ends or the parser fails before @n@
1047-- results are collected.
1054 Int -> Parser m a b -> Fold m b c -> Parser m a c
1055count n = countBetween n n
1056-- count n p f = manyP (takeEQ n f) p
1058-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1059-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1061-- We can implemnent parsers like the following using 'manyTillP':
1064-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1069{-# INLINE manyTillP #-}
1070manyTillP :: -- MonadCatch m =>
1071 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1072manyTillP _p1 _p2 _f = undefined
1073 -- K.toParserK $ D.manyTillP (K.fromParserK p1) (K.fromParserK p2) f
1075-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1076-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1077-- tried again and so on. The parser stops when @test@ succeeds. The output of
1078-- @test@ is discarded and the output of @collect@ is accumulated by the
1079-- supplied fold. The parser fails if @collect@ fails.
1081-- Stops when the fold @f@ stops.
1085{-# INLINE manyTill #-}
1086manyTill :: MonadCatch m
1087 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1089 K.toParserK $ D.manyTill f (K.fromParserK p1) (K.fromParserK p2)
1091-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1092-- collects the output in the supplied fold. If the the parser @collect@ fails,
1093-- parser @recover@ is run until it stops and then we start repeating the
1094-- parser @collect@ again. The parser fails if the recovery parser fails.
1096-- For example, this can be used to find a key frame in a video stream after an
1101{-# INLINE manyThen #-}
1102manyThen :: -- (Foldable t, MonadCatch m) =>
1103 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1104manyThen _parser _recover _f = undefined
1106-------------------------------------------------------------------------------
1107-- Interleaving a collection of parsers
1108-------------------------------------------------------------------------------
1110-- | Apply a collection of parsers to an input stream in a round robin fashion.
1111-- Each parser is applied until it stops and then we repeat starting with the
1112-- the first parser again.
1116{-# INLINE roundRobin #-}
1117roundRobin :: -- (Foldable t, MonadCatch m) =>
1118 t (Parser m a b) -> Fold m b c -> Parser m a c
1119roundRobin _ps _f = undefined
1121-------------------------------------------------------------------------------
1122-- Repeated Alternatives
1123-------------------------------------------------------------------------------
1125-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1126-- fails the input consumed till now is dropped and the new instance is tried
1127-- on the fresh input.
1131{-# INLINE retryMaxTotal #-}
1132retryMaxTotal :: -- (MonadCatch m) =>
1133 Int -> Parser m a b -> Fold m b c -> Parser m a c
1134retryMaxTotal _n _p _f = undefined
1136-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1140{-# INLINE retryMaxSuccessive #-}
1141retryMaxSuccessive :: -- (MonadCatch m) =>
1142 Int -> Parser m a b -> Fold m b c -> Parser m a c
1143retryMaxSuccessive _n _p _f = undefined
1145-- | Keep trying a parser until it succeeds. When the parser fails the input
1146-- consumed till now is dropped and the new instance is tried on the fresh
1152retry :: -- (MonadCatch m) =>
1153 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