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
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
3
21
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
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:
14
111
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
15
112
'abentley@panoramicfeedback.com': 'Aaron Bentley',
59
150
new_parent = list(ancestors[new_parent])[0]
61
152
new_ancestors[me][new_parent] = distance
64
155
def get_rev_info(rev_id, source):
65
"""Return the committer, message, and date of a revision."""
156
"""Return the committer, message, nick and date of a revision."""
69
161
if rev_id == 'null:':
70
return None, 'Null Revision', None
162
return None, 'Null Revision', None, None
72
164
rev = source.get_revision(rev_id)
73
165
except NoSuchRevision:
75
167
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
76
168
if committer == '':
77
return None, None, None
169
return None, None, None, None
78
170
except ValueError:
79
return None, None, None
171
return None, None, None, None
81
173
committer = short_committer(rev.committer)
82
174
if rev.message is not None:
83
175
message = rev.message.split('\n')[0]
84
176
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
85
177
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
86
179
if '@' in committer:
88
181
committer = mail_map[committer]
92
185
committer = committer_alias[committer]
95
return committer, message, date
188
return committer, message, nick, date
97
190
class Grapher(object):
98
192
def __init__(self, branch, other_branch=None):
99
193
object.__init__(self)
100
194
self.branch = branch
101
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)
102
203
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()
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)
112
self.root, self.ancestors, self.descendants = \
113
revision_graph(revision_a, branch)
116
self.n_history = branch.revision_history()
117
self.distances = node_distances(self.descendants, self.ancestors,
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,
119
210
if other_branch is not None:
120
211
self.base = select_farthest(self.distances, self.common)
121
self.m_history = other_branch.revision_history()
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)
124
223
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))
126
258
def dot_node(self, node, num):
185
331
d_node.node_style.append('dotted')
189
def get_relations(self, collapse=False):
335
def get_relations(self, collapse=False, max_distance=None):
191
337
node_relations = []
194
visible_ancestors = compact_ancestors(self.descendants,
195
self.ancestors, (self.base,))
340
exceptions = self.lcas.union([self.base, self.new_base])
341
visible_ancestors = compact_ancestors(self.descendants,
197
visible_ancestors = self.ancestors
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)
198
353
for node, parents in visible_ancestors.iteritems():
199
354
if node not in dot_nodes:
200
355
dot_nodes[node] = self.dot_node(node, num)
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:
357
for parent, skipped in parents.iteritems():
207
358
if parent not in dot_nodes:
208
359
dot_nodes[parent] = self.dot_node(parent, num)
217
368
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
218
merge_branch=None, ranking="forced"):
219
b = Branch.open_containing(branch)
369
merge_branch=None, ranking="forced", max_distance=None):
370
b = Branch.open_containing(branch)[0]
220
371
if merge_branch is not None:
221
m = Branch.open_containing(merge_branch)
372
m = Branch.open_containing(merge_branch)[0]
224
grapher = Grapher(b, m)
225
relations = grapher.get_relations(collapse)
380
grapher = Grapher(b, m)
381
relations = grapher.get_relations(collapse, max_distance)
227
388
ext = filename.split('.')[-1]
228
389
output = dot_output(relations, ranking)
230
391
if ext not in RSVG_OUTPUT_TYPES:
231
392
antialias = False
233
394
output = list(output)
235
396
invoke_dot_aa(output, filename, ext)
added
removed
graph.py
