incremental-parser (empty) → 0.1
raw patch · 8 files changed
+1634/−0 lines, 8 filesdep +QuickCheckdep +basedep +bytestringsetup-changed
Dependencies added: QuickCheck, base, bytestring, text
Files
- Data/Monoid/Cancellative.hs +132/−0
- Data/Monoid/Factorial.hs +152/−0
- Data/Monoid/Null.hs +61/−0
- LICENSE.txt +674/−0
- Setup.lhs +4/−0
- Test/TestIncrementalParser.hs +201/−0
- Text/ParserCombinators/Incremental.hs +372/−0
- incremental-parser.cabal +38/−0
+ Data/Monoid/Cancellative.hs view
@@ -0,0 +1,132 @@+{- + Copyright 2011 Mario Blazevic++ This file is part of the Streaming Component Combinators (SCC) project.++ The SCC project is free software: you can redistribute it and/or modify it under the terms of the GNU General Public+ License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later+ version.++ SCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty+ of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along with SCC. If not, see+ <http://www.gnu.org/licenses/>.+-}++-- | This module defines the 'Monoid' => 'CancellativeMonoid' => 'GCDMonoid' class hierarchy.+-- ++module Data.Monoid.Cancellative (+ -- * Classes+ CancellativeMonoid, GCDMonoid,+ LeftCancellativeMonoid(..), RightCancellativeMonoid(..),+ LeftGCDMonoid(..), RightGCDMonoid(..)+ ) where++import Data.Monoid (Monoid (mappend))+import qualified Data.List as List+import qualified Data.ByteString as ByteString+import qualified Data.Text as Text+import Data.ByteString (ByteString)+import Data.Text (Text)++-- | Class of monoids with a left inverse of 'mappend', satisfying the following law:+-- +-- > mstripPrefix a (a `mappend` b) == Just b+-- > maybe b (a `mappend`) (mstripPrefix a b) == b+class Monoid m => LeftCancellativeMonoid m where+ mstripPrefix :: m -> m -> Maybe m++-- | Class of monoids with a right inverse of 'mappend', satisfying the following law:+-- +-- > mstripSuffix b (a `mappend` b) == Just a+-- > maybe b (`mappend` a) (mstripSuffix a b) == b+class Monoid m => RightCancellativeMonoid m where+ mstripSuffix :: m -> m -> Maybe m++class LeftCancellativeMonoid m => LeftGCDMonoid m where+ commonPrefix :: m -> m -> m++class RightCancellativeMonoid m => RightGCDMonoid m where+ commonSuffix :: m -> m -> m++-- | Class of monoids for which the 'mappend' operation can be reverted while satisfying the following laws:+-- +-- > mstripPrefix a (a `mappend` b) == Just b+-- > mstripSuffix b (a `mappend` b) == Just a+-- > maybe b (a `mappend`) (mstripPrefix a b) == b+-- > maybe b (`mappend` a) (mstripSuffix a b) == b+class (LeftCancellativeMonoid m, RightCancellativeMonoid m) => CancellativeMonoid m++-- | Class of monoids that allow the greatest common denominator to be found for any two given values. The operations+-- must satisfy the following laws:+-- +-- > commonPrefix (a `mappend` b) (a `mappend` c) == a `mappend` commonPrefix b c+-- > commonSuffix (a `mappend` c) (b `mappend` c) == commonSuffix a b `mappend` c+class (CancellativeMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m++-- List instances++instance Eq x => LeftCancellativeMonoid [x] where+ mstripPrefix = List.stripPrefix++instance Eq x => LeftGCDMonoid [x] where+ commonPrefix (x:xs) (y:ys) | x == y = x : commonPrefix xs ys+ commonPrefix _ _ = []++instance Eq x => RightCancellativeMonoid [x] where+ mstripSuffix s l = fmap List.reverse (mstripPrefix (List.reverse s) (List.reverse l))++instance Eq x => RightGCDMonoid [x] where+ commonSuffix xs ys = List.reverse (commonPrefix (List.reverse xs) (List.reverse ys))++instance Eq x => CancellativeMonoid [x]++instance Eq x => GCDMonoid [x]++-- ByteString instances++instance LeftCancellativeMonoid ByteString where+ mstripPrefix p l = if ByteString.isPrefixOf p l+ then Just (ByteString.drop (ByteString.length p) l)+ else Nothing++instance RightCancellativeMonoid ByteString where+ mstripSuffix s l = if ByteString.isSuffixOf s l+ then Just (ByteString.take (ByteString.length l - ByteString.length s) l)+ else Nothing++instance CancellativeMonoid ByteString++instance LeftGCDMonoid ByteString where+ commonPrefix x y = ByteString.take maxPrefixLength x+ where maxPrefixLength = prefixLength 0+ prefixLength n | ByteString.index x 0 == ByteString.index y 0 = prefixLength (succ n) + prefixLength n = n++instance RightGCDMonoid ByteString where+ commonSuffix x y = ByteString.drop minNonSuffixLength x+ where minNonSuffixLength = nonSuffixLength (ByteString.length x - 1) (ByteString.length y - 1)+ nonSuffixLength m n | ByteString.index x m == ByteString.index y n = nonSuffixLength (pred m) (pred n) + nonSuffixLength m n = m + 1++instance GCDMonoid ByteString++-- Text instances++instance LeftCancellativeMonoid Text where+ mstripPrefix p t = Text.stripPrefix p t++instance RightCancellativeMonoid Text where+ mstripSuffix s t = Text.stripSuffix s t++instance CancellativeMonoid Text++instance LeftGCDMonoid Text where+ commonPrefix x y = maybe Text.empty (\(p, _, _)-> p) (Text.commonPrefixes x y)++instance RightGCDMonoid Text where+ commonSuffix x y = Text.reverse $ commonPrefix (Text.reverse x) (Text.reverse y)++instance GCDMonoid Text
+ Data/Monoid/Factorial.hs view
@@ -0,0 +1,152 @@+{- + Copyright 2011 Mario Blazevic++ This file is part of the Streaming Component Combinators (SCC) project.++ The SCC project is free software: you can redistribute it and/or modify it under the terms of the GNU General Public+ License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later+ version.++ SCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty+ of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along with SCC. If not, see+ <http://www.gnu.org/licenses/>.+-}++-- | This module defines the 'FactorialMonoid' class.+-- ++module Data.Monoid.Factorial (+ -- * Classes+ FactorialMonoid(..),+ -- * Functions+ mbreak, mlength, mmap, mreverse, mtakeWhile, mdropWhile+ )+where++import Data.Monoid (Monoid (..))+import qualified Data.List as List+import qualified Data.ByteString as ByteString+import qualified Data.Text as Text+import Data.ByteString (ByteString)+import Data.Text (Text)++-- | Class of monoids that can be split into irreducible factors, /i.e./, atoms or primes. The methods of this class+-- satisfy the following laws:+-- +-- > mconcat . factors == id+-- > factors mempty == []+-- > all (\f-> factors f == [f]) (factors m)+-- > factors == unfoldr splitPrimePrefix == reverse . unfoldr (fmap swap . splitPrimeSuffix)+-- > primePrefix == maybe mempty fst . splitPrimePrefix+-- > primeSuffix == maybe mempty snd . splitPrimeSuffix+-- > mfoldl f f0 == foldl f f0 . factors+-- > mfoldr f f0 == foldr f f0 . factors+-- > mspan p m == (mconcat l, mconcat r) where (l, r) = span p (factors m)+-- +-- A minimal instance definition must implement 'factors' or 'splitPrimePrefix'.+class Monoid m => FactorialMonoid m where+ -- | Returns a list of all prime factors; inverse of mconcat.+ factors :: m -> [m]+ -- | The prime prefix, 'mempty' if none.+ primePrefix :: m -> m+ -- | The prime suffix, 'mempty' if none.+ primeSuffix :: m -> m+ -- | Splits the argument into its prime prefix and the remaining suffix. Returns 'Nothing' for 'mempty'.+ splitPrimePrefix :: m -> Maybe (m, m)+ -- | Splits the argument into its prime suffix and the remaining prefix. Returns 'Nothing' for 'mempty'.+ splitPrimeSuffix :: m -> Maybe (m, m)+ -- | Like 'foldl' on the list of primes.+ mfoldl :: (a -> m -> a) -> a -> m -> a+ -- | Like 'foldr' on the list of primes.+ mfoldr :: (m -> a -> a) -> a -> m -> a+ -- | Like 'span' on the list of primes.+ mspan :: (m -> Bool) -> m -> (m, m)++ factors = List.unfoldr splitPrimePrefix+ primePrefix = maybe mempty fst . splitPrimePrefix+ primeSuffix = maybe mempty snd . splitPrimeSuffix+ splitPrimePrefix x = case factors x+ of [] -> Nothing+ prefix : rest -> Just (prefix, mconcat rest)+ splitPrimeSuffix x = case factors x+ of [] -> Nothing+ fs -> Just (mconcat (List.init fs), List.last fs)+ mfoldl f f0 = List.foldl f f0 . factors+ mfoldr f f0 = List.foldr f f0 . factors+ mspan p = mfoldr f (mempty, mempty)+ where f s (prefix, suffix) = if p s + then (mappend s prefix, suffix) + else (mempty, mappend s (mappend prefix suffix))++instance FactorialMonoid [x] where+ factors xs = List.map (:[]) xs+ primePrefix [] = []+ primePrefix (x:xs) = [x]+ primeSuffix [] = []+ primeSuffix xs = [List.last xs]+ splitPrimePrefix [] = Nothing+ splitPrimePrefix (x:xs) = Just ([x], xs)+ splitPrimeSuffix [] = Nothing+ splitPrimeSuffix xs = Just (split id xs)+ where split f last@[x] = (f [], last)+ split f (x:xs) = split (f . (x:)) xs+ mfoldl _ acc [] = acc+ mfoldl f acc (x:xs) = mfoldl f (f acc [x]) xs+ mfoldr _ f0 [] = f0+ mfoldr f f0 (x:xs) = f [x] (mfoldr f f0 xs)+ mspan f = List.span (f . (:[]))++instance FactorialMonoid ByteString where+ factors x = factorize (ByteString.length x) x+ where factorize 0 xs = []+ factorize n xs = x : factorize (pred n) xs'+ where (x, xs') = ByteString.splitAt 1 xs+ primePrefix = ByteString.take 1+ primeSuffix x = ByteString.drop (ByteString.length x - 1) x+ splitPrimePrefix x = if ByteString.null x then Nothing else Just (ByteString.splitAt 1 x)+ splitPrimeSuffix x = if ByteString.null x then Nothing else Just (ByteString.splitAt (ByteString.length x - 1) x)+ mfoldl f = ByteString.foldl f'+ where f' a byte = f a (ByteString.singleton byte)+ mfoldr f = ByteString.foldr f'+ where f' byte a = f (ByteString.singleton byte) a+ mspan f x = ByteString.splitAt (findIndex 0 x) x+ where findIndex i x | ByteString.null x = i+ findIndex i x = if f (ByteString.take 1 x) then findIndex (succ i) (ByteString.drop 1 x) else i++instance FactorialMonoid Text where+ factors = Text.chunksOf 1+ primePrefix = Text.take 1+ primeSuffix x = if Text.null x then Text.empty else Text.singleton (Text.last x)+ splitPrimePrefix x = if Text.null x then Nothing else Just (Text.splitAt 1 x)+ splitPrimeSuffix x = if Text.null x then Nothing else Just (Text.splitAt (Text.length x - 1) x)+ mfoldl f = Text.foldl f'+ where f' a char = f a (Text.singleton char)+ mfoldr f = Text.foldr f'+ where f' char a = f (Text.singleton char) a+ mspan f = Text.span (f . Text.singleton)++-- | A 'List.break' equivalent.+mbreak :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)+mbreak = mspan . (not .)++-- | A 'List.length' equivalent.+mlength :: FactorialMonoid m => m -> Int+mlength = List.length . factors++-- | A 'List.map' equivalent.+mmap :: FactorialMonoid m => (m -> m) -> m -> m+mmap f = mconcat . List.map f . factors++-- | A 'List.reverse' equivalent.+mreverse :: FactorialMonoid m => m -> m+mreverse = mconcat . List.reverse . factors++-- | A 'List.takeWhile' equivalent.+mtakeWhile :: FactorialMonoid m => (m -> Bool) -> m -> m+mtakeWhile p = fst . mspan p++-- | A 'List.dropWhile' equivalent.+mdropWhile :: FactorialMonoid m => (m -> Bool) -> m -> m+mdropWhile p = snd . mspan p
+ Data/Monoid/Null.hs view
@@ -0,0 +1,61 @@+{- + Copyright 2011 Mario Blazevic++ This file is part of the Streaming Component Combinators (SCC) project.++ The SCC project is free software: you can redistribute it and/or modify it under the terms of the GNU General Public+ License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later+ version.++ SCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty+ of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along with SCC. If not, see+ <http://www.gnu.org/licenses/>.+-}++-- | This module defines the MonoidNull class.+-- ++module Data.Monoid.Null (+ -- * Classes+ MonoidNull(..)+ )+where+ +import Data.Monoid (Monoid(mempty), First(..), Last(..))+import qualified Data.List as List+import qualified Data.ByteString as ByteString+import qualified Data.Text as Text+import Data.ByteString (ByteString)+import Data.Text (Text)+ +-- | Extension of 'Monoid' that allows testing a value for equality with 'mempty'. The following law must hold:+-- +-- > mnull == (== mempty)+class Monoid m => MonoidNull m where+ mnull :: m -> Bool++instance MonoidNull [x] where+ mnull = List.null++instance MonoidNull ByteString where+ mnull = ByteString.null++instance MonoidNull Text where+ mnull = Text.null++instance (MonoidNull a, MonoidNull b) => MonoidNull (a, b) where+ mnull (a, b) = mnull a && mnull b+ +instance Monoid a => MonoidNull (Maybe a) where+ mnull Nothing = True+ mnull _ = False++instance MonoidNull (First a) where+ mnull (First Nothing) = True+ mnull _ = False++instance MonoidNull (Last a) where+ mnull (Last Nothing) = True+ mnull _ = False
+ LICENSE.txt view
@@ -0,0 +1,674 @@+ GNU GENERAL PUBLIC LICENSE+ Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.++ Preamble++ The GNU General Public License is a free, copyleft license for+software and other kinds of works.++ The licenses for most software and other practical works are designed+to take away your freedom to share and change the works. By contrast,+the GNU General Public License is intended to guarantee your freedom to+share and change all versions of a program--to make sure it remains free+software for all its users. We, the Free Software Foundation, use the+GNU General Public License for most of our software; it applies also to+any other work released this way by its authors. You can apply it to+your programs, too.++ When we speak of free software, we are referring to freedom, not+price. Our General Public Licenses are designed to make sure that you+have the freedom to distribute copies of free software (and charge for+them if you wish), that you receive source code or can get it if you+want it, that you can change the software or use pieces of it in new+free programs, and that you know you can do these things.++ To protect your rights, we need to prevent others from denying you+these rights or asking you to surrender the rights. Therefore, you have+certain responsibilities if you distribute copies of the software, or if+you modify it: responsibilities to respect the freedom of others.++ For example, if you distribute copies of such a program, whether+gratis or for a fee, you must pass on to the recipients the same+freedoms that you received. You must make sure that they, too, receive+or can get the source code. And you must show them these terms so they+know their rights.++ Developers that use the GNU GPL protect your rights with two steps:+(1) assert copyright on the software, and (2) offer you this License+giving you legal permission to copy, distribute and/or modify it.++ For the developers' and authors' protection, the GPL clearly explains+that there is no warranty for this free software. For both users' and+authors' sake, the GPL requires that modified versions be marked as+changed, so that their problems will not be attributed erroneously to+authors of previous versions.++ Some devices are designed to deny users access to install or run+modified versions of the software inside them, although the manufacturer+can do so. This is fundamentally incompatible with the aim of+protecting users' freedom to change the software. The systematic+pattern of such abuse occurs in the area of products for individuals to+use, which is precisely where it is most unacceptable. Therefore, we+have designed this version of the GPL to prohibit the practice for those+products. If such problems arise substantially in other domains, we+stand ready to extend this provision to those domains in future versions+of the GPL, as needed to protect the freedom of users.++ Finally, every program is threatened constantly by software patents.+States should not allow patents to restrict development and use of+software on general-purpose computers, but in those that do, we wish to+avoid the special danger that patents applied to a free program could+make it effectively proprietary. To prevent this, the GPL assures that+patents cannot be used to render the program non-free.++ The precise terms and conditions for copying, distribution and+modification follow.++ TERMS AND CONDITIONS++ 0. Definitions.++ "This License" refers to version 3 of the GNU General Public License.++ "Copyright" also means copyright-like laws that apply to other kinds of+works, such as semiconductor masks.++ "The Program" refers to any copyrightable work licensed under this+License. Each licensee is addressed as "you". "Licensees" and+"recipients" may be individuals or organizations.++ To "modify" a work means to copy from or adapt all or part of the work+in a fashion requiring copyright permission, other than the making of an+exact copy. The resulting work is called a "modified version" of the+earlier work or a work "based on" the earlier work.++ A "covered work" means either the unmodified Program or a work based+on the Program.++ To "propagate" a work means to do anything with it that, without+permission, would make you directly or secondarily liable for+infringement under applicable copyright law, except executing it on a+computer or modifying a private copy. Propagation includes copying,+distribution (with or without modification), making available to the+public, and in some countries other activities as well.++ To "convey" a work means any kind of propagation that enables other+parties to make or receive copies. Mere interaction with a user through+a computer network, with no transfer of a copy, is not conveying.++ An interactive user interface displays "Appropriate Legal Notices"+to the extent that it includes a convenient and prominently visible+feature that (1) displays an appropriate copyright notice, and (2)+tells the user that there is no warranty for the work (except to the+extent that warranties are provided), that licensees may convey the+work under this License, and how to view a copy of this License. If+the interface presents a list of user commands or options, such as a+menu, a prominent item in the list meets this criterion.++ 1. Source Code.++ The "source code" for a work means the preferred form of the work+for making modifications to it. "Object code" means any non-source+form of a work.++ A "Standard Interface" means an interface that either is an official+standard defined by a recognized standards body, or, in the case of+interfaces specified for a particular programming language, one that+is widely used among developers working in that language.++ The "System Libraries" of an executable work include anything, other+than the work as a whole, that (a) is included in the normal form of+packaging a Major Component, but which is not part of that Major+Component, and (b) serves only to enable use of the work with that+Major Component, or to implement a Standard Interface for which an+implementation is available to the public in source code form. A+"Major Component", in this context, means a major essential component+(kernel, window system, and so on) of the specific operating system+(if any) on which the executable work runs, or a compiler used to+produce the work, or an object code interpreter used to run it.++ The "Corresponding Source" for a work in object code form means all+the source code needed to generate, install, and (for an executable+work) run the object code and to modify the work, including scripts to+control those activities. However, it does not include the work's+System Libraries, or general-purpose tools or generally available free+programs which are used unmodified in performing those activities but+which are not part of the work. For example, Corresponding Source+includes interface definition files associated with source files for+the work, and the source code for shared libraries and dynamically+linked subprograms that the work is specifically designed to require,+such as by intimate data communication or control flow between those+subprograms and other parts of the work.++ The Corresponding Source need not include anything that users+can regenerate automatically from other parts of the Corresponding+Source.++ The Corresponding Source for a work in source code form is that+same work.++ 2. Basic Permissions.++ All rights granted under this License are granted for the term of+copyright on the Program, and are irrevocable provided the stated+conditions are met. This License explicitly affirms your unlimited+permission to run the unmodified Program. The output from running a+covered work is covered by this License only if the output, given its+content, constitutes a covered work. This License acknowledges your+rights of fair use or other equivalent, as provided by copyright law.++ You may make, run and propagate covered works that you do not+convey, without conditions so long as your license otherwise remains+in force. You may convey covered works to others for the sole purpose+of having them make modifications exclusively for you, or provide you+with facilities for running those works, provided that you comply with+the terms of this License in conveying all material for which you do+not control copyright. Those thus making or running the covered works+for you must do so exclusively on your behalf, under your direction+and control, on terms that prohibit them from making any copies of+your copyrighted material outside their relationship with you.++ Conveying under any other circumstances is permitted solely under+the conditions stated below. Sublicensing is not allowed; section 10+makes it unnecessary.++ 3. Protecting Users' Legal Rights From Anti-Circumvention Law.++ No covered work shall be deemed part of an effective technological+measure under any applicable law fulfilling obligations under article+11 of the WIPO copyright treaty adopted on 20 December 1996, or+similar laws prohibiting or restricting circumvention of such+measures.++ When you convey a covered work, you waive any legal power to forbid+circumvention of technological measures to the extent such circumvention+is effected by exercising rights under this License with respect to+the covered work, and you disclaim any intention to limit operation or+modification of the work as a means of enforcing, against the work's+users, your or third parties' legal rights to forbid circumvention of+technological measures.++ 4. Conveying Verbatim Copies.++ You may convey verbatim copies of the Program's source code as you+receive it, in any medium, provided that you conspicuously and+appropriately publish on each copy an appropriate copyright notice;+keep intact all notices stating that this License and any+non-permissive terms added in accord with section 7 apply to the code;+keep intact all notices of the absence of any warranty; and give all+recipients a copy of this License along with the Program.++ You may charge any price or no price for each copy that you convey,+and you may offer support or warranty protection for a fee.++ 5. Conveying Modified Source Versions.++ You may convey a work based on the Program, or the modifications to+produce it from the Program, in the form of source code under the+terms of section 4, provided that you also meet all of these conditions:++ a) The work must carry prominent notices stating that you modified+ it, and giving a relevant date.++ b) The work must carry prominent notices stating that it is+ released under this License and any conditions added under section+ 7. This requirement modifies the requirement in section 4 to+ "keep intact all notices".++ c) You must license the entire work, as a whole, under this+ License to anyone who comes into possession of a copy. This+ License will therefore apply, along with any applicable section 7+ additional terms, to the whole of the work, and all its parts,+ regardless of how they are packaged. This License gives no+ permission to license the work in any other way, but it does not+ invalidate such permission if you have separately received it.++ d) If the work has interactive user interfaces, each must display+ Appropriate Legal Notices; however, if the Program has interactive+ interfaces that do not display Appropriate Legal Notices, your+ work need not make them do so.++ A compilation of a covered work with other separate and independent+works, which are not by their nature extensions of the covered work,+and which are not combined with it such as to form a larger program,+in or on a volume of a storage or distribution medium, is called an+"aggregate" if the compilation and its resulting copyright are not+used to limit the access or legal rights of the compilation's users+beyond what the individual works permit. Inclusion of a covered work+in an aggregate does not cause this License to apply to the other+parts of the aggregate.++ 6. Conveying Non-Source Forms.++ You may convey a covered work in object code form under the terms+of sections 4 and 5, provided that you also convey the+machine-readable Corresponding Source under the terms of this License,+in one of these ways:++ a) Convey the object code in, or embodied in, a physical product+ (including a physical distribution medium), accompanied by the+ Corresponding Source fixed on a durable physical medium+ customarily used for software interchange.++ b) Convey the object code in, or embodied in, a physical product+ (including a physical distribution medium), accompanied by a+ written offer, valid for at least three years and valid for as+ long as you offer spare parts or customer support for that product+ model, to give anyone who possesses the object code either (1) a+ copy of the Corresponding Source for all the software in the+ product that is covered by this License, on a durable physical+ medium customarily used for software interchange, for a price no+ more than your reasonable cost of physically performing this+ conveying of source, or (2) access to copy the+ Corresponding Source from a network server at no charge.++ c) Convey individual copies of the object code with a copy of the+ written offer to provide the Corresponding Source. This+ alternative is allowed only occasionally and noncommercially, and+ only if you received the object code with such an offer, in accord+ with subsection 6b.++ d) Convey the object code by offering access from a designated+ place (gratis or for a charge), and offer equivalent access to the+ Corresponding Source in the same way through the same place at no+ further charge. You need not require recipients to copy the+ Corresponding Source along with the object code. If the place to+ copy the object code is a network server, the Corresponding Source+ may be on a different server (operated by you or a third party)+ that supports equivalent copying facilities, provided you maintain+ clear directions next to the object code saying where to find the+ Corresponding Source. Regardless of what server hosts the+ Corresponding Source, you remain obligated to ensure that it is+ available for as long as needed to satisfy these requirements.++ e) Convey the object code using peer-to-peer transmission, provided+ you inform other peers where the object code and Corresponding+ Source of the work are being offered to the general public at no+ charge under subsection 6d.++ A separable portion of the object code, whose source code is excluded+from the Corresponding Source as a System Library, need not be+included in conveying the object code work.++ A "User Product" is either (1) a "consumer product", which means any+tangible personal property which is normally used for personal, family,+or household purposes, or (2) anything designed or sold for incorporation+into a dwelling. In determining whether a product is a consumer product,+doubtful cases shall be resolved in favor of coverage. For a particular+product received by a particular user, "normally used" refers to a+typical or common use of that class of product, regardless of the status+of the particular user or of the way in which the particular user+actually uses, or expects or is expected to use, the product. A product+is a consumer product regardless of whether the product has substantial+commercial, industrial or non-consumer uses, unless such uses represent+the only significant mode of use of the product.++ "Installation Information" for a User Product means any methods,+procedures, authorization keys, or other information required to install+and execute modified versions of a covered work in that User Product from+a modified version of its Corresponding Source. The information must+suffice to ensure that the continued functioning of the modified object+code is in no case prevented or interfered with solely because+modification has been made.++ If you convey an object code work under this section in, or with, or+specifically for use in, a User Product, and the conveying occurs as+part of a transaction in which the right of possession and use of the+User Product is transferred to the recipient in perpetuity or for a+fixed term (regardless of how the transaction is characterized), the+Corresponding Source conveyed under this section must be accompanied+by the Installation Information. But this requirement does not apply+if neither you nor any third party retains the ability to install+modified object code on the User Product (for example, the work has+been installed in ROM).++ The requirement to provide Installation Information does not include a+requirement to continue to provide support service, warranty, or updates+for a work that has been modified or installed by the recipient, or for+the User Product in which it has been modified or installed. Access to a+network may be denied when the modification itself materially and+adversely affects the operation of the network or violates the rules and+protocols for communication across the network.++ Corresponding Source conveyed, and Installation Information provided,+in accord with this section must be in a format that is publicly+documented (and with an implementation available to the public in+source code form), and must require no special password or key for+unpacking, reading or copying.++ 7. Additional Terms.++ "Additional permissions" are terms that supplement the terms of this+License by making exceptions from one or more of its conditions.+Additional permissions that are applicable to the entire Program shall+be treated as though they were included in this License, to the extent+that they are valid under applicable law. If additional permissions+apply only to part of the Program, that part may be used separately+under those permissions, but the entire Program remains governed by+this License without regard to the additional permissions.++ When you convey a copy of a covered work, you may at your option+remove any additional permissions from that copy, or from any part of+it. (Additional permissions may be written to require their own+removal in certain cases when you modify the work.) You may place+additional permissions on material, added by you to a covered work,+for which you have or can give appropriate copyright permission.++ Notwithstanding any other provision of this License, for material you+add to a covered work, you may (if authorized by the copyright holders of+that material) supplement the terms of this License with terms:++ a) Disclaiming warranty or limiting liability differently from the+ terms of sections 15 and 16 of this License; or++ b) Requiring preservation of specified reasonable legal notices or+ author attributions in that material or in the Appropriate Legal+ Notices displayed by works containing it; or++ c) Prohibiting misrepresentation of the origin of that material, or+ requiring that modified versions of such material be marked in+ reasonable ways as different from the original version; or++ d) Limiting the use for publicity purposes of names of licensors or+ authors of the material; or++ e) Declining to grant rights under trademark law for use of some+ trade names, trademarks, or service marks; or++ f) Requiring indemnification of licensors and authors of that+ material by anyone who conveys the material (or modified versions of+ it) with contractual assumptions of liability to the recipient, for+ any liability that these contractual assumptions directly impose on+ those licensors and authors.++ All other non-permissive additional terms are considered "further+restrictions" within the meaning of section 10. If the Program as you+received it, or any part of it, contains a notice stating that it is+governed by this License along with a term that is a further+restriction, you may remove that term. If a license document contains+a further restriction but permits relicensing or conveying under this+License, you may add to a covered work material governed by the terms+of that license document, provided that the further restriction does+not survive such relicensing or conveying.++ If you add terms to a covered work in accord with this section, you+must place, in the relevant source files, a statement of the+additional terms that apply to those files, or a notice indicating+where to find the applicable terms.++ Additional terms, permissive or non-permissive, may be stated in the+form of a separately written license, or stated as exceptions;+the above requirements apply either way.++ 8. Termination.++ You may not propagate or modify a covered work except as expressly+provided under this License. Any attempt otherwise to propagate or+modify it is void, and will automatically terminate your rights under+this License (including any patent licenses granted under the third+paragraph of section 11).++ However, if you cease all violation of this License, then your+license from a particular copyright holder is reinstated (a)+provisionally, unless and until the copyright holder explicitly and+finally terminates your license, and (b) permanently, if the copyright+holder fails to notify you of the violation by some reasonable means+prior to 60 days after the cessation.++ Moreover, your license from a particular copyright holder is+reinstated permanently if the copyright holder notifies you of the+violation by some reasonable means, this is the first time you have+received notice of violation of this License (for any work) from that+copyright holder, and you cure the violation prior to 30 days after+your receipt of the notice.++ Termination of your rights under this section does not terminate the+licenses of parties who have received copies or rights from you under+this License. If your rights have been terminated and not permanently+reinstated, you do not qualify to receive new licenses for the same+material under section 10.++ 9. Acceptance Not Required for Having Copies.++ You are not required to accept this License in order to receive or+run a copy of the Program. Ancillary propagation of a covered work+occurring solely as a consequence of using peer-to-peer transmission+to receive a copy likewise does not require acceptance. However,+nothing other than this License grants you permission to propagate or+modify any covered work. These actions infringe copyright if you do+not accept this License. Therefore, by modifying or propagating a+covered work, you indicate your acceptance of this License to do so.++ 10. Automatic Licensing of Downstream Recipients.++ Each time you convey a covered work, the recipient automatically+receives a license from the original licensors, to run, modify and+propagate that work, subject to this License. You are not responsible+for enforcing compliance by third parties with this License.++ An "entity transaction" is a transaction transferring control of an+organization, or substantially all assets of one, or subdividing an+organization, or merging organizations. If propagation of a covered+work results from an entity transaction, each party to that+transaction who receives a copy of the work also receives whatever+licenses to the work the party's predecessor in interest had or could+give under the previous paragraph, plus a right to possession of the+Corresponding Source of the work from the predecessor in interest, if+the predecessor has it or can get it with reasonable efforts.++ You may not impose any further restrictions on the exercise of the+rights granted or affirmed under this License. For example, you may+not impose a license fee, royalty, or other charge for exercise of+rights granted under this License, and you may not initiate litigation+(including a cross-claim or counterclaim in a lawsuit) alleging that+any patent claim is infringed by making, using, selling, offering for+sale, or importing the Program or any portion of it.++ 11. Patents.++ A "contributor" is a copyright holder who authorizes use under this+License of the Program or a work on which the Program is based. The+work thus licensed is called the contributor's "contributor version".++ A contributor's "essential patent claims" are all patent claims+owned or controlled by the contributor, whether already acquired or+hereafter acquired, that would be infringed by some manner, permitted+by this License, of making, using, or selling its contributor version,+but do not include claims that would be infringed only as a+consequence of further modification of the contributor version. For+purposes of this definition, "control" includes the right to grant+patent sublicenses in a manner consistent with the requirements of+this License.++ Each contributor grants you a non-exclusive, worldwide, royalty-free+patent license under the contributor's essential patent claims, to+make, use, sell, offer for sale, import and otherwise run, modify and+propagate the contents of its contributor version.++ In the following three paragraphs, a "patent license" is any express+agreement or commitment, however denominated, not to enforce a patent+(such as an express permission to practice a patent or covenant not to+sue for patent infringement). To "grant" such a patent license to a+party means to make such an agreement or commitment not to enforce a+patent against the party.++ If you convey a covered work, knowingly relying on a patent license,+and the Corresponding Source of the work is not available for anyone+to copy, free of charge and under the terms of this License, through a+publicly available network server or other readily accessible means,+then you must either (1) cause the Corresponding Source to be so+available, or (2) arrange to deprive yourself of the benefit of the+patent license for this particular work, or (3) arrange, in a manner+consistent with the requirements of this License, to extend the patent+license to downstream recipients. "Knowingly relying" means you have+actual knowledge that, but for the patent license, your conveying the+covered work in a country, or your recipient's use of the covered work+in a country, would infringe one or more identifiable patents in that+country that you have reason to believe are valid.++ If, pursuant to or in connection with a single transaction or+arrangement, you convey, or propagate by procuring conveyance of, a+covered work, and grant a patent license to some of the parties+receiving the covered work authorizing them to use, propagate, modify+or convey a specific copy of the covered work, then the patent license+you grant is automatically extended to all recipients of the covered+work and works based on it.++ A patent license is "discriminatory" if it does not include within+the scope of its coverage, prohibits the exercise of, or is+conditioned on the non-exercise of one or more of the rights that are+specifically granted under this License. You may not convey a covered+work if you are a party to an arrangement with a third party that is+in the business of distributing software, under which you make payment+to the third party based on the extent of your activity of conveying+the work, and under which the third party grants, to any of the+parties who would receive the covered work from you, a discriminatory+patent license (a) in connection with copies of the covered work+conveyed by you (or copies made from those copies), or (b) primarily+for and in connection with specific products or compilations that+contain the covered work, unless you entered into that arrangement,+or that patent license was granted, prior to 28 March 2007.++ Nothing in this License shall be construed as excluding or limiting+any implied license or other defenses to infringement that may+otherwise be available to you under applicable patent law.++ 12. No Surrender of Others' Freedom.++ If conditions are imposed on you (whether by court order, agreement or+otherwise) that contradict the conditions of this License, they do not+excuse you from the conditions of this License. If you cannot convey a+covered work so as to satisfy simultaneously your obligations under this+License and any other pertinent obligations, then as a consequence you may+not convey it at all. For example, if you agree to terms that obligate you+to collect a royalty for further conveying from those to whom you convey+the Program, the only way you could satisfy both those terms and this+License would be to refrain entirely from conveying the Program.++ 13. Use with the GNU Affero General Public License.++ Notwithstanding any other provision of this License, you have+permission to link or combine any covered work with a work licensed+under version 3 of the GNU Affero General Public License into a single+combined work, and to convey the resulting work. The terms of this+License will continue to apply to the part which is the covered work,+but the special requirements of the GNU Affero General Public License,+section 13, concerning interaction through a network will apply to the+combination as such.++ 14. Revised Versions of this License.++ The Free Software Foundation may publish revised and/or new versions of+the GNU General Public License from time to time. Such new versions will+be similar in spirit to the present version, but may differ in detail to+address new problems or concerns.++ Each version is given a distinguishing version number. If the+Program specifies that a certain numbered version of the GNU General+Public License "or any later version" applies to it, you have the+option of following the terms and conditions either of that numbered+version or of any later version published by the Free Software+Foundation. If the Program does not specify a version number of the+GNU General Public License, you may choose any version ever published+by the Free Software Foundation.++ If the Program specifies that a proxy can decide which future+versions of the GNU General Public License can be used, that proxy's+public statement of acceptance of a version permanently authorizes you+to choose that version for the Program.++ Later license versions may give you additional or different+permissions. However, no additional obligations are imposed on any+author or copyright holder as a result of your choosing to follow a+later version.++ 15. Disclaimer of Warranty.++ THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY+APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT+HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY+OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,+THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR+PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM+IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF+ALL NECESSARY SERVICING, REPAIR OR CORRECTION.++ 16. Limitation of Liability.++ IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS+THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY+GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE+USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF+DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD+PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),+EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF+SUCH DAMAGES.++ 17. Interpretation of Sections 15 and 16.++ If the disclaimer of warranty and limitation of liability provided+above cannot be given local legal effect according to their terms,+reviewing courts shall apply local law that most closely approximates+an absolute waiver of all civil liability in connection with the+Program, unless a warranty or assumption of liability accompanies a+copy of the Program in return for a fee.++ END OF TERMS AND CONDITIONS++ How to Apply These Terms to Your New Programs++ If you develop a new program, and you want it to be of the greatest+possible use to the public, the best way to achieve this is to make it+free software which everyone can redistribute and change under these terms.++ To do so, attach the following notices to the program. It is safest+to attach them to the start of each source file to most effectively+state the exclusion of warranty; and each file should have at least+the "copyright" line and a pointer to where the full notice is found.++ <one line to give the program's name and a brief idea of what it does.>+ Copyright (C) <year> <name of author>++ This program is free software: you can redistribute it and/or modify+ it under the terms of the GNU General Public License as published by+ the Free Software Foundation, either version 3 of the License, or+ (at your option) any later version.++ This program is distributed in the hope that it will be useful,+ but WITHOUT ANY WARRANTY; without even the implied warranty of+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the+ GNU General Public License for more details.++ You should have received a copy of the GNU General Public License+ along with this program. If not, see <http://www.gnu.org/licenses/>.++Also add information on how to contact you by electronic and paper mail.++ If the program does terminal interaction, make it output a short+notice like this when it starts in an interactive mode:++ <program> Copyright (C) <year> <name of author>+ This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'.+ This is free software, and you are welcome to redistribute it+ under certain conditions; type `show c' for details.++The hypothetical commands `show w' and `show c' should show the appropriate+parts of the General Public License. Of course, your program's commands+might be different; for a GUI interface, you would use an "about box".++ You should also get your employer (if you work as a programmer) or school,+if any, to sign a "copyright disclaimer" for the program, if necessary.+For more information on this, and how to apply and follow the GNU GPL, see+<http://www.gnu.org/licenses/>.++ The GNU General Public License does not permit incorporating your program+into proprietary programs. If your program is a subroutine library, you+may consider it more useful to permit linking proprietary applications with+the library. If this is what you want to do, use the GNU Lesser General+Public License instead of this License. But first, please read+<http://www.gnu.org/philosophy/why-not-lgpl.html>.
+ Setup.lhs view
@@ -0,0 +1,4 @@+#! /usr/bin/env runhaskell+ +> import Distribution.Simple+> main = defaultMain
+ Test/TestIncrementalParser.hs view
@@ -0,0 +1,201 @@+{- + Copyright 2011 Mario Blazevic++ This file is part of the Streaming Component Combinators (SCC) project.++ The SCC project is free software: you can redistribute it and/or modify it under the terms of the GNU General Public+ License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later+ version.++ SCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty+ of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along with SCC. If not, see+ <http://www.gnu.org/licenses/>.+-}++-- | This module contains tests of "Text.ParserCombinators.Incremental" module.++{-# LANGUAGE FlexibleInstances, ScopedTypeVariables #-}++module Main where++import Control.Applicative (Alternative, empty, (*>), (<|>))+import Control.Monad (liftM, liftM2)+import Data.List (find, minimumBy, nub, sort)+import Data.Monoid (Monoid(..))+import System.Environment (getArgs)++import Test.QuickCheck (Arbitrary(..), Gen, Property, property, (==>), (.&&.), forAll, oneof, resize, sized, verbose,+ whenFail)+import Test.QuickCheck.Checkers (Binop, EqProp(..), TestBatch, isAssoc, leftId, rightId, verboseBatch)+import Test.QuickCheck.Classes (functor, monad, monoid, applicative, monadFunctor, monadApplicative, monadOr)++import Text.ParserCombinators.Incremental (Parser, feedEof, feed, completeResults,+ (><), (<<|>),+ anyToken, eof, lookAhead, notFollowedBy, satisfy, skip, token, string,+ showWith)++main = do args <- getArgs + case args of [] -> mapM_ verboseBatch tests+ _ -> mapM_ (\batch-> maybe (error ("No test batch named " ++ batch)) verboseBatch + (find ((batch ==) . fst) tests)) args++parser2 :: Parser [Bool] (String, String)+parser2 = undefined++parser3 :: Parser [Bool] (String, String, String)+parser3 = undefined++tests :: [TestBatch]+tests = [monoid parser3,+ functor parser3,+ applicative parser3,+ alternative parser2,+ monad parser3,+ monadFunctor parser2,+ monadApplicative parser2,+ monadOr parser2,+ primitives,+ lookAheadBatch,+ join]++-- | Properties to check that the 'Alternative' @m@ satisfies the alternative+-- properties+alternative :: forall m a b.+ ( Alternative m+ , Arbitrary (m a), Arbitrary (m b)+ , Show (m a), Show (m b)+ , EqProp (m a), EqProp (m b)+ ) =>+ m (a,b) -> TestBatch+alternative = const ( "alternative"+ , [ ("left zero" , property leftZeroP)+ , ("right zero" , property rightZeroP)+ , ("left identity" , leftId (<|>) (empty :: m a))+ , ("right identity", rightId (<|>) (empty :: m a))+ , ("associativity" , isAssoc ((<|>) :: Binop (m a)))+ , ("left distribution", property leftDistP)+ ]+ )+ where+ leftZeroP :: m a -> Property+ rightZeroP :: m a -> Property+ leftDistP :: m a -> m a -> m b -> Property++ leftZeroP k = (empty *> k) =-= empty+ rightZeroP k = (k *> empty) =-= (empty :: m b)+ leftDistP a b k = ((a <|> b) *> k) =-= ((a *> k) <|> (b *> k))++primitives :: TestBatch+primitives = ("primitives",+ [("anyToken EOF", feedEof (anyToken :: Parser [Bool] [Bool]) =-= empty),+ ("anyToken list", property tokenListP),+ ("token", property tokenP),+ ("token = satisfy . (==)", property tokenSatisfyP),+ ("satisfy not", property satisfyNotP),+ ("satisfy or not", property satisfyOrNotP),+ ("string", property stringP),+ ("feed eof", property feedEofP),+ ("feedEof eof", property feedEofEofP)])+ where tokenListP :: Bool -> [Bool] -> Property+ tokenP :: Bool -> [Bool] -> Property+ tokenSatisfyP :: Bool -> Property+ satisfyNotP :: (Bool -> Bool) -> Property+ satisfyOrNotP :: (Bool -> Bool) -> Property+ stringP :: [Bool] -> [Bool] -> Property+ feedEofP :: [Bool] -> Property+ feedEofEofP :: Bool+ + tokenListP x xs = canonicalResults (feed (x:xs) anyToken) =-= [([x], xs)]+ tokenP x xs = canonicalResults (feed (x:xs) (token [x])) =-= [([x], xs)]+ tokenSatisfyP x = token [x] =-= satisfy (== [x])+ satisfyNotP pred = satisfy (pred . head) =-= (notFollowedBy (satisfy (not . pred . head)) >< anyToken)+ satisfyOrNotP pred = (satisfy (pred . head) <|> satisfy (not . pred . head)) =-= anyToken+ stringP xs ys = xs /= [] ==> canonicalResults (feed (xs ++ ys) (string xs)) =-= [(xs, ys)]+ feedEofP x = x /= [] ==> feed x eof =-= (empty :: Parser [Bool] String)+ feedEofEofP = canonicalResults (feedEof eof :: Parser [Bool] String) == [([], [])]++lookAheadBatch :: TestBatch+lookAheadBatch = ("lookAhead",+ [("lookAhead", property lookAheadP),+ ("lookAhead p >> p", property lookAheadConsumeP),+ ("notFollowedBy p >< p", property lookAheadNotOrP),+ ("not not", property lookAheadNotNotP),+ ("lookAhead anyToken", property lookAheadTokenP)])+ where lookAheadP :: [Bool] -> Parser [Bool] String -> Bool+ lookAheadConsumeP :: Parser [Bool] String -> Property+ lookAheadNotOrP :: Parser [Bool] String -> Property+ lookAheadNotNotP :: Parser [Bool] String -> Property+ lookAheadTokenP :: Bool -> [Bool] -> Bool+ + lookAheadP xs p = completeResults (feed xs $ lookAhead p)+ == map (\(r, _)-> (r, xs)) (completeResults (feed xs p))+ lookAheadConsumeP p = (lookAhead p >> p) =-= p+ lookAheadNotOrP p = (notFollowedBy p >< p) =-= empty+ lookAheadNotNotP p = notFollowedBy (notFollowedBy p :: Parser [Bool] ()) =-= (skip (lookAhead p) :: Parser [Bool] ())+ lookAheadTokenP x xs = canonicalResults (feed (x:xs) (lookAhead anyToken)) == [([x], x:xs)]++instance (Eq x, Monoid x, Ord x, Show x) => EqProp (Parser [Bool] x) where+ p1 =-= p2 = sameResults (feedEof p1) (feedEof p2)+ .&&. halveSize (\s-> sized $ \n-> whenFail (print (n, s, p1, p2)) (feed s p1 =-= feed s p2)) arbitrary+ where sameResults p1 p2 = whenFail (print (canonicalResults p1) >> putStrLn " !=" >> print (canonicalResults p2)+ >> putStrLn " =>" >> print p1 >> putStrLn " !=" >> print p2)+ (canonicalResults p1 == canonicalResults p2)++join :: TestBatch+join = ("join",+ [("empty ><", property leftZeroP),+ (">< empty", property rightZeroP),+ ("(<|>) ><", property leftDistP),+ (">< (<|>)", property rightDistP),+ ("><", property joinP)])+ where leftZeroP :: Parser [Bool] String -> Property+ rightZeroP :: Parser [Bool] String -> Property+ leftDistP :: Parser [Bool] String -> Parser [Bool] String -> Parser [Bool] String -> Property+ rightDistP :: Parser [Bool] String -> Parser [Bool] String -> Parser [Bool] String -> Property+ joinP :: [Bool] -> Parser [Bool] String -> Parser [Bool] String -> Bool++ leftZeroP k = (empty >< k) =-= empty+ rightZeroP k = (k >< empty) =-= empty+ leftDistP a b k = ((a <|> b) >< k) =-= ((a >< k) <|> (b >< k))+ rightDistP k a b = (k >< (a <|> b)) =-= ((k >< a) <|> (k >< b))+ joinP input a b = canonicalResults (feed input (a >< b))+ == sort (nub [(r1 ++ r2, rest') + | (r1, rest) <- canonicalResults (feed input a),+ (r2, rest') <- completeResults (feed rest b)])++canonicalResults p = sort $ nub $ completeResults p++instance (Arbitrary r, Monoid r) => Arbitrary (Parser [Bool] r) where+ arbitrary = sized $ + \n-> resize (min 50 n) $+ oneof [return empty,+ reduceSize return arbitrary,+ splitSize (><) (liftM return arbitrary) arbitrary,+ splitSize (<|>) arbitrary arbitrary,+ splitSize (<<|>) arbitrary arbitrary,+ reduceSize (anyToken >>) arbitrary,+ reduceSize (satisfy head >>) arbitrary,+ reduceSize (satisfy (not . head) >>) arbitrary,+ reduceSize lookAhead arbitrary,+ reduceSize notFollowedBy (arbitrary :: Gen (Parser [Bool] r))]++instance (Monoid r, Show r) => Show (Parser [Bool] r) where+ show p = showWith (showBoolFun show) show p++instance Monoid Bool where+ mempty = False+ mappend = (||)++showBoolFun :: (r -> String) -> ([Bool] -> r) -> String+showBoolFun show f = "\\[b]-> if b then " ++ show (f [True]) ++ " else " ++ show (f [False])++splitSize :: (a -> b -> c) -> Gen a -> Gen b -> Gen c+splitSize f a b = sized $ \n-> liftM2 f (resize (div n 2) a) (resize (div n 2) b)++reduceSize :: (a -> b) -> Gen a -> Gen b+reduceSize f a = sized $ \n-> liftM f (resize (if n > 0 then pred n else n) a)++halveSize :: (a -> Property) -> Gen a -> Property+halveSize f a = sized $ \n-> if n < 2 then property True else resize (n `div` 2) (a >>= f)
+ Text/ParserCombinators/Incremental.hs view
@@ -0,0 +1,372 @@+{- + Copyright 2010-2011 Mario Blazevic++ This file is part of the Streaming Component Combinators (SCC) project.++ The SCC project is free software: you can redistribute it and/or modify it under the terms of the GNU General Public+ License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later+ version.++ SCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty+ of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along with SCC. If not, see+ <http://www.gnu.org/licenses/>.+-}++-- | This module defines incremental parsers. +-- +-- The exported 'Parser' type can provide partial parsing results from partial input, as long as the output is a+-- 'Monoid'. Construct a parser using the primitives and combinators, supply it with input using functions 'feed' and+-- 'feedEof', and extract the parsed output using 'results'.+-- +-- Implementation is based on Brzozowski derivatives.++{-# LANGUAGE ScopedTypeVariables, Rank2Types, ExistentialQuantification #-}++module Text.ParserCombinators.Incremental (+ -- * The Parser type+ Parser,+ -- * Using a Parser+ feed, feedEof, results, completeResults, resultPrefix,+ -- * Parser primitives+ eof, anyToken, token, satisfy, acceptAll, string, takeWhile, takeWhile1,+ -- * Parser combinators+ count, skip, option, many0, many1, manyTill,+ mapIncremental, (><), (<<|>), lookAhead, notFollowedBy, and, andThen,+ -- * Utilities+ showWith+ )+where++import Prelude hiding (and, foldl, takeWhile)+import Control.Applicative (Applicative (pure, (<*>), (*>), (<*)), Alternative (empty, (<|>), some, many), + optional, liftA2)+import Control.Monad (Functor (fmap), Monad (return, (>>=), (>>)), MonadPlus (mzero, mplus), ap, liftM2)+import Data.Maybe (fromMaybe)+import Data.Monoid (Monoid, mempty, mappend)+import Data.Monoid.Cancellative (LeftCancellativeMonoid (mstripPrefix))+import Data.Monoid.Factorial (FactorialMonoid (splitPrimePrefix, mfoldr), mspan)+import Data.Monoid.Null (MonoidNull(mnull))+import Data.Foldable (Foldable, foldl, toList)++-- | The central parser type. Its first parameter is the input monoid, the second the output.+data Parser s r = Failure+ | Result s r+ | ResultPart (r -> r) (Parser s r)+ | Choice (Parser s r) (Parser s r)+ | CommitedLeftChoice (Parser s r) (Parser s r)+ | More (s -> Parser s r)+ | forall r'. Apply (Parser s r' -> Parser s r) (Parser s r')+ | forall r'. ApplyInput (s -> Parser s r' -> Parser s r) (Parser s r')++-- | Feeds a chunk of the input to the parser.+feed :: Monoid s => s -> Parser s r -> Parser s r+feed _ Failure = Failure+feed s (Result t r) = Result (mappend t s) r+feed s (ResultPart r p) = resultPart r (feed s p)+feed s (Choice p1 p2) = feed s p1 <|> feed s p2+feed s (CommitedLeftChoice p1 p2) = feed s p1 <<|> feed s p2+feed s p@(More f) = f s+feed s (Apply f p) = f (feed s p)+feed s (ApplyInput f p) = f s (feed s p)++-- | Signals the end of the input.+feedEof :: Monoid s => Parser s r -> Parser s r+feedEof Failure = Failure+feedEof p@Result{} = p+feedEof (ResultPart r p) = prepend r (feedEof p)+ where prepend r (Result t r') = Result t (r r')+ prepend r (Choice p1 p2) = prepend r p1 <|> prepend r p2+ prepend r Failure = Failure+feedEof (Choice p1 p2) = feedEof p1 <|> feedEof p2+feedEof (CommitedLeftChoice p1 p2) = feedEof p1 <<|> feedEof p2+feedEof More{} = Failure+feedEof (Apply f p) = feedEof (f $ feedEof p)+feedEof (ApplyInput f p) = feedEof (f mempty $ feedEof p)++-- | Extracts all available parsing results. The first component of the result pair is a list of complete results+-- together with the unconsumed remainder of the input. If the parsing can continue further, the second component of the+-- pair provides the partial result prefix together with the parser for the rest of the input.+results :: Monoid r => Parser s r -> ([(r, s)], Maybe (r, Parser s r))+results Failure = ([], Nothing)+results (Result t r) = ([(r, t)], Nothing)+results (ResultPart f p) = (map prepend results', fmap prepend rest)+ where (results', rest) = results p+ prepend (x, y) = (f x, y)+results (Choice p1@Result{} p2) = (results1 ++ results2, combine rest1 rest2)+ where (results1, rest1) = results p1+ (results2, rest2) = results p2+ combine Nothing rest2 = rest2+ combine rest1 Nothing = rest1+ combine (Just (r1, p1)) (Just (r2, p2)) = + Just (mempty, Choice (ResultPart (mappend r1) p1) (ResultPart (mappend r2) p2))+results p = ([], Just (mempty, p))++-- | Like 'results', but returns only the complete results with the corresponding unconsumed inputs.+completeResults :: Parser s r -> [(r, s)]+completeResults (Result t r) = [(r, t)]+completeResults (ResultPart f p) = map (\(r, t)-> (f r, t)) (completeResults p)+completeResults (Choice p1@Result{} p2) = completeResults p1 ++ completeResults p2+completeResults _ = []++-- | Determines if there are any complete results available.+hasResult :: Parser s r -> Bool+hasResult Result{} = True+hasResult (ResultPart _ p) = hasResult p+hasResult (Choice Result{} _) = True+hasResult (CommitedLeftChoice _ p) = hasResult p+hasResult _ = False++-- | Like 'results', but returns only the partial result prefix.+resultPrefix :: Monoid r => Parser s r -> (r, Parser s r)+resultPrefix (Result t r) = (r, Result t mempty)+resultPrefix (ResultPart f p) = (f r, p')+ where (r, p') = resultPrefix p+resultPrefix p = (mempty, p)++-- | Behaves like the argument parser, but without consuming any input.+lookAhead :: Monoid s => Parser s r -> Parser s r+lookAhead p = lookAheadInto mempty p++-- | Does not consume any input; succeeds (with 'mempty' result) iff the argument parser fails.+notFollowedBy :: (Monoid s, Monoid r) => Parser s r' -> Parser s r+notFollowedBy = lookAheadNotInto mempty++lookAheadInto :: Monoid s => s -> Parser s r -> Parser s r+lookAheadInto t Failure = Failure+lookAheadInto t (Result _ r) = Result t r+lookAheadInto t (ResultPart r p) = resultPart r (lookAheadInto t p)+lookAheadInto t (More f) = More (\s-> lookAheadInto (mappend t s) (f s))+lookAheadInto t (Choice p1 p2) = lookAheadInto t p1 <|> lookAheadInto t p2+lookAheadInto t p = ApplyInput (\t' p'-> lookAheadInto (mappend t t') p') p++lookAheadNotInto :: (Monoid s, Monoid r) => s -> Parser s r' -> Parser s r+lookAheadNotInto t Failure = Result t mempty+lookAheadNotInto t (Result _ r) = Failure+lookAheadNotInto t (Choice (Result _ r) _) = Failure+lookAheadNotInto t (ResultPart r p) = lookAheadNotInto t p+lookAheadNotInto t p = ApplyInput (\t' p'-> lookAheadNotInto (mappend t t') p') p++-- | Provides a partial parsing result.+resultPart :: (r -> r) -> Parser s r -> Parser s r+resultPart _ Failure = Failure+resultPart f (Result t r) = Result t (f r)+resultPart f (Choice (Result t r) p) = Choice (Result t (f r)) (resultPart f p)+resultPart f (ResultPart g p) = ResultPart (f . g) p+resultPart f p = ResultPart f p++-- | Usage of 'fmap' destroys the incrementality of parsing results, if you need it use 'mapIncremental' instead.+instance Monoid s => Functor (Parser s) where+ fmap f Failure = Failure+ fmap f (Result t r) = Result t (f r)+ fmap f (Choice p1 p2) = fmap f p1 <|> fmap f p2+ fmap f (CommitedLeftChoice p1 p2) = fmap f p1 <<|> fmap f p2+ fmap f (More g) = More (fmap f . g)+ fmap f p = Apply (fmap f) p++-- | The '<*>' combinator requires its both arguments to provide complete parsing results, takeWhile '*>' and '<*' preserve+-- the incremental results.+instance Monoid s => Applicative (Parser s) where+ pure = Result mempty+ (<*>) = ap+ (*>) = (>>)++ Failure <* _ = Failure+ Result t r <* p = feed t p *> pure r+ ResultPart r p1 <* p2 = ResultPart r (p1 <* p2)+ Choice p1a p1b <* p2 = (p1a <* p2) <|> (p1b <* p2)+ More f <* p = More (\x-> f x <* p)+ p1 <* p2 = Apply (<* p2) p1++-- | The '<|>' choice combinator is symmetric.+instance Monoid s => Alternative (Parser s) where+ empty = Failure+ + Failure <|> p = p+ p <|> Failure = p+ More f <|> More g = More (\x-> f x <|> g x)+ p1@Result{} <|> p2 = Choice p1 p2+ Choice p1a@Result{} p1b <|> p2 = Choice p1a (p1b <|> p2)+ p1 <|> p2@Result{} = Choice p2 p1+ p1 <|> Choice p2a@Result{} p2b = Choice p2a (p1 <|> p2b)+ p1 <|> p2 = Choice p1 p2++-- | Usage of '>>=' destroys the incrementality of its left argument's parsing results, but '>>' is safe to use.+instance Monoid s => Monad (Parser s) where+ return = Result mempty++ Failure >>= _ = Failure+ Result t r >>= f = feed t (f r)+ Choice p1 p2 >>= f = (p1 >>= f) <|> (p2 >>= f)+ More f >>= g = More (\x-> f x >>= g)+ p >>= f = Apply (>>= f) p++ Failure >> _ = Failure+ Result t _ >> p = feed t p+ ResultPart r p1 >> p2 = p1 >> p2+ Choice p1a p1b >> p2 = (p1a >> p2) <|> (p1b >> p2)+ More f >> p = More (\x-> f x >> p)+ p1 >> p2 = Apply (>> p2) p1++-- | The 'MonadPlus' and the 'Alternative' instance differ: the former's 'mplus' combinator equals the asymmetric '<<|>'+-- choice.+instance Monoid s => MonadPlus (Parser s) where+ mzero = Failure+ mplus = (<<|>)++-- | Two parsers can be sequentially joined.+instance (Monoid s, Monoid r) => Monoid (Parser s r) where+ mempty = return mempty+ mappend = (><)++-- instance (Monoid s, Monoid r, Show s, Show r) => Show (Parser s r) where+-- show = showWith (show . ($ mempty)) show++showWith :: (Monoid s, Monoid r, Show s) => ((s -> Parser s r) -> String) -> (r -> String) -> Parser s r -> String+showWith sm sr Failure = "Failure"+showWith sm sr (Result t r) = "(Result (" ++ shows t ("++) " ++ sr r ++ ")")+showWith sm sr (ResultPart f p) = "(ResultPart (mappend " ++ sr (f mempty) ++ ") " ++ showWith sm sr p ++ ")"+showWith sm sr (Choice p1 p2) = "(Choice " ++ showWith sm sr p1 ++ " " ++ showWith sm sr p2 ++ ")"+showWith sm sr (CommitedLeftChoice p1 p2) = + "(CommitedLeftChoice " ++ showWith sm sr p1 ++ " " ++ showWith sm sr p2 ++ ")"+showWith sm sr (More f) = "(More $ " ++ sm f ++ ")"+showWith sm sr (Apply f p) = "Apply"+showWith sm sr (ApplyInput f p) = "ApplyInput"++-- | Like 'fmap', but capable of mapping partial results, being restricted to 'Monoid' types only.+mapIncremental :: (Monoid s, Monoid a, Monoid b) => (a -> b) -> Parser s a -> Parser s b+mapIncremental f Failure = Failure+mapIncremental f (Result t r) = Result t (f r)+mapIncremental f (ResultPart r p) = ResultPart (f (r mempty) `mappend`) (mapIncremental f p)+mapIncremental f (Choice p1 p2) = mapIncremental f p1 <|> mapIncremental f p2+mapIncremental f (CommitedLeftChoice p1 p2) = mapIncremental f p1 <<|> mapIncremental f p2+mapIncremental f (More g) = More (mapIncremental f . g)+mapIncremental f p = Apply (mapIncremental f) p++-- | Left-weighted choice. The right parser is used only if the left one utterly fails.+infixl 3 <<|>+(<<|>) :: Parser s r -> Parser s r -> Parser s r+Failure <<|> p = p+p <<|> Failure = p+p <<|> _ | hasResult p = p+More f <<|> More g = More (\x-> f x <<|> g x)+p1 <<|> p2 = CommitedLeftChoice p1 p2++-- | Join operator on parsers of same type, preserving the incremental results.+infixl 5 ><+(><) :: (Monoid s, Monoid r) => Parser s r -> Parser s r -> Parser s r+Failure >< _ = Failure+Result t r >< p = resultPart (mappend r) (feed t p)+ResultPart r p1 >< p2 = resultPart r (p1 >< p2)+Choice p1a p1b >< p2 = (p1a >< p2) <|> (p1b >< p2)+More f >< p = More (\x-> f x >< p)+p1 >< p2 = Apply (>< p2) p1++-- | A parser that fails on any input and succeeds at its end.+eof :: (MonoidNull s, Monoid r) => Parser s r+eof = notFollowedBy nonEmptyInput+ where nonEmptyInput = More $ \s-> if mnull s then nonEmptyInput else return s++-- | A parser that accepts any single input atom.+anyToken :: FactorialMonoid s => Parser s s+anyToken = More f+ where f s = case splitPrimePrefix s+ of Just (first, rest) -> Result rest first+ Nothing -> anyToken++-- | A parser that accepts a specific input atom.+token :: (Eq s, FactorialMonoid s) => s -> Parser s s+token x = satisfy (== x)++-- | A parser that accepts an input atom only if it satisfies the given predicate.+satisfy :: FactorialMonoid s => (s -> Bool) -> Parser s s+satisfy pred = p+ where p = More f+ f s = case splitPrimePrefix s+ of Just (first, rest) -> if pred first then Result rest first else Failure+ Nothing -> p++-- | A parser that consumes and returns the given prefix of the input.+string :: (LeftCancellativeMonoid s, MonoidNull s) => s -> Parser s s+string x | mnull x = mempty+string x = More (\y-> case (mstripPrefix x y, mstripPrefix y x)+ of (Just y', _) -> Result y' x+ (Nothing, Nothing) -> Failure+ (Nothing, Just x') -> string x' >> return x)++-- | A parser accepting the longest sequence of input atoms that match the given predicate; an optimized version of+-- 'many0 . satisfy'.+takeWhile :: (FactorialMonoid s, MonoidNull s) => (s -> Bool) -> Parser s s+takeWhile = fst . takeWhiles++-- | A parser accepting the longest non-empty sequence of input atoms that match the given predicate; an optimized+-- version of 'many1 . satisfy'.+takeWhile1 :: (FactorialMonoid s, MonoidNull s) => (s -> Bool) -> Parser s s+takeWhile1 = snd . takeWhiles++takeWhiles p = (takeWhile, takeWhile1)+ where takeWhile = CommitedLeftChoice takeWhile1 (return mempty)+ takeWhile1 = More f+ f s | mnull s = takeWhile1+ f s = let (prefix, suffix) = mspan p s + in if mnull prefix then Failure+ else if mnull suffix then resultPart (mappend prefix) takeWhile+ else Result suffix prefix++-- | Accepts the given number of occurrences of the argument parser.+count :: (Monoid s, Monoid r) => Int -> Parser s r -> Parser s r+count n p | n > 0 = p >< count (pred n) p+ | otherwise = mempty++-- | Like 'optional', but restricted to 'Monoid' results.+option :: (Monoid s, Monoid r) => Parser s r -> Parser s r+option p = p <|> return mempty++-- | Discards the results of the argument parser.+skip :: (Monoid s, Monoid r) => Parser s r' -> Parser s r+skip p = p >> mempty++-- | Zero or more argument occurrences like 'many', but matches the longest possible input sequence.+many0 :: (Monoid s, Monoid r) => Parser s r -> Parser s r+many0 = fst . manies++-- | One or more argument occurrences like 'some', but matches the longest possible input sequence.+many1 :: (Monoid s, Monoid r) => Parser s r -> Parser s r+many1 = snd . manies++manies p = (many0, many1)+ where many0 = CommitedLeftChoice many1 (return mempty)+ many1 = More (\s-> feed s (p >< many0))++-- | Repeats matching the first argument until the second one succeeds.+manyTill :: (Monoid s, Monoid r) => Parser s r -> Parser s r' -> Parser s r+manyTill next end = t+ where t = skip end <<|> (next >< t)++-- | A parser that accepts all input.+acceptAll :: Monoid s => Parser s s+acceptAll = CommitedLeftChoice (More $ \s-> resultPart (mappend s) acceptAll) (return mempty)++-- | Parallel parser conjunction: the combined parser keeps accepting input as long as both arguments do.+and :: (Monoid s, Monoid r1, Monoid r2) => Parser s r1 -> Parser s r2 -> Parser s (r1, r2)+Failure `and` _ = Failure+_ `and` Failure = Failure+p `and` Result _ r = fmap (\x-> (x, r)) (feedEof p)+Result _ r `and` p = fmap (\x-> (r, x)) (feedEof p)+ResultPart f p1 `and` p2 = fmap (\(r1, r2)-> (f r1, r2)) (p1 `and` p2)+p1 `and` ResultPart f p2 = fmap (\(r1, r2)-> (r1, f r2)) (p1 `and` p2)+Choice p1a p1b `and` p2 = (p1a `and` p2) <|> (p1b `and` p2)+p1 `and` Choice p2a p2b = (p1 `and` p2a) <|> (p1 `and` p2b)+More f `and` p = More (\x-> f x `and` feed x p)+p `and` More f = More (\x-> feed x p `and` f x)+p1 `and` p2 = (feedEof p1 `and` feedEof p2) <|> More (\x-> feed x p1 `and` feed x p2)++-- | Parser sequence that preserves incremental results, otherwise equivalent to 'liftA2' (,)+andThen :: (Monoid s, Monoid r1, Monoid r2) => Parser s r1 -> Parser s r2 -> Parser s (r1, r2)+Failure `andThen` _ = Failure+Result t r `andThen` p = resultPart (mappend (r, mempty)) (feed t (fmap ((,) mempty) p))+ResultPart f p1 `andThen` p2 = resultPart (\(r1, r2)-> (f r1, r2)) (p1 `andThen` p2)+Choice p1a p1b `andThen` p2 = (p1a `andThen` p2) <|> (p1b `andThen` p2)+More f `andThen` p = More (\x-> f x `andThen` p)+p1 `andThen` p2 = Apply (`andThen` p2) p1
+ incremental-parser.cabal view
@@ -0,0 +1,38 @@+Name: incremental-parser+Version: 0.1+Cabal-Version: >= 1.2+Build-Type: Simple+Synopsis: Generic parser library capable of providing partial results from partial input.+Category: Parsing+Tested-with: GHC+Description:+ This package defines yet another parser library. This one is implemented using the concept of Brzozowski derivatives,+ tweaked and optimized to work with any monoidal input type. Lists, ByteString, and Text are supported out of the box.+ If the parser result is also a monoid, the parser can provide it incrementally, before the complete input is parsed.+ +License: GPL+License-file: LICENSE.txt+Copyright: (c) 2011 Mario Blazevic+Author: Mario Blazevic+Maintainer: blamario@yahoo.com+Homepage: http://patch-tag.com/r/blamario/incremental-parser/wiki/+-- Source-repository head+-- type: darcs+-- location: http://code.haskell.org/SCC/+Flag Test+ Description: Install QuickCheck test suite+ Default: False++Executable test-incremental-parser+ Main-is: Test/TestIncrementalParser.hs+ Other-Modules: Text.ParserCombinators.Incremental,+ Data.Monoid.Cancellative, Data.Monoid.Factorial, Data.Monoid.Null+ Build-Depends: base < 5, bytestring >= 0.9 && < 1.0, text >= 0.11.0.1 && < 0.12, QuickCheck >= 2 && < 3+ if !flag(test)+ buildable: False++Library+ Exposed-Modules: Text.ParserCombinators.Incremental,+ Data.Monoid.Cancellative, Data.Monoid.Factorial, Data.Monoid.Null+ Build-Depends: base < 5, bytestring >= 0.9 && < 1.0, text >= 0.11.0.1 && < 0.12+ GHC-prof-options: -auto-all