← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2011-09-25 01:56:48 UTC
  • mto: This revision was merged to the branch mainline in revision 779.
  • Revision ID: aaron@aaronbentley.com-20110925015648-41tbr3wonksf7efh
Add get_rev_info test.

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
1
 
# Copyright (C) 2005 Aaron Bentley
2
 
# <aaron.bentley@utoronto.ca>
 
1
# Copyright (C) 2005, 2008 Aaron Bentley
 
2
# <aaron@aaronbentley.com>
3
3
#
4
4
#    This program is free software; you can redistribute it and/or modify
5
5
#    it under the terms of the GNU General Public License as published by
14
14
#    You should have received a copy of the GNU General Public License
15
15
#    along with this program; if not, write to the Free Software
16
16
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
17
 
 
18
 
 
19
import time
 
20
 
 
21
from bzrlib.branch import Branch
 
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
 
23
from bzrlib.revision import NULL_REVISION
 
24
 
17
25
from bzrtools import short_committer
18
 
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
19
 
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
20
 
from bzrlib.branch import Branch
21
 
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
22
 
from bzrlib.graph import node_distances, select_farthest
23
 
from bzrlib.revision import combined_graph, revision_graph
24
 
from bzrlib.revision import MultipleRevisionSources
25
 
import bzrlib.errors
26
 
import re
27
 
import os.path
28
 
import time
 
26
from dotgraph import (
 
27
    dot_output,
 
28
    DOT_OUTPUT_TYPES,
 
29
    Edge,
 
30
    invoke_dot,
 
31
    invoke_dot_aa,
 
32
    invoke_dot_html,
 
33
    Node,
 
34
    NoDot,
 
35
    NoRsvg,
 
36
    RSVG_OUTPUT_TYPES,
 
37
    )
 
38
 
 
39
 
 
40
def max_distance(node, ancestors, distances, root_descendants):
 
41
    """Calculate the max distance to an ancestor.
 
42
    Return None if not all possible ancestors have known distances"""
 
43
    best = None
 
44
    if node in distances:
 
45
        best = distances[node]
 
46
    for ancestor in ancestors[node]:
 
47
        # skip ancestors we will never traverse:
 
48
        if root_descendants is not None and ancestor not in root_descendants:
 
49
            continue
 
50
        # An ancestor which is not listed in ancestors will never be in
 
51
        # distances, so we pretend it never existed.
 
52
        if ancestor not in ancestors:
 
53
            continue
 
54
        if ancestor not in distances:
 
55
            return None
 
56
        if best is None or distances[ancestor]+1 > best:
 
57
            best = distances[ancestor] + 1
 
58
    return best
 
59
 
 
60
 
 
61
def node_distances(graph, ancestors, start, root_descendants=None):
 
62
    """Produce a list of nodes, sorted by distance from a start node.
 
63
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
 
64
    backwards seemed too complicated.
 
65
 
 
66
    For each node, we walk its descendants.  If all the descendant's ancestors
 
67
    have a max-distance-to-start, (excluding ones that can never reach start),
 
68
    we calculate their max-distance-to-start, and schedule their descendants.
 
69
 
 
70
    So when a node's last parent acquires a distance, it will acquire a
 
71
    distance on the next iteration.
 
72
 
 
73
    Once we know the max distances for all nodes, we can return a list sorted
 
74
    by distance, farthest first.
 
75
    """
 
76
    distances = {start: 0}
 
77
    lines = set([start])
 
78
    while len(lines) > 0:
 
79
        new_lines = set()
 
80
        for line in lines:
 
81
            line_descendants = graph[line]
 
82
            for descendant in line_descendants:
 
83
                distance = max_distance(descendant, ancestors, distances,
 
84
                                        root_descendants)
 
85
                if distance is None:
 
86
                    continue
 
87
                distances[descendant] = distance
 
88
                new_lines.add(descendant)
 
89
        lines = new_lines
 
90
    return distances
 
91
 
 
92
 
 
93
def nodes_by_distance(distances):
 
94
    """Return a list of nodes sorted by distance"""
 
95
    def by_distance(n):
 
96
        return distances[n],n
 
97
 
 
98
    node_list = distances.keys()
 
99
    node_list.sort(key=by_distance, reverse=True)
 
100
    return node_list
 
101
 
 
102
 
 
103
def select_farthest(distances, common):
 
104
    """Return the farthest common node, or None if no node qualifies."""
 
105
    node_list = nodes_by_distance(distances)
 
106
    for node in node_list:
 
107
        if node in common:
 
108
            return node
 
109
 
29
110
 
30
111
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
31
112
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
56
137
    for me, my_parents in ancestors.iteritems():
57
138
        if me in skip:
58
139
            continue
59
 
        new_ancestors[me] = {} 
 
140
        new_ancestors[me] = {}
60
141
        for parent in my_parents:
61
 
            new_parent = parent 
 
142
            new_parent = parent
62
143
            distance = 0
63
144
            while can_skip(new_parent, descendants, ancestors):
64
145
                if new_parent in exceptions:
69
150
                new_parent = list(ancestors[new_parent])[0]
70
151
                distance += 1
71
152
            new_ancestors[me][new_parent] = distance
72
 
    return new_ancestors    
 
153
    return new_ancestors
73
154
 
74
155
def get_rev_info(rev_id, source):
75
 
    """Return the committer, message, and date of a revision."""
 
156
    """Return the committer, message, nick and date of a revision."""
76
157
    committer = None
77
158
    message = None
78
159
    date = None
 
160
    nick = None
79
161
    if rev_id == 'null:':
80
162
        return None, 'Null Revision', None, None
81
163
    try:
106
188
    return committer, message, nick, date
107
189
 
108
190
class Grapher(object):
 
191
 
109
192
    def __init__(self, branch, other_branch=None):
110
193
        object.__init__(self)
111
194
        self.branch = branch
112
195
        self.other_branch = other_branch
 
196
        if other_branch is not None:
 
197
            other_repo = other_branch.repository
 
198
            revision_b = self.other_branch.last_revision()
 
199
        else:
 
200
            other_repo = None
 
201
            revision_b = None
 
202
        self.graph = self.branch.repository.get_graph(other_repo)
113
203
        revision_a = self.branch.last_revision()
114
 
        if other_branch is not None:
115
 
            branch.fetch(other_branch)
116
 
            revision_b = self.other_branch.last_revision()
117
 
            try:
118
 
                self.root, self.ancestors, self.descendants, self.common = \
119
 
                    combined_graph(revision_a, revision_b,
120
 
                                   self.branch.repository)
121
 
            except bzrlib.errors.NoCommonRoot:
122
 
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
123
 
        else:
124
 
            self.root, self.ancestors, self.descendants = \
125
 
                revision_graph(revision_a, branch.repository)
126
 
            self.common = []
127
 
 
 
204
        self.scan_graph(revision_a, revision_b)
128
205
        self.n_history = branch.revision_history()
129
 
        self.distances = node_distances(self.descendants, self.ancestors, 
 
206
        self.n_revnos = branch.get_revision_id_to_revno_map()
 
207
        self.distances = node_distances(self.descendants, self.ancestors,
130
208
                                        self.root)
131
209
        if other_branch is not None:
132
210
            self.base = select_farthest(self.distances, self.common)
133
 
            self.m_history = other_branch.revision_history() 
 
211
            self.m_history = other_branch.revision_history()
 
212
            self.m_revnos = other_branch.get_revision_id_to_revno_map()
 
213
            self.new_base = self.graph.find_unique_lca(revision_a,
 
214
                                                       revision_b)
 
215
            self.lcas = self.graph.find_lca(revision_a, revision_b)
134
216
        else:
135
217
            self.base = None
 
218
            self.new_base = None
 
219
            self.lcas = set()
136
220
            self.m_history = []
 
221
            self.m_revnos = {}
 
222
 
 
223
    def scan_graph(self, revision_a, revision_b):
 
224
        a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
 
225
        self.ancestors = a_ancestors
 
226
        self.root = NULL_REVISION
 
227
        if revision_b is not None:
 
228
            b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
 
229
            self.common = set(a_ancestors.keys())
 
230
            self.common.intersection_update(b_ancestors)
 
231
            self.ancestors.update(b_ancestors)
 
232
        else:
 
233
            self.common = []
 
234
            revision_b = None
 
235
        self.descendants = {}
 
236
        ghosts = set()
 
237
        for revision, parents in self.ancestors.iteritems():
 
238
            self.descendants.setdefault(revision, [])
 
239
            if parents is None:
 
240
                ghosts.add(revision)
 
241
                parents = [NULL_REVISION]
 
242
            for parent in parents:
 
243
                self.descendants.setdefault(parent, []).append(revision)
 
244
        for ghost in ghosts:
 
245
            self.ancestors[ghost] = [NULL_REVISION]
 
246
 
 
247
    @staticmethod
 
248
    def _get_revno_str(prefix, revno_map, revision_id):
 
249
        try:
 
250
            revno = revno_map[revision_id]
 
251
        except KeyError:
 
252
            return None
 
253
        return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
137
254
 
138
255
    def dot_node(self, node, num):
139
256
        try:
145
262
        except ValueError:
146
263
            m_rev = None
147
264
        if (n_rev, m_rev) == (None, None):
148
 
            name = node[-5:]
 
265
            name = self._get_revno_str('r', self.n_revnos, node)
 
266
            if name is None:
 
267
                name = self._get_revno_str('R', self.m_revnos, node)
 
268
            if name is None:
 
269
                name = node[-5:]
149
270
            cluster = None
150
271
        elif n_rev == m_rev:
151
272
            name = "rR%d" % n_rev
171
292
            assert m_rev is not None
172
293
            cluster = "other_history"
173
294
            color = "#ff0000"
 
295
        if node in self.lcas:
 
296
            color = "#9933cc"
174
297
        if node == self.base:
175
 
            color = "#33ff99"
 
298
            color = "#669933"
 
299
            if node == self.new_base:
 
300
                color = "#33ff33"
 
301
        if node == self.new_base:
 
302
            color = '#33cc99'
176
303
 
177
304
        label = [name]
178
 
        committer, message, nick, date = get_rev_info(node, 
 
305
        committer, message, nick, date = get_rev_info(node,
179
306
                                                      self.branch.repository)
180
307
        if committer is not None:
181
308
            label.append(committer)
192
319
        else:
193
320
            rank = None
194
321
 
195
 
        d_node = Node("n%d" % num, color=color, label="\\n".join(label), 
 
322
        d_node = Node("n%d" % num, color=color, label="\\n".join(label),
196
323
                    rev_id=node, cluster=cluster, message=message,
197
324
                    date=date)
198
325
        d_node.rank = rank
201
328
            d_node.node_style.append('dotted')
202
329
 
203
330
        return d_node
204
 
       
 
331
 
205
332
    def get_relations(self, collapse=False, max_distance=None):
206
333
        dot_nodes = {}
207
334
        node_relations = []
208
335
        num = 0
209
336
        if collapse:
210
 
            visible_ancestors = compact_ancestors(self.descendants, 
211
 
                                                  self.ancestors, (self.base,))
 
337
            exceptions = self.lcas.union([self.base, self.new_base])
 
338
            visible_ancestors = compact_ancestors(self.descendants,
 
339
                                                  self.ancestors,
 
340
                                                  exceptions)
212
341
        else:
213
 
            visible_ancestors = self.ancestors
 
342
            visible_ancestors = {}
 
343
            for revision, parents in self.ancestors.iteritems():
 
344
                visible_ancestors[revision] = dict((p, 0) for p in parents)
214
345
        if max_distance is not None:
215
346
            min_distance = max(self.distances.values()) - max_distance
216
 
            visible_ancestors = dict((n, p) for n, p in visible_ancestors.iteritems() if
217
 
                    self.distances[n] >= min_distance)
 
347
            visible_ancestors = dict((n, p) for n, p in
 
348
                                     visible_ancestors.iteritems() if
 
349
                                     self.distances[n] >= min_distance)
218
350
        for node, parents in visible_ancestors.iteritems():
219
351
            if node not in dot_nodes:
220
352
                dot_nodes[node] = self.dot_node(node, num)
221
353
                num += 1
222
 
            if visible_ancestors is self.ancestors:
223
 
                parent_iter = ((f, 0) for f in parents)
224
 
            else:
225
 
                parent_iter = (f for f in parents.iteritems())
226
 
            for parent, skipped in parent_iter:
 
354
            for parent, skipped in parents.iteritems():
227
355
                if parent not in dot_nodes:
228
356
                    dot_nodes[parent] = self.dot_node(parent, num)
229
357
                    num += 1
259
387
    done = False
260
388
    if ext not in RSVG_OUTPUT_TYPES:
261
389
        antialias = False
262
 
    if antialias: 
 
390
    if antialias:
263
391
        output = list(output)
264
392
        try:
265
393
            invoke_dot_aa(output, filename, ext)
277
405
            done = True
278
406
        except NoDot, e:
279
407
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
280
 
                " is installed correctly, or use --noantialias")
 
408
                " is installed correctly.")
281
409
    elif ext == 'dot' and not done:
282
410
        my_file = file(filename, 'wb')
283
411
        for fragment in output:
287
415
            invoke_dot_html(output, filename)
288
416
        except NoDot, e:
289
417
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
290
 
                " is installed correctly, or use --noantialias")
 
418
                " is installed correctly.")
291
419
    elif not done:
292
420
        print "Unknown file extension: %s" % ext
293