~bzr-pqm/bzr/bzr.dev

3246.2.2 by Martin Pool
Fix up import of tsort
1
# Copyright (C) 2005, 2008 Canonical Ltd
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
2
#
974.1.68 by Aaron Bentley
Added GPL notice
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
7
#
974.1.68 by Aaron Bentley
Added GPL notice
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
# GNU General Public License for more details.
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
12
#
974.1.68 by Aaron Bentley
Added GPL notice
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
4183.7.1 by Sabin Iacob
update FSF mailing address
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
974.1.68 by Aaron Bentley
Added GPL notice
16
1594.2.15 by Robert Collins
Unfuck performance.
17
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
18
def max_distance(node, ancestors, distances, root_descendants):
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
19
    """Calculate the max distance to an ancestor.
974.1.66 by Aaron Bentley
more cleanups, docs, sorting stuff
20
    Return None if not all possible ancestors have known distances"""
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
21
    best = None
22
    if node in distances:
23
        best = distances[node]
24
    for ancestor in ancestors[node]:
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
25
        # skip ancestors we will never traverse:
26
        if root_descendants is not None and ancestor not in root_descendants:
27
            continue
974.1.66 by Aaron Bentley
more cleanups, docs, sorting stuff
28
        # An ancestor which is not listed in ancestors will never be in
29
        # distances, so we pretend it never existed.
974.1.64 by Aaron Bentley
Handled ancestors that are missing when finding a base
30
        if ancestor not in ancestors:
31
            continue
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
32
        if ancestor not in distances:
33
            return None
1185.8.3 by Aaron Bentley
Fixed bug in distance-from-root graph operation
34
        if best is None or distances[ancestor]+1 > best:
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
35
            best = distances[ancestor] + 1
36
    return best
37
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
38
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
39
def node_distances(graph, ancestors, start, root_descendants=None):
974.1.66 by Aaron Bentley
more cleanups, docs, sorting stuff
40
    """Produce a list of nodes, sorted by distance from a start node.
41
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
42
    backwards seemed too complicated.
43
44
    For each node, we walk its descendants.  If all the descendant's ancestors
45
    have a max-distance-to-start, (excluding ones that can never reach start),
46
    we calculate their max-distance-to-start, and schedule their descendants.
47
48
    So when a node's last parent acquires a distance, it will acquire a
49
    distance on the next iteration.
50
51
    Once we know the max distances for all nodes, we can return a list sorted
52
    by distance, farthest first.
53
    """
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
54
    distances = {start: 0}
974.1.60 by aaron.bentley at utoronto
Initial import of common-ancestor detection
55
    lines = set([start])
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
56
    while len(lines) > 0:
57
        new_lines = set()
58
        for line in lines:
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
59
            line_descendants = graph[line]
60
            for descendant in line_descendants:
61
                distance = max_distance(descendant, ancestors, distances,
62
                                        root_descendants)
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
63
                if distance is None:
64
                    continue
65
                distances[descendant] = distance
66
                new_lines.add(descendant)
67
        lines = new_lines
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
68
    return distances
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
69
974.1.87 by Aaron Bentley
Refactored and documented graph stuff
70
def nodes_by_distance(distances):
71
    """Return a list of nodes sorted by distance"""
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
72
    def by_distance(n):
974.1.66 by Aaron Bentley
more cleanups, docs, sorting stuff
73
        return distances[n],n
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
74
974.1.59 by aaron.bentley at utoronto
Created yet another longest-patch-picker
75
    node_list = distances.keys()
76
    node_list.sort(key=by_distance, reverse=True)
77
    return node_list
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
78
974.1.87 by Aaron Bentley
Refactored and documented graph stuff
79
def select_farthest(distances, common):
80
    """Return the farthest common node, or None if no node qualifies."""
81
    node_list = nodes_by_distance(distances)
82
    for node in node_list:
83
        if node in common:
84
            return node
85
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
86
def all_descendants(descendants, start):
974.1.87 by Aaron Bentley
Refactored and documented graph stuff
87
    """Produce a set of all descendants of the start node.
88
    The input is a map of node->list of descendants for a graph encompassing
89
    start.
90
    """
974.1.72 by Aaron Bentley
added all_descendants and node_distances, exception when root doesn't exist
91
    result = set()
92
    lines = set([start])
93
    while len(lines) > 0:
94
        new_lines = set()
95
        for line in lines:
96
            if line not in descendants:
97
                continue
98
            for descendant in descendants[line]:
99
                if descendant in result:
100
                    continue
101
                result.add(descendant)
102
                new_lines.add(descendant)
103
        lines = new_lines
104
    return result
1594.2.3 by Robert Collins
bugfix revision.MultipleRevisionSources.get_revision_graph to integrate ghosts between sources. [slow on weaves, fast on knits.
105
106
107
class Graph(object):
1759.2.2 by Jelmer Vernooij
Revert some of my spelling fixes and fix some typos after review by Aaron.
108
    """A graph object which can memoise and cache results for performance."""
1594.2.3 by Robert Collins
bugfix revision.MultipleRevisionSources.get_revision_graph to integrate ghosts between sources. [slow on weaves, fast on knits.
109
110
    def __init__(self):
111
        super(Graph, self).__init__()
112
        self.roots = set([])
113
        self.ghosts = set([])
114
        self._graph_ancestors = {}
115
        self._graph_descendants = {}
116
117
    def add_ghost(self, node_id):
118
        """Add a ghost to the graph."""
119
        self.ghosts.add(node_id)
120
        self._ensure_descendant(node_id)
121
122
    def add_node(self, node_id, parent_ids):
123
        """Add node_id to the graph with parent_ids as its parents."""
2592.3.31 by Robert Collins
All GraphKnit based repository tests passing.
124
        if len(parent_ids) == 0:
1594.2.3 by Robert Collins
bugfix revision.MultipleRevisionSources.get_revision_graph to integrate ghosts between sources. [slow on weaves, fast on knits.
125
            self.roots.add(node_id)
126
        self._graph_ancestors[node_id] = list(parent_ids)
127
        self._ensure_descendant(node_id)
128
        for parent in parent_ids:
129
            self._ensure_descendant(parent)
130
            self._graph_descendants[parent][node_id] = 1
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
131
1594.2.3 by Robert Collins
bugfix revision.MultipleRevisionSources.get_revision_graph to integrate ghosts between sources. [slow on weaves, fast on knits.
132
    def _ensure_descendant(self, node_id):
133
        """Ensure that a descendant lookup for node_id will work."""
134
        if not node_id in self._graph_descendants:
135
            self._graph_descendants[node_id] = {}
136
137
    def get_ancestors(self):
138
        """Return a dictionary of graph node:ancestor_list entries."""
139
        return dict(self._graph_ancestors.items())
140
2530.1.1 by Aaron Bentley
Make topological sorting optional for get_ancestry
141
    def get_ancestry(self, node_id, topo_sorted=True):
1594.2.15 by Robert Collins
Unfuck performance.
142
        """Return the inclusive ancestors of node_id in topological order."""
143
        # maybe optimise this ?
3246.2.2 by Martin Pool
Fix up import of tsort
144
        from bzrlib.tsort import topo_sort
1594.2.15 by Robert Collins
Unfuck performance.
145
        result = {}
146
        pending = set([node_id])
147
        while len(pending):
148
            current = pending.pop()
149
            parents = self._graph_ancestors[current]
150
            parents = [parent for parent in parents if parent not in self.ghosts]
151
            result[current] = parents
152
            for parent in parents:
153
                if parent not in result and parent not in pending:
154
                    pending.add(parent)
2530.1.1 by Aaron Bentley
Make topological sorting optional for get_ancestry
155
        if not topo_sorted:
156
            return result.keys()
1594.2.15 by Robert Collins
Unfuck performance.
157
        return topo_sort(result.items())
158
1594.2.3 by Robert Collins
bugfix revision.MultipleRevisionSources.get_revision_graph to integrate ghosts between sources. [slow on weaves, fast on knits.
159
    def get_descendants(self):
160
        """Return a dictionary of graph node:child_node:distance entries."""
161
        return dict(self._graph_descendants.items())