Debian Codegraph @

tests/migrations/test_graph.py

raw
1 from django.db.migrations.exceptions import CircularDependencyError, NodeNotFoundError
2 from django.db.migrations.graph import DummyNode, MigrationGraph, Node
3 from django.test import SimpleTestCase
4
5
6 class GraphTests(SimpleTestCase):
7 """
8 Tests the digraph structure.
9 """
10
11 def test_simple_graph(self):
12 """
13 Tests a basic dependency graph:
14
15 app_a: 0001 <-- 0002 <--- 0003 <-- 0004
16 /
17 app_b: 0001 <-- 0002 <-/
18 """
19 # Build graph
20 graph = MigrationGraph()
21 graph.add_node(("app_a", "0001"), None)
22 graph.add_node(("app_a", "0002"), None)
23 graph.add_node(("app_a", "0003"), None)
24 graph.add_node(("app_a", "0004"), None)
25 graph.add_node(("app_b", "0001"), None)
26 graph.add_node(("app_b", "0002"), None)
27 graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_a", "0003"))
28 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
29 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
30 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))
31 graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
32 # Test root migration case
33 self.assertEqual(
34 graph.forwards_plan(("app_a", "0001")),
35 [("app_a", "0001")],
36 )
37 # Test branch B only
38 self.assertEqual(
39 graph.forwards_plan(("app_b", "0002")),
40 [("app_b", "0001"), ("app_b", "0002")],
41 )
42 # Test whole graph
43 self.assertEqual(
44 graph.forwards_plan(("app_a", "0004")),
45 [
46 ("app_b", "0001"),
47 ("app_b", "0002"),
48 ("app_a", "0001"),
49 ("app_a", "0002"),
50 ("app_a", "0003"),
51 ("app_a", "0004"),
52 ],
53 )
54 # Test reverse to b:0002
55 self.assertEqual(
56 graph.backwards_plan(("app_b", "0002")),
57 [("app_a", "0004"), ("app_a", "0003"), ("app_b", "0002")],
58 )
59 # Test roots and leaves
60 self.assertEqual(
61 graph.root_nodes(),
62 [("app_a", "0001"), ("app_b", "0001")],
63 )
64 self.assertEqual(
65 graph.leaf_nodes(),
66 [("app_a", "0004"), ("app_b", "0002")],
67 )
68
69 def test_complex_graph(self):
70 r"""
71 Tests a complex dependency graph:
72
73 app_a: 0001 <-- 0002 <--- 0003 <-- 0004
74 \ \ / /
75 app_b: 0001 <-\ 0002 <-X /
76 \ \ /
77 app_c: \ 0001 <-- 0002 <-
78 """
79 # Build graph
80 graph = MigrationGraph()
81 graph.add_node(("app_a", "0001"), None)
82 graph.add_node(("app_a", "0002"), None)
83 graph.add_node(("app_a", "0003"), None)
84 graph.add_node(("app_a", "0004"), None)
85 graph.add_node(("app_b", "0001"), None)
86 graph.add_node(("app_b", "0002"), None)
87 graph.add_node(("app_c", "0001"), None)
88 graph.add_node(("app_c", "0002"), None)
89 graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_a", "0003"))
90 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
91 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
92 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))
93 graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
94 graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_c", "0002"))
95 graph.add_dependency("app_c.0002", ("app_c", "0002"), ("app_c", "0001"))
96 graph.add_dependency("app_c.0001", ("app_c", "0001"), ("app_b", "0001"))
97 graph.add_dependency("app_c.0002", ("app_c", "0002"), ("app_a", "0002"))
98 # Test branch C only
99 self.assertEqual(
100 graph.forwards_plan(("app_c", "0002")),
101 [
102 ("app_b", "0001"),
103 ("app_c", "0001"),
104 ("app_a", "0001"),
105 ("app_a", "0002"),
106 ("app_c", "0002"),
107 ],
108 )
109 # Test whole graph
110 self.assertEqual(
111 graph.forwards_plan(("app_a", "0004")),
112 [
113 ("app_b", "0001"),
114 ("app_c", "0001"),
115 ("app_a", "0001"),
116 ("app_a", "0002"),
117 ("app_c", "0002"),
118 ("app_b", "0002"),
119 ("app_a", "0003"),
120 ("app_a", "0004"),
121 ],
122 )
123 # Test reverse to b:0001
124 self.assertEqual(
125 graph.backwards_plan(("app_b", "0001")),
126 [
127 ("app_a", "0004"),
128 ("app_c", "0002"),
129 ("app_c", "0001"),
130 ("app_a", "0003"),
131 ("app_b", "0002"),
132 ("app_b", "0001"),
133 ],
134 )
135 # Test roots and leaves
136 self.assertEqual(
137 graph.root_nodes(),
138 [("app_a", "0001"), ("app_b", "0001"), ("app_c", "0001")],
139 )
140 self.assertEqual(
141 graph.leaf_nodes(),
142 [("app_a", "0004"), ("app_b", "0002"), ("app_c", "0002")],
143 )
144
145 def test_circular_graph(self):
146 """
147 Tests a circular dependency graph.
148 """
149 # Build graph
150 graph = MigrationGraph()
151 graph.add_node(("app_a", "0001"), None)
152 graph.add_node(("app_a", "0002"), None)
153 graph.add_node(("app_a", "0003"), None)
154 graph.add_node(("app_b", "0001"), None)
155 graph.add_node(("app_b", "0002"), None)
156 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
157 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
158 graph.add_dependency("app_a.0001", ("app_a", "0001"), ("app_b", "0002"))
159 graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
160 graph.add_dependency("app_b.0001", ("app_b", "0001"), ("app_a", "0003"))
161 # Test whole graph
162 with self.assertRaises(CircularDependencyError):
163 graph.ensure_not_cyclic()
164
165 def test_circular_graph_2(self):
166 graph = MigrationGraph()
167 graph.add_node(("A", "0001"), None)
168 graph.add_node(("C", "0001"), None)
169 graph.add_node(("B", "0001"), None)
170 graph.add_dependency("A.0001", ("A", "0001"), ("B", "0001"))
171 graph.add_dependency("B.0001", ("B", "0001"), ("A", "0001"))
172 graph.add_dependency("C.0001", ("C", "0001"), ("B", "0001"))
173
174 with self.assertRaises(CircularDependencyError):
175 graph.ensure_not_cyclic()
176
177 def test_iterative_dfs(self):
178 graph = MigrationGraph()
179 root = ("app_a", "1")
180 graph.add_node(root, None)
181 expected = [root]
182 for i in range(2, 750):
183 parent = ("app_a", str(i - 1))
184 child = ("app_a", str(i))
185 graph.add_node(child, None)
186 graph.add_dependency(str(i), child, parent)
187 expected.append(child)
188 leaf = expected[-1]
189
190 forwards_plan = graph.forwards_plan(leaf)
191 self.assertEqual(expected, forwards_plan)
192
193 backwards_plan = graph.backwards_plan(root)
194 self.assertEqual(expected[::-1], backwards_plan)
195
196 def test_iterative_dfs_complexity(self):
197 """
198 In a graph with merge migrations, iterative_dfs() traverses each node
199 only once even if there are multiple paths leading to it.
200 """
201 n = 50
202 graph = MigrationGraph()
203 for i in range(1, n + 1):
204 graph.add_node(("app_a", str(i)), None)
205 graph.add_node(("app_b", str(i)), None)
206 graph.add_node(("app_c", str(i)), None)
207 for i in range(1, n):
208 graph.add_dependency(None, ("app_b", str(i)), ("app_a", str(i)))
209 graph.add_dependency(None, ("app_c", str(i)), ("app_a", str(i)))
210 graph.add_dependency(None, ("app_a", str(i + 1)), ("app_b", str(i)))
211 graph.add_dependency(None, ("app_a", str(i + 1)), ("app_c", str(i)))
212 plan = graph.forwards_plan(("app_a", str(n)))
213 expected = [
214 (app, str(i)) for i in range(1, n) for app in ["app_a", "app_c", "app_b"]
215 ] + [("app_a", str(n))]
216 self.assertEqual(plan, expected)
217
218 def test_plan_invalid_node(self):
219 """
220 Tests for forwards/backwards_plan of nonexistent node.
221 """
222 graph = MigrationGraph()
223 message = "Node ('app_b', '0001') not a valid node"
224
225 with self.assertRaisesMessage(NodeNotFoundError, message):
226 graph.forwards_plan(("app_b", "0001"))
227
228 with self.assertRaisesMessage(NodeNotFoundError, message):
229 graph.backwards_plan(("app_b", "0001"))
230
231 def test_missing_parent_nodes(self):
232 """
233 Tests for missing parent nodes.
234 """
235 # Build graph
236 graph = MigrationGraph()
237 graph.add_node(("app_a", "0001"), None)
238 graph.add_node(("app_a", "0002"), None)
239 graph.add_node(("app_a", "0003"), None)
240 graph.add_node(("app_b", "0001"), None)
241 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
242 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
243 msg = (
244 "Migration app_a.0001 dependencies reference nonexistent parent node "
245 "('app_b', '0002')"
246 )
247 with self.assertRaisesMessage(NodeNotFoundError, msg):
248 graph.add_dependency("app_a.0001", ("app_a", "0001"), ("app_b", "0002"))
249
250 def test_missing_child_nodes(self):
251 """
252 Tests for missing child nodes.
253 """
254 # Build graph
255 graph = MigrationGraph()
256 graph.add_node(("app_a", "0001"), None)
257 msg = (
258 "Migration app_a.0002 dependencies reference nonexistent child node "
259 "('app_a', '0002')"
260 )
261 with self.assertRaisesMessage(NodeNotFoundError, msg):
262 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
263
264 def test_validate_consistency_missing_parent(self):
265 graph = MigrationGraph()
266 graph.add_node(("app_a", "0001"), None)
267 graph.add_dependency(
268 "app_a.0001", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
269 )
270 msg = (
271 "Migration app_a.0001 dependencies reference nonexistent parent node "
272 "('app_b', '0002')"
273 )
274 with self.assertRaisesMessage(NodeNotFoundError, msg):
275 graph.validate_consistency()
276
277 def test_validate_consistency_missing_child(self):
278 graph = MigrationGraph()
279 graph.add_node(("app_b", "0002"), None)
280 graph.add_dependency(
281 "app_b.0002", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
282 )
283 msg = (
284 "Migration app_b.0002 dependencies reference nonexistent child node "
285 "('app_a', '0001')"
286 )
287 with self.assertRaisesMessage(NodeNotFoundError, msg):
288 graph.validate_consistency()
289
290 def test_validate_consistency_no_error(self):
291 graph = MigrationGraph()
292 graph.add_node(("app_a", "0001"), None)
293 graph.add_node(("app_b", "0002"), None)
294 graph.add_dependency(
295 "app_a.0001", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
296 )
297 graph.validate_consistency()
298
299 def test_validate_consistency_dummy(self):
300 """
301 validate_consistency() raises an error if there's an isolated dummy
302 node.
303 """
304 msg = "app_a.0001 (req'd by app_b.0002) is missing!"
305 graph = MigrationGraph()
306 graph.add_dummy_node(
307 key=("app_a", "0001"), origin="app_b.0002", error_message=msg
308 )
309 with self.assertRaisesMessage(NodeNotFoundError, msg):
310 graph.validate_consistency()
311
312 def test_remove_replaced_nodes(self):
313 """
314 Replaced nodes are properly removed and dependencies remapped.
315 """
316 # Add some dummy nodes to be replaced.
317 graph = MigrationGraph()
318 graph.add_dummy_node(
319 key=("app_a", "0001"), origin="app_a.0002", error_message="BAD!"
320 )
321 graph.add_dummy_node(
322 key=("app_a", "0002"), origin="app_b.0001", error_message="BAD!"
323 )
324 graph.add_dependency(
325 "app_a.0002", ("app_a", "0002"), ("app_a", "0001"), skip_validation=True
326 )
327 # Add some normal parent and child nodes to test dependency remapping.
328 graph.add_node(("app_c", "0001"), None)
329 graph.add_node(("app_b", "0001"), None)
330 graph.add_dependency(
331 "app_a.0001", ("app_a", "0001"), ("app_c", "0001"), skip_validation=True
332 )
333 graph.add_dependency(
334 "app_b.0001", ("app_b", "0001"), ("app_a", "0002"), skip_validation=True
335 )
336 # Try replacing before replacement node exists.
337 msg = (
338 "Unable to find replacement node ('app_a', '0001_squashed_0002'). It was "
339 "either never added to the migration graph, or has been removed."
340 )
341 with self.assertRaisesMessage(NodeNotFoundError, msg):
342 graph.remove_replaced_nodes(
343 replacement=("app_a", "0001_squashed_0002"),
344 replaced=[("app_a", "0001"), ("app_a", "0002")],
345 )
346 graph.add_node(("app_a", "0001_squashed_0002"), None)
347 # Ensure `validate_consistency()` still raises an error at this stage.
348 with self.assertRaisesMessage(NodeNotFoundError, "BAD!"):
349 graph.validate_consistency()
350 # Remove the dummy nodes.
351 graph.remove_replaced_nodes(
352 replacement=("app_a", "0001_squashed_0002"),
353 replaced=[("app_a", "0001"), ("app_a", "0002")],
354 )
355 # Ensure graph is now consistent and dependencies have been remapped
356 graph.validate_consistency()
357 parent_node = graph.node_map[("app_c", "0001")]
358 replacement_node = graph.node_map[("app_a", "0001_squashed_0002")]
359 child_node = graph.node_map[("app_b", "0001")]
360 self.assertIn(parent_node, replacement_node.parents)
361 self.assertIn(replacement_node, parent_node.children)
362 self.assertIn(child_node, replacement_node.children)
363 self.assertIn(replacement_node, child_node.parents)
364
365 def test_remove_replacement_node(self):
366 """
367 A replacement node is properly removed and child dependencies remapped.
368 We assume parent dependencies are already correct.
369 """
370 # Add some dummy nodes to be replaced.
371 graph = MigrationGraph()
372 graph.add_node(("app_a", "0001"), None)
373 graph.add_node(("app_a", "0002"), None)
374 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
375 # Try removing replacement node before replacement node exists.
376 msg = (
377 "Unable to remove replacement node ('app_a', '0001_squashed_0002'). It was"
378 " either never added to the migration graph, or has been removed already."
379 )
380 with self.assertRaisesMessage(NodeNotFoundError, msg):
381 graph.remove_replacement_node(
382 replacement=("app_a", "0001_squashed_0002"),
383 replaced=[("app_a", "0001"), ("app_a", "0002")],
384 )
385 graph.add_node(("app_a", "0001_squashed_0002"), None)
386 # Add a child node to test dependency remapping.
387 graph.add_node(("app_b", "0001"), None)
388 graph.add_dependency(
389 "app_b.0001", ("app_b", "0001"), ("app_a", "0001_squashed_0002")
390 )
391 # Remove the replacement node.
392 graph.remove_replacement_node(
393 replacement=("app_a", "0001_squashed_0002"),
394 replaced=[("app_a", "0001"), ("app_a", "0002")],
395 )
396 # Ensure graph is consistent and child dependency has been remapped
397 graph.validate_consistency()
398 replaced_node = graph.node_map[("app_a", "0002")]
399 child_node = graph.node_map[("app_b", "0001")]
400 self.assertIn(child_node, replaced_node.children)
401 self.assertIn(replaced_node, child_node.parents)
402 # Child dependency hasn't also gotten remapped to the other replaced
403 # node.
404 other_replaced_node = graph.node_map[("app_a", "0001")]
405 self.assertNotIn(child_node, other_replaced_node.children)
406 self.assertNotIn(other_replaced_node, child_node.parents)
407
408 def test_infinite_loop(self):
409 """
410 Tests a complex dependency graph:
411
412 app_a: 0001 <-
413 \
414 app_b: 0001 <- x 0002 <-
415 / \
416 app_c: 0001<- <------------- x 0002
417
418 And apply squashing on app_c.
419 """
420 graph = MigrationGraph()
421
422 graph.add_node(("app_a", "0001"), None)
423 graph.add_node(("app_b", "0001"), None)
424 graph.add_node(("app_b", "0002"), None)
425 graph.add_node(("app_c", "0001_squashed_0002"), None)
426
427 graph.add_dependency(
428 "app_b.0001", ("app_b", "0001"), ("app_c", "0001_squashed_0002")
429 )
430 graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_a", "0001"))
431 graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
432 graph.add_dependency(
433 "app_c.0001_squashed_0002",
434 ("app_c", "0001_squashed_0002"),
435 ("app_b", "0002"),
436 )
437
438 with self.assertRaises(CircularDependencyError):
439 graph.ensure_not_cyclic()
440
441 def test_stringify(self):
442 graph = MigrationGraph()
443 self.assertEqual(str(graph), "Graph: 0 nodes, 0 edges")
444
445 graph.add_node(("app_a", "0001"), None)
446 graph.add_node(("app_a", "0002"), None)
447 graph.add_node(("app_a", "0003"), None)
448 graph.add_node(("app_b", "0001"), None)
449 graph.add_node(("app_b", "0002"), None)
450 graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
451 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
452 graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))
453
454 self.assertEqual(str(graph), "Graph: 5 nodes, 3 edges")
455 self.assertEqual(repr(graph), "<MigrationGraph: nodes=5, edges=3>")
456
457
458 class NodeTests(SimpleTestCase):
459 def test_node_repr(self):
460 node = Node(("app_a", "0001"))
461 self.assertEqual(repr(node), "<Node: ('app_a', '0001')>")
462
463 def test_node_str(self):
464 node = Node(("app_a", "0001"))
465 self.assertEqual(str(node), "('app_a', '0001')")
466
467 def test_dummynode_repr(self):
468 node = DummyNode(
469 key=("app_a", "0001"),
470 origin="app_a.0001",
471 error_message="x is missing",
472 )
473 self.assertEqual(repr(node), "<DummyNode: ('app_a', '0001')>")