/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 viz/linegraph.py

Allow bzr-gtk and Bazaar versions to be out of sync. No longer warn about 
newer versions of Bazaar, on the assumption the API is sufficiently stable now.

Show diffs side-by-side

added added

removed removed

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