/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
13
 
 
14
 
def linegraph(branch, start, maxnum):
15
 
    """Produce a directed graph of a bzr branch.
16
 
 
17
 
    Returns a list of tuples of (revid,
18
 
                                 node,
19
 
                                 lines,
20
 
                                 parents,
21
 
                                 children,
22
 
                                 revno_sequence).
 
14
from bzrlib import ui
 
15
 
 
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.
 
19
 
 
20
    Returns a tuple of (line_graph, revid_index, columns_len) where
 
21
    * line_graph is a list of tuples of (revid,
 
22
                                         node,
 
23
                                         lines,
 
24
                                         parents,
 
25
                                         children,
 
26
                                         revno_sequence),
 
27
    * revid_index is a dict of each revision with the key being the revid, and
 
28
      the value the row index, and
 
29
    * columns_len is the number of columns need to draw the line graph.
 
30
    
23
31
 
24
32
    Node is a tuple of (column, colour) with column being a zero-indexed
25
33
    column number of the graph that this revision represents and colour
35
43
    It's up to you how to actually draw the nodes and lines (straight,
36
44
    curved, kinked, etc.) and to pick the actual colours for each index.
37
45
    """
38
 
       
39
 
    mainline = branch.revision_history()
40
 
    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()
41
54
    graph_children = {}
42
 
    for revid in graph_parents.keys():
43
 
        graph_children[revid] = []
44
 
 
45
 
    merge_sorted_revisions = merge_sort(
46
 
        graph_parents,
47
 
        start,
48
 
        mainline,
49
 
        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:]
50
103
    
51
104
    revid_index = {}
52
105
    revno_index = {}
 
106
    
 
107
    # This will hold an item for each "branch". For a revisions, the revsion
 
108
    # number less the least significant digit is the branch_id, and used as the
 
109
    # key for the dict. Hence revision with the same revsion number less the
 
110
    # least significant digit are considered to be in the same branch line.
 
111
    # e.g.: for revisions 290.12.1 and 290.12.2, the branch_id would be 290.12,
 
112
    # and these two revisions will be in the same branch line. Each value is
 
113
    # a list of rev_indexes in the branch.
53
114
    branch_lines = {}
 
115
    
54
116
    linegraph = []    
55
117
    
56
 
    for (rev_index, (sequence_number,
57
 
                     revid,
58
 
                     merge_depth,
59
 
                     revno_sequence,
60
 
                     end_of_merge)) in enumerate(merge_sorted_revisions):
61
 
        
62
 
        revid_index[revid] = rev_index
63
 
        revno_index[revno_sequence] = rev_index
64
 
        
65
 
        branch_id = revno_sequence[0:-1]
66
 
        
67
 
        branch_line = None
68
 
        if branch_id not in branch_lines:
69
 
            branch_line = {"line_type": "branch_line",
70
 
                           "branch_id": branch_id,
71
 
                           "rev_indexes": [],
72
 
                           "min_index": rev_index,
73
 
                           "max_index": 0}
74
 
            branch_lines[branch_id] = branch_line
75
 
        else:
76
 
            branch_line = branch_lines[branch_id]
77
 
        branch_line["rev_indexes"].append(rev_index)
78
 
        if rev_index > branch_line["max_index"]:
79
 
            branch_line["max_index"] = rev_index
80
 
        
81
 
        parents = graph_parents[revid]
82
 
        for parent_revid in parents:
83
 
            graph_children[parent_revid].append(revid)
84
 
        
85
 
        linegraph.append([revid,
86
 
                          None,
87
 
                          [],
88
 
                          parents,
89
 
                          None,
90
 
                          revno_sequence])
91
 
 
92
 
    branch_ids = branch_lines.keys()
93
 
    def branch_id_cmp(x, y):
94
 
        len_x = len(x)
95
 
        len_y = len(y)
96
 
        if len_x == len_y:
97
 
            return -cmp(x, y)
98
 
        return cmp(len_x, len_y)
99
 
        
100
 
    branch_ids.sort(branch_id_cmp)
101
 
    lines = []
102
 
    columns = []
103
 
    
104
 
    for branch_id in branch_ids:
105
 
        branch_line = branch_lines[branch_id]
106
 
        
107
 
        append_line(columns, branch_line)
108
 
        branch_id = branch_line["branch_id"]
109
 
        color = reduce(lambda x, y: x+y, branch_id, 0)
110
 
        col_index = branch_line["col_index"]
111
 
        node = (col_index, color)        
112
 
        
113
 
        for rev_index in branch_line["rev_indexes"]:
114
 
            (sequence_number,
115
 
                 revid,
116
 
                 merge_depth,
117
 
                 revno_sequence,
118
 
                 end_of_merge) = merge_sorted_revisions[rev_index]
119
 
            
120
 
            linegraph[rev_index][1] = node
121
 
            linegraph[rev_index][4] = graph_children[revid]
122
 
            
123
 
            for parent_revid in graph_parents[revid]:
124
 
                if parent_revid in revid_index:
125
 
                    parent_index = revid_index[parent_revid]
126
 
                    parent_revno = merge_sorted_revisions[parent_index][3]
127
 
                    parent_branch_id = parent_revno[0:-1]
128
 
                    line = {"line_type": "inter_branch_line",
129
 
                            "min_index": rev_index,
130
 
                            "max_index": parent_index}
131
 
                    lines.append(line)
132
 
                    if branch_id != parent_branch_id and \
133
 
                                    parent_index - rev_index > 1:
134
 
                        append_line(columns, line)
135
 
    
136
 
    for line in lines:
137
 
        parent_index = line["max_index"]
138
 
        parent_node = linegraph[parent_index][1]
139
 
        parent_col_index = parent_node[0]
140
 
        color = parent_node[1]
141
 
        
142
 
        child_index = line["min_index"]
143
 
        child_col_index = linegraph[child_index][1][0]
144
 
        
145
 
        if "col_index" in line:
146
 
            line_col_index = line["col_index"]
147
 
            linegraph[child_index][2].append(
148
 
                (child_col_index,
149
 
                 line_col_index,
150
 
                 color))
151
 
            for line_part_index in range(child_index+1, parent_index-1):
152
 
                linegraph[line_part_index][2].append(
153
 
                    (line_col_index,   
154
 
                     line_col_index,
155
 
                     color))
156
 
            linegraph[parent_index-1][2].append(
157
 
                (line_col_index,
158
 
                 parent_col_index,
159
 
                 color))
160
 
        else:
161
 
            linegraph[child_index][2].append(
162
 
                (child_col_index,
163
 
                 parent_col_index,
164
 
                 color))
165
 
            for line_part_index in range(child_index+1, parent_index):
166
 
                linegraph[line_part_index][2].append(
167
 
                    (parent_col_index,   
168
 
                     parent_col_index,
169
 
                     color))
170
 
                    
171
 
    
172
 
    return (linegraph, revid_index)
173
 
 
174
 
def append_line(columns, line):
175
 
    for col_index, column in enumerate(columns):
 
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,
 
352
                         line_col_indexes[0],
 
353
                         parent_color))
 
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)
 
375
    
 
376
 
 
377
def _branch_line_col_search_order(columns, parent_col_index):
 
378
    for col_index in range(parent_col_index, len(columns)):
 
379
        yield col_index
 
380
    for col_index in range(parent_col_index-1, -1, -1):
 
381
        yield col_index
 
382
 
 
383
def _line_col_search_order(columns, parent_col_index, child_col_index):
 
384
    if parent_col_index is not None:
 
385
        max_index = max(parent_col_index, child_col_index)
 
386
        min_index = min(parent_col_index, child_col_index)
 
387
        for col_index in range(max_index, min_index -1, -1):
 
388
            yield col_index
 
389
    else:
 
390
        max_index = child_col_index
 
391
        min_index = child_col_index
 
392
        yield child_col_index
 
393
    i = 1
 
394
    while max_index + i < len(columns) or \
 
395
          min_index - i > -1:
 
396
        if max_index + i < len(columns):
 
397
            yield max_index + i
 
398
        if min_index - i > -1:
 
399
            yield min_index - i
 
400
        i += 1
 
401
 
 
402
def _find_free_column(columns, empty_column, col_search_order, line_range):
 
403
    for col_index in col_search_order:
 
404
        column = columns[col_index]
176
405
        has_overlaping_line = False
177
 
        for col_line in column:
178
 
            if not (col_line["min_index"] >= line["max_index"] or \
179
 
                    col_line["max_index"] <=  line["min_index"]):
 
406
        for row_index in line_range:
 
407
            if column[row_index]:
180
408
                has_overlaping_line = True
181
409
                break
182
410
        if not has_overlaping_line:
183
411
            break
184
412
    else:
185
413
        col_index = len(columns)
186
 
        columns.append([])
187
 
    line["col_index"] = col_index
188
 
    columns[col_index].append(line)
189
 
    
 
414
        column = list(empty_column)
 
415
        columns.append(column)
 
416
    return col_index
190
417
 
 
418
def _mark_column_as_used(columns, col_index, line_range):
 
419
    column = columns[col_index]
 
420
    for row_index in line_range:
 
421
        column[row_index] = True    
191
422
 
192
423
def same_branch(a, b):
193
424
    """Return whether we think revisions a and b are on the same branch."""