/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: Javier Derderian
  • Date: 2008-04-11 20:34:06 UTC
  • mto: (465.1.1 gtk.patch)
  • mto: This revision was merged to the branch mainline in revision 466.
  • Revision ID: javierder@gmail.com-20080411203406-ftlwyodw9vr87olv
Updated "Compare with..." (#78765) to use revbrowser.RevisionBrowser.
Also needed to fix #215872 to make it work.

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
 
from bzrlib.revision import NULL_REVISION
12
12
from bzrlib.tsort import merge_sort
13
 
from bzrlib import ui
14
 
 
15
 
 
16
 
def linegraph(graph, start_revs, maxnum=None, broken_line_length=None,
17
 
              graph_data=True, mainline_only=False, root_progress=None):
 
13
 
 
14
def linegraph(repository, start_revs, maxnum, broken_line_length = None,
 
15
              graph_data = True, mainline_only = False):
18
16
    """Produce a directed graph of a bzr repository.
19
17
 
20
18
    Returns a tuple of (line_graph, revid_index, columns_len) where
27
25
    * revid_index is a dict of each revision with the key being the revid, and
28
26
      the value the row index, and
29
27
    * columns_len is the number of columns need to draw the line graph.
30
 
 
 
28
    
31
29
 
32
30
    Node is a tuple of (column, colour) with column being a zero-indexed
33
31
    column number of the graph that this revision represents and colour
43
41
    It's up to you how to actually draw the nodes and lines (straight,
44
42
    curved, kinked, etc.) and to pick the actual colours for each index.
45
43
    """
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(None, step_number)
51
 
 
 
44
    
 
45
    if type(start_revs) != list:
 
46
        start_revs = [start_revs]
 
47
        
 
48
    graph = repository.get_graph()
52
49
    graph_parents = {}
53
 
    ghosts = set()
54
50
    graph_children = {}
55
 
    update_root_progress(1)
56
 
    progress_bar = ui.ui_factory.nested_progress_bar()
57
 
    try:
58
 
        progress_bar.update("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()
 
51
    for (revid, parent_revids) in graph.iter_ancestry(start_revs):
 
52
        graph_parents[revid] = parent_revids
 
53
        graph_children[revid] = []
74
54
 
75
 
    update_root_progress(2)
76
 
    progress_bar = ui.ui_factory.nested_progress_bar()
77
 
    try:
78
 
        progress_bar.update("Removing ghosts", 0, len(ghosts))
79
 
        for i, ghost in enumerate(ghosts):
80
 
            if i % 25 == 0:
81
 
                progress_bar.update(None, 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
55
    graph_parents["top:"] = start_revs
88
56
 
89
57
    if len(graph_parents)>0:
93
61
            generate_revno=True)
94
62
    else:
95
63
        merge_sorted_revisions = ()
96
 
 
 
64
    
97
65
    if mainline_only:
98
66
        merge_sorted_revisions = [elem for elem in merge_sorted_revisions \
99
67
                                  if len(elem[3])==1 ]
100
68
 
101
69
    assert merge_sorted_revisions[0][1] == "top:"
102
70
    merge_sorted_revisions = merge_sorted_revisions[1:]
103
 
 
 
71
    
104
72
    revid_index = {}
105
73
    revno_index = {}
106
 
 
 
74
    
107
75
    # This will hold an item for each "branch". For a revisions, the revsion
108
76
    # number less the least significant digit is the branch_id, and used as the
109
77
    # key for the dict. Hence revision with the same revsion number less the
112
80
    # and these two revisions will be in the same branch line. Each value is
113
81
    # a list of rev_indexes in the branch.
114
82
    branch_lines = {}
115
 
 
116
 
    linegraph = []
117
 
 
118
 
    update_root_progress(3)
119
 
    progress_bar = ui.ui_factory.nested_progress_bar()
120
 
    try:
121
 
        progress_bar.update("Finding nodes", 0, 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, 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()
 
83
    
 
84
    linegraph = []    
 
85
    
 
86
    for (rev_index, (sequence_number,
 
87
                     revid,
 
88
                     merge_depth,
 
89
                     revno_sequence,
 
90
                     end_of_merge)) in enumerate(merge_sorted_revisions):
 
91
        if maxnum and rev_index >= maxnum:
 
92
            break
 
93
        revid_index[revid] = rev_index
 
94
        
 
95
        parents = graph_parents[revid]
 
96
        for parent_revid in parents:
 
97
            graph_children[parent_revid].append(revid)
 
98
        
 
99
        linegraph.append([revid,
 
100
                          None,
 
101
                          [],
 
102
                          parents,
 
103
                          None,
 
104
                          revno_sequence])
 
105
        
 
106
        if graph_data:
 
107
            revno_index[revno_sequence] = rev_index
 
108
            
 
109
            branch_id = revno_sequence[0:-1]
 
110
            
 
111
            branch_line = None
 
112
            if branch_id not in branch_lines:
 
113
                branch_line = []
 
114
                branch_lines[branch_id] = branch_line
 
115
            else:
 
116
                branch_line = branch_lines[branch_id]
 
117
            
 
118
            branch_line.append(rev_index)        
157
119
 
158
120
    if graph_data:
159
121
        branch_ids = branch_lines.keys()
160
 
 
 
122
    
161
123
        def branch_id_cmp(x, y):
162
124
            """Compaire branch_id's first by the number of digits, then reversed
163
125
            by their value"""
166
128
            if len_x == len_y:
167
129
                return -cmp(x, y)
168
130
            return cmp(len_x, len_y)
169
 
 
 
131
        
170
132
        branch_ids.sort(branch_id_cmp)
171
133
        # This will hold a tuple of (child_index, parent_index, col_index) for each
172
134
        # line that needs to be drawn. If col_index is not none, then the line is
179
141
        # cell allready contains a node or line. This use when deciding what column
180
142
        # to place a branch line or line in, without it overlaping something else.
181
143
        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("Organizing edges", 0, len(branch_ids))
188
 
            for i, branch_id in enumerate(branch_ids):
189
 
                if i % 25 == 0:
190
 
                    progress_bar.update(None, 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]
 
144
        
 
145
        
 
146
        for branch_id in branch_ids:
 
147
            branch_line = branch_lines[branch_id]
 
148
            
 
149
            # Find the col_index for the direct parent branch. This will be the
 
150
            # starting point when looking for a free column.
 
151
            parent_col_index = 0
 
152
            parent_index = None
 
153
            if len(branch_id) > 1:
 
154
                parent_revno = branch_id[0:-1]
 
155
                if parent_revno in revno_index:
 
156
                    parent_index = revno_index[parent_revno]
 
157
                    parent_node = linegraph[parent_index][1]
 
158
                    if parent_node:
 
159
                        parent_col_index = parent_node[0]
 
160
                    
 
161
            
 
162
            col_search_order = _branch_line_col_search_order(columns,
 
163
                                                             parent_col_index)
 
164
            color = reduce(lambda x, y: x+y, branch_id, 0)
 
165
            cur_cont_line = []
 
166
            
 
167
            line_range = []
 
168
            last_rev_index = None
 
169
            for rev_index in branch_line:
 
170
                if last_rev_index:
 
171
                    if broken_line_length and \
 
172
                       rev_index - last_rev_index > broken_line_length:
 
173
                        line_range.append(last_rev_index+1)
 
174
                        line_range.append(rev_index-1)
 
175
                    else:
 
176
                        line_range.extend(range(last_rev_index+1, rev_index))
 
177
                
 
178
                line_range.append(rev_index)
 
179
                last_rev_index = rev_index
 
180
            
 
181
            if parent_index:
 
182
                if broken_line_length and \
 
183
                   parent_index - last_rev_index > broken_line_length:
 
184
                    line_range.append(last_rev_index+1)
 
185
                else:
 
186
                    line_range.extend(range(last_rev_index+1, parent_index))
 
187
            
 
188
            col_index = _find_free_column(columns,
 
189
                                          empty_column,
 
190
                                          col_search_order,
 
191
                                          line_range)
 
192
            node = (col_index, color)
 
193
            for rev_index in branch_line:
 
194
                linegraph[rev_index][1] = node
 
195
                columns[col_index][rev_index] = True
 
196
            
 
197
            for rev_index in branch_line:
 
198
                (sequence_number,
 
199
                     revid,
 
200
                     merge_depth,
 
201
                     revno_sequence,
 
202
                     end_of_merge) = merge_sorted_revisions[rev_index]
 
203
                
 
204
                linegraph[rev_index][4] = graph_children[revid]
 
205
                col_index = linegraph[rev_index][1][0]
 
206
                
 
207
                for parent_revid in graph_parents[revid]:
 
208
                    if parent_revid in revid_index:
 
209
                        
 
210
                        parent_index = revid_index[parent_revid]                            
201
211
                        parent_node = linegraph[parent_index][1]
202
212
                        if parent_node:
203
213
                            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
214
                        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
 
215
                            parent_col_index = None
 
216
                        col_search_order = \
 
217
                                _line_col_search_order(columns,
 
218
                                                       parent_col_index,
 
219
                                                       col_index)
 
220
                            
 
221
                        # If this line is really long, break it.
 
222
                        if len(branch_id) > 0 and \
 
223
                           broken_line_length and \
 
224
                           parent_index - rev_index > broken_line_length:
 
225
                            child_line_col_index = \
 
226
                                _find_free_column(columns,
 
227
                                                  empty_column,
 
228
                                                  col_search_order,
 
229
                                                  (rev_index + 1,))
 
230
                            _mark_column_as_used(columns,
 
231
                                                 child_line_col_index,
 
232
                                                 (rev_index + 1,))
 
233
                            
 
234
                            # Recall _line_col_search_order to reset it back to
 
235
                            # the beging.
260
236
                            col_search_order = \
261
237
                                    _line_col_search_order(columns,
262
238
                                                           parent_col_index,
263
239
                                                           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("Prettifying graph", 0, 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, 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))
 
240
                            parent_col_line_index = \
 
241
                                _find_free_column(columns,
 
242
                                                  empty_column,
 
243
                                                  col_search_order,
 
244
                                                  (parent_index - 1,))
 
245
                            _mark_column_as_used(columns,
 
246
                                                 parent_col_line_index,
 
247
                                                 (parent_index - 1,))
 
248
                            lines.append((rev_index,
 
249
                                          parent_index,
 
250
                                          (child_line_col_index,
 
251
                                           parent_col_line_index)))
 
252
                        else :
 
253
                            line_col_index = col_index
 
254
                            if parent_index - rev_index >1:
 
255
                                line_range = range(rev_index + 1, parent_index)
 
256
                                line_col_index = \
 
257
                                    _find_free_column(columns,
 
258
                                                      empty_column,
 
259
                                                      col_search_order,
 
260
                                                      line_range)
 
261
                                _mark_column_as_used(columns,
 
262
                                                     line_col_index,
 
263
                                                     line_range)
 
264
                            lines.append((rev_index,
 
265
                                          parent_index,
 
266
                                          (line_col_index,)))
 
267
        
 
268
        for (child_index, parent_index, line_col_indexes) in lines:
 
269
            (child_col_index, child_color) = linegraph[child_index][1]
 
270
            (parent_col_index, parent_color) = linegraph[parent_index][1]
 
271
            
 
272
            if len(line_col_indexes) == 1:
 
273
                if parent_index - child_index == 1:
 
274
                    linegraph[child_index][2].append(
 
275
                        (child_col_index,
 
276
                         parent_col_index,
 
277
                         parent_color))
347
278
                else:
348
 
                    # Broken line
349
279
                    # line from the child's column to the lines column
350
280
                    linegraph[child_index][2].append(
351
281
                        (child_col_index,
352
282
                         line_col_indexes[0],
353
283
                         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))
 
284
                    # lines down the line's column
 
285
                    for line_part_index in range(child_index+1, parent_index-1):
 
286
                        linegraph[line_part_index][2].append(
 
287
                            (line_col_indexes[0],   
 
288
                             line_col_indexes[0],
 
289
                             parent_color))
365
290
                    # line from the line's column to the parent's column
366
291
                    linegraph[parent_index-1][2].append(
367
 
                        (line_col_indexes[1],
 
292
                        (line_col_indexes[0],
368
293
                         parent_col_index,
369
294
                         parent_color))
370
 
        finally:
371
 
            progress_bar.finished()
 
295
            else:
 
296
                # Broken line
 
297
                # line from the child's column to the lines column
 
298
                linegraph[child_index][2].append(
 
299
                    (child_col_index,
 
300
                     line_col_indexes[0],
 
301
                     parent_color))
 
302
                # Broken line end
 
303
                linegraph[child_index+1][2].append(
 
304
                    (line_col_indexes[0],
 
305
                     None,
 
306
                     parent_color))
 
307
                
 
308
                # Broken line end 
 
309
                linegraph[parent_index-2][2].append(
 
310
                    (None,
 
311
                     line_col_indexes[1],
 
312
                     parent_color))
 
313
                # line from the line's column to the parent's column
 
314
                linegraph[parent_index-1][2].append(
 
315
                    (line_col_indexes[1],
 
316
                     parent_col_index,
 
317
                     parent_color))
372
318
        return (linegraph, revid_index, len(columns))
373
319
    else:
374
320
        return (linegraph, revid_index, 0)
375
 
 
 
321
    
376
322
 
377
323
def _branch_line_col_search_order(columns, parent_col_index):
378
324
    for col_index in range(parent_col_index, len(columns)):
418
364
def _mark_column_as_used(columns, col_index, line_range):
419
365
    column = columns[col_index]
420
366
    for row_index in line_range:
421
 
        column[row_index] = True
 
367
        column[row_index] = True    
422
368
 
423
369
def same_branch(a, b):
424
370
    """Return whether we think revisions a and b are on the same branch."""