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 crate::metadata::EntityTypeMeta;
11use std::any::TypeId;
12use std::collections::{HashMap, VecDeque};
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.entry(nav.related_type_id).or_default().push(*type_id);
36                }
37            }
38        }
39        Self { edges, nodes }
40    }
41
42    /// Kahn's algorithm topological sort: principals first, dependents after.
43    /// Self-edges (type depends on itself) are excluded from in-degree
44    /// counting — same-type instance ordering is handled by the cascade
45    /// drain + fixup pipeline.
46    pub fn topological_sort(&self) -> Vec<TypeId> {
47        let mut in_degree: HashMap<TypeId, usize> = HashMap::new();
48        for node in &self.nodes {
49            in_degree.entry(*node).or_insert(0);
50        }
51        for (child, parents) in &self.edges {
52            let count = parents.iter().filter(|p| **p != *child).count();
53            *in_degree.entry(*child).or_insert(0) += count;
54        }
55
56        let mut queue: VecDeque<TypeId> = in_degree
57            .iter()
58            .filter(|(_, &deg)| deg == 0)
59            .map(|(&k, _)| k)
60            .collect();
61        let mut result: Vec<TypeId> = Vec::new();
62        while let Some(node) = queue.pop_front() {
63            result.push(node);
64            for (child, parents) in &self.edges {
65                if parents.iter().any(|p| *p == node && *p != *child) {
66                    let deg = in_degree.entry(*child).or_insert(0);
67                    if *deg > 0 {
68                        *deg -= 1;
69                    }
70                    if *deg == 0 && !result.contains(child) && !queue.contains(child) {
71                        queue.push_back(*child);
72                    }
73                }
74            }
75        }
76        for node in &self.nodes {
77            if !result.contains(node) {
78                result.push(*node);
79            }
80        }
81        result
82    }
83
84    /// Deletion order: reverse topological (dependents before principals).
85    pub fn deletion_order(&self) -> Vec<TypeId> {
86        let mut order = self.topological_sort();
87        order.reverse();
88        order
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn empty_graph_returns_empty() {
98        let metas: HashMap<TypeId, EntityTypeMeta> = HashMap::new();
99        let graph = DependencyGraph::build(&metas);
100        assert!(graph.topological_sort().is_empty());
101    }
102
103    #[test]
104    fn deletion_order_is_reverse_of_insert() {
105        let metas: HashMap<TypeId, EntityTypeMeta> = HashMap::new();
106        let graph = DependencyGraph::build(&metas);
107        let insert = graph.topological_sort();
108        let delete = graph.deletion_order();
109        assert_eq!(delete, insert.into_iter().rev().collect::<Vec<_>>());
110    }
111}
rust_ef/dependency_graph.rs

rust_ef/
dependency_graph.rs
