Merge lp:~jelmer/bzr/faster-stacked-tree-build into lp:bzr

[Jelmer Vernooij]

This branch was originally submitted by spiv. Here is his cover letter:

Here's my branch that makes 'bzr branch --stacked $SMART_SERVER_URL' much, much faster. It adds a new kind of search “texts for revision”, and adds that to the HPSS protocol (without adding a new verb, just a new search body, as usual it will fallback to VFS if the server doesn't support the new thing), and checks for the new search in get_stream.

The basic idea here is that to build a working tree we need to fetch all the texts, and if the new local repo is stacked we may as well fetch all that data in a single stream and save it into that repo (rather than fetching it text-by-text when we try to build the tree from the empty local repo stacked on the remote fallback).

I forget exactly what is missing from this branch, but probably not much. I think mainly just some clarity about the new SearchResult APIs it adds, and that's perhaps best resolved by having other folks review this anyway. So: review away!

(This is actually all code from while I was still working at Canonical, but the flu stopped me from having time to give it a final self-review and/or polish, so here it is without that.)

[Martin Pool (mbp)]

I haven't read it extremely carefully but it looks basically ok.
Thanks for pushing it up.

It would be nice to get some news and what's new entries that give
some indication of how much performance has actually changed.

[Martin Pool (mbp)]

+ # XXX: this is a gross hack.
+ mutter('HACK adding texts-for-rev:%s', tip)

[tweak] Can you add something more about what's specifically wrong with it or what ought to be done instead (even just a pointer to bug 791704), otherwise for someone who comes to look at it it's just kind of rubbing it in.

I presume what you're saying is gross is the special case for when this fires? Or is it that it is done as a special search at all? It does look like it will cause a similar performance cliff to what we currently have when you branch into a new empty repository as opposed to creating a new repository.

[optional] Thinking this through makes me wonder if we should have a debug option to force this on or force it off, so that we can eg use it as a workaround and can more easily compare the performance.

+# def get_full_keys(self):
+# return set(sr.get_full_keys() for sr in self.search_results)

[query] If this is really dead can you just remove it? Likewise below.

+ def __init__(self, revision_id, repo=None):
+ """Constructor.
+
+ :param revision_id: A revision ID. All records needed to create a
+ checkout of this revision are referenced by this result (i.e. the
+ revision record and corresponding inventory record, and all
+ referenced texts and chk_bytes).
+ :param repo: An optional repository. If not given, then
+ ``get_full_keys`` cannot be used.
+ """
+ self.revision_id = revision_id
+# self.repo = repo

[query] Is the repo really unused? Maybe the function prototype or docstring needs to be changed?

+ if self.texts_for_inv is not None:
+ # Emit all CHK records for this inventory, and add all texts
+ # those nodes reference.
+ keys = set()
+ for node in self.texts_for_inv.id_to_entry.iter_nodes():
+ keys.add(node.key())
+ if type(node) is chk_map.LeafNode:
+ self._text_keys.update(
+ [chk_map._bytes_to_text_key(b) for b in
+ node._items.values()])
+ stream = self.from_repository.chk_bytes.get_record_stream(
+ keys, 'unordered', True)
+ for record in stream:
+ yield record
+ uninteresting_root_keys.add(
+ self.texts_for_inv.id_to_entry.key())

[comment] This seems to be getting kind of large for a nested function but perhaps refactoring it is out of scope.

[query] It's not obvious to me that there are tests for this actually being reached, but I might be just missing that.

I'd like to get a second review, probably from John, and someone should also build this and just play with it to check the behaviour is reasonable. This needs to be considered as a risk factor for the landing on lp (maybe we should have somewhere to accumulate a list of them.)

[Martin Pool (mbp)]

So, I can do these tweaks, if spiv is busy, but I would definitely like a second review.

[Vincent Ladeuil (vila)]

@jam: AIUI you're working on this bug now, what should be the status of *this* proposal in that respect ?

review: Needs Information

[Jelmer Vernooij (jelmer)]

I'm looking at finishing this.

[Andrew Bennetts (spiv)]

On Wed, Nov 16, 2011 at 03:52:39PM -0000, Jelmer Vernooij wrote:
> Jelmer Vernooij has proposed merging lp:~jelmer/bzr/faster-stacked-tree-build into lp:bzr.

Thanks for picking this up!

-Andrew.

=== modified file 'bzrlib/__init__.py'
--- bzrlib/__init__.py	2012-01-16 17:57:43 +0000
+++ bzrlib/__init__.py	2012-01-25 17:56:30 +0000
@@ -148,13 +148,10 @@
     """
     try:
         import ctypes
-    except ImportError:
-        return
-    pythonapi = getattr(ctypes, "pythonapi", None)
-    if pythonapi is None:
-        # Not CPython ctypes implementation
-        return
-    old_ptr = ctypes.c_void_p.in_dll(pythonapi, "Py_FileSystemDefaultEncoding")
+        old_ptr = ctypes.c_void_p.in_dll(ctypes.pythonapi,
+            "Py_FileSystemDefaultEncoding")
+    except (ImportError, ValueError):
+        return # No ctypes or not CPython implementation, do nothing
     new_ptr = ctypes.cast(ctypes.c_char_p(intern(new_enc)), ctypes.c_void_p)
     old_ptr.value = new_ptr.value
     if sys.getfilesystemencoding() != new_enc:

=== modified file 'bzrlib/bzrdir.py'
--- bzrlib/bzrdir.py	2012-01-18 20:27:41 +0000
+++ bzrlib/bzrdir.py	2012-01-25 17:56:30 +0000
@@ -410,8 +410,27 @@
         else:
             target_repo_kind = fetch.TargetRepoKinds.PREEXISTING
         fetch_spec_factory.target_repo_kind = target_repo_kind
+        create_tree = (create_tree_if_local and not result.has_workingtree() and
+            isinstance(target_transport, local.LocalTransport) and
+            (result_repo is None or result_repo.make_working_trees()))
+
         if source_repository is not None:
-            fetch_spec = fetch_spec_factory.make_fetch_spec()
+            if revision_id is not None:
+                tip = revision_id
+            elif source_branch is not None:
+                tip = source_branch.last_revision()
+            else:
+                tip = _mod_revision.NULL_REVISION
+            if (create_tree and is_new_repo
+                and tip != _mod_revision.NULL_REVISION
+                and target_repo_kind == fetch.TargetRepoKinds.STACKED):
+                # We're creating a tree for a stacked branch, so make sure we
+                # fetch the texts we're about to need to construct that tree.
+                # XXX: this is a gross hack.
+                mutter('HACK adding texts-for-rev:%s', tip)
+                fetch_spec = vf_search.TextsForRevisionSearchResult(tip)
+            else:
+                fetch_spec = fetch_spec_factory.make_fetch_spec()
             result_repo.fetch(source_repository, fetch_spec=fetch_spec)
 
         if source_branch is None:
@@ -426,9 +445,7 @@
         mutter("created new branch %r" % (result_branch,))
 
         # Create/update the result working tree
-        if (create_tree_if_local and not result.has_workingtree() and
-            isinstance(target_transport, local.LocalTransport) and
-            (result_repo is None or result_repo.make_working_trees())):
+        if create_tree:
             wt = result.create_workingtree(accelerator_tree=accelerator_tree,
                 hardlink=hardlink, from_branch=result_branch)
             wt.lock_write()

=== modified file 'bzrlib/chk_map.py'
--- bzrlib/chk_map.py	2011-12-19 13:23:58 +0000
+++ bzrlib/chk_map.py	2012-01-25 17:56:30 +0000
@@ -222,6 +222,15 @@
                 result.append('      %r %r' % (tuple(key), value))
         return result
 
+    def iter_nodes(self):
+        """Yield all nodes of this CHK map."""
+        self._ensure_root()
+        node = self._root_node
+        yield node
+        if type(node) is InternalNode:
+            for node, node_filter in node._iter_nodes(self._store):
+                yield node
+
     @classmethod
     def from_dict(klass, store, initial_value, maximum_size=0, key_width=1,
         search_key_func=None):

=== modified file 'bzrlib/remote.py'
--- bzrlib/remote.py	2012-01-19 14:17:55 +0000
+++ bzrlib/remote.py	2012-01-25 17:56:30 +0000
@@ -2998,14 +2998,16 @@
             except errors.UnknownSmartMethod:
                 medium._remember_remote_is_before(version)
             except errors.UnknownErrorFromSmartServer, e:
-                if isinstance(search, vf_search.EverythingResult):
+                new_in_2_5_searches = (
+                    vf_search.EverythingResult, vf_search.TextsForRevisionSearchResult)
+                if isinstance(search, new_in_2_5_searches):
                     error_verb = e.error_from_smart_server.error_verb
                     if error_verb == 'BadSearch':
-                        # Pre-2.4 servers don't support this sort of search.
+                        # Pre-2.5 servers don't support this sort of search.
                         # XXX: perhaps falling back to VFS on BadSearch is a
                         # good idea in general?  It might provide a little bit
                         # of protection against client-side bugs.
-                        medium._remember_remote_is_before((2, 4))
+                        medium._remember_remote_is_before((2, 5))
                         break
                 raise
             else:

=== modified file 'bzrlib/repofmt/groupcompress_repo.py'
--- bzrlib/repofmt/groupcompress_repo.py	2011-12-19 19:15:58 +0000
+++ bzrlib/repofmt/groupcompress_repo.py	2012-01-25 17:56:30 +0000
@@ -786,7 +786,8 @@
                 pass
         except errors.NoSuchRevision, e:
             problems.append(
-                "missing chk node(s) for parent_id_basename_to_file_id maps")
+                "missing chk node(s) for parent_id_basename_to_file_id maps: %s"
+                % (str(e),))
         present_text_keys = no_fallback_texts_index.get_parent_map(text_keys)
         missing_text_keys = text_keys.difference(present_text_keys)
         if missing_text_keys:
@@ -1158,6 +1159,8 @@
         self._text_fetch_order = 'groupcompress'
         self._chk_id_roots = None
         self._chk_p_id_roots = None
+        self.texts_for_rev = None
+        self.texts_for_inv = None
 
     def _get_inventory_stream(self, inventory_keys, allow_absent=False):
         """Get a stream of inventory texts.
@@ -1167,6 +1170,7 @@
         """
         self._chk_id_roots = []
         self._chk_p_id_roots = []
+        self._texts_for_inv = None
         def _filtered_inv_stream():
             id_roots_set = set()
             p_id_roots_set = set()
@@ -1180,8 +1184,13 @@
                     else:
                         raise errors.NoSuchRevision(self, record.key)
                 bytes = record.get_bytes_as('fulltext')
-                chk_inv = inventory.CHKInventory.deserialise(None, bytes,
-                                                             record.key)
+                if record.key[-1] == self.texts_for_rev:
+                    chk_inv = inventory.CHKInventory.deserialise(
+                        self.from_repository.chk_bytes, bytes, record.key)
+                    self.texts_for_inv = chk_inv
+                else:
+                    chk_inv = inventory.CHKInventory.deserialise(None, bytes,
+                                                                 record.key)
                 key = chk_inv.id_to_entry.key()
                 if key not in id_roots_set:
                     self._chk_id_roots.append(key)
@@ -1222,6 +1231,22 @@
                     inv.parent_id_basename_to_file_id.key())
         chk_bytes = self.from_repository.chk_bytes
         def _filter_id_to_entry():
+            if self.texts_for_inv is not None:
+                # Emit all CHK records for this inventory, and add all texts
+                # those nodes reference.
+                keys = set()
+                for node in self.texts_for_inv.id_to_entry.iter_nodes():
+                    keys.add(node.key())
+                    if type(node) is chk_map.LeafNode:
+                        self._text_keys.update(
+                            [chk_map._bytes_to_text_key(b) for b in
+                                node._items.values()])
+                stream = self.from_repository.chk_bytes.get_record_stream(
+                    keys, 'unordered', True)
+                for record in stream:
+                    yield record
+                uninteresting_root_keys.add(
+                    self.texts_for_inv.id_to_entry.key())
             interesting_nodes = chk_map.iter_interesting_nodes(chk_bytes,
                         self._chk_id_roots, uninteresting_root_keys)
             for record in _filter_text_keys(interesting_nodes, self._text_keys,
@@ -1232,12 +1257,25 @@
             self._chk_id_roots = None
         yield 'chk_bytes', _filter_id_to_entry()
         def _get_parent_id_basename_to_file_id_pages():
+            if self.texts_for_inv is not None:
+                # Emit all CHK records for this inventory.
+                keys = set()
+                inv = self.texts_for_inv
+                for node in inv.parent_id_basename_to_file_id.iter_nodes():
+                    keys.add(node.key())
+                stream = self.from_repository.chk_bytes.get_record_stream(
+                    keys, 'unordered', True)
+                for record in stream:
+                    yield record
+                uninteresting_pid_root_keys.add(
+                    inv.parent_id_basename_to_file_id.key())
             for record, items in chk_map.iter_interesting_nodes(chk_bytes,
                         self._chk_p_id_roots, uninteresting_pid_root_keys):
                 if record is not None:
                     yield record
             # Consumed
             self._chk_p_id_roots = None
+            self.texts_for_inv = None
         yield 'chk_bytes', _get_parent_id_basename_to_file_id_pages()
 
     def _get_text_stream(self):
@@ -1260,6 +1298,20 @@
                 yield record
 
         revision_ids = search.get_keys()
+        texts_for_rev = None
+        for special in search.get_special():
+            if special[0] == 'texts-for-rev':
+                if texts_for_rev is not None:
+                    raise errors.BzrError("Cannot handle special search: %r" %
+                        (search,))
+                texts_for_rev = special[1]
+                if texts_for_rev not in revision_ids:
+                    raise AssertionError('texts_for_rev %r not in %r'
+                        % (texts_for_rev, revision_ids))
+            else:
+                raise errors.BzrError("Cannot handle special search: %r" %
+                    (search,))
+        revision_ids = frozenset(revision_ids)
         pb = ui.ui_factory.nested_progress_bar()
         rc = self._record_counter
         self._record_counter.setup(len(revision_ids))
@@ -1278,6 +1330,7 @@
         # Clear the repo's get_parent_map cache too.
         self.from_repository._unstacked_provider.disable_cache()
         self.from_repository._unstacked_provider.enable_cache()
+        self.texts_for_rev = texts_for_rev
         s = self._get_inventory_stream(self._revision_keys)
         yield (s[0], wrap_and_count(pb, rc, s[1]))
         self.from_repository.inventories.clear_cache()

=== modified file 'bzrlib/smart/repository.py'
--- bzrlib/smart/repository.py	2011-12-19 13:23:58 +0000
+++ bzrlib/smart/repository.py	2012-01-25 17:56:30 +0000
@@ -99,6 +99,10 @@
         elif lines[0] == 'search':
             return self.recreate_search_from_recipe(repository, lines[1:],
                 discard_excess=discard_excess)
+        elif lines[0] == 'texts-for-rev':
+            if len(lines) > 2:
+                return (None, FailedSmartServerResponse(('BadSearch',)))
+            return (vf_search.TextsForRevisionSearchResult(lines[1]), None)
         else:
             return (None, FailedSmartServerResponse(('BadSearch',)))
 

=== modified file 'bzrlib/tests/blackbox/test_branch.py'
--- bzrlib/tests/blackbox/test_branch.py	2012-01-19 12:01:12 +0000
+++ bzrlib/tests/blackbox/test_branch.py	2012-01-25 17:56:30 +0000
@@ -424,13 +424,12 @@
 
     def test_branch_stacked(self):
         # We have a mainline
-        trunk_tree = self.make_branch_and_tree('mainline',
-            format='1.9')
+        trunk_tree = self.make_branch_and_tree('mainline')
         original_revid = trunk_tree.commit('mainline')
         self.assertRevisionInRepository('mainline', original_revid)
         # and a branch from it which is stacked
         out, err = self.run_bzr(['branch', '--stacked', 'mainline',
-            'newbranch'])
+            'newbranch', '--no-tree'])
         self.assertEqual('', out)
         self.assertEqual('Created new stacked branch referring to %s.\n' %
             trunk_tree.branch.base, err)

=== modified file 'bzrlib/tests/per_branch/test_stacking.py'
--- bzrlib/tests/per_branch/test_stacking.py	2011-11-24 17:24:21 +0000
+++ bzrlib/tests/per_branch/test_stacking.py	2012-01-25 17:56:30 +0000
@@ -143,7 +143,8 @@
         trunk_revid = trunk_tree.commit('mainline')
         # and make branch from it which is stacked
         try:
-            new_dir = trunk_tree.bzrdir.sprout('newbranch', stacked=True)
+            new_dir = trunk_tree.bzrdir.sprout('newbranch', stacked=True,
+                create_tree_if_local=False)
         except unstackable_format_errors, e:
             raise TestNotApplicable(e)
         # stacked repository
@@ -160,14 +161,16 @@
         trunk_revid = trunk_tree.commit('mainline')
         # Make sure that we can make a stacked branch from it
         try:
-            trunk_tree.bzrdir.sprout('testbranch', stacked=True)
+            trunk_tree.bzrdir.sprout('testbranch', stacked=True,
+                create_tree_if_local=False)
         except unstackable_format_errors, e:
             raise TestNotApplicable(e)
         # Now serve the original mainline from a smart server
         remote_transport = self.make_smart_server('mainline')
         remote_bzrdir = bzrdir.BzrDir.open_from_transport(remote_transport)
         # and make branch from the smart server which is stacked
-        new_dir = remote_bzrdir.sprout('newbranch', stacked=True)
+        new_dir = remote_bzrdir.sprout('newbranch', stacked=True,
+            create_tree_if_local=False)
         # stacked repository
         self.assertRevisionNotInRepository('newbranch', trunk_revid)
         tree = new_dir.open_branch().create_checkout('local')
@@ -187,7 +190,8 @@
         mainline_revid = 'rev-1'
         # and make branch from it which is stacked (with no tags)
         try:
-            new_dir = trunk.bzrdir.sprout(self.get_url('newbranch'), stacked=True)
+            new_dir = trunk.bzrdir.sprout(self.get_url('newbranch'),
+                stacked=True, create_tree_if_local=False)
         except unstackable_format_errors, e:
             raise TestNotApplicable(e)
         # stacked repository
@@ -534,14 +538,12 @@
         stack_on.commit('first commit', rev_id='rev1')
         try:
             stacked_dir = stack_on.bzrdir.sprout(
-                self.get_url('stacked'), stacked=True)
+                self.get_url('stacked'), stacked=True,
+                create_tree_if_local=False)
         except unstackable_format_errors, e:
             raise TestNotApplicable('Format does not support stacking.')
-        try:
-            stacked = stacked_dir.open_workingtree()
-        except errors.NoWorkingTree:
-            stacked = stacked_dir.open_branch().create_checkout(
-                'stacked-checkout', lightweight=True)
+        stacked = stacked_dir.open_branch().create_checkout(
+            'stacked-checkout', lightweight=True)
         tree = stacked.branch.create_checkout('local')
         tree.commit('second commit', rev_id='rev2')
         # Sanity check: stacked's repo should not contain rev1, otherwise this

=== modified file 'bzrlib/tests/per_repository/test_commit_builder.py'
--- bzrlib/tests/per_repository/test_commit_builder.py	2011-12-22 16:17:28 +0000
+++ bzrlib/tests/per_repository/test_commit_builder.py	2012-01-25 17:56:30 +0000
@@ -284,6 +284,7 @@
             if not builder.supports_record_entry_contents:
                 raise tests.TestNotApplicable("CommitBuilder doesn't support "
                     "record_entry_contents")
+            builder.will_record_deletes()
             ie = inventory.make_entry('directory', '', None,
                     tree.get_root_id())
             delta, version_recorded, fs_hash = builder.record_entry_contents(
@@ -299,7 +300,7 @@
             if got_new_revision:
                 self.assertEqual(('', '', ie.file_id, ie), delta)
                 # The delta should be tracked
-                self.assertEqual(delta, builder._basis_delta[-1])
+                self.assertEqual(delta, builder.get_basis_delta()[-1])
             else:
                 self.assertEqual(None, delta)
             # Directories do not get hashed.
@@ -441,7 +442,7 @@
                 # the delta should be returned, and recorded in _basis_delta
                 delta = builder.record_delete("foo", "foo-id")
                 self.assertEqual(("foo", None, "foo-id", None), delta)
-                self.assertEqual(delta, builder._basis_delta[-1])
+                self.assertEqual(delta, builder.get_basis_delta()[-1])
                 builder.finish_inventory()
                 rev_id2 = builder.commit('delete foo')
             except:
@@ -463,13 +464,14 @@
         try:
             builder = tree.branch.get_commit_builder([rev_id])
             try:
+                builder.will_record_deletes()
                 delete_change = ('foo-id', ('foo', None), True, (True, False),
                     (tree.path2id(''), None), ('foo', None), ('file', None),
                     (False, None))
                 list(builder.record_iter_changes(tree, rev_id,
                     [delete_change]))
                 self.assertEqual(("foo", None, "foo-id", None),
-                    builder._basis_delta[0])
+                    builder.get_basis_delta()[0])
                 self.assertTrue(builder.any_changes())
                 builder.finish_inventory()
                 rev_id2 = builder.commit('delete foo')
@@ -866,6 +868,7 @@
                 if not builder.supports_record_entry_contents:
                     raise tests.TestNotApplicable("CommitBuilder doesn't "
                         "support record_entry_contents")
+                builder.will_record_deletes()
                 parent_tree = tree.basis_tree()
                 parent_tree.lock_read()
                 self.addCleanup(parent_tree.unlock)
@@ -913,7 +916,8 @@
                 if delta_against_basis:
                     expected_delta = (name, new_name, file_id, new_entry)
                     # The delta should be recorded
-                    self.assertEqual(expected_delta, builder._basis_delta[-1])
+                    self.assertEqual(expected_delta,
+                        builder.get_basis_delta()[-1])
                 else:
                     expected_delta = None
                 self.assertEqual(expected_delta, delta)
@@ -954,6 +958,7 @@
             # record_entry_contents.
             parent_ids = tree.get_parent_ids()
             builder = tree.branch.get_commit_builder(parent_ids)
+            builder.will_record_deletes()
             parent_tree = tree.basis_tree()
             parent_tree.lock_read()
             self.addCleanup(parent_tree.unlock)
@@ -975,15 +980,6 @@
                 self.assertEqualStat(result[2][1], tree_file_stat[1])
             else:
                 self.assertEqual([], result)
-            delta = builder._basis_delta
-            delta_dict = dict((change[2], change) for change in delta)
-            version_recorded = (file_id in delta_dict and
-                delta_dict[file_id][3] is not None and
-                delta_dict[file_id][3].revision == builder._new_revision_id)
-            if records_version:
-                self.assertTrue(version_recorded)
-            else:
-                self.assertFalse(version_recorded)
             self.assertIs(None, builder.new_inventory)
             builder.finish_inventory()
             if tree.branch.repository._format.supports_full_versioned_files:
@@ -993,6 +989,16 @@
                 self.assertEqual(inv_sha1, builder.inv_sha1)
             self.assertIs(None, builder.new_inventory)
             rev2 = builder.commit('')
+            delta = builder.get_basis_delta()
+            delta_dict = dict((change[2], change) for change in delta)
+            version_recorded = (file_id in delta_dict and
+                delta_dict[file_id][3] is not None and
+                delta_dict[file_id][3].revision == rev2)
+            if records_version:
+                self.assertTrue(version_recorded)
+            else:
+                self.assertFalse(version_recorded)
+
             new_inventory = builder.revision_tree().inventory
             new_entry = new_inventory[file_id]
             if delta_against_basis:

=== modified file 'bzrlib/tests/per_repository_reference/test_commit_with_stacking.py'
--- bzrlib/tests/per_repository_reference/test_commit_with_stacking.py	2011-01-11 00:36:10 +0000
+++ bzrlib/tests/per_repository_reference/test_commit_with_stacking.py	2012-01-25 17:56:30 +0000
@@ -39,13 +39,10 @@
         base_tree.commit('base adds f2', rev_id=self.r2_key[0])
         stacked_url = urlutils.join(base_tree.branch.base, '../stacked')
         stacked_bzrdir = base_tree.bzrdir.sprout(stacked_url,
-            stacked=True)
-        if isinstance(stacked_bzrdir, remote.RemoteBzrDir):
-            stacked_branch = stacked_bzrdir.open_branch()
-            stacked_tree = stacked_branch.create_checkout('stacked',
-                lightweight=True)
-        else:
-            stacked_tree = stacked_bzrdir.open_workingtree()
+            stacked=True, create_tree_if_local=False)
+        stacked_branch = stacked_bzrdir.open_branch()
+        stacked_tree = stacked_branch.create_checkout('stacked-tree',
+            lightweight=True)
         return base_tree, stacked_tree
 
 
@@ -79,7 +76,7 @@
         base_tree, stacked_tree = self.make_stacked_target()
         self.assertEqual(1,
                 len(stacked_tree.branch.repository._fallback_repositories))
-        self.build_tree_contents([('stacked/f1.txt', 'new content\n')])
+        self.build_tree_contents([('stacked-tree/f1.txt', 'new content\n')])
         stacked_tree.commit('new content', rev_id='new-rev-id')
         # We open the repository without fallbacks to ensure the data is
         # locally true
@@ -142,7 +139,7 @@
     def test_multi_stack(self):
         """base + stacked + stacked-on-stacked"""
         base_tree, stacked_tree = self.make_stacked_target()
-        self.build_tree(['stacked/f3.txt'])
+        self.build_tree(['stacked-tree/f3.txt'])
         stacked_tree.add(['f3.txt'], ['f3.txt-id'])
         stacked_key = ('stacked-rev-id',)
         stacked_tree.commit('add f3', rev_id=stacked_key[0])
@@ -153,16 +150,13 @@
         stacked2_url = urlutils.join(base_tree.branch.base, '../stacked2')
         stacked2_bzrdir = stacked_tree.bzrdir.sprout(stacked2_url,
                             revision_id=self.r1_key[0],
-                            stacked=True)
-        if isinstance(stacked2_bzrdir, remote.RemoteBzrDir):
-            stacked2_branch = stacked2_bzrdir.open_branch()
-            stacked2_tree = stacked2_branch.create_checkout('stacked2',
-                lightweight=True)
-        else:
-            stacked2_tree = stacked2_bzrdir.open_workingtree()
+                            stacked=True, create_tree_if_local=False)
+        stacked2_branch = stacked2_bzrdir.open_branch()
+        stacked2_tree = stacked2_branch.create_checkout('stacked2-tree',
+            lightweight=True)
         # stacked2 is stacked on stacked, but its content is rev1, so
         # it needs to pull the basis information from a fallback-of-fallback.
-        self.build_tree(['stacked2/f3.txt'])
+        self.build_tree(['stacked2-tree/f3.txt'])
         stacked2_only_repo = self.get_only_repo(stacked2_tree)
         self.assertPresent([], stacked2_only_repo.inventories,
                            [self.r1_key, self.r2_key])

=== modified file 'bzrlib/tests/test_remote.py'
--- bzrlib/tests/test_remote.py	2012-01-06 22:06:36 +0000
+++ bzrlib/tests/test_remote.py	2012-01-25 17:56:30 +0000
@@ -3934,11 +3934,11 @@
         self.setup_smart_server_with_call_log()
         tree1 = self.make_branch_and_tree('tree1', format='1.9')
         tree1.commit('rev1', rev_id='rev1')
-        tree2 = tree1.branch.bzrdir.sprout('tree2', stacked=True
-            ).open_workingtree()
-        local_tree = tree2.branch.create_checkout('local')
+        stacked_b = tree1.branch.bzrdir.sprout('branch2',
+            stacked=True, create_tree_if_local=False).open_branch()
+        local_tree = stacked_b.create_checkout('local')
         local_tree.commit('local changes make me feel good.')
-        branch2 = Branch.open(self.get_url('tree2'))
+        branch2 = Branch.open(self.get_url('branch2'))
         branch2.lock_read()
         self.addCleanup(branch2.unlock)
         return tree1.branch, branch2
@@ -4013,9 +4013,9 @@
         # is itself stacked yields the full data from all three sources.
         def make_stacked_stacked():
             _, stacked = self.prepare_stacked_remote_branch()
-            tree = stacked.bzrdir.sprout('tree3', stacked=True
-                ).open_workingtree()
-            local_tree = tree.branch.create_checkout('local-tree3')
+            local_branch = stacked.bzrdir.sprout('tree3', stacked=True,
+                create_tree_if_local=False).open_branch()
+            local_tree = local_branch.create_checkout('local-tree3')
             local_tree.commit('more local changes are better')
             branch = Branch.open(self.get_url('tree3'))
             branch.lock_read()
@@ -4113,37 +4113,60 @@
                 override_existing=True, info=orig_info)
 
     def test_fetch_everything_backwards_compat(self):
-        """Can fetch with EverythingResult even with pre 2.4 servers.
+        """Can fetch with EverythingResult even with pre 2.5 servers.
         
-        Pre-2.4 do not support 'everything' searches with the
+        Pre-2.5 do not support 'everything' searches with the
         Repository.get_stream_1.19 verb.
         """
-        verb_log = []
+        self.disable_search(lambda bytes: bytes == 'everything')
+        local = self.make_branch('local')
+        builder = self.make_branch_builder('remote')
+        builder.build_commit(message="Commit.")
+        remote_branch_url = self.smart_server.get_url() + 'remote'
+        remote_branch = bzrdir.BzrDir.open(remote_branch_url).open_branch()
+        self.hpss_calls = []
+        fetch_spec = vf_search.EverythingResult(remote_branch.repository)
+        local.repository.fetch(remote_branch.repository, fetch_spec=fetch_spec)
+        # make sure the overridden verb was used
+        self.assertLength(1, self.verb_log)
+        # more than one HPSS call is needed, but because it's a VFS callback
+        # its hard to predict exactly how many.
+        self.assertTrue(len(self.hpss_calls) > 1)
+
+    def disable_search(self, reject_search_func):
+        self.verb_log = verb_log = []
         class OldGetStreamVerb(SmartServerRepositoryGetStream_1_19):
             """A version of the Repository.get_stream_1.19 verb patched to
-            reject 'everything' searches the way 2.3 and earlier do.
+            reject searches matching reject_search_func (to emulate old
+            servers).
             """
             def recreate_search(self, repository, search_bytes,
                                 discard_excess=False):
                 verb_log.append(search_bytes.split('\n', 1)[0])
-                if search_bytes == 'everything':
-                    return (None,
-                            request.FailedSmartServerResponse(('BadSearch',)))
+                if reject_search_func(search_bytes):
+                    return (None, request.FailedSmartServerResponse(('BadSearch',)))
                 return super(OldGetStreamVerb,
                         self).recreate_search(repository, search_bytes,
                             discard_excess=discard_excess)
         self.override_verb('Repository.get_stream_1.19', OldGetStreamVerb)
+
+    def test_fetch_texts_for_rev_backwards_compat(self):
+        """Can fetch with TextsForRevisionSearchResult even with pre 2.5 servers.
+        
+        Pre-2.5 do not support 'texts-for-rev' searches with the
+        Repository.get_stream_1.19 verb.
+        """
+        self.disable_search(lambda bytes: bytes.startswith('texts-for-rev\n'))
         local = self.make_branch('local')
         builder = self.make_branch_builder('remote')
-        builder.build_commit(message="Commit.")
+        builder.build_commit(message="Commit.", rev_id='rev-1')
         remote_branch_url = self.smart_server.get_url() + 'remote'
         remote_branch = bzrdir.BzrDir.open(remote_branch_url).open_branch()
         self.hpss_calls = []
-        local.repository.fetch(
-            remote_branch.repository,
-            fetch_spec=vf_search.EverythingResult(remote_branch.repository))
+        local.repository.fetch(remote_branch.repository,
+            fetch_spec=vf_search.TextsForRevisionSearchResult('rev-1'))
         # make sure the overridden verb was used
-        self.assertLength(1, verb_log)
+        self.assertLength(1, self.verb_log)
         # more than one HPSS call is needed, but because it's a VFS callback
         # its hard to predict exactly how many.
         self.assertTrue(len(self.hpss_calls) > 1)

=== modified file 'bzrlib/tests/test_repository.py'
--- bzrlib/tests/test_repository.py	2011-12-22 19:54:56 +0000
+++ bzrlib/tests/test_repository.py	2012-01-25 17:56:30 +0000
@@ -1559,7 +1559,8 @@
         """
         b_source = self.make_abc_branch()
         b_base = b_source.bzrdir.sprout('base', revision_id='A').open_branch()
-        b_stacked = b_base.bzrdir.sprout('stacked', stacked=True).open_branch()
+        b_stacked = b_base.bzrdir.sprout('stacked', stacked=True,
+            create_tree_if_local=False).open_branch()
         b_stacked.lock_write()
         self.addCleanup(b_stacked.unlock)
         b_stacked.fetch(b_source, 'B')

=== modified file 'bzrlib/vf_search.py'
--- bzrlib/vf_search.py	2011-12-19 13:23:58 +0000
+++ bzrlib/vf_search.py	2012-01-25 17:56:30 +0000
@@ -61,6 +61,9 @@
         """
         raise NotImplementedError(self.get_keys)
 
+    def get_special(self):
+        return []
+
     def is_empty(self):
         """Return false if the search lists 1 or more revisions."""
         raise NotImplementedError(self.is_empty)
@@ -509,3 +512,93 @@
         # walking, so we can exclude them from the start list.
         start_keys = set(start_keys).difference(found_heads)
     return start_keys, exclude_keys, len(keys)
+
+
+class UnionSearchResult(AbstractSearchResult):
+    """The union of multiple search results."""
+
+    def __init__(self, search_results):
+        self.search_results = frozenset(search_results)
+
+    def get_recipe(self):
+        """Return a recipe that can be used to replay this search.
+
+        :return: A tuple of ('union', (recipe, ...)).
+        """
+        return ('union', tuple(sr.get_recipe() for sr in self.search_results))
+
+    def get_network_struct(self):
+        """Return a tuple that can be transmitted via the HPSS protocol."""
+        return ('union',
+                tuple(sr.get_network_struct() for sr in self.search_results))
+
+    def get_keys(self):
+        """Return the keys found in this search.
+
+        :return: A set of keys.
+        """
+        return set(sr.get_keys() for sr in self.search_results)
+
+    def get_special(self):
+        specials = []
+        for sr in self.search_results:
+            specials.extend(sr.get_special())
+        return specials
+
+    def is_empty(self):
+        """Return false if the search lists 1 or more revisions."""
+        return all(sr.is_empty() for sr in self.search_results)
+
+    def refine(self, seen, referenced):
+        """Create a new search by refining this search.
+
+        :param seen: Revisions that have been satisfied.
+        :param referenced: Revision references observed while satisfying some
+            of this search.
+        :return: A search result.
+        """
+        raise NotImplementedError(self.refine)
+
+
+class TextsForRevisionSearchResult(AbstractSearchResult):
+    """A search result specifying all the texts for a given revision."""
+
+    def __init__(self, revision_id):
+        """Constructor.
+
+        :param revision_id: A revision ID.  All records needed to create a
+            checkout of this revision are referenced by this result (i.e. the
+            revision record and corresponding inventory record, and all
+            referenced texts and chk_bytes).
+        """
+        self.revision_id = revision_id
+
+    def get_recipe(self):
+        """Return a recipe that can be used to replay this search.
+
+        :return: A tuple of ('texts-for-rev', revision_id)
+        """
+        return ('texts-for-rev', self.revision_id)
+
+    def get_network_struct(self):
+        """Return a tuple that can be transmitted via the HPSS protocol."""
+        return ('texts-for-rev', self.revision_id)
+
+    def get_keys(self):
+        return [self.revision_id]
+
+    def get_special(self):
+        return [('texts-for-rev', self.revision_id)]
+
+    def is_empty(self):
+        """Return false if the search lists 1 or more revisions."""
+        return False
+
+    def refine(self, seen, referenced):
+        # XXX: this is pretty wrong, but texts-for-rev is advisory rather than
+        # mandatory I guess...
+        #trace.mutter("seen, ref'd: %r, %r", seen, referenced)
+        res = SearchResult(set(), set(referenced), 0, set()).refine(seen, referenced)
+        #trace.mutter("-> %r", res)
+        return res
+        #raise NotImplementedError(self.refine)

=== modified file 'doc/en/release-notes/bzr-2.5.txt'
--- doc/en/release-notes/bzr-2.5.txt	2012-01-23 15:02:51 +0000
+++ doc/en/release-notes/bzr-2.5.txt	2012-01-25 17:56:30 +0000
@@ -36,6 +36,10 @@
   a control directory (but no branch or working tree).
   (Jelmer Vernooij, #913980)
 
+* Much improved performance of ``bzr branch --stacked`` against the
+  smart server, by introduction of a new search type.
+  (Andrew Bennetts, Jelmer Vernooij, #791704)
+
 * New HPSS call for ``BzrDir.get_branches``. (Jelmer Vernooij, #894460)
 
 * Two new command hooks, ``pre_command`` and ``post_command``,