git.iko.soy/streamly
on 95ebe09 help sign in
streamly/core/src/Streamly/Data/Parser.hs
147 lines 3.9 kB history raw
1-- |
2-- Module : Streamly.Data.Parser
3-- Copyright : (c) 2020 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
6-- Stability : pre-release
7-- Portability : GHC
8--
9-- Fast backtracking parsers with stream fusion and native streaming
10-- capability. Parsers are just more powerful folds, folds and parsers can be
11-- interconverted.
12--
13-- Note that these parsers do not report the error context (e.g. line number or
14-- column). This may be supported in future.
15--
16-- mtl instances are not provided. If the 'Parser' type is the top most layer
17-- (which should be the case almost always) you can just use 'fromEffect' to
18-- execute the lower layer monad effects.
19--
20-- == Performance Notes
21--
22-- This module is designed for fusion, inline the operations in this module for
23-- fusion to occur, avoid using these operations in recursive calls, avoid
24-- operations like 'sequence', 'asum' on these parsers. If you need these then
25-- use the 'ParserK' module instead.
26--
27-- The 'Parser' type represents a stream consumer by composing state as data
28-- which enables stream fusion. Stream fusion generates a tight loop without
29-- any constructor allocations between the stages, providing C like performance
30-- for the loop. Stream fusion works when multiple functions are combined in a
31-- pipeline statically. Therefore, the operations in this module must be
32-- inlined and must not be used recursively to allow for stream fusion.
33--
34-- Using the 'Parser' type parsing operations like 'one', 'splitWith' etc.
35-- degrade quadratically (O(n^2)) when combined many times. If you need to
36-- combine these operations, say more than 50 times in a single loop, then you
37-- should use the continuation style parser type 'ParserK' instead. Also, if
38-- you need to use these operations in a recursive loop you should use
39-- 'ParserK' instead.
40--
41-- The 'ParserK' type represents a stream consumer by composing function calls,
42-- therefore, a function call overhead is incurred at each composition. It is
43-- quite fast in general but may be a few times slower than a fused parser.
44-- However, it allows for scalable dynamic composition especially parsers can
45-- be used in recursive calls. Using the 'ParserK' type operations like
46-- 'splitWith' provide linear (O(n)) performance with respect to the number of
47-- compositions..
48--
49-- 'Parser' and 'ParserK' types can be interconverted.
50--
51module Streamly.Data.Parser
52 (
53 -- * Parser Type
54 Parser
56 -- -- * Downgrade to Fold
57 -- , toFold
59 -- * Parsers
60 -- ** From Folds
61 , fromFold
63 -- ** Without Input
64 -- , fromFoldMaybe
65 , fromPure
66 , fromEffect
67 , die
68 -- , dieM
69 , peek
70 , eof
72 -- ** Element parsers
74 -- All of these can be expressed in terms of either
75 , one
76 -- , oneEq
77 -- , oneNotEq
78 , oneOf
79 , noneOf
80 , satisfy
81 -- , maybe
82 -- , either
84 -- ** Sequences
85 , streamEqBy
86 , listEqBy
87 , listEq
89 -- * Combinators
90 -- Mapping on output
91 -- , rmapM
93 -- ** Mapping on input
94 , lmap
95 , lmapM
97 -- * Map on output
98 , rmapM
100 -- ** Filtering
101 , filter
103 -- ** Look Ahead
104 , lookAhead
106 -- ** Tokenize by length
107 -- , takeBetween
108 , takeEQ
109 -- , takeGE
110 -- , takeP
112 -- ** Tokenize by predicate
113 -- , takeWhileP
114 , takeWhile
115 , takeWhile1
116 , dropWhile
117 -- , takeEndBy
118 -- , takeEndByEsc
119 -- , takeStartBy
120 , wordBy
122 -- ** Grouping
123 , groupBy
124 -- , groupByRolling
125 -- , groupByRollingEither
127 -- ** Framing
128 -- , wordFramedBy
129 , wordWithQuotes
130 , wordStripQuotes
132 -- * Alternative
133 , alt
135 -- ** Splitting
136 , many
137 , some
138 , manyTill
140 -- ** De-interleaving
141 , deintercalate
142 )
144where
146import Streamly.Internal.Data.Parser
147import Prelude hiding (dropWhile, takeWhile, filter)