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 : experimental
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
73 -- | Parsers chained in series, if one parser terminates the composition
76 -- | Grab a sequence of input elements without inspecting them
78 , 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)
204 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
206import Streamly.Internal.Data.Fold.Types (Fold(..))
207import Streamly.Internal.Data.Parser.ParserK.Types (Parser)
209import qualified Streamly.Internal.Data.Parser.ParserD as D
210import qualified Streamly.Internal.Data.Parser.ParserK.Types as K
212-------------------------------------------------------------------------------
213-- Upgrade folds to parses
214-------------------------------------------------------------------------------
216-- | Make a 'Parser' from a 'Fold'.
220{-# INLINE fromFold #-}
221fromFold :: MonadCatch m => Fold m a b -> Parser m a b
222fromFold = K.toParserK . D.fromFold
224-------------------------------------------------------------------------------
225-- Terminating but not failing folds
226-------------------------------------------------------------------------------
229-- >>> S.parse (PR.any (== 0)) $ S.fromList [1,0,1]
233any :: MonadCatch m => (a -> Bool) -> Parser m a Bool
234any = K.toParserK . D.any
237-- >>> S.parse (PR.all (== 0)) $ S.fromList [1,0,1]
241all :: MonadCatch m => (a -> Bool) -> Parser m a Bool
242all = K.toParserK . D.all
244-- This is the dual of stream "yield".
246-- | A parser that always yields a pure value without consuming any input.
250{-# INLINE [3] yield #-}
251yield :: MonadCatch m => b -> Parser m a b
252yield = K.toParserK . D.yield
253{-# RULES "yield fallback to CPS" [2]
254 forall a. K.toParserK (D.yield a) = K.yield a #-}
256-- This is the dual of stream "yieldM".
258-- | A parser that always yields the result of an effectful action without
259-- consuming any input.
264yieldM :: MonadCatch m => m b -> Parser m a b
265yieldM = K.toParserK . D.yieldM
267-- This is the dual of "nil".
269-- | A parser that always fails with an error message without consuming
274{-# INLINE [3] die #-}
275die :: MonadCatch m => String -> Parser m a b
276die = K.toParserK . D.die
277{-# RULES "die fallback to CPS" [2]
278 forall a. K.toParserK (D.die a) = K.die a #-}
280-- This is the dual of "nilM".
282-- | A parser that always fails with an effectful error message and without
283-- consuming any input.
288dieM :: MonadCatch m => m String -> Parser m a b
289dieM = K.toParserK . D.dieM
291-------------------------------------------------------------------------------
293-------------------------------------------------------------------------------
295-- | Peek the head element of a stream, without consuming it. Fails if it
296-- encounters end of input.
298-- >>> S.parse ((,) <$> PR.peek <*> PR.satisfy (> 0)) $ S.fromList [1]
302-- peek = lookAhead (satisfy True)
308peek :: MonadCatch m => Parser m a a
309peek = K.toParserK D.peek
311-- | Succeeds if we are at the end of input, fails otherwise.
313-- >>> S.parse ((,) <$> PR.satisfy (> 0) <*> PR.eof) $ S.fromList [1]
319eof :: MonadCatch m => Parser m a ()
320eof = K.toParserK D.eof
322-- | Returns the next element if it passes the predicate, fails otherwise.
324-- >>> S.parse (PR.satisfy (== 1)) $ S.fromList [1,0,1]
329{-# INLINE satisfy #-}
330satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
331satisfy = K.toParserK . D.satisfy
333-- | Map a 'Maybe' returning function on the next element in the stream. The
334-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
340maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
341maybe = K.toParserK . D.maybe
343-- | Map an 'Either' returning function on the next element in the stream. If
344-- the function returns 'Left err', the parser fails with the error message
345-- @err@ otherwise returns the 'Right' value.
350either :: MonadCatch m => (a -> Either String b) -> Parser m a b
351either = K.toParserK . D.either
353-------------------------------------------------------------------------------
355-------------------------------------------------------------------------------
357-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
358-- elements and folds them using the supplied fold.
360-- Stops after @n@ elements.
361-- Fails if the stream ends before @m@ elements could be taken.
363-- @takeBetween@ is the most general take operation, other take operations can
364-- be defined in terms of takeBetween. For example:
367-- take = takeBetween 0 n -- equivalent of takeLE
368-- take1 = takeBetween 1 n -- equivalent of takeLE1
369-- takeEQ = takeBetween n n
370-- takeGE = takeBetween n maxBound
375{-# INLINE takeBetween #-}
376takeBetween :: -- MonadCatch m =>
377 Int -> Int -> Fold m a b -> Parser m a b
378takeBetween _m _n = undefined -- K.toParserK . D.takeBetween m n
382-- Note: this is called takeP in some parser libraries.
384-- TODO Once we have terminating folds, this Parse should get replaced by Fold.
385-- Alternatively, we can name it "chunkOf" and the corresponding time domain
386-- combinator as "intervalOf" or even "chunk" and "interval".
388-- | Take at most @n@ input elements and fold them using the supplied fold.
390-- Stops after @n@ elements.
393-- >>> S.parse (PR.take 1 FL.toList) $ S.fromList [1]
396-- >>> S.parse (PR.take (-1) FL.toList) $ S.fromList [1]
400-- S.chunksOf n f = S.parseMany (FL.take n f)
406take :: MonadCatch m => Int -> Fold m a b -> Parser m a b
407take n = K.toParserK . D.take n
409-- | Stops after taking exactly @n@ input elements.
411-- * Stops - after @n@ elements.
412-- * Fails - if the stream ends before it can collect @n@ elements.
414-- >>> S.parse (PR.takeEQ 4 FL.toList) $ S.fromList [1,0,1]
415-- > "takeEQ: Expecting exactly 4 elements, got 3"
420takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
421takeEQ n = K.toParserK . D.takeEQ n
423-- | Take at least @n@ input elements, but can collect more.
426-- * Fails - if the stream end before producing @n@ elements.
428-- >>> S.parse (PR.takeGE 4 FL.toList) $ S.fromList [1,0,1]
429-- > "takeGE: Expecting at least 4 elements, got only 3"
431-- >>> S.parse (PR.takeGE 4 FL.toList) $ S.fromList [1,0,1,0,1]
437takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
438takeGE n = K.toParserK . D.takeGE n
441-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
443-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
444-- input. The combinator stops when the condition fails or if the collecting
447-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
448-- implemented in terms of this:
451-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
454-- Stops: when the condition fails or the collecting parser stops.
455-- Fails: when the collecting parser fails.
459{-# INLINE takeWhileP #-}
460takeWhileP :: -- MonadCatch m =>
461 (a -> Bool) -> Parser m a b -> Parser m a b
462takeWhileP _cond = undefined -- K.toParserK . D.takeWhileP cond
464-- | Collect stream elements until an element fails the predicate. The element
465-- on which the predicate fails is returned back to the input stream.
467-- * Stops - when the predicate fails.
470-- >>> S.parse (PR.takeWhile (== 0) FL.toList) $ S.fromList [0,0,1,0,1]
473-- We can implement a @breakOn@ using 'takeWhile':
476-- breakOn p = takeWhile (not p)
481{-# INLINE takeWhile #-}
482takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
483takeWhile cond = K.toParserK . D.takeWhile cond
485-- | Like 'takeWhile' but takes at least one element otherwise fails.
489{-# INLINE takeWhile1 #-}
490takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
491takeWhile1 cond = K.toParserK . D.takeWhile1 cond
493-- | Like 'sliceSepBy' but uses a 'Parser' instead of a 'Fold' to collect the
494-- input. @sliceSepByP cond parser@ parses a slice of the input using @parser@
495-- until @cond@ succeeds or the parser stops.
497-- This is a generalized slicing parser which can be used to implement other
501-- sliceSepByMax cond n p = sliceBy cond (take n p)
502-- sliceSepByBetween cond m n p = sliceBy cond (takeBetween m n p)
507{-# INLINABLE sliceSepByP #-}
508sliceSepByP :: -- MonadCatch m =>
509 (a -> Bool) -> Parser m a b -> Parser m a b
510sliceSepByP _cond = undefined -- K.toParserK . D.sliceSepByP cond
512-- Note: Keep this consistent with S.splitOn. In fact we should eliminate
513-- S.splitOn in favor of the parser.
515-- | Split on an infixed separator element, dropping the separator. Splits the
516-- stream on separator elements determined by the supplied predicate, separator
517-- is considered as infixed between two segments, if one side of the separator
518-- is missing then it is parsed as an empty stream. The supplied 'Fold' is
519-- applied on the split segments. With '-' representing non-separator elements
520-- and '.' as separator, 'splitOn' splits as follows:
523-- "--.--" => "--" "--"
528-- @PR.sliceSepBy (== x)@ is an inverse of @S.intercalate (S.yield x)@
530-- Let's use the following definition for illustration:
532-- > splitOn p = PR.many FL.toList $ PR.sliceSepBy p (FL.toList)
533-- > splitOn' p = S.parse (splitOn p) . S.fromList
535-- >>> splitOn' (== '.') ""
538-- >>> splitOn' (== '.') "."
541-- >>> splitOn' (== '.') ".a"
544-- >>> splitOn' (== '.') "a."
547-- >>> splitOn' (== '.') "a.b"
550-- >>> splitOn' (== '.') "a..b"
553-- * Stops - when the predicate succeeds.
557{-# INLINABLE sliceSepBy #-}
558sliceSepBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
559sliceSepBy cond = K.toParserK . D.sliceSepBy cond
561-- | Like 'sliceSepBy' but does not drop the separator element, instead
562-- separator is emitted as a separate element in the output.
565{-# INLINABLE sliceSepWith #-}
566sliceSepWith :: -- MonadCatch m =>
567 (a -> Bool) -> Fold m a b -> Parser m a b
568sliceSepWith _cond = undefined -- K.toParserK . D.sliceSepBy cond
570-- | Collect stream elements until an element succeeds the predicate. Also take
571-- the element on which the predicate succeeded. The succeeding element is
572-- treated as a suffix separator which is kept in the output segement.
574-- * Stops - when the predicate succeeds.
577-- S.splitWithSuffix pred f = S.parseMany (PR.sliceEndWith pred f)
581{-# INLINABLE sliceEndWith #-}
584 (a -> Bool) -> Fold m a b -> Parser m a b
585sliceEndWith = undefined
587-- | Collect stream elements until an elements passes the predicate, return the
588-- last element on which the predicate succeeded back to the input stream. If
589-- the predicate succeeds on the first element itself then it is kept in the
590-- stream and we continue collecting. The succeeding element is treated as a
591-- prefix separator which is kept in the output segement.
593-- * Stops - when the predicate succeeds in non-leading position.
596-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
600{-# INLINABLE sliceBeginWith #-}
603 (a -> Bool) -> Fold m a b -> Parser m a b
604sliceBeginWith = undefined
606-- | Like 'sliceSepBy' but terminates a parse even before the separator
607-- is encountered if its size exceeds the specified maximum limit.
609-- > take n = PR.sliceSepByMax (const True) n
610-- > sliceSepBy p = PR.sliceSepByMax p maxBound
612-- Let's use the following definitions for illustration:
614-- > splitOn p n = PR.many FL.toList $ PR.sliceSepByMax p n (FL.toList)
615-- > splitOn' p n = S.parse (splitOn p n) . S.fromList
617-- >>> splitOn' (== '.') 0 ""
620-- >>> splitOn' (== '.') 0 "a"
621-- infinite list of empty strings
623-- >>> splitOn' (== '.') 3 "hello.world"
624-- ["hel","lo","wor","ld"]
626-- If the separator is found and the limit is reached at the same time then it
627-- behaves just like 'sliceSepBy' i.e. the separator is dropped.
629-- >>> splitOn' (== '.') 0 "."
632-- >>> splitOn' (== '.') 0 ".."
635-- * Stops - when the predicate succeeds or the limit is reached.
639{-# INLINABLE sliceSepByMax #-}
640sliceSepByMax :: MonadCatch m
641 => (a -> Bool) -> Int -> Fold m a b -> Parser m a b
642sliceSepByMax cond cnt = K.toParserK . D.sliceSepByMax cond cnt
644-- | Like 'sliceSepBy' but the separator elements can be escaped using an
645-- escape char determined by the second predicate.
648{-# INLINABLE escapedSliceSepBy #-}
649escapedSliceSepBy :: -- MonadCatch m =>
650 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
651escapedSliceSepBy _cond _esc = undefined
652 -- K.toParserK . D.escapedSliceSepBy cond esc
654-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
655-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
656-- element to escape the occurrence of the framing elements within the frame.
657-- Nested frames are allowed, but nesting is removed when parsing.
661-- >>> escapedFrameBy (== '{') (== '}') (== '\\') S.toList $ S.fromList "{hello}"
664-- >>> escapedFrameBy (== '{') (== '}') (== '\\') S.toList $ S.fromList "{hello {world}}"
667-- >>> escapedFrameBy (== '{') (== '}') (== '\\') S.toList $ S.fromList "{hello \\{world\\}}"
670-- >>> escapedFrameBy (== '{') (== '}') (== '\\') S.toList $ S.fromList "{hello {world}"
671-- > ParseError "Unterminated '{'"
674{-# INLINABLE escapedFrameBy #-}
675escapedFrameBy :: -- MonadCatch m =>
676 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
677escapedFrameBy _begin _end _escape _p = undefined
678 -- K.toParserK . D.frameBy begin end escape p
680-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
681-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
682-- @["a","b"]@. In other words, its like parsing words from whitespace
685-- * Stops - when it finds a word separator after a non-word element
689-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
694{-# INLINABLE wordBy #-}
697 (a -> Bool) -> Fold m a b -> Parser m a b
700-- | @groupBy cmp f $ S.fromList [a,b,c,...]@ assigns the element @a@ to the
701-- first group, then if @a \`cmp` b@ is 'True' @b@ is also assigned to the same
702-- group. If @a \`cmp` c@ is 'True' then @c@ is also assigned to the same
703-- group and so on. When the comparison fails a new group is started. Each
704-- group is folded using the 'Fold' @f@ and the result of the fold is emitted
705-- in the output stream.
707-- * Stops - when the comparison fails.
711-- S.groupsBy cmp f = S.parseMany (PR.groupBy cmp f)
716{-# INLINABLE groupBy #-}
719 (a -> a -> Bool) -> Fold m a b -> Parser m a b
722-- | Match the given sequence of elements using the given comparison function.
724-- >>> S.parse $ S.eqBy (==) "string" $ S.fromList "string"
726-- >>> S.parse $ S.eqBy (==) "mismatch" $ S.fromList "match"
727-- > *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
732eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
733eqBy cmp = K.toParserK . D.eqBy cmp
735-------------------------------------------------------------------------------
737-------------------------------------------------------------------------------
739-- | Sequential parser application. Apply two parsers sequentially to an input
740-- stream. The input is provided to the first parser, when it is done the
741-- remaining input is provided to the second parser. If both the parsers
742-- succeed their outputs are combined using the supplied function. The
743-- operation fails if any of the parsers fail.
745-- Note: This is a parsing dual of appending streams using
746-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
749-- This implementation is strict in the second argument, therefore, the
750-- following will fail:
752-- >>> S.parse (PR.splitWith const (PR.satisfy (> 0)) undefined) $ S.fromList [1]
754-- Compare with 'Applicative' instance method '<*>'. This implementation allows
755-- stream fusion but has quadratic complexity. This can fuse with other
756-- operations and can be faster than 'Applicative' instance for small number
757-- (less than 8) of compositions.
761{-# INLINE splitWith #-}
762splitWith :: MonadCatch m
763 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
765 K.toParserK $ D.splitWith 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-- >>> S.parse (split_ (PR.satisfy (> 0)) undefined) $ S.fromList [1]
778-- Compare with 'Applicative' instance method '*>'. This implementation allows
779-- stream fusion but has quadratic complexity. This can fuse with other
780-- operations, and can be faster than 'Applicative' instance for small
781-- number (less than 8) of compositions.
786split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
787split_ p1 p2 = K.toParserK $ D.split_ (K.fromParserK p1) (K.fromParserK p2)
789-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
790-- of them succeed or anyone of them fails and combines their output using @f@.
791-- The parser succeeds if both the parsers succeed.
795{-# INLINE teeWith #-}
796teeWith :: MonadCatch m
797 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
799 K.toParserK $ D.teeWith f (K.fromParserK p1) (K.fromParserK p2)
801-- | Like 'teeWith' but ends parsing and zips the results, if available,
802-- whenever the first parser ends.
806{-# INLINE teeWithFst #-}
807teeWithFst :: MonadCatch m
808 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
810 K.toParserK $ D.teeWithFst f (K.fromParserK p1) (K.fromParserK p2)
812-- | Like 'teeWith' but ends parsing and zips the results, if available,
813-- whenever any of the parsers ends or fails.
817{-# INLINE teeWithMin #-}
818teeWithMin :: MonadCatch m
819 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
821 K.toParserK $ D.teeWithMin f (K.fromParserK p1) (K.fromParserK p2)
823-- | Sequential alternative. Apply the input to the first parser and return the
824-- result if the parser succeeds. If the first parser fails then backtrack and
825-- apply the same input to the second parser and return the result.
827-- Note: This implementation is not lazy in the second argument. The following
830-- >>> S.parse (PR.satisfy (> 0) `PR.alt` undefined) $ S.fromList [1..10]
832-- Compare with 'Alternative' instance method '<|>'. This implementation allows
833-- stream fusion but has quadratic complexity. This can fuse with other
834-- operations and can be much faster than 'Alternative' instance for small
835-- number (less than 8) of alternatives.
840alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
841alt p1 p2 = K.toParserK $ D.alt (K.fromParserK p1) (K.fromParserK p2)
843-- | Shortest alternative. Apply both parsers in parallel but choose the result
844-- from the one which consumed least input i.e. take the shortest succeeding
849{-# INLINE shortest #-}
850shortest :: MonadCatch m
851 => Parser m x a -> Parser m x a -> Parser m x a
852shortest p1 p2 = K.toParserK $ D.shortest (K.fromParserK p1) (K.fromParserK p2)
854-- | Longest alternative. Apply both parsers in parallel but choose the result
855-- from the one which consumed more input i.e. take the longest succeeding
860{-# INLINE longest #-}
861longest :: MonadCatch m
862 => Parser m x a -> Parser m x a -> Parser m x a
863longest p1 p2 = K.toParserK $ D.longest (K.fromParserK p1) (K.fromParserK p2)
865-- | Run a parser without consuming the input.
869{-# INLINE lookAhead #-}
870lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
871lookAhead p = K.toParserK $ D.lookAhead $ K.fromParserK p
873-------------------------------------------------------------------------------
875-------------------------------------------------------------------------------
877-- To deinterleave we can chain two parsers one behind the other. The input is
878-- given to the first parser and the input definitively rejected by the first
879-- parser is given to the second parser.
881-- We can either have the parsers themselves buffer the input or use the shared
882-- global buffer to hold it until none of the parsers need it. When the first
883-- parser returns Skip (i.e. rewind) we let the second parser consume the
884-- rejected input and when it is done we move the cursor forward to the first
885-- parser again. This will require a "move forward" command as well.
887-- To implement grep we can use three parsers, one to find the pattern, one
888-- to store the context behind the pattern and one to store the context in
889-- front of the pattern. When a match occurs we need to emit the accumulator of
890-- all the three parsers. One parser can count the line numbers to provide the
893-- | Apply two parsers alternately to an input stream. The input stream is
894-- considered an interleaving of two patterns. The two parsers represent the
897-- This undoes a "gintercalate" of two streams.
901{-# INLINE deintercalate #-}
904 Fold m a y -> Parser m x a
905 -> Fold m b z -> Parser m x b
907deintercalate = undefined
909-------------------------------------------------------------------------------
910-- Sequential Collection
911-------------------------------------------------------------------------------
913-- | @sequence f t@ collects sequential parses of parsers in the container @t@
914-- using the fold @f@. Fails if the input ends or any of the parsers fail.
916-- This is same as 'Data.Traversable.sequence' but more efficient.
920{-# INLINE sequence #-}
923 Fold m b c -> t (Parser m a b) -> Parser m a c
924sequence _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.
954 t (Parser m a b) -> Parser m a b
955choice _ps = undefined
957-------------------------------------------------------------------------------
958-- Sequential Repetition
959-------------------------------------------------------------------------------
962-- TODO "many" is essentially a Fold because it cannot fail. So it can be
963-- downgraded to a Fold. Or we can make the return type a Fold instead and
964-- upgrade that to a parser when needed.
966-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
967-- results. Parsing stops or fails if the collecting parser stops or fails.
972manyP :: -- MonadCatch m =>
973 Parser m b c -> Parser m a b -> Parser m a c
974manyP _f _p = undefined -- K.toParserK $ D.manyP f (K.fromParserK p)
976-- | Collect zero or more parses. Apply the parser repeatedly on the input
977-- stream, stop when the parser fails, accumulate zero or more parse results
978-- using the supplied 'Fold'. This parser never fails, in case the first
979-- application of parser fails it returns an empty result.
981-- Compare with 'Control.Applicative.many'.
986many :: MonadCatch m => Fold m b c -> Parser m a b -> Parser m a c
987many f p = K.toParserK $ D.many f (K.fromParserK p)
988-- many = countBetween 0 maxBound
990-- | Collect one or more parses. Apply the supplied parser repeatedly on the
991-- input stream and accumulate the parse results as long as the parser
992-- succeeds, stop when it fails. This parser fails if not even one result is
995-- Compare with 'Control.Applicative.some'.
1000some :: MonadCatch m => Fold m b c -> Parser m a b -> Parser m a c
1001some f p = K.toParserK $ D.some f (K.fromParserK p)
1002-- some f p = manyP (takeGE 1 f) p
1003-- many = countBetween 1 maxBound
1005-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1006-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1007-- the input ends or the parser fails before @m@ results are collected.
1011{-# INLINE countBetween #-}
1014 Int -> Int -> Fold m b c -> Parser m a b -> Parser m a c
1015countBetween _m _n _f = undefined
1016-- countBetween m n f p = manyP (takeBetween m n f) p
1018-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1019-- the fold @f@. Fails if the input ends or the parser fails before @n@
1020-- results are collected.
1027 Int -> Fold m b c -> Parser m a b -> Parser m a c
1028count n = countBetween n n
1029-- count n f p = manyP (takeEQ n f) p
1031-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1032-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1034-- We can implemnent parsers like the following using 'manyTillP':
1037-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1042{-# INLINE manyTillP #-}
1043manyTillP :: -- MonadCatch m =>
1044 Parser m b c -> Parser m a b -> Parser m a x -> Parser m a c
1045manyTillP _f _p1 _p2 = undefined
1046 -- K.toParserK $ D.manyTillP f (K.fromParserK p1) (K.fromParserK p2)
1048-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1049-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1050-- tried again and so on. The parser stops when @test@ succeeds. The output of
1051-- @test@ is discarded and the output of @collect@ is accumulated by the
1052-- supplied fold. The parser fails if @collect@ fails.
1056{-# INLINE manyTill #-}
1057manyTill :: MonadCatch m
1058 => Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1060 K.toParserK $ D.manyTill f (K.fromParserK p1) (K.fromParserK p2)
1062-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1063-- collects the output in the supplied fold. If the the parser @collect@ fails,
1064-- parser @recover@ is run until it stops and then we start repeating the
1065-- parser @collect@ again. The parser fails if the recovery parser fails.
1067-- For example, this can be used to find a key frame in a video stream after an
1072{-# INLINE manyThen #-}
1073manyThen :: -- (Foldable t, MonadCatch m) =>
1074 Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1075manyThen _f _parser _recover = undefined
1077-------------------------------------------------------------------------------
1078-- Interleaving a collection of parsers
1079-------------------------------------------------------------------------------
1081-- | Apply a collection of parsers to an input stream in a round robin fashion.
1082-- Each parser is applied until it stops and then we repeat starting with the
1083-- the first parser again.
1087{-# INLINE roundRobin #-}
1088roundRobin :: -- (Foldable t, MonadCatch m) =>
1089 Fold m b c -> t (Parser m a b) -> Parser m a c
1090roundRobin _f _ps = undefined
1092-------------------------------------------------------------------------------
1093-- Repeated Alternatives
1094-------------------------------------------------------------------------------
1096-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1097-- fails the input consumed till now is dropped and the new instance is tried
1098-- on the fresh input.
1102{-# INLINE retryMaxTotal #-}
1103retryMaxTotal :: -- (MonadCatch m) =>
1104 Int -> Fold m b c -> Parser m a b -> Parser m a c
1105retryMaxTotal _n _f _p = undefined
1107-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1111{-# INLINE retryMaxSuccessive #-}
1112retryMaxSuccessive :: -- (MonadCatch m) =>
1113 Int -> Fold m b c -> Parser m a b -> Parser m a c
1114retryMaxSuccessive _n _f _p = undefined
1116-- | Keep trying a parser until it succeeds. When the parser fails the input
1117-- consumed till now is dropped and the new instance is tried on the fresh
1123retry :: -- (MonadCatch m) =>
1124 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