dir.c

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