/brz/remove-bazaar

# Copyright (C) 2005-2011 Canonical Ltd

#

# This program is free software; you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

# GNU General Public License for more details.

#

# You should have received a copy of the GNU General Public License

# along with this program; if not, write to the Free Software

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

"""Walk multiple trees simultaneously.

"""

from __future__ import absolute_import

from . import (

    errors,

    osutils,

    )

from .sixish import (

    text_type,

    viewvalues,

    )

class MultiWalker(object):

    """Walk multiple trees simultaneously, getting combined results."""

    # Note: This could be written to not assume you can do out-of-order

    #       lookups. Instead any nodes that don't match in all trees could be

    #       marked as 'deferred', and then returned in the final cleanup loop.

    #       For now, I think it is "nicer" to return things as close to the

    #       "master_tree" order as we can.

    def __init__(self, master_tree, other_trees):

        """Create a new MultiWalker.

        All trees being walked must implement "iter_entries_by_dir()", such

        that they yield (path, object) tuples, where that object will have a

        '.file_id' member, that can be used to check equality.

        :param master_tree: All trees will be 'slaved' to the master_tree such

            that nodes in master_tree will be used as 'first-pass' sync points.

            Any nodes that aren't in master_tree will be merged in a second

            pass.

        :param other_trees: A list of other trees to walk simultaneously.

        """

        self._master_tree = master_tree

        self._other_trees = other_trees

        # Keep track of any nodes that were properly processed just out of

        # order, that way we don't return them at the end, we don't have to

        # track *all* processed file_ids, just the out-of-order ones

        self._out_of_order_processed = set()

    @staticmethod

    def _step_one(iterator):

        """Step an iter_entries_by_dir iterator.

        :return: (has_more, path, ie)

            If has_more is False, path and ie will be None.

        """

        try:

            path, ie = next(iterator)

        except StopIteration:

            return False, None, None

        else:

            return True, path, ie

    @staticmethod

    def _lt_path_by_dirblock(path1, path2):

        """Compare two paths based on what directory they are in.

        This generates a sort order, such that all children of a directory are

        sorted together, and grandchildren are in the same order as the

        children appear. But all grandchildren come after all children.

        :param path1: first path

        :param path2: the second path

        :return: negative number if ``path1`` comes first,

            0 if paths are equal

            and a positive number if ``path2`` sorts first

        """

        # Shortcut this special case

        if path1 == path2:

            return False

        # This is stolen from _dirstate_helpers_py.py, only switching it to

        # Unicode objects. Consider using encode_utf8() and then using the

        # optimized versions, or maybe writing optimized unicode versions.

        if not isinstance(path1, text_type):

            raise TypeError("'path1' must be a unicode string, not %s: %r"

                            % (type(path1), path1))

        if not isinstance(path2, text_type):

            raise TypeError("'path2' must be a unicode string, not %s: %r"

                            % (type(path2), path2))

        return (MultiWalker._path_to_key(path1) <

                MultiWalker._path_to_key(path2))

    @staticmethod

    def _path_to_key(path):

        dirname, basename = osutils.split(path)

        return (dirname.split(u'/'), basename)

    def _lookup_by_master_path(self, extra_entries, other_tree, master_path):

        return self._lookup_by_file_id(

            extra_entries, other_tree,

            self._master_tree.path2id(master_path))

    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):

        """Lookup an inventory entry by file_id.

        This is called when an entry is missing in the normal order.

        Generally this is because a file was either renamed, or it was

        deleted/added. If the entry was found in the inventory and not in

        extra_entries, it will be added to self._out_of_order_processed

        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This

            should be filled with entries that were found before they were

            used. If file_id is present, it will be removed from the

            dictionary.

        :param other_tree: The Tree to search, in case we didn't find the entry

            yet.

        :param file_id: The file_id to look for

        :return: (path, ie) if found or (None, None) if not present.

        """

        if file_id in extra_entries:

            return extra_entries.pop(file_id)

        try:

            cur_path = other_tree.id2path(file_id)

        except errors.NoSuchId:

            cur_path = None

        if cur_path is None:

            return (None, None)

        else:

            self._out_of_order_processed.add(file_id)

            cur_ie = next(other_tree.iter_entries_by_dir(

                specific_files=[cur_path]))[1]

            return (cur_path, cur_ie)

    def iter_all(self):

        """Match up the values in the different trees."""

        for result in self._walk_master_tree():

            yield result

        self._finish_others()

        for result in self._walk_others():

            yield result

    def _walk_master_tree(self):

        """First pass, walk all trees in lock-step.

        When we are done, all nodes in the master_tree will have been

        processed. _other_walkers, _other_entries, and _others_extra will be

        set on 'self' for future processing.

        """

        # This iterator has the most "inlining" done, because it tends to touch

        # every file in the tree, while the others only hit nodes that don't

        # match.

        master_iterator = self._master_tree.iter_entries_by_dir()

        other_walkers = [other.iter_entries_by_dir()

                         for other in self._other_trees]

        other_entries = [self._step_one(walker) for walker in other_walkers]

        # Track extra nodes in the other trees

        others_extra = [{} for _ in range(len(self._other_trees))]

        master_has_more = True

        step_one = self._step_one

        lookup_by_file_id = self._lookup_by_file_id

        out_of_order_processed = self._out_of_order_processed

        while master_has_more:

            (master_has_more, path, master_ie) = step_one(master_iterator)

            if not master_has_more:

                break

            other_values = []

            other_values_append = other_values.append

            next_other_entries = []

            next_other_entries_append = next_other_entries.append

            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):

                if not other_has_more:

                    other_values_append(self._lookup_by_master_path(

                        others_extra[idx], self._other_trees[idx], path))

                    next_other_entries_append((False, None, None))

                elif master_ie.file_id == other_ie.file_id:

                    # This is the critical code path, as most of the entries

                    # should match between most trees.

                    other_values_append((other_path, other_ie))

                    next_other_entries_append(step_one(other_walkers[idx]))

                else:

                    # This walker did not match, step it until it either

                    # matches, or we know we are past the current walker.

                    other_walker = other_walkers[idx]

                    other_extra = others_extra[idx]

                    while (other_has_more and

                           self._lt_path_by_dirblock(other_path, path)):

                        other_file_id = other_ie.file_id

                        if other_file_id not in out_of_order_processed:

                            other_extra[other_file_id] = (other_path, other_ie)

                        other_has_more, other_path, other_ie = \

                            step_one(other_walker)

                    if other_has_more and other_ie.file_id == master_ie.file_id:

                        # We ended up walking to this point, match and step

                        # again

                        other_values_append((other_path, other_ie))

                        other_has_more, other_path, other_ie = \

                            step_one(other_walker)

                    else:

                        # This record isn't in the normal order, see if it

                        # exists at all.

                        other_values_append(self._lookup_by_master_path(

                            other_extra, self._other_trees[idx], path))

                    next_other_entries_append((other_has_more, other_path,

                                               other_ie))

            other_entries = next_other_entries

            # We've matched all the walkers, yield this datapoint

            yield path, master_ie.file_id, master_ie, other_values

        self._other_walkers = other_walkers

        self._other_entries = other_entries

        self._others_extra = others_extra

    def _finish_others(self):

        """Finish walking the other iterators, so we get all entries."""

        for idx, info in enumerate(self._other_entries):

            other_extra = self._others_extra[idx]

            (other_has_more, other_path, other_ie) = info

            while other_has_more:

                other_file_id = other_ie.file_id

                if other_file_id not in self._out_of_order_processed:

                    other_extra[other_file_id] = (other_path, other_ie)

                other_has_more, other_path, other_ie = \

                    self._step_one(self._other_walkers[idx])

        del self._other_entries

    def _walk_others(self):

        """Finish up by walking all the 'deferred' nodes."""

        # TODO: One alternative would be to grab all possible unprocessed

        #       file_ids, and then sort by path, and then yield them. That

        #       might ensure better ordering, in case a caller strictly

        #       requires parents before children.

        for idx, other_extra in enumerate(self._others_extra):

            others = sorted(viewvalues(other_extra),

                            key=lambda x: self._path_to_key(x[0]))

            for other_path, other_ie in others:

                file_id = other_ie.file_id

                # We don't need to check out_of_order_processed here, because

                # the lookup_by_file_id will be removing anything processed

                # from the extras cache

                other_extra.pop(file_id)

                other_values = [(None, None)] * idx

                other_values.append((other_path, other_ie))

                for alt_idx, alt_extra in enumerate(self._others_extra[idx + 1:]):

                    alt_idx = alt_idx + idx + 1

                    alt_extra = self._others_extra[alt_idx]

                    alt_tree = self._other_trees[alt_idx]

                    other_values.append(self._lookup_by_file_id(

                        alt_extra, alt_tree, file_id))

                yield other_path, file_id, None, other_values