/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 branchview/linegraph.py

  • Committer: Jelmer Vernooij
  • Date: 2008-06-29 15:47:30 UTC
  • mto: This revision was merged to the branch mainline in revision 519.
  • Revision ID: jelmer@samba.org-20080629154730-xfsotoxwkiytf0ph
Pass graph object rather than full repository to linegraph.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 distances(branch, start):
34
 
    """Sort the revisions.
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.
39
 
 
40
 
    Returns a tuple of (revids, revisions, colours, children)
41
 
    """
42
 
    revisions = { start: branch.get_revision(start) }
43
 
    children = { revisions[start]: set() }
44
 
    distances = { start: 0 }
45
 
    colours = { start: 0 }
46
 
    last_colour = 0
47
 
 
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
52
 
    todo = set([ start ])
53
 
    while todo:
54
 
        revid = todo.pop()
55
 
        revision = revisions[revid]
56
 
        distance = distances[revid] + 1
57
 
        colour = colours[revid]
58
 
 
59
 
        found_same = False
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:
63
 
                continue
64
 
 
65
 
            # Get the parent from the cache, or put it in the cache
66
 
            try:
67
 
                parent = revisions[parent_id]
68
 
                children[parent].add(revision)
69
 
            except KeyError:
70
 
                try:
71
 
                    parent = revisions[parent_id] \
72
 
                             = branch.get_revision(parent_id)
73
 
                except NoSuchRevision:
74
 
                    parent = revisions[parent_id] = DummyRevision(parent_id)
75
 
 
76
 
                children[parent] = set([ revision ])
77
 
 
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):
82
 
                found_same = True
83
 
                colours[parent_id] = colour
84
 
                if len(revision.parent_ids) > 1:
85
 
                    distances[parent_id] = distance + 10
86
 
                else:
87
 
                    distances[parent_id] = distance
88
 
            else:
89
 
                colours[parent_id] = last_colour = last_colour + 1
90
 
                distances[parent_id] = distance
91
 
 
92
 
            todo.add(parent_id)
93
 
 
94
 
    return ( sorted(distances, key=distances.get), revisions, colours,
95
 
             children )
96
 
 
97
 
def graph(revids, revisions, colours):
98
 
    """Produce a directed graph of a bzr branch.
99
 
 
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.
104
 
 
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.
109
 
 
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.
115
 
 
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.
118
 
    """
119
 
    hanging = revids[:1]
120
 
    for revid in revids:
121
 
        lines = []
122
 
        node = None
123
 
 
124
 
        new_hanging = []
125
 
        for h_idx, hang in enumerate(hanging):
126
 
            if hang == revid:
127
 
                # We've matched a hanging revision, so need to output a node
128
 
                # at this point
129
 
                node = (h_idx, colours[revid])
130
 
 
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:
136
 
                    try:
137
 
                        n_idx = new_hanging.index(parent_id)
138
 
                    except ValueError:
139
 
                        n_idx = len(new_hanging)
140
 
                        new_hanging.append(parent_id)
141
 
                    lines.append((h_idx, n_idx, colours[parent_id]))
142
 
            else:
143
 
                # Revision keeps on hanging, adjust for any change in the
144
 
                # graph shape and try to collapse hangs to keep the graph
145
 
                # small.
146
 
                try:
147
 
                    n_idx = new_hanging.index(hang)
148
 
                except ValueError:
149
 
                    n_idx = len(new_hanging)
150
 
                    new_hanging.append(hang)
151
 
                lines.append((h_idx, n_idx, colours[hang]))
152
 
        hanging = new_hanging
153
 
 
154
 
        yield (revisions[revid], node, lines)
155
 
 
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
160
 
        return True
161
 
    elif a.committer == b.committer:
162
 
        # Same committer so may as well be
163
 
        return True
164
 
    else:
165
 
        return False
 
1
# -*- coding: UTF-8 -*-
 
2
"""Directed graph production.
 
3
 
 
4
This module contains the code to produce an ordered directed graph of a
 
5
bzr branch, such as we display in the tree view at the top of the bzrk
 
6
window.
 
7
"""
 
8
 
 
9
__copyright__ = "Copyright © 2005 Canonical Ltd."
 
10
__author__    = "Scott James Remnant <scott@ubuntu.com>"
 
11
 
 
12
from bzrlib.revision import NULL_REVISION
 
13
from bzrlib.tsort import merge_sort
 
14
 
 
15
def linegraph(graph, start_revs, maxnum, broken_line_length = None,
 
16
              graph_data = True, mainline_only = False):
 
17
    """Produce a directed graph of a bzr repository.
 
18
 
 
19
    Returns a tuple of (line_graph, revid_index, columns_len) where
 
20
    * line_graph is a list of tuples of (revid,
 
21
                                         node,
 
22
                                         lines,
 
23
                                         parents,
 
24
                                         children,
 
25
                                         revno_sequence),
 
26
    * revid_index is a dict of each revision with the key being the revid, and
 
27
      the value the row index, and
 
28
    * columns_len is the number of columns need to draw the line graph.
 
29
    
 
30
 
 
31
    Node is a tuple of (column, colour) with column being a zero-indexed
 
32
    column number of the graph that this revision represents and colour
 
33
    being a zero-indexed colour (which doesn't specify any actual colour
 
34
    in particular) to draw the node in.
 
35
 
 
36
    Lines is a list of tuples which represent lines you should draw away
 
37
    from the revision, if you also need to draw lines into the revision
 
38
    you should use the lines list from the previous iteration.  Each
 
39
    typle in the list is in the form (start, end, colour) with start and
 
40
    end being zero-indexed column numbers and colour as in node.
 
41
 
 
42
    It's up to you how to actually draw the nodes and lines (straight,
 
43
    curved, kinked, etc.) and to pick the actual colours for each index.
 
44
    """
 
45
    
 
46
    graph_parents = {}
 
47
    ghosts = set()
 
48
    graph_children = {}
 
49
    for (revid, parent_revids) in graph.iter_ancestry(start_revs):
 
50
        if parent_revids is None:
 
51
            ghosts.add(revid)
 
52
            continue
 
53
        if parent_revids == (NULL_REVISION,):
 
54
            graph_parents[revid] = ()
 
55
        else:
 
56
            graph_parents[revid] = parent_revids
 
57
        for parent in parent_revids:
 
58
            graph_children.setdefault(parent, []).append(revid)
 
59
        graph_children.setdefault(revid, [])
 
60
    for ghost in ghosts:
 
61
        for ghost_child in graph_children[ghost]:
 
62
            graph_parents[ghost_child] = [p for p in graph_parents[ghost_child]
 
63
                                          if p not in ghosts]
 
64
    graph_parents["top:"] = start_revs
 
65
 
 
66
    if len(graph_parents)>0:
 
67
        merge_sorted_revisions = merge_sort(
 
68
            graph_parents,
 
69
            "top:",
 
70
            generate_revno=True)
 
71
    else:
 
72
        merge_sorted_revisions = ()
 
73
    
 
74
    if mainline_only:
 
75
        merge_sorted_revisions = [elem for elem in merge_sorted_revisions \
 
76
                                  if len(elem[3])==1 ]
 
77
 
 
78
    assert merge_sorted_revisions[0][1] == "top:"
 
79
    merge_sorted_revisions = merge_sorted_revisions[1:]
 
80
    
 
81
    revid_index = {}
 
82
    revno_index = {}
 
83
    
 
84
    # This will hold an item for each "branch". For a revisions, the revsion
 
85
    # number less the least significant digit is the branch_id, and used as the
 
86
    # key for the dict. Hence revision with the same revsion number less the
 
87
    # least significant digit are considered to be in the same branch line.
 
88
    # e.g.: for revisions 290.12.1 and 290.12.2, the branch_id would be 290.12,
 
89
    # and these two revisions will be in the same branch line. Each value is
 
90
    # a list of rev_indexes in the branch.
 
91
    branch_lines = {}
 
92
    
 
93
    linegraph = []    
 
94
    
 
95
    for (rev_index, (sequence_number,
 
96
                     revid,
 
97
                     merge_depth,
 
98
                     revno_sequence,
 
99
                     end_of_merge)) in enumerate(merge_sorted_revisions):
 
100
        if maxnum and rev_index >= maxnum:
 
101
            break
 
102
        revid_index[revid] = rev_index
 
103
        
 
104
        parents = graph_parents[revid]
 
105
        linegraph.append([revid,
 
106
                          None,
 
107
                          [],
 
108
                          parents,
 
109
                          None,
 
110
                          revno_sequence])
 
111
        
 
112
        if graph_data:
 
113
            revno_index[revno_sequence] = rev_index
 
114
            
 
115
            branch_id = revno_sequence[0:-1]
 
116
            
 
117
            branch_line = None
 
118
            if branch_id not in branch_lines:
 
119
                branch_line = []
 
120
                branch_lines[branch_id] = branch_line
 
121
            else:
 
122
                branch_line = branch_lines[branch_id]
 
123
            
 
124
            branch_line.append(rev_index)        
 
125
 
 
126
    if graph_data:
 
127
        branch_ids = branch_lines.keys()
 
128
    
 
129
        def branch_id_cmp(x, y):
 
130
            """Compaire branch_id's first by the number of digits, then reversed
 
131
            by their value"""
 
132
            len_x = len(x)
 
133
            len_y = len(y)
 
134
            if len_x == len_y:
 
135
                return -cmp(x, y)
 
136
            return cmp(len_x, len_y)
 
137
        
 
138
        branch_ids.sort(branch_id_cmp)
 
139
        # This will hold a tuple of (child_index, parent_index, col_index) for each
 
140
        # line that needs to be drawn. If col_index is not none, then the line is
 
141
        # drawn along that column, else the the line can be drawn directly between
 
142
        # the child and parent because either the child and parent are in the same
 
143
        # branch line, or the child and parent are 1 row apart.
 
144
        lines = []
 
145
        empty_column = [False for i in range(len(graph_parents))]
 
146
        # This will hold a bit map for each cell. If the cell is true, then the
 
147
        # cell allready contains a node or line. This use when deciding what column
 
148
        # to place a branch line or line in, without it overlaping something else.
 
149
        columns = [list(empty_column)]
 
150
        
 
151
        
 
152
        for branch_id in branch_ids:
 
153
            branch_line = branch_lines[branch_id]
 
154
            
 
155
            # Find the col_index for the direct parent branch. This will be the
 
156
            # starting point when looking for a free column.
 
157
            parent_col_index = 0
 
158
            parent_index = None
 
159
            if len(branch_id) > 1:
 
160
                parent_revno = branch_id[0:-1]
 
161
                if parent_revno in revno_index:
 
162
                    parent_index = revno_index[parent_revno]
 
163
                    parent_node = linegraph[parent_index][1]
 
164
                    if parent_node:
 
165
                        parent_col_index = parent_node[0]
 
166
                    
 
167
            
 
168
            col_search_order = _branch_line_col_search_order(columns,
 
169
                                                             parent_col_index)
 
170
            color = reduce(lambda x, y: x+y, branch_id, 0)
 
171
            cur_cont_line = []
 
172
            
 
173
            line_range = []
 
174
            last_rev_index = None
 
175
            for rev_index in branch_line:
 
176
                if last_rev_index:
 
177
                    if broken_line_length and \
 
178
                       rev_index - last_rev_index > broken_line_length:
 
179
                        line_range.append(last_rev_index+1)
 
180
                        line_range.append(rev_index-1)
 
181
                    else:
 
182
                        line_range.extend(range(last_rev_index+1, rev_index))
 
183
                
 
184
                line_range.append(rev_index)
 
185
                last_rev_index = rev_index
 
186
            
 
187
            if parent_index:
 
188
                if broken_line_length and \
 
189
                   parent_index - last_rev_index > broken_line_length:
 
190
                    line_range.append(last_rev_index+1)
 
191
                else:
 
192
                    line_range.extend(range(last_rev_index+1, parent_index))
 
193
            
 
194
            col_index = _find_free_column(columns,
 
195
                                          empty_column,
 
196
                                          col_search_order,
 
197
                                          line_range)
 
198
            node = (col_index, color)
 
199
            for rev_index in branch_line:
 
200
                linegraph[rev_index][1] = node
 
201
                columns[col_index][rev_index] = True
 
202
            
 
203
            for rev_index in branch_line:
 
204
                (sequence_number,
 
205
                     revid,
 
206
                     merge_depth,
 
207
                     revno_sequence,
 
208
                     end_of_merge) = merge_sorted_revisions[rev_index]
 
209
                
 
210
                linegraph[rev_index][4] = graph_children[revid]
 
211
                col_index = linegraph[rev_index][1][0]
 
212
                
 
213
                for parent_revid in graph_parents[revid]:
 
214
                    if parent_revid in revid_index:
 
215
                        
 
216
                        parent_index = revid_index[parent_revid]                            
 
217
                        parent_node = linegraph[parent_index][1]
 
218
                        if parent_node:
 
219
                            parent_col_index = parent_node[0]
 
220
                        else:
 
221
                            parent_col_index = None
 
222
                        col_search_order = \
 
223
                                _line_col_search_order(columns,
 
224
                                                       parent_col_index,
 
225
                                                       col_index)
 
226
                            
 
227
                        # If this line is really long, break it.
 
228
                        if len(branch_id) > 0 and \
 
229
                           broken_line_length and \
 
230
                           parent_index - rev_index > broken_line_length:
 
231
                            child_line_col_index = \
 
232
                                _find_free_column(columns,
 
233
                                                  empty_column,
 
234
                                                  col_search_order,
 
235
                                                  (rev_index + 1,))
 
236
                            _mark_column_as_used(columns,
 
237
                                                 child_line_col_index,
 
238
                                                 (rev_index + 1,))
 
239
                            
 
240
                            # Recall _line_col_search_order to reset it back to
 
241
                            # the beging.
 
242
                            col_search_order = \
 
243
                                    _line_col_search_order(columns,
 
244
                                                           parent_col_index,
 
245
                                                           col_index)
 
246
                            parent_col_line_index = \
 
247
                                _find_free_column(columns,
 
248
                                                  empty_column,
 
249
                                                  col_search_order,
 
250
                                                  (parent_index - 1,))
 
251
                            _mark_column_as_used(columns,
 
252
                                                 parent_col_line_index,
 
253
                                                 (parent_index - 1,))
 
254
                            lines.append((rev_index,
 
255
                                          parent_index,
 
256
                                          (child_line_col_index,
 
257
                                           parent_col_line_index)))
 
258
                        else :
 
259
                            line_col_index = col_index
 
260
                            if parent_index - rev_index >1:
 
261
                                line_range = range(rev_index + 1, parent_index)
 
262
                                line_col_index = \
 
263
                                    _find_free_column(columns,
 
264
                                                      empty_column,
 
265
                                                      col_search_order,
 
266
                                                      line_range)
 
267
                                _mark_column_as_used(columns,
 
268
                                                     line_col_index,
 
269
                                                     line_range)
 
270
                            lines.append((rev_index,
 
271
                                          parent_index,
 
272
                                          (line_col_index,)))
 
273
        
 
274
        for (child_index, parent_index, line_col_indexes) in lines:
 
275
            (child_col_index, child_color) = linegraph[child_index][1]
 
276
            (parent_col_index, parent_color) = linegraph[parent_index][1]
 
277
            
 
278
            if len(line_col_indexes) == 1:
 
279
                if parent_index - child_index == 1:
 
280
                    linegraph[child_index][2].append(
 
281
                        (child_col_index,
 
282
                         parent_col_index,
 
283
                         parent_color))
 
284
                else:
 
285
                    # line from the child's column to the lines column
 
286
                    linegraph[child_index][2].append(
 
287
                        (child_col_index,
 
288
                         line_col_indexes[0],
 
289
                         parent_color))
 
290
                    # lines down the line's column
 
291
                    for line_part_index in range(child_index+1, parent_index-1):
 
292
                        linegraph[line_part_index][2].append(
 
293
                            (line_col_indexes[0],   
 
294
                             line_col_indexes[0],
 
295
                             parent_color))
 
296
                    # line from the line's column to the parent's column
 
297
                    linegraph[parent_index-1][2].append(
 
298
                        (line_col_indexes[0],
 
299
                         parent_col_index,
 
300
                         parent_color))
 
301
            else:
 
302
                # Broken line
 
303
                # line from the child's column to the lines column
 
304
                linegraph[child_index][2].append(
 
305
                    (child_col_index,
 
306
                     line_col_indexes[0],
 
307
                     parent_color))
 
308
                # Broken line end
 
309
                linegraph[child_index+1][2].append(
 
310
                    (line_col_indexes[0],
 
311
                     None,
 
312
                     parent_color))
 
313
                
 
314
                # Broken line end 
 
315
                linegraph[parent_index-2][2].append(
 
316
                    (None,
 
317
                     line_col_indexes[1],
 
318
                     parent_color))
 
319
                # line from the line's column to the parent's column
 
320
                linegraph[parent_index-1][2].append(
 
321
                    (line_col_indexes[1],
 
322
                     parent_col_index,
 
323
                     parent_color))
 
324
        return (linegraph, revid_index, len(columns))
 
325
    else:
 
326
        return (linegraph, revid_index, 0)
 
327
    
 
328
 
 
329
def _branch_line_col_search_order(columns, parent_col_index):
 
330
    for col_index in range(parent_col_index, len(columns)):
 
331
        yield col_index
 
332
    for col_index in range(parent_col_index-1, -1, -1):
 
333
        yield col_index
 
334
 
 
335
def _line_col_search_order(columns, parent_col_index, child_col_index):
 
336
    if parent_col_index is not None:
 
337
        max_index = max(parent_col_index, child_col_index)
 
338
        min_index = min(parent_col_index, child_col_index)
 
339
        for col_index in range(max_index, min_index -1, -1):
 
340
            yield col_index
 
341
    else:
 
342
        max_index = child_col_index
 
343
        min_index = child_col_index
 
344
        yield child_col_index
 
345
    i = 1
 
346
    while max_index + i < len(columns) or \
 
347
          min_index - i > -1:
 
348
        if max_index + i < len(columns):
 
349
            yield max_index + i
 
350
        if min_index - i > -1:
 
351
            yield min_index - i
 
352
        i += 1
 
353
 
 
354
def _find_free_column(columns, empty_column, col_search_order, line_range):
 
355
    for col_index in col_search_order:
 
356
        column = columns[col_index]
 
357
        has_overlaping_line = False
 
358
        for row_index in line_range:
 
359
            if column[row_index]:
 
360
                has_overlaping_line = True
 
361
                break
 
362
        if not has_overlaping_line:
 
363
            break
 
364
    else:
 
365
        col_index = len(columns)
 
366
        column = list(empty_column)
 
367
        columns.append(column)
 
368
    return col_index
 
369
 
 
370
def _mark_column_as_used(columns, col_index, line_range):
 
371
    column = columns[col_index]
 
372
    for row_index in line_range:
 
373
        column[row_index] = True    
 
374
 
 
375
def same_branch(a, b):
 
376
    """Return whether we think revisions a and b are on the same branch."""
 
377
    if len(a.parent_ids) == 1:
 
378
        # Defacto same branch if only parent
 
379
        return True
 
380
    elif a.committer == b.committer:
 
381
        # Same committer so may as well be
 
382
        return True
 
383
    else:
 
384
        return False