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