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.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
69
new_parent = list(ancestors[new_parent])[0]
152
71
new_ancestors[me][new_parent] = distance
155
74
def get_rev_info(rev_id, source):
156
"""Return the committer, message, nick and date of a revision."""
75
"""Return the committer, message, and date of a revision."""
161
79
if rev_id == 'null:':
162
return None, 'Null Revision', None, None
80
return None, 'Null Revision', None
164
82
rev = source.get_revision(rev_id)
165
83
except NoSuchRevision:
167
85
committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
168
86
if committer == '':
169
return None, None, None, None
87
return None, None, None
170
88
except ValueError:
171
return None, None, None, None
89
return None, None, None
173
91
committer = short_committer(rev.committer)
174
92
if rev.message is not None:
175
93
message = rev.message.split('\n')[0]
176
94
gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
177
95
date = time.strftime('%Y/%m/%d', gmtime)
178
nick = rev.properties.get('branch-nick')
179
96
if '@' in committer:
181
98
committer = mail_map[committer]
185
102
committer = committer_alias[committer]
188
return committer, message, nick, date
105
return committer, message, date
190
107
class Grapher(object):
192
108
def __init__(self, branch, other_branch=None):
193
109
object.__init__(self)
194
110
self.branch = branch
195
111
self.other_branch = other_branch
112
revision_a = self.branch.last_revision()
196
113
if other_branch is not None:
197
other_repo = other_branch.repository
114
branch.fetch(other_branch)
198
115
revision_b = self.other_branch.last_revision()
117
self.root, self.ancestors, self.descendants, self.common = \
118
combined_graph(revision_a, revision_b,
119
self.branch.repository)
120
except bzrlib.errors.NoCommonRoot:
121
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,
123
self.root, self.ancestors, self.descendants = \
124
revision_graph(revision_a, branch.repository)
127
self.n_history = branch.revision_history()
128
self.distances = node_distances(self.descendants, self.ancestors,
210
130
if other_branch is not None:
211
131
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)
132
self.m_history = other_branch.revision_history()
223
135
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
137
def dot_node(self, node, num):
331
196
d_node.node_style.append('dotted')
335
def get_relations(self, collapse=False, max_distance=None):
200
def get_relations(self, collapse=False):
337
202
node_relations = []
340
exceptions = self.lcas.union([self.base, self.new_base])
341
visible_ancestors = compact_ancestors(self.descendants,
205
visible_ancestors = compact_ancestors(self.descendants,
206
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)
208
visible_ancestors = self.ancestors
353
209
for node, parents in visible_ancestors.iteritems():
354
210
if node not in dot_nodes:
355
211
dot_nodes[node] = self.dot_node(node, num)
357
for parent, skipped in parents.iteritems():
213
if visible_ancestors is self.ancestors:
214
parent_iter = ((f, 0) for f in parents)
216
parent_iter = (f for f in parents.iteritems())
217
for parent, skipped in parent_iter:
358
218
if parent not in dot_nodes:
359
219
dot_nodes[parent] = self.dot_node(parent, num)
added
removed
graph.py
