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
1
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
2
from dotgraph import mail_map, RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES
21
3
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',
4
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
5
from bzrlib.fetch import greedy_fetch
6
from bzrlib.graph import node_distances, select_farthest
7
from bzrlib.revision import combined_graph, MultipleRevisionSources
12
mail_map.update({'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
13
'abentley@panoramicfeedback.com': 'Aaron Bentley',
14
'abentley@lappy' : 'Aaron Bentley',
15
'john@arbash-meinel.com' : 'John Arbash Meinel',
16
'mbp@sourcefrog.net' : 'Martin Pool',
17
'robertc@robertcollins.net' : 'Robert Collins',
119
20
committer_alias = {'abentley': 'Aaron Bentley'}
21
def add_relations(rev_id):
22
if rev_id in ancestors:
25
if rev_id not in nodes:
26
nodes[rev_id] = Node("n%d" % counter, label = rev_id)
28
revision = branch.get_revision(rev_id)
29
ancestors [rev_id] = []
30
for p in (p.revision_id for p in revision.parents):
32
if p not in descendants:
34
descendants[p].append(rev_id)
35
ancestors [rev_id].append(rev_id)
37
def short_committer(committer):
38
new_committer = re.sub('<.*>', '', committer).strip(' ')
39
if len(new_committer) < 2:
120
43
def can_skip(rev_id, descendants, ancestors):
121
44
if rev_id not in descendants:
123
elif rev_id not in ancestors:
125
46
elif len(ancestors[rev_id]) != 1:
127
elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
48
elif len(descendants[ancestors[rev_id][0]]) != 1:
129
50
elif len(descendants[rev_id]) != 1:
134
def compact_ancestors(descendants, ancestors, exceptions=()):
55
def compact_descendants(descendants, ancestors):
137
for me, my_parents in ancestors.iteritems():
58
for me, my_descendants in descendants.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, nick and date of a revision."""
161
if rev_id == 'null:':
162
return None, 'Null Revision', None, None
164
rev = source.get_revision(rev_id)
61
new_descendants[me] = []
62
for descendant in my_descendants:
63
new_descendant = descendant
64
while can_skip(new_descendant, descendants, ancestors):
65
skip.add(new_descendant)
66
if new_descendant in new_descendants:
67
del new_descendants[new_descendant]
68
new_descendant = descendants[new_descendant][0]
69
new_descendants[me].append(new_descendant)
70
return new_descendants
73
def graph_ancestry(branch, collapse=True):
75
q = ((i+1, n) for (i, n) in enumerate(branch.revision_history()))
78
branch_name = os.path.basename(branch.base)
79
except AttributeError:
81
for (revno, rev_id) in q:
82
nodes[rev_id] = Node("R%d" % revno, color="#ffff00", rev_id=rev_id,
88
lines = [branch.last_patch()]
92
if rev_id not in nodes:
93
nodes[rev_id] = Node("n%d" % counter, label=rev_id,
98
revision = branch.get_revision(rev_id)
99
except bzrlib.errors.NoSuchRevision:
100
nodes[rev_id].node_style.append('dotted')
102
if nodes[rev_id].committer is None:
103
nodes[rev_id].committer = short_committer(revision.committer)
104
parent_ids = [r.revision_id for r in revision.parents]
105
ancestors [rev_id] = parent_ids
106
for parent in parent_ids:
107
if parent not in ancestors:
108
new_lines.add(parent)
109
descendants[parent] = []
110
descendants[parent].append(rev_id)
114
for node in nodes.itervalues():
115
node.label = node.get_label()
117
visible_descendants = compact_descendants(descendants, ancestors)
119
visible_descendants = descendants
121
for key, values in visible_descendants.iteritems():
123
node_relations.append((nodes[key], nodes[value]))
124
return node_relations
126
def get_committer(rev_id, source):
128
committer = short_committer(source.get_revision(rev_id).committer)
165
129
except NoSuchRevision:
167
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
169
return None, None, None, None
131
committer = '-'.join(rev_id.split('-')[:-2])\
170
133
except ValueError:
171
return None, None, None, None
173
committer = short_committer(rev.committer)
174
if rev.message is not None:
175
message = rev.message.split('\n')[0]
176
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
177
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
179
135
if '@' in committer:
181
137
committer = mail_map[committer]
185
141
committer = committer_alias[committer]
188
return committer, message, nick, date
190
class Grapher(object):
192
def __init__(self, branch, other_branch=None):
193
object.__init__(self)
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()
202
self.graph = self.branch.repository.get_graph(other_repo)
203
revision_a = self.branch.last_revision()
204
self.scan_graph(revision_a, revision_b)
205
self.n_history = branch.revision_history()
206
self.n_revnos = branch.get_revision_id_to_revno_map()
207
self.distances = node_distances(self.descendants, self.ancestors,
209
if other_branch is not None:
210
self.base = select_farthest(self.distances, self.common)
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,
215
self.lcas = self.graph.find_lca(revision_a, revision_b)
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)
235
self.descendants = {}
237
for revision, parents in self.ancestors.iteritems():
238
self.descendants.setdefault(revision, [])
241
parents = [NULL_REVISION]
242
for parent in parents:
243
self.descendants.setdefault(parent, []).append(revision)
245
self.ancestors[ghost] = [NULL_REVISION]
248
def _get_revno_str(prefix, revno_map, revision_id):
250
revno = revno_map[revision_id]
253
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
255
def dot_node(self, node, num):
257
n_rev = self.n_history.index(node) + 1
147
def graph_merge_pick(branch, other_branch):
148
greedy_fetch(branch, other_branch)
149
revision_a = branch.last_patch()
150
revision_b = other_branch.last_patch()
152
root, ancestors, descendants, common = \
153
combined_graph(revision_a, revision_b, branch)
154
except bzrlib.errors.NoCommonRoot:
155
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
156
distances = node_distances(descendants, ancestors, root)
157
base = select_farthest(distances, common)
158
n_history = branch.revision_history()
161
def dot_node(node, num):
163
n_rev = n_history.index(node) + 1
258
164
except ValueError:
261
m_rev = self.m_history.index(node) + 1
167
m_rev = m_history.index(node) + 1
262
168
except ValueError:
264
170
if (n_rev, m_rev) == (None, None):
265
name = self._get_revno_str('r', self.n_revnos, node)
267
name = self._get_revno_str('R', self.m_revnos, node)
271
173
elif n_rev == m_rev:
272
174
name = "rR%d" % n_rev
292
194
assert m_rev is not None
293
195
cluster = "other_history"
294
196
color = "#ff0000"
295
if node in self.lcas:
297
if node == self.base:
299
if node == self.new_base:
301
if node == self.new_base:
305
committer, message, nick, date = get_rev_info(node,
306
self.branch.repository)
201
committer = get_committer(node, branch)
307
202
if committer is not None:
308
203
label.append(committer)
316
if node in self.distances:
317
rank = self.distances[node]
318
label.append('d%d' % self.distances[node])
322
d_node = Node("n%d" % num, color=color, label="\\n".join(label),
323
rev_id=node, cluster=cluster, message=message,
327
if node not in self.ancestors:
328
d_node.node_style.append('dotted')
332
def get_relations(self, collapse=False, max_distance=None):
337
exceptions = self.lcas.union([self.base, self.new_base])
338
visible_ancestors = compact_ancestors(self.descendants,
342
visible_ancestors = {}
343
for revision, parents in self.ancestors.iteritems():
344
visible_ancestors[revision] = dict((p, 0) for p in parents)
345
if max_distance is not None:
346
min_distance = max(self.distances.values()) - max_distance
347
visible_ancestors = dict((n, p) for n, p in
348
visible_ancestors.iteritems() if
349
self.distances[n] >= min_distance)
350
for node, parents in visible_ancestors.iteritems():
351
if node not in dot_nodes:
352
dot_nodes[node] = self.dot_node(node, num)
354
for parent, skipped in parents.iteritems():
355
if parent not in dot_nodes:
356
dot_nodes[parent] = self.dot_node(parent, num)
358
edge = Edge(dot_nodes[parent], dot_nodes[node])
360
edge.label = "%d" % skipped
361
node_relations.append(edge)
362
return node_relations
205
if node in distances:
206
label.append('d%d' % distances[node])
207
return Node("n%d" % num, color=color, label="\\n".join(label),
208
rev_id=node, cluster=cluster)
211
for num,node in enumerate(descendants):
212
dot_nodes[node] = dot_node(node, num)
215
for node, parents in ancestors.iteritems():
216
if node not in dot_nodes:
217
dot_nodes[node] = dot_node(node, 100000)
218
for parent in parents:
219
node_relations.append((dot_nodes[parent], dot_nodes[node]))
220
return node_relations
365
223
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
366
merge_branch=None, ranking="forced", max_distance=None):
367
b = Branch.open_containing(branch)[0]
368
if merge_branch is not None:
369
m = Branch.open_containing(merge_branch)[0]
225
b = Branch.open_containing(branch)
226
if merge_branch is None:
227
relations = graph_ancestry(b, collapse)
377
grapher = Grapher(b, m)
378
relations = grapher.get_relations(collapse, max_distance)
229
m = Branch.open_containing(merge_branch)
230
relations = graph_merge_pick(b, m)
385
232
ext = filename.split('.')[-1]
386
output = dot_output(relations, ranking)
388
if ext not in RSVG_OUTPUT_TYPES:
391
output = list(output)
233
if antialias and ext in RSVG_OUTPUT_TYPES:
393
invoke_dot_aa(output, filename, ext)
235
invoke_dot_aa(dot_output(relations), filename, ext)
396
237
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
397
238
" is installed correctly.")
398
239
except NoRsvg, e:
399
print "Not antialiasing because rsvg (from librsvg-bin) is not"\
402
if ext in DOT_OUTPUT_TYPES and not antialias and not done:
404
invoke_dot(output, filename, ext)
407
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
408
" is installed correctly.")
409
elif ext == 'dot' and not done:
410
my_file = file(filename, 'wb')
411
for fragment in output:
412
my_file.write(fragment.encode('utf-8'))
415
invoke_dot_html(output, filename)
417
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
418
" is installed correctly.")
240
raise BzrCommandError("Can't find 'rsvg'. Please ensure "\
241
"librsvg-bin is installed correctly, or use --noantialias.")
242
elif ext in DOT_OUTPUT_TYPES:
244
invoke_dot(dot_output(relations), filename, ext)
246
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
247
" is installed correctly, or use --noantialias")
249
file(filename, 'wb').write("".join(list(dot_output(relations))))
420
251
print "Unknown file extension: %s" % ext
added
removed
graph.py
