/b-gtk/fix-viz

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Scott James Remnant
  • Date: 2005-10-17 01:07:49 UTC
  • Revision ID: scott@netsplit.com-20051017010749-15fa95fc2cf09289
Commit the first version of bzrk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
 
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)