xlog_ir/
plan.rs

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

xlog_ir/
plan.rs
