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