/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 bzrlib/tsort.py

  • Committer: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

Show diffs side-by-side

added added

removed removed

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