presolve_compiler/
component_instance_scope.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use crate::{
4    ComponentInstanceId, ComponentInstancePlan, ComponentInstanceStatus, ComponentRootId,
5    ComponentStructuralRegionId, SemanticId,
6};
7
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct ComponentInstanceScopeNode {
10    pub id: ComponentInstanceId,
11    pub component: SemanticId,
12    pub owner_root: ComponentRootId,
13    pub depth: usize,
14    pub structural_region: Option<ComponentStructuralRegionId>,
15    pub status: ComponentInstanceStatus,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
19pub enum ComponentInstanceScopeViolation {
20    UnknownParent,
21    UnknownChild,
22    MissingParent,
23    ParentReciprocity,
24    MultipleParents,
25    InvalidRoot,
26    DepthMismatch,
27    OwnerRootMismatch,
28    Cycle,
29    Unreachable,
30    NonCanonicalOrdering,
31}
32
33#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
34pub struct ComponentInstanceScopeDiagnostic {
35    pub violation: ComponentInstanceScopeViolation,
36    pub instance: ComponentInstanceId,
37    pub related: Option<ComponentInstanceId>,
38}
39
40#[derive(Debug, Clone, PartialEq, Eq, Default)]
41pub struct ComponentInstanceScopeGraph {
42    pub nodes: BTreeMap<ComponentInstanceId, ComponentInstanceScopeNode>,
43    pub parent_by_instance: BTreeMap<ComponentInstanceId, ComponentInstanceId>,
44    pub children_by_instance: BTreeMap<ComponentInstanceId, Vec<ComponentInstanceId>>,
45    pub roots: Vec<ComponentInstanceId>,
46}
47
48impl ComponentInstanceScopeGraph {
49    #[must_use]
50    pub fn node(&self, id: &ComponentInstanceId) -> Option<&ComponentInstanceScopeNode> {
51        self.nodes.get(id)
52    }
53
54    #[must_use]
55    pub fn parent(&self, id: &ComponentInstanceId) -> Option<&ComponentInstanceId> {
56        self.parent_by_instance.get(id)
57    }
58
59    #[must_use]
60    pub fn children(&self, id: &ComponentInstanceId) -> &[ComponentInstanceId] {
61        self.children_by_instance.get(id).map_or(&[], Vec::as_slice)
62    }
63
64    #[must_use]
65    pub fn ancestors(&self, id: &ComponentInstanceId) -> Vec<&ComponentInstanceId> {
66        let mut result = Vec::new();
67        let mut seen = BTreeSet::from([id]);
68        let mut current = id;
69        while let Some(parent) = self.parent(current) {
70            if !seen.insert(parent) {
71                break;
72            }
73            result.push(parent);
74            current = parent;
75        }
76        result
77    }
78}
79
80/// Project executable H4 instances into the sole runtime composition ancestry graph.
81#[must_use]
82pub fn build_component_instance_scope_graph(
83    plan: &ComponentInstancePlan,
84) -> ComponentInstanceScopeGraph {
85    let nodes = plan
86        .instances
87        .values()
88        .map(|instance| {
89            (
90                instance.id.clone(),
91                ComponentInstanceScopeNode {
92                    id: instance.id.clone(),
93                    component: instance.component.clone(),
94                    owner_root: instance.owner_root.clone(),
95                    depth: instance.depth,
96                    structural_region: instance.structural_region.clone(),
97                    status: instance.status,
98                },
99            )
100        })
101        .collect::<BTreeMap<_, _>>();
102    let parent_by_instance = plan
103        .instances
104        .values()
105        .filter_map(|instance| {
106            instance
107                .parent_instance
108                .as_ref()
109                .map(|parent| (instance.id.clone(), parent.clone()))
110        })
111        .collect::<BTreeMap<_, _>>();
112    let mut children_by_instance = nodes
113        .keys()
114        .cloned()
115        .map(|id| (id, Vec::new()))
116        .collect::<BTreeMap<_, _>>();
117    for (child, parent) in &parent_by_instance {
118        if let Some(children) = children_by_instance.get_mut(parent) {
119            children.push(child.clone());
120        }
121    }
122    for children in children_by_instance.values_mut() {
123        children.sort();
124    }
125    let roots = plan
126        .instances
127        .values()
128        .filter(|instance| instance.parent_instance.is_none())
129        .map(|instance| instance.id.clone())
130        .collect();
131
132    ComponentInstanceScopeGraph {
133        nodes,
134        parent_by_instance,
135        children_by_instance,
136        roots,
137    }
138}
139
140/// Validate graph reciprocity, reachability, depth, root, cycle, and ordering invariants.
141#[must_use]
142#[allow(clippy::too_many_lines)]
143pub fn validate_component_instance_scope_graph(
144    graph: &ComponentInstanceScopeGraph,
145) -> Vec<ComponentInstanceScopeDiagnostic> {
146    let mut diagnostics = Vec::new();
147    let root_set = graph.roots.iter().cloned().collect::<BTreeSet<_>>();
148
149    if !is_sorted_unique(&graph.roots) {
150        if let Some(root) = graph.roots.first() {
151            push_diagnostic(
152                &mut diagnostics,
153                ComponentInstanceScopeViolation::NonCanonicalOrdering,
154                root,
155                None,
156            );
157        }
158    }
159
160    for (id, node) in &graph.nodes {
161        match graph.parent_by_instance.get(id) {
162            None if node.depth == 0 && root_set.contains(id) => {}
163            None if node.depth > 0 => push_diagnostic(
164                &mut diagnostics,
165                ComponentInstanceScopeViolation::MissingParent,
166                id,
167                None,
168            ),
169            None => push_diagnostic(
170                &mut diagnostics,
171                ComponentInstanceScopeViolation::InvalidRoot,
172                id,
173                None,
174            ),
175            Some(parent) => {
176                if graph.nodes.contains_key(parent) {
177                    if graph.node(parent).is_some_and(|parent_node| {
178                        node.depth != parent_node.depth.saturating_add(1)
179                    }) {
180                        push_diagnostic(
181                            &mut diagnostics,
182                            ComponentInstanceScopeViolation::DepthMismatch,
183                            id,
184                            Some(parent),
185                        );
186                    }
187                    if graph
188                        .node(parent)
189                        .is_some_and(|parent_node| node.owner_root != parent_node.owner_root)
190                    {
191                        push_diagnostic(
192                            &mut diagnostics,
193                            ComponentInstanceScopeViolation::OwnerRootMismatch,
194                            id,
195                            Some(parent),
196                        );
197                    }
198                    if !graph.children(parent).contains(id) {
199                        push_diagnostic(
200                            &mut diagnostics,
201                            ComponentInstanceScopeViolation::ParentReciprocity,
202                            id,
203                            Some(parent),
204                        );
205                    }
206                } else {
207                    push_diagnostic(
208                        &mut diagnostics,
209                        ComponentInstanceScopeViolation::UnknownParent,
210                        id,
211                        Some(parent),
212                    );
213                }
214                if root_set.contains(id) {
215                    push_diagnostic(
216                        &mut diagnostics,
217                        ComponentInstanceScopeViolation::InvalidRoot,
218                        id,
219                        Some(parent),
220                    );
221                }
222            }
223        }
224    }
225
226    let mut observed_parents =
227        BTreeMap::<ComponentInstanceId, BTreeSet<ComponentInstanceId>>::new();
228    for (parent, children) in &graph.children_by_instance {
229        if !graph.nodes.contains_key(parent) {
230            push_diagnostic(
231                &mut diagnostics,
232                ComponentInstanceScopeViolation::UnknownParent,
233                parent,
234                None,
235            );
236        }
237        if !is_sorted_unique(children) {
238            push_diagnostic(
239                &mut diagnostics,
240                ComponentInstanceScopeViolation::NonCanonicalOrdering,
241                parent,
242                None,
243            );
244        }
245        for child in children {
246            if !graph.nodes.contains_key(child) {
247                push_diagnostic(
248                    &mut diagnostics,
249                    ComponentInstanceScopeViolation::UnknownChild,
250                    parent,
251                    Some(child),
252                );
253                continue;
254            }
255            observed_parents
256                .entry(child.clone())
257                .or_default()
258                .insert(parent.clone());
259            if graph.parent(child) != Some(parent) {
260                push_diagnostic(
261                    &mut diagnostics,
262                    ComponentInstanceScopeViolation::ParentReciprocity,
263                    child,
264                    Some(parent),
265                );
266            }
267        }
268    }
269    for (child, parents) in observed_parents {
270        if parents.len() > 1 {
271            push_diagnostic(
272                &mut diagnostics,
273                ComponentInstanceScopeViolation::MultipleParents,
274                &child,
275                parents.iter().next(),
276            );
277        }
278    }
279
280    for id in graph.nodes.keys() {
281        if parent_chain_cycles(graph, id) {
282            push_diagnostic(
283                &mut diagnostics,
284                ComponentInstanceScopeViolation::Cycle,
285                id,
286                graph.parent(id),
287            );
288        }
289    }
290
291    let mut reachable = BTreeSet::new();
292    for root in &graph.roots {
293        collect_reachable(graph, root, &mut reachable);
294    }
295    for id in graph.nodes.keys().filter(|id| !reachable.contains(*id)) {
296        push_diagnostic(
297            &mut diagnostics,
298            ComponentInstanceScopeViolation::Unreachable,
299            id,
300            graph.parent(id),
301        );
302    }
303
304    diagnostics.sort();
305    diagnostics.dedup();
306    diagnostics
307}
308
309fn parent_chain_cycles(graph: &ComponentInstanceScopeGraph, id: &ComponentInstanceId) -> bool {
310    let mut seen = BTreeSet::new();
311    let mut current = id;
312    while let Some(parent) = graph.parent(current) {
313        if !seen.insert(current) || parent == id {
314            return true;
315        }
316        current = parent;
317    }
318    false
319}
320
321fn collect_reachable(
322    graph: &ComponentInstanceScopeGraph,
323    id: &ComponentInstanceId,
324    reachable: &mut BTreeSet<ComponentInstanceId>,
325) {
326    if !reachable.insert(id.clone()) {
327        return;
328    }
329    for child in graph.children(id) {
330        collect_reachable(graph, child, reachable);
331    }
332}
333
334fn is_sorted_unique<T: Ord>(items: &[T]) -> bool {
335    items.windows(2).all(|pair| pair[0] < pair[1])
336}
337
338fn push_diagnostic(
339    diagnostics: &mut Vec<ComponentInstanceScopeDiagnostic>,
340    violation: ComponentInstanceScopeViolation,
341    instance: &ComponentInstanceId,
342    related: Option<&ComponentInstanceId>,
343) {
344    diagnostics.push(ComponentInstanceScopeDiagnostic {
345        violation,
346        instance: instance.clone(),
347        related: related.cloned(),
348    });
349}
350
351#[cfg(test)]
352mod tests {
353    use crate::{
354        build_application_semantic_model, validate_component_instance_scope_graph,
355        ComponentInstanceScopeViolation,
356    };
357
358    #[test]
359    fn builds_exact_repeated_instance_ancestry_and_excludes_blocked_plans() {
360        let asm = build_application_semantic_model(&presolve_parser::parse_file(
361            "src/Scope.tsx",
362            r#"
363@component("x-card") class Card extends Component { render() { return <article />; } }
364@component("x-shell") class Shell extends Component { render() { return <section><Card /></section>; } }
365@component("x-page") class Page extends Component { render() { return <main><Shell /><Card /><Missing /></main>; } }
366"#,
367        ));
368        let graph = &asm.component_instance_scope;
369
370        assert_eq!(graph.nodes.len(), 4);
371        assert_eq!(graph.roots.len(), 1);
372        assert!(validate_component_instance_scope_graph(graph).is_empty());
373        assert!(asm
374            .blocked_component_instances()
375            .iter()
376            .all(|blocked| !graph.nodes.contains_key(&blocked.id)));
377        let nested_card = graph
378            .nodes
379            .values()
380            .find(|node| node.depth == 2)
381            .expect("nested Card");
382        let ancestors = graph.ancestors(&nested_card.id);
383        assert_eq!(ancestors.len(), 2);
384        assert_eq!(graph.children(ancestors[0]).len(), 1);
385    }
386
387    #[test]
388    fn reports_deterministic_integrity_violations_on_mutated_graphs() {
389        let asm = build_application_semantic_model(&presolve_parser::parse_file(
390            "src/InvalidScope.tsx",
391            r#"
392@component("x-child") class Child extends Component { render() { return <span />; } }
393@component("x-page") class Page extends Component { render() { return <main><Child /><Child /></main>; } }
394"#,
395        ));
396        let mut graph = asm.component_instance_scope.clone();
397        let root = graph.roots[0].clone();
398        let child = graph.children(&root)[0].clone();
399        let sibling = graph.children(&root)[1].clone();
400        graph.parent_by_instance.insert(root.clone(), child.clone());
401        graph
402            .children_by_instance
403            .get_mut(&child)
404            .unwrap()
405            .push(root.clone());
406        graph
407            .children_by_instance
408            .get_mut(&root)
409            .unwrap()
410            .push(child.clone());
411        graph
412            .children_by_instance
413            .get_mut(&sibling)
414            .unwrap()
415            .push(child.clone());
416        graph.nodes.get_mut(&child).unwrap().depth = 9;
417        graph.nodes.remove(&sibling);
418
419        let first = validate_component_instance_scope_graph(&graph);
420        let second = validate_component_instance_scope_graph(&graph);
421        assert_eq!(first, second);
422        let violations = first
423            .iter()
424            .map(|diagnostic| diagnostic.violation)
425            .collect::<std::collections::BTreeSet<_>>();
426        assert!(violations.contains(&ComponentInstanceScopeViolation::InvalidRoot));
427        assert!(violations.contains(&ComponentInstanceScopeViolation::DepthMismatch));
428        assert!(violations.contains(&ComponentInstanceScopeViolation::Cycle));
429        assert!(violations.contains(&ComponentInstanceScopeViolation::MultipleParents));
430        assert!(violations.contains(&ComponentInstanceScopeViolation::NonCanonicalOrdering));
431        assert!(violations.contains(&ComponentInstanceScopeViolation::UnknownChild));
432        assert!(violations.contains(&ComponentInstanceScopeViolation::UnknownParent));
433    }
434}
presolve_compiler/component_instance_scope.rs

presolve_compiler/
component_instance_scope.rs
