parser-regex 0.2.0.0 → 0.2.0.1

raw patch · 9 files changed

+219/−55 lines, 9 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• LICENSE +2/−4
• parser-regex.cabal +12/−3
• src/Regex/Base.hs +129/−2
• src/Regex/Internal/Num.hs +1/−3
• src/Regex/Internal/Parser.hs +2/−2
• src/Regex/Internal/Regex.hs +1/−1
• src/Regex/List.hs +34/−20
• src/Regex/Text.hs +34/−20

@@ -1,3 +1,7 @@+### 0.2.0.1 -- 2024-12-25++* Documentation improvements+ ### 0.2.0.0 -- 2024-11-24  * Breaking changes

@@ -1,7 +1,5 @@ Copyright (c) 2024, Soumik Sarkar -All rights reserved.- Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: @@ -13,7 +11,7 @@       disclaimer in the documentation and/or other materials provided       with the distribution. -    * Neither the name of meooow25 nor the names of other+    * Neither the name of the copyright holder nor the names of other       contributors may be used to endorse or promote products derived       from this software without specific prior written permission. @@ -21,7 +19,7 @@ "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,+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

@@ -1,8 +1,7 @@ cabal-version:      2.4 name:               parser-regex-version:            0.2.0.0+version:            0.2.0.1 synopsis:           Regex based parsers-description:        Regex based parsers. homepage:           https://github.com/meooow25/parser-regex bug-reports:        https://github.com/meooow25/parser-regex/issues license:            BSD-3-Clause@@ -15,13 +14,23 @@     README.md     CHANGELOG.md +description:+    Regex based parsers. See+    .+    ["Regex.Text"]: To work with @Text@ from the @text@ library.+    .+    ["Regex.List"]: To work with @String@s or lists.+    .+    ["Regex.Base"]: To work with other sequences.+ tested-with:     GHC == 9.0.2   , GHC == 9.2.8   , GHC == 9.4.8   , GHC == 9.6.6-  , GHC == 9.8.2+  , GHC == 9.8.4   , GHC == 9.10.1+  , GHC == 9.12.1  source-repository head     type:     git

@@ -1,6 +1,9 @@ -- | This module exports base types and functions. You can use these to define--- functions to work on arbitrary sequence types. If you want to work with--- @Text@ or @String@, import and use "Regex.Text" or "Regex.List" instead.+-- functions to work on arbitrary sequence types.+--+-- If you want to work with @Text@ or @String@, import and use "Regex.Text" or+-- "Regex.List" instead.+-- module Regex.Base   (     -- * @RE@ and @Parser@@@ -57,6 +60,20 @@   , R.liftA2'   , R.foldlMany'   , R.foldlManyMin'++    -- * Additional information++    -- ** Recursive definitions+    -- $recursive-definitions++    -- ** Laziness+    -- $laziness++    -- ** Looping parsers+    -- $looping-parsers++    -- ** Performance+    -- $performance   ) where  import qualified Regex.Internal.Regex as R@@ -92,4 +109,114 @@ -- __WARNING__: If you are not sure whether to use these function, -- /don't use these functions/. Simply use @fmap@, @liftA2@, @foldlMany@ or -- @foldlManyMin@ instead.+--++-- $recursive-definitions+--+-- It is not possible to define a @RE@ recursively. If it were permitted, it+-- would be capable of parsing more than+-- [regular languages](https://en.wikipedia.org/wiki/Regular_language).+-- Unfortunately, there is no good way\* to make it impossible to write such+-- a regex in the first place. So it must be avoided by the programmer. As an+-- example, avoid this:+--+-- @+-- re :: RE Int [Int]+-- re = liftA2 (:) (single 1) re \<|> [] \<$ single 0  -- diverges!+-- @+--+-- Instead, use appropriate combinators from this module:+--+-- @+-- re = many (single 1) <* single 0+-- @+--+-- For the same reason, be cautious when using combinators from the other+-- packages on @RE@s. Make sure that they do not attempt to construct a+-- recursive @RE@.+--+-- If you find that your regex is impossible to write without recursion,+-- you are attempting to parse a non-regular language! You need a more powerful+-- parser than what this library has to offer.+--+-- \*[Unlifted datatypes](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/primitives.html#unlifted-datatypes)+-- can be used for this but they are too inconvenient to work with.+--++-- $laziness+--+-- Parsing is lazy in the result value, i.e. the @a@ in @RE c a@ or+-- @Parser c a@. In fact, for the algorithm used in this library, this laziness+-- is essential for good runtime complexity. However, there is little reason+-- to be lazy in other aspects, such as the elements of the sequence, @c@, or+-- the functions and regexes used in combinators. Functions are strict in such+-- arguments.+--+-- @+-- -- Lazy in the result+-- parseFoldr foldr (compile (pure ⊥)) [] = Just ⊥+-- parseFoldr foldr (compile (fmap (\\_ -> ⊥) (single 1))) [1] = Just ⊥+--+-- -- Strict in places like+-- single ⊥ = ⊥+-- fmap ⊥ r = ⊥+-- liftA2 f r ⊥ = ⊥+-- @+--++-- $looping-parsers+--+-- What should be the result of parsing an empty sequence with+-- @(many (pure ()))@?+--+-- Since @many r@ parses @r@ as many times as possible, and @pure ()@ succeeds+-- without consuming input, the result should arguably be the infinite list+-- @repeat ()@. Similarly, parsing an empty sequence with+-- @(foldlMany f z (pure ()))@ should diverge. Note that this applies to not+-- just @pure x@, but any regex that can succeed without consuming input, such+-- as @many x@, @manyMin x@, etc.+--+-- This library considers that such an outcome is not desirable in practice. It+-- would be surprising to get an infinite structure from a parser. So, in the+-- case that @many@ succeeds an infinite number of times, this library treats it+-- as succeeding /zero/ times.+--+-- By this rule, @(many (pure ()))@ on an empty sequence parses as @[]@ and+-- @(foldlMany f z (pure ()))@ parses as @z@.+--+-- This behavior makes it impossible to distinguish between zero parses and+-- infinite parses. To address this, an alternate combinator 'Regex.List.manyr'+-- is provided. This parses into a 'Regex.List.Many', a type that clearly+-- indicates if parsing succeeded without consuming input into an infinite list,+-- or if it succeeded a finite number of times.+--++-- $performance+--+-- This section describes some performance characteristics of this library,+-- without requiring a dive into the source code.+--+-- Parsing with a @RE@ is done in two distinct steps.+--+-- 1. A @RE@ is compiled to a @Parser@, which is a+-- [nondeterministic finite automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton)+-- (NFA), in \(O(m)\) time. \(m\) here is the size of the @RE@, which is the+-- number of nodes in its internal tree representation. The resulting @Parser@+-- has \(O(m)\) size.+-- 2. The @Parser@ is run on a sequence in \(O(mn \log m)\) time, where \(n\) is+-- the length of the sequence. This assumes that each @(c -> Maybe a)@ function+-- used to parse individual elements takes \(O(1)\) time.+--+-- /Performance tip/: Use @(\<$)@ over @(\<$>)@, and @(\<*)@\/@(*>)@ over+-- @liftA2@\/@(\<*>)@ when ignoring the result of a @RE@. Knowing the result is+-- ignored allows compiling to a faster parser.+--+-- Memory usage for parsing is \(O(nm)\), but+--+-- * If the result of a @RE@ is ignored using @(\<$)@, @(\<*)@, or @(*>)@, only+--   \(O(m)\) memory is required.+--+-- This applies even as subcomponents. So, any subcomponent @RE@ of a larger+-- @RE@ that is only recognizing a section of the list is cheaper in terms of+-- memory. --

@@ -133,9 +133,7 @@ {-# INLINE mkSignedIntRange #-}  absw :: Int -> Word-absw x = if x == minBound-         then fromIntegral (abs (x+1) + 1)-         else fromIntegral (abs x)+absw = fromIntegral . abs  ------------------- -- Parsing ranges

@@ -409,7 +409,7 @@ parseFoldr :: Foldr f c -> Parser c a -> f -> Maybe a parseFoldr fr = \p xs -> prepareParser p >>= fr f finishParser xs   where-    f c k = X.oneShot (\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.@@ -460,7 +460,7 @@   Nothing -> pure Nothing   Just ps -> loop ps   where-    loop ps = next >>= \m -> case m of+    loop !ps = next >>= \m -> case m of       Nothing -> pure (finishParser ps)       Just c -> case stepParser ps c of         Nothing -> pure Nothing

@@ -85,7 +85,7 @@ -- -- Note that, because of bias, it is /not true/ that @a \<|> b = b \<|> a@. ----- /Performance note/: Prefer the smaller of equivalent regexes, i.e. prefer+-- /Performance tip/: Prefer the smaller of equivalent regexes, i.e. prefer -- @(a \<|> b) \<*> c@ over @(a \<*> c) \<|> (b \<*> c)@. -- data RE c a where

@@ -81,7 +81,18 @@   , L.replaceAll      -- * Additional information-    -- $info++    -- ** Recursive definitions+    -- $recursive-definitions++    -- ** Laziness+    -- $laziness++    -- ** Looping parsers+    -- $looping-parsers++    -- ** Performance+    -- $performance   ) where  import qualified Regex.Internal.Regex as R@@ -104,9 +115,7 @@ -- * "Data.Traversable": @traverse@, @for@, @sequenceA@ -- --- $info------ == Recursive definitions+-- $recursive-definitions -- -- It is not possible to define a @RE@ recursively. If it were permitted, it -- would be capable of parsing more than@@ -134,16 +143,17 @@ -- you are attempting to parse a non-regular language! You need a more powerful -- parser than what this library has to offer. ----- \* [Unlifted datatypes](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/primitives.html#unlifted-datatypes)--- can serve this purpose but they are too inconvenient to work with.+-- \*[Unlifted datatypes](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/primitives.html#unlifted-datatypes)+-- can be used for this but they are too inconvenient to work with. ----- == Laziness++-- $laziness -- -- Parsing is lazy in the result value, i.e. the @a@ in @RE c a@ or -- @Parser c a@. In fact, for the algorithm used in this library, this laziness -- is essential for good runtime complexity. However, there is little reason--- to be lazy in other aspects, such as the values of the sequence, @c@, or the--- functions and regexes used in combinators. Functions are strict in such+-- to be lazy in other aspects, such as the elements of the sequence, @c@, or+-- the functions and regexes used in combinators. Functions are strict in such -- arguments. -- -- @@@ -157,7 +167,8 @@ -- liftA2 f r ⊥ = ⊥ -- @ ----- == Looping parsers++-- $looping-parsers -- -- What should be the result of @reParse (many (pure ())) ""@? --@@ -168,7 +179,7 @@ -- can succeed without consuming input, such as @many x@, @manyMin x@, etc. -- -- This library considers that such an outcome is not desirable in practice. It--- would be surprising to get an infinite structure from your parser. So, in the+-- would be surprising to get an infinite structure from a parser. So, in the -- case that @many@ succeeds an infinite number of times, this library treats it -- as succeeding /zero/ times. --@@ -181,25 +192,28 @@ -- indicates if parsing succeeded without consuming input into an infinite list, -- or if it succeeded a finite number of times. ----- == Performance++-- $performance ----- This section may be useful for someone looking to understand the performance--- of this library without diving into the source code.+-- This section describes some performance characteristics of this library,+-- without requiring a dive into the source code. -- -- Parsing with a @RE@ is done in two distinct steps. ----- 1. A @RE@ is compiled to a @Parser@ in \(O(m)\) time, where \(m\) is the size--- of the @RE@. This is a+-- 1. A @RE@ is compiled to a @Parser@, which is a -- [nondeterministic finite automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton)--- (NFA).+-- (NFA), in \(O(m)\) time. \(m\) here is the size of the @RE@, which is the+-- number of nodes in its internal tree representation. The resulting @Parser@+-- has \(O(m)\) size. -- 2. The @Parser@ is run on a list in \(O(mn \log m)\) time, where \(n\) is--- the length of the list. Assumes every @Char@ is parsed in \(O(1)\).+-- the length of the list. This assumes that each @(c -> Maybe a)@ function+-- used to parse individual elements takes \(O(1)\) time. ----- /Performance note/: Use @(\<$)@ over @(\<$>)@, and @(\<*)@\/@(*>)@ over+-- /Performance tip/: Use @(\<$)@ over @(\<$>)@, and @(\<*)@\/@(*>)@ over -- @liftA2@\/@(\<*>)@ when ignoring the result of a @RE@. Knowing the result is -- ignored allows compiling to a faster parser. ----- Memory usage for parsing is \(O(nm)\).+-- Memory usage for parsing is \(O(nm)\), but -- -- * If the result of a @RE@ is ignored using @(\<$)@, @(\<*)@, or @(*>)@, only --   \(O(m)\) memory is required.

@@ -81,7 +81,18 @@   , T.replaceAll      -- * Additional information-    -- $info++    -- ** Recursive definitions+    -- $recursive-definitions++    -- ** Laziness+    -- $laziness++    -- ** Looping parsers+    -- $looping-parsers++    -- ** Performance+    -- $performance   ) where  import qualified Regex.Internal.Regex as R@@ -104,9 +115,7 @@ -- * "Data.Traversable": @traverse@, @for@, @sequenceA@ -- --- $info------ == Recursive definitions+-- $recursive-definitions -- -- It is not possible to define a @RE@ recursively. If it were permitted, it -- would be capable of parsing more than@@ -134,16 +143,17 @@ -- you are attempting to parse a non-regular language! You need a more powerful -- parser than what this library has to offer. ----- \* [Unlifted datatypes](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/primitives.html#unlifted-datatypes)--- can serve this purpose but they are too inconvenient to work with.+-- \*[Unlifted datatypes](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/primitives.html#unlifted-datatypes)+-- can be used for this but they are too inconvenient to work with. ----- == Laziness++-- $laziness -- -- Parsing is lazy in the result value, i.e. the @a@ in @RE c a@ or -- @Parser c a@. In fact, for the algorithm used in this library, this laziness -- is essential for good runtime complexity. However, there is little reason--- to be lazy in other aspects, such as the values of the sequence, @c@, or the--- functions and regexes used in combinators. Functions are strict in such+-- to be lazy in other aspects, such as the elements of the sequence, @c@, or+-- the functions and regexes used in combinators. Functions are strict in such -- arguments. -- -- @@@ -157,7 +167,8 @@ -- liftA2 f r ⊥ = ⊥ -- @ ----- == Looping parsers++-- $looping-parsers -- -- What should be the result of @reParse (many (pure ())) ""@? --@@ -168,7 +179,7 @@ -- can succeed without consuming input, such as @many x@, @manyMin x@, etc. -- -- This library considers that such an outcome is not desirable in practice. It--- would be surprising to get an infinite structure from your parser. So, in the+-- would be surprising to get an infinite structure from a parser. So, in the -- case that @many@ succeeds an infinite number of times, this library treats it -- as succeeding /zero/ times. --@@ -181,25 +192,28 @@ -- indicates if parsing succeeded without consuming input into an infinite list, -- or if it succeeded a finite number of times. ----- == Performance++-- $performance ----- This section may be useful for someone looking to understand the performance--- of this library without diving into the source code.+-- This section describes some performance characteristics of this library,+-- without requiring a dive into the source code. -- -- Parsing with a @RE@ is done in two distinct steps. ----- 1. A @RE@ is compiled to a @Parser@ in \(O(m)\) time, where \(m\) is the size--- of the @RE@. This is a+-- 1. A @RE@ is compiled to a @Parser@, which is a -- [nondeterministic finite automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton)--- (NFA).+-- (NFA), in \(O(m)\) time. \(m\) here is the size of the @RE@, which is the+-- number of nodes in its internal tree representation. The resulting @Parser@+-- has \(O(m)\) size. -- 2. The @Parser@ is run on a @Text@ in \(O(mn \log m)\) time, where \(n\) is--- the length of the @Text@. Assumes every @Char@ is parsed in \(O(1)\).+-- the length of the @Text@. This assumes that each @(TextToken -> Maybe a)@+-- function used to parse individual elements takes \(O(1)\) time. ----- /Performance note/: Use @(\<$)@ over @(\<$>)@, and @(\<*)@\/@(*>)@ over+-- /Performance tip/: Use @(\<$)@ over @(\<$>)@, and @(\<*)@\/@(*>)@ over -- @liftA2@\/@(\<*>)@ when ignoring the result of a @RE@. Knowing the result is -- ignored allows compiling to a faster parser. ----- Memory usage for parsing is \(O(nm)\).+-- Memory usage for parsing is \(O(nm)\), but -- -- * If the result of a @RE@ is ignored using @(\<$)@, @(\<*)@, or @(*>)@, only --   \(O(m)\) memory is required.