← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: Vincent Ladeuil
  • Date: 2009-06-22 12:52:39 UTC
  • mto: (4471.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4472.
  • Revision ID: v.ladeuil+lp@free.fr-20090622125239-kabo9smxt9c3vnir
Use a consistent scheme for naming pyrex source files.

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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
18
18
"""Topological sorting routines."""
42
42
 
43
43
    def __init__(self, graph):
44
44
        """Topological sorting of a graph.
45
 
    
 
45
 
46
46
        :param graph: sequence of pairs of node_name->parent_names_list.
47
47
                      i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
48
48
                      For this input the output from the sort or
49
49
                      iter_topo_order routines will be:
50
50
                      'A', 'B', 'C'
51
 
        
 
51
 
52
52
        node identifiers can be any hashable object, and are typically strings.
53
53
 
54
54
        If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
57
57
        The graph is sorted lazily: until you iterate or sort the input is
58
58
        not processed other than to create an internal representation.
59
59
 
60
 
        iteration or sorting may raise GraphCycleError if a cycle is present 
 
60
        iteration or sorting may raise GraphCycleError if a cycle is present
61
61
        in the graph.
62
62
        """
63
63
        # a dict of the graph.
65
65
        self._visitable = set(self._graph)
66
66
        ### if debugging:
67
67
        # self._original_graph = dict(graph)
68
 
        
 
68
 
69
69
        # this is a stack storing the depth first search into the graph.
70
70
        self._node_name_stack = []
71
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 
 
72
        # stack stores the parents we have not yet checked for the node at the
73
73
        # matching depth in _node_name_stack
74
74
        self._pending_parents_stack = []
75
75
        # this is a set of the completed nodes for fast checking whether a
79
79
 
80
80
    def sorted(self):
81
81
        """Sort the graph and return as a list.
82
 
        
 
82
 
83
83
        After calling this the sorter is empty and you must create a new one.
84
84
        """
85
85
        return list(self.iter_topo_order())
96
96
 
97
97
    def iter_topo_order(self):
98
98
        """Yield the nodes of the graph in a topological order.
99
 
        
 
99
 
100
100
        After finishing iteration the sorter is empty and you cannot continue
101
101
        iteration.
102
102
        """
116
116
                    yield self._pop_node()
117
117
                else:
118
118
                    while self._pending_parents_stack[-1]:
119
 
                        # recurse depth first into a single parent 
 
119
                        # recurse depth first into a single parent
120
120
                        next_node_name = self._pending_parents_stack[-1].pop()
121
121
                        if next_node_name in self._completed_node_names:
122
122
                            # this parent was completed by a child on the
136
136
                            # this indicates a cycle.
137
137
                            raise errors.GraphCycleError(self._node_name_stack)
138
138
                        self._push_node(next_node_name, parents)
139
 
                        # and do not continue processing parents until this 'call' 
 
139
                        # and do not continue processing parents until this 'call'
140
140
                        # has recursed.
141
141
                        break
142
142
 
143
143
    def _push_node(self, node_name, parents):
144
144
        """Add node_name to the pending node stack.
145
 
        
 
145
 
146
146
        Names in this stack will get emitted into the output as they are popped
147
147
        off the stack.
148
148
        """
150
150
        self._pending_parents_stack.append(list(parents))
151
151
 
152
152
    def _pop_node(self):
153
 
        """Pop the top node off the stack 
 
153
        """Pop the top node off the stack
154
154
 
155
155
        The node is appended to the sorted output.
156
156
        """
167
167
    """Topological sort a graph which groups merges.
168
168
 
169
169
    :param graph: sequence of pairs of node->parents_list.
170
 
    :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
171
171
                       reachable from branch_tip are not included in the
172
172
                       output.
173
173
    :param mainline_revisions: If not None this forces a mainline to be
209
209
    def __init__(self, graph, branch_tip, mainline_revisions=None,
210
210
        generate_revno=False):
211
211
        """Merge-aware topological sorting of a graph.
212
 
    
 
212
 
213
213
        :param graph: sequence of pairs of node_name->parent_names_list.
214
214
                      i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
215
215
                      For this input the output from the sort or
216
216
                      iter_topo_order routines will be:
217
217
                      'A', 'B', 'C'
218
 
        :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
219
219
                       reachable from branch_tip are not included in the
220
220
                       output.
221
221
        :param mainline_revisions: If not None this forces a mainline to be
233
233
        The result is a list sorted so that all parents come before
234
234
        their children. Each element of the list is a tuple containing:
235
235
        (sequence_number, node_name, merge_depth, end_of_merge)
236
 
         * 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
237
237
           GUIs.
238
238
         * node_name: The node name: opaque text to the merge routine.
239
239
         * merge_depth: How many levels of merging deep this node has been
250
250
             second commit in the trunk'.
251
251
         * end_of_merge: When True the next node is part of a different merge.
252
252
 
253
 
        
 
253
 
254
254
        node identifiers can be any hashable object, and are typically strings.
255
255
 
256
256
        If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
259
259
        The graph is sorted lazily: until you iterate or sort the input is
260
260
        not processed other than to create an internal representation.
261
261
 
262
 
        iteration or sorting may raise GraphCycleError if a cycle is present 
 
262
        iteration or sorting may raise GraphCycleError if a cycle is present
263
263
        in the graph.
264
264
 
265
265
        Background information on the design:
284
284
              E  1   [F]
285
285
              F 0
286
286
              C is the end of a cluster due to rule 1.
287
 
              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
288
288
                is not its left most ancestor
289
289
              E is the end of a cluster due to rule 1
290
290
              F might be but we need more data.
291
 
              
 
291
 
292
292
        we show connecting lines to a parent when:
293
293
         - The parent is the start of a merge within this cluster.
294
 
           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
295
295
           was merged to the mainline.
296
296
           This can be detected thus:
297
 
            * 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
298
298
              the list.
299
 
          
 
299
 
300
300
          The next revision in the list constraint is needed for this case:
301
 
          A 0   [D, B]   
302
 
          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
303
303
                           but not a merge
304
 
          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
305
305
                           ancestor - see the end of merge rules.
306
306
          D 0   [G, E]
307
307
          E  1  [G, F]
342
342
        else:
343
343
            self._mainline_revisions = list(mainline_revisions)
344
344
            self._stop_revision = self._mainline_revisions[0]
345
 
        # 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
346
346
        # therefore irrelevant
347
347
        for index, revision in enumerate(self._mainline_revisions[1:]):
348
348
            # NB: index 0 means self._mainline_revisions[1]
351
351
            if parent is None:
352
352
                # end of mainline_revisions history
353
353
                continue
354
 
            if self._graph[revision][0] == parent:
 
354
            graph_parent_ids = self._graph[revision]
 
355
            if not graph_parent_ids:
 
356
                # We ran into a ghost, skip over it, this is a workaround for
 
357
                # bug #243536, the _graph has had ghosts stripped, but the
 
358
                # mainline_revisions have not
 
359
                continue
 
360
            if graph_parent_ids[0] == parent:
355
361
                continue
356
362
            # remove it from its prior spot
357
363
            self._graph[revision].remove(parent)
372
378
                            for revision in self._graph)
373
379
        # Each mainline revision counts how many child branches have spawned from it.
374
380
        self._revno_to_branch_count = {}
375
 
        
 
381
 
376
382
        # this is a stack storing the depth first search into the graph.
377
383
        self._node_name_stack = []
378
384
        # at each level of recursion we need the merge depth this node is at:
379
385
        self._node_merge_depth_stack = []
380
386
        # at each level of 'recursion' we have to check each parent. This
381
 
        # 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
382
388
        # matching depth in _node_name_stack
383
389
        self._pending_parents_stack = []
384
390
        # When we first look at a node we assign it a seqence number from its
396
402
        # D 0  [F, E]
397
403
        # E  1 [F]
398
404
        # F 0
399
 
        # the scheduling order is: F, E, D, C, B, A 
 
405
        # the scheduling order is: F, E, D, C, B, A
400
406
        # that is - 'left subtree, right subtree, node'
401
407
        # which would mean that when we schedule A we can emit the entire tree.
402
408
        self._scheduled_nodes = []
403
 
        # 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
404
410
        # unmerged subtree. After this subtree is scheduled, all other subtrees
405
411
        # have their merge depth increased by one from this nodes merge depth.
406
412
        # it contains tuples - name, merge_depth
414
420
 
415
421
    def sorted(self):
416
422
        """Sort the graph and return as a list.
417
 
        
 
423
 
418
424
        After calling this the sorter is empty and you must create a new one.
419
425
        """
420
426
        return list(self.iter_topo_order())
421
427
 
422
428
    def iter_topo_order(self):
423
429
        """Yield the nodes of the graph in a topological order.
424
 
        
 
430
 
425
431
        After finishing iteration the sorter is empty and you cannot continue
426
432
        iteration.
427
433
        """
510
516
                    revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
511
517
            else:
512
518
                # no parents, use the root sequence
513
 
                root_count = revno_to_branch_count.get(0, 0)
 
519
                root_count = revno_to_branch_count.get(0, -1)
 
520
                root_count += 1
514
521
                if root_count:
515
522
                    revno = (0, root_count, 1)
516
523
                else:
517
524
                    revno = (1,)
518
 
                root_count += 1
519
525
                revno_to_branch_count[0] = root_count
520
526
 
521
527
            # store the revno for this node for future reference
542
548
                    else:
543
549
                        # place any merges in right-to-left order for scheduling
544
550
                        # which gives us left-to-right order after we reverse
545
 
                        # the scheduled queue. XXX: This has the effect of 
 
551
                        # the scheduled queue. XXX: This has the effect of
546
552
                        # allocating common-new revisions to the right-most
547
 
                        # subtree rather than the left most, which will 
 
553
                        # subtree rather than the left most, which will
548
554
                        # display nicely (you get smaller trees at the top
549
555
                        # of the combined merge).
550
556
                        next_node_name = pending_parents_stack[-1].pop()
576
582
                        next_node_name,
577
583
                        next_merge_depth,
578
584
                        parents)
579
 
                    # and do not continue processing parents until this 'call' 
 
585
                    # and do not continue processing parents until this 'call'
580
586
                    # has recursed.
581
587
                    break
582
588
 
611
617
 
612
618
    def _push_node(self, node_name, merge_depth, parents):
613
619
        """Add node_name to the pending node stack.
614
 
        
 
620
 
615
621
        Names in this stack will get emitted into the output as they are popped
616
622
        off the stack.
617
623
        """
633
639
        self._first_child_stack.append(first_child)
634
640
 
635
641
    def _pop_node(self):
636
 
        """Pop the top node off the stack 
 
642
        """Pop the top node off the stack
637
643
 
638
644
        The node is appended to the sorted output.
639
645
        """