ls-files -k: a directory only can be killed if the index has a non-directory

"ls-files -o" and "ls-files -k" both traverse the working tree down
to find either all untracked paths or those that will be "killed"
(removed from the working tree to make room) when the paths recorded
in the index are checked out.  It is necessary to traverse the
working tree fully when enumerating all the "other" paths, but when
we are only interested in "killed" paths, we can take advantage of
the fact that paths that do not overlap with entries in the index
can never be killed.

The treat_one_path() helper function, which is called during the
recursive traversal, is the ideal place to implement an
optimization.

When we are looking at a directory P in the working tree, there are
three cases:

(1) P exists in the index.  Everything inside the directory P in
the working tree needs to go when P is checked out from the
index.

(2) P does not exist in the index, but there is P/Q in the index.
We know P will stay a directory when we check out the contents
of the index, but we do not know yet if there is a directory
P/Q in the working tree to be killed, so we need to recurse.

(3) P does not exist in the index, and there is no P/Q in the index
to require P to be a directory, either.  Only in this case, we
know that everything inside P will not be killed without
recursing.

Note that this helper is called by treat_leading_path() that decides
if we need to traverse only subdirectories of a single common
leading directory, which is essential for this optimization to be
correct.  This caller checks each level of the leading path
component from shallower directory to deeper ones, and that is what
allows us to only check if the path appears in the index.  If the
call to treat_one_path() weren't there, given a path P/Q/R, the real
traversal may start from directory P/Q/R, even when the index
records P as a regular file, and we would end up having to check if
any leading subpath in P/Q/R, e.g. P, appears in the index.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index 22020729cbc35dc5fe11d2a3194fe5994fe67ff9..c7eb6f4873045d787c0c7e4cc80c0209f6b7af83 100644 (file)
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -213,6 +213,8 @@ static void show_files(struct dir_struct *dir)
 
        /* For cached/deleted files we don't need to even do the readdir */
        if (show_others || show_killed) {
+               if (!show_others)
+                       dir->flags |= DIR_COLLECT_KILLED_ONLY;
                fill_directory(dir, pathspec);
                if (show_others)
                        show_other_files(dir);

diff --git a/dir.c b/dir.c
index 2f82cd193e5753ac7ecb7cdda66e8e587aaa1b7f..ff768f31af0aa828bdcea83304c81e4ae2cb8444 100644 (file)
--- a/dir.c
+++ b/dir.c
@@ -1173,12 +1173,37 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
                                          int dtype, struct dirent *de)
 {
        int exclude;
+       int has_path_in_index = !!cache_name_exists(path->buf, path->len, ignore_case);
+
        if (dtype == DT_UNKNOWN)
                dtype = get_dtype(de, path->buf, path->len);
 
        /* Always exclude indexed files */
-       if (dtype != DT_DIR &&
-           cache_name_exists(path->buf, path->len, ignore_case))
+       if (dtype != DT_DIR && has_path_in_index)
+               return path_none;
+
+       /*
+        * When we are looking at a directory P in the working tree,
+        * there are three cases:
+        *
+        * (1) P exists in the index.  Everything inside the directory P in
+        * the working tree needs to go when P is checked out from the
+        * index.
+        *
+        * (2) P does not exist in the index, but there is P/Q in the index.
+        * We know P will stay a directory when we check out the contents
+        * of the index, but we do not know yet if there is a directory
+        * P/Q in the working tree to be killed, so we need to recurse.
+        *
+        * (3) P does not exist in the index, and there is no P/Q in the index
+        * to require P to be a directory, either.  Only in this case, we
+        * know that everything inside P will not be killed without
+        * recursing.
+        */
+       if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
+           (dtype == DT_DIR) &&
+           !has_path_in_index &&
+           (directory_exists_in_index(path->buf, path->len) == index_nonexistent))
                return path_none;
 
        exclude = is_excluded(dir, path->buf, &dtype);

diff --git a/dir.h b/dir.h
index 3d6b80c933b395644c005f6d8df4697215ff000a..4677b861f0046492b2b2026789eaa69850afcc77 100644 (file)
--- a/dir.h
+++ b/dir.h
@@ -80,7 +80,8 @@ struct dir_struct {
                DIR_HIDE_EMPTY_DIRECTORIES = 1<<2,
                DIR_NO_GITLINKS = 1<<3,
                DIR_COLLECT_IGNORED = 1<<4,
-               DIR_SHOW_IGNORED_TOO = 1<<5
+               DIR_SHOW_IGNORED_TOO = 1<<5,
+               DIR_COLLECT_KILLED_ONLY = 1<<6
        } flags;
        struct dir_entry **entries;
        struct dir_entry **ignored;