Merge branch 'ds/maintenance-part-1'
[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 "ss" is not NULL, compute SHA-1 of the exclude file and fill
1044  * stat data from disk (only valid if add_patterns returns zero). If
1045  * ss_valid is non-zero, "ss" 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, ss->sha1 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 untracked_cache_dir *untracked,
2109                                            struct cached_dir *cdir,
2110                                            struct index_state *istate,
2111                                            struct strbuf *path,
2112                                            int baselen,
2113                                            const struct pathspec *pathspec)
2114 {
2115         /*
2116          * WARNING: From this function, you can return path_recurse or you
2117          *          can call read_directory_recursive() (or neither), but
2118          *          you CAN'T DO BOTH.
2119          */
2120         strbuf_setlen(path, baselen);
2121         if (!cdir->ucd) {
2122                 strbuf_addstr(path, cdir->file);
2123                 return path_untracked;
2124         }
2125         strbuf_addstr(path, cdir->ucd->name);
2126         /* treat_one_path() does this before it calls treat_directory() */
2127         strbuf_complete(path, '/');
2128         if (cdir->ucd->check_only)
2129                 /*
2130                  * check_only is set as a result of treat_directory() getting
2131                  * to its bottom. Verify again the same set of directories
2132                  * with check_only set.
2133                  */
2134                 return read_directory_recursive(dir, istate, path->buf, path->len,
2135                                                 cdir->ucd, 1, 0, pathspec);
2136         /*
2137          * We get path_recurse in the first run when
2138          * directory_exists_in_index() returns index_nonexistent. We
2139          * are sure that new changes in the index does not impact the
2140          * outcome. Return now.
2141          */
2142         return path_recurse;
2143 }
2144
2145 static enum path_treatment treat_path(struct dir_struct *dir,
2146                                       struct untracked_cache_dir *untracked,
2147                                       struct cached_dir *cdir,
2148                                       struct index_state *istate,
2149                                       struct strbuf *path,
2150                                       int baselen,
2151                                       const struct pathspec *pathspec)
2152 {
2153         int has_path_in_index, dtype, excluded;
2154
2155         if (!cdir->d_name)
2156                 return treat_path_fast(dir, untracked, cdir, istate, path,
2157                                        baselen, pathspec);
2158         if (is_dot_or_dotdot(cdir->d_name) || !fspathcmp(cdir->d_name, ".git"))
2159                 return path_none;
2160         strbuf_setlen(path, baselen);
2161         strbuf_addstr(path, cdir->d_name);
2162         if (simplify_away(path->buf, path->len, pathspec))
2163                 return path_none;
2164
2165         dtype = resolve_dtype(cdir->d_type, istate, path->buf, path->len);
2166
2167         /* Always exclude indexed files */
2168         has_path_in_index = !!index_file_exists(istate, path->buf, path->len,
2169                                                 ignore_case);
2170         if (dtype != DT_DIR && has_path_in_index)
2171                 return path_none;
2172
2173         /*
2174          * When we are looking at a directory P in the working tree,
2175          * there are three cases:
2176          *
2177          * (1) P exists in the index.  Everything inside the directory P in
2178          * the working tree needs to go when P is checked out from the
2179          * index.
2180          *
2181          * (2) P does not exist in the index, but there is P/Q in the index.
2182          * We know P will stay a directory when we check out the contents
2183          * of the index, but we do not know yet if there is a directory
2184          * P/Q in the working tree to be killed, so we need to recurse.
2185          *
2186          * (3) P does not exist in the index, and there is no P/Q in the index
2187          * to require P to be a directory, either.  Only in this case, we
2188          * know that everything inside P will not be killed without
2189          * recursing.
2190          */
2191         if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
2192             (dtype == DT_DIR) &&
2193             !has_path_in_index &&
2194             (directory_exists_in_index(istate, path->buf, path->len) == index_nonexistent))
2195                 return path_none;
2196
2197         excluded = is_excluded(dir, istate, path->buf, &dtype);
2198
2199         /*
2200          * Excluded? If we don't explicitly want to show
2201          * ignored files, ignore it
2202          */
2203         if (excluded && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
2204                 return path_excluded;
2205
2206         switch (dtype) {
2207         default:
2208                 return path_none;
2209         case DT_DIR:
2210                 /*
2211                  * WARNING: Do not ignore/amend the return value from
2212                  * treat_directory(), and especially do not change it to return
2213                  * path_recurse as that can cause exponential slowdown.
2214                  * Instead, modify treat_directory() to return the right value.
2215                  */
2216                 strbuf_addch(path, '/');
2217                 return treat_directory(dir, istate, untracked,
2218                                        path->buf, path->len,
2219                                        baselen, excluded, pathspec);
2220         case DT_REG:
2221         case DT_LNK:
2222                 if (pathspec &&
2223                     !match_pathspec(istate, pathspec, path->buf, path->len,
2224                                     0 /* prefix */, NULL /* seen */,
2225                                     0 /* is_dir */))
2226                         return path_none;
2227                 if (excluded)
2228                         return path_excluded;
2229                 return path_untracked;
2230         }
2231 }
2232
2233 static void add_untracked(struct untracked_cache_dir *dir, const char *name)
2234 {
2235         if (!dir)
2236                 return;
2237         ALLOC_GROW(dir->untracked, dir->untracked_nr + 1,
2238                    dir->untracked_alloc);
2239         dir->untracked[dir->untracked_nr++] = xstrdup(name);
2240 }
2241
2242 static int valid_cached_dir(struct dir_struct *dir,
2243                             struct untracked_cache_dir *untracked,
2244                             struct index_state *istate,
2245                             struct strbuf *path,
2246                             int check_only)
2247 {
2248         struct stat st;
2249
2250         if (!untracked)
2251                 return 0;
2252
2253         /*
2254          * With fsmonitor, we can trust the untracked cache's valid field.
2255          */
2256         refresh_fsmonitor(istate);
2257         if (!(dir->untracked->use_fsmonitor && untracked->valid)) {
2258                 if (lstat(path->len ? path->buf : ".", &st)) {
2259                         memset(&untracked->stat_data, 0, sizeof(untracked->stat_data));
2260                         return 0;
2261                 }
2262                 if (!untracked->valid ||
2263                         match_stat_data_racy(istate, &untracked->stat_data, &st)) {
2264                         fill_stat_data(&untracked->stat_data, &st);
2265                         return 0;
2266                 }
2267         }
2268
2269         if (untracked->check_only != !!check_only)
2270                 return 0;
2271
2272         /*
2273          * prep_exclude will be called eventually on this directory,
2274          * but it's called much later in last_matching_pattern(). We
2275          * need it now to determine the validity of the cache for this
2276          * path. The next calls will be nearly no-op, the way
2277          * prep_exclude() is designed.
2278          */
2279         if (path->len && path->buf[path->len - 1] != '/') {
2280                 strbuf_addch(path, '/');
2281                 prep_exclude(dir, istate, path->buf, path->len);
2282                 strbuf_setlen(path, path->len - 1);
2283         } else
2284                 prep_exclude(dir, istate, path->buf, path->len);
2285
2286         /* hopefully prep_exclude() haven't invalidated this entry... */
2287         return untracked->valid;
2288 }
2289
2290 static int open_cached_dir(struct cached_dir *cdir,
2291                            struct dir_struct *dir,
2292                            struct untracked_cache_dir *untracked,
2293                            struct index_state *istate,
2294                            struct strbuf *path,
2295                            int check_only)
2296 {
2297         const char *c_path;
2298
2299         memset(cdir, 0, sizeof(*cdir));
2300         cdir->untracked = untracked;
2301         if (valid_cached_dir(dir, untracked, istate, path, check_only))
2302                 return 0;
2303         c_path = path->len ? path->buf : ".";
2304         cdir->fdir = opendir(c_path);
2305         if (!cdir->fdir)
2306                 warning_errno(_("could not open directory '%s'"), c_path);
2307         if (dir->untracked) {
2308                 invalidate_directory(dir->untracked, untracked);
2309                 dir->untracked->dir_opened++;
2310         }
2311         if (!cdir->fdir)
2312                 return -1;
2313         return 0;
2314 }
2315
2316 static int read_cached_dir(struct cached_dir *cdir)
2317 {
2318         struct dirent *de;
2319
2320         if (cdir->fdir) {
2321                 de = readdir(cdir->fdir);
2322                 if (!de) {
2323                         cdir->d_name = NULL;
2324                         cdir->d_type = DT_UNKNOWN;
2325                         return -1;
2326                 }
2327                 cdir->d_name = de->d_name;
2328                 cdir->d_type = DTYPE(de);
2329                 return 0;
2330         }
2331         while (cdir->nr_dirs < cdir->untracked->dirs_nr) {
2332                 struct untracked_cache_dir *d = cdir->untracked->dirs[cdir->nr_dirs];
2333                 if (!d->recurse) {
2334                         cdir->nr_dirs++;
2335                         continue;
2336                 }
2337                 cdir->ucd = d;
2338                 cdir->nr_dirs++;
2339                 return 0;
2340         }
2341         cdir->ucd = NULL;
2342         if (cdir->nr_files < cdir->untracked->untracked_nr) {
2343                 struct untracked_cache_dir *d = cdir->untracked;
2344                 cdir->file = d->untracked[cdir->nr_files++];
2345                 return 0;
2346         }
2347         return -1;
2348 }
2349
2350 static void close_cached_dir(struct cached_dir *cdir)
2351 {
2352         if (cdir->fdir)
2353                 closedir(cdir->fdir);
2354         /*
2355          * We have gone through this directory and found no untracked
2356          * entries. Mark it valid.
2357          */
2358         if (cdir->untracked) {
2359                 cdir->untracked->valid = 1;
2360                 cdir->untracked->recurse = 1;
2361         }
2362 }
2363
2364 static void add_path_to_appropriate_result_list(struct dir_struct *dir,
2365         struct untracked_cache_dir *untracked,
2366         struct cached_dir *cdir,
2367         struct index_state *istate,
2368         struct strbuf *path,
2369         int baselen,
2370         const struct pathspec *pathspec,
2371         enum path_treatment state)
2372 {
2373         /* add the path to the appropriate result list */
2374         switch (state) {
2375         case path_excluded:
2376                 if (dir->flags & DIR_SHOW_IGNORED)
2377                         dir_add_name(dir, istate, path->buf, path->len);
2378                 else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
2379                         ((dir->flags & DIR_COLLECT_IGNORED) &&
2380                         exclude_matches_pathspec(path->buf, path->len,
2381                                                  pathspec)))
2382                         dir_add_ignored(dir, istate, path->buf, path->len);
2383                 break;
2384
2385         case path_untracked:
2386                 if (dir->flags & DIR_SHOW_IGNORED)
2387                         break;
2388                 dir_add_name(dir, istate, path->buf, path->len);
2389                 if (cdir->fdir)
2390                         add_untracked(untracked, path->buf + baselen);
2391                 break;
2392
2393         default:
2394                 break;
2395         }
2396 }
2397
2398 /*
2399  * Read a directory tree. We currently ignore anything but
2400  * directories, regular files and symlinks. That's because git
2401  * doesn't handle them at all yet. Maybe that will change some
2402  * day.
2403  *
2404  * Also, we ignore the name ".git" (even if it is not a directory).
2405  * That likely will not change.
2406  *
2407  * If 'stop_at_first_file' is specified, 'path_excluded' is returned
2408  * to signal that a file was found. This is the least significant value that
2409  * indicates that a file was encountered that does not depend on the order of
2410  * whether an untracked or excluded path was encountered first.
2411  *
2412  * Returns the most significant path_treatment value encountered in the scan.
2413  * If 'stop_at_first_file' is specified, `path_excluded` is the most
2414  * significant path_treatment value that will be returned.
2415  */
2416
2417 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
2418         struct index_state *istate, const char *base, int baselen,
2419         struct untracked_cache_dir *untracked, int check_only,
2420         int stop_at_first_file, const struct pathspec *pathspec)
2421 {
2422         /*
2423          * WARNING: Do NOT recurse unless path_recurse is returned from
2424          *          treat_path().  Recursing on any other return value
2425          *          can result in exponential slowdown.
2426          */
2427         struct cached_dir cdir;
2428         enum path_treatment state, subdir_state, dir_state = path_none;
2429         struct strbuf path = STRBUF_INIT;
2430
2431         strbuf_add(&path, base, baselen);
2432
2433         if (open_cached_dir(&cdir, dir, untracked, istate, &path, check_only))
2434                 goto out;
2435
2436         if (untracked)
2437                 untracked->check_only = !!check_only;
2438
2439         while (!read_cached_dir(&cdir)) {
2440                 /* check how the file or directory should be treated */
2441                 state = treat_path(dir, untracked, &cdir, istate, &path,
2442                                    baselen, pathspec);
2443
2444                 if (state > dir_state)
2445                         dir_state = state;
2446
2447                 /* recurse into subdir if instructed by treat_path */
2448                 if (state == path_recurse) {
2449                         struct untracked_cache_dir *ud;
2450                         ud = lookup_untracked(dir->untracked, untracked,
2451                                               path.buf + baselen,
2452                                               path.len - baselen);
2453                         subdir_state =
2454                                 read_directory_recursive(dir, istate, path.buf,
2455                                                          path.len, ud,
2456                                                          check_only, stop_at_first_file, pathspec);
2457                         if (subdir_state > dir_state)
2458                                 dir_state = subdir_state;
2459
2460                         if (pathspec &&
2461                             !match_pathspec(istate, pathspec, path.buf, path.len,
2462                                             0 /* prefix */, NULL,
2463                                             0 /* do NOT special case dirs */))
2464                                 state = path_none;
2465                 }
2466
2467                 if (check_only) {
2468                         if (stop_at_first_file) {
2469                                 /*
2470                                  * If stopping at first file, then
2471                                  * signal that a file was found by
2472                                  * returning `path_excluded`. This is
2473                                  * to return a consistent value
2474                                  * regardless of whether an ignored or
2475                                  * excluded file happened to be
2476                                  * encountered 1st.
2477                                  *
2478                                  * In current usage, the
2479                                  * `stop_at_first_file` is passed when
2480                                  * an ancestor directory has matched
2481                                  * an exclude pattern, so any found
2482                                  * files will be excluded.
2483                                  */
2484                                 if (dir_state >= path_excluded) {
2485                                         dir_state = path_excluded;
2486                                         break;
2487                                 }
2488                         }
2489
2490                         /* abort early if maximum state has been reached */
2491                         if (dir_state == path_untracked) {
2492                                 if (cdir.fdir)
2493                                         add_untracked(untracked, path.buf + baselen);
2494                                 break;
2495                         }
2496                         /* skip the add_path_to_appropriate_result_list() */
2497                         continue;
2498                 }
2499
2500                 add_path_to_appropriate_result_list(dir, untracked, &cdir,
2501                                                     istate, &path, baselen,
2502                                                     pathspec, state);
2503         }
2504         close_cached_dir(&cdir);
2505  out:
2506         strbuf_release(&path);
2507
2508         return dir_state;
2509 }
2510
2511 int cmp_dir_entry(const void *p1, const void *p2)
2512 {
2513         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
2514         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
2515
2516         return name_compare(e1->name, e1->len, e2->name, e2->len);
2517 }
2518
2519 /* check if *out lexically strictly contains *in */
2520 int check_dir_entry_contains(const struct dir_entry *out, const struct dir_entry *in)
2521 {
2522         return (out->len < in->len) &&
2523                 (out->name[out->len - 1] == '/') &&
2524                 !memcmp(out->name, in->name, out->len);
2525 }
2526
2527 static int treat_leading_path(struct dir_struct *dir,
2528                               struct index_state *istate,
2529                               const char *path, int len,
2530                               const struct pathspec *pathspec)
2531 {
2532         struct strbuf sb = STRBUF_INIT;
2533         struct strbuf subdir = STRBUF_INIT;
2534         int prevlen, baselen;
2535         const char *cp;
2536         struct cached_dir cdir;
2537         enum path_treatment state = path_none;
2538
2539         /*
2540          * For each directory component of path, we are going to check whether
2541          * that path is relevant given the pathspec.  For example, if path is
2542          *    foo/bar/baz/
2543          * then we will ask treat_path() whether we should go into foo, then
2544          * whether we should go into bar, then whether baz is relevant.
2545          * Checking each is important because e.g. if path is
2546          *    .git/info/
2547          * then we need to check .git to know we shouldn't traverse it.
2548          * If the return from treat_path() is:
2549          *    * path_none, for any path, we return false.
2550          *    * path_recurse, for all path components, we return true
2551          *    * <anything else> for some intermediate component, we make sure
2552          *        to add that path to the relevant list but return false
2553          *        signifying that we shouldn't recurse into it.
2554          */
2555
2556         while (len && path[len - 1] == '/')
2557                 len--;
2558         if (!len)
2559                 return 1;
2560
2561         memset(&cdir, 0, sizeof(cdir));
2562         cdir.d_type = DT_DIR;
2563         baselen = 0;
2564         prevlen = 0;
2565         while (1) {
2566                 prevlen = baselen + !!baselen;
2567                 cp = path + prevlen;
2568                 cp = memchr(cp, '/', path + len - cp);
2569                 if (!cp)
2570                         baselen = len;
2571                 else
2572                         baselen = cp - path;
2573                 strbuf_reset(&sb);
2574                 strbuf_add(&sb, path, baselen);
2575                 if (!is_directory(sb.buf))
2576                         break;
2577                 strbuf_reset(&sb);
2578                 strbuf_add(&sb, path, prevlen);
2579                 strbuf_reset(&subdir);
2580                 strbuf_add(&subdir, path+prevlen, baselen-prevlen);
2581                 cdir.d_name = subdir.buf;
2582                 state = treat_path(dir, NULL, &cdir, istate, &sb, prevlen, pathspec);
2583
2584                 if (state != path_recurse)
2585                         break; /* do not recurse into it */
2586                 if (len <= baselen)
2587                         break; /* finished checking */
2588         }
2589         add_path_to_appropriate_result_list(dir, NULL, &cdir, istate,
2590                                             &sb, baselen, pathspec,
2591                                             state);
2592
2593         strbuf_release(&subdir);
2594         strbuf_release(&sb);
2595         return state == path_recurse;
2596 }
2597
2598 static const char *get_ident_string(void)
2599 {
2600         static struct strbuf sb = STRBUF_INIT;
2601         struct utsname uts;
2602
2603         if (sb.len)
2604                 return sb.buf;
2605         if (uname(&uts) < 0)
2606                 die_errno(_("failed to get kernel name and information"));
2607         strbuf_addf(&sb, "Location %s, system %s", get_git_work_tree(),
2608                     uts.sysname);
2609         return sb.buf;
2610 }
2611
2612 static int ident_in_untracked(const struct untracked_cache *uc)
2613 {
2614         /*
2615          * Previous git versions may have saved many NUL separated
2616          * strings in the "ident" field, but it is insane to manage
2617          * many locations, so just take care of the first one.
2618          */
2619
2620         return !strcmp(uc->ident.buf, get_ident_string());
2621 }
2622
2623 static void set_untracked_ident(struct untracked_cache *uc)
2624 {
2625         strbuf_reset(&uc->ident);
2626         strbuf_addstr(&uc->ident, get_ident_string());
2627
2628         /*
2629          * This strbuf used to contain a list of NUL separated
2630          * strings, so save NUL too for backward compatibility.
2631          */
2632         strbuf_addch(&uc->ident, 0);
2633 }
2634
2635 static void new_untracked_cache(struct index_state *istate)
2636 {
2637         struct untracked_cache *uc = xcalloc(1, sizeof(*uc));
2638         strbuf_init(&uc->ident, 100);
2639         uc->exclude_per_dir = ".gitignore";
2640         /* should be the same flags used by git-status */
2641         uc->dir_flags = DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES;
2642         set_untracked_ident(uc);
2643         istate->untracked = uc;
2644         istate->cache_changed |= UNTRACKED_CHANGED;
2645 }
2646
2647 void add_untracked_cache(struct index_state *istate)
2648 {
2649         if (!istate->untracked) {
2650                 new_untracked_cache(istate);
2651         } else {
2652                 if (!ident_in_untracked(istate->untracked)) {
2653                         free_untracked_cache(istate->untracked);
2654                         new_untracked_cache(istate);
2655                 }
2656         }
2657 }
2658
2659 void remove_untracked_cache(struct index_state *istate)
2660 {
2661         if (istate->untracked) {
2662                 free_untracked_cache(istate->untracked);
2663                 istate->untracked = NULL;
2664                 istate->cache_changed |= UNTRACKED_CHANGED;
2665         }
2666 }
2667
2668 static struct untracked_cache_dir *validate_untracked_cache(struct dir_struct *dir,
2669                                                       int base_len,
2670                                                       const struct pathspec *pathspec)
2671 {
2672         struct untracked_cache_dir *root;
2673         static int untracked_cache_disabled = -1;
2674
2675         if (!dir->untracked)
2676                 return NULL;
2677         if (untracked_cache_disabled < 0)
2678                 untracked_cache_disabled = git_env_bool("GIT_DISABLE_UNTRACKED_CACHE", 0);
2679         if (untracked_cache_disabled)
2680                 return NULL;
2681
2682         /*
2683          * We only support $GIT_DIR/info/exclude and core.excludesfile
2684          * as the global ignore rule files. Any other additions
2685          * (e.g. from command line) invalidate the cache. This
2686          * condition also catches running setup_standard_excludes()
2687          * before setting dir->untracked!
2688          */
2689         if (dir->unmanaged_exclude_files)
2690                 return NULL;
2691
2692         /*
2693          * Optimize for the main use case only: whole-tree git
2694          * status. More work involved in treat_leading_path() if we
2695          * use cache on just a subset of the worktree. pathspec
2696          * support could make the matter even worse.
2697          */
2698         if (base_len || (pathspec && pathspec->nr))
2699                 return NULL;
2700
2701         /* Different set of flags may produce different results */
2702         if (dir->flags != dir->untracked->dir_flags ||
2703             /*
2704              * See treat_directory(), case index_nonexistent. Without
2705              * this flag, we may need to also cache .git file content
2706              * for the resolve_gitlink_ref() call, which we don't.
2707              */
2708             !(dir->flags & DIR_SHOW_OTHER_DIRECTORIES) ||
2709             /* We don't support collecting ignore files */
2710             (dir->flags & (DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO |
2711                            DIR_COLLECT_IGNORED)))
2712                 return NULL;
2713
2714         /*
2715          * If we use .gitignore in the cache and now you change it to
2716          * .gitexclude, everything will go wrong.
2717          */
2718         if (dir->exclude_per_dir != dir->untracked->exclude_per_dir &&
2719             strcmp(dir->exclude_per_dir, dir->untracked->exclude_per_dir))
2720                 return NULL;
2721
2722         /*
2723          * EXC_CMDL is not considered in the cache. If people set it,
2724          * skip the cache.
2725          */
2726         if (dir->exclude_list_group[EXC_CMDL].nr)
2727                 return NULL;
2728
2729         if (!ident_in_untracked(dir->untracked)) {
2730                 warning(_("untracked cache is disabled on this system or location"));
2731                 return NULL;
2732         }
2733
2734         if (!dir->untracked->root) {
2735                 const int len = sizeof(*dir->untracked->root);
2736                 dir->untracked->root = xmalloc(len);
2737                 memset(dir->untracked->root, 0, len);
2738         }
2739
2740         /* Validate $GIT_DIR/info/exclude and core.excludesfile */
2741         root = dir->untracked->root;
2742         if (!oideq(&dir->ss_info_exclude.oid,
2743                    &dir->untracked->ss_info_exclude.oid)) {
2744                 invalidate_gitignore(dir->untracked, root);
2745                 dir->untracked->ss_info_exclude = dir->ss_info_exclude;
2746         }
2747         if (!oideq(&dir->ss_excludes_file.oid,
2748                    &dir->untracked->ss_excludes_file.oid)) {
2749                 invalidate_gitignore(dir->untracked, root);
2750                 dir->untracked->ss_excludes_file = dir->ss_excludes_file;
2751         }
2752
2753         /* Make sure this directory is not dropped out at saving phase */
2754         root->recurse = 1;
2755         return root;
2756 }
2757
2758 int read_directory(struct dir_struct *dir, struct index_state *istate,
2759                    const char *path, int len, const struct pathspec *pathspec)
2760 {
2761         struct untracked_cache_dir *untracked;
2762
2763         trace_performance_enter();
2764
2765         if (has_symlink_leading_path(path, len)) {
2766                 trace_performance_leave("read directory %.*s", len, path);
2767                 return dir->nr;
2768         }
2769
2770         untracked = validate_untracked_cache(dir, len, pathspec);
2771         if (!untracked)
2772                 /*
2773                  * make sure untracked cache code path is disabled,
2774                  * e.g. prep_exclude()
2775                  */
2776                 dir->untracked = NULL;
2777         if (!len || treat_leading_path(dir, istate, path, len, pathspec))
2778                 read_directory_recursive(dir, istate, path, len, untracked, 0, 0, pathspec);
2779         QSORT(dir->entries, dir->nr, cmp_dir_entry);
2780         QSORT(dir->ignored, dir->ignored_nr, cmp_dir_entry);
2781
2782         trace_performance_leave("read directory %.*s", len, path);
2783         if (dir->untracked) {
2784                 static int force_untracked_cache = -1;
2785                 static struct trace_key trace_untracked_stats = TRACE_KEY_INIT(UNTRACKED_STATS);
2786
2787                 if (force_untracked_cache < 0)
2788                         force_untracked_cache =
2789                                 git_env_bool("GIT_FORCE_UNTRACKED_CACHE", 0);
2790                 trace_printf_key(&trace_untracked_stats,
2791                                  "node creation: %u\n"
2792                                  "gitignore invalidation: %u\n"
2793                                  "directory invalidation: %u\n"
2794                                  "opendir: %u\n",
2795                                  dir->untracked->dir_created,
2796                                  dir->untracked->gitignore_invalidated,
2797                                  dir->untracked->dir_invalidated,
2798                                  dir->untracked->dir_opened);
2799                 if (force_untracked_cache &&
2800                         dir->untracked == istate->untracked &&
2801                     (dir->untracked->dir_opened ||
2802                      dir->untracked->gitignore_invalidated ||
2803                      dir->untracked->dir_invalidated))
2804                         istate->cache_changed |= UNTRACKED_CHANGED;
2805                 if (dir->untracked != istate->untracked) {
2806                         FREE_AND_NULL(dir->untracked);
2807                 }
2808         }
2809         return dir->nr;
2810 }
2811
2812 int file_exists(const char *f)
2813 {
2814         struct stat sb;
2815         return lstat(f, &sb) == 0;
2816 }
2817
2818 int repo_file_exists(struct repository *repo, const char *path)
2819 {
2820         if (repo != the_repository)
2821                 BUG("do not know how to check file existence in arbitrary repo");
2822
2823         return file_exists(path);
2824 }
2825
2826 static int cmp_icase(char a, char b)
2827 {
2828         if (a == b)
2829                 return 0;
2830         if (ignore_case)
2831                 return toupper(a) - toupper(b);
2832         return a - b;
2833 }
2834
2835 /*
2836  * Given two normalized paths (a trailing slash is ok), if subdir is
2837  * outside dir, return -1.  Otherwise return the offset in subdir that
2838  * can be used as relative path to dir.
2839  */
2840 int dir_inside_of(const char *subdir, const char *dir)
2841 {
2842         int offset = 0;
2843
2844         assert(dir && subdir && *dir && *subdir);
2845
2846         while (*dir && *subdir && !cmp_icase(*dir, *subdir)) {
2847                 dir++;
2848                 subdir++;
2849                 offset++;
2850         }
2851
2852         /* hel[p]/me vs hel[l]/yeah */
2853         if (*dir && *subdir)
2854                 return -1;
2855
2856         if (!*subdir)
2857                 return !*dir ? offset : -1; /* same dir */
2858
2859         /* foo/[b]ar vs foo/[] */
2860         if (is_dir_sep(dir[-1]))
2861                 return is_dir_sep(subdir[-1]) ? offset : -1;
2862
2863         /* foo[/]bar vs foo[] */
2864         return is_dir_sep(*subdir) ? offset + 1 : -1;
2865 }
2866
2867 int is_inside_dir(const char *dir)
2868 {
2869         char *cwd;
2870         int rc;
2871
2872         if (!dir)
2873                 return 0;
2874
2875         cwd = xgetcwd();
2876         rc = (dir_inside_of(cwd, dir) >= 0);
2877         free(cwd);
2878         return rc;
2879 }
2880
2881 int is_empty_dir(const char *path)
2882 {
2883         DIR *dir = opendir(path);
2884         struct dirent *e;
2885         int ret = 1;
2886
2887         if (!dir)
2888                 return 0;
2889
2890         while ((e = readdir(dir)) != NULL)
2891                 if (!is_dot_or_dotdot(e->d_name)) {
2892                         ret = 0;
2893                         break;
2894                 }
2895
2896         closedir(dir);
2897         return ret;
2898 }
2899
2900 static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
2901 {
2902         DIR *dir;
2903         struct dirent *e;
2904         int ret = 0, original_len = path->len, len, kept_down = 0;
2905         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
2906         int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
2907         struct object_id submodule_head;
2908
2909         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
2910             !resolve_gitlink_ref(path->buf, "HEAD", &submodule_head)) {
2911                 /* Do not descend and nuke a nested git work tree. */
2912                 if (kept_up)
2913                         *kept_up = 1;
2914                 return 0;
2915         }
2916
2917         flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
2918         dir = opendir(path->buf);
2919         if (!dir) {
2920                 if (errno == ENOENT)
2921                         return keep_toplevel ? -1 : 0;
2922                 else if (errno == EACCES && !keep_toplevel)
2923                         /*
2924                          * An empty dir could be removable even if it
2925                          * is unreadable:
2926                          */
2927                         return rmdir(path->buf);
2928                 else
2929                         return -1;
2930         }
2931         strbuf_complete(path, '/');
2932
2933         len = path->len;
2934         while ((e = readdir(dir)) != NULL) {
2935                 struct stat st;
2936                 if (is_dot_or_dotdot(e->d_name))
2937                         continue;
2938
2939                 strbuf_setlen(path, len);
2940                 strbuf_addstr(path, e->d_name);
2941                 if (lstat(path->buf, &st)) {
2942                         if (errno == ENOENT)
2943                                 /*
2944                                  * file disappeared, which is what we
2945                                  * wanted anyway
2946                                  */
2947                                 continue;
2948                         /* fall through */
2949                 } else if (S_ISDIR(st.st_mode)) {
2950                         if (!remove_dir_recurse(path, flag, &kept_down))
2951                                 continue; /* happy */
2952                 } else if (!only_empty &&
2953                            (!unlink(path->buf) || errno == ENOENT)) {
2954                         continue; /* happy, too */
2955                 }
2956
2957                 /* path too long, stat fails, or non-directory still exists */
2958                 ret = -1;
2959                 break;
2960         }
2961         closedir(dir);
2962
2963         strbuf_setlen(path, original_len);
2964         if (!ret && !keep_toplevel && !kept_down)
2965                 ret = (!rmdir(path->buf) || errno == ENOENT) ? 0 : -1;
2966         else if (kept_up)
2967                 /*
2968                  * report the uplevel that it is not an error that we
2969                  * did not rmdir() our directory.
2970                  */
2971                 *kept_up = !ret;
2972         return ret;
2973 }
2974
2975 int remove_dir_recursively(struct strbuf *path, int flag)
2976 {
2977         return remove_dir_recurse(path, flag, NULL);
2978 }
2979
2980 static GIT_PATH_FUNC(git_path_info_exclude, "info/exclude")
2981
2982 void setup_standard_excludes(struct dir_struct *dir)
2983 {
2984         dir->exclude_per_dir = ".gitignore";
2985
2986         /* core.excludesfile defaulting to $XDG_CONFIG_HOME/git/ignore */
2987         if (!excludes_file)
2988                 excludes_file = xdg_config_home("ignore");
2989         if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
2990                 add_patterns_from_file_1(dir, excludes_file,
2991                                          dir->untracked ? &dir->ss_excludes_file : NULL);
2992
2993         /* per repository user preference */
2994         if (startup_info->have_repository) {
2995                 const char *path = git_path_info_exclude();
2996                 if (!access_or_warn(path, R_OK, 0))
2997                         add_patterns_from_file_1(dir, path,
2998                                                  dir->untracked ? &dir->ss_info_exclude : NULL);
2999         }
3000 }
3001
3002 int remove_path(const char *name)
3003 {
3004         char *slash;
3005
3006         if (unlink(name) && !is_missing_file_error(errno))
3007                 return -1;
3008
3009         slash = strrchr(name, '/');
3010         if (slash) {
3011                 char *dirs = xstrdup(name);
3012                 slash = dirs + (slash - name);
3013                 do {
3014                         *slash = '\0';
3015                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
3016                 free(dirs);
3017         }
3018         return 0;
3019 }
3020
3021 /*
3022  * Frees memory within dir which was allocated, and resets fields for further
3023  * use.  Does not free dir itself.
3024  */
3025 void dir_clear(struct dir_struct *dir)
3026 {
3027         int i, j;
3028         struct exclude_list_group *group;
3029         struct pattern_list *pl;
3030         struct exclude_stack *stk;
3031
3032         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
3033                 group = &dir->exclude_list_group[i];
3034                 for (j = 0; j < group->nr; j++) {
3035                         pl = &group->pl[j];
3036                         if (i == EXC_DIRS)
3037                                 free((char *)pl->src);
3038                         clear_pattern_list(pl);
3039                 }
3040                 free(group->pl);
3041         }
3042
3043         for (i = 0; i < dir->ignored_nr; i++)
3044                 free(dir->ignored[i]);
3045         for (i = 0; i < dir->nr; i++)
3046                 free(dir->entries[i]);
3047         free(dir->ignored);
3048         free(dir->entries);
3049
3050         stk = dir->exclude_stack;
3051         while (stk) {
3052                 struct exclude_stack *prev = stk->prev;
3053                 free(stk);
3054                 stk = prev;
3055         }
3056         strbuf_release(&dir->basebuf);
3057
3058         dir_init(dir);
3059 }
3060
3061 struct ondisk_untracked_cache {
3062         struct stat_data info_exclude_stat;
3063         struct stat_data excludes_file_stat;
3064         uint32_t dir_flags;
3065 };
3066
3067 #define ouc_offset(x) offsetof(struct ondisk_untracked_cache, x)
3068
3069 struct write_data {
3070         int index;         /* number of written untracked_cache_dir */
3071         struct ewah_bitmap *check_only; /* from untracked_cache_dir */
3072         struct ewah_bitmap *valid;      /* from untracked_cache_dir */
3073         struct ewah_bitmap *sha1_valid; /* set if exclude_sha1 is not null */
3074         struct strbuf out;
3075         struct strbuf sb_stat;
3076         struct strbuf sb_sha1;
3077 };
3078
3079 static void stat_data_to_disk(struct stat_data *to, const struct stat_data *from)
3080 {
3081         to->sd_ctime.sec  = htonl(from->sd_ctime.sec);
3082         to->sd_ctime.nsec = htonl(from->sd_ctime.nsec);
3083         to->sd_mtime.sec  = htonl(from->sd_mtime.sec);
3084         to->sd_mtime.nsec = htonl(from->sd_mtime.nsec);
3085         to->sd_dev        = htonl(from->sd_dev);
3086         to->sd_ino        = htonl(from->sd_ino);
3087         to->sd_uid        = htonl(from->sd_uid);
3088         to->sd_gid        = htonl(from->sd_gid);
3089         to->sd_size       = htonl(from->sd_size);
3090 }
3091
3092 static void write_one_dir(struct untracked_cache_dir *untracked,
3093                           struct write_data *wd)
3094 {
3095         struct stat_data stat_data;
3096         struct strbuf *out = &wd->out;
3097         unsigned char intbuf[16];
3098         unsigned int intlen, value;
3099         int i = wd->index++;
3100
3101         /*
3102          * untracked_nr should be reset whenever valid is clear, but
3103          * for safety..
3104          */
3105         if (!untracked->valid) {
3106                 untracked->untracked_nr = 0;
3107                 untracked->check_only = 0;
3108         }
3109
3110         if (untracked->check_only)
3111                 ewah_set(wd->check_only, i);
3112         if (untracked->valid) {
3113                 ewah_set(wd->valid, i);
3114                 stat_data_to_disk(&stat_data, &untracked->stat_data);
3115                 strbuf_add(&wd->sb_stat, &stat_data, sizeof(stat_data));
3116         }
3117         if (!is_null_oid(&untracked->exclude_oid)) {
3118                 ewah_set(wd->sha1_valid, i);
3119                 strbuf_add(&wd->sb_sha1, untracked->exclude_oid.hash,
3120                            the_hash_algo->rawsz);
3121         }
3122
3123         intlen = encode_varint(untracked->untracked_nr, intbuf);
3124         strbuf_add(out, intbuf, intlen);
3125
3126         /* skip non-recurse directories */
3127         for (i = 0, value = 0; i < untracked->dirs_nr; i++)
3128                 if (untracked->dirs[i]->recurse)
3129                         value++;
3130         intlen = encode_varint(value, intbuf);
3131         strbuf_add(out, intbuf, intlen);
3132
3133         strbuf_add(out, untracked->name, strlen(untracked->name) + 1);
3134
3135         for (i = 0; i < untracked->untracked_nr; i++)
3136                 strbuf_add(out, untracked->untracked[i],
3137                            strlen(untracked->untracked[i]) + 1);
3138
3139         for (i = 0; i < untracked->dirs_nr; i++)
3140                 if (untracked->dirs[i]->recurse)
3141                         write_one_dir(untracked->dirs[i], wd);
3142 }
3143
3144 void write_untracked_extension(struct strbuf *out, struct untracked_cache *untracked)
3145 {
3146         struct ondisk_untracked_cache *ouc;
3147         struct write_data wd;
3148         unsigned char varbuf[16];
3149         int varint_len;
3150         const unsigned hashsz = the_hash_algo->rawsz;
3151
3152         ouc = xcalloc(1, sizeof(*ouc));
3153         stat_data_to_disk(&ouc->info_exclude_stat, &untracked->ss_info_exclude.stat);
3154         stat_data_to_disk(&ouc->excludes_file_stat, &untracked->ss_excludes_file.stat);
3155         ouc->dir_flags = htonl(untracked->dir_flags);
3156
3157         varint_len = encode_varint(untracked->ident.len, varbuf);
3158         strbuf_add(out, varbuf, varint_len);
3159         strbuf_addbuf(out, &untracked->ident);
3160
3161         strbuf_add(out, ouc, sizeof(*ouc));
3162         strbuf_add(out, untracked->ss_info_exclude.oid.hash, hashsz);
3163         strbuf_add(out, untracked->ss_excludes_file.oid.hash, hashsz);
3164         strbuf_add(out, untracked->exclude_per_dir, strlen(untracked->exclude_per_dir) + 1);
3165         FREE_AND_NULL(ouc);
3166
3167         if (!untracked->root) {
3168                 varint_len = encode_varint(0, varbuf);
3169                 strbuf_add(out, varbuf, varint_len);
3170                 return;
3171         }
3172
3173         wd.index      = 0;
3174         wd.check_only = ewah_new();
3175         wd.valid      = ewah_new();
3176         wd.sha1_valid = ewah_new();
3177         strbuf_init(&wd.out, 1024);
3178         strbuf_init(&wd.sb_stat, 1024);
3179         strbuf_init(&wd.sb_sha1, 1024);
3180         write_one_dir(untracked->root, &wd);
3181
3182         varint_len = encode_varint(wd.index, varbuf);
3183         strbuf_add(out, varbuf, varint_len);
3184         strbuf_addbuf(out, &wd.out);
3185         ewah_serialize_strbuf(wd.valid, out);
3186         ewah_serialize_strbuf(wd.check_only, out);
3187         ewah_serialize_strbuf(wd.sha1_valid, out);
3188         strbuf_addbuf(out, &wd.sb_stat);
3189         strbuf_addbuf(out, &wd.sb_sha1);
3190         strbuf_addch(out, '\0'); /* safe guard for string lists */
3191
3192         ewah_free(wd.valid);
3193         ewah_free(wd.check_only);
3194         ewah_free(wd.sha1_valid);
3195         strbuf_release(&wd.out);
3196         strbuf_release(&wd.sb_stat);
3197         strbuf_release(&wd.sb_sha1);
3198 }
3199
3200 static void free_untracked(struct untracked_cache_dir *ucd)
3201 {
3202         int i;
3203         if (!ucd)
3204                 return;
3205         for (i = 0; i < ucd->dirs_nr; i++)
3206                 free_untracked(ucd->dirs[i]);
3207         for (i = 0; i < ucd->untracked_nr; i++)
3208                 free(ucd->untracked[i]);
3209         free(ucd->untracked);
3210         free(ucd->dirs);
3211         free(ucd);
3212 }
3213
3214 void free_untracked_cache(struct untracked_cache *uc)
3215 {
3216         if (uc)
3217                 free_untracked(uc->root);
3218         free(uc);
3219 }
3220
3221 struct read_data {
3222         int index;
3223         struct untracked_cache_dir **ucd;
3224         struct ewah_bitmap *check_only;
3225         struct ewah_bitmap *valid;
3226         struct ewah_bitmap *sha1_valid;
3227         const unsigned char *data;
3228         const unsigned char *end;
3229 };
3230
3231 static void stat_data_from_disk(struct stat_data *to, const unsigned char *data)
3232 {
3233         memcpy(to, data, sizeof(*to));
3234         to->sd_ctime.sec  = ntohl(to->sd_ctime.sec);
3235         to->sd_ctime.nsec = ntohl(to->sd_ctime.nsec);
3236         to->sd_mtime.sec  = ntohl(to->sd_mtime.sec);
3237         to->sd_mtime.nsec = ntohl(to->sd_mtime.nsec);
3238         to->sd_dev        = ntohl(to->sd_dev);
3239         to->sd_ino        = ntohl(to->sd_ino);
3240         to->sd_uid        = ntohl(to->sd_uid);
3241         to->sd_gid        = ntohl(to->sd_gid);
3242         to->sd_size       = ntohl(to->sd_size);
3243 }
3244
3245 static int read_one_dir(struct untracked_cache_dir **untracked_,
3246                         struct read_data *rd)
3247 {
3248         struct untracked_cache_dir ud, *untracked;
3249         const unsigned char *data = rd->data, *end = rd->end;
3250         const unsigned char *eos;
3251         unsigned int value;
3252         int i;
3253
3254         memset(&ud, 0, sizeof(ud));
3255
3256         value = decode_varint(&data);
3257         if (data > end)
3258                 return -1;
3259         ud.recurse         = 1;
3260         ud.untracked_alloc = value;
3261         ud.untracked_nr    = value;
3262         if (ud.untracked_nr)
3263                 ALLOC_ARRAY(ud.untracked, ud.untracked_nr);
3264
3265         ud.dirs_alloc = ud.dirs_nr = decode_varint(&data);
3266         if (data > end)
3267                 return -1;
3268         ALLOC_ARRAY(ud.dirs, ud.dirs_nr);
3269
3270         eos = memchr(data, '\0', end - data);
3271         if (!eos || eos == end)
3272                 return -1;
3273
3274         *untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), eos - data, 1));
3275         memcpy(untracked, &ud, sizeof(ud));
3276         memcpy(untracked->name, data, eos - data + 1);
3277         data = eos + 1;
3278
3279         for (i = 0; i < untracked->untracked_nr; i++) {
3280                 eos = memchr(data, '\0', end - data);
3281                 if (!eos || eos == end)
3282                         return -1;
3283                 untracked->untracked[i] = xmemdupz(data, eos - data);
3284                 data = eos + 1;
3285         }
3286
3287         rd->ucd[rd->index++] = untracked;
3288         rd->data = data;
3289
3290         for (i = 0; i < untracked->dirs_nr; i++) {
3291                 if (read_one_dir(untracked->dirs + i, rd) < 0)
3292                         return -1;
3293         }
3294         return 0;
3295 }
3296
3297 static void set_check_only(size_t pos, void *cb)
3298 {
3299         struct read_data *rd = cb;
3300         struct untracked_cache_dir *ud = rd->ucd[pos];
3301         ud->check_only = 1;
3302 }
3303
3304 static void read_stat(size_t pos, void *cb)
3305 {
3306         struct read_data *rd = cb;
3307         struct untracked_cache_dir *ud = rd->ucd[pos];
3308         if (rd->data + sizeof(struct stat_data) > rd->end) {
3309                 rd->data = rd->end + 1;
3310                 return;
3311         }
3312         stat_data_from_disk(&ud->stat_data, rd->data);
3313         rd->data += sizeof(struct stat_data);
3314         ud->valid = 1;
3315 }
3316
3317 static void read_oid(size_t pos, void *cb)
3318 {
3319         struct read_data *rd = cb;
3320         struct untracked_cache_dir *ud = rd->ucd[pos];
3321         if (rd->data + the_hash_algo->rawsz > rd->end) {
3322                 rd->data = rd->end + 1;
3323                 return;
3324         }
3325         hashcpy(ud->exclude_oid.hash, rd->data);
3326         rd->data += the_hash_algo->rawsz;
3327 }
3328
3329 static void load_oid_stat(struct oid_stat *oid_stat, const unsigned char *data,
3330                           const unsigned char *sha1)
3331 {
3332         stat_data_from_disk(&oid_stat->stat, data);
3333         hashcpy(oid_stat->oid.hash, sha1);
3334         oid_stat->valid = 1;
3335 }
3336
3337 struct untracked_cache *read_untracked_extension(const void *data, unsigned long sz)
3338 {
3339         struct untracked_cache *uc;
3340         struct read_data rd;
3341         const unsigned char *next = data, *end = (const unsigned char *)data + sz;
3342         const char *ident;
3343         int ident_len;
3344         ssize_t len;
3345         const char *exclude_per_dir;
3346         const unsigned hashsz = the_hash_algo->rawsz;
3347         const unsigned offset = sizeof(struct ondisk_untracked_cache);
3348         const unsigned exclude_per_dir_offset = offset + 2 * hashsz;
3349
3350         if (sz <= 1 || end[-1] != '\0')
3351                 return NULL;
3352         end--;
3353
3354         ident_len = decode_varint(&next);
3355         if (next + ident_len > end)
3356                 return NULL;
3357         ident = (const char *)next;
3358         next += ident_len;
3359
3360         if (next + exclude_per_dir_offset + 1 > end)
3361                 return NULL;
3362
3363         uc = xcalloc(1, sizeof(*uc));
3364         strbuf_init(&uc->ident, ident_len);
3365         strbuf_add(&uc->ident, ident, ident_len);
3366         load_oid_stat(&uc->ss_info_exclude,
3367                       next + ouc_offset(info_exclude_stat),
3368                       next + offset);
3369         load_oid_stat(&uc->ss_excludes_file,
3370                       next + ouc_offset(excludes_file_stat),
3371                       next + offset + hashsz);
3372         uc->dir_flags = get_be32(next + ouc_offset(dir_flags));
3373         exclude_per_dir = (const char *)next + exclude_per_dir_offset;
3374         uc->exclude_per_dir = xstrdup(exclude_per_dir);
3375         /* NUL after exclude_per_dir is covered by sizeof(*ouc) */
3376         next += exclude_per_dir_offset + strlen(exclude_per_dir) + 1;
3377         if (next >= end)
3378                 goto done2;
3379
3380         len = decode_varint(&next);
3381         if (next > end || len == 0)
3382                 goto done2;
3383
3384         rd.valid      = ewah_new();
3385         rd.check_only = ewah_new();
3386         rd.sha1_valid = ewah_new();
3387         rd.data       = next;
3388         rd.end        = end;
3389         rd.index      = 0;
3390         ALLOC_ARRAY(rd.ucd, len);
3391
3392         if (read_one_dir(&uc->root, &rd) || rd.index != len)
3393                 goto done;
3394
3395         next = rd.data;
3396         len = ewah_read_mmap(rd.valid, next, end - next);
3397         if (len < 0)
3398                 goto done;
3399
3400         next += len;
3401         len = ewah_read_mmap(rd.check_only, next, end - next);
3402         if (len < 0)
3403                 goto done;
3404
3405         next += len;
3406         len = ewah_read_mmap(rd.sha1_valid, next, end - next);
3407         if (len < 0)
3408                 goto done;
3409
3410         ewah_each_bit(rd.check_only, set_check_only, &rd);
3411         rd.data = next + len;
3412         ewah_each_bit(rd.valid, read_stat, &rd);
3413         ewah_each_bit(rd.sha1_valid, read_oid, &rd);
3414         next = rd.data;
3415
3416 done:
3417         free(rd.ucd);
3418         ewah_free(rd.valid);
3419         ewah_free(rd.check_only);
3420         ewah_free(rd.sha1_valid);
3421 done2:
3422         if (next != end) {
3423                 free_untracked_cache(uc);
3424                 uc = NULL;
3425         }
3426         return uc;
3427 }
3428
3429 static void invalidate_one_directory(struct untracked_cache *uc,
3430                                      struct untracked_cache_dir *ucd)
3431 {
3432         uc->dir_invalidated++;
3433         ucd->valid = 0;
3434         ucd->untracked_nr = 0;
3435 }
3436
3437 /*
3438  * Normally when an entry is added or removed from a directory,
3439  * invalidating that directory is enough. No need to touch its
3440  * ancestors. When a directory is shown as "foo/bar/" in git-status
3441  * however, deleting or adding an entry may have cascading effect.
3442  *
3443  * Say the "foo/bar/file" has become untracked, we need to tell the
3444  * untracked_cache_dir of "foo" that "bar/" is not an untracked
3445  * directory any more (because "bar" is managed by foo as an untracked
3446  * "file").
3447  *
3448  * Similarly, if "foo/bar/file" moves from untracked to tracked and it
3449  * was the last untracked entry in the entire "foo", we should show
3450  * "foo/" instead. Which means we have to invalidate past "bar" up to
3451  * "foo".
3452  *
3453  * This function traverses all directories from root to leaf. If there
3454  * is a chance of one of the above cases happening, we invalidate back
3455  * to root. Otherwise we just invalidate the leaf. There may be a more
3456  * sophisticated way than checking for SHOW_OTHER_DIRECTORIES to
3457  * detect these cases and avoid unnecessary invalidation, for example,
3458  * checking for the untracked entry named "bar/" in "foo", but for now
3459  * stick to something safe and simple.
3460  */
3461 static int invalidate_one_component(struct untracked_cache *uc,
3462                                     struct untracked_cache_dir *dir,
3463                                     const char *path, int len)
3464 {
3465         const char *rest = strchr(path, '/');
3466
3467         if (rest) {
3468                 int component_len = rest - path;
3469                 struct untracked_cache_dir *d =
3470                         lookup_untracked(uc, dir, path, component_len);
3471                 int ret =
3472                         invalidate_one_component(uc, d, rest + 1,
3473                                                  len - (component_len + 1));
3474                 if (ret)
3475                         invalidate_one_directory(uc, dir);
3476                 return ret;
3477         }
3478
3479         invalidate_one_directory(uc, dir);
3480         return uc->dir_flags & DIR_SHOW_OTHER_DIRECTORIES;
3481 }
3482
3483 void untracked_cache_invalidate_path(struct index_state *istate,
3484                                      const char *path, int safe_path)
3485 {
3486         if (!istate->untracked || !istate->untracked->root)
3487                 return;
3488         if (!safe_path && !verify_path(path, 0))
3489                 return;
3490         invalidate_one_component(istate->untracked, istate->untracked->root,
3491                                  path, strlen(path));
3492 }
3493
3494 void untracked_cache_remove_from_index(struct index_state *istate,
3495                                        const char *path)
3496 {
3497         untracked_cache_invalidate_path(istate, path, 1);
3498 }
3499
3500 void untracked_cache_add_to_index(struct index_state *istate,
3501                                   const char *path)
3502 {
3503         untracked_cache_invalidate_path(istate, path, 1);
3504 }
3505
3506 static void connect_wt_gitdir_in_nested(const char *sub_worktree,
3507                                         const char *sub_gitdir)
3508 {
3509         int i;
3510         struct repository subrepo;
3511         struct strbuf sub_wt = STRBUF_INIT;
3512         struct strbuf sub_gd = STRBUF_INIT;
3513
3514         const struct submodule *sub;
3515
3516         /* If the submodule has no working tree, we can ignore it. */
3517         if (repo_init(&subrepo, sub_gitdir, sub_worktree))
3518                 return;
3519
3520         if (repo_read_index(&subrepo) < 0)
3521                 die(_("index file corrupt in repo %s"), subrepo.gitdir);
3522
3523         for (i = 0; i < subrepo.index->cache_nr; i++) {
3524                 const struct cache_entry *ce = subrepo.index->cache[i];
3525
3526                 if (!S_ISGITLINK(ce->ce_mode))
3527                         continue;
3528
3529                 while (i + 1 < subrepo.index->cache_nr &&
3530                        !strcmp(ce->name, subrepo.index->cache[i + 1]->name))
3531                         /*
3532                          * Skip entries with the same name in different stages
3533                          * to make sure an entry is returned only once.
3534                          */
3535                         i++;
3536
3537                 sub = submodule_from_path(&subrepo, &null_oid, ce->name);
3538                 if (!sub || !is_submodule_active(&subrepo, ce->name))
3539                         /* .gitmodules broken or inactive sub */
3540                         continue;
3541
3542                 strbuf_reset(&sub_wt);
3543                 strbuf_reset(&sub_gd);
3544                 strbuf_addf(&sub_wt, "%s/%s", sub_worktree, sub->path);
3545                 strbuf_addf(&sub_gd, "%s/modules/%s", sub_gitdir, sub->name);
3546
3547                 connect_work_tree_and_git_dir(sub_wt.buf, sub_gd.buf, 1);
3548         }
3549         strbuf_release(&sub_wt);
3550         strbuf_release(&sub_gd);
3551         repo_clear(&subrepo);
3552 }
3553
3554 void connect_work_tree_and_git_dir(const char *work_tree_,
3555                                    const char *git_dir_,
3556                                    int recurse_into_nested)
3557 {
3558         struct strbuf gitfile_sb = STRBUF_INIT;
3559         struct strbuf cfg_sb = STRBUF_INIT;
3560         struct strbuf rel_path = STRBUF_INIT;
3561         char *git_dir, *work_tree;
3562
3563         /* Prepare .git file */
3564         strbuf_addf(&gitfile_sb, "%s/.git", work_tree_);
3565         if (safe_create_leading_directories_const(gitfile_sb.buf))
3566                 die(_("could not create directories for %s"), gitfile_sb.buf);
3567
3568         /* Prepare config file */
3569         strbuf_addf(&cfg_sb, "%s/config", git_dir_);
3570         if (safe_create_leading_directories_const(cfg_sb.buf))
3571                 die(_("could not create directories for %s"), cfg_sb.buf);
3572
3573         git_dir = real_pathdup(git_dir_, 1);
3574         work_tree = real_pathdup(work_tree_, 1);
3575
3576         /* Write .git file */
3577         write_file(gitfile_sb.buf, "gitdir: %s",
3578                    relative_path(git_dir, work_tree, &rel_path));
3579         /* Update core.worktree setting */
3580         git_config_set_in_file(cfg_sb.buf, "core.worktree",
3581                                relative_path(work_tree, git_dir, &rel_path));
3582
3583         strbuf_release(&gitfile_sb);
3584         strbuf_release(&cfg_sb);
3585         strbuf_release(&rel_path);
3586
3587         if (recurse_into_nested)
3588                 connect_wt_gitdir_in_nested(work_tree, git_dir);
3589
3590         free(work_tree);
3591         free(git_dir);
3592 }
3593
3594 /*
3595  * Migrate the git directory of the given path from old_git_dir to new_git_dir.
3596  */
3597 void relocate_gitdir(const char *path, const char *old_git_dir, const char *new_git_dir)
3598 {
3599         if (rename(old_git_dir, new_git_dir) < 0)
3600                 die_errno(_("could not migrate git directory from '%s' to '%s'"),
3601                         old_git_dir, new_git_dir);
3602
3603         connect_work_tree_and_git_dir(path, new_git_dir, 0);
3604 }