sim_lib_class/
lineage.rs

1//! Bounded, evidence-carrying class lineage policies.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5/// A loader-neutral view of declared class parents.
6pub trait LineageGraph {
7    type Node: Clone + Ord;
8
9    /// Returns parents in the order declared by the language adapter.
10    fn declared_parents(&self, node: &Self::Node) -> Vec<Self::Node>;
11}
12
13/// Independent admission limits for a lineage computation.
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub struct LineageBudget {
16    pub nodes: usize,
17    pub work: usize,
18}
19
20/// The precedence rule made impossible by a C3 merge.
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub struct PrecedenceConstraint<N> {
23    /// The node a remaining parent linearization requires first.
24    pub before: N,
25    /// The blocked candidate that the remaining linearization requires later.
26    pub after: N,
27}
28
29/// Exact, inspectable failure evidence from a lineage policy.
30#[derive(Clone, Debug, PartialEq, Eq)]
31pub enum LineageError<N> {
32    Cycle {
33        path: Vec<N>,
34    },
35    ConflictingPrecedence {
36        parents: (N, N),
37        constraint: PrecedenceConstraint<N>,
38    },
39    NodeBudgetExhausted {
40        limit: usize,
41        required: usize,
42    },
43    WorkBudgetExhausted {
44        limit: usize,
45        performed: usize,
46    },
47}
48
49/// Pluggable class-linearization policy.
50pub trait LineagePolicy<G: LineageGraph> {
51    fn linearize(
52        &self,
53        graph: &G,
54        root: &G::Node,
55        budget: LineageBudget,
56    ) -> Result<Vec<G::Node>, LineageError<G::Node>>;
57}
58
59#[derive(Clone, Copy, Debug, Default)]
60pub struct C3Policy;
61
62#[derive(Clone, Copy, Debug, Default)]
63pub struct DeclaredOrderPolicy;
64
65#[derive(Clone, Copy)]
66struct Meter {
67    limit: usize,
68    used: usize,
69}
70
71type Traversal<N> = (Vec<N>, BTreeMap<N, Vec<N>>);
72
73impl Meter {
74    fn charge<N>(&mut self) -> Result<(), LineageError<N>> {
75        if self.used == self.limit {
76            return Err(LineageError::WorkBudgetExhausted {
77                limit: self.limit,
78                performed: self.used,
79            });
80        }
81        self.used += 1;
82        Ok(())
83    }
84}
85
86fn postorder<G: LineageGraph>(
87    graph: &G,
88    root: &G::Node,
89    budget: LineageBudget,
90    work: &mut Meter,
91) -> Result<Traversal<G::Node>, LineageError<G::Node>> {
92    let mut parents = BTreeMap::new();
93    let mut state = BTreeMap::<G::Node, u8>::new();
94    let mut path = Vec::new();
95    let mut order = Vec::new();
96    let mut stack = vec![(root.clone(), false)];
97
98    while let Some((node, leaving)) = stack.pop() {
99        work.charge()?;
100        if leaving {
101            state.insert(node.clone(), 2);
102            let popped = path.pop();
103            debug_assert!(popped.as_ref() == Some(&node));
104            order.push(node);
105            continue;
106        }
107        match state.get(&node).copied() {
108            Some(2) => continue,
109            Some(1) => {
110                let start = path.iter().position(|item| item == &node).unwrap_or(0);
111                let mut cycle = path[start..].to_vec();
112                cycle.push(node);
113                return Err(LineageError::Cycle { path: cycle });
114            }
115            None => {}
116            _ => unreachable!(),
117        }
118        let required = state.len() + 1;
119        if required > budget.nodes {
120            return Err(LineageError::NodeBudgetExhausted {
121                limit: budget.nodes,
122                required,
123            });
124        }
125        state.insert(node.clone(), 1);
126        path.push(node.clone());
127        let direct = graph.declared_parents(&node);
128        parents.insert(node.clone(), direct.clone());
129        stack.push((node, true));
130        for parent in direct.into_iter().rev() {
131            stack.push((parent, false));
132        }
133    }
134    Ok((order, parents))
135}
136
137impl<G: LineageGraph> LineagePolicy<G> for DeclaredOrderPolicy {
138    fn linearize(
139        &self,
140        graph: &G,
141        root: &G::Node,
142        budget: LineageBudget,
143    ) -> Result<Vec<G::Node>, LineageError<G::Node>> {
144        let mut work = Meter {
145            limit: budget.work,
146            used: 0,
147        };
148        let (_, parents) = postorder(graph, root, budget, &mut work)?;
149        let mut result = Vec::new();
150        let mut seen = BTreeSet::new();
151        let mut stack = vec![root.clone()];
152        while let Some(node) = stack.pop() {
153            work.charge()?;
154            if !seen.insert(node.clone()) {
155                continue;
156            }
157            result.push(node.clone());
158            for parent in parents.get(&node).into_iter().flatten().rev() {
159                stack.push(parent.clone());
160            }
161        }
162        Ok(result)
163    }
164}
165
166impl<G: LineageGraph> LineagePolicy<G> for C3Policy {
167    fn linearize(
168        &self,
169        graph: &G,
170        root: &G::Node,
171        budget: LineageBudget,
172    ) -> Result<Vec<G::Node>, LineageError<G::Node>> {
173        let mut work = Meter {
174            limit: budget.work,
175            used: 0,
176        };
177        let (order, parents) = postorder(graph, root, budget, &mut work)?;
178        let mut complete = BTreeMap::<G::Node, Vec<G::Node>>::new();
179        for node in order {
180            let direct = &parents[&node];
181            let mut sequences: Vec<Vec<G::Node>> = direct
182                .iter()
183                .map(|parent| complete[parent].clone())
184                .collect();
185            sequences.push(direct.clone());
186            let mut merged = vec![node.clone()];
187            loop {
188                sequences.retain(|sequence| !sequence.is_empty());
189                if sequences.is_empty() {
190                    break;
191                }
192                let mut selected = None;
193                for sequence in &sequences {
194                    work.charge()?;
195                    let candidate = &sequence[0];
196                    if sequences
197                        .iter()
198                        .all(|other| !other[1..].contains(candidate))
199                    {
200                        selected = Some(candidate.clone());
201                        break;
202                    }
203                }
204                let Some(candidate) = selected else {
205                    let before = sequences[0][0].clone();
206                    let blocker = sequences
207                        .iter()
208                        .find(|sequence| sequence[1..].contains(&before))
209                        .expect("blocked C3 head");
210                    let required_before = blocker[0].clone();
211                    return Err(LineageError::ConflictingPrecedence {
212                        parents: (before.clone(), required_before.clone()),
213                        constraint: PrecedenceConstraint {
214                            before: required_before,
215                            after: before,
216                        },
217                    });
218                };
219                merged.push(candidate.clone());
220                for sequence in &mut sequences {
221                    if sequence.first() == Some(&candidate) {
222                        sequence.remove(0);
223                    }
224                }
225            }
226            complete.insert(node, merged);
227        }
228        Ok(complete.remove(root).expect("root visited"))
229    }
230}
231
232#[cfg(test)]
233mod tests {
234    use super::*;
235
236    #[derive(Default)]
237    struct Graph(BTreeMap<usize, Vec<usize>>);
238    impl LineageGraph for Graph {
239        type Node = usize;
240        fn declared_parents(&self, node: &usize) -> Vec<usize> {
241            self.0.get(node).cloned().unwrap_or_default()
242        }
243    }
244    fn generous() -> LineageBudget {
245        LineageBudget {
246            nodes: 100,
247            work: 10_000,
248        }
249    }
250
251    #[test]
252    fn classic_c3_conflict_reports_parents_and_constraint() {
253        let graph = Graph(BTreeMap::from([
254            (1, vec![]),
255            (2, vec![]),
256            (3, vec![1, 2]),
257            (4, vec![2, 1]),
258            (5, vec![3, 4]),
259        ]));
260        assert_eq!(
261            C3Policy.linearize(&graph, &5, generous()),
262            Err(LineageError::ConflictingPrecedence {
263                parents: (1, 2),
264                constraint: PrecedenceConstraint {
265                    before: 2,
266                    after: 1
267                }
268            })
269        );
270    }
271
272    #[test]
273    fn ten_thousand_deep_hostile_chain_exhausts_without_recursion() {
274        let graph = Graph((1..10_000).map(|node| (node, vec![node - 1])).collect());
275        assert_eq!(
276            C3Policy.linearize(
277                &graph,
278                &9_999,
279                LineageBudget {
280                    nodes: 512,
281                    work: 20_000
282                }
283            ),
284            Err(LineageError::NodeBudgetExhausted {
285                limit: 512,
286                required: 513
287            })
288        );
289    }
290
291    #[test]
292    fn exact_cycle_path_is_retained() {
293        let graph = Graph(BTreeMap::from([(1, vec![2]), (2, vec![3]), (3, vec![1])]));
294        assert_eq!(
295            DeclaredOrderPolicy.linearize(&graph, &1, generous()),
296            Err(LineageError::Cycle {
297                path: vec![1, 2, 3, 1]
298            })
299        );
300    }
301
302    #[test]
303    fn both_policies_are_deterministic_across_graph_insertion_orders() {
304        let rows = [(0, vec![]), (1, vec![0]), (2, vec![0]), (3, vec![1, 2])];
305        let forward = Graph(rows.clone().into_iter().collect());
306        let reverse = Graph(rows.into_iter().rev().collect());
307        assert_eq!(
308            C3Policy.linearize(&forward, &3, generous()).unwrap(),
309            vec![3, 1, 2, 0]
310        );
311        assert_eq!(
312            C3Policy.linearize(&forward, &3, generous()),
313            C3Policy.linearize(&reverse, &3, generous())
314        );
315        assert_eq!(
316            DeclaredOrderPolicy.linearize(&forward, &3, generous()),
317            DeclaredOrderPolicy.linearize(&reverse, &3, generous())
318        );
319    }
320}
sim_lib_class/lineage.rs

sim_lib_class/
lineage.rs
