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