Debian Codegraph @

django/db/migrations/graph.py

raw
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