/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-06-29 19:34:29 UTC
  • mto: This revision was merged to the branch mainline in revision 520.
  • Revision ID: jelmer@samba.org-20080629193429-ir2ilmbko6qkubg5
Add Branch/Index option if bzr-search is available.

Show diffs side-by-side

added added

removed removed

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