/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: Mark Lee
  • Date: 2009-07-11 18:39:14 UTC
  • mto: This revision was merged to the branch mainline in revision 661.
  • Revision ID: bzr@lazymalevolence.com-20090711183914-zuii3et5skiv2njo
Re-ignore credits.pickle.

Show diffs side-by-side

added added

removed removed

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