/b-gtk/fix-viz

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
1
"""Directed graph production.
2
3
This module contains the code to produce an ordered directed graph of a
4
bzr branch, such as we display in the tree view at the top of the bzrk
5
window.
6
"""
7
672 by Vincent Ladeuil
Thanks to lamont, we know spell Prettifying with the right number of 't'.
8
__copyright__ = "Copyright 2005 Canonical Ltd."
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
9
__author__    = "Scott James Remnant <scott@ubuntu.com>"
10
450.8.1 by Jelmer Vernooij
Fix regression in graph determination code.
11
from bzrlib.revision import NULL_REVISION
256.2.25 by Gary van der Merwe
Use Merge sort
12
from bzrlib.tsort import merge_sort
475.2.1 by Chad MILLER
Make "vizualize" use the GUI progress bar defined in the parent 'ui' module.
13
from bzrlib import ui
14
511.5.2 by Jelmer Vernooij
Add simple test for linegraph.
15
def linegraph(graph, start_revs, maxnum=None, broken_line_length=None,
511.5.3 by Jelmer Vernooij
Merge Chad's progress bar in viz patch.
16
              graph_data=True, mainline_only=False, root_progress=None):
328 by Jelmer Vernooij
Use repository instead of branch in more places, to make it easier to support multiple branches in viz.
17
    """Produce a directed graph of a bzr repository.
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
18
256.4.1 by Gary van der Merwe
* Set a width and use ellips on Revision No column.
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
    
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
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
    """
511.5.3 by Jelmer Vernooij
Merge Chad's progress bar in viz patch.
45
    assert isinstance(start_revs, list)
475.2.2 by Chad MILLER
Big diff, few changes. :(
46
    def update_root_progress(step_number):
47
        """IFF our container received a root progress bar, then update it."""
48
        if root_progress is not None:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
49
            root_progress.update(None, step_number)
475.2.2 by Chad MILLER
Big diff, few changes. :(
50
452.4.1 by Jelmer Vernooij
Support displaying multiple tips in viz.
51
    graph_parents = {}
471.1.1 by Aaron Bentley
Get viz working on graphs with ghosts
52
    ghosts = set()
471.1.2 by Aaron Bentley
Turn my_graph_children into plain graph_children
53
    graph_children = {}
475.2.2 by Chad MILLER
Big diff, few changes. :(
54
    update_root_progress(1)
55
    progress_bar = ui.ui_factory.nested_progress_bar()
56
    try:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
57
        progress_bar.update("Arranging tree fragments")
475.2.2 by Chad MILLER
Big diff, few changes. :(
58
        for i, (revid, parent_revids) in enumerate(graph.iter_ancestry(start_revs)):
59
            if i % 25 == 0:
60
                progress_bar.tick()
61
            if parent_revids is None:
62
                ghosts.add(revid)
63
                continue
64
            if parent_revids == (NULL_REVISION,):
65
                graph_parents[revid] = ()
66
            else:
67
                graph_parents[revid] = parent_revids
68
            for parent in parent_revids:
69
                graph_children.setdefault(parent, []).append(revid)
511.5.3 by Jelmer Vernooij
Merge Chad's progress bar in viz patch.
70
            graph_children.setdefault(revid, [])
475.2.2 by Chad MILLER
Big diff, few changes. :(
71
    finally:
72
        progress_bar.finished()
73
74
    update_root_progress(2)
75
    progress_bar = ui.ui_factory.nested_progress_bar()
76
    try:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
77
        progress_bar.update("Removing ghosts", 0, len(ghosts))
475.2.2 by Chad MILLER
Big diff, few changes. :(
78
        for i, ghost in enumerate(ghosts):
79
            if i % 25 == 0:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
80
                progress_bar.update(None, i)
475.2.2 by Chad MILLER
Big diff, few changes. :(
81
            for ghost_child in graph_children[ghost]:
82
                graph_parents[ghost_child] = [p for p in graph_parents[ghost_child]
83
                                              if p not in ghosts]
84
    finally:
85
        progress_bar.finished()
452.4.1 by Jelmer Vernooij
Support displaying multiple tips in viz.
86
    graph_parents["top:"] = start_revs
87
421.1.1 by Gary van der Merwe
Make viz not throw errors when there are 0 commits.
88
    if len(graph_parents)>0:
89
        merge_sorted_revisions = merge_sort(
90
            graph_parents,
452.4.1 by Jelmer Vernooij
Support displaying multiple tips in viz.
91
            "top:",
421.1.1 by Gary van der Merwe
Make viz not throw errors when there are 0 commits.
92
            generate_revno=True)
93
    else:
94
        merge_sorted_revisions = ()
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
95
    
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
96
    if mainline_only:
97
        merge_sorted_revisions = [elem for elem in merge_sorted_revisions \
98
                                  if len(elem[3])==1 ]
452.4.1 by Jelmer Vernooij
Support displaying multiple tips in viz.
99
100
    assert merge_sorted_revisions[0][1] == "top:"
101
    merge_sorted_revisions = merge_sorted_revisions[1:]
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
102
    
256.2.28 by Gary van der Merwe
Better line drawing with info from merge_sort
103
    revid_index = {}
256.2.48 by Gary van der Merwe
Make the line to a direct parent in the same column as the child branch line.
104
    revno_index = {}
256.2.46 by Gary van der Merwe
Store branch lines as list rather than dict.
105
    
106
    # This will hold an item for each "branch". For a revisions, the revsion
107
    # number less the least significant digit is the branch_id, and used as the
108
    # key for the dict. Hence revision with the same revsion number less the
109
    # least significant digit are considered to be in the same branch line.
110
    # e.g.: for revisions 290.12.1 and 290.12.2, the branch_id would be 290.12,
111
    # and these two revisions will be in the same branch line. Each value is
256.2.50 by Gary van der Merwe
First implementation of broken lines.
112
    # a list of rev_indexes in the branch.
256.2.28 by Gary van der Merwe
Better line drawing with info from merge_sort
113
    branch_lines = {}
256.2.46 by Gary van der Merwe
Store branch lines as list rather than dict.
114
    
256.2.28 by Gary van der Merwe
Better line drawing with info from merge_sort
115
    linegraph = []    
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
116
    
475.2.2 by Chad MILLER
Big diff, few changes. :(
117
    update_root_progress(3)
475.2.1 by Chad MILLER
Make "vizualize" use the GUI progress bar defined in the parent 'ui' module.
118
    progress_bar = ui.ui_factory.nested_progress_bar()
475.2.2 by Chad MILLER
Big diff, few changes. :(
119
    try:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
120
        progress_bar.update("Finding nodes", 0, len(merge_sorted_revisions))
475.2.2 by Chad MILLER
Big diff, few changes. :(
121
        for (rev_index, (sequence_number,
122
                         revid,
123
                         merge_depth,
124
                         revno_sequence,
125
                         end_of_merge)) in enumerate(merge_sorted_revisions):
475.2.1 by Chad MILLER
Make "vizualize" use the GUI progress bar defined in the parent 'ui' module.
126
475.2.2 by Chad MILLER
Big diff, few changes. :(
127
            if rev_index % 25 == 0:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
128
                progress_bar.update(None, rev_index)
475.2.2 by Chad MILLER
Big diff, few changes. :(
129
            if maxnum and rev_index >= maxnum:
130
                break
131
            revid_index[revid] = rev_index
132
            
133
            parents = graph_parents[revid]
134
            linegraph.append([revid,
135
                              None,
136
                              [],
137
                              parents,
138
                              None,
139
                              revno_sequence])
140
            
141
            if graph_data:
142
                revno_index[revno_sequence] = rev_index
143
                
144
                branch_id = revno_sequence[0:-1]
145
                
146
                branch_line = None
147
                if branch_id not in branch_lines:
148
                    branch_line = []
149
                    branch_lines[branch_id] = branch_line
150
                else:
151
                    branch_line = branch_lines[branch_id]
152
                
153
                branch_line.append(rev_index)        
154
    finally:
155
        progress_bar.finished()
256.2.33 by Gary van der Merwe
Revert fast test
156
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
157
    if graph_data:
158
        branch_ids = branch_lines.keys()
159
    
160
        def branch_id_cmp(x, y):
161
            """Compaire branch_id's first by the number of digits, then reversed
162
            by their value"""
163
            len_x = len(x)
164
            len_y = len(y)
165
            if len_x == len_y:
166
                return -cmp(x, y)
167
            return cmp(len_x, len_y)
168
        
169
        branch_ids.sort(branch_id_cmp)
170
        # This will hold a tuple of (child_index, parent_index, col_index) for each
171
        # line that needs to be drawn. If col_index is not none, then the line is
172
        # drawn along that column, else the the line can be drawn directly between
173
        # the child and parent because either the child and parent are in the same
174
        # branch line, or the child and parent are 1 row apart.
175
        lines = []
176
        empty_column = [False for i in range(len(graph_parents))]
177
        # This will hold a bit map for each cell. If the cell is true, then the
178
        # cell allready contains a node or line. This use when deciding what column
179
        # to place a branch line or line in, without it overlaping something else.
180
        columns = [list(empty_column)]
181
        
182
        
475.2.2 by Chad MILLER
Big diff, few changes. :(
183
        update_root_progress(4)
475.2.1 by Chad MILLER
Make "vizualize" use the GUI progress bar defined in the parent 'ui' module.
184
        progress_bar = ui.ui_factory.nested_progress_bar()
475.2.2 by Chad MILLER
Big diff, few changes. :(
185
        try:
576.4.2 by Jelmer Vernooij
Fix typo.
186
            progress_bar.update("Organizing edges", 0, len(branch_ids))
475.2.2 by Chad MILLER
Big diff, few changes. :(
187
            for i, branch_id in enumerate(branch_ids):
188
                if i % 25 == 0:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
189
                    progress_bar.update(None, i)
475.2.2 by Chad MILLER
Big diff, few changes. :(
190
                branch_line = branch_lines[branch_id]
191
                
192
                # Find the col_index for the direct parent branch. This will be the
193
                # starting point when looking for a free column.
194
                parent_col_index = 0
195
                parent_index = None
196
                if len(branch_id) > 1:
197
                    parent_revno = branch_id[0:-1]
198
                    if parent_revno in revno_index:
199
                        parent_index = revno_index[parent_revno]
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
200
                        parent_node = linegraph[parent_index][1]
201
                        if parent_node:
202
                            parent_col_index = parent_node[0]
475.2.2 by Chad MILLER
Big diff, few changes. :(
203
                        
204
                
205
                col_search_order = _branch_line_col_search_order(columns,
206
                                                                 parent_col_index)
207
                color = reduce(lambda x, y: x+y, branch_id, 0)
208
                cur_cont_line = []
209
                
210
                line_range = []
211
                last_rev_index = None
212
                for rev_index in branch_line:
213
                    if last_rev_index:
214
                        if broken_line_length and \
215
                           rev_index - last_rev_index > broken_line_length:
216
                            line_range.append(last_rev_index+1)
217
                            line_range.append(rev_index-1)
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
218
                        else:
475.2.2 by Chad MILLER
Big diff, few changes. :(
219
                            line_range.extend(range(last_rev_index+1, rev_index))
220
                    
221
                    line_range.append(rev_index)
222
                    last_rev_index = rev_index
223
                
224
                if parent_index:
225
                    if broken_line_length and \
226
                       parent_index - last_rev_index > broken_line_length:
227
                        line_range.append(last_rev_index+1)
228
                    else:
229
                        line_range.extend(range(last_rev_index+1, parent_index))
230
                
231
                col_index = _find_free_column(columns,
232
                                              empty_column,
233
                                              col_search_order,
234
                                              line_range)
235
                node = (col_index, color)
236
                for rev_index in branch_line:
237
                    linegraph[rev_index][1] = node
238
                    columns[col_index][rev_index] = True
239
                
240
                for rev_index in branch_line:
241
                    (sequence_number,
242
                         revid,
243
                         merge_depth,
244
                         revno_sequence,
245
                         end_of_merge) = merge_sorted_revisions[rev_index]
246
                    
247
                    linegraph[rev_index][4] = graph_children[revid]
248
                    col_index = linegraph[rev_index][1][0]
249
                    
250
                    for parent_revid in graph_parents[revid]:
251
                        if parent_revid in revid_index:
252
                            
253
                            parent_index = revid_index[parent_revid]                            
254
                            parent_node = linegraph[parent_index][1]
255
                            if parent_node:
256
                                parent_col_index = parent_node[0]
257
                            else:
258
                                parent_col_index = None
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
259
                            col_search_order = \
260
                                    _line_col_search_order(columns,
261
                                                           parent_col_index,
262
                                                           col_index)
475.2.2 by Chad MILLER
Big diff, few changes. :(
263
                                
264
                            # If this line is really long, break it.
265
                            if len(branch_id) > 0 and \
266
                               broken_line_length and \
267
                               parent_index - rev_index > broken_line_length:
268
                                child_line_col_index = \
269
                                    _find_free_column(columns,
270
                                                      empty_column,
271
                                                      col_search_order,
272
                                                      (rev_index + 1,))
273
                                _mark_column_as_used(columns,
274
                                                     child_line_col_index,
275
                                                     (rev_index + 1,))
276
                                
277
                                # Recall _line_col_search_order to reset it back to
278
                                # the beging.
279
                                col_search_order = \
280
                                        _line_col_search_order(columns,
281
                                                               parent_col_index,
282
                                                               col_index)
283
                                parent_col_line_index = \
284
                                    _find_free_column(columns,
285
                                                      empty_column,
286
                                                      col_search_order,
287
                                                      (parent_index - 1,))
288
                                _mark_column_as_used(columns,
289
                                                     parent_col_line_index,
290
                                                     (parent_index - 1,))
291
                                lines.append((rev_index,
292
                                              parent_index,
293
                                              (child_line_col_index,
294
                                               parent_col_line_index)))
295
                            else :
296
                                line_col_index = col_index
297
                                if parent_index - rev_index >1:
298
                                    line_range = range(rev_index + 1, parent_index)
299
                                    line_col_index = \
300
                                        _find_free_column(columns,
301
                                                          empty_column,
302
                                                          col_search_order,
303
                                                          line_range)
304
                                    _mark_column_as_used(columns,
305
                                                         line_col_index,
306
                                                         line_range)
307
                                lines.append((rev_index,
308
                                              parent_index,
309
                                              (line_col_index,)))
310
        finally:
311
            progress_bar.finished()
256.2.40 by Gary van der Merwe
Take out a whole bunch of code for better performance.
312
        
475.2.2 by Chad MILLER
Big diff, few changes. :(
313
        update_root_progress(5)
475.2.1 by Chad MILLER
Make "vizualize" use the GUI progress bar defined in the parent 'ui' module.
314
        progress_bar = ui.ui_factory.nested_progress_bar()
475.2.2 by Chad MILLER
Big diff, few changes. :(
315
        try:
672 by Vincent Ladeuil
Thanks to lamont, we know spell Prettifying with the right number of 't'.
316
            progress_bar.update("Prettifying graph", 0, len(lines))
475.2.2 by Chad MILLER
Big diff, few changes. :(
317
            for i, (child_index, parent_index, line_col_indexes) in enumerate(lines):
318
                if i % 25 == 0:
576.4.1 by Jelmer Vernooij
Avoid using explicit names for progress bar function arguments since they differ.
319
                    progress_bar.update(None, i)
475.2.2 by Chad MILLER
Big diff, few changes. :(
320
                (child_col_index, child_color) = linegraph[child_index][1]
321
                (parent_col_index, parent_color) = linegraph[parent_index][1]
322
                
323
                if len(line_col_indexes) == 1:
324
                    if parent_index - child_index == 1:
325
                        linegraph[child_index][2].append(
326
                            (child_col_index,
327
                             parent_col_index,
328
                             parent_color))
329
                    else:
330
                        # line from the child's column to the lines column
331
                        linegraph[child_index][2].append(
332
                            (child_col_index,
333
                             line_col_indexes[0],
334
                             parent_color))
335
                        # lines down the line's column
336
                        for line_part_index in range(child_index+1, parent_index-1):
337
                            linegraph[line_part_index][2].append(
338
                                (line_col_indexes[0],   
339
                                 line_col_indexes[0],
340
                                 parent_color))
341
                        # line from the line's column to the parent's column
342
                        linegraph[parent_index-1][2].append(
343
                            (line_col_indexes[0],
344
                             parent_col_index,
345
                             parent_color))
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
346
                else:
475.2.2 by Chad MILLER
Big diff, few changes. :(
347
                    # Broken line
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
348
                    # line from the child's column to the lines column
349
                    linegraph[child_index][2].append(
350
                        (child_col_index,
351
                         line_col_indexes[0],
352
                         parent_color))
475.2.2 by Chad MILLER
Big diff, few changes. :(
353
                    # Broken line end
354
                    linegraph[child_index+1][2].append(
355
                        (line_col_indexes[0],
356
                         None,
357
                         parent_color))
358
                    
359
                    # Broken line end 
360
                    linegraph[parent_index-2][2].append(
361
                        (None,
362
                         line_col_indexes[1],
363
                         parent_color))
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
364
                    # line from the line's column to the parent's column
365
                    linegraph[parent_index-1][2].append(
475.2.2 by Chad MILLER
Big diff, few changes. :(
366
                        (line_col_indexes[1],
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
367
                         parent_col_index,
368
                         parent_color))
475.2.2 by Chad MILLER
Big diff, few changes. :(
369
        finally:
370
            progress_bar.finished()
423.1.18 by Gary van der Merwe
Add options to viz treeview to not show the line graph, and to only show the main line.
371
        return (linegraph, revid_index, len(columns))
372
    else:
373
        return (linegraph, revid_index, 0)
256.2.28 by Gary van der Merwe
Better line drawing with info from merge_sort
374
    
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
375
256.2.48 by Gary van der Merwe
Make the line to a direct parent in the same column as the child branch line.
376
def _branch_line_col_search_order(columns, parent_col_index):
256.2.58 by Gary van der Merwe
Improve the performance of the search order functions by making them
377
    for col_index in range(parent_col_index, len(columns)):
378
        yield col_index
379
    for col_index in range(parent_col_index-1, -1, -1):
380
        yield col_index
256.2.47 by Gary van der Merwe
Tweek the search order of columns.
381
256.2.48 by Gary van der Merwe
Make the line to a direct parent in the same column as the child branch line.
382
def _line_col_search_order(columns, parent_col_index, child_col_index):
383
    if parent_col_index is not None:
256.2.58 by Gary van der Merwe
Improve the performance of the search order functions by making them
384
        max_index = max(parent_col_index, child_col_index)
385
        min_index = min(parent_col_index, child_col_index)
386
        for col_index in range(max_index, min_index -1, -1):
387
            yield col_index
256.2.48 by Gary van der Merwe
Make the line to a direct parent in the same column as the child branch line.
388
    else:
256.2.58 by Gary van der Merwe
Improve the performance of the search order functions by making them
389
        max_index = child_col_index
390
        min_index = child_col_index
391
        yield child_col_index
256.2.47 by Gary van der Merwe
Tweek the search order of columns.
392
    i = 1
256.2.58 by Gary van der Merwe
Improve the performance of the search order functions by making them
393
    while max_index + i < len(columns) or \
394
          min_index - i > -1:
395
        if max_index + i < len(columns):
396
            yield max_index + i
397
        if min_index - i > -1:
398
            yield min_index - i
256.2.47 by Gary van der Merwe
Tweek the search order of columns.
399
        i += 1
400
256.2.50 by Gary van der Merwe
First implementation of broken lines.
401
def _find_free_column(columns, empty_column, col_search_order, line_range):
256.2.47 by Gary van der Merwe
Tweek the search order of columns.
402
    for col_index in col_search_order:
256.2.44 by Gary van der Merwe
Chose what column to place nodes and lines in better.
403
        column = columns[col_index]
256.2.40 by Gary van der Merwe
Take out a whole bunch of code for better performance.
404
        has_overlaping_line = False
256.2.42 by Gary van der Merwe
Performance improvements.
405
        for row_index in line_range:
406
            if column[row_index]:
256.2.40 by Gary van der Merwe
Take out a whole bunch of code for better performance.
407
                has_overlaping_line = True
408
                break
409
        if not has_overlaping_line:
410
            break
411
    else:
412
        col_index = len(columns)
256.2.42 by Gary van der Merwe
Performance improvements.
413
        column = list(empty_column)
414
        columns.append(column)
256.2.50 by Gary van der Merwe
First implementation of broken lines.
415
    return col_index
416
417
def _mark_column_as_used(columns, col_index, line_range):
418
    column = columns[col_index]
256.2.42 by Gary van der Merwe
Performance improvements.
419
    for row_index in line_range:
256.2.50 by Gary van der Merwe
First implementation of broken lines.
420
        column[row_index] = True    
256.2.26 by Gary van der Merwe
Use info from merge sort to draw lines. Needs work
421
422
def same_branch(a, b):
423
    """Return whether we think revisions a and b are on the same branch."""
424
    if len(a.parent_ids) == 1:
425
        # Defacto same branch if only parent
426
        return True
427
    elif a.committer == b.committer:
428
        # Same committer so may as well be
429
        return True
430
    else:
431
        return False