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