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