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
- browse files at revision 511.3.1
- compare with another revision
- download diff
- download tarball
- view history from revision 511.3.1
- Committer: Jelmer Vernooij
- Date: 2008-06-28 17:13:46 UTC
- mto: This revision was merged to the branch mainline in revision 517.
- Revision ID: jelmer@samba.org-20080628171346-ob42iggcc663s4xz
Show full license details in about dialog.
- files added:
- branchview
- preferences
- files removed:
- tortoise-bzr.py
- files renamed:
- viz/graphcell.py => branchview/graphcell.py
- viz/linegraph.py => branchview/linegraph.py
- viz/treemodel.py => branchview/treemodel.py
- viz/treeview.py => branchview/treeview.py
- bzr-icon-64.png => icons/bzr-icon-64.png
- preferences.py => preferences/__init__.py
- files modified:
- AUTHORS
added
removed
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)):
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0