Rev 4670: Implement an expansion function that works directly on the chk maps. in http://bazaar.launchpad.net/~jameinel/bzr/2.0.1-faster-log-dir-bug374730

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.0.1-faster-log-dir-bug374730

------------------------------------------------------------
revno: 4670
revision-id: john at arbash-meinel.com-20090923215633-u3dxk23wsnlx4tqs
parent: john at arbash-meinel.com-20090923214306-o0ecifj3bffgfrcr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.0.1-faster-log-dir-bug374730
timestamp: Wed 2009-09-23 16:56:33 -0500
message:
  Implement an expansion function that works directly on the chk maps.
-------------- next part --------------
=== modified file 'bzrlib/inventory.py'
--- a/bzrlib/inventory.py	2009-09-23 21:43:06 +0000
+++ b/bzrlib/inventory.py	2009-09-23 21:56:33 +0000
@@ -1568,18 +1568,20 @@
             foo-id, baz-id, frob-id, fringle-id
         As interesting ids.
         """
+        # When we hit the TREE_ROOT, we'll get an interesting parent of None,
+        # but we don't actually want to recurse into that
         interesting_parents = set([None])
         # TODO: Pre-pass over the list of fileids to see if anything is already
         #       deserialized in self._fileid_to_entry_cache
 
         directories_to_expand = set()
-        children_of_parent_id = {}
+        # children_of_parent_id = {}
         # It is okay if some of the fileids are missing
         for entry in self._getitems(file_ids):
             if entry.kind == 'directory':
                 directories_to_expand.add(entry.file_id)
             interesting_parents.add(entry.parent_id)
-            children_of_parent_id.setdefault(entry.parent_id, []).append(entry)
+            #children_of_parent_id.setdefault(entry.parent_id, []).append(entry)
 
         # Now, interesting_parents has all of the direct parents, but not the
         # parents of those parents. It also may have some duplicates with
@@ -1589,12 +1591,26 @@
             next_parents = set()
             for entry in self._getitems(remaining_parents):
                 next_parents.add(entry.parent_id)
+                #children_of_parent_id.setdefault(entry.parent_id, []).append(entry)
             # Remove any search tips we've already processed
             remaining_parents = next_parents.difference(interesting_parents)
             interesting_parents.update(remaining_parents)
             # We should probably also .difference(directories_to_expand)
         interesting_parents.discard(None)
-        return interesting_parents, file_ids
+        result_file_ids = set(file_ids)
+        while directories_to_expand:
+            # Expand directories by looking in the
+            # parent_id_basename_to_file_id map
+            keys = [(f,) for f in directories_to_expand]
+            directories_to_expand = set()
+            items = self.parent_id_basename_to_file_id.iteritems(keys)
+            next_file_ids = set([item[1] for item in items])
+            next_file_ids = next_file_ids.difference(result_file_ids)
+            result_file_ids.update(next_file_ids)
+            for entry in self._getitems(next_file_ids):
+                if entry.kind == 'directory':
+                    directories_to_expand.add(entry.file_id)
+        return interesting_parents, result_file_ids
 
     def filter(self, specific_fileids):
         """Get an inventory view filtered against a set of file-ids.

=== modified file 'bzrlib/tests/test_inv.py'
--- a/bzrlib/tests/test_inv.py	2009-09-23 21:43:06 +0000
+++ b/bzrlib/tests/test_inv.py	2009-09-23 21:56:33 +0000
@@ -1180,7 +1180,7 @@
         val_parents, val_other = inv._expand_fileids_to_parents_and_children(
                                     file_ids)
         self.assertEqual(set(parent_ids), val_parents)
-        self.assertEqual(other_ids, val_other)
+        self.assertEqual(set(other_ids), val_other)
 
     def test_make_simple_inventory(self):
         inv = self.make_simple_inventory()
@@ -1221,3 +1221,10 @@
         inv = self.make_simple_inventory()
         self.assertExpand(['TREE_ROOT', 'dir1-id', 'sub-dir1-id'], 
                           ['subsub-file1-id'], inv, ['subsub-file1-id'])
+
+    def test_get_children(self):
+        inv = self.make_simple_inventory()
+        self.assertExpand(['TREE_ROOT'], 
+                          ['dir1-id', 'sub-dir1-id', 'sub-file1-id',
+                           'sub-file2-id', 'subsub-file1-id',
+                          ], inv, ['dir1-id'])