/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: Daniel Schierbeck
  • Date: 2008-04-07 20:34:51 UTC
  • mfrom: (450.6.13 bugs)
  • mto: (463.2.1 bug.78765)
  • mto: This revision was merged to the branch mainline in revision 462.
  • Revision ID: daniel.schierbeck@gmail.com-20080407203451-2i6el7jf9t0k9y64
Merged bug page improvements.

Show diffs side-by-side

added added

removed removed

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