« back to all changes in this revision
Viewing changes to bzrlib/tsort.py
- browse files at revision 1624.1.2
- compare with another revision
- compare with revision 5452
- download diff
- download tarball
- view history from revision 1624.1.2
- Committer: Robert Collins
- Date: 2006-03-28 11:16:28 UTC
- mto: (1626.2.1 integration)
- mto: This revision was merged to the branch mainline in revision 1628.
- Revision ID: robertc@robertcollins.net-20060328111628-47766b0fdfa443ab
Add MergeSort facility to bzrlib.tsort.
- files modified:
- bzrlib/tests/test_tsort.py
added
removed
bzrlib/tsort.py
21
21
import bzrlib.errors as errors
22
22
23
23
24
__all__ = ["topo_sort", "TopoSorter", "merge_sort", "MergeSorter"]
25
26
24
27
def topo_sort(graph):
25
28
"""Topological sort a graph.
26
29
29
32
The result is a list of node names, such that all parents come before
30
33
their children.
31
34
32
Nodes at the same depth are returned in sorted order.
33
34
35
node identifiers can be any hashable object, and are typically strings.
35
36
"""
36
37
return TopoSorter(graph).sorted()
141
142
Names in this stack will get emitted into the output as they are popped
142
143
off the stack.
143
144
"""
144
145
self._node_name_stack.append(node_name)
146
self._pending_parents_stack.append(list(parents))
147
148
def _pop_node(self):
149
"""Pop the top node off the stack
150
151
The node is appended to the sorted output.
152
"""
153
# we are returning from the flattened call frame:
154
# pop off the local variables
155
node_name = self._node_name_stack.pop()
156
self._pending_parents_stack.pop()
157
158
self._completed_node_names.add(node_name)
145
self._node_name_stack.append(node_name)
146
self._pending_parents_stack.append(list(parents))
147
148
def _pop_node(self):
149
"""Pop the top node off the stack
150
151
The node is appended to the sorted output.
152
"""
153
# we are returning from the flattened call frame:
154
# pop off the local variables
155
node_name = self._node_name_stack.pop()
156
self._pending_parents_stack.pop()
157
158
self._completed_node_names.add(node_name)
159
return node_name
160
161
162
def merge_sort(graph, branch_tip):
163
"""Topological sort a graph which groups merges.
164
165
:param graph: sequence of pairs of node->parents_list.
166
:param branch_tip: the tip of the branch to graph. Revisions not
167
reachable from branch_tip are not included in the
168
output.
169
170
The result is a list of node names, such that all parents come before
171
their children.
172
173
node identifiers can be any hashable object, and are typically strings.
174
"""
175
return MergeSorter(graph, branch_tip).sorted()
176
177
178
class MergeSorter(object):
179
180
def __init__(self, graph, branch_tip):
181
"""Merge-aware topological sorting of a graph.
182
183
:param graph: sequence of pairs of node_name->parent_names_list.
184
i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
185
For this input the output from the sort or
186
iter_topo_order routines will be:
187
'A', 'B', 'C'
188
189
node identifiers can be any hashable object, and are typically strings.
190
191
If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
192
one of the two values for 'a'.
193
194
The graph is sorted lazily: until you iterate or sort the input is
195
not processed other than to create an internal representation.
196
197
iteration or sorting may raise GraphCycleError if a cycle is present
198
in the graph.
199
200
Background information on the design:
201
-------------------------------------
202
definition: the end of any cluster or 'merge' occurs when:
203
1 - the next revision has a lower merge depth than we do.
204
i.e.
205
A 0
206
B 1
207
C 2
208
D 1
209
E 0
210
C, D are the ends of clusters, E might be but we need more data.
211
2 - or the next revision at our merge depth is not our left most
212
ancestor.
213
This is required to handle multiple-merges in one commit.
214
i.e.
215
A 0 [F, B, E]
216
B 1 [D, C]
217
C 2 [D]
218
D 1 [F]
219
E 1 [F]
220
F 0
221
C is the end of a cluster due to rule 1.
222
D is not the end of a cluster from rule 1, but is from rule 2: E
223
is not its left most ancestor
224
E is the end of a cluster due to rule 1
225
F might be but we need more data.
226
227
we show connecting lines to a parent when:
228
- The parent is the start of a merge within this cluster.
229
That is, the merge was not done to the mainline before this cluster
230
was merged to the mainline.
231
This can be detected thus:
232
* The parent has a higher merge depth and is the next revision in
233
the list.
234
235
The next revision in the list constraint is needed for this case:
236
A 0 [D, B]
237
B 1 [C, F] # we do not want to show a line to F which is depth 2
238
but not a merge
239
C 1 [H] # note that this is a long line to show back to the
240
ancestor - see the end of merge rules.
241
D 0 [G, E]
242
E 1 [G, F]
243
F 2 [G]
244
G 1 [H]
245
H 0
246
- Part of this merges 'branch':
247
The parent has the same merge depth and is our left most parent and we
248
are not the end of the cluster.
249
A 0 [C, B] lines: [B, C]
250
B 1 [E, C] lines: [C]
251
C 0 [D] lines: [D]
252
D 0 [F, E] lines: [E, F]
253
E 1 [F] lines: [F]
254
F 0
255
- The end of this merge/cluster:
256
we can ONLY have multiple parents at the end of a cluster if this
257
branch was previously merged into the 'mainline'.
258
- if we have one and only one parent, show it
259
Note that this may be to a greater merge depth - for instance if
260
this branch continued from a deeply nested branch to add something
261
to it.
262
- if we have more than one parent - show the second oldest (older ==
263
further down the list) parent with
264
an equal or lower merge depth
265
XXXX revisit when awake. ddaa asks about the relevance of each one
266
- maybe more than one parent is relevant
267
"""
268
# a dict of the graph.
269
self._graph = dict(graph)
270
# we need to do a check late in the process to detect end-of-merges
271
# which requires the parents to be accessible: its easier for now
272
# to just keep the original graph around.
273
self._original_graph = dict(graph)
274
275
# this is a stack storing the depth first search into the graph.
276
self._node_name_stack = []
277
# at each level of recursion we need the merge depth this node is at:
278
self._node_merge_depth_stack = []
279
# at each level of 'recursion' we have to check each parent. This
280
# stack stores the parents we have not yet checked for the node at the
281
# matching depth in _node_name_stack
282
self._pending_parents_stack = []
283
# this is a set of the nodes who have been completely analysed for fast
284
# membership checking
285
self._completed_node_names = set()
286
# this is the scheduling of nodes list.
287
# Nodes are scheduled
288
# from the bottom left of the tree: in the tree
289
# A 0 [D, B]
290
# B 1 [C]
291
# C 1 [D]
292
# D 0 [F, E]
293
# E 1 [F]
294
# F 0
295
# the scheduling order is: F, E, D, C, B, A
296
# that is - 'left subtree, right subtree, node'
297
# which would mean that when we schedule A we can emit the entire tree.
298
self._scheduled_nodes = []
299
# This records for each node when we have processed its left most
300
# unmerged subtree. After this subtree is scheduled, all other subtrees
301
# have their merge depth increased by one from this nodes merge depth.
302
self._left_subtree_done_stack = []
303
304
# seed the search with the tip of the branch
305
if branch_tip is not None:
306
parents = self._graph.pop(branch_tip)
307
self._push_node(branch_tip, 0, parents)
308
309
def sorted(self):
310
"""Sort the graph and return as a list.
311
312
After calling this the sorter is empty and you must create a new one.
313
"""
314
return list(self.iter_topo_order())
315
316
def iter_topo_order(self):
317
"""Yield the nodes of the graph in a topological order.
318
319
After finishing iteration the sorter is empty and you cannot continue
320
iteration.
321
"""
322
while self._node_name_stack:
323
# loop until this call completes.
324
parents_to_visit = self._pending_parents_stack[-1]
325
# if all parents are done, the revision is done
326
if not parents_to_visit:
327
# append the revision to the topo sorted scheduled list:
328
# all the nodes parents have been scheduled added, now
329
# we can add it to the output.
330
self._pop_node()
331
else:
332
while self._pending_parents_stack[-1]:
333
if not self._left_subtree_done_stack[-1]:
334
# recurse depth first into the primary parent
335
next_node_name = self._pending_parents_stack[-1].pop(0)
336
else:
337
# place any merges in right-to-left order for scheduling
338
# which gives us left-to-right order after we reverse
339
# the scheduled queue. XXX: This has the effect of
340
# allocating common-new revisions to the right-most
341
# subtree rather than the left most, which will
342
# display nicely (you get smaller trees at the top
343
# of the combined merge).
344
next_node_name = self._pending_parents_stack[-1].pop()
345
if next_node_name in self._completed_node_names:
346
# this parent was completed by a child on the
347
# call stack. skip it.
348
continue
349
# otherwise transfer it from the source graph into the
350
# top of the current depth first search stack.
351
try:
352
parents = self._graph.pop(next_node_name)
353
except KeyError:
354
# if the next node is not in the source graph it has
355
# already been popped from it and placed into the
356
# current search stack (but not completed or we would
357
# have hit the continue 4 lines up.
358
# this indicates a cycle.
359
raise errors.GraphCycleError(self._node_name_stack)
360
next_merge_depth = 0
361
if self._left_subtree_done_stack[-1]:
362
next_merge_depth = 1
363
else:
364
next_merge_depth = 0
365
self._left_subtree_done_stack[-1] = True
366
next_merge_depth = (
367
self._node_merge_depth_stack[-1] + next_merge_depth)
368
self._push_node(
369
next_node_name,
370
next_merge_depth,
371
parents)
372
# and do not continue processing parents until this 'call'
373
# has recursed.
374
break
375
# We have scheduled the graph. Now deliver the ordered output:
376
sequence_number = 0
377
while self._scheduled_nodes:
378
node_name, merge_depth = self._scheduled_nodes.pop()
379
if not len(self._scheduled_nodes):
380
end_of_merge = True
381
elif self._scheduled_nodes[-1][1] < merge_depth:
382
# the next node is to our left
383
end_of_merge = True
384
elif (self._scheduled_nodes[-1][1] == merge_depth and
385
(self._scheduled_nodes[-1][0] not in
386
self._original_graph[node_name])):
387
# the next node was part of a multiple-merge.
388
end_of_merge = True
389
else:
390
end_of_merge = False
391
yield (sequence_number, node_name, merge_depth, end_of_merge)
392
sequence_number += 1
393
394
def _push_node(self, node_name, merge_depth, parents):
395
"""Add node_name to the pending node stack.
396
397
Names in this stack will get emitted into the output as they are popped
398
off the stack.
399
"""
400
self._node_name_stack.append(node_name)
401
self._node_merge_depth_stack.append(merge_depth)
402
self._left_subtree_done_stack.append(False)
403
self._pending_parents_stack.append(list(parents))
404
405
def _pop_node(self):
406
"""Pop the top node off the stack
407
408
The node is appended to the sorted output.
409
"""
410
# we are returning from the flattened call frame:
411
# pop off the local variables
412
node_name = self._node_name_stack.pop()
413
merge_depth = self._node_merge_depth_stack.pop()
414
self._left_subtree_done_stack.pop()
415
self._pending_parents_stack.pop()
416
417
self._completed_node_names.add(node_name)
418
self._scheduled_nodes.append((node_name, merge_depth))
159
419
return node_name
Loggerhead is a web-based interface for Breezy
Version: 2.0.1