1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
use std::fmt::Debug; use std::iter::ExactSizeIterator; use crate::{ unionfind::{Key, UnionFind, Value}, ENode, Id, Language, }; /** Arbitrary data associated with an [`EClass`]. `egg` allows you to associate arbitrary data with each eclass. The [`Metadata`] allows that data to behave well even across eclasses merges. [`Metadata`] can prove useful in many situtations. One common one is constant folding, a kind of partial evaluation. In that case, the metadata is basically `Option<L>`, storing the cheapest constant expression (if any) that's equivalent to the enodes in this eclass. See the test files [`math.rs`] and [`prop.rs`] for more complex examples on this usage of [`Metadata`]. If you don't care about [`Metadata`], `()` implements it trivally, just use that. # Example ``` use egg::{*, rewrite as rw}; define_language! { enum EasyMath { Num(i32), Add = "+", Mul = "*", Variable(String), } } use EasyMath::*; type Meta = Option<i32>; impl Metadata<EasyMath> for Meta { type Error = (); fn merge(&self, other: &Self) -> Self { self.clone().and(other.clone()) } fn make(enode: ENode<EasyMath, &Self>) -> Self { let c = |i: usize| enode.children[i].clone(); match enode.op { Num(i) => Some(i), Add => Some(c(0)? + c(1)?), Mul => Some(c(0)? * c(1)?), _ => None, } } fn modify(eclass: &mut EClass<EasyMath, Self>) { if let Some(i) = eclass.metadata { eclass.nodes.push(enode!(Num(i))) } } } let rules: &[Rewrite<EasyMath, Meta>] = &[ 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 mut egraph = EGraph::<EasyMath, Meta>::default(); let whole_thing = egraph.add_expr(&"(+ 0 (* (+ 4 -3) foo))".parse().unwrap()); SimpleRunner::default().run(&mut egraph, &rules); let just_foo = egraph.add(enode!(Variable("foo".into()))); assert_eq!(egraph.find(whole_thing), egraph.find(just_foo)); ``` [`Metadata`]: trait.Metadata.html [`EClass`]: struct.EClass.html [`ENode`]: struct.ENode.html [`math.rs`]: https://github.com/mwillsey/egg/blob/master/tests/math.rs [`prop.rs`]: https://github.com/mwillsey/egg/blob/master/tests/prop.rs */ pub trait Metadata<L>: Sized + Debug { /// Unused for now, probably just make this `()`. type Error: Debug; /// Defines how to merge two [`Metadata`]s when their containing /// [`EClass`]es merge. /// /// [`Metadata`]: trait.Metadata.html /// [`EClass`]: struct.EClass.html fn merge(&self, other: &Self) -> Self; /// Makes a new [`Metadata`] given an operator and its children /// [`Metadata`]. /// /// [`Metadata`]: trait.Metadata.html fn make(enode: ENode<L, &Self>) -> Self; /// A hook that allow a [`Metadata`] to modify its containing /// [`EClass`]. /// /// By default this does nothing. /// /// [`Metadata`]: trait.Metadata.html /// [`EClass`]: struct.EClass.html fn modify(_eclass: &mut EClass<L, Self>) {} } impl<L: Language> Metadata<L> for () { type Error = std::convert::Infallible; fn merge(&self, _other: &()) {} fn make(_enode: ENode<L, &()>) {} } /// An equivalence class of [`ENode`]s /// /// [`ENode`]: struct.ENode.html #[derive(Debug, Clone)] #[non_exhaustive] pub struct EClass<L, M> { /// This eclass's id. pub id: Id, /// The equivalent enodes in this equivalence class. pub nodes: Vec<ENode<L>>, /// The metadata associated with this eclass. pub metadata: M, #[cfg(feature = "parent-pointers")] #[doc(hidden)] pub(crate) parents: indexmap::IndexSet<usize>, } impl<L, M> EClass<L, M> { /// Returns `true` if the `eclass` is empty. pub fn is_empty(&self) -> bool { self.nodes.is_empty() } /// Returns the number of enodes in this eclass. pub fn len(&self) -> usize { self.nodes.len() } /// Iterates over the enodes in the this eclass. pub fn iter(&self) -> impl ExactSizeIterator<Item = &ENode<L>> { self.nodes.iter() } } impl<L: Language, M: Metadata<L>> Value for EClass<L, M> { type Error = std::convert::Infallible; fn merge<K: Key>( _unionfind: &mut UnionFind<K, Self>, to: Self, from: Self, ) -> Result<Self, Self::Error> { let mut less = to.nodes; let mut more = from.nodes; // make sure less is actually smaller if more.len() < less.len() { std::mem::swap(&mut less, &mut more); } more.extend(less); let mut eclass = EClass { id: to.id, nodes: more, metadata: to.metadata.merge(&from.metadata), #[cfg(feature = "parent-pointers")] parents: { let mut parents = to.parents; parents.extend(from.parents); parents }, }; M::modify(&mut eclass); Ok(eclass) } }