Merge branch 'jc/strbuf-branchname-fix' into maint
[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->exclude->flags & EXC_FLAG_NEGATIVE)
826                                 dir->exclude = NULL;
827                         if (dir->exclude) {
828                                 dir->basebuf[stk->baselen] = 0;
829                                 dir->exclude_stack = stk;
830                                 return;
831                         }
832                 }
833
834                 /* Try to read per-directory file unless path is too long */
835                 if (dir->exclude_per_dir &&
836                     stk->baselen + strlen(dir->exclude_per_dir) < PATH_MAX) {
837                         strcpy(dir->basebuf + stk->baselen,
838                                         dir->exclude_per_dir);
839                         /*
840                          * dir->basebuf gets reused by the traversal, but we
841                          * need fname to remain unchanged to ensure the src
842                          * member of each struct exclude correctly
843                          * back-references its source file.  Other invocations
844                          * of add_exclude_list provide stable strings, so we
845                          * strdup() and free() here in the caller.
846                          */
847                         el->src = strdup(dir->basebuf);
848                         add_excludes_from_file_to_list(dir->basebuf,
849                                         dir->basebuf, stk->baselen, el, 1);
850                 }
851                 dir->exclude_stack = stk;
852                 current = stk->baselen;
853         }
854         dir->basebuf[baselen] = '\0';
855 }
856
857 /*
858  * Loads the exclude lists for the directory containing pathname, then
859  * scans all exclude lists to determine whether pathname is excluded.
860  * Returns the exclude_list element which matched, or NULL for
861  * undecided.
862  */
863 struct exclude *last_exclude_matching(struct dir_struct *dir,
864                                              const char *pathname,
865                                              int *dtype_p)
866 {
867         int pathlen = strlen(pathname);
868         const char *basename = strrchr(pathname, '/');
869         basename = (basename) ? basename+1 : pathname;
870
871         prep_exclude(dir, pathname, basename-pathname);
872
873         if (dir->exclude)
874                 return dir->exclude;
875
876         return last_exclude_matching_from_lists(dir, pathname, pathlen,
877                         basename, dtype_p);
878 }
879
880 /*
881  * Loads the exclude lists for the directory containing pathname, then
882  * scans all exclude lists to determine whether pathname is excluded.
883  * Returns 1 if true, otherwise 0.
884  */
885 int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
886 {
887         struct exclude *exclude =
888                 last_exclude_matching(dir, pathname, dtype_p);
889         if (exclude)
890                 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
891         return 0;
892 }
893
894 static struct dir_entry *dir_entry_new(const char *pathname, int len)
895 {
896         struct dir_entry *ent;
897
898         ent = xmalloc(sizeof(*ent) + len + 1);
899         ent->len = len;
900         memcpy(ent->name, pathname, len);
901         ent->name[len] = 0;
902         return ent;
903 }
904
905 static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
906 {
907         if (cache_name_exists(pathname, len, ignore_case))
908                 return NULL;
909
910         ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
911         return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
912 }
913
914 struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len)
915 {
916         if (!cache_name_is_other(pathname, len))
917                 return NULL;
918
919         ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
920         return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
921 }
922
923 enum exist_status {
924         index_nonexistent = 0,
925         index_directory,
926         index_gitdir
927 };
928
929 /*
930  * Do not use the alphabetically stored index to look up
931  * the directory name; instead, use the case insensitive
932  * name hash.
933  */
934 static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
935 {
936         struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);
937         unsigned char endchar;
938
939         if (!ce)
940                 return index_nonexistent;
941         endchar = ce->name[len];
942
943         /*
944          * The cache_entry structure returned will contain this dirname
945          * and possibly additional path components.
946          */
947         if (endchar == '/')
948                 return index_directory;
949
950         /*
951          * If there are no additional path components, then this cache_entry
952          * represents a submodule.  Submodules, despite being directories,
953          * are stored in the cache without a closing slash.
954          */
955         if (!endchar && S_ISGITLINK(ce->ce_mode))
956                 return index_gitdir;
957
958         /* This should never be hit, but it exists just in case. */
959         return index_nonexistent;
960 }
961
962 /*
963  * The index sorts alphabetically by entry name, which
964  * means that a gitlink sorts as '\0' at the end, while
965  * a directory (which is defined not as an entry, but as
966  * the files it contains) will sort with the '/' at the
967  * end.
968  */
969 static enum exist_status directory_exists_in_index(const char *dirname, int len)
970 {
971         int pos;
972
973         if (ignore_case)
974                 return directory_exists_in_index_icase(dirname, len);
975
976         pos = cache_name_pos(dirname, len);
977         if (pos < 0)
978                 pos = -pos-1;
979         while (pos < active_nr) {
980                 struct cache_entry *ce = active_cache[pos++];
981                 unsigned char endchar;
982
983                 if (strncmp(ce->name, dirname, len))
984                         break;
985                 endchar = ce->name[len];
986                 if (endchar > '/')
987                         break;
988                 if (endchar == '/')
989                         return index_directory;
990                 if (!endchar && S_ISGITLINK(ce->ce_mode))
991                         return index_gitdir;
992         }
993         return index_nonexistent;
994 }
995
996 /*
997  * When we find a directory when traversing the filesystem, we
998  * have three distinct cases:
999  *
1000  *  - ignore it
1001  *  - see it as a directory
1002  *  - recurse into it
1003  *
1004  * and which one we choose depends on a combination of existing
1005  * git index contents and the flags passed into the directory
1006  * traversal routine.
1007  *
1008  * Case 1: If we *already* have entries in the index under that
1009  * directory name, we always recurse into the directory to see
1010  * all the files.
1011  *
1012  * Case 2: If we *already* have that directory name as a gitlink,
1013  * we always continue to see it as a gitlink, regardless of whether
1014  * there is an actual git directory there or not (it might not
1015  * be checked out as a subproject!)
1016  *
1017  * Case 3: if we didn't have it in the index previously, we
1018  * have a few sub-cases:
1019  *
1020  *  (a) if "show_other_directories" is true, we show it as
1021  *      just a directory, unless "hide_empty_directories" is
1022  *      also true, in which case we need to check if it contains any
1023  *      untracked and / or ignored files.
1024  *  (b) if it looks like a git directory, and we don't have
1025  *      'no_gitlinks' set we treat it as a gitlink, and show it
1026  *      as a directory.
1027  *  (c) otherwise, we recurse into it.
1028  */
1029 static enum path_treatment treat_directory(struct dir_struct *dir,
1030         const char *dirname, int len, int exclude,
1031         const struct path_simplify *simplify)
1032 {
1033         /* The "len-1" is to strip the final '/' */
1034         switch (directory_exists_in_index(dirname, len-1)) {
1035         case index_directory:
1036                 return path_recurse;
1037
1038         case index_gitdir:
1039                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1040                         return path_none;
1041                 return path_untracked;
1042
1043         case index_nonexistent:
1044                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1045                         break;
1046                 if (!(dir->flags & DIR_NO_GITLINKS)) {
1047                         unsigned char sha1[20];
1048                         if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)
1049                                 return path_untracked;
1050                 }
1051                 return path_recurse;
1052         }
1053
1054         /* This is the "show_other_directories" case */
1055
1056         if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1057                 return exclude ? path_excluded : path_untracked;
1058
1059         return read_directory_recursive(dir, dirname, len, 1, simplify);
1060 }
1061
1062 /*
1063  * This is an inexact early pruning of any recursive directory
1064  * reading - if the path cannot possibly be in the pathspec,
1065  * return true, and we'll skip it early.
1066  */
1067 static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)
1068 {
1069         if (simplify) {
1070                 for (;;) {
1071                         const char *match = simplify->path;
1072                         int len = simplify->len;
1073
1074                         if (!match)
1075                                 break;
1076                         if (len > pathlen)
1077                                 len = pathlen;
1078                         if (!memcmp(path, match, len))
1079                                 return 0;
1080                         simplify++;
1081                 }
1082                 return 1;
1083         }
1084         return 0;
1085 }
1086
1087 /*
1088  * This function tells us whether an excluded path matches a
1089  * list of "interesting" pathspecs. That is, whether a path matched
1090  * by any of the pathspecs could possibly be ignored by excluding
1091  * the specified path. This can happen if:
1092  *
1093  *   1. the path is mentioned explicitly in the pathspec
1094  *
1095  *   2. the path is a directory prefix of some element in the
1096  *      pathspec
1097  */
1098 static int exclude_matches_pathspec(const char *path, int len,
1099                 const struct path_simplify *simplify)
1100 {
1101         if (simplify) {
1102                 for (; simplify->path; simplify++) {
1103                         if (len == simplify->len
1104                             && !memcmp(path, simplify->path, len))
1105                                 return 1;
1106                         if (len < simplify->len
1107                             && simplify->path[len] == '/'
1108                             && !memcmp(path, simplify->path, len))
1109                                 return 1;
1110                 }
1111         }
1112         return 0;
1113 }
1114
1115 static int get_index_dtype(const char *path, int len)
1116 {
1117         int pos;
1118         struct cache_entry *ce;
1119
1120         ce = cache_name_exists(path, len, 0);
1121         if (ce) {
1122                 if (!ce_uptodate(ce))
1123                         return DT_UNKNOWN;
1124                 if (S_ISGITLINK(ce->ce_mode))
1125                         return DT_DIR;
1126                 /*
1127                  * Nobody actually cares about the
1128                  * difference between DT_LNK and DT_REG
1129                  */
1130                 return DT_REG;
1131         }
1132
1133         /* Try to look it up as a directory */
1134         pos = cache_name_pos(path, len);
1135         if (pos >= 0)
1136                 return DT_UNKNOWN;
1137         pos = -pos-1;
1138         while (pos < active_nr) {
1139                 ce = active_cache[pos++];
1140                 if (strncmp(ce->name, path, len))
1141                         break;
1142                 if (ce->name[len] > '/')
1143                         break;
1144                 if (ce->name[len] < '/')
1145                         continue;
1146                 if (!ce_uptodate(ce))
1147                         break;  /* continue? */
1148                 return DT_DIR;
1149         }
1150         return DT_UNKNOWN;
1151 }
1152
1153 static int get_dtype(struct dirent *de, const char *path, int len)
1154 {
1155         int dtype = de ? DTYPE(de) : DT_UNKNOWN;
1156         struct stat st;
1157
1158         if (dtype != DT_UNKNOWN)
1159                 return dtype;
1160         dtype = get_index_dtype(path, len);
1161         if (dtype != DT_UNKNOWN)
1162                 return dtype;
1163         if (lstat(path, &st))
1164                 return dtype;
1165         if (S_ISREG(st.st_mode))
1166                 return DT_REG;
1167         if (S_ISDIR(st.st_mode))
1168                 return DT_DIR;
1169         if (S_ISLNK(st.st_mode))
1170                 return DT_LNK;
1171         return dtype;
1172 }
1173
1174 static enum path_treatment treat_one_path(struct dir_struct *dir,
1175                                           struct strbuf *path,
1176                                           const struct path_simplify *simplify,
1177                                           int dtype, struct dirent *de)
1178 {
1179         int exclude;
1180         if (dtype == DT_UNKNOWN)
1181                 dtype = get_dtype(de, path->buf, path->len);
1182
1183         /* Always exclude indexed files */
1184         if (dtype != DT_DIR &&
1185             cache_name_exists(path->buf, path->len, ignore_case))
1186                 return path_none;
1187
1188         exclude = is_excluded(dir, path->buf, &dtype);
1189
1190         /*
1191          * Excluded? If we don't explicitly want to show
1192          * ignored files, ignore it
1193          */
1194         if (exclude && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
1195                 return path_excluded;
1196
1197         switch (dtype) {
1198         default:
1199                 return path_none;
1200         case DT_DIR:
1201                 strbuf_addch(path, '/');
1202                 return treat_directory(dir, path->buf, path->len, exclude,
1203                         simplify);
1204         case DT_REG:
1205         case DT_LNK:
1206                 return exclude ? path_excluded : path_untracked;
1207         }
1208 }
1209
1210 static enum path_treatment treat_path(struct dir_struct *dir,
1211                                       struct dirent *de,
1212                                       struct strbuf *path,
1213                                       int baselen,
1214                                       const struct path_simplify *simplify)
1215 {
1216         int dtype;
1217
1218         if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
1219                 return path_none;
1220         strbuf_setlen(path, baselen);
1221         strbuf_addstr(path, de->d_name);
1222         if (simplify_away(path->buf, path->len, simplify))
1223                 return path_none;
1224
1225         dtype = DTYPE(de);
1226         return treat_one_path(dir, path, simplify, dtype, de);
1227 }
1228
1229 /*
1230  * Read a directory tree. We currently ignore anything but
1231  * directories, regular files and symlinks. That's because git
1232  * doesn't handle them at all yet. Maybe that will change some
1233  * day.
1234  *
1235  * Also, we ignore the name ".git" (even if it is not a directory).
1236  * That likely will not change.
1237  *
1238  * Returns the most significant path_treatment value encountered in the scan.
1239  */
1240 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
1241                                     const char *base, int baselen,
1242                                     int check_only,
1243                                     const struct path_simplify *simplify)
1244 {
1245         DIR *fdir;
1246         enum path_treatment state, subdir_state, dir_state = path_none;
1247         struct dirent *de;
1248         struct strbuf path = STRBUF_INIT;
1249
1250         strbuf_add(&path, base, baselen);
1251
1252         fdir = opendir(path.len ? path.buf : ".");
1253         if (!fdir)
1254                 goto out;
1255
1256         while ((de = readdir(fdir)) != NULL) {
1257                 /* check how the file or directory should be treated */
1258                 state = treat_path(dir, de, &path, baselen, simplify);
1259                 if (state > dir_state)
1260                         dir_state = state;
1261
1262                 /* recurse into subdir if instructed by treat_path */
1263                 if (state == path_recurse) {
1264                         subdir_state = read_directory_recursive(dir, path.buf,
1265                                 path.len, check_only, simplify);
1266                         if (subdir_state > dir_state)
1267                                 dir_state = subdir_state;
1268                 }
1269
1270                 if (check_only) {
1271                         /* abort early if maximum state has been reached */
1272                         if (dir_state == path_untracked)
1273                                 break;
1274                         /* skip the dir_add_* part */
1275                         continue;
1276                 }
1277
1278                 /* add the path to the appropriate result list */
1279                 switch (state) {
1280                 case path_excluded:
1281                         if (dir->flags & DIR_SHOW_IGNORED)
1282                                 dir_add_name(dir, path.buf, path.len);
1283                         else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
1284                                 ((dir->flags & DIR_COLLECT_IGNORED) &&
1285                                 exclude_matches_pathspec(path.buf, path.len,
1286                                         simplify)))
1287                                 dir_add_ignored(dir, path.buf, path.len);
1288                         break;
1289
1290                 case path_untracked:
1291                         if (!(dir->flags & DIR_SHOW_IGNORED))
1292                                 dir_add_name(dir, path.buf, path.len);
1293                         break;
1294
1295                 default:
1296                         break;
1297                 }
1298         }
1299         closedir(fdir);
1300  out:
1301         strbuf_release(&path);
1302
1303         return dir_state;
1304 }
1305
1306 static int cmp_name(const void *p1, const void *p2)
1307 {
1308         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
1309         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
1310
1311         return cache_name_compare(e1->name, e1->len,
1312                                   e2->name, e2->len);
1313 }
1314
1315 static struct path_simplify *create_simplify(const char **pathspec)
1316 {
1317         int nr, alloc = 0;
1318         struct path_simplify *simplify = NULL;
1319
1320         if (!pathspec)
1321                 return NULL;
1322
1323         for (nr = 0 ; ; nr++) {
1324                 const char *match;
1325                 if (nr >= alloc) {
1326                         alloc = alloc_nr(alloc);
1327                         simplify = xrealloc(simplify, alloc * sizeof(*simplify));
1328                 }
1329                 match = *pathspec++;
1330                 if (!match)
1331                         break;
1332                 simplify[nr].path = match;
1333                 simplify[nr].len = simple_length(match);
1334         }
1335         simplify[nr].path = NULL;
1336         simplify[nr].len = 0;
1337         return simplify;
1338 }
1339
1340 static void free_simplify(struct path_simplify *simplify)
1341 {
1342         free(simplify);
1343 }
1344
1345 static int treat_leading_path(struct dir_struct *dir,
1346                               const char *path, int len,
1347                               const struct path_simplify *simplify)
1348 {
1349         struct strbuf sb = STRBUF_INIT;
1350         int baselen, rc = 0;
1351         const char *cp;
1352         int old_flags = dir->flags;
1353
1354         while (len && path[len - 1] == '/')
1355                 len--;
1356         if (!len)
1357                 return 1;
1358         baselen = 0;
1359         dir->flags &= ~DIR_SHOW_OTHER_DIRECTORIES;
1360         while (1) {
1361                 cp = path + baselen + !!baselen;
1362                 cp = memchr(cp, '/', path + len - cp);
1363                 if (!cp)
1364                         baselen = len;
1365                 else
1366                         baselen = cp - path;
1367                 strbuf_setlen(&sb, 0);
1368                 strbuf_add(&sb, path, baselen);
1369                 if (!is_directory(sb.buf))
1370                         break;
1371                 if (simplify_away(sb.buf, sb.len, simplify))
1372                         break;
1373                 if (treat_one_path(dir, &sb, simplify,
1374                                    DT_DIR, NULL) == path_none)
1375                         break; /* do not recurse into it */
1376                 if (len <= baselen) {
1377                         rc = 1;
1378                         break; /* finished checking */
1379                 }
1380         }
1381         strbuf_release(&sb);
1382         dir->flags = old_flags;
1383         return rc;
1384 }
1385
1386 int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
1387 {
1388         struct path_simplify *simplify;
1389
1390         if (has_symlink_leading_path(path, len))
1391                 return dir->nr;
1392
1393         simplify = create_simplify(pathspec);
1394         if (!len || treat_leading_path(dir, path, len, simplify))
1395                 read_directory_recursive(dir, path, len, 0, simplify);
1396         free_simplify(simplify);
1397         qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
1398         qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
1399         return dir->nr;
1400 }
1401
1402 int file_exists(const char *f)
1403 {
1404         struct stat sb;
1405         return lstat(f, &sb) == 0;
1406 }
1407
1408 /*
1409  * Given two normalized paths (a trailing slash is ok), if subdir is
1410  * outside dir, return -1.  Otherwise return the offset in subdir that
1411  * can be used as relative path to dir.
1412  */
1413 int dir_inside_of(const char *subdir, const char *dir)
1414 {
1415         int offset = 0;
1416
1417         assert(dir && subdir && *dir && *subdir);
1418
1419         while (*dir && *subdir && *dir == *subdir) {
1420                 dir++;
1421                 subdir++;
1422                 offset++;
1423         }
1424
1425         /* hel[p]/me vs hel[l]/yeah */
1426         if (*dir && *subdir)
1427                 return -1;
1428
1429         if (!*subdir)
1430                 return !*dir ? offset : -1; /* same dir */
1431
1432         /* foo/[b]ar vs foo/[] */
1433         if (is_dir_sep(dir[-1]))
1434                 return is_dir_sep(subdir[-1]) ? offset : -1;
1435
1436         /* foo[/]bar vs foo[] */
1437         return is_dir_sep(*subdir) ? offset + 1 : -1;
1438 }
1439
1440 int is_inside_dir(const char *dir)
1441 {
1442         char cwd[PATH_MAX];
1443         if (!dir)
1444                 return 0;
1445         if (!getcwd(cwd, sizeof(cwd)))
1446                 die_errno("can't find the current directory");
1447         return dir_inside_of(cwd, dir) >= 0;
1448 }
1449
1450 int is_empty_dir(const char *path)
1451 {
1452         DIR *dir = opendir(path);
1453         struct dirent *e;
1454         int ret = 1;
1455
1456         if (!dir)
1457                 return 0;
1458
1459         while ((e = readdir(dir)) != NULL)
1460                 if (!is_dot_or_dotdot(e->d_name)) {
1461                         ret = 0;
1462                         break;
1463                 }
1464
1465         closedir(dir);
1466         return ret;
1467 }
1468
1469 static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
1470 {
1471         DIR *dir;
1472         struct dirent *e;
1473         int ret = 0, original_len = path->len, len, kept_down = 0;
1474         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
1475         int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
1476         unsigned char submodule_head[20];
1477
1478         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
1479             !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
1480                 /* Do not descend and nuke a nested git work tree. */
1481                 if (kept_up)
1482                         *kept_up = 1;
1483                 return 0;
1484         }
1485
1486         flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
1487         dir = opendir(path->buf);
1488         if (!dir) {
1489                 /* an empty dir could be removed even if it is unreadble */
1490                 if (!keep_toplevel)
1491                         return rmdir(path->buf);
1492                 else
1493                         return -1;
1494         }
1495         if (path->buf[original_len - 1] != '/')
1496                 strbuf_addch(path, '/');
1497
1498         len = path->len;
1499         while ((e = readdir(dir)) != NULL) {
1500                 struct stat st;
1501                 if (is_dot_or_dotdot(e->d_name))
1502                         continue;
1503
1504                 strbuf_setlen(path, len);
1505                 strbuf_addstr(path, e->d_name);
1506                 if (lstat(path->buf, &st))
1507                         ; /* fall thru */
1508                 else if (S_ISDIR(st.st_mode)) {
1509                         if (!remove_dir_recurse(path, flag, &kept_down))
1510                                 continue; /* happy */
1511                 } else if (!only_empty && !unlink(path->buf))
1512                         continue; /* happy, too */
1513
1514                 /* path too long, stat fails, or non-directory still exists */
1515                 ret = -1;
1516                 break;
1517         }
1518         closedir(dir);
1519
1520         strbuf_setlen(path, original_len);
1521         if (!ret && !keep_toplevel && !kept_down)
1522                 ret = rmdir(path->buf);
1523         else if (kept_up)
1524                 /*
1525                  * report the uplevel that it is not an error that we
1526                  * did not rmdir() our directory.
1527                  */
1528                 *kept_up = !ret;
1529         return ret;
1530 }
1531
1532 int remove_dir_recursively(struct strbuf *path, int flag)
1533 {
1534         return remove_dir_recurse(path, flag, NULL);
1535 }
1536
1537 void setup_standard_excludes(struct dir_struct *dir)
1538 {
1539         const char *path;
1540         char *xdg_path;
1541
1542         dir->exclude_per_dir = ".gitignore";
1543         path = git_path("info/exclude");
1544         if (!excludes_file) {
1545                 home_config_paths(NULL, &xdg_path, "ignore");
1546                 excludes_file = xdg_path;
1547         }
1548         if (!access_or_warn(path, R_OK, 0))
1549                 add_excludes_from_file(dir, path);
1550         if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
1551                 add_excludes_from_file(dir, excludes_file);
1552 }
1553
1554 int remove_path(const char *name)
1555 {
1556         char *slash;
1557
1558         if (unlink(name) && errno != ENOENT && errno != ENOTDIR)
1559                 return -1;
1560
1561         slash = strrchr(name, '/');
1562         if (slash) {
1563                 char *dirs = xstrdup(name);
1564                 slash = dirs + (slash - name);
1565                 do {
1566                         *slash = '\0';
1567                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
1568                 free(dirs);
1569         }
1570         return 0;
1571 }
1572
1573 static int pathspec_item_cmp(const void *a_, const void *b_)
1574 {
1575         struct pathspec_item *a, *b;
1576
1577         a = (struct pathspec_item *)a_;
1578         b = (struct pathspec_item *)b_;
1579         return strcmp(a->match, b->match);
1580 }
1581
1582 int init_pathspec(struct pathspec *pathspec, const char **paths)
1583 {
1584         const char **p = paths;
1585         int i;
1586
1587         memset(pathspec, 0, sizeof(*pathspec));
1588         if (!p)
1589                 return 0;
1590         while (*p)
1591                 p++;
1592         pathspec->raw = paths;
1593         pathspec->nr = p - paths;
1594         if (!pathspec->nr)
1595                 return 0;
1596
1597         pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
1598         for (i = 0; i < pathspec->nr; i++) {
1599                 struct pathspec_item *item = pathspec->items+i;
1600                 const char *path = paths[i];
1601
1602                 item->match = path;
1603                 item->len = strlen(path);
1604                 item->flags = 0;
1605                 if (limit_pathspec_to_literal()) {
1606                         item->nowildcard_len = item->len;
1607                 } else {
1608                         item->nowildcard_len = simple_length(path);
1609                         if (item->nowildcard_len < item->len) {
1610                                 pathspec->has_wildcard = 1;
1611                                 if (path[item->nowildcard_len] == '*' &&
1612                                     no_wildcard(path + item->nowildcard_len + 1))
1613                                         item->flags |= PATHSPEC_ONESTAR;
1614                         }
1615                 }
1616         }
1617
1618         qsort(pathspec->items, pathspec->nr,
1619               sizeof(struct pathspec_item), pathspec_item_cmp);
1620
1621         return 0;
1622 }
1623
1624 void free_pathspec(struct pathspec *pathspec)
1625 {
1626         free(pathspec->items);
1627         pathspec->items = NULL;
1628 }
1629
1630 int limit_pathspec_to_literal(void)
1631 {
1632         static int flag = -1;
1633         if (flag < 0)
1634                 flag = git_env_bool(GIT_LITERAL_PATHSPECS_ENVIRONMENT, 0);
1635         return flag;
1636 }
1637
1638 /*
1639  * Frees memory within dir which was allocated for exclude lists and
1640  * the exclude_stack.  Does not free dir itself.
1641  */
1642 void clear_directory(struct dir_struct *dir)
1643 {
1644         int i, j;
1645         struct exclude_list_group *group;
1646         struct exclude_list *el;
1647         struct exclude_stack *stk;
1648
1649         for (i = EXC_CMDL; i <= EXC_FILE; i++) {
1650                 group = &dir->exclude_list_group[i];
1651                 for (j = 0; j < group->nr; j++) {
1652                         el = &group->el[j];
1653                         if (i == EXC_DIRS)
1654                                 free((char *)el->src);
1655                         clear_exclude_list(el);
1656                 }
1657                 free(group->el);
1658         }
1659
1660         stk = dir->exclude_stack;
1661         while (stk) {
1662                 struct exclude_stack *prev = stk->prev;
1663                 free(stk);
1664                 stk = prev;
1665         }
1666 }