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