slotted_egraphs/
types.rs

1use crate::*;
2
3/// Ids identify e-classes.
4#[derive(Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
5pub struct Id(pub usize);
6
7/// AppliedIds are invocations of e-classes.
8///
9/// Recall that in slotted egraphs, e-classes have arguments - and in order to talk about the set of terms in an e-class, you always need to invocate your e-class using a bunch of arguments.
10/// This "invocation" is what an AppliedId represents. The [Id] part identifies an e-class, and the [SlotMap] is used to map the argument-slots of the e-class to the values that you put into them.
11#[derive(Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
12pub struct AppliedId {
13    pub id: Id,
14
15    // m is always a bijection!
16    // m maps the slots from `id` (be it ENode::slots() in a RecExpr, or EGraph::slots(Id) for eclasses) to the slots that we insert into it.
17    // m.keys() == id.slots
18    pub m: SlotMap,
19}
20
21/// A "term" or "expression" from some given [Language] L.
22// The AppliedIds in `node` are ignored (any typically set to AppliedId::null()). They are replaced by the children RecExpr.
23// A non-fancy version of RecExpr that uses the slots as "names".
24#[derive(Clone, PartialEq, Eq)]
25pub struct RecExpr<L: Language> {
26    pub node: L,
27    pub children: Vec<RecExpr<L>>,
28}
29
30impl AppliedId {
31    pub fn new(id: Id, m: SlotMap) -> Self {
32        let s = AppliedId { id, m };
33        if CHECKS {
34            s.check();
35        }
36        s
37    }
38
39    pub(crate) fn check(&self) {
40        assert!(self.m.is_bijection());
41    }
42
43    #[track_caller]
44    pub fn apply_slotmap(&self, m: &SlotMap) -> AppliedId {
45        if CHECKS {
46            assert!(
47                m.keys().is_superset(&self.slots()),
48                "AppliedId::apply_slotmap: The SlotMap doesn't map all free slots!"
49            );
50        }
51        self.apply_slotmap_partial(m)
52    }
53
54    pub fn apply_slotmap_partial(&self, m: &SlotMap) -> AppliedId {
55        AppliedId::new(self.id, self.m.compose_partial(m))
56    }
57
58    pub fn apply_slotmap_fresh(&self, m: &SlotMap) -> AppliedId {
59        AppliedId::new(self.id, self.m.compose_fresh(m))
60    }
61
62    pub fn slots(&self) -> SmallHashSet<Slot> {
63        self.m.values()
64    }
65
66    // ordered!
67    pub fn slots_mut(&mut self) -> Vec<&mut Slot> {
68        self.m.values_mut().collect()
69    }
70
71    pub fn null() -> Self {
72        AppliedId {
73            id: Id(0),
74            m: SlotMap::new(),
75        }
76    }
77}
slotted_egraphs/types.rs

slotted_egraphs/
types.rs
