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