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 bzrtools import short_committer
18
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
19
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
20
from bzrlib.branch import Branch
21
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
22
from bzrlib.fetch import greedy_fetch
23
from bzrlib.graph import node_distances, select_farthest
24
from bzrlib.revision import combined_graph, revision_graph
25
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
31
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
112
32
'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
33
'abentley@lappy' : 'Aaron Bentley',
150
70
new_parent = list(ancestors[new_parent])[0]
152
72
new_ancestors[me][new_parent] = distance
155
75
def get_rev_info(rev_id, source):
156
"""Return the committer, message, nick and date of a revision."""
76
"""Return the committer, message, and date of a revision."""
161
80
if rev_id == 'null:':
162
return None, 'Null Revision', None, None
81
return None, 'Null Revision', None
164
83
rev = source.get_revision(rev_id)
165
84
except NoSuchRevision:
167
86
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
168
87
if committer == '':
169
return None, None, None, None
88
return None, None, None
170
89
except ValueError:
171
return None, None, None, None
90
return None, None, None
173
92
committer = short_committer(rev.committer)
174
93
if rev.message is not None:
175
94
message = rev.message.split('\n')[0]
176
95
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
177
96
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
179
97
if '@' in committer:
181
99
committer = mail_map[committer]
185
103
committer = committer_alias[committer]
188
return committer, message, nick, date
106
return committer, message, date
190
108
class Grapher(object):
192
109
def __init__(self, branch, other_branch=None):
193
110
object.__init__(self)
194
111
self.branch = branch
195
112
self.other_branch = other_branch
113
revision_a = self.branch.last_revision()
196
114
if other_branch is not None:
197
other_repo = other_branch.repository
115
greedy_fetch(branch, other_branch)
198
116
revision_b = self.other_branch.last_revision()
118
self.root, self.ancestors, self.descendants, self.common = \
119
combined_graph(revision_a, revision_b,
120
self.branch.repository)
121
except bzrlib.errors.NoCommonRoot:
122
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)
124
self.root, self.ancestors, self.descendants = \
125
revision_graph(revision_a, branch.repository)
205
128
self.n_history = branch.revision_history()
206
self.n_revnos = branch.get_revision_id_to_revno_map()
207
self.distances = node_distances(self.descendants, self.ancestors,
129
self.distances = node_distances(self.descendants, self.ancestors,
209
131
if other_branch is not None:
210
132
self.base = select_farthest(self.distances, self.common)
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)
133
self.m_history = other_branch.revision_history()
220
136
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))
255
138
def dot_node(self, node, num):
328
197
d_node.node_style.append('dotted')
332
def get_relations(self, collapse=False, max_distance=None):
201
def get_relations(self, collapse=False):
334
203
node_relations = []
337
exceptions = self.lcas.union([self.base, self.new_base])
338
visible_ancestors = compact_ancestors(self.descendants,
206
visible_ancestors = compact_ancestors(self.descendants,
207
self.ancestors, (self.base,))
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)
209
visible_ancestors = self.ancestors
350
210
for node, parents in visible_ancestors.iteritems():
351
211
if node not in dot_nodes:
352
212
dot_nodes[node] = self.dot_node(node, num)
354
for parent, skipped in parents.iteritems():
214
if visible_ancestors is self.ancestors:
215
parent_iter = ((f, 0) for f in parents)
217
parent_iter = (f for f in parents.iteritems())
218
for parent, skipped in parent_iter:
355
219
if parent not in dot_nodes:
356
220
dot_nodes[parent] = self.dot_node(parent, num)
407
271
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
408
" is installed correctly.")
272
" is installed correctly, or use --noantialias")
409
273
elif ext == 'dot' and not done:
410
274
my_file = file(filename, 'wb')
411
275
for fragment in output:
412
my_file.write(fragment.encode('utf-8'))
276
my_file.write(fragment)
413
277
elif ext == 'html':
415
279
invoke_dot_html(output, filename)
417
281
raise BzrCommandError("Can't find 'dot'. Please ensure Graphviz"\
418
" is installed correctly.")
282
" is installed correctly, or use --noantialias")
420
284
print "Unknown file extension: %s" % ext
added
removed
graph.py
