« back to all changes in this revision
Viewing changes to graph.py
- browse files at revision 152.1.2
- compare with another revision
- download diff
- download tarball
- view history from revision 152.1.2
- Committer: Aaron Bentley
- Date: 2005-09-13 22:49:40 UTC
- mto: (147.1.21)
- mto: This revision was merged to the branch mainline in revision 154.
- Revision ID: abentley@panoramicfeedback.com-20050913224940-c6db07f39dd303be
Updated docs, obsoleted old executibles
- files added:
- .bzrignore
- files removed:
- .be/bugs/4ddc9130-fe72-4d0c-9848-157ad6f2c14d
- .be/bugs/7c3b4f3e-33c5-4112-b8df-c209ec6cc8b6
- files renamed:
- fetch_ghosts.py => fetch_missing.py
- files modified:
- INSTALL
added
removed
graph.py
1
# Copyright (C) 2005 Aaron Bentley
2
# <aaron.bentley@utoronto.ca>
3
#
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.
8
#
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.
13
#
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
17
1
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
2
from dotgraph import mail_map
19
3
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
4
from bzrlib.errors import BzrCommandError
25
5
import bzrlib.errors
26
6
import re
27
7
import os.path
28
import time
29
30
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
31
'abentley@panoramicfeedback.com': 'Aaron Bentley',
32
'abentley@lappy' : 'Aaron Bentley',
33
'john@arbash-meinel.com' : 'John Arbash Meinel',
34
'mbp@sourcefrog.net' : 'Martin Pool',
35
'robertc@robertcollins.net' : 'Robert Collins',
36
}
37
38
committer_alias = {'abentley': 'Aaron Bentley'}
8
9
mail_map.update({'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
10
'abentley@panoramicfeedback.com': 'Aaron Bentley',
11
'abentley@lappy' : 'Aaron Bentley',
12
'john@arbash-meinel.com' : 'John Arbash Meinel',
13
'mbp@sourcefrog.net' : 'Martin Pool',
14
'robertc@robertcollins.net' : 'Robert Collins',
15
})
16
17
def add_relations(rev_id):
18
if rev_id in ancestors:
19
return
20
print rev_id
21
if rev_id not in nodes:
22
nodes[rev_id] = Node("n%d" % counter, label = rev_id)
23
counter += 1
24
revision = branch.get_revision(rev_id)
25
ancestors [rev_id] = []
26
for p in (p.revision_id for p in revision.parents):
27
add_relations(p)
28
if p not in descendants:
29
descendants[p] = []
30
descendants[p].append(rev_id)
31
ancestors [rev_id].append(rev_id)
32
39
33
def short_committer(committer):
40
34
new_committer = re.sub('<.*>', '', committer).strip(' ')
41
35
if len(new_committer) < 2:
45
39
def can_skip(rev_id, descendants, ancestors):
46
40
if rev_id not in descendants:
47
41
return False
48
elif rev_id not in ancestors:
49
return False
50
42
elif len(ancestors[rev_id]) != 1:
51
43
return False
52
elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
44
elif len(descendants[ancestors[rev_id][0]]) != 1:
53
45
return False
54
46
elif len(descendants[rev_id]) != 1:
55
47
return False
56
48
else:
57
49
return True
58
50
59
def compact_ancestors(descendants, ancestors, exceptions=()):
60
new_ancestors={}
51
def compact_descendants(descendants, ancestors):
52
new_descendants={}
61
53
skip = set()
62
for me, my_parents in ancestors.iteritems():
54
for me, my_descendants in descendants.iteritems():
63
55
if me in skip:
64
56
continue
65
new_ancestors[me] = {}
66
for parent in my_parents:
67
new_parent = parent
68
distance = 0
69
while can_skip(new_parent, descendants, ancestors):
70
if new_parent in exceptions:
71
break
72
skip.add(new_parent)
73
if new_parent in new_ancestors:
74
del new_ancestors[new_parent]
75
new_parent = list(ancestors[new_parent])[0]
76
distance += 1
77
new_ancestors[me][new_parent] = distance
78
return new_ancestors
79
80
def get_rev_info(rev_id, source):
81
"""Return the committer, message, and date of a revision."""
82
committer = None
83
message = None
84
date = None
85
if rev_id == 'null:':
86
return None, 'Null Revision', None
87
try:
88
rev = source.get_revision(rev_id)
89
except NoSuchRevision:
90
try:
91
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
92
if committer == '':
93
return None, None, None
94
except ValueError:
95
return None, None, None
96
else:
97
committer = short_committer(rev.committer)
98
if rev.message is not None:
99
message = rev.message.split('\n')[0]
100
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
101
date = time.strftime('%Y/%m/%d', gmtime)
102
if '@' in committer:
103
try:
104
committer = mail_map[committer]
105
except KeyError:
106
pass
107
try:
108
committer = committer_alias[committer]
109
except KeyError:
110
pass
111
return committer, message, date
112
113
class Grapher(object):
114
def __init__(self, branch, other_branch=None):
115
object.__init__(self)
116
self.branch = branch
117
self.other_branch = other_branch
118
revision_a = self.branch.last_revision()
119
if other_branch is not None:
120
greedy_fetch(branch, other_branch)
121
revision_b = self.other_branch.last_revision()
57
new_descendants[me] = []
58
for descendant in my_descendants:
59
new_descendant = descendant
60
while can_skip(new_descendant, descendants, ancestors):
61
skip.add(new_descendant)
62
if new_descendant in new_descendants:
63
del new_descendants[new_descendant]
64
new_descendant = descendants[new_descendant][0]
65
new_descendants[me].append(new_descendant)
66
return new_descendants
67
68
69
def graph_ancestry(branch, collapse=True):
70
nodes = {}
71
q = ((i+1, n) for (i, n) in enumerate(branch.revision_history()))
72
r = 1
73
try:
74
branch_name = os.path.basename(branch.base)
75
except AttributeError:
76
branch_name = "main"
77
for (revno, rev_id) in q:
78
nodes[rev_id] = Node("R%d" % revno, color="#ffff00", rev_id=rev_id,
79
cluster=branch_name)
80
81
ancestors = {}
82
descendants = {}
83
counter = 0
84
lines = [branch.last_patch()]
85
while len(lines) > 0:
86
new_lines = set()
87
for rev_id in lines:
88
if rev_id not in nodes:
89
nodes[rev_id] = Node("n%d" % counter, label=rev_id,
90
rev_id=rev_id)
91
counter+=1
92
122
93
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)
127
else:
128
self.root, self.ancestors, self.descendants = \
129
revision_graph(revision_a, branch)
130
self.common = []
131
132
self.n_history = branch.revision_history()
133
self.distances = node_distances(self.descendants, self.ancestors,
134
self.root)
135
if other_branch is not None:
136
self.base = select_farthest(self.distances, self.common)
137
self.m_history = other_branch.revision_history()
138
else:
139
self.base = None
140
self.m_history = []
141
142
def dot_node(self, node, num):
143
try:
144
n_rev = self.n_history.index(node) + 1
145
except ValueError:
146
n_rev = None
147
try:
148
m_rev = self.m_history.index(node) + 1
149
except ValueError:
150
m_rev = None
151
if (n_rev, m_rev) == (None, None):
152
name = node[-5:]
153
cluster = None
154
elif n_rev == m_rev:
155
name = "rR%d" % n_rev
156
else:
157
namelist = []
158
for prefix, revno in (('r', n_rev), ('R', m_rev)):
159
if revno is not None:
160
namelist.append("%s%d" % (prefix, revno))
161
name = ' '.join(namelist)
162
if None not in (n_rev, m_rev):
163
cluster = "common_history"
164
color = "#ff9900"
165
elif (None, None) == (n_rev, m_rev):
166
cluster = None
167
if node in self.common:
168
color = "#6699ff"
169
else:
170
color = "white"
171
elif n_rev is not None:
172
cluster = "my_history"
173
color = "#ffff00"
174
else:
175
assert m_rev is not None
176
cluster = "other_history"
177
color = "#ff0000"
178
if node == self.base:
179
color = "#33ff99"
180
181
label = [name]
182
committer, message, date = get_rev_info(node, self.branch)
183
if committer is not None:
184
label.append(committer)
185
186
if date is not None:
187
label.append(date)
188
189
if node in self.distances:
190
rank = self.distances[node]
191
label.append('d%d' % self.distances[node])
192
else:
193
rank = None
194
195
d_node = Node("n%d" % num, color=color, label="\\n".join(label),
196
rev_id=node, cluster=cluster, message=message,
197
date=date)
198
d_node.rank = rank
199
200
if node not in self.ancestors:
201
d_node.node_style.append('dotted')
202
203
return d_node
204
205
def get_relations(self, collapse=False):
206
dot_nodes = {}
207
node_relations = []
208
num = 0
209
if collapse:
210
visible_ancestors = compact_ancestors(self.descendants,
211
self.ancestors, (self.base,))
212
else:
213
visible_ancestors = self.ancestors
214
for node, parents in visible_ancestors.iteritems():
215
if node not in dot_nodes:
216
dot_nodes[node] = self.dot_node(node, num)
217
num += 1
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:
223
if parent not in dot_nodes:
224
dot_nodes[parent] = self.dot_node(parent, num)
225
num += 1
226
edge = Edge(dot_nodes[parent], dot_nodes[node])
227
if skipped != 0:
228
edge.label = "%d" % skipped
229
node_relations.append(edge)
230
return node_relations
231
232
233
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
234
merge_branch=None, ranking="forced"):
235
b = Branch.open_containing(branch)[0]
236
if merge_branch is not None:
237
m = Branch.open_containing(merge_branch)[0]
94
revision = branch.get_revision(rev_id)
95
except bzrlib.errors.NoSuchRevision:
96
nodes[rev_id].node_style.append('dotted')
97
continue
98
if nodes[rev_id].committer is None:
99
nodes[rev_id].committer = short_committer(revision.committer)
100
parent_ids = [r.revision_id for r in revision.parents]
101
ancestors [rev_id] = parent_ids
102
for parent in parent_ids:
103
if parent not in ancestors:
104
new_lines.add(parent)
105
descendants[parent] = []
106
descendants[parent].append(rev_id)
107
lines = new_lines
108
node_relations = []
109
110
if collapse:
111
visible_descendants = compact_descendants(descendants, ancestors)
238
112
else:
239
m = None
240
b.lock_read()
241
try:
242
if m is not None:
243
m.lock_read()
244
try:
245
grapher = Grapher(b, m)
246
relations = grapher.get_relations(collapse)
247
finally:
248
if m is not None:
249
m.unlock()
250
finally:
251
b.unlock()
113
visible_descendants = descendants
114
115
for key, values in visible_descendants.iteritems():
116
for value in values:
117
node_relations.append((nodes[key], nodes[value]))
118
return node_relations
252
119
120
def write_ancestry_file(branch, filename, collapse=True, antialias=True):
121
b = Branch(branch)
122
relations = graph_ancestry(b, collapse)
253
123
ext = filename.split('.')[-1]
254
output = dot_output(relations, ranking)
255
done = False
256
if ext not in RSVG_OUTPUT_TYPES:
257
antialias = False
258
if antialias:
259
output = list(output)
124
if antialias and ext in ('png', 'jpg'):
260
125
try:
261
invoke_dot_aa(output, filename, ext)
262
done = True
126
invoke_dot_aa(dot_output(relations), filename, ext)
263
127
except NoDot, e:
264
128
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
265
129
" is installed correctly.")
266
130
except NoRsvg, e:
267
print "Not antialiasing because rsvg (from librsvg-bin) is not"\
268
" installed."
269
antialias = False
270
if ext in DOT_OUTPUT_TYPES and not antialias and not done:
271
try:
272
invoke_dot(output, filename, ext)
273
done = True
274
except NoDot, e:
275
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
276
" is installed correctly, or use --noantialias")
277
elif ext == 'dot' and not done:
278
my_file = file(filename, 'wb')
279
for fragment in output:
280
my_file.write(fragment)
281
elif ext == 'html':
282
try:
283
invoke_dot_html(output, filename)
284
except NoDot, e:
285
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
286
" is installed correctly, or use --noantialias")
287
elif not done:
131
raise BzrCommandError("Can't find 'rsvg'. Please ensure "\
132
"librsvg-bin is installed correctly, or use --noantialias.")
133
elif ext in ('svg', 'svgz', 'gif', 'jpg', 'ps', 'fig', 'mif', 'png'):
134
try:
135
invoke_dot(dot_output(relations), filename, ext)
136
except NoDot, e:
137
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
138
" is installed correctly, or use --noantialias")
139
elif ext=='dot':
140
file(filename, 'wb').write("".join(list(dot_output(relations))))
141
else:
288
142
print "Unknown file extension: %s" % ext
289
143
Loggerhead is a web-based interface for Breezy
Version: 2.0.1