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 450.1.14
- compare with another revision
- download diff
- download tarball
- view history from revision 450.1.14
- Committer: Jelmer Vernooij
- Date: 2008-04-02 13:36:55 UTC
- mto: (450.9.2 graphcell-selected) (461.1.2 trunk) (471.1.1 bzr-gtk)
- mto: This revision was merged to the branch mainline in revision 458.
- Revision ID: jelmer@samba.org-20080402133655-ygtmjz2fh9k0o17s
Fix regressions in plugins tab.
- files added:
- gpg.py
- files removed:
- bzr-gtk.applications
- files renamed:
- bzr-handle-patch => handle-patch
- files modified:
- .bzrignore
added
removed
branchview/linegraph.py
1
# -*- coding: UTF-8 -*-
1
2
"""Directed graph production.
2
3
3
4
This module contains the code to produce an ordered directed graph of a
5
6
window.
6
7
"""
7
8
8
__copyright__ = "Copyright 2005 Canonical Ltd."
9
__copyright__ = "Copyright © 2005 Canonical Ltd."
9
10
__author__ = "Scott James Remnant <scott@ubuntu.com>"
10
11
11
from bzrlib.revision import NULL_REVISION
12
12
from bzrlib.tsort import merge_sort
13
from bzrlib import ui
14
13
15
def linegraph(graph, start_revs, maxnum=None, broken_line_length=None,
16
graph_data=True, mainline_only=False, root_progress=None):
14
def linegraph(repository, start_revs, maxnum, broken_line_length = None,
15
graph_data = True, mainline_only = False):
17
16
"""Produce a directed graph of a bzr repository.
18
17
19
18
Returns a tuple of (line_graph, revid_index, columns_len) where
42
41
It's up to you how to actually draw the nodes and lines (straight,
43
42
curved, kinked, etc.) and to pick the actual colours for each index.
44
43
"""
45
assert isinstance(start_revs, list)
46
def update_root_progress(step_number):
47
"""IFF our container received a root progress bar, then update it."""
48
if root_progress is not None:
49
root_progress.update(None, step_number)
50
44
45
graph = repository.get_graph()
51
46
graph_parents = {}
52
ghosts = set()
53
47
graph_children = {}
54
update_root_progress(1)
55
progress_bar = ui.ui_factory.nested_progress_bar()
56
try:
57
progress_bar.update("Arranging tree fragments")
58
for i, (revid, parent_revids) in enumerate(graph.iter_ancestry(start_revs)):
59
if i % 25 == 0:
60
progress_bar.tick()
61
if parent_revids is None:
62
ghosts.add(revid)
63
continue
64
if parent_revids == (NULL_REVISION,):
65
graph_parents[revid] = ()
66
else:
67
graph_parents[revid] = parent_revids
68
for parent in parent_revids:
69
graph_children.setdefault(parent, []).append(revid)
70
graph_children.setdefault(revid, [])
71
finally:
72
progress_bar.finished()
48
for (revid, parent_revids) in graph.iter_ancestry(start_revs):
49
graph_parents[revid] = parent_revids
50
graph_children[revid] = []
73
51
74
update_root_progress(2)
75
progress_bar = ui.ui_factory.nested_progress_bar()
76
try:
77
progress_bar.update("Removing ghosts", 0, len(ghosts))
78
for i, ghost in enumerate(ghosts):
79
if i % 25 == 0:
80
progress_bar.update(None, i)
81
for ghost_child in graph_children[ghost]:
82
graph_parents[ghost_child] = [p for p in graph_parents[ghost_child]
83
if p not in ghosts]
84
finally:
85
progress_bar.finished()
86
52
graph_parents["top:"] = start_revs
87
53
88
54
if len(graph_parents)>0:
114
80
115
81
linegraph = []
116
82
117
update_root_progress(3)
118
progress_bar = ui.ui_factory.nested_progress_bar()
119
try:
120
progress_bar.update("Finding nodes", 0, len(merge_sorted_revisions))
121
for (rev_index, (sequence_number,
122
revid,
123
merge_depth,
124
revno_sequence,
125
end_of_merge)) in enumerate(merge_sorted_revisions):
126
127
if rev_index % 25 == 0:
128
progress_bar.update(None, rev_index)
129
if maxnum and rev_index >= maxnum:
130
break
131
revid_index[revid] = rev_index
132
133
parents = graph_parents[revid]
134
linegraph.append([revid,
135
None,
136
[],
137
parents,
138
None,
139
revno_sequence])
140
141
if graph_data:
142
revno_index[revno_sequence] = rev_index
143
144
branch_id = revno_sequence[0:-1]
145
146
branch_line = None
147
if branch_id not in branch_lines:
148
branch_line = []
149
branch_lines[branch_id] = branch_line
150
else:
151
branch_line = branch_lines[branch_id]
152
153
branch_line.append(rev_index)
154
finally:
155
progress_bar.finished()
83
for (rev_index, (sequence_number,
84
revid,
85
merge_depth,
86
revno_sequence,
87
end_of_merge)) in enumerate(merge_sorted_revisions):
88
if maxnum and rev_index >= maxnum:
89
break
90
revid_index[revid] = rev_index
91
92
parents = graph_parents[revid]
93
for parent_revid in parents:
94
graph_children[parent_revid].append(revid)
95
96
linegraph.append([revid,
97
None,
98
[],
99
parents,
100
None,
101
revno_sequence])
102
103
if graph_data:
104
revno_index[revno_sequence] = rev_index
105
106
branch_id = revno_sequence[0:-1]
107
108
branch_line = None
109
if branch_id not in branch_lines:
110
branch_line = []
111
branch_lines[branch_id] = branch_line
112
else:
113
branch_line = branch_lines[branch_id]
114
115
branch_line.append(rev_index)
156
116
157
117
if graph_data:
158
118
branch_ids = branch_lines.keys()
180
140
columns = [list(empty_column)]
181
141
182
142
183
update_root_progress(4)
184
progress_bar = ui.ui_factory.nested_progress_bar()
185
try:
186
progress_bar.update("Organizing edges", 0, len(branch_ids))
187
for i, branch_id in enumerate(branch_ids):
188
if i % 25 == 0:
189
progress_bar.update(None, i)
190
branch_line = branch_lines[branch_id]
191
192
# Find the col_index for the direct parent branch. This will be the
193
# starting point when looking for a free column.
194
parent_col_index = 0
195
parent_index = None
196
if len(branch_id) > 1:
197
parent_revno = branch_id[0:-1]
198
if parent_revno in revno_index:
199
parent_index = revno_index[parent_revno]
143
for branch_id in branch_ids:
144
branch_line = branch_lines[branch_id]
145
146
# Find the col_index for the direct parent branch. This will be the
147
# starting point when looking for a free column.
148
parent_col_index = 0
149
parent_index = None
150
if len(branch_id) > 1:
151
parent_revno = branch_id[0:-1]
152
if parent_revno in revno_index:
153
parent_index = revno_index[parent_revno]
154
parent_node = linegraph[parent_index][1]
155
if parent_node:
156
parent_col_index = parent_node[0]
157
158
159
col_search_order = _branch_line_col_search_order(columns,
160
parent_col_index)
161
color = reduce(lambda x, y: x+y, branch_id, 0)
162
cur_cont_line = []
163
164
line_range = []
165
last_rev_index = None
166
for rev_index in branch_line:
167
if last_rev_index:
168
if broken_line_length and \
169
rev_index - last_rev_index > broken_line_length:
170
line_range.append(last_rev_index+1)
171
line_range.append(rev_index-1)
172
else:
173
line_range.extend(range(last_rev_index+1, rev_index))
174
175
line_range.append(rev_index)
176
last_rev_index = rev_index
177
178
if parent_index:
179
if broken_line_length and \
180
parent_index - last_rev_index > broken_line_length:
181
line_range.append(last_rev_index+1)
182
else:
183
line_range.extend(range(last_rev_index+1, parent_index))
184
185
col_index = _find_free_column(columns,
186
empty_column,
187
col_search_order,
188
line_range)
189
node = (col_index, color)
190
for rev_index in branch_line:
191
linegraph[rev_index][1] = node
192
columns[col_index][rev_index] = True
193
194
for rev_index in branch_line:
195
(sequence_number,
196
revid,
197
merge_depth,
198
revno_sequence,
199
end_of_merge) = merge_sorted_revisions[rev_index]
200
201
linegraph[rev_index][4] = graph_children[revid]
202
col_index = linegraph[rev_index][1][0]
203
204
for parent_revid in graph_parents[revid]:
205
if parent_revid in revid_index:
206
207
parent_index = revid_index[parent_revid]
200
208
parent_node = linegraph[parent_index][1]
201
209
if parent_node:
202
210
parent_col_index = parent_node[0]
203
204
205
col_search_order = _branch_line_col_search_order(columns,
206
parent_col_index)
207
color = reduce(lambda x, y: x+y, branch_id, 0)
208
cur_cont_line = []
209
210
line_range = []
211
last_rev_index = None
212
for rev_index in branch_line:
213
if last_rev_index:
214
if broken_line_length and \
215
rev_index - last_rev_index > broken_line_length:
216
line_range.append(last_rev_index+1)
217
line_range.append(rev_index-1)
218
211
else:
219
line_range.extend(range(last_rev_index+1, rev_index))
220
221
line_range.append(rev_index)
222
last_rev_index = rev_index
223
224
if parent_index:
225
if broken_line_length and \
226
parent_index - last_rev_index > broken_line_length:
227
line_range.append(last_rev_index+1)
228
else:
229
line_range.extend(range(last_rev_index+1, parent_index))
230
231
col_index = _find_free_column(columns,
232
empty_column,
233
col_search_order,
234
line_range)
235
node = (col_index, color)
236
for rev_index in branch_line:
237
linegraph[rev_index][1] = node
238
columns[col_index][rev_index] = True
239
240
for rev_index in branch_line:
241
(sequence_number,
242
revid,
243
merge_depth,
244
revno_sequence,
245
end_of_merge) = merge_sorted_revisions[rev_index]
246
247
linegraph[rev_index][4] = graph_children[revid]
248
col_index = linegraph[rev_index][1][0]
249
250
for parent_revid in graph_parents[revid]:
251
if parent_revid in revid_index:
252
253
parent_index = revid_index[parent_revid]
254
parent_node = linegraph[parent_index][1]
255
if parent_node:
256
parent_col_index = parent_node[0]
257
else:
258
parent_col_index = None
212
parent_col_index = None
213
col_search_order = \
214
_line_col_search_order(columns,
215
parent_col_index,
216
col_index)
217
218
# If this line is really long, break it.
219
if len(branch_id) > 0 and \
220
broken_line_length and \
221
parent_index - rev_index > broken_line_length:
222
child_line_col_index = \
223
_find_free_column(columns,
224
empty_column,
225
col_search_order,
226
(rev_index + 1,))
227
_mark_column_as_used(columns,
228
child_line_col_index,
229
(rev_index + 1,))
230
231
# Recall _line_col_search_order to reset it back to
232
# the beging.
259
233
col_search_order = \
260
234
_line_col_search_order(columns,
261
235
parent_col_index,
262
236
col_index)
263
264
# If this line is really long, break it.
265
if len(branch_id) > 0 and \
266
broken_line_length and \
267
parent_index - rev_index > broken_line_length:
268
child_line_col_index = \
269
_find_free_column(columns,
270
empty_column,
271
col_search_order,
272
(rev_index + 1,))
273
_mark_column_as_used(columns,
274
child_line_col_index,
275
(rev_index + 1,))
276
277
# Recall _line_col_search_order to reset it back to
278
# the beging.
279
col_search_order = \
280
_line_col_search_order(columns,
281
parent_col_index,
282
col_index)
283
parent_col_line_index = \
284
_find_free_column(columns,
285
empty_column,
286
col_search_order,
287
(parent_index - 1,))
288
_mark_column_as_used(columns,
289
parent_col_line_index,
290
(parent_index - 1,))
291
lines.append((rev_index,
292
parent_index,
293
(child_line_col_index,
294
parent_col_line_index)))
295
else :
296
line_col_index = col_index
297
if parent_index - rev_index >1:
298
line_range = range(rev_index + 1, parent_index)
299
line_col_index = \
300
_find_free_column(columns,
301
empty_column,
302
col_search_order,
303
line_range)
304
_mark_column_as_used(columns,
305
line_col_index,
306
line_range)
307
lines.append((rev_index,
308
parent_index,
309
(line_col_index,)))
310
finally:
311
progress_bar.finished()
237
parent_col_line_index = \
238
_find_free_column(columns,
239
empty_column,
240
col_search_order,
241
(parent_index - 1,))
242
_mark_column_as_used(columns,
243
parent_col_line_index,
244
(parent_index - 1,))
245
lines.append((rev_index,
246
parent_index,
247
(child_line_col_index,
248
parent_col_line_index)))
249
else :
250
line_col_index = col_index
251
if parent_index - rev_index >1:
252
line_range = range(rev_index + 1, parent_index)
253
line_col_index = \
254
_find_free_column(columns,
255
empty_column,
256
col_search_order,
257
line_range)
258
_mark_column_as_used(columns,
259
line_col_index,
260
line_range)
261
lines.append((rev_index,
262
parent_index,
263
(line_col_index,)))
312
264
313
update_root_progress(5)
314
progress_bar = ui.ui_factory.nested_progress_bar()
315
try:
316
progress_bar.update("Prettifying graph", 0, len(lines))
317
for i, (child_index, parent_index, line_col_indexes) in enumerate(lines):
318
if i % 25 == 0:
319
progress_bar.update(None, i)
320
(child_col_index, child_color) = linegraph[child_index][1]
321
(parent_col_index, parent_color) = linegraph[parent_index][1]
322
323
if len(line_col_indexes) == 1:
324
if parent_index - child_index == 1:
325
linegraph[child_index][2].append(
326
(child_col_index,
327
parent_col_index,
328
parent_color))
329
else:
330
# line from the child's column to the lines column
331
linegraph[child_index][2].append(
332
(child_col_index,
333
line_col_indexes[0],
334
parent_color))
335
# lines down the line's column
336
for line_part_index in range(child_index+1, parent_index-1):
337
linegraph[line_part_index][2].append(
338
(line_col_indexes[0],
339
line_col_indexes[0],
340
parent_color))
341
# line from the line's column to the parent's column
342
linegraph[parent_index-1][2].append(
343
(line_col_indexes[0],
344
parent_col_index,
345
parent_color))
265
for (child_index, parent_index, line_col_indexes) in lines:
266
(child_col_index, child_color) = linegraph[child_index][1]
267
(parent_col_index, parent_color) = linegraph[parent_index][1]
268
269
if len(line_col_indexes) == 1:
270
if parent_index - child_index == 1:
271
linegraph[child_index][2].append(
272
(child_col_index,
273
parent_col_index,
274
parent_color))
346
275
else:
347
# Broken line
348
276
# line from the child's column to the lines column
349
277
linegraph[child_index][2].append(
350
278
(child_col_index,
351
279
line_col_indexes[0],
352
280
parent_color))
353
# Broken line end
354
linegraph[child_index+1][2].append(
355
(line_col_indexes[0],
356
None,
357
parent_color))
358
359
# Broken line end
360
linegraph[parent_index-2][2].append(
361
(None,
362
line_col_indexes[1],
363
parent_color))
281
# lines down the line's column
282
for line_part_index in range(child_index+1, parent_index-1):
283
linegraph[line_part_index][2].append(
284
(line_col_indexes[0],
285
line_col_indexes[0],
286
parent_color))
364
287
# line from the line's column to the parent's column
365
288
linegraph[parent_index-1][2].append(
366
(line_col_indexes[1],
289
(line_col_indexes[0],
367
290
parent_col_index,
368
291
parent_color))
369
finally:
370
progress_bar.finished()
292
else:
293
# Broken line
294
# line from the child's column to the lines column
295
linegraph[child_index][2].append(
296
(child_col_index,
297
line_col_indexes[0],
298
parent_color))
299
# Broken line end
300
linegraph[child_index+1][2].append(
301
(line_col_indexes[0],
302
None,
303
parent_color))
304
305
# Broken line end
306
linegraph[parent_index-2][2].append(
307
(None,
308
line_col_indexes[1],
309
parent_color))
310
# line from the line's column to the parent's column
311
linegraph[parent_index-1][2].append(
312
(line_col_indexes[1],
313
parent_col_index,
314
parent_color))
371
315
return (linegraph, revid_index, len(columns))
372
316
else:
373
317
return (linegraph, revid_index, 0)
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0