Merge lp:~bzr/bzr/faster-ls into lp:~bzr/bzr/trunk-old

[Ian Clatworthy]

[Ian Clatworthy (ian-clatworthy)]

This patch makes ls faster. In particular, ls on a historical revision is faster: ls -r-1 on the OpenOffice trunk drops from 62 seconds to 1.3 seconds. Plain ls on a subdirectory gets faster as well, dropping from 3-4 seconds to around 1 second.

As well as improving performance, I've moved most of the ls logic out of builtins.py to ls.py. New unit tests are needed for this new public API. Before I add those, I'd like a reviewer to confirm:

1. the new API looks right
2. my changes to the blackbox tests are correct.

In the latter case, I believe that 'ls dir --from-root' ought to show just the stuff in dir, not everything (as the current test expects).

[John A Meinel (jameinel)]

I would *like* to see 'ls' work on top of "iter_entries_by_dir()" rather than list_files().

As near as I can tell, the only thing that list_files gives is "kind character" (though perhaps it also does more with unversioned files?)

I'd like to know if you think that is possible, or if it is too different of an api.

I'm not sure about having a file named "ls.py", maybe it's okay. I don't really have a much better name for it.

+# Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Canonical Ltd

I'm pretty sure 'ls.py' is only (C) 2009 :)

+def ls(tree, outf, from_dir=None, recursive=False, kind=None, unknown=False,
+ versioned=False, ignored=False, verbose=False, null=False, show_ids=False,
+ prefix=None, from_root=False):

^- When I see a function with that many parameters, I wonder if it wouldn't be better implemented as some sort of class... Not saying that is true here, but it seems like it might.

I think we should also think about whether it would be possible to add "bzr ls --added" more easily with this change or not. As near as I can tell, it would be ~ the same effort, so at least it isn't worse.

The main difficulty we've had is that "Versioned" is a state of a single tree, but "Added" is a diff between two trees. So you need an api that can give you the difference among 3 trees:
1) basis_tree
2) current working tree (versioned info)
3) filesystem

Since that gives you "Newly Versioned" "Renamed" "Ignored" etc.

As for the blackbox changes... You changed everything to be '--recurse' to '--no-recurse' (since the default changed), but you didn't add back any "--recurse" tests.

Also, is this the correct behavior:
        self.ls_equals('subdir/b\n'
                       , '--from-root')

I'm thinking it probably is, but I'll note that it is a change in behavior. 'bzr ls --from-root' used to be equivalent to 'bzr ls ../../' until you got to the root. We now don't have a way from a subdirectory to say "ls everything" without giving the full path to the root.

While doing "bzr ls --from-root ." would be an easy way to specify the opposite.

review: Needs Information

[John A Meinel (jameinel)]

Sorry, I hit 'Save' before I was done.

=== modified file 'bzrlib/transform.py'

I really wonder if this should be in "bzrlib/preview_tree.py". Not that you have to do that.

I noticed you didn't add "bzrlib/tests/test_ls.py". Since the code is now refactored, it would be nice if most of the 'blackbox/tests_ls.py' was actually done as whitebox tests. Again, not required, but if you at least added the test file and some very basic tests, it would be a place that could be obviously expanded later.

So overall, I think it is worth landing something like this.

[Robert Collins (lifeless)]

Just a couple of comments.

ls.py doesn't seem to know if its UI layer or logic layer.

I'd personally rather have a clear logic layer - something that takes
the needed parameters and provides an iterator over [semi-]structured
data.

then the command can be
for thing in [dols]:
    self.output.write("%s%s\n" % (thing[0], thing[1]))

This would make this useful for GUI's as well.

I think a good home for this would be tree.py, rather than a new python
module, as it is very tree specific code (in fact, in refactoring terms,
the first parameter 'tree' stands out like a ForeignMethod).

-Rob

[Martin Pool (mbp)]

> This patch makes ls faster. In particular, ls on a historical revision is
> faster: ls -r-1 on the OpenOffice trunk drops from 62 seconds to 1.3 seconds.
> Plain ls on a subdirectory gets faster as well, dropping from 3-4 seconds to
> around 1 second.

Just a meta-comment: also explaining in the cover letter what you changed to do that will help with reviews. People may have comments only on the approach without reading the patches and also it helps verify the patch does what was intended.

[Ian Clatworthy (ian-clatworthy)]

> Just a couple of comments.
>
> ls.py doesn't seem to know if its UI layer or logic layer.
>
> I'd personally rather have a clear logic layer - something that takes
> the needed parameters and provides an iterator over [semi-]structured
> data.
>
> then the command can be
> for thing in [dols]:
> self.output.write("%s%s\n" % (thing[0], thing[1]))
>
> This would make this useful for GUI's as well.
>
> I think a good home for this would be tree.py, rather than a new python
> module, as it is very tree specific code (in fact, in refactoring terms,
> the first parameter 'tree' stands out like a ForeignMethod).

All good points, though the use case for a GUI ls client isn't really there. (The functionality tends to be provided by far more powerful GUIs like qbrowse and Olive). I'll resubmit this in a less ambitious form, just focusing on the logic bug and performance issue for now.

=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2009-06-11 06:54:33 +0000
+++ bzrlib/builtins.py	2009-06-16 02:37:53 +0000
@@ -2357,42 +2357,32 @@
             recursive=False, from_root=False,
             unknown=False, versioned=False, ignored=False,
             null=False, kind=None, show_ids=False, path=None):
-
+        # Validate the command line options
         if kind and kind not in ('file', 'directory', 'symlink'):
             raise errors.BzrCommandError('invalid kind specified')
-
         if verbose and null:
             raise errors.BzrCommandError('Cannot set both --verbose and --null')
-        all = not (unknown or versioned or ignored)
-
-        selection = {'I':ignored, '?':unknown, 'V':versioned}
-
         if path is None:
-            fs_path = '.'
-            prefix = ''
-        else:
-            if from_root:
-                raise errors.BzrCommandError('cannot specify both --from-root'
-                                             ' and PATH')
-            fs_path = path
-            prefix = path
-        tree, branch, relpath = bzrdir.BzrDir.open_containing_tree_or_branch(
-            fs_path)
-        if from_root:
-            relpath = u''
-        elif relpath:
-            relpath += '/'
+            path = '.'
+        elif from_root:
+            raise errors.BzrCommandError('cannot specify both --from-root'
+                                         ' and PATH')
+
+        # Get the tree
+        tree, branch, dir = bzrdir.BzrDir.open_containing_tree_or_branch(path)
+        mutter("ls dir is %s", dir)
         if revision is not None or tree is None:
             tree = _get_one_revision_tree('ls', revision, branch=branch)
 
-        apply_view = False
-        if isinstance(tree, WorkingTree) and tree.supports_views():
-            view_files = tree.views.lookup_view()
-            if view_files:
-                apply_view = True
-                view_str = views.view_display_str(view_files)
-                note("Ignoring files outside view. View is %s" % view_str)
+        # Calculate the prefix to use
+        prefix = None
+        if from_root:
+            if dir:
+                prefix = dir + '/'
+        elif path != '.':
+            prefix = path + '/'
 
+<<<<<<< TREE
         tree.lock_read()
         try:
             for fp, fc, fkind, fid, entry in tree.list_files(include_root=False):
@@ -2436,6 +2426,13 @@
                             self.outf.write(outstring + '\n')
         finally:
             tree.unlock()
+=======
+        # Display the files
+        from bzrlib import ls
+        ls.ls(tree, self.outf, from_dir=dir, recursive=recursive,
+            kind=kind, unknown=unknown, versioned=versioned, ignored=ignored,
+            verbose=verbose, null=null, show_ids=show_ids, prefix=prefix)
+>>>>>>> MERGE-SOURCE
 
 
 class cmd_unknowns(Command):
 
=== added file 'bzrlib/ls.py'
--- bzrlib/ls.py	1970-01-01 00:00:00 +0000
+++ bzrlib/ls.py	2009-06-16 02:37:53 +0000
@@ -0,0 +1,115 @@
+# Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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
+
+"""List files in a tree."""
+
+
+from bzrlib.lazy_import import lazy_import
+lazy_import(globals(), """
+from bzrlib import (
+    errors,
+    osutils,
+    )
+from bzrlib.trace import mutter, note
+from bzrlib.workingtree import WorkingTree
+""")
+
+
+def ls(tree, outf, from_dir=None, recursive=False, kind=None, unknown=False,
+    versioned=False, ignored=False, verbose=False, null=False, show_ids=False,
+    prefix=None, from_root=False):
+    """List files for a tree.
+
+    If unknown, versioned and ignored are all False, then all are displayed.
+
+    :param tree: the tree to display files for
+    :param outf: the output stream
+    :param from_dir: just from this directory
+    :param recursive: whether to recurse into subdirectories or not
+    :param kind: one of 'file', 'symlink', 'directory' or None for all
+    :param unknown: include unknown files or not
+    :param versioned: include versioned files or not
+    :param ignored: include ignored files or not
+    :param verbose: show file kinds, not just paths
+    :param null: separate entries with null characters instead of newlines
+    :param show_ids: show file_ids or not
+    :param prefix: prefix paths with this string or None for no prefix
+    :param from_root: show paths from the root instead of relative
+    """
+    mutter("ls from: %s" % (from_dir,))
+    # Tell the user if a view if being applied
+    apply_view = False
+    if isinstance(tree, WorkingTree) and tree.supports_views():
+        view_files = tree.views.lookup_view()
+        if view_files:
+            apply_view = True
+            view_str = views.view_display_str(view_files)
+            note("Ignoring files outside view. View is %s" % view_str)
+
+    # Find and display the files
+    all = not (unknown or versioned or ignored)
+    selection = {'I':ignored, '?':unknown, 'V':versioned}
+    #if from_dir and from_root:
+    #    prefix = from_dir
+    #else:
+    #    prefix = None
+    tree.lock_read()
+    try:
+        for fp, fc, fkind, fid, entry in tree.list_files(include_root=False,
+            from_dir=from_dir, recursive=recursive):
+            # Apply additional masking
+            if not all and not selection[fc]:
+                continue
+            if kind is not None and fkind != kind:
+                continue
+            if apply_view:
+                if from_dir:
+                    fullpath = osutils.pathjoin(from_dir, fp)
+                else:
+                    fullpath = fp
+                try:
+                    views.check_path_in_view(tree, fullpath)
+                except errors.FileOutsideView:
+                    continue
+
+            # Output the entry
+            kindch = entry.kind_character()
+            if prefix is not None:
+                fp = osutils.pathjoin(prefix, fp)
+            outstring = fp + kindch
+            if verbose:
+                outstring = '%-8s %s' % (fc, outstring)
+                if show_ids and fid is not None:
+                    outstring = "%-50s %s" % (outstring, fid)
+                outf.write(outstring + '\n')
+            elif null:
+                outf.write(fp + '\0')
+                if show_ids:
+                    if fid is not None:
+                        outf.write(fid)
+                    outf.write('\0')
+                outf.flush()
+            else:
+                if show_ids:
+                    if fid is not None:
+                        my_id = fid
+                    else:
+                        my_id = ''
+                    outf.write('%-50s %s\n' % (outstring, my_id))
+                else:
+                    outf.write(outstring + '\n')
+    finally:
+        tree.unlock()
 
=== modified file 'bzrlib/revisiontree.py'
--- bzrlib/revisiontree.py	2009-06-10 03:56:49 +0000
+++ bzrlib/revisiontree.py	2009-06-16 02:37:53 +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/blackbox/test_ls.py'
--- bzrlib/tests/blackbox/test_ls.py	2009-05-08 13:39:32 +0000
+++ bzrlib/tests/blackbox/test_ls.py	2009-06-16 02:37:53 +0000
@@ -129,19 +129,11 @@
         self.ls_equals('b\n')
         self.ls_equals('b\0'
                   , '--null')
-        self.ls_equals('.bzrignore\n'
-                       'a\n'
-                       'subdir/\n'
-                       'subdir/b\n'
+        self.ls_equals('subdir/b\n'
                        , '--from-root')
-        self.ls_equals('.bzrignore\0'
-                       'a\0'
-                       'subdir\0'
-                       'subdir/b\0'
+        self.ls_equals('subdir/b\0'
                        , '--from-root --null')
-        self.ls_equals('.bzrignore\n'
-                       'a\n'
-                       'subdir/\n'
+        self.ls_equals('subdir/b\n'
                        , '--from-root', recursive=False)
 
     def test_ls_path(self):
 
=== 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:37:53 +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:37:53 +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:37:53 +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:37:53 +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