Merge branch 'jc/ls-files-killed-optim'
authorJunio C Hamano <gitster@pobox.com>
Wed, 11 Sep 2013 22:03:28 +0000 (15:03 -0700)
committerJunio C Hamano <gitster@pobox.com>
Wed, 11 Sep 2013 22:03:28 +0000 (15:03 -0700)
"git ls-files -k" needs to crawl only the part of the working tree
that may overlap the paths in the index to find killed files, but
shared code with the logic to find all the untracked files, which
made it unnecessarily inefficient.

* jc/ls-files-killed-optim:
dir.c::test_one_path(): work around directory_exists_in_index_icase() breakage
t3010: update to demonstrate "ls-files -k" optimization pitfalls
ls-files -k: a directory only can be killed if the index has a non-directory
dir.c: use the cache_* macro to access the current index

1  2 
builtin/ls-files.c
dir.c
dir.h
t/t3010-ls-files-killed-modified.sh
diff --combined builtin/ls-files.c
index d4823c9d38e5e22dff62d979601e0b06b9c857f3,c7eb6f4873045d787c0c7e4cc80c0209f6b7af83..e1cf6d8547d4aa7f548fb80f0efb8f4e7b1d9c8e
@@@ -13,7 -13,6 +13,7 @@@
  #include "parse-options.h"
  #include "resolve-undo.h"
  #include "string-list.h"
 +#include "pathspec.h"
  
  static int abbrev;
  static int show_deleted;
@@@ -31,7 -30,7 +31,7 @@@ static int debug_mode
  static const char *prefix;
  static int max_prefix_len;
  static int prefix_len;
 -static const char **pathspec;
 +static struct pathspec pathspec;
  static int error_unmatch;
  static char *ps_matched;
  static const char *with_tree;
@@@ -47,14 -46,10 +47,14 @@@ static const char *tag_modified = ""
  static const char *tag_skip_worktree = "";
  static const char *tag_resolve_undo = "";
  
 -static void write_name(const char* name, size_t len)
 +static void write_name(const char *name)
  {
 -      write_name_quoted_relative(name, len, prefix, prefix_len, stdout,
 -                      line_terminator);
 +      /*
 +       * With "--full-name", prefix_len=0; this caller needs to pass
 +       * an empty string in that case (a NULL is good for "").
 +       */
 +      write_name_quoted_relative(name, prefix_len ? prefix : NULL,
 +                                 stdout, line_terminator);
  }
  
  static void show_dir_entry(const char *tag, struct dir_entry *ent)
        if (len >= ent->len)
                die("git ls-files: internal error - directory entry not superset of prefix");
  
 -      if (!match_pathspec(pathspec, ent->name, ent->len, len, ps_matched))
 +      if (!match_pathspec_depth(&pathspec, ent->name, ent->len, len, ps_matched))
                return;
  
        fputs(tag, stdout);
 -      write_name(ent->name, ent->len);
 +      write_name(ent->name);
  }
  
  static void show_other_files(struct dir_struct *dir)
@@@ -132,14 -127,14 +132,14 @@@ static void show_killed_files(struct di
        }
  }
  
 -static void show_ce_entry(const char *tag, struct cache_entry *ce)
 +static void show_ce_entry(const char *tag, const struct cache_entry *ce)
  {
        int len = max_prefix_len;
  
        if (len >= ce_namelen(ce))
                die("git ls-files: internal error - cache entry not superset of prefix");
  
 -      if (!match_pathspec(pathspec, ce->name, ce_namelen(ce), len, ps_matched))
 +      if (!match_pathspec_depth(&pathspec, ce->name, ce_namelen(ce), len, ps_matched))
                return;
  
        if (tag && *tag && show_valid_bit &&
                       find_unique_abbrev(ce->sha1,abbrev),
                       ce_stage(ce));
        }
 -      write_name(ce->name, ce_namelen(ce));
 +      write_name(ce->name);
        if (debug_mode) {
 -              printf("  ctime: %d:%d\n", ce->ce_ctime.sec, ce->ce_ctime.nsec);
 -              printf("  mtime: %d:%d\n", ce->ce_mtime.sec, ce->ce_mtime.nsec);
 -              printf("  dev: %d\tino: %d\n", ce->ce_dev, ce->ce_ino);
 -              printf("  uid: %d\tgid: %d\n", ce->ce_uid, ce->ce_gid);
 -              printf("  size: %d\tflags: %x\n", ce->ce_size, ce->ce_flags);
 +              const struct stat_data *sd = &ce->ce_stat_data;
 +
 +              printf("  ctime: %d:%d\n", sd->sd_ctime.sec, sd->sd_ctime.nsec);
 +              printf("  mtime: %d:%d\n", sd->sd_mtime.sec, sd->sd_mtime.nsec);
 +              printf("  dev: %d\tino: %d\n", sd->sd_dev, sd->sd_ino);
 +              printf("  uid: %d\tgid: %d\n", sd->sd_uid, sd->sd_gid);
 +              printf("  size: %d\tflags: %x\n", sd->sd_size, ce->ce_flags);
        }
  }
  
@@@ -195,7 -188,7 +195,7 @@@ static void show_ru_info(void
                len = strlen(path);
                if (len < max_prefix_len)
                        continue; /* outside of the prefix */
 -              if (!match_pathspec(pathspec, path, len, max_prefix_len, ps_matched))
 +              if (!match_pathspec_depth(&pathspec, path, len, max_prefix_len, ps_matched))
                        continue; /* uninterested */
                for (i = 0; i < 3; i++) {
                        if (!ui->mode[i])
                        printf("%s%06o %s %d\t", tag_resolve_undo, ui->mode[i],
                               find_unique_abbrev(ui->sha1[i], abbrev),
                               i + 1);
 -                      write_name(path, len);
 +                      write_name(path);
                }
        }
  }
  
 -static int ce_excluded(struct dir_struct *dir, struct cache_entry *ce)
 +static int ce_excluded(struct dir_struct *dir, const struct cache_entry *ce)
  {
        int dtype = ce_to_dtype(ce);
        return is_excluded(dir, ce->name, &dtype);
@@@ -220,15 -213,17 +220,17 @@@ static void show_files(struct dir_struc
  
        /* For cached/deleted files we don't need to even do the readdir */
        if (show_others || show_killed) {
 -              fill_directory(dir, pathspec);
+               if (!show_others)
+                       dir->flags |= DIR_COLLECT_KILLED_ONLY;
 +              fill_directory(dir, &pathspec);
                if (show_others)
                        show_other_files(dir);
                if (show_killed)
                        show_killed_files(dir);
        }
 -      if (show_cached | show_stage) {
 +      if (show_cached || show_stage) {
                for (i = 0; i < active_nr; i++) {
 -                      struct cache_entry *ce = active_cache[i];
 +                      const struct cache_entry *ce = active_cache[i];
                        if ((dir->flags & DIR_SHOW_IGNORED) &&
                            !ce_excluded(dir, ce))
                                continue;
                                (ce_skip_worktree(ce) ? tag_skip_worktree : tag_cached), ce);
                }
        }
 -      if (show_deleted | show_modified) {
 +      if (show_deleted || show_modified) {
                for (i = 0; i < active_nr; i++) {
 -                      struct cache_entry *ce = active_cache[i];
 +                      const struct cache_entry *ce = active_cache[i];
                        struct stat st;
                        int err;
                        if ((dir->flags & DIR_SHOW_IGNORED) &&
@@@ -278,7 -273,7 +280,7 @@@ static void prune_cache(const char *pre
        last = active_nr;
        while (last > first) {
                int next = (last + first) >> 1;
 -              struct cache_entry *ce = active_cache[next];
 +              const struct cache_entry *ce = active_cache[next];
                if (!strncmp(ce->name, prefix, max_prefix_len)) {
                        first = next+1;
                        continue;
        active_nr = last;
  }
  
 -static void strip_trailing_slash_from_submodules(void)
 -{
 -      const char **p;
 -
 -      for (p = pathspec; *p != NULL; p++) {
 -              int len = strlen(*p), pos;
 -
 -              if (len < 1 || (*p)[len - 1] != '/')
 -                      continue;
 -              pos = cache_name_pos(*p, len - 1);
 -              if (pos >= 0 && S_ISGITLINK(active_cache[pos]->ce_mode))
 -                      *p = xstrndup(*p, len - 1);
 -      }
 -}
 -
  /*
   * Read the tree specified with --with-tree option
   * (typically, HEAD) into stage #1 and then
@@@ -319,12 -329,13 +321,12 @@@ void overlay_tree_on_cache(const char *
        }
  
        if (prefix) {
 -              static const char *(matchbuf[2]);
 -              matchbuf[0] = prefix;
 -              matchbuf[1] = NULL;
 -              init_pathspec(&pathspec, matchbuf);
 -              pathspec.items[0].nowildcard_len = pathspec.items[0].len;
 +              static const char *(matchbuf[1]);
 +              matchbuf[0] = NULL;
 +              parse_pathspec(&pathspec, PATHSPEC_ALL_MAGIC,
 +                             PATHSPEC_PREFER_CWD, prefix, matchbuf);
        } else
 -              init_pathspec(&pathspec, NULL);
 +              memset(&pathspec, 0, sizeof(pathspec));
        if (read_tree(tree, 1, &pathspec))
                die("unable to read tree entries %s", tree_name);
  
        }
  }
  
 -int report_path_error(const char *ps_matched, const char **pathspec, const char *prefix)
 +int report_path_error(const char *ps_matched,
 +                    const struct pathspec *pathspec,
 +                    const char *prefix)
  {
        /*
         * Make sure all pathspec matched; otherwise it is an error.
         */
        struct strbuf sb = STRBUF_INIT;
 -      const char *name;
        int num, errors = 0;
 -      for (num = 0; pathspec[num]; num++) {
 +      for (num = 0; num < pathspec->nr; num++) {
                int other, found_dup;
  
                if (ps_matched[num])
                /*
                 * The caller might have fed identical pathspec
                 * twice.  Do not barf on such a mistake.
 +               * FIXME: parse_pathspec should have eliminated
 +               * duplicate pathspec.
                 */
                for (found_dup = other = 0;
 -                   !found_dup && pathspec[other];
 +                   !found_dup && other < pathspec->nr;
                     other++) {
                        if (other == num || !ps_matched[other])
                                continue;
 -                      if (!strcmp(pathspec[other], pathspec[num]))
 +                      if (!strcmp(pathspec->items[other].original,
 +                                  pathspec->items[num].original))
                                /*
                                 * Ok, we have a match already.
                                 */
                if (found_dup)
                        continue;
  
 -              name = quote_path_relative(pathspec[num], -1, &sb, prefix);
                error("pathspec '%s' did not match any file(s) known to git.",
 -                    name);
 +                    pathspec->items[num].original);
                errors++;
        }
        strbuf_release(&sb);
@@@ -449,24 -457,24 +451,24 @@@ int cmd_ls_files(int argc, const char *
                { OPTION_CALLBACK, 'z', NULL, NULL, NULL,
                        N_("paths are separated with NUL character"),
                        PARSE_OPT_NOARG, option_parse_z },
 -              OPT_BOOLEAN('t', NULL, &show_tag,
 +              OPT_BOOL('t', NULL, &show_tag,
                        N_("identify the file status with tags")),
 -              OPT_BOOLEAN('v', NULL, &show_valid_bit,
 +              OPT_BOOL('v', NULL, &show_valid_bit,
                        N_("use lowercase letters for 'assume unchanged' files")),
 -              OPT_BOOLEAN('c', "cached", &show_cached,
 +              OPT_BOOL('c', "cached", &show_cached,
                        N_("show cached files in the output (default)")),
 -              OPT_BOOLEAN('d', "deleted", &show_deleted,
 +              OPT_BOOL('d', "deleted", &show_deleted,
                        N_("show deleted files in the output")),
 -              OPT_BOOLEAN('m', "modified", &show_modified,
 +              OPT_BOOL('m', "modified", &show_modified,
                        N_("show modified files in the output")),
 -              OPT_BOOLEAN('o', "others", &show_others,
 +              OPT_BOOL('o', "others", &show_others,
                        N_("show other files in the output")),
                OPT_BIT('i', "ignored", &dir.flags,
                        N_("show ignored files in the output"),
                        DIR_SHOW_IGNORED),
 -              OPT_BOOLEAN('s', "stage", &show_stage,
 +              OPT_BOOL('s', "stage", &show_stage,
                        N_("show staged contents' object name in the output")),
 -              OPT_BOOLEAN('k', "killed", &show_killed,
 +              OPT_BOOL('k', "killed", &show_killed,
                        N_("show files on the filesystem that need to be removed")),
                OPT_BIT(0, "directory", &dir.flags,
                        N_("show 'other' directories' name only"),
                OPT_NEGBIT(0, "empty-directory", &dir.flags,
                        N_("don't show empty directories"),
                        DIR_HIDE_EMPTY_DIRECTORIES),
 -              OPT_BOOLEAN('u', "unmerged", &show_unmerged,
 +              OPT_BOOL('u', "unmerged", &show_unmerged,
                        N_("show unmerged files in the output")),
 -              OPT_BOOLEAN(0, "resolve-undo", &show_resolve_undo,
 +              OPT_BOOL(0, "resolve-undo", &show_resolve_undo,
                            N_("show resolve-undo information")),
                { OPTION_CALLBACK, 'x', "exclude", &exclude_list, N_("pattern"),
                        N_("skip files matching pattern"),
                { OPTION_SET_INT, 0, "full-name", &prefix_len, NULL,
                        N_("make the output relative to the project top directory"),
                        PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL },
 -              OPT_BOOLEAN(0, "error-unmatch", &error_unmatch,
 +              OPT_BOOL(0, "error-unmatch", &error_unmatch,
                        N_("if any <file> is not in the index, treat this as an error")),
                OPT_STRING(0, "with-tree", &with_tree, N_("tree-ish"),
                        N_("pretend that paths removed since <tree-ish> are still present")),
                OPT__ABBREV(&abbrev),
 -              OPT_BOOLEAN(0, "debug", &debug_mode, N_("show debugging data")),
 +              OPT_BOOL(0, "debug", &debug_mode, N_("show debugging data")),
                OPT_END()
        };
  
        if (require_work_tree && !is_inside_work_tree())
                setup_work_tree();
  
 -      pathspec = get_pathspec(prefix, argv);
 -
 -      /* be nice with submodule paths ending in a slash */
 -      if (pathspec)
 -              strip_trailing_slash_from_submodules();
 +      parse_pathspec(&pathspec, 0,
 +                     PATHSPEC_PREFER_CWD |
 +                     PATHSPEC_STRIP_SUBMODULE_SLASH_CHEAP,
 +                     prefix, argv);
  
        /* Find common prefix for all pathspec's */
 -      max_prefix = common_prefix(pathspec);
 +      max_prefix = common_prefix(&pathspec);
        max_prefix_len = max_prefix ? strlen(max_prefix) : 0;
  
        /* Treat unmatching pathspec elements as errors */
 -      if (pathspec && error_unmatch) {
 -              int num;
 -              for (num = 0; pathspec[num]; num++)
 -                      ;
 -              ps_matched = xcalloc(1, num);
 -      }
 +      if (pathspec.nr && error_unmatch)
 +              ps_matched = xcalloc(1, pathspec.nr);
  
        if ((dir.flags & DIR_SHOW_IGNORED) && !exc_given)
                die("ls-files --ignored needs some exclude pattern");
  
        /* With no flags, we default to showing the cached files */
 -      if (!(show_stage | show_deleted | show_others | show_unmerged |
 -            show_killed | show_modified | show_resolve_undo))
 +      if (!(show_stage || show_deleted || show_others || show_unmerged ||
 +            show_killed || show_modified || show_resolve_undo))
                show_cached = 1;
  
        if (max_prefix)
  
        if (ps_matched) {
                int bad;
 -              bad = report_path_error(ps_matched, pathspec, prefix);
 +              bad = report_path_error(ps_matched, &pathspec, prefix);
                if (bad)
                        fprintf(stderr, "Did you forget to 'git add'?\n");
  
diff --combined dir.c
index 1128110a441538215e5bc046183b11b6b49f129e,1000dc236889a340aa1613549fe73fe7f6b2a648..b439ff0e63481bebb4039901b029bad978b46929
--- 1/dir.c
--- 2/dir.c
+++ b/dir.c
@@@ -11,7 -11,6 +11,7 @@@
  #include "dir.h"
  #include "refs.h"
  #include "wildmatch.h"
 +#include "pathspec.h"
  
  struct path_simplify {
        int len;
@@@ -52,32 -51,26 +52,32 @@@ int fnmatch_icase(const char *pattern, 
        return fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));
  }
  
 -inline int git_fnmatch(const char *pattern, const char *string,
 -                     int flags, int prefix)
 +inline int git_fnmatch(const struct pathspec_item *item,
 +                     const char *pattern, const char *string,
 +                     int prefix)
  {
 -      int fnm_flags = 0;
 -      if (flags & GFNM_PATHNAME)
 -              fnm_flags |= FNM_PATHNAME;
        if (prefix > 0) {
 -              if (strncmp(pattern, string, prefix))
 +              if (ps_strncmp(item, pattern, string, prefix))
                        return FNM_NOMATCH;
                pattern += prefix;
                string += prefix;
        }
 -      if (flags & GFNM_ONESTAR) {
 +      if (item->flags & PATHSPEC_ONESTAR) {
                int pattern_len = strlen(++pattern);
                int string_len = strlen(string);
                return string_len < pattern_len ||
 -                     strcmp(pattern,
 -                            string + string_len - pattern_len);
 +                      ps_strcmp(item, pattern,
 +                                string + string_len - pattern_len);
        }
 -      return fnmatch(pattern, string, fnm_flags);
 +      if (item->magic & PATHSPEC_GLOB)
 +              return wildmatch(pattern, string,
 +                               WM_PATHNAME |
 +                               (item->magic & PATHSPEC_ICASE ? WM_CASEFOLD : 0),
 +                               NULL);
 +      else
 +              /* wildmatch has not learned no FNM_PATHNAME mode yet */
 +              return fnmatch(pattern, string,
 +                             item->magic & PATHSPEC_ICASE ? FNM_CASEFOLD : 0);
  }
  
  static int fnmatch_icase_mem(const char *pattern, int patternlen,
        return match_status;
  }
  
 -static size_t common_prefix_len(const char **pathspec)
 +static size_t common_prefix_len(const struct pathspec *pathspec)
  {
 -      const char *n, *first;
 +      int n;
        size_t max = 0;
 -      int literal = limit_pathspec_to_literal();
  
 -      if (!pathspec)
 -              return max;
 -
 -      first = *pathspec;
 -      while ((n = *pathspec++)) {
 -              size_t i, len = 0;
 -              for (i = 0; first == n || i < max; i++) {
 -                      char c = n[i];
 -                      if (!c || c != first[i] || (!literal && is_glob_special(c)))
 +      /*
 +       * ":(icase)path" is treated as a pathspec full of
 +       * wildcard. In other words, only prefix is considered common
 +       * prefix. If the pathspec is abc/foo abc/bar, running in
 +       * subdir xyz, the common prefix is still xyz, not xuz/abc as
 +       * in non-:(icase).
 +       */
 +      GUARD_PATHSPEC(pathspec,
 +                     PATHSPEC_FROMTOP |
 +                     PATHSPEC_MAXDEPTH |
 +                     PATHSPEC_LITERAL |
 +                     PATHSPEC_GLOB |
 +                     PATHSPEC_ICASE);
 +
 +      for (n = 0; n < pathspec->nr; n++) {
 +              size_t i = 0, len = 0, item_len;
 +              if (pathspec->items[n].magic & PATHSPEC_ICASE)
 +                      item_len = pathspec->items[n].prefix;
 +              else
 +                      item_len = pathspec->items[n].nowildcard_len;
 +              while (i < item_len && (n == 0 || i < max)) {
 +                      char c = pathspec->items[n].match[i];
 +                      if (c != pathspec->items[0].match[i])
                                break;
                        if (c == '/')
                                len = i + 1;
 +                      i++;
                }
 -              if (first == n || len < max) {
 +              if (n == 0 || len < max) {
                        max = len;
                        if (!max)
                                break;
   * Returns a copy of the longest leading path common among all
   * pathspecs.
   */
 -char *common_prefix(const char **pathspec)
 +char *common_prefix(const struct pathspec *pathspec)
  {
        unsigned long len = common_prefix_len(pathspec);
  
 -      return len ? xmemdupz(*pathspec, len) : NULL;
 +      return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
  }
  
 -int fill_directory(struct dir_struct *dir, const char **pathspec)
 +int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
  {
        size_t len;
  
        len = common_prefix_len(pathspec);
  
        /* Read the directory and prune it */
 -      read_directory(dir, pathspec ? *pathspec : "", len, pathspec);
 +      read_directory(dir, pathspec->nr ? pathspec->_raw[0] : "", len, pathspec);
        return len;
  }
  
@@@ -192,6 -171,113 +192,6 @@@ int within_depth(const char *name, int 
        return 1;
  }
  
 -/*
 - * Does 'match' match the given name?
 - * A match is found if
 - *
 - * (1) the 'match' string is leading directory of 'name', or
 - * (2) the 'match' string is a wildcard and matches 'name', or
 - * (3) the 'match' string is exactly the same as 'name'.
 - *
 - * and the return value tells which case it was.
 - *
 - * It returns 0 when there is no match.
 - */
 -static int match_one(const char *match, const char *name, int namelen)
 -{
 -      int matchlen;
 -      int literal = limit_pathspec_to_literal();
 -
 -      /* If the match was just the prefix, we matched */
 -      if (!*match)
 -              return MATCHED_RECURSIVELY;
 -
 -      if (ignore_case) {
 -              for (;;) {
 -                      unsigned char c1 = tolower(*match);
 -                      unsigned char c2 = tolower(*name);
 -                      if (c1 == '\0' || (!literal && is_glob_special(c1)))
 -                              break;
 -                      if (c1 != c2)
 -                              return 0;
 -                      match++;
 -                      name++;
 -                      namelen--;
 -              }
 -      } else {
 -              for (;;) {
 -                      unsigned char c1 = *match;
 -                      unsigned char c2 = *name;
 -                      if (c1 == '\0' || (!literal && is_glob_special(c1)))
 -                              break;
 -                      if (c1 != c2)
 -                              return 0;
 -                      match++;
 -                      name++;
 -                      namelen--;
 -              }
 -      }
 -
 -      /*
 -       * If we don't match the matchstring exactly,
 -       * we need to match by fnmatch
 -       */
 -      matchlen = strlen(match);
 -      if (strncmp_icase(match, name, matchlen)) {
 -              if (literal)
 -                      return 0;
 -              return !fnmatch_icase(match, name, 0) ? MATCHED_FNMATCH : 0;
 -      }
 -
 -      if (namelen == matchlen)
 -              return MATCHED_EXACTLY;
 -      if (match[matchlen-1] == '/' || name[matchlen] == '/')
 -              return MATCHED_RECURSIVELY;
 -      return 0;
 -}
 -
 -/*
 - * Given a name and a list of pathspecs, returns the nature of the
 - * closest (i.e. most specific) match of the name to any of the
 - * pathspecs.
 - *
 - * The caller typically calls this multiple times with the same
 - * pathspec and seen[] array but with different name/namelen
 - * (e.g. entries from the index) and is interested in seeing if and
 - * how each pathspec matches all the names it calls this function
 - * with.  A mark is left in the seen[] array for each pathspec element
 - * indicating the closest type of match that element achieved, so if
 - * seen[n] remains zero after multiple invocations, that means the nth
 - * pathspec did not match any names, which could indicate that the
 - * user mistyped the nth pathspec.
 - */
 -int match_pathspec(const char **pathspec, const char *name, int namelen,
 -              int prefix, char *seen)
 -{
 -      int i, retval = 0;
 -
 -      if (!pathspec)
 -              return 1;
 -
 -      name += prefix;
 -      namelen -= prefix;
 -
 -      for (i = 0; pathspec[i] != NULL; i++) {
 -              int how;
 -              const char *match = pathspec[i] + prefix;
 -              if (seen && seen[i] == MATCHED_EXACTLY)
 -                      continue;
 -              how = match_one(match, name, namelen);
 -              if (how) {
 -                      if (retval < how)
 -                              retval = how;
 -                      if (seen && seen[i] < how)
 -                              seen[i] = how;
 -              }
 -      }
 -      return retval;
 -}
 -
  /*
   * Does 'match' match the given name?
   * A match is found if
@@@ -211,44 -297,11 +211,44 @@@ static int match_pathspec_item(const st
        const char *match = item->match + prefix;
        int matchlen = item->len - prefix;
  
 +      /*
 +       * The normal call pattern is:
 +       * 1. prefix = common_prefix_len(ps);
 +       * 2. prune something, or fill_directory
 +       * 3. match_pathspec_depth()
 +       *
 +       * 'prefix' at #1 may be shorter than the command's prefix and
 +       * it's ok for #2 to match extra files. Those extras will be
 +       * trimmed at #3.
 +       *
 +       * Suppose the pathspec is 'foo' and '../bar' running from
 +       * subdir 'xyz'. The common prefix at #1 will be empty, thanks
 +       * to "../". We may have xyz/foo _and_ XYZ/foo after #2. The
 +       * user does not want XYZ/foo, only the "foo" part should be
 +       * case-insensitive. We need to filter out XYZ/foo here. In
 +       * other words, we do not trust the caller on comparing the
 +       * prefix part when :(icase) is involved. We do exact
 +       * comparison ourselves.
 +       *
 +       * Normally the caller (common_prefix_len() in fact) does
 +       * _exact_ matching on name[-prefix+1..-1] and we do not need
 +       * to check that part. Be defensive and check it anyway, in
 +       * case common_prefix_len is changed, or a new caller is
 +       * introduced that does not use common_prefix_len.
 +       *
 +       * If the penalty turns out too high when prefix is really
 +       * long, maybe change it to
 +       * strncmp(match, name, item->prefix - prefix)
 +       */
 +      if (item->prefix && (item->magic & PATHSPEC_ICASE) &&
 +          strncmp(item->match, name - prefix, item->prefix))
 +              return 0;
 +
        /* If the match was just the prefix, we matched */
        if (!*match)
                return MATCHED_RECURSIVELY;
  
 -      if (matchlen <= namelen && !strncmp(match, name, matchlen)) {
 +      if (matchlen <= namelen && !ps_strncmp(item, match, name, matchlen)) {
                if (matchlen == namelen)
                        return MATCHED_EXACTLY;
  
        }
  
        if (item->nowildcard_len < item->len &&
 -          !git_fnmatch(match, name,
 -                       item->flags & PATHSPEC_ONESTAR ? GFNM_ONESTAR : 0,
 +          !git_fnmatch(item, match, name,
                         item->nowildcard_len - prefix))
                return MATCHED_FNMATCH;
  
@@@ -285,17 -339,8 +285,17 @@@ int match_pathspec_depth(const struct p
  {
        int i, retval = 0;
  
 +      GUARD_PATHSPEC(ps,
 +                     PATHSPEC_FROMTOP |
 +                     PATHSPEC_MAXDEPTH |
 +                     PATHSPEC_LITERAL |
 +                     PATHSPEC_GLOB |
 +                     PATHSPEC_ICASE);
 +
        if (!ps->nr) {
 -              if (!ps->recursive || ps->max_depth == -1)
 +              if (!ps->recursive ||
 +                  !(ps->magic & PATHSPEC_MAXDEPTH) ||
 +                  ps->max_depth == -1)
                        return MATCHED_RECURSIVELY;
  
                if (within_depth(name, namelen, 0, ps->max_depth))
                if (seen && seen[i] == MATCHED_EXACTLY)
                        continue;
                how = match_pathspec_item(ps->items+i, prefix, name, namelen);
 -              if (ps->recursive && ps->max_depth != -1 &&
 +              if (ps->recursive &&
 +                  (ps->magic & PATHSPEC_MAXDEPTH) &&
 +                  ps->max_depth != -1 &&
                    how && how != MATCHED_FNMATCH) {
                        int len = ps->items[i].len;
                        if (name[len] == '/')
  /*
   * Return the length of the "simple" part of a path match limiter.
   */
 -static int simple_length(const char *match)
 +int simple_length(const char *match)
  {
        int len = -1;
  
        }
  }
  
 -static int no_wildcard(const char *string)
 +int no_wildcard(const char *string)
  {
        return string[simple_length(string)] == '\0';
  }
@@@ -429,15 -472,14 +429,14 @@@ static void *read_skip_worktree_file_fr
        unsigned long sz;
        enum object_type type;
        void *data;
-       struct index_state *istate = &the_index;
  
        len = strlen(path);
-       pos = index_name_pos(istate, path, len);
+       pos = cache_name_pos(path, len);
        if (pos < 0)
                return NULL;
-       if (!ce_skip_worktree(istate->cache[pos]))
+       if (!ce_skip_worktree(active_cache[pos]))
                return NULL;
-       data = read_sha1_file(istate->cache[pos]->sha1, &type, &sz);
+       data = read_sha1_file(active_cache[pos]->sha1, &type, &sz);
        if (!data || type != OBJ_BLOB) {
                free(data);
                return NULL;
@@@ -778,9 -820,6 +777,9 @@@ static void prep_exclude(struct dir_str
                                dir->basebuf, stk->baselen - 1,
                                dir->basebuf + current, &dt);
                        dir->basebuf[stk->baselen - 1] = '/';
 +                      if (dir->exclude &&
 +                          dir->exclude->flags & EXC_FLAG_NEGATIVE)
 +                              dir->exclude = NULL;
                        if (dir->exclude) {
                                dir->basebuf[stk->baselen] = 0;
                                dir->exclude_stack = stk;
@@@ -884,13 -923,13 +883,13 @@@ enum exist_status 
  };
  
  /*
-  * Do not use the alphabetically stored index to look up
+  * Do not use the alphabetically sorted index to look up
   * the directory name; instead, use the case insensitive
   * name hash.
   */
  static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
  {
-       const struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);
 -      struct cache_entry *ce = cache_name_exists(dirname, len + 1, ignore_case);
++      const struct cache_entry *ce = cache_name_exists(dirname, len + 1, ignore_case);
        unsigned char endchar;
  
        if (!ce)
@@@ -934,7 -973,7 +933,7 @@@ static enum exist_status directory_exis
        if (pos < 0)
                pos = -pos-1;
        while (pos < active_nr) {
 -              struct cache_entry *ce = active_cache[pos++];
 +              const struct cache_entry *ce = active_cache[pos++];
                unsigned char endchar;
  
                if (strncmp(ce->name, dirname, len))
@@@ -993,7 -1032,9 +992,7 @@@ static enum path_treatment treat_direct
                return path_recurse;
  
        case index_gitdir:
 -              if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
 -                      return path_none;
 -              return path_untracked;
 +              return path_none;
  
        case index_nonexistent:
                if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
@@@ -1070,7 -1111,7 +1069,7 @@@ static int exclude_matches_pathspec(con
  static int get_index_dtype(const char *path, int len)
  {
        int pos;
 -      struct cache_entry *ce;
 +      const struct cache_entry *ce;
  
        ce = cache_name_exists(path, len, 0);
        if (ce) {
@@@ -1132,14 -1173,51 +1131,51 @@@ static enum path_treatment treat_one_pa
                                          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) {
+               /*
+                * NEEDSWORK: directory_exists_in_index_icase()
+                * assumes that one byte past the given path is
+                * readable and has '/', which needs to be fixed, but
+                * until then, work it around in the caller.
+                */
+               strbuf_addch(path, '/');
+               if (directory_exists_in_index(path->buf, path->len - 1) ==
+                   index_nonexistent) {
+                       strbuf_setlen(path, path->len - 1);
+                       return path_none;
+               }
+               strbuf_setlen(path, path->len - 1);
+       }
        exclude = is_excluded(dir, path->buf, &dtype);
  
        /*
@@@ -1338,25 -1416,14 +1374,25 @@@ static int treat_leading_path(struct di
        return rc;
  }
  
 -int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
 +int read_directory(struct dir_struct *dir, const char *path, int len, const struct pathspec *pathspec)
  {
        struct path_simplify *simplify;
  
 +      /*
 +       * Check out create_simplify()
 +       */
 +      if (pathspec)
 +              GUARD_PATHSPEC(pathspec,
 +                             PATHSPEC_FROMTOP |
 +                             PATHSPEC_MAXDEPTH |
 +                             PATHSPEC_LITERAL |
 +                             PATHSPEC_GLOB |
 +                             PATHSPEC_ICASE);
 +
        if (has_symlink_leading_path(path, len))
                return dir->nr;
  
 -      simplify = create_simplify(pathspec);
 +      simplify = create_simplify(pathspec ? pathspec->_raw : NULL);
        if (!len || treat_leading_path(dir, path, len, simplify))
                read_directory_recursive(dir, path, len, 0, simplify);
        free_simplify(simplify);
@@@ -1511,9 -1578,9 +1547,9 @@@ void setup_standard_excludes(struct dir
                home_config_paths(NULL, &xdg_path, "ignore");
                excludes_file = xdg_path;
        }
 -      if (!access_or_warn(path, R_OK))
 +      if (!access_or_warn(path, R_OK, 0))
                add_excludes_from_file(dir, path);
 -      if (excludes_file && !access_or_warn(excludes_file, R_OK))
 +      if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
                add_excludes_from_file(dir, excludes_file);
  }
  
@@@ -1536,6 -1603,71 +1572,6 @@@ int remove_path(const char *name
        return 0;
  }
  
 -static int pathspec_item_cmp(const void *a_, const void *b_)
 -{
 -      struct pathspec_item *a, *b;
 -
 -      a = (struct pathspec_item *)a_;
 -      b = (struct pathspec_item *)b_;
 -      return strcmp(a->match, b->match);
 -}
 -
 -int init_pathspec(struct pathspec *pathspec, const char **paths)
 -{
 -      const char **p = paths;
 -      int i;
 -
 -      memset(pathspec, 0, sizeof(*pathspec));
 -      if (!p)
 -              return 0;
 -      while (*p)
 -              p++;
 -      pathspec->raw = paths;
 -      pathspec->nr = p - paths;
 -      if (!pathspec->nr)
 -              return 0;
 -
 -      pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
 -      for (i = 0; i < pathspec->nr; i++) {
 -              struct pathspec_item *item = pathspec->items+i;
 -              const char *path = paths[i];
 -
 -              item->match = path;
 -              item->len = strlen(path);
 -              item->flags = 0;
 -              if (limit_pathspec_to_literal()) {
 -                      item->nowildcard_len = item->len;
 -              } else {
 -                      item->nowildcard_len = simple_length(path);
 -                      if (item->nowildcard_len < item->len) {
 -                              pathspec->has_wildcard = 1;
 -                              if (path[item->nowildcard_len] == '*' &&
 -                                  no_wildcard(path + item->nowildcard_len + 1))
 -                                      item->flags |= PATHSPEC_ONESTAR;
 -                      }
 -              }
 -      }
 -
 -      qsort(pathspec->items, pathspec->nr,
 -            sizeof(struct pathspec_item), pathspec_item_cmp);
 -
 -      return 0;
 -}
 -
 -void free_pathspec(struct pathspec *pathspec)
 -{
 -      free(pathspec->items);
 -      pathspec->items = NULL;
 -}
 -
 -int limit_pathspec_to_literal(void)
 -{
 -      static int flag = -1;
 -      if (flag < 0)
 -              flag = git_env_bool(GIT_LITERAL_PATHSPECS_ENVIRONMENT, 0);
 -      return flag;
 -}
 -
  /*
   * Frees memory within dir which was allocated for exclude lists and
   * the exclude_stack.  Does not free dir itself.
diff --combined dir.h
index 343ec7aa3188a904f4517241b31250a57f11eddb,4677b861f0046492b2b2026789eaa69850afcc77..9b7e4e77d8b11bab92a91a6ce3e8920e50d23f9b
--- 1/dir.h
--- 2/dir.h
+++ b/dir.h
@@@ -80,7 -80,8 +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;
  #define MATCHED_RECURSIVELY 1
  #define MATCHED_FNMATCH 2
  #define MATCHED_EXACTLY 3
 -extern char *common_prefix(const char **pathspec);
 -extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);
 +extern int simple_length(const char *match);
 +extern int no_wildcard(const char *string);
 +extern char *common_prefix(const struct pathspec *pathspec);
  extern int match_pathspec_depth(const struct pathspec *pathspec,
                                const char *name, int namelen,
                                int prefix, char *seen);
  extern int within_depth(const char *name, int namelen, int depth, int max_depth);
  
 -extern int fill_directory(struct dir_struct *dir, const char **pathspec);
 -extern int read_directory(struct dir_struct *, const char *path, int len, const char **pathspec);
 +extern int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec);
 +extern int read_directory(struct dir_struct *, const char *path, int len, const struct pathspec *pathspec);
  
  extern int is_excluded_from_list(const char *pathname, int pathlen, const char *basename,
                                 int *dtype, struct exclude_list *el);
@@@ -199,9 -199,10 +200,9 @@@ extern int fnmatch_icase(const char *pa
  /*
   * The prefix part of pattern must not contains wildcards.
   */
 -#define GFNM_PATHNAME 1               /* similar to FNM_PATHNAME */
 -#define GFNM_ONESTAR  2               /* there is only _one_ wildcard, a star */
 -
 -extern int git_fnmatch(const char *pattern, const char *string,
 -                     int flags, int prefix);
 +struct pathspec_item;
 +extern int git_fnmatch(const struct pathspec_item *item,
 +                     const char *pattern, const char *string,
 +                     int prefix);
  
  #endif
index f611d799b690457e306571adf16813b238a27dc9,ab1deae3b2e759b1cdbc22fd4c5c4bcf31f306c1..6d3b828a951e4c03b886087393269dbe4d5c5c8f
@@@ -11,8 -11,7 +11,9 @@@ This test prepares the following in th
      path1       - a symlink
      path2/file2 - a file in a directory
      path3/file3 - a file in a directory
+     pathx/ju    - a file in a directory
 +    submod1/  - a submodule
 +    submod2/  - another submodule
  
  and the following on the filesystem:
  
      path4     - a file
      path5     - a symlink
      path6/file6 - a file in a directory
+     pathx/ju/nk - a file in a directory to be killed
 +    submod1/  - a submodule (modified from the cache)
 +    submod2/  - a submodule (matches the cache)
  
 -git ls-files -k should report that existing filesystem
 -objects except path4, path5 and path6/file6 to be killed.
 +git ls-files -k should report that existing filesystem objects
 +path0/*, path1/*, path2 and path3 to be killed.
  
  Also for modification test, the cache and working tree have:
  
      path10    - a non-empty file, cache dirtied.
  
  We should report path0, path1, path2/file2, path3/file3, path7 and path8
 -modified without reporting path9 and path10.
 +modified without reporting path9 and path10.  submod1 is also modified.
  '
  . ./test-lib.sh
  
 -date >path0
 -if test_have_prereq SYMLINKS
 -then
 -      ln -s xyzzy path1
 -else
 -      date > path1
 -fi
 -mkdir path2 path3 pathx
 -date >path2/file2
 -date >path3/file3
 ->pathx/ju
 -: >path7
 -date >path8
 -: >path9
 -date >path10
 -test_expect_success \
 -    'git update-index --add to add various paths.' \
 -    "git update-index --add -- path0 path1 path?/file? pathx/ju path7 path8 path9 path10"
 -
 -rm -fr path? ;# leave path10 alone
 -date >path2
 -if test_have_prereq SYMLINKS
 -then
 -      ln -s frotz path3
 -      ln -s nitfol path5
 -else
 -      date > path3
 -      date > path5
 -fi
 -mkdir -p path0 path1 path6 pathx/ju
 -date >path0/file0
 -date >path1/file1
 -date >path6/file6
 -date >path7
 -: >path8
 -: >path9
 -touch path10
 ->pathx/ju/nk
 -
 -cat >.expected <<EOF
 -path0/file0
 -path1/file1
 -path2
 -path3
 -pathx/ju/nk
 -EOF
 -
 -test_expect_success 'git ls-files -k to show killed files (w/o icase)' '
 -    git ls-files -k >.output &&
 -    test_cmp .expected .output
 +test_expect_success 'git update-index --add to add various paths.' '
 +      date >path0 &&
 +      test_ln_s_add xyzzy path1 &&
-       mkdir path2 path3 &&
++      mkdir path2 path3 pathx &&
 +      date >path2/file2 &&
 +      date >path3/file3 &&
++      >pathx/ju &&
 +      : >path7 &&
 +      date >path8 &&
 +      : >path9 &&
 +      date >path10 &&
-       git update-index --add -- path0 path?/file? path7 path8 path9 path10 &&
++      git update-index --add -- path0 path?/file? pathx/ju path7 path8 path9 path10 &&
 +      for i in 1 2
 +      do
 +              git init submod$i &&
 +              (
 +                      cd submod$i && git commit --allow-empty -m "empty $i"
 +              ) || break
 +      done &&
 +      git update-index --add submod[12]
 +      (
 +              cd submod1 &&
 +              git commit --allow-empty -m "empty 1 (updated)"
 +      ) &&
 +      rm -fr path?    # leave path10 alone
  '
  
 -test_expect_success 'git ls-files -k to show killed files (w/ icase)' '
 -    git -c core.ignorecase=true ls-files -k >.output &&
 -    test_cmp .expected .output
 +test_expect_success 'git ls-files -k to show killed files.' '
 +      date >path2 &&
 +      if test_have_prereq SYMLINKS
 +      then
 +              ln -s frotz path3 &&
 +              ln -s nitfol path5
 +      else
 +              date >path3 &&
 +              date >path5
 +      fi &&
-       mkdir path0 path1 path6 &&
++      mkdir -p path0 path1 path6 pathx/ju &&
 +      date >path0/file0 &&
 +      date >path1/file1 &&
 +      date >path6/file6 &&
 +      date >path7 &&
 +      : >path8 &&
 +      : >path9 &&
 +      touch path10 &&
-       git ls-files -k >.output
- '
- test_expect_success 'validate git ls-files -k output.' '
-       cat >.expected <<-\EOF &&
++      >pathx/ju/nk &&
++      cat >.expected <<-\EOF
 +      path0/file0
 +      path1/file1
 +      path2
 +      path3
++      pathx/ju/nk
 +      EOF
+ '
 -test_expect_success \
 -    'git ls-files -m to show modified files.' \
 -    'git ls-files -m >.output'
 -cat >.expected <<EOF
 -path0
 -path1
 -path2/file2
 -path3/file3
 -path7
 -path8
 -pathx/ju
 -EOF
 -
 -test_expect_success \
 -    'validate git ls-files -m output.' \
 -    'test_cmp .expected .output'
++test_expect_success 'git ls-files -k output (w/o icase)' '
++      git ls-files -k >.output
++      test_cmp .expected .output
++'
++
++test_expect_success 'git ls-files -k output (w/ icase)' '
++      git -c core.ignorecase=true ls-files -k >.output
 +      test_cmp .expected .output
 +'
 +
 +test_expect_success 'git ls-files -m to show modified files.' '
 +      git ls-files -m >.output
 +'
 +
 +test_expect_success 'validate git ls-files -m output.' '
 +      cat >.expected <<-\EOF &&
 +      path0
 +      path1
 +      path2/file2
 +      path3/file3
 +      path7
 +      path8
++      pathx/ju
 +      submod1
 +      EOF
 +      test_cmp .expected .output
 +'
  
  test_done