← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-03 19:28:48 UTC
  • mto: This revision was merged to the branch mainline in revision 4410.
  • Revision ID: john@arbash-meinel.com-20090603192848-dsx5k8kwl611mk8h
Spend a little bit more time optimizing the read_revision_from_string loop
without removing the safety checking.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
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):
72
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.
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):
409
414
 
410
415
        # seed the search with the tip of the branch
411
416
        if (branch_tip is not None and
412
 
            branch_tip != _mod_revision.NULL_REVISION and
413
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
417
            branch_tip != _mod_revision.NULL_REVISION):
414
418
            parents = self._graph.pop(branch_tip)
415
419
            self._push_node(branch_tip, 0, parents)
416
420
 
459
463
            left_subtree_pushed_stack_append(False)
460
464
            pending_parents_stack_append(list(parents))
461
465
            # as we push it, check if it is the first child
462
 
            parent_info = None
463
466
            if parents:
464
467
                # node has parents, assign from the left most parent.
465
 
                try:
466
 
                    parent_info = revnos[parents[0]]
467
 
                except KeyError:
468
 
                    # Left-hand parent is a ghost, consider it not to exist
469
 
                    pass
470
 
            if parent_info is not None:
 
468
                parent_info = revnos[parents[0]]
471
469
                first_child = parent_info[1]
472
470
                parent_info[1] = False
473
471
            else:
501
499
            pending_parents_stack_pop()
502
500
 
503
501
            parents = original_graph[node_name]
504
 
            parent_revno = None
505
502
            if parents:
506
503
                # node has parents, assign from the left most parent.
507
 
                try:
508
 
                    parent_revno = revnos[parents[0]][0]
509
 
                except KeyError:
510
 
                    # left-hand parent is a ghost, treat it as not existing
511
 
                    pass
512
 
            if parent_revno is not None:
 
504
                parent_revno = revnos[parents[0]][0]
513
505
                if not first_child:
514
506
                    # not the first child, make a new branch
515
507
                    base_revno = parent_revno[0]
553
545
                    if not left_subtree_pushed_stack[-1]:
554
546
                        # recurse depth first into the primary parent
555
547
                        next_node_name = pending_parents_stack[-1].pop(0)
556
 
                        is_left_subtree = True
557
 
                        left_subtree_pushed_stack[-1] = True
558
548
                    else:
559
549
                        # place any merges in right-to-left order for scheduling
560
550
                        # which gives us left-to-right order after we reverse
564
554
                        # display nicely (you get smaller trees at the top
565
555
                        # of the combined merge).
566
556
                        next_node_name = pending_parents_stack[-1].pop()
567
 
                        is_left_subtree = False
568
557
                    if next_node_name in completed_node_names:
569
558
                        # this parent was completed by a child on the
570
559
                        # call stack. skip it.
579
568
                        # current search stack (but not completed or we would
580
569
                        # have hit the continue 4 lines up.
581
570
                        # this indicates a cycle.
582
 
                        if next_node_name in self._original_graph:
583
 
                            raise errors.GraphCycleError(node_name_stack)
584
 
                        else:
585
 
                            # This is just a ghost parent, ignore it
586
 
                            continue
 
571
                        raise errors.GraphCycleError(node_name_stack)
587
572
                    next_merge_depth = 0
588
 
                    if is_left_subtree:
 
573
                    if left_subtree_pushed_stack[-1]:
589
574
                        # a new child branch from name_stack[-1]
 
575
                        next_merge_depth = 1
 
576
                    else:
590
577
                        next_merge_depth = 0
591
 
                    else:
592
 
                        next_merge_depth = 1
 
578
                        left_subtree_pushed_stack[-1] = True
593
579
                    next_merge_depth = (
594
580
                        node_merge_depth_stack[-1] + next_merge_depth)
595
581
                    push_node(
640
626
        self._left_subtree_pushed_stack.append(False)
641
627
        self._pending_parents_stack.append(list(parents))
642
628
        # as we push it, figure out if this is the first child
643
 
        parent_info = None
 
629
        parents = self._original_graph[node_name]
644
630
        if parents:
645
631
            # node has parents, assign from the left most parent.
646
 
            try:
647
 
                parent_info = self._revnos[parents[0]]
648
 
            except KeyError:
649
 
                # Left-hand parent is a ghost, consider it not to exist
650
 
                pass
651
 
        if parent_info is not None:
 
632
            parent_info = self._revnos[parents[0]]
652
633
            first_child = parent_info[1]
653
634
            parent_info[1] = False
654
635
        else:
672
653
        self._pending_parents_stack.pop()
673
654
 
674
655
        parents = self._original_graph[node_name]
675
 
        parent_revno = None
676
656
        if parents:
677
657
            # node has parents, assign from the left most parent.
678
 
            try:
679
 
                parent_revno = self._revnos[parents[0]][0]
680
 
            except KeyError:
681
 
                # left-hand parent is a ghost, treat it as not existing
682
 
                pass
683
 
        if parent_revno is not None:
 
658
            parent_revno = self._revnos[parents[0]][0]
684
659
            if not first_child:
685
660
                # not the first child, make a new branch
686
661
                base_revno = parent_revno[0]
696
671
        else:
697
672
            # no parents, use the root sequence
698
673
            root_count = self._revno_to_branch_count.get(0, 0)
699
 
            root_count = self._revno_to_branch_count.get(0, -1)
700
 
            root_count += 1
701
674
            if root_count:
702
675
                revno = (0, root_count, 1)
703
676
            else:
704
677
                revno = (1,)
 
678
            root_count += 1
705
679
            self._revno_to_branch_count[0] = root_count
706
680
 
707
681
        # store the revno for this node for future reference