aboutsummaryrefslogtreecommitdiffstats
path: root/internal/services/migration_dependency_graph.go
blob: 3f0e4176fa3c2fe8af847e888345c0436ea5d1a8 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
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
}