1
# Copyright (C) 2005, 2008 Aaron Bentley
2
# <aaron@aaronbentley.com>
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.
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.
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
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
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
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
14
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
112
15
'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
16
'abentley@lappy' : 'Aaron Bentley',
160
69
if rev_id == 'null:':
161
return None, 'Null Revision', None, None
70
return None, 'Null Revision', None
163
72
rev = source.get_revision(rev_id)
164
73
except NoSuchRevision:
166
75
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
167
76
if committer == '':
168
return None, None, None, None
77
return None, None, None
169
78
except ValueError:
170
return None, None, None, None
79
return None, None, None
172
81
committer = short_committer(rev.committer)
173
82
if rev.message is not None:
174
83
message = rev.message.split('\n')[0]
175
84
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
176
85
date = time.strftime('%Y/%m/%d', gmtime)
177
nick = rev.properties.get('branch-nick')
178
86
if '@' in committer:
180
88
committer = mail_map[committer]
184
92
committer = committer_alias[committer]
187
return committer, message, nick, date
95
return committer, message, date
189
97
class Grapher(object):
191
98
def __init__(self, branch, other_branch=None):
192
99
object.__init__(self)
193
100
self.branch = branch
194
101
self.other_branch = other_branch
102
revision_a = self.branch.last_revision()
195
103
if other_branch is not None:
196
other_repo = other_branch.repository
104
greedy_fetch(branch, other_branch)
197
105
revision_b = self.other_branch.last_revision()
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)
201
self.graph = self.branch.repository.get_graph(other_repo)
202
revision_a = self.branch.last_revision()
203
self.scan_graph(revision_a, revision_b)
112
self.root, self.ancestors, self.descendants = \
113
revision_graph(revision_a, branch)
204
116
self.n_history = branch.revision_history()
205
self.n_revnos = branch.get_revision_id_to_revno_map()
206
self.distances = node_distances(self.descendants, self.ancestors,
117
self.distances = node_distances(self.descendants, self.ancestors,
208
119
if other_branch is not None:
209
120
self.base = select_farthest(self.distances, self.common)
210
self.m_history = other_branch.revision_history()
211
self.m_revnos = other_branch.get_revision_id_to_revno_map()
212
self.new_base = self.graph.find_unique_lca(revision_a,
214
self.lcas = self.graph.find_lca(revision_a, revision_b)
121
self.m_history = other_branch.revision_history()
219
124
self.m_history = []
222
def scan_graph(self, revision_a, revision_b):
223
a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
224
self.ancestors = a_ancestors
225
self.root = NULL_REVISION
226
if revision_b is not None:
227
b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
228
self.common = set(a_ancestors.keys())
229
self.common.intersection_update(b_ancestors)
230
self.ancestors.update(b_ancestors)
234
self.descendants = {}
236
for revision, parents in self.ancestors.iteritems():
237
self.descendants.setdefault(revision, [])
240
parents = [NULL_REVISION]
241
for parent in parents:
242
self.descendants.setdefault(parent, []).append(revision)
244
self.ancestors[ghost] = [NULL_REVISION]
247
def _get_revno_str(prefix, revno_map, revision_id):
249
revno = revno_map[revision_id]
252
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
254
126
def dot_node(self, node, num):
327
185
d_node.node_style.append('dotted')
331
def get_relations(self, collapse=False, max_distance=None):
189
def get_relations(self, collapse=False):
333
191
node_relations = []
336
exceptions = self.lcas.union([self.base, self.new_base])
337
visible_ancestors = compact_ancestors(self.descendants,
194
visible_ancestors = compact_ancestors(self.descendants,
195
self.ancestors, (self.base,))
341
visible_ancestors = {}
342
for revision, parents in self.ancestors.iteritems():
343
visible_ancestors[revision] = dict((p, 0) for p in parents)
344
if max_distance is not None:
345
min_distance = max(self.distances.values()) - max_distance
346
visible_ancestors = dict((n, p) for n, p in
347
visible_ancestors.iteritems() if
348
self.distances[n] >= min_distance)
197
visible_ancestors = self.ancestors
349
198
for node, parents in visible_ancestors.iteritems():
350
199
if node not in dot_nodes:
351
200
dot_nodes[node] = self.dot_node(node, num)
353
for parent, skipped in parents.iteritems():
202
if visible_ancestors is self.ancestors:
203
parent_iter = ((f, 0) for f in parents)
205
parent_iter = (f for f in parents.iteritems())
206
for parent, skipped in parent_iter:
354
207
if parent not in dot_nodes:
355
208
dot_nodes[parent] = self.dot_node(parent, num)
364
217
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
365
merge_branch=None, ranking="forced", max_distance=None):
218
merge_branch=None, ranking="forced"):
366
219
b = Branch.open_containing(branch)[0]
367
220
if merge_branch is not None:
368
221
m = Branch.open_containing(merge_branch)[0]
376
grapher = Grapher(b, m)
377
relations = grapher.get_relations(collapse, max_distance)
224
grapher = Grapher(b, m)
225
relations = grapher.get_relations(collapse)
384
227
ext = filename.split('.')[-1]
385
228
output = dot_output(relations, ranking)
387
230
if ext not in RSVG_OUTPUT_TYPES:
388
231
antialias = False
390
233
output = list(output)
392
235
invoke_dot_aa(output, filename, ext)
added
removed
graph.py
