aether_explain/
lib.rs

1use aether_ast::{DerivationTrace, PhaseGraph, PlanExplanation, TupleId};
2use aether_runtime::DerivedSet;
3use indexmap::{IndexMap, IndexSet};
4use thiserror::Error;
5
6pub trait Explainer {
7    fn explain_tuple(&self, id: &TupleId) -> Result<DerivationTrace, ExplainError>;
8    fn explain_plan(&self, plan: &PhaseGraph) -> Result<PlanExplanation, ExplainError>;
9}
10
11#[derive(Clone, Debug, Default)]
12pub struct InMemoryExplainer {
13    tuples: IndexMap<TupleId, aether_ast::DerivedTuple>,
14}
15
16impl InMemoryExplainer {
17    pub fn from_derived_set(derived: &DerivedSet) -> Self {
18        let tuples = derived
19            .tuples
20            .iter()
21            .map(|tuple| (tuple.tuple.id, tuple.clone()))
22            .collect();
23        Self { tuples }
24    }
25
26    fn collect_trace(
27        &self,
28        tuple_id: TupleId,
29        visited: &mut IndexSet<TupleId>,
30        tuples: &mut Vec<aether_ast::DerivedTuple>,
31    ) -> Result<(), ExplainError> {
32        if !visited.insert(tuple_id) {
33            return Ok(());
34        }
35
36        let tuple = self
37            .tuples
38            .get(&tuple_id)
39            .cloned()
40            .ok_or(ExplainError::UnknownTuple(tuple_id))?;
41
42        tuples.push(tuple.clone());
43        for parent in &tuple.metadata.parent_tuple_ids {
44            if !self.tuples.contains_key(parent) {
45                return Err(ExplainError::DanglingParentTuple {
46                    tuple: tuple_id,
47                    parent: *parent,
48                });
49            }
50            self.collect_trace(*parent, visited, tuples)?;
51        }
52
53        Ok(())
54    }
55}
56
57impl Explainer for InMemoryExplainer {
58    fn explain_tuple(&self, id: &TupleId) -> Result<DerivationTrace, ExplainError> {
59        let mut visited = IndexSet::new();
60        let mut tuples = Vec::new();
61        self.collect_trace(*id, &mut visited, &mut tuples)?;
62
63        Ok(DerivationTrace { root: *id, tuples })
64    }
65
66    fn explain_plan(&self, plan: &PhaseGraph) -> Result<PlanExplanation, ExplainError> {
67        Ok(PlanExplanation {
68            summary: format!(
69                "Phase graph with {} node(s) and {} edge(s)",
70                plan.nodes.len(),
71                plan.edges.len()
72            ),
73            phase_graph: plan.clone(),
74        })
75    }
76}
77
78#[derive(Debug, Error)]
79pub enum ExplainError {
80    #[error("unknown tuple {0}")]
81    UnknownTuple(TupleId),
82    #[error("tuple {tuple} references missing parent tuple {parent}")]
83    DanglingParentTuple { tuple: TupleId, parent: TupleId },
84}
85
86#[cfg(test)]
87mod tests {
88    use super::{ExplainError, Explainer, InMemoryExplainer};
89    use aether_ast::{
90        DerivedTuple, DerivedTupleMetadata, PredicateId, RuleId, Tuple, TupleId, Value,
91    };
92    use aether_runtime::{DerivedSet, RuntimeIteration};
93
94    fn tuple(
95        id: u64,
96        values: &[u64],
97        parent_tuple_ids: &[u64],
98        source_datom_ids: &[u64],
99        iteration: usize,
100    ) -> DerivedTuple {
101        DerivedTuple {
102            tuple: Tuple {
103                id: TupleId::new(id),
104                predicate: PredicateId::new(1),
105                values: values.iter().copied().map(Value::U64).collect(),
106            },
107            metadata: DerivedTupleMetadata {
108                rule_id: RuleId::new(1),
109                predicate_id: PredicateId::new(1),
110                stratum: 0,
111                scc_id: 0,
112                iteration,
113                parent_tuple_ids: parent_tuple_ids.iter().copied().map(TupleId::new).collect(),
114                source_datom_ids: source_datom_ids
115                    .iter()
116                    .copied()
117                    .map(aether_ast::ElementId::new)
118                    .collect(),
119                imported_cuts: Vec::new(),
120            },
121            policy: None,
122        }
123    }
124
125    #[test]
126    fn explain_tuple_returns_recursive_trace() {
127        let derived = DerivedSet {
128            tuples: vec![
129                tuple(1, &[1, 2], &[], &[11], 1),
130                tuple(2, &[2, 3], &[], &[12], 1),
131                tuple(3, &[1, 3], &[1, 2], &[11, 12], 2),
132            ],
133            iterations: vec![
134                RuntimeIteration {
135                    iteration: 1,
136                    delta_size: 2,
137                },
138                RuntimeIteration {
139                    iteration: 2,
140                    delta_size: 1,
141                },
142                RuntimeIteration {
143                    iteration: 3,
144                    delta_size: 0,
145                },
146            ],
147            predicate_index: Default::default(),
148        };
149        let explainer = InMemoryExplainer::from_derived_set(&derived);
150
151        let trace = explainer
152            .explain_tuple(&TupleId::new(3))
153            .expect("explain recursive tuple");
154
155        assert_eq!(trace.root, TupleId::new(3));
156        assert_eq!(
157            trace
158                .tuples
159                .iter()
160                .map(|tuple| tuple.tuple.id)
161                .collect::<Vec<_>>(),
162            vec![TupleId::new(3), TupleId::new(1), TupleId::new(2)]
163        );
164        assert_eq!(trace.tuples[0].metadata.source_datom_ids.len(), 2);
165    }
166
167    #[test]
168    fn explain_tuple_reports_unknown_roots() {
169        let explainer = InMemoryExplainer::default();
170        let error = explainer
171            .explain_tuple(&TupleId::new(99))
172            .expect_err("unknown tuple should fail");
173
174        assert!(matches!(error, ExplainError::UnknownTuple(id) if id == TupleId::new(99)));
175    }
176
177    #[test]
178    fn explain_tuple_reports_dangling_parent_references() {
179        let derived = DerivedSet {
180            tuples: vec![tuple(7, &[1, 4], &[8], &[21], 2)],
181            iterations: Vec::new(),
182            predicate_index: Default::default(),
183        };
184        let explainer = InMemoryExplainer::from_derived_set(&derived);
185
186        let error = explainer
187            .explain_tuple(&TupleId::new(7))
188            .expect_err("dangling parent should fail");
189
190        assert!(matches!(
191            error,
192            ExplainError::DanglingParentTuple { tuple, parent }
193                if tuple == TupleId::new(7) && parent == TupleId::new(8)
194        ));
195    }
196}
aether_explain/lib.rs

aether_explain/
lib.rs
