/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: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2020-08-23 01:15:41 UTC
  • mfrom: (7520.1.4 merge-3.1)
  • Revision ID: breezy.the.bot@gmail.com-20200823011541-nv0oh7nzaganx2qy
Merge lp:brz/3.1.

Merged from https://code.launchpad.net/~jelmer/brz/merge-3.1/+merge/389690

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tsort.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
 
18
17
"""Topological sorting routines."""
19
18
 
20
19
 
21
 
from bzrlib import (
 
20
from . import (
22
21
    errors,
23
22
    graph as _mod_graph,
24
23
    revision as _mod_revision,
82
81
        """
83
82
        return list(self.iter_topo_order())
84
83
 
85
 
###        Useful if fiddling with this code.
86
 
###        # cross check
 
84
# Useful if fiddling with this code.
 
85
# cross check
87
86
###        sorted_names = list(self.iter_topo_order())
88
 
###        for index in range(len(sorted_names)):
 
87
# for index in range(len(sorted_names)):
89
88
###            rev = sorted_names[index]
90
 
###            for left_index in range(index):
91
 
###                if rev in self.original_graph[sorted_names[left_index]]:
92
 
###                    print "revision in parent list of earlier revision"
 
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"
93
92
###                    import pdb;pdb.set_trace()
94
93
 
95
94
    def iter_topo_order(self):
177
176
        revision number sequences in the output. See the output description of
178
177
        the MergeSorter docstring for details.
179
178
    :result: See the MergeSorter docstring for details.
180
 
    node identifiers can be any hashable object, and are typically strings.
 
179
 
 
180
    Node identifiers can be any hashable object, and are typically strings.
181
181
    """
182
182
    return MergeSorter(graph, branch_tip, mainline_revisions,
183
 
        generate_revno).sorted()
 
183
                       generate_revno).sorted()
184
184
 
185
185
 
186
186
class MergeSorter(object):
199
199
                 '_revno_to_branch_count',
200
200
                 '_completed_node_names',
201
201
                 '_scheduled_nodes',
202
 
                ]
 
202
                 ]
203
203
 
204
204
    def __init__(self, graph, branch_tip, mainline_revisions=None,
205
 
        generate_revno=False):
 
205
                 generate_revno=False):
206
206
        """Merge-aware topological sorting of a graph.
207
207
 
208
208
        :param graph: sequence of pairs of node_name->parent_names_list.
361
361
        # we need to do a check late in the process to detect end-of-merges
362
362
        # which requires the parents to be accessible: its easier for now
363
363
        # to just keep the original graph around.
364
 
        self._original_graph = dict(self._graph.items())
 
364
        self._original_graph = self._graph.copy()
365
365
        # we need to know the revision numbers of revisions to determine
366
366
        # the revision numbers of their descendants
367
367
        # this is a graph from node to [revno_tuple, first_child]
408
408
        self._left_subtree_pushed_stack = []
409
409
 
410
410
        # seed the search with the tip of the branch
411
 
        if (branch_tip is not None and
412
 
            branch_tip != _mod_revision.NULL_REVISION and
413
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
411
        if (branch_tip is not None
 
412
            and branch_tip != _mod_revision.NULL_REVISION
 
413
                and branch_tip != (_mod_revision.NULL_REVISION,)):
414
414
            parents = self._graph.pop(branch_tip)
415
415
            self._push_node(branch_tip, 0, parents)
416
416
 
486
486
                     completed_node_names_add=self._completed_node_names.add,
487
487
                     scheduled_nodes_append=scheduled_nodes.append,
488
488
                     revno_to_branch_count=self._revno_to_branch_count,
489
 
                    ):
 
489
                     ):
490
490
            """Pop the top node off the stack
491
491
 
492
492
            The node is appended to the sorted output.
538
538
            scheduled_nodes_append((node_name, merge_depth, revno))
539
539
            return node_name
540
540
 
541
 
 
542
541
        while node_name_stack:
543
542
            # loop until this call completes.
544
543
            parents_to_visit = pending_parents_stack[-1]
616
615
            elif scheduled_nodes[-1][1] < merge_depth:
617
616
                # the next node is to our left
618
617
                end_of_merge = True
619
 
            elif (scheduled_nodes[-1][1] == merge_depth and
620
 
                  (scheduled_nodes[-1][0] not in
621
 
                   original_graph[node_name])):
 
618
            elif (scheduled_nodes[-1][1] == merge_depth
 
619
                  and (scheduled_nodes[-1][0] not in
 
620
                       original_graph[node_name])):
622
621
                # the next node was part of a multiple-merge.
623
622
                end_of_merge = True
624
623
            else:
707
706
        # store the revno for this node for future reference
708
707
        self._revnos[node_name][0] = revno
709
708
        self._completed_node_names.add(node_name)
710
 
        self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
 
709
        self._scheduled_nodes.append(
 
710
            (node_name, merge_depth, self._revnos[node_name][0]))
711
711
        return node_name