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
100 , groupByRollingEither
105 -- , prefixOf -- match any prefix of a given string
106 -- , suffixOf -- match any suffix of a given string
107 -- , infixOf -- match any substring of a given string
110 -- Second order parsers (parsers using parsers)
111 -- * Binary Combinators
113 -- ** Sequential Applicative
117 -- ** Parallel Applicatives
121 -- , teeTill -- like manyTill but parallel
123 -- ** Sequential Interleaving
124 -- Use two folds, run a primary parser, its rejected values go to the
128 -- ** Sequential Alternative
131 -- ** Parallel Alternatives
136 -- * N-ary Combinators
137 -- ** Sequential Collection
141 -- ** Sequential Repetition
153 -- | TODO: traditional implmentations of these may be of limited use. For
154 -- example, consider parsing lines separated by @\\r\\n@. The main parser
155 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
156 -- can apply the "sep" parser.
158 -- We can instead implement these as special cases of deintercalate.
171 -- | A simple and stupid impl would be to just convert the stream to an
172 -- array and give the array reference to all consumers. The array can be
173 -- grown on demand by any consumer and truncated when nonbody needs it.
175 -- ** Distribute to collection
176 -- ** Distribute to repetition
178 -- ** Interleaved collection
185 -- ** Collection of Alternatives
191 -- , fastestN -- first N successful in time
192 -- , choiceN -- first N successful in position
194 , choice -- first successful in position
196 -- ** Repeated Alternatives
203import Control.Monad.Catch (MonadCatch, MonadThrow)
205 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
207import Streamly.Internal.Data.Fold.Type (Fold(..))
208import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
210import qualified Streamly.Internal.Data.Fold.Type as FL
211import qualified Streamly.Internal.Data.Parser.ParserD as D
212import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
217-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
218-- >>> import qualified Streamly.Prelude as Stream
219-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
220-- >>> import qualified Streamly.Data.Fold as Fold
221-- >>> import qualified Streamly.Internal.Data.Parser as Parser
223-------------------------------------------------------------------------------
224-- Downgrade a parser to a Fold
225-------------------------------------------------------------------------------
227-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
228-- parser fails or tries to backtrack.
230-- This can be useful in combinators that accept a Fold and we know that a
231-- Parser cannot fail or failure exception is acceptable as there is no way to
237toFold :: MonadThrow m => Parser m a b -> Fold m a b
238toFold p = D.toFold $ K.fromParserK p
240-------------------------------------------------------------------------------
241-- Upgrade folds to parses
242-------------------------------------------------------------------------------
244-- | Make a 'Parser' from a 'Fold'.
248{-# INLINE fromFold #-}
249fromFold :: MonadCatch m => Fold m a b -> Parser m a b
250fromFold = K.toParserK . D.fromFold
252-------------------------------------------------------------------------------
253-- Terminating but not failing folds
254-------------------------------------------------------------------------------
256-- This is the dual of stream "fromPure".
258-- | A parser that always yields a pure value without consuming any input.
262{-# INLINE [3] fromPure #-}
263fromPure :: MonadCatch m => b -> Parser m a b
264fromPure = K.toParserK . D.fromPure
265{-# RULES "fromPure fallback to CPS" [2]
266 forall a. K.toParserK (D.fromPure a) = K.fromPure a #-}
268-- This is the dual of stream "fromEffect".
270-- | A parser that always yields the result of an effectful action without
271-- consuming any input.
275{-# INLINE fromEffect #-}
276fromEffect :: MonadCatch m => m b -> Parser m a b
277fromEffect = K.fromEffect -- K.toParserK . D.fromEffect
279-- This is the dual of "nil".
281-- | A parser that always fails with an error message without consuming
286{-# INLINE [3] die #-}
287die :: MonadCatch m => String -> Parser m a b
288die = K.toParserK . D.die
289{-# RULES "die fallback to CPS" [2]
290 forall a. K.toParserK (D.die a) = K.die a #-}
292-- This is the dual of "nilM".
294-- | A parser that always fails with an effectful error message and without
295-- consuming any input.
300dieM :: MonadCatch m => m String -> Parser m a b
301dieM = K.toParserK . D.dieM
303-------------------------------------------------------------------------------
305-------------------------------------------------------------------------------
307-- | Peek the head element of a stream, without consuming it. Fails if it
308-- encounters end of input.
310-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
314-- peek = lookAhead (satisfy True)
320peek :: MonadCatch m => Parser m a a
321peek = K.toParserK D.peek
323-- | Succeeds if we are at the end of input, fails otherwise.
325-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
331eof :: MonadCatch m => Parser m a ()
332eof = K.toParserK D.eof
334-- | Returns the next element if it passes the predicate, fails otherwise.
336-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
341{-# INLINE satisfy #-}
342satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
343satisfy = K.toParserK . D.satisfy
345-- | Map a 'Maybe' returning function on the next element in the stream. The
346-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
352maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
353maybe = K.toParserK . D.maybe
355-- | Map an 'Either' returning function on the next element in the stream. If
356-- the function returns 'Left err', the parser fails with the error message
357-- @err@ otherwise returns the 'Right' value.
362either :: MonadCatch m => (a -> Either String b) -> Parser m a b
363either = K.toParserK . D.either
365-------------------------------------------------------------------------------
367-------------------------------------------------------------------------------
369-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
370-- elements and folds them using the supplied fold.
372-- Stops after @n@ elements.
373-- Fails if the stream ends before @m@ elements could be taken.
379-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
380-- where prsr = Parser.takeBetween low high Fold.toList
385-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
388-- >>> takeBetween' 2 4 [1, 2]
391-- >>> takeBetween' 2 4 [1]
392-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
394-- >>> takeBetween' 0 0 [1, 2]
397-- >>> takeBetween' 0 1 []
400-- @takeBetween@ is the most general take operation, other take operations can
401-- be defined in terms of takeBetween. For example:
404-- take = takeBetween 0 n -- equivalent of take
405-- take1 = takeBetween 1 n -- equivalent of takeLE1
406-- takeEQ = takeBetween n n
407-- takeGE = takeBetween n maxBound
412{-# INLINE takeBetween #-}
413takeBetween :: MonadCatch m =>
414 Int -> Int -> Fold m a b -> Parser m a b
415takeBetween m n = K.toParserK . D.takeBetween m n
417-- | Stops after taking exactly @n@ input elements.
419-- * Stops - after consuming @n@ elements.
420-- * Fails - if the stream or the collecting fold ends before it can collect
421-- exactly @n@ elements.
423-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
424-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
429takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
430takeEQ n = K.toParserK . D.takeEQ n
432-- | Take at least @n@ input elements, but can collect more.
434-- * Stops - when the collecting fold stops.
435-- * Fails - if the stream or the collecting fold ends before producing @n@
438-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
439-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
441-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
447takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
448takeGE n = K.toParserK . D.takeGE n
451-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
453-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
454-- input. The combinator stops when the condition fails or if the collecting
457-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
458-- implemented in terms of this:
461-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
464-- Stops: when the condition fails or the collecting parser stops.
465-- Fails: when the collecting parser fails.
469{-# INLINE takeWhileP #-}
470takeWhileP :: -- MonadCatch m =>
471 (a -> Bool) -> Parser m a b -> Parser m a b
472takeWhileP _cond = undefined -- K.toParserK . D.takeWhileP cond
474-- | Collect stream elements until an element fails the predicate. The element
475-- on which the predicate fails is returned back to the input stream.
477-- * Stops - when the predicate fails or the collecting fold stops.
480-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
483-- We can implement a @breakOn@ using 'takeWhile':
486-- breakOn p = takeWhile (not p)
491{-# INLINE takeWhile #-}
492takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
493takeWhile cond = K.toParserK . D.takeWhile cond
495-- | Like 'takeWhile' but takes at least one element otherwise fails.
499{-# INLINE takeWhile1 #-}
500takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
501takeWhile1 cond = K.toParserK . D.takeWhile1 cond
503-- | Drain the input as long as the predicate succeeds, running the effects and
504-- discarding the results.
506-- This is also called @skipWhile@ in some parsing libraries.
510{-# INLINE drainWhile #-}
511drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
512drainWhile p = takeWhile p FL.drain
514-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
515-- @cond@ succeeds or the parser stops.
517-- This is a generalized slicing parser which can be used to implement other
521-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
522-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
527{-# INLINABLE sliceSepByP #-}
530 (a -> Bool) -> Parser m a b -> Parser m a b
531sliceSepByP cond = K.toParserK . D.sliceSepByP cond . K.fromParserK
533-- | Like 'sliceSepBy' but does not drop the separator element, instead
534-- separator is emitted as a separate element in the output.
537{-# INLINABLE sliceSepWith #-}
538sliceSepWith :: -- MonadCatch m =>
539 (a -> Bool) -> Fold m a b -> Parser m a b
540sliceSepWith _cond = undefined -- K.toParserK . D.sliceSepBy cond
542-- | Collect stream elements until an elements passes the predicate, return the
543-- last element on which the predicate succeeded back to the input stream. If
544-- the predicate succeeds on the first element itself then the parser does not
545-- terminate there. The succeeding element in the leading position
546-- is treated as a prefix separator which is kept in the output segment.
548-- * Stops - when the predicate succeeds in non-leading position.
551-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
556-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
557-- where prsr = Parser.sliceBeginWith odd Fold.toList
561-- >>> sliceBeginWithOdd [2, 4, 6, 3]
562-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
565-- >>> sliceBeginWithOdd [3, 5, 7, 4]
568-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
571-- >>> sliceBeginWithOdd []
576{-# INLINABLE sliceBeginWith #-}
579 (a -> Bool) -> Fold m a b -> Parser m a b
580sliceBeginWith cond = K.toParserK . D.sliceBeginWith cond
582-- | Like 'sliceSepBy' but the separator elements can be escaped using an
583-- escape char determined by the second predicate.
586{-# INLINABLE escapedSliceSepBy #-}
587escapedSliceSepBy :: -- MonadCatch m =>
588 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
589escapedSliceSepBy _cond _esc = undefined
590 -- K.toParserK . D.escapedSliceSepBy cond esc
592-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
593-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
594-- element to escape the occurrence of the framing elements within the frame.
595-- Nested frames are allowed, but nesting is removed when parsing.
600-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
603-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
606-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
609-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
610-- ParseError "Unterminated '{'"
615{-# INLINABLE escapedFrameBy #-}
616escapedFrameBy :: -- MonadCatch m =>
617 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
618escapedFrameBy _begin _end _escape _p = undefined
619 -- K.toParserK . D.frameBy begin end escape p
621-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
622-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
623-- @["a","b"]@. In other words, its like parsing words from whitespace
626-- * Stops - when it finds a word separator after a non-word element
630-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
634wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
635wordBy f = K.toParserK . D.wordBy f
637-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
638-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
639-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
640-- then @c@ is also assigned to the same group and so on. When the comparison
641-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
642-- the result of the fold is the result of the parser.
644-- * Stops - when the comparison fails.
650-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
654-- >>> runGroupsBy (<) []
657-- >>> runGroupsBy (<) [1]
660-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
661-- [[3,5,4],[1,2],[0]]
665{-# INLINABLE groupBy #-}
666groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
667groupBy eq = K.toParserK . D.groupBy eq
669-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
670-- successive elements in the input stream. Assuming the input stream to the
671-- parser is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
672-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
673-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
674-- then @c@ is also assigned to the same group and so on. When the comparison
675-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
676-- the result of the fold is the result of the parser.
678-- * Stops - when the comparison fails.
682-- runGroupsByRolling eq =
684-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
688-- >>> runGroupsByRolling (<) []
691-- >>> runGroupsByRolling (<) [1]
694-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
695-- [[3,5],[4],[1,2],[0]]
699{-# INLINABLE groupByRolling #-}
700groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
701groupByRolling eq = K.toParserK . D.groupByRolling eq
703-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
704-- the first fold as long as the predicate holds 'True', if the predicate is
705-- 'False' collects using the second fold as long as it remains 'False'.
706-- Returns 'Left' for the first case and 'Right' for the second case.
708-- For example, if we want to detect sorted sequences in a stream, both
709-- ascending and descending cases we can use 'groupByRollingEither (<=)
710-- Fold.toList Fold.toList'.
713{-# INLINABLE groupByRollingEither #-}
714groupByRollingEither :: -- MonadCatch m =>
715 (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a (Either b b)
716groupByRollingEither = undefined
718-- | Match the given sequence of elements using the given comparison function.
720-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
722-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
723-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
728eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
729eqBy cmp = K.toParserK . D.eqBy cmp
731-------------------------------------------------------------------------------
733-------------------------------------------------------------------------------
735-- | Sequential parser application. Apply two parsers sequentially to an input
736-- stream. The input is provided to the first parser, when it is done the
737-- remaining input is provided to the second parser. If both the parsers
738-- succeed their outputs are combined using the supplied function. The
739-- operation fails if any of the parsers fail.
741-- Note: This is a parsing dual of appending streams using
742-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
745-- This implementation is strict in the second argument, therefore, the
746-- following will fail:
748-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
749-- *** Exception: Prelude.undefined
752-- Compare with 'Applicative' instance method '<*>'. This implementation allows
753-- stream fusion but has quadratic complexity. This can fuse with other
754-- operations and can be faster than 'Applicative' instance for small number
755-- (less than 8) of compositions.
757-- Many combinators can be expressed using @serialWith@ and other parser
758-- primitives. Some common idioms are described below,
761-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
762-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
766-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
767-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
771-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
772-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
777{-# INLINE serialWith #-}
778serialWith :: MonadCatch m
779 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
781 K.toParserK $ D.serialWith f (K.fromParserK p1) (K.fromParserK p2)
783-- | Sequential parser application ignoring the output of the first parser.
784-- Apply two parsers sequentially to an input stream. The input is provided to
785-- the first parser, when it is done the remaining input is provided to the
786-- second parser. The output of the parser is the output of the second parser.
787-- The operation fails if any of the parsers fail.
789-- This implementation is strict in the second argument, therefore, the
790-- following will fail:
792-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
793-- *** Exception: Prelude.undefined
796-- Compare with 'Applicative' instance method '*>'. This implementation allows
797-- stream fusion but has quadratic complexity. This can fuse with other
798-- operations, and can be faster than 'Applicative' instance for small
799-- number (less than 8) of compositions.
804split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
805split_ p1 p2 = K.toParserK $ D.split_ (K.fromParserK p1) (K.fromParserK p2)
807-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
808-- of them succeed or anyone of them fails and combines their output using @f@.
809-- The parser succeeds if both the parsers succeed.
813{-# INLINE teeWith #-}
814teeWith :: MonadCatch m
815 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
817 K.toParserK $ D.teeWith f (K.fromParserK p1) (K.fromParserK p2)
819-- | Like 'teeWith' but ends parsing and zips the results, if available,
820-- whenever the first parser ends.
824{-# INLINE teeWithFst #-}
825teeWithFst :: MonadCatch m
826 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
828 K.toParserK $ D.teeWithFst f (K.fromParserK p1) (K.fromParserK p2)
830-- | Like 'teeWith' but ends parsing and zips the results, if available,
831-- whenever any of the parsers ends or fails.
835{-# INLINE teeWithMin #-}
836teeWithMin :: MonadCatch m
837 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
839 K.toParserK $ D.teeWithMin f (K.fromParserK p1) (K.fromParserK p2)
841-- | Sequential alternative. Apply the input to the first parser and return the
842-- result if the parser succeeds. If the first parser fails then backtrack and
843-- apply the same input to the second parser and return the result.
845-- Note: This implementation is not lazy in the second argument. The following
848-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
851-- Compare with 'Alternative' instance method '<|>'. This implementation allows
852-- stream fusion but has quadratic complexity. This can fuse with other
853-- operations and can be much faster than 'Alternative' instance for small
854-- number (less than 8) of alternatives.
859alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
860alt p1 p2 = K.toParserK $ D.alt (K.fromParserK p1) (K.fromParserK p2)
862-- | Shortest alternative. Apply both parsers in parallel but choose the result
863-- from the one which consumed least input i.e. take the shortest succeeding
868{-# INLINE shortest #-}
869shortest :: MonadCatch m
870 => Parser m x a -> Parser m x a -> Parser m x a
871shortest p1 p2 = K.toParserK $ D.shortest (K.fromParserK p1) (K.fromParserK p2)
873-- | Longest alternative. Apply both parsers in parallel but choose the result
874-- from the one which consumed more input i.e. take the longest succeeding
879{-# INLINE longest #-}
880longest :: MonadCatch m
881 => Parser m x a -> Parser m x a -> Parser m x a
882longest p1 p2 = K.toParserK $ D.longest (K.fromParserK p1) (K.fromParserK p2)
884-- | Run a parser without consuming the input.
888{-# INLINE lookAhead #-}
889lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
890lookAhead p = K.toParserK $ D.lookAhead $ K.fromParserK p
892-- | Takes at-most @n@ input elements.
894-- * Stops - when the collecting parser stops.
895-- * Fails - when the collecting parser fails.
897-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
900-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
901-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
905takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
906takeP i p = K.toParserK $ D.takeP i $ K.fromParserK p
908-------------------------------------------------------------------------------
910-------------------------------------------------------------------------------
912-- To deinterleave we can chain two parsers one behind the other. The input is
913-- given to the first parser and the input definitively rejected by the first
914-- parser is given to the second parser.
916-- We can either have the parsers themselves buffer the input or use the shared
917-- global buffer to hold it until none of the parsers need it. When the first
918-- parser returns Skip (i.e. rewind) we let the second parser consume the
919-- rejected input and when it is done we move the cursor forward to the first
920-- parser again. This will require a "move forward" command as well.
922-- To implement grep we can use three parsers, one to find the pattern, one
923-- to store the context behind the pattern and one to store the context in
924-- front of the pattern. When a match occurs we need to emit the accumulator of
925-- all the three parsers. One parser can count the line numbers to provide the
928-- | Apply two parsers alternately to an input stream. The input stream is
929-- considered an interleaving of two patterns. The two parsers represent the
932-- This undoes a "gintercalate" of two streams.
936{-# INLINE deintercalate #-}
939 Fold m a y -> Parser m x a
940 -> Fold m b z -> Parser m x b
942deintercalate = undefined
944-------------------------------------------------------------------------------
945-- Sequential Collection
946-------------------------------------------------------------------------------
948-- | @concatSequence f t@ collects sequential parses of parsers in the
949-- container @t@ using the fold @f@. Fails if the input ends or any of the
952-- This is same as 'Data.Traversable.sequence' but more efficient.
956{-# INLINE concatSequence #-}
959 Fold m b c -> t (Parser m a b) -> Parser m a c
960concatSequence _f _p = undefined
962-- | Map a 'Parser' returning function on the result of a 'Parser'.
964-- Compare with 'Monad' instance method '>>='. This implementation allows
965-- stream fusion but has quadratic complexity. This can fuse with other
966-- operations and can be much faster than 'Monad' instance for small number
967-- (less than 8) of compositions.
971{-# INLINE concatMap #-}
972concatMap :: MonadCatch m
973 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
974concatMap f p = K.toParserK $ D.concatMap (K.fromParserK . f) (K.fromParserK p)
976-------------------------------------------------------------------------------
977-- Alternative Collection
978-------------------------------------------------------------------------------
980-- | @choice parsers@ applies the @parsers@ in order and returns the first
983-- This is same as 'asum' but more efficient.
989 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
990choice ps = K.toParserK $ D.choice $ K.fromParserK <$> ps
992-------------------------------------------------------------------------------
993-- Sequential Repetition
994-------------------------------------------------------------------------------
997-- TODO "many" is essentially a Fold because it cannot fail. So it can be
998-- downgraded to a Fold. Or we can make the return type a Fold instead and
999-- upgrade that to a parser when needed.
1001-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1002-- results. Parsing stops or fails if the collecting parser stops or fails.
1007manyP :: -- MonadCatch m =>
1008 Parser m a b -> Parser m b c -> Parser m a c
1009manyP _p _f = undefined -- K.toParserK $ D.manyP (K.fromParserK p) f
1011-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1012-- input stream and push the parse results to a downstream fold.
1014-- Stops: when the downstream fold stops or the parser fails.
1015-- Fails: never, produces zero or more results.
1017-- Compare with 'Control.Applicative.many'.
1022many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1023many p f = K.toParserK $ D.many (K.fromParserK p) f
1024-- many = countBetween 0 maxBound
1026-- Note: many1 would perhaps be a better name for this and consistent with
1027-- other names like takeWhile1. But we retain the name "some" for
1030-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1031-- input stream and push the parse results to a downstream fold.
1033-- Stops: when the downstream fold stops or the parser fails.
1034-- Fails: if it stops without producing a single result.
1036-- @some fld parser = manyP (takeGE 1 fld) parser@
1038-- Compare with 'Control.Applicative.some'.
1043some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1044some p f = K.toParserK $ D.some (K.fromParserK p) f
1045-- some p f = manyP p (takeGE 1 f)
1046-- many = countBetween 1 maxBound
1048-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1049-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1050-- the input ends or the parser fails before @m@ results are collected.
1054{-# INLINE countBetween #-}
1057 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1058countBetween _m _n _p = undefined
1059-- countBetween m n p f = manyP (takeBetween m n f) p
1061-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1062-- the fold @f@. Fails if the input ends or the parser fails before @n@
1063-- results are collected.
1070 Int -> Parser m a b -> Fold m b c -> Parser m a c
1071count n = countBetween n n
1072-- count n p f = manyP (takeEQ n f) p
1074-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1075-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1077-- We can implemnent parsers like the following using 'manyTillP':
1080-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1085{-# INLINE manyTillP #-}
1086manyTillP :: -- MonadCatch m =>
1087 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1088manyTillP _p1 _p2 _f = undefined
1089 -- K.toParserK $ D.manyTillP (K.fromParserK p1) (K.fromParserK p2) f
1091-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1092-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1093-- tried again and so on. The parser stops when @test@ succeeds. The output of
1094-- @test@ is discarded and the output of @collect@ is accumulated by the
1095-- supplied fold. The parser fails if @collect@ fails.
1097-- Stops when the fold @f@ stops.
1101{-# INLINE manyTill #-}
1102manyTill :: MonadCatch m
1103 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1105 K.toParserK $ D.manyTill f (K.fromParserK p1) (K.fromParserK p2)
1107-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1108-- collects the output in the supplied fold. If the the parser @collect@ fails,
1109-- parser @recover@ is run until it stops and then we start repeating the
1110-- parser @collect@ again. The parser fails if the recovery parser fails.
1112-- For example, this can be used to find a key frame in a video stream after an
1117{-# INLINE manyThen #-}
1118manyThen :: -- (Foldable t, MonadCatch m) =>
1119 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1120manyThen _parser _recover _f = undefined
1122-------------------------------------------------------------------------------
1123-- Interleaving a collection of parsers
1124-------------------------------------------------------------------------------
1126-- | Apply a collection of parsers to an input stream in a round robin fashion.
1127-- Each parser is applied until it stops and then we repeat starting with the
1128-- the first parser again.
1132{-# INLINE roundRobin #-}
1133roundRobin :: -- (Foldable t, MonadCatch m) =>
1134 t (Parser m a b) -> Fold m b c -> Parser m a c
1135roundRobin _ps _f = undefined
1137-------------------------------------------------------------------------------
1138-- Repeated Alternatives
1139-------------------------------------------------------------------------------
1141-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1142-- fails the input consumed till now is dropped and the new instance is tried
1143-- on the fresh input.
1147{-# INLINE retryMaxTotal #-}
1148retryMaxTotal :: -- (MonadCatch m) =>
1149 Int -> Parser m a b -> Fold m b c -> Parser m a c
1150retryMaxTotal _n _p _f = undefined
1152-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1156{-# INLINE retryMaxSuccessive #-}
1157retryMaxSuccessive :: -- (MonadCatch m) =>
1158 Int -> Parser m a b -> Fold m b c -> Parser m a c
1159retryMaxSuccessive _n _p _f = undefined
1161-- | Keep trying a parser until it succeeds. When the parser fails the input
1162-- consumed till now is dropped and the new instance is tried on the fresh
1168retry :: -- (MonadCatch m) =>
1169 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