/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 16:11:12 UTC
  • mfrom: (475.2.2 gtk)
  • mto: This revision was merged to the branch mainline in revision 519.
  • Revision ID: jelmer@samba.org-20080629161112-3j4zp0r0e7cv6cds
Merge Chad's progress bar in viz patch.

Show diffs side-by-side

added added

removed removed

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