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
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',
119
committer_alias = {'abentley': 'Aaron Bentley'}
4
from bzrlib.errors import BzrCommandError, NoCommonRoot
5
from bzrlib.fetch import greedy_fetch
6
from bzrlib.graph import node_distances, select_farthest
7
from bzrlib.revision import combined_graph
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',
20
def add_relations(rev_id):
21
if rev_id in ancestors:
24
if rev_id not in nodes:
25
nodes[rev_id] = Node("n%d" % counter, label = rev_id)
27
revision = branch.get_revision(rev_id)
28
ancestors [rev_id] = []
29
for p in (p.revision_id for p in revision.parents):
31
if p not in descendants:
33
descendants[p].append(rev_id)
34
ancestors [rev_id].append(rev_id)
36
def short_committer(committer):
37
new_committer = re.sub('<.*>', '', committer).strip(' ')
38
if len(new_committer) < 2:
120
42
def can_skip(rev_id, descendants, ancestors):
121
43
if rev_id not in descendants:
123
elif rev_id not in ancestors:
125
45
elif len(ancestors[rev_id]) != 1:
127
elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
47
elif len(descendants[ancestors[rev_id][0]]) != 1:
129
49
elif len(descendants[rev_id]) != 1:
134
def compact_ancestors(descendants, ancestors, exceptions=()):
54
def compact_descendants(descendants, ancestors):
137
for me, my_parents in ancestors.iteritems():
57
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
60
new_descendants[me] = []
61
for descendant in my_descendants:
62
new_descendant = descendant
63
while can_skip(new_descendant, descendants, ancestors):
64
skip.add(new_descendant)
65
if new_descendant in new_descendants:
66
del new_descendants[new_descendant]
67
new_descendant = descendants[new_descendant][0]
68
new_descendants[me].append(new_descendant)
69
return new_descendants
72
def graph_ancestry(branch, collapse=True):
74
q = ((i+1, n) for (i, n) in enumerate(branch.revision_history()))
164
rev = source.get_revision(rev_id)
165
except NoSuchRevision:
167
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
169
return None, None, None, None
171
return None, None, None, None
77
branch_name = os.path.basename(branch.base)
78
except AttributeError:
80
for (revno, rev_id) in q:
81
nodes[rev_id] = Node("R%d" % revno, color="#ffff00", rev_id=rev_id,
87
lines = [branch.last_patch()]
91
if rev_id not in nodes:
92
nodes[rev_id] = Node("n%d" % counter, label=rev_id,
97
revision = branch.get_revision(rev_id)
98
except bzrlib.errors.NoSuchRevision:
99
nodes[rev_id].node_style.append('dotted')
101
if nodes[rev_id].committer is None:
102
nodes[rev_id].committer = short_committer(revision.committer)
103
parent_ids = [r.revision_id for r in revision.parents]
104
ancestors [rev_id] = parent_ids
105
for parent in parent_ids:
106
if parent not in ancestors:
107
new_lines.add(parent)
108
descendants[parent] = []
109
descendants[parent].append(rev_id)
114
visible_descendants = compact_descendants(descendants, ancestors)
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')
181
committer = mail_map[committer]
116
visible_descendants = descendants
118
for key, values in visible_descendants.iteritems():
120
node_relations.append((nodes[key], nodes[value]))
121
return node_relations
123
def graph_merge_pick(branch, other_branch):
124
greedy_fetch(branch, other_branch)
125
revision_a = branch.last_patch()
126
revision_b = other_branch.last_patch()
185
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 = list(self.graph.iter_lefthand_ancestry(revision_a))
206
self.n_history.reverse()
207
self.n_revnos = branch.get_revision_id_to_revno_map()
208
self.distances = node_distances(self.descendants, self.ancestors,
210
if other_branch is not None:
211
self.base = select_farthest(self.distances, self.common)
212
self.m_history = self.graph.iter_lefthand_ancestry(revision_b)
213
self.m_history = list(self.m_history)
214
self.m_history.reverse()
215
self.m_revnos = other_branch.get_revision_id_to_revno_map()
216
self.new_base = self.graph.find_unique_lca(revision_a,
218
self.lcas = self.graph.find_lca(revision_a, revision_b)
226
def scan_graph(self, revision_a, revision_b):
227
a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
228
self.ancestors = a_ancestors
229
self.root = NULL_REVISION
230
if revision_b is not None:
231
b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
232
self.common = set(a_ancestors.keys())
233
self.common.intersection_update(b_ancestors)
234
self.ancestors.update(b_ancestors)
238
self.descendants = {}
240
for revision, parents in self.ancestors.iteritems():
241
self.descendants.setdefault(revision, [])
244
parents = [NULL_REVISION]
245
for parent in parents:
246
self.descendants.setdefault(parent, []).append(revision)
248
self.ancestors[ghost] = [NULL_REVISION]
251
def _get_revno_str(prefix, revno_map, revision_id):
253
revno = revno_map[revision_id]
256
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
258
def dot_node(self, node, num):
260
n_rev = self.n_history.index(node) + 1
128
root, ancestors, descendants, common = \
129
combined_graph(revision_a, revision_b, branch)
130
except bzrlib.errors.NoCommonRoot:
131
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
132
distances = node_distances(descendants, ancestors, root)
133
base = select_farthest(distances, common)
134
n_history = branch.revision_history()
135
m_history = other_branch.revision_history()
137
def dot_node(node, num):
139
n_rev = n_history.index(node) + 1
261
140
except ValueError:
264
m_rev = self.m_history.index(node) + 1
143
m_rev = m_history.index(node) + 1
265
144
except ValueError:
267
146
if (n_rev, m_rev) == (None, None):
268
name = self._get_revno_str('r', self.n_revnos, node)
270
name = self._get_revno_str('R', self.m_revnos, node)
274
149
elif n_rev == m_rev:
275
150
name = "rR%d" % n_rev
278
for prefix, revno in (('r', n_rev), ('R', m_rev)):
279
if revno is not None:
280
namelist.append("%s%d" % (prefix, revno))
153
for prefix, num in (('r', n_rev), ('R', m_rev)):
155
namelist.append("%s%d" % (prefix, num))
281
156
name = ' '.join(namelist)
282
157
if None not in (n_rev, m_rev):
283
158
cluster = "common_history"
284
159
color = "#ff9900"
285
160
elif (None, None) == (n_rev, m_rev):
287
if node in self.common:
288
163
color = "#6699ff"
291
166
elif n_rev is not None:
292
167
cluster = "my_history"
293
168
color = "#ffff00"
295
170
assert m_rev is not None
296
171
cluster = "other_history"
297
172
color = "#ff0000"
298
if node in self.lcas:
300
if node == self.base:
302
if node == self.new_base:
304
if node == self.new_base:
308
committer, message, nick, date = get_rev_info(node,
309
self.branch.repository)
310
if committer is not None:
311
label.append(committer)
319
if node in self.distances:
320
rank = self.distances[node]
321
label.append('d%d' % self.distances[node])
325
d_node = Node("n%d" % num, color=color, label="\\n".join(label),
326
rev_id=node, cluster=cluster, message=message,
330
if node not in self.ancestors:
331
d_node.node_style.append('dotted')
335
def get_relations(self, collapse=False, max_distance=None):
340
exceptions = self.lcas.union([self.base, self.new_base])
341
visible_ancestors = compact_ancestors(self.descendants,
345
visible_ancestors = {}
346
for revision, parents in self.ancestors.iteritems():
347
visible_ancestors[revision] = dict((p, 0) for p in parents)
348
if max_distance is not None:
349
min_distance = max(self.distances.values()) - max_distance
350
visible_ancestors = dict((n, p) for n, p in
351
visible_ancestors.iteritems() if
352
self.distances[n] >= min_distance)
353
for node, parents in visible_ancestors.iteritems():
354
if node not in dot_nodes:
355
dot_nodes[node] = self.dot_node(node, num)
357
for parent, skipped in parents.iteritems():
358
if parent not in dot_nodes:
359
dot_nodes[parent] = self.dot_node(parent, num)
361
edge = Edge(dot_nodes[parent], dot_nodes[node])
363
edge.label = "%d" % skipped
364
node_relations.append(edge)
365
return node_relations
368
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
369
merge_branch=None, ranking="forced", max_distance=None):
370
b = Branch.open_containing(branch)[0]
371
if merge_branch is not None:
372
m = Branch.open_containing(merge_branch)[0]
380
grapher = Grapher(b, m)
381
relations = grapher.get_relations(collapse, max_distance)
177
if node in distances:
178
label.append('d%d' % distances[node])
179
return Node("n%d" % num, color=color, label="\\n".join(label),
180
rev_id=node, cluster=cluster)
183
for num,node in enumerate(descendants):
184
dot_nodes[node] = dot_node(node, num)
187
for node, parents in ancestors.iteritems():
188
if node not in dot_nodes:
189
dot_nodes[node] = dot_node(node, 100000)
190
for parent in parents:
191
node_relations.append((dot_nodes[parent], dot_nodes[node]))
192
return node_relations
195
def write_ancestry_file(branch, filename, collapse=True, antialias=True):
196
b = Branch.open_containing(branch)
197
relations = graph_merge_pick(b, b)
388
198
ext = filename.split('.')[-1]
389
output = dot_output(relations, ranking)
391
if ext not in RSVG_OUTPUT_TYPES:
394
output = list(output)
199
if antialias and ext in ('png', 'jpg'):
396
invoke_dot_aa(output, filename, ext)
201
invoke_dot_aa(dot_output(relations), filename, ext)
399
203
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
400
204
" is installed correctly.")
401
205
except NoRsvg, e:
402
print "Not antialiasing because rsvg (from librsvg-bin) is not"\
405
if ext in DOT_OUTPUT_TYPES and not antialias and not done:
407
invoke_dot(output, filename, ext)
410
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
411
" is installed correctly.")
412
elif ext == 'dot' and not done:
413
my_file = file(filename, 'wb')
414
for fragment in output:
415
my_file.write(fragment.encode('utf-8'))
418
invoke_dot_html(output, filename)
420
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
421
" is installed correctly.")
206
raise BzrCommandError("Can't find 'rsvg'. Please ensure "\
207
"librsvg-bin is installed correctly, or use --noantialias.")
208
elif ext in ('svg', 'svgz', 'gif', 'jpg', 'ps', 'fig', 'mif', 'png'):
210
invoke_dot(dot_output(relations), filename, ext)
212
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
213
" is installed correctly, or use --noantialias")
215
file(filename, 'wb').write("".join(list(dot_output(relations))))
423
217
print "Unknown file extension: %s" % ext
added
removed
graph.py
