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
- browse files at revision 256.2.54
- compare with another revision
- download diff
- download tarball
- view history from revision 256.2.54
- Committer: Gary van der Merwe
- Date: 2007-09-22 15:01:53 UTC
- mfrom: (256.4.1 gtk)
- mto: This revision was merged to the branch mainline in revision 289.
- Revision ID: garyvdm@gmail.com-20070922150153-zkqtq9gfj9d3pwrk
Merge viz changes
- files added:
- tests/test_viz.py
- files removed:
- branchview
- preferences
- files renamed:
- icons/bzr-icon-64.png => bzr-icon-64.png
- revisionview.py => logview.py
- preferences/__init__.py => preferences.py
- branchview/graphcell.py => viz/graphcell.py
- branchview/linegraph.py => viz/linegraph.py
- branchview/treemodel.py => viz/treemodel.py
- files modified:
- AUTHORS
added
removed
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
# FIXME: This should be configurable
45
BROKEN_LINE_LENGTH = 32
46
47
# We get the mainline so we can pass it to merge_sort to make merge_sort
48
# run faster.
49
mainline = branch.revision_history()
50
graph_parents = branch.repository.get_revision_graph(start)
48
51
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:]
52
for revid in graph_parents.iterkeys():
53
graph_children[revid] = []
54
55
merge_sorted_revisions = merge_sort(
56
graph_parents,
57
start,
58
mainline,
59
generate_revno=True)
80
60
81
61
revid_index = {}
82
62
revno_index = {}
97
77
merge_depth,
98
78
revno_sequence,
99
79
end_of_merge)) in enumerate(merge_sorted_revisions):
100
if maxnum and rev_index >= maxnum:
101
break
80
102
81
revid_index[revid] = rev_index
82
revno_index[revno_sequence] = rev_index
83
84
branch_id = revno_sequence[0:-1]
85
86
branch_line = None
87
if branch_id not in branch_lines:
88
branch_line = []
89
branch_lines[branch_id] = branch_line
90
else:
91
branch_line = branch_lines[branch_id]
92
93
branch_line.append(rev_index)
103
94
104
95
parents = graph_parents[revid]
96
for parent_revid in parents:
97
graph_children[parent_revid].append(revid)
98
105
99
linegraph.append([revid,
106
100
None,
107
101
[],
108
102
parents,
109
103
None,
110
104
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
105
106
branch_ids = branch_lines.keys()
107
108
def branch_id_cmp(x, y):
109
"""Compaire branch_id's first by the number of digits, then reversed
110
by their value"""
111
len_x = len(x)
112
len_y = len(y)
113
if len_x == len_y:
114
return -cmp(x, y)
115
return cmp(len_x, len_y)
116
117
branch_ids.sort(branch_id_cmp)
118
# This will hold a tuple of (child_index, parent_index, col_index) for each
119
# line that needs to be drawn. If col_index is not none, then the line is
120
# drawn along that column, else the the line can be drawn directly between
121
# the child and parent because either the child and parent are in the same
122
# branch line, or the child and parent are 1 row apart.
123
lines = []
124
empty_column = [False for i in range(len(graph_parents))]
125
# This will hold a bit map for each cell. If the cell is true, then the
126
# cell allready contains a node or line. This use when deciding what column
127
# to place a branch line or line in, without it overlaping something else.
128
columns = [list(empty_column)]
129
130
131
for branch_id in branch_ids:
132
branch_line = branch_lines[branch_id]
133
134
# Find the col_index for the direct parent branch. This will be the
135
# starting point when looking for a free column.
136
parent_col_index = 0
137
parent_index = None
138
if len(branch_id) > 1:
139
parent_revno = branch_id[0:-1]
140
if parent_revno in revno_index:
141
parent_index = revno_index[parent_revno]
142
parent_node = linegraph[parent_index][1]
143
if parent_node:
144
parent_col_index = parent_node[0]
145
146
147
col_search_order = _branch_line_col_search_order(columns,
148
parent_col_index)
149
color = reduce(lambda x, y: x+y, branch_id, 0)
150
cur_cont_line = []
151
152
line_range = []
153
last_rev_index = None
154
for rev_index in branch_line:
155
if last_rev_index:
156
if rev_index - last_rev_index > BROKEN_LINE_LENGTH:
157
line_range.append(last_rev_index+1)
158
line_range.append(rev_index-1)
159
else:
160
line_range.extend(range(last_rev_index+1, rev_index))
161
162
line_range.append(rev_index)
163
last_rev_index = rev_index
164
165
if parent_index:
166
if parent_index - last_rev_index > BROKEN_LINE_LENGTH:
167
line_range.append(last_rev_index+1)
121
168
else:
122
branch_line = branch_lines[branch_id]
123
124
branch_line.append(rev_index)
125
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]
169
line_range.extend(range(last_rev_index+1, parent_index))
170
171
col_index = _find_free_column(columns,
172
empty_column,
173
col_search_order,
174
line_range)
175
node = (col_index, color)
176
for rev_index in branch_line:
177
linegraph[rev_index][1] = node
178
columns[col_index][rev_index] = True
179
180
for rev_index in branch_line:
181
(sequence_number,
182
revid,
183
merge_depth,
184
revno_sequence,
185
end_of_merge) = merge_sorted_revisions[rev_index]
186
187
linegraph[rev_index][4] = graph_children[revid]
188
col_index = linegraph[rev_index][1][0]
189
190
for parent_revid in graph_parents[revid]:
191
if parent_revid in revid_index:
192
193
parent_index = revid_index[parent_revid]
163
194
parent_node = linegraph[parent_index][1]
164
195
if parent_node:
165
196
parent_col_index = parent_node[0]
166
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
197
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:
198
parent_col_index = None
199
col_search_order = \
200
_line_col_search_order(columns,
201
parent_col_index,
202
col_index)
215
203
216
parent_index = revid_index[parent_revid]
217
parent_node = linegraph[parent_index][1]
218
if parent_node:
219
parent_col_index = parent_node[0]
220
else:
221
parent_col_index = None
222
col_search_order = \
223
_line_col_search_order(columns,
224
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,)))
204
# If this line is really long, break it.
205
if len(branch_id) > 0 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
parent_col_line_index = \
216
_find_free_column(columns,
217
empty_column,
218
col_search_order,
219
(parent_index - 1,))
220
_mark_column_as_used(columns,
221
parent_col_line_index,
222
(parent_index - 1,))
223
lines.append((rev_index,
224
parent_index,
225
(child_line_col_index,
226
parent_col_line_index)))
227
else :
228
line_col_index = col_index
229
if parent_index - rev_index >1:
230
line_range = range(rev_index + 1, parent_index)
231
line_col_index = \
232
_find_free_column(columns,
233
empty_column,
234
col_search_order,
235
line_range)
236
_mark_column_as_used(columns,
237
line_col_index,
238
line_range)
239
lines.append((rev_index,
240
parent_index,
241
(line_col_index,)))
242
243
for (child_index, parent_index, line_col_indexes) in lines:
244
(child_col_index, child_color) = linegraph[child_index][1]
245
(parent_col_index, parent_color) = linegraph[parent_index][1]
273
246
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))
247
if len(line_col_indexes) == 1:
248
if parent_index - child_index == 1:
249
linegraph[child_index][2].append(
250
(child_col_index,
251
parent_col_index,
252
parent_color))
301
253
else:
302
# Broken line
303
254
# line from the child's column to the lines column
304
255
linegraph[child_index][2].append(
305
256
(child_col_index,
306
257
line_col_indexes[0],
307
258
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))
259
# lines down the line's column
260
for line_part_index in range(child_index+1, parent_index-1):
261
linegraph[line_part_index][2].append(
262
(line_col_indexes[0],
263
line_col_indexes[0],
264
parent_color))
319
265
# line from the line's column to the parent's column
320
266
linegraph[parent_index-1][2].append(
321
(line_col_indexes[1],
267
(line_col_indexes[0],
322
268
parent_col_index,
323
269
parent_color))
324
return (linegraph, revid_index, len(columns))
325
else:
326
return (linegraph, revid_index, 0)
270
else:
271
# Broken line
272
# line from the child's column to the lines column
273
linegraph[child_index][2].append(
274
(child_col_index,
275
line_col_indexes[0],
276
parent_color))
277
# Broken line end
278
linegraph[child_index+1][2].append(
279
(line_col_indexes[0],
280
None,
281
parent_color))
282
283
# Broken line end
284
linegraph[parent_index-2][2].append(
285
(None,
286
line_col_indexes[1],
287
parent_color))
288
# line from the line's column to the parent's column
289
linegraph[parent_index-1][2].append(
290
(line_col_indexes[1],
291
parent_col_index,
292
parent_color))
293
327
294
295
return (linegraph, revid_index, len(columns))
328
296
329
297
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
298
return range(parent_col_index, len(columns)) + \
299
range(parent_col_index-1, -1, -1)
334
300
335
301
def _line_col_search_order(columns, parent_col_index, child_col_index):
302
dest_col_indexes = []
336
303
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
304
dest_col_indexes.append(parent_col_index)
341
305
else:
342
max_index = child_col_index
343
min_index = child_col_index
344
yield child_col_index
306
dest_col_indexes.append(child_col_index)
307
dest_col_indexes.append(child_col_index)
308
dest_col_indexes.sort()
309
col_search_order = range(dest_col_indexes[1], dest_col_indexes[0] -1, -1)
345
310
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
311
while dest_col_indexes[1] + i < len(columns) or \
312
dest_col_indexes[0] - i > -1:
313
if dest_col_indexes[1] + i < len(columns):
314
col_search_order.append(dest_col_indexes[1] + i)
315
if dest_col_indexes[0] - i > -1:
316
col_search_order.append(dest_col_indexes[0] - i)
352
317
i += 1
318
return col_search_order
353
319
354
320
def _find_free_column(columns, empty_column, col_search_order, line_range):
355
321
for col_index in col_search_order:
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0