Home / Rust / Data structures

egg - An implementation of egraphs

egg: egraphs good Check out the web demo for some quick egraph action. Using egg Add egg to your Cargo.toml like this: [dependencies] egg = "0.4.1" De
Information
Category: Rust / Data structures
Watchers: 23
Star: 1.1k
Fork: 109
Last update: Dec 5, 2023
Resource links
https://mwillsey.com/papers/egg/
https://github.com/egraphs-good/egg

egg logo egg: egraphs good

Build Status Crates.io Docs.rs

Check out the web demo for some quick egraph action.

Using egg

Add egg to your Cargo.toml like this:

[dependencies]
egg = "0.4.1"

Developing

It's written in Rust. Typically, you install Rust using rustup.

Run cargo doc --open to build and open the documentation in a browser.

Before committing/pushing, make sure to run make, which runs all the tests and lints that CI will.

Tests

You will need graphviz to run the tests. Running cargo test will run the tests. Some tests may time out; try cargo test --release if that happens.

There are a couple interesting tests in the tests directory:

  • prop.rs implements propositional logic and proves some simple theorems.
  • math.rs implements real arithmetic, with a little bit of symbolic differentiation.
  • lambda.rs implements a small lambda calculus, using egg as a partial evaluator.
17 Open More issues
Closed

Pathological rebuild performance

Consider an analysis that is overwhelmingly likely to propagate updates throughout the e-graph. In my use-case, I was computing AstSize in my Analysis, as I needed it for some heuristics. The below example models this by always returning DidMerge(true, true).

use egg::*;

// Runtime is extremely sensitive to this argument
const SIZE: usize = 14;

type EGraph = egg::EGraph<SymbolLang, MyAnalysis>;

struct MyAnalysis;

impl Analysis<SymbolLang> for MyAnalysis {
    type Data = ();

    fn make(_: &EGraph, _: &SymbolLang) {}
    fn merge(&mut self, _: &mut (), _: ()) -> DidMerge {
        DidMerge(true, true)
    }
}

fn wrap(egraph: &mut EGraph, mut v: Id) {
    for _ in 0..SIZE {
        let f = egraph.add(SymbolLang { op: "f".into(), children: vec![v] });
        let g = egraph.add(SymbolLang { op: "g".into(), children: vec![v] });
        egraph.union(f, g);
        v = f;
    }
}

fn main() {
    env_logger::init();

    let mut egraph = EGraph::new(MyAnalysis);
    let x = egraph.add(SymbolLang { op: "x".into(), children: vec![] });
    let y = egraph.add(SymbolLang { op: "y".into(), children: vec![] });
    wrap(&mut egraph, x);
    wrap(&mut egraph, y);
    egraph.rebuild();

    egraph.union(x, y);
    egraph.rebuild();
}

Running this with RUST_LOG=egg=info cargo r --release prints:

[2023-02-21T05:20:57Z INFO  egg::egraph] REBUILT! in 0.000s
      Old: hc size 58, eclasses: 30
      New: hc size 58, eclasses: 30
      unions: 0, trimmed nodes: 0
[2023-02-21T05:21:15Z INFO  egg::egraph] REBUILT! in 18.454s
      Old: hc size 58, eclasses: 29
      New: hc size 58, eclasses: 15
      unions: 14, trimmed nodes: 28

The issue is that process_unions iterates through analysis_pending in a random order, instead of bottom-up. Performing the latter accurately might be non-trivial, but while I haven't thought through this fully, I believe a very good approximation, that would recover the optimal asymptotic complexity, is to count how many times the analysis data of each e-node has been handled during the current rebuild, and in each iteration pick the one where this count is lowest (with something like BinaryHeap).

opened Feb 21, 2023 by meithecatte 18
Closed

Clarify Analysis ordering

The new Analysis::merge could use a bit more doc, along the line of:

Analysis::Data must form a partial order. For example, the "constant" analysis for i32 forms the order None < Some(x: i32) for any x (but any pair of Some(x), Some(y) are not comparable). merge modifies to to be the least upper bound of to and from. For example, take merge(a, b):

  1. When b = None there is no need to modify a, as b contains no information (is the bottom of the partial order). We know for sure b <= a.
  2. When a = None and b = Some(2) modifies a to be Some(2), as b > a.
  3. When a = Some(1) and b = Some(1) there is no modification.
  4. When a = Some(1) and b = Some(2) egg should panic, as the points have no LUB (they give conflicting information for what the constant should be).

Is the above consistent with the implementation? I also can't figure out what the ordering returned by merge is supposed to mean from the tests.

opened Apr 10, 2021 by remysucre 18
Closed

What happened to Language::children()?

This method was present in the latest release but no longer exists in the development version. I don't see anything in the changelog about it. I have the same question about Language::children_mut().

opened Apr 14, 2021 by rosekunkel 16
Closed

Make Analysis::make take in the E-graph mutably

I have a use case where I want to tag each value in the E-graph with type information, which itself should be stored either in the E-graph or in another E-graph stored in the Analysis. This requires me to mutate the E-graph or at least the Analysis from inside Analysis::make (the alternative would be to wrap a nested E-graph in the analysis in RefCell or RwLock); thankfully, just making the E-graph reference passed in mutable is enough to get this to work with only minimal changes (sticking an &mut on implementations of Analysis) to anything else. Unfortunately, this is still a breaking change, so not sure if you guys would be interested in it.

opened Oct 9, 2023 by imbrem 15
Closed

Problems upgrading

Ran into two problems upgrading. One was easy enough to work around but the other may be worth discussing.

  1. display_op was removed and you now implement Display for the Language type. This feels a bit weird though since it only displays the operator, not the whole Language struct. This may be better as a separate trait like FromOp?
  2. The FromOp requires Error, but there are a few cases where that won't be implemented. For instance -- previously my errors were String, but that doesn't implement Error. I'm also now using the anyhow crate for errors, and that also doesn't implement Error (https://docs.rs/anyhow/1.0.51/anyhow/struct.Error.html#impl-AsRef%3Cdyn%20Error%20+%20%27static%3E). Seems like that requirement may be needlessly restrictive. Could it instead require Display + 'static or AsRef<dyn Error + 'static> or something like that?
opened Nov 29, 2021 by bjchambers 12
Closed

Adding equivalences during rewriting

I'm not exactly sure what terms to use to describe this, so I'll explain the example and some thoughts.

Say we have a simple language that includes some math, and the ability to construct records { (<name>: <expr>)* } and access fields <expr>.<name>. A very reasonable rewrite rule in this would be { ?name: ?expr, .. }.?name => ?expr. Obviously, we can't implement that rule for a variety of reasons, including the fact it is variadic.

Now, one option would be to match the field ref, and have that run a specially implemented rule that used information about the expression (possibly whether it was a record) to apply the rewrite. I'll probably pursue if necessary. But, that also has some problems -- for instance, if there are other operators such as an if expression then the field ref may not be applied directly.

Another idea I had was to focus on the record introduction rather than the field ref. If for every record { ?name1: ?expr1, ?name2: ?expr2, ... } I added ?record.?name1 = ?expr1, ?record.?name2 = ?expr2, etc. then I believe that those equivalences would be preferred, etc.

But, I'm not sure how to go about writing a rule that says "for each record (ideally only once when it is added), add these equivalences". I think it is possible to explicitly union things within the DFG, so adding the equivalences is easy. It seems like it may be possible with a custom searcher and a custom applier, but I'm not sure if that would re-execute the search every time.

I'm also not sure if it should produce a single subst for the record (and then the applier should iterate over the fields) or if it should produce a subst for each field. The latter seems tricky since there is no way to carry the field name in the subst.

Are there any examples of applying egg to languages with records with these kinds of equivalences?

opened Oct 6, 2021 by bjchambers 12
Open

Proof explanations for multi_rewrite

Hi everyone! I was exploring proof construction with egg. I needed to have non-symmetrical rules, so that when I check (a, b) for equivalence it is true, and (b, a) is not. I used a hack from tests/prop.rs with multi_rewrite, but I am facing something weird right now. If an Explanation<L> provided by explain_equivalence contains a multi_rewrite rule, its name in the graph is something like .../.cargo/registry/src/github.com-1ecc6299db9ec823/egg-0.9.3/src/multipattern.rs:167:32. I have just added a printing of a proof to tests/prop.rs here.

Trying to prove goal 5: (-> x z)
Explanation: (& (-> x y) (-> y z))
(Rewrite<= /Users/andrei/.cargo/registry/src/github.com-1ecc6299db9ec823/egg-0.9.3/src/multipattern.rs:167:32 (| (~ x) z))
(Rewrite=> def_imply_flip (-> x z))
test prove_chain ... ok
opened Feb 8, 2023 by K-dizzled 11
Open

Add an example that **doesn't use** the define_language macro?

It'd be great if one of the tests (that you point to as examples of how to setup egg) didn't use the define_language macro - as I actually don't have a clue how to hook up egg to my toy compiler IR without having some sort of textual representation! I'm sure there must be a way for me to hook up my toy IR to egg, I'm just not sure how!

opened Dec 5, 2022 by sheredom 9
Open

Pretty printing stack overflow for proofs

Right now, getting proofs with get_string_with_let can stack overflow because of our bad pretty printer.

opened Oct 25, 2022 by oflatt 0
Open

LpExtractor creates an infeasible problem for CBC

Hi. I'm having fun with egg.

I encountered an infeasible error with CBC that prevents LpExtractor from processing cyclic e-graphs.

Example: tmp

use egg::*;

fn main() {
    env_logger::init();

    let mut egraph = EGraph::<SymbolLang, ()>::default();

    let g = egraph.add_expr(&"(g v x)".parse().unwrap());
    let v = egraph.add_expr(&"v".parse().unwrap());
    let f = egraph.add(SymbolLang::new("f", vec![v, g]));
    let top = egraph.add(SymbolLang::new("list", vec![f, g]));
    egraph.rebuild();

    let runner = Runner::default()
        .with_iter_limit(100)
        .with_node_limit(10_000)
        .with_egraph(egraph)
        .run(&vec![rewrite!("f"; "(f ?v (g ?v ?a))" => "?a")]);

    runner.egraph.dot().to_dot("tmp.dot").unwrap();

    LpExtractor::new(&runner.egraph, AstSize).solve(top);
}

Log produced:

[INFO  egg::egraph] REBUILT! in 0.000s
      Old: hc size 5, eclasses: 5         
      New: hc size 5, eclasses: 5
      unions: 0, trimmed nodes: 0
[INFO  egg::egraph] REBUILT! in 0.000s
      Old: hc size 5, eclasses: 5        
      New: hc size 5, eclasses: 5
      unions: 0, trimmed nodes: 0
[INFO  egg::run]
    Iteration 0
[INFO  egg::run] Search time: 0.000048125
[INFO  egg::run] Apply time: 0.000038416
[INFO  egg::egraph] REBUILT! in 0.000s
      Old: hc size 5, eclasses: 4
      New: hc size 6, eclasses: 4
      unions: 0, trimmed nodes: 0
[INFO  egg::run] Rebuild time: 0.000590618
[INFO  egg::run] Size: n=6, e=4
[INFO  egg::run]
    Iteration 1
[INFO  egg::run] Search time: 0.000033264
[INFO  egg::run] Apply time: 0.000013224
[INFO  egg::egraph] REBUILT! in 0.000s
      Old: hc size 6, eclasses: 4
      New: hc size 6, eclasses: 4
      unions: 0, trimmed nodes: 0
[INFO  egg::run] Rebuild time: 0.000198928
[INFO  egg::run] Size: n=6, e=4
[INFO  egg::run] Stopping: Saturated
[/home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/egg-0.9.0/src/lp_extract.rs:138] max_order = 50.0
Welcome to the CBC MILP Solver
Version: 2.10
Build Date: Jun 30 2022

command line - Cbc_C_Interface -solve -quit (default strategy 1)
Problem is infeasible - 0.00 seconds
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.00

[INFO  egg::lp_extract] CBC status Finished, LinearRelaxationInfeasible
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/egg-0.9.0/src/lp_extract.rs:192:80
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

This find_cycles extracts g as a result. But I might need f instead. https://github.com/egraphs-good/egg/blob/main/src/lp_extract.rs#L209

For the moment, I'm avoiding the error with code like is_dag. Perhaps, it works for others.

fn find_cycles<L, N>(egraph: &EGraph<L, N>, mut f: impl FnMut(Id, usize))
where
    L: Language,
    N: Analysis<L>,
{
    for class in egraph.classes() {
        let id = class.id;
        for (i, node) in egraph[id].iter().enumerate() {
            for &child in node.children() {
                if usize::from(child) >= usize::from(id) {
                    f(id, i);
                    break;
                }
            }
        }
    }
}

(Could be related: https://github.com/egraphs-good/egg/issues/196 )

opened Oct 2, 2022 by khaki3 8
Open

Cycles in existence proofs

While working at Certora I came across Cycle in existance! errors. I'm guessing union_trusted broke existance proofs because when I was implementing it I forgot they were a thing. I'll look into it.

opened Aug 31, 2022 by oflatt 0
Open

assertion failed: solution.col(v.active) > 0.0

error: thread '<unnamed>' panicked at 'assertion failed: solution.col(v.active) > 0.0' code location: https://github.com/egraphs-good/egg/blob/ab0692ac5eaafbde485f7534b7a318d082069d80/src/lp_extract.rs#L190

Is this a bug in LP extraction, what does hitting this assertion mean?

opened Jul 4, 2022 by Bastacyclop 3

Contents

    facebookresearch EGG: Emergence of lanGuage in Games
    OrangeXC 🍳 A website use mTime api (egg)
    egg-mode-rs egg-mode - Library to interact with the Twitter API
    eggprotocol EGG Protocol multiplies yields by enabling assets escrowing on cross-chain smart contracts.
    egraphs-good Python bindings for egg
    GeekTree0101 Karrot iOS 3rd workshop easter egg
    fatetop Do anything with egg
    gejiaheng :egg: An Android App for Dribbble
    WeiChiaChang 📱 Trigger easter eggs on mobile device
    facebookresearch A Python toolbox for performing gradient-free optimization
    ddgll vue-easteregg - Easey add an easteregg to your vue app (default with konami code)
    bmispelon What do you get when you cross a pony and a walrus?
    Codecademy Connects konami-code-js to emojisplosion for a glorious easter egg
    Arlequiin An application that can generate traduction pokeemerald dizzy egg project files. Credits to Pokecreator and myself.
    ipfs IPFS implementation in JavaScript
    ertugrulcetin GlueList is brand new list implementation which is faster than classic List implementations
    jruby JRuby, an implementation of Ruby on the JVM
    7449 Support unlimited picture rotation BannerLayout, the minimum implementation of the code banner
    ClementPinard Pytorch implementation of FlowNet by Dosovitskiy et al.
    7449 rxnetwork,rxbus,rxcache,rxjsoup
    ikostrikov PyTorch implementation of Trust Region Policy Optimization
    Share this repo

    Related Repos


    Data structures
    265
    A minimal `syn` syntax tree pretty-printer
    dtolnay prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form
     
    Data structures
    4
    A memory efficient syntax tree for language developers
    udoprog syntree A memory efficient syntax tree. This crate provides a tree structure which always is contiguously stored and manipulated in memory. It provide
     
    Data structures
    8
    Rust library providing fast language model queries in compressed space
    kampersanda tongrams-rs: Tons of N-grams in Rust This is a Rust port of tongrams to index and query large language models in compressed space, in which the data s
     
    Data structures
    5
    Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface
    skmendez tree-sitter-traversal Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface. Using cursors, iteration over the tree c
     
    Data structures
    3
    A tiny rusty Xmas tree without bells and whistles
    lmammino xmas A tiny rusty Xmas tree without bells and whistles Run Just clone this repo and run: cargo run (Requires to have Rust installed) Contributing Ever
     
    Data structures
    33
    A LED Christmas Tree controlled by Rust. Contribute your own renderers!
    AngelOnFira Rusty Christmas Tree This is code that draws on the LED Christmas Tree made by @aidancrowther. You can see his 3D design files and Pi Pico setup code
     
    Data structures
    3
    A syntax highlighter for Node powered by Tree Sitter. Written in Rust.
    devongovett tree-sitter-highlight A syntax highlighter for Node.js powered by Tree Sitter. Usage The following will output HTML: const treeSitter = require('tree-
     
    Data structures
    229
    Tree command, improved.
    dduan tre A modern alternative to the tree command that: lists directory structure in a tree-like diagram, like the classics. skips ignored files in git rep
     
    Data structures
    12
    Serialize & deserialize device tree binary using serde
    luojia65 serde_device_tree Use serde framework to deserialize Device Tree Blob binary files; no_std compatible. Use this library Run example: cargo run --examp
     
    Data structures
    10
    StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL
    AFLplusplus StdFuzzer StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL Building Build with $ cargo build --release Compiling a
     
    Data structures
    9
    Rasterization using compute shaders
    pudnax gpu_compute_rasterizer This is a basic implementation of a rasterizer using compute shaders and wgpu. Based on: https://github.com/OmarShehata/webgpu-
     
    Data structures
    3
    A "cursed" container with opaque keys, usable as a static variable
    u1f408 cursedcontainer Please, for the love of all things good in the world, do not use this crate unless you've read the code thoroughly and understand the
     
    Data structures
    3
    Voluntarily contributed solutions for the first practical exercise for the Compilerbau lec...
    Yandrik Solutions for the first practical exercise Compilerbau lecture WiSe 2021/2022 - Ulm University Contributing Want to add your solution? Great! Just add
     
    Data structures
    12
    Common data structures and algorithms for competitive programming in Rust
    utilForever algorithm-rs algorithm-rs is common data structures and algorithms for competitive programming in Rust. Contents TBA How To Contribute Contributions a
     
    Data structures
    1.4k
    Rust implementations of algorithms and data structures useful for bioinformatics.
    rust-bio This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.