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