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