/b-gtk/fix-viz

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

« back to all changes in this revision

Viewing changes to branchview/linegraph.py

  • Committer: Daniel Schierbeck
  • Date: 2008-01-23 16:36:21 UTC
  • mto: (423.1.8 trunk)
  • mto: This revision was merged to the branch mainline in revision 429.
  • Revision ID: daniel.schierbeck@gmail.com-20080123163621-x8kublc38ojipnly
Made the revision popup menu correctly add tags.

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