parser-regex 0.1.0.0 → 0.2.0.0

raw patch · 13 files changed

+482/−115 lines, 13 filesdep −bytestringdep ~QuickCheckdep ~containersdep ~tasty-quickcheckPVP ok

version bump matches the API change (PVP)

Dependencies removed: bytestring

Dependency ranges changed: QuickCheck, containers, tasty-quickcheck

API changes (from Hackage documentation)

Files

• CHANGELOG.md +10/−0
• README.md +121/−23
• parser-regex.cabal +14/−15
• src/Regex/Base.hs +3/−2
• src/Regex/Internal/CharSet.hs +24/−11
• src/Regex/Internal/Debug.hs +14/−3
• src/Regex/Internal/Generated/CaseFold.hs +30/−3
• src/Regex/Internal/List.hs +13/−4
• src/Regex/Internal/Parser.hs +119/−23
• src/Regex/Internal/Regex.hs +7/−2
• src/Regex/Internal/Text.hs +51/−27
• src/Regex/Internal/Unique.hs +12/−1
• test/Test.hs +64/−1

@@ -1,3 +1,13 @@+### 0.2.0.0 -- 2024-11-24++* Breaking changes+  * Parsing fails more eagerly. This affects lazy list parsing and parsing via+    the `Regex.Base` functions `prepareParser` and `stepParser`.+* Additions+  * Added `Regex.Base.parseNext`.+* Other+  * Some internal modules are now exported.+ ### 0.1.0.0 -- 2024-03-04  * First version.

@@ -9,7 +9,7 @@  * Parsers based on [regular expressions](https://en.wikipedia.org/wiki/Regular_expression),   capable of parsing [regular languages](https://en.wikipedia.org/wiki/Regular_language).-  There are no extra features that would make parsing non-regular languages+  Note that there are no extra features to make parsing non-regular languages   possible. * Regexes are composed using combinators. * Resumable parsing of sequences of any type containing values of any type.@@ -18,8 +18,20 @@ * Parsing runtime is linear in the length of the sequence being parsed. No   exponential backtracking. -## Example+## Examples +### Versus regex patterns++```+^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?+```++Can you guess what this matches?++This is a non-validating regex to extract parts of a URI, from+[RFC 3986](https://datatracker.ietf.org/doc/html/rfc3986#appendix-B). It can+be translated as follows.+ ```hs {-# LANGUAGE OverloadedStrings #-} import Control.Applicative (optional)@@ -37,9 +49,6 @@   , fragment  :: Maybe Text   } deriving Show --- ^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?--- A non-validating regex to extract parts of a URI, from RFC 3986--- Translated: uriRE :: REText URI uriRE = URI   <$> optional (R.someTextOf (CS.not ":/?#") <* R.char ':')@@ -57,9 +66,87 @@           , fragment = Just "parser-regex" }) ``` +### More parsing++Parsing is straightforward, even for tasks which may be impractical with+submatch extraction typically offered by regex libraries.++```hs+import Control.Applicative ((<|>))+import Data.Text (Text)++import Regex.Text (REText)+import qualified Regex.Text as R+import qualified Data.CharSet as CS++data Expr+  = Var Text+  | Expr :+ Expr+  | Expr :- Expr+  | Expr :* Expr+  deriving Show++exprRE :: REText Expr+exprRE = var `R.chainl1` mul `R.chainl1` (add <|> sub)+  where+    var = Var <$> R.someTextOf CS.asciiLower+    add = (:+) <$ R.char '+'+    sub = (:-) <$ R.char '-'+    mul = (:*) <$ R.char '*'+```+```hs+>>> import qualified Regex.Text as R+>>> R.reParse exprRE "a+b-c*d*e+f"+Just (((Var "a" :+ Var "b") :- ((Var "c" :* Var "d") :* Var "e")) :+ Var "f")+```++### Find and replace++Find and replace using regexes are supported for `Text` and lists.++```hs+>>> import Control.Applicative ((<|>))+>>> import qualified Data.Text as T+>>> import qualified Regex.Text as R+>>>+>>> data Color = Blue | Orange deriving Show+>>> let re = Blue <$ R.text "blue" <|> Orange <$ R.text "orange"+>>> R.find re "color: orange"+Just Orange+>>>+>>> let re = T.toUpper <$> (R.text "cat" <|> R.text "dog" <|> R.text "fish")+>>> R.replaceAll re "locate selfish hotdog"+"loCATe selFISH hotDOG"+```++### Parse any sequence++Regexes are not restricted to parsing text. For example, one may parse vectors+from the [vector](https://hackage.haskell.org/package/vector) library, because+why not.++```hs+import Regex.Base (Parser)+import qualified Regex.Base as R+import qualified Data.Vector.Generic as VG++parseVector :: VG.Vector v c => Parser c a -> v c -> Maybe a+parseVector = R.parseFoldr VG.foldr+```+```hs+>>> import Control.Applicative (many)+>>> import qualified Data.Vector as V+>>> import qualified Regex.Base as R+>>>+>>> let p = R.compile $ many ((,) <$> R.satisfy even <*> R.satisfy odd)+>>> let v = V.fromList [0..5] :: V.Vector Int+>>> parseVector p v+Just [(0,1),(2,3),(4,5)]+```+ ## Documentation -Please find the documentation on Hackage:+Documentation is available on Hackage: [parser-regex](https://hackage.haskell.org/package/parser-regex)  Already familiar with regex patterns? See the@@ -70,33 +157,44 @@ ### `regex-applicative`  [`regex-applicative`](https://hackage.haskell.org/package/regex-applicative) is-the primary inspiration for this library, and provides a similar set of-features.-`parser-regex` attempts to be a more fully-featured library built on the-ideas of `regex-applicative`.+the primary inspiration for this library, and is similar in many ways. +`parser-regex` attempts to be a more efficient and featureful library built on+the ideas of `regex-applicative`, though it does not aim to provide a superset+of `regex-applicative`'s API.+ ### Traditional regex libraries -Other alternatives are more traditional regex libraries that use regex patterns,-like [`regex-tdfa`](https://hackage.haskell.org/package/regex-tdfa) and-[`regex-pcre`](https://hackage.haskell.org/package/regex-pcre)/-[`regex-pcre-builtin`](https://hackage.haskell.org/package/regex-pcre-builtin).+These libraries use regex patterns. -Reasons to use `parser-regex` over traditional regex libraries:+* [`regex-pcre`](https://hackage.haskell.org/package/regex-pcre)/[`regex-pcre-builtin`](https://hackage.haskell.org/package/regex-pcre-builtin)+* [`regex-tdfa`](https://hackage.haskell.org/package/regex-tdfa)+* [`pcre-light`](https://hackage.haskell.org/package/pcre-light)/[`pcre-heavy`](https://hackage.haskell.org/package/pcre-heavy)+* [`pcre2`](https://hackage.haskell.org/package/pcre2) +Consider using these if++* The terseness of regex patterns is well-suited for your use case.+* You need something very fast for typical use cases. `regex-pcre`,+  `regex-pcre-builtin`, `pcre-light`, `pcre-heavy` are faster than+  `parser-regex` for typical use cases, but there are trade-offs—such as losing+  Unicode support and a risk of [ReDoS](https://en.wikipedia.org/wiki/ReDoS).++Use `parser-regex` instead if+ * You prefer parser combinators over regex patterns * You need more powerful parsing capabilities than just submatch extraction-* You need to parse a sequence type that is not supported by these regex-  libraries+* You need to parse a sequence that is not supported by the above libraries -Reasons to use traditional regex libraries over `parser-regex`:+For a detailed comparison of regex libraries,+[see here](https://github.com/meooow25/parser-regex/tree/master/bench). -* The terseness of regex patterns is better suited for your use case-* You need something very fast, and adversarial input is not a concern.-  Use `regex-pcre`/`regex-pcre-builtin`.+### Other options -For a more detailed comparison of regex libraries, see-[here](https://github.com/meooow25/parser-regex/tree/master/bench).+If you are not restricted to regexes, there are many other parsing libraries you+may use, too many to list here. See the+["Parsing" category on Hackage](https://hackage.haskell.org/packages/#cat:Parsing)+for a start.  ## Contributing 

@@ -1,6 +1,6 @@ cabal-version:      2.4 name:               parser-regex-version:            0.1.0.0+version:            0.2.0.0 synopsis:           Regex based parsers description:        Regex based parsers. homepage:           https://github.com/meooow25/parser-regex@@ -19,15 +19,17 @@     GHC == 9.0.2   , GHC == 9.2.8   , GHC == 9.4.8-  , GHC == 9.6.4-  , GHC == 9.8.1+  , GHC == 9.6.6+  , GHC == 9.8.2+  , GHC == 9.10.1  source-repository head     type:     git     location: https://github.com/meooow25/parser-regex.git  common warnings-    ghc-options: -Wall+    ghc-options:+        -Wall -Wcompat -Widentities -Wredundant-constraints -Wunused-packages  library     import:           warnings@@ -37,22 +39,21 @@         Regex.Base         Regex.List         Regex.Text--    other-modules:         Regex.Internal.CharSet-        Regex.Internal.CharSets         Regex.Internal.Debug-        Regex.Internal.Generated.CaseFold-        Regex.Internal.List-        Regex.Internal.Num         Regex.Internal.Parser         Regex.Internal.Regex         Regex.Internal.Text         Regex.Internal.Unique +    other-modules:+        Regex.Internal.CharSets+        Regex.Internal.Generated.CaseFold+        Regex.Internal.List+        Regex.Internal.Num+     build-depends:         base >= 4.15 && < 5.0-      , bytestring >= 0.10.12 && < 0.13       , containers >= 0.6.4 && < 0.8       , deepseq >= 1.4.5 && < 1.6       , ghc-bignum >= 1.1 && < 1.4@@ -68,14 +69,12 @@      build-depends:         base-      , bytestring-      , containers       , parser-regex-      , QuickCheck >= 2.14.3 && < 2.15+      , QuickCheck >= 2.14.3 && < 2.16       , quickcheck-classes-base >= 0.6.2 && < 0.7       , tasty >= 1.5 && < 1.6       , tasty-hunit >= 0.10.1 && < 0.11-      , tasty-quickcheck >= 0.10.3 && < 0.11+      , tasty-quickcheck >= 0.10.3 && < 0.12       , text      hs-source-dirs:   test

@@ -19,6 +19,7 @@   , P.finishParser   , P.Foldr   , P.parseFoldr+  , P.parseNext      -- * @RE@s and combinators   , R.token@@ -67,8 +68,8 @@ -- a large amount of control over the parsing process, making it possible to -- parse in a resumable or even branching manner. ----- As a simpler alternative to the trio of functions above, @parseFoldr@ can be--- used on any sequence type that can be folded over.+-- @parseFoldr@ and @parseNext@ may be more convenient to use, depending on the+-- sequence to parse. --  -- $strict

@@ -1,7 +1,17 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE MagicHash #-}+{-# OPTIONS_HADDOCK not-home #-}++-- | This is an internal module. You probably don't need to import this. Import+-- "Data.CharSet" instead.+--+-- = WARNING+--+-- Definitions in this module allow violating invariants that would otherwise be+-- guaranteed by non-internal modules. Use at your own risk!+-- module Regex.Internal.CharSet-  ( CharSet+  ( CharSet(..)   , empty   , singleton   , fromRange@@ -27,7 +37,7 @@ import qualified Prelude import Data.Char import Data.String-import Data.Foldable (foldl')+import qualified Data.Foldable as F import qualified Data.IntMap.Strict as IM import Data.Semigroup (Semigroup(..), stimesIdempotentMonoid) import GHC.Exts (Int(..), Char(..), chr#)@@ -46,21 +56,21 @@   showsPrec p cs = showParen (p > 10) $     showString "fromRanges " . shows (ranges cs) --- | @fromString = 'fromList'@+-- | @fromString@ = 'fromList' instance IsString CharSet where   fromString = fromList --- | @(<>) = 'union'@+-- | @(<>)@ = 'union' instance Semigroup CharSet where   (<>) = union-  sconcat = foldl' union empty+  sconcat = F.foldl' union empty   {-# INLINE sconcat #-}   stimes = stimesIdempotentMonoid --- | @mempty = 'empty'@+-- | @mempty@ = 'empty' instance Monoid CharSet where   mempty = empty-  mconcat = foldl' union empty+  mconcat = F.foldl' union empty   {-# INLINE mconcat #-}  -- | The empty set.@@ -78,12 +88,12 @@  -- | \(O(s \min(s,C))\). Create a set from @Char@s in a list. fromList :: [Char] -> CharSet-fromList = foldl' (flip insert) empty+fromList = F.foldl' (flip insert) empty {-# INLINE fromList #-}  -- | \(O(n \min(n,C))\). Create a set from the given @Char@ ranges (inclusive). fromRanges :: [(Char, Char)] -> CharSet-fromRanges = foldl' (flip insertRange) empty+fromRanges = F.foldl' (flip insertRange) empty {-# INLINE fromRanges #-}  -- | \(O(\min(n,C))\). Insert a @Char@ into a set.@@ -220,7 +230,10 @@  -- | Is the internal structure of the set valid? valid :: CharSet -> Bool-valid cs = and (zipWith (<=) ls hs)-        && all (>1) (zipWith (flip (-)) hs (tail ls))+valid cs = noneEmpty && noneAdjacent   where     (ls,hs) = unzip (fmap (fmap ord) (IM.assocs (unCharSet cs)))+    noneEmpty = and (zipWith (<=) ls hs)+    noneAdjacent = case ls of+      [] -> True+      _:ls' -> all (>1) (zipWith (-) ls' hs)

@@ -1,6 +1,11 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE ScopedTypeVariables #-}++-- | This module provides functions for visualizing @RE@s and @Parser@s.+-- [See here](https://github.com/meooow25/parser-regex/wiki/Visualizations)+-- for some examples.+-- module Regex.Internal.Debug   ( reToDot   , parserToDot@@ -29,7 +34,7 @@  -- | Generate a [Graphviz DOT](https://graphviz.org/doc/info/lang.html) -- visualization of a 'RE'. Optionally takes an alphabet @[c]@, which will be--- tested against the 'token' functions in the 'RE' and accepted characters+-- tested against the @token@ functions in the 'RE' and accepted characters -- displayed. reToDot :: forall c a. Maybe ([c], [c] -> String) -> RE c a -> String reToDot ma re0 = execM $ do@@ -69,7 +74,7 @@  -- | Generate a [Graphviz DOT](https://graphviz.org/doc/info/lang.html) -- visualization of a 'Parser'. Optionally takes an alphabet @[c]@, which will--- be tested against the 'token' functions in the 'Parser' and the accepted+-- be tested against the @token@ functions in the 'Parser' and the accepted -- characters displayed. parserToDot :: forall c a. Maybe ([c], [c] -> String) -> Parser c a -> String parserToDot ma p0 = execM $ do@@ -133,6 +138,9 @@ -- Display Chars ------------------ +-- |+-- >>> dispCharRanges "abc012def"+-- "[('0','2'),('a','f')]" dispCharRanges :: [Char] -> String dispCharRanges = show . CS.ranges . CS.fromList @@ -169,7 +177,10 @@     (fromString . escape . disp) (filter (isJust . t) cs))  escape :: String -> String-escape = init . tail . show+escape = init . tail' . show+  where+    tail' (_:xs) = xs+    tail' [] = error "tail'"  (<+>) :: Str -> Str -> Str s1 <+> s2 = s1 <> " " <> s2

@@ -1,9 +1,9 @@ -- DO NOT EDIT -- This file was generated by GenCaseFold.hs from a CaseFolding.txt with header ----- CaseFolding-15.1.0.txt--- Date: 2023-05-12, 21:53:10 GMT--- © 2023 Unicode®, Inc.+-- CaseFolding-16.0.0.txt+-- Date: 2024-04-30, 21:48:11 GMT+-- © 2024 Unicode®, Inc. -- module Regex.Internal.Generated.CaseFold   ( caseFoldSimple@@ -545,6 +545,7 @@   '\x1c86' -> '\x44a'   '\x1c87' -> '\x463'   '\x1c88' -> '\xa64b'+  '\x1c89' -> '\x1c8a'   '\x1c90' -> '\x10d0'   '\x1c91' -> '\x10d1'   '\x1c92' -> '\x10d2'@@ -1097,9 +1098,13 @@   '\xa7c6' -> '\x1d8e'   '\xa7c7' -> '\xa7c8'   '\xa7c9' -> '\xa7ca'+  '\xa7cb' -> '\x264'+  '\xa7cc' -> '\xa7cd'   '\xa7d0' -> '\xa7d1'   '\xa7d6' -> '\xa7d7'   '\xa7d8' -> '\xa7d9'+  '\xa7da' -> '\xa7db'+  '\xa7dc' -> '\x19b'   '\xa7f5' -> '\xa7f6'   '\xab70' -> '\x13a0'   '\xab71' -> '\x13a1'@@ -1370,6 +1375,28 @@   '\x10cb0' -> '\x10cf0'   '\x10cb1' -> '\x10cf1'   '\x10cb2' -> '\x10cf2'+  '\x10d50' -> '\x10d70'+  '\x10d51' -> '\x10d71'+  '\x10d52' -> '\x10d72'+  '\x10d53' -> '\x10d73'+  '\x10d54' -> '\x10d74'+  '\x10d55' -> '\x10d75'+  '\x10d56' -> '\x10d76'+  '\x10d57' -> '\x10d77'+  '\x10d58' -> '\x10d78'+  '\x10d59' -> '\x10d79'+  '\x10d5a' -> '\x10d7a'+  '\x10d5b' -> '\x10d7b'+  '\x10d5c' -> '\x10d7c'+  '\x10d5d' -> '\x10d7d'+  '\x10d5e' -> '\x10d7e'+  '\x10d5f' -> '\x10d7f'+  '\x10d60' -> '\x10d80'+  '\x10d61' -> '\x10d81'+  '\x10d62' -> '\x10d82'+  '\x10d63' -> '\x10d83'+  '\x10d64' -> '\x10d84'+  '\x10d65' -> '\x10d85'   '\x118a0' -> '\x118c0'   '\x118a1' -> '\x118c1'   '\x118a2' -> '\x118c2'

@@ -291,6 +291,9 @@  -- | \(O(mn \log m)\). Parse a list with a @RE@. --+-- Parses the entire list, not just a prefix or a substring.+-- Returns early without demanding the entire list on parse failure.+-- -- Uses 'Regex.List.compile', see the note there. -- -- If parsing multiple lists using the same @RE@, it is wasteful to compile@@ -305,6 +308,9 @@ {-# INLINE reParse #-}  -- | \(O(mn \log m)\). Parse a list with a @Parser@.+--+-- Parses the entire list, not just a prefix or a substring.+-- Returns early without demanding the entire list on parse failure. parse :: Parser c a -> [c] -> Maybe a parse = P.parseFoldr foldr {-# INLINE parse #-}@@ -313,6 +319,9 @@ -- parse failure. -- -- For use with parsers that are known to never fail.+--+-- Parses the entire list, not just a prefix or a substring.+-- Returns early without demanding the entire list on parse failure. parseSure :: Parser c a -> [c] -> a parseSure p = fromMaybe parseSureError . parse p {-# INLINE parseSure #-}@@ -415,20 +424,20 @@   where     f a b c = concat [a,b,c] --- | \(O(mn \log m)\). Replace non-overlapping matches of the given @RE@ with--- their results.+-- | \(O(mn \log m)\). Replace all non-overlapping matches of the given @RE@+-- with their results. -- -- ==== __Examples__ -- -- >>> replaceAll (" and " <$ list ", ") "red, blue, green" -- "red and blue and green" ----- >>> replaceAll ("Fruit" <$ list "Time" <|> "banana" <$ list "arrow") "Time flies like an arrow"+-- >>> replaceAll ("Fruit" <$ list "Time" <|> "a banana" <$ list "an arrow") "Time flies like an arrow" -- "Fruit flies like a banana" -- -- @ -- sep = 'oneOfChar' "-./"--- digits n = 'replicateM' n (oneOfChar 'Data.CharSet.digit')+-- digits n = 'Control.Monad.replicateM' n (oneOfChar 'Data.CharSet.digit') -- toYmd d m y = concat [y, \"-\", m, \"-\", d] -- date = toYmd \<$> digits 2 \<* sep --              \<*> digits 2 \<* sep

@@ -2,6 +2,15 @@ {-# LANGUAGE GADTs #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ScopedTypeVariables #-}+{-# OPTIONS_HADDOCK not-home #-}++-- | This is an internal module. You probably don't need to import this.+--+-- = WARNING+--+-- Definitions in this module allow violating invariants that would otherwise be+-- guaranteed by non-internal modules. Use at your own risk!+-- module Regex.Internal.Parser   ( Parser(..)   , Node(..)@@ -14,6 +23,7 @@   , finishParser   , Foldr   , parseFoldr+  , parseNext   ) where  import Control.Applicative@@ -22,6 +32,7 @@ import Data.Maybe (isJust) import Data.Primitive.SmallArray import qualified Data.Foldable as F+import qualified GHC.Exts as X  import Regex.Internal.Regex (RE(..), Strictness(..), Greediness(..)) import Regex.Internal.Unique (Unique(..), UniqueSet)@@ -39,18 +50,18 @@   PPure   :: a -> Parser c a   PLiftA2 :: !Strictness -> !(a1 -> a2 -> a) -> !(Parser c a1) -> !(Parser c a2) -> Parser c a   PEmpty  :: Parser c a-  PAlt    :: !Unique -> !(Parser c a) -> !(Parser c a) -> !(SmallArray (Parser c a)) -> Parser c a-  PFoldGr :: !Unique -> !Strictness -> !(a -> a1 -> a) -> a -> !(Parser c a1) -> Parser c a-  PFoldMn :: !Unique -> !Strictness -> !(a -> a1 -> a) -> a -> !(Parser c a1) -> Parser c a-  PMany   :: !Unique -> !(a1 -> a) -> !(a2 -> a) -> !(a2 -> a1 -> a2) -> !a2 -> !(Parser c a1) -> Parser c a+  PAlt    :: {-# UNPACK #-} !Unique -> !(Parser c a) -> !(Parser c a) -> {-# UNPACK #-} !(SmallArray (Parser c a)) -> Parser c a+  PFoldGr :: {-# UNPACK #-} !Unique -> !Strictness -> !(a -> a1 -> a) -> a -> !(Parser c a1) -> Parser c a+  PFoldMn :: {-# UNPACK #-} !Unique -> !Strictness -> !(a -> a1 -> a) -> a -> !(Parser c a1) -> Parser c a+  PMany   :: {-# UNPACK #-} !Unique -> !(a1 -> a) -> !(a2 -> a) -> !(a2 -> a1 -> a2) -> !a2 -> !(Parser c a1) -> Parser c a  -- | A node in the NFA. Used for recognition. data Node c a where   NAccept :: a -> Node c a-  NGuard  :: !Unique -> Node c a -> Node c a+  NGuard  :: {-# UNPACK #-} !Unique -> Node c a -> Node c a   NToken  :: !(c -> Maybe a1) -> !(Node c a) -> Node c a   NEmpty  :: Node c a-  NAlt    :: !(Node c a) -> !(Node c a) -> !(SmallArray (Node c a)) -> Node c a+  NAlt    :: !(Node c a) -> !(Node c a) -> {-# UNPACK #-} !(SmallArray (Node c a)) -> Node c a -- Note that NGuard is lazy in the node. We have to introduce laziness in -- at least one place, to make a graph with loops possible. @@ -186,10 +197,10 @@   CFmap_   :: !(Node c a1) -> !(Cont c a1 a) -> Cont c b a   CLiftA2A :: !Strictness -> !(b -> a2 -> a3) -> !(Parser c a2) -> !(Cont c a3 a) -> Cont c b a   CLiftA2B :: !Strictness -> !(a1 -> b -> a3) -> a1 -> !(Cont c a3 a) -> Cont c b a-  CAlt     :: !Unique -> !(Cont c b a) -> Cont c b a-  CFoldGr  :: !Unique -> !Strictness -> !(Parser c b) -> !(a1 -> b -> a1) -> a1 -> !(Cont c a1 a) -> Cont c b a-  CFoldMn  :: !Unique -> !Strictness -> !(Parser c b) -> !(a1 -> b -> a1) -> a1 -> !(Cont c a1 a) -> Cont c b a-  CMany    :: !Unique -> !(Parser c b) -> !(b -> a2) -> !(a1 -> a2) -> !(a1 -> b -> a1) -> !a1 -> !(Cont c a2 a) -> Cont c b a+  CAlt     :: {-# UNPACK #-} !Unique -> !(Cont c b a) -> Cont c b a+  CFoldGr  :: {-# UNPACK #-} !Unique -> !Strictness -> !(Parser c b) -> !(a1 -> b -> a1) -> a1 -> !(Cont c a1 a) -> Cont c b a+  CFoldMn  :: {-# UNPACK #-} !Unique -> !Strictness -> !(Parser c b) -> !(a1 -> b -> a1) -> a1 -> !(Cont c a1 a) -> Cont c b a+  CMany    :: {-# UNPACK #-} !Unique -> !(Parser c b) -> !(b -> a2) -> !(a1 -> a2) -> !(a1 -> b -> a1) -> !a1 -> !(Cont c a2 a) -> Cont c b a  data NeedCList c a where   NeedCCons :: !(c -> Maybe b) -> !(Cont c b a) -> !(NeedCList c a) -> NeedCList c a@@ -334,16 +345,20 @@   }  -- | \(O(m \log m)\). Prepare a parser for input.-prepareParser :: Parser c a -> ParserState c a+--+-- Returns @Nothing@ if parsing has failed regardless of further input.+-- Otherwise, returns the initial @ParserState@.+prepareParser :: Parser c a -> Maybe (ParserState c a) prepareParser p = toParserState (down p CTop stepStateZero) --- | \(O(m \log m)\). Step a parser by feeding a single element @c@. Returns--- @Nothing@ if the parse has failed regardless of further input. Otherwise,--- returns an updated @ParserState@.+-- | \(O(m \log m)\). Step a parser by feeding a single element @c@.+--+-- Returns @Nothing@ if parsing has failed regardless of further input.+-- Otherwise, returns an updated @ParserState@. stepParser :: ParserState c a -> c -> Maybe (ParserState c a) stepParser ps c = case psNeed ps of   NeedCNil -> Nothing-  needs -> Just $! toParserState (go needs)+  needs -> toParserState (go needs)   where     go (NeedCCons t ct rest) =       let !pt = go rest@@ -355,21 +370,102 @@ finishParser :: ParserState c a -> Maybe a finishParser = psResult -toParserState :: StepState c a -> ParserState c a-toParserState pt = ParserState-  { psNeed = sNeed pt-  , psResult = sResult pt-  }+toParserState :: StepState c a -> Maybe (ParserState c a)+toParserState ss = case (sNeed ss, sResult ss) of+  (NeedCNil, Nothing) -> Nothing+  (need, result) -> Just $! ParserState { psNeed = need, psResult = result }  -- | A fold function. type Foldr f a = forall b. (a -> b -> b) -> b -> f -> b --- | \(O(mn \log m)\). Run a parser given a sequence @f@ and a fold of @f@.+-- | \(O(mn \log m)\). Run a parser given a sequence @f@ and a fold function.+--+-- Parses the entire sequence, not just a prefix or an substring.+-- Returns early on parse failure, if the fold can short circuit.+--+-- ==== __Examples__+--+-- @+-- import qualified Data.Vector.Generic as VG -- from vector+--+-- import Regex.Base (Parser)+-- import qualified Regex.Base as R+--+-- parseVector :: VG.Vector v c => Parser c a -> v c -> Maybe a+-- parseVector p v = R.'parseFoldr' VG.foldr p v+-- @+--+-- >>> import Control.Applicative (many)+-- >>> import qualified Data.Vector as V+-- >>> import Regex.Base (Parser)+-- >>> import qualified Regex.Base as R+-- >>>+-- >>> let p = R.compile $ many ((,) <$> R.satisfy even <*> R.satisfy odd) :: Parser Int [(Int, Int)]+-- >>> parseVector p (V.fromList [0..5])+-- Just [(0,1),(2,3),(4,5)]+-- >>> parseVector p (V.fromList [0,2..6])+-- Nothing+-- parseFoldr :: Foldr f c -> Parser c a -> f -> Maybe a-parseFoldr fr = \p xs -> fr f finishParser xs (prepareParser p)+parseFoldr fr = \p xs -> prepareParser p >>= fr f finishParser xs   where-    f c k = \ps -> stepParser ps c >>= k+    f c k = X.oneShot (\ps -> stepParser ps c >>= k) {-# INLINE parseFoldr #-}++-- | \(O(mn \log m)\). Run a parser given a \"@next@\" action.+--+-- Calls @next@ repeatedly to yield elements. A @Nothing@ is interpreted as+-- end-of-sequence.+--+-- Parses the entire sequence, not just a prefix or an substring.+-- Returns without exhausting the input on parse failure.+--+-- ==== __Examples__+--+-- @+-- import Conduit (ConduitT, await, sinkNull) -- from conduit+--+-- import Regex.Base (Parser)+-- import qualified Regex.Base as R+--+-- parseConduit :: Monad m => Parser c a -> ConduitT c x m (Maybe a)+-- parseConduit p = R.'parseNext' p await <* sinkNull+-- @+--+-- >>> import Control.Applicative (many)+-- >>> import Conduit ((.|), iterMC, runConduit, yieldMany)+-- >>> import Regex.Base (Parser)+-- >>> import qualified Regex.Base as R+-- >>>+-- >>> let p = R.compile $ many ((,) <$> R.satisfy even <*> R.satisfy odd) :: Parser Int [(Int, Int)]+-- >>> let printYieldMany xs = yieldMany xs .| iterMC print+-- >>> runConduit $ printYieldMany [0..5] .| parseConduit p+-- 0+-- 1+-- 2+-- 3+-- 4+-- 5+-- Just [(0,1),(2,3),(4,5)]+-- >>> runConduit $ printYieldMany [0,2..6] .| parseConduit p+-- 0+-- 2+-- 4+-- 6+-- Nothing+--+-- @since 0.2.0.0+parseNext :: Monad m => Parser c a -> m (Maybe c) -> m (Maybe a)+parseNext p next = case prepareParser p of+  Nothing -> pure Nothing+  Just ps -> loop ps+  where+    loop ps = next >>= \m -> case m of+      Nothing -> pure (finishParser ps)+      Just c -> case stepParser ps c of+        Nothing -> pure Nothing+        Just ps' -> loop ps'+{-# INLINE parseNext #-}  --------- -- Util

@@ -1,5 +1,9 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE GADTs #-}+{-# OPTIONS_HADDOCK not-home #-}++-- | This is an internal module. You probably don't need to import this.+-- module Regex.Internal.Regex   ( RE(..)   , Strictness(..)@@ -120,13 +124,13 @@   some re = liftA2' (:) re (many re)   many = fmap reverse . foldlMany' (flip (:)) [] --- | @(<>) = liftA2 (<>)@+-- | @(<>)@ = @liftA2 (<>)@ instance Semigroup a => Semigroup (RE c a) where   (<>) = liftA2 (<>)   sconcat = fmap sconcat . sequenceA   {-# INLINE sconcat #-} --- | @mempty = pure mempty@+-- | @mempty@ = @pure mempty@ instance Monoid a => Monoid (RE c a) where   mempty = pure mempty   mconcat = fmap mconcat . sequenceA@@ -180,6 +184,7 @@ -- Many --------- +-- | A repeating value or a finite list. data Many a   = Repeat a   -- ^ A single value repeating indefinitely   | Finite [a] -- ^ A finite list

@@ -1,8 +1,19 @@ {-# LANGUAGE BangPatterns #-}+{-# OPTIONS_HADDOCK not-home #-}++-- | This is an internal module. You probably don't need to import this. Import+-- "Regex.Text" instead.+--+-- = WARNING+--+-- Definitions in this module allow violating invariants that would otherwise be+-- guaranteed by non-internal modules. Use at your own risk!+-- module Regex.Internal.Text   (-    TextToken+    TextToken(..)   , REText+  , textTokenFoldr    , token   , satisfy@@ -49,7 +60,7 @@  import Control.Applicative import Data.Char-import Data.Foldable (foldl')+import qualified Data.Foldable as F import Data.Maybe (fromMaybe) import Numeric.Natural import Data.Text (Text)@@ -77,6 +88,10 @@ -- This module uses RE TextToken for Text regexes instead of simply RE Char to -- support Text slicing. It does mean that use cases not using slicing pay a -- small cost, but it is not worth having two separate Text regex APIs.+--+-- Slicing is made possible by the unsafeAdjacentAppend function. Of course,+-- this means that REs using it MUST NOT be used with multiple Texts, such as+-- trying to parse chunks of a lazy Text. data TextToken = TextToken   { tArr     :: {-# UNPACK #-} !TArray.Array   , tOffset  :: {-# UNPACK #-} !Int@@ -137,47 +152,47 @@ -- as described by the Unicode standard. textIgnoreCase :: Text -> REText Text textIgnoreCase t =-  T.foldr' (\c cs -> R.liftA2' adjacentAppend (ignoreCaseTokenMatch c) cs)+  T.foldr' (\c cs -> R.liftA2' unsafeAdjacentAppend (ignoreCaseTokenMatch c) cs)            (pure T.empty)            t -- See Note [Why simple case fold]  -- | Parse any @Text@. Biased towards matching more. manyText :: REText Text-manyText = R.foldlMany' adjacentAppend T.empty anyTokenMatch+manyText = R.foldlMany' unsafeAdjacentAppend T.empty anyTokenMatch  -- | Parse any non-empty @Text@. Biased towards matching more. someText :: REText Text-someText = R.liftA2' adjacentAppend anyTokenMatch manyText+someText = R.liftA2' unsafeAdjacentAppend anyTokenMatch manyText  -- | Parse any @Text@. Minimal, i.e. biased towards matching less. manyTextMin :: REText Text-manyTextMin = R.foldlManyMin' adjacentAppend T.empty anyTokenMatch+manyTextMin = R.foldlManyMin' unsafeAdjacentAppend T.empty anyTokenMatch  -- | Parse any non-empty @Text@. Minimal, i.e. biased towards matching less. someTextMin :: REText Text-someTextMin = R.liftA2' adjacentAppend anyTokenMatch manyTextMin+someTextMin = R.liftA2' unsafeAdjacentAppend anyTokenMatch manyTextMin  -- | Parse any @Text@ containing members of the @CharSet@. -- Biased towards matching more. manyTextOf :: CharSet -> REText Text-manyTextOf !cs = R.foldlMany' adjacentAppend T.empty (oneOfTokenMatch cs)+manyTextOf !cs = R.foldlMany' unsafeAdjacentAppend T.empty (oneOfTokenMatch cs)  -- | Parse any non-empty @Text@ containing members of the @CharSet@. -- Biased towards matching more. someTextOf :: CharSet -> REText Text-someTextOf !cs = R.liftA2' adjacentAppend (oneOfTokenMatch cs) (manyTextOf cs)+someTextOf !cs = R.liftA2' unsafeAdjacentAppend (oneOfTokenMatch cs) (manyTextOf cs)  -- | Parse any @Text@ containing members of the @CharSet@. -- Minimal, i.e. biased towards matching less. manyTextOfMin :: CharSet -> REText Text-manyTextOfMin !cs = R.foldlManyMin' adjacentAppend T.empty (oneOfTokenMatch cs)+manyTextOfMin !cs = R.foldlManyMin' unsafeAdjacentAppend T.empty (oneOfTokenMatch cs)  -- | Parse any non-empty @Text@ containing members of the @CharSet@. -- Minimal, i.e. biased towards matching less. someTextOfMin :: CharSet -> REText Text someTextOfMin !cs =-  R.liftA2' adjacentAppend (oneOfTokenMatch cs) (manyTextOfMin cs)+  R.liftA2' unsafeAdjacentAppend (oneOfTokenMatch cs) (manyTextOfMin cs)  ----------------- -- Numeric REs@@ -314,11 +329,14 @@       RFmap _ _ re1 -> go re1       RFmap_ _ re1 -> go re1       RPure _ -> RPure T.empty-      RLiftA2 _ _ re1 re2 -> RLiftA2 Strict adjacentAppend (go re1) (go re2)+      RLiftA2 _ _ re1 re2 ->+        RLiftA2 Strict unsafeAdjacentAppend (go re1) (go re2)       REmpty -> REmpty       RAlt re1 re2 -> RAlt (go re1) (go re2)-      RMany _ _ _ _ re1 -> RFold Strict Greedy adjacentAppend T.empty (go re1)-      RFold _ gr _ _ re1 -> RFold Strict gr adjacentAppend T.empty (go re1)+      RMany _ _ _ _ re1 ->+        RFold Strict Greedy unsafeAdjacentAppend T.empty (go re1)+      RFold _ gr _ _ re1 ->+        RFold Strict gr unsafeAdjacentAppend T.empty (go re1)  data WithMatch a = WM {-# UNPACK #-} !Text a @@ -330,10 +348,10 @@  instance Applicative WithMatch where   pure = WM T.empty-  liftA2 f (WM t1 x) (WM t2 y) = WM (adjacentAppend t1 t2) (f x y)+  liftA2 f (WM t1 x) (WM t2 y) = WM (unsafeAdjacentAppend t1 t2) (f x y)  liftA2WM' :: (a1 -> a2 -> b) -> WithMatch a1 -> WithMatch a2 -> WithMatch b-liftA2WM' f (WM t1 x) (WM t2 y) = WM (adjacentAppend t1 t2) $! f x y+liftA2WM' f (WM t1 x) (WM t2 y) = WM (unsafeAdjacentAppend t1 t2) $! f x y  -- | Rebuild the @RE@ to include the matched @Text@ alongside the result. withMatch :: REText a -> REText (Text, a)@@ -368,16 +386,18 @@ -- Parse ---------- -tokenFoldr :: (TextToken -> b -> b) -> b -> Text -> b-tokenFoldr f z (TInternal.Text a o0 l) = loop o0+textTokenFoldr :: (TextToken -> b -> b) -> b -> Text -> b+textTokenFoldr f z (TInternal.Text a o0 l) = loop o0   where     loop o | o - o0 >= l = z     loop o = case TUnsafe.iterArray a o of       TUnsafe.Iter c clen -> f (TextToken a o c) (loop (o + clen))-{-# INLINE tokenFoldr #-}+{-# INLINE textTokenFoldr #-}  -- | \(O(mn \log m)\). Parse a @Text@ with a @REText@. --+-- Parses the entire @Text@, not just a prefix or a substring.+-- -- Uses 'Regex.Text.compile', see the note there. -- -- If parsing multiple @Text@s using the same @RE@, it is wasteful to compile@@ -392,13 +412,17 @@ {-# INLINE reParse #-}  -- | \(O(mn \log m)\). Parse a @Text@ with a @ParserText@.+--+-- Parses the entire @Text@, not just a prefix or a substring. parse :: ParserText a -> Text -> Maybe a-parse = P.parseFoldr tokenFoldr+parse = P.parseFoldr textTokenFoldr  -- | \(O(mn \log m)\). Parse a @Text@ with a @ParserText@. Calls 'error' on -- parse failure. -- -- For use with parsers that are known to never fail.+--+-- Parses the entire @Text@, not just a prefix or a substring. parseSure :: ParserText a -> Text -> a parseSure p = fromMaybe parseSureError . parse p @@ -501,8 +525,8 @@   where     f a b c = reverseConcat [c,b,a] --- | \(O(mn \log m)\). Replace non-overlapping matches of the given @RE@ with--- their results.+-- | \(O(mn \log m)\). Replace all non-overlapping matches of the given @RE@+-- with their results. -- -- ==== __Examples__ --@@ -511,12 +535,12 @@ -- -- For simple replacements like above, prefer @Data.Text.'Data.Text.replace'@. ----- >>> replaceAll ("Fruit" <$ text "Time" <|> "banana" <$ text "arrow") "Time flies like an arrow"+-- >>> replaceAll ("Fruit" <$ text "Time" <|> "a banana" <$ text "an arrow") "Time flies like an arrow" -- "Fruit flies like a banana" -- -- @ -- sep = 'oneOf' "-./"--- digits n = 'toMatch' ('replicateM_' n (oneOf 'Data.CharSet.digit'))+-- digits n = 'toMatch' ('Control.Monad.replicateM_' n (oneOf 'Data.CharSet.digit')) -- toYmd d m y = mconcat [y, \"-\", m, \"-\", d] -- date = toYmd \<$> digits 2 \<* sep --              \<*> digits 2 \<* sep@@ -539,8 +563,8 @@  -- WARNING: If t1 and t2 are not empty, they must be adjacent slices of the -- same Text. In other words, sameByteArray# a1 _a2 && o1 + l1 == _o2.-adjacentAppend :: Text -> Text -> Text-adjacentAppend t1@(TInternal.Text a1 o1 l1) t2@(TInternal.Text _a2 _o2 l2)+unsafeAdjacentAppend :: Text -> Text -> Text+unsafeAdjacentAppend t1@(TInternal.Text a1 o1 l1) t2@(TInternal.Text _a2 _o2 l2)   | T.null t1 = t2   | T.null t2 = t1   | otherwise = TInternal.Text a1 o1 (l1+l2)@@ -558,7 +582,7 @@       | otherwise = reverseConcatOverflowError       where         acc' = acc + l-    len = foldl' flen 0 ts+    len = F.foldl' flen 0 ts     arr = TArray.run $ do       marr <- TArray.new len       let loop !_ [] = pure marr

@@ -1,3 +1,12 @@+{-# OPTIONS_HADDOCK not-home #-}++-- | This is an internal module. You probably don't need to import this.+--+-- = WARNING+--+-- Definitions in this module allow violating invariants that would otherwise be+-- guaranteed by non-internal modules. Use at your own risk!+-- module Regex.Internal.Unique   ( Unique(..)   , UniqueSet@@ -12,7 +21,9 @@ -- | A unique ID. Must be >= 0. newtype Unique = Unique { unUnique :: Int } --- | A set of 'Unique's. The bitmask is a set for IDs 0..63 (0..31 if 32-bit).+-- | A set of 'Unique's.++-- The bitmask is a set for IDs 0..63 on 64-bit and 0..31 on 32-bit. -- Set operations on this are very fast and speed up the common case of small -- regexes a little bit, at the cost of a little more memory. data UniqueSet = UniqueSet {-# UNPACK #-} !Int !IS.IntSet

@@ -7,7 +7,7 @@ import Control.Monad import Data.Char import qualified Data.List as L-import Data.Maybe+import Data.Maybe (isJust, isNothing) import Data.List.NonEmpty (NonEmpty(..)) import Data.Proxy import Data.Semigroup@@ -41,6 +41,9 @@     , listCombinatorTests     , stringOpTests     ]+  , testGroup "Regex.Base"+    [ earlyFailureTests+    ]   , manyTests   , charSetTests   ]@@ -1545,6 +1548,66 @@     , testCase "abc xyz abcabc" $ RL.replaceAll ("xyz" <$ RL.list "abc") "abcabc" @?= "xyzxyz"     , testCase "aba xyz ababababa" $ RL.replaceAll ("xyz" <$ RL.list "aba") "ababababa" @?= "xyzbxyzba"     , testCase "abc xyz ab" $ RL.replaceAll ("xyz" <$ RL.list "abc") "ab" @?= "ab"+    ]+  ]++---------+-- Base+---------++earlyFailureTests :: TestTree+earlyFailureTests = testGroup "Early failure"+  [ testCase "prepareParser cases" $ do+      void (R.prepareParser (R.compile empty)) @?= Nothing+      void (R.prepareParser (R.compile (pure () *> empty))) @?= Nothing+      void (R.prepareParser (R.compile (empty *> pure ()))) @?= Nothing+      void (R.prepareParser (R.compile (empty <|> empty))) @?= Nothing++      void (R.prepareParser (R.compile R.anySingle)) @?= Just ()+      void (R.prepareParser (R.compile (pure ()))) @?= Just ()++  , testGroup "stepParser"+    [ testCase ". a,aa" $+        case R.prepareParser (R.compile R.anySingle) of+          Nothing -> assertFailure "prepare"+          Just ps0 -> do+            R.finishParser ps0 @?= Nothing+            case R.stepParser ps0 'a' of+              Just ps1 -> do+                R.finishParser ps1 @?= Just 'a'+                void (R.stepParser ps1 'b') @?= Nothing+              _ -> assertFailure "step ps0"++    , testCase "* aa,aaa" $+        case R.prepareParser (R.compile (many R.anySingle)) of+          Nothing -> assertFailure "prepare"+          Just ps0 -> do+            R.finishParser ps0 @?= Just ""+            case R.stepParser ps0 'a' of+              Just ps1 -> do+                R.finishParser ps1 @?= Just "a"+                case R.stepParser ps1 'a' of+                  Just ps2 -> do+                    R.finishParser ps2 @?= Just "aa"+                    void (R.stepParser ps2 'a') @?= Just ()+                  _ -> assertFailure "step ps1"+              _ -> assertFailure "step ps0"++    , testCase "ab ax,abx" $+        case R.prepareParser (R.compile (RL.list "ab")) of+          Nothing -> assertFailure "prepare"+          Just ps0 -> do+            R.finishParser ps0 @?= Nothing+            case R.stepParser ps0 'a' of+              Just ps1 -> do+                R.finishParser ps1 @?= Nothing+                void (R.stepParser ps1 'x') @?= Nothing+                case R.stepParser ps1 'b' of+                  Just ps2 -> do+                    R.finishParser ps2 @?= Just "ab"+                    void (R.stepParser ps2 'x') @?= Nothing+                  _ -> assertFailure "step ps1"+              _ -> assertFailure "step ps0"     ]   ]