« back to all changes in this revision
Viewing changes to graph.py
- browse files at revision 86
- compare with another revision
- download diff
- download tarball
- view history from revision 86
- Committer: Aaron Bentley
- Date: 2005-06-15 15:25:13 UTC
- Revision ID: abentley@panoramicfeedback.com-20050615152512-e2afe3f794604a12
Added Michael Ellerman's shelf/unshelf
added
removed
graph.py
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, Edge
3
from bzrlib.branch import Branch
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
8
import bzrlib.errors
9
import re
10
import os.path
11
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',
18
})
19
20
committer_alias = {'abentley': 'Aaron Bentley'}
21
def add_relations(rev_id):
22
if rev_id in ancestors:
23
return
24
print rev_id
25
if rev_id not in nodes:
26
nodes[rev_id] = Node("n%d" % counter, label = rev_id)
27
counter += 1
28
revision = branch.get_revision(rev_id)
29
ancestors [rev_id] = []
30
for p in (p.revision_id for p in revision.parents):
31
add_relations(p)
32
if p not in descendants:
33
descendants[p] = []
34
descendants[p].append(rev_id)
35
ancestors [rev_id].append(rev_id)
36
37
def short_committer(committer):
38
new_committer = re.sub('<.*>', '', committer).strip(' ')
39
if len(new_committer) < 2:
40
return committer
41
return new_committer
42
43
def can_skip(rev_id, descendants, ancestors):
44
if rev_id not in descendants:
45
return False
46
elif rev_id not in ancestors:
47
return False
48
elif len(ancestors[rev_id]) != 1:
49
return False
50
elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
51
return False
52
elif len(descendants[rev_id]) != 1:
53
return False
54
else:
55
return True
56
57
def compact_ancestors(descendants, ancestors, exceptions=()):
58
new_ancestors={}
59
skip = set()
60
for me, my_parents in ancestors.iteritems():
61
if me in skip:
62
continue
63
new_ancestors[me] = {}
64
for parent in my_parents:
65
new_parent = parent
66
distance = 0
67
while can_skip(new_parent, descendants, ancestors):
68
if new_parent in exceptions:
69
break
70
skip.add(new_parent)
71
if new_parent in new_ancestors:
72
del new_ancestors[new_parent]
73
new_parent = list(ancestors[new_parent])[0]
74
distance += 1
75
new_ancestors[me][new_parent] = distance
76
return new_ancestors
77
78
def compact_descendants(descendants, ancestors):
79
new_descendants={}
80
skip = set()
81
for me, my_descendants in descendants.iteritems():
82
if me in skip:
83
continue
84
new_descendants[me] = []
85
for descendant in my_descendants:
86
new_descendant = descendant
87
while can_skip(new_descendant, descendants, ancestors):
88
skip.add(new_descendant)
89
if new_descendant in new_descendants:
90
del new_descendants[new_descendant]
91
new_descendant = descendants[new_descendant][0]
92
new_descendants[me].append(new_descendant)
93
return new_descendants
94
95
96
def graph_ancestry(branch, collapse=True):
97
nodes = {}
98
q = ((i+1, n) for (i, n) in enumerate(branch.revision_history()))
99
r = 1
100
try:
101
branch_name = os.path.basename(branch.base)
102
except AttributeError:
103
branch_name = "main"
104
for (revno, rev_id) in q:
105
nodes[rev_id] = Node("R%d" % revno, color="#ffff00", rev_id=rev_id,
106
cluster=branch_name)
107
108
ancestors = {}
109
descendants = {}
110
counter = 0
111
lines = [branch.last_patch()]
112
while len(lines) > 0:
113
new_lines = set()
114
for rev_id in lines:
115
if rev_id not in nodes:
116
nodes[rev_id] = Node("n%d" % counter, label=rev_id,
117
rev_id=rev_id)
118
counter+=1
119
120
try:
121
revision = branch.get_revision(rev_id)
122
except bzrlib.errors.NoSuchRevision:
123
nodes[rev_id].node_style.append('dotted')
124
continue
125
if nodes[rev_id].committer is None:
126
nodes[rev_id].committer = short_committer(revision.committer)
127
parent_ids = [r.revision_id for r in revision.parents]
128
ancestors [rev_id] = parent_ids
129
for parent in parent_ids:
130
if parent not in ancestors:
131
new_lines.add(parent)
132
descendants[parent] = []
133
descendants[parent].append(rev_id)
134
lines = new_lines
135
node_relations = []
136
137
for node in nodes.itervalues():
138
node.label = node.get_label()
139
if collapse:
140
visible_descendants = compact_descendants(descendants, ancestors)
141
else:
142
visible_descendants = descendants
143
144
for key, values in visible_descendants.iteritems():
145
for value in values:
146
node_relations.append((nodes[key], nodes[value]))
147
return node_relations
148
149
def get_committer(rev_id, source):
150
try:
151
committer = short_committer(source.get_revision(rev_id).committer)
152
except NoSuchRevision:
153
try:
154
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
155
if committer == '':
156
return None
157
except ValueError:
158
return None
159
if '@' in committer:
160
try:
161
committer = mail_map[committer]
162
except KeyError:
163
pass
164
try:
165
committer = committer_alias[committer]
166
except KeyError:
167
pass
168
return committer
169
170
class Grapher(object):
171
def __init__(self, branch, other_branch):
172
object.__init__(self)
173
self.branch = branch
174
self.other_branch = other_branch
175
greedy_fetch(branch, other_branch)
176
revision_a = self.branch.last_patch()
177
revision_b = self.other_branch.last_patch()
178
try:
179
self.root, self.ancestors, self.descendants, self.common = \
180
combined_graph(revision_a, revision_b, self.branch)
181
except bzrlib.errors.NoCommonRoot:
182
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
183
self.distances = node_distances(self.descendants, self.ancestors,
184
self.root)
185
self.base = select_farthest(self.distances, self.common)
186
self.n_history = branch.revision_history()
187
self.m_history = other_branch.revision_history()
188
189
def dot_node(self, node, num):
190
try:
191
n_rev = self.n_history.index(node) + 1
192
except ValueError:
193
n_rev = None
194
try:
195
m_rev = self.m_history.index(node) + 1
196
except ValueError:
197
m_rev = None
198
if (n_rev, m_rev) == (None, None):
199
name = node[-5:]
200
cluster = None
201
elif n_rev == m_rev:
202
name = "rR%d" % n_rev
203
else:
204
namelist = []
205
for prefix, revno in (('r', n_rev), ('R', m_rev)):
206
if revno is not None:
207
namelist.append("%s%d" % (prefix, revno))
208
name = ' '.join(namelist)
209
if None not in (n_rev, m_rev):
210
cluster = "common_history"
211
color = "#ff9900"
212
elif (None, None) == (n_rev, m_rev):
213
cluster = None
214
if node in self.common:
215
color = "#6699ff"
216
else:
217
color = None
218
elif n_rev is not None:
219
cluster = "my_history"
220
color = "#ffff00"
221
else:
222
assert m_rev is not None
223
cluster = "other_history"
224
color = "#ff0000"
225
if node == self.base:
226
color = "#33ff99"
227
228
label = [name]
229
committer = get_committer(node, self.branch)
230
if committer is not None:
231
label.append(committer)
232
233
if node in self.distances:
234
rank = self.distances[node]
235
label.append('d%d' % self.distances[node])
236
else:
237
rank = None
238
239
d_node = Node("n%d" % num, color=color, label="\\n".join(label),
240
rev_id=node, cluster=cluster)
241
d_node.rank = rank
242
243
if node not in self.ancestors:
244
d_node.node_style.append('dotted')
245
246
return d_node
247
248
def get_relations(self, collapse=False):
249
dot_nodes = {}
250
node_relations = []
251
num = 0
252
if collapse:
253
visible_ancestors = compact_ancestors(self.descendants,
254
self.ancestors, (self.base,))
255
else:
256
visible_ancestors = self.ancestors
257
for node, parents in visible_ancestors.iteritems():
258
if node not in dot_nodes:
259
dot_nodes[node] = self.dot_node(node, num)
260
num += 1
261
if visible_ancestors is self.ancestors:
262
parent_iter = ((f, 0) for f in parents)
263
else:
264
parent_iter = (f for f in parents.iteritems())
265
for parent, skipped in parent_iter:
266
if parent not in dot_nodes:
267
dot_nodes[parent] = self.dot_node(parent, num)
268
num += 1
269
edge = Edge(dot_nodes[parent], dot_nodes[node])
270
if skipped != 0:
271
edge.label = "%d" % skipped
272
node_relations.append(edge)
273
return node_relations
274
275
276
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
277
merge_branch=None, ranking="forced"):
278
b = Branch.open_containing(branch)
279
if merge_branch is None:
280
relations = graph_ancestry(b, collapse)
281
else:
282
m = Branch.open_containing(merge_branch)
283
grapher = Grapher(b, m)
284
relations = grapher.get_relations(collapse)
285
286
ext = filename.split('.')[-1]
287
output = dot_output(relations, ranking)
288
if antialias and ext in RSVG_OUTPUT_TYPES:
289
try:
290
invoke_dot_aa(output, filename, ext)
291
except NoDot, e:
292
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
293
" is installed correctly.")
294
except NoRsvg, e:
295
raise BzrCommandError("Can't find 'rsvg'. Please ensure "\
296
"librsvg-bin is installed correctly, or use --noantialias.")
297
elif ext in DOT_OUTPUT_TYPES:
298
try:
299
invoke_dot(output, filename, ext)
300
except NoDot, e:
301
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
302
" is installed correctly, or use --noantialias")
303
elif ext=='dot':
304
my_file = file(filename, 'wb')
305
for fragment in output:
306
my_file.write(fragment)
307
else:
308
print "Unknown file extension: %s" % ext
309
Loggerhead is a web-based interface for Breezy
Version: 2.0.1