/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: 2012-07-09 15:23:26 UTC
  • mto: This revision was merged to the branch mainline in revision 794.
  • Revision ID: jelmer@samba.org-20120709152326-dzxb8zoz0btull7n
https://launchpad.net/bugs/714767
https://launchpad.net/bugs/949798
https://launchpad.net/bugs/998994
https://launchpad.net/bugs/342135
https://launchpad.net/bugs/342136
https://launchpad.net/bugs/394536
Remove bzr-notify.

Show diffs side-by-side

added added

removed removed

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