packages feed

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)