Merge lp:~jelmer/brz/split-multiwalker into lp:brz

[Jelmer Vernooij]

Move MultiWalker out into its own module.

It's only used by LCA.

=== modified file 'breezy/merge.py'
--- breezy/merge.py	2019-02-14 21:45:23 +0000
+++ breezy/merge.py	2019-05-12 10:12:09 +0000
@@ -904,17 +904,16 @@
         else:
             interesting_files = None
         result = []
-        walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
+        from .multiwalker import MultiWalker
+        walker = MultiWalker(self.other_tree, self._lca_trees)
 
         base_inventory = self.base_tree.root_inventory
         this_inventory = self.this_tree.root_inventory
-        for path, file_id, other_ie, lca_values in walker.iter_all():
+        for other_path, file_id, other_ie, lca_values in walker.iter_all():
             # Is this modified at all from any of the other trees?
             if other_ie is None:
                 other_ie = _none_entry
                 other_path = None
-            else:
-                other_path = self.other_tree.id2path(file_id)
             if interesting_files is not None and other_path not in interesting_files:
                 continue
 

=== added file 'breezy/multiwalker.py'
--- breezy/multiwalker.py	1970-01-01 00:00:00 +0000
+++ breezy/multiwalker.py	2019-05-12 10:12:09 +0000
@@ -0,0 +1,266 @@
+# 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_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)
+        # TODO: Is id2path better as the first call, or is
+        #       inventory[file_id] better as a first check?
+        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 = other_tree.root_inventory.get_entry(file_id)
+            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
+
+            file_id = master_ie.file_id
+            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(lookup_by_file_id(
+                        others_extra[idx], self._other_trees[idx], file_id))
+                    next_other_entries_append((False, None, None))
+                elif 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 == 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(lookup_by_file_id(
+                            other_extra, self._other_trees[idx], file_id))
+                    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, 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
+
+
+

=== modified file 'breezy/tests/__init__.py'
--- breezy/tests/__init__.py	2019-02-03 23:43:20 +0000
+++ breezy/tests/__init__.py	2019-05-12 10:12:09 +0000
@@ -4146,6 +4146,7 @@
         'breezy.tests.test_missing',
         'breezy.tests.test_msgeditor',
         'breezy.tests.test_multiparent',
+        'breezy.tests.test_multiwalker',
         'breezy.tests.test_mutabletree',
         'breezy.tests.test_nonascii',
         'breezy.tests.test_options',

=== added file 'breezy/tests/test_multiwalker.py'
--- breezy/tests/test_multiwalker.py	1970-01-01 00:00:00 +0000
+++ breezy/tests/test_multiwalker.py	2019-05-12 10:12:09 +0000
@@ -0,0 +1,305 @@
+# Copyright (C) 2006-2009, 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
+
+"""Tests for MultiWalker."""
+
+from breezy import (
+    revision,
+    multiwalker,
+    tree as _mod_tree,
+    )
+from breezy.tests import (
+    TestCaseWithTransport,
+    )
+
+
+class TestMultiWalker(TestCaseWithTransport):
+
+    def assertStepOne(self, has_more, path, file_id, iterator):
+        retval = multiwalker.MultiWalker._step_one(iterator)
+        if not has_more:
+            self.assertIs(None, path)
+            self.assertIs(None, file_id)
+            self.assertEqual((False, None, None), retval)
+        else:
+            self.assertEqual((has_more, path, file_id),
+                             (retval[0], retval[1], retval[2].file_id))
+
+    def test__step_one_empty(self):
+        tree = self.make_branch_and_tree('empty')
+        repo = tree.branch.repository
+        empty_tree = repo.revision_tree(revision.NULL_REVISION)
+
+        iterator = empty_tree.iter_entries_by_dir()
+        self.assertStepOne(False, None, None, iterator)
+        self.assertStepOne(False, None, None, iterator)
+
+    def test__step_one(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b/', 'tree/b/c'])
+        tree.add(['a', 'b', 'b/c'], [b'a-id', b'b-id', b'c-id'])
+
+        iterator = tree.iter_entries_by_dir()
+        tree.lock_read()
+        self.addCleanup(tree.unlock)
+
+        root_id = tree.path2id('')
+        self.assertStepOne(True, '', root_id, iterator)
+        self.assertStepOne(True, 'a', b'a-id', iterator)
+        self.assertStepOne(True, 'b', b'b-id', iterator)
+        self.assertStepOne(True, 'b/c', b'c-id', iterator)
+        self.assertStepOne(False, None, None, iterator)
+        self.assertStepOne(False, None, None, iterator)
+
+    def assertWalkerNext(self, exp_path, exp_file_id, master_has_node,
+                         exp_other_paths, iterator):
+        """Check what happens when we step the iterator.
+
+        :param path: The path for this entry
+        :param file_id: The file_id for this entry
+        :param master_has_node: Does the master tree have this entry?
+        :param exp_other_paths: A list of other_path values.
+        :param iterator: The iterator to step
+        """
+        path, file_id, master_ie, other_values = next(iterator)
+        self.assertEqual((exp_path, exp_file_id), (path, file_id),
+                         'Master entry did not match')
+        if master_has_node:
+            self.assertIsNot(None, master_ie, 'master should have an entry')
+        else:
+            self.assertIs(None, master_ie, 'master should not have an entry')
+        self.assertEqual(len(exp_other_paths), len(other_values),
+                         'Wrong number of other entries')
+        other_paths = []
+        other_file_ids = []
+        for path, ie in other_values:
+            other_paths.append(path)
+            if ie is None:
+                other_file_ids.append(None)
+            else:
+                other_file_ids.append(ie.file_id)
+
+        exp_file_ids = []
+        for path in exp_other_paths:
+            if path is None:
+                exp_file_ids.append(None)
+            else:
+                exp_file_ids.append(file_id)
+        self.assertEqual(exp_other_paths, other_paths, "Other paths incorrect")
+        self.assertEqual(exp_file_ids, other_file_ids,
+                         "Other file_ids incorrect")
+
+    def lock_and_get_basis_and_root_id(self, tree):
+        tree.lock_read()
+        self.addCleanup(tree.unlock)
+        basis_tree = tree.basis_tree()
+        basis_tree.lock_read()
+        self.addCleanup(basis_tree.unlock)
+        root_id = tree.path2id('')
+        return basis_tree, root_id
+
+    def test_simple_stepping(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b/', 'tree/b/c'])
+        tree.add(['a', 'b', 'b/c'], [b'a-id', b'b-id', b'c-id'])
+
+        tree.commit('first', rev_id=b'first-rev-id')
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
+        self.assertWalkerNext(u'b/c', b'c-id', True, [u'b/c'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_master_has_extra(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b/', 'tree/c', 'tree/d'])
+        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
+
+        tree.commit('first', rev_id=b'first-rev-id')
+
+        tree.add(['c'], [b'c-id'])
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
+        self.assertWalkerNext(u'c', b'c-id', True, [None], iterator)
+        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_master_renamed_to_earlier(self):
+        """The record is still present, it just shows up early."""
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/c', 'tree/d'])
+        tree.add(['a', 'c', 'd'], [b'a-id', b'c-id', b'd-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+        tree.rename_one('d', 'b')
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'b', b'd-id', True, [u'd'], iterator)
+        self.assertWalkerNext(u'c', b'c-id', True, [u'c'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_master_renamed_to_later(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
+        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+        tree.rename_one('b', 'e')
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
+        self.assertWalkerNext(u'e', b'b-id', True, [u'b'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_other_extra_in_middle(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
+        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+        tree.remove(['b'])
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
+        self.assertWalkerNext(u'b', b'b-id', False, [u'b'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_other_extra_at_end(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
+        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+        tree.remove(['d'])
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+        walker = multiwalker.MultiWalker(tree, [basis_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
+        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
+        self.assertWalkerNext(u'd', b'd-id', False, [u'd'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_others_extra_at_end(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b', 'tree/c', 'tree/d', 'tree/e'])
+        tree.add(['a', 'b', 'c', 'd', 'e'],
+                 [b'a-id', b'b-id', b'c-id', b'd-id', b'e-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+        tree.remove(['e'])
+        tree.commit('second', rev_id=b'second-rev-id')
+        tree.remove(['d'])
+        tree.commit('third', rev_id=b'third-rev-id')
+        tree.remove(['c'])
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+        first_tree = tree.branch.repository.revision_tree(b'first-rev-id')
+        second_tree = tree.branch.repository.revision_tree(b'second-rev-id')
+        walker = multiwalker.MultiWalker(tree, [basis_tree, first_tree,
+                                              second_tree])
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u'', u'', u''], iterator)
+        self.assertWalkerNext(u'a', b'a-id', True,
+                              [u'a', u'a', u'a'], iterator)
+        self.assertWalkerNext(u'b', b'b-id', True,
+                              [u'b', u'b', u'b'], iterator)
+        self.assertWalkerNext(u'c', b'c-id', False,
+                              [u'c', u'c', u'c'], iterator)
+        self.assertWalkerNext(u'd', b'd-id', False,
+                              [None, u'd', u'd'], iterator)
+        self.assertWalkerNext(u'e', b'e-id', False,
+                              [None, u'e', None], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def test_different_file_id_in_others(self):
+        tree = self.make_branch_and_tree('tree')
+        self.build_tree(['tree/a', 'tree/b', 'tree/c/'])
+        tree.add(['a', 'b', 'c'], [b'a-id', b'b-id', b'c-id'])
+        tree.commit('first', rev_id=b'first-rev-id')
+
+        tree.rename_one('b', 'c/d')
+        self.build_tree(['tree/b'])
+        tree.add(['b'], [b'b2-id'])
+        tree.commit('second', rev_id=b'second-rev-id')
+
+        tree.rename_one('a', 'c/e')
+        self.build_tree(['tree/a'])
+        tree.add(['a'], [b'a2-id'])
+
+        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
+        first_tree = tree.branch.repository.revision_tree(b'first-rev-id')
+        walker = multiwalker.MultiWalker(tree, [basis_tree, first_tree])
+
+        iterator = walker.iter_all()
+        self.assertWalkerNext(u'', root_id, True, [u'', u''], iterator)
+        self.assertWalkerNext(u'a', b'a2-id', True, [None, None], iterator)
+        self.assertWalkerNext(u'b', b'b2-id', True, [u'b', None], iterator)
+        self.assertWalkerNext(u'c', b'c-id', True, [u'c', u'c'], iterator)
+        self.assertWalkerNext(u'c/d', b'b-id', True, [u'c/d', u'b'], iterator)
+        self.assertWalkerNext(u'c/e', b'a-id', True, [u'a', u'a'], iterator)
+        self.assertRaises(StopIteration, next, iterator)
+
+    def assertLtByDirblock(self, lt_val, path1, path2):
+        self.assertEqual(
+            lt_val, multiwalker.MultiWalker._lt_path_by_dirblock(path1, path2))
+
+    def test__lt_path_by_dirblock(self):
+        # We only support Unicode strings at this point
+        self.assertRaises(
+            TypeError, multiwalker.MultiWalker._lt_path_by_dirblock, b'', b'b')
+        self.assertLtByDirblock(False, u'', u'')
+        self.assertLtByDirblock(False, u'a', u'a')
+        self.assertLtByDirblock(False, u'a/b', u'a/b')
+        self.assertLtByDirblock(False, u'a/b/c', u'a/b/c')
+        self.assertLtByDirblock(False, u'a-a', u'a')
+        self.assertLtByDirblock(True, u'a-a', u'a/a')
+        self.assertLtByDirblock(True, u'a=a', u'a/a')
+        self.assertLtByDirblock(False, u'a-a/a', u'a/a')
+        self.assertLtByDirblock(False, u'a=a/a', u'a/a')
+        self.assertLtByDirblock(False, u'a-a/a', u'a/a/a')
+        self.assertLtByDirblock(False, u'a=a/a', u'a/a/a')
+        self.assertLtByDirblock(False, u'a-a/a/a', u'a/a/a')
+        self.assertLtByDirblock(False, u'a=a/a/a', u'a/a/a')
+
+    def assertPathToKey(self, expected, path):
+        self.assertEqual(expected, multiwalker.MultiWalker._path_to_key(path))
+
+    def test__path_to_key(self):
+        self.assertPathToKey(([u''], u''), u'')
+        self.assertPathToKey(([u''], u'a'), u'a')
+        self.assertPathToKey(([u'a'], u'b'), u'a/b')
+        self.assertPathToKey(([u'a', u'b'], u'c'), u'a/b/c')

=== modified file 'breezy/tests/test_tree.py'
--- breezy/tests/test_tree.py	2018-11-12 01:41:38 +0000
+++ breezy/tests/test_tree.py	2019-05-12 10:12:09 +0000
@@ -163,285 +163,6 @@
         self.assertEqual(len(delta.added), 1)
 
 
-class TestMultiWalker(TestCaseWithTransport):
-
-    def assertStepOne(self, has_more, path, file_id, iterator):
-        retval = _mod_tree.MultiWalker._step_one(iterator)
-        if not has_more:
-            self.assertIs(None, path)
-            self.assertIs(None, file_id)
-            self.assertEqual((False, None, None), retval)
-        else:
-            self.assertEqual((has_more, path, file_id),
-                             (retval[0], retval[1], retval[2].file_id))
-
-    def test__step_one_empty(self):
-        tree = self.make_branch_and_tree('empty')
-        repo = tree.branch.repository
-        empty_tree = repo.revision_tree(revision.NULL_REVISION)
-
-        iterator = empty_tree.iter_entries_by_dir()
-        self.assertStepOne(False, None, None, iterator)
-        self.assertStepOne(False, None, None, iterator)
-
-    def test__step_one(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b/', 'tree/b/c'])
-        tree.add(['a', 'b', 'b/c'], [b'a-id', b'b-id', b'c-id'])
-
-        iterator = tree.iter_entries_by_dir()
-        tree.lock_read()
-        self.addCleanup(tree.unlock)
-
-        root_id = tree.path2id('')
-        self.assertStepOne(True, '', root_id, iterator)
-        self.assertStepOne(True, 'a', b'a-id', iterator)
-        self.assertStepOne(True, 'b', b'b-id', iterator)
-        self.assertStepOne(True, 'b/c', b'c-id', iterator)
-        self.assertStepOne(False, None, None, iterator)
-        self.assertStepOne(False, None, None, iterator)
-
-    def assertWalkerNext(self, exp_path, exp_file_id, master_has_node,
-                         exp_other_paths, iterator):
-        """Check what happens when we step the iterator.
-
-        :param path: The path for this entry
-        :param file_id: The file_id for this entry
-        :param master_has_node: Does the master tree have this entry?
-        :param exp_other_paths: A list of other_path values.
-        :param iterator: The iterator to step
-        """
-        path, file_id, master_ie, other_values = next(iterator)
-        self.assertEqual((exp_path, exp_file_id), (path, file_id),
-                         'Master entry did not match')
-        if master_has_node:
-            self.assertIsNot(None, master_ie, 'master should have an entry')
-        else:
-            self.assertIs(None, master_ie, 'master should not have an entry')
-        self.assertEqual(len(exp_other_paths), len(other_values),
-                         'Wrong number of other entries')
-        other_paths = []
-        other_file_ids = []
-        for path, ie in other_values:
-            other_paths.append(path)
-            if ie is None:
-                other_file_ids.append(None)
-            else:
-                other_file_ids.append(ie.file_id)
-
-        exp_file_ids = []
-        for path in exp_other_paths:
-            if path is None:
-                exp_file_ids.append(None)
-            else:
-                exp_file_ids.append(file_id)
-        self.assertEqual(exp_other_paths, other_paths, "Other paths incorrect")
-        self.assertEqual(exp_file_ids, other_file_ids,
-                         "Other file_ids incorrect")
-
-    def lock_and_get_basis_and_root_id(self, tree):
-        tree.lock_read()
-        self.addCleanup(tree.unlock)
-        basis_tree = tree.basis_tree()
-        basis_tree.lock_read()
-        self.addCleanup(basis_tree.unlock)
-        root_id = tree.path2id('')
-        return basis_tree, root_id
-
-    def test_simple_stepping(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b/', 'tree/b/c'])
-        tree.add(['a', 'b', 'b/c'], [b'a-id', b'b-id', b'c-id'])
-
-        tree.commit('first', rev_id=b'first-rev-id')
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
-        self.assertWalkerNext(u'b/c', b'c-id', True, [u'b/c'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_master_has_extra(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b/', 'tree/c', 'tree/d'])
-        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
-
-        tree.commit('first', rev_id=b'first-rev-id')
-
-        tree.add(['c'], [b'c-id'])
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
-        self.assertWalkerNext(u'c', b'c-id', True, [None], iterator)
-        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_master_renamed_to_earlier(self):
-        """The record is still present, it just shows up early."""
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/c', 'tree/d'])
-        tree.add(['a', 'c', 'd'], [b'a-id', b'c-id', b'd-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-        tree.rename_one('d', 'b')
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'b', b'd-id', True, [u'd'], iterator)
-        self.assertWalkerNext(u'c', b'c-id', True, [u'c'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_master_renamed_to_later(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
-        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-        tree.rename_one('b', 'e')
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
-        self.assertWalkerNext(u'e', b'b-id', True, [u'b'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_other_extra_in_middle(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
-        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-        tree.remove(['b'])
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'd', b'd-id', True, [u'd'], iterator)
-        self.assertWalkerNext(u'b', b'b-id', False, [u'b'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_other_extra_at_end(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b', 'tree/d'])
-        tree.add(['a', 'b', 'd'], [b'a-id', b'b-id', b'd-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-        tree.remove(['d'])
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-        walker = _mod_tree.MultiWalker(tree, [basis_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True, [u'a'], iterator)
-        self.assertWalkerNext(u'b', b'b-id', True, [u'b'], iterator)
-        self.assertWalkerNext(u'd', b'd-id', False, [u'd'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_others_extra_at_end(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b', 'tree/c', 'tree/d', 'tree/e'])
-        tree.add(['a', 'b', 'c', 'd', 'e'],
-                 [b'a-id', b'b-id', b'c-id', b'd-id', b'e-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-        tree.remove(['e'])
-        tree.commit('second', rev_id=b'second-rev-id')
-        tree.remove(['d'])
-        tree.commit('third', rev_id=b'third-rev-id')
-        tree.remove(['c'])
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-        first_tree = tree.branch.repository.revision_tree(b'first-rev-id')
-        second_tree = tree.branch.repository.revision_tree(b'second-rev-id')
-        walker = _mod_tree.MultiWalker(tree, [basis_tree, first_tree,
-                                              second_tree])
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u'', u'', u''], iterator)
-        self.assertWalkerNext(u'a', b'a-id', True,
-                              [u'a', u'a', u'a'], iterator)
-        self.assertWalkerNext(u'b', b'b-id', True,
-                              [u'b', u'b', u'b'], iterator)
-        self.assertWalkerNext(u'c', b'c-id', False,
-                              [u'c', u'c', u'c'], iterator)
-        self.assertWalkerNext(u'd', b'd-id', False,
-                              [None, u'd', u'd'], iterator)
-        self.assertWalkerNext(u'e', b'e-id', False,
-                              [None, u'e', None], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def test_different_file_id_in_others(self):
-        tree = self.make_branch_and_tree('tree')
-        self.build_tree(['tree/a', 'tree/b', 'tree/c/'])
-        tree.add(['a', 'b', 'c'], [b'a-id', b'b-id', b'c-id'])
-        tree.commit('first', rev_id=b'first-rev-id')
-
-        tree.rename_one('b', 'c/d')
-        self.build_tree(['tree/b'])
-        tree.add(['b'], [b'b2-id'])
-        tree.commit('second', rev_id=b'second-rev-id')
-
-        tree.rename_one('a', 'c/e')
-        self.build_tree(['tree/a'])
-        tree.add(['a'], [b'a2-id'])
-
-        basis_tree, root_id = self.lock_and_get_basis_and_root_id(tree)
-        first_tree = tree.branch.repository.revision_tree(b'first-rev-id')
-        walker = _mod_tree.MultiWalker(tree, [basis_tree, first_tree])
-
-        iterator = walker.iter_all()
-        self.assertWalkerNext(u'', root_id, True, [u'', u''], iterator)
-        self.assertWalkerNext(u'a', b'a2-id', True, [None, None], iterator)
-        self.assertWalkerNext(u'b', b'b2-id', True, [u'b', None], iterator)
-        self.assertWalkerNext(u'c', b'c-id', True, [u'c', u'c'], iterator)
-        self.assertWalkerNext(u'c/d', b'b-id', True, [u'c/d', u'b'], iterator)
-        self.assertWalkerNext(u'c/e', b'a-id', True, [u'a', u'a'], iterator)
-        self.assertRaises(StopIteration, next, iterator)
-
-    def assertLtByDirblock(self, lt_val, path1, path2):
-        self.assertEqual(
-            lt_val, _mod_tree.MultiWalker._lt_path_by_dirblock(path1, path2))
-
-    def test__lt_path_by_dirblock(self):
-        # We only support Unicode strings at this point
-        self.assertRaises(
-            TypeError, _mod_tree.MultiWalker._lt_path_by_dirblock, b'', b'b')
-        self.assertLtByDirblock(False, u'', u'')
-        self.assertLtByDirblock(False, u'a', u'a')
-        self.assertLtByDirblock(False, u'a/b', u'a/b')
-        self.assertLtByDirblock(False, u'a/b/c', u'a/b/c')
-        self.assertLtByDirblock(False, u'a-a', u'a')
-        self.assertLtByDirblock(True, u'a-a', u'a/a')
-        self.assertLtByDirblock(True, u'a=a', u'a/a')
-        self.assertLtByDirblock(False, u'a-a/a', u'a/a')
-        self.assertLtByDirblock(False, u'a=a/a', u'a/a')
-        self.assertLtByDirblock(False, u'a-a/a', u'a/a/a')
-        self.assertLtByDirblock(False, u'a=a/a', u'a/a/a')
-        self.assertLtByDirblock(False, u'a-a/a/a', u'a/a/a')
-        self.assertLtByDirblock(False, u'a=a/a/a', u'a/a/a')
-
-    def assertPathToKey(self, expected, path):
-        self.assertEqual(expected, _mod_tree.MultiWalker._path_to_key(path))
-
-    def test__path_to_key(self):
-        self.assertPathToKey(([u''], u''), u'')
-        self.assertPathToKey(([u''], u'a'), u'a')
-        self.assertPathToKey(([u'a'], u'b'), u'a/b')
-        self.assertPathToKey(([u'a', u'b'], u'c'), u'a/b/c')
-
-
 class FindPreviousPathsTests(TestCaseWithTransport):
 
     def test_new(self):

=== modified file 'breezy/tree.py'
--- breezy/tree.py	2019-02-02 15:13:30 +0000
+++ breezy/tree.py	2019-05-12 10:12:09 +0000
@@ -945,7 +945,8 @@
                                                    changed_file_ids):
                 yield result
 
-    def _get_entry(self, tree, path):
+    @staticmethod
+    def _get_entry(tree, path):
         """Get an inventory entry from a tree, with missing entries as None.
 
         If the tree raises NotImplementedError on accessing .inventory, then
@@ -1091,239 +1092,6 @@
 InterTree.register_optimiser(InterTree)
 
 
-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_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)
-        # TODO: Is id2path better as the first call, or is
-        #       inventory[file_id] better as a first check?
-        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 = other_tree.root_inventory.get_entry(file_id)
-            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
-
-            file_id = master_ie.file_id
-            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(lookup_by_file_id(
-                        others_extra[idx], self._other_trees[idx], file_id))
-                    next_other_entries_append((False, None, None))
-                elif 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 == 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(lookup_by_file_id(
-                            other_extra, self._other_trees[idx], file_id))
-                    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, 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
-
-
 def find_previous_paths(from_tree, to_tree, paths):
     """Find previous tree paths.