rust_ef/
dependency_graph.rs

1//! Dependency graph and topological sort — determines entity save order.
2//!
3//! Principals (independent entities) are ordered before dependents (entities
4//! with foreign keys pointing at principals). Delete order is the reverse.
5//!
6//! Self-referential relationships (a type with a HasMany pointing at itself)
7//! do not affect type-level ordering — instance-level ordering is handled by
8//! the cascade drain + FK fixup pipeline.
9
10use std::any::TypeId;
11use std::collections::{HashMap, VecDeque};
12use crate::metadata::EntityTypeMeta;
13
14pub struct DependencyGraph {
15    /// child_type_id → list of principal type_ids it depends on.
16    edges: HashMap<TypeId, Vec<TypeId>>,
17    nodes: Vec<TypeId>,
18}
19
20impl DependencyGraph {
21    /// Builds the graph from entity metadata. Edges come from HasMany and
22    /// ManyToMany navigations: `related_type_id` (child) depends on `type_id`
23    /// (principal).
24    pub fn build(metas: &HashMap<TypeId, EntityTypeMeta>) -> Self {
25        let mut edges: HashMap<TypeId, Vec<TypeId>> = HashMap::new();
26        let mut nodes: Vec<TypeId> = Vec::new();
27        for (type_id, meta) in metas {
28            nodes.push(*type_id);
29            for nav in &meta.navigations {
30                if matches!(
31                    nav.kind,
32                    crate::metadata::NavigationKind::HasMany
33                        | crate::metadata::NavigationKind::ManyToMany
34                ) {
35                    edges
36                        .entry(nav.related_type_id)
37                        .or_default()
38                        .push(*type_id);
39                }
40            }
41        }
42        Self { edges, nodes }
43    }
44
45    /// Kahn's algorithm topological sort: principals first, dependents after.
46    /// Self-edges (type depends on itself) are excluded from in-degree
47    /// counting — same-type instance ordering is handled by the cascade
48    /// drain + fixup pipeline.
49    pub fn topological_sort(&self) -> Vec<TypeId> {
50        let mut in_degree: HashMap<TypeId, usize> = HashMap::new();
51        for node in &self.nodes {
52            in_degree.entry(*node).or_insert(0);
53        }
54        for (child, parents) in &self.edges {
55            let count = parents.iter().filter(|p| **p != *child).count();
56            *in_degree.entry(*child).or_insert(0) += count;
57        }
58
59        let mut queue: VecDeque<TypeId> = in_degree
60            .iter()
61            .filter(|(_, &deg)| deg == 0)
62            .map(|(&k, _)| k)
63            .collect();
64        let mut result: Vec<TypeId> = Vec::new();
65        while let Some(node) = queue.pop_front() {
66            result.push(node);
67            for (child, parents) in &self.edges {
68                if parents.iter().any(|p| *p == node && *p != *child) {
69                    let deg = in_degree.entry(*child).or_insert(0);
70                    if *deg > 0 {
71                        *deg -= 1;
72                    }
73                    if *deg == 0 && !result.contains(child) && !queue.contains(child) {
74                        queue.push_back(*child);
75                    }
76                }
77            }
78        }
79        for node in &self.nodes {
80            if !result.contains(node) {
81                result.push(*node);
82            }
83        }
84        result
85    }
86
87    /// Deletion order: reverse topological (dependents before principals).
88    pub fn deletion_order(&self) -> Vec<TypeId> {
89        let mut order = self.topological_sort();
90        order.reverse();
91        order
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn empty_graph_returns_empty() {
101        let metas: HashMap<TypeId, EntityTypeMeta> = HashMap::new();
102        let graph = DependencyGraph::build(&metas);
103        assert!(graph.topological_sort().is_empty());
104    }
105
106    #[test]
107    fn deletion_order_is_reverse_of_insert() {
108        let metas: HashMap<TypeId, EntityTypeMeta> = HashMap::new();
109        let graph = DependencyGraph::build(&metas);
110        let insert = graph.topological_sort();
111        let delete = graph.deletion_order();
112        assert_eq!(delete, insert.into_iter().rev().collect::<Vec<_>>());
113    }
114}
rust_ef/dependency_graph.rs

rust_ef/
dependency_graph.rs
