replace-megaparsec 1.1.4.0 → 1.1.5.0
raw patch · 6 files changed
+107/−253 lines, 6 filesdep −criterionPVP ok
version bump matches the API change (PVP)
Dependencies removed: criterion
API changes (from Hackage documentation)
Files
- CHANGELOG.md +3/−0
- LICENSE +21/−6
- README.md +68/−34
- bench/BenchUnit.hs +0/−156
- replace-megaparsec.cabal +6/−51
- src/Replace/Megaparsec.hs +9/−6
CHANGELOG.md view
@@ -15,3 +15,6 @@ * In `streamEditT`, replace `fold` with `mconcat`. The benchmarks now show linear scaling instead of quadratic. +## 1.1.5.0 -- 2019-10-08++* Move benchmarks to [__replace-benchmark__](https://github.com/jamesdbrock/replace-benchmark)
LICENSE view
@@ -1,11 +1,26 @@-BSD-2-Clause- Copyright (c) 2019, James Brock+All rights reserved. -Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:+Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met: -1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.+1. Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer. -2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.+2. Redistributions in binary form must reproduce the above copyright+ notice, this list of conditions and the following disclaimer in the+ documentation and/or other materials provided with the+ distribution. -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
README.md view
@@ -7,6 +7,7 @@ * [Usage Examples](#usage-examples) * [In the Shell](#in-the-shell) * [Alternatives](#alternatives)+* [Benchmarks](#benchmarks) * [Hypothetically Asked Questions](#hypothetically-asked-questions) __replace-megaparsec__ is for finding text patterns, and also editing and@@ -37,7 +38,7 @@ See [__replace-attoparsec__](https://hackage.haskell.org/package/replace-attoparsec) for the [__attoparsec__](http://hackage.haskell.org/package/attoparsec)-version. ([__megaparsec__ is as fast as __attoparsec__](https://github.com/mrkkrp/megaparsec#performance)).+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? @@ -66,7 +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+ Megaparsec parsers are able pattern-match 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.@@ -95,13 +96,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 = chunk "0x" >> hexadecimal :: Parsec Void String Integer@@ -154,8 +155,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@@ -237,7 +238,8 @@ that it can match successfully only on the third time that it finds a letter. To enable the parser to remember how many times it has run, we'll compose the parser with a `State` monad from-the `mtl` package. (Run in `ghci` with `cabal v2-repl -b mtl`).+the `mtl` package. (Run in `ghci` with `cabal v2-repl -b mtl`). Because it has+stateful memory, this parser is an example of a “context-sensitive” grammar. ```haskell import qualified Control.Monad.State.Strict as MTL@@ -260,9 +262,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@@ -284,12 +286,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 ``` @@ -300,6 +302,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>@@ -312,41 +318,69 @@ <http://hackage.haskell.org/package/template> -# 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__. - Consider a 1 megabyte file that consists of `"foo"` every ten bytes:+The __dense__ case is one megabyte of alternating spaces and `x`s+like - ```- foo foo foo foo foo foo ...- ```+```+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+``` - We want to replace all the `"foo"` with `"bar"`. We would expect `sed`- to be about at the upper bound of speed for this task, so here- are the `perf` results when we compare `sed s/foo/bar/g`- to __replace-megaparsec__ with some different stream types.+The __sparse__ case is one megabyte of spaces with a single `x` in the middle+like - | Method | `perf task-clock` |- | :--- | ---: |- | `sed` | 39 msec |- | `streamEdit String` | 793 msec |- | `streamEdit ByteString` | 513 msec |- | `streamEdit Text` | 428 msec |+```+ x+``` -2. *Could we write this library for __parsec__?*+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/megaparsec/docs/Text-Megaparsec.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
− bench/BenchUnit.hs
@@ -1,156 +0,0 @@-{-# LANGUAGE OverloadedStrings #-}-{-# LANGUAGE BangPatterns #-}--import Text.Megaparsec-import Replace.Megaparsec-import Criterion.Main-import Criterion.Types-import qualified Data.ByteString as B-import qualified Data.ByteString.Lazy as BL-import qualified Data.ByteString.Builder as B.Builder-import qualified Data.Text as T-import qualified Data.Text.Lazy as TL-import Data.Void--fooStringM :: String-fooStringM = take 1000000 $ cycle " foo" -- a million bytes of foos-fooString10K :: String-fooString10K = take 10000 fooStringM-fooString100K :: String-fooString100K = take 100000 fooStringM--fooByteStringM :: B.ByteString-fooByteStringM = BL.toStrict fooByteStringLM-fooByteString10K :: B.ByteString-fooByteString10K = B.take 10000 fooByteStringM-fooByteString100K :: B.ByteString-fooByteString100K = B.take 100000 fooByteStringM--fooByteStringLM :: BL.ByteString-fooByteStringLM = B.Builder.toLazyByteString $ B.Builder.string8 fooStringM-fooByteStringL10K :: BL.ByteString-fooByteStringL10K = BL.take 10000 fooByteStringLM-fooByteStringL100K :: BL.ByteString-fooByteStringL100K = BL.take 100000 fooByteStringLM--fooTextM :: T.Text-fooTextM = T.pack fooStringM-fooText10K :: T.Text-fooText10K = T.take 10000 fooTextM-fooText100K :: T.Text-fooText100K = T.take 100000 fooTextM--fooTextLM :: TL.Text-fooTextLM = TL.pack fooStringM-fooTextL10K :: TL.Text-fooTextL10K = TL.take 10000 fooTextLM-fooTextL100K :: TL.Text-fooTextL100K = TL.take 100000 fooTextLM--main :: IO ()-main = defaultMainWith (defaultConfig- { reportFile = Just "criterion-report.html"- , resamples = 100- })- [ bgroup "String"- [ bench "sepCap 10,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void String String)))- fooString10K- , bench "streamEdit 10,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void String String) (const "bar"))- fooString10K- , bench "sepCap 100,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void String String)))- fooString100K- , bench "streamEdit 100,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void String String) (const "bar"))- fooString100K- , bench "sepCap 1,000,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void String String)))- fooStringM- , bench "streamEdit 1,000,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void String String) (const "bar"))- fooStringM- ]- , bgroup "ByteString.Strict"- [ bench "sepCap 10,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void B.ByteString B.ByteString)))- fooByteString10K- , bench "streamEdit 10,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void B.ByteString B.ByteString) (const "bar"))- fooByteString10K- , bench "sepCap 100,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void B.ByteString B.ByteString)))- fooByteString100K- , bench "streamEdit 100,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void B.ByteString B.ByteString) (const "bar"))- fooByteString100K- , bench "sepCap 1,000,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void B.ByteString B.ByteString)))- fooByteStringM- , bench "streamEdit 1,000,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void B.ByteString B.ByteString) (const "bar"))- fooByteStringM- ]- , bgroup "ByteString.Lazy"- [ bench "sepCap 10,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString)))- fooByteStringL10K- , bench "streamEdit 10,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString) (const "bar"))- fooByteStringL10K- , bench "sepCap 100,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString)))- fooByteStringL100K- , bench "streamEdit 100,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString) (const "bar"))- fooByteStringL100K- , bench "sepCap 1,000,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString)))- fooByteStringLM- , bench "streamEdit 1,000,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void BL.ByteString BL.ByteString) (const "bar"))- fooByteStringLM- ]- , bgroup "Text.Strict"- [ bench "sepCap 10,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void T.Text T.Text)))- fooText10K- , bench "streamEdit 10,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void T.Text T.Text) (const "bar"))- fooText10K- , bench "sepCap 100,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void T.Text T.Text)))- fooText100K- , bench "streamEdit 100,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void T.Text T.Text) (const "bar"))- fooText100K- , bench "sepCap 1,000,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void T.Text T.Text)))- fooTextM- , bench "streamEdit 1,000,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void T.Text T.Text) (const "bar"))- fooTextM- ]- , bgroup "Text.Lazy"- [ bench "sepCap 10,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void TL.Text TL.Text)))- fooTextL10K- , bench "streamEdit 10,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void TL.Text TL.Text) (const "bar"))- fooTextL10K- , bench "sepCap 100,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void TL.Text TL.Text)))- fooTextL100K- , bench "streamEdit 100,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void TL.Text TL.Text) (const "bar"))- fooTextL100K- , bench "sepCap 1,000,000" $ whnf- (parseMaybe (sepCap (chunk "foo" :: Parsec Void TL.Text TL.Text)))- fooTextLM- , bench "streamEdit 1,000,000" $ whnf- (streamEdit (chunk "foo" :: Parsec Void TL.Text TL.Text) (const "bar"))- fooTextLM- ]- ]-
replace-megaparsec.cabal view
@@ -1,18 +1,19 @@ name: replace-megaparsec-version: 1.1.4.0+version: 1.1.5.0 cabal-version: 1.18-synopsis: Stream edit, find-and-replace with Megaparsec parsers+synopsis: Find, replace, and edit text patterns with Megaparsec parsers homepage: https://github.com/jamesdbrock/replace-megaparsec bug-reports: https://github.com/jamesdbrock/replace-megaparsec/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 Megaparsec monadic parsers.+ Find text patterns, and also edit or replace the found patterns. Use+ Megaparsec monadic parsers instead of regular expressions for pattern matching. extra-doc-files: README.md , CHANGELOG.md@@ -63,50 +64,4 @@ , Cabal , bytestring ghc-options: -Wall----- Disable these executables for now, they clutter up--- the dependency list and `cabal v2-build`.------ executable bench-string--- main-is: BenchString.hs--- hs-source-dirs: bench--- default-language: Haskell2010--- build-depends: base >= 4.0 && < 5.0--- , megaparsec--- , replace-megaparsec--- ghc-options: -O2 -Wall------ executable bench-text--- main-is: BenchText.hs--- hs-source-dirs: bench--- default-language: Haskell2010--- build-depends: base >= 4.0 && < 5.0--- , megaparsec--- , replace-megaparsec--- , text--- ghc-options: -O2 -Wall------ executable bench-bytestring--- main-is: BenchByteString.hs--- hs-source-dirs: bench--- default-language: Haskell2010--- build-depends: base >= 4.0 && < 5.0--- , megaparsec--- , replace-megaparsec--- , bytestring--- ghc-options: -O2 -Wall--benchmark bench-unit- main-is: BenchUnit.hs- hs-source-dirs: bench- type: exitcode-stdio-1.0- default-language: Haskell2010- build-depends: base >= 4.0 && < 5.0- , megaparsec- , replace-megaparsec- , text- , bytestring- , criterion- ghc-options: -O2 -Wall
src/Replace/Megaparsec.hs view
@@ -1,5 +1,8 @@ -- | -- Module : Replace.Megaparsec+-- Copyright : ©2019 James Brock+-- License : BSD2+-- Maintainer: James Brock <jamesbrock@gmail.com> -- -- __Replace.Megaparsec__ is for finding text patterns, and also editing and -- replacing the found patterns.@@ -98,17 +101,17 @@ $ many $ fmap Right (try $ consumeSome sep) <|> fmap Left anySingle where sequenceLeft :: [Either l r] -> [Either [l] r]- sequenceLeft = foldr consLeft []+ sequenceLeft = {-# SCC 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