2-- Module : Streamly.Internal.Data.Parser.ParserD
3-- Copyright : (c) 2020 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- Fast backtracking parsers with stream fusion and native streaming
12-- 'Applicative' and 'Control.Applicative.Alternative' type class based
13-- combinators from the
14-- <http://hackage.haskell.org/package/parser-combinators parser-combinators>
15-- package can also be used with the 'Parser' type. However, there are two
16-- important differences between @parser-combinators@ and the equivalent ones
17-- provided in this module in terms of performance:
19-- 1) @parser-combinators@ use plain Haskell lists to collect the results, in a
20-- strict Monad like IO, the results are necessarily buffered before they can
21-- be consumed. This may not perform optimally in streaming applications
22-- processing large amounts of data. Equivalent combinators in this module can
23-- consume the results of parsing using a 'Fold', thus providing a scalability
24-- and a composable consumer.
26-- 2) Several combinators in this module can be many times faster because of
27-- stream fusion. For example, 'Streamly.Internal.Data.Parser.many' combinator
28-- in this module is much faster than the 'Control.Applicative.many' combinator
29-- of 'Control.Applicative.Alternative' type class.
33-- Failing parsers in this module throw the 'D.ParseError' exception.
37-- As far as possible, try that the names of the combinators in this module are
40-- * <https://hackage.haskell.org/package/base/docs/Text-ParserCombinators-ReadP.html base/Text.ParserCombinators.ReadP>
41-- * <http://hackage.haskell.org/package/parser-combinators parser-combinators>
42-- * <http://hackage.haskell.org/package/megaparsec megaparsec>
43-- * <http://hackage.haskell.org/package/attoparsec attoparsec>
44-- * <http://hackage.haskell.org/package/parsec parsec>
46module Streamly.Internal.Data.Parser.ParserD
53 -- * Downgrade to Fold
56 -- First order parsers
77 -- All of these can be expressed in terms of either
88 -- * Sequence parsers (tokenizers)
90 -- | Parsers chained in series, if one parser terminates the composition
91 -- terminates. Currently we are using folds to collect the output of the
92 -- parsers but we can use Parsers instead of folds to make the composition
93 -- more powerful. For example, we can do:
95 -- takeEndByOrMax cond n p = takeEndBy cond (take n p)
96 -- takeEndByBetween cond m n p = takeEndBy cond (takeBetween m n p)
97 -- takeWhileBetween cond m n p = takeWhile cond (takeBetween m n p)
101 -- | Grab a sequence of input elements without inspecting them
103 -- , take -- takeBetween 0 n
104 , takeEQ -- takeBetween n n
105 , takeGE -- takeBetween n maxBound
106 -- , takeGE1 -- take1 -- takeBetween 1 n
109 -- Grab a sequence of input elements by inspecting them
122 -- ** Single Element Separators
123 -- | Separator could be in prefix postion ('takeStartBy'), or suffix
124 -- position ('takeEndBy').
126 -- These can be implemented modularly with refolds, using takeWhile and
140 , groupByRollingEither
146 , takeFramedByGeneric
152 -- , prefixOf -- match any prefix of a given string
153 -- , suffixOf -- match any suffix of a given string
154 -- , infixOf -- match any substring of a given string
161 -- Second order parsers (parsers using parsers)
162 -- * Binary Combinators
164 -- ** Sequential Applicative
169 -- ** Parallel Applicatives
173 -- , teeTill -- like manyTill but parallel
176 -- ** Sequential Interleaving
177 -- Use two folds, run a primary parser, its rejected values go to the
180 -- , deintercalatePrefix
181 -- , deintercalateSuffix
184 -- | TODO: traditional implmentations of these may be of limited use. For
185 -- example, consider parsing lines separated by @\\r\\n@. The main parser
186 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
187 -- can apply the "sep" parser.
189 -- We can instead implement these as special cases of deintercalate.
201 -- ** Sequential Alternative
205 -- ** Parallel Alternatives
211 -- * N-ary Combinators
212 -- ** Sequential Collection
216 -- ** Sequential Repetition
219 -- , countBetweenTill
230 -- A simple and stupid impl would be to just convert the stream to an array
231 -- and give the array reference to all consumers. The array can be grown on
232 -- demand by any consumer and truncated when nonbody needs it.
234 -- -- ** Distribute to collection
235 -- -- ** Distribute to repetition
237 -- ** Interleaved collection
244 -- -- ** Interleaved repetition
245 -- repeat one parser and when it fails run an error recovery parser
246 -- e.g. to find a key frame in the stream after an error
248 -- ** Collection of Alternatives
254 -- , fastestN -- first N successful in time
255 -- , choiceN -- first N successful in position
257 -- , choice -- first successful in position
259 -- ** Repeated Alternatives
279import Control.Monad (when)
280import Data.Bifunctor (first)
281import Fusion.Plugin.Types (Fuse(..))
282import Streamly.Internal.Data.Fold.Type (Fold(..))
283import Streamly.Internal.Data.SVar.Type (defState)
284import Streamly.Internal.Data.Either.Strict (Either'(..))
285import Streamly.Internal.Data.Maybe.Strict (Maybe'(..))
286import Streamly.Internal.Data.Tuple.Strict (Tuple'(..))
287import Streamly.Internal.Data.Stream.StreamD.Type (Stream)
289import qualified Data.Foldable as Foldable
290import qualified Streamly.Internal.Data.Fold.Type as FL
291import qualified Streamly.Internal.Data.Stream.StreamD.Type as D
292import qualified Streamly.Internal.Data.Stream.StreamD.Generate as D
295 (any, all, take, takeWhile, sequence, concatMap, maybe, either, span
296 , zip, filter, dropWhile)
297-- import Streamly.Internal.Data.Parser.ParserD.Tee
298import Streamly.Internal.Data.Parser.ParserD.Type
303-- >>> import Prelude hiding ()
304-- >>> import Control.Applicative
305-- >>> import Data.Char (isSpace)
306-- >>> import qualified Data.Foldable as Foldable
307-- >>> import qualified Data.Maybe as Maybe
308-- >>> import qualified Streamly.Data.Stream as Stream
309-- >>> import qualified Streamly.Internal.Data.Stream as Stream
310-- >>> import qualified Streamly.Internal.Data.Fold as Fold
311-- >>> import qualified Streamly.Internal.Data.Parser as Parser
313-------------------------------------------------------------------------------
314-- Downgrade a parser to a Fold
315-------------------------------------------------------------------------------
317-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
318-- parser fails or tries to backtrack.
320-- This can be useful in combinators that accept a Fold and we know that a
321-- Parser cannot fail or failure exception is acceptable as there is no way to
327toFold :: Monad m => Parser a m b -> Fold m a b
328toFold (Parser pstep pinitial pextract) = Fold step initial extract
335 IPartial s -> return $ FL.Partial s
336 IDone b -> return $ FL.Done b
338 error $ "toFold: parser throws error in initial" ++ err
340 perror n = error $ "toFold: parser backtracks in Partial: " ++ show n
341 cerror n = error $ "toFold: parser backtracks in Continue: " ++ show n
342 derror n = error $ "toFold: parser backtracks in Done: " ++ show n
343 eerror err = error $ "toFold: parser throws error: " ++ err
348 Partial 0 s -> return $ FL.Partial s
349 Continue 0 s -> return $ FL.Partial s
350 Done 0 b -> return $ FL.Done b
351 Partial n _ -> perror n
352 Continue n _ -> cerror n
354 Error err -> eerror err
360 Partial n _ -> perror n
361 Continue n _ -> cerror n
363 Error err -> eerror err
365-------------------------------------------------------------------------------
366-- Upgrade folds to parses
367-------------------------------------------------------------------------------
369-- | Make a 'Parser' from a 'Fold'.
371{-# INLINE fromFold #-}
372fromFold :: Monad m => Fold m a b -> Parser a m b
373fromFold (Fold fstep finitial fextract) = Parser step initial extract
381 FL.Partial s1 -> IPartial s1
388 FL.Partial s1 -> Partial 0 s1
389 FL.Done b -> Done 0 b
391 extract = fmap (Done 0) . fextract
393-- | Convert a Maybe returning fold to an error returning parser. The first
394-- argument is the error message that the parser would return when the fold
399{-# INLINE fromFoldMaybe #-}
400fromFoldMaybe :: Monad m => String -> Fold m a (Maybe b) -> Parser a m b
401fromFoldMaybe errMsg (Fold fstep finitial fextract) =
402 Parser step initial extract
410 FL.Partial s1 -> IPartial s1
414 Nothing -> IError errMsg
420 FL.Partial s1 -> Partial 0 s1
424 Nothing -> Error errMsg
429 Just x -> return $ Done 0 x
430 Nothing -> return $ Error errMsg
432-------------------------------------------------------------------------------
434-------------------------------------------------------------------------------
436-- | Peek the head element of a stream, without consuming it. Fails if it
437-- encounters end of input.
439-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
443-- peek = lookAhead (satisfy True)
447peek :: Monad m => Parser a m a
448peek = Parser step initial extract
452 initial = return $ IPartial ()
454 step () a = return $ Done 1 a
456 extract () = return $ Error "peek: end of input"
458-- | Succeeds if we are at the end of input, fails otherwise.
460-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
464eof :: Monad m => Parser a m ()
465eof = Parser step initial extract
469 initial = return $ IPartial ()
471 step () _ = return $ Error "eof: not at end of input"
473 extract () = return $ Done 0 ()
475-- | Return the next element of the input. Returns 'Nothing'
476-- on end of input. Also known as 'head'.
480{-# DEPRECATED next "Please use \"fromFold Fold.one\" instead" #-}
482next :: Monad m => Parser a m (Maybe a)
483next = Parser step initial extract
487 initial = pure $ IPartial ()
489 step () a = pure $ Done 0 (Just a)
491 extract () = pure $ Done 0 Nothing
493-- | Map an 'Either' returning function on the next element in the stream. If
494-- the function returns 'Left err', the parser fails with the error message
495-- @err@ otherwise returns the 'Right' value.
500either :: Monad m => (a -> Either String b) -> Parser a m b
501either f = Parser step initial extract
505 initial = return $ IPartial ()
510 Left err -> Error err
512 extract () = return $ Error "end of input"
514-- | Map a 'Maybe' returning function on the next element in the stream. The
515-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
518-- >>> toEither = Maybe.maybe (Left "maybe: predicate failed") Right
519-- >>> maybe f = Parser.either (toEither . f)
521-- >>> maybe f = Parser.fromFoldMaybe "maybe: predicate failed" (Fold.maybe f)
526maybe :: Monad m => (a -> Maybe b) -> Parser a m b
527-- maybe f = either (Maybe.maybe (Left "maybe: predicate failed") Right . f)
528maybe parserF = Parser step initial extract
532 initial = return $ IPartial ()
537 Nothing -> Error "maybe: predicate failed"
539 extract () = return $ Error "maybe: end of input"
541-- | Returns the next element if it passes the predicate, fails otherwise.
543-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
546-- >>> toMaybe f x = if f x then Just x else Nothing
547-- >>> satisfy f = Parser.maybe (toMaybe f)
549{-# INLINE satisfy #-}
550satisfy :: Monad m => (a -> Bool) -> Parser a m a
551-- satisfy predicate = maybe (\a -> if predicate a then Just a else Nothing)
552satisfy predicate = Parser step initial extract
556 initial = return $ IPartial ()
561 else Error "satisfy: predicate failed"
563 extract () = return $ Error "satisfy: end of input"
565-- | Consume one element from the head of the stream. Fails if it encounters
568-- >>> one = Parser.satisfy $ const True
571one :: Monad m => Parser a m a
572one = satisfy $ const True
574-- Alternate names: "only", "onlyThis".
576-- | Match a specific element.
578-- >>> oneEq x = Parser.satisfy (== x)
581oneEq :: (Monad m, Eq a) => a -> Parser a m a
582oneEq x = satisfy (== x)
584-- Alternate names: "exclude", "notThis".
586-- | Match anything other than the supplied element.
588-- >>> oneNotEq x = Parser.satisfy (/= x)
590{-# INLINE oneNotEq #-}
591oneNotEq :: (Monad m, Eq a) => a -> Parser a m a
592oneNotEq x = satisfy (/= x)
594-- | Match any one of the elements in the supplied list.
596-- >>> oneOf xs = Parser.satisfy (`Foldable.elem` xs)
598-- When performance matters a pattern matching predicate could be more
599-- efficient than a 'Foldable' datatype:
610-- GHC may use a binary search instead of linear search in the list.
611-- Alternatively, you can also use an array instead of list for storage and
615oneOf :: (Monad m, Eq a, Foldable f) => f a -> Parser a m a
616oneOf xs = satisfy (`Foldable.elem` xs)
618-- | See performance notes in 'oneOf'.
620-- >>> noneOf xs = Parser.satisfy (`Foldable.notElem` xs)
623noneOf :: (Monad m, Eq a, Foldable f) => f a -> Parser a m a
624noneOf xs = satisfy (`Foldable.notElem` xs)
626-------------------------------------------------------------------------------
628-------------------------------------------------------------------------------
630-- Required to fuse "take" with "many" in "chunksOf", for ghc-9.x
631{-# ANN type Tuple'Fused Fuse #-}
632data Tuple'Fused a b = Tuple'Fused !a !b deriving Show
634-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
635-- elements and folds them using the supplied fold.
637-- Stops after @n@ elements.
638-- Fails if the stream ends before @m@ elements could be taken.
644-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
645-- where prsr = Parser.takeBetween low high Fold.toList
650-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
653-- >>> takeBetween' 2 4 [1, 2]
656-- >>> takeBetween' 2 4 [1]
657-- Left (ParseError "takeBetween: Expecting alteast 2 elements, got 1")
659-- >>> takeBetween' 0 0 [1, 2]
662-- >>> takeBetween' 0 1 []
665-- @takeBetween@ is the most general take operation, other take operations can
666-- be defined in terms of takeBetween. For example:
668-- >>> take n = Parser.takeBetween 0 n
669-- >>> takeEQ n = Parser.takeBetween n n
670-- >>> takeGE n = Parser.takeBetween n maxBound
674{-# INLINE takeBetween #-}
675takeBetween :: Monad m => Int -> Int -> Fold m a b -> Parser a m b
676takeBetween low high (Fold fstep finitial fextract) =
678 Parser step initial (extract streamErr)
683 "takeBetween: Expecting alteast " ++ show low
684 ++ " elements, got " ++ show i
687 "takeBetween: lower bound - " ++ show low
688 ++ " is greater than higher bound - " ++ show high
690 foldErr :: Int -> String
692 "takeBetween: the collecting fold terminated after"
693 ++ " consuming" ++ show i ++ " elements"
694 ++ " minimum" ++ show low ++ " elements needed"
696 -- Exactly the same as snext except different constructors, we can possibly
697 -- deduplicate the two.
703 let s1 = Tuple'Fused i1 s
705 -- XXX ideally this should be a Continue instead
706 then return $ IPartial s1
707 else iextract foldErr s1
712 else IError (foldErr i1)
715 when (low >= 0 && high >= 0 && low > high)
718 finitial >>= inext (-1)
720 -- Keep the impl same as inext
726 let s1 = Tuple'Fused i1 s
728 then return $ Continue 0 s1
729 else extract foldErr s1
734 else Error (foldErr i1)
736 step (Tuple'Fused i s) a = fstep s a >>= snext i
738 extract f (Tuple'Fused i s)
739 | i >= low && i <= high = fmap (Done 0) (fextract s)
740 | otherwise = return $ Error (f i)
742 -- XXX Need to make Initial return type Step to deduplicate this
743 iextract f (Tuple'Fused i s)
744 | i >= low && i <= high = fmap IDone (fextract s)
745 | otherwise = return $ IError (f i)
747-- | Stops after taking exactly @n@ input elements.
749-- * Stops - after consuming @n@ elements.
750-- * Fails - if the stream or the collecting fold ends before it can collect
751-- exactly @n@ elements.
753-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
754-- Left (ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3")
757takeEQ :: Monad m => Int -> Fold m a b -> Parser a m b
758takeEQ n (Fold fstep finitial fextract) = Parser step initial extract
767 FL.Partial s -> IPartial $ Tuple' 0 s
772 $ "takeEQ: Expecting exactly " ++ show cnt
773 ++ " elements, fold terminated without"
774 ++ " consuming any elements"
781 FL.Partial s -> Continue 0 $ Tuple' i1 s
784 $ "takeEQ: Expecting exactly " ++ show cnt
785 ++ " elements, fold terminated on " ++ show i1
790 FL.Partial s -> fextract s
791 FL.Done b -> return b
792 -- XXX we should not reach here when initial returns Step type
793 -- reachable only when n == 0
794 | otherwise = Done 1 <$> fextract r
801 | i == 0 && cnt == 0 = fmap (Done 0) $ fextract r
805 $ "takeEQ: Expecting exactly " ++ show cnt
806 ++ " elements, input terminated on " ++ show i
808-- | Take at least @n@ input elements, but can collect more.
810-- * Stops - when the collecting fold stops.
811-- * Fails - if the stream or the collecting fold ends before producing @n@
814-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
815-- Left (ParseError "takeGE: Expecting at least 4 elements, input terminated on 3")
817-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
823takeGE :: Monad m => Int -> Fold m a b -> Parser a m b
824takeGE n (Fold fstep finitial fextract) = Parser step initial extract
833 FL.Partial s -> IPartial $ Tuple' 0 s
838 $ "takeGE: Expecting at least " ++ show cnt
839 ++ " elements, fold terminated without"
840 ++ " consuming any elements"
847 FL.Partial s -> Continue 0 $ Tuple' i1 s
850 $ "takeGE: Expecting at least " ++ show cnt
851 ++ " elements, fold terminated on " ++ show i1
856 FL.Partial s -> Partial 0 $ Tuple' i1 s
857 FL.Done b -> Done 0 b
864 | i >= cnt = fmap (Done 0) $ fextract r
868 $ "takeGE: Expecting at least " ++ show cnt
869 ++ " elements, input terminated on " ++ show i
871-------------------------------------------------------------------------------
872-- Conditional splitting
873-------------------------------------------------------------------------------
875-- XXX We should perhaps use only takeWhileP and rename it to takeWhile.
877-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
878-- input. The combinator stops when the condition fails or if the collecting
881-- Other interesting parsers can be implemented in terms of this parser:
883-- >>> takeWhile1 cond p = Parser.takeWhileP cond (Parser.takeBetween 1 maxBound p)
884-- >>> takeWhileBetween cond m n p = Parser.takeWhileP cond (Parser.takeBetween m n p)
886-- Stops: when the condition fails or the collecting parser stops.
887-- Fails: when the collecting parser fails.
891{-# INLINE takeWhileP #-}
892takeWhileP :: Monad m => (a -> Bool) -> Parser a m b -> Parser a m b
893takeWhileP predicate (Parser pstep pinitial pextract) =
894 Parser step pinitial pextract
903 -- XXX need a map on count
905 Error err -> return $ Error err
906 Done n s1 -> return $ Done (n + 1) s1
907 Partial _ _ -> error "Bug: takeWhileP: Partial in extract"
908 Continue n s1 -> return $ Continue (n + 1) s1
910-- | Collect stream elements until an element fails the predicate. The element
911-- on which the predicate fails is returned back to the input stream.
913-- * Stops - when the predicate fails or the collecting fold stops.
916-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
919-- >>> takeWhile cond f = Parser.takeWhileP cond (Parser.fromFold f)
921-- We can implement a @breakOn@ using 'takeWhile':
924-- breakOn p = takeWhile (not p)
927{-# INLINE takeWhile #-}
928takeWhile :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b
929-- takeWhile cond f = takeWhileP cond (fromFold f)
930takeWhile predicate (Fold fstep finitial fextract) =
931 Parser step initial extract
938 FL.Partial s -> IPartial s
947 FL.Partial s1 -> Partial 0 s1
948 FL.Done b -> Done 0 b
949 else Done 1 <$> fextract s
951 extract s = fmap (Done 0) (fextract s)
954-- XXX This may not be composable because of the b argument. We can instead
955-- return a "Reparse b a m b" so that those can be composed.
956{-# INLINE takeWhile1X #-}
957takeWhile1 :: Monad m => b -> (a -> Bool) -> Refold m b a b -> Parser a m b
958-- We can implement this using satisfy and takeWhile. We can use "satisfy
959-- p", fold the result with the refold and then use the "takeWhile p" and
960-- fold that using the refold.
961takeWhile1 acc cond f = undefined
964-- | Like 'takeWhile' but takes at least one element otherwise fails.
966-- >>> takeWhile1 cond p = Parser.takeWhileP cond (Parser.takeBetween 1 maxBound p)
968{-# INLINE takeWhile1 #-}
969takeWhile1 :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b
970-- takeWhile1 cond f = takeWhileP cond (takeBetween 1 maxBound f)
971takeWhile1 predicate (Fold fstep finitial fextract) =
972 Parser step initial extract
979 FL.Partial s -> IPartial (Left' s)
982 $ "takeWhile1: fold terminated without consuming:"
985 {-# INLINE process #-}
990 FL.Partial s1 -> Partial 0 (Right' s1)
991 FL.Done b -> Done 0 b
996 else return $ Error "takeWhile1: predicate failed on first element"
1004 extract (Left' _) = return $ Error "takeWhile1: end of input"
1005 extract (Right' s) = fmap (Done 0) (fextract s)
1007-- | Drain the input as long as the predicate succeeds, running the effects and
1008-- discarding the results.
1010-- This is also called @skipWhile@ in some parsing libraries.
1012-- >>> dropWhile p = Parser.takeWhile p Fold.drain
1014{-# INLINE dropWhile #-}
1015dropWhile :: Monad m => (a -> Bool) -> Parser a m ()
1016dropWhile p = takeWhile p FL.drain
1018-------------------------------------------------------------------------------
1020-------------------------------------------------------------------------------
1022data FramedEscState s =
1023 FrameEscInit !s | FrameEscGo !s !Int | FrameEscEsc !s !Int
1025-- XXX We can remove Maybe from esc
1026{-# INLINE takeFramedByGeneric #-}
1027takeFramedByGeneric :: Monad m =>
1029 -> Maybe (a -> Bool)
1030 -> Maybe (a -> Bool)
1033takeFramedByGeneric esc begin end (Fold fstep finitial fextract) =
1035 Parser step initial extract
1043 FL.Partial s -> IPartial (FrameEscInit s)
1045 error "takeFramedByGeneric: fold done without input"
1047 {-# INLINE process #-}
1052 FL.Partial s1 -> Continue 0 (FrameEscGo s1 n)
1053 FL.Done b -> Done 0 b
1055 {-# INLINE processNoEsc #-}
1056 processNoEsc s a n =
1061 -- takeFramedBy case
1065 then Done 0 <$> fextract s
1066 else process s a (n - 1)
1068 let n1 = if isBegin a then n + 1 else n
1070 Nothing -> -- takeEndBy case
1072 then Done 0 <$> fextract s
1074 Nothing -> -- takeStartBy case
1078 then Done 0 <$> fextract s
1081 error $ "takeFramedByGeneric: "
1082 ++ "Both begin and end frame predicate missing"
1084 {-# INLINE processCheckEsc #-}
1085 processCheckEsc s a n =
1089 then return $ Partial 0 $ FrameEscEsc s n
1090 else processNoEsc s a n
1091 Nothing -> processNoEsc s a n
1093 step (FrameEscInit s) a =
1097 then return $ Partial 0 (FrameEscGo s 0)
1098 else return $ Error "takeFramedByGeneric: missing frame start"
1103 then Done 0 <$> fextract s
1104 else processCheckEsc s a 0
1106 error "Both begin and end frame predicate missing"
1107 step (FrameEscGo s n) a = processCheckEsc s a n
1108 step (FrameEscEsc s n) a = process s a n
1110 err = return . Error
1112 extract (FrameEscInit _) =
1113 err "takeFramedByGeneric: empty token"
1114 extract (FrameEscGo s _) =
1118 Nothing -> fmap (Done 0) $ fextract s
1119 Just _ -> err "takeFramedByGeneric: missing frame end"
1120 Nothing -> err "takeFramedByGeneric: missing closing frame"
1121 extract (FrameEscEsc _ _) = err "takeFramedByGeneric: trailing escape"
1123-- | @takeEndBy cond parser@ parses a token that ends by a separator chosen by
1124-- the supplied predicate. The separator is also taken with the token.
1126-- This can be combined with other parsers to implement other interesting
1127-- parsers as follows:
1129-- >>> takeEndByLE cond n p = Parser.takeEndBy cond (Parser.fromFold $ Fold.take n p)
1130-- >>> takeEndByBetween cond m n p = Parser.takeEndBy cond (Parser.takeBetween m n p)
1132-- >>> takeEndBy = Parser.takeEndByEsc (const False)
1134-- See also "Streamly.Data.Fold.takeEndBy". Unlike the fold, the collecting
1135-- parser in the takeEndBy parser can decide whether to fail or not if the
1136-- stream does not end with separator.
1140{-# INLINE takeEndBy #-}
1141takeEndBy :: Monad m => (a -> Bool) -> Parser a m b -> Parser a m b
1142-- takeEndBy = takeEndByEsc (const False)
1143takeEndBy cond (Parser pstep pinitial pextract) =
1145 Parser step initial pextract
1155 else extractStep pextract res
1157-- | Like 'takeEndBy' but the separator elements can be escaped using an
1158-- escape char determined by the first predicate. The escape characters are
1162{-# INLINE takeEndByEsc #-}
1163takeEndByEsc :: Monad m =>
1164 (a -> Bool) -> (a -> Bool) -> Parser a m b -> Parser a m b
1165takeEndByEsc isEsc isSep (Parser pstep pinitial pextract) =
1167 Parser step initial extract
1171 initial = first Left' <$> pinitial
1173 step (Left' s) a = do
1175 then return $ Partial 0 $ Right' s
1179 then return $ first Left' res
1180 else fmap (first Left') $ extractStep pextract res
1182 step (Right' s) a = do
1184 return $ first Left' res
1186 extract (Left' s) = fmap (first Left') $ pextract s
1187 extract (Right' _) =
1188 return $ Error "takeEndByEsc: trailing escape"
1190-- | Like 'takeEndBy' but the separator is dropped.
1192-- See also "Streamly.Data.Fold.takeEndBy_".
1196{-# INLINE takeEndBy_ #-}
1197takeEndBy_ :: (a -> Bool) -> Parser a m b -> Parser a m b
1200 takeFramedByGeneric Nothing Nothing (Just isEnd) (toFold p)
1202takeEndBy_ cond (Parser pstep pinitial pextract) =
1204 Parser step pinitial pextract
1213-- | Take either the separator or the token. Separator is a Left value and
1214-- token is Right value.
1217{-# INLINE takeEitherSepBy #-}
1218takeEitherSepBy :: -- Monad m =>
1219 (a -> Bool) -> Fold m (Either a b) c -> Parser a m c
1220takeEitherSepBy _cond = undefined -- D.toParserK . D.takeEitherSepBy cond
1222-- | Parse a token that starts with an element chosen by the predicate. The
1223-- parser fails if the input does not start with the selected element.
1225-- * Stops - when the predicate succeeds in non-leading position.
1226-- * Fails - when the predicate fails in the leading position.
1228-- >>> splitWithPrefix p f = Stream.parseMany (Parser.takeStartBy p f)
1232-- >>> p = Parser.takeStartBy (== ',') Fold.toList
1233-- >>> leadingComma = Stream.parse p . Stream.fromList
1234-- >>> leadingComma "a,b"
1235-- Left (ParseError "takeStartBy: missing frame start")
1237-- >>> leadingComma ",,"
1239-- >>> leadingComma ",a,b"
1241-- >>> leadingComma ""
1246{-# INLINE takeStartBy #-}
1247takeStartBy :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b
1248takeStartBy cond (Fold fstep finitial fextract) =
1250 Parser step initial extract
1258 FL.Partial s -> IPartial (Left' s)
1259 FL.Done _ -> IError "takeStartBy: fold done without input"
1261 {-# INLINE process #-}
1266 FL.Partial s1 -> Partial 0 (Right' s1)
1267 FL.Done b -> Done 0 b
1272 else return $ Error "takeStartBy: missing frame start"
1276 else Done 1 <$> fextract s
1278 extract (Left' s) = fmap (Done 0) $ fextract s
1279 extract (Right' s) = fmap (Done 0) $ fextract s
1281-- | Like 'takeStartBy' but drops the separator.
1283-- >>> takeStartBy_ isBegin = Parser.takeFramedByGeneric Nothing (Just isBegin) Nothing
1285{-# INLINE takeStartBy_ #-}
1286takeStartBy_ :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b
1287takeStartBy_ isBegin = takeFramedByGeneric Nothing (Just isBegin) Nothing
1289-- | @takeFramedByEsc_ isEsc isBegin isEnd fold@ parses a token framed using a
1290-- begin and end predicate, and an escape character. The frame begin and end
1291-- characters lose their special meaning if preceded by the escape character.
1293-- Nested frames are allowed if begin and end markers are different, nested
1294-- frames must be balanced unless escaped, nested frame markers are emitted as
1299-- >>> p = Parser.takeFramedByEsc_ (== '\\') (== '{') (== '}') Fold.toList
1300-- >>> Stream.parse p $ Stream.fromList "{hello}"
1302-- >>> Stream.parse p $ Stream.fromList "{hello {world}}"
1303-- Right "hello {world}"
1304-- >>> Stream.parse p $ Stream.fromList "{hello \\{world}"
1305-- Right "hello {world"
1306-- >>> Stream.parse p $ Stream.fromList "{hello {world}"
1307-- Left (ParseError "takeFramedByEsc_: missing frame end")
1310{-# INLINE takeFramedByEsc_ #-}
1311takeFramedByEsc_ :: Monad m =>
1312 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser a m b
1313-- takeFramedByEsc_ isEsc isEnd p =
1314-- takeFramedByGeneric (Just isEsc) Nothing (Just isEnd) (toFold p)
1315takeFramedByEsc_ isEsc isBegin isEnd (Fold fstep finitial fextract) =
1317 Parser step initial extract
1325 FL.Partial s -> IPartial (FrameEscInit s)
1327 error "takeFramedByEsc_: fold done without input"
1329 {-# INLINE process #-}
1334 FL.Partial s1 -> Continue 0 (FrameEscGo s1 n)
1335 FL.Done b -> Done 0 b
1337 step (FrameEscInit s) a =
1339 then return $ Partial 0 (FrameEscGo s 0)
1340 else return $ Error "takeFramedByEsc_: missing frame start"
1341 step (FrameEscGo s n) a =
1343 then return $ Partial 0 $ FrameEscEsc s n
1347 let n1 = if isBegin a then n + 1 else n
1351 then Done 0 <$> fextract s
1352 else process s a (n - 1)
1353 step (FrameEscEsc s n) a = process s a n
1355 err = return . Error
1357 extract (FrameEscInit _) = err "takeFramedByEsc_: empty token"
1358 extract (FrameEscGo _ _) = err "takeFramedByEsc_: missing frame end"
1359 extract (FrameEscEsc _ _) = err "takeFramedByEsc_: trailing escape"
1361data FramedState s = FrameInit !s | FrameGo !s Int
1363-- | @takeFramedBy_ isBegin isEnd fold@ parses a token framed by a begin and an
1366-- >>> takeFramedBy_ = Parser.takeFramedByEsc_ (const False)
1368{-# INLINE takeFramedBy_ #-}
1369takeFramedBy_ :: Monad m =>
1370 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser a m b
1371-- takeFramedBy_ isBegin isEnd =
1372-- takeFramedByGeneric (Just (const False)) (Just isBegin) (Just isEnd)
1373takeFramedBy_ isBegin isEnd (Fold fstep finitial fextract) =
1375 Parser step initial extract
1383 FL.Partial s -> IPartial (FrameInit s)
1385 error "takeFramedBy_: fold done without input"
1387 {-# INLINE process #-}
1392 FL.Partial s1 -> Continue 0 (FrameGo s1 n)
1393 FL.Done b -> Done 0 b
1395 step (FrameInit s) a =
1397 then return $ Continue 0 (FrameGo s 0)
1398 else return $ Error "takeFramedBy_: missing frame start"
1399 step (FrameGo s n) a
1401 let n1 = if isBegin a then n + 1 else n
1403 | n == 0 = Done 0 <$> fextract s
1404 | otherwise = process s a (n - 1)
1406 err = return . Error
1408 extract (FrameInit _) = err "takeFramedBy_: empty token"
1409 extract (FrameGo _ _) = err "takeFramedBy_: missing frame end"
1411-------------------------------------------------------------------------------
1412-- Grouping and words
1413-------------------------------------------------------------------------------
1415data WordByState s b = WBLeft !s | WBWord !s | WBRight !b
1417-- Note we can also get words using something like:
1418-- sepBy FL.toList (takeWhile (not . p) Fold.toList) (dropWhile p)
1420-- But that won't be as efficient and ergonomic.
1422-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
1423-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
1424-- @["a","b"]@. In other words, its like parsing words from whitespace
1427-- * Stops - when it finds a word separator after a non-word element
1430-- >>> wordBy = Parser.wordFramedBy (const False) (const False) (const False)
1433-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
1436{-# INLINE wordBy #-}
1437wordBy :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b
1438wordBy predicate (Fold fstep finitial fextract) = Parser step initial extract
1442 {-# INLINE worder #-}
1447 FL.Partial s1 -> Partial 0 $ WBWord s1
1448 FL.Done b -> Done 0 b
1454 FL.Partial s -> IPartial $ WBLeft s
1455 FL.Done b -> IDone b
1458 if not (predicate a)
1460 else return $ Partial 0 $ WBLeft s
1462 if not (predicate a)
1466 return $ Partial 0 $ WBRight b
1467 step (WBRight b) a =
1469 $ if not (predicate a)
1471 else Partial 0 $ WBRight b
1473 extract (WBLeft s) = fmap (Done 0) $ fextract s
1474 extract (WBWord s) = fmap (Done 0) $ fextract s
1475 extract (WBRight b) = return (Done 0 b)
1477data WordFramedState s b =
1478 WordFramedSkipPre !s
1479 | WordFramedWord !s !Int
1480 | WordFramedEsc !s !Int
1481 | WordFramedSkipPost !b
1483-- | Like 'wordBy' but treats anything inside a pair of quotes as a single
1484-- word, the quotes can be escaped by an escape character. Recursive quotes
1485-- are possible if quote begin and end characters are different, quotes must be
1486-- balanced. Outermost quotes are stripped.
1488-- >>> braces = Parser.wordFramedBy (== '\\') (== '{') (== '}') isSpace Fold.toList
1489-- >>> Stream.parse braces $ Stream.fromList "{ab} cd"
1491-- >>> Stream.parse braces $ Stream.fromList "{ab}{cd}"
1493-- >>> Stream.parse braces $ Stream.fromList "a{b} cd"
1495-- >>> Stream.parse braces $ Stream.fromList "a{{b}} cd"
1498-- >>> quotes = Parser.wordFramedBy (== '\\') (== '"') (== '"') isSpace Fold.toList
1499-- >>> Stream.parse quotes $ Stream.fromList "\"a\"\"b\""
1502{-# INLINE wordFramedBy #-}
1503wordFramedBy :: Monad m =>
1504 (a -> Bool) -- ^ Matches escape elem?
1505 -> (a -> Bool) -- ^ Matches left quote?
1506 -> (a -> Bool) -- ^ matches right quote?
1507 -> (a -> Bool) -- ^ matches word separator?
1510wordFramedBy isEsc isBegin isEnd isSep
1511 (Fold fstep finitial fextract) =
1512 Parser step initial extract
1520 FL.Partial s -> IPartial (WordFramedSkipPre s)
1522 error "wordFramedBy: fold done without input"
1524 {-# INLINE process #-}
1529 FL.Partial s1 -> Continue 0 (WordFramedWord s1 n)
1530 FL.Done b -> Done 0 b
1532 step (WordFramedSkipPre s) a
1533 | isEsc a = return $ Continue 0 $ WordFramedEsc s 0
1534 | isSep a = return $ Partial 0 $ WordFramedSkipPre s
1535 | isBegin a = return $ Continue 0 $ WordFramedWord s 1
1537 return $ Error "wordFramedBy: missing frame start"
1538 | otherwise = process s a 0
1539 step (WordFramedWord s n) a
1540 | isEsc a = return $ Continue 0 $ WordFramedEsc s n
1541 | n == 0 && isSep a = do
1543 return $ Partial 0 $ WordFramedSkipPost b
1545 -- We need to use different order for checking begin and end for
1546 -- the n == 0 and n == 1 case so that when the begin and end
1547 -- character is the same we treat the one after begin as end.
1550 -- Need to check isBegin first
1552 then return $ Continue 0 $ WordFramedWord s 1
1554 then return $ Error "wordFramedBy: missing frame start"
1557 -- Need to check isEnd first
1561 then return $ Continue 0 $ WordFramedWord s 0
1562 else process s a (n - 1)
1564 then process s a (n + 1)
1566 step (WordFramedEsc s n) a = process s a n
1567 step (WordFramedSkipPost b) a =
1571 else Partial 0 $ WordFramedSkipPost b
1573 err = return . Error
1575 extract (WordFramedSkipPre s) = fmap (Done 0) $ fextract s
1576 extract (WordFramedWord s n) =
1578 then fmap (Done 0) $ fextract s
1579 else err "wordFramedBy: missing frame end"
1580 extract (WordFramedEsc _ _) =
1581 err "wordFramedBy: trailing escape"
1582 extract (WordFramedSkipPost b) = return (Done 0 b)
1584data WordQuotedState s b a =
1585 WordQuotedSkipPre !s
1586 | WordUnquotedWord !s
1587 | WordQuotedWord !s !Int !a !a
1588 | WordUnquotedEsc !s
1589 | WordQuotedEsc !s !Int !a !a
1590 | WordQuotedSkipPost !b
1592-- XXX If quote start and end chars are different then quotes can be nested
1593-- without escaping. However, is there a case for the use of nested quotes?
1595-- XXX Simplify like blockWithQuotes
1597-- | Like 'wordBy' but word separators within quotes are ignored. Quote
1598-- character can be used within quotes if escaped using the supplied escape
1599-- char. A different quoting character can be used inside quotes without
1600-- escaping. Starting quote determines the ending quote.
1608-- >>> '\'' -> Just x
1612-- >>> rq = (`elem` ['"', '\''])
1613-- >>> p keep = Parser.wordWithQuotes keep (== '\\') lq rq isSpace Fold.toList
1615-- >>> Stream.parse (p False) $ Stream.fromList "a\"b'c\";'d\"e'f ghi"
1616-- Right "ab'c;d\"ef"
1618-- Outer quotes and backslashes from the input string are removed by Haskell,
1619-- therefore, the actual input string looks like:
1621-- From this the outer quotes are stripped by the parser, double quotes inside
1622-- single quotes or vice-versa are kept.
1624-- >>> Stream.parse (p True) $ Stream.fromList "a\"b'c\";'d\"e'f ghi"
1625-- Right "a\"b'c\";'d\"e'f"
1627{-# INLINE wordWithQuotes #-}
1628wordWithQuotes :: (Monad m, Eq a) =>
1629 Bool -- ^ keep the quotes in the output
1630 -> (a -> Bool) -- ^ Matches an escape elem?
1631 -> (a -> Maybe a) -- ^ If left quote, return right quote, else nothing.
1632 -> (a -> Bool) -- ^ Matches a right quote?
1633 -> (a -> Bool) -- ^ Matches a word separator?
1636wordWithQuotes keepQuotes isEsc toRight isEnd isSep
1637 (Fold fstep finitial fextract) =
1638 Parser step initial extract
1646 FL.Partial s -> IPartial (WordQuotedSkipPre s)
1648 error "wordWithQuotes: fold done without input"
1650 {-# INLINE process #-}
1651 process s a n ql qr = do
1655 FL.Partial s1 -> Continue 0 (WordQuotedWord s1 n ql qr)
1656 FL.Done b -> Done 0 b
1658 {-# INLINE processUnquoted #-}
1659 processUnquoted s a = do
1663 FL.Partial s1 -> Continue 0 (WordUnquotedWord s1)
1664 FL.Done b -> Done 0 b
1666 step (WordQuotedSkipPre s) a
1667 | isEsc a = return $ Continue 0 $ WordUnquotedEsc s
1668 | isSep a = return $ Partial 0 $ WordQuotedSkipPre s
1673 then process s a 1 a qr
1674 else return $ Continue 0 $ WordQuotedWord s 1 a qr
1677 return $ Error "wordWithQuotes: missing frame start"
1678 | otherwise -> processUnquoted s a
1679 step (WordUnquotedWord s) a
1680 | isEsc a = return $ Continue 0 $ WordUnquotedEsc s
1683 return $ Partial 0 $ WordQuotedSkipPost b
1688 then process s a 1 a qr
1689 else return $ Continue 0 $ WordQuotedWord s 1 a qr
1692 then return $ Error "wordWithQuotes: missing frame start"
1693 else processUnquoted s a
1694 step (WordQuotedWord s n ql qr) a
1695 | isEsc a = return $ Continue 0 $ WordQuotedEsc s n ql qr
1696 -- XXX Will this ever occur? Will n ever be 0?
1697 | n == 0 && isSep a = do
1699 return $ Partial 0 $ WordQuotedSkipPost b
1705 then processUnquoted s a
1706 else return $ Continue 0 $ WordUnquotedWord s
1707 else process s a (n - 1) ql qr
1709 then process s a (n + 1) ql qr
1710 else process s a n ql qr
1711 step (WordUnquotedEsc s) a = processUnquoted s a
1712 step (WordQuotedEsc s n ql qr) a = process s a n ql qr
1713 step (WordQuotedSkipPost b) a =
1717 else Partial 0 $ WordQuotedSkipPost b
1719 err = return . Error
1721 extract (WordQuotedSkipPre s) = fmap (Done 0) $ fextract s
1722 extract (WordUnquotedWord s) = fmap (Done 0) $ fextract s
1723 extract (WordQuotedWord s n _ _) =
1725 then fmap (Done 0) $ fextract s
1726 else err "wordWithQuotes: missing frame end"
1727 extract WordQuotedEsc {} =
1728 err "wordWithQuotes: trailing escape"
1729 extract (WordUnquotedEsc _) =
1730 err "wordWithQuotes: trailing escape"
1731 extract (WordQuotedSkipPost b) = return (Done 0 b)
1733data BlockParseState s =
1735 | BlockUnquoted !Int !s
1736 | BlockQuoted !Int !s
1737 | BlockQuotedEsc !Int !s
1739-- Blocks can be of different types e.g. {} or (). We only parse from the
1740-- perspective of the outermost block type. The nesting of that block are
1741-- checked. Any other block types nested inside it are opaque to us and can be
1742-- parsed when the contents of the block are parsed.
1744-- XXX Put a limit on nest level to keep the API safe.
1746-- | Parse a block enclosed within open, close brackets. Block contents may be
1747-- quoted, brackets inside quotes are ignored. Quoting characters can be used
1748-- within quotes if escaped. A block can have a nested block inside it.
1750-- Quote begin and end chars are the same. Block brackets and quote chars must
1751-- not overlap. Block start and end brackets must be different for nesting
1752-- blocks within blocks.
1754-- >>> p = Parser.blockWithQuotes '{' '}' '"' '\\' Fold.toList
1755-- >>> Stream.parse p $ Stream.fromList "{msg: \"hello world\"}"
1756-- Right "msg: \"hello world\""
1758{-# INLINE blockWithQuotes #-}
1759blockWithQuotes :: (Monad m, Eq a) =>
1760 a -- ^ Block opening bracket
1761 -> a -- ^ Block closing bracket
1762 -> a -- ^ quote char
1763 -> a -- ^ escape char
1766blockWithQuotes bopen bclose quote esc
1767 (Fold fstep finitial fextract) =
1768 Parser step initial extract
1776 FL.Partial s -> IPartial (BlockInit s)
1778 error "blockWithQuotes: fold finished without input"
1780 {-# INLINE process #-}
1781 process s a nextState = do
1785 FL.Partial s1 -> Continue 0 (nextState s1)
1786 FL.Done b -> Done 0 b
1788 step (BlockInit s) a =
1791 then Continue 0 $ BlockUnquoted 1 s
1792 else Error "blockWithQuotes: missing block start"
1793 step (BlockUnquoted level s) a =
1795 then process s a (BlockUnquoted (level + 1))
1800 then fmap (Done 0) (fextract s)
1801 else process s a (BlockUnquoted (level - 1))
1804 then process s a (BlockQuoted level)
1805 else process s a (BlockUnquoted level)
1806 step (BlockQuoted level s) a
1807 | a == esc = process s a (BlockQuotedEsc level)
1810 then process s a (BlockUnquoted level)
1811 else process s a (BlockQuoted level)
1812 step (BlockQuotedEsc level s) a = process s a (BlockQuoted level)
1814 err = return . Error
1816 extract (BlockInit s) = fmap (Done 0) $ fextract s
1817 extract (BlockUnquoted level _) =
1818 err $ "blockWithQuotes: finished at block nest level " ++ show level
1819 extract (BlockQuoted level _) =
1820 err $ "blockWithQuotes: finished, inside an unfinished quote, "
1821 ++ "at block nest level " ++ show level
1822 extract (BlockQuotedEsc level _) =
1823 err $ "blockWithQuotes: finished, inside an unfinished quote, "
1824 ++ "after an escape char, at block nest level " ++ show level
1826{-# ANN type GroupByState Fuse #-}
1827data GroupByState a s
1829 | GroupByGrouping !a !s
1831-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
1832-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
1833-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
1834-- then @c@ is also assigned to the same group and so on. When the comparison
1835-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
1836-- the result of the fold is the result of the parser.
1838-- * Stops - when the comparison fails.
1843-- Stream.fold Fold.toList
1844-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
1848-- >>> runGroupsBy (<) []
1851-- >>> runGroupsBy (<) [1]
1854-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
1855-- [Right [3,5,4],Right [1,2],Right [0]]
1857{-# INLINE groupBy #-}
1858groupBy :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser a m b
1859groupBy eq (Fold fstep finitial fextract) = Parser step initial extract
1863 {-# INLINE grouper #-}
1868 FL.Done b -> Done 0 b
1869 FL.Partial s1 -> Partial 0 (GroupByGrouping a0 s1)
1875 FL.Partial s -> IPartial $ GroupByInit s
1876 FL.Done b -> IDone b
1878 step (GroupByInit s) a = grouper s a a
1879 step (GroupByGrouping a0 s) a =
1882 else Done 1 <$> fextract s
1884 extract (GroupByInit s) = fmap (Done 0) $ fextract s
1885 extract (GroupByGrouping _ s) = fmap (Done 0) $ fextract s
1887-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
1888-- successive elements in the input stream. Assuming the input stream
1889-- is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
1890-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
1891-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
1892-- then @c@ is also assigned to the same group and so on. When the comparison
1893-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
1894-- the result of the fold is the result of the parser.
1896-- * Stops - when the comparison fails.
1900-- runGroupsByRolling eq =
1901-- Stream.fold Fold.toList
1902-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
1906-- >>> runGroupsByRolling (<) []
1909-- >>> runGroupsByRolling (<) [1]
1912-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
1913-- [Right [3,5],Right [4],Right [1,2],Right [0]]
1917{-# INLINE groupByRolling #-}
1918groupByRolling :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser a m b
1919groupByRolling eq (Fold fstep finitial fextract) = Parser step initial extract
1923 {-# INLINE grouper #-}
1928 FL.Done b -> Done 0 b
1929 FL.Partial s1 -> Partial 0 (GroupByGrouping a s1)
1935 FL.Partial s -> IPartial $ GroupByInit s
1936 FL.Done b -> IDone b
1938 step (GroupByInit s) a = grouper s a
1939 step (GroupByGrouping a0 s) a =
1942 else Done 1 <$> fextract s
1944 extract (GroupByInit s) = fmap (Done 0) $ fextract s
1945 extract (GroupByGrouping _ s) = fmap (Done 0) $ fextract s
1947{-# ANN type GroupByStatePair Fuse #-}
1948data GroupByStatePair a s1 s2
1949 = GroupByInitPair !s1 !s2
1950 | GroupByGroupingPair !a !s1 !s2
1951 | GroupByGroupingPairL !a !s1 !s2
1952 | GroupByGroupingPairR !a !s1 !s2
1954-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
1955-- the first fold as long as the predicate holds 'True', if the predicate is
1956-- 'False' collects using the second fold as long as it remains 'False'.
1957-- Returns 'Left' for the first case and 'Right' for the second case.
1959-- For example, if we want to detect sorted sequences in a stream, both
1960-- ascending and descending cases we can use 'groupByRollingEither (<=)
1961-- Fold.toList Fold.toList'.
1964{-# INLINE groupByRollingEither #-}
1965groupByRollingEither :: Monad m =>
1966 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser a m (Either b c)
1969 (Fold fstep1 finitial1 fextract1)
1970 (Fold fstep2 finitial2 fextract2) = Parser step initial extract
1974 {-# INLINE grouper #-}
1975 grouper s1 s2 a = do
1976 return $ Continue 0 (GroupByGroupingPair a s1 s2)
1978 {-# INLINE grouperL2 #-}
1979 grouperL2 s1 s2 a = do
1983 FL.Done b -> Done 0 (Left b)
1984 FL.Partial s11 -> Partial 0 (GroupByGroupingPairL a s11 s2)
1986 {-# INLINE grouperL #-}
1987 grouperL s1 s2 a0 a = do
1990 FL.Done b -> return $ Done 0 (Left b)
1991 FL.Partial s11 -> grouperL2 s11 s2 a
1993 {-# INLINE grouperR2 #-}
1994 grouperR2 s1 s2 a = do
1998 FL.Done b -> Done 0 (Right b)
1999 FL.Partial s21 -> Partial 0 (GroupByGroupingPairR a s1 s21)
2001 {-# INLINE grouperR #-}
2002 grouperR s1 s2 a0 a = do
2005 FL.Done b -> return $ Done 0 (Right b)
2006 FL.Partial s21 -> grouperR2 s1 s21 a
2015 FL.Partial s2 -> IPartial $ GroupByInitPair s1 s2
2016 FL.Done b -> IDone (Right b)
2017 FL.Done b -> IDone (Left b)
2019 step (GroupByInitPair s1 s2) a = grouper s1 s2 a
2021 step (GroupByGroupingPair a0 s1 s2) a =
2023 then grouperL s1 s2 a0 a
2024 else grouperR s1 s2 a0 a
2026 step (GroupByGroupingPairL a0 s1 s2) a =
2028 then grouperL2 s1 s2 a
2029 else Done 1 . Left <$> fextract1 s1
2031 step (GroupByGroupingPairR a0 s1 s2) a =
2033 then grouperR2 s1 s2 a
2034 else Done 1 . Right <$> fextract2 s2
2036 extract (GroupByInitPair s1 _) = Done 0 . Left <$> fextract1 s1
2037 extract (GroupByGroupingPairL _ s1 _) = Done 0 . Left <$> fextract1 s1
2038 extract (GroupByGroupingPairR _ _ s2) = Done 0 . Right <$> fextract2 s2
2039 extract (GroupByGroupingPair a s1 _) = do
2042 FL.Done b -> return $ Done 0 (Left b)
2043 FL.Partial s11 -> Done 0 . Left <$> fextract1 s11
2045-- XXX use an Unfold instead of a list?
2046-- XXX custom combinators for matching list, array and stream?
2047-- XXX rename to listBy?
2049-- | Match the given sequence of elements using the given comparison function.
2050-- Returns the original sequence if successful.
2054-- >>> listEqBy cmp xs = Parser.streamEqBy cmp (Stream.fromList xs) *> Parser.fromPure xs
2058-- >>> Stream.parse (Parser.listEqBy (==) "string") $ Stream.fromList "string"
2061-- >>> Stream.parse (Parser.listEqBy (==) "mismatch") $ Stream.fromList "match"
2062-- Left (ParseError "streamEqBy: mismtach occurred")
2064{-# INLINE listEqBy #-}
2065listEqBy :: Monad m => (a -> a -> Bool) -> [a] -> Parser a m [a]
2066listEqBy cmp xs = streamEqBy cmp (D.fromList xs) *> fromPure xs
2068listEqBy cmp str = Parser step initial extract
2072 -- XXX Should return IDone in initial for [] case
2073 initial = return $ IPartial str
2075 step [] _ = return $ Done 0 str
2080 else Error "listEqBy: failed, yet to match the last element"
2086 $ "listEqBy: failed, yet to match "
2087 ++ show (length xs + 1) ++ " elements"
2092 $ "listEqBy: end of input, yet to match "
2093 ++ show (length xs) ++ " elements"
2096-- | Like 'listEqBy' but uses a stream instead of a list and does not return
2099-- See also: "Streamly.Data.Stream.streamEqBy"
2101{-# INLINE streamEqBy #-}
2102streamEqBy :: Monad m => (a -> a -> Bool) -> D.Stream m a -> Parser a m ()
2103streamEqBy cmp (D.Stream sstep state) = Parser step initial extract
2108 r <- sstep defState state
2110 D.Yield x s -> return $ IPartial (Just' x, s)
2111 D.Stop -> return $ IDone ()
2112 -- Need Skip/Continue in initial to loop right here
2113 D.Skip s -> return $ IPartial (Nothing', s)
2115 step (Just' x, st) a =
2118 r <- sstep defState st
2121 D.Yield x1 s -> Continue 0 (Just' x1, s)
2123 D.Skip s -> Continue 1 (Nothing', s)
2124 else return $ Error "streamEqBy: mismtach occurred"
2125 step (Nothing', st) a = do
2126 r <- sstep defState st
2131 then Continue 0 (Nothing', s)
2132 else Error "streamEqBy: mismatch occurred"
2134 D.Skip s -> Continue 1 (Nothing', s)
2136 extract _ = return $ Error "streamEqBy: end of input"
2139-- | Match the input sequence with the supplied list and return it if
2142-- >>> listEq = Parser.listEqBy (==)
2144{-# INLINE listEq #-}
2145listEq :: (Monad m, Eq a) => [a] -> Parser a m [a]
2146listEq = listEqBy (==)
2148-- | Match if the input stream is a subsequence of the argument stream i.e. all
2149-- the elements of the input stream occur, in order, in the argument stream.
2150-- The elements do not have to occur consecutively. A sequence is considered a
2151-- subsequence of itself.
2152{-# INLINE subsequenceBy #-}
2153subsequenceBy :: -- Monad m =>
2154 (a -> a -> Bool) -> Stream m a -> Parser a m ()
2155subsequenceBy = undefined
2158-- Should go in Data.Parser.Regex in streamly package so that it can depend on
2160{-# INLINE regexPosix #-}
2161regexPosix :: -- Monad m =>
2162 Regex -> Parser m a (Maybe (Array (MatchOffset, MatchLength)))
2163regexPosix = undefined
2165{-# INLINE regexPCRE #-}
2166regexPCRE :: -- Monad m =>
2167 Regex -> Parser m a (Maybe (Array (MatchOffset, MatchLength)))
2168regexPCRE = undefined
2171-------------------------------------------------------------------------------
2172-- Transformations on input
2173-------------------------------------------------------------------------------
2175-- Initial needs a "Continue" constructor to implement scans on parsers. As a
2176-- parser can always return a Continue in initial when we feed the fold's
2177-- initial result to it. We can work this around for postscan by introducing an
2178-- initial state and calling "initial" only on the first input.
2180-- | Stateful scan on the input of a parser using a Fold.
2184{-# INLINE postscan #-}
2185postscan :: -- Monad m =>
2186 Fold m a b -> Parser b m c -> Parser a m c
2189{-# INLINE zipWithM #-}
2190zipWithM :: Monad m =>
2191 (a -> b -> m c) -> D.Stream m a -> Fold m c x -> Parser b m x
2192zipWithM zf (D.Stream sstep state) (Fold fstep finitial fextract) =
2193 Parser step initial extract
2201 r <- sstep defState state
2203 D.Yield x s -> return $ IPartial (Just' x, s, fs)
2207 -- Need Skip/Continue in initial to loop right here
2208 D.Skip s -> return $ IPartial (Nothing', s, fs)
2209 FL.Done x -> return $ IDone x
2211 step (Just' a, st, fs) b = do
2215 FL.Partial fs1 -> do
2216 r <- sstep defState st
2218 D.Yield x1 s -> return $ Continue 0 (Just' x1, s, fs1)
2222 D.Skip s -> return $ Continue 1 (Nothing', s, fs1)
2223 FL.Done x -> return $ Done 0 x
2224 step (Nothing', st, fs) b = do
2225 r <- sstep defState st
2232 return $ Continue 0 (Nothing', s, fs1)
2233 FL.Done x -> return $ Done 0 x
2237 D.Skip s -> return $ Continue 1 (Nothing', s, fs)
2239 extract _ = return $ Error "zipWithM: end of input"
2241-- | Zip the input of a fold with a stream.
2246zip :: Monad m => D.Stream m a -> Fold m (a, b) x -> Parser b m x
2247zip = zipWithM (curry return)
2249-- | Pair each element of a fold input with its index, starting from index 0.
2252{-# INLINE indexed #-}
2253indexed :: forall m a b. Monad m => Fold m (Int, a) b -> Parser a m b
2254indexed = zip (D.enumerateFromIntegral 0 :: D.Stream m Int)
2256-- | @makeIndexFilter indexer filter predicate@ generates a fold filtering
2257-- function using a fold indexing function that attaches an index to each input
2258-- element and a filtering function that filters using @(index, element) ->
2259-- Bool) as predicate.
2264-- filterWithIndex = makeIndexFilter indexed filter
2265-- filterWithAbsTime = makeIndexFilter timestamped filter
2266-- filterWithRelTime = makeIndexFilter timeIndexed filter
2270{-# INLINE makeIndexFilter #-}
2272 (Fold m (s, a) b -> Parser a m b)
2273 -> (((s, a) -> Bool) -> Fold m (s, a) b -> Fold m (s, a) b)
2274 -> (((s, a) -> Bool) -> Fold m a b -> Parser a m b)
2275makeIndexFilter f comb g = f . comb g . FL.lmap snd
2277-- | @sampleFromthen offset stride@ samples the element at @offset@ index and
2278-- then every element at strides of @stride@.
2281{-# INLINE sampleFromthen #-}
2282sampleFromthen :: Monad m => Int -> Int -> Fold m a b -> Parser a m b
2283sampleFromthen offset size =
2284 makeIndexFilter indexed FL.filter (\(i, _) -> (i + offset) `mod` size == 0)
2286--------------------------------------------------------------------------------
2288--------------------------------------------------------------------------------
2290-- | @span p f1 f2@ composes folds @f1@ and @f2@ such that @f1@ consumes the
2291-- input as long as the predicate @p@ is 'True'. @f2@ consumes the rest of the
2295-- > let span_ p xs = Stream.parse (Parser.span p Fold.toList Fold.toList) $ Stream.fromList xs
2297-- > span_ (< 1) [1,2,3]
2300-- > span_ (< 2) [1,2,3]
2303-- > span_ (< 4) [1,2,3]
2310span :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a c -> Parser a m (b, c)
2311span p f1 f2 = noErrorUnsafeSplitWith (,) (takeWhile p f1) (fromFold f2)
2313-- | Break the input stream into two groups, the first group takes the input as
2314-- long as the predicate applied to the first element of the stream and next
2315-- input element holds 'True', the second group takes the rest of the input.
2319{-# INLINE spanBy #-}
2322 => (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser a m (b, c)
2323spanBy eq f1 f2 = noErrorUnsafeSplitWith (,) (groupBy eq f1) (fromFold f2)
2325-- | Like 'spanBy' but applies the predicate in a rolling fashion i.e.
2326-- predicate is applied to the previous and the next input elements.
2329{-# INLINE spanByRolling #-}
2332 => (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser a m (b, c)
2333spanByRolling eq f1 f2 =
2334 noErrorUnsafeSplitWith (,) (groupByRolling eq f1) (fromFold f2)
2336-------------------------------------------------------------------------------
2338-------------------------------------------------------------------------------
2340-- | Takes at-most @n@ input elements.
2342-- * Stops - when the collecting parser stops.
2343-- * Fails - when the collecting parser fails.
2345-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
2348-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
2349-- Left (ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4")
2353takeP :: Monad m => Int -> Parser a m b -> Parser a m b
2354takeP lim (Parser pstep pinitial pextract) = Parser step initial extract
2363 then return $ IPartial $ Tuple' 0 s
2365 IDone b -> return $ IDone b
2366 IError e -> return $ IError e
2368 step (Tuple' cnt r) a = do
2376 then return $ Partial 0 $ Tuple' cnt1 s
2380 Done n b -> Done n b
2381 Continue n s1 -> Continue n (Tuple' (cnt1 - n) s1)
2382 Error err -> Error err
2383 Partial _ _ -> error "takeP: Partial in extract"
2388 then return $ Continue 0 $ Tuple' cnt1 s
2392 Done n b -> Done n b
2393 Continue n s1 -> Continue n (Tuple' (cnt1 - n) s1)
2394 Error err -> Error err
2395 Partial _ _ -> error "takeP: Partial in extract"
2397 let taken = cnt1 - n
2399 return $ Partial n $ Tuple' taken s
2401 let taken = cnt1 - n
2403 return $ Continue n $ Tuple' taken s
2404 Done n b -> return $ Done n b
2405 Error str -> return $ Error str
2407 extract (Tuple' cnt r) = do
2410 Done n b -> Done n b
2411 Continue n s1 -> Continue n (Tuple' (cnt - n) s1)
2412 Error err -> Error err
2413 Partial _ _ -> error "takeP: Partial in extract"
2415 -- XXX Need to make the Initial type Step to remove this
2420 Error err -> IError err
2421 _ -> error "Bug: takeP invalid state in initial"
2423-- | Run a parser without consuming the input.
2425{-# INLINE lookAhead #-}
2426lookAhead :: Monad m => Parser a m b -> Parser a m b
2427lookAhead (Parser step1 initial1 _) = Parser step initial extract
2433 return $ case res of
2434 IPartial s -> IPartial (Tuple' 0 s)
2436 IError e -> IError e
2438 step (Tuple' cnt st) a = do
2443 Partial n s -> Continue n (Tuple' (cnt1 - n) s)
2444 Continue n s -> Continue n (Tuple' (cnt1 - n) s)
2445 Done _ b -> Done cnt1 b
2446 Error err -> Error err
2448 -- XXX returning an error let's us backtrack. To implement it in a way so
2449 -- that it terminates on eof without an error then we need a way to
2450 -- backtrack on eof, that will require extract to return 'Step' type.
2451 extract (Tuple' n _) =
2454 $ "lookAhead: end of input after consuming "
2455 ++ show n ++ " elements"
2457-------------------------------------------------------------------------------
2459-------------------------------------------------------------------------------
2461-- To deinterleave we can chain two parsers one behind the other. The input is
2462-- given to the first parser and the input definitively rejected by the first
2463-- parser is given to the second parser.
2465-- We can either have the parsers themselves buffer the input or use the shared
2466-- global buffer to hold it until none of the parsers need it. When the first
2467-- parser returns Skip (i.e. rewind) we let the second parser consume the
2468-- rejected input and when it is done we move the cursor forward to the first
2469-- parser again. This will require a "move forward" command as well.
2471-- To implement grep we can use three parsers, one to find the pattern, one
2472-- to store the context behind the pattern and one to store the context in
2473-- front of the pattern. When a match occurs we need to emit the accumulator of
2474-- all the three parsers. One parser can count the line numbers to provide the
2477data DeintercalateState fs sp ss =
2478 DeintercalateL !fs !sp
2479 | DeintercalateR !fs !ss !Bool
2481-- XXX rename this to intercalate
2483-- | Apply two parsers alternately to an input stream. The input stream is
2484-- considered an interleaving of two patterns. The two parsers represent the
2487{-# INLINE deintercalate #-}
2488deintercalate :: Monad m =>
2491 -> Fold m (Either x y) z
2494 (Parser stepL initialL extractL)
2495 (Parser stepR initialR extractR)
2496 (Fold fstep finitial fextract) = Parser step initial extract
2501 error $ "deintercalate: " ++ p ++ " parser cannot "
2502 ++ status ++ " without input"
2510 IPartial sL -> return $ IPartial $ DeintercalateL fs sL
2511 IDone _ -> errMsg "left" "succeed"
2512 IError _ -> errMsg "left" "fail"
2513 FL.Done c -> return $ IDone c
2515 step (DeintercalateL fs sL) a = do
2518 Partial n s -> return $ Partial n (DeintercalateL fs s)
2519 Continue n s -> return $ Continue n (DeintercalateL fs s)
2521 fres <- fstep fs (Left b)
2523 FL.Partial fs1 -> do
2528 $ Partial n (DeintercalateR fs1 sR False)
2529 IDone _ -> errMsg "right" "succeed"
2530 IError _ -> errMsg "right" "fail"
2531 FL.Done c -> return $ Done n c
2532 Error err -> return $ Error err
2533 step (DeintercalateR fs sR consumed) a = do
2536 Partial n s -> return $ Partial n (DeintercalateR fs s True)
2537 Continue n s -> return $ Continue n (DeintercalateR fs s True)
2541 fres <- fstep fs (Right b)
2543 FL.Partial fs1 -> do
2547 return $ Partial n $ DeintercalateL fs1 sL
2548 IDone _ -> errMsg "left" "succeed"
2549 IError _ -> errMsg "left" "fail"
2550 FL.Done c -> return $ Done n c
2551 else error "deintercalate: infinite loop"
2552 Error err -> return $ Error err
2554 {-# INLINE processResult #-}
2555 processResult n fs r = do
2558 FL.Partial fs1 -> fmap (Done n) $ fextract fs1
2559 FL.Done c -> return (Done n c)
2561 extract (DeintercalateL fs sL) = do
2564 Done n b -> processResult n fs (Left b)
2565 Error err -> return $ Error err
2566 Continue n s -> return $ Continue n (DeintercalateL fs s)
2567 Partial _ _ -> error "Partial in extract"
2569 extract (DeintercalateR fs sR consumed) = do
2572 Done n b -> processResult n fs (Right b)
2573 Error err -> return $ Error err
2574 -- XXX Review consumed
2575 Continue n s -> return $ Continue n (DeintercalateR fs s consumed)
2576 Partial _ _ -> error "Partial in extract"
2578data SepByState fs sp ss =
2580 | SepBySeparator !fs !ss !Bool
2582-- | Run the content parser first, when it is done, the separator parser is
2583-- run, when it is done content parser is run again and so on. If none of the
2584-- parsers consumes an input then parser returns a failure.
2586-- >>> sepBy p1 p2 sink = Parser.deintercalate p1 p2 (Fold.catLefts sink)
2587-- >>> sepBy content sep sink = Parser.sepBy1 content sep sink <|> return mempty
2591 Parser a m b -> Parser a m x -> Fold m b c -> Parser a m c
2593 (Parser pstep pinitial pextract)
2594 (Parser sstep sinitial _)
2595 (Fold fstep finitial fextract) = Parser step initial extract
2600 error $ "sepBy: " ++ p ++ " parser cannot "
2601 ++ status ++ " without input"
2609 IPartial sp -> return $ IPartial $ SepByInit fs sp
2610 IDone _ -> errMsg "content" "succeed"
2611 IError _ -> errMsg "content" "fail"
2612 FL.Done b -> return $ IDone b
2614 step (SepByInit fs sp) a = do
2617 Partial n s -> return $ Partial n (SepByInit fs s)
2618 Continue n s -> return $ Continue n (SepByInit fs s)
2622 FL.Partial fs1 -> do
2626 return $ Partial n (SepBySeparator fs1 ss False)
2627 IDone _ -> errMsg "separator" "succeed"
2628 IError _ -> errMsg "separator" "fail"
2629 FL.Done c -> return $ Done n c
2630 Error err -> return $ Error err
2631 step (SepBySeparator fs ss consumed) a = do
2634 Partial n s -> return $ Partial n (SepBySeparator fs s True)
2635 Continue n s -> return $ Continue n (SepBySeparator fs s True)
2641 IPartial sp -> return $ Partial n $ SepByInit fs sp
2642 IDone _ -> errMsg "content" "succeed"
2643 IError _ -> errMsg "content" "fail"
2644 else error "sepBy: infinite loop"
2645 Error err -> return $ Error err
2647 extract (SepByInit fs sp) = do
2653 FL.Partial fs1 -> fmap (Done n) $ fextract fs1
2654 FL.Done c -> return (Done n c)
2655 Error err -> return $ Error err
2656 Continue n s -> return $ Continue n (SepByInit fs s)
2657 Partial _ _ -> error "Partial in extract"
2659 extract (SepBySeparator fs _ _) = fmap (Done 0) $ fextract fs
2661-- XXX This can be implemented using refold, parse one and then continue
2662-- collecting the rest in that.
2664-- | Parse items separated by a separator parsed by the supplied parser. At
2665-- least one item must be present for the parser to succeed.
2667-- Note that this can go in infinite loop if both the parsers fail on some
2668-- input. Detection of that would make the implementation more complex.
2670{-# INLINE sepBy1 #-}
2672 Parser a m b -> Parser a m x -> Fold m b c -> Parser a m c
2673sepBy1 p sep sink = do
2675 f <- fromEffect $ FL.reduce sink
2676 f1 <- fromEffect $ FL.snoc f x
2679-------------------------------------------------------------------------------
2680-- Interleaving a collection of parsers
2681-------------------------------------------------------------------------------
2683-- | Apply a collection of parsers to an input stream in a round robin fashion.
2684-- Each parser is applied until it stops and then we repeat starting with the
2685-- the first parser again.
2689{-# INLINE roundRobin #-}
2690roundRobin :: -- (Foldable t, Monad m) =>
2691 t (Parser a m b) -> Fold m b c -> Parser a m c
2692roundRobin _ps _f = undefined
2694-------------------------------------------------------------------------------
2695-- Sequential Collection
2696-------------------------------------------------------------------------------
2698-- | @sequence f p@ collects sequential parses of parsers in a
2699-- serial stream @p@ using the fold @f@. Fails if the input ends or any
2700-- of the parsers fail.
2704{-# INLINE sequence #-}
2705sequence :: Monad m =>
2706 D.Stream m (Parser a m b) -> Fold m b c -> Parser a m c
2707sequence (D.Stream sstep sstate) (Fold fstep finitial fextract) =
2708 Parser step initial extract
2715 FL.Partial fs -> return $ IPartial (Nothing', sstate, fs)
2716 FL.Done c -> return $ IDone c
2718 -- state does not contain any parser
2719 -- yield a new parser from the stream
2720 step (Nothing', ss, fs) _ = do
2721 sres <- sstep defState ss
2723 D.Yield p ss1 -> return $ Continue 1 (Just' p, ss1, fs)
2727 D.Skip ss1 -> return $ Continue 1 (Nothing', ss1, fs)
2729 -- state holds a parser that may or may not have been
2730 -- initialized. pinit holds the initial parser state
2731 -- or modified parser state respectively
2732 step (Just' (Parser pstep pinit pextr), ss, fs) a = do
2740 Just' $ Parser pstep (return $ IPartial ps2) pextr
2741 in return $ Partial n (newP, ss, fs)
2744 Just' $ Parser pstep (return $ IPartial ps2) pextr
2745 in return $ Continue n (newP, ss, fs)
2750 return $ Partial n (Nothing', ss, fs1)
2751 FL.Done c -> return $ Done n c
2752 Error msg -> return $ Error msg
2757 return $ Partial 1 (Nothing', ss, fs1)
2758 FL.Done c -> return $ Done 1 c
2759 IError err -> return $ Error err
2761 extract (Nothing', _, fs) = fmap (Done 0) $ fextract fs
2762 extract (Just' (Parser pstep pinit pextr), ss, fs) = do
2771 FL.Partial fs1 -> fmap (Done n) $ fextract fs1
2772 FL.Done c -> return (Done n c)
2773 Error err -> return $ Error err
2774 Continue n s -> return $ Continue n (Just' (Parser pstep (return (IPartial s)) pextr), ss, fs)
2775 Partial _ _ -> error "Partial in extract"
2779 FL.Partial fs1 -> fmap (Done 0) $ fextract fs1
2780 FL.Done c -> return (Done 0 c)
2781 IError err -> return $ Error err
2783-------------------------------------------------------------------------------
2784-- Alternative Collection
2785-------------------------------------------------------------------------------
2788-- | @choice parsers@ applies the @parsers@ in order and returns the first
2791-- This is same as 'asum' but more efficient.
2795{-# INLINE choice #-}
2796choice :: (MonadCatch m, Foldable t) => t (Parser a m b) -> Parser a m b
2797choice = foldl1 shortest
2800-------------------------------------------------------------------------------
2801-- Sequential Repetition
2802-------------------------------------------------------------------------------
2804-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
2805-- results. Parsing stops or fails if the collecting parser stops or fails.
2810manyP :: -- MonadCatch m =>
2811 Parser a m b -> Parser b m c -> Parser a m c
2812manyP _p _f = undefined
2814-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
2815-- input stream and push the parse results to a downstream fold.
2817-- Stops: when the downstream fold stops or the parser fails.
2818-- Fails: never, produces zero or more results.
2820-- >>> many = Parser.countBetween 0 maxBound
2822-- Compare with 'Control.Applicative.many'.
2825many :: Monad m => Parser a m b -> Fold m b c -> Parser a m c
2827-- many = countBetween 0 maxBound
2829-- Note: many1 would perhaps be a better name for this and consistent with
2830-- other names like takeWhile1. But we retain the name "some" for
2833-- | Collect one or more parses. Apply the supplied parser repeatedly on the
2834-- input stream and push the parse results to a downstream fold.
2836-- Stops: when the downstream fold stops or the parser fails.
2837-- Fails: if it stops without producing a single result.
2839-- >>> some p f = Parser.manyP p (Parser.takeGE 1 f)
2840-- >>> some = Parser.countBetween 1 maxBound
2842-- Compare with 'Control.Applicative.some'.
2845some :: Monad m => Parser a m b -> Fold m b c -> Parser a m c
2847-- some p f = manyP p (takeGE 1 f)
2848-- some = countBetween 1 maxBound
2850-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
2851-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
2852-- the input ends or the parser fails before @m@ results are collected.
2854-- >>> countBetween m n p f = Parser.manyP p (Parser.takeBetween m n f)
2858{-# INLINE countBetween #-}
2859countBetween :: -- MonadCatch m =>
2860 Int -> Int -> Parser a m b -> Fold m b c -> Parser a m c
2861countBetween _m _n _p = undefined
2862-- countBetween m n p f = manyP p (takeBetween m n f)
2864-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
2865-- the fold @f@. Fails if the input ends or the parser fails before @n@
2866-- results are collected.
2868-- >>> count n = Parser.countBetween n n
2869-- >>> count n p f = Parser.manyP p (Parser.takeEQ n f)
2874count :: -- MonadCatch m =>
2875 Int -> Parser a m b -> Fold m b c -> Parser a m c
2876count n = countBetween n n
2877-- count n p f = manyP p (takeEQ n f)
2879-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
2880-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
2882-- We can implemnent parsers like the following using 'manyTillP':
2885-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
2890{-# INLINE manyTillP #-}
2891manyTillP :: -- Monad m =>
2892 Parser a m b -> Parser a m x -> Parser b m c -> Parser a m c
2893manyTillP _p1 _p2 _f = undefined
2894 -- D.toParserK $ D.manyTillP (D.fromParserK p1) (D.fromParserK p2) f
2896data ManyTillState fs sr sl
2897 = ManyTillR Int fs sr
2898 | ManyTillL Int fs sl
2900-- | @manyTill chunking test f@ tries the parser @test@ on the input, if @test@
2901-- fails it backtracks and tries @chunking@, after @chunking@ succeeds @test@ is
2902-- tried again and so on. The parser stops when @test@ succeeds. The output of
2903-- @test@ is discarded and the output of @chunking@ is accumulated by the
2904-- supplied fold. The parser fails if @chunking@ fails.
2906-- Stops when the fold @f@ stops.
2908{-# INLINE manyTill #-}
2910 => Parser a m b -> Parser a m x -> Fold m b c -> Parser a m c
2911manyTill (Parser stepL initialL extractL)
2912 (Parser stepR initialR _)
2913 (Fold fstep finitial fextract) =
2914 Parser step initial extract
2918 -- Caution: Mutual recursion
2920 scrutL fs p c d e = do
2923 IPartial sl -> return $ c (ManyTillL 0 fs sl)
2927 FL.Partial fs1 -> scrutR fs1 p c d e
2928 FL.Done fb -> return $ d fb
2929 IError err -> return $ e err
2931 scrutR fs p c d e = do
2934 IPartial sr -> return $ p (ManyTillR 0 fs sr)
2935 IDone _ -> d <$> fextract fs
2936 IError _ -> scrutL fs p c d e
2941 FL.Partial fs -> scrutR fs IPartial IPartial IDone IError
2942 FL.Done b -> return $ IDone b
2944 step (ManyTillR cnt fs st) a = do
2947 Partial n s -> return $ Partial n (ManyTillR 0 fs s)
2949 assertM(cnt + 1 - n >= 0)
2950 return $ Continue n (ManyTillR (cnt + 1 - n) fs s)
2958 return $ Continue (cnt + 1) (ManyTillL 0 fs sl)
2966 FL.Partial fs1 -> scrutR fs1 p c d Error
2967 FL.Done fb -> return $ Done cnt1 fb
2968 IError err -> return $ Error err
2969 -- XXX the cnt is being used only by the assert
2970 step (ManyTillL cnt fs st) a = do
2973 Partial n s -> return $ Partial n (ManyTillL 0 fs s)
2975 assertM(cnt + 1 - n >= 0)
2976 return $ Continue n (ManyTillL (cnt + 1 - n) fs s)
2981 scrutR s (Partial n) (Continue n) (Done n) Error
2982 FL.Done b1 -> return $ Done n b1
2983 Error err -> return $ Error err
2985 extract (ManyTillL cnt fs sR) = do
2991 FL.Partial fs1 -> fmap (Done n) $ fextract fs1
2992 FL.Done c -> return (Done n c)
2993 Error err -> return $ Error err
2996 return $ Continue n (ManyTillL 0 fs s)
2997 Partial _ _ -> error "Partial in extract"
2998 extract (ManyTillR _ fs _) = fmap (Done 0) $ fextract fs
3000-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
3001-- collects the output in the supplied fold. If the the parser @collect@ fails,
3002-- parser @recover@ is run until it stops and then we start repeating the
3003-- parser @collect@ again. The parser fails if the recovery parser fails.
3005-- For example, this can be used to find a key frame in a video stream after an
3010{-# INLINE manyThen #-}
3011manyThen :: -- (Foldable t, Monad m) =>
3012 Parser a m b -> Parser a m x -> Fold m b c -> Parser a m c
3013manyThen _parser _recover _f = undefined
3015-------------------------------------------------------------------------------
3016-- Repeated Alternatives
3017-------------------------------------------------------------------------------
3019-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
3020-- fails the input consumed till now is dropped and the new instance is tried
3021-- on the fresh input.
3025{-# INLINE retryMaxTotal #-}
3026retryMaxTotal :: -- (Monad m) =>
3027 Int -> Parser a m b -> Fold m b c -> Parser a m c
3028retryMaxTotal _n _p _f = undefined
3030-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
3034{-# INLINE retryMaxSuccessive #-}
3035retryMaxSuccessive :: -- (Monad m) =>
3036 Int -> Parser a m b -> Fold m b c -> Parser a m c
3037retryMaxSuccessive _n _p _f = undefined
3039-- | Keep trying a parser until it succeeds. When the parser fails the input
3040-- consumed till now is dropped and the new instance is tried on the fresh
3046retry :: -- (Monad m) =>
3047 Parser a m b -> Parser a m 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