aboutsummaryrefslogtreecommitdiffstats
path: root/internal/services/migration_dependency_graph_test.go
diff options
context:
space:
mode:
authorEugene Triguba <hello@eugenetriguba.com>2025-10-18 10:43:39 -0400
committerEugene Triguba <hello@eugenetriguba.com>2025-11-26 11:46:57 -0500
commite5658d1f61415054029b66cd2f703f1f40138460 (patch)
treec609e209f4cebc62dd985d1b773558f47eb73bf6 /internal/services/migration_dependency_graph_test.go
parentAdd is-branch main check for docs deployment (diff)
downloadcli-e5658d1f61415054029b66cd2f703f1f40138460.zip
Add support for migration dependencies
Diffstat (limited to 'internal/services/migration_dependency_graph_test.go')
-rw-r--r--internal/services/migration_dependency_graph_test.go377
1 files changed, 377 insertions, 0 deletions
diff --git a/internal/services/migration_dependency_graph_test.go b/internal/services/migration_dependency_graph_test.go
new file mode 100644
index 0000000..29d36db
--- /dev/null
+++ b/internal/services/migration_dependency_graph_test.go
@@ -0,0 +1,377 @@
+package services
+
+import (
+ "testing"
+
+ "git.sr.ht/~eugenetriguba/bolt/internal/configloader"
+ "git.sr.ht/~eugenetriguba/bolt/internal/models"
+ "git.sr.ht/~eugenetriguba/checkmate/assert"
+ "git.sr.ht/~eugenetriguba/checkmate/check"
+)
+
+func TestTopologicalSort_ThreeMigrationsWithDependencies(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "003": {Version: "003", Dependencies: []string{"001", "002"}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "001": {Version: "001", Dependencies: []string{}},
+ }
+
+ sorted, err := graph.TopologicalSort(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(sorted), 3)
+ assert.Equal(t, sorted[0].Version, "001")
+ assert.Equal(t, sorted[1].Version, "002")
+ assert.Equal(t, sorted[2].Version, "003")
+}
+
+func TestTopologicalSort_CircularDependency(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{"002"}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ }
+
+ _, err := graph.TopologicalSort(migrations)
+
+ assert.ErrorContains(t, err, "circular dependency detected")
+}
+
+func TestTopologicalSort_NonExistentDependency(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{"002"}},
+ }
+
+ _, err := graph.TopologicalSort(migrations)
+
+ assert.ErrorContains(t, err, "depends on non-existent migration")
+}
+
+func TestTopologicalSort_EmptyList(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{}
+
+ sorted, err := graph.TopologicalSort(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(sorted), 0)
+}
+
+func TestTopologicalSort_DiamondDependency(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ // Diamond: 001 -> 002, 001 -> 003, 002 -> 004, 003 -> 004
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "003": {Version: "003", Dependencies: []string{"001"}},
+ "004": {Version: "004", Dependencies: []string{"002", "003"}},
+ }
+
+ sorted, err := graph.TopologicalSort(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(sorted), 4)
+ assert.Equal(t, sorted[0].Version, "001")
+ // 002 and 003 can be in either order (both depend only on 001)
+ // But our implementation sorts deterministically
+ assert.Equal(t, sorted[1].Version, "002")
+ assert.Equal(t, sorted[2].Version, "003")
+ assert.Equal(t, sorted[3].Version, "004")
+}
+
+func TestTopologicalSort_TimestampVersionStyle(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleTimestamp,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "20250101120000": {Version: "20250101120000", Dependencies: []string{}},
+ "20250101130000": {Version: "20250101130000", Dependencies: []string{"20250101120000"}},
+ "20250101110000": {Version: "20250101110000", Dependencies: []string{}},
+ }
+
+ sorted, err := graph.TopologicalSort(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(sorted), 3)
+ // Should be sorted by timestamp among peers
+ assert.Equal(t, sorted[0].Version, "20250101110000")
+ assert.Equal(t, sorted[1].Version, "20250101120000")
+ assert.Equal(t, sorted[2].Version, "20250101130000")
+}
+
+func TestReverseTopologicalSort(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "003": {Version: "003", Dependencies: []string{"001", "002"}},
+ }
+
+ reversed, err := graph.ReverseTopologicalSort(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(reversed), 3)
+ assert.Equal(t, reversed[0].Version, "003")
+ assert.Equal(t, reversed[1].Version, "002")
+ assert.Equal(t, reversed[2].Version, "001")
+}
+
+func TestReverseTopologicalSort_CircularDependency(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{"002"}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ }
+
+ _, err := graph.ReverseTopologicalSort(migrations)
+
+ assert.ErrorContains(t, err, "circular dependency detected")
+}
+
+func TestCheckDependenciesApplied_AllApplied(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: true, Dependencies: []string{"001"}},
+ "003": {Version: "003", Applied: false, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckDependenciesApplied(allMigrations["003"], allMigrations)
+
+ assert.Nil(t, err)
+}
+
+func TestCheckDependenciesApplied_DependencyNotApplied(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: false, Dependencies: []string{"001"}},
+ "003": {Version: "003", Applied: false, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckDependenciesApplied(allMigrations["003"], allMigrations)
+
+ assert.ErrorContains(t, err, "cannot apply migration 003")
+ assert.ErrorContains(t, err, "dependency 002 has not been applied")
+}
+
+func TestCheckDependenciesApplied_DependencyDoesNotExist(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "003": {Version: "003", Applied: false, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckDependenciesApplied(allMigrations["003"], allMigrations)
+
+ assert.ErrorContains(t, err, "cannot apply migration 003")
+ assert.ErrorContains(t, err, "dependency 002 does not exist")
+}
+
+func TestCheckDependenciesApplied_NoDependencies(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: false, Dependencies: []string{}},
+ }
+
+ err := graph.CheckDependenciesApplied(allMigrations["001"], allMigrations)
+
+ assert.Nil(t, err)
+}
+
+func TestCheckNoDependentsApplied_NoDependents(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: true, Dependencies: []string{"001"}},
+ "003": {Version: "003", Applied: false, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckNoDependentsApplied(allMigrations["002"], allMigrations)
+
+ assert.Nil(t, err)
+}
+
+func TestCheckNoDependentsApplied_HasAppliedDependent(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: true, Dependencies: []string{"001"}},
+ "003": {Version: "003", Applied: true, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckNoDependentsApplied(allMigrations["002"], allMigrations)
+
+ assert.ErrorContains(t, err, "cannot revert migration 002")
+ assert.ErrorContains(t, err, "migration 003 still applied and depends on it")
+}
+
+func TestCheckNoDependentsApplied_HasUnappliedDependent(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: true, Dependencies: []string{"001"}},
+ "003": {Version: "003", Applied: false, Dependencies: []string{"001", "002"}},
+ }
+
+ err := graph.CheckNoDependentsApplied(allMigrations["002"], allMigrations)
+
+ assert.Nil(t, err)
+}
+
+func TestCheckNoDependentsApplied_RootMigration(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ allMigrations := map[string]*models.Migration{
+ "001": {Version: "001", Applied: true, Dependencies: []string{}},
+ "002": {Version: "002", Applied: true, Dependencies: []string{"001"}},
+ }
+
+ err := graph.CheckNoDependentsApplied(allMigrations["001"], allMigrations)
+
+ assert.ErrorContains(t, err, "cannot revert migration 001")
+ assert.ErrorContains(t, err, "migration 002 still applied and depends on it")
+}
+
+func TestFindLeafNodes_NoMigrations(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+
+ leafNodes, err := graph.FindLeafNodes(map[string]*models.Migration{})
+
+ assert.Nil(t, err)
+ assert.DeepEqual(t, leafNodes, []string{})
+}
+
+func TestFindLeafNodes_SingleMigration(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ }
+
+ leafNodes, err := graph.FindLeafNodes(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(leafNodes), 1)
+ assert.Contains(t, leafNodes, "001")
+}
+
+func TestFindLeafNodes_LinearChain(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "003": {Version: "003", Dependencies: []string{"002"}},
+ }
+
+ leafNodes, err := graph.FindLeafNodes(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(leafNodes), 1)
+ assert.Contains(t, leafNodes, "003")
+}
+
+func TestFindLeafNodes_ParallelBranches(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "003": {Version: "003", Dependencies: []string{"001"}},
+ }
+
+ leafNodes, err := graph.FindLeafNodes(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(leafNodes), 2)
+ assert.Contains(t, leafNodes, "002")
+ assert.Contains(t, leafNodes, "003")
+}
+
+func TestFindLeafNodes_ComplexGraph(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{})
+ // Diamond shape: 001 -> 002, 001 -> 003, 002 -> 004, 003 -> 004
+ // Plus independent branch: 005
+ migrations := map[string]*models.Migration{
+ "001": {Version: "001", Dependencies: []string{}},
+ "002": {Version: "002", Dependencies: []string{"001"}},
+ "003": {Version: "003", Dependencies: []string{"001"}},
+ "004": {Version: "004", Dependencies: []string{"002", "003"}},
+ "005": {Version: "005", Dependencies: []string{}},
+ }
+
+ leafNodes, err := graph.FindLeafNodes(migrations)
+
+ assert.Nil(t, err)
+ assert.Equal(t, len(leafNodes), 2)
+ assert.Contains(t, leafNodes, "004")
+ assert.Contains(t, leafNodes, "005")
+}
+
+func TestSortByVersion_Sequential(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleSequential,
+ },
+ })
+ migrations := []*models.Migration{
+ {Version: "003"},
+ {Version: "001"},
+ {Version: "002"},
+ }
+
+ graph.sortByVersion(migrations)
+
+ check.Equal(t, migrations[0].Version, "001")
+ check.Equal(t, migrations[1].Version, "002")
+ check.Equal(t, migrations[2].Version, "003")
+}
+
+func TestSortByVersion_Timestamp(t *testing.T) {
+ graph := NewMigrationDependencyGraph(configloader.Config{
+ Migrations: configloader.MigrationsConfig{
+ VersionStyle: configloader.VersionStyleTimestamp,
+ },
+ })
+ migrations := []*models.Migration{
+ {Version: "20250101130000"},
+ {Version: "20250101110000"},
+ {Version: "20250101120000"},
+ }
+
+ graph.sortByVersion(migrations)
+
+ check.Equal(t, migrations[0].Version, "20250101110000")
+ check.Equal(t, migrations[1].Version, "20250101120000")
+ check.Equal(t, migrations[2].Version, "20250101130000")
+}