1
# Copyright (C) 2005, 2008 Aaron Bentley
2
# <aaron@aaronbentley.com>
4
# This program is free software; you can redistribute it and/or modify
5
# it under the terms of the GNU General Public License as published by
6
# the Free Software Foundation; either version 2 of the License, or
7
# (at your option) any later version.
9
# This program is distributed in the hope that it will be useful,
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
# GNU General Public License for more details.
14
# You should have received a copy of the GNU General Public License
15
# along with this program; if not, write to the Free Software
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
from bzrlib.branch import Branch
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
from bzrlib.revision import NULL_REVISION
25
from bzrtools import short_committer
26
from dotgraph import (
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"""
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:
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:
54
if ancestor not in distances:
56
if best is None or distances[ancestor]+1 > best:
57
best = distances[ancestor] + 1
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.
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.
70
So when a node's last parent acquires a distance, it will acquire a
71
distance on the next iteration.
73
Once we know the max distances for all nodes, we can return a list sorted
74
by distance, farthest first.
76
distances = {start: 0}
81
line_descendants = graph[line]
82
for descendant in line_descendants:
83
distance = max_distance(descendant, ancestors, distances,
87
distances[descendant] = distance
88
new_lines.add(descendant)
93
def nodes_by_distance(distances):
94
"""Return a list of nodes sorted by distance"""
98
node_list = distances.keys()
99
node_list.sort(key=by_distance, reverse=True)
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:
111
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
112
'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
'abentley@lappy' : 'Aaron Bentley',
114
'john@arbash-meinel.com' : 'John Arbash Meinel',
115
'mbp@sourcefrog.net' : 'Martin Pool',
116
'robertc@robertcollins.net' : 'Robert Collins',
119
committer_alias = {'abentley': 'Aaron Bentley'}
120
def can_skip(rev_id, descendants, ancestors):
121
if rev_id not in descendants:
123
elif rev_id not in ancestors:
125
elif len(ancestors[rev_id]) != 1:
127
elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
129
elif len(descendants[rev_id]) != 1:
134
def compact_ancestors(descendants, ancestors, exceptions=()):
137
for me, my_parents in ancestors.iteritems():
140
new_ancestors[me] = {}
141
for parent in my_parents:
144
while can_skip(new_parent, descendants, ancestors):
145
if new_parent in exceptions:
148
if new_parent in new_ancestors:
149
del new_ancestors[new_parent]
150
new_parent = list(ancestors[new_parent])[0]
152
new_ancestors[me][new_parent] = distance
155
def get_rev_info(rev_id, source):
156
"""Return the committer, message, and date of a revision."""
160
if rev_id == 'null:':
161
return None, 'Null Revision', None, None
163
rev = source.get_revision(rev_id)
164
except NoSuchRevision:
166
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
168
return None, None, None, None
170
return None, None, None, None
172
committer = short_committer(rev.committer)
173
if rev.message is not None:
174
message = rev.message.split('\n')[0]
175
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
176
date = time.strftime('%Y/%m/%d', gmtime)
177
nick = rev.properties.get('branch-nick')
180
committer = mail_map[committer]
184
committer = committer_alias[committer]
187
return committer, message, nick, date
189
class Grapher(object):
191
def __init__(self, branch, other_branch=None):
192
object.__init__(self)
194
self.other_branch = other_branch
195
if other_branch is not None:
196
other_repo = other_branch.repository
197
revision_b = self.other_branch.last_revision()
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)
204
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,
208
if other_branch is not None:
209
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,
214
self.lcas = self.graph.find_lca(revision_a, revision_b)
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)
234
self.descendants = {}
236
for revision, parents in self.ancestors.iteritems():
237
self.descendants.setdefault(revision, [])
240
parents = [NULL_REVISION]
241
for parent in parents:
242
self.descendants.setdefault(parent, []).append(revision)
244
self.ancestors[ghost] = [NULL_REVISION]
247
def _get_revno_str(prefix, revno_map, revision_id):
249
revno = revno_map[revision_id]
252
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
254
def dot_node(self, node, num):
256
n_rev = self.n_history.index(node) + 1
260
m_rev = self.m_history.index(node) + 1
263
if (n_rev, m_rev) == (None, None):
264
name = self._get_revno_str('r', self.n_revnos, node)
266
name = self._get_revno_str('R', self.m_revnos, node)
271
name = "rR%d" % n_rev
274
for prefix, revno in (('r', n_rev), ('R', m_rev)):
275
if revno is not None:
276
namelist.append("%s%d" % (prefix, revno))
277
name = ' '.join(namelist)
278
if None not in (n_rev, m_rev):
279
cluster = "common_history"
281
elif (None, None) == (n_rev, m_rev):
283
if node in self.common:
287
elif n_rev is not None:
288
cluster = "my_history"
291
assert m_rev is not None
292
cluster = "other_history"
294
if node in self.lcas:
296
if node == self.base:
298
if node == self.new_base:
300
if node == self.new_base:
304
committer, message, nick, date = get_rev_info(node,
305
self.branch.repository)
306
if committer is not None:
307
label.append(committer)
315
if node in self.distances:
316
rank = self.distances[node]
317
label.append('d%d' % self.distances[node])
321
d_node = Node("n%d" % num, color=color, label="\\n".join(label),
322
rev_id=node, cluster=cluster, message=message,
326
if node not in self.ancestors:
327
d_node.node_style.append('dotted')
331
def get_relations(self, collapse=False, max_distance=None):
336
exceptions = self.lcas.union([self.base, self.new_base])
337
visible_ancestors = compact_ancestors(self.descendants,
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)
349
for node, parents in visible_ancestors.iteritems():
350
if node not in dot_nodes:
351
dot_nodes[node] = self.dot_node(node, num)
353
for parent, skipped in parents.iteritems():
354
if parent not in dot_nodes:
355
dot_nodes[parent] = self.dot_node(parent, num)
357
edge = Edge(dot_nodes[parent], dot_nodes[node])
359
edge.label = "%d" % skipped
360
node_relations.append(edge)
361
return node_relations
364
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
365
merge_branch=None, ranking="forced", max_distance=None):
366
b = Branch.open_containing(branch)[0]
367
if merge_branch is not None:
368
m = Branch.open_containing(merge_branch)[0]
376
grapher = Grapher(b, m)
377
relations = grapher.get_relations(collapse, max_distance)
384
ext = filename.split('.')[-1]
385
output = dot_output(relations, ranking)
387
if ext not in RSVG_OUTPUT_TYPES:
390
output = list(output)
392
invoke_dot_aa(output, filename, ext)
395
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
396
" is installed correctly.")
398
print "Not antialiasing because rsvg (from librsvg-bin) is not"\
401
if ext in DOT_OUTPUT_TYPES and not antialias and not done:
403
invoke_dot(output, filename, ext)
406
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
407
" is installed correctly.")
408
elif ext == 'dot' and not done:
409
my_file = file(filename, 'wb')
410
for fragment in output:
411
my_file.write(fragment.encode('utf-8'))
414
invoke_dot_html(output, filename)
416
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
417
" is installed correctly.")
419
print "Unknown file extension: %s" % ext
added
removed
graph.py
