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 -- All of these can be expressed in terms of either
85 -- * Sequence parsers (tokenizers)
87 -- | Parsers chained in series, if one parser terminates the composition
93 -- | Grab a sequence of input elements without inspecting them
95 -- , take -- takeBetween 0 n
96 , takeEQ -- takeBetween n n
97 , takeGE -- takeBetween n maxBound
100 -- Grab a sequence of input elements by inspecting them
126 , groupByRollingEither
132 , takeFramedByGeneric
139 -- , prefixOf -- match any prefix of a given string
140 -- , suffixOf -- match any suffix of a given string
141 -- , infixOf -- match any substring of a given string
144 -- Second order parsers (parsers using parsers)
145 -- * Binary Combinators
147 -- ** Sequential Applicative
152 -- ** Parallel Applicatives
156 -- , teeTill -- like manyTill but parallel
159 -- ** Sequential Interleaving
160 -- Use two folds, run a primary parser, its rejected values go to the
163 -- , deintercalatePrefix
164 -- , deintercalateSuffix
167 -- | TODO: traditional implmentations of these may be of limited use. For
168 -- example, consider parsing lines separated by @\\r\\n@. The main parser
169 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
170 -- can apply the "sep" parser.
172 -- We can instead implement these as special cases of deintercalate.
184 -- ** Sequential Alternative
188 -- ** Parallel Alternatives
194 -- * N-ary Combinators
195 -- ** Sequential Collection
199 -- ** Sequential Repetition
212 -- | A simple and stupid impl would be to just convert the stream to an
213 -- array and give the array reference to all consumers. The array can be
214 -- grown on demand by any consumer and truncated when nonbody needs it.
216 -- ** Distribute to collection
217 -- ** Distribute to repetition
219 -- ** Interleaved collection
226 -- ** Collection of Alternatives
232 -- , fastestN -- first N successful in time
233 -- , choiceN -- first N successful in position
235 -- , choice -- first successful in position
237 -- ** Repeated Alternatives
247import Data.Functor (($>))
249 ( any, all, dropWhile, take, takeWhile, sequence, concatMap, maybe, either
252import Streamly.Internal.Data.Fold.Type (Fold(..))
253import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
254import Streamly.Internal.Data.Stream.Type (Stream)
256import qualified Streamly.Internal.Data.Fold.Type as FL
257import qualified Streamly.Internal.Data.Parser.ParserD as D
258import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
259import qualified Streamly.Internal.Data.Stream.Type as Stream
264-- >>> :set -package streamly
265-- >>> import Prelude hiding (any, all, dropWhile, take, takeWhile, sequence, concatMap, maybe, either, filter)
266-- >>> import Control.Applicative ((<|>))
267-- >>> import Data.Char (isSpace)
268-- >>> import qualified Data.Maybe as Maybe
269-- >>> import qualified Streamly.Data.Stream as Stream
270-- >>> import qualified Streamly.Internal.Data.Stream as Stream (parse, parseMany)
271-- >>> import qualified Streamly.Internal.Data.Fold as Fold
272-- >>> import qualified Streamly.Internal.Data.Parser as Parser
274-------------------------------------------------------------------------------
275-- Downgrade a parser to a Fold
276-------------------------------------------------------------------------------
278-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
279-- parser fails or tries to backtrack.
281-- This can be useful in combinators that accept a Fold and we know that a
282-- Parser cannot fail or failure exception is acceptable as there is no way to
288toFold :: Monad m => Parser m a b -> Fold m a b
289toFold p = D.toFold $ D.fromParserK p
291-------------------------------------------------------------------------------
292-- Upgrade folds to parses
293-------------------------------------------------------------------------------
295-- | Make a 'Parser' from a 'Fold'.
299{-# INLINE fromFold #-}
300fromFold :: Monad m => Fold m a b -> Parser m a b
301fromFold = D.toParserK . D.fromFold
303-- | Convert a Maybe returning fold to an error returning parser. The first
304-- argument is the error message that the parser would return when the fold
309{-# INLINE fromFoldMaybe #-}
310fromFoldMaybe :: Monad m => String -> Fold m a (Maybe b) -> Parser m a b
311fromFoldMaybe err = D.toParserK . D.fromFoldMaybe err
313-------------------------------------------------------------------------------
314-- Terminating but not failing folds
315-------------------------------------------------------------------------------
317-- This is the dual of stream "fromPure".
319-- | A parser that always yields a pure value without consuming any input.
323{-# INLINE [3] fromPure #-}
324fromPure :: Monad m => b -> Parser m a b
325fromPure = D.toParserK . D.fromPure
326{-# RULES "fromPure fallback to CPS" [2]
327 forall a. D.toParserK (D.fromPure a) = K.fromPure a #-}
329-- This is the dual of stream "fromEffect".
331-- | A parser that always yields the result of an effectful action without
332-- consuming any input.
336{-# INLINE fromEffect #-}
337fromEffect :: Monad m => m b -> Parser m a b
338fromEffect = K.fromEffect -- D.toParserK . D.fromEffect
340-- This is the dual of "nil".
342-- | A parser that always fails with an error message without consuming
347{-# INLINE [3] die #-}
348die :: Monad m => String -> Parser m a b
349die = D.toParserK . D.die
350{-# RULES "die fallback to CPS" [2]
351 forall a. D.toParserK (D.die a) = K.die a #-}
353-- This is the dual of "nilM".
355-- | A parser that always fails with an effectful error message and without
356-- consuming any input.
361dieM :: Monad m => m String -> Parser m a b
362dieM = D.toParserK . D.dieM
364-------------------------------------------------------------------------------
366-------------------------------------------------------------------------------
368-- | @lmap f parser@ maps the function @f@ on the input of the parser.
370-- >>> Stream.parse (Parser.lmap (\x -> x * x) (Parser.fromFold Fold.sum)) (Stream.enumerateFromTo 1 100)
373-- > lmap = Parser.lmapM return
377lmap :: Monad m => (a -> b) -> Parser m b r -> Parser m a r
378lmap f p = D.toParserK $ D.lmap f $ D.fromParserK p
380-- | @lmapM f parser@ maps the monadic function @f@ on the input of the parser.
384lmapM :: Monad m => (a -> m b) -> Parser m b r -> Parser m a r
385lmapM f p = D.toParserK $ D.lmapM f $ D.fromParserK p
387-- | Include only those elements that pass a predicate.
389-- >>> Stream.parse (Parser.filter (> 5) (Parser.fromFold Fold.sum)) $ Stream.fromList [1..10]
394filter :: Monad m => (a -> Bool) -> Parser m a b -> Parser m a b
395filter f p = D.toParserK $ D.filter f $ D.fromParserK p
397-------------------------------------------------------------------------------
399-------------------------------------------------------------------------------
401-- | Peek the head element of a stream, without consuming it. Fails if it
402-- encounters end of input.
404-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
408-- peek = lookAhead (satisfy True)
414peek :: Monad m => Parser m a a
415peek = D.toParserK D.peek
417-- | Succeeds if we are at the end of input, fails otherwise.
419-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
425eof :: Monad m => Parser m a ()
426eof = D.toParserK D.eof
428-- | Returns the next element if it passes the predicate, fails otherwise.
430-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
433-- >>> toMaybe f x = if f x then Just x else Nothing
434-- >>> satisfy f = Parser.maybe (toMaybe f)
438{-# INLINE satisfy #-}
439satisfy :: Monad m => (a -> Bool) -> Parser m a a
440satisfy = D.toParserK . D.satisfy
442-- | Consume one element from the head of the stream. Fails if it encounters
445-- >>> one = Parser.satisfy $ const True
450one :: Monad m => Parser m a a
451one = satisfy $ const True
453-- | Match a specific element.
455-- >>> element x = Parser.satisfy (== x)
457{-# INLINE element #-}
458element :: (Monad m, Eq a) => a -> Parser m a a
459element x = satisfy (== x)
461-- | Match anything other than the supplied element.
463-- >>> except x = Parser.satisfy (/= x)
466except :: (Monad m, Eq a) => a -> Parser m a a
467except x = satisfy (/= x)
469-- | Match any one of the elements in the supplied list.
471-- >>> oneOf xs = Parser.satisfy (`elem` xs)
473-- When performance matters a pattern matching predicate could be more
474-- efficient than a list:
485-- GHC may use a binary search instead of linear search in the list.
486-- Alternatively, you can also use an array instead of list for storage and
490oneOf :: (Monad m, Eq a) => [a] -> Parser m a a
491oneOf xs = satisfy (`elem` xs)
493-- | See performance notes in 'oneOf'.
495-- >>> noneOf xs = Parser.satisfy (`notElem` xs)
498noneOf :: (Monad m, Eq a) => [a] -> Parser m a a
499noneOf xs = satisfy (`notElem` xs)
501-- | Return the next element of the input. Returns 'Nothing'
502-- on end of input. Also known as 'head'.
506{-# DEPRECATED next "Please use \"fromFold Fold.one\" instead" #-}
508next :: Monad m => Parser m a (Maybe a)
509next = D.toParserK D.next
511-- | Map a 'Maybe' returning function on the next element in the stream. The
512-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
515-- >>> toEither = Maybe.maybe (Left "maybe: predicate failed") Right
516-- >>> maybe f = Parser.either (toEither . f)
518-- >>> maybe f = Parser.fromFoldMaybe "maybe: predicate failed" (Fold.maybe f)
523maybe :: Monad m => (a -> Maybe b) -> Parser m a b
524maybe = D.toParserK . D.maybe
526-- | Map an 'Either' returning function on the next element in the stream. If
527-- the function returns 'Left err', the parser fails with the error message
528-- @err@ otherwise returns the 'Right' value.
533either :: Monad m => (a -> Either String b) -> Parser m a b
534either = D.toParserK . D.either
536-------------------------------------------------------------------------------
538-------------------------------------------------------------------------------
540-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
541-- elements and folds them using the supplied fold.
543-- Stops after @n@ elements.
544-- Fails if the stream ends before @m@ elements could be taken.
550-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
551-- where prsr = Parser.takeBetween low high Fold.toList
556-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
559-- >>> takeBetween' 2 4 [1, 2]
562-- >>> takeBetween' 2 4 [1]
563-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
565-- >>> takeBetween' 0 0 [1, 2]
568-- >>> takeBetween' 0 1 []
571-- @takeBetween@ is the most general take operation, other take operations can
572-- be defined in terms of takeBetween. For example:
574-- >>> take n = Parser.takeBetween 0 n
575-- >>> takeEQ n = Parser.takeBetween n n
576-- >>> takeGE n = Parser.takeBetween n maxBound
580{-# INLINE takeBetween #-}
581takeBetween :: Monad m =>
582 Int -> Int -> Fold m a b -> Parser m a b
583takeBetween m n = D.toParserK . D.takeBetween m n
585-- | Stops after taking exactly @n@ input elements.
587-- * Stops - after consuming @n@ elements.
588-- * Fails - if the stream or the collecting fold ends before it can collect
589-- exactly @n@ elements.
591-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
592-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
597takeEQ :: Monad m => Int -> Fold m a b -> Parser m a b
598takeEQ n = D.toParserK . D.takeEQ n
600-- | Take at least @n@ input elements, but can collect more.
602-- * Stops - when the collecting fold stops.
603-- * Fails - if the stream or the collecting fold ends before producing @n@
606-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
607-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
609-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
615takeGE :: Monad m => Int -> Fold m a b -> Parser m a b
616takeGE n = D.toParserK . D.takeGE n
618-------------------------------------------------------------------------------
619-- Take until a condition
620-------------------------------------------------------------------------------
623-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
625-- XXX We should perhaps use only takeWhileP and rename it to takeWhile.
627-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
628-- input. The combinator stops when the condition fails or if the collecting
631-- Other interesting parsers can be implemented in terms of this parser:
633-- >>> takeWhile1 cond p = Parser.takeWhileP cond (Parser.takeBetween 1 maxBound p)
634-- >>> takeWhileBetween cond m n p = Parser.takeWhileP cond (Parser.takeBetween m n p)
636-- Stops: when the condition fails or the collecting parser stops.
637-- Fails: when the collecting parser fails.
641{-# INLINE takeWhileP #-}
642takeWhileP :: Monad m => (a -> Bool) -> Parser m a b -> Parser m a b
643takeWhileP cond p = D.toParserK $ D.takeWhileP cond (D.fromParserK p)
645-- | Collect stream elements until an element fails the predicate. The element
646-- on which the predicate fails is returned back to the input stream.
648-- * Stops - when the predicate fails or the collecting fold stops.
651-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
654-- >>> takeWhile cond f = Parser.takeWhileP cond (Parser.fromFold f)
656-- We can implement a @breakOn@ using 'takeWhile':
659-- breakOn p = takeWhile (not p)
664{-# INLINE takeWhile #-}
665takeWhile :: Monad m => (a -> Bool) -> Fold m a b -> Parser m a b
666takeWhile cond = D.toParserK . D.takeWhile cond
667-- takeWhile cond f = takeWhileP cond (fromFold f)
669-- | Like 'takeWhile' but takes at least one element otherwise fails.
671-- >>> takeWhile1 cond p = Parser.takeWhileP cond (Parser.takeBetween 1 maxBound p)
675{-# INLINE takeWhile1 #-}
676takeWhile1 :: Monad m => (a -> Bool) -> Fold m a b -> Parser m a b
677takeWhile1 cond = D.toParserK . D.takeWhile1 cond
678-- takeWhile1 cond f = takeWhileP cond (takeBetween 1 maxBound f)
680-- | Drain the input as long as the predicate succeeds, running the effects and
681-- discarding the results.
683-- This is also called @skipWhile@ in some parsing libraries.
685-- >>> dropWhile p = Parser.takeWhile p Fold.drain
689{-# INLINE dropWhile #-}
690dropWhile :: Monad m => (a -> Bool) -> Parser m a ()
691dropWhile p = takeWhile p FL.drain
693-------------------------------------------------------------------------------
695-------------------------------------------------------------------------------
697-- XXX We can remove Maybe from esc
698{-# INLINE takeFramedByGeneric #-}
699takeFramedByGeneric :: Monad m =>
705takeFramedByGeneric esc begin end f =
706 D.toParserK $ D.takeFramedByGeneric esc begin end f
708-- | @takeEndBy cond parser@ parses a token that ends by a separator chosen by
709-- the supplied predicate. The separator is also taken with the token.
711-- This can be combined with other parsers to implement other interesting
712-- parsers as follows:
714-- >>> takeEndByLE cond n p = Parser.takeEndBy cond (Parser.fromFold $ Fold.take n p)
715-- >>> takeEndByBetween cond m n p = Parser.takeEndBy cond (Parser.takeBetween m n p)
717-- >>> takeEndBy = Parser.takeEndByEsc (const False)
719-- See also "Streamly.Data.Fold.takeEndBy". Unlike the fold, the collecting
720-- parser in the takeEndBy parser can decide whether to fail or not if the
721-- stream does not end with separator.
725{-# INLINE takeEndBy #-}
726takeEndBy :: Monad m => (a -> Bool) -> Parser m a b -> Parser m a b
727takeEndBy cond = D.toParserK . D.takeEndBy cond . D.fromParserK
728-- takeEndBy = takeEndByEsc (const False)
730-- | Like 'takeEndBy' but the separator is dropped.
732-- See also "Streamly.Data.Fold.takeEndBy_".
736{-# INLINE takeEndBy_ #-}
737takeEndBy_ :: Monad m => (a -> Bool) -> Parser m a b -> Parser m a b
738takeEndBy_ cond = D.toParserK . D.takeEndBy_ cond . D.fromParserK
741 takeFramedByGeneric Nothing Nothing (Just isEnd) (toFold p)
744-- | Take either the separator or the token. Separator is a Left value and
745-- token is Right value.
748{-# INLINE takeEitherSepBy #-}
749takeEitherSepBy :: -- Monad m =>
750 (a -> Bool) -> Fold m (Either a b) c -> Parser m a c
751takeEitherSepBy _cond = undefined -- D.toParserK . D.takeEitherSepBy cond
753-- | Parse a token that starts with an element chosen by the predicate. The
754-- parser fails if the input does not start with the selected element.
756-- * Stops - when the predicate succeeds in non-leading position.
757-- * Fails - when the predicate fails in the leading position.
759-- >>> splitWithPrefix p f = Stream.parseMany (Parser.takeStartBy p f)
763-- >>> p = Parser.takeStartBy (== ',') Fold.toList
764-- >>> leadingComma = Stream.parse p . Stream.fromList
765-- >>> leadingComma "a,b"
766-- *** Exception: ParseError "takeStartBy: missing frame start"
768-- >>> leadingComma ",,"
770-- >>> leadingComma ",a,b"
772-- >>> leadingComma ""
777{-# INLINE takeStartBy #-}
778takeStartBy :: Monad m => (a -> Bool) -> Fold m a b -> Parser m a b
779takeStartBy cond = D.toParserK . D.takeStartBy cond
781-- | Like 'takeStartBy' but drops the separator.
783-- >>> takeStartBy_ isBegin = Parser.takeFramedByGeneric Nothing (Just isBegin) Nothing
785{-# INLINE takeStartBy_ #-}
786takeStartBy_ :: Monad m => (a -> Bool) -> Fold m a b -> Parser m a b
787takeStartBy_ isBegin = takeFramedByGeneric Nothing (Just isBegin) Nothing
789-------------------------------------------------------------------------------
790-- Quoting and Escaping
791-------------------------------------------------------------------------------
793-- | Like 'takeEndBy' but the separator elements can be escaped using an
794-- escape char determined by the first predicate. The escape characters are
798{-# INLINE takeEndByEsc #-}
799takeEndByEsc :: Monad m =>
800 (a -> Bool) -> (a -> Bool) -> Parser m a b -> Parser m a b
801takeEndByEsc isEsc isEnd p =
802 D.toParserK $ D.takeEndByEsc isEsc isEnd (D.fromParserK p)
804-- | @takeFramedByEsc_ isEsc isBegin isEnd fold@ parses a token framed using a
805-- begin and end predicate, and an escape character. The frame begin and end
806-- characters lose their special meaning if preceded by the escape character.
808-- Nested frames are allowed if begin and end markers are different, nested
809-- frames must be balanced unless escaped, nested frame markers are emitted as
814-- >>> p = Parser.takeFramedByEsc_ (== '\\') (== '{') (== '}') Fold.toList
815-- >>> Stream.parse p $ Stream.fromList "{hello}"
817-- >>> Stream.parse p $ Stream.fromList "{hello {world}}"
819-- >>> Stream.parse p $ Stream.fromList "{hello \\{world}"
821-- >>> Stream.parse p $ Stream.fromList "{hello {world}"
822-- *** Exception: ParseError "takeFramedByEsc_: missing frame end"
825{-# INLINE takeFramedByEsc_ #-}
826takeFramedByEsc_ :: Monad m =>
827 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
828takeFramedByEsc_ isEsc isBegin isEnd f =
829 D.toParserK $ D.takeFramedByEsc_ isEsc isBegin isEnd f
830-- takeEndByEsc_ isEsc isEnd p =
831-- takeFramedByGeneric (Just isEsc) Nothing (Just isEnd) (toFold p)
833-- | @takeFramedBy_ isBegin isEnd fold@ parses a token framed by a begin and an
836-- >>> takeFramedBy_ = Parser.takeFramedByEsc_ (const False)
838{-# INLINE takeFramedBy_ #-}
839takeFramedBy_ :: Monad m =>
840 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
841takeFramedBy_ isBegin isEnd f = D.toParserK $ D.takeFramedBy_ isBegin isEnd f
842-- takeFramedBy_ isBegin isEnd =
843-- takeFramedByGeneric (Just (const False)) (Just isBegin) (Just isEnd)
845-------------------------------------------------------------------------------
847-------------------------------------------------------------------------------
849-- Note we can also get words using something like:
850-- sepBy FL.toList (takeWhile (not . p) Fold.toList) (dropWhile p)
852-- But that won't be as efficient and ergonomic.
854-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
855-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
856-- @["a","b"]@. In other words, its like parsing words from whitespace
859-- * Stops - when it finds a word separator after a non-word element
862-- >>> wordBy = Parser.wordFramedBy (const False) (const False) (const False)
865-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
869wordBy :: Monad m => (a -> Bool) -> Fold m a b -> Parser m a b
870wordBy f = D.toParserK . D.wordBy f
872-- | Like 'wordBy' but treats anything inside a pair of quotes as a single
873-- word, the quotes can be escaped by an escape character. Recursive quotes
874-- are possible if quote begin and end characters are different, quotes must be
875-- balanced. Outermost quotes are stripped.
877-- >>> braces = Parser.wordFramedBy (== '\\') (== '{') (== '}') isSpace Fold.toList
878-- >>> Stream.parse braces $ Stream.fromList "{ab} cd"
880-- >>> Stream.parse braces $ Stream.fromList "{ab}{cd}"
882-- >>> Stream.parse braces $ Stream.fromList "a{b} cd"
884-- >>> Stream.parse braces $ Stream.fromList "a{{b}} cd"
887-- >>> quotes = Parser.wordFramedBy (== '\\') (== '"') (== '"') isSpace Fold.toList
888-- >>> Stream.parse quotes $ Stream.fromList "\"a\"\"b\""
892{-# INLINE wordFramedBy #-}
893wordFramedBy :: Monad m =>
894 (a -> Bool) -- ^ Escape
895 -> (a -> Bool) -- ^ left quote
896 -> (a -> Bool) -- ^ right quote
897 -> (a -> Bool) -- ^ word seperator
900wordFramedBy isEsc isBegin isEnd isSpc =
901 D.toParserK . D.wordFramedBy isEsc isBegin isEnd isSpc
903-- | Like 'wordFramedBy' but the closing quote is determined by the opening
904-- quote. The first quote begin starts a quote that is closed by its
905-- corresponding closing quote.
907-- 'wordFramedBy' and 'wordQuotedBy' both allow multiple quote characters based
908-- on the predicates but 'wordQuotedBy' always fixes the quote at the first
909-- occurrence and then it is closed only by the corresponding closing quote.
910-- Therefore, other quoting characters can be embedded inside it as normal
911-- characters. On the other hand, 'wordFramedBy' would close the quote as soon
912-- as it encounters any of the closing quotes.
914-- >>> q = (`elem` ['"', '\''])
915-- >>> p kQ = Parser.wordQuotedBy kQ (== '\\') q q id isSpace Fold.toList
917-- >>> Stream.parse (p False) $ Stream.fromList "a\"b'c\";'d\"e'f ghi"
920-- >>> Stream.parse (p True) $ Stream.fromList "a\"b'c\";'d\"e'f ghi"
923{-# INLINE wordQuotedBy #-}
924wordQuotedBy :: (Monad m, Eq a) =>
925 Bool -- ^ keep the quotes in the output
926 -> (a -> Bool) -- ^ Escape
927 -> (a -> Bool) -- ^ left quote
928 -> (a -> Bool) -- ^ right quote
929 -> (a -> a) -- ^ get right quote from left quote
930 -> (a -> Bool) -- ^ word seperator
933wordQuotedBy keepQuotes isEsc isBegin isEnd toRight isSpc =
934 D.toParserK . D.wordQuotedBy keepQuotes isEsc isBegin isEnd toRight isSpc
936-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
937-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
938-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
939-- then @c@ is also assigned to the same group and so on. When the comparison
940-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
941-- the result of the fold is the result of the parser.
943-- * Stops - when the comparison fails.
948-- Stream.fold Fold.toList
949-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
953-- >>> runGroupsBy (<) []
956-- >>> runGroupsBy (<) [1]
959-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
960-- [[3,5,4],[1,2],[0]]
964{-# INLINE groupBy #-}
965groupBy :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
966groupBy eq = D.toParserK . D.groupBy eq
968-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
969-- successive elements in the input stream. Assuming the input stream
970-- is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
971-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
972-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
973-- then @c@ is also assigned to the same group and so on. When the comparison
974-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
975-- the result of the fold is the result of the parser.
977-- * Stops - when the comparison fails.
981-- runGroupsByRolling eq =
982-- Stream.fold Fold.toList
983-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
987-- >>> runGroupsByRolling (<) []
990-- >>> runGroupsByRolling (<) [1]
993-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
994-- [[3,5],[4],[1,2],[0]]
998{-# INLINE groupByRolling #-}
999groupByRolling :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
1000groupByRolling eq = D.toParserK . D.groupByRolling eq
1002-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
1003-- the first fold as long as the predicate holds 'True', if the predicate is
1004-- 'False' collects using the second fold as long as it remains 'False'.
1005-- Returns 'Left' for the first case and 'Right' for the second case.
1007-- For example, if we want to detect sorted sequences in a stream, both
1008-- ascending and descending cases we can use 'groupByRollingEither (<=)
1009-- Fold.toList Fold.toList'.
1012{-# INLINE groupByRollingEither #-}
1013groupByRollingEither :: Monad m =>
1014 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser m a (Either b c)
1015groupByRollingEither eq f1 = D.toParserK . D.groupByRollingEither eq f1
1017-- XXX Use a stream instead of a list so that we can use any container type.
1019-- | Match the given sequence of elements using the given comparison function.
1021-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
1023-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
1024-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
1029eqBy :: Monad m => (a -> a -> Bool) -> [a] -> Parser m a ()
1030eqBy cmp = D.toParserK . D.eqBy cmp
1032-- | Match the input sequence with the supplied list and return it if
1037list :: (Monad m, Eq a) => [a] -> Parser m a [a]
1038list xs = eqBy (==) xs $> xs
1040-------------------------------------------------------------------------------
1042-------------------------------------------------------------------------------
1044-- | Sequential parser application. Apply two parsers sequentially to an input
1045-- stream. The input is provided to the first parser, when it is done the
1046-- remaining input is provided to the second parser. If both the parsers
1047-- succeed their outputs are combined using the supplied function. The
1048-- operation fails if any of the parsers fail.
1050-- Note: This is a parsing dual of appending streams using
1051-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
1054-- This implementation is strict in the second argument, therefore, the
1055-- following will fail:
1057-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
1058-- *** Exception: Prelude.undefined
1061-- Compare with 'Applicative' instance method '<*>'. This implementation allows
1062-- stream fusion but has quadratic complexity. This can fuse with other
1063-- operations and can be faster than 'Applicative' instance for small number
1064-- (less than 8) of compositions.
1066-- Many combinators can be expressed using @serialWith@ and other parser
1067-- primitives. Some common idioms are described below,
1070-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
1071-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
1075-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
1076-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
1080-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
1081-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
1086{-# INLINE serialWith #-}
1087serialWith :: Monad m
1088 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
1090 D.toParserK $ D.serialWith f (D.fromParserK p1) (D.fromParserK p2)
1092-- | Sequential parser application ignoring the output of the first parser.
1093-- Apply two parsers sequentially to an input stream. The input is provided to
1094-- the first parser, when it is done the remaining input is provided to the
1095-- second parser. The output of the parser is the output of the second parser.
1096-- The operation fails if any of the parsers fail.
1098-- This implementation is strict in the second argument, therefore, the
1099-- following will fail:
1101-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
1102-- *** Exception: Prelude.undefined
1105-- Compare with 'Applicative' instance method '*>'. This implementation allows
1106-- stream fusion but has quadratic complexity. This can fuse with other
1107-- operations, and can be faster than 'Applicative' instance for small
1108-- number (less than 8) of compositions.
1112{-# INLINE split_ #-}
1113split_ :: Monad m => Parser m x a -> Parser m x b -> Parser m x b
1114split_ p1 p2 = D.toParserK $ D.split_ (D.fromParserK p1) (D.fromParserK p2)
1117-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
1118-- of them succeed or anyone of them fails and combines their output using @f@.
1119-- The parser succeeds if both the parsers succeed.
1123{-# INLINE teeWith #-}
1125 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
1127 D.toParserK $ D.teeWith f (D.fromParserK p1) (D.fromParserK p2)
1129-- | Like 'teeWith' but ends parsing and zips the results, if available,
1130-- whenever the first parser ends.
1134{-# INLINE teeWithFst #-}
1135teeWithFst :: Monad m
1136 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
1138 D.toParserK $ D.teeWithFst f (D.fromParserK p1) (D.fromParserK p2)
1140-- | Like 'teeWith' but ends parsing and zips the results, if available,
1141-- whenever any of the parsers ends or fails.
1145{-# INLINE teeWithMin #-}
1146teeWithMin :: Monad m
1147 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
1149 D.toParserK $ D.teeWithMin f (D.fromParserK p1) (D.fromParserK p2)
1152-- | Sequential alternative. Apply the input to the first parser and return the
1153-- result if the parser succeeds. If the first parser fails then backtrack and
1154-- apply the same input to the second parser and return the result.
1156-- Note: This implementation is not lazy in the second argument. The following
1159-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
1162-- Compare with 'Alternative' instance method '<|>'. This implementation allows
1163-- stream fusion but has quadratic complexity. This can fuse with other
1164-- operations and can be much faster than 'Alternative' instance for small
1165-- number (less than 8) of alternatives.
1170alt :: Monad m => Parser m x a -> Parser m x a -> Parser m x a
1171alt p1 p2 = D.toParserK $ D.alt (D.fromParserK p1) (D.fromParserK p2)
1174-- | Shortest alternative. Apply both parsers in parallel but choose the result
1175-- from the one which consumed least input i.e. take the shortest succeeding
1180{-# INLINE shortest #-}
1182 => Parser m x a -> Parser m x a -> Parser m x a
1183shortest p1 p2 = D.toParserK $ D.shortest (D.fromParserK p1) (D.fromParserK p2)
1185-- | Longest alternative. Apply both parsers in parallel but choose the result
1186-- from the one which consumed more input i.e. take the longest succeeding
1191{-# INLINE longest #-}
1193 => Parser m x a -> Parser m x a -> Parser m x a
1194longest p1 p2 = D.toParserK $ D.longest (D.fromParserK p1) (D.fromParserK p2)
1197-- | Run a parser without consuming the input.
1201{-# INLINE lookAhead #-}
1202lookAhead :: Monad m => Parser m a b -> Parser m a b
1203lookAhead p = D.toParserK $ D.lookAhead $ D.fromParserK p
1205-- | Takes at-most @n@ input elements.
1207-- * Stops - when the collecting parser stops.
1208-- * Fails - when the collecting parser fails.
1210-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
1213-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
1214-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
1218takeP :: Monad m => Int -> Parser m a b -> Parser m a b
1219takeP i p = D.toParserK $ D.takeP i $ D.fromParserK p
1221-------------------------------------------------------------------------------
1222-- Sequential Collection
1223-------------------------------------------------------------------------------
1225-- | @concatSequence f p@ collects sequential parses of parsers in a
1226-- serial stream @p@ using the fold @f@. Fails if the input ends or any
1227-- of the parsers fail.
1229-- An even more efficient implementation can use ParserD type Parser in
1234{-# INLINE concatSequence #-}
1237 Fold m b c -> Stream m (Parser m a b) -> Parser m a c
1239 let sp = fmap D.fromParserK $ Stream.toStreamD p
1240 in D.toParserK $ D.sequence f sp
1242-- | Map a 'Parser' returning function on the result of a 'Parser'.
1244-- Compare with 'Monad' instance method '>>='. This implementation allows
1245-- stream fusion but has quadratic complexity. This can fuse with other
1246-- operations and can be much faster than 'Monad' instance for small number
1247-- (less than 8) of compositions.
1251{-# INLINE concatMap #-}
1253 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
1254concatMap f p = D.toParserK $ D.concatMap (D.fromParserK . f) (D.fromParserK p)
1257-------------------------------------------------------------------------------
1258-- Alternative Collection
1259-------------------------------------------------------------------------------
1261-- | @choice parsers@ applies the @parsers@ in order and returns the first
1264-- This is same as 'asum' but more efficient.
1268{-# INLINE choice #-}
1270 (Functor t, Foldable t, Monad m) => t (Parser m a b) -> Parser m a b
1271choice ps = D.toParserK $ D.choice $ D.fromParserK <$> ps
1274-------------------------------------------------------------------------------
1275-- Sequential Repetition
1276-------------------------------------------------------------------------------
1278-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1279-- results. Parsing stops or fails if the collecting parser stops or fails.
1284manyP :: -- Monad m =>
1285 Parser m a b -> Parser m b c -> Parser m a c
1286manyP _p _f = undefined -- D.toParserK $ D.manyP (D.fromParserK p) f
1288-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1289-- input stream and push the parse results to a downstream fold.
1291-- Stops: when the downstream fold stops or the parser fails.
1292-- Fails: never, produces zero or more results.
1294-- >>> many = Parser.countBetween 0 maxBound
1296-- Compare with 'Control.Applicative.many'.
1301many :: Monad m => Parser m a b -> Fold m b c -> Parser m a c
1302many p f = D.toParserK $ D.many (D.fromParserK p) f
1304-- Note: many1 would perhaps be a better name for this and consistent with
1305-- other names like takeWhile1. But we retain the name "some" for
1308-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1309-- input stream and push the parse results to a downstream fold.
1311-- Stops: when the downstream fold stops or the parser fails.
1312-- Fails: if it stops without producing a single result.
1314-- >>> some p f = Parser.manyP p (Parser.takeGE 1 f)
1315-- >>> some = Parser.countBetween 1 maxBound
1317-- Compare with 'Control.Applicative.some'.
1322some :: Monad m => Parser m a b -> Fold m b c -> Parser m a c
1323some p f = D.toParserK $ D.some (D.fromParserK p) f
1324-- some p f = manyP p (takeGE 1 f)
1325-- some = countBetween 1 maxBound
1327-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1328-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1329-- the input ends or the parser fails before @m@ results are collected.
1331-- >>> countBetween m n p f = Parser.manyP p (Parser.takeBetween m n f)
1335{-# INLINE countBetween #-}
1336countBetween :: -- Monad m =>
1337 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1338countBetween _m _n _p = undefined
1339-- countBetween m n p f = manyP p (takeBetween m n f)
1341-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1342-- the fold @f@. Fails if the input ends or the parser fails before @n@
1343-- results are collected.
1345-- >>> count n = Parser.countBetween n n
1346-- >>> count n p f = Parser.manyP p (Parser.takeEQ n f)
1351count :: -- Monad m =>
1352 Int -> Parser m a b -> Fold m b c -> Parser m a c
1353count n = countBetween n n
1354-- count n p f = manyP p (takeEQ n f)
1356-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1357-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1359-- We can implemnent parsers like the following using 'manyTillP':
1362-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1367{-# INLINE manyTillP #-}
1368manyTillP :: -- Monad m =>
1369 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1370manyTillP _p1 _p2 _f = undefined
1371 -- D.toParserK $ D.manyTillP (D.fromParserK p1) (D.fromParserK p2) f
1373-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1374-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1375-- tried again and so on. The parser stops when @test@ succeeds. The output of
1376-- @test@ is discarded and the output of @collect@ is accumulated by the
1377-- supplied fold. The parser fails if @collect@ fails.
1379-- Stops when the fold @f@ stops.
1383{-# INLINE manyTill #-}
1385 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1387 D.toParserK $ D.manyTill f (D.fromParserK p1) (D.fromParserK p2)
1389-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1390-- collects the output in the supplied fold. If the the parser @collect@ fails,
1391-- parser @recover@ is run until it stops and then we start repeating the
1392-- parser @collect@ again. The parser fails if the recovery parser fails.
1394-- For example, this can be used to find a key frame in a video stream after an
1399{-# INLINE manyThen #-}
1400manyThen :: -- (Foldable t, Monad m) =>
1401 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1402manyThen _parser _recover _f = undefined
1404-------------------------------------------------------------------------------
1406-------------------------------------------------------------------------------
1408-- To deinterleave we can chain two parsers one behind the other. The input is
1409-- given to the first parser and the input definitively rejected by the first
1410-- parser is given to the second parser.
1412-- We can either have the parsers themselves buffer the input or use the shared
1413-- global buffer to hold it until none of the parsers need it. When the first
1414-- parser returns Skip (i.e. rewind) we let the second parser consume the
1415-- rejected input and when it is done we move the cursor forward to the first
1416-- parser again. This will require a "move forward" command as well.
1418-- To implement grep we can use three parsers, one to find the pattern, one
1419-- to store the context behind the pattern and one to store the context in
1420-- front of the pattern. When a match occurs we need to emit the accumulator of
1421-- all the three parsers. One parser can count the line numbers to provide the
1424-- XXX rename this to intercalate
1425-- | Apply two parsers alternately to an input stream. The input stream is
1426-- considered an interleaving of two patterns. The two parsers represent the
1429-- This undoes a "gintercalate" of two streams.
1433{-# INLINE deintercalate #-}
1434deintercalate :: Monad m =>
1435 Fold m (Either x y) z
1439deintercalate sink contentL contentR =
1442 sink (D.fromParserK contentL) (D.fromParserK contentR)
1444-- | Parse items separated by a separator parsed by the supplied parser. At
1445-- least one item must be present for the parser to succeed.
1447-- Note that this can go in infinite loop if both the parsers fail on some
1448-- input. Detection of that would make the implementation more complex.
1450{-# INLINE sepBy1 #-}
1452 Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1453sepBy1 sink p sep = do
1455 f <- fromEffect $ FL.initialize sink
1456 f1 <- fromEffect $ FL.snoc f x
1459-- | Run the content parser first, when it is done, the separator parser is
1460-- run, when it is done content parser is run again and so on. If none of the
1461-- parsers consumes an input then parser returns a failure.
1463-- >>> sepBy sink = Parser.deintercalate (Fold.lefts sink)
1464-- >>> sepBy sink content sep = Parser.sepBy1 sink content sep <|> return mempty
1468 Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1469sepBy sink content sep =
1470 D.toParserK $ D.sepBy sink (D.fromParserK content) (D.fromParserK sep)
1471-- sepBy sink = deintercalate (FL.lefts sink)
1473-------------------------------------------------------------------------------
1474-- Interleaving a collection of parsers
1475-------------------------------------------------------------------------------
1477-- | Apply a collection of parsers to an input stream in a round robin fashion.
1478-- Each parser is applied until it stops and then we repeat starting with the
1479-- the first parser again.
1483{-# INLINE roundRobin #-}
1484roundRobin :: -- (Foldable t, Monad m) =>
1485 t (Parser m a b) -> Fold m b c -> Parser m a c
1486roundRobin _ps _f = undefined
1488-------------------------------------------------------------------------------
1489-- Repeated Alternatives
1490-------------------------------------------------------------------------------
1492-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1493-- fails the input consumed till now is dropped and the new instance is tried
1494-- on the fresh input.
1498{-# INLINE retryMaxTotal #-}
1499retryMaxTotal :: -- (Monad m) =>
1500 Int -> Parser m a b -> Fold m b c -> Parser m a c
1501retryMaxTotal _n _p _f = undefined
1503-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1507{-# INLINE retryMaxSuccessive #-}
1508retryMaxSuccessive :: -- (Monad m) =>
1509 Int -> Parser m a b -> Fold m b c -> Parser m a c
1510retryMaxSuccessive _n _p _f = undefined
1512-- | Keep trying a parser until it succeeds. When the parser fails the input
1513-- consumed till now is dropped and the new instance is tried on the fresh
1519retry :: -- (Monad m) =>
1520 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