« back to all changes in this revision
Viewing changes to bzrlib/tsort.py
- browse files at revision 2084
- compare with another revision
- compare with revision 1904.2.1
- download diff
- download tarball
- view history from revision 2084
- Committer: Canonical.com Patch Queue Manager
- Date: 2006-10-16 10:03:21 UTC
- mfrom: (1988.4.6 dotted-revno-input.)
- Revision ID: pqm@pqm.ubuntu.com-20061016100321-c4951c9fc020dbd0
(Robert Collins) Output dotted decimal revision numbers during log, and accept them as revision specifiers.
added
removed
bzrlib/tsort.py
159
159
return node_name
160
160
161
161
162
def merge_sort(graph, branch_tip, mainline_revisions=None):
162
def merge_sort(graph, branch_tip, mainline_revisions=None, generate_revno=False):
163
163
"""Topological sort a graph which groups merges.
164
164
165
165
:param graph: sequence of pairs of node->parents_list.
174
174
old revision listed in the mainline revisions
175
175
list.
176
176
The order for this parameter is oldest-first.
177
178
The result is a list of node names, such that all parents come before
179
their children.
180
177
:param generate_revno: Optional parameter controlling the generation of
178
revision number sequences in the output. See the output description of
179
the MergeSorter docstring for details.
180
:result: See the MergeSorter docstring for details.
181
181
node identifiers can be any hashable object, and are typically strings.
182
182
"""
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
183
return MergeSorter(graph, branch_tip, mainline_revisions,
184
generate_revno).sorted()
184
185
185
186
186
187
class MergeSorter(object):
187
188
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
189
def __init__(self, graph, branch_tip, mainline_revisions=None,
190
generate_revno=False):
189
191
"""Merge-aware topological sorting of a graph.
190
192
191
193
:param graph: sequence of pairs of node_name->parent_names_list.
204
206
old revision listed in the mainline revisions
205
207
list.
206
208
The order for this parameter is oldest-first.
209
:param generate_revno: Optional parameter controlling the generation of
210
revision number sequences in the output. See the output description
211
for more details.
212
213
The result is a list sorted so that all parents come before
214
their children. Each element of the list is a tuple containing:
215
(sequence_number, node_name, merge_depth, end_of_merge)
216
* sequence_number: The sequence of this row in the output. Useful for
217
GUIs.
218
* node_name: The node name: opaque text to the merge routine.
219
* merge_depth: How many levels of merging deep this node has been
220
found.
221
* revno_sequence: When requested this field provides a sequence of
222
revision numbers for all revisions. The format is:
223
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
224
branch that the revno is on. From left to right the REVNO numbers
225
are the sequence numbers within that branch of the revision.
226
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
227
the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
228
This should be read as 'A is the first commit in the trunk',
229
'B is the first commit on the first branch made from A', 'C is the
230
second commit in the trunk'.
231
* end_of_merge: When True the next node is part of a different merge.
207
232
208
233
209
234
node identifiers can be any hashable object, and are typically strings.
285
310
XXXX revisit when awake. ddaa asks about the relevance of each one
286
311
- maybe more than one parent is relevant
287
312
"""
313
self._generate_revno = generate_revno
288
314
# a dict of the graph.
289
315
self._graph = dict(graph)
290
316
# if there is an explicit mainline, alter the graph to match. This is
315
341
# which requires the parents to be accessible: its easier for now
316
342
# to just keep the original graph around.
317
343
self._original_graph = dict(self._graph.items())
344
# we need to know the revision numbers of revisions to determine
345
# the revision numbers of their descendants
346
# this is a graph from node to [revno_tuple, sequence_number]
347
# where sequence is the number of branches made from the node,
348
# and revno_tuple is the tuple that was assigned to the node.
349
# we dont know revnos to start with, so we start it seeded with
350
# [None, 0]
351
self._revnos = dict((revision, [None, 0]) for revision in self._graph)
352
# the global implicit root node has revno 0, but we need to know
353
# the sequence number for it too:
354
self._root_sequence = 0
318
355
319
356
# this is a stack storing the depth first search into the graph.
320
357
self._node_name_stack = []
324
361
# stack stores the parents we have not yet checked for the node at the
325
362
# matching depth in _node_name_stack
326
363
self._pending_parents_stack = []
364
# When we first look at a node we assign it a seqence number from its
365
# leftmost parent.
366
self._assigned_sequence_stack = []
327
367
# this is a set of the nodes who have been completely analysed for fast
328
368
# membership checking
329
369
self._completed_node_names = set()
343
383
# This records for each node when we have processed its left most
344
384
# unmerged subtree. After this subtree is scheduled, all other subtrees
345
385
# have their merge depth increased by one from this nodes merge depth.
346
self._left_subtree_done_stack = []
386
# it contains tuples - name, merge_depth
387
self._left_subtree_pushed_stack = []
347
388
348
389
# seed the search with the tip of the branch
349
390
if branch_tip is not None:
374
415
self._pop_node()
375
416
else:
376
417
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
418
if not self._left_subtree_pushed_stack[-1]:
378
419
# recurse depth first into the primary parent
379
420
next_node_name = self._pending_parents_stack[-1].pop(0)
380
421
else:
402
443
# this indicates a cycle.
403
444
raise errors.GraphCycleError(self._node_name_stack)
404
445
next_merge_depth = 0
405
if self._left_subtree_done_stack[-1]:
446
if self._left_subtree_pushed_stack[-1]:
447
# a new child branch from name_stack[-1]
406
448
next_merge_depth = 1
407
449
else:
408
450
next_merge_depth = 0
409
self._left_subtree_done_stack[-1] = True
451
self._left_subtree_pushed_stack[-1] = True
410
452
next_merge_depth = (
411
453
self._node_merge_depth_stack[-1] + next_merge_depth)
412
454
self._push_node(
419
461
# We have scheduled the graph. Now deliver the ordered output:
420
462
sequence_number = 0
421
463
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
464
node_name, merge_depth, revno = self._scheduled_nodes.pop()
423
465
if node_name == self._stop_revision:
424
466
return
425
467
if not len(self._scheduled_nodes):
468
# last revision is the end of a merge
426
469
end_of_merge = True
427
470
elif self._scheduled_nodes[-1][1] < merge_depth:
428
471
# the next node is to our left
434
477
end_of_merge = True
435
478
else:
436
479
end_of_merge = False
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
480
if self._generate_revno:
481
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
482
else:
483
yield (sequence_number, node_name, merge_depth, end_of_merge)
438
484
sequence_number += 1
439
485
440
486
def _push_node(self, node_name, merge_depth, parents):
445
491
"""
446
492
self._node_name_stack.append(node_name)
447
493
self._node_merge_depth_stack.append(merge_depth)
448
self._left_subtree_done_stack.append(False)
494
self._left_subtree_pushed_stack.append(False)
449
495
self._pending_parents_stack.append(list(parents))
496
# as we push it, assign it a sequence number against its parent:
497
parents = self._original_graph[node_name]
498
if parents:
499
# node has parents, assign from the left most parent.
500
parent_revno = self._revnos[parents[0]]
501
sequence = parent_revno[1]
502
parent_revno[1] += 1
503
else:
504
# no parents, use the root sequence
505
sequence = self._root_sequence
506
self._root_sequence +=1
507
self._assigned_sequence_stack.append(sequence)
450
508
451
509
def _pop_node(self):
452
510
"""Pop the top node off the stack
457
515
# pop off the local variables
458
516
node_name = self._node_name_stack.pop()
459
517
merge_depth = self._node_merge_depth_stack.pop()
460
self._left_subtree_done_stack.pop()
518
sequence = self._assigned_sequence_stack.pop()
519
# remove this node from the pending lists:
520
self._left_subtree_pushed_stack.pop()
461
521
self._pending_parents_stack.pop()
462
522
523
parents = self._original_graph[node_name]
524
if parents:
525
# node has parents, assign from the left most parent.
526
parent_revno = self._revnos[parents[0]]
527
if sequence:
528
# not the first child, make a new branch
529
revno = parent_revno[0] + (sequence, 1)
530
else:
531
# increment the sequence number within the branch
532
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
533
else:
534
# no parents, use the root sequence
535
if sequence:
536
# make a parallel import revision number
537
revno = (0, sequence, 1)
538
else:
539
revno = (1,)
540
541
# store the revno for this node for future reference
542
self._revnos[node_name][0] = revno
463
543
self._completed_node_names.add(node_name)
464
self._scheduled_nodes.append((node_name, merge_depth))
544
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
465
545
return node_name
Loggerhead is a web-based interface for Breezy
Version: 2.0.1