srtree-3.0.1.0: src/Text/ParseRule.hs
{-# language OverloadedStrings #-}
-----------------------------------------------------------------------------
-- |
-- Module : Text.ParseRule
-- Copyright : (c) Fabricio Olivetti 2021 - 2024
-- License : BSD3
-- Maintainer : fabricio.olivetti@gmail.com
-- Stability : experimental
-- Portability :
--
-- Parser and resolver for user-supplied equality-saturation rewrite rules
-- and rule sets.
--
-- A rule is written as
--
-- > lhs -> rhs -- one-way rewrite
-- > lhs <=> rhs -- bidirectional (two one-way rules)
-- > lhs -> rhs | isNotZero(x) -- conditional rule
-- > lhs -> rhs | isPositive(x), isInteger(y)
--
-- Patterns use the same expression syntax as 'parsePat': @x<i>@ is feature
-- variable @i@, @t<i>@ is parameter @i@, @v<i>@ or any single letter @[a-zA-Z]@
-- is a pattern variable (wildcard), and numeric literals are constants.
-- Operators: @+@ @-@ @*@ @/@ @^@ @**@ @|**|@ (power of absolute value) @aq@ and
-- the unary functions @sin@ @cos@ @tan@ @log@ @exp@ @sqrt@ @abs@ @recip@
-- @cbrt@ @square@ @cube@ @logabs@ @sqrtabs@ (and capitalized aliases).
--
-- Conditions refer to a fixed registry of named predicates ('conditionRegistry')
-- applied to a pattern variable, e.g. @isNotZero(x)@. Every variable occurring
-- in the target (and in a condition) must also occur in the source; for a
-- bidirectional rule both sides must use the same variables.
--
-- A rule set is either one of the builtin names ('rulesetNames'), a file
-- prefixed with @\@@ containing one rule per line (@#@ comments), or an inline
-- rule list with rules separated by @;@. Use 'resolveRules' to accept any of
-- the three spellings.
--
-----------------------------------------------------------------------------
module Text.ParseRule
( ParsePat, parsePat, parsePatExpr
, parseRule, parseRules
, conditionRegistry, knownConditions
, rulesetNames, rulesetByName, resolveRules
) where
import Control.Applicative ((<|>))
import Data.Attoparsec.ByteString.Char8 hiding ( match, takeWhile )
import Data.Attoparsec.Expr
import qualified Data.ByteString.Char8 as B
import Data.Char (isAlpha)
import Data.List (dropWhileEnd, intercalate, isInfixOf, isPrefixOf, nub)
import Data.List.Split (splitOn)
import qualified Data.Map.Strict as Map
import System.Directory (doesFileExist)
import Data.SRTree
import Algorithm.EqSat.Egraph (NOp(..))
import Algorithm.EqSat.DB
import Algorithm.EqSat.Simplify
( ConstrFun, isConstPt, isConstPos, isNotParam, isNotZero
, isEven, isInteger, isPositive, isValid
, rewrites, rewritesParams, rewritesSimple, rewritesWithConstant
, rewriteBasic, rewritesFun, rewritesMergeOnly
)
-- * Pattern parsing
type ParsePat = Parser Pattern
-- | parses a string representing a pattern expression (e.g. @v0 * x0 + t0@).
-- Pattern variables can be written as @v<i>@ or as a single letter @[a-zA-Z]@
-- (e.g. @x + 0@).
parsePat :: B.ByteString -> Either String Pattern
parsePat = eitherResult . (`feed` "") . parse parsePatExpr . putEOL . B.strip
putEOL :: B.ByteString -> B.ByteString
putEOL bs | B.null bs = bs
| B.last bs == '\n' = bs
| otherwise = B.snoc bs '\n'
parsePatExpr :: ParsePat
parsePatExpr = parsePatternExpr (prefixOps : binOps) [] var
where
prefixOps = Prelude.map (uncurry prefix)
[ ("id", id), ("abs", abs)
, ("sinh", sinh), ("cosh", cosh), ("tanh", tanh)
, ("sin", sin), ("cos", cos), ("tan", tan)
, ("asinh", asinh), ("acosh", acosh), ("atanh", atanh)
, ("asin", asin), ("acos", acos), ("atan", atan)
, ("sqrtabs", sqrtabs'), ("sqrt", sqrt), ("cbrt", cbrt'), ("square", (**2))
, ("logabs", logabs'), ("log", log), ("exp", exp), ("cube", cube'), ("recip", recip')
, ("Id", id), ("Abs", abs)
, ("Sinh", sinh), ("Cosh", cosh), ("Tanh", tanh)
, ("Sin", sin), ("Cos", cos), ("Tan", tan)
, ("ASinh", asinh), ("ACosh", acosh), ("ATanh", atanh)
, ("ASin", asin), ("ACos", acos), ("ATan", atan)
, ("SqrtAbs", sqrtabs'), ("Sqrt", sqrt), ("Cbrt", cbrt'), ("Square", (**2))
, ("LogAbs", logabs'), ("Log", log), ("Exp", exp), ("Recip", recip'), ("Cube", cube')
, ("|log|", logabs'), ("|Log|", logabs'), ("|sqrt|", sqrtabs'), ("|Sqrt|", sqrtabs')
, ("√", sqrt), ("|√|", sqrtabs')
]
binOps = [[binary "^" (**) AssocLeft], [binary "**" (**) AssocLeft]
, [binary "*" (*) AssocLeft, binary "/" (/) AssocLeft]
, [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft]
, [binary "|**|" powabs AssocLeft], [binary "|^|" powabs AssocLeft]
, [binary "aq" aq AssocLeft], [binary "|/|" aq AssocLeft]
]
powabs l r = Fixed $ Bin PowerAbs l r
aq l r = Fixed $ Bin AQ l r
logabs' t = Fixed $ Uni LogAbs t
sqrtabs' t = Fixed $ Uni SqrtAbs t
cbrt' t = Fixed $ Uni Cbrt t
cube' t = Fixed $ Uni Cube t
recip' t = Fixed $ Uni Recip t
var = do char 'x'
ix <- decimal
pure $ Fixed $ Var ix
<|> do char 't'
ix <- decimal
pure $ Fixed $ Param ix
<|> do char 'v'
ix <- decimal
pure $ VarPat (toEnum $ ix+65)
<|> do c <- letter_ascii
pure $ VarPat c
<?> "var"
-- | Creates a parser for a binary operator
binary :: B.ByteString -> (a -> a -> a) -> Assoc -> Operator B.ByteString a
binary name fun = Infix (do{ string (B.cons ' ' (B.snoc name ' ')) <|> string name; pure fun })
-- | Creates a parser for a unary function
prefix :: B.ByteString -> (a -> a) -> Operator B.ByteString a
prefix name fun = Prefix (do{ string name; pure fun })
-- | Envelopes the parser in parens
parens :: Parser a -> Parser a
parens e = do{ string "("; e' <- e; string ")"; pure e' } <?> "parens"
parsePatternExpr :: [[Operator B.ByteString Pattern]] -> [ParsePat -> ParsePat] -> ParsePat -> ParsePat
parsePatternExpr table binFuns var =
do e <- expr
many1' space
pure e
where
term = parens expr <|> choice (Prelude.map ($ expr) binFuns) <|> coef <|> var <?> "term"
expr = buildExpressionParser table term
coef = Fixed . Const <$> signed double <?> "const"
-- * Rule parsing
-- | A rule direction: one-way ('Dir') or bidirectional ('Bi').
data ArrKind = Dir | Bi deriving (Eq, Show)
-- | Parses a single rewrite rule @lhs -> rhs@, @lhs => rhs@, @lhs <=> rhs@ or
-- @lhs == rhs@, optionally followed by @| cond1(x), cond2(y)@.
parseRule :: B.ByteString -> Either String Rule
parseRule raw =
case dropWhile isSpace . takeWhile (/= '#') $ B.unpack raw of
"" -> Left "empty rule"
s -> do
(lhsStr, arr, rhsRest) <- splitArrow s
let (rhsStr, condStr) = splitConds rhsRest
lhs <- parsePat (B.pack lhsStr)
rhs <- parsePat (B.pack rhsStr)
conds <- mapM parseCond (filter (not . null) (splitOn "," condStr))
validateRule lhs rhs arr conds
let base = case arr of
Dir -> lhs :=> rhs
Bi -> lhs :==: rhs
pure $ foldl (:|) base [cf arg | (_, arg, cf) <- conds]
-- | Parses a rule set: one rule per line, @#@ comments, and/or @;@-separated
-- rules within a line.
parseRules :: B.ByteString -> Either String [Rule]
parseRules txt = go 1 (lines (B.unpack txt))
where
go _ [] = Right []
go i (l:ls) =
let pieces = filter (not . all isSpace) (splitOn ";" (takeWhile (/= '#') l))
in case traverse (parseRule . B.pack) pieces of
Left e -> Left ("line " <> show i <> ": " <> e)
Right rs -> fmap (rs <>) (go (i+1) ls)
-- | Splits at the first rule arrow. Longest arrow first at each position so
-- that @<=>@ wins over @=>@.
splitArrow :: String -> Either String (String, ArrKind, String)
splitArrow = go ""
where
go _ [] = Left "a rule must contain an arrow ('->' for one-way, '<=>' for bidirectional)"
go acc s@(c:cs)
| Just (arr, n) <- matchArrow s = Right (reverse acc, arr, drop n s)
| otherwise = go (c:acc) cs
matchArrow s
| "<=>" `isPrefixOf` s = Just (Bi, 3)
| "->" `isPrefixOf` s = Just (Dir, 2)
| "=>" `isPrefixOf` s = Just (Dir, 2)
| "==" `isPrefixOf` s = Just (Bi, 2)
| otherwise = Nothing
-- | Splits the right-hand side of a rule at the condition separator @|@.
-- A @|@ is only a condition separator when it is followed by @name(...)@, so
-- the @|**|@, @|log|@, ... operators are not confused with conditions.
splitConds :: String -> (String, String)
splitConds = go ""
where
go acc [] = (reverse acc, "")
go acc s@(c:cs)
| c == '|', isCondStart (dropWhile isSpace cs) = (reverse acc, dropWhile isSpace cs)
| otherwise = go (c:acc) cs
isCondStart s = case span isAlpha s of
(_:_, rest) -> case dropWhile isSpace rest of
('(':_) -> True
_ -> False
_ -> False
-- | Parses a single condition @name(arg)@ where @arg@ is a pattern variable.
-- Returns the condition name (for error messages), the argument pattern and
-- the predicate.
parseCond :: String -> Either String (String, Pattern, ConstrFun)
parseCond s0 =
let s = dropWhile isSpace s0
(name, rest) = span isAlpha s
rest1 = dropWhile isSpace rest
in if null name
then Left ("invalid condition '" <> s0 <> "': expected name(patternVar)")
else case rest1 of
'(' : rest2 -> case break (== ')') rest2 of
(argStr, ')':_) -> do
arg <- parsePat (B.pack argStr)
cf <- maybe (Left ("unknown condition '" <> name <> "'. Known conditions: "
<> intercalate ", " (Map.keys conditionRegistry)))
Right (Map.lookup name conditionRegistry)
pure (name, arg, cf)
_ -> Left ("unterminated condition '" <> s0 <> "': missing ')'")
_ -> Left ("expected '(' after condition name in '" <> s0 <> "'")
-- | Checks that every target/condition variable is bound by the source
-- pattern. A bidirectional rule must bind the same variables on both sides
-- (its conditions are applied to both directions).
validateRule :: Pattern -> Pattern -> ArrKind -> [(String, Pattern, ConstrFun)] -> Either String ()
validateRule lhs rhs arr conds = do
let lv = patVars lhs
rv = patVars rhs
case arr of
Dir -> case filter (`notElem` lv) rv of
[] -> Right ()
vs -> Left ("unbound target variable(s) " <> show vs
<> ": every target variable must appear in the source pattern")
Bi -> if null (filter (`notElem` lv) rv) && null (filter (`notElem` rv) lv)
then Right ()
else Left "both sides of a bidirectional ('<=>') rule must use the same pattern variables"
mapM_ (\(_, arg, _) -> case arg of
VarPat c | c `elem` lv -> Right ()
VarPat c -> Left ("condition variable '" <> [c] <> "' does not appear in the source pattern")
_ -> Left "condition arguments must be pattern variables (e.g. isNotZero(x))")
conds
-- | The pattern variables occurring in a pattern.
patVars :: Pattern -> [Char]
patVars = nub . go
where
go (VarPat c) = [c]
go Hole = []
go (Fixed t) = case t of
Var _ -> []
Param _ -> []
Const _ -> []
Y _ -> []
Uni _ a -> go a
Bin _ a b -> go a <> go b
go (NAry _ cs) = concatMap child cs
child (Ch p) = go p
child (Rest c) = [c]
child (MapP p c) = c : go p
-- * Conditions and rule sets
-- | Registry of the named condition predicates usable in user rules. Each
-- predicate constrains the e-class bound to a pattern variable.
conditionRegistry :: Map.Map String ConstrFun
conditionRegistry = Map.fromList
[ ("isConst", isConstPt)
, ("isConstPt", isConstPt)
, ("isConstPos", isConstPos)
, ("isNotParam", isNotParam)
, ("isNotZero", isNotZero)
, ("isEven", isEven)
, ("isInteger", isInteger)
, ("isPositive", isPositive)
, ("isValid", isValid)
]
-- | The names accepted in 'conditionRegistry'.
knownConditions :: [String]
knownConditions = Map.keys conditionRegistry
-- | Builtin rule set names.
rulesetNames :: [String]
rulesetNames = ["default", "params", "simple", "constant", "basic", "fun", "merge-only"]
-- | Looks up a builtin rule set by name.
rulesetByName :: String -> Maybe [Rule]
rulesetByName "default" = Just rewrites
rulesetByName "params" = Just rewritesParams
rulesetByName "simple" = Just rewritesSimple
rulesetByName "constant" = Just rewritesWithConstant
rulesetByName "basic" = Just rewriteBasic
rulesetByName "fun" = Just rewritesFun
rulesetByName "merge-only" = Just rewritesMergeOnly
rulesetByName _ = Nothing
-- | Resolves a rule set specification: a builtin name ('rulesetNames'),
-- @\@FILE@ with one rule per line, or inline rules separated by @;@ (e.g.
-- @\"x + 0 -> x; log(exp(x)) <=> x\"@). The empty string and @\"default\"@
-- select the default rule set. Returns a user-readable error message when the
-- specification cannot be resolved.
resolveRules :: String -> IO (Either String [Rule])
resolveRules spec
| null trimmed = pure (Right rewrites)
| Just rs <- rulesetByName trimmed = pure (Right rs)
| ('@':path) <- trimmed =
do ok <- doesFileExist path
if not ok
then pure (Left ("rules file not found: " <> path))
else parseRules <$> B.readFile path
| any (`isInfixOf` spec) ["->", "<=>", "=>", "=="] = pure (parseRules (B.pack spec))
| otherwise = pure (Left ("unknown rule set '" <> spec <> "'. Use a builtin name ("
<> intercalate ", " rulesetNames
<> "), @FILE with one rule per line, or inline rules such as "
<> "'x + 0 -> x' (multiple rules separated by ';')."))
where
trimmed = dropWhileEnd isSpace (dropWhile isSpace spec)