replace-attoparsec 1.0.2.0 → 1.0.3.0
raw patch · 6 files changed
+130/−53 lines, 6 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- README.md +70/−22
- replace-attoparsec.cabal +6/−5
- src/Replace/Attoparsec/ByteString.hs +8/−8
- src/Replace/Attoparsec/Text.hs +15/−17
- tests/TestByteString.hs +15/−0
- tests/TestText.hs +16/−1
README.md view
@@ -37,8 +37,9 @@ See [__replace-megaparsec__](https://hackage.haskell.org/package/replace-megaparsec) for the [__megaparsec__](http://hackage.haskell.org/package/megaparsec)-version.+version. ([__megaparsec__ is as fast as __attoparsec__.](https://github.com/mrkkrp/megaparsec#performance)) + ## Why would we want to do pattern matching and substitution with parsers instead of regular expressions? * Haskell parsers have a nicer syntax than@@ -66,10 +67,7 @@ * Regular expressions are only able to pattern-match [regular](https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy) grammers.- Parsers are able pattern-match with context-free grammers, and- even context-sensitive grammers, if needed. See below for- an example of lifting a `Parser` into a `State` monad for context-sensitive- pattern-matching.+ Attoparsec parsers are able pattern-match context-free grammers. * The replacement expression for a traditional regular expression-based substitution command is usually just a string template in which@@ -97,13 +95,13 @@ ## Parsing with `sepCap` family of parser combinators The following examples show how to match a pattern to a string of text-and deconstruct the string of text by separating it into sections+and separate it into sections which match the pattern, and sections which don't match. ### Pattern match, capture only the parsed result with `sepCap` Separate the input string into sections which can be parsed as a hexadecimal-number with a prefix `"0x"`, and sections which can't.+number with a prefix `"0x"`, and sections which can't. Parse the numbers. ```haskell let hexparser = string "0x" >> hexadecimal :: Parser Integer@@ -156,8 +154,8 @@ ### Pattern match balanced parentheses -Find the outer parentheses of all balanced nested parentheses.-Here's an example of matching a pattern that can't be expressed by a regular+Find groups of balanced nested parentheses. This is an example of a+“context-free” grammar, a pattern that can't be expressed by a regular expression. We can express the pattern with a recursive parser. ```haskell@@ -236,9 +234,9 @@ # In the Shell If we're going to have a viable `sed` replacement then we want to be able-to use it easily from the command line. This script uses the+to use it easily from the command line. This [Stack script interpreter](https://docs.haskellstack.org/en/stable/GUIDE/#script-interpreter)-To find decimal numbers in a stream and replace them with their double.+script will find decimal numbers in a stream and replace them with their double. ```haskell #!/usr/bin/env stack@@ -265,12 +263,12 @@ If you have [The Haskell Tool Stack](https://docs.haskellstack.org/en/stable/README/)-installed then you can just copy-paste this into a file named `script.hs` and+installed then you can just copy-paste this into a file named `doubler.hs` and run it. (On the first run Stack may need to download the dependencies.) ```bash-$ chmod u+x script.hs-$ echo "1 6 21 107" | ./script.hs+$ chmod u+x doubler.hs+$ echo "1 6 21 107" | ./doubler.hs 2 12 42 214 ``` @@ -281,6 +279,10 @@ <http://hackage.haskell.org/package/regex-applicative> +<http://hackage.haskell.org/package/pcre-heavy>++<http://hackage.haskell.org/package/lens-regex-pcre>+ <http://hackage.haskell.org/package/regex> <http://hackage.haskell.org/package/pipes-parse>@@ -297,23 +299,69 @@ <http://hackage.haskell.org/package/attosplit> -# Hypothetically Asked Questions+# Benchmarks -1. *Is it fast?*+The benchmark task is to find all of the one-character patterns `x` in a+text stream and replace them by a function which returns the constant+string `oo`. So, like the regex `s/x/oo/g`. - lol not really. `sepCap` is fundamentally about consuming the stream one- token at a time while we try and fail to run a parser and then- backtrack each time. That's- [a slow activity](https://markkarpov.com/megaparsec/megaparsec.html#writing-efficient-parsers).+We have two benchmark input cases, which we call __dense__ and __sparse__. -2. *Could we write this library for __parsec__?*+The __dense__ case is one megabyte of alternating spaces and `x`s+like +```+x x x x x x x x x x x x x x x x x x x x x x x x x x x x+```++The __sparse__ case is one megabyte of spaces with a single `x` in the middle+like++```+ x+```++Each benchmark program reads the input from `stdin`, replaces `x` with `oo`,+and writes the result to `stdout`. The time elapsed is measured by `perf stat`.++See [replace-benchmark](https://github.com/jamesdbrock/replace-benchmark)+for details.++| Program | dense | sparse |+| :--- | ---: | ---: |+| Python `re.sub`¹ | 89.23ms | 23.98ms |+| Perl `s///ge`² | 180.65ms | 5.60ms |+| [`Replace.Megaparsec.streamEdit`][m] `String` | 454.95ms | 375.04ms |+| [`Replace.Megaparsec.streamEdit`][m] `ByteString` | 611.98ms | 433.26ms |+| [`Replace.Megaparsec.streamEdit`][m] `Text` | 592.66ms | 353.32ms |+| [`Replace.Attoparsec.ByteString.streamEdit`][ab] | 537.57ms | 407.33ms |+| [`Replace.Attoparsec.Text.streamEdit`][at] | 549.62ms | 280.96ms |+| [`Text.Regex.Applicative.replace`][ra] `String` | 1083.98ms | 646.40ms |+| [`Text.Regex.PCRE.Heavy.gsub`][ph] `Text` | ⊥³ | 14.76ms |++¹ Python 3.7.4++² This is perl 5, version 28, subversion 2 (v5.28.2) built for x86_64-linux-thread-multi++³ Does not finish.++[m]: https://hackage.haskell.org/package/replace-megaparsec/docs/Replace-Megaparsec.html#v:streamEdit+[ab]: https://hackage.haskell.org/package/replace-attoparsec/docs/Replace-Attoparsec-ByteString.html#v:streamEdit+[at]: https://hackage.haskell.org/package/replace-attoparsec/docs/Replace-Attoparsec-Text.html#v:streamEdit+[ra]: http://hackage.haskell.org/package/regex-applicative/docs/Text-Regex-Applicative.html#v:replace+[ph]: http://hackage.haskell.org/package/pcre-heavy/docs/Text-Regex-PCRE-Heavy.html+++# Hypothetically Asked Questions++1. *Could we write this library for __parsec__?*+ No, because the [`match`](https://hackage.haskell.org/package/attoparsec/docs/Data-Attoparsec-Text.html#v:match) combinator doesn't exist for __parsec__. (I can't find it anywhere. [Can it be written?](http://www.serpentine.com/blog/2014/05/31/attoparsec/#from-strings-to-buffers-and-cursors)) -3. *Is this a good idea?*+2. *Is this a good idea?* You may have heard it suggested that monadic parsers are better when the input stream is mostly signal, and regular expressions are better
replace-attoparsec.cabal view
@@ -1,18 +1,19 @@ name: replace-attoparsec-version: 1.0.2.0+version: 1.0.3.0 cabal-version: 1.18-synopsis: Stream edit, find-and-replace with Attoparsec parsers+synopsis: Find, replace, and edit text patterns with Attoparsec parsers homepage: https://github.com/jamesdbrock/replace-attoparsec bug-reports: https://github.com/jamesdbrock/replace-attoparsec/issues license: BSD2 license-file: LICENSE-author: James Brock-maintainer: jamesbrock@gmail.com+author: James Brock <jamesbrock@gmail.com>+maintainer: James Brock <jamesbrock@gmail.com> build-type: Simple category: Parsing description: - Stream editing and find-and-replace with Attoparsec monadic parsers.+ Find text patterns, and also edit or replace the found patterns. Use+ Attoparsec monadic parsers instead of regular expressions for pattern matching. extra-doc-files: README.md , CHANGELOG.md
src/Replace/Attoparsec/ByteString.hs view
@@ -1,5 +1,8 @@ -- | -- Module : Replace.Attoparsec.ByteString+-- Copyright : ©2019 James Brock+-- License : BSD2+-- Maintainer: James Brock <jamesbrock@gmail.com> -- -- __Replace.Attoparsec__ is for finding text patterns, and also editing and -- replacing the found patterns.@@ -45,7 +48,6 @@ ) where --- import Control.Exception (SomeException, throw) import Data.Functor.Identity import Data.Bifunctor import Control.Applicative@@ -87,7 +89,6 @@ -- but, importantly, it returns the parsed result of the @sep@ parser instead -- of throwing it away. ---{-# INLINABLE sepCap #-} sepCap :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either B.ByteString a]@@ -114,6 +115,7 @@ offset2 <- getOffset when (offset1 >= offset2) empty return x+{-# INLINABLE sepCap #-} -- | -- == Find all occurences, parse and capture pattern matches@@ -129,11 +131,11 @@ -- @ -- findAllCap sep = 'sepCap' ('Data.Attoparsec.ByteString.match' sep) -- @-{-# INLINABLE findAllCap #-} findAllCap :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either B.ByteString (B.ByteString, a)] findAllCap sep = sepCap (match sep)+{-# INLINABLE findAllCap #-} -- |@@ -150,11 +152,11 @@ -- @ -- findAll sep = (fmap.fmap) ('Data.Bifunctor.second' fst) $ 'sepCap' ('Data.Attoparsec.ByteString.match' sep) -- @-{-# INLINABLE findAll #-} findAll :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either B.ByteString B.ByteString] findAll sep = (fmap.fmap) (second fst) $ sepCap (match sep)+{-# INLINABLE findAll #-} -- |@@ -185,7 +187,6 @@ -- @ -- streamEdit ('Data.Attoparsec.ByteString.match' sep) 'Data.Tuple.fst' ≡ 'Data.Function.id' -- @-{-# INLINABLE streamEdit #-} streamEdit -- :: forall s a. (Stream s, Monoid s, Tokens s ~ s, Show s, Show (Token s), Typeable s) :: Parser a@@ -197,7 +198,7 @@ -- ^ The input stream of text to be edited. -> B.ByteString streamEdit sep editor = runIdentity . streamEditT sep (Identity . editor)-+{-# INLINABLE streamEdit #-} -- | -- == Stream editor transformer@@ -211,7 +212,6 @@ -- -- If you want the @editor@ function to remember some state, -- then run this in a stateful monad.-{-# INLINABLE streamEditT #-} streamEditT :: (Monad m) => Parser a@@ -231,7 +231,7 @@ -- report that as a bug. -- (We don't use MonadFail because Identity is not a MonadFail.) (Right r) -> fmap mconcat $ traverse (either return editor) r-+{-# INLINABLE streamEditT #-} -- | Get the 'Data.Attoparsec.ByteString.Parser' ’s current offset position in the stream. --
src/Replace/Attoparsec/Text.hs view
@@ -1,5 +1,8 @@ -- | -- Module : Replace.Attoparsec.Text+-- Copyright : ©2019 James Brock+-- License : BSD2+-- Maintainer: James Brock <jamesbrock@gmail.com> -- -- __Replace.Attoparsec__ is for finding text patterns, and also editing and -- replacing the found patterns.@@ -28,6 +31,7 @@ -- See the __[replace-attoparsec](https://hackage.haskell.org/package/replace-attoparsec)__ package README for usage examples. {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE BangPatterns #-} module Replace.Attoparsec.Text (@@ -45,10 +49,8 @@ ) where --- import Control.Exception (SomeException, throw) import Data.Functor.Identity import Data.Bifunctor--- import Data.Char import Control.Applicative import Control.Monad import Data.Attoparsec.Text@@ -87,7 +89,6 @@ -- but, importantly, it returns the parsed result of the @sep@ parser instead -- of throwing it away. ---{-# INLINABLE sepCap #-} sepCap :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either T.Text a]@@ -99,17 +100,18 @@ sequenceLeft = foldr consLeft [] where consLeft :: Either l r -> [Either [l] r] -> [Either [l] r]- consLeft (Left l) ((Left ls):xs) = (Left (l:ls)):xs- consLeft (Left l) xs = (Left [l]):xs- consLeft (Right r) xs = (Right r):xs+ consLeft (Left l) ((Left ls):xs) = {-# SCC consLeft #-} (Left (l:ls)):xs+ consLeft (Left l) xs = {-# SCC consLeft #-} (Left [l]):xs+ consLeft (Right r) xs = {-# SCC consLeft #-} (Right r):xs -- If sep succeeds and consumes 0 input tokens, we must force it to fail, -- otherwise infinite loop- consumeSome p = do+ consumeSome p = {-# SCC consumeSome #-} do offset1 <- getOffset- x <- p+ x <- {-# SCC sep #-} p offset2 <- getOffset when (offset1 >= offset2) empty return x+{-# INLINABLE sepCap #-} -- | -- == Find all occurences, parse and capture pattern matches@@ -125,12 +127,11 @@ -- @ -- findAllCap sep = 'sepCap' ('Data.Attoparsec.Text.match' sep) -- @-{-# INLINABLE findAllCap #-} findAllCap :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either T.Text (T.Text, a)] findAllCap sep = sepCap (match sep)-+{-# INLINABLE findAllCap #-} -- | -- == Find all occurences@@ -146,12 +147,11 @@ -- @ -- findAll sep = (fmap.fmap) ('Data.Bifunctor.second' fst) $ 'sepCap' ('Data.Attoparsec.Text.match' sep) -- @-{-# INLINABLE findAll #-} findAll :: Parser a -- ^ The pattern matching parser @sep@ -> Parser [Either T.Text T.Text] findAll sep = (fmap.fmap) (second fst) $ sepCap (match sep)-+{-# INLINABLE findAll #-} -- | -- == Stream editor@@ -181,9 +181,7 @@ -- @ -- streamEdit ('Data.Attoparsec.Text.match' sep) 'Data.Tuple.fst' ≡ 'Data.Function.id' -- @-{-# INLINABLE streamEdit #-} streamEdit- -- :: forall s a. (Stream s, Monoid s, Tokens s ~ s, Show s, Show (Token s), Typeable s) :: Parser a -- ^ The parser @sep@ for the pattern of interest. -> (a -> T.Text)@@ -193,7 +191,7 @@ -- ^ The input stream of text to be edited. -> T.Text streamEdit sep editor = runIdentity . streamEditT sep (Identity . editor)-+{-# INLINABLE streamEdit #-} -- | -- == Stream editor transformer@@ -207,7 +205,6 @@ -- -- If you want the @editor@ function to remember some state, -- then run this in a stateful monad.-{-# INLINABLE streamEditT #-} streamEditT :: (Monad m) => Parser a@@ -227,11 +224,12 @@ -- report that as a bug. -- (We don't use MonadFail because Identity is not a MonadFail.) (Right r) -> fmap mconcat $ traverse (either return editor) r-+{-# INLINABLE streamEditT #-} -- | Get the 'Data.Attoparsec.Text.Parser' ’s current offset position in the stream. -- -- [“… you know you're in an uncomfortable state of sin :-)” — bos](https://github.com/bos/attoparsec/issues/101) getOffset :: Parser Int getOffset = AT.Parser $ \t pos more _ succ' -> succ' t pos more (AT.fromPos pos)+{-# INLINABLE getOffset #-}
tests/TestByteString.hs view
@@ -41,6 +41,8 @@ (sepCap (return (read "a" :: Int) :: Parser Int)) ("a") ([Left "a"])+ , Test $ streamEditTest "x to o" (string "x") (const "o") "x x x" "o o o"+ , Test $ streamEditTest "ordering" (string "456") (const "ABC") "123456789" "123ABC789" ] where runParserTest nam p input expected = TestInstance@@ -53,6 +55,19 @@ else return (Finished $ TestSuite.Fail $ show output ++ " ≠ " ++ show expected) , name = nam+ , tags = []+ , options = []+ , setOption = \_ _ -> Left "no options supported"+ }++ streamEditTest nam sep editor input expected = TestInstance+ { run = do+ let output = streamEdit sep editor input+ if (output == expected)+ then return (Finished Pass)+ else return (Finished $ TestSuite.Fail+ $ show output ++ " ≠ " ++ show expected)+ , name = "streamEdit " ++ nam , tags = [] , options = [] , setOption = \_ _ -> Left "no options supported"
tests/TestText.hs view
@@ -39,6 +39,8 @@ (sepCap (return (read "a" :: Int) :: Parser Int)) ("a") ([Left "a"])+ , Test $ streamEditTest "x to o" (string "x") (const "o") "x x x" "o o o"+ , Test $ streamEditTest "ordering" (string "456") (const "ABC") "123456789" "123ABC789" ] where runParserTest nam p input expected = TestInstance@@ -50,7 +52,20 @@ then return (Finished Pass) else return (Finished $ TestSuite.Fail $ show output ++ " ≠ " ++ show expected)- , name = nam+ , name = "sepCap " ++ nam+ , tags = []+ , options = []+ , setOption = \_ _ -> Left "no options supported"+ }++ streamEditTest nam sep editor input expected = TestInstance+ { run = do+ let output = streamEdit sep editor input+ if (output == expected)+ then return (Finished Pass)+ else return (Finished $ TestSuite.Fail+ $ show output ++ " ≠ " ++ show expected)+ , name = "streamEdit " ++ nam , tags = [] , options = [] , setOption = \_ _ -> Left "no options supported"