Merge branch 'mr/bisect-in-c-3'
[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_free_entries(&pl->parent_hashmap, struct pattern_entry, ent);
821         hashmap_free_entries(&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_free_entries(&pl->recursive_hashmap, struct pattern_entry, ent);
925         hashmap_free_entries(&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 /*
1039  * Given a file with name "fname", read it (either from disk, or from
1040  * an index if 'istate' is non-null), parse it and store the
1041  * exclude rules in "pl".
1042  *
1043  * If "oid_stat" is not NULL, compute oid of the exclude file and fill
1044  * stat data from disk (only valid if add_patterns returns zero). If
1045  * oid_stat.valid is non-zero, "oid_stat" must contain good value as input.
1046  */
1047 static int add_patterns(const char *fname, const char *base, int baselen,
1048                         struct pattern_list *pl, struct index_state *istate,
1049                         struct oid_stat *oid_stat)
1050 {
1051         struct stat st;
1052         int r;
1053         int fd;
1054         size_t size = 0;
1055         char *buf;
1056
1057         fd = open(fname, O_RDONLY);
1058         if (fd < 0 || fstat(fd, &st) < 0) {
1059                 if (fd < 0)
1060                         warn_on_fopen_errors(fname);
1061                 else
1062                         close(fd);
1063                 if (!istate)
1064                         return -1;
1065                 r = read_skip_worktree_file_from_index(istate, fname,
1066                                                        &size, &buf,
1067                                                        oid_stat);
1068                 if (r != 1)
1069                         return r;
1070         } else {
1071                 size = xsize_t(st.st_size);
1072                 if (size == 0) {
1073                         if (oid_stat) {
1074                                 fill_stat_data(&oid_stat->stat, &st);
1075                                 oidcpy(&oid_stat->oid, the_hash_algo->empty_blob);
1076                                 oid_stat->valid = 1;
1077                         }
1078                         close(fd);
1079                         return 0;
1080                 }
1081                 buf = xmallocz(size);
1082                 if (read_in_full(fd, buf, size) != size) {
1083                         free(buf);
1084                         close(fd);
1085                         return -1;
1086                 }
1087                 buf[size++] = '\n';
1088                 close(fd);
1089                 if (oid_stat) {
1090                         int pos;
1091                         if (oid_stat->valid &&
1092                             !match_stat_data_racy(istate, &oid_stat->stat, &st))
1093                                 ; /* no content change, oid_stat->oid still good */
1094                         else if (istate &&
1095                                  (pos = index_name_pos(istate, fname, strlen(fname))) >= 0 &&
1096                                  !ce_stage(istate->cache[pos]) &&
1097                                  ce_uptodate(istate->cache[pos]) &&
1098                                  !would_convert_to_git(istate, fname))
1099                                 oidcpy(&oid_stat->oid,
1100                                        &istate->cache[pos]->oid);
1101                         else
1102                                 hash_object_file(the_hash_algo, buf, size,
1103                                                  "blob", &oid_stat->oid);
1104                         fill_stat_data(&oid_stat->stat, &st);
1105                         oid_stat->valid = 1;
1106                 }
1107         }
1108
1109         add_patterns_from_buffer(buf, size, base, baselen, pl);
1110         return 0;
1111 }
1112
1113 static int add_patterns_from_buffer(char *buf, size_t size,
1114                                     const char *base, int baselen,
1115                                     struct pattern_list *pl)
1116 {
1117         int i, lineno = 1;
1118         char *entry;
1119
1120         hashmap_init(&pl->recursive_hashmap, pl_hashmap_cmp, NULL, 0);
1121         hashmap_init(&pl->parent_hashmap, pl_hashmap_cmp, NULL, 0);
1122
1123         pl->filebuf = buf;
1124
1125         if (skip_utf8_bom(&buf, size))
1126                 size -= buf - pl->filebuf;
1127
1128         entry = buf;
1129
1130         for (i = 0; i < size; i++) {
1131                 if (buf[i] == '\n') {
1132                         if (entry != buf + i && entry[0] != '#') {
1133                                 buf[i - (i && buf[i-1] == '\r')] = 0;
1134                                 trim_trailing_spaces(entry);
1135                                 add_pattern(entry, base, baselen, pl, lineno);
1136                         }
1137                         lineno++;
1138                         entry = buf + i + 1;
1139                 }
1140         }
1141         return 0;
1142 }
1143
1144 int add_patterns_from_file_to_list(const char *fname, const char *base,
1145                                    int baselen, struct pattern_list *pl,
1146                                    struct index_state *istate)
1147 {
1148         return add_patterns(fname, base, baselen, pl, istate, NULL);
1149 }
1150
1151 int add_patterns_from_blob_to_list(
1152         struct object_id *oid,
1153         const char *base, int baselen,
1154         struct pattern_list *pl)
1155 {
1156         char *buf;
1157         size_t size;
1158         int r;
1159
1160         r = do_read_blob(oid, NULL, &size, &buf);
1161         if (r != 1)
1162                 return r;
1163
1164         add_patterns_from_buffer(buf, size, base, baselen, pl);
1165         return 0;
1166 }
1167
1168 struct pattern_list *add_pattern_list(struct dir_struct *dir,
1169                                       int group_type, const char *src)
1170 {
1171         struct pattern_list *pl;
1172         struct exclude_list_group *group;
1173
1174         group = &dir->exclude_list_group[group_type];
1175         ALLOC_GROW(group->pl, group->nr + 1, group->alloc);
1176         pl = &group->pl[group->nr++];
1177         memset(pl, 0, sizeof(*pl));
1178         pl->src = src;
1179         return pl;
1180 }
1181
1182 /*
1183  * Used to set up core.excludesfile and .git/info/exclude lists.
1184  */
1185 static void add_patterns_from_file_1(struct dir_struct *dir, const char *fname,
1186                                      struct oid_stat *oid_stat)
1187 {
1188         struct pattern_list *pl;
1189         /*
1190          * catch setup_standard_excludes() that's called before
1191          * dir->untracked is assigned. That function behaves
1192          * differently when dir->untracked is non-NULL.
1193          */
1194         if (!dir->untracked)
1195                 dir->unmanaged_exclude_files++;
1196         pl = add_pattern_list(dir, EXC_FILE, fname);
1197         if (add_patterns(fname, "", 0, pl, NULL, oid_stat) < 0)
1198                 die(_("cannot use %s as an exclude file"), fname);
1199 }
1200
1201 void add_patterns_from_file(struct dir_struct *dir, const char *fname)
1202 {
1203         dir->unmanaged_exclude_files++; /* see validate_untracked_cache() */
1204         add_patterns_from_file_1(dir, fname, NULL);
1205 }
1206
1207 int match_basename(const char *basename, int basenamelen,
1208                    const char *pattern, int prefix, int patternlen,
1209                    unsigned flags)
1210 {
1211         if (prefix == patternlen) {
1212                 if (patternlen == basenamelen &&
1213                     !fspathncmp(pattern, basename, basenamelen))
1214                         return 1;
1215         } else if (flags & PATTERN_FLAG_ENDSWITH) {
1216                 /* "*literal" matching against "fooliteral" */
1217                 if (patternlen - 1 <= basenamelen &&
1218                     !fspathncmp(pattern + 1,
1219                                    basename + basenamelen - (patternlen - 1),
1220                                    patternlen - 1))
1221                         return 1;
1222         } else {
1223                 if (fnmatch_icase_mem(pattern, patternlen,
1224                                       basename, basenamelen,
1225                                       0) == 0)
1226                         return 1;
1227         }
1228         return 0;
1229 }
1230
1231 int match_pathname(const char *pathname, int pathlen,
1232                    const char *base, int baselen,
1233                    const char *pattern, int prefix, int patternlen,
1234                    unsigned flags)
1235 {
1236         const char *name;
1237         int namelen;
1238
1239         /*
1240          * match with FNM_PATHNAME; the pattern has base implicitly
1241          * in front of it.
1242          */
1243         if (*pattern == '/') {
1244                 pattern++;
1245                 patternlen--;
1246                 prefix--;
1247         }
1248
1249         /*
1250          * baselen does not count the trailing slash. base[] may or
1251          * may not end with a trailing slash though.
1252          */
1253         if (pathlen < baselen + 1 ||
1254             (baselen && pathname[baselen] != '/') ||
1255             fspathncmp(pathname, base, baselen))
1256                 return 0;
1257
1258         namelen = baselen ? pathlen - baselen - 1 : pathlen;
1259         name = pathname + pathlen - namelen;
1260
1261         if (prefix) {
1262                 /*
1263                  * if the non-wildcard part is longer than the
1264                  * remaining pathname, surely it cannot match.
1265                  */
1266                 if (prefix > namelen)
1267                         return 0;
1268
1269                 if (fspathncmp(pattern, name, prefix))
1270                         return 0;
1271                 pattern += prefix;
1272                 patternlen -= prefix;
1273                 name    += prefix;
1274                 namelen -= prefix;
1275
1276                 /*
1277                  * If the whole pattern did not have a wildcard,
1278                  * then our prefix match is all we need; we
1279                  * do not need to call fnmatch at all.
1280                  */
1281                 if (!patternlen && !namelen)
1282                         return 1;
1283         }
1284
1285         return fnmatch_icase_mem(pattern, patternlen,
1286                                  name, namelen,
1287                                  WM_PATHNAME) == 0;
1288 }
1289
1290 /*
1291  * Scan the given exclude list in reverse to see whether pathname
1292  * should be ignored.  The first match (i.e. the last on the list), if
1293  * any, determines the fate.  Returns the exclude_list element which
1294  * matched, or NULL for undecided.
1295  */
1296 static struct path_pattern *last_matching_pattern_from_list(const char *pathname,
1297                                                        int pathlen,
1298                                                        const char *basename,
1299                                                        int *dtype,
1300                                                        struct pattern_list *pl,
1301                                                        struct index_state *istate)
1302 {
1303         struct path_pattern *res = NULL; /* undecided */
1304         int i;
1305
1306         if (!pl->nr)
1307                 return NULL;    /* undefined */
1308
1309         for (i = pl->nr - 1; 0 <= i; i--) {
1310                 struct path_pattern *pattern = pl->patterns[i];
1311                 const char *exclude = pattern->pattern;
1312                 int prefix = pattern->nowildcardlen;
1313
1314                 if (pattern->flags & PATTERN_FLAG_MUSTBEDIR) {
1315                         *dtype = resolve_dtype(*dtype, istate, pathname, pathlen);
1316                         if (*dtype != DT_DIR)
1317                                 continue;
1318                 }
1319
1320                 if (pattern->flags & PATTERN_FLAG_NODIR) {
1321                         if (match_basename(basename,
1322                                            pathlen - (basename - pathname),
1323                                            exclude, prefix, pattern->patternlen,
1324                                            pattern->flags)) {
1325                                 res = pattern;
1326                                 break;
1327                         }
1328                         continue;
1329                 }
1330
1331                 assert(pattern->baselen == 0 ||
1332                        pattern->base[pattern->baselen - 1] == '/');
1333                 if (match_pathname(pathname, pathlen,
1334                                    pattern->base,
1335                                    pattern->baselen ? pattern->baselen - 1 : 0,
1336                                    exclude, prefix, pattern->patternlen,
1337                                    pattern->flags)) {
1338                         res = pattern;
1339                         break;
1340                 }
1341         }
1342         return res;
1343 }
1344
1345 /*
1346  * Scan the list of patterns to determine if the ordered list
1347  * of patterns matches on 'pathname'.
1348  *
1349  * Return 1 for a match, 0 for not matched and -1 for undecided.
1350  */
1351 enum pattern_match_result path_matches_pattern_list(
1352                                 const char *pathname, int pathlen,
1353                                 const char *basename, int *dtype,
1354                                 struct pattern_list *pl,
1355                                 struct index_state *istate)
1356 {
1357         struct path_pattern *pattern;
1358         struct strbuf parent_pathname = STRBUF_INIT;
1359         int result = NOT_MATCHED;
1360         const char *slash_pos;
1361
1362         if (!pl->use_cone_patterns) {
1363                 pattern = last_matching_pattern_from_list(pathname, pathlen, basename,
1364                                                         dtype, pl, istate);
1365                 if (pattern) {
1366                         if (pattern->flags & PATTERN_FLAG_NEGATIVE)
1367                                 return NOT_MATCHED;
1368                         else
1369                                 return MATCHED;
1370                 }
1371
1372                 return UNDECIDED;
1373         }
1374
1375         if (pl->full_cone)
1376                 return MATCHED;
1377
1378         strbuf_addch(&parent_pathname, '/');
1379         strbuf_add(&parent_pathname, pathname, pathlen);
1380
1381         if (hashmap_contains_path(&pl->recursive_hashmap,
1382                                   &parent_pathname)) {
1383                 result = MATCHED_RECURSIVE;
1384                 goto done;
1385         }
1386
1387         slash_pos = strrchr(parent_pathname.buf, '/');
1388
1389         if (slash_pos == parent_pathname.buf) {
1390                 /* include every file in root */
1391                 result = MATCHED;
1392                 goto done;
1393         }
1394
1395         strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
1396
1397         if (hashmap_contains_path(&pl->parent_hashmap, &parent_pathname)) {
1398                 result = MATCHED;
1399                 goto done;
1400         }
1401
1402         if (hashmap_contains_parent(&pl->recursive_hashmap,
1403                                     pathname,
1404                                     &parent_pathname))
1405                 result = MATCHED_RECURSIVE;
1406
1407 done:
1408         strbuf_release(&parent_pathname);
1409         return result;
1410 }
1411
1412 static struct path_pattern *last_matching_pattern_from_lists(
1413                 struct dir_struct *dir, struct index_state *istate,
1414                 const char *pathname, int pathlen,
1415                 const char *basename, int *dtype_p)
1416 {
1417         int i, j;
1418         struct exclude_list_group *group;
1419         struct path_pattern *pattern;
1420         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
1421                 group = &dir->exclude_list_group[i];
1422                 for (j = group->nr - 1; j >= 0; j--) {
1423                         pattern = last_matching_pattern_from_list(
1424                                 pathname, pathlen, basename, dtype_p,
1425                                 &group->pl[j], istate);
1426                         if (pattern)
1427                                 return pattern;
1428                 }
1429         }
1430         return NULL;
1431 }
1432
1433 /*
1434  * Loads the per-directory exclude list for the substring of base
1435  * which has a char length of baselen.
1436  */
1437 static void prep_exclude(struct dir_struct *dir,
1438                          struct index_state *istate,
1439                          const char *base, int baselen)
1440 {
1441         struct exclude_list_group *group;
1442         struct pattern_list *pl;
1443         struct exclude_stack *stk = NULL;
1444         struct untracked_cache_dir *untracked;
1445         int current;
1446
1447         group = &dir->exclude_list_group[EXC_DIRS];
1448
1449         /*
1450          * Pop the exclude lists from the EXCL_DIRS exclude_list_group
1451          * which originate from directories not in the prefix of the
1452          * path being checked.
1453          */
1454         while ((stk = dir->exclude_stack) != NULL) {
1455                 if (stk->baselen <= baselen &&
1456                     !strncmp(dir->basebuf.buf, base, stk->baselen))
1457                         break;
1458                 pl = &group->pl[dir->exclude_stack->exclude_ix];
1459                 dir->exclude_stack = stk->prev;
1460                 dir->pattern = NULL;
1461                 free((char *)pl->src); /* see strbuf_detach() below */
1462                 clear_pattern_list(pl);
1463                 free(stk);
1464                 group->nr--;
1465         }
1466
1467         /* Skip traversing into sub directories if the parent is excluded */
1468         if (dir->pattern)
1469                 return;
1470
1471         /*
1472          * Lazy initialization. All call sites currently just
1473          * memset(dir, 0, sizeof(*dir)) before use. Changing all of
1474          * them seems lots of work for little benefit.
1475          */
1476         if (!dir->basebuf.buf)
1477                 strbuf_init(&dir->basebuf, PATH_MAX);
1478
1479         /* Read from the parent directories and push them down. */
1480         current = stk ? stk->baselen : -1;
1481         strbuf_setlen(&dir->basebuf, current < 0 ? 0 : current);
1482         if (dir->untracked)
1483                 untracked = stk ? stk->ucd : dir->untracked->root;
1484         else
1485                 untracked = NULL;
1486
1487         while (current < baselen) {
1488                 const char *cp;
1489                 struct oid_stat oid_stat;
1490
1491                 stk = xcalloc(1, sizeof(*stk));
1492                 if (current < 0) {
1493                         cp = base;
1494                         current = 0;
1495                 } else {
1496                         cp = strchr(base + current + 1, '/');
1497                         if (!cp)
1498                                 die("oops in prep_exclude");
1499                         cp++;
1500                         untracked =
1501                                 lookup_untracked(dir->untracked, untracked,
1502                                                  base + current,
1503                                                  cp - base - current);
1504                 }
1505                 stk->prev = dir->exclude_stack;
1506                 stk->baselen = cp - base;
1507                 stk->exclude_ix = group->nr;
1508                 stk->ucd = untracked;
1509                 pl = add_pattern_list(dir, EXC_DIRS, NULL);
1510                 strbuf_add(&dir->basebuf, base + current, stk->baselen - current);
1511                 assert(stk->baselen == dir->basebuf.len);
1512
1513                 /* Abort if the directory is excluded */
1514                 if (stk->baselen) {
1515                         int dt = DT_DIR;
1516                         dir->basebuf.buf[stk->baselen - 1] = 0;
1517                         dir->pattern = last_matching_pattern_from_lists(dir,
1518                                                                         istate,
1519                                 dir->basebuf.buf, stk->baselen - 1,
1520                                 dir->basebuf.buf + current, &dt);
1521                         dir->basebuf.buf[stk->baselen - 1] = '/';
1522                         if (dir->pattern &&
1523                             dir->pattern->flags & PATTERN_FLAG_NEGATIVE)
1524                                 dir->pattern = NULL;
1525                         if (dir->pattern) {
1526                                 dir->exclude_stack = stk;
1527                                 return;
1528                         }
1529                 }
1530
1531                 /* Try to read per-directory file */
1532                 oidclr(&oid_stat.oid);
1533                 oid_stat.valid = 0;
1534                 if (dir->exclude_per_dir &&
1535                     /*
1536                      * If we know that no files have been added in
1537                      * this directory (i.e. valid_cached_dir() has
1538                      * been executed and set untracked->valid) ..
1539                      */
1540                     (!untracked || !untracked->valid ||
1541                      /*
1542                       * .. and .gitignore does not exist before
1543                       * (i.e. null exclude_oid). Then we can skip
1544                       * loading .gitignore, which would result in
1545                       * ENOENT anyway.
1546                       */
1547                      !is_null_oid(&untracked->exclude_oid))) {
1548                         /*
1549                          * dir->basebuf gets reused by the traversal, but we
1550                          * need fname to remain unchanged to ensure the src
1551                          * member of each struct path_pattern correctly
1552                          * back-references its source file.  Other invocations
1553                          * of add_pattern_list provide stable strings, so we
1554                          * strbuf_detach() and free() here in the caller.
1555                          */
1556                         struct strbuf sb = STRBUF_INIT;
1557                         strbuf_addbuf(&sb, &dir->basebuf);
1558                         strbuf_addstr(&sb, dir->exclude_per_dir);
1559                         pl->src = strbuf_detach(&sb, NULL);
1560                         add_patterns(pl->src, pl->src, stk->baselen, pl, istate,
1561                                      untracked ? &oid_stat : NULL);
1562                 }
1563                 /*
1564                  * NEEDSWORK: when untracked cache is enabled, prep_exclude()
1565                  * will first be called in valid_cached_dir() then maybe many
1566                  * times more in last_matching_pattern(). When the cache is
1567                  * used, last_matching_pattern() will not be called and
1568                  * reading .gitignore content will be a waste.
1569                  *
1570                  * So when it's called by valid_cached_dir() and we can get
1571                  * .gitignore SHA-1 from the index (i.e. .gitignore is not
1572                  * modified on work tree), we could delay reading the
1573                  * .gitignore content until we absolutely need it in
1574                  * last_matching_pattern(). Be careful about ignore rule
1575                  * order, though, if you do that.
1576                  */
1577                 if (untracked &&
1578                     !oideq(&oid_stat.oid, &untracked->exclude_oid)) {
1579                         invalidate_gitignore(dir->untracked, untracked);
1580                         oidcpy(&untracked->exclude_oid, &oid_stat.oid);
1581                 }
1582                 dir->exclude_stack = stk;
1583                 current = stk->baselen;
1584         }
1585         strbuf_setlen(&dir->basebuf, baselen);
1586 }
1587
1588 /*
1589  * Loads the exclude lists for the directory containing pathname, then
1590  * scans all exclude lists to determine whether pathname is excluded.
1591  * Returns the exclude_list element which matched, or NULL for
1592  * undecided.
1593  */
1594 struct path_pattern *last_matching_pattern(struct dir_struct *dir,
1595                                       struct index_state *istate,
1596                                       const char *pathname,
1597                                       int *dtype_p)
1598 {
1599         int pathlen = strlen(pathname);
1600         const char *basename = strrchr(pathname, '/');
1601         basename = (basename) ? basename+1 : pathname;
1602
1603         prep_exclude(dir, istate, pathname, basename-pathname);
1604
1605         if (dir->pattern)
1606                 return dir->pattern;
1607
1608         return last_matching_pattern_from_lists(dir, istate, pathname, pathlen,
1609                         basename, dtype_p);
1610 }
1611
1612 /*
1613  * Loads the exclude lists for the directory containing pathname, then
1614  * scans all exclude lists to determine whether pathname is excluded.
1615  * Returns 1 if true, otherwise 0.
1616  */
1617 int is_excluded(struct dir_struct *dir, struct index_state *istate,
1618                 const char *pathname, int *dtype_p)
1619 {
1620         struct path_pattern *pattern =
1621                 last_matching_pattern(dir, istate, pathname, dtype_p);
1622         if (pattern)
1623                 return pattern->flags & PATTERN_FLAG_NEGATIVE ? 0 : 1;
1624         return 0;
1625 }
1626
1627 static struct dir_entry *dir_entry_new(const char *pathname, int len)
1628 {
1629         struct dir_entry *ent;
1630
1631         FLEX_ALLOC_MEM(ent, name, pathname, len);
1632         ent->len = len;
1633         return ent;
1634 }
1635
1636 static struct dir_entry *dir_add_name(struct dir_struct *dir,
1637                                       struct index_state *istate,
1638                                       const char *pathname, int len)
1639 {
1640         if (index_file_exists(istate, pathname, len, ignore_case))
1641                 return NULL;
1642
1643         ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
1644         return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
1645 }
1646
1647 struct dir_entry *dir_add_ignored(struct dir_struct *dir,
1648                                   struct index_state *istate,
1649                                   const char *pathname, int len)
1650 {
1651         if (!index_name_is_other(istate, pathname, len))
1652                 return NULL;
1653
1654         ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
1655         return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
1656 }
1657
1658 enum exist_status {
1659         index_nonexistent = 0,
1660         index_directory,
1661         index_gitdir
1662 };
1663
1664 /*
1665  * Do not use the alphabetically sorted index to look up
1666  * the directory name; instead, use the case insensitive
1667  * directory hash.
1668  */
1669 static enum exist_status directory_exists_in_index_icase(struct index_state *istate,
1670                                                          const char *dirname, int len)
1671 {
1672         struct cache_entry *ce;
1673
1674         if (index_dir_exists(istate, dirname, len))
1675                 return index_directory;
1676
1677         ce = index_file_exists(istate, dirname, len, ignore_case);
1678         if (ce && S_ISGITLINK(ce->ce_mode))
1679                 return index_gitdir;
1680
1681         return index_nonexistent;
1682 }
1683
1684 /*
1685  * The index sorts alphabetically by entry name, which
1686  * means that a gitlink sorts as '\0' at the end, while
1687  * a directory (which is defined not as an entry, but as
1688  * the files it contains) will sort with the '/' at the
1689  * end.
1690  */
1691 static enum exist_status directory_exists_in_index(struct index_state *istate,
1692                                                    const char *dirname, int len)
1693 {
1694         int pos;
1695
1696         if (ignore_case)
1697                 return directory_exists_in_index_icase(istate, dirname, len);
1698
1699         pos = index_name_pos(istate, dirname, len);
1700         if (pos < 0)
1701                 pos = -pos-1;
1702         while (pos < istate->cache_nr) {
1703                 const struct cache_entry *ce = istate->cache[pos++];
1704                 unsigned char endchar;
1705
1706                 if (strncmp(ce->name, dirname, len))
1707                         break;
1708                 endchar = ce->name[len];
1709                 if (endchar > '/')
1710                         break;
1711                 if (endchar == '/')
1712                         return index_directory;
1713                 if (!endchar && S_ISGITLINK(ce->ce_mode))
1714                         return index_gitdir;
1715         }
1716         return index_nonexistent;
1717 }
1718
1719 /*
1720  * When we find a directory when traversing the filesystem, we
1721  * have three distinct cases:
1722  *
1723  *  - ignore it
1724  *  - see it as a directory
1725  *  - recurse into it
1726  *
1727  * and which one we choose depends on a combination of existing
1728  * git index contents and the flags passed into the directory
1729  * traversal routine.
1730  *
1731  * Case 1: If we *already* have entries in the index under that
1732  * directory name, we always recurse into the directory to see
1733  * all the files.
1734  *
1735  * Case 2: If we *already* have that directory name as a gitlink,
1736  * we always continue to see it as a gitlink, regardless of whether
1737  * there is an actual git directory there or not (it might not
1738  * be checked out as a subproject!)
1739  *
1740  * Case 3: if we didn't have it in the index previously, we
1741  * have a few sub-cases:
1742  *
1743  *  (a) if "show_other_directories" is true, we show it as
1744  *      just a directory, unless "hide_empty_directories" is
1745  *      also true, in which case we need to check if it contains any
1746  *      untracked and / or ignored files.
1747  *  (b) if it looks like a git directory, and we don't have
1748  *      'no_gitlinks' set we treat it as a gitlink, and show it
1749  *      as a directory.
1750  *  (c) otherwise, we recurse into it.
1751  */
1752 static enum path_treatment treat_directory(struct dir_struct *dir,
1753         struct index_state *istate,
1754         struct untracked_cache_dir *untracked,
1755         const char *dirname, int len, int baselen, int excluded,
1756         const struct pathspec *pathspec)
1757 {
1758         /*
1759          * WARNING: From this function, you can return path_recurse or you
1760          *          can call read_directory_recursive() (or neither), but
1761          *          you CAN'T DO BOTH.
1762          */
1763         enum path_treatment state;
1764         int matches_how = 0;
1765         int nested_repo = 0, check_only, stop_early;
1766         int old_ignored_nr, old_untracked_nr;
1767         /* The "len-1" is to strip the final '/' */
1768         enum exist_status status = directory_exists_in_index(istate, dirname, len-1);
1769
1770         if (status == index_directory)
1771                 return path_recurse;
1772         if (status == index_gitdir)
1773                 return path_none;
1774         if (status != index_nonexistent)
1775                 BUG("Unhandled value for directory_exists_in_index: %d\n", status);
1776
1777         /*
1778          * We don't want to descend into paths that don't match the necessary
1779          * patterns.  Clearly, if we don't have a pathspec, then we can't check
1780          * for matching patterns.  Also, if (excluded) then we know we matched
1781          * the exclusion patterns so as an optimization we can skip checking
1782          * for matching patterns.
1783          */
1784         if (pathspec && !excluded) {
1785                 matches_how = match_pathspec_with_flags(istate, pathspec,
1786                                                         dirname, len,
1787                                                         0 /* prefix */,
1788                                                         NULL /* seen */,
1789                                                         DO_MATCH_LEADING_PATHSPEC);
1790                 if (!matches_how)
1791                         return path_none;
1792         }
1793
1794
1795         if ((dir->flags & DIR_SKIP_NESTED_GIT) ||
1796                 !(dir->flags & DIR_NO_GITLINKS)) {
1797                 struct strbuf sb = STRBUF_INIT;
1798                 strbuf_addstr(&sb, dirname);
1799                 nested_repo = is_nonbare_repository_dir(&sb);
1800                 strbuf_release(&sb);
1801         }
1802         if (nested_repo) {
1803                 if ((dir->flags & DIR_SKIP_NESTED_GIT) ||
1804                     (matches_how == MATCHED_RECURSIVELY_LEADING_PATHSPEC))
1805                         return path_none;
1806                 return excluded ? path_excluded : path_untracked;
1807         }
1808
1809         if (!(dir->flags & DIR_SHOW_OTHER_DIRECTORIES)) {
1810                 if (excluded &&
1811                     (dir->flags & DIR_SHOW_IGNORED_TOO) &&
1812                     (dir->flags & DIR_SHOW_IGNORED_TOO_MODE_MATCHING)) {
1813
1814                         /*
1815                          * This is an excluded directory and we are
1816                          * showing ignored paths that match an exclude
1817                          * pattern.  (e.g. show directory as ignored
1818                          * only if it matches an exclude pattern).
1819                          * This path will either be 'path_excluded`
1820                          * (if we are showing empty directories or if
1821                          * the directory is not empty), or will be
1822                          * 'path_none' (empty directory, and we are
1823                          * not showing empty directories).
1824                          */
1825                         if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1826                                 return path_excluded;
1827
1828                         if (read_directory_recursive(dir, istate, dirname, len,
1829                                                      untracked, 1, 1, pathspec) == path_excluded)
1830                                 return path_excluded;
1831
1832                         return path_none;
1833                 }
1834                 return path_recurse;
1835         }
1836
1837         /* This is the "show_other_directories" case */
1838
1839         /*
1840          * If we have a pathspec which could match something _below_ this
1841          * directory (e.g. when checking 'subdir/' having a pathspec like
1842          * 'subdir/some/deep/path/file' or 'subdir/widget-*.c'), then we
1843          * need to recurse.
1844          */
1845         if (matches_how == MATCHED_RECURSIVELY_LEADING_PATHSPEC)
1846                 return path_recurse;
1847
1848         /*
1849          * Other than the path_recurse case immediately above, we only need
1850          * to recurse into untracked/ignored directories if either of the
1851          * following bits is set:
1852          *   - DIR_SHOW_IGNORED_TOO (because then we need to determine if
1853          *                           there are ignored entries below)
1854          *   - DIR_HIDE_EMPTY_DIRECTORIES (because we have to determine if
1855          *                                 the directory is empty)
1856          */
1857         if (!(dir->flags & (DIR_SHOW_IGNORED_TOO | DIR_HIDE_EMPTY_DIRECTORIES)))
1858                 return excluded ? path_excluded : path_untracked;
1859
1860         /*
1861          * ...and even if DIR_SHOW_IGNORED_TOO is set, we can still avoid
1862          * recursing into ignored directories if the path is excluded and
1863          * DIR_SHOW_IGNORED_TOO_MODE_MATCHING is also set.
1864          */
1865         if (excluded &&
1866             (dir->flags & DIR_SHOW_IGNORED_TOO) &&
1867             (dir->flags & DIR_SHOW_IGNORED_TOO_MODE_MATCHING))
1868                 return path_excluded;
1869
1870         /*
1871          * Even if we don't want to know all the paths under an untracked or
1872          * ignored directory, we may still need to go into the directory to
1873          * determine if it is empty (because with DIR_HIDE_EMPTY_DIRECTORIES,
1874          * an empty directory should be path_none instead of path_excluded or
1875          * path_untracked).
1876          */
1877         check_only = ((dir->flags & DIR_HIDE_EMPTY_DIRECTORIES) &&
1878                       !(dir->flags & DIR_SHOW_IGNORED_TOO));
1879
1880         /*
1881          * However, there's another optimization possible as a subset of
1882          * check_only, based on the cases we have to consider:
1883          *   A) Directory matches no exclude patterns:
1884          *     * Directory is empty => path_none
1885          *     * Directory has an untracked file under it => path_untracked
1886          *     * Directory has only ignored files under it => path_excluded
1887          *   B) Directory matches an exclude pattern:
1888          *     * Directory is empty => path_none
1889          *     * Directory has an untracked file under it => path_excluded
1890          *     * Directory has only ignored files under it => path_excluded
1891          * In case A, we can exit as soon as we've found an untracked
1892          * file but otherwise have to walk all files.  In case B, though,
1893          * we can stop at the first file we find under the directory.
1894          */
1895         stop_early = check_only && excluded;
1896
1897         /*
1898          * If /every/ file within an untracked directory is ignored, then
1899          * we want to treat the directory as ignored (for e.g. status
1900          * --porcelain), without listing the individual ignored files
1901          * underneath.  To do so, we'll save the current ignored_nr, and
1902          * pop all the ones added after it if it turns out the entire
1903          * directory is ignored.  Also, when DIR_SHOW_IGNORED_TOO and
1904          * !DIR_KEEP_UNTRACKED_CONTENTS then we don't want to show
1905          * untracked paths so will need to pop all those off the last
1906          * after we traverse.
1907          */
1908         old_ignored_nr = dir->ignored_nr;
1909         old_untracked_nr = dir->nr;
1910
1911         /* Actually recurse into dirname now, we'll fixup the state later. */
1912         untracked = lookup_untracked(dir->untracked, untracked,
1913                                      dirname + baselen, len - baselen);
1914         state = read_directory_recursive(dir, istate, dirname, len, untracked,
1915                                          check_only, stop_early, pathspec);
1916
1917         /* There are a variety of reasons we may need to fixup the state... */
1918         if (state == path_excluded) {
1919                 /* state == path_excluded implies all paths under
1920                  * dirname were ignored...
1921                  *
1922                  * if running e.g. `git status --porcelain --ignored=matching`,
1923                  * then we want to see the subpaths that are ignored.
1924                  *
1925                  * if running e.g. just `git status --porcelain`, then
1926                  * we just want the directory itself to be listed as ignored
1927                  * and not the individual paths underneath.
1928                  */
1929                 int want_ignored_subpaths =
1930                         ((dir->flags & DIR_SHOW_IGNORED_TOO) &&
1931                          (dir->flags & DIR_SHOW_IGNORED_TOO_MODE_MATCHING));
1932
1933                 if (want_ignored_subpaths) {
1934                         /*
1935                          * with --ignored=matching, we want the subpaths
1936                          * INSTEAD of the directory itself.
1937                          */
1938                         state = path_none;
1939                 } else {
1940                         int i;
1941                         for (i = old_ignored_nr + 1; i<dir->ignored_nr; ++i)
1942                                 FREE_AND_NULL(dir->ignored[i]);
1943                         dir->ignored_nr = old_ignored_nr;
1944                 }
1945         }
1946
1947         /*
1948          * We may need to ignore some of the untracked paths we found while
1949          * traversing subdirectories.
1950          */
1951         if ((dir->flags & DIR_SHOW_IGNORED_TOO) &&
1952             !(dir->flags & DIR_KEEP_UNTRACKED_CONTENTS)) {
1953                 int i;
1954                 for (i = old_untracked_nr + 1; i<dir->nr; ++i)
1955                         FREE_AND_NULL(dir->entries[i]);
1956                 dir->nr = old_untracked_nr;
1957         }
1958
1959         /*
1960          * If there is nothing under the current directory and we are not
1961          * hiding empty directories, then we need to report on the
1962          * untracked or ignored status of the directory itself.
1963          */
1964         if (state == path_none && !(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1965                 state = excluded ? path_excluded : path_untracked;
1966
1967         return state;
1968 }
1969
1970 /*
1971  * This is an inexact early pruning of any recursive directory
1972  * reading - if the path cannot possibly be in the pathspec,
1973  * return true, and we'll skip it early.
1974  */
1975 static int simplify_away(const char *path, int pathlen,
1976                          const struct pathspec *pathspec)
1977 {
1978         int i;
1979
1980         if (!pathspec || !pathspec->nr)
1981                 return 0;
1982
1983         GUARD_PATHSPEC(pathspec,
1984                        PATHSPEC_FROMTOP |
1985                        PATHSPEC_MAXDEPTH |
1986                        PATHSPEC_LITERAL |
1987                        PATHSPEC_GLOB |
1988                        PATHSPEC_ICASE |
1989                        PATHSPEC_EXCLUDE |
1990                        PATHSPEC_ATTR);
1991
1992         for (i = 0; i < pathspec->nr; i++) {
1993                 const struct pathspec_item *item = &pathspec->items[i];
1994                 int len = item->nowildcard_len;
1995
1996                 if (len > pathlen)
1997                         len = pathlen;
1998                 if (!ps_strncmp(item, item->match, path, len))
1999                         return 0;
2000         }
2001
2002         return 1;
2003 }
2004
2005 /*
2006  * This function tells us whether an excluded path matches a
2007  * list of "interesting" pathspecs. That is, whether a path matched
2008  * by any of the pathspecs could possibly be ignored by excluding
2009  * the specified path. This can happen if:
2010  *
2011  *   1. the path is mentioned explicitly in the pathspec
2012  *
2013  *   2. the path is a directory prefix of some element in the
2014  *      pathspec
2015  */
2016 static int exclude_matches_pathspec(const char *path, int pathlen,
2017                                     const struct pathspec *pathspec)
2018 {
2019         int i;
2020
2021         if (!pathspec || !pathspec->nr)
2022                 return 0;
2023
2024         GUARD_PATHSPEC(pathspec,
2025                        PATHSPEC_FROMTOP |
2026                        PATHSPEC_MAXDEPTH |
2027                        PATHSPEC_LITERAL |
2028                        PATHSPEC_GLOB |
2029                        PATHSPEC_ICASE |
2030                        PATHSPEC_EXCLUDE);
2031
2032         for (i = 0; i < pathspec->nr; i++) {
2033                 const struct pathspec_item *item = &pathspec->items[i];
2034                 int len = item->nowildcard_len;
2035
2036                 if (len == pathlen &&
2037                     !ps_strncmp(item, item->match, path, pathlen))
2038                         return 1;
2039                 if (len > pathlen &&
2040                     item->match[pathlen] == '/' &&
2041                     !ps_strncmp(item, item->match, path, pathlen))
2042                         return 1;
2043         }
2044         return 0;
2045 }
2046
2047 static int get_index_dtype(struct index_state *istate,
2048                            const char *path, int len)
2049 {
2050         int pos;
2051         const struct cache_entry *ce;
2052
2053         ce = index_file_exists(istate, path, len, 0);
2054         if (ce) {
2055                 if (!ce_uptodate(ce))
2056                         return DT_UNKNOWN;
2057                 if (S_ISGITLINK(ce->ce_mode))
2058                         return DT_DIR;
2059                 /*
2060                  * Nobody actually cares about the
2061                  * difference between DT_LNK and DT_REG
2062                  */
2063                 return DT_REG;
2064         }
2065
2066         /* Try to look it up as a directory */
2067         pos = index_name_pos(istate, path, len);
2068         if (pos >= 0)
2069                 return DT_UNKNOWN;
2070         pos = -pos-1;
2071         while (pos < istate->cache_nr) {
2072                 ce = istate->cache[pos++];
2073                 if (strncmp(ce->name, path, len))
2074                         break;
2075                 if (ce->name[len] > '/')
2076                         break;
2077                 if (ce->name[len] < '/')
2078                         continue;
2079                 if (!ce_uptodate(ce))
2080                         break;  /* continue? */
2081                 return DT_DIR;
2082         }
2083         return DT_UNKNOWN;
2084 }
2085
2086 static int resolve_dtype(int dtype, struct index_state *istate,
2087                          const char *path, int len)
2088 {
2089         struct stat st;
2090
2091         if (dtype != DT_UNKNOWN)
2092                 return dtype;
2093         dtype = get_index_dtype(istate, path, len);
2094         if (dtype != DT_UNKNOWN)
2095                 return dtype;
2096         if (lstat(path, &st))
2097                 return dtype;
2098         if (S_ISREG(st.st_mode))
2099                 return DT_REG;
2100         if (S_ISDIR(st.st_mode))
2101                 return DT_DIR;
2102         if (S_ISLNK(st.st_mode))
2103                 return DT_LNK;
2104         return dtype;
2105 }
2106
2107 static enum path_treatment treat_path_fast(struct dir_struct *dir,
2108                                            struct cached_dir *cdir,
2109                                            struct index_state *istate,
2110                                            struct strbuf *path,
2111                                            int baselen,
2112                                            const struct pathspec *pathspec)
2113 {
2114         /*
2115          * WARNING: From this function, you can return path_recurse or you
2116          *          can call read_directory_recursive() (or neither), but
2117          *          you CAN'T DO BOTH.
2118          */
2119         strbuf_setlen(path, baselen);
2120         if (!cdir->ucd) {
2121                 strbuf_addstr(path, cdir->file);
2122                 return path_untracked;
2123         }
2124         strbuf_addstr(path, cdir->ucd->name);
2125         /* treat_one_path() does this before it calls treat_directory() */
2126         strbuf_complete(path, '/');
2127         if (cdir->ucd->check_only)
2128                 /*
2129                  * check_only is set as a result of treat_directory() getting
2130                  * to its bottom. Verify again the same set of directories
2131                  * with check_only set.
2132                  */
2133                 return read_directory_recursive(dir, istate, path->buf, path->len,
2134                                                 cdir->ucd, 1, 0, pathspec);
2135         /*
2136          * We get path_recurse in the first run when
2137          * directory_exists_in_index() returns index_nonexistent. We
2138          * are sure that new changes in the index does not impact the
2139          * outcome. Return now.
2140          */
2141         return path_recurse;
2142 }
2143
2144 static enum path_treatment treat_path(struct dir_struct *dir,
2145                                       struct untracked_cache_dir *untracked,
2146                                       struct cached_dir *cdir,
2147                                       struct index_state *istate,
2148                                       struct strbuf *path,
2149                                       int baselen,
2150                                       const struct pathspec *pathspec)
2151 {
2152         int has_path_in_index, dtype, excluded;
2153
2154         if (!cdir->d_name)
2155                 return treat_path_fast(dir, cdir, istate, path,
2156                                        baselen, pathspec);
2157         if (is_dot_or_dotdot(cdir->d_name) || !fspathcmp(cdir->d_name, ".git"))
2158                 return path_none;
2159         strbuf_setlen(path, baselen);
2160         strbuf_addstr(path, cdir->d_name);
2161         if (simplify_away(path->buf, path->len, pathspec))
2162                 return path_none;
2163
2164         dtype = resolve_dtype(cdir->d_type, istate, path->buf, path->len);
2165
2166         /* Always exclude indexed files */
2167         has_path_in_index = !!index_file_exists(istate, path->buf, path->len,
2168                                                 ignore_case);
2169         if (dtype != DT_DIR && has_path_in_index)
2170                 return path_none;
2171
2172         /*
2173          * When we are looking at a directory P in the working tree,
2174          * there are three cases:
2175          *
2176          * (1) P exists in the index.  Everything inside the directory P in
2177          * the working tree needs to go when P is checked out from the
2178          * index.
2179          *
2180          * (2) P does not exist in the index, but there is P/Q in the index.
2181          * We know P will stay a directory when we check out the contents
2182          * of the index, but we do not know yet if there is a directory
2183          * P/Q in the working tree to be killed, so we need to recurse.
2184          *
2185          * (3) P does not exist in the index, and there is no P/Q in the index
2186          * to require P to be a directory, either.  Only in this case, we
2187          * know that everything inside P will not be killed without
2188          * recursing.
2189          */
2190         if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
2191             (dtype == DT_DIR) &&
2192             !has_path_in_index &&
2193             (directory_exists_in_index(istate, path->buf, path->len) == index_nonexistent))
2194                 return path_none;
2195
2196         excluded = is_excluded(dir, istate, path->buf, &dtype);
2197
2198         /*
2199          * Excluded? If we don't explicitly want to show
2200          * ignored files, ignore it
2201          */
2202         if (excluded && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
2203                 return path_excluded;
2204
2205         switch (dtype) {
2206         default:
2207                 return path_none;
2208         case DT_DIR:
2209                 /*
2210                  * WARNING: Do not ignore/amend the return value from
2211                  * treat_directory(), and especially do not change it to return
2212                  * path_recurse as that can cause exponential slowdown.
2213                  * Instead, modify treat_directory() to return the right value.
2214                  */
2215                 strbuf_addch(path, '/');
2216                 return treat_directory(dir, istate, untracked,
2217                                        path->buf, path->len,
2218                                        baselen, excluded, pathspec);
2219         case DT_REG:
2220         case DT_LNK:
2221                 if (pathspec &&
2222                     !match_pathspec(istate, pathspec, path->buf, path->len,
2223                                     0 /* prefix */, NULL /* seen */,
2224                                     0 /* is_dir */))
2225                         return path_none;
2226                 if (excluded)
2227                         return path_excluded;
2228                 return path_untracked;
2229         }
2230 }
2231
2232 static void add_untracked(struct untracked_cache_dir *dir, const char *name)
2233 {
2234         if (!dir)
2235                 return;
2236         ALLOC_GROW(dir->untracked, dir->untracked_nr + 1,
2237                    dir->untracked_alloc);
2238         dir->untracked[dir->untracked_nr++] = xstrdup(name);
2239 }
2240
2241 static int valid_cached_dir(struct dir_struct *dir,
2242                             struct untracked_cache_dir *untracked,
2243                             struct index_state *istate,
2244                             struct strbuf *path,
2245                             int check_only)
2246 {
2247         struct stat st;
2248
2249         if (!untracked)
2250                 return 0;
2251
2252         /*
2253          * With fsmonitor, we can trust the untracked cache's valid field.
2254          */
2255         refresh_fsmonitor(istate);
2256         if (!(dir->untracked->use_fsmonitor && untracked->valid)) {
2257                 if (lstat(path->len ? path->buf : ".", &st)) {
2258                         memset(&untracked->stat_data, 0, sizeof(untracked->stat_data));
2259                         return 0;
2260                 }
2261                 if (!untracked->valid ||
2262                         match_stat_data_racy(istate, &untracked->stat_data, &st)) {
2263                         fill_stat_data(&untracked->stat_data, &st);
2264                         return 0;
2265                 }
2266         }
2267
2268         if (untracked->check_only != !!check_only)
2269                 return 0;
2270
2271         /*
2272          * prep_exclude will be called eventually on this directory,
2273          * but it's called much later in last_matching_pattern(). We
2274          * need it now to determine the validity of the cache for this
2275          * path. The next calls will be nearly no-op, the way
2276          * prep_exclude() is designed.
2277          */
2278         if (path->len && path->buf[path->len - 1] != '/') {
2279                 strbuf_addch(path, '/');
2280                 prep_exclude(dir, istate, path->buf, path->len);
2281                 strbuf_setlen(path, path->len - 1);
2282         } else
2283                 prep_exclude(dir, istate, path->buf, path->len);
2284
2285         /* hopefully prep_exclude() haven't invalidated this entry... */
2286         return untracked->valid;
2287 }
2288
2289 static int open_cached_dir(struct cached_dir *cdir,
2290                            struct dir_struct *dir,
2291                            struct untracked_cache_dir *untracked,
2292                            struct index_state *istate,
2293                            struct strbuf *path,
2294                            int check_only)
2295 {
2296         const char *c_path;
2297
2298         memset(cdir, 0, sizeof(*cdir));
2299         cdir->untracked = untracked;
2300         if (valid_cached_dir(dir, untracked, istate, path, check_only))
2301                 return 0;
2302         c_path = path->len ? path->buf : ".";
2303         cdir->fdir = opendir(c_path);
2304         if (!cdir->fdir)
2305                 warning_errno(_("could not open directory '%s'"), c_path);
2306         if (dir->untracked) {
2307                 invalidate_directory(dir->untracked, untracked);
2308                 dir->untracked->dir_opened++;
2309         }
2310         if (!cdir->fdir)
2311                 return -1;
2312         return 0;
2313 }
2314
2315 static int read_cached_dir(struct cached_dir *cdir)
2316 {
2317         struct dirent *de;
2318
2319         if (cdir->fdir) {
2320                 de = readdir(cdir->fdir);
2321                 if (!de) {
2322                         cdir->d_name = NULL;
2323                         cdir->d_type = DT_UNKNOWN;
2324                         return -1;
2325                 }
2326                 cdir->d_name = de->d_name;
2327                 cdir->d_type = DTYPE(de);
2328                 return 0;
2329         }
2330         while (cdir->nr_dirs < cdir->untracked->dirs_nr) {
2331                 struct untracked_cache_dir *d = cdir->untracked->dirs[cdir->nr_dirs];
2332                 if (!d->recurse) {
2333                         cdir->nr_dirs++;
2334                         continue;
2335                 }
2336                 cdir->ucd = d;
2337                 cdir->nr_dirs++;
2338                 return 0;
2339         }
2340         cdir->ucd = NULL;
2341         if (cdir->nr_files < cdir->untracked->untracked_nr) {
2342                 struct untracked_cache_dir *d = cdir->untracked;
2343                 cdir->file = d->untracked[cdir->nr_files++];
2344                 return 0;
2345         }
2346         return -1;
2347 }
2348
2349 static void close_cached_dir(struct cached_dir *cdir)
2350 {
2351         if (cdir->fdir)
2352                 closedir(cdir->fdir);
2353         /*
2354          * We have gone through this directory and found no untracked
2355          * entries. Mark it valid.
2356          */
2357         if (cdir->untracked) {
2358                 cdir->untracked->valid = 1;
2359                 cdir->untracked->recurse = 1;
2360         }
2361 }
2362
2363 static void add_path_to_appropriate_result_list(struct dir_struct *dir,
2364         struct untracked_cache_dir *untracked,
2365         struct cached_dir *cdir,
2366         struct index_state *istate,
2367         struct strbuf *path,
2368         int baselen,
2369         const struct pathspec *pathspec,
2370         enum path_treatment state)
2371 {
2372         /* add the path to the appropriate result list */
2373         switch (state) {
2374         case path_excluded:
2375                 if (dir->flags & DIR_SHOW_IGNORED)
2376                         dir_add_name(dir, istate, path->buf, path->len);
2377                 else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
2378                         ((dir->flags & DIR_COLLECT_IGNORED) &&
2379                         exclude_matches_pathspec(path->buf, path->len,
2380                                                  pathspec)))
2381                         dir_add_ignored(dir, istate, path->buf, path->len);
2382                 break;
2383
2384         case path_untracked:
2385                 if (dir->flags & DIR_SHOW_IGNORED)
2386                         break;
2387                 dir_add_name(dir, istate, path->buf, path->len);
2388                 if (cdir->fdir)
2389                         add_untracked(untracked, path->buf + baselen);
2390                 break;
2391
2392         default:
2393                 break;
2394         }
2395 }
2396
2397 /*
2398  * Read a directory tree. We currently ignore anything but
2399  * directories, regular files and symlinks. That's because git
2400  * doesn't handle them at all yet. Maybe that will change some
2401  * day.
2402  *
2403  * Also, we ignore the name ".git" (even if it is not a directory).
2404  * That likely will not change.
2405  *
2406  * If 'stop_at_first_file' is specified, 'path_excluded' is returned
2407  * to signal that a file was found. This is the least significant value that
2408  * indicates that a file was encountered that does not depend on the order of
2409  * whether an untracked or excluded path was encountered first.
2410  *
2411  * Returns the most significant path_treatment value encountered in the scan.
2412  * If 'stop_at_first_file' is specified, `path_excluded` is the most
2413  * significant path_treatment value that will be returned.
2414  */
2415
2416 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
2417         struct index_state *istate, const char *base, int baselen,
2418         struct untracked_cache_dir *untracked, int check_only,
2419         int stop_at_first_file, const struct pathspec *pathspec)
2420 {
2421         /*
2422          * WARNING: Do NOT recurse unless path_recurse is returned from
2423          *          treat_path().  Recursing on any other return value
2424          *          can result in exponential slowdown.
2425          */
2426         struct cached_dir cdir;
2427         enum path_treatment state, subdir_state, dir_state = path_none;
2428         struct strbuf path = STRBUF_INIT;
2429
2430         strbuf_add(&path, base, baselen);
2431
2432         if (open_cached_dir(&cdir, dir, untracked, istate, &path, check_only))
2433                 goto out;
2434
2435         if (untracked)
2436                 untracked->check_only = !!check_only;
2437
2438         while (!read_cached_dir(&cdir)) {
2439                 /* check how the file or directory should be treated */
2440                 state = treat_path(dir, untracked, &cdir, istate, &path,
2441                                    baselen, pathspec);
2442
2443                 if (state > dir_state)
2444                         dir_state = state;
2445
2446                 /* recurse into subdir if instructed by treat_path */
2447                 if (state == path_recurse) {
2448                         struct untracked_cache_dir *ud;
2449                         ud = lookup_untracked(dir->untracked, untracked,
2450                                               path.buf + baselen,
2451                                               path.len - baselen);
2452                         subdir_state =
2453                                 read_directory_recursive(dir, istate, path.buf,
2454                                                          path.len, ud,
2455                                                          check_only, stop_at_first_file, pathspec);
2456                         if (subdir_state > dir_state)
2457                                 dir_state = subdir_state;
2458
2459                         if (pathspec &&
2460                             !match_pathspec(istate, pathspec, path.buf, path.len,
2461                                             0 /* prefix */, NULL,
2462                                             0 /* do NOT special case dirs */))
2463                                 state = path_none;
2464                 }
2465
2466                 if (check_only) {
2467                         if (stop_at_first_file) {
2468                                 /*
2469                                  * If stopping at first file, then
2470                                  * signal that a file was found by
2471                                  * returning `path_excluded`. This is
2472                                  * to return a consistent value
2473                                  * regardless of whether an ignored or
2474                                  * excluded file happened to be
2475                                  * encountered 1st.
2476                                  *
2477                                  * In current usage, the
2478                                  * `stop_at_first_file` is passed when
2479                                  * an ancestor directory has matched
2480                                  * an exclude pattern, so any found
2481                                  * files will be excluded.
2482                                  */
2483                                 if (dir_state >= path_excluded) {
2484                                         dir_state = path_excluded;
2485                                         break;
2486                                 }
2487                         }
2488
2489                         /* abort early if maximum state has been reached */
2490                         if (dir_state == path_untracked) {
2491                                 if (cdir.fdir)
2492                                         add_untracked(untracked, path.buf + baselen);
2493                                 break;
2494                         }
2495                         /* skip the add_path_to_appropriate_result_list() */
2496                         continue;
2497                 }
2498
2499                 add_path_to_appropriate_result_list(dir, untracked, &cdir,
2500                                                     istate, &path, baselen,
2501                                                     pathspec, state);
2502         }
2503         close_cached_dir(&cdir);
2504  out:
2505         strbuf_release(&path);
2506
2507         return dir_state;
2508 }
2509
2510 int cmp_dir_entry(const void *p1, const void *p2)
2511 {
2512         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
2513         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
2514
2515         return name_compare(e1->name, e1->len, e2->name, e2->len);
2516 }
2517
2518 /* check if *out lexically strictly contains *in */
2519 int check_dir_entry_contains(const struct dir_entry *out, const struct dir_entry *in)
2520 {
2521         return (out->len < in->len) &&
2522                 (out->name[out->len - 1] == '/') &&
2523                 !memcmp(out->name, in->name, out->len);
2524 }
2525
2526 static int treat_leading_path(struct dir_struct *dir,
2527                               struct index_state *istate,
2528                               const char *path, int len,
2529                               const struct pathspec *pathspec)
2530 {
2531         struct strbuf sb = STRBUF_INIT;
2532         struct strbuf subdir = STRBUF_INIT;
2533         int prevlen, baselen;
2534         const char *cp;
2535         struct cached_dir cdir;
2536         enum path_treatment state = path_none;
2537
2538         /*
2539          * For each directory component of path, we are going to check whether
2540          * that path is relevant given the pathspec.  For example, if path is
2541          *    foo/bar/baz/
2542          * then we will ask treat_path() whether we should go into foo, then
2543          * whether we should go into bar, then whether baz is relevant.
2544          * Checking each is important because e.g. if path is
2545          *    .git/info/
2546          * then we need to check .git to know we shouldn't traverse it.
2547          * If the return from treat_path() is:
2548          *    * path_none, for any path, we return false.
2549          *    * path_recurse, for all path components, we return true
2550          *    * <anything else> for some intermediate component, we make sure
2551          *        to add that path to the relevant list but return false
2552          *        signifying that we shouldn't recurse into it.
2553          */
2554
2555         while (len && path[len - 1] == '/')
2556                 len--;
2557         if (!len)
2558                 return 1;
2559
2560         memset(&cdir, 0, sizeof(cdir));
2561         cdir.d_type = DT_DIR;
2562         baselen = 0;
2563         prevlen = 0;
2564         while (1) {
2565                 prevlen = baselen + !!baselen;
2566                 cp = path + prevlen;
2567                 cp = memchr(cp, '/', path + len - cp);
2568                 if (!cp)
2569                         baselen = len;
2570                 else
2571                         baselen = cp - path;
2572                 strbuf_reset(&sb);
2573                 strbuf_add(&sb, path, baselen);
2574                 if (!is_directory(sb.buf))
2575                         break;
2576                 strbuf_reset(&sb);
2577                 strbuf_add(&sb, path, prevlen);
2578                 strbuf_reset(&subdir);
2579                 strbuf_add(&subdir, path+prevlen, baselen-prevlen);
2580                 cdir.d_name = subdir.buf;
2581                 state = treat_path(dir, NULL, &cdir, istate, &sb, prevlen, pathspec);
2582
2583                 if (state != path_recurse)
2584                         break; /* do not recurse into it */
2585                 if (len <= baselen)
2586                         break; /* finished checking */
2587         }
2588         add_path_to_appropriate_result_list(dir, NULL, &cdir, istate,
2589                                             &sb, baselen, pathspec,
2590                                             state);
2591
2592         strbuf_release(&subdir);
2593         strbuf_release(&sb);
2594         return state == path_recurse;
2595 }
2596
2597 static const char *get_ident_string(void)
2598 {
2599         static struct strbuf sb = STRBUF_INIT;
2600         struct utsname uts;
2601
2602         if (sb.len)
2603                 return sb.buf;
2604         if (uname(&uts) < 0)
2605                 die_errno(_("failed to get kernel name and information"));
2606         strbuf_addf(&sb, "Location %s, system %s", get_git_work_tree(),
2607                     uts.sysname);
2608         return sb.buf;
2609 }
2610
2611 static int ident_in_untracked(const struct untracked_cache *uc)
2612 {
2613         /*
2614          * Previous git versions may have saved many NUL separated
2615          * strings in the "ident" field, but it is insane to manage
2616          * many locations, so just take care of the first one.
2617          */
2618
2619         return !strcmp(uc->ident.buf, get_ident_string());
2620 }
2621
2622 static void set_untracked_ident(struct untracked_cache *uc)
2623 {
2624         strbuf_reset(&uc->ident);
2625         strbuf_addstr(&uc->ident, get_ident_string());
2626
2627         /*
2628          * This strbuf used to contain a list of NUL separated
2629          * strings, so save NUL too for backward compatibility.
2630          */
2631         strbuf_addch(&uc->ident, 0);
2632 }
2633
2634 static void new_untracked_cache(struct index_state *istate)
2635 {
2636         struct untracked_cache *uc = xcalloc(1, sizeof(*uc));
2637         strbuf_init(&uc->ident, 100);
2638         uc->exclude_per_dir = ".gitignore";
2639         /* should be the same flags used by git-status */
2640         uc->dir_flags = DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES;
2641         set_untracked_ident(uc);
2642         istate->untracked = uc;
2643         istate->cache_changed |= UNTRACKED_CHANGED;
2644 }
2645
2646 void add_untracked_cache(struct index_state *istate)
2647 {
2648         if (!istate->untracked) {
2649                 new_untracked_cache(istate);
2650         } else {
2651                 if (!ident_in_untracked(istate->untracked)) {
2652                         free_untracked_cache(istate->untracked);
2653                         new_untracked_cache(istate);
2654                 }
2655         }
2656 }
2657
2658 void remove_untracked_cache(struct index_state *istate)
2659 {
2660         if (istate->untracked) {
2661                 free_untracked_cache(istate->untracked);
2662                 istate->untracked = NULL;
2663                 istate->cache_changed |= UNTRACKED_CHANGED;
2664         }
2665 }
2666
2667 static struct untracked_cache_dir *validate_untracked_cache(struct dir_struct *dir,
2668                                                       int base_len,
2669                                                       const struct pathspec *pathspec)
2670 {
2671         struct untracked_cache_dir *root;
2672         static int untracked_cache_disabled = -1;
2673
2674         if (!dir->untracked)
2675                 return NULL;
2676         if (untracked_cache_disabled < 0)
2677                 untracked_cache_disabled = git_env_bool("GIT_DISABLE_UNTRACKED_CACHE", 0);
2678         if (untracked_cache_disabled)
2679                 return NULL;
2680
2681         /*
2682          * We only support $GIT_DIR/info/exclude and core.excludesfile
2683          * as the global ignore rule files. Any other additions
2684          * (e.g. from command line) invalidate the cache. This
2685          * condition also catches running setup_standard_excludes()
2686          * before setting dir->untracked!
2687          */
2688         if (dir->unmanaged_exclude_files)
2689                 return NULL;
2690
2691         /*
2692          * Optimize for the main use case only: whole-tree git
2693          * status. More work involved in treat_leading_path() if we
2694          * use cache on just a subset of the worktree. pathspec
2695          * support could make the matter even worse.
2696          */
2697         if (base_len || (pathspec && pathspec->nr))
2698                 return NULL;
2699
2700         /* Different set of flags may produce different results */
2701         if (dir->flags != dir->untracked->dir_flags ||
2702             /*
2703              * See treat_directory(), case index_nonexistent. Without
2704              * this flag, we may need to also cache .git file content
2705              * for the resolve_gitlink_ref() call, which we don't.
2706              */
2707             !(dir->flags & DIR_SHOW_OTHER_DIRECTORIES) ||
2708             /* We don't support collecting ignore files */
2709             (dir->flags & (DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO |
2710                            DIR_COLLECT_IGNORED)))
2711                 return NULL;
2712
2713         /*
2714          * If we use .gitignore in the cache and now you change it to
2715          * .gitexclude, everything will go wrong.
2716          */
2717         if (dir->exclude_per_dir != dir->untracked->exclude_per_dir &&
2718             strcmp(dir->exclude_per_dir, dir->untracked->exclude_per_dir))
2719                 return NULL;
2720
2721         /*
2722          * EXC_CMDL is not considered in the cache. If people set it,
2723          * skip the cache.
2724          */
2725         if (dir->exclude_list_group[EXC_CMDL].nr)
2726                 return NULL;
2727
2728         if (!ident_in_untracked(dir->untracked)) {
2729                 warning(_("untracked cache is disabled on this system or location"));
2730                 return NULL;
2731         }
2732
2733         if (!dir->untracked->root) {
2734                 const int len = sizeof(*dir->untracked->root);
2735                 dir->untracked->root = xmalloc(len);
2736                 memset(dir->untracked->root, 0, len);
2737         }
2738
2739         /* Validate $GIT_DIR/info/exclude and core.excludesfile */
2740         root = dir->untracked->root;
2741         if (!oideq(&dir->ss_info_exclude.oid,
2742                    &dir->untracked->ss_info_exclude.oid)) {
2743                 invalidate_gitignore(dir->untracked, root);
2744                 dir->untracked->ss_info_exclude = dir->ss_info_exclude;
2745         }
2746         if (!oideq(&dir->ss_excludes_file.oid,
2747                    &dir->untracked->ss_excludes_file.oid)) {
2748                 invalidate_gitignore(dir->untracked, root);
2749                 dir->untracked->ss_excludes_file = dir->ss_excludes_file;
2750         }
2751
2752         /* Make sure this directory is not dropped out at saving phase */
2753         root->recurse = 1;
2754         return root;
2755 }
2756
2757 int read_directory(struct dir_struct *dir, struct index_state *istate,
2758                    const char *path, int len, const struct pathspec *pathspec)
2759 {
2760         struct untracked_cache_dir *untracked;
2761
2762         trace_performance_enter();
2763
2764         if (has_symlink_leading_path(path, len)) {
2765                 trace_performance_leave("read directory %.*s", len, path);
2766                 return dir->nr;
2767         }
2768
2769         untracked = validate_untracked_cache(dir, len, pathspec);
2770         if (!untracked)
2771                 /*
2772                  * make sure untracked cache code path is disabled,
2773                  * e.g. prep_exclude()
2774                  */
2775                 dir->untracked = NULL;
2776         if (!len || treat_leading_path(dir, istate, path, len, pathspec))
2777                 read_directory_recursive(dir, istate, path, len, untracked, 0, 0, pathspec);
2778         QSORT(dir->entries, dir->nr, cmp_dir_entry);
2779         QSORT(dir->ignored, dir->ignored_nr, cmp_dir_entry);
2780
2781         trace_performance_leave("read directory %.*s", len, path);
2782         if (dir->untracked) {
2783                 static int force_untracked_cache = -1;
2784                 static struct trace_key trace_untracked_stats = TRACE_KEY_INIT(UNTRACKED_STATS);
2785
2786                 if (force_untracked_cache < 0)
2787                         force_untracked_cache =
2788                                 git_env_bool("GIT_FORCE_UNTRACKED_CACHE", 0);
2789                 trace_printf_key(&trace_untracked_stats,
2790                                  "node creation: %u\n"
2791                                  "gitignore invalidation: %u\n"
2792                                  "directory invalidation: %u\n"
2793                                  "opendir: %u\n",
2794                                  dir->untracked->dir_created,
2795                                  dir->untracked->gitignore_invalidated,
2796                                  dir->untracked->dir_invalidated,
2797                                  dir->untracked->dir_opened);
2798                 if (force_untracked_cache &&
2799                         dir->untracked == istate->untracked &&
2800                     (dir->untracked->dir_opened ||
2801                      dir->untracked->gitignore_invalidated ||
2802                      dir->untracked->dir_invalidated))
2803                         istate->cache_changed |= UNTRACKED_CHANGED;
2804                 if (dir->untracked != istate->untracked) {
2805                         FREE_AND_NULL(dir->untracked);
2806                 }
2807         }
2808         return dir->nr;
2809 }
2810
2811 int file_exists(const char *f)
2812 {
2813         struct stat sb;
2814         return lstat(f, &sb) == 0;
2815 }
2816
2817 int repo_file_exists(struct repository *repo, const char *path)
2818 {
2819         if (repo != the_repository)
2820                 BUG("do not know how to check file existence in arbitrary repo");
2821
2822         return file_exists(path);
2823 }
2824
2825 static int cmp_icase(char a, char b)
2826 {
2827         if (a == b)
2828                 return 0;
2829         if (ignore_case)
2830                 return toupper(a) - toupper(b);
2831         return a - b;
2832 }
2833
2834 /*
2835  * Given two normalized paths (a trailing slash is ok), if subdir is
2836  * outside dir, return -1.  Otherwise return the offset in subdir that
2837  * can be used as relative path to dir.
2838  */
2839 int dir_inside_of(const char *subdir, const char *dir)
2840 {
2841         int offset = 0;
2842
2843         assert(dir && subdir && *dir && *subdir);
2844
2845         while (*dir && *subdir && !cmp_icase(*dir, *subdir)) {
2846                 dir++;
2847                 subdir++;
2848                 offset++;
2849         }
2850
2851         /* hel[p]/me vs hel[l]/yeah */
2852         if (*dir && *subdir)
2853                 return -1;
2854
2855         if (!*subdir)
2856                 return !*dir ? offset : -1; /* same dir */
2857
2858         /* foo/[b]ar vs foo/[] */
2859         if (is_dir_sep(dir[-1]))
2860                 return is_dir_sep(subdir[-1]) ? offset : -1;
2861
2862         /* foo[/]bar vs foo[] */
2863         return is_dir_sep(*subdir) ? offset + 1 : -1;
2864 }
2865
2866 int is_inside_dir(const char *dir)
2867 {
2868         char *cwd;
2869         int rc;
2870
2871         if (!dir)
2872                 return 0;
2873
2874         cwd = xgetcwd();
2875         rc = (dir_inside_of(cwd, dir) >= 0);
2876         free(cwd);
2877         return rc;
2878 }
2879
2880 int is_empty_dir(const char *path)
2881 {
2882         DIR *dir = opendir(path);
2883         struct dirent *e;
2884         int ret = 1;
2885
2886         if (!dir)
2887                 return 0;
2888
2889         while ((e = readdir(dir)) != NULL)
2890                 if (!is_dot_or_dotdot(e->d_name)) {
2891                         ret = 0;
2892                         break;
2893                 }
2894
2895         closedir(dir);
2896         return ret;
2897 }
2898
2899 static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
2900 {
2901         DIR *dir;
2902         struct dirent *e;
2903         int ret = 0, original_len = path->len, len, kept_down = 0;
2904         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
2905         int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
2906         struct object_id submodule_head;
2907
2908         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
2909             !resolve_gitlink_ref(path->buf, "HEAD", &submodule_head)) {
2910                 /* Do not descend and nuke a nested git work tree. */
2911                 if (kept_up)
2912                         *kept_up = 1;
2913                 return 0;
2914         }
2915
2916         flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
2917         dir = opendir(path->buf);
2918         if (!dir) {
2919                 if (errno == ENOENT)
2920                         return keep_toplevel ? -1 : 0;
2921                 else if (errno == EACCES && !keep_toplevel)
2922                         /*
2923                          * An empty dir could be removable even if it
2924                          * is unreadable:
2925                          */
2926                         return rmdir(path->buf);
2927                 else
2928                         return -1;
2929         }
2930         strbuf_complete(path, '/');
2931
2932         len = path->len;
2933         while ((e = readdir(dir)) != NULL) {
2934                 struct stat st;
2935                 if (is_dot_or_dotdot(e->d_name))
2936                         continue;
2937
2938                 strbuf_setlen(path, len);
2939                 strbuf_addstr(path, e->d_name);
2940                 if (lstat(path->buf, &st)) {
2941                         if (errno == ENOENT)
2942                                 /*
2943                                  * file disappeared, which is what we
2944                                  * wanted anyway
2945                                  */
2946                                 continue;
2947                         /* fall through */
2948                 } else if (S_ISDIR(st.st_mode)) {
2949                         if (!remove_dir_recurse(path, flag, &kept_down))
2950                                 continue; /* happy */
2951                 } else if (!only_empty &&
2952                            (!unlink(path->buf) || errno == ENOENT)) {
2953                         continue; /* happy, too */
2954                 }
2955
2956                 /* path too long, stat fails, or non-directory still exists */
2957                 ret = -1;
2958                 break;
2959         }
2960         closedir(dir);
2961
2962         strbuf_setlen(path, original_len);
2963         if (!ret && !keep_toplevel && !kept_down)
2964                 ret = (!rmdir(path->buf) || errno == ENOENT) ? 0 : -1;
2965         else if (kept_up)
2966                 /*
2967                  * report the uplevel that it is not an error that we
2968                  * did not rmdir() our directory.
2969                  */
2970                 *kept_up = !ret;
2971         return ret;
2972 }
2973
2974 int remove_dir_recursively(struct strbuf *path, int flag)
2975 {
2976         return remove_dir_recurse(path, flag, NULL);
2977 }
2978
2979 static GIT_PATH_FUNC(git_path_info_exclude, "info/exclude")
2980
2981 void setup_standard_excludes(struct dir_struct *dir)
2982 {
2983         dir->exclude_per_dir = ".gitignore";
2984
2985         /* core.excludesfile defaulting to $XDG_CONFIG_HOME/git/ignore */
2986         if (!excludes_file)
2987                 excludes_file = xdg_config_home("ignore");
2988         if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
2989                 add_patterns_from_file_1(dir, excludes_file,
2990                                          dir->untracked ? &dir->ss_excludes_file : NULL);
2991
2992         /* per repository user preference */
2993         if (startup_info->have_repository) {
2994                 const char *path = git_path_info_exclude();
2995                 if (!access_or_warn(path, R_OK, 0))
2996                         add_patterns_from_file_1(dir, path,
2997                                                  dir->untracked ? &dir->ss_info_exclude : NULL);
2998         }
2999 }
3000
3001 int remove_path(const char *name)
3002 {
3003         char *slash;
3004
3005         if (unlink(name) && !is_missing_file_error(errno))
3006                 return -1;
3007
3008         slash = strrchr(name, '/');
3009         if (slash) {
3010                 char *dirs = xstrdup(name);
3011                 slash = dirs + (slash - name);
3012                 do {
3013                         *slash = '\0';
3014                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
3015                 free(dirs);
3016         }
3017         return 0;
3018 }
3019
3020 /*
3021  * Frees memory within dir which was allocated, and resets fields for further
3022  * use.  Does not free dir itself.
3023  */
3024 void dir_clear(struct dir_struct *dir)
3025 {
3026         int i, j;
3027         struct exclude_list_group *group;
3028         struct pattern_list *pl;
3029         struct exclude_stack *stk;
3030
3031         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
3032                 group = &dir->exclude_list_group[i];
3033                 for (j = 0; j < group->nr; j++) {
3034                         pl = &group->pl[j];
3035                         if (i == EXC_DIRS)
3036                                 free((char *)pl->src);
3037                         clear_pattern_list(pl);
3038                 }
3039                 free(group->pl);
3040         }
3041
3042         for (i = 0; i < dir->ignored_nr; i++)
3043                 free(dir->ignored[i]);
3044         for (i = 0; i < dir->nr; i++)
3045                 free(dir->entries[i]);
3046         free(dir->ignored);
3047         free(dir->entries);
3048
3049         stk = dir->exclude_stack;
3050         while (stk) {
3051                 struct exclude_stack *prev = stk->prev;
3052                 free(stk);
3053                 stk = prev;
3054         }
3055         strbuf_release(&dir->basebuf);
3056
3057         dir_init(dir);
3058 }
3059
3060 struct ondisk_untracked_cache {
3061         struct stat_data info_exclude_stat;
3062         struct stat_data excludes_file_stat;
3063         uint32_t dir_flags;
3064 };
3065
3066 #define ouc_offset(x) offsetof(struct ondisk_untracked_cache, x)
3067
3068 struct write_data {
3069         int index;         /* number of written untracked_cache_dir */
3070         struct ewah_bitmap *check_only; /* from untracked_cache_dir */
3071         struct ewah_bitmap *valid;      /* from untracked_cache_dir */
3072         struct ewah_bitmap *sha1_valid; /* set if exclude_sha1 is not null */
3073         struct strbuf out;
3074         struct strbuf sb_stat;
3075         struct strbuf sb_sha1;
3076 };
3077
3078 static void stat_data_to_disk(struct stat_data *to, const struct stat_data *from)
3079 {
3080         to->sd_ctime.sec  = htonl(from->sd_ctime.sec);
3081         to->sd_ctime.nsec = htonl(from->sd_ctime.nsec);
3082         to->sd_mtime.sec  = htonl(from->sd_mtime.sec);
3083         to->sd_mtime.nsec = htonl(from->sd_mtime.nsec);
3084         to->sd_dev        = htonl(from->sd_dev);
3085         to->sd_ino        = htonl(from->sd_ino);
3086         to->sd_uid        = htonl(from->sd_uid);
3087         to->sd_gid        = htonl(from->sd_gid);
3088         to->sd_size       = htonl(from->sd_size);
3089 }
3090
3091 static void write_one_dir(struct untracked_cache_dir *untracked,
3092                           struct write_data *wd)
3093 {
3094         struct stat_data stat_data;
3095         struct strbuf *out = &wd->out;
3096         unsigned char intbuf[16];
3097         unsigned int intlen, value;
3098         int i = wd->index++;
3099
3100         /*
3101          * untracked_nr should be reset whenever valid is clear, but
3102          * for safety..
3103          */
3104         if (!untracked->valid) {
3105                 untracked->untracked_nr = 0;
3106                 untracked->check_only = 0;
3107         }
3108
3109         if (untracked->check_only)
3110                 ewah_set(wd->check_only, i);
3111         if (untracked->valid) {
3112                 ewah_set(wd->valid, i);
3113                 stat_data_to_disk(&stat_data, &untracked->stat_data);
3114                 strbuf_add(&wd->sb_stat, &stat_data, sizeof(stat_data));
3115         }
3116         if (!is_null_oid(&untracked->exclude_oid)) {
3117                 ewah_set(wd->sha1_valid, i);
3118                 strbuf_add(&wd->sb_sha1, untracked->exclude_oid.hash,
3119                            the_hash_algo->rawsz);
3120         }
3121
3122         intlen = encode_varint(untracked->untracked_nr, intbuf);
3123         strbuf_add(out, intbuf, intlen);
3124
3125         /* skip non-recurse directories */
3126         for (i = 0, value = 0; i < untracked->dirs_nr; i++)
3127                 if (untracked->dirs[i]->recurse)
3128                         value++;
3129         intlen = encode_varint(value, intbuf);
3130         strbuf_add(out, intbuf, intlen);
3131
3132         strbuf_add(out, untracked->name, strlen(untracked->name) + 1);
3133
3134         for (i = 0; i < untracked->untracked_nr; i++)
3135                 strbuf_add(out, untracked->untracked[i],
3136                            strlen(untracked->untracked[i]) + 1);
3137
3138         for (i = 0; i < untracked->dirs_nr; i++)
3139                 if (untracked->dirs[i]->recurse)
3140                         write_one_dir(untracked->dirs[i], wd);
3141 }
3142
3143 void write_untracked_extension(struct strbuf *out, struct untracked_cache *untracked)
3144 {
3145         struct ondisk_untracked_cache *ouc;
3146         struct write_data wd;
3147         unsigned char varbuf[16];
3148         int varint_len;
3149         const unsigned hashsz = the_hash_algo->rawsz;
3150
3151         ouc = xcalloc(1, sizeof(*ouc));
3152         stat_data_to_disk(&ouc->info_exclude_stat, &untracked->ss_info_exclude.stat);
3153         stat_data_to_disk(&ouc->excludes_file_stat, &untracked->ss_excludes_file.stat);
3154         ouc->dir_flags = htonl(untracked->dir_flags);
3155
3156         varint_len = encode_varint(untracked->ident.len, varbuf);
3157         strbuf_add(out, varbuf, varint_len);
3158         strbuf_addbuf(out, &untracked->ident);
3159
3160         strbuf_add(out, ouc, sizeof(*ouc));
3161         strbuf_add(out, untracked->ss_info_exclude.oid.hash, hashsz);
3162         strbuf_add(out, untracked->ss_excludes_file.oid.hash, hashsz);
3163         strbuf_add(out, untracked->exclude_per_dir, strlen(untracked->exclude_per_dir) + 1);
3164         FREE_AND_NULL(ouc);
3165
3166         if (!untracked->root) {
3167                 varint_len = encode_varint(0, varbuf);
3168                 strbuf_add(out, varbuf, varint_len);
3169                 return;
3170         }
3171
3172         wd.index      = 0;
3173         wd.check_only = ewah_new();
3174         wd.valid      = ewah_new();
3175         wd.sha1_valid = ewah_new();
3176         strbuf_init(&wd.out, 1024);
3177         strbuf_init(&wd.sb_stat, 1024);
3178         strbuf_init(&wd.sb_sha1, 1024);
3179         write_one_dir(untracked->root, &wd);
3180
3181         varint_len = encode_varint(wd.index, varbuf);
3182         strbuf_add(out, varbuf, varint_len);
3183         strbuf_addbuf(out, &wd.out);
3184         ewah_serialize_strbuf(wd.valid, out);
3185         ewah_serialize_strbuf(wd.check_only, out);
3186         ewah_serialize_strbuf(wd.sha1_valid, out);
3187         strbuf_addbuf(out, &wd.sb_stat);
3188         strbuf_addbuf(out, &wd.sb_sha1);
3189         strbuf_addch(out, '\0'); /* safe guard for string lists */
3190
3191         ewah_free(wd.valid);
3192         ewah_free(wd.check_only);
3193         ewah_free(wd.sha1_valid);
3194         strbuf_release(&wd.out);
3195         strbuf_release(&wd.sb_stat);
3196         strbuf_release(&wd.sb_sha1);
3197 }
3198
3199 static void free_untracked(struct untracked_cache_dir *ucd)
3200 {
3201         int i;
3202         if (!ucd)
3203                 return;
3204         for (i = 0; i < ucd->dirs_nr; i++)
3205                 free_untracked(ucd->dirs[i]);
3206         for (i = 0; i < ucd->untracked_nr; i++)
3207                 free(ucd->untracked[i]);
3208         free(ucd->untracked);
3209         free(ucd->dirs);
3210         free(ucd);
3211 }
3212
3213 void free_untracked_cache(struct untracked_cache *uc)
3214 {
3215         if (uc)
3216                 free_untracked(uc->root);
3217         free(uc);
3218 }
3219
3220 struct read_data {
3221         int index;
3222         struct untracked_cache_dir **ucd;
3223         struct ewah_bitmap *check_only;
3224         struct ewah_bitmap *valid;
3225         struct ewah_bitmap *sha1_valid;
3226         const unsigned char *data;
3227         const unsigned char *end;
3228 };
3229
3230 static void stat_data_from_disk(struct stat_data *to, const unsigned char *data)
3231 {
3232         memcpy(to, data, sizeof(*to));
3233         to->sd_ctime.sec  = ntohl(to->sd_ctime.sec);
3234         to->sd_ctime.nsec = ntohl(to->sd_ctime.nsec);
3235         to->sd_mtime.sec  = ntohl(to->sd_mtime.sec);
3236         to->sd_mtime.nsec = ntohl(to->sd_mtime.nsec);
3237         to->sd_dev        = ntohl(to->sd_dev);
3238         to->sd_ino        = ntohl(to->sd_ino);
3239         to->sd_uid        = ntohl(to->sd_uid);
3240         to->sd_gid        = ntohl(to->sd_gid);
3241         to->sd_size       = ntohl(to->sd_size);
3242 }
3243
3244 static int read_one_dir(struct untracked_cache_dir **untracked_,
3245                         struct read_data *rd)
3246 {
3247         struct untracked_cache_dir ud, *untracked;
3248         const unsigned char *data = rd->data, *end = rd->end;
3249         const unsigned char *eos;
3250         unsigned int value;
3251         int i;
3252
3253         memset(&ud, 0, sizeof(ud));
3254
3255         value = decode_varint(&data);
3256         if (data > end)
3257                 return -1;
3258         ud.recurse         = 1;
3259         ud.untracked_alloc = value;
3260         ud.untracked_nr    = value;
3261         if (ud.untracked_nr)
3262                 ALLOC_ARRAY(ud.untracked, ud.untracked_nr);
3263
3264         ud.dirs_alloc = ud.dirs_nr = decode_varint(&data);
3265         if (data > end)
3266                 return -1;
3267         ALLOC_ARRAY(ud.dirs, ud.dirs_nr);
3268
3269         eos = memchr(data, '\0', end - data);
3270         if (!eos || eos == end)
3271                 return -1;
3272
3273         *untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), eos - data, 1));
3274         memcpy(untracked, &ud, sizeof(ud));
3275         memcpy(untracked->name, data, eos - data + 1);
3276         data = eos + 1;
3277
3278         for (i = 0; i < untracked->untracked_nr; i++) {
3279                 eos = memchr(data, '\0', end - data);
3280                 if (!eos || eos == end)
3281                         return -1;
3282                 untracked->untracked[i] = xmemdupz(data, eos - data);
3283                 data = eos + 1;
3284         }
3285
3286         rd->ucd[rd->index++] = untracked;
3287         rd->data = data;
3288
3289         for (i = 0; i < untracked->dirs_nr; i++) {
3290                 if (read_one_dir(untracked->dirs + i, rd) < 0)
3291                         return -1;
3292         }
3293         return 0;
3294 }
3295
3296 static void set_check_only(size_t pos, void *cb)
3297 {
3298         struct read_data *rd = cb;
3299         struct untracked_cache_dir *ud = rd->ucd[pos];
3300         ud->check_only = 1;
3301 }
3302
3303 static void read_stat(size_t pos, void *cb)
3304 {
3305         struct read_data *rd = cb;
3306         struct untracked_cache_dir *ud = rd->ucd[pos];
3307         if (rd->data + sizeof(struct stat_data) > rd->end) {
3308                 rd->data = rd->end + 1;
3309                 return;
3310         }
3311         stat_data_from_disk(&ud->stat_data, rd->data);
3312         rd->data += sizeof(struct stat_data);
3313         ud->valid = 1;
3314 }
3315
3316 static void read_oid(size_t pos, void *cb)
3317 {
3318         struct read_data *rd = cb;
3319         struct untracked_cache_dir *ud = rd->ucd[pos];
3320         if (rd->data + the_hash_algo->rawsz > rd->end) {
3321                 rd->data = rd->end + 1;
3322                 return;
3323         }
3324         hashcpy(ud->exclude_oid.hash, rd->data);
3325         rd->data += the_hash_algo->rawsz;
3326 }
3327
3328 static void load_oid_stat(struct oid_stat *oid_stat, const unsigned char *data,
3329                           const unsigned char *sha1)
3330 {
3331         stat_data_from_disk(&oid_stat->stat, data);
3332         hashcpy(oid_stat->oid.hash, sha1);
3333         oid_stat->valid = 1;
3334 }
3335
3336 struct untracked_cache *read_untracked_extension(const void *data, unsigned long sz)
3337 {
3338         struct untracked_cache *uc;
3339         struct read_data rd;
3340         const unsigned char *next = data, *end = (const unsigned char *)data + sz;
3341         const char *ident;
3342         int ident_len;
3343         ssize_t len;
3344         const char *exclude_per_dir;
3345         const unsigned hashsz = the_hash_algo->rawsz;
3346         const unsigned offset = sizeof(struct ondisk_untracked_cache);
3347         const unsigned exclude_per_dir_offset = offset + 2 * hashsz;
3348
3349         if (sz <= 1 || end[-1] != '\0')
3350                 return NULL;
3351         end--;
3352
3353         ident_len = decode_varint(&next);
3354         if (next + ident_len > end)
3355                 return NULL;
3356         ident = (const char *)next;
3357         next += ident_len;
3358
3359         if (next + exclude_per_dir_offset + 1 > end)
3360                 return NULL;
3361
3362         uc = xcalloc(1, sizeof(*uc));
3363         strbuf_init(&uc->ident, ident_len);
3364         strbuf_add(&uc->ident, ident, ident_len);
3365         load_oid_stat(&uc->ss_info_exclude,
3366                       next + ouc_offset(info_exclude_stat),
3367                       next + offset);
3368         load_oid_stat(&uc->ss_excludes_file,
3369                       next + ouc_offset(excludes_file_stat),
3370                       next + offset + hashsz);
3371         uc->dir_flags = get_be32(next + ouc_offset(dir_flags));
3372         exclude_per_dir = (const char *)next + exclude_per_dir_offset;
3373         uc->exclude_per_dir = xstrdup(exclude_per_dir);
3374         /* NUL after exclude_per_dir is covered by sizeof(*ouc) */
3375         next += exclude_per_dir_offset + strlen(exclude_per_dir) + 1;
3376         if (next >= end)
3377                 goto done2;
3378
3379         len = decode_varint(&next);
3380         if (next > end || len == 0)
3381                 goto done2;
3382
3383         rd.valid      = ewah_new();
3384         rd.check_only = ewah_new();
3385         rd.sha1_valid = ewah_new();
3386         rd.data       = next;
3387         rd.end        = end;
3388         rd.index      = 0;
3389         ALLOC_ARRAY(rd.ucd, len);
3390
3391         if (read_one_dir(&uc->root, &rd) || rd.index != len)
3392                 goto done;
3393
3394         next = rd.data;
3395         len = ewah_read_mmap(rd.valid, next, end - next);
3396         if (len < 0)
3397                 goto done;
3398
3399         next += len;
3400         len = ewah_read_mmap(rd.check_only, next, end - next);
3401         if (len < 0)
3402                 goto done;
3403
3404         next += len;
3405         len = ewah_read_mmap(rd.sha1_valid, next, end - next);
3406         if (len < 0)
3407                 goto done;
3408
3409         ewah_each_bit(rd.check_only, set_check_only, &rd);
3410         rd.data = next + len;
3411         ewah_each_bit(rd.valid, read_stat, &rd);
3412         ewah_each_bit(rd.sha1_valid, read_oid, &rd);
3413         next = rd.data;
3414
3415 done:
3416         free(rd.ucd);
3417         ewah_free(rd.valid);
3418         ewah_free(rd.check_only);
3419         ewah_free(rd.sha1_valid);
3420 done2:
3421         if (next != end) {
3422                 free_untracked_cache(uc);
3423                 uc = NULL;
3424         }
3425         return uc;
3426 }
3427
3428 static void invalidate_one_directory(struct untracked_cache *uc,
3429                                      struct untracked_cache_dir *ucd)
3430 {
3431         uc->dir_invalidated++;
3432         ucd->valid = 0;
3433         ucd->untracked_nr = 0;
3434 }
3435
3436 /*
3437  * Normally when an entry is added or removed from a directory,
3438  * invalidating that directory is enough. No need to touch its
3439  * ancestors. When a directory is shown as "foo/bar/" in git-status
3440  * however, deleting or adding an entry may have cascading effect.
3441  *
3442  * Say the "foo/bar/file" has become untracked, we need to tell the
3443  * untracked_cache_dir of "foo" that "bar/" is not an untracked
3444  * directory any more (because "bar" is managed by foo as an untracked
3445  * "file").
3446  *
3447  * Similarly, if "foo/bar/file" moves from untracked to tracked and it
3448  * was the last untracked entry in the entire "foo", we should show
3449  * "foo/" instead. Which means we have to invalidate past "bar" up to
3450  * "foo".
3451  *
3452  * This function traverses all directories from root to leaf. If there
3453  * is a chance of one of the above cases happening, we invalidate back
3454  * to root. Otherwise we just invalidate the leaf. There may be a more
3455  * sophisticated way than checking for SHOW_OTHER_DIRECTORIES to
3456  * detect these cases and avoid unnecessary invalidation, for example,
3457  * checking for the untracked entry named "bar/" in "foo", but for now
3458  * stick to something safe and simple.
3459  */
3460 static int invalidate_one_component(struct untracked_cache *uc,
3461                                     struct untracked_cache_dir *dir,
3462                                     const char *path, int len)
3463 {
3464         const char *rest = strchr(path, '/');
3465
3466         if (rest) {
3467                 int component_len = rest - path;
3468                 struct untracked_cache_dir *d =
3469                         lookup_untracked(uc, dir, path, component_len);
3470                 int ret =
3471                         invalidate_one_component(uc, d, rest + 1,
3472                                                  len - (component_len + 1));
3473                 if (ret)
3474                         invalidate_one_directory(uc, dir);
3475                 return ret;
3476         }
3477
3478         invalidate_one_directory(uc, dir);
3479         return uc->dir_flags & DIR_SHOW_OTHER_DIRECTORIES;
3480 }
3481
3482 void untracked_cache_invalidate_path(struct index_state *istate,
3483                                      const char *path, int safe_path)
3484 {
3485         if (!istate->untracked || !istate->untracked->root)
3486                 return;
3487         if (!safe_path && !verify_path(path, 0))
3488                 return;
3489         invalidate_one_component(istate->untracked, istate->untracked->root,
3490                                  path, strlen(path));
3491 }
3492
3493 void untracked_cache_remove_from_index(struct index_state *istate,
3494                                        const char *path)
3495 {
3496         untracked_cache_invalidate_path(istate, path, 1);
3497 }
3498
3499 void untracked_cache_add_to_index(struct index_state *istate,
3500                                   const char *path)
3501 {
3502         untracked_cache_invalidate_path(istate, path, 1);
3503 }
3504
3505 static void connect_wt_gitdir_in_nested(const char *sub_worktree,
3506                                         const char *sub_gitdir)
3507 {
3508         int i;
3509         struct repository subrepo;
3510         struct strbuf sub_wt = STRBUF_INIT;
3511         struct strbuf sub_gd = STRBUF_INIT;
3512
3513         const struct submodule *sub;
3514
3515         /* If the submodule has no working tree, we can ignore it. */
3516         if (repo_init(&subrepo, sub_gitdir, sub_worktree))
3517                 return;
3518
3519         if (repo_read_index(&subrepo) < 0)
3520                 die(_("index file corrupt in repo %s"), subrepo.gitdir);
3521
3522         for (i = 0; i < subrepo.index->cache_nr; i++) {
3523                 const struct cache_entry *ce = subrepo.index->cache[i];
3524
3525                 if (!S_ISGITLINK(ce->ce_mode))
3526                         continue;
3527
3528                 while (i + 1 < subrepo.index->cache_nr &&
3529                        !strcmp(ce->name, subrepo.index->cache[i + 1]->name))
3530                         /*
3531                          * Skip entries with the same name in different stages
3532                          * to make sure an entry is returned only once.
3533                          */
3534                         i++;
3535
3536                 sub = submodule_from_path(&subrepo, &null_oid, ce->name);
3537                 if (!sub || !is_submodule_active(&subrepo, ce->name))
3538                         /* .gitmodules broken or inactive sub */
3539                         continue;
3540
3541                 strbuf_reset(&sub_wt);
3542                 strbuf_reset(&sub_gd);
3543                 strbuf_addf(&sub_wt, "%s/%s", sub_worktree, sub->path);
3544                 strbuf_addf(&sub_gd, "%s/modules/%s", sub_gitdir, sub->name);
3545
3546                 connect_work_tree_and_git_dir(sub_wt.buf, sub_gd.buf, 1);
3547         }
3548         strbuf_release(&sub_wt);
3549         strbuf_release(&sub_gd);
3550         repo_clear(&subrepo);
3551 }
3552
3553 void connect_work_tree_and_git_dir(const char *work_tree_,
3554                                    const char *git_dir_,
3555                                    int recurse_into_nested)
3556 {
3557         struct strbuf gitfile_sb = STRBUF_INIT;
3558         struct strbuf cfg_sb = STRBUF_INIT;
3559         struct strbuf rel_path = STRBUF_INIT;
3560         char *git_dir, *work_tree;
3561
3562         /* Prepare .git file */
3563         strbuf_addf(&gitfile_sb, "%s/.git", work_tree_);
3564         if (safe_create_leading_directories_const(gitfile_sb.buf))
3565                 die(_("could not create directories for %s"), gitfile_sb.buf);
3566
3567         /* Prepare config file */
3568         strbuf_addf(&cfg_sb, "%s/config", git_dir_);
3569         if (safe_create_leading_directories_const(cfg_sb.buf))
3570                 die(_("could not create directories for %s"), cfg_sb.buf);
3571
3572         git_dir = real_pathdup(git_dir_, 1);
3573         work_tree = real_pathdup(work_tree_, 1);
3574
3575         /* Write .git file */
3576         write_file(gitfile_sb.buf, "gitdir: %s",
3577                    relative_path(git_dir, work_tree, &rel_path));
3578         /* Update core.worktree setting */
3579         git_config_set_in_file(cfg_sb.buf, "core.worktree",
3580                                relative_path(work_tree, git_dir, &rel_path));
3581
3582         strbuf_release(&gitfile_sb);
3583         strbuf_release(&cfg_sb);
3584         strbuf_release(&rel_path);
3585
3586         if (recurse_into_nested)
3587                 connect_wt_gitdir_in_nested(work_tree, git_dir);
3588
3589         free(work_tree);
3590         free(git_dir);
3591 }
3592
3593 /*
3594  * Migrate the git directory of the given path from old_git_dir to new_git_dir.
3595  */
3596 void relocate_gitdir(const char *path, const char *old_git_dir, const char *new_git_dir)
3597 {
3598         if (rename(old_git_dir, new_git_dir) < 0)
3599                 die_errno(_("could not migrate git directory from '%s' to '%s'"),
3600                         old_git_dir, new_git_dir);
3601
3602         connect_work_tree_and_git_dir(path, new_git_dir, 0);
3603 }