/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

  • Committer: Daniel Schierbeck
  • Date: 2007-12-06 23:37:06 UTC
  • mto: This revision was merged to the branch mainline in revision 417.
  • Revision ID: daniel.schierbeck@gmail.com-20071206233706-eeinks66w86r3gfm
Fixed bug in gmissing.

Show diffs side-by-side

added added

removed removed

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