← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

remove all trailing whitespace from bzr source

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
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]
378
378
                            for revision in self._graph)
379
379
        # Each mainline revision counts how many child branches have spawned from it.
380
380
        self._revno_to_branch_count = {}
381
 
        
 
381
 
382
382
        # this is a stack storing the depth first search into the graph.
383
383
        self._node_name_stack = []
384
384
        # at each level of recursion we need the merge depth this node is at:
385
385
        self._node_merge_depth_stack = []
386
386
        # at each level of 'recursion' we have to check each parent. This
387
 
        # 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
388
388
        # matching depth in _node_name_stack
389
389
        self._pending_parents_stack = []
390
390
        # When we first look at a node we assign it a seqence number from its
402
402
        # D 0  [F, E]
403
403
        # E  1 [F]
404
404
        # F 0
405
 
        # the scheduling order is: F, E, D, C, B, A 
 
405
        # the scheduling order is: F, E, D, C, B, A
406
406
        # that is - 'left subtree, right subtree, node'
407
407
        # which would mean that when we schedule A we can emit the entire tree.
408
408
        self._scheduled_nodes = []
409
 
        # 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
410
410
        # unmerged subtree. After this subtree is scheduled, all other subtrees
411
411
        # have their merge depth increased by one from this nodes merge depth.
412
412
        # it contains tuples - name, merge_depth
420
420
 
421
421
    def sorted(self):
422
422
        """Sort the graph and return as a list.
423
 
        
 
423
 
424
424
        After calling this the sorter is empty and you must create a new one.
425
425
        """
426
426
        return list(self.iter_topo_order())
427
427
 
428
428
    def iter_topo_order(self):
429
429
        """Yield the nodes of the graph in a topological order.
430
 
        
 
430
 
431
431
        After finishing iteration the sorter is empty and you cannot continue
432
432
        iteration.
433
433
        """
548
548
                    else:
549
549
                        # place any merges in right-to-left order for scheduling
550
550
                        # which gives us left-to-right order after we reverse
551
 
                        # the scheduled queue. XXX: This has the effect of 
 
551
                        # the scheduled queue. XXX: This has the effect of
552
552
                        # allocating common-new revisions to the right-most
553
 
                        # subtree rather than the left most, which will 
 
553
                        # subtree rather than the left most, which will
554
554
                        # display nicely (you get smaller trees at the top
555
555
                        # of the combined merge).
556
556
                        next_node_name = pending_parents_stack[-1].pop()
582
582
                        next_node_name,
583
583
                        next_merge_depth,
584
584
                        parents)
585
 
                    # and do not continue processing parents until this 'call' 
 
585
                    # and do not continue processing parents until this 'call'
586
586
                    # has recursed.
587
587
                    break
588
588
 
617
617
 
618
618
    def _push_node(self, node_name, merge_depth, parents):
619
619
        """Add node_name to the pending node stack.
620
 
        
 
620
 
621
621
        Names in this stack will get emitted into the output as they are popped
622
622
        off the stack.
623
623
        """
639
639
        self._first_child_stack.append(first_child)
640
640
 
641
641
    def _pop_node(self):
642
 
        """Pop the top node off the stack 
 
642
        """Pop the top node off the stack
643
643
 
644
644
        The node is appended to the sorted output.
645
645
        """