Merge lp:~bzr/bzr/list-files-norecurse into lp:~bzr/bzr/trunk-old

[Ian Clatworthy]

[Ian Clatworthy (ian-clatworthy)]

This patch is the core of the work to make the ls command faster. 2 new parameters are added to the tree.list_files() API: from_dir and recursive. Numerous tests are added to cover these new parameters.

Implementation-wise, this builds on the iter-entries-norecurse branch.

[John A Meinel (jameinel)]

I believe Tree.list_files() is actually meant to be a 'deprecated' function that we just never got around to actually deprecating.

I'd rather see the code changed to use Tree.iter_entries_by_dir directly.

Also, as near as I can tell, this doesn't actually update any callers to *use* the new functionality, is that true?

review: Needs Information

[Ian Clatworthy (ian-clatworthy)]

John A Meinel wrote:
> Also, as near as I can tell, this doesn't actually update any callers to *use* the new functionality, is that true?
>
That's right. Another patch builds on this one, namely
https://code.edge.launchpad.net/~bzr/bzr/faster-ls/+merge/6670.

Ian C.

[Martin Pool (mbp)]

It's ok with me to merge this if you're finding it useful. I think John is right that the interfaces here could be cleaned up though.

review: Approve

=== modified file 'bzrlib/revisiontree.py'
--- bzrlib/revisiontree.py	2009-06-10 03:56:49 +0000
+++ bzrlib/revisiontree.py	2009-06-16 02:38:01 +0000
@@ -114,11 +114,18 @@
     def has_filename(self, filename):
         return bool(self.inventory.path2id(filename))
 
-    def list_files(self, include_root=False):
+    def list_files(self, include_root=False, from_dir=None, recursive=True):
         # The only files returned by this are those from the version
-        entries = self.inventory.iter_entries()
-        # skip the root for compatability with the current apis.
-        if self.inventory.root is not None and not include_root:
+        inv = self.inventory
+        if from_dir is None:
+            from_dir_id = None
+        else:
+            from_dir_id = inv.path2id(from_dir)
+            if from_dir_id is None:
+                # Directory not versioned
+                return
+        entries = inv.iter_entries(from_dir=from_dir_id, recursive=recursive)
+        if inv.root is not None and not include_root and from_dir is None:
             # skip the root for compatability with the current apis.
             entries.next()
         for path, entry in entries:

=== modified file 'bzrlib/tests/tree_implementations/test_list_files.py'
--- bzrlib/tests/tree_implementations/test_list_files.py	2009-03-23 14:59:43 +0000
+++ bzrlib/tests/tree_implementations/test_list_files.py	2009-06-16 02:38:01 +0000
@@ -49,7 +49,68 @@
         try:
             actual = [(path, status, kind, file_id)
                       for path, status, kind, file_id, ie in
-                          tree.list_files(include_root=False)]
+                          tree.list_files()]
+        finally:
+            tree.unlock()
+        self.assertEqual(expected, actual)
+
+    def test_list_files_with_root_no_recurse(self):
+        work_tree = self.make_branch_and_tree('wt')
+        tree = self.get_tree_no_parents_abc_content(work_tree)
+        expected = [('', 'V', 'directory', 'root-id'),
+                    ('a', 'V', 'file', 'a-id'),
+                    ('b', 'V', 'directory', 'b-id'),
+                   ]
+        tree.lock_read()
+        try:
+            actual = [(path, status, kind, file_id)
+                for path, status, kind, file_id, ie in
+                    tree.list_files(include_root=True, recursive=False)]
+        finally:
+            tree.unlock()
+        self.assertEqual(expected, actual)
+
+    def test_list_files_no_root_no_recurse(self):
+        work_tree = self.make_branch_and_tree('wt')
+        tree = self.get_tree_no_parents_abc_content(work_tree)
+        expected = [('a', 'V', 'file', 'a-id'),
+                    ('b', 'V', 'directory', 'b-id'),
+                   ]
+        tree.lock_read()
+        try:
+            actual = [(path, status, kind, file_id)
+                for path, status, kind, file_id, ie in
+                    tree.list_files(recursive=False)]
+        finally:
+            tree.unlock()
+        self.assertEqual(expected, actual)
+
+    def test_list_files_from_dir(self):
+        work_tree = self.make_branch_and_tree('wt')
+        tree = self.get_tree_no_parents_abc_content(work_tree)
+        expected = [('c', 'V', 'file', 'c-id'),
+                   ]
+        tree.lock_read()
+        try:
+            actual = [(path, status, kind, file_id)
+                      for path, status, kind, file_id, ie in
+                          tree.list_files(from_dir='b')]
+        finally:
+            tree.unlock()
+        self.assertEqual(expected, actual)
+
+    def test_list_files_from_dir_no_recurse(self):
+        # The test trees don't have much nesting so test with an explicit root
+        work_tree = self.make_branch_and_tree('wt')
+        tree = self.get_tree_no_parents_abc_content(work_tree)
+        expected = [('a', 'V', 'file', 'a-id'),
+                    ('b', 'V', 'directory', 'b-id'),
+                   ]
+        tree.lock_read()
+        try:
+            actual = [(path, status, kind, file_id)
+                      for path, status, kind, file_id, ie in
+                          tree.list_files(from_dir='', recursive=False)]
         finally:
             tree.unlock()
         self.assertEqual(expected, actual)

=== modified file 'bzrlib/transform.py'
--- bzrlib/transform.py	2009-06-10 03:56:49 +0000
+++ bzrlib/transform.py	2009-06-16 02:38:01 +0000
@@ -1748,7 +1748,7 @@
             if self._transform.final_file_id(trans_id) is None:
                 yield self._final_paths._determine_path(trans_id)
 
-    def _make_inv_entries(self, ordered_entries, specific_file_ids):
+    def _make_inv_entries(self, ordered_entries, specific_file_ids=None):
         for trans_id, parent_file_id in ordered_entries:
             file_id = self._transform.final_file_id(trans_id)
             if file_id is None:
@@ -1791,14 +1791,41 @@
                                                       specific_file_ids):
             yield unicode(self._final_paths.get_path(trans_id)), entry
 
-    def list_files(self, include_root=False):
-        """See Tree.list_files."""
+    def _iter_entries_for_dir(self, dir_path):
+        """Return path, entry for items in a directory without recursing down."""
+        dir_file_id = self.path2id(dir_path)
+        ordered_ids = []
+        for file_id in self.iter_children(dir_file_id):
+            trans_id = self._transform.trans_id_file_id(file_id)
+            ordered_ids.append((trans_id, file_id))
+        for entry, trans_id in self._make_inv_entries(ordered_ids):
+            yield unicode(self._final_paths.get_path(trans_id)), entry
+
+    def list_files(self, include_root=False, from_dir=None, recursive=True):
+        """See WorkingTree.list_files."""
         # XXX This should behave like WorkingTree.list_files, but is really
         # more like RevisionTree.list_files.
-        for path, entry in self.iter_entries_by_dir():
-            if entry.name == '' and not include_root:
-                continue
-            yield path, 'V', entry.kind, entry.file_id, entry
+        if recursive:
+            prefix = None
+            if from_dir:
+                prefix = from_dir + '/'
+            entries = self.iter_entries_by_dir()
+            for path, entry in entries:
+                if entry.name == '' and not include_root:
+                    continue
+                if prefix:
+                    if not path.startswith(prefix):
+                        continue
+                    path = path[len(prefix):]
+                yield path, 'V', entry.kind, entry.file_id, entry
+        else:
+            if from_dir is None and include_root is True:
+                root_entry = inventory.make_entry('directory', '',
+                    ROOT_PARENT, self.get_root_id())
+                yield '', 'V', 'directory', root_entry.file_id, root_entry
+            entries = self._iter_entries_for_dir(from_dir or '')
+            for path, entry in entries:
+                yield path, 'V', entry.kind, entry.file_id, entry
 
     def kind(self, file_id):
         trans_id = self._transform.trans_id_file_id(file_id)

=== modified file 'bzrlib/workingtree.py'
--- bzrlib/workingtree.py	2009-06-15 15:47:45 +0000
+++ bzrlib/workingtree.py	2009-06-16 02:38:01 +0000
@@ -1115,15 +1115,16 @@
     def _kind(self, relpath):
         return osutils.file_kind(self.abspath(relpath))
 
-    def list_files(self, include_root=False):
-        """Recursively list all files as (path, class, kind, id, entry).
+    def list_files(self, include_root=False, from_dir=None, recursive=True):
+        """List all files as (path, class, kind, id, entry).
 
         Lists, but does not descend into unversioned directories.
-
         This does not include files that have been deleted in this
-        tree.
+        tree. Skips the control directory.
 
-        Skips the control directory.
+        :param include_root: if True, do not return an entry for the root
+        :param from_dir: start from this directory or None for the root
+        :param recursive: whether to recurse into subdirectories or not
         """
         # list_files is an iterator, so @needs_read_lock doesn't work properly
         # with it. So callers should be careful to always read_lock the tree.
@@ -1131,7 +1132,7 @@
             raise errors.ObjectNotLocked(self)
 
         inv = self.inventory
-        if include_root is True:
+        if from_dir is None and include_root is True:
             yield ('', 'V', 'directory', inv.root.file_id, inv.root)
         # Convert these into local objects to save lookup times
         pathjoin = osutils.pathjoin
@@ -1144,13 +1145,22 @@
         fk_entries = {'directory':TreeDirectory, 'file':TreeFile, 'symlink':TreeLink}
 
         # directory file_id, relative path, absolute path, reverse sorted children
-        children = os.listdir(self.basedir)
+        if from_dir is not None:
+            from_dir_id = inv.path2id(from_dir)
+            if from_dir_id is None:
+                # Directory not versioned
+                return
+            from_dir_abspath = pathjoin(self.basedir, from_dir)
+        else:
+            from_dir_id = inv.root.file_id
+            from_dir_abspath = self.basedir
+        children = os.listdir(from_dir_abspath)
         children.sort()
         # jam 20060527 The kernel sized tree seems equivalent whether we
         # use a deque and popleft to keep them sorted, or if we use a plain
         # list and just reverse() them.
         children = collections.deque(children)
-        stack = [(inv.root.file_id, u'', self.basedir, children)]
+        stack = [(from_dir_id, u'', from_dir_abspath, children)]
         while stack:
             from_dir_id, from_dir_relpath, from_dir_abspath, children = stack[-1]
 
@@ -1214,14 +1224,15 @@
                 if fk != 'directory':
                     continue
 
-                # But do this child first
-                new_children = os.listdir(fap)
-                new_children.sort()
-                new_children = collections.deque(new_children)
-                stack.append((f_ie.file_id, fp, fap, new_children))
-                # Break out of inner loop,
-                # so that we start outer loop with child
-                break
+                # But do this child first if recursing down
+                if recursive:
+                    new_children = os.listdir(fap)
+                    new_children.sort()
+                    new_children = collections.deque(new_children)
+                    stack.append((f_ie.file_id, fp, fap, new_children))
+                    # Break out of inner loop,
+                    # so that we start outer loop with child
+                    break
             else:
                 # if we finished all children, pop it off the stack
                 stack.pop()

=== modified file 'bzrlib/workingtree_4.py'
--- bzrlib/workingtree_4.py	2009-06-11 04:23:53 +0000
+++ bzrlib/workingtree_4.py	2009-06-16 02:38:01 +0000
@@ -1844,12 +1844,19 @@
             return None
         return ie.executable
 
-    def list_files(self, include_root=False):
+    def list_files(self, include_root=False, from_dir=None, recursive=True):
         # We use a standard implementation, because DirStateRevisionTree is
         # dealing with one of the parents of the current state
         inv = self._get_inventory()
-        entries = inv.iter_entries()
-        if self.inventory.root is not None and not include_root:
+        if from_dir is None:
+            from_dir_id = None
+        else:
+            from_dir_id = inv.path2id(from_dir)
+            if from_dir_id is None:
+                # Directory not versioned
+                return
+        entries = inv.iter_entries(from_dir=from_dir_id, recursive=recursive)
+        if inv.root is not None and not include_root and from_dir is None:
             entries.next()
         for path, entry in entries:
             yield path, 'V', entry.kind, entry.file_id, entry