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") }