/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 = [None]
50
 
    mainline.extend(branch.revision_history())
51
 
    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()
52
54
    graph_children = {}
53
 
    for revid in graph_parents.iterkeys():
54
 
        graph_children[revid] = []
55
 
 
56
 
    merge_sorted_revisions = merge_sort(
57
 
        graph_parents,
58
 
        start,
59
 
        mainline,
60
 
        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:]
61
103
    
62
104
    revid_index = {}
63
105
    revno_index = {}
73
115
    
74
116
    linegraph = []    
75
117
    
76
 
    for (rev_index, (sequence_number,
77
 
                     revid,
78
 
                     merge_depth,
79
 
                     revno_sequence,
80
 
                     end_of_merge)) in enumerate(merge_sorted_revisions):
81
 
        if maxnum and rev_index >= maxnum:
82
 
            break
83
 
        revid_index[revid] = rev_index
84
 
        revno_index[revno_sequence] = rev_index
85
 
        
86
 
        branch_id = revno_sequence[0:-1]
87
 
        
88
 
        branch_line = None
89
 
        if branch_id not in branch_lines:
90
 
            branch_line = []
91
 
            branch_lines[branch_id] = branch_line
92
 
        else:
93
 
            branch_line = branch_lines[branch_id]
94
 
        
95
 
        branch_line.append(rev_index)
96
 
        
97
 
        parents = graph_parents[revid]
98
 
        for parent_revid in parents:
99
 
            graph_children[parent_revid].append(revid)
100
 
        
101
 
        linegraph.append([revid,
102
 
                          None,
103
 
                          [],
104
 
                          parents,
105
 
                          None,
106
 
                          revno_sequence])
107
 
 
108
 
    branch_ids = branch_lines.keys()
109
 
    
110
 
    def branch_id_cmp(x, y):
111
 
        """Compaire branch_id's first by the number of digits, then reversed
112
 
        by their value"""
113
 
        len_x = len(x)
114
 
        len_y = len(y)
115
 
        if len_x == len_y:
116
 
            return -cmp(x, y)
117
 
        return cmp(len_x, len_y)
118
 
    
119
 
    branch_ids.sort(branch_id_cmp)
120
 
    # This will hold a tuple of (child_index, parent_index, col_index) for each
121
 
    # line that needs to be drawn. If col_index is not none, then the line is
122
 
    # drawn along that column, else the the line can be drawn directly between
123
 
    # the child and parent because either the child and parent are in the same
124
 
    # branch line, or the child and parent are 1 row apart.
125
 
    lines = []
126
 
    empty_column = [False for i in range(len(graph_parents))]
127
 
    # This will hold a bit map for each cell. If the cell is true, then the
128
 
    # cell allready contains a node or line. This use when deciding what column
129
 
    # to place a branch line or line in, without it overlaping something else.
130
 
    columns = [list(empty_column)]
131
 
    
132
 
    
133
 
    for branch_id in branch_ids:
134
 
        branch_line = branch_lines[branch_id]
135
 
        
136
 
        # Find the col_index for the direct parent branch. This will be the
137
 
        # starting point when looking for a free column.
138
 
        parent_col_index = 0
139
 
        parent_index = None
140
 
        if len(branch_id) > 1:
141
 
            parent_revno = branch_id[0:-1]
142
 
            if parent_revno in revno_index:
143
 
                parent_index = revno_index[parent_revno]
144
 
                parent_node = linegraph[parent_index][1]
145
 
                if parent_node:
146
 
                    parent_col_index = parent_node[0]
147
 
                
148
 
        
149
 
        col_search_order = _branch_line_col_search_order(columns,
150
 
                                                         parent_col_index)
151
 
        color = reduce(lambda x, y: x+y, branch_id, 0)
152
 
        cur_cont_line = []
153
 
        
154
 
        line_range = []
155
 
        last_rev_index = None
156
 
        for rev_index in branch_line:
157
 
            if last_rev_index:
158
 
                if BROKEN_LINE_LENGTH and \
159
 
                   rev_index - last_rev_index > BROKEN_LINE_LENGTH:
160
 
                    line_range.append(last_rev_index+1)
161
 
                    line_range.append(rev_index-1)
162
 
                else:
163
 
                    line_range.extend(range(last_rev_index+1, rev_index))
164
 
            
165
 
            line_range.append(rev_index)
166
 
            last_rev_index = rev_index
167
 
        
168
 
        if parent_index:
169
 
            if BROKEN_LINE_LENGTH and \
170
 
               parent_index - last_rev_index > BROKEN_LINE_LENGTH:
171
 
                line_range.append(last_rev_index+1)
172
 
            else:
173
 
                line_range.extend(range(last_rev_index+1, parent_index))
174
 
        
175
 
        col_index = _find_free_column(columns,
176
 
                                      empty_column,
177
 
                                      col_search_order,
178
 
                                      line_range)
179
 
        node = (col_index, color)
180
 
        for rev_index in branch_line:
181
 
            linegraph[rev_index][1] = node
182
 
            columns[col_index][rev_index] = True
183
 
        
184
 
        for rev_index in branch_line:
185
 
            (sequence_number,
186
 
                 revid,
187
 
                 merge_depth,
188
 
                 revno_sequence,
189
 
                 end_of_merge) = merge_sorted_revisions[rev_index]
190
 
            
191
 
            linegraph[rev_index][4] = graph_children[revid]
192
 
            col_index = linegraph[rev_index][1][0]
193
 
            
194
 
            for parent_revid in graph_parents[revid]:
195
 
                if parent_revid in revid_index:
196
 
                    
197
 
                    parent_index = revid_index[parent_revid]                            
198
 
                    parent_node = linegraph[parent_index][1]
199
 
                    if parent_node:
200
 
                        parent_col_index = parent_node[0]
201
 
                    else:
202
 
                        parent_col_index = None
203
 
                    col_search_order = \
204
 
                            _line_col_search_order(columns,
205
 
                                                   parent_col_index,
206
 
                                                   col_index)
207
 
                        
208
 
                    # If this line is really long, break it.
209
 
                    if len(branch_id) > 0 and \
210
 
                       BROKEN_LINE_LENGTH and \
211
 
                       parent_index - rev_index > BROKEN_LINE_LENGTH:
212
 
                        child_line_col_index = \
213
 
                            _find_free_column(columns,
214
 
                                              empty_column,
215
 
                                              col_search_order,
216
 
                                              (rev_index + 1,))
217
 
                        _mark_column_as_used(columns,
218
 
                                             child_line_col_index,
219
 
                                             (rev_index + 1,))
220
 
                        
221
 
                        # Recall _line_col_search_order to reset it back to
222
 
                        # the beging.
223
 
                        col_search_order = \
224
 
                                _line_col_search_order(columns,
225
 
                                                       parent_col_index,
226
 
                                                       col_index)
227
 
                        parent_col_line_index = \
228
 
                            _find_free_column(columns,
229
 
                                              empty_column,
230
 
                                              col_search_order,
231
 
                                              (parent_index - 1,))
232
 
                        _mark_column_as_used(columns,
233
 
                                             parent_col_line_index,
234
 
                                             (parent_index - 1,))
235
 
                        lines.append((rev_index,
236
 
                                      parent_index,
237
 
                                      (child_line_col_index,
238
 
                                       parent_col_line_index)))
239
 
                    else :
240
 
                        line_col_index = col_index
241
 
                        if parent_index - rev_index >1:
242
 
                            line_range = range(rev_index + 1, parent_index)
243
 
                            line_col_index = \
244
 
                                _find_free_column(columns,
245
 
                                                  empty_column,
246
 
                                                  col_search_order,
247
 
                                                  line_range)
248
 
                            _mark_column_as_used(columns,
249
 
                                                 line_col_index,
250
 
                                                 line_range)
251
 
                        lines.append((rev_index,
252
 
                                      parent_index,
253
 
                                      (line_col_index,)))
254
 
    
255
 
    for (child_index, parent_index, line_col_indexes) in lines:
256
 
        (child_col_index, child_color) = linegraph[child_index][1]
257
 
        (parent_col_index, parent_color) = linegraph[parent_index][1]
258
 
        
259
 
        if len(line_col_indexes) == 1:
260
 
            if parent_index - child_index == 1:
261
 
                linegraph[child_index][2].append(
262
 
                    (child_col_index,
263
 
                     parent_col_index,
264
 
                     parent_color))
265
 
            else:
266
 
                # line from the child's column to the lines column
267
 
                linegraph[child_index][2].append(
268
 
                    (child_col_index,
269
 
                     line_col_indexes[0],
270
 
                     parent_color))
271
 
                # lines down the line's column
272
 
                for line_part_index in range(child_index+1, parent_index-1):
273
 
                    linegraph[line_part_index][2].append(
274
 
                        (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,
275
352
                         line_col_indexes[0],
276
353
                         parent_color))
277
 
                # line from the line's column to the parent's column
278
 
                linegraph[parent_index-1][2].append(
279
 
                    (line_col_indexes[0],
280
 
                     parent_col_index,
281
 
                     parent_color))
282
 
        else:
283
 
            # Broken line
284
 
            # line from the child's column to the lines column
285
 
            linegraph[child_index][2].append(
286
 
                (child_col_index,
287
 
                 line_col_indexes[0],
288
 
                 parent_color))
289
 
            # Broken line end
290
 
            linegraph[child_index+1][2].append(
291
 
                (line_col_indexes[0],
292
 
                 None,
293
 
                 parent_color))
294
 
            
295
 
            # Broken line end 
296
 
            linegraph[parent_index-2][2].append(
297
 
                (None,
298
 
                 line_col_indexes[1],
299
 
                 parent_color))
300
 
            # line from the line's column to the parent's column
301
 
            linegraph[parent_index-1][2].append(
302
 
                (line_col_indexes[1],
303
 
                 parent_col_index,
304
 
                 parent_color))
305
 
            
 
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)
306
375
    
307
 
    return (linegraph, revid_index, len(columns))
308
376
 
309
377
def _branch_line_col_search_order(columns, parent_col_index):
310
378
    for col_index in range(parent_col_index, len(columns)):