← 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: 2008-10-04 14:10:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3805.
  • Revision ID: john@arbash-meinel.com-20081004141013-yskxjlwtuy2k18ue
Playing around with expanding requests for btree index nodes into neighboring nodes.

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]
374
378
                            for revision in self._graph)
375
379
        # Each mainline revision counts how many child branches have spawned from it.
376
380
        self._revno_to_branch_count = {}
377
 
 
 
381
        
378
382
        # this is a stack storing the depth first search into the graph.
379
383
        self._node_name_stack = []
380
384
        # at each level of recursion we need the merge depth this node is at:
381
385
        self._node_merge_depth_stack = []
382
386
        # 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
 
387
        # stack stores the parents we have not yet checked for the node at the 
384
388
        # matching depth in _node_name_stack
385
389
        self._pending_parents_stack = []
386
390
        # When we first look at a node we assign it a seqence number from its
398
402
        # D 0  [F, E]
399
403
        # E  1 [F]
400
404
        # F 0
401
 
        # the scheduling order is: F, E, D, C, B, A
 
405
        # the scheduling order is: F, E, D, C, B, A 
402
406
        # that is - 'left subtree, right subtree, node'
403
407
        # which would mean that when we schedule A we can emit the entire tree.
404
408
        self._scheduled_nodes = []
405
 
        # This records for each node when we have processed its left most
 
409
        # This records for each node when we have processed its left most 
406
410
        # unmerged subtree. After this subtree is scheduled, all other subtrees
407
411
        # have their merge depth increased by one from this nodes merge depth.
408
412
        # it contains tuples - name, merge_depth
410
414
 
411
415
        # seed the search with the tip of the branch
412
416
        if (branch_tip is not None and
413
 
            branch_tip != _mod_revision.NULL_REVISION and
414
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
417
            branch_tip != _mod_revision.NULL_REVISION):
415
418
            parents = self._graph.pop(branch_tip)
416
419
            self._push_node(branch_tip, 0, parents)
417
420
 
418
421
    def sorted(self):
419
422
        """Sort the graph and return as a list.
420
 
 
 
423
        
421
424
        After calling this the sorter is empty and you must create a new one.
422
425
        """
423
426
        return list(self.iter_topo_order())
424
427
 
425
428
    def iter_topo_order(self):
426
429
        """Yield the nodes of the graph in a topological order.
427
 
 
 
430
        
428
431
        After finishing iteration the sorter is empty and you cannot continue
429
432
        iteration.
430
433
        """
460
463
            left_subtree_pushed_stack_append(False)
461
464
            pending_parents_stack_append(list(parents))
462
465
            # as we push it, check if it is the first child
463
 
            parent_info = None
464
466
            if parents:
465
467
                # 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:
 
468
                parent_info = revnos[parents[0]]
472
469
                first_child = parent_info[1]
473
470
                parent_info[1] = False
474
471
            else:
502
499
            pending_parents_stack_pop()
503
500
 
504
501
            parents = original_graph[node_name]
505
 
            parent_revno = None
506
502
            if parents:
507
503
                # 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:
 
504
                parent_revno = revnos[parents[0]][0]
514
505
                if not first_child:
515
506
                    # not the first child, make a new branch
516
507
                    base_revno = parent_revno[0]
554
545
                    if not left_subtree_pushed_stack[-1]:
555
546
                        # recurse depth first into the primary parent
556
547
                        next_node_name = pending_parents_stack[-1].pop(0)
557
 
                        is_left_subtree = True
558
 
                        left_subtree_pushed_stack[-1] = True
559
548
                    else:
560
549
                        # place any merges in right-to-left order for scheduling
561
550
                        # which gives us left-to-right order after we reverse
562
 
                        # the scheduled queue. XXX: This has the effect of
 
551
                        # the scheduled queue. XXX: This has the effect of 
563
552
                        # allocating common-new revisions to the right-most
564
 
                        # subtree rather than the left most, which will
 
553
                        # subtree rather than the left most, which will 
565
554
                        # display nicely (you get smaller trees at the top
566
555
                        # of the combined merge).
567
556
                        next_node_name = pending_parents_stack[-1].pop()
568
 
                        is_left_subtree = False
569
557
                    if next_node_name in completed_node_names:
570
558
                        # this parent was completed by a child on the
571
559
                        # call stack. skip it.
580
568
                        # current search stack (but not completed or we would
581
569
                        # have hit the continue 4 lines up.
582
570
                        # 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
 
571
                        raise errors.GraphCycleError(node_name_stack)
588
572
                    next_merge_depth = 0
589
 
                    if is_left_subtree:
 
573
                    if left_subtree_pushed_stack[-1]:
590
574
                        # a new child branch from name_stack[-1]
 
575
                        next_merge_depth = 1
 
576
                    else:
591
577
                        next_merge_depth = 0
592
 
                    else:
593
 
                        next_merge_depth = 1
 
578
                        left_subtree_pushed_stack[-1] = True
594
579
                    next_merge_depth = (
595
580
                        node_merge_depth_stack[-1] + next_merge_depth)
596
581
                    push_node(
597
582
                        next_node_name,
598
583
                        next_merge_depth,
599
584
                        parents)
600
 
                    # and do not continue processing parents until this 'call'
 
585
                    # and do not continue processing parents until this 'call' 
601
586
                    # has recursed.
602
587
                    break
603
588
 
632
617
 
633
618
    def _push_node(self, node_name, merge_depth, parents):
634
619
        """Add node_name to the pending node stack.
635
 
 
 
620
        
636
621
        Names in this stack will get emitted into the output as they are popped
637
622
        off the stack.
638
623
        """
641
626
        self._left_subtree_pushed_stack.append(False)
642
627
        self._pending_parents_stack.append(list(parents))
643
628
        # as we push it, figure out if this is the first child
644
 
        parent_info = None
 
629
        parents = self._original_graph[node_name]
645
630
        if parents:
646
631
            # 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:
 
632
            parent_info = self._revnos[parents[0]]
653
633
            first_child = parent_info[1]
654
634
            parent_info[1] = False
655
635
        else:
659
639
        self._first_child_stack.append(first_child)
660
640
 
661
641
    def _pop_node(self):
662
 
        """Pop the top node off the stack
 
642
        """Pop the top node off the stack 
663
643
 
664
644
        The node is appended to the sorted output.
665
645
        """
673
653
        self._pending_parents_stack.pop()
674
654
 
675
655
        parents = self._original_graph[node_name]
676
 
        parent_revno = None
677
656
        if parents:
678
657
            # 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:
 
658
            parent_revno = self._revnos[parents[0]][0]
685
659
            if not first_child:
686
660
                # not the first child, make a new branch
687
661
                base_revno = parent_revno[0]
697
671
        else:
698
672
            # no parents, use the root sequence
699
673
            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
674
            if root_count:
703
675
                revno = (0, root_count, 1)
704
676
            else:
705
677
                revno = (1,)
 
678
            root_count += 1
706
679
            self._revno_to_branch_count[0] = root_count
707
680
 
708
681
        # store the revno for this node for future reference