/b-gtk/fix-viz

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz

« back to all changes in this revision

Viewing changes to branchview/linegraph.py

  • Committer: Jelmer Vernooij
  • Date: 2008-03-14 02:19:21 UTC
  • mto: (452.2.3 trunk)
  • mto: This revision was merged to the branch mainline in revision 453.
  • Revision ID: jelmer@samba.org-20080314021921-2dgptk62dhp7pd91
Honor child_submit_to in the submit_branch if no email address was specified.
Consistent with the changes in bzr.dev.

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, 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_parents = repository.get_revision_graph(start)
51
46
    graph_children = {}
52
47
    for revid in graph_parents.iterkeys():
53
48
        graph_children[revid] = []
54
49
 
55
 
    merge_sorted_revisions = merge_sort(
56
 
        graph_parents,
57
 
        start,
58
 
        mainline,
59
 
        generate_revno=True)
 
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 ]
60
61
    
61
62
    revid_index = {}
62
63
    revno_index = {}
80
81
        if maxnum and rev_index >= maxnum:
81
82
            break
82
83
        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
84
        
96
85
        parents = graph_parents[revid]
97
86
        for parent_revid in parents:
103
92
                          parents,
104
93
                          None,
105
94
                          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
 
105
            else:
 
106
                branch_line = branch_lines[branch_id]
 
107
            
 
108
            branch_line.append(rev_index)        
106
109
 
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]                            
 
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]
197
147
                    parent_node = linegraph[parent_index][1]
198
148
                    if parent_node:
199
149
                        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)
200
165
                    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.
 
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
222
206
                        col_search_order = \
223
207
                                _line_col_search_order(columns,
224
208
                                                       parent_col_index,
225
209
                                                       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]
 
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,)))
257
257
        
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))
 
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))
264
285
            else:
 
286
                # Broken line
265
287
                # line from the child's column to the lines column
266
288
                linegraph[child_index][2].append(
267
289
                    (child_col_index,
268
290
                     line_col_indexes[0],
269
291
                     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))
 
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))
276
303
                # line from the line's column to the parent's column
277
304
                linegraph[parent_index-1][2].append(
278
 
                    (line_col_indexes[0],
 
305
                    (line_col_indexes[1],
279
306
                     parent_col_index,
280
307
                     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
 
            
 
308
        return (linegraph, revid_index, len(columns))
 
309
    else:
 
310
        return (linegraph, revid_index, 0)
305
311
    
306
 
    return (linegraph, revid_index, len(columns))
307
312
 
308
313
def _branch_line_col_search_order(columns, parent_col_index):
309
314
    for col_index in range(parent_col_index, len(columns)):