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
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
21
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
30
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
112
31
'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
32
'abentley@lappy' : 'Aaron Bentley',
150
75
new_parent = list(ancestors[new_parent])[0]
152
77
new_ancestors[me][new_parent] = distance
155
80
def get_rev_info(rev_id, source):
156
"""Return the committer, message, nick and date of a revision."""
81
"""Return the committer, message, and date of a revision."""
161
85
if rev_id == 'null:':
162
return None, 'Null Revision', None, None
86
return None, 'Null Revision', None
164
88
rev = source.get_revision(rev_id)
165
89
except NoSuchRevision:
167
91
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
168
92
if committer == '':
169
return None, None, None, None
93
return None, None, None
170
94
except ValueError:
171
return None, None, None, None
95
return None, None, None
173
97
committer = short_committer(rev.committer)
174
98
if rev.message is not None:
175
99
message = rev.message.split('\n')[0]
176
100
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
177
101
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
179
102
if '@' in committer:
181
104
committer = mail_map[committer]
185
108
committer = committer_alias[committer]
188
return committer, message, nick, date
111
return committer, message, date
190
113
class Grapher(object):
192
114
def __init__(self, branch, other_branch=None):
193
115
object.__init__(self)
194
116
self.branch = branch
195
117
self.other_branch = other_branch
118
revision_a = self.branch.last_revision()
196
119
if other_branch is not None:
197
other_repo = other_branch.repository
120
greedy_fetch(branch, other_branch)
198
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)
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,
128
self.root, self.ancestors, self.descendants = \
129
revision_graph(revision_a, branch)
132
self.n_history = branch.revision_history()
133
self.distances = node_distances(self.descendants, self.ancestors,
210
135
if other_branch is not None:
211
136
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)
137
self.m_history = other_branch.revision_history()
223
140
self.m_history = []
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
142
def dot_node(self, node, num):
331
201
d_node.node_style.append('dotted')
335
def get_relations(self, collapse=False, max_distance=None):
205
def get_relations(self, collapse=False):
337
207
node_relations = []
340
exceptions = self.lcas.union([self.base, self.new_base])
341
visible_ancestors = compact_ancestors(self.descendants,
210
visible_ancestors = compact_ancestors(self.descendants,
211
self.ancestors, (self.base,))
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)
213
visible_ancestors = self.ancestors
353
214
for node, parents in visible_ancestors.iteritems():
354
215
if node not in dot_nodes:
355
216
dot_nodes[node] = self.dot_node(node, num)
357
for parent, skipped in parents.iteritems():
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:
358
223
if parent not in dot_nodes:
359
224
dot_nodes[parent] = self.dot_node(parent, num)
368
233
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
369
merge_branch=None, ranking="forced", max_distance=None):
234
merge_branch=None, ranking="forced"):
370
235
b = Branch.open_containing(branch)[0]
371
236
if merge_branch is not None:
372
237
m = Branch.open_containing(merge_branch)[0]
377
242
if m is not None:
380
245
grapher = Grapher(b, m)
381
relations = grapher.get_relations(collapse, max_distance)
246
relations = grapher.get_relations(collapse)
383
248
if m is not None:
410
275
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
411
" is installed correctly.")
276
" is installed correctly, or use --noantialias")
412
277
elif ext == 'dot' and not done:
413
278
my_file = file(filename, 'wb')
414
279
for fragment in output:
415
my_file.write(fragment.encode('utf-8'))
280
my_file.write(fragment)
416
281
elif ext == 'html':
418
283
invoke_dot_html(output, filename)
420
285
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
421
" is installed correctly.")
286
" is installed correctly, or use --noantialias")
423
288
print "Unknown file extension: %s" % ext
added
removed
graph.py
