1
# Modified for use with Olive:
2
# Copyright (C) 2006 by Szilveszter Farkas (Phanatic) <szilveszter.farkas@gmail.com>
3
# Original copyright holder:
4
# Copyright (C) 2005 by Canonical Ltd. (Scott James Remnant <scott@ubuntu.com>)
6
# This program is free software; you can redistribute it and/or modify
7
# it under the terms of the GNU General Public License as published by
8
# the Free Software Foundation; either version 2 of the License, or
9
# (at your option) any later version.
11
# This program is distributed in the hope that it will be useful,
12
# but WITHOUT ANY WARRANTY; without even the implied warranty of
13
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
# GNU General Public License for more details.
16
# You should have received a copy of the GNU General Public License
17
# along with this program; if not, write to the Free Software
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
"""Directed graph production.
22
This module contains the code to produce an ordered directed graph of a
23
bzr branch, such as we display in the tree view at the top of the bzrk
27
__copyright__ = "Copyright © 2005 Canonical Ltd."
28
__author__ = "Scott James Remnant <scott@ubuntu.com>"
31
from bzrlib.tsort import merge_sort
34
class DummyRevision(object):
35
"""Dummy bzr revision.
37
Sometimes, especially in older bzr branches, a revision is referenced
38
as the parent of another but not actually present in the branch's store.
39
When this happens we use an instance of this class instead of the real
40
Revision object (which we can't get).
43
def __init__(self, revid):
44
self.revision_id = revid
47
self.message = self.revision_id
50
class RevisionProxy(object):
51
"""A revision proxy object.
53
This will demand load the revision it represents when the committer or
54
message attributes are accessed in order to populate them. It is
55
constructed with the revision id and parent_ids list and a repository
56
object to request the revision from when needed.
59
def __init__(self, revid, parent_ids, repository):
60
self.revision_id = revid
61
self.parent_ids = parent_ids
62
self._repository = repository
65
def _get_attribute_getter(attr):
66
def get_attribute(self):
67
if self._revision is None:
69
return getattr(self._revision, attr)
71
committer = property(_get_attribute_getter('committer'))
72
message = property(_get_attribute_getter('message'))
73
properties = property(_get_attribute_getter('properties'))
74
timestamp = property(_get_attribute_getter('timestamp'))
75
timezone = property(_get_attribute_getter('timezone'))
78
"""Load the revision object."""
79
self._revision = self._repository.get_revision(self.revision_id)
82
class DistanceMethod(object):
84
def __init__(self, branch, start):
89
self.children_of_id = {start: set()}
90
self.parent_ids_of = {}
91
self.colours = { start: 0 }
93
self.direct_parent_of = {}
96
def fill_caches(self):
97
graph = self.branch.repository.get_revision_graph_with_ghosts([self.start])
98
for revid in graph.ghosts:
99
self.cache_revision(DummyRevision(revid))
100
for revid, parents in graph.get_ancestors().items():
101
self.cache_revision(RevisionProxy(revid, parents, self.branch.repository))
103
def cache_revision(self, revision):
104
"Set the caches for a newly retrieved revision."""
105
revid = revision.revision_id
106
# Build a revision cache
107
self.revisions[revid] = revision
108
# Build a children dictionary
109
for parent_id in revision.parent_ids:
110
self.children_of_id.setdefault(parent_id, set()).add(revision)
111
# Build a parents dictionnary, where redundant parents will be removed,
112
# and that will be passed along tothe rest of program.
113
if len(revision.parent_ids) != len(set(revision.parent_ids)):
114
# fix the parent_ids list.
116
parent_ids_set = set()
117
for parent_id in revision.parent_ids:
118
if parent_id in parent_ids_set:
120
parent_ids.append(parent_id)
121
parent_ids_set.add(parent_id)
122
revision.parent_ids = parent_ids
123
self.parent_ids_of[revision] = list(revision.parent_ids)
124
self.graph[revid] = revision.parent_ids
126
def make_children_map(self):
127
revisions = self.revisions
128
return dict((revisions[revid], c)
129
for (revid, c) in self.children_of_id.iteritems())
131
def sort_revisions(self, sorted_revids, maxnum):
132
revisions = self.revisions
133
parent_ids_of = self.parent_ids_of
134
children_of_id = self.children_of_id
135
# Try to compact sequences of revisions on the same branch.
138
expected_id = sorted_revids[0]
141
revid = sorted_revids.pop(0)
142
if revid != expected_id:
143
skipped_revids.append(revid)
145
revision = revisions[revid]
146
for child in children_of_id[revid]:
147
# postpone if any child is missing
148
if child.revision_id not in distances:
149
if expected_id not in pending_ids:
150
pending_ids.append(expected_id)
151
expected_id = pending_ids.pop(0)
152
skipped_revids.append(revid)
153
sorted_revids[:0] = skipped_revids
154
del skipped_revids[:]
157
# all children are here, push!
158
distances[revid] = len(distances)
159
if maxnum is not None and len(distances) > maxnum:
160
# bail out early if a limit was specified
161
sorted_revids[:0] = skipped_revids
162
for revid in sorted_revids:
163
distances[revid] = len(distances)
165
# all parents will need to be pushed as soon as possible
166
for parent in parent_ids_of[revision]:
167
if parent not in pending_ids:
168
pending_ids.insert(0, parent)
171
expected_id = pending_ids.pop(0)
172
# if the next expected revid has already been skipped, requeue
173
# the skipped ids, except those that would go right back to the
175
if expected_id in skipped_revids:
176
pos = skipped_revids.index(expected_id)
177
sorted_revids[:0] = skipped_revids[pos:]
178
del skipped_revids[pos:]
179
self.distances = distances
180
return sorted(distances, key=distances.get)
182
def choose_colour(self, revid):
183
revision = self.revisions[revid]
184
children_of_id = self.children_of_id
185
parent_ids_of = self.parent_ids_of
186
colours = self.colours
188
the_children = children_of_id[revid]
189
if len(the_children) == 1:
190
[child] = the_children
191
if len(parent_ids_of[child]) == 1:
192
# one-one relationship between parent and child, same
194
colours[revid] = colours[child.revision_id]
196
self.choose_colour_one_child(revision, child)
198
self.choose_colour_many_children(revision, the_children)
200
def choose_colour_one_child(self, revision, child):
201
revid = revision.revision_id
202
direct_parent_of = self.direct_parent_of
203
revisions = self.revisions
204
# one child with multiple parents, the first parent with
205
# the same committer gets the colour
206
direct_parent = direct_parent_of.get(child)
207
if direct_parent is None:
208
# if it has not been found yet, find it now and remember
209
for parent_id in self.parent_ids_of[child]:
210
parent_revision = revisions[parent_id]
211
if parent_revision.committer == child.committer:
212
# found the first parent with the same committer
213
direct_parent = parent_revision
214
direct_parent_of[child] = direct_parent
216
if direct_parent == revision:
217
self.colours[revid] = self.colours[child.revision_id]
219
self.colours[revid] = self.last_colour = self.last_colour + 1
221
def choose_colour_many_children(self, revision, the_children):
222
"""Colour revision revision."""
223
revid = revision.revision_id
224
direct_parent_of = self.direct_parent_of
225
# multiple children, get the colour of the last displayed child
226
# with the same committer which does not already have its colour
229
for child in the_children:
230
if child.committer != revision.committer:
232
direct_parent = direct_parent_of.get(child)
233
if direct_parent == revision:
234
self.colours[revid] = self.colours[child.revision_id]
236
# FIXME: Colouring based on whats been displayed MUST be done with
237
# knowledge of the revisions being output.
238
# until the refactoring to fold graph() into this more compactly is
239
# done, I've disabled this reuse. RBC 20060403
240
# if direct_parent is None:
241
# available[child] = distances[child.revision_id]
242
# .. it will be something like available[child] = \
243
# revs[child.revision_id][0] - which is the sequence number
246
sorted_children = sorted(available, key=available.get)
247
child = sorted_children[-1]
248
direct_parent_of[child] = revision
249
self.colours[revid] = self.colours[child.revision_id]
251
# no candidate children is available, pick the next
253
self.colours[revid] = self.last_colour = self.last_colour + 1
256
def distances(branch, start):
257
"""Sort the revisions.
259
Traverses the branch revision tree starting at start and produces an
260
ordered list of revisions such that a revision always comes after
261
any revision it is the parent of.
263
Returns a tuple of (revids, revisions, colours, children)
265
distance = DistanceMethod(branch, start)
266
distance.fill_caches()
267
distance.merge_sorted = merge_sort(distance.graph, distance.start)
268
children = distance.make_children_map()
270
for seq, revid, merge_depth, end_of_merge in distance.merge_sorted:
271
distance.choose_colour(revid)
273
revisions = distance.revisions
274
colours = distance.colours
275
parent_ids_of = distance.parent_ids_of
276
return (revisions, colours, children, parent_ids_of, distance.merge_sorted)
279
def graph(revisions, colours, merge_sorted):
280
"""Produce a directed graph of a bzr branch.
282
For each revision it then yields a tuple of (revision, node, lines).
283
If the revision is only referenced in the branch and not present in the
284
store, revision will be a DummyRevision object, otherwise it is the bzr
285
Revision object with the meta-data for the revision.
287
Node is a tuple of (column, colour) with column being a zero-indexed
288
column number of the graph that this revision represents and colour
289
being a zero-indexed colour (which doesn't specify any actual colour
290
in particular) to draw the node in.
292
Lines is a list of tuples which represent lines you should draw away
293
from the revision, if you also need to draw lines into the revision
294
you should use the lines list from the previous iteration. Each
295
typle in the list is in the form (start, end, colour) with start and
296
end being zero-indexed column numbers and colour as in node.
298
It's up to you how to actually draw the nodes and lines (straight,
299
curved, kinked, etc.) and to pick the actual colours for each index.
301
if not len(merge_sorted):
303
# split merge_sorted into a map:
305
# FIXME: get a hint on this from the merge_sorted data rather than
306
# calculating it ourselves
307
# mapping from rev_id to the sequence number of the next lowest rev
309
# mapping from rev_id to next-in-branch-revid - may be None for end
311
next_branch_revid = {}
312
# the stack we are in in the sorted data for determining which
313
# next_lower_rev to set. It is a stack which has one list at each
314
# depth - the ids at that depth that need the same id allocated.
316
for seq, revid, indent, end_merge in merge_sorted:
317
revs[revid] = (seq, indent, end_merge)
318
if indent == len(current_stack):
319
# new merge group starts
320
current_stack.append([revid])
321
elif indent == len(current_stack) - 1:
322
# part of the current merge group
323
current_stack[-1].append(revid)
325
# end of a merge group
326
while current_stack[-1]:
327
stack_rev_id = current_stack[-1].pop()
328
# record the next lower rev for this rev:
329
next_lower_rev[stack_rev_id] = seq
330
# if this followed a non-end-merge rev in this group note that
331
if len(current_stack[-1]):
332
if not revs[current_stack[-1][-1]][2]:
333
next_branch_revid[current_stack[-1][-1]] = stack_rev_id
335
# append to the now-current merge group
336
current_stack[-1].append(revid)
337
# assign a value to all the depth 0 revisions
338
while current_stack[-1]:
339
stack_rev_id = current_stack[-1].pop()
340
# record the next lower rev for this rev:
341
next_lower_rev[stack_rev_id] = len(merge_sorted)
342
# if this followed a non-end-merge rev in this group note that
343
if len(current_stack[-1]):
344
if not revs[current_stack[-1][-1]][2]:
345
next_branch_revid[current_stack[-1][-1]] = stack_rev_id
347
# a list of the current revisions we are drawing lines TO indicating
348
# the sequence of their lines on the screen.
349
# i.e. [A, B, C] means that the line to A, to B, and to C are in
350
# (respectively), 0, 1, 2 on the screen.
351
hanging = [merge_sorted[0][1]]
352
for seq, revid, indent, end_merge in merge_sorted:
353
# a list of the lines to draw: their position in the
354
# previous row, their position in this row, and the colour
355
# (which is the colour they are routing to).
360
for h_idx, hang in enumerate(hanging):
361
# one of these will be the current lines node:
362
# we are drawing a line. h_idx
364
# we have found the current lines node
365
node = (h_idx, colours[revid])
367
# note that we might have done the main parent
368
drawn_parents = set()
370
def draw_line(from_idx, to_idx, revision_id):
372
n_idx = new_hanging.index(revision_id)
374
# force this to be vertical at the place this rev was
376
new_hanging.insert(to_idx, revision_id)
378
lines.append((from_idx, n_idx, colours[revision_id]))
381
# we want to draw a line to the next commit on 'this' branch
383
# drop this line first.
384
parent_id = next_branch_revid[revid]
385
draw_line(h_idx, h_idx, parent_id)
386
# we have drawn this parent
387
drawn_parents.add(parent_id)
389
# this is the last revision in a 'merge', show where it came from
390
if len(revisions[revid].parent_ids) > 1:
392
# parents means this commit was a merge, and being
393
# the end point of a merge group means that all
394
# the parent revisions were merged into branches
395
# to the left of this before this was committed
396
# - so we want to show this as a new branch from
398
# to do this, we show the parent with the lowest
399
# sequence number, which is the one that this
400
# branch 'spawned from', and no others.
401
# If this sounds like a problem, remember that:
402
# if the parent was not already in our mainline
403
# it would show up as a merge into this making
404
# this not the end of a merge-line.
405
lowest = len(merge_sorted)
406
for parent_id in revisions[revid].parent_ids:
407
if revs[parent_id][0] < lowest:
408
lowest = revs[parent_id][0]
409
assert lowest != len(merge_sorted)
410
draw_line(h_idx, len(new_hanging), merge_sorted[lowest][1])
411
drawn_parents.add(merge_sorted[lowest][1])
412
elif len(revisions[revid].parent_ids) == 1:
413
# only one parent, must show this link to be useful.
414
parent_id = revisions[revid].parent_ids[0]
415
draw_line(h_idx, len(new_hanging), parent_id)
416
drawn_parents.add(parent_id)
418
# what do we want to draw lines to from here:
419
# each parent IF its relevant.
421
# Now we need to hang its parents, we put them at the point
422
# the old column was so anything to the right of this has
423
# to move outwards to make room. We also try and collapse
424
# hangs to keep the graph small.
425
# RBC: we do not draw lines to parents that were already merged
426
# unless its the last revision in a merge group.
427
for parent_id in revisions[revid].parent_ids:
428
if parent_id in drawn_parents:
430
parent_seq = revs[parent_id][0]
431
parent_depth = revs[parent_id][1]
432
if parent_depth == indent + 1:
433
# The parent was a merge into this branch determine if
434
# it was already merged into the mainline via a
435
# different merge: if all revisions between us and
436
# parent_seq have a indent greater than there are no
437
# revisions with a lower indent than us.
438
# We do not use 'parent_depth < indent' because that
439
# would allow un-uniqueified merges to show up, and
440
# merge_sorted should take care of that for us (but
441
# does not trim the values)
442
if parent_seq < next_lower_rev[revid]:
443
draw_line(h_idx, len(new_hanging), parent_id)
444
elif parent_depth == indent and parent_seq == seq + 1:
445
# part of this branch
446
draw_line(h_idx, len(new_hanging), parent_id)
448
# draw a line from the previous position of this line to the
450
# h_idx is the old position.
451
# new_indent is the new position.
452
draw_line(h_idx, len(new_hanging), hang)
453
# we've calculated the row, assign new_hanging to hanging to setup for
455
hanging = new_hanging
457
yield (revisions[revid], node, lines)
460
def same_branch(a, b):
461
"""Return whether we think revisions a and b are on the same branch."""
462
if len(a.parent_ids) == 1:
463
# Defacto same branch if only parent
465
elif a.committer == b.committer:
466
# Same committer so may as well be
added
removed
olive/frontend/gtk/viz/graph.py
