[][src]Crate egg

EGraphs (and almost everything else in this crate) are parameterized over the language given by the user (by implementing the Language trait).

If your Language implements FromStr (and Languages derived using define_language! do), you can easily create RecExprs to add to an EGraph.

Add egg to your Cargo.toml like this:

[dependencies]
egg = "0.1.0"
use egg::{*, rewrite as rw};

define_language! {
    enum SimpleLanguage {
        Num(i32),
        Add = "+",
        Mul = "*",
        // language items are parsed in order, and we want symbol to
        // be a fallback, so we put it last
        Symbol(String),
    }
}

let rules: &[Rewrite<SimpleLanguage, ()>] = &[
    rw!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
    rw!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),

    rw!("add-0"; "(+ ?a 0)" => "?a"),
    rw!("mul-0"; "(* ?a 0)" => "0"),
    rw!("mul-1"; "(* ?a 1)" => "?a"),
];

let start = "(+ 0 (* 1 foo))".parse().unwrap();
let (egraph, report) = SimpleRunner::default().run_expr(start, &rules);
println!(
    "Stopped after {} iterations, reason: {:?}",
    report.iterations.len(),
    report.stop_reason
);

Macros

define_language

A macro to easily create a Language.

enode

Utility macro to create an ENode.

recexpr

Utility macro to create an RecExpr.

rewrite

A macro to easily make Rewrites.

Structs

AstDepth

A simple CostFunction that counts maximum ast depth.

AstSize

A simple CostFunction that counts total ast size.

ConditionEqual
ConditionalApplier
Dot

A wrapper for an EGraph that can output GraphViz for visualization.

EClass
EGraph

Data structure to keep track of equalities between expressions.

ENode
Extractor

Extracting a single RecExpr from an EGraph.

Iteration
ParseError
QuestionMarkName
RecExpr
Rewrite
RunReport
SearchMatches
SimpleRunner
WildMap

Enums

Pattern
SimpleRunnerError

Traits

Applier
Condition
CostFunction

A cost function that can be used by an Extractor.

Language

Trait defines a Language whose terms will be in the EGraph.

Metadata
Runner
Searcher

Type Definitions

Id