gaman_core/
graphs.rs

1use std::collections::{HashMap, HashSet};
2
3use thiserror::Error;
4
5use crate::migrations::Migration;
6
7#[derive(Debug, Error)]
8pub enum GraphError {
9    #[error("duplicate migration id: {0}")]
10    DuplicateId(String),
11    #[error("cycle detected in migration graph")]
12    CycleDetected,
13    #[error("multiple heads detected — run make --merge to resolve")]
14    Conflict,
15    #[error("unknown dependency '{dep}' referenced by '{migration}'")]
16    UnknownDependency { migration: String, dep: String },
17    #[error("no migrations in graph")]
18    Empty,
19    #[error(
20        "invalid migration id '{0}': only lowercase letters, digits, and underscores are allowed (namespaced ids like 'auth/0001_init' are set automatically by embedded children)"
21    )]
22    InvalidId(String),
23    #[error("unknown migration id or prefix '{0}'")]
24    UnknownId(String),
25    #[error("migration id prefix '{prefix}' is ambiguous: {matches}")]
26    AmbiguousId { prefix: String, matches: String },
27}
28
29/// A single node in the migration DAG.
30#[derive(Debug, Clone)]
31pub struct MigrationNode {
32    pub migration: Migration,
33}
34
35/// Directed acyclic graph of migrations.
36/// Edges: dependency → dependent (A → B means B depends on A).
37#[derive(Debug, Default)]
38pub struct MigrationGraph {
39    nodes: HashMap<String, MigrationNode>,
40}
41
42impl MigrationGraph {
43    pub fn new() -> Self {
44        Self::default()
45    }
46
47    /// Add a migration to the graph.
48    pub fn add(&mut self, migration: Migration) -> Result<(), GraphError> {
49        let id = migration.id.clone();
50        if self.nodes.contains_key(&id) {
51            return Err(GraphError::DuplicateId(id));
52        }
53        self.nodes.insert(id, MigrationNode { migration });
54        Ok(())
55    }
56
57    /// Validate that an id is safe as a filename and unambiguous.
58    /// Only lowercase letters, digits, and underscores are allowed.
59    /// Called by Migrator before writing any new migration file.
60    pub fn validate_id(id: &str) -> Result<(), GraphError> {
61        if id.is_empty()
62            || !id
63                .chars()
64                .all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || c == '_')
65        {
66            return Err(GraphError::InvalidId(id.to_string()));
67        }
68        Ok(())
69    }
70
71    /// Return IDs of all head migrations (those with no dependents).
72    pub fn heads(&self) -> Vec<&str> {
73        let mut has_dependents: HashSet<&str> = HashSet::new();
74        for node in self.nodes.values() {
75            for dep in &node.migration.dependencies {
76                has_dependents.insert(dep.as_str());
77            }
78        }
79        self.nodes
80            .keys()
81            .filter(|id| !has_dependents.contains(id.as_str()))
82            .map(String::as_str)
83            .collect()
84    }
85
86    /// Return the next sequential number (1-based) for a new migration.
87    /// Parses the leading digits of each migration id (e.g. "0003_add_users" → 3).
88    /// Returns 1 if the graph is empty.
89    pub fn next_number(&self) -> u32 {
90        self.nodes
91            .keys()
92            .filter(|id| !id.contains('/'))
93            .filter_map(|id| id.split('_').next()?.parse::<u32>().ok())
94            .max()
95            .map(|n| n + 1)
96            .unwrap_or(1)
97    }
98
99    /// Returns `Err` if there are multiple heads (conflict).
100    pub fn detect_conflict(&self) -> Result<(), GraphError> {
101        let heads = self.heads();
102        if heads.len() > 1 {
103            Err(GraphError::Conflict)
104        } else {
105            Ok(())
106        }
107    }
108
109    /// Validate that the graph contains no cycles.
110    pub fn validate_acyclic(&self) -> Result<(), GraphError> {
111        // DFS-based cycle detection
112        let mut visited: HashSet<&str> = HashSet::new();
113        let mut stack: HashSet<&str> = HashSet::new();
114
115        for id in self.nodes.keys() {
116            self.dfs(id, &mut visited, &mut stack)?;
117        }
118        Ok(())
119    }
120
121    fn dfs<'a>(
122        &'a self,
123        id: &'a str,
124        visited: &mut HashSet<&'a str>,
125        stack: &mut HashSet<&'a str>,
126    ) -> Result<(), GraphError> {
127        if stack.contains(id) {
128            return Err(GraphError::CycleDetected);
129        }
130        if visited.contains(id) {
131            return Ok(());
132        }
133        stack.insert(id);
134        if let Some(node) = self.nodes.get(id) {
135            for dep in &node.migration.dependencies {
136                self.dfs(dep.as_str(), visited, stack)?;
137            }
138        }
139        stack.remove(id);
140        visited.insert(id);
141        Ok(())
142    }
143
144    /// Produce a deterministic topological order of all migration IDs.
145    pub fn topological_order(&self) -> Result<Vec<&str>, GraphError> {
146        self.validate_acyclic()?;
147        self.validate_dependencies()?;
148
149        let mut visited: HashSet<&str> = HashSet::new();
150        let mut order: Vec<&str> = Vec::new();
151
152        let mut ids: Vec<&str> = self.nodes.keys().map(String::as_str).collect();
153        ids.sort();
154
155        for id in ids {
156            self.topo_visit(id, &mut visited, &mut order);
157        }
158        Ok(order)
159    }
160
161    fn validate_dependencies(&self) -> Result<(), GraphError> {
162        for node in self.nodes.values() {
163            for dep in &node.migration.dependencies {
164                if !self.nodes.contains_key(dep.as_str()) {
165                    return Err(GraphError::UnknownDependency {
166                        migration: node.migration.id.clone(),
167                        dep: dep.clone(),
168                    });
169                }
170            }
171        }
172        Ok(())
173    }
174
175    fn topo_visit<'a>(
176        &'a self,
177        id: &'a str,
178        visited: &mut HashSet<&'a str>,
179        order: &mut Vec<&'a str>,
180    ) {
181        if visited.contains(id) {
182            return;
183        }
184        visited.insert(id);
185        if let Some(node) = self.nodes.get(id) {
186            let mut deps: Vec<&str> = node
187                .migration
188                .dependencies
189                .iter()
190                .map(String::as_str)
191                .collect();
192            deps.sort();
193            for dep in deps {
194                self.topo_visit(dep, visited, order);
195            }
196        }
197        order.push(id);
198    }
199
200    /// Create an empty merge migration that depends on all current heads.
201    pub fn create_merge_migration(&self, id: String) -> Result<Migration, GraphError> {
202        let heads = self.heads();
203        if heads.len() <= 1 {
204            return Err(GraphError::Empty);
205        }
206        let mut dependencies: Vec<String> = heads.iter().map(|s| s.to_string()).collect();
207        dependencies.sort();
208        Ok(Migration {
209            id,
210            dependencies,
211            operations: vec![],
212            atomic: true,
213        })
214    }
215
216    pub fn get(&self, id: &str) -> Option<&Migration> {
217        self.nodes.get(id).map(|n| &n.migration)
218    }
219
220    /// Resolves an exact migration id or an unambiguous prefix in graph order.
221    ///
222    /// Exact ids take precedence over prefixes. Ambiguous prefixes return all
223    /// matching ids in deterministic topological order.
224    pub fn resolve_id(&self, input: &str) -> Result<String, GraphError> {
225        if self.nodes.contains_key(input) {
226            return Ok(input.to_string());
227        }
228
229        let matches: Vec<&str> = self
230            .topological_order()?
231            .into_iter()
232            .filter(|id| id.starts_with(input))
233            .collect();
234        match matches.as_slice() {
235            [] => Err(GraphError::UnknownId(input.to_string())),
236            [id] => Ok((*id).to_string()),
237            _ => Err(GraphError::AmbiguousId {
238                prefix: input.to_string(),
239                matches: matches.join(", "),
240            }),
241        }
242    }
243}
244
245#[cfg(test)]
246mod tests {
247    use super::*;
248
249    fn migration(id: &str, deps: &[&str]) -> Migration {
250        Migration {
251            id: id.to_string(),
252            dependencies: deps.iter().map(|s| s.to_string()).collect(),
253            operations: vec![],
254            atomic: true,
255        }
256    }
257
258    fn linear_graph() -> MigrationGraph {
259        // 0001 → 0002 → 0003
260        let mut g = MigrationGraph::new();
261        g.add(migration("0001_initial", &[])).unwrap();
262        g.add(migration("0002_add_users", &["0001_initial"]))
263            .unwrap();
264        g.add(migration("0003_add_posts", &["0002_add_users"]))
265            .unwrap();
266        g
267    }
268
269    /// Adding the same migration id twice must return DuplicateId.
270    #[test]
271    fn add_duplicate_id_is_error() {
272        let mut g = MigrationGraph::new();
273        g.add(migration("0001_initial", &[])).unwrap();
274        let err = g.add(migration("0001_initial", &[])).unwrap_err();
275        assert!(matches!(err, GraphError::DuplicateId(id) if id == "0001_initial"));
276    }
277
278    /// An empty graph has no heads.
279    #[test]
280    fn empty_graph_has_no_heads() {
281        let g = MigrationGraph::new();
282        assert!(g.heads().is_empty());
283    }
284
285    /// A single migration with no dependencies is the sole head.
286    #[test]
287    fn single_migration_is_head() {
288        let mut g = MigrationGraph::new();
289        g.add(migration("0001_initial", &[])).unwrap();
290        assert_eq!(g.heads(), vec!["0001_initial"]);
291    }
292
293    /// In a linear chain, only the last migration is the head.
294    #[test]
295    fn linear_chain_has_one_head() {
296        let g = linear_graph();
297        assert_eq!(g.heads(), vec!["0003_add_posts"]);
298    }
299
300    /// Branching graph — two migrations from the same root — produces two heads.
301    #[test]
302    fn branching_graph_has_two_heads() {
303        let mut g = MigrationGraph::new();
304        g.add(migration("0001_initial", &[])).unwrap();
305        g.add(migration("0002_branch_a", &["0001_initial"]))
306            .unwrap();
307        g.add(migration("0003_branch_b", &["0001_initial"]))
308            .unwrap();
309        let mut heads = g.heads();
310        heads.sort();
311        assert_eq!(heads, vec!["0002_branch_a", "0003_branch_b"]);
312    }
313
314    /// detect_conflict returns Ok for a linear (single-head) graph.
315    #[test]
316    fn detect_conflict_ok_for_linear_graph() {
317        assert!(linear_graph().detect_conflict().is_ok());
318    }
319
320    /// detect_conflict returns Conflict when multiple heads exist.
321    #[test]
322    fn detect_conflict_err_for_branched_graph() {
323        let mut g = MigrationGraph::new();
324        g.add(migration("0001_initial", &[])).unwrap();
325        g.add(migration("0002_branch_a", &["0001_initial"]))
326            .unwrap();
327        g.add(migration("0003_branch_b", &["0001_initial"]))
328            .unwrap();
329        assert!(matches!(g.detect_conflict(), Err(GraphError::Conflict)));
330    }
331
332    /// validate_acyclic passes for a valid DAG.
333    #[test]
334    fn validate_acyclic_passes_for_dag() {
335        assert!(linear_graph().validate_acyclic().is_ok());
336    }
337
338    /// validate_acyclic returns CycleDetected when a cycle exists.
339    #[test]
340    fn validate_acyclic_detects_cycle() {
341        let mut g = MigrationGraph::new();
342        // A depends on B, B depends on A
343        g.add(migration("A", &["B"])).unwrap();
344        g.add(migration("B", &["A"])).unwrap();
345        assert!(matches!(
346            g.validate_acyclic(),
347            Err(GraphError::CycleDetected)
348        ));
349    }
350
351    /// validate_acyclic detects a longer cycle (A → B → C → A).
352    #[test]
353    fn validate_acyclic_detects_longer_cycle() {
354        let mut g = MigrationGraph::new();
355        g.add(migration("A", &["C"])).unwrap();
356        g.add(migration("B", &["A"])).unwrap();
357        g.add(migration("C", &["B"])).unwrap();
358        assert!(matches!(
359            g.validate_acyclic(),
360            Err(GraphError::CycleDetected)
361        ));
362    }
363
364    /// topological_order on a linear chain returns migrations in dependency order.
365    #[test]
366    fn topological_order_linear_chain() {
367        let g = linear_graph();
368        let order = g.topological_order().unwrap();
369        assert_eq!(
370            order,
371            vec!["0001_initial", "0002_add_users", "0003_add_posts"]
372        );
373    }
374
375    /// topological_order is deterministic: dependencies always precede dependents.
376    #[test]
377    fn topological_order_respects_dependencies() {
378        let mut g = MigrationGraph::new();
379        g.add(migration("0003_c", &["0002_b"])).unwrap();
380        g.add(migration("0001_a", &[])).unwrap();
381        g.add(migration("0002_b", &["0001_a"])).unwrap();
382        let order = g.topological_order().unwrap();
383        let pos = |id: &str| order.iter().position(|&s| s == id).unwrap();
384        assert!(pos("0001_a") < pos("0002_b"));
385        assert!(pos("0002_b") < pos("0003_c"));
386    }
387
388    /// topological_order fails on a cyclic graph.
389    #[test]
390    fn topological_order_fails_on_cycle() {
391        let mut g = MigrationGraph::new();
392        g.add(migration("A", &["B"])).unwrap();
393        g.add(migration("B", &["A"])).unwrap();
394        assert!(matches!(
395            g.topological_order(),
396            Err(GraphError::CycleDetected)
397        ));
398    }
399
400    /// next_number returns 1 for an empty graph.
401    #[test]
402    fn next_number_empty_graph() {
403        assert_eq!(MigrationGraph::new().next_number(), 1);
404    }
405
406    /// next_number returns max + 1 for an existing graph.
407    #[test]
408    fn next_number_increments_from_max() {
409        assert_eq!(linear_graph().next_number(), 4);
410    }
411
412    /// next_number handles gaps in numbering correctly.
413    #[test]
414    fn next_number_handles_gaps() {
415        let mut g = MigrationGraph::new();
416        g.add(migration("0001_a", &[])).unwrap();
417        g.add(migration("0005_b", &["0001_a"])).unwrap();
418        assert_eq!(g.next_number(), 6);
419    }
420
421    /// create_merge_migration fails when there is only one head.
422    #[test]
423    fn create_merge_migration_requires_multiple_heads() {
424        let err = linear_graph()
425            .create_merge_migration("merge".to_string())
426            .unwrap_err();
427        assert!(matches!(err, GraphError::Empty));
428    }
429
430    /// create_merge_migration produces a migration with all heads as sorted dependencies.
431    #[test]
432    fn create_merge_migration_depends_on_all_heads() {
433        let mut g = MigrationGraph::new();
434        g.add(migration("0001_initial", &[])).unwrap();
435        g.add(migration("0002_branch_a", &["0001_initial"]))
436            .unwrap();
437        g.add(migration("0003_branch_b", &["0001_initial"]))
438            .unwrap();
439        let merge = g.create_merge_migration("0004_merge".to_string()).unwrap();
440        assert_eq!(merge.id, "0004_merge");
441        assert_eq!(merge.dependencies, vec!["0002_branch_a", "0003_branch_b"]);
442        assert!(merge.operations.is_empty());
443    }
444
445    /// topological_order returns UnknownDependency when a dependency does not exist in the graph.
446    #[test]
447    fn topological_order_fails_on_unknown_dependency() {
448        let mut g = MigrationGraph::new();
449        g.add(migration("0002_b", &["0001_ghost"])).unwrap();
450        let err = g.topological_order().unwrap_err();
451        assert!(matches!(err, GraphError::UnknownDependency { dep, .. } if dep == "0001_ghost"));
452    }
453
454    /// topological_order is stable regardless of the order nodes were added.
455    #[test]
456    fn topological_order_stable_regardless_of_insertion_order() {
457        let mut g1 = MigrationGraph::new();
458        g1.add(migration("0003_add_posts", &["0002_add_users"]))
459            .unwrap();
460        g1.add(migration("0001_initial", &[])).unwrap();
461        g1.add(migration("0002_add_users", &["0001_initial"]))
462            .unwrap();
463
464        let mut g2 = MigrationGraph::new();
465        g2.add(migration("0001_initial", &[])).unwrap();
466        g2.add(migration("0002_add_users", &["0001_initial"]))
467            .unwrap();
468        g2.add(migration("0003_add_posts", &["0002_add_users"]))
469            .unwrap();
470
471        assert_eq!(
472            g1.topological_order().unwrap(),
473            g2.topological_order().unwrap()
474        );
475        assert_eq!(
476            g1.topological_order().unwrap(),
477            vec!["0001_initial", "0002_add_users", "0003_add_posts"]
478        );
479    }
480
481    /// Parallel branches are always ordered alphabetically (not by HashMap iteration).
482    #[test]
483    fn topological_order_parallel_branches_alphabetical() {
484        let mut g = MigrationGraph::new();
485        g.add(migration("0001_initial", &[])).unwrap();
486        g.add(migration("0003_feature_b", &["0001_initial"]))
487            .unwrap();
488        g.add(migration("0002_feature_a", &["0001_initial"]))
489            .unwrap();
490        g.add(migration(
491            "0004_merge",
492            &["0002_feature_a", "0003_feature_b"],
493        ))
494        .unwrap();
495        let order = g.topological_order().unwrap();
496        assert_eq!(order[0], "0001_initial");
497        assert_eq!(order[3], "0004_merge");
498        let pos = |id: &str| order.iter().position(|&s| s == id).unwrap();
499        assert!(
500            pos("0002_feature_a") < pos("0003_feature_b"),
501            "0002 should come before 0003 alphabetically"
502        );
503        assert!(pos("0002_feature_a") < pos("0004_merge"));
504        assert!(pos("0003_feature_b") < pos("0004_merge"));
505    }
506
507    /// topological_order called multiple times on the same graph returns identical results.
508    #[test]
509    fn topological_order_is_stable_across_calls() {
510        let mut g = MigrationGraph::new();
511        g.add(migration("0001_initial", &[])).unwrap();
512        g.add(migration("0003_z_feature", &["0001_initial"]))
513            .unwrap();
514        g.add(migration("0002_a_feature", &["0001_initial"]))
515            .unwrap();
516        g.add(migration(
517            "0004_merge",
518            &["0002_a_feature", "0003_z_feature"],
519        ))
520        .unwrap();
521        let first = g.topological_order().unwrap();
522        let second = g.topological_order().unwrap();
523        assert_eq!(first, second);
524        let pos = |id: &str| first.iter().position(|&s| s == id).unwrap();
525        assert!(pos("0002_a_feature") < pos("0003_z_feature"));
526    }
527
528    /// create_merge_migration always produces sorted dependencies regardless of heads() order.
529    #[test]
530    fn create_merge_migration_deps_are_always_sorted() {
531        let mut g = MigrationGraph::new();
532        g.add(migration("0001_initial", &[])).unwrap();
533        g.add(migration("0002_zzz_last", &["0001_initial"]))
534            .unwrap();
535        g.add(migration("0003_aaa_first", &["0001_initial"]))
536            .unwrap();
537        let merge = g.create_merge_migration("0004_merge".to_string()).unwrap();
538        assert_eq!(merge.dependencies, vec!["0002_zzz_last", "0003_aaa_first"]);
539    }
540
541    /// validate_id rejects empty strings and strings with invalid characters.
542    #[test]
543    fn validate_id_rejects_invalid() {
544        assert!(MigrationGraph::validate_id("").is_err());
545        assert!(MigrationGraph::validate_id("has space").is_err());
546        assert!(MigrationGraph::validate_id("HasUpper").is_err());
547        assert!(MigrationGraph::validate_id("has-dash").is_err());
548        assert!(MigrationGraph::validate_id("0001_ok").is_ok());
549        assert!(MigrationGraph::validate_id("abc123").is_ok());
550    }
551
552    /// Resolves a unique migration id prefix using deterministic graph order.
553    #[test]
554    fn resolve_id_accepts_unique_prefix() {
555        let graph = linear_graph();
556
557        assert_eq!(graph.resolve_id("0002").unwrap(), "0002_add_users");
558    }
559
560    /// Prefers a full id even when another id begins with the same text.
561    #[test]
562    fn resolve_id_prefers_exact_match() {
563        let mut graph = MigrationGraph::new();
564        graph.add(migration("0001_users", &[])).unwrap();
565        graph.add(migration("0001_users_index", &[])).unwrap();
566
567        assert_eq!(graph.resolve_id("0001_users").unwrap(), "0001_users");
568    }
569
570    /// Reports all deterministic candidates when a prefix is ambiguous.
571    #[test]
572    fn resolve_id_rejects_ambiguous_prefix() {
573        let graph = linear_graph();
574
575        let error = graph.resolve_id("000").unwrap_err();
576        assert!(matches!(
577            error,
578            GraphError::AmbiguousId { prefix, matches }
579                if prefix == "000" && matches == "0001_initial, 0002_add_users, 0003_add_posts"
580        ));
581    }
582
583    /// next_number ignores namespaced ids (containing '/') and only counts primary ones.
584    #[test]
585    fn next_number_ignores_namespaced_ids() {
586        let mut g = MigrationGraph::new();
587        g.add(migration("0001_initial", &[])).unwrap();
588        g.add(migration("auth/0001_users", &[])).unwrap();
589        g.add(migration("auth/0002_sessions", &[])).unwrap();
590        // namespaced ids must not inflate the primary counter
591        assert_eq!(g.next_number(), 2);
592    }
593
594    /// next_number returns 1 when only namespaced ids are present.
595    #[test]
596    fn next_number_with_only_namespaced_ids() {
597        let mut g = MigrationGraph::new();
598        g.add(migration("auth/0005_something", &[])).unwrap();
599        assert_eq!(g.next_number(), 1);
600    }
601}
gaman_core/graphs.rs

gaman_core/
graphs.rs
