/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 18:12:29 UTC
  • mto: This revision was merged to the branch mainline in revision 519.
  • Revision ID: jelmer@samba.org-20080629181229-1l2m4cf7vvbyh8qg
Simplify progress bar code, use embedded progress bar inside viz window.

Show diffs side-by-side

added added

removed removed

Lines of Context:
branchview/linegraph.py
9
9
__copyright__ = "Copyright © 2005 Canonical Ltd."
10
10
__author__    = "Scott James Remnant <scott@ubuntu.com>"
11
11
 
 
12
from bzrlib.revision import NULL_REVISION
12
13
from bzrlib.tsort import merge_sort
 
14
from bzrlib import ui
13
15
 
14
 
def linegraph(branch, start, maxnum):
15
 
    """Produce a directed graph of a bzr branch.
 
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.
16
19
 
17
20
    Returns a tuple of (line_graph, revid_index, columns_len) where
18
21
    * line_graph is a list of tuples of (revid,
40
43
    It's up to you how to actually draw the nodes and lines (straight,
41
44
    curved, kinked, etc.) and to pick the actual colours for each index.
42
45
    """
43
 
    
44
 
    # FIXME: This should be configurable
45
 
    BROKEN_LINE_LENGTH = 32
46
 
    
47
 
    # We get the mainline so we can pass it to merge_sort to make merge_sort
48
 
    # run faster.
49
 
    mainline = branch.revision_history()
50
 
    graph_parents = branch.repository.get_revision_graph(start)
 
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_cnt=step_number)
 
51
 
 
52
    graph_parents = {}
 
53
    ghosts = set()
51
54
    graph_children = {}
52
 
    for revid in graph_parents.iterkeys():
53
 
        graph_children[revid] = []
54
 
 
55
 
    merge_sorted_revisions = merge_sort(
56
 
        graph_parents,
57
 
        start,
58
 
        mainline,
59
 
        generate_revno=True)
 
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_cnt=len(ghosts))
 
79
        for i, ghost in enumerate(ghosts):
 
80
            if i % 25 == 0:
 
81
                progress_bar.update(None, current_cnt=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:]
60
103
    
61
104
    revid_index = {}
62
105
    revno_index = {}
72
115
    
73
116
    linegraph = []    
74
117
    
75
 
    for (rev_index, (sequence_number,
76
 
                     revid,
77
 
                     merge_depth,
78
 
                     revno_sequence,
79
 
                     end_of_merge)) in enumerate(merge_sorted_revisions):
80
 
        if maxnum and rev_index >= maxnum:
81
 
            break
82
 
        revid_index[revid] = rev_index
83
 
        revno_index[revno_sequence] = rev_index
84
 
        
85
 
        branch_id = revno_sequence[0:-1]
86
 
        
87
 
        branch_line = None
88
 
        if branch_id not in branch_lines:
89
 
            branch_line = []
90
 
            branch_lines[branch_id] = branch_line
91
 
        else:
92
 
            branch_line = branch_lines[branch_id]
93
 
        
94
 
        branch_line.append(rev_index)
95
 
        
96
 
        parents = graph_parents[revid]
97
 
        for parent_revid in parents:
98
 
            graph_children[parent_revid].append(revid)
99
 
        
100
 
        linegraph.append([revid,
101
 
                          None,
102
 
                          [],
103
 
                          parents,
104
 
                          None,
105
 
                          revno_sequence])
106
 
 
107
 
    branch_ids = branch_lines.keys()
108
 
    
109
 
    def branch_id_cmp(x, y):
110
 
        """Compaire branch_id's first by the number of digits, then reversed
111
 
        by their value"""
112
 
        len_x = len(x)
113
 
        len_y = len(y)
114
 
        if len_x == len_y:
115
 
            return -cmp(x, y)
116
 
        return cmp(len_x, len_y)
117
 
    
118
 
    branch_ids.sort(branch_id_cmp)
119
 
    # This will hold a tuple of (child_index, parent_index, col_index) for each
120
 
    # line that needs to be drawn. If col_index is not none, then the line is
121
 
    # drawn along that column, else the the line can be drawn directly between
122
 
    # the child and parent because either the child and parent are in the same
123
 
    # branch line, or the child and parent are 1 row apart.
124
 
    lines = []
125
 
    empty_column = [False for i in range(len(graph_parents))]
126
 
    # This will hold a bit map for each cell. If the cell is true, then the
127
 
    # cell allready contains a node or line. This use when deciding what column
128
 
    # to place a branch line or line in, without it overlaping something else.
129
 
    columns = [list(empty_column)]
130
 
    
131
 
    
132
 
    for branch_id in branch_ids:
133
 
        branch_line = branch_lines[branch_id]
134
 
        
135
 
        # Find the col_index for the direct parent branch. This will be the
136
 
        # starting point when looking for a free column.
137
 
        parent_col_index = 0
138
 
        parent_index = None
139
 
        if len(branch_id) > 1:
140
 
            parent_revno = branch_id[0:-1]
141
 
            if parent_revno in revno_index:
142
 
                parent_index = revno_index[parent_revno]
143
 
                parent_node = linegraph[parent_index][1]
144
 
                if parent_node:
145
 
                    parent_col_index = parent_node[0]
146
 
                
147
 
        
148
 
        col_search_order = _branch_line_col_search_order(columns,
149
 
                                                         parent_col_index)
150
 
        color = reduce(lambda x, y: x+y, branch_id, 0)
151
 
        cur_cont_line = []
152
 
        
153
 
        line_range = []
154
 
        last_rev_index = None
155
 
        for rev_index in branch_line:
156
 
            if last_rev_index:
157
 
                if BROKEN_LINE_LENGTH and \
158
 
                   rev_index - last_rev_index > BROKEN_LINE_LENGTH:
159
 
                    line_range.append(last_rev_index+1)
160
 
                    line_range.append(rev_index-1)
161
 
                else:
162
 
                    line_range.extend(range(last_rev_index+1, rev_index))
163
 
            
164
 
            line_range.append(rev_index)
165
 
            last_rev_index = rev_index
166
 
        
167
 
        if parent_index:
168
 
            if BROKEN_LINE_LENGTH and \
169
 
               parent_index - last_rev_index > BROKEN_LINE_LENGTH:
170
 
                line_range.append(last_rev_index+1)
171
 
            else:
172
 
                line_range.extend(range(last_rev_index+1, parent_index))
173
 
        
174
 
        col_index = _find_free_column(columns,
175
 
                                      empty_column,
176
 
                                      col_search_order,
177
 
                                      line_range)
178
 
        node = (col_index, color)
179
 
        for rev_index in branch_line:
180
 
            linegraph[rev_index][1] = node
181
 
            columns[col_index][rev_index] = True
182
 
        
183
 
        for rev_index in branch_line:
184
 
            (sequence_number,
185
 
                 revid,
186
 
                 merge_depth,
187
 
                 revno_sequence,
188
 
                 end_of_merge) = merge_sorted_revisions[rev_index]
189
 
            
190
 
            linegraph[rev_index][4] = graph_children[revid]
191
 
            col_index = linegraph[rev_index][1][0]
192
 
            
193
 
            for parent_revid in graph_parents[revid]:
194
 
                if parent_revid in revid_index:
195
 
                    
196
 
                    parent_index = revid_index[parent_revid]                            
197
 
                    parent_node = linegraph[parent_index][1]
198
 
                    if parent_node:
199
 
                        parent_col_index = parent_node[0]
200
 
                    else:
201
 
                        parent_col_index = None
202
 
                    col_search_order = \
203
 
                            _line_col_search_order(columns,
204
 
                                                   parent_col_index,
205
 
                                                   col_index)
206
 
                        
207
 
                    # If this line is really long, break it.
208
 
                    if len(branch_id) > 0 and \
209
 
                       BROKEN_LINE_LENGTH and \
210
 
                       parent_index - rev_index > BROKEN_LINE_LENGTH:
211
 
                        child_line_col_index = \
212
 
                            _find_free_column(columns,
213
 
                                              empty_column,
214
 
                                              col_search_order,
215
 
                                              (rev_index + 1,))
216
 
                        _mark_column_as_used(columns,
217
 
                                             child_line_col_index,
218
 
                                             (rev_index + 1,))
219
 
                        
220
 
                        # Recall _line_col_search_order to reset it back to
221
 
                        # the beging.
222
 
                        col_search_order = \
223
 
                                _line_col_search_order(columns,
224
 
                                                       parent_col_index,
225
 
                                                       col_index)
226
 
                        parent_col_line_index = \
227
 
                            _find_free_column(columns,
228
 
                                              empty_column,
229
 
                                              col_search_order,
230
 
                                              (parent_index - 1,))
231
 
                        _mark_column_as_used(columns,
232
 
                                             parent_col_line_index,
233
 
                                             (parent_index - 1,))
234
 
                        lines.append((rev_index,
235
 
                                      parent_index,
236
 
                                      (child_line_col_index,
237
 
                                       parent_col_line_index)))
238
 
                    else :
239
 
                        line_col_index = col_index
240
 
                        if parent_index - rev_index >1:
241
 
                            line_range = range(rev_index + 1, parent_index)
242
 
                            line_col_index = \
243
 
                                _find_free_column(columns,
244
 
                                                  empty_column,
245
 
                                                  col_search_order,
246
 
                                                  line_range)
247
 
                            _mark_column_as_used(columns,
248
 
                                                 line_col_index,
249
 
                                                 line_range)
250
 
                        lines.append((rev_index,
251
 
                                      parent_index,
252
 
                                      (line_col_index,)))
253
 
    
254
 
    for (child_index, parent_index, line_col_indexes) in lines:
255
 
        (child_col_index, child_color) = linegraph[child_index][1]
256
 
        (parent_col_index, parent_color) = linegraph[parent_index][1]
257
 
        
258
 
        if len(line_col_indexes) == 1:
259
 
            if parent_index - child_index == 1:
260
 
                linegraph[child_index][2].append(
261
 
                    (child_col_index,
262
 
                     parent_col_index,
263
 
                     parent_color))
264
 
            else:
265
 
                # line from the child's column to the lines column
266
 
                linegraph[child_index][2].append(
267
 
                    (child_col_index,
268
 
                     line_col_indexes[0],
269
 
                     parent_color))
270
 
                # lines down the line's column
271
 
                for line_part_index in range(child_index+1, parent_index-1):
272
 
                    linegraph[line_part_index][2].append(
273
 
                        (line_col_indexes[0],   
 
118
    update_root_progress(3)
 
119
    progress_bar = ui.ui_factory.nested_progress_bar()
 
120
    try:
 
121
        progress_bar.update(msg="Finding nodes", total_cnt=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(None, current_cnt=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_cnt=len(branch_ids))
 
188
            for i, branch_id in enumerate(branch_ids):
 
189
                if i % 25 == 0:
 
190
                    progress_bar.update(None, current_cnt=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_cnt=len(lines))
 
318
            for i, (child_index, parent_index, line_col_indexes) in enumerate(lines):
 
319
                if i % 25 == 0:
 
320
                    progress_bar.update(None, current_cnt=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,
274
352
                         line_col_indexes[0],
275
353
                         parent_color))
276
 
                # line from the line's column to the parent's column
277
 
                linegraph[parent_index-1][2].append(
278
 
                    (line_col_indexes[0],
279
 
                     parent_col_index,
280
 
                     parent_color))
281
 
        else:
282
 
            # Broken line
283
 
            # line from the child's column to the lines column
284
 
            linegraph[child_index][2].append(
285
 
                (child_col_index,
286
 
                 line_col_indexes[0],
287
 
                 parent_color))
288
 
            # Broken line end
289
 
            linegraph[child_index+1][2].append(
290
 
                (line_col_indexes[0],
291
 
                 None,
292
 
                 parent_color))
293
 
            
294
 
            # Broken line end 
295
 
            linegraph[parent_index-2][2].append(
296
 
                (None,
297
 
                 line_col_indexes[1],
298
 
                 parent_color))
299
 
            # line from the line's column to the parent's column
300
 
            linegraph[parent_index-1][2].append(
301
 
                (line_col_indexes[1],
302
 
                 parent_col_index,
303
 
                 parent_color))
304
 
            
 
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)
305
375
    
306
 
    return (linegraph, revid_index, len(columns))
307
376
 
308
377
def _branch_line_col_search_order(columns, parent_col_index):
309
378
    for col_index in range(parent_col_index, len(columns)):