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