| 1 |
from functools import total_ordering |
| 2 |
|
| 3 |
from django.db.migrations.state import ProjectState |
| 4 |
|
| 5 |
from .exceptions import CircularDependencyError, NodeNotFoundError |
| 6 |
|
| 7 |
|
| 8 |
@total_ordering |
| 9 |
class Node: |
| 10 |
""" |
| 11 |
A single node in the migration graph. Contains direct links to adjacent |
| 12 |
nodes in either direction. |
| 13 |
""" |
| 14 |
|
| 15 |
def __init__(self, key): |
| 16 |
self.key = key |
| 17 |
self.children = set() |
| 18 |
self.parents = set() |
| 19 |
|
| 20 |
def __eq__(self, other): |
| 21 |
return self.key == other |
| 22 |
|
| 23 |
def __lt__(self, other): |
| 24 |
return self.key < other |
| 25 |
|
| 26 |
def __hash__(self): |
| 27 |
return hash(self.key) |
| 28 |
|
| 29 |
def __getitem__(self, item): |
| 30 |
return self.key[item] |
| 31 |
|
| 32 |
def __str__(self): |
| 33 |
return str(self.key) |
| 34 |
|
| 35 |
def __repr__(self): |
| 36 |
return "<%s: (%r, %r)>" % (self.__class__.__name__, self.key[0], self.key[1]) |
| 37 |
|
| 38 |
def add_child(self, child): |
| 39 |
self.children.add(child) |
| 40 |
|
| 41 |
def add_parent(self, parent): |
| 42 |
self.parents.add(parent) |
| 43 |
|
| 44 |
|
| 45 |
class DummyNode(Node): |
| 46 |
""" |
| 47 |
A node that doesn't correspond to a migration file on disk. |
| 48 |
(A squashed migration that was removed, for example.) |
| 49 |
|
| 50 |
After the migration graph is processed, all dummy nodes should be removed. |
| 51 |
If there are any left, a nonexistent dependency error is raised. |
| 52 |
""" |
| 53 |
|
| 54 |
def __init__(self, key, origin, error_message): |
| 55 |
super().__init__(key) |
| 56 |
self.origin = origin |
| 57 |
self.error_message = error_message |
| 58 |
|
| 59 |
def raise_error(self): |
| 60 |
raise NodeNotFoundError(self.error_message, self.key, origin=self.origin) |
| 61 |
|
| 62 |
|
| 63 |
class MigrationGraph: |
| 64 |
""" |
| 65 |
Represent the digraph of all migrations in a project. |
| 66 |
|
| 67 |
Each migration is a node, and each dependency is an edge. There are |
| 68 |
no implicit dependencies between numbered migrations - the numbering is |
| 69 |
merely a convention to aid file listing. Every new numbered migration |
| 70 |
has a declared dependency to the previous number, meaning that VCS |
| 71 |
branch merges can be detected and resolved. |
| 72 |
|
| 73 |
Migrations files can be marked as replacing another set of migrations - |
| 74 |
this is to support the "squash" feature. The graph handler isn't responsible |
| 75 |
for these; instead, the code to load them in here should examine the |
| 76 |
migration files and if the replaced migrations are all either unapplied |
| 77 |
or not present, it should ignore the replaced ones, load in just the |
| 78 |
replacing migration, and repoint any dependencies that pointed to the |
| 79 |
replaced migrations to point to the replacing one. |
| 80 |
|
| 81 |
A node should be a tuple: (app_path, migration_name). The tree special-cases |
| 82 |
things within an app - namely, root nodes and leaf nodes ignore dependencies |
| 83 |
to other apps. |
| 84 |
""" |
| 85 |
|
| 86 |
def __init__(self): |
| 87 |
self.node_map = {} |
| 88 |
self.nodes = {} |
| 89 |
|
| 90 |
def add_node(self, key, migration): |
| 91 |
assert key not in self.node_map |
| 92 |
node = Node(key) |
| 93 |
self.node_map[key] = node |
| 94 |
self.nodes[key] = migration |
| 95 |
|
| 96 |
def add_dummy_node(self, key, origin, error_message): |
| 97 |
node = DummyNode(key, origin, error_message) |
| 98 |
self.node_map[key] = node |
| 99 |
self.nodes[key] = None |
| 100 |
|
| 101 |
def add_dependency(self, migration, child, parent, skip_validation=False): |
| 102 |
""" |
| 103 |
This may create dummy nodes if they don't yet exist. If |
| 104 |
`skip_validation=True`, validate_consistency() should be called |
| 105 |
afterward. |
| 106 |
""" |
| 107 |
if child not in self.nodes: |
| 108 |
error_message = ( |
| 109 |
"Migration %s dependencies reference nonexistent" |
| 110 |
" child node %r" % (migration, child) |
| 111 |
) |
| 112 |
self.add_dummy_node(child, migration, error_message) |
| 113 |
if parent not in self.nodes: |
| 114 |
error_message = ( |
| 115 |
"Migration %s dependencies reference nonexistent" |
| 116 |
" parent node %r" % (migration, parent) |
| 117 |
) |
| 118 |
self.add_dummy_node(parent, migration, error_message) |
| 119 |
self.node_map[child].add_parent(self.node_map[parent]) |
| 120 |
self.node_map[parent].add_child(self.node_map[child]) |
| 121 |
if not skip_validation: |
| 122 |
self.validate_consistency() |
| 123 |
|
| 124 |
def remove_replaced_nodes(self, replacement, replaced): |
| 125 |
""" |
| 126 |
Remove each of the `replaced` nodes (when they exist). Any |
| 127 |
dependencies that were referencing them are changed to reference the |
| 128 |
`replacement` node instead. |
| 129 |
""" |
| 130 |
# Cast list of replaced keys to set to speed up lookup later. |
| 131 |
replaced = set(replaced) |
| 132 |
try: |
| 133 |
replacement_node = self.node_map[replacement] |
| 134 |
except KeyError as err: |
| 135 |
raise NodeNotFoundError( |
| 136 |
"Unable to find replacement node %r. It was either never added" |
| 137 |
" to the migration graph, or has been removed." % (replacement,), |
| 138 |
replacement, |
| 139 |
) from err |
| 140 |
for replaced_key in replaced: |
| 141 |
self.nodes.pop(replaced_key, None) |
| 142 |
replaced_node = self.node_map.pop(replaced_key, None) |
| 143 |
if replaced_node: |
| 144 |
for child in replaced_node.children: |
| 145 |
child.parents.remove(replaced_node) |
| 146 |
# We don't want to create dependencies between the replaced |
| 147 |
# node and the replacement node as this would lead to |
| 148 |
# self-referencing on the replacement node at a later iteration. |
| 149 |
if child.key not in replaced: |
| 150 |
replacement_node.add_child(child) |
| 151 |
child.add_parent(replacement_node) |
| 152 |
for parent in replaced_node.parents: |
| 153 |
parent.children.remove(replaced_node) |
| 154 |
# Again, to avoid self-referencing. |
| 155 |
if parent.key not in replaced: |
| 156 |
replacement_node.add_parent(parent) |
| 157 |
parent.add_child(replacement_node) |
| 158 |
|
| 159 |
def remove_replacement_node(self, replacement, replaced): |
| 160 |
""" |
| 161 |
The inverse operation to `remove_replaced_nodes`. Almost. Remove the |
| 162 |
replacement node `replacement` and remap its child nodes to `replaced` |
| 163 |
- the list of nodes it would have replaced. Don't remap its parent |
| 164 |
nodes as they are expected to be correct already. |
| 165 |
""" |
| 166 |
self.nodes.pop(replacement, None) |
| 167 |
try: |
| 168 |
replacement_node = self.node_map.pop(replacement) |
| 169 |
except KeyError as err: |
| 170 |
raise NodeNotFoundError( |
| 171 |
"Unable to remove replacement node %r. It was either never added" |
| 172 |
" to the migration graph, or has been removed already." |
| 173 |
% (replacement,), |
| 174 |
replacement, |
| 175 |
) from err |
| 176 |
replaced_nodes = set() |
| 177 |
replaced_nodes_parents = set() |
| 178 |
for key in replaced: |
| 179 |
replaced_node = self.node_map.get(key) |
| 180 |
if replaced_node: |
| 181 |
replaced_nodes.add(replaced_node) |
| 182 |
replaced_nodes_parents |= replaced_node.parents |
| 183 |
# We're only interested in the latest replaced node, so filter out |
| 184 |
# replaced nodes that are parents of other replaced nodes. |
| 185 |
replaced_nodes -= replaced_nodes_parents |
| 186 |
for child in replacement_node.children: |
| 187 |
child.parents.remove(replacement_node) |
| 188 |
for replaced_node in replaced_nodes: |
| 189 |
replaced_node.add_child(child) |
| 190 |
child.add_parent(replaced_node) |
| 191 |
for parent in replacement_node.parents: |
| 192 |
parent.children.remove(replacement_node) |
| 193 |
# NOTE: There is no need to remap parent dependencies as we can |
| 194 |
# assume the replaced nodes already have the correct ancestry. |
| 195 |
|
| 196 |
def validate_consistency(self): |
| 197 |
"""Ensure there are no dummy nodes remaining in the graph.""" |
| 198 |
[n.raise_error() for n in self.node_map.values() if isinstance(n, DummyNode)] |
| 199 |
|
| 200 |
def forwards_plan(self, target): |
| 201 |
""" |
| 202 |
Given a node, return a list of which previous nodes (dependencies) must |
| 203 |
be applied, ending with the node itself. This is the list you would |
| 204 |
follow if applying the migrations to a database. |
| 205 |
""" |
| 206 |
if target not in self.nodes: |
| 207 |
raise NodeNotFoundError("Node %r not a valid node" % (target,), target) |
| 208 |
return self.iterative_dfs(self.node_map[target]) |
| 209 |
|
| 210 |
def backwards_plan(self, target): |
| 211 |
""" |
| 212 |
Given a node, return a list of which dependent nodes (dependencies) |
| 213 |
must be unapplied, ending with the node itself. This is the list you |
| 214 |
would follow if removing the migrations from a database. |
| 215 |
""" |
| 216 |
if target not in self.nodes: |
| 217 |
raise NodeNotFoundError("Node %r not a valid node" % (target,), target) |
| 218 |
return self.iterative_dfs(self.node_map[target], forwards=False) |
| 219 |
|
| 220 |
def iterative_dfs(self, start, forwards=True): |
| 221 |
"""Iterative depth-first search for finding dependencies.""" |
| 222 |
visited = [] |
| 223 |
visited_set = set() |
| 224 |
stack = [(start, False)] |
| 225 |
while stack: |
| 226 |
node, processed = stack.pop() |
| 227 |
if node in visited_set: |
| 228 |
pass |
| 229 |
elif processed: |
| 230 |
visited_set.add(node) |
| 231 |
visited.append(node.key) |
| 232 |
else: |
| 233 |
stack.append((node, True)) |
| 234 |
stack += [ |
| 235 |
(n, False) |
| 236 |
for n in sorted(node.parents if forwards else node.children) |
| 237 |
] |
| 238 |
return visited |
| 239 |
|
| 240 |
def root_nodes(self, app=None): |
| 241 |
""" |
| 242 |
Return all root nodes - that is, nodes with no dependencies inside |
| 243 |
their app. These are the starting point for an app. |
| 244 |
""" |
| 245 |
roots = set() |
| 246 |
for node in self.nodes: |
| 247 |
if all(key[0] != node[0] for key in self.node_map[node].parents) and ( |
| 248 |
not app or app == node[0] |
| 249 |
): |
| 250 |
roots.add(node) |
| 251 |
return sorted(roots) |
| 252 |
|
| 253 |
def leaf_nodes(self, app=None): |
| 254 |
""" |
| 255 |
Return all leaf nodes - that is, nodes with no dependents in their app. |
| 256 |
These are the "most current" version of an app's schema. |
| 257 |
Having more than one per app is technically an error, but one that |
| 258 |
gets handled further up, in the interactive command - it's usually the |
| 259 |
result of a VCS merge and needs some user input. |
| 260 |
""" |
| 261 |
leaves = set() |
| 262 |
for node in self.nodes: |
| 263 |
if all(key[0] != node[0] for key in self.node_map[node].children) and ( |
| 264 |
not app or app == node[0] |
| 265 |
): |
| 266 |
leaves.add(node) |
| 267 |
return sorted(leaves) |
| 268 |
|
| 269 |
def ensure_not_cyclic(self): |
| 270 |
# Algo from GvR: |
| 271 |
# https://neopythonic.blogspot.com/2009/01/detecting-cycles-in-directed-graph.html |
| 272 |
todo = set(self.nodes) |
| 273 |
while todo: |
| 274 |
node = todo.pop() |
| 275 |
stack = [node] |
| 276 |
while stack: |
| 277 |
top = stack[-1] |
| 278 |
for child in self.node_map[top].children: |
| 279 |
# Use child.key instead of child to speed up the frequent |
| 280 |
# hashing. |
| 281 |
node = child.key |
| 282 |
if node in stack: |
| 283 |
cycle = stack[stack.index(node) :] |
| 284 |
raise CircularDependencyError( |
| 285 |
", ".join("%s.%s" % n for n in cycle) |
| 286 |
) |
| 287 |
if node in todo: |
| 288 |
stack.append(node) |
| 289 |
todo.remove(node) |
| 290 |
break |
| 291 |
else: |
| 292 |
node = stack.pop() |
| 293 |
|
| 294 |
def __str__(self): |
| 295 |
return "Graph: %s nodes, %s edges" % self._nodes_and_edges() |
| 296 |
|
| 297 |
def __repr__(self): |
| 298 |
nodes, edges = self._nodes_and_edges() |
| 299 |
return "<%s: nodes=%s, edges=%s>" % (self.__class__.__name__, nodes, edges) |
| 300 |
|
| 301 |
def _nodes_and_edges(self): |
| 302 |
return len(self.nodes), sum( |
| 303 |
len(node.parents) for node in self.node_map.values() |
| 304 |
) |
| 305 |
|
| 306 |
def _generate_plan(self, nodes, at_end): |
| 307 |
plan = [] |
| 308 |
for node in nodes: |
| 309 |
for migration in self.forwards_plan(node): |
| 310 |
if migration not in plan and (at_end or migration not in nodes): |
| 311 |
plan.append(migration) |
| 312 |
return plan |
| 313 |
|
| 314 |
def make_state(self, nodes=None, at_end=True, real_apps=None): |
| 315 |
""" |
| 316 |
Given a migration node or nodes, return a complete ProjectState for it. |
| 317 |
If at_end is False, return the state before the migration has run. |
| 318 |
If nodes is not provided, return the overall most current project state. |
| 319 |
""" |
| 320 |
if nodes is None: |
| 321 |
nodes = list(self.leaf_nodes()) |
| 322 |
if not nodes: |
| 323 |
return ProjectState() |
| 324 |
if not isinstance(nodes[0], tuple): |
| 325 |
nodes = [nodes] |
| 326 |
plan = self._generate_plan(nodes, at_end) |
| 327 |
project_state = ProjectState(real_apps=real_apps) |
| 328 |
for node in plan: |
| 329 |
project_state = self.nodes[node].mutate_state(project_state, preserve=False) |
| 330 |
return project_state |
| 331 |
|
| 332 |
def __contains__(self, node): |
| 333 |
return node in self.nodes |