Skip to main content

gaman_core/diff/
mod.rs

1use std::collections::{BTreeSet, HashMap, HashSet};
2
3use thiserror::Error;
4
5use crate::dialects::Dialect;
6use crate::opaque::{
7    opaque_option_sources_equal, opaque_sources_equal, table_option_sources_equal,
8};
9use crate::operations::Operation;
10use crate::states::{
11    Column, Constraint, EnumDef, ExtensionDef, FunctionDef, Schema, SequenceDef, Table, TriggerDef,
12    ViewDef,
13};
14
15#[derive(Debug, Error)]
16pub enum DiffError {
17    #[error("dependency cycle detected among operations — this is a bug in the diff engine")]
18    DependencyCycle,
19    #[error(
20        "primary key changes on existing table '{0}' are not generated automatically; use an explicit SQL statement migration"
21    )]
22    PrimaryKeyMutation(String),
23    #[error(
24        "PostgreSQL partition metadata on existing table '{0}' cannot be changed automatically; use an explicit raw SQL migration"
25    )]
26    PostgresPartitionMutation(String),
27}
28
29// Walk the schema maps directly. The BTreeMap keys are the canonical identity
30// for each entity, so a plain keyed comparison is enough here.
31
32pub fn generate_diff(current: &Schema, previous: &Schema) -> Vec<Operation> {
33    let mut ops: Vec<Operation> = Vec::new();
34
35    diff_map_with_eq(
36        &current.extensions,
37        &previous.extensions,
38        &mut ops,
39        extension_equal,
40        diff_extension,
41    );
42    diff_map_with_eq(
43        &current.sequences,
44        &previous.sequences,
45        &mut ops,
46        sequence_equal,
47        diff_sequence,
48    );
49    diff_map(&current.enums, &previous.enums, &mut ops, diff_enum);
50    diff_map_with_eq(
51        &current.functions,
52        &previous.functions,
53        &mut ops,
54        function_equal,
55        diff_function,
56    );
57    diff_map_with_eq(
58        &current.views,
59        &previous.views,
60        &mut ops,
61        view_equal,
62        diff_view,
63    );
64    diff_map(
65        &current.tables,
66        &previous.tables,
67        &mut ops,
68        |curr, prev, ops| diff_table(curr, prev, ops, None),
69    );
70
71    ops
72}
73
74fn diff_map<T: PartialEq>(
75    current: &std::collections::BTreeMap<String, T>,
76    previous: &std::collections::BTreeMap<String, T>,
77    ops: &mut Vec<Operation>,
78    handler: fn(Option<&T>, Option<&T>, &mut Vec<Operation>),
79) {
80    for (key, curr_val) in current {
81        match previous.get(key) {
82            None => handler(Some(curr_val), None, ops),
83            Some(prev_val) if prev_val != curr_val => handler(Some(curr_val), Some(prev_val), ops),
84            _ => {}
85        }
86    }
87    for (key, prev_val) in previous {
88        if !current.contains_key(key) {
89            handler(None, Some(prev_val), ops);
90        }
91    }
92}
93
94fn diff_map_with_eq<T>(
95    current: &std::collections::BTreeMap<String, T>,
96    previous: &std::collections::BTreeMap<String, T>,
97    ops: &mut Vec<Operation>,
98    equal: fn(&T, &T) -> bool,
99    handler: fn(Option<&T>, Option<&T>, &mut Vec<Operation>),
100) {
101    for (key, curr_val) in current {
102        match previous.get(key) {
103            None => handler(Some(curr_val), None, ops),
104            Some(prev_val) if !equal(curr_val, prev_val) => {
105                handler(Some(curr_val), Some(prev_val), ops)
106            }
107            _ => {}
108        }
109    }
110    for (key, prev_val) in previous {
111        if !current.contains_key(key) {
112            handler(None, Some(prev_val), ops);
113        }
114    }
115}
116
117fn diff_extension(
118    curr: Option<&ExtensionDef>,
119    prev: Option<&ExtensionDef>,
120    ops: &mut Vec<Operation>,
121) {
122    match (curr, prev) {
123        (Some(c), None) => ops.push(Operation::CreateExtension {
124            extension: c.clone(),
125        }),
126        (None, Some(p)) => ops.push(Operation::DropExtension {
127            extension: p.clone(),
128        }),
129        (Some(c), Some(p)) => {
130            ops.push(Operation::DropExtension {
131                extension: p.clone(),
132            });
133            ops.push(Operation::CreateExtension {
134                extension: c.clone(),
135            });
136        }
137        _ => {}
138    }
139}
140
141fn sequence_equal(current: &SequenceDef, previous: &SequenceDef) -> bool {
142    current.name == previous.name
143        && current.schema == previous.schema
144        && opaque_option_sources_equal(&current.sql, &previous.sql)
145}
146
147fn diff_sequence(
148    current: Option<&SequenceDef>,
149    previous: Option<&SequenceDef>,
150    operations: &mut Vec<Operation>,
151) {
152    match (current, previous) {
153        (Some(sequence), None) => operations.push(Operation::CreateSequence {
154            sequence: sequence.clone(),
155        }),
156        (None, Some(sequence)) => operations.push(Operation::DropSequence {
157            sequence: sequence.clone(),
158        }),
159        (Some(current), Some(previous)) => {
160            operations.push(Operation::DropSequence {
161                sequence: previous.clone(),
162            });
163            operations.push(Operation::CreateSequence {
164                sequence: current.clone(),
165            });
166        }
167        (None, None) => {}
168    }
169}
170
171fn diff_enum(curr: Option<&EnumDef>, prev: Option<&EnumDef>, ops: &mut Vec<Operation>) {
172    match (curr, prev) {
173        (Some(c), None) => ops.push(Operation::CreateEnum {
174            enum_def: c.clone(),
175        }),
176        (None, Some(p)) => ops.push(Operation::DropEnum {
177            enum_def: p.clone(),
178        }),
179        (Some(c), Some(p)) => {
180            let old_set: HashSet<&str> = p.values.iter().map(|v| v.as_str()).collect();
181            let new_set: HashSet<&str> = c.values.iter().map(|v| v.as_str()).collect();
182            if old_set.is_subset(&new_set) && values_are_subsequence(&p.values, &c.values) {
183                ops.push(Operation::AlterEnum {
184                    old: p.clone(),
185                    new: c.clone(),
186                });
187            } else {
188                ops.push(Operation::DropEnum {
189                    enum_def: p.clone(),
190                });
191                ops.push(Operation::CreateEnum {
192                    enum_def: c.clone(),
193                });
194            }
195        }
196        _ => {}
197    }
198}
199
200fn values_are_subsequence(old: &[String], new: &[String]) -> bool {
201    let mut new_iter = new.iter();
202    old.iter()
203        .all(|old_value| new_iter.by_ref().any(|new_value| new_value == old_value))
204}
205
206fn diff_function(curr: Option<&FunctionDef>, prev: Option<&FunctionDef>, ops: &mut Vec<Operation>) {
207    match (curr, prev) {
208        (Some(c), None) => ops.push(Operation::CreateFunction {
209            function: c.clone(),
210        }),
211        (None, Some(p)) => ops.push(Operation::DropFunction {
212            function: p.clone(),
213        }),
214        (Some(c), Some(p)) => {
215            ops.push(Operation::AlterFunction {
216                old: p.clone(),
217                new: c.clone(),
218            });
219        }
220        _ => {}
221    }
222}
223
224fn diff_view(curr: Option<&ViewDef>, prev: Option<&ViewDef>, ops: &mut Vec<Operation>) {
225    match (curr, prev) {
226        (Some(c), None) => ops.push(Operation::CreateView { view: c.clone() }),
227        (None, Some(p)) => ops.push(Operation::DropView { view: p.clone() }),
228        (Some(c), Some(p)) => {
229            ops.push(Operation::ReplaceView {
230                old: p.clone(),
231                new: c.clone(),
232            });
233        }
234        _ => {}
235    }
236}
237
238fn diff_table(
239    curr: Option<&Table>,
240    prev: Option<&Table>,
241    ops: &mut Vec<Operation>,
242    dialect: Option<&Dialect>,
243) {
244    match (curr, prev) {
245        (Some(c), None) => ops.push(Operation::CreateTable { table: c.clone() }),
246        (None, Some(p)) => ops.push(Operation::DropTable { table: p.clone() }),
247        (Some(c), Some(p)) => diff_table_children(p, c, ops, dialect),
248        _ => {}
249    }
250}
251
252fn diff_table_children(
253    prev: &Table,
254    curr: &Table,
255    ops: &mut Vec<Operation>,
256    dialect: Option<&Dialect>,
257) {
258    let table_name = curr.qualified_name();
259    if !table_option_sources_equal(
260        &prev.options.header_raw,
261        &prev.options.tail_raw,
262        &curr.options.header_raw,
263        &curr.options.tail_raw,
264    ) {
265        ops.push(Operation::AcknowledgeTableOptions {
266            table_name: table_name.clone(),
267            old: prev.options.clone(),
268            new: curr.options.clone(),
269        });
270    }
271
272    for change in diff_by_name(
273        &prev.columns,
274        &curr.columns,
275        |c| c.name.as_str(),
276        |left, right| column_equal(left, right, dialect),
277    ) {
278        match change {
279            SubChange::Removed(col) => ops.push(Operation::DropColumn {
280                table_name: table_name.clone(),
281                column: col.clone(),
282                cascade: false,
283            }),
284            SubChange::Added(col) => ops.push(Operation::AddColumn {
285                table_name: table_name.clone(),
286                column: col.clone(),
287            }),
288            SubChange::Modified(old, new) => ops.push(Operation::AlterColumn {
289                table_name: table_name.clone(),
290                old: old.clone(),
291                new: new.clone(),
292                cast_expr: None,
293            }),
294        }
295    }
296
297    for change in diff_by_name(
298        &prev.foreign_keys,
299        &curr.foreign_keys,
300        |fk| fk.name.as_str(),
301        PartialEq::eq,
302    ) {
303        match change {
304            SubChange::Removed(fk) => ops.push(Operation::DropForeignKey {
305                table_name: table_name.clone(),
306                foreign_key: fk.clone(),
307                cascade: false,
308            }),
309            SubChange::Added(fk) => ops.push(Operation::AddForeignKey {
310                table_name: table_name.clone(),
311                foreign_key: fk.clone(),
312            }),
313            SubChange::Modified(old, new) => {
314                ops.push(Operation::DropForeignKey {
315                    table_name: table_name.clone(),
316                    foreign_key: old.clone(),
317                    cascade: false,
318                });
319                ops.push(Operation::AddForeignKey {
320                    table_name: table_name.clone(),
321                    foreign_key: new.clone(),
322                });
323            }
324        }
325    }
326
327    for change in diff_by_name(
328        &prev.indexes,
329        &curr.indexes,
330        |i| i.name.as_str(),
331        index_equal,
332    ) {
333        match change {
334            SubChange::Removed(idx) => ops.push(Operation::DropIndex {
335                table_name: table_name.clone(),
336                index: idx.clone(),
337                concurrent: false,
338            }),
339            SubChange::Added(idx) => ops.push(Operation::AddIndex {
340                table_name: table_name.clone(),
341                index: idx.clone(),
342                concurrent: false,
343            }),
344            SubChange::Modified(old, new) => {
345                ops.push(Operation::DropIndex {
346                    table_name: table_name.clone(),
347                    index: old.clone(),
348                    concurrent: false,
349                });
350                ops.push(Operation::AddIndex {
351                    table_name: table_name.clone(),
352                    index: new.clone(),
353                    concurrent: false,
354                });
355            }
356        }
357    }
358
359    for change in diff_by_name(
360        &prev.constraints,
361        &curr.constraints,
362        |c| c.name(),
363        constraint_equal,
364    ) {
365        match change {
366            SubChange::Removed(con) => ops.push(Operation::DropConstraint {
367                table_name: table_name.clone(),
368                constraint: con.clone(),
369            }),
370            SubChange::Added(con) => ops.push(Operation::AddConstraint {
371                table_name: table_name.clone(),
372                constraint: con.clone(),
373            }),
374            SubChange::Modified(old, new) => {
375                ops.push(Operation::DropConstraint {
376                    table_name: table_name.clone(),
377                    constraint: old.clone(),
378                });
379                ops.push(Operation::AddConstraint {
380                    table_name: table_name.clone(),
381                    constraint: new.clone(),
382                });
383            }
384        }
385    }
386
387    for change in diff_by_name(
388        &prev.triggers,
389        &curr.triggers,
390        |t| t.name.as_deref().unwrap_or(""),
391        trigger_equal,
392    ) {
393        match change {
394            SubChange::Removed(trg) => ops.push(Operation::DropTrigger {
395                table_name: table_name.clone(),
396                trigger: trg.clone(),
397            }),
398            SubChange::Added(trg) => ops.push(Operation::CreateTrigger {
399                table_name: table_name.clone(),
400                trigger: trg.clone(),
401            }),
402            SubChange::Modified(old, new) => ops.push(Operation::AlterTrigger {
403                table_name: table_name.clone(),
404                old: old.clone(),
405                new: new.clone(),
406            }),
407        }
408    }
409}
410
411fn column_equal(left: &Column, right: &Column, dialect: Option<&Dialect>) -> bool {
412    let type_equal = dialect.map_or_else(
413        || left.col_type == right.col_type,
414        |dialect| {
415            dialect.type_comparison_key(&left.col_type)
416                == dialect.type_comparison_key(&right.col_type)
417        },
418    );
419    type_equal
420        && left.name == right.name
421        && left.nullable == right.nullable
422        && dialect.map_or_else(
423            || left.default == right.default,
424            |dialect| match (&left.default, &right.default) {
425                (Some(left), Some(right)) => dialect.default_expressions_equal(left, right),
426                (None, None) => true,
427                _ => false,
428            },
429        )
430        && left.primary_key == right.primary_key
431        && left.references == right.references
432        && left.check == right.check
433        && left.generated == right.generated
434}
435
436fn function_equal(left: &FunctionDef, right: &FunctionDef) -> bool {
437    if left.is_opaque() || right.is_opaque() {
438        return left.qualified_name() == right.qualified_name()
439            && opaque_option_sources_equal(&left.opaque.raw, &right.opaque.raw);
440    }
441    left.name == right.name
442        && left.schema == right.schema
443        && left.parameters_sql() == right.parameters_sql()
444        && left.depends_on == right.depends_on
445        && left.returns == right.returns
446        && left.language == right.language
447        && left.volatility == right.volatility
448        && left.security_definer == right.security_definer
449        && opaque_sources_equal(&left.body, &right.body)
450}
451
452fn view_equal(left: &ViewDef, right: &ViewDef) -> bool {
453    if left.is_opaque() || right.is_opaque() {
454        return left.qualified_name() == right.qualified_name()
455            && opaque_option_sources_equal(&left.opaque.raw, &right.opaque.raw);
456    }
457    left.name == right.name
458        && left.schema == right.schema
459        && opaque_sources_equal(&left.definition, &right.definition)
460}
461
462fn trigger_equal(left: &TriggerDef, right: &TriggerDef) -> bool {
463    if left.is_opaque() || right.is_opaque() {
464        return left.name == right.name
465            && opaque_option_sources_equal(&left.opaque.raw, &right.opaque.raw);
466    }
467    left.name == right.name
468        && left.timing == right.timing
469        && left.events == right.events
470        && left.scope == right.scope
471        && left.function_name == right.function_name
472        && opaque_option_sources_equal(&left.when, &right.when)
473        && opaque_option_sources_equal(&left.query, &right.query)
474        && left.language == right.language
475}
476
477fn constraint_equal(left: &Constraint, right: &Constraint) -> bool {
478    if left.is_opaque() || right.is_opaque() {
479        let left_raw = left.raw_sql().map(ToOwned::to_owned);
480        let right_raw = right.raw_sql().map(ToOwned::to_owned);
481        return left.name() == right.name() && opaque_option_sources_equal(&left_raw, &right_raw);
482    }
483    left == right
484}
485
486fn extension_equal(left: &ExtensionDef, right: &ExtensionDef) -> bool {
487    if left.is_opaque() || right.is_opaque() {
488        return left.qualified_name() == right.qualified_name()
489            && opaque_option_sources_equal(&left.opaque.raw, &right.opaque.raw);
490    }
491    left == right
492}
493
494fn index_equal(left: &crate::states::Index, right: &crate::states::Index) -> bool {
495    if left.is_opaque() || right.is_opaque() {
496        return left.name == right.name
497            && opaque_option_sources_equal(&left.opaque.raw, &right.opaque.raw);
498    }
499    left == right
500}
501
502enum SubChange<'a, T> {
503    Added(&'a T),
504    Removed(&'a T),
505    Modified(&'a T, &'a T),
506}
507
508fn diff_by_name<'a, T>(
509    prev: &'a [T],
510    curr: &'a [T],
511    name_fn: impl Fn(&T) -> &str,
512    equal: impl Fn(&T, &T) -> bool,
513) -> Vec<SubChange<'a, T>> {
514    let prev_map: HashMap<&str, &T> = prev.iter().map(|v| (name_fn(v), v)).collect();
515    let curr_map: HashMap<&str, &T> = curr.iter().map(|v| (name_fn(v), v)).collect();
516    let mut changes = Vec::new();
517
518    for (&name, &prev_val) in &prev_map {
519        if !curr_map.contains_key(name) {
520            changes.push(SubChange::Removed(prev_val));
521        }
522    }
523    for (&name, &curr_val) in &curr_map {
524        match prev_map.get(name) {
525            None => changes.push(SubChange::Added(curr_val)),
526            Some(&prev_val) if !equal(prev_val, curr_val) => {
527                changes.push(SubChange::Modified(prev_val, curr_val))
528            }
529            _ => {}
530        }
531    }
532    changes
533}
534
535// When a function is dropped but a surviving table still carries a trigger
536// referencing it, that trigger is not detected by the detection pass (the
537// trigger node is identical in both states). We inject the DropTrigger here.
538fn inject_orphan_triggers(ops: Vec<Operation>, previous: &Schema) -> Vec<Operation> {
539    let dropped_fns: HashSet<String> = ops
540        .iter()
541        .filter_map(|op| match op {
542            Operation::DropFunction { function } => Some(function.qualified_name()),
543            _ => None,
544        })
545        .collect();
546
547    if dropped_fns.is_empty() {
548        return ops;
549    }
550
551    let dropped_tables: HashSet<String> = ops
552        .iter()
553        .filter_map(|op| match op {
554            Operation::DropTable { table } => Some(table.qualified_name()),
555            _ => None,
556        })
557        .collect();
558
559    let existing_drop_keys: HashSet<String> = ops
560        .iter()
561        .filter_map(|op| match op {
562            Operation::DropTrigger {
563                table_name,
564                trigger,
565            } => trigger
566                .name
567                .as_deref()
568                .map(|n| format!("{}:{}", table_name, n)),
569            _ => None,
570        })
571        .collect();
572
573    let mut injected: Vec<Operation> = Vec::new();
574    for (table_name, table) in &previous.tables {
575        if dropped_tables.contains(table_name) {
576            continue;
577        }
578        for trg in &table.triggers {
579            let references_dropped = trg
580                .function_name
581                .as_deref()
582                .is_some_and(|f| dropped_fns.contains(f));
583            if !references_dropped {
584                continue;
585            }
586            let key = trg
587                .name
588                .as_deref()
589                .map(|n| format!("{}:{}", table_name, n))
590                .unwrap_or_default();
591            if !existing_drop_keys.contains(&key) {
592                injected.push(Operation::DropTrigger {
593                    table_name: table_name.clone(),
594                    trigger: trg.clone(),
595                });
596            }
597        }
598    }
599
600    let mut result = ops;
601    result.extend(injected);
602    result
603}
604
605// Incompatible enum changes (drop+recreate) require surviving columns that use
606// the enum to be temporarily cast to text and back. Without this, DropEnum fails
607// because the type is still in use.
608// Limitation: enum references inside SQL (defaults, check constraints, function
609// bodies, view definitions) cannot be tracked without parsing SQL.
610fn inject_enum_column_casts(ops: Vec<Operation>, previous: &Schema) -> Vec<Operation> {
611    let dropped_enums: HashSet<&str> = ops
612        .iter()
613        .filter_map(|op| match op {
614            Operation::DropEnum { enum_def } => Some(enum_def.name.as_str()),
615            _ => None,
616        })
617        .collect();
618    let created_enums: HashSet<&str> = ops
619        .iter()
620        .filter_map(|op| match op {
621            Operation::CreateEnum { enum_def } => Some(enum_def.name.as_str()),
622            _ => None,
623        })
624        .collect();
625
626    let recreated: HashSet<&str> = dropped_enums
627        .intersection(&created_enums)
628        .copied()
629        .collect();
630    if recreated.is_empty() {
631        return ops;
632    }
633
634    let dropped_tables: HashSet<String> = ops
635        .iter()
636        .filter_map(|op| match op {
637            Operation::DropTable { table } => Some(table.qualified_name()),
638            _ => None,
639        })
640        .collect();
641
642    let touched_columns: HashSet<(&str, &str)> = ops
643        .iter()
644        .filter_map(|op| match op {
645            Operation::DropColumn {
646                table_name, column, ..
647            } => Some((table_name.as_str(), column.name.as_str())),
648            Operation::AlterColumn {
649                table_name, old, ..
650            } => Some((table_name.as_str(), old.name.as_str())),
651            _ => None,
652        })
653        .collect();
654
655    let mut casts: Vec<Operation> = Vec::new();
656
657    for (table_name, table) in &previous.tables {
658        if dropped_tables.contains(table_name) {
659            continue;
660        }
661        for col in &table.columns {
662            if !recreated.contains(col.col_type.as_str()) {
663                continue;
664            }
665            if touched_columns.contains(&(table_name.as_str(), col.name.as_str())) {
666                continue;
667            }
668            let text_col = Column {
669                col_type: "text".to_string(),
670                ..col.clone()
671            };
672            casts.push(Operation::AlterColumn {
673                table_name: table_name.clone(),
674                old: col.clone(),
675                new: text_col.clone(),
676                cast_expr: Some(format!("{}::text", col.name)),
677            });
678            casts.push(Operation::AlterColumn {
679                table_name: table_name.clone(),
680                old: text_col,
681                new: col.clone(),
682                cast_expr: Some(format!("{}::{}", col.name, col.col_type)),
683            });
684        }
685    }
686
687    if casts.is_empty() {
688        return ops;
689    }
690
691    let mut result = Vec::with_capacity(ops.len() + casts.len());
692    result.extend(ops);
693    result.extend(casts);
694    result
695}
696
697// Splits compound CreateTable/DropTable into atomic operations so
698// the topological sort can order sub-entities independently.
699// CreateTable → CreateTable(columns only) + AddFK* + AddIndex* + AddConstraint* + CreateTrigger*
700// DropTable → DropTrigger* + DropConstraint* + DropIndex* + DropFK* + DropTable(columns only)
701fn decompose(ops: Vec<Operation>) -> Vec<Operation> {
702    let mut result = Vec::with_capacity(ops.len() * 2);
703    for op in ops {
704        match op {
705            Operation::CreateTable { mut table } => {
706                let fks = std::mem::take(&mut table.foreign_keys);
707                let indexes = std::mem::take(&mut table.indexes);
708                let constraints = std::mem::take(&mut table.constraints);
709                let triggers = std::mem::take(&mut table.triggers);
710                let tname = table.name.clone();
711                result.push(Operation::CreateTable { table });
712                for fk in fks {
713                    result.push(Operation::AddForeignKey {
714                        table_name: tname.clone(),
715                        foreign_key: fk,
716                    });
717                }
718                for idx in indexes {
719                    result.push(Operation::AddIndex {
720                        table_name: tname.clone(),
721                        index: idx,
722                        concurrent: false,
723                    });
724                }
725                for con in constraints {
726                    result.push(Operation::AddConstraint {
727                        table_name: tname.clone(),
728                        constraint: con,
729                    });
730                }
731                for trg in triggers {
732                    result.push(Operation::CreateTrigger {
733                        table_name: tname.clone(),
734                        trigger: trg,
735                    });
736                }
737            }
738            Operation::DropTable { mut table } => {
739                let fks = std::mem::take(&mut table.foreign_keys);
740                let indexes = std::mem::take(&mut table.indexes);
741                let constraints = std::mem::take(&mut table.constraints);
742                let triggers = std::mem::take(&mut table.triggers);
743                let tname = table.name.clone();
744                for trg in triggers {
745                    result.push(Operation::DropTrigger {
746                        table_name: tname.clone(),
747                        trigger: trg,
748                    });
749                }
750                for con in constraints {
751                    result.push(Operation::DropConstraint {
752                        table_name: tname.clone(),
753                        constraint: con,
754                    });
755                }
756                for idx in indexes {
757                    result.push(Operation::DropIndex {
758                        table_name: tname.clone(),
759                        index: idx,
760                        concurrent: false,
761                    });
762                }
763                for fk in fks {
764                    result.push(Operation::DropForeignKey {
765                        table_name: tname.clone(),
766                        foreign_key: fk,
767                        cascade: false,
768                    });
769                }
770                result.push(Operation::DropTable { table });
771            }
772            other => result.push(other),
773        }
774    }
775    result
776}
777
778// After sorting, folds decomposed sub-entity ops back into their parent
779// CreateTable when the dialect supports inline definitions (e.g. Postgres
780// can inline FKs, indexes, constraints). This produces cleaner migrations.
781// FKs are only inlined when the reference is self-referential or points to a
782// table that already existed before this migration — cross-table FKs within
783// the same migration stay as standalone ops (already sorted after all creates).
784fn fk_can_be_inlined(
785    to_table: &str,
786    owner_table: &str,
787    tables_being_created: &HashSet<String>,
788) -> bool {
789    to_table == owner_table || !tables_being_created.contains(to_table)
790}
791
792fn merge_operations(ops: Vec<Operation>, dialect: &Dialect) -> Vec<Operation> {
793    let tables_being_created: HashSet<String> = ops
794        .iter()
795        .filter_map(|op| match op {
796            Operation::CreateTable { table } => Some(table.qualified_name()),
797            _ => None,
798        })
799        .collect();
800
801    let mut result: Vec<Operation> = Vec::with_capacity(ops.len());
802    let mut created_tables: HashMap<String, usize> = HashMap::new();
803    for op in ops {
804        let merged = match &op {
805            Operation::AddForeignKey {
806                table_name,
807                foreign_key,
808            } if created_tables.contains_key(table_name)
809                && dialect.should_merge(table_name, &op)
810                && fk_can_be_inlined(&foreign_key.to_table, table_name, &tables_being_created) =>
811            {
812                let idx = created_tables[table_name];
813                if let Operation::CreateTable { ref mut table } = result[idx] {
814                    table.foreign_keys.push(foreign_key.clone());
815                }
816                true
817            }
818            Operation::AddIndex {
819                table_name, index, ..
820            } if created_tables.contains_key(table_name)
821                && dialect.should_merge(table_name, &op) =>
822            {
823                let idx = created_tables[table_name];
824                if let Operation::CreateTable { ref mut table } = result[idx] {
825                    table.indexes.push(index.clone());
826                }
827                true
828            }
829            Operation::AddConstraint {
830                table_name,
831                constraint,
832            } if created_tables.contains_key(table_name)
833                && dialect.should_merge(table_name, &op) =>
834            {
835                let idx = created_tables[table_name];
836                if let Operation::CreateTable { ref mut table } = result[idx] {
837                    table.constraints.push(constraint.clone());
838                }
839                true
840            }
841            Operation::CreateTrigger {
842                table_name,
843                trigger,
844            } if created_tables.contains_key(table_name)
845                && dialect.should_merge(table_name, &op) =>
846            {
847                let idx = created_tables[table_name];
848                if let Operation::CreateTable { ref mut table } = result[idx] {
849                    table.triggers.push(trigger.clone());
850                }
851                true
852            }
853            _ => false,
854        };
855        if !merged {
856            if let Operation::CreateTable { ref table } = op {
857                created_tables.insert(table.qualified_name(), result.len());
858            }
859            result.push(op);
860        }
861    }
862    result
863}
864
865// Topologically sort operations with Kahn's algorithm. When multiple nodes are
866// otherwise equal, break ties deterministically so output stays reproducible.
867
868pub fn sort_operations(ops: Vec<Operation>) -> Result<Vec<Operation>, DiffError> {
869    let n = ops.len();
870    if n == 0 {
871        return Ok(ops);
872    }
873
874    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
875    let mut in_deg: Vec<usize> = vec![0; n];
876
877    build_dependency_edges(&ops, &mut adj, &mut in_deg);
878
879    // Kahn's BFS with deterministic tie-breaking via BTreeSet.
880    let mut queue: BTreeSet<(u8, u8, String, usize)> = BTreeSet::new();
881    for i in 0..n {
882        if in_deg[i] == 0 {
883            let (tp, sp) = tiebreak_priority(&ops[i]);
884            queue.insert((tp, sp, ops[i].entity_name().to_string(), i));
885        }
886    }
887
888    let mut sorted_indices: Vec<usize> = Vec::with_capacity(n);
889    while let Some(entry) = queue.iter().next().cloned() {
890        queue.remove(&entry);
891        let idx = entry.3;
892        sorted_indices.push(idx);
893        for &dep in &adj[idx] {
894            in_deg[dep] -= 1;
895            if in_deg[dep] == 0 {
896                let (tp, sp) = tiebreak_priority(&ops[dep]);
897                queue.insert((tp, sp, ops[dep].entity_name().to_string(), dep));
898            }
899        }
900    }
901
902    if sorted_indices.len() != n {
903        return Err(DiffError::DependencyCycle);
904    }
905
906    let mut slots: Vec<Option<Operation>> = ops.into_iter().map(Some).collect();
907    let result = sorted_indices
908        .into_iter()
909        .map(|i| slots[i].take().expect("index used twice"))
910        .collect();
911    Ok(result)
912}
913
914fn tiebreak_priority(op: &Operation) -> (u8, u8) {
915    match op {
916        Operation::CreateExtension { .. } => (0, 0),
917        Operation::CreateSequence { .. } => (0, 1),
918        Operation::CreateEnum { .. }
919        | Operation::RenameEnumValue { .. }
920        | Operation::AlterEnum { .. } => (1, 0),
921        Operation::DropView { .. } => (2, 0),
922        Operation::ReplaceView { .. } => (11, 0),
923        Operation::DropTable { .. } => (4, 0),
924        Operation::CreateFunction { .. } | Operation::AlterFunction { .. } => (5, 0),
925        Operation::CreateTable { .. } => (6, 0),
926        Operation::DeleteRow { .. } => (7, 0),
927        Operation::DropTrigger { .. } => (8, 0),
928        Operation::DropConstraint { .. } => (8, 1),
929        Operation::DropIndex { .. } => (8, 2),
930        Operation::DropForeignKey { .. } => (8, 3),
931        Operation::DropColumn { .. } => (8, 4),
932        Operation::AlterColumn { .. } => (8, 5),
933        Operation::AddColumn { .. } => (8, 6),
934        Operation::AddForeignKey { .. } => (8, 7),
935        Operation::AddIndex { .. } => (8, 8),
936        Operation::AddConstraint { .. } => (8, 9),
937        Operation::CreateTrigger { .. } | Operation::AlterTrigger { .. } => (8, 10),
938        Operation::DropFunction { .. } => (10, 0),
939        Operation::CreateView { .. } => (11, 0),
940        Operation::DropEnum { .. } => (12, 0),
941        Operation::DropExtension { .. } => (13, 0),
942        Operation::DropSequence { .. } => (13, 0),
943        Operation::Statement { .. }
944        | Operation::AcknowledgeTableOptions { .. }
945        | Operation::RenameTable { .. }
946        | Operation::RenameColumn { .. } => (8, 5),
947        Operation::InsertRow { .. } => (9, 0),
948        Operation::UpdateRow { .. } => (9, 1),
949    }
950}
951
952use crate::states::types::{Dep, EntityKind};
953
954fn build_dependency_edges(ops: &[Operation], adj: &mut [Vec<usize>], in_deg: &mut [usize]) {
955    let mut seen: HashSet<(usize, usize)> = HashSet::new();
956
957    let entity_names: Vec<std::borrow::Cow<str>> = ops.iter().map(|op| op.entity_name()).collect();
958    let mut create_idx: HashMap<(EntityKind, &str), Vec<usize>> = HashMap::new();
959    let mut drop_idx: HashMap<(EntityKind, &str), Vec<usize>> = HashMap::new();
960
961    for (i, op) in ops.iter().enumerate() {
962        if let Some(kind) = op.entity_kind() {
963            let name: &str = &entity_names[i];
964            if op.is_drop() {
965                drop_idx.entry((kind, name)).or_default().push(i);
966            } else {
967                create_idx.entry((kind, name)).or_default().push(i);
968            }
969        }
970    }
971
972    let mut add_edge = |from: usize, to: usize| {
973        if from != to && seen.insert((from, to)) {
974            adj[from].push(to);
975            in_deg[to] += 1;
976        }
977    };
978
979    for (identity, drops) in &drop_idx {
980        if identity.0 != EntityKind::Sequence {
981            continue;
982        }
983        let Some(creates) = create_idx.get(identity) else {
984            continue;
985        };
986        for drop_index in drops {
987            for create_index in creates {
988                add_edge(*drop_index, *create_index);
989            }
990        }
991    }
992
993    let resolve_create = |dep: &Dep| -> Vec<usize> {
994        match &dep.name {
995            Some(name) => resolve_named_dependency(&create_idx, dep.kind, name),
996            None => create_idx
997                .iter()
998                .filter(|((k, _), _)| *k == dep.kind)
999                .flat_map(|(_, v)| v.iter().copied())
1000                .collect(),
1001        }
1002    };
1003
1004    let resolve_drop = |dep: &Dep| -> Vec<usize> {
1005        match &dep.name {
1006            Some(name) => resolve_named_dependency(&drop_idx, dep.kind, name),
1007            None => drop_idx
1008                .iter()
1009                .filter(|((k, _), _)| *k == dep.kind)
1010                .flat_map(|(_, v)| v.iter().copied())
1011                .collect(),
1012        }
1013    };
1014
1015    for (i, op) in ops.iter().enumerate() {
1016        if !op.is_drop() {
1017            for dep in op.forward_deps() {
1018                for j in resolve_create(&dep) {
1019                    add_edge(j, i);
1020                }
1021            }
1022        }
1023        if !op.is_create() {
1024            for dep in op.backward_deps() {
1025                for k in resolve_drop(&dep) {
1026                    add_edge(i, k);
1027                }
1028            }
1029        }
1030    }
1031
1032    for (child_index, operation) in ops.iter().enumerate() {
1033        let Operation::DropTable { table } = operation else {
1034            continue;
1035        };
1036        for foreign_key in &table.foreign_keys {
1037            for parent_index in
1038                resolve_named_dependency(&drop_idx, EntityKind::Table, &foreign_key.to_table)
1039            {
1040                add_edge(child_index, parent_index);
1041            }
1042        }
1043    }
1044
1045    let mut by_table: HashMap<&str, Vec<usize>> = HashMap::new();
1046    for (i, op) in ops.iter().enumerate() {
1047        if let Some(tn) = op.table_name() {
1048            let (tp, _) = tiebreak_priority(op);
1049            if tp == 8 {
1050                by_table.entry(tn).or_default().push(i);
1051            }
1052        }
1053    }
1054    for indices in by_table.values() {
1055        for &a in indices {
1056            for &b in indices {
1057                if a == b {
1058                    continue;
1059                }
1060                let (_, spa) = tiebreak_priority(&ops[a]);
1061                let (_, spb) = tiebreak_priority(&ops[b]);
1062                if spa < spb {
1063                    add_edge(a, b);
1064                }
1065            }
1066        }
1067    }
1068}
1069
1070/// Resolves exact entity identities and the canonical zero-argument function
1071/// signature used by function operations.
1072fn resolve_named_dependency(
1073    index: &HashMap<(EntityKind, &str), Vec<usize>>,
1074    kind: EntityKind,
1075    name: &str,
1076) -> Vec<usize> {
1077    if let Some(matches) = index.get(&(kind, name)) {
1078        return matches.clone();
1079    }
1080    if !matches!(kind, EntityKind::Function | EntityKind::Table) {
1081        return Vec::new();
1082    }
1083    let normalized = normalize_dependency_identity(kind, name);
1084    index
1085        .iter()
1086        .filter(|((candidate_kind, candidate), _)| {
1087            *candidate_kind == kind && normalize_dependency_identity(kind, candidate) == normalized
1088        })
1089        .flat_map(|(_, matches)| matches.iter().copied())
1090        .collect()
1091}
1092
1093fn normalize_dependency_identity(kind: EntityKind, identity: &str) -> &str {
1094    match kind {
1095        EntityKind::Function => identity.strip_suffix("()").unwrap_or(identity),
1096        EntityKind::Table => identity.strip_prefix("public.").unwrap_or(identity),
1097        _ => identity,
1098    }
1099}
1100
1101pub(crate) fn dependency_closure(
1102    operations: &[Operation],
1103    seeds: &HashSet<usize>,
1104) -> HashSet<usize> {
1105    let mut adjacency = vec![Vec::new(); operations.len()];
1106    let mut incoming = vec![0; operations.len()];
1107    build_dependency_edges(operations, &mut adjacency, &mut incoming);
1108    let mut reverse = vec![Vec::new(); operations.len()];
1109    for (prerequisite, dependents) in adjacency.iter().enumerate() {
1110        for dependent in dependents {
1111            reverse[*dependent].push(prerequisite);
1112        }
1113    }
1114    let mut selected = seeds.clone();
1115    let mut pending = seeds.iter().copied().collect::<Vec<_>>();
1116    while let Some(index) = pending.pop() {
1117        for prerequisite in &reverse[index] {
1118            if selected.insert(*prerequisite) {
1119                pending.push(*prerequisite);
1120            }
1121        }
1122    }
1123    selected
1124}
1125
1126// Public entry point for diff generation.
1127
1128pub struct DiffEngine;
1129
1130impl DiffEngine {
1131    pub fn new() -> Self {
1132        Self
1133    }
1134
1135    pub fn diff(
1136        &self,
1137        current: &Schema,
1138        previous: &Schema,
1139        dialect: &Dialect,
1140    ) -> Result<Vec<Operation>, DiffError> {
1141        let mut current = current.clone();
1142        let mut previous = previous.clone();
1143        current.canonicalize(dialect);
1144        previous.canonicalize(dialect);
1145        reject_postgres_partition_mutations(&current, &previous)?;
1146        reject_primary_key_mutations(&current, &previous)?;
1147
1148        let raw_ops = generate_diff_for_dialect(&current, &previous, dialect);
1149        let mut raw_ops = raw_ops;
1150        raw_ops.extend(crate::managed_rows::diff_schemas(&current, &previous));
1151        let ops = inject_orphan_triggers(raw_ops, &previous);
1152        let ops = inject_enum_column_casts(ops, &previous);
1153        let ops = decompose(ops);
1154        let ops = sort_operations(ops)?;
1155        let ops = crate::managed_rows::order_operations(ops, &current, &previous)?;
1156        Ok(merge_operations(ops, dialect))
1157    }
1158}
1159
1160fn reject_postgres_partition_mutations(
1161    current: &Schema,
1162    previous: &Schema,
1163) -> Result<(), DiffError> {
1164    for (name, current_table) in &current.tables {
1165        let Some(previous_table) = previous.tables.get(name) else {
1166            continue;
1167        };
1168        if current_table.options.postgres_partition != previous_table.options.postgres_partition {
1169            return Err(DiffError::PostgresPartitionMutation(name.clone()));
1170        }
1171    }
1172    Ok(())
1173}
1174
1175fn generate_diff_for_dialect(
1176    current: &Schema,
1177    previous: &Schema,
1178    dialect: &Dialect,
1179) -> Vec<Operation> {
1180    let mut current_without_tables = current.clone();
1181    current_without_tables.tables.clear();
1182    let mut previous_without_tables = previous.clone();
1183    previous_without_tables.tables.clear();
1184    let mut ops = generate_diff(&current_without_tables, &previous_without_tables);
1185
1186    for (key, current_table) in &current.tables {
1187        match previous.tables.get(key) {
1188            None => diff_table(Some(current_table), None, &mut ops, Some(dialect)),
1189            Some(previous_table) => {
1190                diff_table(
1191                    Some(current_table),
1192                    Some(previous_table),
1193                    &mut ops,
1194                    Some(dialect),
1195                );
1196            }
1197        }
1198    }
1199    for (key, previous_table) in &previous.tables {
1200        if !current.tables.contains_key(key) {
1201            diff_table(None, Some(previous_table), &mut ops, Some(dialect));
1202        }
1203    }
1204    ops
1205}
1206
1207fn reject_primary_key_mutations(current: &Schema, previous: &Schema) -> Result<(), DiffError> {
1208    for (name, current_table) in &current.tables {
1209        let Some(previous_table) = previous.tables.get(name) else {
1210            continue;
1211        };
1212        if current_table.primary_key != previous_table.primary_key {
1213            return Err(DiffError::PrimaryKeyMutation(name.clone()));
1214        }
1215    }
1216    Ok(())
1217}
1218
1219impl Default for DiffEngine {
1220    fn default() -> Self {
1221        Self::new()
1222    }
1223}
1224
1225#[cfg(test)]
1226mod test_diff;