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 }