| Copyright | (c) Fabricio Olivetti 2021 - 2024 |
|---|---|
| License | BSD3 |
| Maintainer | [email protected] |
| Stability | experimental |
| Portability | |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithm.EqSat.Build
Description
Functions related to building and maintaining e-graphs Heavily based on hegg (https:/github.comalt-romes/hegg by alt-romes)
Synopsis
- add :: forall (m :: Type -> Type). Monad m => CostFun -> ENode -> EGraphST m EClassId
- rebuild :: forall (m :: Type -> Type). Monad m => CostFun -> EGraphST m ()
- repair :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> ENode -> EGraphST m ()
- repairAnalysis :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> ENode -> EGraphST m ()
- merge :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> EClassId -> EGraphST m EClassId
- modifyEClass :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> EGraphST m EClassId
- createDB :: forall (m :: Type -> Type). Monad m => EGraphST m DB
- addToDB :: forall (m :: Type -> Type). Monad m => ENode -> EClassId -> EGraphST m ()
- populate :: Maybe IntTrie -> [EClassId] -> Maybe IntTrie
- canonizeMap :: forall (m :: Type -> Type). Monad m => (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m (Map ClassOrVar ClassOrVar, ClassOrVar)
- applyMatch :: forall (m :: Type -> Type). Monad m => CostFun -> Rule -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m ()
- applyMergeOnlyMatch :: forall (m :: Type -> Type). Monad m => CostFun -> Rule -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m ()
- classOfENode :: forall (m :: Type -> Type). Monad m => CostFun -> Map ClassOrVar ClassOrVar -> Pattern -> EGraphST m (Maybe EClassId)
- reprPrat :: forall (m :: Type -> Type). Monad m => CostFun -> Map ClassOrVar ClassOrVar -> Pattern -> EGraphST m EClassId
- isValidHeight :: forall (m :: Type -> Type). Monad m => (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m Bool
- isValidConditions :: forall (m :: Type -> Type). Monad m => Condition -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m Bool
- fromTree :: forall (m :: Type -> Type). Monad m => CostFun -> Fix SRTree -> EGraphST m EClassId
- fromTrees :: forall (m :: Type -> Type). Monad m => CostFun -> [Fix SRTree] -> EGraphST m [EClassId]
- getBest :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m (Fix SRTree)
- getExpressionFrom :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m (Fix SRTree)
- getAllExpressionsFrom :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m [Fix SRTree]
- getRndExpressionFrom :: EClassId -> EGraphST (State StdGen) (Fix SRTree)
- cleanMaps :: forall (m :: Type -> Type). Monad m => EGraphST m ()
- forceState :: forall (m :: Type -> Type) s. Monad m => StateT s m ()
Documentation
add :: forall (m :: Type -> Type). Monad m => CostFun -> ENode -> EGraphST m EClassId Source #
adds a new or existing e-node (merging if necessary)
rebuild :: forall (m :: Type -> Type). Monad m => CostFun -> EGraphST m () Source #
rebuilds the e-graph after inserting or merging e-classes
repair :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> ENode -> EGraphST m () Source #
repairs e-node by canonizing its children if the canonized e-node already exists in e-graph, merge the e-classes
repairAnalysis :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> ENode -> EGraphST m () Source #
repair the analysis of the e-class considering the new added e-node
merge :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> EClassId -> EGraphST m EClassId Source #
merge to equivalent e-classes
modifyEClass :: forall (m :: Type -> Type). Monad m => CostFun -> EClassId -> EGraphST m EClassId Source #
modify an e-class, e.g., add constant e-node and prune non-leaves
DB
createDB :: forall (m :: Type -> Type). Monad m => EGraphST m DB Source #
createDB creates a database of patterns from an e-graph
it simply calls addToDB for every pair (e-node, e-class id) from
the e-graph.
addToDB :: forall (m :: Type -> Type). Monad m => ENode -> EClassId -> EGraphST m () Source #
addToDB adds an e-node and e-class id to the database
populate :: Maybe IntTrie -> [EClassId] -> Maybe IntTrie Source #
Populates an IntTrie with a sequence of e-class ids
canonizeMap :: forall (m :: Type -> Type). Monad m => (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m (Map ClassOrVar ClassOrVar, ClassOrVar) Source #
applyMatch :: forall (m :: Type -> Type). Monad m => CostFun -> Rule -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m () Source #
applyMergeOnlyMatch :: forall (m :: Type -> Type). Monad m => CostFun -> Rule -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m () Source #
classOfENode :: forall (m :: Type -> Type). Monad m => CostFun -> Map ClassOrVar ClassOrVar -> Pattern -> EGraphST m (Maybe EClassId) Source #
gets the e-node of the target of the rule TODO: add consts and modify
reprPrat :: forall (m :: Type -> Type). Monad m => CostFun -> Map ClassOrVar ClassOrVar -> Pattern -> EGraphST m EClassId Source #
adds the target of the rule into the e-graph
isValidHeight :: forall (m :: Type -> Type). Monad m => (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m Bool Source #
isValidConditions :: forall (m :: Type -> Type). Monad m => Condition -> (Map ClassOrVar ClassOrVar, ClassOrVar) -> EGraphST m Bool Source #
returns True if the condition of a rule is valid for that match
Tree to e-graph conversion and utility functions
fromTree :: forall (m :: Type -> Type). Monad m => CostFun -> Fix SRTree -> EGraphST m EClassId Source #
Creates an e-graph from an expression tree
fromTrees :: forall (m :: Type -> Type). Monad m => CostFun -> [Fix SRTree] -> EGraphST m [EClassId] Source #
Builds an e-graph from multiple independent trees
getBest :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m (Fix SRTree) Source #
gets the best expression given the default cost function
getExpressionFrom :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m (Fix SRTree) Source #
returns one expression rooted at e-class eId
TODO: avoid loopings
getAllExpressionsFrom :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m [Fix SRTree] Source #
returns all expressions rooted at e-class eId
TODO: check for infinite list