diff options
| author | Eugene Triguba <hello@eugenetriguba.com> | 2025-10-18 10:43:39 -0400 |
|---|---|---|
| committer | Eugene Triguba <hello@eugenetriguba.com> | 2025-11-26 11:46:57 -0500 |
| commit | e5658d1f61415054029b66cd2f703f1f40138460 (patch) | |
| tree | c609e209f4cebc62dd985d1b773558f47eb73bf6 /internal/services/migration_dependency_graph.go | |
| parent | Add is-branch main check for docs deployment (diff) | |
| download | cli-e5658d1f61415054029b66cd2f703f1f40138460.zip | |
Add support for migration dependencies
Diffstat (limited to 'internal/services/migration_dependency_graph.go')
| -rw-r--r-- | internal/services/migration_dependency_graph.go | 191 |
1 files changed, 191 insertions, 0 deletions
diff --git a/internal/services/migration_dependency_graph.go b/internal/services/migration_dependency_graph.go new file mode 100644 index 0000000..3f0e417 --- /dev/null +++ b/internal/services/migration_dependency_graph.go @@ -0,0 +1,191 @@ +package services + +import ( + "fmt" + "slices" + "sort" + "strconv" + "time" + + "git.sr.ht/~eugenetriguba/bolt/internal/configloader" + "git.sr.ht/~eugenetriguba/bolt/internal/models" +) + +// MigrationDependencyGraph handles all dependency graph operations for migrations, +// including topological sorting, dependency validation, and graph analysis. +type MigrationDependencyGraph struct { + cfg configloader.Config +} + +func NewMigrationDependencyGraph(cfg configloader.Config) *MigrationDependencyGraph { + return &MigrationDependencyGraph{cfg: cfg} +} + +// TopologicalSort performs a topological sort on migrations based on their dependencies. +// It uses Kahn's algorithm to detect cycles and order migrations. When multiple migrations +// have the same topological level, they are sorted by version for determinism. `migrations` +// is expected to be a map of version -> Migration. +func (g *MigrationDependencyGraph) TopologicalSort(migrations map[string]*models.Migration) ([]*models.Migration, error) { + graph := make(map[string][]*models.Migration) + inDegree := make(map[string]int) + + // To start, we need to build the graph and in-degree count. + for _, m := range migrations { + for _, dep := range m.Dependencies { + if _, exists := migrations[dep]; !exists { + return nil, fmt.Errorf( + "migration %s depends on non-existent migration %s", + m.Version, dep, + ) + } + graph[dep] = append(graph[dep], m) + inDegree[m.Version]++ + } + } + + // Next step of Kahn's algorithm is to find the vertices with in-degree of 0 + // Often, this will simply be one migration (the first migration), but there + // could be multiple independent migrations which would result in multiple + // starting points. + queue := make([]*models.Migration, 0) + for _, m := range migrations { + if inDegree[m.Version] == 0 { + queue = append(queue, m) + } + } + // Within each topological level, we want to sort the migrations by the version + // for determinism, so it's easier to reason about how migrations will execute. + g.sortByVersion(queue) + + result := make([]*models.Migration, 0) + for len(queue) > 0 { + current := queue[0] + queue = queue[1:] + result = append(result, current) + + newlyAvailable := make([]*models.Migration, 0) + for _, neighbor := range graph[current.Version] { + inDegree[neighbor.Version]-- + if inDegree[neighbor.Version] == 0 { + newlyAvailable = append(newlyAvailable, neighbor) + } + } + + g.sortByVersion(newlyAvailable) + queue = append(queue, newlyAvailable...) + g.sortByVersion(queue) + } + + if len(result) != len(migrations) { + return nil, fmt.Errorf("circular dependency detected in migrations") + } + + return result, nil +} + +// ReverseTopologicalSort returns migrations in reverse topological order (for reverting). +func (g *MigrationDependencyGraph) ReverseTopologicalSort(migrations map[string]*models.Migration) ([]*models.Migration, error) { + sorted, err := g.TopologicalSort(migrations) + if err != nil { + return nil, err + } + reversed := make([]*models.Migration, len(sorted)) + for i, m := range sorted { + reversed[len(sorted)-1-i] = m + } + return reversed, nil +} + +// sortByVersion sorts migrations by version number deterministically +func (g *MigrationDependencyGraph) sortByVersion(migrations []*models.Migration) { + sort.Slice(migrations, func(i, j int) bool { + if g.cfg.Migrations.VersionStyle == configloader.VersionStyleSequential { + v1, _ := strconv.ParseInt(migrations[i].Version, 10, 64) + v2, _ := strconv.ParseInt(migrations[j].Version, 10, 64) + return v1 < v2 + } + // Note: If not sequential, we assume timestamp style. + t1, _ := time.Parse("20060102150405", migrations[i].Version) + t2, _ := time.Parse("20060102150405", migrations[j].Version) + return t1.Before(t2) + }) +} + +// CheckDependenciesApplied verifies that all dependencies of a migration have been applied. +func (g *MigrationDependencyGraph) CheckDependenciesApplied( + migration *models.Migration, + allMigrations map[string]*models.Migration, +) error { + for _, depVersion := range migration.Dependencies { + dep, exists := allMigrations[depVersion] + if !exists { + return fmt.Errorf( + "cannot apply migration %s: dependency %s does not exist", + migration.Version, depVersion, + ) + } + if !dep.Applied { + return fmt.Errorf( + "cannot apply migration %s: dependency %s has not been applied", + migration.Version, depVersion, + ) + } + } + + return nil +} + +// CheckNoDependentsApplied verifies that no applied migrations depend on this migration. +func (g *MigrationDependencyGraph) CheckNoDependentsApplied( + migration *models.Migration, + allMigrations map[string]*models.Migration, +) error { + for _, m := range allMigrations { + if m.Version == migration.Version { + continue + } + if m.Applied && slices.Contains(m.Dependencies, migration.Version) { + return fmt.Errorf( + "cannot revert migration %s: migration %s still applied and depends on it", + migration.Version, m.Version, + ) + } + } + + return nil +} + +// FindLeafNodes finds all migrations that no other migration depends on. These are +// the "leaf" nodes in the dependency graph. If there are circular dependency in the +// migration graph, an error is returned. +func (g *MigrationDependencyGraph) FindLeafNodes(localMigrations map[string]*models.Migration) ([]string, error) { + if len(localMigrations) == 0 { + return []string{}, nil + } + + // Validate there are no circular dependencies by building + // out the dependency graph via topological sort. + _, err := g.TopologicalSort(localMigrations) + if err != nil { + return nil, err + } + + // What are all the migrations that have dependencies? + dependedUpon := make(map[string]bool) + for _, migration := range localMigrations { + for _, dep := range migration.Dependencies { + dependedUpon[dep] = true + } + } + + // What are all the migrations that no other migration depends on? + // These are the leaf nodes. + leafNodes := make([]string, 0) + for _, migration := range localMigrations { + if !dependedUpon[migration.Version] { + leafNodes = append(leafNodes, migration.Version) + } + } + + return leafNodes, nil +} |