regex-genex 0.3.0 → 0.3.1

raw patch · 4 files changed

+39/−23 lines, 4 filesdep +logictdep +stream-monaddep −control-monad-omegaPVP ok

version bump matches the API change (PVP)

Dependencies added: logict, stream-monad

Dependencies removed: control-monad-omega

API changes (from Hackage documentation)

Files

regex-genex.cabal +3/−3
src/Regex/Genex.hs +16/−5
src/Regex/Genex/Normalize.hs +2/−2
src/Regex/Genex/Pure.hs +18/−13

regex-genex.cabal view

@@ -1,5 +1,5 @@ Name            : regex-genex-Version         : 0.3.0+Version         : 0.3.1 license         : OtherLicense license-file    : LICENSE cabal-version   : >= 1.6@@ -20,14 +20,14 @@     other-modules:    Regex.Genex.Pure     extensions      : ImplicitParams, NamedFieldPuns, ParallelListComp, PatternGuards, RecordWildCards     build-depends:-        base >= 3 && < 5, haskell98, mtl, containers, sbv, regex-tdfa, control-monad-omega, text+        base >= 3 && < 5, haskell98, mtl, containers, sbv, regex-tdfa, stream-monad, text, logict  executable genex     main-is:            Main.hs     hs-source-dirs:     . src     extensions      : ImplicitParams, NamedFieldPuns, ParallelListComp, PatternGuards, RecordWildCards     build-depends:-        base >= 3 && < 5, haskell98, mtl, containers, sbv, regex-tdfa, control-monad-omega, text+        base >= 3 && < 5, haskell98, mtl, containers, sbv, regex-tdfa  source-repository head   type:     git

src/Regex/Genex.hs view

@@ -1,4 +1,15 @@ {-# LANGUAGE ImplicitParams, NamedFieldPuns, ParallelListComp, PatternGuards #-}+{-|++This module and the accompanying 'genex' program finds all permutations+of strings that matches every input regular expressions, ordered from+shortest to longest, with full support for back references ('\1' .. '\9')+and word boundaries ('\b').++It requires the @yices@ binary in PATH; please download it from:+<http://yices.csl.sri.com/download-yices2.shtml>++-} module Regex.Genex (Model(..), genex, genexPure, genexPrint, genexModels) where import Data.SBV import Data.SBV.Internals (SBV)@@ -15,7 +26,6 @@ import Data.IntMap (IntMap) import qualified Data.IntMap as IntMap import System.IO.Unsafe (unsafeInterleaveIO)-import Regex.Genex.Normalize (normalize)  -- | Given a list of regular repressions, returns all possible strings that matches every one of them. -- Guarantees to return shorter strings before longer ones.@@ -29,17 +39,18 @@     }     deriving (Show, Eq, Ord) --- | Same as @genex@, but with the entire model returned instead.+-- | Same as 'genex', but with the entire model returned instead. genexModels :: [String] -> IO [Model] genexModels = genexWith (getStringWith id) --- | Same as @genexModels@, but print the models to standard output instead.+-- | Same as 'genexModels', but print the models to standard output instead. genexPrint :: [String] -> IO () genexPrint = genexWith displayString --- | A pure and much faster variant of @genex@, but without support for back-references, anchors or word boundaries.+-- | A pure and much faster variant of 'genex', but without support for+--   back-references, anchors or word boundaries. -- Does not guarantee orders about length of strings.--- Does not depend on the external 'yices' SMT solver.+-- Does not depend on the external @yices@ SMT solver. genexPure :: [String] -> [String] genexPure = Pure.genexPure

src/Regex/Genex/Normalize.hs view

@@ -9,8 +9,8 @@  type BackReferences = IntSet --- | Normalize a regex into "strong star normal form", as defined in the paper---   "Simplifying Regular Expressions: A Quantitative Perspective".+-- | Normalize a regex into @strong star normal form@, as defined in the paper+--   @Simplifying Regular Expressions: A Quantitative Perspective@. normalize :: BackReferences -> Pattern -> Pattern normalize refs p = black $ let ?refs = refs in simplify p

src/Regex/Genex/Pure.hs view

@@ -1,13 +1,18 @@+{-# LANGUAGE RecordWildCards, NamedFieldPuns #-} module Regex.Genex.Pure (genexPure) where+import Control.Monad.Logic.Class (MonadLogic(..)) import qualified Data.Text as T import qualified Data.IntSet as IntSet import qualified Data.Set as Set import Data.List (intersect, (\\)) import Control.Monad-import Control.Monad.Omega+import Control.Monad.Stream import Regex.Genex.Normalize (normalize)+import Debug.Trace import Text.Regex.TDFA.Pattern import Text.Regex.TDFA.ReadRegex (parseRegex)+import Control.Monad.State+import Control.Applicative  parse :: String -> Pattern parse r = case parseRegex r of@@ -15,24 +20,25 @@     Left x -> error $ show x  genexPure :: [String] -> [String]-genexPure = map T.unpack . foldl1 intersect . map (runOmega . omega . normalize IntSet.empty . parse)+genexPure = map T.unpack . foldl1 intersect . map (toList . run . normalize IntSet.empty . parse)  maxRepeat :: Int maxRepeat = 3 -omega :: Pattern -> Omega T.Text-omega p = case p of+each = foldl1 (<|>) . map return++run :: Pattern -> Stream T.Text+run p = case p of     PChar{..} -> isChar getPatternChar     PAny {getPatternSet = PatternSet (Just cset) _ _ _} -> each $ map T.singleton $ Set.toList cset-    PQuest p -> join $ each [return T.empty, omega p]-    PPlus p -> omega $ PBound 1 Nothing p-    PStar _ p -> omega $ PBound 0 Nothing p+    PQuest p -> pure T.empty <|> run p+    PPlus p -> run $ PBound 1 Nothing p+    PStar _ p -> run $ PBound 0 Nothing p     PBound low high p -> do-        p <- omega p-        n <- each [low..maybe (low+3) id high]-        return $ T.replicate n p-    PConcat ps -> fmap T.concat . sequence $ map omega ps-    POr xs -> foldl1 mplus $ map omega xs+        n <- each [low..maybe (low+maxRepeat) id high]+        fmap T.concat . sequence $ replicate n (run p) +    PConcat ps -> fmap T.concat . suspended . sequence $ map run ps+    POr xs -> foldl1 mplus $ map run xs     PDot{} -> notChars []     PEscape {..} -> case getPatternChar of         'n' -> isChar '\n'@@ -50,7 +56,6 @@         ch  -> isChar ch     _      -> error $ show p     where-    isChar :: Char -> Omega T.Text     isChar = return . T.singleton     chars = each . map T.singleton     notChars = chars . ([' '..'~'] \\)