/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/tsort.py

  • Committer: Jelmer Vernooij
  • Date: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tsort.py
16
16
 
17
17
"""Topological sorting routines."""
18
18
 
 
19
from __future__ import absolute_import
 
20
 
19
21
 
20
22
from . import (
21
23
    errors,
81
83
        """
82
84
        return list(self.iter_topo_order())
83
85
 
84
 
# Useful if fiddling with this code.
85
 
# cross check
 
86
###        Useful if fiddling with this code.
 
87
###        # cross check
86
88
###        sorted_names = list(self.iter_topo_order())
87
 
# for index in range(len(sorted_names)):
 
89
###        for index in range(len(sorted_names)):
88
90
###            rev = sorted_names[index]
89
 
# for left_index in range(index):
90
 
# if rev in self.original_graph[sorted_names[left_index]]:
91
 
# print "revision in parent list of earlier revision"
 
91
###            for left_index in range(index):
 
92
###                if rev in self.original_graph[sorted_names[left_index]]:
 
93
###                    print "revision in parent list of earlier revision"
92
94
###                    import pdb;pdb.set_trace()
93
95
 
94
96
    def iter_topo_order(self):
180
182
    Node identifiers can be any hashable object, and are typically strings.
181
183
    """
182
184
    return MergeSorter(graph, branch_tip, mainline_revisions,
183
 
                       generate_revno).sorted()
 
185
        generate_revno).sorted()
184
186
 
185
187
 
186
188
class MergeSorter(object):
199
201
                 '_revno_to_branch_count',
200
202
                 '_completed_node_names',
201
203
                 '_scheduled_nodes',
202
 
                 ]
 
204
                ]
203
205
 
204
206
    def __init__(self, graph, branch_tip, mainline_revisions=None,
205
 
                 generate_revno=False):
 
207
        generate_revno=False):
206
208
        """Merge-aware topological sorting of a graph.
207
209
 
208
210
        :param graph: sequence of pairs of node_name->parent_names_list.
408
410
        self._left_subtree_pushed_stack = []
409
411
 
410
412
        # seed the search with the tip of the branch
411
 
        if (branch_tip is not None
412
 
            and branch_tip != _mod_revision.NULL_REVISION
413
 
                and branch_tip != (_mod_revision.NULL_REVISION,)):
 
413
        if (branch_tip is not None and
 
414
            branch_tip != _mod_revision.NULL_REVISION and
 
415
            branch_tip != (_mod_revision.NULL_REVISION,)):
414
416
            parents = self._graph.pop(branch_tip)
415
417
            self._push_node(branch_tip, 0, parents)
416
418
 
486
488
                     completed_node_names_add=self._completed_node_names.add,
487
489
                     scheduled_nodes_append=scheduled_nodes.append,
488
490
                     revno_to_branch_count=self._revno_to_branch_count,
489
 
                     ):
 
491
                    ):
490
492
            """Pop the top node off the stack
491
493
 
492
494
            The node is appended to the sorted output.
538
540
            scheduled_nodes_append((node_name, merge_depth, revno))
539
541
            return node_name
540
542
 
 
543
 
541
544
        while node_name_stack:
542
545
            # loop until this call completes.
543
546
            parents_to_visit = pending_parents_stack[-1]
615
618
            elif scheduled_nodes[-1][1] < merge_depth:
616
619
                # the next node is to our left
617
620
                end_of_merge = True
618
 
            elif (scheduled_nodes[-1][1] == merge_depth
619
 
                  and (scheduled_nodes[-1][0] not in
620
 
                       original_graph[node_name])):
 
621
            elif (scheduled_nodes[-1][1] == merge_depth and
 
622
                  (scheduled_nodes[-1][0] not in
 
623
                   original_graph[node_name])):
621
624
                # the next node was part of a multiple-merge.
622
625
                end_of_merge = True
623
626
            else:
706
709
        # store the revno for this node for future reference
707
710
        self._revnos[node_name][0] = revno
708
711
        self._completed_node_names.add(node_name)
709
 
        self._scheduled_nodes.append(
710
 
            (node_name, merge_depth, self._revnos[node_name][0]))
 
712
        self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
711
713
        return node_name