bzr branch
http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz
1
by Scott James Remnant
Commit the first version of bzrk. |
1 |
#!/usr/bin/python
|
2 |
# -*- coding: UTF-8 -*-
|
|
3 |
"""Directed graph production.
|
|
4 |
||
5 |
This module contains the code to produce an ordered directed graph of a
|
|
6 |
bzr branch, such as we display in the tree view at the top of the bzrk
|
|
7 |
window.
|
|
8 |
"""
|
|
9 |
||
10 |
__copyright__ = "Copyright © 2005 Canonical Ltd." |
|
11 |
__author__ = "Scott James Remnant <scott@ubuntu.com>" |
|
12 |
||
13 |
||
14 |
from bzrlib.errors import NoSuchRevision |
|
15 |
||
16 |
||
17 |
class DummyRevision(object): |
|
18 |
"""Dummy bzr revision. |
|
19 |
||
20 |
Sometimes, especially in older bzr branches, a revision is referenced
|
|
21 |
as the parent of another but not actually present in the branch's store.
|
|
22 |
When this happens we use an instance of this class instead of the real
|
|
23 |
Revision object (which we can't get).
|
|
24 |
"""
|
|
25 |
||
26 |
def __init__(self, revid): |
|
27 |
self.revision_id = revid |
|
28 |
self.parent_ids = [] |
|
29 |
self.committer = None |
|
30 |
self.message = self.revision_id |
|
31 |
||
32 |
||
33 |
def graph(branch, start): |
|
34 |
"""Produce a directed graph of a bzr branch. |
|
35 |
||
36 |
Traverses the branch revision tree starting at start and produces an
|
|
37 |
ordered list of revisions such that a revision always comes after
|
|
38 |
any revision it is the parent of. It also tries to make a reasonably
|
|
39 |
not-too-stupid decision whether a parent revision is on the same
|
|
40 |
logical branch, as that information is not available with bzr.
|
|
41 |
||
42 |
For each revision it then yields a tuple of (revision, node, lines).
|
|
43 |
If the revision is only referenced in the branch and not present in the
|
|
44 |
store, revision will be a DummyRevision object, otherwise it is the bzr
|
|
45 |
Revision object with the meta-data for the revision.
|
|
46 |
||
47 |
Node is a tuple of (column, colour) with column being a zero-indexed
|
|
48 |
column number of the graph that this revision represents and colour
|
|
49 |
being a zero-indexed colour (which doesn't specify any actual colour
|
|
50 |
in particular) to draw the node in.
|
|
51 |
||
52 |
Lines is a list of tuples which represent lines you should draw away
|
|
53 |
from the revision, if you also need to draw lines into the revision
|
|
54 |
you should use the lines list from the previous iteration. Each
|
|
55 |
typle in the list is in the form (start, end, colour) with start and
|
|
56 |
end being zero-indexed column numbers and colour as in node.
|
|
57 |
||
58 |
It's up to you how to actually draw the nodes and lines (straight,
|
|
59 |
curved, kinked, etc.) and to pick the actual colours for each index.
|
|
60 |
"""
|
|
61 |
revisions = { start: branch.get_revision(start) } |
|
62 |
distances = { start: 0 } |
|
63 |
colours = { start: 0 } |
|
64 |
last_colour = 0 |
|
65 |
||
66 |
# Sort the revisions; the fastest way to do this is to visit each node
|
|
67 |
# as few times as possible (by keeping the todo list in a set) and record
|
|
68 |
# the largest distance to it before queuing up the children if we
|
|
69 |
# increased the distance. This produces the sort order we desire
|
|
70 |
todo = set([ start ]) |
|
71 |
while todo: |
|
72 |
revid = todo.pop() |
|
73 |
revision = revisions[revid] |
|
74 |
distance = distances[revid] + 1 |
|
75 |
colour = colours[revid] |
|
76 |
||
77 |
reused = False |
|
78 |
for parent_id in revision.parent_ids: |
|
79 |
# Check whether there's any point re-processing this
|
|
80 |
if parent_id in distances and distances[parent_id] >= distance: |
|
81 |
continue
|
|
82 |
||
83 |
# Get the parent from the cache, or put it in the cache
|
|
84 |
try: |
|
85 |
parent = revisions[parent_id] |
|
86 |
except KeyError: |
|
87 |
try: |
|
88 |
parent = revisions[parent_id] \ |
|
89 |
= branch.get_revision(parent_id) |
|
90 |
except NoSuchRevision: |
|
91 |
parent = revisions[parent_id] = DummyRevision(parent_id) |
|
92 |
||
93 |
# Make a guess as to whether this node represents the same
|
|
94 |
# branch, or a new one. Penalise same branches in the distance
|
|
95 |
# stakes to give new ones a chance to appear first as one set.
|
|
96 |
if len(revision.parent_ids) == 1: |
|
97 |
colours[parent_id] = colour |
|
98 |
distances[parent_id] = distance |
|
99 |
elif revision.committer == parent.committer and not reused: |
|
100 |
colours[parent_id] = colour |
|
101 |
distances[parent_id] = distance |
|
102 |
reused = True |
|
103 |
else: |
|
104 |
colours[parent_id] = last_colour = last_colour + 1 |
|
105 |
distances[parent_id] = distance + 10 |
|
106 |
||
107 |
todo.add(parent_id) |
|
108 |
||
109 |
# Now iterate the revisions again, but this time in list order rather
|
|
110 |
# than traversing the tree, and build up the graph lines. We do this
|
|
111 |
# by keeping a list of "hanging parents", which can only be removed
|
|
112 |
# once we encounter the revision being hung.
|
|
113 |
hanging = [ start ] |
|
114 |
for revid in sorted(distances, key=distances.get): |
|
115 |
lines = [] |
|
116 |
node = None |
|
117 |
||
118 |
new_hanging = [] |
|
119 |
for h_idx, hang in enumerate(hanging): |
|
120 |
if hang == revid: |
|
121 |
# We've matched a hanging revision, so need to output a node
|
|
122 |
# at this point
|
|
123 |
node = (h_idx, colours[revid]) |
|
124 |
||
125 |
# Now we need to hang its parents, we put them at the point
|
|
126 |
# the old column was so anything to the right of this has
|
|
127 |
# to move outwards to make room. We also try and collapse
|
|
128 |
# hangs to keep the graph small.
|
|
129 |
for parent_id in revisions[revid].parent_ids: |
|
130 |
try: |
|
131 |
n_idx = new_hanging.index(parent_id) |
|
132 |
except ValueError: |
|
133 |
n_idx = len(new_hanging) |
|
134 |
new_hanging.append(parent_id) |
|
135 |
lines.append((h_idx, n_idx, colours[parent_id])) |
|
136 |
else: |
|
137 |
# Revision keeps on hanging, adjust for any change in the
|
|
138 |
# graph shape and try to collapse hangs to keep the graph
|
|
139 |
# small.
|
|
140 |
try: |
|
141 |
n_idx = new_hanging.index(hang) |
|
142 |
except ValueError: |
|
143 |
n_idx = len(new_hanging) |
|
144 |
new_hanging.append(hang) |
|
145 |
lines.append((h_idx, n_idx, colours[hang])) |
|
146 |
hanging = new_hanging |
|
147 |
||
148 |
yield (revisions[revid], node, lines) |