xlog_ir/
plan.rs

1//! Execution plan representation
2
3use crate::metadata::RirMeta;
4use crate::rir::RirNode;
5use xlog_core::RelId;
6
7/// Strongly Connected Component in the dependency graph
8#[derive(Debug, Clone)]
9pub struct Scc {
10    /// Unique SCC identifier
11    pub id: u32,
12    /// Predicate names in this SCC
13    pub predicates: Vec<String>,
14    /// Whether this SCC contains recursion
15    pub is_recursive: bool,
16}
17
18/// Stratum in stratified evaluation
19#[derive(Debug, Clone)]
20pub struct Stratum {
21    /// Stratum number (0 = base)
22    pub id: u32,
23    /// SCCs in this stratum (topologically ordered)
24    pub sccs: Vec<u32>,
25}
26
27/// Compiled rule ready for execution
28#[derive(Debug, Clone)]
29pub struct CompiledRule {
30    /// Head predicate name
31    pub head: String,
32    /// RIR tree for rule body
33    pub body: RirNode,
34    /// Metadata for cost estimation
35    pub meta: RirMeta,
36}
37
38/// Complete execution plan for a program
39#[derive(Debug, Clone)]
40pub struct ExecutionPlan {
41    /// SCCs in dependency order
42    pub sccs: Vec<Scc>,
43    /// Strata for negation ordering
44    pub strata: Vec<Stratum>,
45    /// Compiled rules grouped by SCC
46    pub rules_by_scc: Vec<Vec<CompiledRule>>,
47    /// Total estimated memory peak (bytes)
48    pub est_memory_peak: u64,
49    /// Relation arities known at lowering time (every predicate the
50    /// lowerer assigned a RelId). Consumed by shape promoters that
51    /// must size Scan leaves without schema access (general Free Join
52    /// multiway promotion).
53    pub rel_arities: std::collections::HashMap<RelId, usize>,
54}
55
56impl ExecutionPlan {
57    /// Create a new execution plan from SCCs
58    pub fn new(sccs: Vec<Scc>) -> Self {
59        Self {
60            sccs,
61            strata: vec![],
62            rules_by_scc: vec![],
63            est_memory_peak: 0,
64            rel_arities: std::collections::HashMap::new(),
65        }
66    }
67
68    /// Add strata to the plan
69    pub fn with_strata(mut self, strata: Vec<Stratum>) -> Self {
70        self.strata = strata;
71        self
72    }
73
74    /// Get the number of recursive SCCs
75    pub fn recursive_scc_count(&self) -> usize {
76        self.sccs.iter().filter(|s| s.is_recursive).count()
77    }
78
79    /// Check if this plan has any recursion
80    pub fn has_recursion(&self) -> bool {
81        self.sccs.iter().any(|s| s.is_recursive)
82    }
83}
84
85/// Builder for execution plans
86#[derive(Debug, Default)]
87pub struct PlanBuilder {
88    sccs: Vec<Scc>,
89    strata: Vec<Stratum>,
90    rules: Vec<Vec<CompiledRule>>,
91}
92
93impl PlanBuilder {
94    /// Create a new empty plan builder.
95    pub fn new() -> Self {
96        Self::default()
97    }
98
99    /// Append a strongly connected component to the plan.
100    pub fn add_scc(&mut self, scc: Scc) -> &mut Self {
101        self.sccs.push(scc);
102        self.rules.push(vec![]);
103        self
104    }
105
106    /// Add a compiled rule to the given SCC (by index).
107    pub fn add_rule(&mut self, scc_id: u32, rule: CompiledRule) -> &mut Self {
108        if let Some(rules) = self.rules.get_mut(scc_id as usize) {
109            rules.push(rule);
110        }
111        self
112    }
113
114    /// Append a stratum to the plan.
115    pub fn add_stratum(&mut self, stratum: Stratum) -> &mut Self {
116        self.strata.push(stratum);
117        self
118    }
119
120    /// Consume the builder and produce the final [`ExecutionPlan`].
121    pub fn build(self) -> ExecutionPlan {
122        ExecutionPlan {
123            sccs: self.sccs,
124            strata: self.strata,
125            rules_by_scc: self.rules,
126            est_memory_peak: 0,
127            rel_arities: std::collections::HashMap::new(),
128        }
129    }
130}
131
132#[cfg(test)]
133mod tests {
134    use super::*;
135
136    #[test]
137    fn test_scc_ordering() {
138        let sccs = vec![
139            Scc {
140                id: 0,
141                predicates: vec!["edge".into()],
142                is_recursive: false,
143            },
144            Scc {
145                id: 1,
146                predicates: vec!["reach".into()],
147                is_recursive: true,
148            },
149        ];
150        let plan = ExecutionPlan::new(sccs);
151        assert_eq!(plan.sccs.len(), 2);
152        assert!(!plan.sccs[0].is_recursive);
153        assert!(plan.sccs[1].is_recursive);
154    }
155
156    #[test]
157    fn test_stratum_assignment() {
158        let strata = [
159            Stratum {
160                id: 0,
161                sccs: vec![0, 1],
162            },
163            Stratum {
164                id: 1,
165                sccs: vec![2],
166            },
167        ];
168        assert_eq!(strata[0].sccs.len(), 2);
169    }
170
171    #[test]
172    fn test_plan_builder() {
173        let mut builder = PlanBuilder::new();
174        builder.add_scc(Scc {
175            id: 0,
176            predicates: vec!["p".into()],
177            is_recursive: false,
178        });
179        builder.add_stratum(Stratum {
180            id: 0,
181            sccs: vec![0],
182        });
183        let plan = builder.build();
184        assert_eq!(plan.sccs.len(), 1);
185        assert_eq!(plan.strata.len(), 1);
186    }
187
188    #[test]
189    fn test_has_recursion() {
190        let non_recursive = ExecutionPlan::new(vec![Scc {
191            id: 0,
192            predicates: vec!["p".into()],
193            is_recursive: false,
194        }]);
195        assert!(!non_recursive.has_recursion());
196
197        let recursive = ExecutionPlan::new(vec![Scc {
198            id: 0,
199            predicates: vec!["reach".into()],
200            is_recursive: true,
201        }]);
202        assert!(recursive.has_recursion());
203    }
204}
xlog_ir/plan.rs

xlog_ir/
plan.rs
