/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: Gary van der Merwe
  • Date: 2007-09-22 14:59:45 UTC
  • mto: (256.2.54 gtk)
  • mto: This revision was merged to the branch mainline in revision 289.
  • Revision ID: garyvdm@gmail.com-20070922145945-b8100dvn57yvbxvb
* Set a width and use ellips on Revision No column.
* Pass the number of columns need to render the graph column from 
  line_graph to the graphcell so that the graphcell does not have 
  to work it out for each revision.

Show diffs side-by-side

added added

removed removed

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