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