/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: Vincent Ladeuil
  • Date: 2008-06-10 15:25:47 UTC
  • mto: This revision was merged to the branch mainline in revision 504.
  • Revision ID: v.ladeuil+lp@free.fr-20080610152547-dwmil1p8pd0mfpnl
Fix third failing test (thanks to jam).

* tests/test_commit.py:
(TestPendingRevisions.test_pending_revisions_multi_merge): Fix
provided by jam: bzr we now filter the pending merges so that only
the 'heads()' are included. We just ensure that the pending merges
contain the unique tips for the ancestries.

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