0be7cf19253d5a7648a45ae6d59d92b7957fef70
   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#include "utf8.h"
  16#include "varint.h"
  17#include "ewah/ewok.h"
  18
  19struct path_simplify {
  20        int len;
  21        const char *path;
  22};
  23
  24/*
  25 * Tells read_directory_recursive how a file or directory should be treated.
  26 * Values are ordered by significance, e.g. if a directory contains both
  27 * excluded and untracked files, it is listed as untracked because
  28 * path_untracked > path_excluded.
  29 */
  30enum path_treatment {
  31        path_none = 0,
  32        path_recurse,
  33        path_excluded,
  34        path_untracked
  35};
  36
  37/*
  38 * Support data structure for our opendir/readdir/closedir wrappers
  39 */
  40struct cached_dir {
  41        DIR *fdir;
  42        struct untracked_cache_dir *untracked;
  43        int nr_files;
  44        int nr_dirs;
  45
  46        struct dirent *de;
  47        const char *file;
  48        struct untracked_cache_dir *ucd;
  49};
  50
  51static enum path_treatment read_directory_recursive(struct dir_struct *dir,
  52        const char *path, int len, struct untracked_cache_dir *untracked,
  53        int check_only, const struct path_simplify *simplify);
  54static int get_dtype(struct dirent *de, const char *path, int len);
  55
  56static struct trace_key trace_exclude = TRACE_KEY_INIT(EXCLUDE);
  57
  58/* helper string functions with support for the ignore_case flag */
  59int strcmp_icase(const char *a, const char *b)
  60{
  61        return ignore_case ? strcasecmp(a, b) : strcmp(a, b);
  62}
  63
  64int strncmp_icase(const char *a, const char *b, size_t count)
  65{
  66        return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);
  67}
  68
  69int fnmatch_icase(const char *pattern, const char *string, int flags)
  70{
  71        return wildmatch(pattern, string,
  72                         flags | (ignore_case ? WM_CASEFOLD : 0),
  73                         NULL);
  74}
  75
  76int git_fnmatch(const struct pathspec_item *item,
  77                const char *pattern, const char *string,
  78                int prefix)
  79{
  80        if (prefix > 0) {
  81                if (ps_strncmp(item, pattern, string, prefix))
  82                        return WM_NOMATCH;
  83                pattern += prefix;
  84                string += prefix;
  85        }
  86        if (item->flags & PATHSPEC_ONESTAR) {
  87                int pattern_len = strlen(++pattern);
  88                int string_len = strlen(string);
  89                return string_len < pattern_len ||
  90                        ps_strcmp(item, pattern,
  91                                  string + string_len - pattern_len);
  92        }
  93        if (item->magic & PATHSPEC_GLOB)
  94                return wildmatch(pattern, string,
  95                                 WM_PATHNAME |
  96                                 (item->magic & PATHSPEC_ICASE ? WM_CASEFOLD : 0),
  97                                 NULL);
  98        else
  99                /* wildmatch has not learned no FNM_PATHNAME mode yet */
 100                return wildmatch(pattern, string,
 101                                 item->magic & PATHSPEC_ICASE ? WM_CASEFOLD : 0,
 102                                 NULL);
 103}
 104
 105static int fnmatch_icase_mem(const char *pattern, int patternlen,
 106                             const char *string, int stringlen,
 107                             int flags)
 108{
 109        int match_status;
 110        struct strbuf pat_buf = STRBUF_INIT;
 111        struct strbuf str_buf = STRBUF_INIT;
 112        const char *use_pat = pattern;
 113        const char *use_str = string;
 114
 115        if (pattern[patternlen]) {
 116                strbuf_add(&pat_buf, pattern, patternlen);
 117                use_pat = pat_buf.buf;
 118        }
 119        if (string[stringlen]) {
 120                strbuf_add(&str_buf, string, stringlen);
 121                use_str = str_buf.buf;
 122        }
 123
 124        if (ignore_case)
 125                flags |= WM_CASEFOLD;
 126        match_status = wildmatch(use_pat, use_str, flags, NULL);
 127
 128        strbuf_release(&pat_buf);
 129        strbuf_release(&str_buf);
 130
 131        return match_status;
 132}
 133
 134static size_t common_prefix_len(const struct pathspec *pathspec)
 135{
 136        int n;
 137        size_t max = 0;
 138
 139        /*
 140         * ":(icase)path" is treated as a pathspec full of
 141         * wildcard. In other words, only prefix is considered common
 142         * prefix. If the pathspec is abc/foo abc/bar, running in
 143         * subdir xyz, the common prefix is still xyz, not xuz/abc as
 144         * in non-:(icase).
 145         */
 146        GUARD_PATHSPEC(pathspec,
 147                       PATHSPEC_FROMTOP |
 148                       PATHSPEC_MAXDEPTH |
 149                       PATHSPEC_LITERAL |
 150                       PATHSPEC_GLOB |
 151                       PATHSPEC_ICASE |
 152                       PATHSPEC_EXCLUDE);
 153
 154        for (n = 0; n < pathspec->nr; n++) {
 155                size_t i = 0, len = 0, item_len;
 156                if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
 157                        continue;
 158                if (pathspec->items[n].magic & PATHSPEC_ICASE)
 159                        item_len = pathspec->items[n].prefix;
 160                else
 161                        item_len = pathspec->items[n].nowildcard_len;
 162                while (i < item_len && (n == 0 || i < max)) {
 163                        char c = pathspec->items[n].match[i];
 164                        if (c != pathspec->items[0].match[i])
 165                                break;
 166                        if (c == '/')
 167                                len = i + 1;
 168                        i++;
 169                }
 170                if (n == 0 || len < max) {
 171                        max = len;
 172                        if (!max)
 173                                break;
 174                }
 175        }
 176        return max;
 177}
 178
 179/*
 180 * Returns a copy of the longest leading path common among all
 181 * pathspecs.
 182 */
 183char *common_prefix(const struct pathspec *pathspec)
 184{
 185        unsigned long len = common_prefix_len(pathspec);
 186
 187        return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
 188}
 189
 190int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
 191{
 192        size_t len;
 193
 194        /*
 195         * Calculate common prefix for the pathspec, and
 196         * use that to optimize the directory walk
 197         */
 198        len = common_prefix_len(pathspec);
 199
 200        /* Read the directory and prune it */
 201        read_directory(dir, pathspec->nr ? pathspec->_raw[0] : "", len, pathspec);
 202        return len;
 203}
 204
 205int within_depth(const char *name, int namelen,
 206                        int depth, int max_depth)
 207{
 208        const char *cp = name, *cpe = name + namelen;
 209
 210        while (cp < cpe) {
 211                if (*cp++ != '/')
 212                        continue;
 213                depth++;
 214                if (depth > max_depth)
 215                        return 0;
 216        }
 217        return 1;
 218}
 219
 220#define DO_MATCH_EXCLUDE   1
 221#define DO_MATCH_DIRECTORY 2
 222
 223/*
 224 * Does 'match' match the given name?
 225 * A match is found if
 226 *
 227 * (1) the 'match' string is leading directory of 'name', or
 228 * (2) the 'match' string is a wildcard and matches 'name', or
 229 * (3) the 'match' string is exactly the same as 'name'.
 230 *
 231 * and the return value tells which case it was.
 232 *
 233 * It returns 0 when there is no match.
 234 */
 235static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 236                               const char *name, int namelen, unsigned flags)
 237{
 238        /* name/namelen has prefix cut off by caller */
 239        const char *match = item->match + prefix;
 240        int matchlen = item->len - prefix;
 241
 242        /*
 243         * The normal call pattern is:
 244         * 1. prefix = common_prefix_len(ps);
 245         * 2. prune something, or fill_directory
 246         * 3. match_pathspec()
 247         *
 248         * 'prefix' at #1 may be shorter than the command's prefix and
 249         * it's ok for #2 to match extra files. Those extras will be
 250         * trimmed at #3.
 251         *
 252         * Suppose the pathspec is 'foo' and '../bar' running from
 253         * subdir 'xyz'. The common prefix at #1 will be empty, thanks
 254         * to "../". We may have xyz/foo _and_ XYZ/foo after #2. The
 255         * user does not want XYZ/foo, only the "foo" part should be
 256         * case-insensitive. We need to filter out XYZ/foo here. In
 257         * other words, we do not trust the caller on comparing the
 258         * prefix part when :(icase) is involved. We do exact
 259         * comparison ourselves.
 260         *
 261         * Normally the caller (common_prefix_len() in fact) does
 262         * _exact_ matching on name[-prefix+1..-1] and we do not need
 263         * to check that part. Be defensive and check it anyway, in
 264         * case common_prefix_len is changed, or a new caller is
 265         * introduced that does not use common_prefix_len.
 266         *
 267         * If the penalty turns out too high when prefix is really
 268         * long, maybe change it to
 269         * strncmp(match, name, item->prefix - prefix)
 270         */
 271        if (item->prefix && (item->magic & PATHSPEC_ICASE) &&
 272            strncmp(item->match, name - prefix, item->prefix))
 273                return 0;
 274
 275        /* If the match was just the prefix, we matched */
 276        if (!*match)
 277                return MATCHED_RECURSIVELY;
 278
 279        if (matchlen <= namelen && !ps_strncmp(item, match, name, matchlen)) {
 280                if (matchlen == namelen)
 281                        return MATCHED_EXACTLY;
 282
 283                if (match[matchlen-1] == '/' || name[matchlen] == '/')
 284                        return MATCHED_RECURSIVELY;
 285        } else if ((flags & DO_MATCH_DIRECTORY) &&
 286                   match[matchlen - 1] == '/' &&
 287                   namelen == matchlen - 1 &&
 288                   !ps_strncmp(item, match, name, namelen))
 289                return MATCHED_EXACTLY;
 290
 291        if (item->nowildcard_len < item->len &&
 292            !git_fnmatch(item, match, name,
 293                         item->nowildcard_len - prefix))
 294                return MATCHED_FNMATCH;
 295
 296        return 0;
 297}
 298
 299/*
 300 * Given a name and a list of pathspecs, returns the nature of the
 301 * closest (i.e. most specific) match of the name to any of the
 302 * pathspecs.
 303 *
 304 * The caller typically calls this multiple times with the same
 305 * pathspec and seen[] array but with different name/namelen
 306 * (e.g. entries from the index) and is interested in seeing if and
 307 * how each pathspec matches all the names it calls this function
 308 * with.  A mark is left in the seen[] array for each pathspec element
 309 * indicating the closest type of match that element achieved, so if
 310 * seen[n] remains zero after multiple invocations, that means the nth
 311 * pathspec did not match any names, which could indicate that the
 312 * user mistyped the nth pathspec.
 313 */
 314static int do_match_pathspec(const struct pathspec *ps,
 315                             const char *name, int namelen,
 316                             int prefix, char *seen,
 317                             unsigned flags)
 318{
 319        int i, retval = 0, exclude = flags & DO_MATCH_EXCLUDE;
 320
 321        GUARD_PATHSPEC(ps,
 322                       PATHSPEC_FROMTOP |
 323                       PATHSPEC_MAXDEPTH |
 324                       PATHSPEC_LITERAL |
 325                       PATHSPEC_GLOB |
 326                       PATHSPEC_ICASE |
 327                       PATHSPEC_EXCLUDE);
 328
 329        if (!ps->nr) {
 330                if (!ps->recursive ||
 331                    !(ps->magic & PATHSPEC_MAXDEPTH) ||
 332                    ps->max_depth == -1)
 333                        return MATCHED_RECURSIVELY;
 334
 335                if (within_depth(name, namelen, 0, ps->max_depth))
 336                        return MATCHED_EXACTLY;
 337                else
 338                        return 0;
 339        }
 340
 341        name += prefix;
 342        namelen -= prefix;
 343
 344        for (i = ps->nr - 1; i >= 0; i--) {
 345                int how;
 346
 347                if ((!exclude &&   ps->items[i].magic & PATHSPEC_EXCLUDE) ||
 348                    ( exclude && !(ps->items[i].magic & PATHSPEC_EXCLUDE)))
 349                        continue;
 350
 351                if (seen && seen[i] == MATCHED_EXACTLY)
 352                        continue;
 353                /*
 354                 * Make exclude patterns optional and never report
 355                 * "pathspec ':(exclude)foo' matches no files"
 356                 */
 357                if (seen && ps->items[i].magic & PATHSPEC_EXCLUDE)
 358                        seen[i] = MATCHED_FNMATCH;
 359                how = match_pathspec_item(ps->items+i, prefix, name,
 360                                          namelen, flags);
 361                if (ps->recursive &&
 362                    (ps->magic & PATHSPEC_MAXDEPTH) &&
 363                    ps->max_depth != -1 &&
 364                    how && how != MATCHED_FNMATCH) {
 365                        int len = ps->items[i].len;
 366                        if (name[len] == '/')
 367                                len++;
 368                        if (within_depth(name+len, namelen-len, 0, ps->max_depth))
 369                                how = MATCHED_EXACTLY;
 370                        else
 371                                how = 0;
 372                }
 373                if (how) {
 374                        if (retval < how)
 375                                retval = how;
 376                        if (seen && seen[i] < how)
 377                                seen[i] = how;
 378                }
 379        }
 380        return retval;
 381}
 382
 383int match_pathspec(const struct pathspec *ps,
 384                   const char *name, int namelen,
 385                   int prefix, char *seen, int is_dir)
 386{
 387        int positive, negative;
 388        unsigned flags = is_dir ? DO_MATCH_DIRECTORY : 0;
 389        positive = do_match_pathspec(ps, name, namelen,
 390                                     prefix, seen, flags);
 391        if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
 392                return positive;
 393        negative = do_match_pathspec(ps, name, namelen,
 394                                     prefix, seen,
 395                                     flags | DO_MATCH_EXCLUDE);
 396        return negative ? 0 : positive;
 397}
 398
 399int report_path_error(const char *ps_matched,
 400                      const struct pathspec *pathspec,
 401                      const char *prefix)
 402{
 403        /*
 404         * Make sure all pathspec matched; otherwise it is an error.
 405         */
 406        int num, errors = 0;
 407        for (num = 0; num < pathspec->nr; num++) {
 408                int other, found_dup;
 409
 410                if (ps_matched[num])
 411                        continue;
 412                /*
 413                 * The caller might have fed identical pathspec
 414                 * twice.  Do not barf on such a mistake.
 415                 * FIXME: parse_pathspec should have eliminated
 416                 * duplicate pathspec.
 417                 */
 418                for (found_dup = other = 0;
 419                     !found_dup && other < pathspec->nr;
 420                     other++) {
 421                        if (other == num || !ps_matched[other])
 422                                continue;
 423                        if (!strcmp(pathspec->items[other].original,
 424                                    pathspec->items[num].original))
 425                                /*
 426                                 * Ok, we have a match already.
 427                                 */
 428                                found_dup = 1;
 429                }
 430                if (found_dup)
 431                        continue;
 432
 433                error("pathspec '%s' did not match any file(s) known to git.",
 434                      pathspec->items[num].original);
 435                errors++;
 436        }
 437        return errors;
 438}
 439
 440/*
 441 * Return the length of the "simple" part of a path match limiter.
 442 */
 443int simple_length(const char *match)
 444{
 445        int len = -1;
 446
 447        for (;;) {
 448                unsigned char c = *match++;
 449                len++;
 450                if (c == '\0' || is_glob_special(c))
 451                        return len;
 452        }
 453}
 454
 455int no_wildcard(const char *string)
 456{
 457        return string[simple_length(string)] == '\0';
 458}
 459
 460void parse_exclude_pattern(const char **pattern,
 461                           int *patternlen,
 462                           int *flags,
 463                           int *nowildcardlen)
 464{
 465        const char *p = *pattern;
 466        size_t i, len;
 467
 468        *flags = 0;
 469        if (*p == '!') {
 470                *flags |= EXC_FLAG_NEGATIVE;
 471                p++;
 472        }
 473        len = strlen(p);
 474        if (len && p[len - 1] == '/') {
 475                len--;
 476                *flags |= EXC_FLAG_MUSTBEDIR;
 477        }
 478        for (i = 0; i < len; i++) {
 479                if (p[i] == '/')
 480                        break;
 481        }
 482        if (i == len)
 483                *flags |= EXC_FLAG_NODIR;
 484        *nowildcardlen = simple_length(p);
 485        /*
 486         * we should have excluded the trailing slash from 'p' too,
 487         * but that's one more allocation. Instead just make sure
 488         * nowildcardlen does not exceed real patternlen
 489         */
 490        if (*nowildcardlen > len)
 491                *nowildcardlen = len;
 492        if (*p == '*' && no_wildcard(p + 1))
 493                *flags |= EXC_FLAG_ENDSWITH;
 494        *pattern = p;
 495        *patternlen = len;
 496}
 497
 498void add_exclude(const char *string, const char *base,
 499                 int baselen, struct exclude_list *el, int srcpos)
 500{
 501        struct exclude *x;
 502        int patternlen;
 503        int flags;
 504        int nowildcardlen;
 505
 506        parse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen);
 507        if (flags & EXC_FLAG_MUSTBEDIR) {
 508                char *s;
 509                x = xmalloc(sizeof(*x) + patternlen + 1);
 510                s = (char *)(x+1);
 511                memcpy(s, string, patternlen);
 512                s[patternlen] = '\0';
 513                x->pattern = s;
 514        } else {
 515                x = xmalloc(sizeof(*x));
 516                x->pattern = string;
 517        }
 518        x->patternlen = patternlen;
 519        x->nowildcardlen = nowildcardlen;
 520        x->base = base;
 521        x->baselen = baselen;
 522        x->flags = flags;
 523        x->srcpos = srcpos;
 524        ALLOC_GROW(el->excludes, el->nr + 1, el->alloc);
 525        el->excludes[el->nr++] = x;
 526        x->el = el;
 527}
 528
 529static void *read_skip_worktree_file_from_index(const char *path, size_t *size,
 530                                                struct sha1_stat *sha1_stat)
 531{
 532        int pos, len;
 533        unsigned long sz;
 534        enum object_type type;
 535        void *data;
 536
 537        len = strlen(path);
 538        pos = cache_name_pos(path, len);
 539        if (pos < 0)
 540                return NULL;
 541        if (!ce_skip_worktree(active_cache[pos]))
 542                return NULL;
 543        data = read_sha1_file(active_cache[pos]->sha1, &type, &sz);
 544        if (!data || type != OBJ_BLOB) {
 545                free(data);
 546                return NULL;
 547        }
 548        *size = xsize_t(sz);
 549        if (sha1_stat) {
 550                memset(&sha1_stat->stat, 0, sizeof(sha1_stat->stat));
 551                hashcpy(sha1_stat->sha1, active_cache[pos]->sha1);
 552        }
 553        return data;
 554}
 555
 556/*
 557 * Frees memory within el which was allocated for exclude patterns and
 558 * the file buffer.  Does not free el itself.
 559 */
 560void clear_exclude_list(struct exclude_list *el)
 561{
 562        int i;
 563
 564        for (i = 0; i < el->nr; i++)
 565                free(el->excludes[i]);
 566        free(el->excludes);
 567        free(el->filebuf);
 568
 569        memset(el, 0, sizeof(*el));
 570}
 571
 572static void trim_trailing_spaces(char *buf)
 573{
 574        char *p, *last_space = NULL;
 575
 576        for (p = buf; *p; p++)
 577                switch (*p) {
 578                case ' ':
 579                        if (!last_space)
 580                                last_space = p;
 581                        break;
 582                case '\\':
 583                        p++;
 584                        if (!*p)
 585                                return;
 586                        /* fallthrough */
 587                default:
 588                        last_space = NULL;
 589                }
 590
 591        if (last_space)
 592                *last_space = '\0';
 593}
 594
 595/*
 596 * Given a subdirectory name and "dir" of the current directory,
 597 * search the subdir in "dir" and return it, or create a new one if it
 598 * does not exist in "dir".
 599 *
 600 * If "name" has the trailing slash, it'll be excluded in the search.
 601 */
 602static struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,
 603                                                    struct untracked_cache_dir *dir,
 604                                                    const char *name, int len)
 605{
 606        int first, last;
 607        struct untracked_cache_dir *d;
 608        if (!dir)
 609                return NULL;
 610        if (len && name[len - 1] == '/')
 611                len--;
 612        first = 0;
 613        last = dir->dirs_nr;
 614        while (last > first) {
 615                int cmp, next = (last + first) >> 1;
 616                d = dir->dirs[next];
 617                cmp = strncmp(name, d->name, len);
 618                if (!cmp && strlen(d->name) > len)
 619                        cmp = -1;
 620                if (!cmp)
 621                        return d;
 622                if (cmp < 0) {
 623                        last = next;
 624                        continue;
 625                }
 626                first = next+1;
 627        }
 628
 629        uc->dir_created++;
 630        d = xmalloc(sizeof(*d) + len + 1);
 631        memset(d, 0, sizeof(*d));
 632        memcpy(d->name, name, len);
 633        d->name[len] = '\0';
 634
 635        ALLOC_GROW(dir->dirs, dir->dirs_nr + 1, dir->dirs_alloc);
 636        memmove(dir->dirs + first + 1, dir->dirs + first,
 637                (dir->dirs_nr - first) * sizeof(*dir->dirs));
 638        dir->dirs_nr++;
 639        dir->dirs[first] = d;
 640        return d;
 641}
 642
 643static void do_invalidate_gitignore(struct untracked_cache_dir *dir)
 644{
 645        int i;
 646        dir->valid = 0;
 647        dir->untracked_nr = 0;
 648        for (i = 0; i < dir->dirs_nr; i++)
 649                do_invalidate_gitignore(dir->dirs[i]);
 650}
 651
 652static void invalidate_gitignore(struct untracked_cache *uc,
 653                                 struct untracked_cache_dir *dir)
 654{
 655        uc->gitignore_invalidated++;
 656        do_invalidate_gitignore(dir);
 657}
 658
 659static void invalidate_directory(struct untracked_cache *uc,
 660                                 struct untracked_cache_dir *dir)
 661{
 662        int i;
 663        uc->dir_invalidated++;
 664        dir->valid = 0;
 665        dir->untracked_nr = 0;
 666        for (i = 0; i < dir->dirs_nr; i++)
 667                dir->dirs[i]->recurse = 0;
 668}
 669
 670/*
 671 * Given a file with name "fname", read it (either from disk, or from
 672 * the index if "check_index" is non-zero), parse it and store the
 673 * exclude rules in "el".
 674 *
 675 * If "ss" is not NULL, compute SHA-1 of the exclude file and fill
 676 * stat data from disk (only valid if add_excludes returns zero). If
 677 * ss_valid is non-zero, "ss" must contain good value as input.
 678 */
 679static int add_excludes(const char *fname, const char *base, int baselen,
 680                        struct exclude_list *el, int check_index,
 681                        struct sha1_stat *sha1_stat)
 682{
 683        struct stat st;
 684        int fd, i, lineno = 1;
 685        size_t size = 0;
 686        char *buf, *entry;
 687
 688        fd = open(fname, O_RDONLY);
 689        if (fd < 0 || fstat(fd, &st) < 0) {
 690                if (errno != ENOENT)
 691                        warn_on_inaccessible(fname);
 692                if (0 <= fd)
 693                        close(fd);
 694                if (!check_index ||
 695                    (buf = read_skip_worktree_file_from_index(fname, &size, sha1_stat)) == NULL)
 696                        return -1;
 697                if (size == 0) {
 698                        free(buf);
 699                        return 0;
 700                }
 701                if (buf[size-1] != '\n') {
 702                        buf = xrealloc(buf, size+1);
 703                        buf[size++] = '\n';
 704                }
 705        } else {
 706                size = xsize_t(st.st_size);
 707                if (size == 0) {
 708                        if (sha1_stat) {
 709                                fill_stat_data(&sha1_stat->stat, &st);
 710                                hashcpy(sha1_stat->sha1, EMPTY_BLOB_SHA1_BIN);
 711                                sha1_stat->valid = 1;
 712                        }
 713                        close(fd);
 714                        return 0;
 715                }
 716                buf = xmalloc(size+1);
 717                if (read_in_full(fd, buf, size) != size) {
 718                        free(buf);
 719                        close(fd);
 720                        return -1;
 721                }
 722                buf[size++] = '\n';
 723                close(fd);
 724                if (sha1_stat) {
 725                        int pos;
 726                        if (sha1_stat->valid &&
 727                            !match_stat_data_racy(&the_index, &sha1_stat->stat, &st))
 728                                ; /* no content change, ss->sha1 still good */
 729                        else if (check_index &&
 730                                 (pos = cache_name_pos(fname, strlen(fname))) >= 0 &&
 731                                 !ce_stage(active_cache[pos]) &&
 732                                 ce_uptodate(active_cache[pos]) &&
 733                                 !would_convert_to_git(fname))
 734                                hashcpy(sha1_stat->sha1, active_cache[pos]->sha1);
 735                        else
 736                                hash_sha1_file(buf, size, "blob", sha1_stat->sha1);
 737                        fill_stat_data(&sha1_stat->stat, &st);
 738                        sha1_stat->valid = 1;
 739                }
 740        }
 741
 742        el->filebuf = buf;
 743
 744        if (skip_utf8_bom(&buf, size))
 745                size -= buf - el->filebuf;
 746
 747        entry = buf;
 748
 749        for (i = 0; i < size; i++) {
 750                if (buf[i] == '\n') {
 751                        if (entry != buf + i && entry[0] != '#') {
 752                                buf[i - (i && buf[i-1] == '\r')] = 0;
 753                                trim_trailing_spaces(entry);
 754                                add_exclude(entry, base, baselen, el, lineno);
 755                        }
 756                        lineno++;
 757                        entry = buf + i + 1;
 758                }
 759        }
 760        return 0;
 761}
 762
 763int add_excludes_from_file_to_list(const char *fname, const char *base,
 764                                   int baselen, struct exclude_list *el,
 765                                   int check_index)
 766{
 767        return add_excludes(fname, base, baselen, el, check_index, NULL);
 768}
 769
 770struct exclude_list *add_exclude_list(struct dir_struct *dir,
 771                                      int group_type, const char *src)
 772{
 773        struct exclude_list *el;
 774        struct exclude_list_group *group;
 775
 776        group = &dir->exclude_list_group[group_type];
 777        ALLOC_GROW(group->el, group->nr + 1, group->alloc);
 778        el = &group->el[group->nr++];
 779        memset(el, 0, sizeof(*el));
 780        el->src = src;
 781        return el;
 782}
 783
 784/*
 785 * Used to set up core.excludesfile and .git/info/exclude lists.
 786 */
 787static void add_excludes_from_file_1(struct dir_struct *dir, const char *fname,
 788                                     struct sha1_stat *sha1_stat)
 789{
 790        struct exclude_list *el;
 791        /*
 792         * catch setup_standard_excludes() that's called before
 793         * dir->untracked is assigned. That function behaves
 794         * differently when dir->untracked is non-NULL.
 795         */
 796        if (!dir->untracked)
 797                dir->unmanaged_exclude_files++;
 798        el = add_exclude_list(dir, EXC_FILE, fname);
 799        if (add_excludes(fname, "", 0, el, 0, sha1_stat) < 0)
 800                die("cannot use %s as an exclude file", fname);
 801}
 802
 803void add_excludes_from_file(struct dir_struct *dir, const char *fname)
 804{
 805        dir->unmanaged_exclude_files++; /* see validate_untracked_cache() */
 806        add_excludes_from_file_1(dir, fname, NULL);
 807}
 808
 809int match_basename(const char *basename, int basenamelen,
 810                   const char *pattern, int prefix, int patternlen,
 811                   int flags)
 812{
 813        if (prefix == patternlen) {
 814                if (patternlen == basenamelen &&
 815                    !strncmp_icase(pattern, basename, basenamelen))
 816                        return 1;
 817        } else if (flags & EXC_FLAG_ENDSWITH) {
 818                /* "*literal" matching against "fooliteral" */
 819                if (patternlen - 1 <= basenamelen &&
 820                    !strncmp_icase(pattern + 1,
 821                                   basename + basenamelen - (patternlen - 1),
 822                                   patternlen - 1))
 823                        return 1;
 824        } else {
 825                if (fnmatch_icase_mem(pattern, patternlen,
 826                                      basename, basenamelen,
 827                                      0) == 0)
 828                        return 1;
 829        }
 830        return 0;
 831}
 832
 833int match_pathname(const char *pathname, int pathlen,
 834                   const char *base, int baselen,
 835                   const char *pattern, int prefix, int patternlen,
 836                   int flags)
 837{
 838        const char *name;
 839        int namelen;
 840
 841        /*
 842         * match with FNM_PATHNAME; the pattern has base implicitly
 843         * in front of it.
 844         */
 845        if (*pattern == '/') {
 846                pattern++;
 847                patternlen--;
 848                prefix--;
 849        }
 850
 851        /*
 852         * baselen does not count the trailing slash. base[] may or
 853         * may not end with a trailing slash though.
 854         */
 855        if (pathlen < baselen + 1 ||
 856            (baselen && pathname[baselen] != '/') ||
 857            strncmp_icase(pathname, base, baselen))
 858                return 0;
 859
 860        namelen = baselen ? pathlen - baselen - 1 : pathlen;
 861        name = pathname + pathlen - namelen;
 862
 863        if (prefix) {
 864                /*
 865                 * if the non-wildcard part is longer than the
 866                 * remaining pathname, surely it cannot match.
 867                 */
 868                if (prefix > namelen)
 869                        return 0;
 870
 871                if (strncmp_icase(pattern, name, prefix))
 872                        return 0;
 873                pattern += prefix;
 874                patternlen -= prefix;
 875                name    += prefix;
 876                namelen -= prefix;
 877
 878                /*
 879                 * If the whole pattern did not have a wildcard,
 880                 * then our prefix match is all we need; we
 881                 * do not need to call fnmatch at all.
 882                 */
 883                if (!patternlen && (!namelen || *name == '/'))
 884                        return 1;
 885        }
 886
 887        return fnmatch_icase_mem(pattern, patternlen,
 888                                 name, namelen,
 889                                 WM_PATHNAME) == 0;
 890}
 891
 892/*
 893 * Scan the given exclude list in reverse to see whether pathname
 894 * should be ignored.  The first match (i.e. the last on the list), if
 895 * any, determines the fate.  Returns the exclude_list element which
 896 * matched, or NULL for undecided.
 897 */
 898static struct exclude *last_exclude_matching_from_list(const char *pathname,
 899                                                       int pathlen,
 900                                                       const char *basename,
 901                                                       int *dtype,
 902                                                       struct exclude_list *el)
 903{
 904        struct exclude *exc = NULL; /* undecided */
 905        int i;
 906
 907        if (!el->nr)
 908                return NULL;    /* undefined */
 909
 910        trace_printf_key(&trace_exclude, "exclude: from %s\n", el->src);
 911
 912        for (i = el->nr - 1; 0 <= i; i--) {
 913                struct exclude *x = el->excludes[i];
 914                const char *exclude = x->pattern;
 915                int prefix = x->nowildcardlen;
 916
 917                if (x->flags & EXC_FLAG_MUSTBEDIR) {
 918                        if (*dtype == DT_UNKNOWN)
 919                                *dtype = get_dtype(NULL, pathname, pathlen);
 920                        if (*dtype != DT_DIR)
 921                                continue;
 922                }
 923
 924                if (x->flags & EXC_FLAG_NODIR) {
 925                        if (match_basename(basename,
 926                                           pathlen - (basename - pathname),
 927                                           exclude, prefix, x->patternlen,
 928                                           x->flags)) {
 929                                exc = x;
 930                                break;
 931                        }
 932                        continue;
 933                }
 934
 935                assert(x->baselen == 0 || x->base[x->baselen - 1] == '/');
 936                if (match_pathname(pathname, pathlen,
 937                                   x->base, x->baselen ? x->baselen - 1 : 0,
 938                                   exclude, prefix, x->patternlen, x->flags)) {
 939                        exc = x;
 940                        break;
 941                }
 942        }
 943
 944        if (!exc) {
 945                trace_printf_key(&trace_exclude, "exclude: %.*s => n/a\n",
 946                                 pathlen, pathname);
 947                return NULL;
 948        }
 949
 950        trace_printf_key(&trace_exclude, "exclude: %.*s vs %s at line %d => %s\n",
 951                         pathlen, pathname, exc->pattern, exc->srcpos,
 952                         exc->flags & EXC_FLAG_NEGATIVE ? "no" : "yes");
 953        return exc;
 954}
 955
 956/*
 957 * Scan the list and let the last match determine the fate.
 958 * Return 1 for exclude, 0 for include and -1 for undecided.
 959 */
 960int is_excluded_from_list(const char *pathname,
 961                          int pathlen, const char *basename, int *dtype,
 962                          struct exclude_list *el)
 963{
 964        struct exclude *exclude;
 965        exclude = last_exclude_matching_from_list(pathname, pathlen, basename, dtype, el);
 966        if (exclude)
 967                return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
 968        return -1; /* undecided */
 969}
 970
 971static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir,
 972                const char *pathname, int pathlen, const char *basename,
 973                int *dtype_p)
 974{
 975        int i, j;
 976        struct exclude_list_group *group;
 977        struct exclude *exclude;
 978        for (i = EXC_CMDL; i <= EXC_FILE; i++) {
 979                group = &dir->exclude_list_group[i];
 980                for (j = group->nr - 1; j >= 0; j--) {
 981                        exclude = last_exclude_matching_from_list(
 982                                pathname, pathlen, basename, dtype_p,
 983                                &group->el[j]);
 984                        if (exclude)
 985                                return exclude;
 986                }
 987        }
 988        return NULL;
 989}
 990
 991/*
 992 * Loads the per-directory exclude list for the substring of base
 993 * which has a char length of baselen.
 994 */
 995static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
 996{
 997        struct exclude_list_group *group;
 998        struct exclude_list *el;
 999        struct exclude_stack *stk = NULL;
1000        struct untracked_cache_dir *untracked;
1001        int current;
1002
1003        group = &dir->exclude_list_group[EXC_DIRS];
1004
1005        /*
1006         * Pop the exclude lists from the EXCL_DIRS exclude_list_group
1007         * which originate from directories not in the prefix of the
1008         * path being checked.
1009         */
1010        while ((stk = dir->exclude_stack) != NULL) {
1011                if (stk->baselen <= baselen &&
1012                    !strncmp(dir->basebuf.buf, base, stk->baselen))
1013                        break;
1014                el = &group->el[dir->exclude_stack->exclude_ix];
1015                dir->exclude_stack = stk->prev;
1016                dir->exclude = NULL;
1017                free((char *)el->src); /* see strbuf_detach() below */
1018                clear_exclude_list(el);
1019                free(stk);
1020                group->nr--;
1021        }
1022
1023        /* Skip traversing into sub directories if the parent is excluded */
1024        if (dir->exclude)
1025                return;
1026
1027        /*
1028         * Lazy initialization. All call sites currently just
1029         * memset(dir, 0, sizeof(*dir)) before use. Changing all of
1030         * them seems lots of work for little benefit.
1031         */
1032        if (!dir->basebuf.buf)
1033                strbuf_init(&dir->basebuf, PATH_MAX);
1034
1035        /* Read from the parent directories and push them down. */
1036        current = stk ? stk->baselen : -1;
1037        strbuf_setlen(&dir->basebuf, current < 0 ? 0 : current);
1038        if (dir->untracked)
1039                untracked = stk ? stk->ucd : dir->untracked->root;
1040        else
1041                untracked = NULL;
1042
1043        while (current < baselen) {
1044                const char *cp;
1045                struct sha1_stat sha1_stat;
1046
1047                stk = xcalloc(1, sizeof(*stk));
1048                if (current < 0) {
1049                        cp = base;
1050                        current = 0;
1051                } else {
1052                        cp = strchr(base + current + 1, '/');
1053                        if (!cp)
1054                                die("oops in prep_exclude");
1055                        cp++;
1056                        untracked =
1057                                lookup_untracked(dir->untracked, untracked,
1058                                                 base + current,
1059                                                 cp - base - current);
1060                }
1061                stk->prev = dir->exclude_stack;
1062                stk->baselen = cp - base;
1063                stk->exclude_ix = group->nr;
1064                stk->ucd = untracked;
1065                el = add_exclude_list(dir, EXC_DIRS, NULL);
1066                strbuf_add(&dir->basebuf, base + current, stk->baselen - current);
1067                assert(stk->baselen == dir->basebuf.len);
1068
1069                /* Abort if the directory is excluded */
1070                if (stk->baselen) {
1071                        int dt = DT_DIR;
1072                        dir->basebuf.buf[stk->baselen - 1] = 0;
1073                        dir->exclude = last_exclude_matching_from_lists(dir,
1074                                dir->basebuf.buf, stk->baselen - 1,
1075                                dir->basebuf.buf + current, &dt);
1076                        dir->basebuf.buf[stk->baselen - 1] = '/';
1077                        if (dir->exclude &&
1078                            dir->exclude->flags & EXC_FLAG_NEGATIVE)
1079                                dir->exclude = NULL;
1080                        if (dir->exclude) {
1081                                dir->exclude_stack = stk;
1082                                return;
1083                        }
1084                }
1085
1086                /* Try to read per-directory file */
1087                hashclr(sha1_stat.sha1);
1088                sha1_stat.valid = 0;
1089                if (dir->exclude_per_dir &&
1090                    /*
1091                     * If we know that no files have been added in
1092                     * this directory (i.e. valid_cached_dir() has
1093                     * been executed and set untracked->valid) ..
1094                     */
1095                    (!untracked || !untracked->valid ||
1096                     /*
1097                      * .. and .gitignore does not exist before
1098                      * (i.e. null exclude_sha1). Then we can skip
1099                      * loading .gitignore, which would result in
1100                      * ENOENT anyway.
1101                      */
1102                     !is_null_sha1(untracked->exclude_sha1))) {
1103                        /*
1104                         * dir->basebuf gets reused by the traversal, but we
1105                         * need fname to remain unchanged to ensure the src
1106                         * member of each struct exclude correctly
1107                         * back-references its source file.  Other invocations
1108                         * of add_exclude_list provide stable strings, so we
1109                         * strbuf_detach() and free() here in the caller.
1110                         */
1111                        struct strbuf sb = STRBUF_INIT;
1112                        strbuf_addbuf(&sb, &dir->basebuf);
1113                        strbuf_addstr(&sb, dir->exclude_per_dir);
1114                        el->src = strbuf_detach(&sb, NULL);
1115                        add_excludes(el->src, el->src, stk->baselen, el, 1,
1116                                     untracked ? &sha1_stat : NULL);
1117                }
1118                /*
1119                 * NEEDSWORK: when untracked cache is enabled, prep_exclude()
1120                 * will first be called in valid_cached_dir() then maybe many
1121                 * times more in last_exclude_matching(). When the cache is
1122                 * used, last_exclude_matching() will not be called and
1123                 * reading .gitignore content will be a waste.
1124                 *
1125                 * So when it's called by valid_cached_dir() and we can get
1126                 * .gitignore SHA-1 from the index (i.e. .gitignore is not
1127                 * modified on work tree), we could delay reading the
1128                 * .gitignore content until we absolutely need it in
1129                 * last_exclude_matching(). Be careful about ignore rule
1130                 * order, though, if you do that.
1131                 */
1132                if (untracked &&
1133                    hashcmp(sha1_stat.sha1, untracked->exclude_sha1)) {
1134                        invalidate_gitignore(dir->untracked, untracked);
1135                        hashcpy(untracked->exclude_sha1, sha1_stat.sha1);
1136                }
1137                dir->exclude_stack = stk;
1138                current = stk->baselen;
1139        }
1140        strbuf_setlen(&dir->basebuf, baselen);
1141}
1142
1143/*
1144 * Loads the exclude lists for the directory containing pathname, then
1145 * scans all exclude lists to determine whether pathname is excluded.
1146 * Returns the exclude_list element which matched, or NULL for
1147 * undecided.
1148 */
1149struct exclude *last_exclude_matching(struct dir_struct *dir,
1150                                             const char *pathname,
1151                                             int *dtype_p)
1152{
1153        int pathlen = strlen(pathname);
1154        const char *basename = strrchr(pathname, '/');
1155        basename = (basename) ? basename+1 : pathname;
1156
1157        prep_exclude(dir, pathname, basename-pathname);
1158
1159        if (dir->exclude)
1160                return dir->exclude;
1161
1162        return last_exclude_matching_from_lists(dir, pathname, pathlen,
1163                        basename, dtype_p);
1164}
1165
1166/*
1167 * Loads the exclude lists for the directory containing pathname, then
1168 * scans all exclude lists to determine whether pathname is excluded.
1169 * Returns 1 if true, otherwise 0.
1170 */
1171int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
1172{
1173        struct exclude *exclude =
1174                last_exclude_matching(dir, pathname, dtype_p);
1175        if (exclude)
1176                return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
1177        return 0;
1178}
1179
1180static struct dir_entry *dir_entry_new(const char *pathname, int len)
1181{
1182        struct dir_entry *ent;
1183
1184        ent = xmalloc(sizeof(*ent) + len + 1);
1185        ent->len = len;
1186        memcpy(ent->name, pathname, len);
1187        ent->name[len] = 0;
1188        return ent;
1189}
1190
1191static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
1192{
1193        if (cache_file_exists(pathname, len, ignore_case))
1194                return NULL;
1195
1196        ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
1197        return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
1198}
1199
1200struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len)
1201{
1202        if (!cache_name_is_other(pathname, len))
1203                return NULL;
1204
1205        ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
1206        return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
1207}
1208
1209enum exist_status {
1210        index_nonexistent = 0,
1211        index_directory,
1212        index_gitdir
1213};
1214
1215/*
1216 * Do not use the alphabetically sorted index to look up
1217 * the directory name; instead, use the case insensitive
1218 * directory hash.
1219 */
1220static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
1221{
1222        struct cache_entry *ce;
1223
1224        if (cache_dir_exists(dirname, len))
1225                return index_directory;
1226
1227        ce = cache_file_exists(dirname, len, ignore_case);
1228        if (ce && S_ISGITLINK(ce->ce_mode))
1229                return index_gitdir;
1230
1231        return index_nonexistent;
1232}
1233
1234/*
1235 * The index sorts alphabetically by entry name, which
1236 * means that a gitlink sorts as '\0' at the end, while
1237 * a directory (which is defined not as an entry, but as
1238 * the files it contains) will sort with the '/' at the
1239 * end.
1240 */
1241static enum exist_status directory_exists_in_index(const char *dirname, int len)
1242{
1243        int pos;
1244
1245        if (ignore_case)
1246                return directory_exists_in_index_icase(dirname, len);
1247
1248        pos = cache_name_pos(dirname, len);
1249        if (pos < 0)
1250                pos = -pos-1;
1251        while (pos < active_nr) {
1252                const struct cache_entry *ce = active_cache[pos++];
1253                unsigned char endchar;
1254
1255                if (strncmp(ce->name, dirname, len))
1256                        break;
1257                endchar = ce->name[len];
1258                if (endchar > '/')
1259                        break;
1260                if (endchar == '/')
1261                        return index_directory;
1262                if (!endchar && S_ISGITLINK(ce->ce_mode))
1263                        return index_gitdir;
1264        }
1265        return index_nonexistent;
1266}
1267
1268/*
1269 * When we find a directory when traversing the filesystem, we
1270 * have three distinct cases:
1271 *
1272 *  - ignore it
1273 *  - see it as a directory
1274 *  - recurse into it
1275 *
1276 * and which one we choose depends on a combination of existing
1277 * git index contents and the flags passed into the directory
1278 * traversal routine.
1279 *
1280 * Case 1: If we *already* have entries in the index under that
1281 * directory name, we always recurse into the directory to see
1282 * all the files.
1283 *
1284 * Case 2: If we *already* have that directory name as a gitlink,
1285 * we always continue to see it as a gitlink, regardless of whether
1286 * there is an actual git directory there or not (it might not
1287 * be checked out as a subproject!)
1288 *
1289 * Case 3: if we didn't have it in the index previously, we
1290 * have a few sub-cases:
1291 *
1292 *  (a) if "show_other_directories" is true, we show it as
1293 *      just a directory, unless "hide_empty_directories" is
1294 *      also true, in which case we need to check if it contains any
1295 *      untracked and / or ignored files.
1296 *  (b) if it looks like a git directory, and we don't have
1297 *      'no_gitlinks' set we treat it as a gitlink, and show it
1298 *      as a directory.
1299 *  (c) otherwise, we recurse into it.
1300 */
1301static enum path_treatment treat_directory(struct dir_struct *dir,
1302        struct untracked_cache_dir *untracked,
1303        const char *dirname, int len, int baselen, int exclude,
1304        const struct path_simplify *simplify)
1305{
1306        /* The "len-1" is to strip the final '/' */
1307        switch (directory_exists_in_index(dirname, len-1)) {
1308        case index_directory:
1309                return path_recurse;
1310
1311        case index_gitdir:
1312                return path_none;
1313
1314        case index_nonexistent:
1315                if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
1316                        break;
1317                if (!(dir->flags & DIR_NO_GITLINKS)) {
1318                        unsigned char sha1[20];
1319                        if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)
1320                                return path_untracked;
1321                }
1322                return path_recurse;
1323        }
1324
1325        /* This is the "show_other_directories" case */
1326
1327        if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
1328                return exclude ? path_excluded : path_untracked;
1329
1330        untracked = lookup_untracked(dir->untracked, untracked,
1331                                     dirname + baselen, len - baselen);
1332        return read_directory_recursive(dir, dirname, len,
1333                                        untracked, 1, simplify);
1334}
1335
1336/*
1337 * This is an inexact early pruning of any recursive directory
1338 * reading - if the path cannot possibly be in the pathspec,
1339 * return true, and we'll skip it early.
1340 */
1341static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)
1342{
1343        if (simplify) {
1344                for (;;) {
1345                        const char *match = simplify->path;
1346                        int len = simplify->len;
1347
1348                        if (!match)
1349                                break;
1350                        if (len > pathlen)
1351                                len = pathlen;
1352                        if (!memcmp(path, match, len))
1353                                return 0;
1354                        simplify++;
1355                }
1356                return 1;
1357        }
1358        return 0;
1359}
1360
1361/*
1362 * This function tells us whether an excluded path matches a
1363 * list of "interesting" pathspecs. That is, whether a path matched
1364 * by any of the pathspecs could possibly be ignored by excluding
1365 * the specified path. This can happen if:
1366 *
1367 *   1. the path is mentioned explicitly in the pathspec
1368 *
1369 *   2. the path is a directory prefix of some element in the
1370 *      pathspec
1371 */
1372static int exclude_matches_pathspec(const char *path, int len,
1373                const struct path_simplify *simplify)
1374{
1375        if (simplify) {
1376                for (; simplify->path; simplify++) {
1377                        if (len == simplify->len
1378                            && !memcmp(path, simplify->path, len))
1379                                return 1;
1380                        if (len < simplify->len
1381                            && simplify->path[len] == '/'
1382                            && !memcmp(path, simplify->path, len))
1383                                return 1;
1384                }
1385        }
1386        return 0;
1387}
1388
1389static int get_index_dtype(const char *path, int len)
1390{
1391        int pos;
1392        const struct cache_entry *ce;
1393
1394        ce = cache_file_exists(path, len, 0);
1395        if (ce) {
1396                if (!ce_uptodate(ce))
1397                        return DT_UNKNOWN;
1398                if (S_ISGITLINK(ce->ce_mode))
1399                        return DT_DIR;
1400                /*
1401                 * Nobody actually cares about the
1402                 * difference between DT_LNK and DT_REG
1403                 */
1404                return DT_REG;
1405        }
1406
1407        /* Try to look it up as a directory */
1408        pos = cache_name_pos(path, len);
1409        if (pos >= 0)
1410                return DT_UNKNOWN;
1411        pos = -pos-1;
1412        while (pos < active_nr) {
1413                ce = active_cache[pos++];
1414                if (strncmp(ce->name, path, len))
1415                        break;
1416                if (ce->name[len] > '/')
1417                        break;
1418                if (ce->name[len] < '/')
1419                        continue;
1420                if (!ce_uptodate(ce))
1421                        break;  /* continue? */
1422                return DT_DIR;
1423        }
1424        return DT_UNKNOWN;
1425}
1426
1427static int get_dtype(struct dirent *de, const char *path, int len)
1428{
1429        int dtype = de ? DTYPE(de) : DT_UNKNOWN;
1430        struct stat st;
1431
1432        if (dtype != DT_UNKNOWN)
1433                return dtype;
1434        dtype = get_index_dtype(path, len);
1435        if (dtype != DT_UNKNOWN)
1436                return dtype;
1437        if (lstat(path, &st))
1438                return dtype;
1439        if (S_ISREG(st.st_mode))
1440                return DT_REG;
1441        if (S_ISDIR(st.st_mode))
1442                return DT_DIR;
1443        if (S_ISLNK(st.st_mode))
1444                return DT_LNK;
1445        return dtype;
1446}
1447
1448static enum path_treatment treat_one_path(struct dir_struct *dir,
1449                                          struct untracked_cache_dir *untracked,
1450                                          struct strbuf *path,
1451                                          int baselen,
1452                                          const struct path_simplify *simplify,
1453                                          int dtype, struct dirent *de)
1454{
1455        int exclude;
1456        int has_path_in_index = !!cache_file_exists(path->buf, path->len, ignore_case);
1457
1458        if (dtype == DT_UNKNOWN)
1459                dtype = get_dtype(de, path->buf, path->len);
1460
1461        /* Always exclude indexed files */
1462        if (dtype != DT_DIR && has_path_in_index)
1463                return path_none;
1464
1465        /*
1466         * When we are looking at a directory P in the working tree,
1467         * there are three cases:
1468         *
1469         * (1) P exists in the index.  Everything inside the directory P in
1470         * the working tree needs to go when P is checked out from the
1471         * index.
1472         *
1473         * (2) P does not exist in the index, but there is P/Q in the index.
1474         * We know P will stay a directory when we check out the contents
1475         * of the index, but we do not know yet if there is a directory
1476         * P/Q in the working tree to be killed, so we need to recurse.
1477         *
1478         * (3) P does not exist in the index, and there is no P/Q in the index
1479         * to require P to be a directory, either.  Only in this case, we
1480         * know that everything inside P will not be killed without
1481         * recursing.
1482         */
1483        if ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&
1484            (dtype == DT_DIR) &&
1485            !has_path_in_index &&
1486            (directory_exists_in_index(path->buf, path->len) == index_nonexistent))
1487                return path_none;
1488
1489        exclude = is_excluded(dir, path->buf, &dtype);
1490
1491        /*
1492         * Excluded? If we don't explicitly want to show
1493         * ignored files, ignore it
1494         */
1495        if (exclude && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))
1496                return path_excluded;
1497
1498        switch (dtype) {
1499        default:
1500                return path_none;
1501        case DT_DIR:
1502                strbuf_addch(path, '/');
1503                return treat_directory(dir, untracked, path->buf, path->len,
1504                                       baselen, exclude, simplify);
1505        case DT_REG:
1506        case DT_LNK:
1507                return exclude ? path_excluded : path_untracked;
1508        }
1509}
1510
1511static enum path_treatment treat_path_fast(struct dir_struct *dir,
1512                                           struct untracked_cache_dir *untracked,
1513                                           struct cached_dir *cdir,
1514                                           struct strbuf *path,
1515                                           int baselen,
1516                                           const struct path_simplify *simplify)
1517{
1518        strbuf_setlen(path, baselen);
1519        if (!cdir->ucd) {
1520                strbuf_addstr(path, cdir->file);
1521                return path_untracked;
1522        }
1523        strbuf_addstr(path, cdir->ucd->name);
1524        /* treat_one_path() does this before it calls treat_directory() */
1525        strbuf_complete(path, '/');
1526        if (cdir->ucd->check_only)
1527                /*
1528                 * check_only is set as a result of treat_directory() getting
1529                 * to its bottom. Verify again the same set of directories
1530                 * with check_only set.
1531                 */
1532                return read_directory_recursive(dir, path->buf, path->len,
1533                                                cdir->ucd, 1, simplify);
1534        /*
1535         * We get path_recurse in the first run when
1536         * directory_exists_in_index() returns index_nonexistent. We
1537         * are sure that new changes in the index does not impact the
1538         * outcome. Return now.
1539         */
1540        return path_recurse;
1541}
1542
1543static enum path_treatment treat_path(struct dir_struct *dir,
1544                                      struct untracked_cache_dir *untracked,
1545                                      struct cached_dir *cdir,
1546                                      struct strbuf *path,
1547                                      int baselen,
1548                                      const struct path_simplify *simplify)
1549{
1550        int dtype;
1551        struct dirent *de = cdir->de;
1552
1553        if (!de)
1554                return treat_path_fast(dir, untracked, cdir, path,
1555                                       baselen, simplify);
1556        if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
1557                return path_none;
1558        strbuf_setlen(path, baselen);
1559        strbuf_addstr(path, de->d_name);
1560        if (simplify_away(path->buf, path->len, simplify))
1561                return path_none;
1562
1563        dtype = DTYPE(de);
1564        return treat_one_path(dir, untracked, path, baselen, simplify, dtype, de);
1565}
1566
1567static void add_untracked(struct untracked_cache_dir *dir, const char *name)
1568{
1569        if (!dir)
1570                return;
1571        ALLOC_GROW(dir->untracked, dir->untracked_nr + 1,
1572                   dir->untracked_alloc);
1573        dir->untracked[dir->untracked_nr++] = xstrdup(name);
1574}
1575
1576static int valid_cached_dir(struct dir_struct *dir,
1577                            struct untracked_cache_dir *untracked,
1578                            struct strbuf *path,
1579                            int check_only)
1580{
1581        struct stat st;
1582
1583        if (!untracked)
1584                return 0;
1585
1586        if (stat(path->len ? path->buf : ".", &st)) {
1587                invalidate_directory(dir->untracked, untracked);
1588                memset(&untracked->stat_data, 0, sizeof(untracked->stat_data));
1589                return 0;
1590        }
1591        if (!untracked->valid ||
1592            match_stat_data_racy(&the_index, &untracked->stat_data, &st)) {
1593                if (untracked->valid)
1594                        invalidate_directory(dir->untracked, untracked);
1595                fill_stat_data(&untracked->stat_data, &st);
1596                return 0;
1597        }
1598
1599        if (untracked->check_only != !!check_only) {
1600                invalidate_directory(dir->untracked, untracked);
1601                return 0;
1602        }
1603
1604        /*
1605         * prep_exclude will be called eventually on this directory,
1606         * but it's called much later in last_exclude_matching(). We
1607         * need it now to determine the validity of the cache for this
1608         * path. The next calls will be nearly no-op, the way
1609         * prep_exclude() is designed.
1610         */
1611        if (path->len && path->buf[path->len - 1] != '/') {
1612                strbuf_addch(path, '/');
1613                prep_exclude(dir, path->buf, path->len);
1614                strbuf_setlen(path, path->len - 1);
1615        } else
1616                prep_exclude(dir, path->buf, path->len);
1617
1618        /* hopefully prep_exclude() haven't invalidated this entry... */
1619        return untracked->valid;
1620}
1621
1622static int open_cached_dir(struct cached_dir *cdir,
1623                           struct dir_struct *dir,
1624                           struct untracked_cache_dir *untracked,
1625                           struct strbuf *path,
1626                           int check_only)
1627{
1628        memset(cdir, 0, sizeof(*cdir));
1629        cdir->untracked = untracked;
1630        if (valid_cached_dir(dir, untracked, path, check_only))
1631                return 0;
1632        cdir->fdir = opendir(path->len ? path->buf : ".");
1633        if (dir->untracked)
1634                dir->untracked->dir_opened++;
1635        if (!cdir->fdir)
1636                return -1;
1637        return 0;
1638}
1639
1640static int read_cached_dir(struct cached_dir *cdir)
1641{
1642        if (cdir->fdir) {
1643                cdir->de = readdir(cdir->fdir);
1644                if (!cdir->de)
1645                        return -1;
1646                return 0;
1647        }
1648        while (cdir->nr_dirs < cdir->untracked->dirs_nr) {
1649                struct untracked_cache_dir *d = cdir->untracked->dirs[cdir->nr_dirs];
1650                if (!d->recurse) {
1651                        cdir->nr_dirs++;
1652                        continue;
1653                }
1654                cdir->ucd = d;
1655                cdir->nr_dirs++;
1656                return 0;
1657        }
1658        cdir->ucd = NULL;
1659        if (cdir->nr_files < cdir->untracked->untracked_nr) {
1660                struct untracked_cache_dir *d = cdir->untracked;
1661                cdir->file = d->untracked[cdir->nr_files++];
1662                return 0;
1663        }
1664        return -1;
1665}
1666
1667static void close_cached_dir(struct cached_dir *cdir)
1668{
1669        if (cdir->fdir)
1670                closedir(cdir->fdir);
1671        /*
1672         * We have gone through this directory and found no untracked
1673         * entries. Mark it valid.
1674         */
1675        if (cdir->untracked) {
1676                cdir->untracked->valid = 1;
1677                cdir->untracked->recurse = 1;
1678        }
1679}
1680
1681/*
1682 * Read a directory tree. We currently ignore anything but
1683 * directories, regular files and symlinks. That's because git
1684 * doesn't handle them at all yet. Maybe that will change some
1685 * day.
1686 *
1687 * Also, we ignore the name ".git" (even if it is not a directory).
1688 * That likely will not change.
1689 *
1690 * Returns the most significant path_treatment value encountered in the scan.
1691 */
1692static enum path_treatment read_directory_recursive(struct dir_struct *dir,
1693                                    const char *base, int baselen,
1694                                    struct untracked_cache_dir *untracked, int check_only,
1695                                    const struct path_simplify *simplify)
1696{
1697        struct cached_dir cdir;
1698        enum path_treatment state, subdir_state, dir_state = path_none;
1699        struct strbuf path = STRBUF_INIT;
1700        static int level = 0;
1701
1702        strbuf_add(&path, base, baselen);
1703
1704        trace_printf_key(&trace_exclude, "exclude: [%d] enter '%.*s'\n",
1705                         level++, baselen, base);
1706
1707        if (open_cached_dir(&cdir, dir, untracked, &path, check_only))
1708                goto out;
1709
1710        if (untracked)
1711                untracked->check_only = !!check_only;
1712
1713        while (!read_cached_dir(&cdir)) {
1714                /* check how the file or directory should be treated */
1715                state = treat_path(dir, untracked, &cdir, &path, baselen, simplify);
1716
1717                if (state > dir_state)
1718                        dir_state = state;
1719
1720                /* recurse into subdir if instructed by treat_path */
1721                if (state == path_recurse) {
1722                        struct untracked_cache_dir *ud;
1723                        ud = lookup_untracked(dir->untracked, untracked,
1724                                              path.buf + baselen,
1725                                              path.len - baselen);
1726                        subdir_state =
1727                                read_directory_recursive(dir, path.buf, path.len,
1728                                                         ud, check_only, simplify);
1729                        if (subdir_state > dir_state)
1730                                dir_state = subdir_state;
1731                }
1732
1733                if (check_only) {
1734                        /* abort early if maximum state has been reached */
1735                        if (dir_state == path_untracked) {
1736                                if (cdir.fdir)
1737                                        add_untracked(untracked, path.buf + baselen);
1738                                break;
1739                        }
1740                        /* skip the dir_add_* part */
1741                        continue;
1742                }
1743
1744                /* add the path to the appropriate result list */
1745                switch (state) {
1746                case path_excluded:
1747                        if (dir->flags & DIR_SHOW_IGNORED)
1748                                dir_add_name(dir, path.buf, path.len);
1749                        else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
1750                                ((dir->flags & DIR_COLLECT_IGNORED) &&
1751                                exclude_matches_pathspec(path.buf, path.len,
1752                                        simplify)))
1753                                dir_add_ignored(dir, path.buf, path.len);
1754                        break;
1755
1756                case path_untracked:
1757                        if (dir->flags & DIR_SHOW_IGNORED)
1758                                break;
1759                        dir_add_name(dir, path.buf, path.len);
1760                        if (cdir.fdir)
1761                                add_untracked(untracked, path.buf + baselen);
1762                        break;
1763
1764                default:
1765                        break;
1766                }
1767        }
1768        close_cached_dir(&cdir);
1769 out:
1770        trace_printf_key(&trace_exclude, "exclude: [%d] leave '%.*s'\n",
1771                         --level, baselen, base);
1772        strbuf_release(&path);
1773
1774        return dir_state;
1775}
1776
1777static int cmp_name(const void *p1, const void *p2)
1778{
1779        const struct dir_entry *e1 = *(const struct dir_entry **)p1;
1780        const struct dir_entry *e2 = *(const struct dir_entry **)p2;
1781
1782        return name_compare(e1->name, e1->len, e2->name, e2->len);
1783}
1784
1785static struct path_simplify *create_simplify(const char **pathspec)
1786{
1787        int nr, alloc = 0;
1788        struct path_simplify *simplify = NULL;
1789
1790        if (!pathspec)
1791                return NULL;
1792
1793        for (nr = 0 ; ; nr++) {
1794                const char *match;
1795                ALLOC_GROW(simplify, nr + 1, alloc);
1796                match = *pathspec++;
1797                if (!match)
1798                        break;
1799                simplify[nr].path = match;
1800                simplify[nr].len = simple_length(match);
1801        }
1802        simplify[nr].path = NULL;
1803        simplify[nr].len = 0;
1804        return simplify;
1805}
1806
1807static void free_simplify(struct path_simplify *simplify)
1808{
1809        free(simplify);
1810}
1811
1812static int treat_leading_path(struct dir_struct *dir,
1813                              const char *path, int len,
1814                              const struct path_simplify *simplify)
1815{
1816        struct strbuf sb = STRBUF_INIT;
1817        int baselen, rc = 0;
1818        const char *cp;
1819        int old_flags = dir->flags;
1820
1821        while (len && path[len - 1] == '/')
1822                len--;
1823        if (!len)
1824                return 1;
1825        baselen = 0;
1826        dir->flags &= ~DIR_SHOW_OTHER_DIRECTORIES;
1827        while (1) {
1828                cp = path + baselen + !!baselen;
1829                cp = memchr(cp, '/', path + len - cp);
1830                if (!cp)
1831                        baselen = len;
1832                else
1833                        baselen = cp - path;
1834                strbuf_setlen(&sb, 0);
1835                strbuf_add(&sb, path, baselen);
1836                if (!is_directory(sb.buf))
1837                        break;
1838                if (simplify_away(sb.buf, sb.len, simplify))
1839                        break;
1840                if (treat_one_path(dir, NULL, &sb, baselen, simplify,
1841                                   DT_DIR, NULL) == path_none)
1842                        break; /* do not recurse into it */
1843                if (len <= baselen) {
1844                        rc = 1;
1845                        break; /* finished checking */
1846                }
1847        }
1848        strbuf_release(&sb);
1849        dir->flags = old_flags;
1850        return rc;
1851}
1852
1853static const char *get_ident_string(void)
1854{
1855        static struct strbuf sb = STRBUF_INIT;
1856        struct utsname uts;
1857
1858        if (sb.len)
1859                return sb.buf;
1860        if (uname(&uts) < 0)
1861                die_errno(_("failed to get kernel name and information"));
1862        strbuf_addf(&sb, "Location %s, system %s", get_git_work_tree(),
1863                    uts.sysname);
1864        return sb.buf;
1865}
1866
1867static int ident_in_untracked(const struct untracked_cache *uc)
1868{
1869        /*
1870         * Previous git versions may have saved many NUL separated
1871         * strings in the "ident" field, but it is insane to manage
1872         * many locations, so just take care of the first one.
1873         */
1874
1875        return !strcmp(uc->ident.buf, get_ident_string());
1876}
1877
1878static void set_untracked_ident(struct untracked_cache *uc)
1879{
1880        strbuf_reset(&uc->ident);
1881        strbuf_addstr(&uc->ident, get_ident_string());
1882
1883        /*
1884         * This strbuf used to contain a list of NUL separated
1885         * strings, so save NUL too for backward compatibility.
1886         */
1887        strbuf_addch(&uc->ident, 0);
1888}
1889
1890static void new_untracked_cache(struct index_state *istate)
1891{
1892        struct untracked_cache *uc = xcalloc(1, sizeof(*uc));
1893        strbuf_init(&uc->ident, 100);
1894        uc->exclude_per_dir = ".gitignore";
1895        /* should be the same flags used by git-status */
1896        uc->dir_flags = DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES;
1897        set_untracked_ident(uc);
1898        istate->untracked = uc;
1899        istate->cache_changed |= UNTRACKED_CHANGED;
1900}
1901
1902void add_untracked_cache(struct index_state *istate)
1903{
1904        if (!istate->untracked) {
1905                new_untracked_cache(istate);
1906        } else {
1907                if (!ident_in_untracked(istate->untracked)) {
1908                        free_untracked_cache(istate->untracked);
1909                        new_untracked_cache(istate);
1910                }
1911        }
1912}
1913
1914void remove_untracked_cache(struct index_state *istate)
1915{
1916        if (istate->untracked) {
1917                free_untracked_cache(istate->untracked);
1918                istate->untracked = NULL;
1919                istate->cache_changed |= UNTRACKED_CHANGED;
1920        }
1921}
1922
1923static struct untracked_cache_dir *validate_untracked_cache(struct dir_struct *dir,
1924                                                      int base_len,
1925                                                      const struct pathspec *pathspec)
1926{
1927        struct untracked_cache_dir *root;
1928
1929        if (!dir->untracked || getenv("GIT_DISABLE_UNTRACKED_CACHE"))
1930                return NULL;
1931
1932        /*
1933         * We only support $GIT_DIR/info/exclude and core.excludesfile
1934         * as the global ignore rule files. Any other additions
1935         * (e.g. from command line) invalidate the cache. This
1936         * condition also catches running setup_standard_excludes()
1937         * before setting dir->untracked!
1938         */
1939        if (dir->unmanaged_exclude_files)
1940                return NULL;
1941
1942        /*
1943         * Optimize for the main use case only: whole-tree git
1944         * status. More work involved in treat_leading_path() if we
1945         * use cache on just a subset of the worktree. pathspec
1946         * support could make the matter even worse.
1947         */
1948        if (base_len || (pathspec && pathspec->nr))
1949                return NULL;
1950
1951        /* Different set of flags may produce different results */
1952        if (dir->flags != dir->untracked->dir_flags ||
1953            /*
1954             * See treat_directory(), case index_nonexistent. Without
1955             * this flag, we may need to also cache .git file content
1956             * for the resolve_gitlink_ref() call, which we don't.
1957             */
1958            !(dir->flags & DIR_SHOW_OTHER_DIRECTORIES) ||
1959            /* We don't support collecting ignore files */
1960            (dir->flags & (DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO |
1961                           DIR_COLLECT_IGNORED)))
1962                return NULL;
1963
1964        /*
1965         * If we use .gitignore in the cache and now you change it to
1966         * .gitexclude, everything will go wrong.
1967         */
1968        if (dir->exclude_per_dir != dir->untracked->exclude_per_dir &&
1969            strcmp(dir->exclude_per_dir, dir->untracked->exclude_per_dir))
1970                return NULL;
1971
1972        /*
1973         * EXC_CMDL is not considered in the cache. If people set it,
1974         * skip the cache.
1975         */
1976        if (dir->exclude_list_group[EXC_CMDL].nr)
1977                return NULL;
1978
1979        if (!ident_in_untracked(dir->untracked)) {
1980                warning(_("Untracked cache is disabled on this system or location."));
1981                return NULL;
1982        }
1983
1984        if (!dir->untracked->root) {
1985                const int len = sizeof(*dir->untracked->root);
1986                dir->untracked->root = xmalloc(len);
1987                memset(dir->untracked->root, 0, len);
1988        }
1989
1990        /* Validate $GIT_DIR/info/exclude and core.excludesfile */
1991        root = dir->untracked->root;
1992        if (hashcmp(dir->ss_info_exclude.sha1,
1993                    dir->untracked->ss_info_exclude.sha1)) {
1994                invalidate_gitignore(dir->untracked, root);
1995                dir->untracked->ss_info_exclude = dir->ss_info_exclude;
1996        }
1997        if (hashcmp(dir->ss_excludes_file.sha1,
1998                    dir->untracked->ss_excludes_file.sha1)) {
1999                invalidate_gitignore(dir->untracked, root);
2000                dir->untracked->ss_excludes_file = dir->ss_excludes_file;
2001        }
2002
2003        /* Make sure this directory is not dropped out at saving phase */
2004        root->recurse = 1;
2005        return root;
2006}
2007
2008int read_directory(struct dir_struct *dir, const char *path, int len, const struct pathspec *pathspec)
2009{
2010        struct path_simplify *simplify;
2011        struct untracked_cache_dir *untracked;
2012
2013        /*
2014         * Check out create_simplify()
2015         */
2016        if (pathspec)
2017                GUARD_PATHSPEC(pathspec,
2018                               PATHSPEC_FROMTOP |
2019                               PATHSPEC_MAXDEPTH |
2020                               PATHSPEC_LITERAL |
2021                               PATHSPEC_GLOB |
2022                               PATHSPEC_ICASE |
2023                               PATHSPEC_EXCLUDE);
2024
2025        if (has_symlink_leading_path(path, len))
2026                return dir->nr;
2027
2028        /*
2029         * exclude patterns are treated like positive ones in
2030         * create_simplify. Usually exclude patterns should be a
2031         * subset of positive ones, which has no impacts on
2032         * create_simplify().
2033         */
2034        simplify = create_simplify(pathspec ? pathspec->_raw : NULL);
2035        untracked = validate_untracked_cache(dir, len, pathspec);
2036        if (!untracked)
2037                /*
2038                 * make sure untracked cache code path is disabled,
2039                 * e.g. prep_exclude()
2040                 */
2041                dir->untracked = NULL;
2042        if (!len || treat_leading_path(dir, path, len, simplify))
2043                read_directory_recursive(dir, path, len, untracked, 0, simplify);
2044        free_simplify(simplify);
2045        qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
2046        qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
2047        if (dir->untracked) {
2048                static struct trace_key trace_untracked_stats = TRACE_KEY_INIT(UNTRACKED_STATS);
2049                trace_printf_key(&trace_untracked_stats,
2050                                 "node creation: %u\n"
2051                                 "gitignore invalidation: %u\n"
2052                                 "directory invalidation: %u\n"
2053                                 "opendir: %u\n",
2054                                 dir->untracked->dir_created,
2055                                 dir->untracked->gitignore_invalidated,
2056                                 dir->untracked->dir_invalidated,
2057                                 dir->untracked->dir_opened);
2058                if (dir->untracked == the_index.untracked &&
2059                    (dir->untracked->dir_opened ||
2060                     dir->untracked->gitignore_invalidated ||
2061                     dir->untracked->dir_invalidated))
2062                        the_index.cache_changed |= UNTRACKED_CHANGED;
2063                if (dir->untracked != the_index.untracked) {
2064                        free(dir->untracked);
2065                        dir->untracked = NULL;
2066                }
2067        }
2068        return dir->nr;
2069}
2070
2071int file_exists(const char *f)
2072{
2073        struct stat sb;
2074        return lstat(f, &sb) == 0;
2075}
2076
2077static int cmp_icase(char a, char b)
2078{
2079        if (a == b)
2080                return 0;
2081        if (ignore_case)
2082                return toupper(a) - toupper(b);
2083        return a - b;
2084}
2085
2086/*
2087 * Given two normalized paths (a trailing slash is ok), if subdir is
2088 * outside dir, return -1.  Otherwise return the offset in subdir that
2089 * can be used as relative path to dir.
2090 */
2091int dir_inside_of(const char *subdir, const char *dir)
2092{
2093        int offset = 0;
2094
2095        assert(dir && subdir && *dir && *subdir);
2096
2097        while (*dir && *subdir && !cmp_icase(*dir, *subdir)) {
2098                dir++;
2099                subdir++;
2100                offset++;
2101        }
2102
2103        /* hel[p]/me vs hel[l]/yeah */
2104        if (*dir && *subdir)
2105                return -1;
2106
2107        if (!*subdir)
2108                return !*dir ? offset : -1; /* same dir */
2109
2110        /* foo/[b]ar vs foo/[] */
2111        if (is_dir_sep(dir[-1]))
2112                return is_dir_sep(subdir[-1]) ? offset : -1;
2113
2114        /* foo[/]bar vs foo[] */
2115        return is_dir_sep(*subdir) ? offset + 1 : -1;
2116}
2117
2118int is_inside_dir(const char *dir)
2119{
2120        char *cwd;
2121        int rc;
2122
2123        if (!dir)
2124                return 0;
2125
2126        cwd = xgetcwd();
2127        rc = (dir_inside_of(cwd, dir) >= 0);
2128        free(cwd);
2129        return rc;
2130}
2131
2132int is_empty_dir(const char *path)
2133{
2134        DIR *dir = opendir(path);
2135        struct dirent *e;
2136        int ret = 1;
2137
2138        if (!dir)
2139                return 0;
2140
2141        while ((e = readdir(dir)) != NULL)
2142                if (!is_dot_or_dotdot(e->d_name)) {
2143                        ret = 0;
2144                        break;
2145                }
2146
2147        closedir(dir);
2148        return ret;
2149}
2150
2151static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)
2152{
2153        DIR *dir;
2154        struct dirent *e;
2155        int ret = 0, original_len = path->len, len, kept_down = 0;
2156        int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
2157        int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);
2158        unsigned char submodule_head[20];
2159
2160        if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
2161            !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
2162                /* Do not descend and nuke a nested git work tree. */
2163                if (kept_up)
2164                        *kept_up = 1;
2165                return 0;
2166        }
2167
2168        flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;
2169        dir = opendir(path->buf);
2170        if (!dir) {
2171                if (errno == ENOENT)
2172                        return keep_toplevel ? -1 : 0;
2173                else if (errno == EACCES && !keep_toplevel)
2174                        /*
2175                         * An empty dir could be removable even if it
2176                         * is unreadable:
2177                         */
2178                        return rmdir(path->buf);
2179                else
2180                        return -1;
2181        }
2182        strbuf_complete(path, '/');
2183
2184        len = path->len;
2185        while ((e = readdir(dir)) != NULL) {
2186                struct stat st;
2187                if (is_dot_or_dotdot(e->d_name))
2188                        continue;
2189
2190                strbuf_setlen(path, len);
2191                strbuf_addstr(path, e->d_name);
2192                if (lstat(path->buf, &st)) {
2193                        if (errno == ENOENT)
2194                                /*
2195                                 * file disappeared, which is what we
2196                                 * wanted anyway
2197                                 */
2198                                continue;
2199                        /* fall thru */
2200                } else if (S_ISDIR(st.st_mode)) {
2201                        if (!remove_dir_recurse(path, flag, &kept_down))
2202                                continue; /* happy */
2203                } else if (!only_empty &&
2204                           (!unlink(path->buf) || errno == ENOENT)) {
2205                        continue; /* happy, too */
2206                }
2207
2208                /* path too long, stat fails, or non-directory still exists */
2209                ret = -1;
2210                break;
2211        }
2212        closedir(dir);
2213
2214        strbuf_setlen(path, original_len);
2215        if (!ret && !keep_toplevel && !kept_down)
2216                ret = (!rmdir(path->buf) || errno == ENOENT) ? 0 : -1;
2217        else if (kept_up)
2218                /*
2219                 * report the uplevel that it is not an error that we
2220                 * did not rmdir() our directory.
2221                 */
2222                *kept_up = !ret;
2223        return ret;
2224}
2225
2226int remove_dir_recursively(struct strbuf *path, int flag)
2227{
2228        return remove_dir_recurse(path, flag, NULL);
2229}
2230
2231static GIT_PATH_FUNC(git_path_info_exclude, "info/exclude")
2232
2233void setup_standard_excludes(struct dir_struct *dir)
2234{
2235        const char *path;
2236
2237        dir->exclude_per_dir = ".gitignore";
2238
2239        /* core.excludefile defaulting to $XDG_HOME/git/ignore */
2240        if (!excludes_file)
2241                excludes_file = xdg_config_home("ignore");
2242        if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))
2243                add_excludes_from_file_1(dir, excludes_file,
2244                                         dir->untracked ? &dir->ss_excludes_file : NULL);
2245
2246        /* per repository user preference */
2247        path = git_path_info_exclude();
2248        if (!access_or_warn(path, R_OK, 0))
2249                add_excludes_from_file_1(dir, path,
2250                                         dir->untracked ? &dir->ss_info_exclude : NULL);
2251}
2252
2253int remove_path(const char *name)
2254{
2255        char *slash;
2256
2257        if (unlink(name) && errno != ENOENT && errno != ENOTDIR)
2258                return -1;
2259
2260        slash = strrchr(name, '/');
2261        if (slash) {
2262                char *dirs = xstrdup(name);
2263                slash = dirs + (slash - name);
2264                do {
2265                        *slash = '\0';
2266                } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
2267                free(dirs);
2268        }
2269        return 0;
2270}
2271
2272/*
2273 * Frees memory within dir which was allocated for exclude lists and
2274 * the exclude_stack.  Does not free dir itself.
2275 */
2276void clear_directory(struct dir_struct *dir)
2277{
2278        int i, j;
2279        struct exclude_list_group *group;
2280        struct exclude_list *el;
2281        struct exclude_stack *stk;
2282
2283        for (i = EXC_CMDL; i <= EXC_FILE; i++) {
2284                group = &dir->exclude_list_group[i];
2285                for (j = 0; j < group->nr; j++) {
2286                        el = &group->el[j];
2287                        if (i == EXC_DIRS)
2288                                free((char *)el->src);
2289                        clear_exclude_list(el);
2290                }
2291                free(group->el);
2292        }
2293
2294        stk = dir->exclude_stack;
2295        while (stk) {
2296                struct exclude_stack *prev = stk->prev;
2297                free(stk);
2298                stk = prev;
2299        }
2300        strbuf_release(&dir->basebuf);
2301}
2302
2303struct ondisk_untracked_cache {
2304        struct stat_data info_exclude_stat;
2305        struct stat_data excludes_file_stat;
2306        uint32_t dir_flags;
2307        unsigned char info_exclude_sha1[20];
2308        unsigned char excludes_file_sha1[20];
2309        char exclude_per_dir[FLEX_ARRAY];
2310};
2311
2312#define ouc_size(len) (offsetof(struct ondisk_untracked_cache, exclude_per_dir) + len + 1)
2313
2314struct write_data {
2315        int index;         /* number of written untracked_cache_dir */
2316        struct ewah_bitmap *check_only; /* from untracked_cache_dir */
2317        struct ewah_bitmap *valid;      /* from untracked_cache_dir */
2318        struct ewah_bitmap *sha1_valid; /* set if exclude_sha1 is not null */
2319        struct strbuf out;
2320        struct strbuf sb_stat;
2321        struct strbuf sb_sha1;
2322};
2323
2324static void stat_data_to_disk(struct stat_data *to, const struct stat_data *from)
2325{
2326        to->sd_ctime.sec  = htonl(from->sd_ctime.sec);
2327        to->sd_ctime.nsec = htonl(from->sd_ctime.nsec);
2328        to->sd_mtime.sec  = htonl(from->sd_mtime.sec);
2329        to->sd_mtime.nsec = htonl(from->sd_mtime.nsec);
2330        to->sd_dev        = htonl(from->sd_dev);
2331        to->sd_ino        = htonl(from->sd_ino);
2332        to->sd_uid        = htonl(from->sd_uid);
2333        to->sd_gid        = htonl(from->sd_gid);
2334        to->sd_size       = htonl(from->sd_size);
2335}
2336
2337static void write_one_dir(struct untracked_cache_dir *untracked,
2338                          struct write_data *wd)
2339{
2340        struct stat_data stat_data;
2341        struct strbuf *out = &wd->out;
2342        unsigned char intbuf[16];
2343        unsigned int intlen, value;
2344        int i = wd->index++;
2345
2346        /*
2347         * untracked_nr should be reset whenever valid is clear, but
2348         * for safety..
2349         */
2350        if (!untracked->valid) {
2351                untracked->untracked_nr = 0;
2352                untracked->check_only = 0;
2353        }
2354
2355        if (untracked->check_only)
2356                ewah_set(wd->check_only, i);
2357        if (untracked->valid) {
2358                ewah_set(wd->valid, i);
2359                stat_data_to_disk(&stat_data, &untracked->stat_data);
2360                strbuf_add(&wd->sb_stat, &stat_data, sizeof(stat_data));
2361        }
2362        if (!is_null_sha1(untracked->exclude_sha1)) {
2363                ewah_set(wd->sha1_valid, i);
2364                strbuf_add(&wd->sb_sha1, untracked->exclude_sha1, 20);
2365        }
2366
2367        intlen = encode_varint(untracked->untracked_nr, intbuf);
2368        strbuf_add(out, intbuf, intlen);
2369
2370        /* skip non-recurse directories */
2371        for (i = 0, value = 0; i < untracked->dirs_nr; i++)
2372                if (untracked->dirs[i]->recurse)
2373                        value++;
2374        intlen = encode_varint(value, intbuf);
2375        strbuf_add(out, intbuf, intlen);
2376
2377        strbuf_add(out, untracked->name, strlen(untracked->name) + 1);
2378
2379        for (i = 0; i < untracked->untracked_nr; i++)
2380                strbuf_add(out, untracked->untracked[i],
2381                           strlen(untracked->untracked[i]) + 1);
2382
2383        for (i = 0; i < untracked->dirs_nr; i++)
2384                if (untracked->dirs[i]->recurse)
2385                        write_one_dir(untracked->dirs[i], wd);
2386}
2387
2388void write_untracked_extension(struct strbuf *out, struct untracked_cache *untracked)
2389{
2390        struct ondisk_untracked_cache *ouc;
2391        struct write_data wd;
2392        unsigned char varbuf[16];
2393        int len = 0, varint_len;
2394        if (untracked->exclude_per_dir)
2395                len = strlen(untracked->exclude_per_dir);
2396        ouc = xmalloc(sizeof(*ouc) + len + 1);
2397        stat_data_to_disk(&ouc->info_exclude_stat, &untracked->ss_info_exclude.stat);
2398        stat_data_to_disk(&ouc->excludes_file_stat, &untracked->ss_excludes_file.stat);
2399        hashcpy(ouc->info_exclude_sha1, untracked->ss_info_exclude.sha1);
2400        hashcpy(ouc->excludes_file_sha1, untracked->ss_excludes_file.sha1);
2401        ouc->dir_flags = htonl(untracked->dir_flags);
2402        memcpy(ouc->exclude_per_dir, untracked->exclude_per_dir, len + 1);
2403
2404        varint_len = encode_varint(untracked->ident.len, varbuf);
2405        strbuf_add(out, varbuf, varint_len);
2406        strbuf_add(out, untracked->ident.buf, untracked->ident.len);
2407
2408        strbuf_add(out, ouc, ouc_size(len));
2409        free(ouc);
2410        ouc = NULL;
2411
2412        if (!untracked->root) {
2413                varint_len = encode_varint(0, varbuf);
2414                strbuf_add(out, varbuf, varint_len);
2415                return;
2416        }
2417
2418        wd.index      = 0;
2419        wd.check_only = ewah_new();
2420        wd.valid      = ewah_new();
2421        wd.sha1_valid = ewah_new();
2422        strbuf_init(&wd.out, 1024);
2423        strbuf_init(&wd.sb_stat, 1024);
2424        strbuf_init(&wd.sb_sha1, 1024);
2425        write_one_dir(untracked->root, &wd);
2426
2427        varint_len = encode_varint(wd.index, varbuf);
2428        strbuf_add(out, varbuf, varint_len);
2429        strbuf_addbuf(out, &wd.out);
2430        ewah_serialize_strbuf(wd.valid, out);
2431        ewah_serialize_strbuf(wd.check_only, out);
2432        ewah_serialize_strbuf(wd.sha1_valid, out);
2433        strbuf_addbuf(out, &wd.sb_stat);
2434        strbuf_addbuf(out, &wd.sb_sha1);
2435        strbuf_addch(out, '\0'); /* safe guard for string lists */
2436
2437        ewah_free(wd.valid);
2438        ewah_free(wd.check_only);
2439        ewah_free(wd.sha1_valid);
2440        strbuf_release(&wd.out);
2441        strbuf_release(&wd.sb_stat);
2442        strbuf_release(&wd.sb_sha1);
2443}
2444
2445static void free_untracked(struct untracked_cache_dir *ucd)
2446{
2447        int i;
2448        if (!ucd)
2449                return;
2450        for (i = 0; i < ucd->dirs_nr; i++)
2451                free_untracked(ucd->dirs[i]);
2452        for (i = 0; i < ucd->untracked_nr; i++)
2453                free(ucd->untracked[i]);
2454        free(ucd->untracked);
2455        free(ucd->dirs);
2456        free(ucd);
2457}
2458
2459void free_untracked_cache(struct untracked_cache *uc)
2460{
2461        if (uc)
2462                free_untracked(uc->root);
2463        free(uc);
2464}
2465
2466struct read_data {
2467        int index;
2468        struct untracked_cache_dir **ucd;
2469        struct ewah_bitmap *check_only;
2470        struct ewah_bitmap *valid;
2471        struct ewah_bitmap *sha1_valid;
2472        const unsigned char *data;
2473        const unsigned char *end;
2474};
2475
2476static void stat_data_from_disk(struct stat_data *to, const struct stat_data *from)
2477{
2478        to->sd_ctime.sec  = get_be32(&from->sd_ctime.sec);
2479        to->sd_ctime.nsec = get_be32(&from->sd_ctime.nsec);
2480        to->sd_mtime.sec  = get_be32(&from->sd_mtime.sec);
2481        to->sd_mtime.nsec = get_be32(&from->sd_mtime.nsec);
2482        to->sd_dev        = get_be32(&from->sd_dev);
2483        to->sd_ino        = get_be32(&from->sd_ino);
2484        to->sd_uid        = get_be32(&from->sd_uid);
2485        to->sd_gid        = get_be32(&from->sd_gid);
2486        to->sd_size       = get_be32(&from->sd_size);
2487}
2488
2489static int read_one_dir(struct untracked_cache_dir **untracked_,
2490                        struct read_data *rd)
2491{
2492        struct untracked_cache_dir ud, *untracked;
2493        const unsigned char *next, *data = rd->data, *end = rd->end;
2494        unsigned int value;
2495        int i, len;
2496
2497        memset(&ud, 0, sizeof(ud));
2498
2499        next = data;
2500        value = decode_varint(&next);
2501        if (next > end)
2502                return -1;
2503        ud.recurse         = 1;
2504        ud.untracked_alloc = value;
2505        ud.untracked_nr    = value;
2506        if (ud.untracked_nr)
2507                ud.untracked = xmalloc(sizeof(*ud.untracked) * ud.untracked_nr);
2508        data = next;
2509
2510        next = data;
2511        ud.dirs_alloc = ud.dirs_nr = decode_varint(&next);
2512        if (next > end)
2513                return -1;
2514        ud.dirs = xmalloc(sizeof(*ud.dirs) * ud.dirs_nr);
2515        data = next;
2516
2517        len = strlen((const char *)data);
2518        next = data + len + 1;
2519        if (next > rd->end)
2520                return -1;
2521        *untracked_ = untracked = xmalloc(sizeof(*untracked) + len);
2522        memcpy(untracked, &ud, sizeof(ud));
2523        memcpy(untracked->name, data, len + 1);
2524        data = next;
2525
2526        for (i = 0; i < untracked->untracked_nr; i++) {
2527                len = strlen((const char *)data);
2528                next = data + len + 1;
2529                if (next > rd->end)
2530                        return -1;
2531                untracked->untracked[i] = xstrdup((const char*)data);
2532                data = next;
2533        }
2534
2535        rd->ucd[rd->index++] = untracked;
2536        rd->data = data;
2537
2538        for (i = 0; i < untracked->dirs_nr; i++) {
2539                len = read_one_dir(untracked->dirs + i, rd);
2540                if (len < 0)
2541                        return -1;
2542        }
2543        return 0;
2544}
2545
2546static void set_check_only(size_t pos, void *cb)
2547{
2548        struct read_data *rd = cb;
2549        struct untracked_cache_dir *ud = rd->ucd[pos];
2550        ud->check_only = 1;
2551}
2552
2553static void read_stat(size_t pos, void *cb)
2554{
2555        struct read_data *rd = cb;
2556        struct untracked_cache_dir *ud = rd->ucd[pos];
2557        if (rd->data + sizeof(struct stat_data) > rd->end) {
2558                rd->data = rd->end + 1;
2559                return;
2560        }
2561        stat_data_from_disk(&ud->stat_data, (struct stat_data *)rd->data);
2562        rd->data += sizeof(struct stat_data);
2563        ud->valid = 1;
2564}
2565
2566static void read_sha1(size_t pos, void *cb)
2567{
2568        struct read_data *rd = cb;
2569        struct untracked_cache_dir *ud = rd->ucd[pos];
2570        if (rd->data + 20 > rd->end) {
2571                rd->data = rd->end + 1;
2572                return;
2573        }
2574        hashcpy(ud->exclude_sha1, rd->data);
2575        rd->data += 20;
2576}
2577
2578static void load_sha1_stat(struct sha1_stat *sha1_stat,
2579                           const struct stat_data *stat,
2580                           const unsigned char *sha1)
2581{
2582        stat_data_from_disk(&sha1_stat->stat, stat);
2583        hashcpy(sha1_stat->sha1, sha1);
2584        sha1_stat->valid = 1;
2585}
2586
2587struct untracked_cache *read_untracked_extension(const void *data, unsigned long sz)
2588{
2589        const struct ondisk_untracked_cache *ouc;
2590        struct untracked_cache *uc;
2591        struct read_data rd;
2592        const unsigned char *next = data, *end = (const unsigned char *)data + sz;
2593        const char *ident;
2594        int ident_len, len;
2595
2596        if (sz <= 1 || end[-1] != '\0')
2597                return NULL;
2598        end--;
2599
2600        ident_len = decode_varint(&next);
2601        if (next + ident_len > end)
2602                return NULL;
2603        ident = (const char *)next;
2604        next += ident_len;
2605
2606        ouc = (const struct ondisk_untracked_cache *)next;
2607        if (next + ouc_size(0) > end)
2608                return NULL;
2609
2610        uc = xcalloc(1, sizeof(*uc));
2611        strbuf_init(&uc->ident, ident_len);
2612        strbuf_add(&uc->ident, ident, ident_len);
2613        load_sha1_stat(&uc->ss_info_exclude, &ouc->info_exclude_stat,
2614                       ouc->info_exclude_sha1);
2615        load_sha1_stat(&uc->ss_excludes_file, &ouc->excludes_file_stat,
2616                       ouc->excludes_file_sha1);
2617        uc->dir_flags = get_be32(&ouc->dir_flags);
2618        uc->exclude_per_dir = xstrdup(ouc->exclude_per_dir);
2619        /* NUL after exclude_per_dir is covered by sizeof(*ouc) */
2620        next += ouc_size(strlen(ouc->exclude_per_dir));
2621        if (next >= end)
2622                goto done2;
2623
2624        len = decode_varint(&next);
2625        if (next > end || len == 0)
2626                goto done2;
2627
2628        rd.valid      = ewah_new();
2629        rd.check_only = ewah_new();
2630        rd.sha1_valid = ewah_new();
2631        rd.data       = next;
2632        rd.end        = end;
2633        rd.index      = 0;
2634        rd.ucd        = xmalloc(sizeof(*rd.ucd) * len);
2635
2636        if (read_one_dir(&uc->root, &rd) || rd.index != len)
2637                goto done;
2638
2639        next = rd.data;
2640        len = ewah_read_mmap(rd.valid, next, end - next);
2641        if (len < 0)
2642                goto done;
2643
2644        next += len;
2645        len = ewah_read_mmap(rd.check_only, next, end - next);
2646        if (len < 0)
2647                goto done;
2648
2649        next += len;
2650        len = ewah_read_mmap(rd.sha1_valid, next, end - next);
2651        if (len < 0)
2652                goto done;
2653
2654        ewah_each_bit(rd.check_only, set_check_only, &rd);
2655        rd.data = next + len;
2656        ewah_each_bit(rd.valid, read_stat, &rd);
2657        ewah_each_bit(rd.sha1_valid, read_sha1, &rd);
2658        next = rd.data;
2659
2660done:
2661        free(rd.ucd);
2662        ewah_free(rd.valid);
2663        ewah_free(rd.check_only);
2664        ewah_free(rd.sha1_valid);
2665done2:
2666        if (next != end) {
2667                free_untracked_cache(uc);
2668                uc = NULL;
2669        }
2670        return uc;
2671}
2672
2673static void invalidate_one_directory(struct untracked_cache *uc,
2674                                     struct untracked_cache_dir *ucd)
2675{
2676        uc->dir_invalidated++;
2677        ucd->valid = 0;
2678        ucd->untracked_nr = 0;
2679}
2680
2681/*
2682 * Normally when an entry is added or removed from a directory,
2683 * invalidating that directory is enough. No need to touch its
2684 * ancestors. When a directory is shown as "foo/bar/" in git-status
2685 * however, deleting or adding an entry may have cascading effect.
2686 *
2687 * Say the "foo/bar/file" has become untracked, we need to tell the
2688 * untracked_cache_dir of "foo" that "bar/" is not an untracked
2689 * directory any more (because "bar" is managed by foo as an untracked
2690 * "file").
2691 *
2692 * Similarly, if "foo/bar/file" moves from untracked to tracked and it
2693 * was the last untracked entry in the entire "foo", we should show
2694 * "foo/" instead. Which means we have to invalidate past "bar" up to
2695 * "foo".
2696 *
2697 * This function traverses all directories from root to leaf. If there
2698 * is a chance of one of the above cases happening, we invalidate back
2699 * to root. Otherwise we just invalidate the leaf. There may be a more
2700 * sophisticated way than checking for SHOW_OTHER_DIRECTORIES to
2701 * detect these cases and avoid unnecessary invalidation, for example,
2702 * checking for the untracked entry named "bar/" in "foo", but for now
2703 * stick to something safe and simple.
2704 */
2705static int invalidate_one_component(struct untracked_cache *uc,
2706                                    struct untracked_cache_dir *dir,
2707                                    const char *path, int len)
2708{
2709        const char *rest = strchr(path, '/');
2710
2711        if (rest) {
2712                int component_len = rest - path;
2713                struct untracked_cache_dir *d =
2714                        lookup_untracked(uc, dir, path, component_len);
2715                int ret =
2716                        invalidate_one_component(uc, d, rest + 1,
2717                                                 len - (component_len + 1));
2718                if (ret)
2719                        invalidate_one_directory(uc, dir);
2720                return ret;
2721        }
2722
2723        invalidate_one_directory(uc, dir);
2724        return uc->dir_flags & DIR_SHOW_OTHER_DIRECTORIES;
2725}
2726
2727void untracked_cache_invalidate_path(struct index_state *istate,
2728                                     const char *path)
2729{
2730        if (!istate->untracked || !istate->untracked->root)
2731                return;
2732        invalidate_one_component(istate->untracked, istate->untracked->root,
2733                                 path, strlen(path));
2734}
2735
2736void untracked_cache_remove_from_index(struct index_state *istate,
2737                                       const char *path)
2738{
2739        untracked_cache_invalidate_path(istate, path);
2740}
2741
2742void untracked_cache_add_to_index(struct index_state *istate,
2743                                  const char *path)
2744{
2745        untracked_cache_invalidate_path(istate, path);
2746}