Merge branch 'sk/gitweb-highlight-encoding' into HEAD
[git] / dir.c
1 /*
2  * This handles recursive filename detection with exclude
3  * files, index knowledge etc..
4  *
5  * See Documentation/technical/api-directory-listing.txt
6  *
7  * Copyright (C) Linus Torvalds, 2005-2006
8  *               Junio Hamano, 2005-2006
9  */
10 #include "cache.h"
11 #include "dir.h"
12 #include "refs.h"
13 #include "wildmatch.h"
14 #include "pathspec.h"
15 #include "utf8.h"
16 #include "varint.h"
17 #include "ewah/ewok.h"
18
19 struct path_simplify {
20         int len;
21         const char *path;
22 };
23
24 /*
25  * Tells read_directory_recursive how a file or directory should be treated.
26  * Values are ordered by significance, e.g. if a directory contains both
27  * excluded and untracked files, it is listed as untracked because
28  * path_untracked > path_excluded.
29  */
30 enum path_treatment {
31         path_none = 0,
32         path_recurse,
33         path_excluded,
34         path_untracked
35 };
36
37 /*
38  * Support data structure for our opendir/readdir/closedir wrappers
39  */
40 struct cached_dir {
41         DIR *fdir;
42         struct untracked_cache_dir *untracked;
43         int nr_files;
44         int nr_dirs;
45
46         struct dirent *de;
47         const char *file;
48         struct untracked_cache_dir *ucd;
49 };
50
51 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
52         const char *path, int len, struct untracked_cache_dir *untracked,
53         int check_only, const struct path_simplify *simplify);
54 static int get_dtype(struct dirent *de, const char *path, int len);
55
56 /* helper string functions with support for the ignore_case flag */
57 int strcmp_icase(const char *a, const char *b)
58 {
59         return ignore_case ? strcasecmp(a, b) : strcmp(a, b);
60 }
61
62 int strncmp_icase(const char *a, const char *b, size_t count)
63 {
64         return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);
65 }
66
67 int fnmatch_icase(const char *pattern, const char *string, int flags)
68 {
69         return wildmatch(pattern, string,
70                          flags | (ignore_case ? WM_CASEFOLD : 0),
71                          NULL);
72 }
73
74 int git_fnmatch(const struct pathspec_item *item,
75                 const char *pattern, const char *string,
76                 int prefix)
77 {
78         if (prefix > 0) {
79                 if (ps_strncmp(item, pattern, string, prefix))
80                         return WM_NOMATCH;
81                 pattern += prefix;
82                 string += prefix;
83         }
84         if (item->flags & PATHSPEC_ONESTAR) {
85                 int pattern_len = strlen(++pattern);
86                 int string_len = strlen(string);
87                 return string_len < pattern_len ||
88                         ps_strcmp(item, pattern,
89                                   string + string_len - pattern_len);
90         }
91         if (item->magic & PATHSPEC_GLOB)
92                 return wildmatch(pattern, string,
93                                  WM_PATHNAME |
94                                  (item->magic & PATHSPEC_ICASE ? WM_CASEFOLD : 0),
95                                  NULL);
96         else
97                 /* wildmatch has not learned no FNM_PATHNAME mode yet */
98                 return wildmatch(pattern, string,
99                                  item->magic & PATHSPEC_ICASE ? WM_CASEFOLD : 0,
100                                  NULL);
101 }
102
103 static int fnmatch_icase_mem(const char *pattern, int patternlen,
104                              const char *string, int stringlen,
105                              int flags)
106 {
107         int match_status;
108         struct strbuf pat_buf = STRBUF_INIT;
109         struct strbuf str_buf = STRBUF_INIT;
110         const char *use_pat = pattern;
111         const char *use_str = string;
112
113         if (pattern[patternlen]) {
114                 strbuf_add(&pat_buf, pattern, patternlen);
115                 use_pat = pat_buf.buf;
116         }
117         if (string[stringlen]) {
118                 strbuf_add(&str_buf, string, stringlen);
119                 use_str = str_buf.buf;
120         }
121
122         if (ignore_case)
123                 flags |= WM_CASEFOLD;
124         match_status = wildmatch(use_pat, use_str, flags, NULL);
125
126         strbuf_release(&pat_buf);
127         strbuf_release(&str_buf);
128
129         return match_status;
130 }
131
132 static size_t common_prefix_len(const struct pathspec *pathspec)
133 {
134         int n;
135         size_t max = 0;
136
137         /*
138          * ":(icase)path" is treated as a pathspec full of
139          * wildcard. In other words, only prefix is considered common
140          * prefix. If the pathspec is abc/foo abc/bar, running in
141          * subdir xyz, the common prefix is still xyz, not xuz/abc as
142          * in non-:(icase).
143          */
144         GUARD_PATHSPEC(pathspec,
145                        PATHSPEC_FROMTOP |
146                        PATHSPEC_MAXDEPTH |
147                        PATHSPEC_LITERAL |
148                        PATHSPEC_GLOB |
149                        PATHSPEC_ICASE |
150                        PATHSPEC_EXCLUDE);
151
152         for (n = 0; n < pathspec->nr; n++) {
153                 size_t i = 0, len = 0, item_len;
154                 if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
155                         continue;
156                 if (pathspec->items[n].magic & PATHSPEC_ICASE)
157                         item_len = pathspec->items[n].prefix;
158                 else
159                         item_len = pathspec->items[n].nowildcard_len;
160                 while (i < item_len && (n == 0 || i < max)) {
161                         char c = pathspec->items[n].match[i];
162                         if (c != pathspec->items[0].match[i])
163                                 break;
164                         if (c == '/')
165                                 len = i + 1;
166                         i++;
167                 }
168                 if (n == 0 || len < max) {
169                         max = len;
170                         if (!max)
171                                 break;
172                 }
173         }
174         return max;
175 }
176
177 /*
178  * Returns a copy of the longest leading path common among all
179  * pathspecs.
180  */
181 char *common_prefix(const struct pathspec *pathspec)
182 {
183         unsigned long len = common_prefix_len(pathspec);
184
185         return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
186 }
187
188 int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
189 {
190         size_t len;
191
192         /*
193          * Calculate common prefix for the pathspec, and
194          * use that to optimize the directory walk
195          */
196         len = common_prefix_len(pathspec);
197
198         /* Read the directory and prune it */
199         read_directory(dir, pathspec->nr ? pathspec->_raw[0] : "", len, pathspec);
200         return len;
201 }
202
203 int within_depth(const char *name, int namelen,
204                         int depth, int max_depth)
205 {
206         const char *cp = name, *cpe = name + namelen;
207
208         while (cp < cpe) {
209                 if (*cp++ != '/')
210                         continue;
211                 depth++;
212                 if (depth > max_depth)
213                         return 0;
214         }
215         return 1;
216 }
217
218 #define DO_MATCH_EXCLUDE   1
219 #define DO_MATCH_DIRECTORY 2
220
221 /*
222  * Does 'match' match the given name?
223  * A match is found if
224  *
225  * (1) the 'match' string is leading directory of 'name', or
226  * (2) the 'match' string is a wildcard and matches 'name', or
227  * (3) the 'match' string is exactly the same as 'name'.
228  *
229  * and the return value tells which case it was.
230  *
231  * It returns 0 when there is no match.
232  */
233 static int match_pathspec_item(const struct pathspec_item *item, int prefix,
234                                const char *name, int namelen, unsigned flags)
235 {
236         /* name/namelen has prefix cut off by caller */
237         const char *match = item->match + prefix;
238         int matchlen = item->len - prefix;
239
240         /*
241          * The normal call pattern is:
242          * 1. prefix = common_prefix_len(ps);
243          * 2. prune something, or fill_directory
244          * 3. match_pathspec()
245          *
246          * 'prefix' at #1 may be shorter than the command's prefix and
247          * it's ok for #2 to match extra files. Those extras will be
248          * trimmed at #3.
249          *
250          * Suppose the pathspec is 'foo' and '../bar' running from
251          * subdir 'xyz'. The common prefix at #1 will be empty, thanks
252          * to "../". We may have xyz/foo _and_ XYZ/foo after #2. The
253          * user does not want XYZ/foo, only the "foo" part should be
254          * case-insensitive. We need to filter out XYZ/foo here. In
255          * other words, we do not trust the caller on comparing the
256          * prefix part when :(icase) is involved. We do exact
257          * comparison ourselves.
258          *
259          * Normally the caller (common_prefix_len() in fact) does
260          * _exact_ matching on name[-prefix+1..-1] and we do not need
261          * to check that part. Be defensive and check it anyway, in
262          * case common_prefix_len is changed, or a new caller is
263          * introduced that does not use common_prefix_len.
264          *
265          * If the penalty turns out too high when prefix is really
266          * long, maybe change it to
267          * strncmp(match, name, item->prefix - prefix)
268          */
269         if (item->prefix && (item->magic & PATHSPEC_ICASE) &&
270             strncmp(item->match, name - prefix, item->prefix))
271                 return 0;
272
273         /* If the match was just the prefix, we matched */
274         if (!*match)
275                 return MATCHED_RECURSIVELY;
276
277         if (matchlen <= namelen && !ps_strncmp(item, match, name, matchlen)) {
278                 if (matchlen == namelen)
279                         return MATCHED_EXACTLY;
280
281                 if (match[matchlen-1] == '/' || name[matchlen] == '/')
282                         return MATCHED_RECURSIVELY;
283         } else if ((flags & DO_MATCH_DIRECTORY) &&
284                    match[matchlen - 1] == '/' &&
285                    namelen == matchlen - 1 &&
286                    !ps_strncmp(item, match, name, namelen))
287                 return MATCHED_EXACTLY;
288
289         if (item->nowildcard_len < item->len &&
290             !git_fnmatch(item, match, name,
291                          item->nowildcard_len - prefix))
292                 return MATCHED_FNMATCH;
293
294         return 0;
295 }
296
297 /*
298  * Given a name and a list of pathspecs, returns the nature of the
299  * closest (i.e. most specific) match of the name to any of the
300  * pathspecs.
301  *
302  * The caller typically calls this multiple times with the same
303  * pathspec and seen[] array but with different name/namelen
304  * (e.g. entries from the index) and is interested in seeing if and
305  * how each pathspec matches all the names it calls this function
306  * with.  A mark is left in the seen[] array for each pathspec element
307  * indicating the closest type of match that element achieved, so if
308  * seen[n] remains zero after multiple invocations, that means the nth
309  * pathspec did not match any names, which could indicate that the
310  * user mistyped the nth pathspec.
311  */
312 static int do_match_pathspec(const struct pathspec *ps,
313                              const char *name, int namelen,
314                              int prefix, char *seen,
315                              unsigned flags)
316 {
317         int i, retval = 0, exclude = flags & DO_MATCH_EXCLUDE;
318
319         GUARD_PATHSPEC(ps,
320                        PATHSPEC_FROMTOP |
321                        PATHSPEC_MAXDEPTH |
322                        PATHSPEC_LITERAL |
323                        PATHSPEC_GLOB |
324                        PATHSPEC_ICASE |
325                        PATHSPEC_EXCLUDE);
326
327         if (!ps->nr) {
328                 if (!ps->recursive ||
329                     !(ps->magic & PATHSPEC_MAXDEPTH) ||
330                     ps->max_depth == -1)
331                         return MATCHED_RECURSIVELY;
332
333                 if (within_depth(name, namelen, 0, ps->max_depth))
334                         return MATCHED_EXACTLY;
335                 else
336                         return 0;
337         }
338
339         name += prefix;
340         namelen -= prefix;
341
342         for (i = ps->nr - 1; i >= 0; i--) {
343                 int how;
344
345                 if ((!exclude &&   ps->items[i].magic & PATHSPEC_EXCLUDE) ||
346                     ( exclude && !(ps->items[i].magic & PATHSPEC_EXCLUDE)))
347                         continue;
348
349                 if (seen && seen[i] == MATCHED_EXACTLY)
350                         continue;
351                 /*
352                  * Make exclude patterns optional and never report
353                  * "pathspec ':(exclude)foo' matches no files"
354                  */
355                 if (seen && ps->items[i].magic & PATHSPEC_EXCLUDE)
356                         seen[i] = MATCHED_FNMATCH;
357                 how = match_pathspec_item(ps->items+i, prefix, name,
358                                           namelen, flags);
359                 if (ps->recursive &&
360                     (ps->magic & PATHSPEC_MAXDEPTH) &&
361                     ps->max_depth != -1 &&
362                     how && how != MATCHED_FNMATCH) {
363                         int len = ps->items[i].len;
364                         if (name[len] == '/')
365                                 len++;
366                         if (within_depth(name+len, namelen-len, 0, ps->max_depth))
367                                 how = MATCHED_EXACTLY;
368                         else
369                                 how = 0;
370                 }
371                 if (how) {
372                         if (retval < how)
373                                 retval = how;
374                         if (seen && seen[i] < how)
375                                 seen[i] = how;
376                 }
377         }
378         return retval;
379 }
380
381 int match_pathspec(const struct pathspec *ps,
382                    const char *name, int namelen,
383                    int prefix, char *seen, int is_dir)
384 {
385         int positive, negative;
386         unsigned flags = is_dir ? DO_MATCH_DIRECTORY : 0;
387         positive = do_match_pathspec(ps, name, namelen,
388                                      prefix, seen, flags);
389         if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
390                 return positive;
391         negative = do_match_pathspec(ps, name, namelen,
392                                      prefix, seen,
393                                      flags | DO_MATCH_EXCLUDE);
394         return negative ? 0 : positive;
395 }
396
397 int report_path_error(const char *ps_matched,
398                       const struct pathspec *pathspec,
399                       const char *prefix)
400 {
401         /*
402          * Make sure all pathspec matched; otherwise it is an error.
403          */
404         int num, errors = 0;
405         for (num = 0; num < pathspec->nr; num++) {
406                 int other, found_dup;
407
408                 if (ps_matched[num])
409                         continue;
410                 /*
411                  * The caller might have fed identical pathspec
412                  * twice.  Do not barf on such a mistake.
413                  * FIXME: parse_pathspec should have eliminated
414                  * duplicate pathspec.
415                  */
416                 for (found_dup = other = 0;
417                      !found_dup && other < pathspec->nr;
418                      other++) {
419                         if (other == num || !ps_matched[other])
420                                 continue;
421                         if (!strcmp(pathspec->items[other].original,
422                                     pathspec->items[num].original))
423                                 /*
424                                  * Ok, we have a match already.
425                                  */
426                                 found_dup = 1;
427                 }
428                 if (found_dup)
429                         continue;
430
431                 error("pathspec '%s' did not match any file(s) known to git.",
432                       pathspec->items[num].original);
433                 errors++;
434         }
435         return errors;
436 }
437
438 /*
439  * Return the length of the "simple" part of a path match limiter.
440  */
441 int simple_length(const char *match)
442 {
443         int len = -1;
444
445         for (;;) {
446                 unsigned char c = *match++;
447                 len++;
448                 if (c == '\0' || is_glob_special(c))
449                         return len;
450         }
451 }
452
453 int no_wildcard(const char *string)
454 {
455         return string[simple_length(string)] == '\0';
456 }
457
458 void parse_exclude_pattern(const char **pattern,
459                            int *patternlen,
460                            unsigned *flags,
461                            int *nowildcardlen)
462 {
463         const char *p = *pattern;
464         size_t i, len;
465
466         *flags = 0;
467         if (*p == '!') {
468                 *flags |= EXC_FLAG_NEGATIVE;
469                 p++;
470         }
471         len = strlen(p);
472         if (len && p[len - 1] == '/') {
473                 len--;
474                 *flags |= EXC_FLAG_MUSTBEDIR;
475         }
476         for (i = 0; i < len; i++) {
477                 if (p[i] == '/')
478                         break;
479         }
480         if (i == len)
481                 *flags |= EXC_FLAG_NODIR;
482         *nowildcardlen = simple_length(p);
483         /*
484          * we should have excluded the trailing slash from 'p' too,
485          * but that's one more allocation. Instead just make sure
486          * nowildcardlen does not exceed real patternlen
487          */
488         if (*nowildcardlen > len)
489                 *nowildcardlen = len;
490         if (*p == '*' && no_wildcard(p + 1))
491                 *flags |= EXC_FLAG_ENDSWITH;
492         *pattern = p;
493         *patternlen = len;
494 }
495
496 void add_exclude(const char *string, const char *base,
497                  int baselen, struct exclude_list *el, int srcpos)
498 {
499         struct exclude *x;
500         int patternlen;
501         unsigned flags;
502         int nowildcardlen;
503
504         parse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen);
505         if (flags & EXC_FLAG_MUSTBEDIR) {
506                 FLEXPTR_ALLOC_MEM(x, pattern, string, patternlen);
507         } else {
508                 x = xmalloc(sizeof(*x));
509                 x->pattern = string;
510         }
511         x->patternlen = patternlen;
512         x->nowildcardlen = nowildcardlen;
513         x->base = base;
514         x->baselen = baselen;
515         x->flags = flags;
516         x->srcpos = srcpos;
517         ALLOC_GROW(el->excludes, el->nr + 1, el->alloc);
518         el->excludes[el->nr++] = x;
519         x->el = el;
520 }
521
522 static void *read_skip_worktree_file_from_index(const char *path, size_t *size,
523                                                 struct sha1_stat *sha1_stat)
524 {
525         int pos, len;
526         unsigned long sz;
527         enum object_type type;
528         void *data;
529
530         len = strlen(path);
531         pos = cache_name_pos(path, len);
532         if (pos < 0)
533                 return NULL;
534         if (!ce_skip_worktree(active_cache[pos]))
535                 return NULL;
536         data = read_sha1_file(active_cache[pos]->sha1, &type, &sz);
537         if (!data || type != OBJ_BLOB) {
538                 free(data);
539                 return NULL;
540         }
541         *size = xsize_t(sz);
542         if (sha1_stat) {
543                 memset(&sha1_stat->stat, 0, sizeof(sha1_stat->stat));
544                 hashcpy(sha1_stat->sha1, active_cache[pos]->sha1);
545         }
546         return data;
547 }
548
549 /*
550  * Frees memory within el which was allocated for exclude patterns and
551  * the file buffer.  Does not free el itself.
552  */
553 void clear_exclude_list(struct exclude_list *el)
554 {
555         int i;
556
557         for (i = 0; i < el->nr; i++)
558                 free(el->excludes[i]);
559         free(el->excludes);
560         free(el->filebuf);
561
562         memset(el, 0, sizeof(*el));
563 }
564
565 static void trim_trailing_spaces(char *buf)
566 {
567         char *p, *last_space = NULL;
568
569         for (p = buf; *p; p++)
570                 switch (*p) {
571                 case ' ':
572                         if (!last_space)
573                                 last_space = p;
574                         break;
575                 case '\\':
576                         p++;
577                         if (!*p)
578                                 return;
579                         /* fallthrough */
580                 default:
581                         last_space = NULL;
582                 }
583
584         if (last_space)
585                 *last_space = '\0';
586 }
587
588 /*
589  * Given a subdirectory name and "dir" of the current directory,
590  * search the subdir in "dir" and return it, or create a new one if it
591  * does not exist in "dir".
592  *
593  * If "name" has the trailing slash, it'll be excluded in the search.
594  */
595 static struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,
596                                                     struct untracked_cache_dir *dir,
597                                                     const char *name, int len)
598 {
599         int first, last;
600         struct untracked_cache_dir *d;
601         if (!dir)
602                 return NULL;
603         if (len && name[len - 1] == '/')
604                 len--;
605         first = 0;
606         last = dir->dirs_nr;
607         while (last > first) {
608                 int cmp, next = (last + first) >> 1;
609                 d = dir->dirs[next];
610                 cmp = strncmp(name, d->name, len);
611                 if (!cmp && strlen(d->name) > len)
612                         cmp = -1;
613                 if (!cmp)
614                         return d;
615                 if (cmp < 0) {
616                         last = next;
617                         continue;
618                 }
619                 first = next+1;
620         }
621
622         uc->dir_created++;
623         FLEX_ALLOC_MEM(d, name, name, len);
624
625         ALLOC_GROW(dir->dirs, dir->dirs_nr + 1, dir->dirs_alloc);
626         memmove(dir->dirs + first + 1, dir->dirs + first,
627                 (dir->dirs_nr - first) * sizeof(*dir->dirs));
628         dir->dirs_nr++;
629         dir->dirs[first] = d;
630         return d;
631 }
632
633 static void do_invalidate_gitignore(struct untracked_cache_dir *dir)
634 {
635         int i;
636         dir->valid = 0;
637         dir->untracked_nr = 0;
638         for (i = 0; i < dir->dirs_nr; i++)
639                 do_invalidate_gitignore(dir->dirs[i]);
640 }
641
642 static void invalidate_gitignore(struct untracked_cache *uc,
643                                  struct untracked_cache_dir *dir)
644 {
645         uc->gitignore_invalidated++;
646         do_invalidate_gitignore(dir);
647 }
648
649 static void invalidate_directory(struct untracked_cache *uc,
650                                  struct untracked_cache_dir *dir)
651 {
652         int i;
653         uc->dir_invalidated++;
654         dir->valid = 0;
655         dir->untracked_nr = 0;
656         for (i = 0; i < dir->dirs_nr; i++)
657                 dir->dirs[i]->recurse = 0;
658 }
659
660 /*
661  * Given a file with name "fname", read it (either from disk, or from
662  * the index if "check_index" is non-zero), parse it and store the
663  * exclude rules in "el".
664  *
665  * If "ss" is not NULL, compute SHA-1 of the exclude file and fill
666  * stat data from disk (only valid if add_excludes returns zero). If
667  * ss_valid is non-zero, "ss" must contain good value as input.
668  */
669 static int add_excludes(const char *fname, const char *base, int baselen,
670                         struct exclude_list *el, int check_index,
671                         struct sha1_stat *sha1_stat)
672 {
673         struct stat st;
674         int fd, i, lineno = 1;
675         size_t size = 0;
676         char *buf, *entry;
677
678         fd = open(fname, O_RDONLY);
679         if (fd < 0 || fstat(fd, &st) < 0) {
680                 if (errno != ENOENT)
681                         warn_on_inaccessible(fname);
682                 if (0 <= fd)
683                         close(fd);
684                 if (!check_index ||
685                     (buf = read_skip_worktree_file_from_index(fname, &size, sha1_stat)) == NULL)
686                         return -1;
687                 if (size == 0) {
688                         free(buf);
689                         return 0;
690                 }
691                 if (buf[size-1] != '\n') {
692                         buf = xrealloc(buf, st_add(size, 1));
693                         buf[size++] = '\n';
694                 }
695         } else {
696                 size = xsize_t(st.st_size);
697                 if (size == 0) {
698                         if (sha1_stat) {
699                                 fill_stat_data(&sha1_stat->stat, &st);
700                                 hashcpy(sha1_stat->sha1, EMPTY_BLOB_SHA1_BIN);
701                                 sha1_stat->valid = 1;
702                         }
703                         close(fd);
704                         return 0;
705                 }
706                 buf = xmallocz(size);
707                 if (read_in_full(fd, buf, size) != size) {
708                         free(buf);
709                         close(fd);
710                         return -1;
711                 }
712                 buf[size++] = '\n';
713                 close(fd);
714                 if (sha1_stat) {
715                         int pos;
716                         if (sha1_stat->valid &&
717                             !match_stat_data_racy(&the_index, &sha1_stat->stat, &st))
718                                 ; /* no content change, ss->sha1 still good */
719                         else if (check_index &&
720                                  (pos = cache_name_pos(fname, strlen(fname))) >= 0 &&
721                                  !ce_stage(active_cache[pos]) &&
722                                  ce_uptodate(active_cache[pos]) &&
723                                  !would_convert_to_git(fname))
724                                 hashcpy(sha1_stat->sha1, active_cache[pos]->sha1);
725                         else
726                                 hash_sha1_file(buf, size, "blob", sha1_stat->sha1);
727                         fill_stat_data(&sha1_stat->stat, &st);
728                         sha1_stat->valid = 1;
729                 }
730         }
731
732         el->filebuf = buf;
733
734         if (skip_utf8_bom(&buf, size))
735                 size -= buf - el->filebuf;
736
737         entry = buf;
738
739         for (i = 0; i < size; i++) {
740                 if (buf[i] == '\n') {
741                         if (entry != buf + i && entry[0] != '#') {
742                                 buf[i - (i && buf[i-1] == '\r')] = 0;
743                                 trim_trailing_spaces(entry);
744                                 add_exclude(entry, base, baselen, el, lineno);
745                         }
746                         lineno++;
747                         entry = buf + i + 1;
748                 }
749         }
750         return 0;
751 }
752
753 int add_excludes_from_file_to_list(const char *fname, const char *base,
754                                    int baselen, struct exclude_list *el,
755                                    int check_index)
756 {
757         return add_excludes(fname, base, baselen, el, check_index, NULL);
758 }
759
760 struct exclude_list *add_exclude_list(struct dir_struct *dir,
761                                       int group_type, const char *src)
762 {
763         struct exclude_list *el;
764         struct exclude_list_group *group;
765
766         group = &dir->exclude_list_group[group_type];
767         ALLOC_GROW(group->el, group->nr + 1, group->alloc);
768         el = &group->el[group->nr++];
769         memset(el, 0, sizeof(*el));
770         el->src = src;
771         return el;
772 }
773
774 /*
775  * Used to set up core.excludesfile and .git/info/exclude lists.
776  */
777 static void add_excludes_from_file_1(struct dir_struct *dir, const char *fname,
778                                      struct sha1_stat *sha1_stat)
779 {
780         struct exclude_list *el;
781         /*
782          * catch setup_standard_excludes() that's called before
783          * dir->untracked is assigned. That function behaves
784          * differently when dir->untracked is non-NULL.
785          */
786         if (!dir->untracked)
787                 dir->unmanaged_exclude_files++;
788         el = add_exclude_list(dir, EXC_FILE, fname);
789         if (add_excludes(fname, "", 0, el, 0, sha1_stat) < 0)
790                 die("cannot use %s as an exclude file", fname);
791 }
792
793 void add_excludes_from_file(struct dir_struct *dir, const char *fname)
794 {
795         dir->unmanaged_exclude_files++; /* see validate_untracked_cache() */
796         add_excludes_from_file_1(dir, fname, NULL);
797 }
798
799 int match_basename(const char *basename, int basenamelen,
800                    const char *pattern, int prefix, int patternlen,
801                    unsigned flags)
802 {
803         if (prefix == patternlen) {
804                 if (patternlen == basenamelen &&
805                     !strncmp_icase(pattern, basename, basenamelen))
806                         return 1;
807         } else if (flags & EXC_FLAG_ENDSWITH) {
808                 /* "*literal" matching against "fooliteral" */
809                 if (patternlen - 1 <= basenamelen &&
810                     !strncmp_icase(pattern + 1,
811                                    basename + basenamelen - (patternlen - 1),
812                                    patternlen - 1))
813                         return 1;
814         } else {
815                 if (fnmatch_icase_mem(pattern, patternlen,
816                                       basename, basenamelen,
817                                       0) == 0)
818                         return 1;
819         }
820         return 0;
821 }
822
823 int match_pathname(const char *pathname, int pathlen,
824                    const char *base, int baselen,
825                    const char *pattern, int prefix, int patternlen,
826                    unsigned flags)
827 {
828         const char *name;
829         int namelen;
830
831         /*
832          * match with FNM_PATHNAME; the pattern has base implicitly
833          * in front of it.
834          */
835         if (*pattern == '/') {
836                 pattern++;
837                 patternlen--;
838                 prefix--;
839         }
840
841         /*
842          * baselen does not count the trailing slash. base[] may or
843          * may not end with a trailing slash though.
844          */
845         if (pathlen < baselen + 1 ||
846             (baselen && pathname[baselen] != '/') ||
847             strncmp_icase(pathname, base, baselen))
848                 return 0;
849
850         namelen = baselen ? pathlen - baselen - 1 : pathlen;
851         name = pathname + pathlen - namelen;
852
853         if (prefix) {
854                 /*
855                  * if the non-wildcard part is longer than the
856                  * remaining pathname, surely it cannot match.
857                  */
858                 if (prefix > namelen)
859                         return 0;
860
861                 if (strncmp_icase(pattern, name, prefix))
862                         return 0;
863                 pattern += prefix;
864                 patternlen -= prefix;
865                 name    += prefix;
866                 namelen -= prefix;
867
868                 /*
869                  * If the whole pattern did not have a wildcard,
870                  * then our prefix match is all we need; we
871                  * do not need to call fnmatch at all.
872                  */
873                 if (!patternlen && !namelen)
874                         return 1;
875         }
876
877         return fnmatch_icase_mem(pattern, patternlen,
878                                  name, namelen,
879                                  WM_PATHNAME) == 0;
880 }
881
882 /*
883  * Scan the given exclude list in reverse to see whether pathname
884  * should be ignored.  The first match (i.e. the last on the list), if
885  * any, determines the fate.  Returns the exclude_list element which
886  * matched, or NULL for undecided.
887  */
888 static struct exclude *last_exclude_matching_from_list(const char *pathname,
889                                                        int pathlen,
890                                                        const char *basename,
891                                                        int *dtype,
892                                                        struct exclude_list *el)
893 {
894         struct exclude *exc = NULL; /* undecided */
895         int i;
896
897         if (!el->nr)
898                 return NULL;    /* undefined */
899
900         for (i = el->nr - 1; 0 <= i; i--) {
901                 struct exclude *x = el->excludes[i];
902                 const char *exclude = x->pattern;
903                 int prefix = x->nowildcardlen;
904
905                 if (x->flags & EXC_FLAG_MUSTBEDIR) {
906                         if (*dtype == DT_UNKNOWN)
907                                 *dtype = get_dtype(NULL, pathname, pathlen);
908                         if (*dtype != DT_DIR)
909                                 continue;
910                 }
911
912                 if (x->flags & EXC_FLAG_NODIR) {
913                         if (match_basename(basename,
914                                            pathlen - (basename - pathname),
915                                            exclude, prefix, x->patternlen,
916                                            x->flags)) {
917                                 exc = x;
918                                 break;
919                         }
920                         continue;
921                 }
922
923                 assert(x->baselen == 0 || x->base[x->baselen - 1] == '/');
924                 if (match_pathname(pathname, pathlen,
925                                    x->base, x->baselen ? x->baselen - 1 : 0,
926                                    exclude, prefix, x->patternlen, x->flags)) {
927                         exc = x;
928                         break;
929                 }
930         }
931         return exc;
932 }
933
934 /*
935  * Scan the list and let the last match determine the fate.
936  * Return 1 for exclude, 0 for include and -1 for undecided.
937  */
938 int is_excluded_from_list(const char *pathname,
939                           int pathlen, const char *basename, int *dtype,
940                           struct exclude_list *el)
941 {
942         struct exclude *exclude;
943         exclude = last_exclude_matching_from_list(pathname, pathlen, basename, dtype, el);
944         if (exclude)
945                 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
946         return -1; /* undecided */
947 }
948
949 static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir,
950                 const char *pathname, int pathlen, const char *basename,
951                 int *dtype_p)
952 {
953         int i, j;
954         struct exclude_list_group *group;
955         struct exclude *exclude;
956         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
957                 group = &dir->exclude_list_group[i];
958                 for (j = group->nr - 1; j >= 0; j--) {
959                         exclude = last_exclude_matching_from_list(
960                                 pathname, pathlen, basename, dtype_p,
961                                 &group->el[j]);
962                         if (exclude)
963                                 return exclude;
964                 }
965         }
966         return NULL;
967 }
968
969 /*
970  * Loads the per-directory exclude list for the substring of base
971  * which has a char length of baselen.
972  */
973 static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
974 {
975         struct exclude_list_group *group;
976         struct exclude_list *el;
977         struct exclude_stack *stk = NULL;
978         struct untracked_cache_dir *untracked;
979         int current;
980
981         group = &dir->exclude_list_group[EXC_DIRS];
982
983         /*
984          * Pop the exclude lists from the EXCL_DIRS exclude_list_group
985          * which originate from directories not in the prefix of the
986          * path being checked.
987          */
988         while ((stk = dir->exclude_stack) != NULL) {
989                 if (stk->baselen <= baselen &&
990                     !strncmp(dir->basebuf.buf, base, stk->baselen))
991                         break;
992                 el = &group->el[dir->exclude_stack->exclude_ix];
993                 dir->exclude_stack = stk->prev;
994                 dir->exclude = NULL;
995                 free((char *)el->src); /* see strbuf_detach() below */
996                 clear_exclude_list(el);
997                 free(stk);
998                 group->nr--;
999         }
1000
1001         /* Skip traversing into sub directories if the parent is excluded */
1002         if (dir->exclude)
1003                 return;
1004
1005         /*
1006          * Lazy initialization. All call sites currently just
1007          * memset(dir, 0, sizeof(*dir)) before use. Changing all of
1008          * them seems lots of work for little benefit.
1009          */
1010         if (!dir->basebuf.buf)
1011                 strbuf_init(&dir->basebuf, PATH_MAX);
1012
1013         /* Read from the parent directories and push them down. */
1014         current = stk ? stk->baselen : -1;
1015         strbuf_setlen(&dir->basebuf, current < 0 ? 0 : current);
1016         if (dir->untracked)
1017                 untracked = stk ? stk->ucd : dir->untracked->root;
1018         else
1019                 untracked = NULL;
1020
1021         while (current < baselen) {
1022                 const char *cp;
1023                 struct sha1_stat sha1_stat;
1024
1025                 stk = xcalloc(1, sizeof(*stk));
1026                 if (current < 0) {
1027                         cp = base;
1028                         current = 0;
1029                 } else {
1030                         cp = strchr(base + current + 1, '/');
1031                         if (!cp)
1032                                 die("oops in prep_exclude");
1033                         cp++;
1034                         untracked =
1035                                 lookup_untracked(dir->untracked, untracked,
1036                                                  base + current,
1037                                                  cp - base - current);
1038                 }
1039                 stk->prev = dir->exclude_stack;
1040                 stk->baselen = cp - base;
1041                 stk->exclude_ix = group->nr;
1042                 stk->ucd = untracked;
1043                 el = add_exclude_list(dir, EXC_DIRS, NULL);
1044                 strbuf_add(&dir->basebuf, base + current, stk->baselen - current);
1045                 assert(stk->baselen == dir->basebuf.len);
1046
1047                 /* Abort if the directory is excluded */
1048                 if (stk->baselen) {
1049                         int dt = DT_DIR;
1050                         dir->basebuf.buf[stk->baselen - 1] = 0;
1051                         dir->exclude = last_exclude_matching_from_lists(dir,
1052                                 dir->basebuf.buf, stk->baselen - 1,
1053                                 dir->basebuf.buf + current, &dt);
1054                         dir->basebuf.buf[stk->baselen - 1] = '/';
1055                         if (dir->exclude &&
1056                             dir->exclude->flags & EXC_FLAG_NEGATIVE)
1057                                 dir->exclude = NULL;
1058                         if (dir->exclude) {
1059                                 dir->exclude_stack = stk;
1060                                 return;
1061                         }
1062                 }
1063
1064                 /* Try to read per-directory file */
1065                 hashclr(sha1_stat.sha1);
1066                 sha1_stat.valid = 0;
1067                 if (dir->exclude_per_dir &&
1068                     /*
1069                      * If we know that no files have been added in
1070                      * this directory (i.e. valid_cached_dir() has
1071                      * been executed and set untracked->valid) ..
1072                      */
1073                     (!untracked || !untracked->valid ||
1074                      /*
1075                       * .. and .gitignore does not exist before
1076                       * (i.e. null exclude_sha1). Then we can skip
1077                       * loading .gitignore, which would result in
1078                       * ENOENT anyway.
1079                       */
1080                      !is_null_sha1(untracked->exclude_sha1))) {
1081                         /*
1082                          * dir->basebuf gets reused by the traversal, but we
1083                          * need fname to remain unchanged to ensure the src
1084                          * member of each struct exclude correctly
1085                          * back-references its source file.  Other invocations
1086                          * of add_exclude_list provide stable strings, so we
1087                          * strbuf_detach() and free() here in the caller.
1088                          */
1089                         struct strbuf sb = STRBUF_INIT;
1090                         strbuf_addbuf(&sb, &dir->basebuf);
1091                         strbuf_addstr(&sb, dir->exclude_per_dir);
1092                         el->src = strbuf_detach(&sb, NULL);
1093                         add_excludes(el->src, el->src, stk->baselen, el, 1,
1094                                      untracked ? &sha1_stat : NULL);
1095                 }
1096                 /*
1097                  * NEEDSWORK: when untracked cache is enabled, prep_exclude()
1098                  * will first be called in valid_cached_dir() then maybe many
1099                  * times more in last_exclude_matching(). When the cache is
1100                  * used, last_exclude_matching() will not be called and
1101                  * reading .gitignore content will be a waste.
1102                  *
1103                  * So when it's called by valid_cached_dir() and we can get
1104                  * .gitignore SHA-1 from the index (i.e. .gitignore is not
1105                  * modified on work tree), we could delay reading the
1106                  * .gitignore content until we absolutely need it in
1107                  * last_exclude_matching(). Be careful about ignore rule
1108                  * order, though, if you do that.
1109                  */
1110                 if (untracked &&
1111                     hashcmp(sha1_stat.sha1, untracked->exclude_sha1)) {
1112                         invalidate_gitignore(dir->untracked, untracked);
1113                         hashcpy(untracked->exclude_sha1, sha1_stat.sha1);
1114                 }
1115                 dir->exclude_stack = stk;
1116                 current = stk->baselen;
1117         }
1118         strbuf_setlen(&dir->basebuf, baselen);
1119 }
1120
1121 /*
1122  * Loads the exclude lists for the directory containing pathname, then
1123  * scans all exclude lists to determine whether pathname is excluded.
1124  * Returns the exclude_list element which matched, or NULL for
1125  * undecided.
1126  */
1127 struct exclude *last_exclude_matching(struct dir_struct *dir,
1128                                              const char *pathname,
1129                                              int *dtype_p)
1130 {
1131         int pathlen = strlen(pathname);
1132         const char *basename = strrchr(pathname, '/');
1133         basename = (basename) ? basename+1 : pathname;
1134
1135         prep_exclude(dir, pathname, basename-pathname);
1136
1137         if (dir->exclude)
1138                 return dir->exclude;
1139
1140         return last_exclude_matching_from_lists(dir, pathname, pathlen,
1141                         basename, dtype_p);
1142 }
1143
1144 /*
1145  * Loads the exclude lists for the directory containing pathname, then
1146  * scans all exclude lists to determine whether pathname is excluded.
1147  * Returns 1 if true, otherwise 0.
1148  */
1149 int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
1150 {
1151         struct exclude *exclude =
1152                 last_exclude_matching(dir, pathname, dtype_p);
1153         if (exclude)
1154                 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
1155         return 0;
1156 }
1157
1158 static struct dir_entry *dir_entry_new(const char *pathname, int len)
1159 {
1160         struct dir_entry *ent;
1161
1162         FLEX_ALLOC_MEM(ent, name, pathname, len);
1163         ent->len = len;
1164         return ent;
1165 }
1166
1167 static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
1168 {
1169         if (cache_file_exists(pathname, len, ignore_case))
1170                 return NULL;
1171
1172         ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
1173         return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
1174 }
1175
1176 struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len)
1177 {
1178         if (!cache_name_is_other(pathname, len))
1179                 return NULL;
1180
1181         ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
1182         return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
1183 }
1184
1185 enum exist_status {
1186         index_nonexistent = 0,
1187         index_directory,
1188         index_gitdir
1189 };
1190
1191 /*
1192  * Do not use the alphabetically sorted index to look up
1193  * the directory name; instead, use the case insensitive
1194  * directory hash.
1195  */
1196 static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
1197 {
1198         struct cache_entry *ce;
1199
1200         if (cache_dir_exists(dirname, len))
1201                 return index_directory;
1202
1203         ce = cache_file_exists(dirname, len, ignore_case);
1204         if (ce && S_ISGITLINK(ce->ce_mode))
1205                 return index_gitdir;
1206
1207         return index_nonexistent;
1208 }
1209
1210 /*
1211  * The index sorts alphabetically by entry name, which
1212  * means that a gitlink sorts as '\0' at the end, while
1213  * a directory (which is defined not as an entry, but as
1214  * the files it contains) will sort with the '/' at the
1215  * end.
1216  */
1217 static enum exist_status directory_exists_in_index(const char *dirname, int len)
1218 {
1219         int pos;
1220
1221         if (ignore_case)
1222                 return directory_exists_in_index_icase(dirname, len);
1223
1224         pos = cache_name_pos(dirname, len);
1225         if (pos < 0)
1226                 pos = -pos-1;
1227         while (pos < active_nr) {
1228                 const struct cache_entry *ce = active_cache[pos++];
1229                 unsigned char endchar;
1230
1231                 if (strncmp(ce->name, dirname, len))
1232                         break;
1233                 endchar = ce->name[len];
1234                 if (endchar > '/')
1235                         break;
1236                 if (endchar == '/')
1237                         return index_directory;
1238                 if (!endchar && S_ISGITLINK(ce->ce_mode))
1239                         return index_gitdir;
1240         }
1241         return index_nonexistent;
1242 }
1243
1244 /*
1245  * When we find a directory when traversing the filesystem, we
1246  * have three distinct cases:
1247  *
1248  *  - ignore it
1249  *  - see it as a directory
1250  *  - recurse into it
1251  *
1252  * and which one we choose depends on a combination of existing
1253  * git index contents and the flags passed into the directory
1254  * traversal routine.
1255  *
1256  * Case 1: If we *already* have entries in the index under that
1257  * directory name, we always recurse into the directory to see
1258  * all the files.
1259  *
1260  * Case 2: If we *already* have that directory name as a gitlink,
1261  * we always continue to see it as a gitlink, regardless of whether
1262  * there is an actual git directory there or not (it might not
1263  * be checked out as a subproject!)
1264  *
1265  * Case 3: if we didn't have it in the index previously, we
1266  * have a few sub-cases:
1267  *
1268  *  (a) if "show_other_directories" is true, we show it as
1269  *      just a directory, unless "hide_empty_directories" is
1270  *      also true, in which case we need to check if it contains any
1271  *      untracked and / or ignored files.
1272  *  (b) if it looks like a git directory, and we don't have
1273  *      'no_gitlinks' set we treat it as a gitlink, and show it
1274  *      as a directory.
1275  *  (c) otherwise, we recurse into it.
1276  */
1277 static enum path_treatment treat_directory(struct dir_struct *dir,
1278         struct untracked_cache_dir *untracked,
1279         const char *dirname, int len, int baselen, int exclude,
1280         const struct path_simplify *simplify)
1281 {
1282         /* The "len-1" is to strip the final '/' */
1283         switch (directory_exists_in_index(dirname, len-1)) {
1284         case index_directory:
1285                 return path_recurse;
1286
1287         case index_gitdir:
1288                 return path_none;
1289
1290         case index_nonexistent:
1291                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1292                         break;
1293                 if (!(dir->flags & DIR_NO_GITLINKS)) {
1294                         unsigned char sha1[20];
1295                         if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)
1296                                 return path_untracked;
1297                 }
1298                 return path_recurse;
1299         }
1300
1301         /* This is the "show_other_directories" case */
1302
1303         if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1304                 return exclude ? path_excluded : path_untracked;
1305
1306         untracked = lookup_untracked(dir->untracked, untracked,
1307                                      dirname + baselen, len - baselen);
1308         return read_directory_recursive(dir, dirname, len,
1309                                         untracked, 1, simplify);
1310 }
1311
1312 /*
1313  * This is an inexact early pruning of any recursive directory
1314  * reading - if the path cannot possibly be in the pathspec,
1315  * return true, and we'll skip it early.
1316  */
1317 static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)
1318 {
1319         if (simplify) {
1320                 for (;;) {
1321                         const char *match = simplify->path;
1322                         int len = simplify->len;
1323
1324                         if (!match)
1325                                 break;
1326                         if (len > pathlen)
1327                                 len = pathlen;
1328                         if (!memcmp(path, match, len))
1329                                 return 0;
1330                         simplify++;
1331                 }
1332                 return 1;
1333         }
1334         return 0;
1335 }
1336
1337 /*
1338  * This function tells us whether an excluded path matches a
1339  * list of "interesting" pathspecs. That is, whether a path matched
1340  * by any of the pathspecs could possibly be ignored by excluding
1341  * the specified path. This can happen if:
1342  *
1343  *   1. the path is mentioned explicitly in the pathspec
1344  *
1345  *   2. the path is a directory prefix of some element in the
1346  *      pathspec
1347  */
1348 static int exclude_matches_pathspec(const char *path, int len,
1349                 const struct path_simplify *simplify)
1350 {
1351         if (simplify) {
1352                 for (; simplify->path; simplify++) {
1353                         if (len == simplify->len
1354                             && !memcmp(path, simplify->path, len))
1355                                 return 1;
1356                         if (len < simplify->len
1357                             && simplify->path[len] == '/'
1358                             && !memcmp(path, simplify->path, len))
1359                                 return 1;
1360                 }
1361         }
1362         return 0;
1363 }
1364
1365 static int get_index_dtype(const char *path, int len)
1366 {
1367         int pos;
1368         const struct cache_entry *ce;
1369
1370         ce = cache_file_exists(path, len, 0);
1371         if (ce) {
1372                 if (!ce_uptodate(ce))
1373                         return DT_UNKNOWN;
1374                 if (S_ISGITLINK(ce->ce_mode))
1375                         return DT_DIR;
1376                 /*
1377                  * Nobody actually cares about the
1378                  * difference between DT_LNK and DT_REG
1379                  */
1380                 return DT_REG;
1381         }
1382
1383         /* Try to look it up as a directory */
1384         pos = cache_name_pos(path, len);
1385         if (pos >= 0)
1386                 return DT_UNKNOWN;
1387         pos = -pos-1;
1388         while (pos < active_nr) {
1389                 ce = active_cache[pos++];
1390                 if (strncmp(ce->name, path, len))
1391                         break;
1392                 if (ce->name[len] > '/')
1393                         break;
1394                 if (ce->name[len] < '/')
1395                         continue;
1396                 if (!ce_uptodate(ce))
1397                         break;  /* continue? */
1398                 return DT_DIR;
1399         }
1400         return DT_UNKNOWN;
1401 }
1402
1403 static int get_dtype(struct dirent *de, const char *path, int len)
1404 {
1405         int dtype = de ? DTYPE(de) : DT_UNKNOWN;
1406         struct stat st;
1407
1408         if (dtype != DT_UNKNOWN)
1409                 return dtype;
1410         dtype = get_index_dtype(path, len);
1411         if (dtype != DT_UNKNOWN)
1412                 return dtype;
1413         if (lstat(path, &st))
1414                 return dtype;
1415         if (S_ISREG(st.st_mode))
1416                 return DT_REG;
1417         if (S_ISDIR(st.st_mode))
1418                 return DT_DIR;
1419         if (S_ISLNK(st.st_mode))
1420                 return DT_LNK;
1421         return dtype;
1422 }
1423
1424 static enum path_treatment treat_one_path(struct dir_struct *dir,
1425                                           struct untracked_cache_dir *untracked,
1426                                           struct strbuf *path,
1427                                           int baselen,
1428                                           const struct path_simplify *simplify,
1429                                           int dtype, struct dirent *de)
1430 {
1431         int exclude;
1432         int has_path_in_index = !!cache_file_exists(path->buf, path->len, ignore_case);
1433
1434         if (dtype == DT_UNKNOWN)
1435                 dtype = get_dtype(de, path->buf, path->len);
1436
1437         /* Always exclude indexed files */
1438         if (dtype != DT_DIR && has_path_in_index)
1439                 return path_none;
1440
1441         /*
1442          * When we are looking at a directory P in the working tree,
1443          * there are three cases:
1444          *
1445          * (1) P exists in the index.  Everything inside the directory P in
1446          * the working tree needs to go when P is checked out from the
1447          * index.
1448          *
1449          * (2) P does not exist in the index, but there is P/Q in the index.
1450          * We know P will stay a directory when we check out the contents
1451          * of the index, but we do not know yet if there is a directory
1452          * P/Q in the working tree to be killed, so we need to recurse.
1453          *
1454          * (3) P does not exist in the index, and there is no P/Q in the index
1455          * to require P to be a directory, either.  Only in this case, we
1456          * know that everything inside P will not be killed without
1457          * recursing.
1458          */
1459         if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
1460             (dtype == DT_DIR) &&
1461             !has_path_in_index &&
1462             (directory_exists_in_index(path->buf, path->len) == index_nonexistent))
1463                 return path_none;
1464
1465         exclude = is_excluded(dir, path->buf, &dtype);
1466
1467         /*
1468          * Excluded? If we don't explicitly want to show
1469          * ignored files, ignore it
1470          */
1471         if (exclude && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
1472                 return path_excluded;
1473
1474         switch (dtype) {
1475         default:
1476                 return path_none;
1477         case DT_DIR:
1478                 strbuf_addch(path, '/');
1479                 return treat_directory(dir, untracked, path->buf, path->len,
1480                                        baselen, exclude, simplify);
1481         case DT_REG:
1482         case DT_LNK:
1483                 return exclude ? path_excluded : path_untracked;
1484         }
1485 }
1486
1487 static enum path_treatment treat_path_fast(struct dir_struct *dir,
1488                                            struct untracked_cache_dir *untracked,
1489                                            struct cached_dir *cdir,
1490                                            struct strbuf *path,
1491                                            int baselen,
1492                                            const struct path_simplify *simplify)
1493 {
1494         strbuf_setlen(path, baselen);
1495         if (!cdir->ucd) {
1496                 strbuf_addstr(path, cdir->file);
1497                 return path_untracked;
1498         }
1499         strbuf_addstr(path, cdir->ucd->name);
1500         /* treat_one_path() does this before it calls treat_directory() */
1501         strbuf_complete(path, '/');
1502         if (cdir->ucd->check_only)
1503                 /*
1504                  * check_only is set as a result of treat_directory() getting
1505                  * to its bottom. Verify again the same set of directories
1506                  * with check_only set.
1507                  */
1508                 return read_directory_recursive(dir, path->buf, path->len,
1509                                                 cdir->ucd, 1, simplify);
1510         /*
1511          * We get path_recurse in the first run when
1512          * directory_exists_in_index() returns index_nonexistent. We
1513          * are sure that new changes in the index does not impact the
1514          * outcome. Return now.
1515          */
1516         return path_recurse;
1517 }
1518
1519 static enum path_treatment treat_path(struct dir_struct *dir,
1520                                       struct untracked_cache_dir *untracked,
1521                                       struct cached_dir *cdir,
1522                                       struct strbuf *path,
1523                                       int baselen,
1524                                       const struct path_simplify *simplify)
1525 {
1526         int dtype;
1527         struct dirent *de = cdir->de;
1528
1529         if (!de)
1530                 return treat_path_fast(dir, untracked, cdir, path,
1531                                        baselen, simplify);
1532         if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
1533                 return path_none;
1534         strbuf_setlen(path, baselen);
1535         strbuf_addstr(path, de->d_name);
1536         if (simplify_away(path->buf, path->len, simplify))
1537                 return path_none;
1538
1539         dtype = DTYPE(de);
1540         return treat_one_path(dir, untracked, path, baselen, simplify, dtype, de);
1541 }
1542
1543 static void add_untracked(struct untracked_cache_dir *dir, const char *name)
1544 {
1545         if (!dir)
1546                 return;
1547         ALLOC_GROW(dir->untracked, dir->untracked_nr + 1,
1548                    dir->untracked_alloc);
1549         dir->untracked[dir->untracked_nr++] = xstrdup(name);
1550 }
1551
1552 static int valid_cached_dir(struct dir_struct *dir,
1553                             struct untracked_cache_dir *untracked,
1554                             struct strbuf *path,
1555                             int check_only)
1556 {
1557         struct stat st;
1558
1559         if (!untracked)
1560                 return 0;
1561
1562         if (stat(path->len ? path->buf : ".", &st)) {
1563                 invalidate_directory(dir->untracked, untracked);
1564                 memset(&untracked->stat_data, 0, sizeof(untracked->stat_data));
1565                 return 0;
1566         }
1567         if (!untracked->valid ||
1568             match_stat_data_racy(&the_index, &untracked->stat_data, &st)) {
1569                 if (untracked->valid)
1570                         invalidate_directory(dir->untracked, untracked);
1571                 fill_stat_data(&untracked->stat_data, &st);
1572                 return 0;
1573         }
1574
1575         if (untracked->check_only != !!check_only) {
1576                 invalidate_directory(dir->untracked, untracked);
1577                 return 0;
1578         }
1579
1580         /*
1581          * prep_exclude will be called eventually on this directory,
1582          * but it's called much later in last_exclude_matching(). We
1583          * need it now to determine the validity of the cache for this
1584          * path. The next calls will be nearly no-op, the way
1585          * prep_exclude() is designed.
1586          */
1587         if (path->len && path->buf[path->len - 1] != '/') {
1588                 strbuf_addch(path, '/');
1589                 prep_exclude(dir, path->buf, path->len);
1590                 strbuf_setlen(path, path->len - 1);
1591         } else
1592                 prep_exclude(dir, path->buf, path->len);
1593
1594         /* hopefully prep_exclude() haven't invalidated this entry... */
1595         return untracked->valid;
1596 }
1597
1598 static int open_cached_dir(struct cached_dir *cdir,
1599                            struct dir_struct *dir,
1600                            struct untracked_cache_dir *untracked,
1601                            struct strbuf *path,
1602                            int check_only)
1603 {
1604         memset(cdir, 0, sizeof(*cdir));
1605         cdir->untracked = untracked;
1606         if (valid_cached_dir(dir, untracked, path, check_only))
1607                 return 0;
1608         cdir->fdir = opendir(path->len ? path->buf : ".");
1609         if (dir->untracked)
1610                 dir->untracked->dir_opened++;
1611         if (!cdir->fdir)
1612                 return -1;
1613         return 0;
1614 }
1615
1616 static int read_cached_dir(struct cached_dir *cdir)
1617 {
1618         if (cdir->fdir) {
1619                 cdir->de = readdir(cdir->fdir);
1620                 if (!cdir->de)
1621                         return -1;
1622                 return 0;
1623         }
1624         while (cdir->nr_dirs < cdir->untracked->dirs_nr) {
1625                 struct untracked_cache_dir *d = cdir->untracked->dirs[cdir->nr_dirs];
1626                 if (!d->recurse) {
1627                         cdir->nr_dirs++;
1628                         continue;
1629                 }
1630                 cdir->ucd = d;
1631                 cdir->nr_dirs++;
1632                 return 0;
1633         }
1634         cdir->ucd = NULL;
1635         if (cdir->nr_files < cdir->untracked->untracked_nr) {
1636                 struct untracked_cache_dir *d = cdir->untracked;
1637                 cdir->file = d->untracked[cdir->nr_files++];
1638                 return 0;
1639         }
1640         return -1;
1641 }
1642
1643 static void close_cached_dir(struct cached_dir *cdir)
1644 {
1645         if (cdir->fdir)
1646                 closedir(cdir->fdir);
1647         /*
1648          * We have gone through this directory and found no untracked
1649          * entries. Mark it valid.
1650          */
1651         if (cdir->untracked) {
1652                 cdir->untracked->valid = 1;
1653                 cdir->untracked->recurse = 1;
1654         }
1655 }
1656
1657 /*
1658  * Read a directory tree. We currently ignore anything but
1659  * directories, regular files and symlinks. That's because git
1660  * doesn't handle them at all yet. Maybe that will change some
1661  * day.
1662  *
1663  * Also, we ignore the name ".git" (even if it is not a directory).
1664  * That likely will not change.
1665  *
1666  * Returns the most significant path_treatment value encountered in the scan.
1667  */
1668 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
1669                                     const char *base, int baselen,
1670                                     struct untracked_cache_dir *untracked, int check_only,
1671                                     const struct path_simplify *simplify)
1672 {
1673         struct cached_dir cdir;
1674         enum path_treatment state, subdir_state, dir_state = path_none;
1675         struct strbuf path = STRBUF_INIT;
1676
1677         strbuf_add(&path, base, baselen);
1678
1679         if (open_cached_dir(&cdir, dir, untracked, &path, check_only))
1680                 goto out;
1681
1682         if (untracked)
1683                 untracked->check_only = !!check_only;
1684
1685         while (!read_cached_dir(&cdir)) {
1686                 /* check how the file or directory should be treated */
1687                 state = treat_path(dir, untracked, &cdir, &path, baselen, simplify);
1688
1689                 if (state > dir_state)
1690                         dir_state = state;
1691
1692                 /* recurse into subdir if instructed by treat_path */
1693                 if (state == path_recurse) {
1694                         struct untracked_cache_dir *ud;
1695                         ud = lookup_untracked(dir->untracked, untracked,
1696                                               path.buf + baselen,
1697                                               path.len - baselen);
1698                         subdir_state =
1699                                 read_directory_recursive(dir, path.buf, path.len,
1700                                                          ud, check_only, simplify);
1701                         if (subdir_state > dir_state)
1702                                 dir_state = subdir_state;
1703                 }
1704
1705                 if (check_only) {
1706                         /* abort early if maximum state has been reached */
1707                         if (dir_state == path_untracked) {
1708                                 if (cdir.fdir)
1709                                         add_untracked(untracked, path.buf + baselen);
1710                                 break;
1711                         }
1712                         /* skip the dir_add_* part */
1713                         continue;
1714                 }
1715
1716                 /* add the path to the appropriate result list */
1717                 switch (state) {
1718                 case path_excluded:
1719                         if (dir->flags & DIR_SHOW_IGNORED)
1720                                 dir_add_name(dir, path.buf, path.len);
1721                         else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
1722                                 ((dir->flags & DIR_COLLECT_IGNORED) &&
1723                                 exclude_matches_pathspec(path.buf, path.len,
1724                                         simplify)))
1725                                 dir_add_ignored(dir, path.buf, path.len);
1726                         break;
1727
1728                 case path_untracked:
1729                         if (dir->flags & DIR_SHOW_IGNORED)
1730                                 break;
1731                         dir_add_name(dir, path.buf, path.len);
1732                         if (cdir.fdir)
1733                                 add_untracked(untracked, path.buf + baselen);
1734                         break;
1735
1736                 default:
1737                         break;
1738                 }
1739         }
1740         close_cached_dir(&cdir);
1741  out:
1742         strbuf_release(&path);
1743
1744         return dir_state;
1745 }
1746
1747 static int cmp_name(const void *p1, const void *p2)
1748 {
1749         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
1750         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
1751
1752         return name_compare(e1->name, e1->len, e2->name, e2->len);
1753 }
1754
1755 static struct path_simplify *create_simplify(const char **pathspec)
1756 {
1757         int nr, alloc = 0;
1758         struct path_simplify *simplify = NULL;
1759
1760         if (!pathspec)
1761                 return NULL;
1762
1763         for (nr = 0 ; ; nr++) {
1764                 const char *match;
1765                 ALLOC_GROW(simplify, nr + 1, alloc);
1766                 match = *pathspec++;
1767                 if (!match)
1768                         break;
1769                 simplify[nr].path = match;
1770                 simplify[nr].len = simple_length(match);
1771         }
1772         simplify[nr].path = NULL;
1773         simplify[nr].len = 0;
1774         return simplify;
1775 }
1776
1777 static void free_simplify(struct path_simplify *simplify)
1778 {
1779         free(simplify);
1780 }
1781
1782 static int treat_leading_path(struct dir_struct *dir,
1783                               const char *path, int len,
1784                               const struct path_simplify *simplify)
1785 {
1786         struct strbuf sb = STRBUF_INIT;
1787         int baselen, rc = 0;
1788         const char *cp;
1789         int old_flags = dir->flags;
1790
1791         while (len && path[len - 1] == '/')
1792                 len--;
1793         if (!len)
1794                 return 1;
1795         baselen = 0;
1796         dir->flags &= ~DIR_SHOW_OTHER_DIRECTORIES;
1797         while (1) {
1798                 cp = path + baselen + !!baselen;
1799                 cp = memchr(cp, '/', path + len - cp);
1800                 if (!cp)
1801                         baselen = len;
1802                 else
1803                         baselen = cp - path;
1804                 strbuf_setlen(&sb, 0);
1805                 strbuf_add(&sb, path, baselen);
1806                 if (!is_directory(sb.buf))
1807                         break;
1808                 if (simplify_away(sb.buf, sb.len, simplify))
1809                         break;
1810                 if (treat_one_path(dir, NULL, &sb, baselen, simplify,
1811                                    DT_DIR, NULL) == path_none)
1812                         break; /* do not recurse into it */
1813                 if (len <= baselen) {
1814                         rc = 1;
1815                         break; /* finished checking */
1816                 }
1817         }
1818         strbuf_release(&sb);
1819         dir->flags = old_flags;
1820         return rc;
1821 }
1822
1823 static const char *get_ident_string(void)
1824 {
1825         static struct strbuf sb = STRBUF_INIT;
1826         struct utsname uts;
1827
1828         if (sb.len)
1829                 return sb.buf;
1830         if (uname(&uts) < 0)
1831                 die_errno(_("failed to get kernel name and information"));
1832         strbuf_addf(&sb, "Location %s, system %s", get_git_work_tree(),
1833                     uts.sysname);
1834         return sb.buf;
1835 }
1836
1837 static int ident_in_untracked(const struct untracked_cache *uc)
1838 {
1839         /*
1840          * Previous git versions may have saved many NUL separated
1841          * strings in the "ident" field, but it is insane to manage
1842          * many locations, so just take care of the first one.
1843          */
1844
1845         return !strcmp(uc->ident.buf, get_ident_string());
1846 }
1847
1848 static void set_untracked_ident(struct untracked_cache *uc)
1849 {
1850         strbuf_reset(&uc->ident);
1851         strbuf_addstr(&uc->ident, get_ident_string());
1852
1853         /*
1854          * This strbuf used to contain a list of NUL separated
1855          * strings, so save NUL too for backward compatibility.
1856          */
1857         strbuf_addch(&uc->ident, 0);
1858 }
1859
1860 static void new_untracked_cache(struct index_state *istate)
1861 {
1862         struct untracked_cache *uc = xcalloc(1, sizeof(*uc));
1863         strbuf_init(&uc->ident, 100);
1864         uc->exclude_per_dir = ".gitignore";
1865         /* should be the same flags used by git-status */
1866         uc->dir_flags = DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES;
1867         set_untracked_ident(uc);
1868         istate->untracked = uc;
1869         istate->cache_changed |= UNTRACKED_CHANGED;
1870 }
1871
1872 void add_untracked_cache(struct index_state *istate)
1873 {
1874         if (!istate->untracked) {
1875                 new_untracked_cache(istate);
1876         } else {
1877                 if (!ident_in_untracked(istate->untracked)) {
1878                         free_untracked_cache(istate->untracked);
1879                         new_untracked_cache(istate);
1880                 }
1881         }
1882 }
1883
1884 void remove_untracked_cache(struct index_state *istate)
1885 {
1886         if (istate->untracked) {
1887                 free_untracked_cache(istate->untracked);
1888                 istate->untracked = NULL;
1889                 istate->cache_changed |= UNTRACKED_CHANGED;
1890         }
1891 }
1892
1893 static struct untracked_cache_dir *validate_untracked_cache(struct dir_struct *dir,
1894                                                       int base_len,
1895                                                       const struct pathspec *pathspec)
1896 {
1897         struct untracked_cache_dir *root;
1898
1899         if (!dir->untracked || getenv("GIT_DISABLE_UNTRACKED_CACHE"))
1900                 return NULL;
1901
1902         /*
1903          * We only support $GIT_DIR/info/exclude and core.excludesfile
1904          * as the global ignore rule files. Any other additions
1905          * (e.g. from command line) invalidate the cache. This
1906          * condition also catches running setup_standard_excludes()
1907          * before setting dir->untracked!
1908          */
1909         if (dir->unmanaged_exclude_files)
1910                 return NULL;
1911
1912         /*
1913          * Optimize for the main use case only: whole-tree git
1914          * status. More work involved in treat_leading_path() if we
1915          * use cache on just a subset of the worktree. pathspec
1916          * support could make the matter even worse.
1917          */
1918         if (base_len || (pathspec && pathspec->nr))
1919                 return NULL;
1920
1921         /* Different set of flags may produce different results */
1922         if (dir->flags != dir->untracked->dir_flags ||
1923             /*
1924              * See treat_directory(), case index_nonexistent. Without
1925              * this flag, we may need to also cache .git file content
1926              * for the resolve_gitlink_ref() call, which we don't.
1927              */
1928             !(dir->flags & DIR_SHOW_OTHER_DIRECTORIES) ||
1929             /* We don't support collecting ignore files */
1930             (dir->flags & (DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO |
1931                            DIR_COLLECT_IGNORED)))
1932                 return NULL;
1933
1934         /*
1935          * If we use .gitignore in the cache and now you change it to
1936          * .gitexclude, everything will go wrong.
1937          */
1938         if (dir->exclude_per_dir != dir->untracked->exclude_per_dir &&
1939             strcmp(dir->exclude_per_dir, dir->untracked->exclude_per_dir))
1940                 return NULL;
1941
1942         /*
1943          * EXC_CMDL is not considered in the cache. If people set it,
1944          * skip the cache.
1945          */
1946         if (dir->exclude_list_group[EXC_CMDL].nr)
1947                 return NULL;
1948
1949         if (!ident_in_untracked(dir->untracked)) {
1950                 warning(_("Untracked cache is disabled on this system or location."));
1951                 return NULL;
1952         }
1953
1954         if (!dir->untracked->root) {
1955                 const int len = sizeof(*dir->untracked->root);
1956                 dir->untracked->root = xmalloc(len);
1957                 memset(dir->untracked->root, 0, len);
1958         }
1959
1960         /* Validate $GIT_DIR/info/exclude and core.excludesfile */
1961         root = dir->untracked->root;
1962         if (hashcmp(dir->ss_info_exclude.sha1,
1963                     dir->untracked->ss_info_exclude.sha1)) {
1964                 invalidate_gitignore(dir->untracked, root);
1965                 dir->untracked->ss_info_exclude = dir->ss_info_exclude;
1966         }
1967         if (hashcmp(dir->ss_excludes_file.sha1,
1968                     dir->untracked->ss_excludes_file.sha1)) {
1969                 invalidate_gitignore(dir->untracked, root);
1970                 dir->untracked->ss_excludes_file = dir->ss_excludes_file;
1971         }
1972
1973         /* Make sure this directory is not dropped out at saving phase */
1974         root->recurse = 1;
1975         return root;
1976 }
1977
1978 int read_directory(struct dir_struct *dir, const char *path, int len, const struct pathspec *pathspec)
1979 {
1980         struct path_simplify *simplify;
1981         struct untracked_cache_dir *untracked;
1982
1983         /*
1984          * Check out create_simplify()
1985          */
1986         if (pathspec)
1987                 GUARD_PATHSPEC(pathspec,
1988                                PATHSPEC_FROMTOP |
1989                                PATHSPEC_MAXDEPTH |
1990                                PATHSPEC_LITERAL |
1991                                PATHSPEC_GLOB |
1992                                PATHSPEC_ICASE |
1993                                PATHSPEC_EXCLUDE);
1994
1995         if (has_symlink_leading_path(path, len))
1996                 return dir->nr;
1997
1998         /*
1999          * exclude patterns are treated like positive ones in
2000          * create_simplify. Usually exclude patterns should be a
2001          * subset of positive ones, which has no impacts on
2002          * create_simplify().
2003          */
2004         simplify = create_simplify(pathspec ? pathspec->_raw : NULL);
2005         untracked = validate_untracked_cache(dir, len, pathspec);
2006         if (!untracked)
2007                 /*
2008                  * make sure untracked cache code path is disabled,
2009                  * e.g. prep_exclude()
2010                  */
2011                 dir->untracked = NULL;
2012         if (!len || treat_leading_path(dir, path, len, simplify))
2013                 read_directory_recursive(dir, path, len, untracked, 0, simplify);
2014         free_simplify(simplify);
2015         qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
2016         qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
2017         if (dir->untracked) {
2018                 static struct trace_key trace_untracked_stats = TRACE_KEY_INIT(UNTRACKED_STATS);
2019                 trace_printf_key(&trace_untracked_stats,
2020                                  "node creation: %u\n"
2021                                  "gitignore invalidation: %u\n"
2022                                  "directory invalidation: %u\n"
2023                                  "opendir: %u\n",
2024                                  dir->untracked->dir_created,
2025                                  dir->untracked->gitignore_invalidated,
2026                                  dir->untracked->dir_invalidated,
2027                                  dir->untracked->dir_opened);
2028                 if (dir->untracked == the_index.untracked &&
2029                     (dir->untracked->dir_opened ||
2030                      dir->untracked->gitignore_invalidated ||
2031                      dir->untracked->dir_invalidated))
2032                         the_index.cache_changed |= UNTRACKED_CHANGED;
2033                 if (dir->untracked != the_index.untracked) {
2034                         free(dir->untracked);
2035                         dir->untracked = NULL;
2036                 }
2037         }
2038         return dir->nr;
2039 }
2040
2041 int file_exists(const char *f)
2042 {
2043         struct stat sb;
2044         return lstat(f, &sb) == 0;
2045 }
2046
2047 static int cmp_icase(char a, char b)
2048 {
2049         if (a == b)
2050                 return 0;
2051         if (ignore_case)
2052                 return toupper(a) - toupper(b);
2053         return a - b;
2054 }
2055
2056 /*
2057  * Given two normalized paths (a trailing slash is ok), if subdir is
2058  * outside dir, return -1.  Otherwise return the offset in subdir that
2059  * can be used as relative path to dir.
2060  */
2061 int dir_inside_of(const char *subdir, const char *dir)
2062 {
2063         int offset = 0;
2064
2065         assert(dir && subdir && *dir && *subdir);
2066
2067         while (*dir && *subdir && !cmp_icase(*dir, *subdir)) {
2068                 dir++;
2069                 subdir++;
2070                 offset++;
2071         }
2072
2073         /* hel[p]/me vs hel[l]/yeah */
2074         if (*dir && *subdir)
2075                 return -1;
2076
2077         if (!*subdir)
2078                 return !*dir ? offset : -1; /* same dir */
2079
2080         /* foo/[b]ar vs foo/[] */
2081         if (is_dir_sep(dir[-1]))
2082                 return is_dir_sep(subdir[-1]) ? offset : -1;
2083
2084         /* foo[/]bar vs foo[] */
2085         return is_dir_sep(*subdir) ? offset + 1 : -1;
2086 }
2087
2088 int is_inside_dir(const char *dir)
2089 {
2090         char *cwd;
2091         int rc;
2092
2093         if (!dir)
2094                 return 0;
2095
2096         cwd = xgetcwd();
2097         rc = (dir_inside_of(cwd, dir) >= 0);
2098         free(cwd);
2099         return rc;
2100 }
2101
2102 int is_empty_dir(const char *path)
2103 {
2104         DIR *dir = opendir(path);
2105         struct dirent *e;
2106         int ret = 1;
2107
2108         if (!dir)
2109                 return 0;
2110
2111         while ((e = readdir(dir)) != NULL)
2112                 if (!is_dot_or_dotdot(e->d_name)) {
2113                         ret = 0;
2114                         break;
2115                 }
2116
2117         closedir(dir);
2118         return ret;
2119 }
2120
2121 static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
2122 {
2123         DIR *dir;
2124         struct dirent *e;
2125         int ret = 0, original_len = path->len, len, kept_down = 0;
2126         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
2127         int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
2128         unsigned char submodule_head[20];
2129
2130         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
2131             !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
2132                 /* Do not descend and nuke a nested git work tree. */
2133                 if (kept_up)
2134                         *kept_up = 1;
2135                 return 0;
2136         }
2137
2138         flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
2139         dir = opendir(path->buf);
2140         if (!dir) {
2141                 if (errno == ENOENT)
2142                         return keep_toplevel ? -1 : 0;
2143                 else if (errno == EACCES && !keep_toplevel)
2144                         /*
2145                          * An empty dir could be removable even if it
2146                          * is unreadable:
2147                          */
2148                         return rmdir(path->buf);
2149                 else
2150                         return -1;
2151         }
2152         strbuf_complete(path, '/');
2153
2154         len = path->len;
2155         while ((e = readdir(dir)) != NULL) {
2156                 struct stat st;
2157                 if (is_dot_or_dotdot(e->d_name))
2158                         continue;
2159
2160                 strbuf_setlen(path, len);
2161                 strbuf_addstr(path, e->d_name);
2162                 if (lstat(path->buf, &st)) {
2163                         if (errno == ENOENT)
2164                                 /*
2165                                  * file disappeared, which is what we
2166                                  * wanted anyway
2167                                  */
2168                                 continue;
2169                         /* fall thru */
2170                 } else if (S_ISDIR(st.st_mode)) {
2171                         if (!remove_dir_recurse(path, flag, &kept_down))
2172                                 continue; /* happy */
2173                 } else if (!only_empty &&
2174                            (!unlink(path->buf) || errno == ENOENT)) {
2175                         continue; /* happy, too */
2176                 }
2177
2178                 /* path too long, stat fails, or non-directory still exists */
2179                 ret = -1;
2180                 break;
2181         }
2182         closedir(dir);
2183
2184         strbuf_setlen(path, original_len);
2185         if (!ret && !keep_toplevel && !kept_down)
2186                 ret = (!rmdir(path->buf) || errno == ENOENT) ? 0 : -1;
2187         else if (kept_up)
2188                 /*
2189                  * report the uplevel that it is not an error that we
2190                  * did not rmdir() our directory.
2191                  */
2192                 *kept_up = !ret;
2193         return ret;
2194 }
2195
2196 int remove_dir_recursively(struct strbuf *path, int flag)
2197 {
2198         return remove_dir_recurse(path, flag, NULL);
2199 }
2200
2201 static GIT_PATH_FUNC(git_path_info_exclude, "info/exclude")
2202
2203 void setup_standard_excludes(struct dir_struct *dir)
2204 {
2205         const char *path;
2206
2207         dir->exclude_per_dir = ".gitignore";
2208
2209         /* core.excludefile defaulting to $XDG_HOME/git/ignore */
2210         if (!excludes_file)
2211                 excludes_file = xdg_config_home("ignore");
2212         if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
2213                 add_excludes_from_file_1(dir, excludes_file,
2214                                          dir->untracked ? &dir->ss_excludes_file : NULL);
2215
2216         /* per repository user preference */
2217         path = git_path_info_exclude();
2218         if (!access_or_warn(path, R_OK, 0))
2219                 add_excludes_from_file_1(dir, path,
2220                                          dir->untracked ? &dir->ss_info_exclude : NULL);
2221 }
2222
2223 int remove_path(const char *name)
2224 {
2225         char *slash;
2226
2227         if (unlink(name) && errno != ENOENT && errno != ENOTDIR)
2228                 return -1;
2229
2230         slash = strrchr(name, '/');
2231         if (slash) {
2232                 char *dirs = xstrdup(name);
2233                 slash = dirs + (slash - name);
2234                 do {
2235                         *slash = '\0';
2236                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
2237                 free(dirs);
2238         }
2239         return 0;
2240 }
2241
2242 /*
2243  * Frees memory within dir which was allocated for exclude lists and
2244  * the exclude_stack.  Does not free dir itself.
2245  */
2246 void clear_directory(struct dir_struct *dir)
2247 {
2248         int i, j;
2249         struct exclude_list_group *group;
2250         struct exclude_list *el;
2251         struct exclude_stack *stk;
2252
2253         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
2254                 group = &dir->exclude_list_group[i];
2255                 for (j = 0; j < group->nr; j++) {
2256                         el = &group->el[j];
2257                         if (i == EXC_DIRS)
2258                                 free((char *)el->src);
2259                         clear_exclude_list(el);
2260                 }
2261                 free(group->el);
2262         }
2263
2264         stk = dir->exclude_stack;
2265         while (stk) {
2266                 struct exclude_stack *prev = stk->prev;
2267                 free(stk);
2268                 stk = prev;
2269         }
2270         strbuf_release(&dir->basebuf);
2271 }
2272
2273 struct ondisk_untracked_cache {
2274         struct stat_data info_exclude_stat;
2275         struct stat_data excludes_file_stat;
2276         uint32_t dir_flags;
2277         unsigned char info_exclude_sha1[20];
2278         unsigned char excludes_file_sha1[20];
2279         char exclude_per_dir[FLEX_ARRAY];
2280 };
2281
2282 #define ouc_size(len) (offsetof(struct ondisk_untracked_cache, exclude_per_dir) + len + 1)
2283
2284 struct write_data {
2285         int index;         /* number of written untracked_cache_dir */
2286         struct ewah_bitmap *check_only; /* from untracked_cache_dir */
2287         struct ewah_bitmap *valid;      /* from untracked_cache_dir */
2288         struct ewah_bitmap *sha1_valid; /* set if exclude_sha1 is not null */
2289         struct strbuf out;
2290         struct strbuf sb_stat;
2291         struct strbuf sb_sha1;
2292 };
2293
2294 static void stat_data_to_disk(struct stat_data *to, const struct stat_data *from)
2295 {
2296         to->sd_ctime.sec  = htonl(from->sd_ctime.sec);
2297         to->sd_ctime.nsec = htonl(from->sd_ctime.nsec);
2298         to->sd_mtime.sec  = htonl(from->sd_mtime.sec);
2299         to->sd_mtime.nsec = htonl(from->sd_mtime.nsec);
2300         to->sd_dev        = htonl(from->sd_dev);
2301         to->sd_ino        = htonl(from->sd_ino);
2302         to->sd_uid        = htonl(from->sd_uid);
2303         to->sd_gid        = htonl(from->sd_gid);
2304         to->sd_size       = htonl(from->sd_size);
2305 }
2306
2307 static void write_one_dir(struct untracked_cache_dir *untracked,
2308                           struct write_data *wd)
2309 {
2310         struct stat_data stat_data;
2311         struct strbuf *out = &wd->out;
2312         unsigned char intbuf[16];
2313         unsigned int intlen, value;
2314         int i = wd->index++;
2315
2316         /*
2317          * untracked_nr should be reset whenever valid is clear, but
2318          * for safety..
2319          */
2320         if (!untracked->valid) {
2321                 untracked->untracked_nr = 0;
2322                 untracked->check_only = 0;
2323         }
2324
2325         if (untracked->check_only)
2326                 ewah_set(wd->check_only, i);
2327         if (untracked->valid) {
2328                 ewah_set(wd->valid, i);
2329                 stat_data_to_disk(&stat_data, &untracked->stat_data);
2330                 strbuf_add(&wd->sb_stat, &stat_data, sizeof(stat_data));
2331         }
2332         if (!is_null_sha1(untracked->exclude_sha1)) {
2333                 ewah_set(wd->sha1_valid, i);
2334                 strbuf_add(&wd->sb_sha1, untracked->exclude_sha1, 20);
2335         }
2336
2337         intlen = encode_varint(untracked->untracked_nr, intbuf);
2338         strbuf_add(out, intbuf, intlen);
2339
2340         /* skip non-recurse directories */
2341         for (i = 0, value = 0; i < untracked->dirs_nr; i++)
2342                 if (untracked->dirs[i]->recurse)
2343                         value++;
2344         intlen = encode_varint(value, intbuf);
2345         strbuf_add(out, intbuf, intlen);
2346
2347         strbuf_add(out, untracked->name, strlen(untracked->name) + 1);
2348
2349         for (i = 0; i < untracked->untracked_nr; i++)
2350                 strbuf_add(out, untracked->untracked[i],
2351                            strlen(untracked->untracked[i]) + 1);
2352
2353         for (i = 0; i < untracked->dirs_nr; i++)
2354                 if (untracked->dirs[i]->recurse)
2355                         write_one_dir(untracked->dirs[i], wd);
2356 }
2357
2358 void write_untracked_extension(struct strbuf *out, struct untracked_cache *untracked)
2359 {
2360         struct ondisk_untracked_cache *ouc;
2361         struct write_data wd;
2362         unsigned char varbuf[16];
2363         int varint_len;
2364         size_t len = strlen(untracked->exclude_per_dir);
2365
2366         FLEX_ALLOC_MEM(ouc, exclude_per_dir, untracked->exclude_per_dir, len);
2367         stat_data_to_disk(&ouc->info_exclude_stat, &untracked->ss_info_exclude.stat);
2368         stat_data_to_disk(&ouc->excludes_file_stat, &untracked->ss_excludes_file.stat);
2369         hashcpy(ouc->info_exclude_sha1, untracked->ss_info_exclude.sha1);
2370         hashcpy(ouc->excludes_file_sha1, untracked->ss_excludes_file.sha1);
2371         ouc->dir_flags = htonl(untracked->dir_flags);
2372
2373         varint_len = encode_varint(untracked->ident.len, varbuf);
2374         strbuf_add(out, varbuf, varint_len);
2375         strbuf_add(out, untracked->ident.buf, untracked->ident.len);
2376
2377         strbuf_add(out, ouc, ouc_size(len));
2378         free(ouc);
2379         ouc = NULL;
2380
2381         if (!untracked->root) {
2382                 varint_len = encode_varint(0, varbuf);
2383                 strbuf_add(out, varbuf, varint_len);
2384                 return;
2385         }
2386
2387         wd.index      = 0;
2388         wd.check_only = ewah_new();
2389         wd.valid      = ewah_new();
2390         wd.sha1_valid = ewah_new();
2391         strbuf_init(&wd.out, 1024);
2392         strbuf_init(&wd.sb_stat, 1024);
2393         strbuf_init(&wd.sb_sha1, 1024);
2394         write_one_dir(untracked->root, &wd);
2395
2396         varint_len = encode_varint(wd.index, varbuf);
2397         strbuf_add(out, varbuf, varint_len);
2398         strbuf_addbuf(out, &wd.out);
2399         ewah_serialize_strbuf(wd.valid, out);
2400         ewah_serialize_strbuf(wd.check_only, out);
2401         ewah_serialize_strbuf(wd.sha1_valid, out);
2402         strbuf_addbuf(out, &wd.sb_stat);
2403         strbuf_addbuf(out, &wd.sb_sha1);
2404         strbuf_addch(out, '\0'); /* safe guard for string lists */
2405
2406         ewah_free(wd.valid);
2407         ewah_free(wd.check_only);
2408         ewah_free(wd.sha1_valid);
2409         strbuf_release(&wd.out);
2410         strbuf_release(&wd.sb_stat);
2411         strbuf_release(&wd.sb_sha1);
2412 }
2413
2414 static void free_untracked(struct untracked_cache_dir *ucd)
2415 {
2416         int i;
2417         if (!ucd)
2418                 return;
2419         for (i = 0; i < ucd->dirs_nr; i++)
2420                 free_untracked(ucd->dirs[i]);
2421         for (i = 0; i < ucd->untracked_nr; i++)
2422                 free(ucd->untracked[i]);
2423         free(ucd->untracked);
2424         free(ucd->dirs);
2425         free(ucd);
2426 }
2427
2428 void free_untracked_cache(struct untracked_cache *uc)
2429 {
2430         if (uc)
2431                 free_untracked(uc->root);
2432         free(uc);
2433 }
2434
2435 struct read_data {
2436         int index;
2437         struct untracked_cache_dir **ucd;
2438         struct ewah_bitmap *check_only;
2439         struct ewah_bitmap *valid;
2440         struct ewah_bitmap *sha1_valid;
2441         const unsigned char *data;
2442         const unsigned char *end;
2443 };
2444
2445 static void stat_data_from_disk(struct stat_data *to, const struct stat_data *from)
2446 {
2447         to->sd_ctime.sec  = get_be32(&from->sd_ctime.sec);
2448         to->sd_ctime.nsec = get_be32(&from->sd_ctime.nsec);
2449         to->sd_mtime.sec  = get_be32(&from->sd_mtime.sec);
2450         to->sd_mtime.nsec = get_be32(&from->sd_mtime.nsec);
2451         to->sd_dev        = get_be32(&from->sd_dev);
2452         to->sd_ino        = get_be32(&from->sd_ino);
2453         to->sd_uid        = get_be32(&from->sd_uid);
2454         to->sd_gid        = get_be32(&from->sd_gid);
2455         to->sd_size       = get_be32(&from->sd_size);
2456 }
2457
2458 static int read_one_dir(struct untracked_cache_dir **untracked_,
2459                         struct read_data *rd)
2460 {
2461         struct untracked_cache_dir ud, *untracked;
2462         const unsigned char *next, *data = rd->data, *end = rd->end;
2463         unsigned int value;
2464         int i, len;
2465
2466         memset(&ud, 0, sizeof(ud));
2467
2468         next = data;
2469         value = decode_varint(&next);
2470         if (next > end)
2471                 return -1;
2472         ud.recurse         = 1;
2473         ud.untracked_alloc = value;
2474         ud.untracked_nr    = value;
2475         if (ud.untracked_nr)
2476                 ALLOC_ARRAY(ud.untracked, ud.untracked_nr);
2477         data = next;
2478
2479         next = data;
2480         ud.dirs_alloc = ud.dirs_nr = decode_varint(&next);
2481         if (next > end)
2482                 return -1;
2483         ALLOC_ARRAY(ud.dirs, ud.dirs_nr);
2484         data = next;
2485
2486         len = strlen((const char *)data);
2487         next = data + len + 1;
2488         if (next > rd->end)
2489                 return -1;
2490         *untracked_ = untracked = xmalloc(st_add(sizeof(*untracked), len));
2491         memcpy(untracked, &ud, sizeof(ud));
2492         memcpy(untracked->name, data, len + 1);
2493         data = next;
2494
2495         for (i = 0; i < untracked->untracked_nr; i++) {
2496                 len = strlen((const char *)data);
2497                 next = data + len + 1;
2498                 if (next > rd->end)
2499                         return -1;
2500                 untracked->untracked[i] = xstrdup((const char*)data);
2501                 data = next;
2502         }
2503
2504         rd->ucd[rd->index++] = untracked;
2505         rd->data = data;
2506
2507         for (i = 0; i < untracked->dirs_nr; i++) {
2508                 len = read_one_dir(untracked->dirs + i, rd);
2509                 if (len < 0)
2510                         return -1;
2511         }
2512         return 0;
2513 }
2514
2515 static void set_check_only(size_t pos, void *cb)
2516 {
2517         struct read_data *rd = cb;
2518         struct untracked_cache_dir *ud = rd->ucd[pos];
2519         ud->check_only = 1;
2520 }
2521
2522 static void read_stat(size_t pos, void *cb)
2523 {
2524         struct read_data *rd = cb;
2525         struct untracked_cache_dir *ud = rd->ucd[pos];
2526         if (rd->data + sizeof(struct stat_data) > rd->end) {
2527                 rd->data = rd->end + 1;
2528                 return;
2529         }
2530         stat_data_from_disk(&ud->stat_data, (struct stat_data *)rd->data);
2531         rd->data += sizeof(struct stat_data);
2532         ud->valid = 1;
2533 }
2534
2535 static void read_sha1(size_t pos, void *cb)
2536 {
2537         struct read_data *rd = cb;
2538         struct untracked_cache_dir *ud = rd->ucd[pos];
2539         if (rd->data + 20 > rd->end) {
2540                 rd->data = rd->end + 1;
2541                 return;
2542         }
2543         hashcpy(ud->exclude_sha1, rd->data);
2544         rd->data += 20;
2545 }
2546
2547 static void load_sha1_stat(struct sha1_stat *sha1_stat,
2548                            const struct stat_data *stat,
2549                            const unsigned char *sha1)
2550 {
2551         stat_data_from_disk(&sha1_stat->stat, stat);
2552         hashcpy(sha1_stat->sha1, sha1);
2553         sha1_stat->valid = 1;
2554 }
2555
2556 struct untracked_cache *read_untracked_extension(const void *data, unsigned long sz)
2557 {
2558         const struct ondisk_untracked_cache *ouc;
2559         struct untracked_cache *uc;
2560         struct read_data rd;
2561         const unsigned char *next = data, *end = (const unsigned char *)data + sz;
2562         const char *ident;
2563         int ident_len, len;
2564
2565         if (sz <= 1 || end[-1] != '\0')
2566                 return NULL;
2567         end--;
2568
2569         ident_len = decode_varint(&next);
2570         if (next + ident_len > end)
2571                 return NULL;
2572         ident = (const char *)next;
2573         next += ident_len;
2574
2575         ouc = (const struct ondisk_untracked_cache *)next;
2576         if (next + ouc_size(0) > end)
2577                 return NULL;
2578
2579         uc = xcalloc(1, sizeof(*uc));
2580         strbuf_init(&uc->ident, ident_len);
2581         strbuf_add(&uc->ident, ident, ident_len);
2582         load_sha1_stat(&uc->ss_info_exclude, &ouc->info_exclude_stat,
2583                        ouc->info_exclude_sha1);
2584         load_sha1_stat(&uc->ss_excludes_file, &ouc->excludes_file_stat,
2585                        ouc->excludes_file_sha1);
2586         uc->dir_flags = get_be32(&ouc->dir_flags);
2587         uc->exclude_per_dir = xstrdup(ouc->exclude_per_dir);
2588         /* NUL after exclude_per_dir is covered by sizeof(*ouc) */
2589         next += ouc_size(strlen(ouc->exclude_per_dir));
2590         if (next >= end)
2591                 goto done2;
2592
2593         len = decode_varint(&next);
2594         if (next > end || len == 0)
2595                 goto done2;
2596
2597         rd.valid      = ewah_new();
2598         rd.check_only = ewah_new();
2599         rd.sha1_valid = ewah_new();
2600         rd.data       = next;
2601         rd.end        = end;
2602         rd.index      = 0;
2603         ALLOC_ARRAY(rd.ucd, len);
2604
2605         if (read_one_dir(&uc->root, &rd) || rd.index != len)
2606                 goto done;
2607
2608         next = rd.data;
2609         len = ewah_read_mmap(rd.valid, next, end - next);
2610         if (len < 0)
2611                 goto done;
2612
2613         next += len;
2614         len = ewah_read_mmap(rd.check_only, next, end - next);
2615         if (len < 0)
2616                 goto done;
2617
2618         next += len;
2619         len = ewah_read_mmap(rd.sha1_valid, next, end - next);
2620         if (len < 0)
2621                 goto done;
2622
2623         ewah_each_bit(rd.check_only, set_check_only, &rd);
2624         rd.data = next + len;
2625         ewah_each_bit(rd.valid, read_stat, &rd);
2626         ewah_each_bit(rd.sha1_valid, read_sha1, &rd);
2627         next = rd.data;
2628
2629 done:
2630         free(rd.ucd);
2631         ewah_free(rd.valid);
2632         ewah_free(rd.check_only);
2633         ewah_free(rd.sha1_valid);
2634 done2:
2635         if (next != end) {
2636                 free_untracked_cache(uc);
2637                 uc = NULL;
2638         }
2639         return uc;
2640 }
2641
2642 static void invalidate_one_directory(struct untracked_cache *uc,
2643                                      struct untracked_cache_dir *ucd)
2644 {
2645         uc->dir_invalidated++;
2646         ucd->valid = 0;
2647         ucd->untracked_nr = 0;
2648 }
2649
2650 /*
2651  * Normally when an entry is added or removed from a directory,
2652  * invalidating that directory is enough. No need to touch its
2653  * ancestors. When a directory is shown as "foo/bar/" in git-status
2654  * however, deleting or adding an entry may have cascading effect.
2655  *
2656  * Say the "foo/bar/file" has become untracked, we need to tell the
2657  * untracked_cache_dir of "foo" that "bar/" is not an untracked
2658  * directory any more (because "bar" is managed by foo as an untracked
2659  * "file").
2660  *
2661  * Similarly, if "foo/bar/file" moves from untracked to tracked and it
2662  * was the last untracked entry in the entire "foo", we should show
2663  * "foo/" instead. Which means we have to invalidate past "bar" up to
2664  * "foo".
2665  *
2666  * This function traverses all directories from root to leaf. If there
2667  * is a chance of one of the above cases happening, we invalidate back
2668  * to root. Otherwise we just invalidate the leaf. There may be a more
2669  * sophisticated way than checking for SHOW_OTHER_DIRECTORIES to
2670  * detect these cases and avoid unnecessary invalidation, for example,
2671  * checking for the untracked entry named "bar/" in "foo", but for now
2672  * stick to something safe and simple.
2673  */
2674 static int invalidate_one_component(struct untracked_cache *uc,
2675                                     struct untracked_cache_dir *dir,
2676                                     const char *path, int len)
2677 {
2678         const char *rest = strchr(path, '/');
2679
2680         if (rest) {
2681                 int component_len = rest - path;
2682                 struct untracked_cache_dir *d =
2683                         lookup_untracked(uc, dir, path, component_len);
2684                 int ret =
2685                         invalidate_one_component(uc, d, rest + 1,
2686                                                  len - (component_len + 1));
2687                 if (ret)
2688                         invalidate_one_directory(uc, dir);
2689                 return ret;
2690         }
2691
2692         invalidate_one_directory(uc, dir);
2693         return uc->dir_flags & DIR_SHOW_OTHER_DIRECTORIES;
2694 }
2695
2696 void untracked_cache_invalidate_path(struct index_state *istate,
2697                                      const char *path)
2698 {
2699         if (!istate->untracked || !istate->untracked->root)
2700                 return;
2701         invalidate_one_component(istate->untracked, istate->untracked->root,
2702                                  path, strlen(path));
2703 }
2704
2705 void untracked_cache_remove_from_index(struct index_state *istate,
2706                                        const char *path)
2707 {
2708         untracked_cache_invalidate_path(istate, path);
2709 }
2710
2711 void untracked_cache_add_to_index(struct index_state *istate,
2712                                   const char *path)
2713 {
2714         untracked_cache_invalidate_path(istate, path);
2715 }