Merge branch 'an/diff-index-doc'
[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
15 struct path_simplify {
16         int len;
17         const char *path;
18 };
19
20 /*
21  * Tells read_directory_recursive how a file or directory should be treated.
22  * Values are ordered by significance, e.g. if a directory contains both
23  * excluded and untracked files, it is listed as untracked because
24  * path_untracked > path_excluded.
25  */
26 enum path_treatment {
27         path_none = 0,
28         path_recurse,
29         path_excluded,
30         path_untracked
31 };
32
33 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
34         const char *path, int len,
35         int check_only, const struct path_simplify *simplify);
36 static int get_dtype(struct dirent *de, const char *path, int len);
37
38 /* helper string functions with support for the ignore_case flag */
39 int strcmp_icase(const char *a, const char *b)
40 {
41         return ignore_case ? strcasecmp(a, b) : strcmp(a, b);
42 }
43
44 int strncmp_icase(const char *a, const char *b, size_t count)
45 {
46         return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);
47 }
48
49 int fnmatch_icase(const char *pattern, const char *string, int flags)
50 {
51         return fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));
52 }
53
54 inline int git_fnmatch(const char *pattern, const char *string,
55                        int flags, int prefix)
56 {
57         int fnm_flags = 0;
58         if (flags & GFNM_PATHNAME)
59                 fnm_flags |= FNM_PATHNAME;
60         if (prefix > 0) {
61                 if (strncmp(pattern, string, prefix))
62                         return FNM_NOMATCH;
63                 pattern += prefix;
64                 string += prefix;
65         }
66         if (flags & GFNM_ONESTAR) {
67                 int pattern_len = strlen(++pattern);
68                 int string_len = strlen(string);
69                 return string_len < pattern_len ||
70                        strcmp(pattern,
71                               string + string_len - pattern_len);
72         }
73         return fnmatch(pattern, string, fnm_flags);
74 }
75
76 static int fnmatch_icase_mem(const char *pattern, int patternlen,
77                              const char *string, int stringlen,
78                              int flags)
79 {
80         int match_status;
81         struct strbuf pat_buf = STRBUF_INIT;
82         struct strbuf str_buf = STRBUF_INIT;
83         const char *use_pat = pattern;
84         const char *use_str = string;
85
86         if (pattern[patternlen]) {
87                 strbuf_add(&pat_buf, pattern, patternlen);
88                 use_pat = pat_buf.buf;
89         }
90         if (string[stringlen]) {
91                 strbuf_add(&str_buf, string, stringlen);
92                 use_str = str_buf.buf;
93         }
94
95         if (ignore_case)
96                 flags |= WM_CASEFOLD;
97         match_status = wildmatch(use_pat, use_str, flags, NULL);
98
99         strbuf_release(&pat_buf);
100         strbuf_release(&str_buf);
101
102         return match_status;
103 }
104
105 static size_t common_prefix_len(const char **pathspec)
106 {
107         const char *n, *first;
108         size_t max = 0;
109         int literal = limit_pathspec_to_literal();
110
111         if (!pathspec)
112                 return max;
113
114         first = *pathspec;
115         while ((n = *pathspec++)) {
116                 size_t i, len = 0;
117                 for (i = 0; first == n || i < max; i++) {
118                         char c = n[i];
119                         if (!c || c != first[i] || (!literal && is_glob_special(c)))
120                                 break;
121                         if (c == '/')
122                                 len = i + 1;
123                 }
124                 if (first == n || len < max) {
125                         max = len;
126                         if (!max)
127                                 break;
128                 }
129         }
130         return max;
131 }
132
133 /*
134  * Returns a copy of the longest leading path common among all
135  * pathspecs.
136  */
137 char *common_prefix(const char **pathspec)
138 {
139         unsigned long len = common_prefix_len(pathspec);
140
141         return len ? xmemdupz(*pathspec, len) : NULL;
142 }
143
144 int fill_directory(struct dir_struct *dir, const char **pathspec)
145 {
146         size_t len;
147
148         /*
149          * Calculate common prefix for the pathspec, and
150          * use that to optimize the directory walk
151          */
152         len = common_prefix_len(pathspec);
153
154         /* Read the directory and prune it */
155         read_directory(dir, pathspec ? *pathspec : "", len, pathspec);
156         return len;
157 }
158
159 int within_depth(const char *name, int namelen,
160                         int depth, int max_depth)
161 {
162         const char *cp = name, *cpe = name + namelen;
163
164         while (cp < cpe) {
165                 if (*cp++ != '/')
166                         continue;
167                 depth++;
168                 if (depth > max_depth)
169                         return 0;
170         }
171         return 1;
172 }
173
174 /*
175  * Does 'match' match the given name?
176  * A match is found if
177  *
178  * (1) the 'match' string is leading directory of 'name', or
179  * (2) the 'match' string is a wildcard and matches 'name', or
180  * (3) the 'match' string is exactly the same as 'name'.
181  *
182  * and the return value tells which case it was.
183  *
184  * It returns 0 when there is no match.
185  */
186 static int match_one(const char *match, const char *name, int namelen)
187 {
188         int matchlen;
189         int literal = limit_pathspec_to_literal();
190
191         /* If the match was just the prefix, we matched */
192         if (!*match)
193                 return MATCHED_RECURSIVELY;
194
195         if (ignore_case) {
196                 for (;;) {
197                         unsigned char c1 = tolower(*match);
198                         unsigned char c2 = tolower(*name);
199                         if (c1 == '\0' || (!literal && is_glob_special(c1)))
200                                 break;
201                         if (c1 != c2)
202                                 return 0;
203                         match++;
204                         name++;
205                         namelen--;
206                 }
207         } else {
208                 for (;;) {
209                         unsigned char c1 = *match;
210                         unsigned char c2 = *name;
211                         if (c1 == '\0' || (!literal && is_glob_special(c1)))
212                                 break;
213                         if (c1 != c2)
214                                 return 0;
215                         match++;
216                         name++;
217                         namelen--;
218                 }
219         }
220
221         /*
222          * If we don't match the matchstring exactly,
223          * we need to match by fnmatch
224          */
225         matchlen = strlen(match);
226         if (strncmp_icase(match, name, matchlen)) {
227                 if (literal)
228                         return 0;
229                 return !fnmatch_icase(match, name, 0) ? MATCHED_FNMATCH : 0;
230         }
231
232         if (namelen == matchlen)
233                 return MATCHED_EXACTLY;
234         if (match[matchlen-1] == '/' || name[matchlen] == '/')
235                 return MATCHED_RECURSIVELY;
236         return 0;
237 }
238
239 /*
240  * Given a name and a list of pathspecs, returns the nature of the
241  * closest (i.e. most specific) match of the name to any of the
242  * pathspecs.
243  *
244  * The caller typically calls this multiple times with the same
245  * pathspec and seen[] array but with different name/namelen
246  * (e.g. entries from the index) and is interested in seeing if and
247  * how each pathspec matches all the names it calls this function
248  * with.  A mark is left in the seen[] array for each pathspec element
249  * indicating the closest type of match that element achieved, so if
250  * seen[n] remains zero after multiple invocations, that means the nth
251  * pathspec did not match any names, which could indicate that the
252  * user mistyped the nth pathspec.
253  */
254 int match_pathspec(const char **pathspec, const char *name, int namelen,
255                 int prefix, char *seen)
256 {
257         int i, retval = 0;
258
259         if (!pathspec)
260                 return 1;
261
262         name += prefix;
263         namelen -= prefix;
264
265         for (i = 0; pathspec[i] != NULL; i++) {
266                 int how;
267                 const char *match = pathspec[i] + prefix;
268                 if (seen && seen[i] == MATCHED_EXACTLY)
269                         continue;
270                 how = match_one(match, name, namelen);
271                 if (how) {
272                         if (retval < how)
273                                 retval = how;
274                         if (seen && seen[i] < how)
275                                 seen[i] = how;
276                 }
277         }
278         return retval;
279 }
280
281 /*
282  * Does 'match' match the given name?
283  * A match is found if
284  *
285  * (1) the 'match' string is leading directory of 'name', or
286  * (2) the 'match' string is a wildcard and matches 'name', or
287  * (3) the 'match' string is exactly the same as 'name'.
288  *
289  * and the return value tells which case it was.
290  *
291  * It returns 0 when there is no match.
292  */
293 static int match_pathspec_item(const struct pathspec_item *item, int prefix,
294                                const char *name, int namelen)
295 {
296         /* name/namelen has prefix cut off by caller */
297         const char *match = item->match + prefix;
298         int matchlen = item->len - prefix;
299
300         /* If the match was just the prefix, we matched */
301         if (!*match)
302                 return MATCHED_RECURSIVELY;
303
304         if (matchlen <= namelen && !strncmp(match, name, matchlen)) {
305                 if (matchlen == namelen)
306                         return MATCHED_EXACTLY;
307
308                 if (match[matchlen-1] == '/' || name[matchlen] == '/')
309                         return MATCHED_RECURSIVELY;
310         }
311
312         if (item->nowildcard_len < item->len &&
313             !git_fnmatch(match, name,
314                          item->flags & PATHSPEC_ONESTAR ? GFNM_ONESTAR : 0,
315                          item->nowildcard_len - prefix))
316                 return MATCHED_FNMATCH;
317
318         return 0;
319 }
320
321 /*
322  * Given a name and a list of pathspecs, returns the nature of the
323  * closest (i.e. most specific) match of the name to any of the
324  * pathspecs.
325  *
326  * The caller typically calls this multiple times with the same
327  * pathspec and seen[] array but with different name/namelen
328  * (e.g. entries from the index) and is interested in seeing if and
329  * how each pathspec matches all the names it calls this function
330  * with.  A mark is left in the seen[] array for each pathspec element
331  * indicating the closest type of match that element achieved, so if
332  * seen[n] remains zero after multiple invocations, that means the nth
333  * pathspec did not match any names, which could indicate that the
334  * user mistyped the nth pathspec.
335  */
336 int match_pathspec_depth(const struct pathspec *ps,
337                          const char *name, int namelen,
338                          int prefix, char *seen)
339 {
340         int i, retval = 0;
341
342         if (!ps->nr) {
343                 if (!ps->recursive || ps->max_depth == -1)
344                         return MATCHED_RECURSIVELY;
345
346                 if (within_depth(name, namelen, 0, ps->max_depth))
347                         return MATCHED_EXACTLY;
348                 else
349                         return 0;
350         }
351
352         name += prefix;
353         namelen -= prefix;
354
355         for (i = ps->nr - 1; i >= 0; i--) {
356                 int how;
357                 if (seen && seen[i] == MATCHED_EXACTLY)
358                         continue;
359                 how = match_pathspec_item(ps->items+i, prefix, name, namelen);
360                 if (ps->recursive && ps->max_depth != -1 &&
361                     how && how != MATCHED_FNMATCH) {
362                         int len = ps->items[i].len;
363                         if (name[len] == '/')
364                                 len++;
365                         if (within_depth(name+len, namelen-len, 0, ps->max_depth))
366                                 how = MATCHED_EXACTLY;
367                         else
368                                 how = 0;
369                 }
370                 if (how) {
371                         if (retval < how)
372                                 retval = how;
373                         if (seen && seen[i] < how)
374                                 seen[i] = how;
375                 }
376         }
377         return retval;
378 }
379
380 /*
381  * Return the length of the "simple" part of a path match limiter.
382  */
383 static int simple_length(const char *match)
384 {
385         int len = -1;
386
387         for (;;) {
388                 unsigned char c = *match++;
389                 len++;
390                 if (c == '\0' || is_glob_special(c))
391                         return len;
392         }
393 }
394
395 static int no_wildcard(const char *string)
396 {
397         return string[simple_length(string)] == '\0';
398 }
399
400 void parse_exclude_pattern(const char **pattern,
401                            int *patternlen,
402                            int *flags,
403                            int *nowildcardlen)
404 {
405         const char *p = *pattern;
406         size_t i, len;
407
408         *flags = 0;
409         if (*p == '!') {
410                 *flags |= EXC_FLAG_NEGATIVE;
411                 p++;
412         }
413         len = strlen(p);
414         if (len && p[len - 1] == '/') {
415                 len--;
416                 *flags |= EXC_FLAG_MUSTBEDIR;
417         }
418         for (i = 0; i < len; i++) {
419                 if (p[i] == '/')
420                         break;
421         }
422         if (i == len)
423                 *flags |= EXC_FLAG_NODIR;
424         *nowildcardlen = simple_length(p);
425         /*
426          * we should have excluded the trailing slash from 'p' too,
427          * but that's one more allocation. Instead just make sure
428          * nowildcardlen does not exceed real patternlen
429          */
430         if (*nowildcardlen > len)
431                 *nowildcardlen = len;
432         if (*p == '*' && no_wildcard(p + 1))
433                 *flags |= EXC_FLAG_ENDSWITH;
434         *pattern = p;
435         *patternlen = len;
436 }
437
438 void add_exclude(const char *string, const char *base,
439                  int baselen, struct exclude_list *el, int srcpos)
440 {
441         struct exclude *x;
442         int patternlen;
443         int flags;
444         int nowildcardlen;
445
446         parse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen);
447         if (flags & EXC_FLAG_MUSTBEDIR) {
448                 char *s;
449                 x = xmalloc(sizeof(*x) + patternlen + 1);
450                 s = (char *)(x+1);
451                 memcpy(s, string, patternlen);
452                 s[patternlen] = '\0';
453                 x->pattern = s;
454         } else {
455                 x = xmalloc(sizeof(*x));
456                 x->pattern = string;
457         }
458         x->patternlen = patternlen;
459         x->nowildcardlen = nowildcardlen;
460         x->base = base;
461         x->baselen = baselen;
462         x->flags = flags;
463         x->srcpos = srcpos;
464         ALLOC_GROW(el->excludes, el->nr + 1, el->alloc);
465         el->excludes[el->nr++] = x;
466         x->el = el;
467 }
468
469 static void *read_skip_worktree_file_from_index(const char *path, size_t *size)
470 {
471         int pos, len;
472         unsigned long sz;
473         enum object_type type;
474         void *data;
475         struct index_state *istate = &the_index;
476
477         len = strlen(path);
478         pos = index_name_pos(istate, path, len);
479         if (pos < 0)
480                 return NULL;
481         if (!ce_skip_worktree(istate->cache[pos]))
482                 return NULL;
483         data = read_sha1_file(istate->cache[pos]->sha1, &type, &sz);
484         if (!data || type != OBJ_BLOB) {
485                 free(data);
486                 return NULL;
487         }
488         *size = xsize_t(sz);
489         return data;
490 }
491
492 /*
493  * Frees memory within el which was allocated for exclude patterns and
494  * the file buffer.  Does not free el itself.
495  */
496 void clear_exclude_list(struct exclude_list *el)
497 {
498         int i;
499
500         for (i = 0; i < el->nr; i++)
501                 free(el->excludes[i]);
502         free(el->excludes);
503         free(el->filebuf);
504
505         el->nr = 0;
506         el->excludes = NULL;
507         el->filebuf = NULL;
508 }
509
510 int add_excludes_from_file_to_list(const char *fname,
511                                    const char *base,
512                                    int baselen,
513                                    struct exclude_list *el,
514                                    int check_index)
515 {
516         struct stat st;
517         int fd, i, lineno = 1;
518         size_t size = 0;
519         char *buf, *entry;
520
521         fd = open(fname, O_RDONLY);
522         if (fd < 0 || fstat(fd, &st) < 0) {
523                 if (errno != ENOENT)
524                         warn_on_inaccessible(fname);
525                 if (0 <= fd)
526                         close(fd);
527                 if (!check_index ||
528                     (buf = read_skip_worktree_file_from_index(fname, &size)) == NULL)
529                         return -1;
530                 if (size == 0) {
531                         free(buf);
532                         return 0;
533                 }
534                 if (buf[size-1] != '\n') {
535                         buf = xrealloc(buf, size+1);
536                         buf[size++] = '\n';
537                 }
538         }
539         else {
540                 size = xsize_t(st.st_size);
541                 if (size == 0) {
542                         close(fd);
543                         return 0;
544                 }
545                 buf = xmalloc(size+1);
546                 if (read_in_full(fd, buf, size) != size) {
547                         free(buf);
548                         close(fd);
549                         return -1;
550                 }
551                 buf[size++] = '\n';
552                 close(fd);
553         }
554
555         el->filebuf = buf;
556         entry = buf;
557         for (i = 0; i < size; i++) {
558                 if (buf[i] == '\n') {
559                         if (entry != buf + i && entry[0] != '#') {
560                                 buf[i - (i && buf[i-1] == '\r')] = 0;
561                                 add_exclude(entry, base, baselen, el, lineno);
562                         }
563                         lineno++;
564                         entry = buf + i + 1;
565                 }
566         }
567         return 0;
568 }
569
570 struct exclude_list *add_exclude_list(struct dir_struct *dir,
571                                       int group_type, const char *src)
572 {
573         struct exclude_list *el;
574         struct exclude_list_group *group;
575
576         group = &dir->exclude_list_group[group_type];
577         ALLOC_GROW(group->el, group->nr + 1, group->alloc);
578         el = &group->el[group->nr++];
579         memset(el, 0, sizeof(*el));
580         el->src = src;
581         return el;
582 }
583
584 /*
585  * Used to set up core.excludesfile and .git/info/exclude lists.
586  */
587 void add_excludes_from_file(struct dir_struct *dir, const char *fname)
588 {
589         struct exclude_list *el;
590         el = add_exclude_list(dir, EXC_FILE, fname);
591         if (add_excludes_from_file_to_list(fname, "", 0, el, 0) < 0)
592                 die("cannot use %s as an exclude file", fname);
593 }
594
595 int match_basename(const char *basename, int basenamelen,
596                    const char *pattern, int prefix, int patternlen,
597                    int flags)
598 {
599         if (prefix == patternlen) {
600                 if (patternlen == basenamelen &&
601                     !strncmp_icase(pattern, basename, basenamelen))
602                         return 1;
603         } else if (flags & EXC_FLAG_ENDSWITH) {
604                 /* "*literal" matching against "fooliteral" */
605                 if (patternlen - 1 <= basenamelen &&
606                     !strncmp_icase(pattern + 1,
607                                    basename + basenamelen - (patternlen - 1),
608                                    patternlen - 1))
609                         return 1;
610         } else {
611                 if (fnmatch_icase_mem(pattern, patternlen,
612                                       basename, basenamelen,
613                                       0) == 0)
614                         return 1;
615         }
616         return 0;
617 }
618
619 int match_pathname(const char *pathname, int pathlen,
620                    const char *base, int baselen,
621                    const char *pattern, int prefix, int patternlen,
622                    int flags)
623 {
624         const char *name;
625         int namelen;
626
627         /*
628          * match with FNM_PATHNAME; the pattern has base implicitly
629          * in front of it.
630          */
631         if (*pattern == '/') {
632                 pattern++;
633                 patternlen--;
634                 prefix--;
635         }
636
637         /*
638          * baselen does not count the trailing slash. base[] may or
639          * may not end with a trailing slash though.
640          */
641         if (pathlen < baselen + 1 ||
642             (baselen && pathname[baselen] != '/') ||
643             strncmp_icase(pathname, base, baselen))
644                 return 0;
645
646         namelen = baselen ? pathlen - baselen - 1 : pathlen;
647         name = pathname + pathlen - namelen;
648
649         if (prefix) {
650                 /*
651                  * if the non-wildcard part is longer than the
652                  * remaining pathname, surely it cannot match.
653                  */
654                 if (prefix > namelen)
655                         return 0;
656
657                 if (strncmp_icase(pattern, name, prefix))
658                         return 0;
659                 pattern += prefix;
660                 patternlen -= prefix;
661                 name    += prefix;
662                 namelen -= prefix;
663
664                 /*
665                  * If the whole pattern did not have a wildcard,
666                  * then our prefix match is all we need; we
667                  * do not need to call fnmatch at all.
668                  */
669                 if (!patternlen && !namelen)
670                         return 1;
671         }
672
673         return fnmatch_icase_mem(pattern, patternlen,
674                                  name, namelen,
675                                  WM_PATHNAME) == 0;
676 }
677
678 /*
679  * Scan the given exclude list in reverse to see whether pathname
680  * should be ignored.  The first match (i.e. the last on the list), if
681  * any, determines the fate.  Returns the exclude_list element which
682  * matched, or NULL for undecided.
683  */
684 static struct exclude *last_exclude_matching_from_list(const char *pathname,
685                                                        int pathlen,
686                                                        const char *basename,
687                                                        int *dtype,
688                                                        struct exclude_list *el)
689 {
690         int i;
691
692         if (!el->nr)
693                 return NULL;    /* undefined */
694
695         for (i = el->nr - 1; 0 <= i; i--) {
696                 struct exclude *x = el->excludes[i];
697                 const char *exclude = x->pattern;
698                 int prefix = x->nowildcardlen;
699
700                 if (x->flags & EXC_FLAG_MUSTBEDIR) {
701                         if (*dtype == DT_UNKNOWN)
702                                 *dtype = get_dtype(NULL, pathname, pathlen);
703                         if (*dtype != DT_DIR)
704                                 continue;
705                 }
706
707                 if (x->flags & EXC_FLAG_NODIR) {
708                         if (match_basename(basename,
709                                            pathlen - (basename - pathname),
710                                            exclude, prefix, x->patternlen,
711                                            x->flags))
712                                 return x;
713                         continue;
714                 }
715
716                 assert(x->baselen == 0 || x->base[x->baselen - 1] == '/');
717                 if (match_pathname(pathname, pathlen,
718                                    x->base, x->baselen ? x->baselen - 1 : 0,
719                                    exclude, prefix, x->patternlen, x->flags))
720                         return x;
721         }
722         return NULL; /* undecided */
723 }
724
725 /*
726  * Scan the list and let the last match determine the fate.
727  * Return 1 for exclude, 0 for include and -1 for undecided.
728  */
729 int is_excluded_from_list(const char *pathname,
730                           int pathlen, const char *basename, int *dtype,
731                           struct exclude_list *el)
732 {
733         struct exclude *exclude;
734         exclude = last_exclude_matching_from_list(pathname, pathlen, basename, dtype, el);
735         if (exclude)
736                 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
737         return -1; /* undecided */
738 }
739
740 static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir,
741                 const char *pathname, int pathlen, const char *basename,
742                 int *dtype_p)
743 {
744         int i, j;
745         struct exclude_list_group *group;
746         struct exclude *exclude;
747         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
748                 group = &dir->exclude_list_group[i];
749                 for (j = group->nr - 1; j >= 0; j--) {
750                         exclude = last_exclude_matching_from_list(
751                                 pathname, pathlen, basename, dtype_p,
752                                 &group->el[j]);
753                         if (exclude)
754                                 return exclude;
755                 }
756         }
757         return NULL;
758 }
759
760 /*
761  * Loads the per-directory exclude list for the substring of base
762  * which has a char length of baselen.
763  */
764 static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
765 {
766         struct exclude_list_group *group;
767         struct exclude_list *el;
768         struct exclude_stack *stk = NULL;
769         int current;
770
771         group = &dir->exclude_list_group[EXC_DIRS];
772
773         /* Pop the exclude lists from the EXCL_DIRS exclude_list_group
774          * which originate from directories not in the prefix of the
775          * path being checked. */
776         while ((stk = dir->exclude_stack) != NULL) {
777                 if (stk->baselen <= baselen &&
778                     !strncmp(dir->basebuf, base, stk->baselen))
779                         break;
780                 el = &group->el[dir->exclude_stack->exclude_ix];
781                 dir->exclude_stack = stk->prev;
782                 dir->exclude = NULL;
783                 free((char *)el->src); /* see strdup() below */
784                 clear_exclude_list(el);
785                 free(stk);
786                 group->nr--;
787         }
788
789         /* Skip traversing into sub directories if the parent is excluded */
790         if (dir->exclude)
791                 return;
792
793         /* Read from the parent directories and push them down. */
794         current = stk ? stk->baselen : -1;
795         while (current < baselen) {
796                 struct exclude_stack *stk = xcalloc(1, sizeof(*stk));
797                 const char *cp;
798
799                 if (current < 0) {
800                         cp = base;
801                         current = 0;
802                 }
803                 else {
804                         cp = strchr(base + current + 1, '/');
805                         if (!cp)
806                                 die("oops in prep_exclude");
807                         cp++;
808                 }
809                 stk->prev = dir->exclude_stack;
810                 stk->baselen = cp - base;
811                 stk->exclude_ix = group->nr;
812                 el = add_exclude_list(dir, EXC_DIRS, NULL);
813                 memcpy(dir->basebuf + current, base + current,
814                        stk->baselen - current);
815
816                 /* Abort if the directory is excluded */
817                 if (stk->baselen) {
818                         int dt = DT_DIR;
819                         dir->basebuf[stk->baselen - 1] = 0;
820                         dir->exclude = last_exclude_matching_from_lists(dir,
821                                 dir->basebuf, stk->baselen - 1,
822                                 dir->basebuf + current, &dt);
823                         dir->basebuf[stk->baselen - 1] = '/';
824                         if (dir->exclude) {
825                                 dir->basebuf[stk->baselen] = 0;
826                                 dir->exclude_stack = stk;
827                                 return;
828                         }
829                 }
830
831                 /* Try to read per-directory file unless path is too long */
832                 if (dir->exclude_per_dir &&
833                     stk->baselen + strlen(dir->exclude_per_dir) < PATH_MAX) {
834                         strcpy(dir->basebuf + stk->baselen,
835                                         dir->exclude_per_dir);
836                         /*
837                          * dir->basebuf gets reused by the traversal, but we
838                          * need fname to remain unchanged to ensure the src
839                          * member of each struct exclude correctly
840                          * back-references its source file.  Other invocations
841                          * of add_exclude_list provide stable strings, so we
842                          * strdup() and free() here in the caller.
843                          */
844                         el->src = strdup(dir->basebuf);
845                         add_excludes_from_file_to_list(dir->basebuf,
846                                         dir->basebuf, stk->baselen, el, 1);
847                 }
848                 dir->exclude_stack = stk;
849                 current = stk->baselen;
850         }
851         dir->basebuf[baselen] = '\0';
852 }
853
854 /*
855  * Loads the exclude lists for the directory containing pathname, then
856  * scans all exclude lists to determine whether pathname is excluded.
857  * Returns the exclude_list element which matched, or NULL for
858  * undecided.
859  */
860 struct exclude *last_exclude_matching(struct dir_struct *dir,
861                                              const char *pathname,
862                                              int *dtype_p)
863 {
864         int pathlen = strlen(pathname);
865         const char *basename = strrchr(pathname, '/');
866         basename = (basename) ? basename+1 : pathname;
867
868         prep_exclude(dir, pathname, basename-pathname);
869
870         if (dir->exclude)
871                 return dir->exclude;
872
873         return last_exclude_matching_from_lists(dir, pathname, pathlen,
874                         basename, dtype_p);
875 }
876
877 /*
878  * Loads the exclude lists for the directory containing pathname, then
879  * scans all exclude lists to determine whether pathname is excluded.
880  * Returns 1 if true, otherwise 0.
881  */
882 int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
883 {
884         struct exclude *exclude =
885                 last_exclude_matching(dir, pathname, dtype_p);
886         if (exclude)
887                 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
888         return 0;
889 }
890
891 static struct dir_entry *dir_entry_new(const char *pathname, int len)
892 {
893         struct dir_entry *ent;
894
895         ent = xmalloc(sizeof(*ent) + len + 1);
896         ent->len = len;
897         memcpy(ent->name, pathname, len);
898         ent->name[len] = 0;
899         return ent;
900 }
901
902 static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
903 {
904         if (cache_name_exists(pathname, len, ignore_case))
905                 return NULL;
906
907         ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
908         return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
909 }
910
911 struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len)
912 {
913         if (!cache_name_is_other(pathname, len))
914                 return NULL;
915
916         ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
917         return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
918 }
919
920 enum exist_status {
921         index_nonexistent = 0,
922         index_directory,
923         index_gitdir
924 };
925
926 /*
927  * Do not use the alphabetically stored index to look up
928  * the directory name; instead, use the case insensitive
929  * name hash.
930  */
931 static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
932 {
933         struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);
934         unsigned char endchar;
935
936         if (!ce)
937                 return index_nonexistent;
938         endchar = ce->name[len];
939
940         /*
941          * The cache_entry structure returned will contain this dirname
942          * and possibly additional path components.
943          */
944         if (endchar == '/')
945                 return index_directory;
946
947         /*
948          * If there are no additional path components, then this cache_entry
949          * represents a submodule.  Submodules, despite being directories,
950          * are stored in the cache without a closing slash.
951          */
952         if (!endchar && S_ISGITLINK(ce->ce_mode))
953                 return index_gitdir;
954
955         /* This should never be hit, but it exists just in case. */
956         return index_nonexistent;
957 }
958
959 /*
960  * The index sorts alphabetically by entry name, which
961  * means that a gitlink sorts as '\0' at the end, while
962  * a directory (which is defined not as an entry, but as
963  * the files it contains) will sort with the '/' at the
964  * end.
965  */
966 static enum exist_status directory_exists_in_index(const char *dirname, int len)
967 {
968         int pos;
969
970         if (ignore_case)
971                 return directory_exists_in_index_icase(dirname, len);
972
973         pos = cache_name_pos(dirname, len);
974         if (pos < 0)
975                 pos = -pos-1;
976         while (pos < active_nr) {
977                 struct cache_entry *ce = active_cache[pos++];
978                 unsigned char endchar;
979
980                 if (strncmp(ce->name, dirname, len))
981                         break;
982                 endchar = ce->name[len];
983                 if (endchar > '/')
984                         break;
985                 if (endchar == '/')
986                         return index_directory;
987                 if (!endchar && S_ISGITLINK(ce->ce_mode))
988                         return index_gitdir;
989         }
990         return index_nonexistent;
991 }
992
993 /*
994  * When we find a directory when traversing the filesystem, we
995  * have three distinct cases:
996  *
997  *  - ignore it
998  *  - see it as a directory
999  *  - recurse into it
1000  *
1001  * and which one we choose depends on a combination of existing
1002  * git index contents and the flags passed into the directory
1003  * traversal routine.
1004  *
1005  * Case 1: If we *already* have entries in the index under that
1006  * directory name, we always recurse into the directory to see
1007  * all the files.
1008  *
1009  * Case 2: If we *already* have that directory name as a gitlink,
1010  * we always continue to see it as a gitlink, regardless of whether
1011  * there is an actual git directory there or not (it might not
1012  * be checked out as a subproject!)
1013  *
1014  * Case 3: if we didn't have it in the index previously, we
1015  * have a few sub-cases:
1016  *
1017  *  (a) if "show_other_directories" is true, we show it as
1018  *      just a directory, unless "hide_empty_directories" is
1019  *      also true, in which case we need to check if it contains any
1020  *      untracked and / or ignored files.
1021  *  (b) if it looks like a git directory, and we don't have
1022  *      'no_gitlinks' set we treat it as a gitlink, and show it
1023  *      as a directory.
1024  *  (c) otherwise, we recurse into it.
1025  */
1026 static enum path_treatment treat_directory(struct dir_struct *dir,
1027         const char *dirname, int len, int exclude,
1028         const struct path_simplify *simplify)
1029 {
1030         /* The "len-1" is to strip the final '/' */
1031         switch (directory_exists_in_index(dirname, len-1)) {
1032         case index_directory:
1033                 return path_recurse;
1034
1035         case index_gitdir:
1036                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1037                         return path_none;
1038                 return path_untracked;
1039
1040         case index_nonexistent:
1041                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1042                         break;
1043                 if (!(dir->flags & DIR_NO_GITLINKS)) {
1044                         unsigned char sha1[20];
1045                         if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)
1046                                 return path_untracked;
1047                 }
1048                 return path_recurse;
1049         }
1050
1051         /* This is the "show_other_directories" case */
1052
1053         if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1054                 return exclude ? path_excluded : path_untracked;
1055
1056         return read_directory_recursive(dir, dirname, len, 1, simplify);
1057 }
1058
1059 /*
1060  * This is an inexact early pruning of any recursive directory
1061  * reading - if the path cannot possibly be in the pathspec,
1062  * return true, and we'll skip it early.
1063  */
1064 static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)
1065 {
1066         if (simplify) {
1067                 for (;;) {
1068                         const char *match = simplify->path;
1069                         int len = simplify->len;
1070
1071                         if (!match)
1072                                 break;
1073                         if (len > pathlen)
1074                                 len = pathlen;
1075                         if (!memcmp(path, match, len))
1076                                 return 0;
1077                         simplify++;
1078                 }
1079                 return 1;
1080         }
1081         return 0;
1082 }
1083
1084 /*
1085  * This function tells us whether an excluded path matches a
1086  * list of "interesting" pathspecs. That is, whether a path matched
1087  * by any of the pathspecs could possibly be ignored by excluding
1088  * the specified path. This can happen if:
1089  *
1090  *   1. the path is mentioned explicitly in the pathspec
1091  *
1092  *   2. the path is a directory prefix of some element in the
1093  *      pathspec
1094  */
1095 static int exclude_matches_pathspec(const char *path, int len,
1096                 const struct path_simplify *simplify)
1097 {
1098         if (simplify) {
1099                 for (; simplify->path; simplify++) {
1100                         if (len == simplify->len
1101                             && !memcmp(path, simplify->path, len))
1102                                 return 1;
1103                         if (len < simplify->len
1104                             && simplify->path[len] == '/'
1105                             && !memcmp(path, simplify->path, len))
1106                                 return 1;
1107                 }
1108         }
1109         return 0;
1110 }
1111
1112 static int get_index_dtype(const char *path, int len)
1113 {
1114         int pos;
1115         struct cache_entry *ce;
1116
1117         ce = cache_name_exists(path, len, 0);
1118         if (ce) {
1119                 if (!ce_uptodate(ce))
1120                         return DT_UNKNOWN;
1121                 if (S_ISGITLINK(ce->ce_mode))
1122                         return DT_DIR;
1123                 /*
1124                  * Nobody actually cares about the
1125                  * difference between DT_LNK and DT_REG
1126                  */
1127                 return DT_REG;
1128         }
1129
1130         /* Try to look it up as a directory */
1131         pos = cache_name_pos(path, len);
1132         if (pos >= 0)
1133                 return DT_UNKNOWN;
1134         pos = -pos-1;
1135         while (pos < active_nr) {
1136                 ce = active_cache[pos++];
1137                 if (strncmp(ce->name, path, len))
1138                         break;
1139                 if (ce->name[len] > '/')
1140                         break;
1141                 if (ce->name[len] < '/')
1142                         continue;
1143                 if (!ce_uptodate(ce))
1144                         break;  /* continue? */
1145                 return DT_DIR;
1146         }
1147         return DT_UNKNOWN;
1148 }
1149
1150 static int get_dtype(struct dirent *de, const char *path, int len)
1151 {
1152         int dtype = de ? DTYPE(de) : DT_UNKNOWN;
1153         struct stat st;
1154
1155         if (dtype != DT_UNKNOWN)
1156                 return dtype;
1157         dtype = get_index_dtype(path, len);
1158         if (dtype != DT_UNKNOWN)
1159                 return dtype;
1160         if (lstat(path, &st))
1161                 return dtype;
1162         if (S_ISREG(st.st_mode))
1163                 return DT_REG;
1164         if (S_ISDIR(st.st_mode))
1165                 return DT_DIR;
1166         if (S_ISLNK(st.st_mode))
1167                 return DT_LNK;
1168         return dtype;
1169 }
1170
1171 static enum path_treatment treat_one_path(struct dir_struct *dir,
1172                                           struct strbuf *path,
1173                                           const struct path_simplify *simplify,
1174                                           int dtype, struct dirent *de)
1175 {
1176         int exclude;
1177         if (dtype == DT_UNKNOWN)
1178                 dtype = get_dtype(de, path->buf, path->len);
1179
1180         /* Always exclude indexed files */
1181         if (dtype != DT_DIR &&
1182             cache_name_exists(path->buf, path->len, ignore_case))
1183                 return path_none;
1184
1185         exclude = is_excluded(dir, path->buf, &dtype);
1186
1187         /*
1188          * Excluded? If we don't explicitly want to show
1189          * ignored files, ignore it
1190          */
1191         if (exclude && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
1192                 return path_excluded;
1193
1194         switch (dtype) {
1195         default:
1196                 return path_none;
1197         case DT_DIR:
1198                 strbuf_addch(path, '/');
1199                 return treat_directory(dir, path->buf, path->len, exclude,
1200                         simplify);
1201         case DT_REG:
1202         case DT_LNK:
1203                 return exclude ? path_excluded : path_untracked;
1204         }
1205 }
1206
1207 static enum path_treatment treat_path(struct dir_struct *dir,
1208                                       struct dirent *de,
1209                                       struct strbuf *path,
1210                                       int baselen,
1211                                       const struct path_simplify *simplify)
1212 {
1213         int dtype;
1214
1215         if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
1216                 return path_none;
1217         strbuf_setlen(path, baselen);
1218         strbuf_addstr(path, de->d_name);
1219         if (simplify_away(path->buf, path->len, simplify))
1220                 return path_none;
1221
1222         dtype = DTYPE(de);
1223         return treat_one_path(dir, path, simplify, dtype, de);
1224 }
1225
1226 /*
1227  * Read a directory tree. We currently ignore anything but
1228  * directories, regular files and symlinks. That's because git
1229  * doesn't handle them at all yet. Maybe that will change some
1230  * day.
1231  *
1232  * Also, we ignore the name ".git" (even if it is not a directory).
1233  * That likely will not change.
1234  *
1235  * Returns the most significant path_treatment value encountered in the scan.
1236  */
1237 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
1238                                     const char *base, int baselen,
1239                                     int check_only,
1240                                     const struct path_simplify *simplify)
1241 {
1242         DIR *fdir;
1243         enum path_treatment state, subdir_state, dir_state = path_none;
1244         struct dirent *de;
1245         struct strbuf path = STRBUF_INIT;
1246
1247         strbuf_add(&path, base, baselen);
1248
1249         fdir = opendir(path.len ? path.buf : ".");
1250         if (!fdir)
1251                 goto out;
1252
1253         while ((de = readdir(fdir)) != NULL) {
1254                 /* check how the file or directory should be treated */
1255                 state = treat_path(dir, de, &path, baselen, simplify);
1256                 if (state > dir_state)
1257                         dir_state = state;
1258
1259                 /* recurse into subdir if instructed by treat_path */
1260                 if (state == path_recurse) {
1261                         subdir_state = read_directory_recursive(dir, path.buf,
1262                                 path.len, check_only, simplify);
1263                         if (subdir_state > dir_state)
1264                                 dir_state = subdir_state;
1265                 }
1266
1267                 if (check_only) {
1268                         /* abort early if maximum state has been reached */
1269                         if (dir_state == path_untracked)
1270                                 break;
1271                         /* skip the dir_add_* part */
1272                         continue;
1273                 }
1274
1275                 /* add the path to the appropriate result list */
1276                 switch (state) {
1277                 case path_excluded:
1278                         if (dir->flags & DIR_SHOW_IGNORED)
1279                                 dir_add_name(dir, path.buf, path.len);
1280                         else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
1281                                 ((dir->flags & DIR_COLLECT_IGNORED) &&
1282                                 exclude_matches_pathspec(path.buf, path.len,
1283                                         simplify)))
1284                                 dir_add_ignored(dir, path.buf, path.len);
1285                         break;
1286
1287                 case path_untracked:
1288                         if (!(dir->flags & DIR_SHOW_IGNORED))
1289                                 dir_add_name(dir, path.buf, path.len);
1290                         break;
1291
1292                 default:
1293                         break;
1294                 }
1295         }
1296         closedir(fdir);
1297  out:
1298         strbuf_release(&path);
1299
1300         return dir_state;
1301 }
1302
1303 static int cmp_name(const void *p1, const void *p2)
1304 {
1305         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
1306         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
1307
1308         return cache_name_compare(e1->name, e1->len,
1309                                   e2->name, e2->len);
1310 }
1311
1312 static struct path_simplify *create_simplify(const char **pathspec)
1313 {
1314         int nr, alloc = 0;
1315         struct path_simplify *simplify = NULL;
1316
1317         if (!pathspec)
1318                 return NULL;
1319
1320         for (nr = 0 ; ; nr++) {
1321                 const char *match;
1322                 if (nr >= alloc) {
1323                         alloc = alloc_nr(alloc);
1324                         simplify = xrealloc(simplify, alloc * sizeof(*simplify));
1325                 }
1326                 match = *pathspec++;
1327                 if (!match)
1328                         break;
1329                 simplify[nr].path = match;
1330                 simplify[nr].len = simple_length(match);
1331         }
1332         simplify[nr].path = NULL;
1333         simplify[nr].len = 0;
1334         return simplify;
1335 }
1336
1337 static void free_simplify(struct path_simplify *simplify)
1338 {
1339         free(simplify);
1340 }
1341
1342 static int treat_leading_path(struct dir_struct *dir,
1343                               const char *path, int len,
1344                               const struct path_simplify *simplify)
1345 {
1346         struct strbuf sb = STRBUF_INIT;
1347         int baselen, rc = 0;
1348         const char *cp;
1349         int old_flags = dir->flags;
1350
1351         while (len && path[len - 1] == '/')
1352                 len--;
1353         if (!len)
1354                 return 1;
1355         baselen = 0;
1356         dir->flags &= ~DIR_SHOW_OTHER_DIRECTORIES;
1357         while (1) {
1358                 cp = path + baselen + !!baselen;
1359                 cp = memchr(cp, '/', path + len - cp);
1360                 if (!cp)
1361                         baselen = len;
1362                 else
1363                         baselen = cp - path;
1364                 strbuf_setlen(&sb, 0);
1365                 strbuf_add(&sb, path, baselen);
1366                 if (!is_directory(sb.buf))
1367                         break;
1368                 if (simplify_away(sb.buf, sb.len, simplify))
1369                         break;
1370                 if (treat_one_path(dir, &sb, simplify,
1371                                    DT_DIR, NULL) == path_none)
1372                         break; /* do not recurse into it */
1373                 if (len <= baselen) {
1374                         rc = 1;
1375                         break; /* finished checking */
1376                 }
1377         }
1378         strbuf_release(&sb);
1379         dir->flags = old_flags;
1380         return rc;
1381 }
1382
1383 int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
1384 {
1385         struct path_simplify *simplify;
1386
1387         if (has_symlink_leading_path(path, len))
1388                 return dir->nr;
1389
1390         simplify = create_simplify(pathspec);
1391         if (!len || treat_leading_path(dir, path, len, simplify))
1392                 read_directory_recursive(dir, path, len, 0, simplify);
1393         free_simplify(simplify);
1394         qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
1395         qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
1396         return dir->nr;
1397 }
1398
1399 int file_exists(const char *f)
1400 {
1401         struct stat sb;
1402         return lstat(f, &sb) == 0;
1403 }
1404
1405 /*
1406  * Given two normalized paths (a trailing slash is ok), if subdir is
1407  * outside dir, return -1.  Otherwise return the offset in subdir that
1408  * can be used as relative path to dir.
1409  */
1410 int dir_inside_of(const char *subdir, const char *dir)
1411 {
1412         int offset = 0;
1413
1414         assert(dir && subdir && *dir && *subdir);
1415
1416         while (*dir && *subdir && *dir == *subdir) {
1417                 dir++;
1418                 subdir++;
1419                 offset++;
1420         }
1421
1422         /* hel[p]/me vs hel[l]/yeah */
1423         if (*dir && *subdir)
1424                 return -1;
1425
1426         if (!*subdir)
1427                 return !*dir ? offset : -1; /* same dir */
1428
1429         /* foo/[b]ar vs foo/[] */
1430         if (is_dir_sep(dir[-1]))
1431                 return is_dir_sep(subdir[-1]) ? offset : -1;
1432
1433         /* foo[/]bar vs foo[] */
1434         return is_dir_sep(*subdir) ? offset + 1 : -1;
1435 }
1436
1437 int is_inside_dir(const char *dir)
1438 {
1439         char cwd[PATH_MAX];
1440         if (!dir)
1441                 return 0;
1442         if (!getcwd(cwd, sizeof(cwd)))
1443                 die_errno("can't find the current directory");
1444         return dir_inside_of(cwd, dir) >= 0;
1445 }
1446
1447 int is_empty_dir(const char *path)
1448 {
1449         DIR *dir = opendir(path);
1450         struct dirent *e;
1451         int ret = 1;
1452
1453         if (!dir)
1454                 return 0;
1455
1456         while ((e = readdir(dir)) != NULL)
1457                 if (!is_dot_or_dotdot(e->d_name)) {
1458                         ret = 0;
1459                         break;
1460                 }
1461
1462         closedir(dir);
1463         return ret;
1464 }
1465
1466 static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
1467 {
1468         DIR *dir;
1469         struct dirent *e;
1470         int ret = 0, original_len = path->len, len, kept_down = 0;
1471         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
1472         int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
1473         unsigned char submodule_head[20];
1474
1475         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
1476             !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
1477                 /* Do not descend and nuke a nested git work tree. */
1478                 if (kept_up)
1479                         *kept_up = 1;
1480                 return 0;
1481         }
1482
1483         flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
1484         dir = opendir(path->buf);
1485         if (!dir) {
1486                 /* an empty dir could be removed even if it is unreadble */
1487                 if (!keep_toplevel)
1488                         return rmdir(path->buf);
1489                 else
1490                         return -1;
1491         }
1492         if (path->buf[original_len - 1] != '/')
1493                 strbuf_addch(path, '/');
1494
1495         len = path->len;
1496         while ((e = readdir(dir)) != NULL) {
1497                 struct stat st;
1498                 if (is_dot_or_dotdot(e->d_name))
1499                         continue;
1500
1501                 strbuf_setlen(path, len);
1502                 strbuf_addstr(path, e->d_name);
1503                 if (lstat(path->buf, &st))
1504                         ; /* fall thru */
1505                 else if (S_ISDIR(st.st_mode)) {
1506                         if (!remove_dir_recurse(path, flag, &kept_down))
1507                                 continue; /* happy */
1508                 } else if (!only_empty && !unlink(path->buf))
1509                         continue; /* happy, too */
1510
1511                 /* path too long, stat fails, or non-directory still exists */
1512                 ret = -1;
1513                 break;
1514         }
1515         closedir(dir);
1516
1517         strbuf_setlen(path, original_len);
1518         if (!ret && !keep_toplevel && !kept_down)
1519                 ret = rmdir(path->buf);
1520         else if (kept_up)
1521                 /*
1522                  * report the uplevel that it is not an error that we
1523                  * did not rmdir() our directory.
1524                  */
1525                 *kept_up = !ret;
1526         return ret;
1527 }
1528
1529 int remove_dir_recursively(struct strbuf *path, int flag)
1530 {
1531         return remove_dir_recurse(path, flag, NULL);
1532 }
1533
1534 void setup_standard_excludes(struct dir_struct *dir)
1535 {
1536         const char *path;
1537         char *xdg_path;
1538
1539         dir->exclude_per_dir = ".gitignore";
1540         path = git_path("info/exclude");
1541         if (!excludes_file) {
1542                 home_config_paths(NULL, &xdg_path, "ignore");
1543                 excludes_file = xdg_path;
1544         }
1545         if (!access_or_warn(path, R_OK, 0))
1546                 add_excludes_from_file(dir, path);
1547         if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
1548                 add_excludes_from_file(dir, excludes_file);
1549 }
1550
1551 int remove_path(const char *name)
1552 {
1553         char *slash;
1554
1555         if (unlink(name) && errno != ENOENT && errno != ENOTDIR)
1556                 return -1;
1557
1558         slash = strrchr(name, '/');
1559         if (slash) {
1560                 char *dirs = xstrdup(name);
1561                 slash = dirs + (slash - name);
1562                 do {
1563                         *slash = '\0';
1564                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
1565                 free(dirs);
1566         }
1567         return 0;
1568 }
1569
1570 static int pathspec_item_cmp(const void *a_, const void *b_)
1571 {
1572         struct pathspec_item *a, *b;
1573
1574         a = (struct pathspec_item *)a_;
1575         b = (struct pathspec_item *)b_;
1576         return strcmp(a->match, b->match);
1577 }
1578
1579 int init_pathspec(struct pathspec *pathspec, const char **paths)
1580 {
1581         const char **p = paths;
1582         int i;
1583
1584         memset(pathspec, 0, sizeof(*pathspec));
1585         if (!p)
1586                 return 0;
1587         while (*p)
1588                 p++;
1589         pathspec->raw = paths;
1590         pathspec->nr = p - paths;
1591         if (!pathspec->nr)
1592                 return 0;
1593
1594         pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
1595         for (i = 0; i < pathspec->nr; i++) {
1596                 struct pathspec_item *item = pathspec->items+i;
1597                 const char *path = paths[i];
1598
1599                 item->match = path;
1600                 item->len = strlen(path);
1601                 item->flags = 0;
1602                 if (limit_pathspec_to_literal()) {
1603                         item->nowildcard_len = item->len;
1604                 } else {
1605                         item->nowildcard_len = simple_length(path);
1606                         if (item->nowildcard_len < item->len) {
1607                                 pathspec->has_wildcard = 1;
1608                                 if (path[item->nowildcard_len] == '*' &&
1609                                     no_wildcard(path + item->nowildcard_len + 1))
1610                                         item->flags |= PATHSPEC_ONESTAR;
1611                         }
1612                 }
1613         }
1614
1615         qsort(pathspec->items, pathspec->nr,
1616               sizeof(struct pathspec_item), pathspec_item_cmp);
1617
1618         return 0;
1619 }
1620
1621 void free_pathspec(struct pathspec *pathspec)
1622 {
1623         free(pathspec->items);
1624         pathspec->items = NULL;
1625 }
1626
1627 int limit_pathspec_to_literal(void)
1628 {
1629         static int flag = -1;
1630         if (flag < 0)
1631                 flag = git_env_bool(GIT_LITERAL_PATHSPECS_ENVIRONMENT, 0);
1632         return flag;
1633 }
1634
1635 /*
1636  * Frees memory within dir which was allocated for exclude lists and
1637  * the exclude_stack.  Does not free dir itself.
1638  */
1639 void clear_directory(struct dir_struct *dir)
1640 {
1641         int i, j;
1642         struct exclude_list_group *group;
1643         struct exclude_list *el;
1644         struct exclude_stack *stk;
1645
1646         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
1647                 group = &dir->exclude_list_group[i];
1648                 for (j = 0; j < group->nr; j++) {
1649                         el = &group->el[j];
1650                         if (i == EXC_DIRS)
1651                                 free((char *)el->src);
1652                         clear_exclude_list(el);
1653                 }
1654                 free(group->el);
1655         }
1656
1657         stk = dir->exclude_stack;
1658         while (stk) {
1659                 struct exclude_stack *prev = stk->prev;
1660                 free(stk);
1661                 stk = prev;
1662         }
1663 }