aboutsummaryrefslogtreecommitdiffstats
path: root/internal/services/migration_dependency_graph.go
diff options
context:
space:
mode:
Diffstat (limited to 'internal/services/migration_dependency_graph.go')
-rw-r--r--internal/services/migration_dependency_graph.go191
1 files changed, 0 insertions, 191 deletions
diff --git a/internal/services/migration_dependency_graph.go b/internal/services/migration_dependency_graph.go
deleted file mode 100644
index 3f0e417..0000000
--- a/internal/services/migration_dependency_graph.go
+++ /dev/null
@@ -1,191 +0,0 @@
-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
-}