← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: Martin Pool
  • Date: 2008-06-03 07:03:55 UTC
  • mto: This revision was merged to the branch mainline in revision 3491.
  • Revision ID: mbp@sourcefrog.net-20080603070355-65ca5vd490vj9rnk
Doc updates re PPAs

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
18
"""Topological sorting routines."""
19
19
 
20
20
 
21
 
from bzrlib import (
22
 
    errors,
23
 
    graph as _mod_graph,
24
 
    revision as _mod_revision,
25
 
    )
 
21
from bzrlib import errors
 
22
import bzrlib.revision as _mod_revision
26
23
 
27
24
 
28
25
__all__ = ["topo_sort", "TopoSorter", "merge_sort", "MergeSorter"]
33
30
 
34
31
    graph -- sequence of pairs of node->parents_list.
35
32
 
36
 
    The result is a list of node names, such that all parents come before their
37
 
    children.
 
33
    The result is a list of node names, such that all parents come before
 
34
    their children.
38
35
 
39
36
    node identifiers can be any hashable object, and are typically strings.
40
 
 
41
 
    This function has the same purpose as the TopoSorter class, but uses a
42
 
    different algorithm to sort the graph. That means that while both return a
43
 
    list with parents before their child nodes, the exact ordering can be
44
 
    different.
45
 
 
46
 
    topo_sort is faster when the whole list is needed, while when iterating
47
 
    over a part of the list, TopoSorter.iter_topo_order should be used.
48
37
    """
49
 
    kg = _mod_graph.KnownGraph(dict(graph))
50
 
    return kg.topo_sort()
 
38
    return TopoSorter(graph).sorted()
51
39
 
52
40
 
53
41
class TopoSorter(object):
54
42
 
55
43
    def __init__(self, graph):
56
44
        """Topological sorting of a graph.
57
 
 
 
45
    
58
46
        :param graph: sequence of pairs of node_name->parent_names_list.
59
47
                      i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
60
48
                      For this input the output from the sort or
61
49
                      iter_topo_order routines will be:
62
50
                      'A', 'B', 'C'
63
 
 
 
51
        
64
52
        node identifiers can be any hashable object, and are typically strings.
65
53
 
66
54
        If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
69
57
        The graph is sorted lazily: until you iterate or sort the input is
70
58
        not processed other than to create an internal representation.
71
59
 
72
 
        iteration or sorting may raise GraphCycleError if a cycle is present
 
60
        iteration or sorting may raise GraphCycleError if a cycle is present 
73
61
        in the graph.
74
62
        """
75
 
        # store a dict of the graph.
 
63
        # a dict of the graph.
76
64
        self._graph = dict(graph)
 
65
        self._visitable = set(self._graph)
 
66
        ### if debugging:
 
67
        # self._original_graph = dict(graph)
 
68
        
 
69
        # this is a stack storing the depth first search into the graph.
 
70
        self._node_name_stack = []
 
71
        # at each level of 'recursion' we have to check each parent. This
 
72
        # stack stores the parents we have not yet checked for the node at the 
 
73
        # matching depth in _node_name_stack
 
74
        self._pending_parents_stack = []
 
75
        # this is a set of the completed nodes for fast checking whether a
 
76
        # parent in a node we are processing on the stack has already been
 
77
        # emitted and thus can be skipped.
 
78
        self._completed_node_names = set()
77
79
 
78
80
    def sorted(self):
79
81
        """Sort the graph and return as a list.
80
 
 
 
82
        
81
83
        After calling this the sorter is empty and you must create a new one.
82
84
        """
83
85
        return list(self.iter_topo_order())
94
96
 
95
97
    def iter_topo_order(self):
96
98
        """Yield the nodes of the graph in a topological order.
97
 
 
 
99
        
98
100
        After finishing iteration the sorter is empty and you cannot continue
99
101
        iteration.
100
102
        """
101
 
        graph = self._graph
102
 
        visitable = set(graph)
103
 
 
104
 
        # this is a stack storing the depth first search into the graph.
105
 
        pending_node_stack = []
106
 
        # at each level of 'recursion' we have to check each parent. This
107
 
        # stack stores the parents we have not yet checked for the node at the
108
 
        # matching depth in pending_node_stack
109
 
        pending_parents_stack = []
110
 
 
111
 
        # this is a set of the completed nodes for fast checking whether a
112
 
        # parent in a node we are processing on the stack has already been
113
 
        # emitted and thus can be skipped.
114
 
        completed_node_names = set()
115
 
 
116
 
        while graph:
 
103
        while self._graph:
117
104
            # now pick a random node in the source graph, and transfer it to the
118
 
            # top of the depth first search stack of pending nodes.
119
 
            node_name, parents = graph.popitem()
120
 
            pending_node_stack.append(node_name)
121
 
            pending_parents_stack.append(list(parents))
122
 
 
123
 
            # loop until pending_node_stack is empty
124
 
            while pending_node_stack:
125
 
                parents_to_visit = pending_parents_stack[-1]
126
 
                # if there are no parents left, the revision is done
 
105
            # top of the depth first search stack.
 
106
            node_name, parents = self._graph.popitem()
 
107
            self._push_node(node_name, parents)
 
108
            while self._node_name_stack:
 
109
                # loop until this call completes.
 
110
                parents_to_visit = self._pending_parents_stack[-1]
 
111
                # if all parents are done, the revision is done
127
112
                if not parents_to_visit:
128
113
                    # append the revision to the topo sorted list
129
 
                    # all the nodes parents have been added to the output,
130
 
                    # now we can add it to the output.
131
 
                    popped_node = pending_node_stack.pop()
132
 
                    pending_parents_stack.pop()
133
 
                    completed_node_names.add(popped_node)
134
 
                    yield popped_node
 
114
                    # all the nodes parents have been added to the output, now
 
115
                    # we can add it to the output.
 
116
                    yield self._pop_node()
135
117
                else:
136
 
                    # recurse depth first into a single parent
137
 
                    next_node_name = parents_to_visit.pop()
138
 
 
139
 
                    if next_node_name in completed_node_names:
140
 
                        # parent was already completed by a child, skip it.
141
 
                        continue
142
 
                    if next_node_name not in visitable:
143
 
                        # parent is not a node in the original graph, skip it.
144
 
                        continue
145
 
 
146
 
                    # transfer it along with its parents from the source graph
147
 
                    # into the top of the current depth first search stack.
148
 
                    try:
149
 
                        parents = graph.pop(next_node_name)
150
 
                    except KeyError:
151
 
                        # if the next node is not in the source graph it has
152
 
                        # already been popped from it and placed into the
153
 
                        # current search stack (but not completed or we would
154
 
                        # have hit the continue 6 lines up).  this indicates a
155
 
                        # cycle.
156
 
                        raise errors.GraphCycleError(pending_node_stack)
157
 
                    pending_node_stack.append(next_node_name)
158
 
                    pending_parents_stack.append(list(parents))
 
118
                    while self._pending_parents_stack[-1]:
 
119
                        # recurse depth first into a single parent 
 
120
                        next_node_name = self._pending_parents_stack[-1].pop()
 
121
                        if next_node_name in self._completed_node_names:
 
122
                            # this parent was completed by a child on the
 
123
                            # call stack. skip it.
 
124
                            continue
 
125
                        if next_node_name not in self._visitable:
 
126
                            continue
 
127
                        # otherwise transfer it from the source graph into the
 
128
                        # top of the current depth first search stack.
 
129
                        try:
 
130
                            parents = self._graph.pop(next_node_name)
 
131
                        except KeyError:
 
132
                            # if the next node is not in the source graph it has
 
133
                            # already been popped from it and placed into the
 
134
                            # current search stack (but not completed or we would
 
135
                            # have hit the continue 4 lines up.
 
136
                            # this indicates a cycle.
 
137
                            raise errors.GraphCycleError(self._node_name_stack)
 
138
                        self._push_node(next_node_name, parents)
 
139
                        # and do not continue processing parents until this 'call' 
 
140
                        # has recursed.
 
141
                        break
 
142
 
 
143
    def _push_node(self, node_name, parents):
 
144
        """Add node_name to the pending node stack.
 
145
        
 
146
        Names in this stack will get emitted into the output as they are popped
 
147
        off the stack.
 
148
        """
 
149
        self._node_name_stack.append(node_name)
 
150
        self._pending_parents_stack.append(list(parents))
 
151
 
 
152
    def _pop_node(self):
 
153
        """Pop the top node off the stack 
 
154
 
 
155
        The node is appended to the sorted output.
 
156
        """
 
157
        # we are returning from the flattened call frame:
 
158
        # pop off the local variables
 
159
        node_name = self._node_name_stack.pop()
 
160
        self._pending_parents_stack.pop()
 
161
 
 
162
        self._completed_node_names.add(node_name)
 
163
        return node_name
159
164
 
160
165
 
161
166
def merge_sort(graph, branch_tip, mainline_revisions=None, generate_revno=False):
162
167
    """Topological sort a graph which groups merges.
163
168
 
164
169
    :param graph: sequence of pairs of node->parents_list.
165
 
    :param branch_tip: the tip of the branch to graph. Revisions not
 
170
    :param branch_tip: the tip of the branch to graph. Revisions not 
166
171
                       reachable from branch_tip are not included in the
167
172
                       output.
168
173
    :param mainline_revisions: If not None this forces a mainline to be
177
182
        revision number sequences in the output. See the output description of
178
183
        the MergeSorter docstring for details.
179
184
    :result: See the MergeSorter docstring for details.
180
 
 
181
 
    Node identifiers can be any hashable object, and are typically strings.
 
185
    node identifiers can be any hashable object, and are typically strings.
182
186
    """
183
187
    return MergeSorter(graph, branch_tip, mainline_revisions,
184
188
        generate_revno).sorted()
205
209
    def __init__(self, graph, branch_tip, mainline_revisions=None,
206
210
        generate_revno=False):
207
211
        """Merge-aware topological sorting of a graph.
208
 
 
 
212
    
209
213
        :param graph: sequence of pairs of node_name->parent_names_list.
210
214
                      i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
211
215
                      For this input the output from the sort or
212
216
                      iter_topo_order routines will be:
213
217
                      'A', 'B', 'C'
214
 
        :param branch_tip: the tip of the branch to graph. Revisions not
 
218
        :param branch_tip: the tip of the branch to graph. Revisions not 
215
219
                       reachable from branch_tip are not included in the
216
220
                       output.
217
221
        :param mainline_revisions: If not None this forces a mainline to be
229
233
        The result is a list sorted so that all parents come before
230
234
        their children. Each element of the list is a tuple containing:
231
235
        (sequence_number, node_name, merge_depth, end_of_merge)
232
 
         * sequence_number: The sequence of this row in the output. Useful for
 
236
         * sequence_number: The sequence of this row in the output. Useful for 
233
237
           GUIs.
234
238
         * node_name: The node name: opaque text to the merge routine.
235
239
         * merge_depth: How many levels of merging deep this node has been
246
250
             second commit in the trunk'.
247
251
         * end_of_merge: When True the next node is part of a different merge.
248
252
 
249
 
 
 
253
        
250
254
        node identifiers can be any hashable object, and are typically strings.
251
255
 
252
256
        If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
255
259
        The graph is sorted lazily: until you iterate or sort the input is
256
260
        not processed other than to create an internal representation.
257
261
 
258
 
        iteration or sorting may raise GraphCycleError if a cycle is present
 
262
        iteration or sorting may raise GraphCycleError if a cycle is present 
259
263
        in the graph.
260
264
 
261
265
        Background information on the design:
280
284
              E  1   [F]
281
285
              F 0
282
286
              C is the end of a cluster due to rule 1.
283
 
              D is not the end of a cluster from rule 1, but is from rule 2: E
 
287
              D is not the end of a cluster from rule 1, but is from rule 2: E 
284
288
                is not its left most ancestor
285
289
              E is the end of a cluster due to rule 1
286
290
              F might be but we need more data.
287
 
 
 
291
              
288
292
        we show connecting lines to a parent when:
289
293
         - The parent is the start of a merge within this cluster.
290
 
           That is, the merge was not done to the mainline before this cluster
 
294
           That is, the merge was not done to the mainline before this cluster 
291
295
           was merged to the mainline.
292
296
           This can be detected thus:
293
 
            * The parent has a higher merge depth and is the next revision in
 
297
            * The parent has a higher merge depth and is the next revision in 
294
298
              the list.
295
 
 
 
299
          
296
300
          The next revision in the list constraint is needed for this case:
297
 
          A 0   [D, B]
298
 
          B  1  [C, F]   # we do not want to show a line to F which is depth 2
 
301
          A 0   [D, B]   
 
302
          B  1  [C, F]   # we do not want to show a line to F which is depth 2 
299
303
                           but not a merge
300
 
          C  1  [H]      # note that this is a long line to show back to the
 
304
          C  1  [H]      # note that this is a long line to show back to the 
301
305
                           ancestor - see the end of merge rules.
302
306
          D 0   [G, E]
303
307
          E  1  [G, F]
338
342
        else:
339
343
            self._mainline_revisions = list(mainline_revisions)
340
344
            self._stop_revision = self._mainline_revisions[0]
341
 
        # skip the first revision, its what we reach and its parents are
 
345
        # skip the first revision, its what we reach and its parents are 
342
346
        # therefore irrelevant
343
347
        for index, revision in enumerate(self._mainline_revisions[1:]):
344
348
            # NB: index 0 means self._mainline_revisions[1]
347
351
            if parent is None:
348
352
                # end of mainline_revisions history
349
353
                continue
350
 
            graph_parent_ids = self._graph[revision]
351
 
            if not graph_parent_ids:
352
 
                # We ran into a ghost, skip over it, this is a workaround for
353
 
                # bug #243536, the _graph has had ghosts stripped, but the
354
 
                # mainline_revisions have not
355
 
                continue
356
 
            if graph_parent_ids[0] == parent:
 
354
            if self._graph[revision][0] == parent:
357
355
                continue
358
356
            # remove it from its prior spot
359
357
            self._graph[revision].remove(parent)
374
372
                            for revision in self._graph)
375
373
        # Each mainline revision counts how many child branches have spawned from it.
376
374
        self._revno_to_branch_count = {}
377
 
 
 
375
        
378
376
        # this is a stack storing the depth first search into the graph.
379
377
        self._node_name_stack = []
380
378
        # at each level of recursion we need the merge depth this node is at:
381
379
        self._node_merge_depth_stack = []
382
380
        # at each level of 'recursion' we have to check each parent. This
383
 
        # stack stores the parents we have not yet checked for the node at the
 
381
        # stack stores the parents we have not yet checked for the node at the 
384
382
        # matching depth in _node_name_stack
385
383
        self._pending_parents_stack = []
386
384
        # When we first look at a node we assign it a seqence number from its
398
396
        # D 0  [F, E]
399
397
        # E  1 [F]
400
398
        # F 0
401
 
        # the scheduling order is: F, E, D, C, B, A
 
399
        # the scheduling order is: F, E, D, C, B, A 
402
400
        # that is - 'left subtree, right subtree, node'
403
401
        # which would mean that when we schedule A we can emit the entire tree.
404
402
        self._scheduled_nodes = []
405
 
        # This records for each node when we have processed its left most
 
403
        # This records for each node when we have processed its left most 
406
404
        # unmerged subtree. After this subtree is scheduled, all other subtrees
407
405
        # have their merge depth increased by one from this nodes merge depth.
408
406
        # it contains tuples - name, merge_depth
410
408
 
411
409
        # seed the search with the tip of the branch
412
410
        if (branch_tip is not None and
413
 
            branch_tip != _mod_revision.NULL_REVISION and
414
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
411
            branch_tip != _mod_revision.NULL_REVISION):
415
412
            parents = self._graph.pop(branch_tip)
416
413
            self._push_node(branch_tip, 0, parents)
417
414
 
418
415
    def sorted(self):
419
416
        """Sort the graph and return as a list.
420
 
 
 
417
        
421
418
        After calling this the sorter is empty and you must create a new one.
422
419
        """
423
420
        return list(self.iter_topo_order())
424
421
 
425
422
    def iter_topo_order(self):
426
423
        """Yield the nodes of the graph in a topological order.
427
 
 
 
424
        
428
425
        After finishing iteration the sorter is empty and you cannot continue
429
426
        iteration.
430
427
        """
460
457
            left_subtree_pushed_stack_append(False)
461
458
            pending_parents_stack_append(list(parents))
462
459
            # as we push it, check if it is the first child
463
 
            parent_info = None
464
460
            if parents:
465
461
                # node has parents, assign from the left most parent.
466
 
                try:
467
 
                    parent_info = revnos[parents[0]]
468
 
                except KeyError:
469
 
                    # Left-hand parent is a ghost, consider it not to exist
470
 
                    pass
471
 
            if parent_info is not None:
 
462
                parent_info = revnos[parents[0]]
472
463
                first_child = parent_info[1]
473
464
                parent_info[1] = False
474
465
            else:
502
493
            pending_parents_stack_pop()
503
494
 
504
495
            parents = original_graph[node_name]
505
 
            parent_revno = None
506
496
            if parents:
507
497
                # node has parents, assign from the left most parent.
508
 
                try:
509
 
                    parent_revno = revnos[parents[0]][0]
510
 
                except KeyError:
511
 
                    # left-hand parent is a ghost, treat it as not existing
512
 
                    pass
513
 
            if parent_revno is not None:
 
498
                parent_revno = revnos[parents[0]][0]
514
499
                if not first_child:
515
500
                    # not the first child, make a new branch
516
501
                    base_revno = parent_revno[0]
525
510
                    revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
526
511
            else:
527
512
                # no parents, use the root sequence
528
 
                root_count = revno_to_branch_count.get(0, -1)
529
 
                root_count += 1
 
513
                root_count = revno_to_branch_count.get(0, 0)
530
514
                if root_count:
531
515
                    revno = (0, root_count, 1)
532
516
                else:
533
517
                    revno = (1,)
 
518
                root_count += 1
534
519
                revno_to_branch_count[0] = root_count
535
520
 
536
521
            # store the revno for this node for future reference
554
539
                    if not left_subtree_pushed_stack[-1]:
555
540
                        # recurse depth first into the primary parent
556
541
                        next_node_name = pending_parents_stack[-1].pop(0)
557
 
                        is_left_subtree = True
558
 
                        left_subtree_pushed_stack[-1] = True
559
542
                    else:
560
543
                        # place any merges in right-to-left order for scheduling
561
544
                        # which gives us left-to-right order after we reverse
562
 
                        # the scheduled queue. XXX: This has the effect of
 
545
                        # the scheduled queue. XXX: This has the effect of 
563
546
                        # allocating common-new revisions to the right-most
564
 
                        # subtree rather than the left most, which will
 
547
                        # subtree rather than the left most, which will 
565
548
                        # display nicely (you get smaller trees at the top
566
549
                        # of the combined merge).
567
550
                        next_node_name = pending_parents_stack[-1].pop()
568
 
                        is_left_subtree = False
569
551
                    if next_node_name in completed_node_names:
570
552
                        # this parent was completed by a child on the
571
553
                        # call stack. skip it.
580
562
                        # current search stack (but not completed or we would
581
563
                        # have hit the continue 4 lines up.
582
564
                        # this indicates a cycle.
583
 
                        if next_node_name in self._original_graph:
584
 
                            raise errors.GraphCycleError(node_name_stack)
585
 
                        else:
586
 
                            # This is just a ghost parent, ignore it
587
 
                            continue
 
565
                        raise errors.GraphCycleError(node_name_stack)
588
566
                    next_merge_depth = 0
589
 
                    if is_left_subtree:
 
567
                    if left_subtree_pushed_stack[-1]:
590
568
                        # a new child branch from name_stack[-1]
 
569
                        next_merge_depth = 1
 
570
                    else:
591
571
                        next_merge_depth = 0
592
 
                    else:
593
 
                        next_merge_depth = 1
 
572
                        left_subtree_pushed_stack[-1] = True
594
573
                    next_merge_depth = (
595
574
                        node_merge_depth_stack[-1] + next_merge_depth)
596
575
                    push_node(
597
576
                        next_node_name,
598
577
                        next_merge_depth,
599
578
                        parents)
600
 
                    # and do not continue processing parents until this 'call'
 
579
                    # and do not continue processing parents until this 'call' 
601
580
                    # has recursed.
602
581
                    break
603
582
 
632
611
 
633
612
    def _push_node(self, node_name, merge_depth, parents):
634
613
        """Add node_name to the pending node stack.
635
 
 
 
614
        
636
615
        Names in this stack will get emitted into the output as they are popped
637
616
        off the stack.
638
617
        """
641
620
        self._left_subtree_pushed_stack.append(False)
642
621
        self._pending_parents_stack.append(list(parents))
643
622
        # as we push it, figure out if this is the first child
644
 
        parent_info = None
 
623
        parents = self._original_graph[node_name]
645
624
        if parents:
646
625
            # node has parents, assign from the left most parent.
647
 
            try:
648
 
                parent_info = self._revnos[parents[0]]
649
 
            except KeyError:
650
 
                # Left-hand parent is a ghost, consider it not to exist
651
 
                pass
652
 
        if parent_info is not None:
 
626
            parent_info = self._revnos[parents[0]]
653
627
            first_child = parent_info[1]
654
628
            parent_info[1] = False
655
629
        else:
659
633
        self._first_child_stack.append(first_child)
660
634
 
661
635
    def _pop_node(self):
662
 
        """Pop the top node off the stack
 
636
        """Pop the top node off the stack 
663
637
 
664
638
        The node is appended to the sorted output.
665
639
        """
673
647
        self._pending_parents_stack.pop()
674
648
 
675
649
        parents = self._original_graph[node_name]
676
 
        parent_revno = None
677
650
        if parents:
678
651
            # node has parents, assign from the left most parent.
679
 
            try:
680
 
                parent_revno = self._revnos[parents[0]][0]
681
 
            except KeyError:
682
 
                # left-hand parent is a ghost, treat it as not existing
683
 
                pass
684
 
        if parent_revno is not None:
 
652
            parent_revno = self._revnos[parents[0]][0]
685
653
            if not first_child:
686
654
                # not the first child, make a new branch
687
655
                base_revno = parent_revno[0]
697
665
        else:
698
666
            # no parents, use the root sequence
699
667
            root_count = self._revno_to_branch_count.get(0, 0)
700
 
            root_count = self._revno_to_branch_count.get(0, -1)
701
 
            root_count += 1
702
668
            if root_count:
703
669
                revno = (0, root_count, 1)
704
670
            else:
705
671
                revno = (1,)
 
672
            root_count += 1
706
673
            self._revno_to_branch_count[0] = root_count
707
674
 
708
675
        # store the revno for this node for future reference