diff options
Diffstat (limited to 'internal/services/migration_dependency_graph.go')
| -rw-r--r-- | internal/services/migration_dependency_graph.go | 191 |
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 -} |