egg_sketches/
lib.rs

1#![warn(missing_docs)]
2/*!
3
4`egg-sketches` is a library adding support for program sketches on top of the `egg` (**e**-**g**raphs **g**ood) library,
5an e-graph library optimized for equality saturation.
6
7*Sketches* are program patterns that are satisfied by a family of programs.
8They can also be seen as incomplete or partial programs as they can leave details unspecified.
9
10This library is born from our paper on [*Sketch-Guided Equality Saturation*](https://arxiv.org/abs/2111.13040),
11a semi-automatic technique that allows programmers to provide program sketches to guide rewriting.
12
13If you're new to `egg`,  e-graphs or equality saturation, the `egg` [tutorial](https://egraphs-good.github.io/egg/egg/tutorials/index.html) is good to get started.
14
15To see examples of how to use this sketch libary, you can look at the [tests](https://github.com/Bastacyclop/egg-sketches/blob/main/tests) on Github.
16
17*/
18
19pub(crate) use egg::*;
20
21mod analysis;
22pub(crate) mod extract_common;
23mod extract;
24/// Alternative recursive descent implementation of sketch extraction inspired from pattern matching. This is instead of the bottom-up e-class analysis approach.
25///
26/// FIXME: recursive descent gives wrong results since update to egg main!
27pub mod recursive_extract;
28mod hashcons;
29mod sketch;
30
31#[cfg(feature = "util")]
32/// Utility functions for integration tests and examples
33pub mod util;
34
35pub use {
36    extract::eclass_extract_sketch,
37    // extract::extract_sketch,
38    extract::eclass_satisfies_sketch,
39    extract::satisfies_sketch,
40    sketch::{Sketch, SketchNode},
41};
42
43pub(crate) type BuildHasher = fxhash::FxBuildHasher;
44
45pub(crate) type HashMap<K, V> = hashbrown::HashMap<K, V, BuildHasher>;
46pub(crate) type HashSet<K> = hashbrown::HashSet<K, BuildHasher>;
47
48pub(crate) type IndexMap<K, V> = indexmap::IndexMap<K, V, BuildHasher>;
49pub(crate) type IndexSet<K> = indexmap::IndexSet<K, BuildHasher>;
egg_sketches/lib.rs

egg_sketches/
lib.rs
