← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2005-11-10 20:15:27 UTC
  • Revision ID: aaron.bentley@utoronto.ca-20051110201527-8caa84ae529a1871
Added Daniel Silverstone to credits

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
1
 
# Copyright (C) 2005, 2008 Aaron Bentley
2
 
# <aaron@aaronbentley.com>
 
1
# Copyright (C) 2005 Aaron Bentley
 
2
# <aaron.bentley@utoronto.ca>
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
 
 
 
17
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
 
18
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
 
19
from bzrlib.branch import Branch
 
20
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
 
21
from bzrlib.fetch import greedy_fetch
 
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
19
28
import time
20
29
 
21
 
from bzrlib.branch import Branch
22
 
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
 
from bzrlib.revision import NULL_REVISION
24
 
 
25
 
from bzrtools import short_committer
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
 
 
110
 
 
111
30
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
112
31
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
32
            'abentley@lappy'                : 'Aaron Bentley',
117
36
            }
118
37
 
119
38
committer_alias = {'abentley': 'Aaron Bentley'}
 
39
def short_committer(committer):
 
40
    new_committer = re.sub('<.*>', '', committer).strip(' ')
 
41
    if len(new_committer) < 2:
 
42
        return committer
 
43
    return new_committer
 
44
 
120
45
def can_skip(rev_id, descendants, ancestors):
121
46
    if rev_id not in descendants:
122
47
        return False
137
62
    for me, my_parents in ancestors.iteritems():
138
63
        if me in skip:
139
64
            continue
140
 
        new_ancestors[me] = {}
 
65
        new_ancestors[me] = {} 
141
66
        for parent in my_parents:
142
 
            new_parent = parent
 
67
            new_parent = parent 
143
68
            distance = 0
144
69
            while can_skip(new_parent, descendants, ancestors):
145
70
                if new_parent in exceptions:
150
75
                new_parent = list(ancestors[new_parent])[0]
151
76
                distance += 1
152
77
            new_ancestors[me][new_parent] = distance
153
 
    return new_ancestors
 
78
    return new_ancestors    
154
79
 
155
80
def get_rev_info(rev_id, source):
156
81
    """Return the committer, message, and date of a revision."""
158
83
    message = None
159
84
    date = None
160
85
    if rev_id == 'null:':
161
 
        return None, 'Null Revision', None, None
 
86
        return None, 'Null Revision', None
162
87
    try:
163
88
        rev = source.get_revision(rev_id)
164
89
    except NoSuchRevision:
165
90
        try:
166
91
            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
167
92
            if committer == '':
168
 
                return None, None, None, None
 
93
                return None, None, None
169
94
        except ValueError:
170
 
            return None, None, None, None
 
95
            return None, None, None
171
96
    else:
172
97
        committer = short_committer(rev.committer)
173
98
        if rev.message is not None:
174
99
            message = rev.message.split('\n')[0]
175
100
        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
176
101
        date = time.strftime('%Y/%m/%d', gmtime)
177
 
        nick = rev.properties.get('branch-nick')
178
102
    if '@' in committer:
179
103
        try:
180
104
            committer = mail_map[committer]
184
108
        committer = committer_alias[committer]
185
109
    except KeyError:
186
110
        pass
187
 
    return committer, message, nick, date
 
111
    return committer, message, date
188
112
 
189
113
class Grapher(object):
190
 
 
191
114
    def __init__(self, branch, other_branch=None):
192
115
        object.__init__(self)
193
116
        self.branch = branch
194
117
        self.other_branch = other_branch
 
118
        revision_a = self.branch.last_revision()
195
119
        if other_branch is not None:
196
 
            other_repo = other_branch.repository
 
120
            greedy_fetch(branch, other_branch)
197
121
            revision_b = self.other_branch.last_revision()
 
122
            try:
 
123
                self.root, self.ancestors, self.descendants, self.common = \
 
124
                    combined_graph(revision_a, revision_b, self.branch)
 
125
            except bzrlib.errors.NoCommonRoot:
 
126
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
198
127
        else:
199
 
            other_repo = None
200
 
            revision_b = None
201
 
        self.graph = self.branch.repository.get_graph(other_repo)
202
 
        revision_a = self.branch.last_revision()
203
 
        self.scan_graph(revision_a, revision_b)
 
128
            self.root, self.ancestors, self.descendants = \
 
129
                revision_graph(revision_a, branch)
 
130
            self.common = []
 
131
 
204
132
        self.n_history = branch.revision_history()
205
 
        self.n_revnos = branch.get_revision_id_to_revno_map()
206
 
        self.distances = node_distances(self.descendants, self.ancestors,
 
133
        self.distances = node_distances(self.descendants, self.ancestors, 
207
134
                                        self.root)
208
135
        if other_branch is not None:
209
136
            self.base = select_farthest(self.distances, self.common)
210
 
            self.m_history = other_branch.revision_history()
211
 
            self.m_revnos = other_branch.get_revision_id_to_revno_map()
212
 
            self.new_base = self.graph.find_unique_lca(revision_a,
213
 
                                                       revision_b)
214
 
            self.lcas = self.graph.find_lca(revision_a, revision_b)
 
137
            self.m_history = other_branch.revision_history() 
215
138
        else:
216
139
            self.base = None
217
 
            self.new_base = None
218
 
            self.lcas = set()
219
140
            self.m_history = []
220
 
            self.m_revnos = {}
221
 
 
222
 
    def scan_graph(self, revision_a, revision_b):
223
 
        a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
224
 
        self.ancestors = a_ancestors
225
 
        self.root = NULL_REVISION
226
 
        if revision_b is not None:
227
 
            b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
228
 
            self.common = set(a_ancestors.keys())
229
 
            self.common.intersection_update(b_ancestors)
230
 
            self.ancestors.update(b_ancestors)
231
 
        else:
232
 
            self.common = []
233
 
            revision_b = None
234
 
        self.descendants = {}
235
 
        ghosts = set()
236
 
        for revision, parents in self.ancestors.iteritems():
237
 
            self.descendants.setdefault(revision, [])
238
 
            if parents is None:
239
 
                ghosts.add(revision)
240
 
                parents = [NULL_REVISION]
241
 
            for parent in parents:
242
 
                self.descendants.setdefault(parent, []).append(revision)
243
 
        for ghost in ghosts:
244
 
            self.ancestors[ghost] = [NULL_REVISION]
245
 
 
246
 
    @staticmethod
247
 
    def _get_revno_str(prefix, revno_map, revision_id):
248
 
        try:
249
 
            revno = revno_map[revision_id]
250
 
        except KeyError:
251
 
            return None
252
 
        return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
253
141
 
254
142
    def dot_node(self, node, num):
255
143
        try:
261
149
        except ValueError:
262
150
            m_rev = None
263
151
        if (n_rev, m_rev) == (None, None):
264
 
            name = self._get_revno_str('r', self.n_revnos, node)
265
 
            if name is None:
266
 
                name = self._get_revno_str('R', self.m_revnos, node)
267
 
            if name is None:
268
 
                name = node[-5:]
 
152
            name = node[-5:]
269
153
            cluster = None
270
154
        elif n_rev == m_rev:
271
155
            name = "rR%d" % n_rev
291
175
            assert m_rev is not None
292
176
            cluster = "other_history"
293
177
            color = "#ff0000"
294
 
        if node in self.lcas:
295
 
            color = "#9933cc"
296
178
        if node == self.base:
297
 
            color = "#669933"
298
 
            if node == self.new_base:
299
 
                color = "#33ff33"
300
 
        if node == self.new_base:
301
 
            color = '#33cc99'
 
179
            color = "#33ff99"
302
180
 
303
181
        label = [name]
304
 
        committer, message, nick, date = get_rev_info(node,
305
 
                                                      self.branch.repository)
 
182
        committer, message, date = get_rev_info(node, self.branch)
306
183
        if committer is not None:
307
184
            label.append(committer)
308
185
 
309
 
        if nick is not None:
310
 
            label.append(nick)
311
 
 
312
186
        if date is not None:
313
187
            label.append(date)
314
188
 
318
192
        else:
319
193
            rank = None
320
194
 
321
 
        d_node = Node("n%d" % num, color=color, label="\\n".join(label),
 
195
        d_node = Node("n%d" % num, color=color, label="\\n".join(label), 
322
196
                    rev_id=node, cluster=cluster, message=message,
323
197
                    date=date)
324
198
        d_node.rank = rank
327
201
            d_node.node_style.append('dotted')
328
202
 
329
203
        return d_node
330
 
 
331
 
    def get_relations(self, collapse=False, max_distance=None):
 
204
        
 
205
    def get_relations(self, collapse=False):
332
206
        dot_nodes = {}
333
207
        node_relations = []
334
208
        num = 0
335
209
        if collapse:
336
 
            exceptions = self.lcas.union([self.base, self.new_base])
337
 
            visible_ancestors = compact_ancestors(self.descendants,
338
 
                                                  self.ancestors,
339
 
                                                  exceptions)
 
210
            visible_ancestors = compact_ancestors(self.descendants, 
 
211
                                                  self.ancestors, (self.base,))
340
212
        else:
341
 
            visible_ancestors = {}
342
 
            for revision, parents in self.ancestors.iteritems():
343
 
                visible_ancestors[revision] = dict((p, 0) for p in parents)
344
 
        if max_distance is not None:
345
 
            min_distance = max(self.distances.values()) - max_distance
346
 
            visible_ancestors = dict((n, p) for n, p in
347
 
                                     visible_ancestors.iteritems() if
348
 
                                     self.distances[n] >= min_distance)
 
213
            visible_ancestors = self.ancestors
349
214
        for node, parents in visible_ancestors.iteritems():
350
215
            if node not in dot_nodes:
351
216
                dot_nodes[node] = self.dot_node(node, num)
352
217
                num += 1
353
 
            for parent, skipped in parents.iteritems():
 
218
            if visible_ancestors is self.ancestors:
 
219
                parent_iter = ((f, 0) for f in parents)
 
220
            else:
 
221
                parent_iter = (f for f in parents.iteritems())
 
222
            for parent, skipped in parent_iter:
354
223
                if parent not in dot_nodes:
355
224
                    dot_nodes[parent] = self.dot_node(parent, num)
356
225
                    num += 1
362
231
 
363
232
 
364
233
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
365
 
                        merge_branch=None, ranking="forced", max_distance=None):
 
234
                        merge_branch=None, ranking="forced"):
366
235
    b = Branch.open_containing(branch)[0]
367
236
    if merge_branch is not None:
368
237
        m = Branch.open_containing(merge_branch)[0]
369
238
    else:
370
239
        m = None
371
 
    b.lock_write()
 
240
    b.lock_read()
372
241
    try:
373
242
        if m is not None:
374
243
            m.lock_read()
375
244
        try:
376
245
            grapher = Grapher(b, m)
377
 
            relations = grapher.get_relations(collapse, max_distance)
 
246
            relations = grapher.get_relations(collapse)
378
247
        finally:
379
248
            if m is not None:
380
249
                m.unlock()
386
255
    done = False
387
256
    if ext not in RSVG_OUTPUT_TYPES:
388
257
        antialias = False
389
 
    if antialias:
 
258
    if antialias: 
390
259
        output = list(output)
391
260
        try:
392
261
            invoke_dot_aa(output, filename, ext)
404
273
            done = True
405
274
        except NoDot, e:
406
275
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
407
 
                " is installed correctly.")
 
276
                " is installed correctly, or use --noantialias")
408
277
    elif ext == 'dot' and not done:
409
278
        my_file = file(filename, 'wb')
410
279
        for fragment in output:
411
 
            my_file.write(fragment.encode('utf-8'))
 
280
            my_file.write(fragment)
412
281
    elif ext == 'html':
413
282
        try:
414
283
            invoke_dot_html(output, filename)
415
284
        except NoDot, e:
416
285
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
417
 
                " is installed correctly.")
 
286
                " is installed correctly, or use --noantialias")
418
287
    elif not done:
419
288
        print "Unknown file extension: %s" % ext
 
289