/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: John Arbash Meinel
  • Date: 2007-10-30 21:15:13 UTC
  • mfrom: (326 trunk)
  • mto: (330.3.3 trunk)
  • mto: This revision was merged to the branch mainline in revision 368.
  • Revision ID: john@arbash-meinel.com-20071030211513-l8ukdfa81g1y74mi
Merge the latest trunk 326

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