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
29pub fn generate_diff(current: &Schema, previous: &Schema) -> Vec<Operation> {
33 let mut ops: Vec<Operation> = Vec::new();
34
35 diff_map_with_eq(
36 ¤t.extensions,
37 &previous.extensions,
38 &mut ops,
39 extension_equal,
40 diff_extension,
41 );
42 diff_map_with_eq(
43 ¤t.sequences,
44 &previous.sequences,
45 &mut ops,
46 sequence_equal,
47 diff_sequence,
48 );
49 diff_map(¤t.enums, &previous.enums, &mut ops, diff_enum);
50 diff_map_with_eq(
51 ¤t.functions,
52 &previous.functions,
53 &mut ops,
54 function_equal,
55 diff_function,
56 );
57 diff_map_with_eq(
58 ¤t.views,
59 &previous.views,
60 &mut ops,
61 view_equal,
62 diff_view,
63 );
64 diff_map(
65 ¤t.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(¤t.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
535fn 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
605fn 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
697fn 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
778fn 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
865pub 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 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
1070fn 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
1126pub 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(¤t, &previous)?;
1146 reject_primary_key_mutations(¤t, &previous)?;
1147
1148 let raw_ops = generate_diff_for_dialect(¤t, &previous, dialect);
1149 let mut raw_ops = raw_ops;
1150 raw_ops.extend(crate::managed_rows::diff_schemas(¤t, &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, ¤t, &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 ¤t.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(¤t_without_tables, &previous_without_tables);
1185
1186 for (key, current_table) in ¤t.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 ¤t.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;