/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: 2010-06-17 20:25:04 UTC
  • mfrom: (690 realtrunk)
  • mto: This revision was merged to the branch mainline in revision 691.
  • Revision ID: jelmer@samba.org-20100617202504-7yln6khkqftlun6i
Merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
branchview/linegraph.py
12
12
from bzrlib.tsort import merge_sort
13
13
from bzrlib import ui
14
14
 
15
 
 
16
15
def linegraph(graph, start_revs, maxnum=None, broken_line_length=None,
17
16
              graph_data=True, mainline_only=False, root_progress=None):
18
17
    """Produce a directed graph of a bzr repository.
27
26
    * revid_index is a dict of each revision with the key being the revid, and
28
27
      the value the row index, and
29
28
    * columns_len is the number of columns need to draw the line graph.
30
 
 
 
29
    
31
30
 
32
31
    Node is a tuple of (column, colour) with column being a zero-indexed
33
32
    column number of the graph that this revision represents and colour
93
92
            generate_revno=True)
94
93
    else:
95
94
        merge_sorted_revisions = ()
96
 
 
 
95
    
97
96
    if mainline_only:
98
97
        merge_sorted_revisions = [elem for elem in merge_sorted_revisions \
99
98
                                  if len(elem[3])==1 ]
100
99
 
101
100
    assert merge_sorted_revisions[0][1] == "top:"
102
101
    merge_sorted_revisions = merge_sorted_revisions[1:]
103
 
 
 
102
    
104
103
    revid_index = {}
105
104
    revno_index = {}
106
 
 
 
105
    
107
106
    # This will hold an item for each "branch". For a revisions, the revsion
108
107
    # number less the least significant digit is the branch_id, and used as the
109
108
    # key for the dict. Hence revision with the same revsion number less the
112
111
    # and these two revisions will be in the same branch line. Each value is
113
112
    # a list of rev_indexes in the branch.
114
113
    branch_lines = {}
115
 
 
116
 
    linegraph = []
117
 
 
 
114
    
 
115
    linegraph = []    
 
116
    
118
117
    update_root_progress(3)
119
118
    progress_bar = ui.ui_factory.nested_progress_bar()
120
119
    try:
130
129
            if maxnum and rev_index >= maxnum:
131
130
                break
132
131
            revid_index[revid] = rev_index
133
 
 
 
132
            
134
133
            parents = graph_parents[revid]
135
134
            linegraph.append([revid,
136
135
                              None,
138
137
                              parents,
139
138
                              None,
140
139
                              revno_sequence])
141
 
 
 
140
            
142
141
            if graph_data:
143
142
                revno_index[revno_sequence] = rev_index
144
 
 
 
143
                
145
144
                branch_id = revno_sequence[0:-1]
146
 
 
 
145
                
147
146
                branch_line = None
148
147
                if branch_id not in branch_lines:
149
148
                    branch_line = []
150
149
                    branch_lines[branch_id] = branch_line
151
150
                else:
152
151
                    branch_line = branch_lines[branch_id]
153
 
 
154
 
                branch_line.append(rev_index)
 
152
                
 
153
                branch_line.append(rev_index)        
155
154
    finally:
156
155
        progress_bar.finished()
157
156
 
158
157
    if graph_data:
159
158
        branch_ids = branch_lines.keys()
160
 
 
 
159
    
161
160
        def branch_id_cmp(x, y):
162
161
            """Compaire branch_id's first by the number of digits, then reversed
163
162
            by their value"""
166
165
            if len_x == len_y:
167
166
                return -cmp(x, y)
168
167
            return cmp(len_x, len_y)
169
 
 
 
168
        
170
169
        branch_ids.sort(branch_id_cmp)
171
170
        # This will hold a tuple of (child_index, parent_index, col_index) for each
172
171
        # line that needs to be drawn. If col_index is not none, then the line is
179
178
        # cell allready contains a node or line. This use when deciding what column
180
179
        # to place a branch line or line in, without it overlaping something else.
181
180
        columns = [list(empty_column)]
182
 
 
183
 
 
 
181
        
 
182
        
184
183
        update_root_progress(4)
185
184
        progress_bar = ui.ui_factory.nested_progress_bar()
186
185
        try:
189
188
                if i % 25 == 0:
190
189
                    progress_bar.update(None, i)
191
190
                branch_line = branch_lines[branch_id]
192
 
 
 
191
                
193
192
                # Find the col_index for the direct parent branch. This will be the
194
193
                # starting point when looking for a free column.
195
194
                parent_col_index = 0
201
200
                        parent_node = linegraph[parent_index][1]
202
201
                        if parent_node:
203
202
                            parent_col_index = parent_node[0]
204
 
 
205
 
 
 
203
                        
 
204
                
206
205
                col_search_order = _branch_line_col_search_order(columns,
207
206
                                                                 parent_col_index)
208
207
                color = reduce(lambda x, y: x+y, branch_id, 0)
209
208
                cur_cont_line = []
210
 
 
 
209
                
211
210
                line_range = []
212
211
                last_rev_index = None
213
212
                for rev_index in branch_line:
218
217
                            line_range.append(rev_index-1)
219
218
                        else:
220
219
                            line_range.extend(range(last_rev_index+1, rev_index))
221
 
 
 
220
                    
222
221
                    line_range.append(rev_index)
223
222
                    last_rev_index = rev_index
224
 
 
 
223
                
225
224
                if parent_index:
226
225
                    if broken_line_length and \
227
226
                       parent_index - last_rev_index > broken_line_length:
228
227
                        line_range.append(last_rev_index+1)
229
228
                    else:
230
229
                        line_range.extend(range(last_rev_index+1, parent_index))
231
 
 
 
230
                
232
231
                col_index = _find_free_column(columns,
233
232
                                              empty_column,
234
233
                                              col_search_order,
237
236
                for rev_index in branch_line:
238
237
                    linegraph[rev_index][1] = node
239
238
                    columns[col_index][rev_index] = True
240
 
 
 
239
                
241
240
                for rev_index in branch_line:
242
241
                    (sequence_number,
243
242
                         revid,
244
243
                         merge_depth,
245
244
                         revno_sequence,
246
245
                         end_of_merge) = merge_sorted_revisions[rev_index]
247
 
 
 
246
                    
248
247
                    linegraph[rev_index][4] = graph_children[revid]
249
248
                    col_index = linegraph[rev_index][1][0]
250
 
 
 
249
                    
251
250
                    for parent_revid in graph_parents[revid]:
252
251
                        if parent_revid in revid_index:
253
 
 
254
 
                            parent_index = revid_index[parent_revid]
 
252
                            
 
253
                            parent_index = revid_index[parent_revid]                            
255
254
                            parent_node = linegraph[parent_index][1]
256
255
                            if parent_node:
257
256
                                parent_col_index = parent_node[0]
261
260
                                    _line_col_search_order(columns,
262
261
                                                           parent_col_index,
263
262
                                                           col_index)
264
 
 
 
263
                                
265
264
                            # If this line is really long, break it.
266
265
                            if len(branch_id) > 0 and \
267
266
                               broken_line_length and \
274
273
                                _mark_column_as_used(columns,
275
274
                                                     child_line_col_index,
276
275
                                                     (rev_index + 1,))
277
 
 
 
276
                                
278
277
                                # Recall _line_col_search_order to reset it back to
279
278
                                # the beging.
280
279
                                col_search_order = \
310
309
                                              (line_col_index,)))
311
310
        finally:
312
311
            progress_bar.finished()
313
 
 
 
312
        
314
313
        update_root_progress(5)
315
314
        progress_bar = ui.ui_factory.nested_progress_bar()
316
315
        try:
320
319
                    progress_bar.update(None, i)
321
320
                (child_col_index, child_color) = linegraph[child_index][1]
322
321
                (parent_col_index, parent_color) = linegraph[parent_index][1]
323
 
 
 
322
                
324
323
                if len(line_col_indexes) == 1:
325
324
                    if parent_index - child_index == 1:
326
325
                        linegraph[child_index][2].append(
336
335
                        # lines down the line's column
337
336
                        for line_part_index in range(child_index+1, parent_index-1):
338
337
                            linegraph[line_part_index][2].append(
339
 
                                (line_col_indexes[0], 
 
338
                                (line_col_indexes[0],   
340
339
                                 line_col_indexes[0],
341
340
                                 parent_color))
342
341
                        # line from the line's column to the parent's column
356
355
                        (line_col_indexes[0],
357
356
                         None,
358
357
                         parent_color))
359
 
 
 
358
                    
360
359
                    # Broken line end 
361
360
                    linegraph[parent_index-2][2].append(
362
361
                        (None,
372
371
        return (linegraph, revid_index, len(columns))
373
372
    else:
374
373
        return (linegraph, revid_index, 0)
375
 
 
 
374
    
376
375
 
377
376
def _branch_line_col_search_order(columns, parent_col_index):
378
377
    for col_index in range(parent_col_index, len(columns)):
418
417
def _mark_column_as_used(columns, col_index, line_range):
419
418
    column = columns[col_index]
420
419
    for row_index in line_range:
421
 
        column[row_index] = True
 
420
        column[row_index] = True    
422
421
 
423
422
def same_branch(a, b):
424
423
    """Return whether we think revisions a and b are on the same branch."""