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