12.9 The migration graph: MigrationGraph
The migration graph, a MigrationGraph, has a node for each migration the loader keeps and an edge for each dependency the loader gives it, and it is what orders migrations. MigrationGraph and MigrationGraph walk it for an order in which migrations can be applied and unapplied, MigrationGraph and MigrationGraph find where an application’s history begins and ends, and MigrationGraph builds the project state at a node.
Migrations have to be applied in an order, and the numbers in their files’ names do not give it: the numbering is a convention that helps in listing the files, and makes no migration depend on another. What gives the order is each migration’s dependencies, which name the migrations that must be applied before it, and its Migration, which names those to be applied after it, a dependency declared from the other end.
The graph is those declarations as a structure that can be asked. The loader makes it, in MigrationLoader (Finding migrations: MigrationLoader), and nothing in Django changes it once that has returned. The executor makes its plans from it, and the autodetector asks it where an application’s history ends. A graph holds no connection, and none of its methods asks which migrations are applied.
Two dictionaries by key: nodes and node_map
A MigrationGraph is two dictionaries with the same keys, a key being the pair of an application’s label and a migration’s name. MigrationGraph maps a key to its migration, which is how a key becomes the migration to run. MigrationGraph maps a key to a node, a Node, which holds the edges: Node.parents is the set of the nodes this one depends on, its parents, and Node.children the set of those that depend on it, so that an edge can be followed from either end. A Node compares, hashes and sorts as its key.
MigrationGraph enters a key in both dictionaries, and MigrationGraph, given a child’s key and a parent’s key, puts each of the two nodes in the other’s set. Here is the loader’s graph of harbour, the chapter’s example project of four applications (Migrations), after its first makemigrations. The recordings are of a running Django: a line of Python is as it was run; a line that names a method by its declaring class is a call, set in under what made it, with the migration it was called on in square brackets; -> is followed by a value or by the exception raised; only the lines a passage is about are written, and what ran between them is left out.
str(graph) -> 'Graph: 5 nodes, 7 edges'
...
graph.nodes['yard', '0001_initial'] -> yard.0001_initial
graph.node_map['yard', '0001_initial'] -> the node ('yard', '0001_initial')
...
sorted(node.key for node in graph.node_map['fleet', '0001_initial'].parents) -> [('crew', '0001_initial')]
sorted(node.key for node in graph.node_map['fleet', '0001_initial'].children) -> [('crew', '0002_initial'), ('office', '0001_initial'), ('yard', '0001_initial')]
Plans: forwards_plan and backwards_plan
MigrationGraph answers what must be applied before a migration can be: it takes a key and returns the keys of everything the migration depends on, directly or through others, each after everything it depends on, ending with the key given. MigrationGraph answers what must be unapplied before a migration can be: the keys of everything that depends on it, directly or through others, each after its own dependents, ending again with the key given. Both call MigrationGraph, which follows Node.parents for the first and, with forwards=False, Node.children for the second.
graph.forwards_plan(('crew', '0002_initial')) -> [('crew', '0001_initial'), ('fleet', '0001_initial'), ('office', '0001_initial'), ('crew', '0002_initial')]
...
graph.backwards_plan(('fleet', '0001_initial')) -> [('yard', '0001_initial'), ('crew', '0002_initial'), ('office', '0001_initial'), ('fleet', '0001_initial')]
iterative_dfs is a depth-first walk that lists a node on the way back from it. It keeps a stack of its own: a node taken off the stack for the first time is put back with a mark and its parents (for a backwards plan, its children) are put on top of it, and when the marked node comes off again everything that has to come before it has been listed, and it is listed. A set of the nodes already listed keeps a node reached by several paths from being listed twice. The method loops and does not call itself, so a long chain of dependencies makes a long list and not a deep call stack.
What orders such a list, then, is the edges and, where they leave a choice, the keys. The set the walk follows has no order; the walk sorts it, puts its nodes on the stack in the order of their keys and takes them off in the reverse, and so goes first into the one whose key sorts last. That is how yard’s migration comes first in the backwards plan for fleet’s: of fleet’s three children it sorts last. So the same nodes and edges give the same plan.
MigrationExecutor makes the executor’s plan from these lists and the migrations it counts as applied: of a forwards plan it keeps the migrations not among them, of a backwards plan those that are (Applying a plan: MigrationExecutor).
Root nodes and leaf nodes
MigrationGraph and MigrationGraph say where an application’s history begins and ends, and look at edges within the application only: a root node has no parent in its own application, a leaf node no child in its own. Each returns a sorted list of keys, for every application or, given a label, for one.
graph.root_nodes() -> [('crew', '0001_initial'), ('fleet', '0001_initial'), ('office', '0001_initial'), ('yard', '0001_initial')]
graph.leaf_nodes() -> [('crew', '0002_initial'), ('fleet', '0001_initial'), ('office', '0001_initial'), ('yard', '0001_initial')]
Fleet’s one migration is fleet’s root and its leaf, though it has a parent in crew and children in three applications. A dependency may have "__first__" or "__latest__" in place of a migration’s name; where the loader makes a key of one, the key is the first of the root nodes, or of the leaf nodes, of the application it names (MigrationLoader; Finding migrations: MigrationLoader). The leaf nodes, each the most current version of its application’s schema, are migrate’s targets when it is given no migration’s name (The migrate command, showmigrations and sqlmigrate), and the autodetector has an application’s first new migration depend on its first leaf node (From operations to migrations: dependencies, order and names).
More than one leaf node in an application is an error, usually the result of a merge in version control, and the graph accepts it. Later in yard’s history a migration from a colleague’s branch stands beside one that makemigrations wrote, both depending on the same migration of yard:
loader.graph.leaf_nodes('yard') -> [('yard', '0006_dock_covered'), ('yard', '0006_long_dock')]
MigrationLoader reports such an application, and makemigrations --merge writes a migration that depends on both leaves (The makemigrations command).
The project state at a node: make_state
MigrationGraph builds the project state as it stands once a node’s migration has run: it makes a ProjectState with no model states (Project state: ProjectState and its model states) and calls Migration of each migration of the node’s forwards plan on it, in order, with preserve=False, which changes that one state in place. Only the operations’ state halves run, and no database is touched. Given several keys, or none and so every leaf node, make_state has MigrationGraph join their forwards plans into one list with no key twice. With at_end=False the key given is left out of the list, and the state is the one before its migration:
before = graph.make_state(('yard', '0001_initial'), at_end=False)
MigrationGraph.make_state(nodes=('yard', '0001_initial'), at_end=False)
MigrationGraph._generate_plan(nodes=[('yard', '0001_initial')], at_end=False) -> [('crew', '0001_initial'), ('fleet', '0001_initial')]
Migration.mutate_state(preserve=False) [crew.0001_initial]
Migration.mutate_state(preserve=False) [fleet.0001_initial]
-> a ProjectState of 5 model states, its registry not rendered
The state before a migration is what sqlmigrate starts from (The migrate command, showmigrations and sqlmigrate). make_state gives the new state the labels it is passed as ProjectState, the applications whose models are to come from the main registry when the state is rendered; its one caller in Django, MigrationLoader, passes the unmigrated applications, those with no package of migrations. For a graph with no nodes make_state returns a ProjectState made without them.
A dependency on a migration that is not there
MigrationGraph, given a key that is no node, first makes a DummyNode for it and links it like any other: a node whose migration in MigrationGraph is None, carrying the message of the error it stands for and the migration that named it, which is what add_dependency is passed a migration for. MigrationGraph raises that error for a dummy node still in the graph: a NodeNotFoundError, a LookupError whose NodeNotFoundError is the missing key and NodeNotFoundError the migration. add_dependency calls it once it has linked the two nodes, unless it is passed skip_validation=True. Here small is a graph of the recording’s own with one node, and yard_first is that node’s migration, yard.0001_initial:
small.add_dependency(yard_first, ('yard', '0001_initial'), ('fleet', '0009_missing'), skip_validation=True)
small.node_map['fleet', '0009_missing'] -> the DummyNode ('fleet', '0009_missing')
small.nodes['fleet', '0009_missing'] -> None
small.validate_consistency() -> raises NodeNotFoundError: Migration yard.0001_initial dependencies reference nonexistent parent node ('fleet', '0009_missing')
The loader passes skip_validation=True with every edge and makes the check once, after the last of them (MigrationLoader; Finding migrations: MigrationLoader). By then a dummy node may be gone. A migration that replaces others (a squashed one) may stand in the graph in their place, and where one of them is a dummy node, having no file, the loader then takes that node out and gives its place in the dependency to the replacing migration: a migration can go on naming a replaced migration whose file is deleted. Squashed migrations: replaces and the squashmigrations command has that.
A cycle: ensure_not_cyclic
Dependencies that lead back to where they began can be given no order, and the walks assume there are none: MigrationGraph counts a node as seen only once it has listed it, and in a cycle each node waits for another, so a walk that came to one would not end. MigrationGraph looks for one, and is the last thing MigrationLoader does (Finding migrations: MigrationLoader), so a missing dependency is reported before a cycle. It follows children from each node it has not yet visited, keeping the path it is on, and when a child is already on the path it raises CircularDependencyError. The message is the cycle: the migrations from that child to the end of the path, each depending on the one before it.