/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 16:24:24 UTC
  • mto: This revision was merged to the branch mainline in revision 519.
  • Revision ID: jelmer@samba.org-20080629162424-48a6rrjmmpejfcyr
Stop emitting no longer used revisions-loaded message.

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