/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: 2018-11-18 18:23:32 UTC
  • mto: This revision was merged to the branch mainline in revision 7197.
  • Revision ID: jelmer@jelmer.uk-20181118182332-viz1qvqese2mo9i6
Fix some more Bazaar references.

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
 
 
21
 
from bzrlib import (
 
19
from __future__ import absolute_import
 
20
 
 
21
 
 
22
from . import (
22
23
    errors,
23
24
    graph as _mod_graph,
24
25
    revision as _mod_revision,
82
83
        """
83
84
        return list(self.iter_topo_order())
84
85
 
85
 
###        Useful if fiddling with this code.
86
 
###        # cross check
 
86
# Useful if fiddling with this code.
 
87
# cross check
87
88
###        sorted_names = list(self.iter_topo_order())
88
 
###        for index in range(len(sorted_names)):
 
89
# for index in range(len(sorted_names)):
89
90
###            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"
 
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"
93
94
###                    import pdb;pdb.set_trace()
94
95
 
95
96
    def iter_topo_order(self):
177
178
        revision number sequences in the output. See the output description of
178
179
        the MergeSorter docstring for details.
179
180
    :result: See the MergeSorter docstring for details.
180
 
    node identifiers can be any hashable object, and are typically strings.
 
181
 
 
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.
361
363
        # we need to do a check late in the process to detect end-of-merges
362
364
        # which requires the parents to be accessible: its easier for now
363
365
        # to just keep the original graph around.
364
 
        self._original_graph = dict(self._graph.items())
 
366
        self._original_graph = self._graph.copy()
365
367
        # we need to know the revision numbers of revisions to determine
366
368
        # the revision numbers of their descendants
367
369
        # this is a graph from node to [revno_tuple, first_child]
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 and
412
 
            branch_tip != _mod_revision.NULL_REVISION and
413
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
413
        if (branch_tip is not None
 
414
            and branch_tip != _mod_revision.NULL_REVISION
 
415
                and 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
 
541
 
 
542
543
        while node_name_stack:
543
544
            # loop until this call completes.
544
545
            parents_to_visit = pending_parents_stack[-1]
616
617
            elif scheduled_nodes[-1][1] < merge_depth:
617
618
                # the next node is to our left
618
619
                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])):
 
620
            elif (scheduled_nodes[-1][1] == merge_depth
 
621
                  and (scheduled_nodes[-1][0] not in
 
622
                       original_graph[node_name])):
622
623
                # the next node was part of a multiple-merge.
623
624
                end_of_merge = True
624
625
            else:
707
708
        # store the revno for this node for future reference
708
709
        self._revnos[node_name][0] = revno
709
710
        self._completed_node_names.add(node_name)
710
 
        self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
 
711
        self._scheduled_nodes.append(
 
712
            (node_name, merge_depth, self._revnos[node_name][0]))
711
713
        return node_name