2
# -*- coding: UTF-8 -*-
3
"""Directed graph production.
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
10
__copyright__ = "Copyright © 2005 Canonical Ltd."
11
__author__ = "Scott James Remnant <scott@ubuntu.com>"
14
from bzrlib.errors import NoSuchRevision
17
class DummyRevision(object):
18
"""Dummy bzr revision.
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).
26
def __init__(self, revid):
27
self.revision_id = revid
30
self.message = self.revision_id
33
def graph(branch, start):
34
"""Produce a directed graph of a bzr branch.
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.
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.
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.
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.
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.
61
revisions = { start: branch.get_revision(start) }
62
distances = { start: 0 }
63
colours = { start: 0 }
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
73
revision = revisions[revid]
74
distance = distances[revid] + 1
75
colour = colours[revid]
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:
83
# Get the parent from the cache, or put it in the cache
85
parent = revisions[parent_id]
88
parent = revisions[parent_id] \
89
= branch.get_revision(parent_id)
90
except NoSuchRevision:
91
parent = revisions[parent_id] = DummyRevision(parent_id)
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
104
colours[parent_id] = last_colour = last_colour + 1
105
distances[parent_id] = distance + 10
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.
114
for revid in sorted(distances, key=distances.get):
119
for h_idx, hang in enumerate(hanging):
121
# We've matched a hanging revision, so need to output a node
123
node = (h_idx, colours[revid])
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:
131
n_idx = new_hanging.index(parent_id)
133
n_idx = len(new_hanging)
134
new_hanging.append(parent_id)
135
lines.append((h_idx, n_idx, colours[parent_id]))
137
# Revision keeps on hanging, adjust for any change in the
138
# graph shape and try to collapse hangs to keep the graph
141
n_idx = new_hanging.index(hang)
143
n_idx = len(new_hanging)
144
new_hanging.append(hang)
145
lines.append((h_idx, n_idx, colours[hang]))
146
hanging = new_hanging
148
yield (revisions[revid], node, lines)
added
removed
graph.py
