aboutsummaryrefslogtreecommitdiffstats
path: root/internal/services/migration_dependency_graph.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.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.go')
-rw-r--r--internal/services/migration_dependency_graph.go191
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
+}