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