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