← Back to branch summary

~ubuntu-branches/debian/sid/python-django/sid

« back to all changes in this revision

Viewing changes to django/db/migrations/graph.py

  • Committer: Package Import Robot
  • Author(s): Raphaël Hertzog
  • Date: 2014-09-17 14:15:11 UTC
  • mfrom: (1.3.17) (6.2.18 experimental)
  • Revision ID: package-import@ubuntu.com-20140917141511-icneokthe9ww5sk4
Tags: 1.7-2
* Release to unstable.
* Add a migrate-south sample script to help users apply their South
  migrations. Thanks to Brian May.

Show diffs side-by-side

added added

removed removed

Lines of Context:
django/db/migrations/graph.py
 
1
from __future__ import unicode_literals
 
2
 
 
3
from django.utils.datastructures import OrderedSet
 
4
from django.db.migrations.state import ProjectState
 
5
 
 
6
 
 
7
class MigrationGraph(object):
 
8
    """
 
9
    Represents the digraph of all migrations in a project.
 
10
 
 
11
    Each migration is a node, and each dependency is an edge. There are
 
12
    no implicit dependencies between numbered migrations - the numbering is
 
13
    merely a convention to aid file listing. Every new numbered migration
 
14
    has a declared dependency to the previous number, meaning that VCS
 
15
    branch merges can be detected and resolved.
 
16
 
 
17
    Migrations files can be marked as replacing another set of migrations -
 
18
    this is to support the "squash" feature. The graph handler isn't responsible
 
19
    for these; instead, the code to load them in here should examine the
 
20
    migration files and if the replaced migrations are all either unapplied
 
21
    or not present, it should ignore the replaced ones, load in just the
 
22
    replacing migration, and repoint any dependencies that pointed to the
 
23
    replaced migrations to point to the replacing one.
 
24
 
 
25
    A node should be a tuple: (app_path, migration_name). The tree special-cases
 
26
    things within an app - namely, root nodes and leaf nodes ignore dependencies
 
27
    to other apps.
 
28
    """
 
29
 
 
30
    def __init__(self):
 
31
        self.nodes = {}
 
32
        self.dependencies = {}
 
33
        self.dependents = {}
 
34
 
 
35
    def add_node(self, node, implementation):
 
36
        self.nodes[node] = implementation
 
37
 
 
38
    def add_dependency(self, migration, child, parent):
 
39
        if child not in self.nodes:
 
40
            raise KeyError("Migration %s dependencies references nonexistent child node %r" % (migration, child))
 
41
        if parent not in self.nodes:
 
42
            raise KeyError("Migration %s dependencies references nonexistent parent node %r" % (migration, parent))
 
43
        self.dependencies.setdefault(child, set()).add(parent)
 
44
        self.dependents.setdefault(parent, set()).add(child)
 
45
 
 
46
    def forwards_plan(self, node):
 
47
        """
 
48
        Given a node, returns a list of which previous nodes (dependencies)
 
49
        must be applied, ending with the node itself.
 
50
        This is the list you would follow if applying the migrations to
 
51
        a database.
 
52
        """
 
53
        if node not in self.nodes:
 
54
            raise ValueError("Node %r not a valid node" % (node, ))
 
55
        return self.dfs(node, lambda x: self.dependencies.get(x, set()))
 
56
 
 
57
    def backwards_plan(self, node):
 
58
        """
 
59
        Given a node, returns a list of which dependent nodes (dependencies)
 
60
        must be unapplied, ending with the node itself.
 
61
        This is the list you would follow if removing the migrations from
 
62
        a database.
 
63
        """
 
64
        if node not in self.nodes:
 
65
            raise ValueError("Node %r not a valid node" % (node, ))
 
66
        return self.dfs(node, lambda x: self.dependents.get(x, set()))
 
67
 
 
68
    def root_nodes(self, app=None):
 
69
        """
 
70
        Returns all root nodes - that is, nodes with no dependencies inside
 
71
        their app. These are the starting point for an app.
 
72
        """
 
73
        roots = set()
 
74
        for node in self.nodes:
 
75
            if not any(key[0] == node[0] for key in self.dependencies.get(node, set())) and (not app or app == node[0]):
 
76
                roots.add(node)
 
77
        return sorted(roots)
 
78
 
 
79
    def leaf_nodes(self, app=None):
 
80
        """
 
81
        Returns all leaf nodes - that is, nodes with no dependents in their app.
 
82
        These are the "most current" version of an app's schema.
 
83
        Having more than one per app is technically an error, but one that
 
84
        gets handled further up, in the interactive command - it's usually the
 
85
        result of a VCS merge and needs some user input.
 
86
        """
 
87
        leaves = set()
 
88
        for node in self.nodes:
 
89
            if not any(key[0] == node[0] for key in self.dependents.get(node, set())) and (not app or app == node[0]):
 
90
                leaves.add(node)
 
91
        return sorted(leaves)
 
92
 
 
93
    def dfs(self, start, get_children):
 
94
        """
 
95
        Dynamic programming based depth first search, for finding dependencies.
 
96
        """
 
97
        cache = {}
 
98
 
 
99
        def _dfs(start, get_children, path):
 
100
            # If we already computed this, use that (dynamic programming)
 
101
            if (start, get_children) in cache:
 
102
                return cache[(start, get_children)]
 
103
            # If we've traversed here before, that's a circular dep
 
104
            if start in path:
 
105
                raise CircularDependencyError(path[path.index(start):] + [start])
 
106
            # Build our own results list, starting with us
 
107
            results = []
 
108
            results.append(start)
 
109
            # We need to add to results all the migrations this one depends on
 
110
            children = sorted(get_children(start))
 
111
            path.append(start)
 
112
            for n in children:
 
113
                results = _dfs(n, get_children, path) + results
 
114
            path.pop()
 
115
            # Use OrderedSet to ensure only one instance of each result
 
116
            results = list(OrderedSet(results))
 
117
            # Populate DP cache
 
118
            cache[(start, get_children)] = results
 
119
            # Done!
 
120
            return results
 
121
        return _dfs(start, get_children, [])
 
122
 
 
123
    def __str__(self):
 
124
        return "Graph: %s nodes, %s edges" % (len(self.nodes), sum(len(x) for x in self.dependencies.values()))
 
125
 
 
126
    def make_state(self, nodes=None, at_end=True, real_apps=None):
 
127
        """
 
128
        Given a migration node or nodes, returns a complete ProjectState for it.
 
129
        If at_end is False, returns the state before the migration has run.
 
130
        If nodes is not provided, returns the overall most current project state.
 
131
        """
 
132
        if nodes is None:
 
133
            nodes = list(self.leaf_nodes())
 
134
        if len(nodes) == 0:
 
135
            return ProjectState()
 
136
        if not isinstance(nodes[0], tuple):
 
137
            nodes = [nodes]
 
138
        plan = []
 
139
        for node in nodes:
 
140
            for migration in self.forwards_plan(node):
 
141
                if migration not in plan:
 
142
                    if not at_end and migration in nodes:
 
143
                        continue
 
144
                    plan.append(migration)
 
145
        project_state = ProjectState(real_apps=real_apps)
 
146
        for node in plan:
 
147
            project_state = self.nodes[node].mutate_state(project_state)
 
148
        return project_state
 
149
 
 
150
    def __contains__(self, node):
 
151
        return node in self.nodes
 
152
 
 
153
 
 
154
class CircularDependencyError(Exception):
 
155
    """
 
156
    Raised when there's an impossible-to-resolve circular dependency.
 
157
    """
 
158
    pass