14
14
# You should have received a copy of the GNU General Public License
15
15
# along with this program; if not, write to the Free Software
16
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
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
19
21
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
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:
30
111
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
31
112
'abentley@panoramicfeedback.com': 'Aaron Bentley',
75
150
new_parent = list(ancestors[new_parent])[0]
77
152
new_ancestors[me][new_parent] = distance
80
155
def get_rev_info(rev_id, source):
81
"""Return the committer, message, and date of a revision."""
156
"""Return the committer, message, nick and date of a revision."""
85
161
if rev_id == 'null:':
86
return None, 'Null Revision', None
162
return None, 'Null Revision', None, None
88
164
rev = source.get_revision(rev_id)
89
165
except NoSuchRevision:
91
167
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
92
168
if committer == '':
93
return None, None, None
169
return None, None, None, None
94
170
except ValueError:
95
return None, None, None
171
return None, None, None, None
97
173
committer = short_committer(rev.committer)
98
174
if rev.message is not None:
99
175
message = rev.message.split('\n')[0]
100
176
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
101
177
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
102
179
if '@' in committer:
104
181
committer = mail_map[committer]
108
185
committer = committer_alias[committer]
111
return committer, message, date
188
return committer, message, nick, date
113
190
class Grapher(object):
114
192
def __init__(self, branch, other_branch=None):
115
193
object.__init__(self)
116
194
self.branch = branch
117
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)
118
203
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()
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)
128
self.root, self.ancestors, self.descendants = \
129
revision_graph(revision_a, branch)
204
self.scan_graph(revision_a, revision_b)
132
205
self.n_history = branch.revision_history()
133
self.distances = node_distances(self.descendants, self.ancestors,
206
self.n_revnos = branch.get_revision_id_to_revno_map()
207
self.distances = node_distances(self.descendants, self.ancestors,
135
209
if other_branch is not None:
136
210
self.base = select_farthest(self.distances, self.common)
137
self.m_history = other_branch.revision_history()
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)
140
220
self.m_history = []
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))
142
255
def dot_node(self, node, num):
201
328
d_node.node_style.append('dotted')
205
def get_relations(self, collapse=False):
332
def get_relations(self, collapse=False, max_distance=None):
207
334
node_relations = []
210
visible_ancestors = compact_ancestors(self.descendants,
211
self.ancestors, (self.base,))
337
exceptions = self.lcas.union([self.base, self.new_base])
338
visible_ancestors = compact_ancestors(self.descendants,
213
visible_ancestors = self.ancestors
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)
214
350
for node, parents in visible_ancestors.iteritems():
215
351
if node not in dot_nodes:
216
352
dot_nodes[node] = self.dot_node(node, num)
218
if visible_ancestors is self.ancestors:
219
parent_iter = ((f, 0) for f in parents)
221
parent_iter = (f for f in parents.iteritems())
222
for parent, skipped in parent_iter:
354
for parent, skipped in parents.iteritems():
223
355
if parent not in dot_nodes:
224
356
dot_nodes[parent] = self.dot_node(parent, num)
233
365
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
234
merge_branch=None, ranking="forced"):
366
merge_branch=None, ranking="forced", max_distance=None):
235
367
b = Branch.open_containing(branch)[0]
236
368
if merge_branch is not None:
237
369
m = Branch.open_containing(merge_branch)[0]
242
374
if m is not None:
245
377
grapher = Grapher(b, m)
246
relations = grapher.get_relations(collapse)
378
relations = grapher.get_relations(collapse, max_distance)
248
380
if m is not None:
275
407
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
276
" is installed correctly, or use --noantialias")
408
" is installed correctly.")
277
409
elif ext == 'dot' and not done:
278
410
my_file = file(filename, 'wb')
279
411
for fragment in output:
280
my_file.write(fragment)
412
my_file.write(fragment.encode('utf-8'))
281
413
elif ext == 'html':
283
415
invoke_dot_html(output, filename)
285
417
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
286
" is installed correctly, or use --noantialias")
418
" is installed correctly.")
288
420
print "Unknown file extension: %s" % ext
added
removed
graph.py
