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 distances(branch, start):
34
"""Sort the revisions.
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.
40
Returns a tuple of (revids, revisions, colours, children)
42
revisions = { start: branch.get_revision(start) }
43
children = { revisions[start]: set() }
44
distances = { start: 0 }
45
colours = { start: 0 }
48
# Sort the revisions; the fastest way to do this is to visit each node
49
# as few times as possible (by keeping the todo list in a set) and record
50
# the largest distance to it before queuing up the children if we
51
# increased the distance. This produces the sort order we desire
55
revision = revisions[revid]
56
distance = distances[revid] + 1
57
colour = colours[revid]
60
for parent_id in revision.parent_ids:
61
# Check whether there's any point re-processing this
62
if parent_id in distances and distances[parent_id] >= distance:
65
# Get the parent from the cache, or put it in the cache
67
parent = revisions[parent_id]
68
children[parent].add(revision)
71
parent = revisions[parent_id] \
72
= branch.get_revision(parent_id)
73
except NoSuchRevision:
74
parent = revisions[parent_id] = DummyRevision(parent_id)
76
children[parent] = set([ revision ])
78
# Penalise revisions a little at a fork if we think they're on
79
# the same branch -- this makes the few few (at least) revisions
80
# of a branch appear straight after the fork
81
if not found_same and same_branch(revision, parent):
83
colours[parent_id] = colour
84
if len(revision.parent_ids) > 1:
85
distances[parent_id] = distance + 10
87
distances[parent_id] = distance
89
colours[parent_id] = last_colour = last_colour + 1
90
distances[parent_id] = distance
94
return ( sorted(distances, key=distances.get), revisions, colours,
97
def graph(revids, revisions, colours):
98
"""Produce a directed graph of a bzr branch.
100
For each revision it then yields a tuple of (revision, node, lines).
101
If the revision is only referenced in the branch and not present in the
102
store, revision will be a DummyRevision object, otherwise it is the bzr
103
Revision object with the meta-data for the revision.
105
Node is a tuple of (column, colour) with column being a zero-indexed
106
column number of the graph that this revision represents and colour
107
being a zero-indexed colour (which doesn't specify any actual colour
108
in particular) to draw the node in.
110
Lines is a list of tuples which represent lines you should draw away
111
from the revision, if you also need to draw lines into the revision
112
you should use the lines list from the previous iteration. Each
113
typle in the list is in the form (start, end, colour) with start and
114
end being zero-indexed column numbers and colour as in node.
116
It's up to you how to actually draw the nodes and lines (straight,
117
curved, kinked, etc.) and to pick the actual colours for each index.
125
for h_idx, hang in enumerate(hanging):
127
# We've matched a hanging revision, so need to output a node
129
node = (h_idx, colours[revid])
131
# Now we need to hang its parents, we put them at the point
132
# the old column was so anything to the right of this has
133
# to move outwards to make room. We also try and collapse
134
# hangs to keep the graph small.
135
for parent_id in revisions[revid].parent_ids:
137
n_idx = new_hanging.index(parent_id)
139
n_idx = len(new_hanging)
140
new_hanging.append(parent_id)
141
lines.append((h_idx, n_idx, colours[parent_id]))
143
# Revision keeps on hanging, adjust for any change in the
144
# graph shape and try to collapse hangs to keep the graph
147
n_idx = new_hanging.index(hang)
149
n_idx = len(new_hanging)
150
new_hanging.append(hang)
151
lines.append((h_idx, n_idx, colours[hang]))
152
hanging = new_hanging
154
yield (revisions[revid], node, lines)
156
def same_branch(a, b):
157
"""Return whether we think revisions a and b are on the same branch."""
158
if len(a.parent_ids) == 1:
159
# Defacto same branch if only parent
161
elif a.committer == b.committer:
162
# Same committer so may as well be
added
removed
graph.py
