git.oblomov.eu Git - git/blob - dir.c

   1 /*
   2  * This handles recursive filename detection with exclude
   3  * files, index knowledge etc..
   4  *
   5  * Copyright (C) Linus Torvalds, 2005-2006
   6  *               Junio Hamano, 2005-2006
   7  */
   8 #include "cache.h"
   9 #include "dir.h"
  10 #include "refs.h"
  11
  12 struct path_simplify {
  13         int len;
  14         const char *path;
  15 };
  16
  17 static int read_directory_recursive(struct dir_struct *dir, const char *path, int len,
  18         int check_only, const struct path_simplify *simplify);
  19 static int get_dtype(struct dirent *de, const char *path, int len);
  20
  21 /* helper string functions with support for the ignore_case flag */
  22 int strcmp_icase(const char *a, const char *b)
  23 {
  24         return ignore_case ? strcasecmp(a, b) : strcmp(a, b);
  25 }
  26
  27 int strncmp_icase(const char *a, const char *b, size_t count)
  28 {
  29         return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);
  30 }
  31
  32 int fnmatch_icase(const char *pattern, const char *string, int flags)
  33 {
  34         return fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));
  35 }
  36
  37 size_t common_prefix_len(const char **pathspec)
  38 {
  39         const char *n, *first;
  40         size_t max = 0;
  41
  42         if (!pathspec)
  43                 return max;
  44
  45         first = *pathspec;
  46         while ((n = *pathspec++)) {
  47                 size_t i, len = 0;
  48                 for (i = 0; first == n || i < max; i++) {
  49                         char c = n[i];
  50                         if (!c || c != first[i] || is_glob_special(c))
  51                                 break;
  52                         if (c == '/')
  53                                 len = i + 1;
  54                 }
  55                 if (first == n || len < max) {
  56                         max = len;
  57                         if (!max)
  58                                 break;
  59                 }
  60         }
  61         return max;
  62 }
  63
  64 int fill_directory(struct dir_struct *dir, const char **pathspec)
  65 {
  66         const char *path;
  67         size_t len;
  68
  69         /*
  70          * Calculate common prefix for the pathspec, and
  71          * use that to optimize the directory walk
  72          */
  73         len = common_prefix_len(pathspec);
  74         path = "";
  75
  76         if (len)
  77                 path = xmemdupz(*pathspec, len);
  78
  79         /* Read the directory and prune it */
  80         read_directory(dir, path, len, pathspec);
  81         if (*path)
  82                 free((char *)path);
  83         return len;
  84 }
  85
  86 int within_depth(const char *name, int namelen,
  87                         int depth, int max_depth)
  88 {
  89         const char *cp = name, *cpe = name + namelen;
  90
  91         while (cp < cpe) {
  92                 if (*cp++ != '/')
  93                         continue;
  94                 depth++;
  95                 if (depth > max_depth)
  96                         return 0;
  97         }
  98         return 1;
  99 }
 100
 101 /*
 102  * Does 'match' match the given name?
 103  * A match is found if
 104  *
 105  * (1) the 'match' string is leading directory of 'name', or
 106  * (2) the 'match' string is a wildcard and matches 'name', or
 107  * (3) the 'match' string is exactly the same as 'name'.
 108  *
 109  * and the return value tells which case it was.
 110  *
 111  * It returns 0 when there is no match.
 112  */
 113 static int match_one(const char *match, const char *name, int namelen)
 114 {
 115         int matchlen;
 116
 117         /* If the match was just the prefix, we matched */
 118         if (!*match)
 119                 return MATCHED_RECURSIVELY;
 120
 121         if (ignore_case) {
 122                 for (;;) {
 123                         unsigned char c1 = tolower(*match);
 124                         unsigned char c2 = tolower(*name);
 125                         if (c1 == '\0' || is_glob_special(c1))
 126                                 break;
 127                         if (c1 != c2)
 128                                 return 0;
 129                         match++;
 130                         name++;
 131                         namelen--;
 132                 }
 133         } else {
 134                 for (;;) {
 135                         unsigned char c1 = *match;
 136                         unsigned char c2 = *name;
 137                         if (c1 == '\0' || is_glob_special(c1))
 138                                 break;
 139                         if (c1 != c2)
 140                                 return 0;
 141                         match++;
 142                         name++;
 143                         namelen--;
 144                 }
 145         }
 146
 147
 148         /*
 149          * If we don't match the matchstring exactly,
 150          * we need to match by fnmatch
 151          */
 152         matchlen = strlen(match);
 153         if (strncmp_icase(match, name, matchlen))
 154                 return !fnmatch_icase(match, name, 0) ? MATCHED_FNMATCH : 0;
 155
 156         if (namelen == matchlen)
 157                 return MATCHED_EXACTLY;
 158         if (match[matchlen-1] == '/' || name[matchlen] == '/')
 159                 return MATCHED_RECURSIVELY;
 160         return 0;
 161 }
 162
 163 /*
 164  * Given a name and a list of pathspecs, see if the name matches
 165  * any of the pathspecs.  The caller is also interested in seeing
 166  * all pathspec matches some names it calls this function with
 167  * (otherwise the user could have mistyped the unmatched pathspec),
 168  * and a mark is left in seen[] array for pathspec element that
 169  * actually matched anything.
 170  */
 171 int match_pathspec(const char **pathspec, const char *name, int namelen,
 172                 int prefix, char *seen)
 173 {
 174         int i, retval = 0;
 175
 176         if (!pathspec)
 177                 return 1;
 178
 179         name += prefix;
 180         namelen -= prefix;
 181
 182         for (i = 0; pathspec[i] != NULL; i++) {
 183                 int how;
 184                 const char *match = pathspec[i] + prefix;
 185                 if (seen && seen[i] == MATCHED_EXACTLY)
 186                         continue;
 187                 how = match_one(match, name, namelen);
 188                 if (how) {
 189                         if (retval < how)
 190                                 retval = how;
 191                         if (seen && seen[i] < how)
 192                                 seen[i] = how;
 193                 }
 194         }
 195         return retval;
 196 }
 197
 198 /*
 199  * Does 'match' match the given name?
 200  * A match is found if
 201  *
 202  * (1) the 'match' string is leading directory of 'name', or
 203  * (2) the 'match' string is a wildcard and matches 'name', or
 204  * (3) the 'match' string is exactly the same as 'name'.
 205  *
 206  * and the return value tells which case it was.
 207  *
 208  * It returns 0 when there is no match.
 209  */
 210 static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 211                                const char *name, int namelen)
 212 {
 213         /* name/namelen has prefix cut off by caller */
 214         const char *match = item->match + prefix;
 215         int matchlen = item->len - prefix;
 216
 217         /* If the match was just the prefix, we matched */
 218         if (!*match)
 219                 return MATCHED_RECURSIVELY;
 220
 221         if (matchlen <= namelen && !strncmp(match, name, matchlen)) {
 222                 if (matchlen == namelen)
 223                         return MATCHED_EXACTLY;
 224
 225                 if (match[matchlen-1] == '/' || name[matchlen] == '/')
 226                         return MATCHED_RECURSIVELY;
 227         }
 228
 229         if (item->use_wildcard && !fnmatch(match, name, 0))
 230                 return MATCHED_FNMATCH;
 231
 232         return 0;
 233 }
 234
 235 /*
 236  * Given a name and a list of pathspecs, see if the name matches
 237  * any of the pathspecs.  The caller is also interested in seeing
 238  * all pathspec matches some names it calls this function with
 239  * (otherwise the user could have mistyped the unmatched pathspec),
 240  * and a mark is left in seen[] array for pathspec element that
 241  * actually matched anything.
 242  */
 243 int match_pathspec_depth(const struct pathspec *ps,
 244                          const char *name, int namelen,
 245                          int prefix, char *seen)
 246 {
 247         int i, retval = 0;
 248
 249         if (!ps->nr) {
 250                 if (!ps->recursive || ps->max_depth == -1)
 251                         return MATCHED_RECURSIVELY;
 252
 253                 if (within_depth(name, namelen, 0, ps->max_depth))
 254                         return MATCHED_EXACTLY;
 255                 else
 256                         return 0;
 257         }
 258
 259         name += prefix;
 260         namelen -= prefix;
 261
 262         for (i = ps->nr - 1; i >= 0; i--) {
 263                 int how;
 264                 if (seen && seen[i] == MATCHED_EXACTLY)
 265                         continue;
 266                 how = match_pathspec_item(ps->items+i, prefix, name, namelen);
 267                 if (ps->recursive && ps->max_depth != -1 &&
 268                     how && how != MATCHED_FNMATCH) {
 269                         int len = ps->items[i].len;
 270                         if (name[len] == '/')
 271                                 len++;
 272                         if (within_depth(name+len, namelen-len, 0, ps->max_depth))
 273                                 how = MATCHED_EXACTLY;
 274                         else
 275                                 how = 0;
 276                 }
 277                 if (how) {
 278                         if (retval < how)
 279                                 retval = how;
 280                         if (seen && seen[i] < how)
 281                                 seen[i] = how;
 282                 }
 283         }
 284         return retval;
 285 }
 286
 287 static int no_wildcard(const char *string)
 288 {
 289         return string[strcspn(string, "*?[{\\")] == '\0';
 290 }
 291
 292 void add_exclude(const char *string, const char *base,
 293                  int baselen, struct exclude_list *which)
 294 {
 295         struct exclude *x;
 296         size_t len;
 297         int to_exclude = 1;
 298         int flags = 0;
 299
 300         if (*string == '!') {
 301                 to_exclude = 0;
 302                 string++;
 303         }
 304         len = strlen(string);
 305         if (len && string[len - 1] == '/') {
 306                 char *s;
 307                 x = xmalloc(sizeof(*x) + len);
 308                 s = (char *)(x+1);
 309                 memcpy(s, string, len - 1);
 310                 s[len - 1] = '\0';
 311                 string = s;
 312                 x->pattern = s;
 313                 flags = EXC_FLAG_MUSTBEDIR;
 314         } else {
 315                 x = xmalloc(sizeof(*x));
 316                 x->pattern = string;
 317         }
 318         x->to_exclude = to_exclude;
 319         x->patternlen = strlen(string);
 320         x->base = base;
 321         x->baselen = baselen;
 322         x->flags = flags;
 323         if (!strchr(string, '/'))
 324                 x->flags |= EXC_FLAG_NODIR;
 325         if (no_wildcard(string))
 326                 x->flags |= EXC_FLAG_NOWILDCARD;
 327         if (*string == '*' && no_wildcard(string+1))
 328                 x->flags |= EXC_FLAG_ENDSWITH;
 329         ALLOC_GROW(which->excludes, which->nr + 1, which->alloc);
 330         which->excludes[which->nr++] = x;
 331 }
 332
 333 static void *read_skip_worktree_file_from_index(const char *path, size_t *size)
 334 {
 335         int pos, len;
 336         unsigned long sz;
 337         enum object_type type;
 338         void *data;
 339         struct index_state *istate = &the_index;
 340
 341         len = strlen(path);
 342         pos = index_name_pos(istate, path, len);
 343         if (pos < 0)
 344                 return NULL;
 345         if (!ce_skip_worktree(istate->cache[pos]))
 346                 return NULL;
 347         data = read_sha1_file(istate->cache[pos]->sha1, &type, &sz);
 348         if (!data || type != OBJ_BLOB) {
 349                 free(data);
 350                 return NULL;
 351         }
 352         *size = xsize_t(sz);
 353         return data;
 354 }
 355
 356 void free_excludes(struct exclude_list *el)
 357 {
 358         int i;
 359
 360         for (i = 0; i < el->nr; i++)
 361                 free(el->excludes[i]);
 362         free(el->excludes);
 363
 364         el->nr = 0;
 365         el->excludes = NULL;
 366 }
 367
 368 int add_excludes_from_file_to_list(const char *fname,
 369                                    const char *base,
 370                                    int baselen,
 371                                    char **buf_p,
 372                                    struct exclude_list *which,
 373                                    int check_index)
 374 {
 375         struct stat st;
 376         int fd, i;
 377         size_t size = 0;
 378         char *buf, *entry;
 379
 380         fd = open(fname, O_RDONLY);
 381         if (fd < 0 || fstat(fd, &st) < 0) {
 382                 if (0 <= fd)
 383                         close(fd);
 384                 if (!check_index ||
 385                     (buf = read_skip_worktree_file_from_index(fname, &size)) == NULL)
 386                         return -1;
 387                 if (size == 0) {
 388                         free(buf);
 389                         return 0;
 390                 }
 391                 if (buf[size-1] != '\n') {
 392                         buf = xrealloc(buf, size+1);
 393                         buf[size++] = '\n';
 394                 }
 395         }
 396         else {
 397                 size = xsize_t(st.st_size);
 398                 if (size == 0) {
 399                         close(fd);
 400                         return 0;
 401                 }
 402                 buf = xmalloc(size+1);
 403                 if (read_in_full(fd, buf, size) != size) {
 404                         free(buf);
 405                         close(fd);
 406                         return -1;
 407                 }
 408                 buf[size++] = '\n';
 409                 close(fd);
 410         }
 411
 412         if (buf_p)
 413                 *buf_p = buf;
 414         entry = buf;
 415         for (i = 0; i < size; i++) {
 416                 if (buf[i] == '\n') {
 417                         if (entry != buf + i && entry[0] != '#') {
 418                                 buf[i - (i && buf[i-1] == '\r')] = 0;
 419                                 add_exclude(entry, base, baselen, which);
 420                         }
 421                         entry = buf + i + 1;
 422                 }
 423         }
 424         return 0;
 425 }
 426
 427 void add_excludes_from_file(struct dir_struct *dir, const char *fname)
 428 {
 429         if (add_excludes_from_file_to_list(fname, "", 0, NULL,
 430                                            &dir->exclude_list[EXC_FILE], 0) < 0)
 431                 die("cannot use %s as an exclude file", fname);
 432 }
 433
 434 static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
 435 {
 436         struct exclude_list *el;
 437         struct exclude_stack *stk = NULL;
 438         int current;
 439
 440         if ((!dir->exclude_per_dir) ||
 441             (baselen + strlen(dir->exclude_per_dir) >= PATH_MAX))
 442                 return; /* too long a path -- ignore */
 443
 444         /* Pop the ones that are not the prefix of the path being checked. */
 445         el = &dir->exclude_list[EXC_DIRS];
 446         while ((stk = dir->exclude_stack) != NULL) {
 447                 if (stk->baselen <= baselen &&
 448                     !strncmp(dir->basebuf, base, stk->baselen))
 449                         break;
 450                 dir->exclude_stack = stk->prev;
 451                 while (stk->exclude_ix < el->nr)
 452                         free(el->excludes[--el->nr]);
 453                 free(stk->filebuf);
 454                 free(stk);
 455         }
 456
 457         /* Read from the parent directories and push them down. */
 458         current = stk ? stk->baselen : -1;
 459         while (current < baselen) {
 460                 struct exclude_stack *stk = xcalloc(1, sizeof(*stk));
 461                 const char *cp;
 462
 463                 if (current < 0) {
 464                         cp = base;
 465                         current = 0;
 466                 }
 467                 else {
 468                         cp = strchr(base + current + 1, '/');
 469                         if (!cp)
 470                                 die("oops in prep_exclude");
 471                         cp++;
 472                 }
 473                 stk->prev = dir->exclude_stack;
 474                 stk->baselen = cp - base;
 475                 stk->exclude_ix = el->nr;
 476                 memcpy(dir->basebuf + current, base + current,
 477                        stk->baselen - current);
 478                 strcpy(dir->basebuf + stk->baselen, dir->exclude_per_dir);
 479                 add_excludes_from_file_to_list(dir->basebuf,
 480                                                dir->basebuf, stk->baselen,
 481                                                &stk->filebuf, el, 1);
 482                 dir->exclude_stack = stk;
 483                 current = stk->baselen;
 484         }
 485         dir->basebuf[baselen] = '\0';
 486 }
 487
 488 /* Scan the list and let the last match determine the fate.
 489  * Return 1 for exclude, 0 for include and -1 for undecided.
 490  */
 491 int excluded_from_list(const char *pathname,
 492                        int pathlen, const char *basename, int *dtype,
 493                        struct exclude_list *el)
 494 {
 495         int i;
 496
 497         if (el->nr) {
 498                 for (i = el->nr - 1; 0 <= i; i--) {
 499                         struct exclude *x = el->excludes[i];
 500                         const char *exclude = x->pattern;
 501                         int to_exclude = x->to_exclude;
 502
 503                         if (x->flags & EXC_FLAG_MUSTBEDIR) {
 504                                 if (*dtype == DT_UNKNOWN)
 505                                         *dtype = get_dtype(NULL, pathname, pathlen);
 506                                 if (*dtype != DT_DIR)
 507                                         continue;
 508                         }
 509
 510                         if (x->flags & EXC_FLAG_NODIR) {
 511                                 /* match basename */
 512                                 if (x->flags & EXC_FLAG_NOWILDCARD) {
 513                                         if (!strcmp_icase(exclude, basename))
 514                                                 return to_exclude;
 515                                 } else if (x->flags & EXC_FLAG_ENDSWITH) {
 516                                         if (x->patternlen - 1 <= pathlen &&
 517                                             !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1))
 518                                                 return to_exclude;
 519                                 } else {
 520                                         if (fnmatch_icase(exclude, basename, 0) == 0)
 521                                                 return to_exclude;
 522                                 }
 523                         }
 524                         else {
 525                                 /* match with FNM_PATHNAME:
 526                                  * exclude has base (baselen long) implicitly
 527                                  * in front of it.
 528                                  */
 529                                 int baselen = x->baselen;
 530                                 if (*exclude == '/')
 531                                         exclude++;
 532
 533                                 if (pathlen < baselen ||
 534                                     (baselen && pathname[baselen-1] != '/') ||
 535                                     strncmp_icase(pathname, x->base, baselen))
 536                                     continue;
 537
 538                                 if (x->flags & EXC_FLAG_NOWILDCARD) {
 539                                         if (!strcmp_icase(exclude, pathname + baselen))
 540                                                 return to_exclude;
 541                                 } else {
 542                                         if (fnmatch_icase(exclude, pathname+baselen,
 543                                                     FNM_PATHNAME) == 0)
 544                                             return to_exclude;
 545                                 }
 546                         }
 547                 }
 548         }
 549         return -1; /* undecided */
 550 }
 551
 552 int excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
 553 {
 554         int pathlen = strlen(pathname);
 555         int st;
 556         const char *basename = strrchr(pathname, '/');
 557         basename = (basename) ? basename+1 : pathname;
 558
 559         prep_exclude(dir, pathname, basename-pathname);
 560         for (st = EXC_CMDL; st <= EXC_FILE; st++) {
 561                 switch (excluded_from_list(pathname, pathlen, basename,
 562                                            dtype_p, &dir->exclude_list[st])) {
 563                 case 0:
 564                         return 0;
 565                 case 1:
 566                         return 1;
 567                 }
 568         }
 569         return 0;
 570 }
 571
 572 static struct dir_entry *dir_entry_new(const char *pathname, int len)
 573 {
 574         struct dir_entry *ent;
 575
 576         ent = xmalloc(sizeof(*ent) + len + 1);
 577         ent->len = len;
 578         memcpy(ent->name, pathname, len);
 579         ent->name[len] = 0;
 580         return ent;
 581 }
 582
 583 static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
 584 {
 585         if (cache_name_exists(pathname, len, ignore_case))
 586                 return NULL;
 587
 588         ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
 589         return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
 590 }
 591
 592 struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len)
 593 {
 594         if (!cache_name_is_other(pathname, len))
 595                 return NULL;
 596
 597         ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc);
 598         return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len);
 599 }
 600
 601 enum exist_status {
 602         index_nonexistent = 0,
 603         index_directory,
 604         index_gitdir
 605 };
 606
 607 /*
 608  * Do not use the alphabetically stored index to look up
 609  * the directory name; instead, use the case insensitive
 610  * name hash.
 611  */
 612 static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)
 613 {
 614         struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);
 615         unsigned char endchar;
 616
 617         if (!ce)
 618                 return index_nonexistent;
 619         endchar = ce->name[len];
 620
 621         /*
 622          * The cache_entry structure returned will contain this dirname
 623          * and possibly additional path components.
 624          */
 625         if (endchar == '/')
 626                 return index_directory;
 627
 628         /*
 629          * If there are no additional path components, then this cache_entry
 630          * represents a submodule.  Submodules, despite being directories,
 631          * are stored in the cache without a closing slash.
 632          */
 633         if (!endchar && S_ISGITLINK(ce->ce_mode))
 634                 return index_gitdir;
 635
 636         /* This should never be hit, but it exists just in case. */
 637         return index_nonexistent;
 638 }
 639
 640 /*
 641  * The index sorts alphabetically by entry name, which
 642  * means that a gitlink sorts as '\0' at the end, while
 643  * a directory (which is defined not as an entry, but as
 644  * the files it contains) will sort with the '/' at the
 645  * end.
 646  */
 647 static enum exist_status directory_exists_in_index(const char *dirname, int len)
 648 {
 649         int pos;
 650
 651         if (ignore_case)
 652                 return directory_exists_in_index_icase(dirname, len);
 653
 654         pos = cache_name_pos(dirname, len);
 655         if (pos < 0)
 656                 pos = -pos-1;
 657         while (pos < active_nr) {
 658                 struct cache_entry *ce = active_cache[pos++];
 659                 unsigned char endchar;
 660
 661                 if (strncmp(ce->name, dirname, len))
 662                         break;
 663                 endchar = ce->name[len];
 664                 if (endchar > '/')
 665                         break;
 666                 if (endchar == '/')
 667                         return index_directory;
 668                 if (!endchar && S_ISGITLINK(ce->ce_mode))
 669                         return index_gitdir;
 670         }
 671         return index_nonexistent;
 672 }
 673
 674 /*
 675  * When we find a directory when traversing the filesystem, we
 676  * have three distinct cases:
 677  *
 678  *  - ignore it
 679  *  - see it as a directory
 680  *  - recurse into it
 681  *
 682  * and which one we choose depends on a combination of existing
 683  * git index contents and the flags passed into the directory
 684  * traversal routine.
 685  *
 686  * Case 1: If we *already* have entries in the index under that
 687  * directory name, we always recurse into the directory to see
 688  * all the files.
 689  *
 690  * Case 2: If we *already* have that directory name as a gitlink,
 691  * we always continue to see it as a gitlink, regardless of whether
 692  * there is an actual git directory there or not (it might not
 693  * be checked out as a subproject!)
 694  *
 695  * Case 3: if we didn't have it in the index previously, we
 696  * have a few sub-cases:
 697  *
 698  *  (a) if "show_other_directories" is true, we show it as
 699  *      just a directory, unless "hide_empty_directories" is
 700  *      also true and the directory is empty, in which case
 701  *      we just ignore it entirely.
 702  *  (b) if it looks like a git directory, and we don't have
 703  *      'no_gitlinks' set we treat it as a gitlink, and show it
 704  *      as a directory.
 705  *  (c) otherwise, we recurse into it.
 706  */
 707 enum directory_treatment {
 708         show_directory,
 709         ignore_directory,
 710         recurse_into_directory
 711 };
 712
 713 static enum directory_treatment treat_directory(struct dir_struct *dir,
 714         const char *dirname, int len,
 715         const struct path_simplify *simplify)
 716 {
 717         /* The "len-1" is to strip the final '/' */
 718         switch (directory_exists_in_index(dirname, len-1)) {
 719         case index_directory:
 720                 return recurse_into_directory;
 721
 722         case index_gitdir:
 723                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
 724                         return ignore_directory;
 725                 return show_directory;
 726
 727         case index_nonexistent:
 728                 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
 729                         break;
 730                 if (!(dir->flags & DIR_NO_GITLINKS)) {
 731                         unsigned char sha1[20];
 732                         if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)
 733                                 return show_directory;
 734                 }
 735                 return recurse_into_directory;
 736         }
 737
 738         /* This is the "show_other_directories" case */
 739         if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
 740                 return show_directory;
 741         if (!read_directory_recursive(dir, dirname, len, 1, simplify))
 742                 return ignore_directory;
 743         return show_directory;
 744 }
 745
 746 /*
 747  * This is an inexact early pruning of any recursive directory
 748  * reading - if the path cannot possibly be in the pathspec,
 749  * return true, and we'll skip it early.
 750  */
 751 static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)
 752 {
 753         if (simplify) {
 754                 for (;;) {
 755                         const char *match = simplify->path;
 756                         int len = simplify->len;
 757
 758                         if (!match)
 759                                 break;
 760                         if (len > pathlen)
 761                                 len = pathlen;
 762                         if (!memcmp(path, match, len))
 763                                 return 0;
 764                         simplify++;
 765                 }
 766                 return 1;
 767         }
 768         return 0;
 769 }
 770
 771 /*
 772  * This function tells us whether an excluded path matches a
 773  * list of "interesting" pathspecs. That is, whether a path matched
 774  * by any of the pathspecs could possibly be ignored by excluding
 775  * the specified path. This can happen if:
 776  *
 777  *   1. the path is mentioned explicitly in the pathspec
 778  *
 779  *   2. the path is a directory prefix of some element in the
 780  *      pathspec
 781  */
 782 static int exclude_matches_pathspec(const char *path, int len,
 783                 const struct path_simplify *simplify)
 784 {
 785         if (simplify) {
 786                 for (; simplify->path; simplify++) {
 787                         if (len == simplify->len
 788                             && !memcmp(path, simplify->path, len))
 789                                 return 1;
 790                         if (len < simplify->len
 791                             && simplify->path[len] == '/'
 792                             && !memcmp(path, simplify->path, len))
 793                                 return 1;
 794                 }
 795         }
 796         return 0;
 797 }
 798
 799 static int get_index_dtype(const char *path, int len)
 800 {
 801         int pos;
 802         struct cache_entry *ce;
 803
 804         ce = cache_name_exists(path, len, 0);
 805         if (ce) {
 806                 if (!ce_uptodate(ce))
 807                         return DT_UNKNOWN;
 808                 if (S_ISGITLINK(ce->ce_mode))
 809                         return DT_DIR;
 810                 /*
 811                  * Nobody actually cares about the
 812                  * difference between DT_LNK and DT_REG
 813                  */
 814                 return DT_REG;
 815         }
 816
 817         /* Try to look it up as a directory */
 818         pos = cache_name_pos(path, len);
 819         if (pos >= 0)
 820                 return DT_UNKNOWN;
 821         pos = -pos-1;
 822         while (pos < active_nr) {
 823                 ce = active_cache[pos++];
 824                 if (strncmp(ce->name, path, len))
 825                         break;
 826                 if (ce->name[len] > '/')
 827                         break;
 828                 if (ce->name[len] < '/')
 829                         continue;
 830                 if (!ce_uptodate(ce))
 831                         break;  /* continue? */
 832                 return DT_DIR;
 833         }
 834         return DT_UNKNOWN;
 835 }
 836
 837 static int get_dtype(struct dirent *de, const char *path, int len)
 838 {
 839         int dtype = de ? DTYPE(de) : DT_UNKNOWN;
 840         struct stat st;
 841
 842         if (dtype != DT_UNKNOWN)
 843                 return dtype;
 844         dtype = get_index_dtype(path, len);
 845         if (dtype != DT_UNKNOWN)
 846                 return dtype;
 847         if (lstat(path, &st))
 848                 return dtype;
 849         if (S_ISREG(st.st_mode))
 850                 return DT_REG;
 851         if (S_ISDIR(st.st_mode))
 852                 return DT_DIR;
 853         if (S_ISLNK(st.st_mode))
 854                 return DT_LNK;
 855         return dtype;
 856 }
 857
 858 enum path_treatment {
 859         path_ignored,
 860         path_handled,
 861         path_recurse
 862 };
 863
 864 static enum path_treatment treat_one_path(struct dir_struct *dir,
 865                                           char *path, int *len,
 866                                           const struct path_simplify *simplify,
 867                                           int dtype, struct dirent *de)
 868 {
 869         int exclude = excluded(dir, path, &dtype);
 870         if (exclude && (dir->flags & DIR_COLLECT_IGNORED)
 871             && exclude_matches_pathspec(path, *len, simplify))
 872                 dir_add_ignored(dir, path, *len);
 873
 874         /*
 875          * Excluded? If we don't explicitly want to show
 876          * ignored files, ignore it
 877          */
 878         if (exclude && !(dir->flags & DIR_SHOW_IGNORED))
 879                 return path_ignored;
 880
 881         if (dtype == DT_UNKNOWN)
 882                 dtype = get_dtype(de, path, *len);
 883
 884         /*
 885          * Do we want to see just the ignored files?
 886          * We still need to recurse into directories,
 887          * even if we don't ignore them, since the
 888          * directory may contain files that we do..
 889          */
 890         if (!exclude && (dir->flags & DIR_SHOW_IGNORED)) {
 891                 if (dtype != DT_DIR)
 892                         return path_ignored;
 893         }
 894
 895         switch (dtype) {
 896         default:
 897                 return path_ignored;
 898         case DT_DIR:
 899                 memcpy(path + *len, "/", 2);
 900                 (*len)++;
 901                 switch (treat_directory(dir, path, *len, simplify)) {
 902                 case show_directory:
 903                         if (exclude != !!(dir->flags
 904                                           & DIR_SHOW_IGNORED))
 905                                 return path_ignored;
 906                         break;
 907                 case recurse_into_directory:
 908                         return path_recurse;
 909                 case ignore_directory:
 910                         return path_ignored;
 911                 }
 912                 break;
 913         case DT_REG:
 914         case DT_LNK:
 915                 break;
 916         }
 917         return path_handled;
 918 }
 919
 920 static enum path_treatment treat_path(struct dir_struct *dir,
 921                                       struct dirent *de,
 922                                       char *path, int path_max,
 923                                       int baselen,
 924                                       const struct path_simplify *simplify,
 925                                       int *len)
 926 {
 927         int dtype;
 928
 929         if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
 930                 return path_ignored;
 931         *len = strlen(de->d_name);
 932         /* Ignore overly long pathnames! */
 933         if (*len + baselen + 8 > path_max)
 934                 return path_ignored;
 935         memcpy(path + baselen, de->d_name, *len + 1);
 936         *len += baselen;
 937         if (simplify_away(path, *len, simplify))
 938                 return path_ignored;
 939
 940         dtype = DTYPE(de);
 941         return treat_one_path(dir, path, len, simplify, dtype, de);
 942 }
 943
 944 /*
 945  * Read a directory tree. We currently ignore anything but
 946  * directories, regular files and symlinks. That's because git
 947  * doesn't handle them at all yet. Maybe that will change some
 948  * day.
 949  *
 950  * Also, we ignore the name ".git" (even if it is not a directory).
 951  * That likely will not change.
 952  */
 953 static int read_directory_recursive(struct dir_struct *dir,
 954                                     const char *base, int baselen,
 955                                     int check_only,
 956                                     const struct path_simplify *simplify)
 957 {
 958         DIR *fdir = opendir(*base ? base : ".");
 959         int contents = 0;
 960
 961         if (fdir) {
 962                 struct dirent *de;
 963                 char path[PATH_MAX + 1];
 964                 memcpy(path, base, baselen);
 965
 966                 while ((de = readdir(fdir)) != NULL) {
 967                         int len;
 968                         switch (treat_path(dir, de, path, sizeof(path),
 969                                            baselen, simplify, &len)) {
 970                         case path_recurse:
 971                                 contents += read_directory_recursive
 972                                         (dir, path, len, 0, simplify);
 973                                 continue;
 974                         case path_ignored:
 975                                 continue;
 976                         case path_handled:
 977                                 break;
 978                         }
 979                         contents++;
 980                         if (check_only)
 981                                 goto exit_early;
 982                         else
 983                                 dir_add_name(dir, path, len);
 984                 }
 985 exit_early:
 986                 closedir(fdir);
 987         }
 988
 989         return contents;
 990 }
 991
 992 static int cmp_name(const void *p1, const void *p2)
 993 {
 994         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
 995         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
 996
 997         return cache_name_compare(e1->name, e1->len,
 998                                   e2->name, e2->len);
 999 }
1000
1001 /*
1002  * Return the length of the "simple" part of a path match limiter.
1003  */
1004 static int simple_length(const char *match)
1005 {
1006         int len = -1;
1007
1008         for (;;) {
1009                 unsigned char c = *match++;
1010                 len++;
1011                 if (c == '\0' || is_glob_special(c))
1012                         return len;
1013         }
1014 }
1015
1016 static struct path_simplify *create_simplify(const char **pathspec)
1017 {
1018         int nr, alloc = 0;
1019         struct path_simplify *simplify = NULL;
1020
1021         if (!pathspec)
1022                 return NULL;
1023
1024         for (nr = 0 ; ; nr++) {
1025                 const char *match;
1026                 if (nr >= alloc) {
1027                         alloc = alloc_nr(alloc);
1028                         simplify = xrealloc(simplify, alloc * sizeof(*simplify));
1029                 }
1030                 match = *pathspec++;
1031                 if (!match)
1032                         break;
1033                 simplify[nr].path = match;
1034                 simplify[nr].len = simple_length(match);
1035         }
1036         simplify[nr].path = NULL;
1037         simplify[nr].len = 0;
1038         return simplify;
1039 }
1040
1041 static void free_simplify(struct path_simplify *simplify)
1042 {
1043         free(simplify);
1044 }
1045
1046 static int treat_leading_path(struct dir_struct *dir,
1047                               const char *path, int len,
1048                               const struct path_simplify *simplify)
1049 {
1050         char pathbuf[PATH_MAX];
1051         int baselen, blen;
1052         const char *cp;
1053
1054         while (len && path[len - 1] == '/')
1055                 len--;
1056         if (!len)
1057                 return 1;
1058         baselen = 0;
1059         while (1) {
1060                 cp = path + baselen + !!baselen;
1061                 cp = memchr(cp, '/', path + len - cp);
1062                 if (!cp)
1063                         baselen = len;
1064                 else
1065                         baselen = cp - path;
1066                 memcpy(pathbuf, path, baselen);
1067                 pathbuf[baselen] = '\0';
1068                 if (!is_directory(pathbuf))
1069                         return 0;
1070                 if (simplify_away(pathbuf, baselen, simplify))
1071                         return 0;
1072                 blen = baselen;
1073                 if (treat_one_path(dir, pathbuf, &blen, simplify,
1074                                    DT_DIR, NULL) == path_ignored)
1075                         return 0; /* do not recurse into it */
1076                 if (len <= baselen)
1077                         return 1; /* finished checking */
1078         }
1079 }
1080
1081 int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
1082 {
1083         struct path_simplify *simplify;
1084
1085         if (has_symlink_leading_path(path, len))
1086                 return dir->nr;
1087
1088         simplify = create_simplify(pathspec);
1089         if (!len || treat_leading_path(dir, path, len, simplify))
1090                 read_directory_recursive(dir, path, len, 0, simplify);
1091         free_simplify(simplify);
1092         qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
1093         qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);
1094         return dir->nr;
1095 }
1096
1097 int file_exists(const char *f)
1098 {
1099         struct stat sb;
1100         return lstat(f, &sb) == 0;
1101 }
1102
1103 /*
1104  * Given two normalized paths (a trailing slash is ok), if subdir is
1105  * outside dir, return -1.  Otherwise return the offset in subdir that
1106  * can be used as relative path to dir.
1107  */
1108 int dir_inside_of(const char *subdir, const char *dir)
1109 {
1110         int offset = 0;
1111
1112         assert(dir && subdir && *dir && *subdir);
1113
1114         while (*dir && *subdir && *dir == *subdir) {
1115                 dir++;
1116                 subdir++;
1117                 offset++;
1118         }
1119
1120         /* hel[p]/me vs hel[l]/yeah */
1121         if (*dir && *subdir)
1122                 return -1;
1123
1124         if (!*subdir)
1125                 return !*dir ? offset : -1; /* same dir */
1126
1127         /* foo/[b]ar vs foo/[] */
1128         if (is_dir_sep(dir[-1]))
1129                 return is_dir_sep(subdir[-1]) ? offset : -1;
1130
1131         /* foo[/]bar vs foo[] */
1132         return is_dir_sep(*subdir) ? offset + 1 : -1;
1133 }
1134
1135 int is_inside_dir(const char *dir)
1136 {
1137         char cwd[PATH_MAX];
1138         if (!dir)
1139                 return 0;
1140         if (!getcwd(cwd, sizeof(cwd)))
1141                 die_errno("can't find the current directory");
1142         return dir_inside_of(cwd, dir) >= 0;
1143 }
1144
1145 int is_empty_dir(const char *path)
1146 {
1147         DIR *dir = opendir(path);
1148         struct dirent *e;
1149         int ret = 1;
1150
1151         if (!dir)
1152                 return 0;
1153
1154         while ((e = readdir(dir)) != NULL)
1155                 if (!is_dot_or_dotdot(e->d_name)) {
1156                         ret = 0;
1157                         break;
1158                 }
1159
1160         closedir(dir);
1161         return ret;
1162 }
1163
1164 int remove_dir_recursively(struct strbuf *path, int flag)
1165 {
1166         DIR *dir;
1167         struct dirent *e;
1168         int ret = 0, original_len = path->len, len;
1169         int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);
1170         unsigned char submodule_head[20];
1171
1172         if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
1173             !resolve_gitlink_ref(path->buf, "HEAD", submodule_head))
1174                 /* Do not descend and nuke a nested git work tree. */
1175                 return 0;
1176
1177         dir = opendir(path->buf);
1178         if (!dir)
1179                 return rmdir(path->buf);
1180         if (path->buf[original_len - 1] != '/')
1181                 strbuf_addch(path, '/');
1182
1183         len = path->len;
1184         while ((e = readdir(dir)) != NULL) {
1185                 struct stat st;
1186                 if (is_dot_or_dotdot(e->d_name))
1187                         continue;
1188
1189                 strbuf_setlen(path, len);
1190                 strbuf_addstr(path, e->d_name);
1191                 if (lstat(path->buf, &st))
1192                         ; /* fall thru */
1193                 else if (S_ISDIR(st.st_mode)) {
1194                         if (!remove_dir_recursively(path, only_empty))
1195                                 continue; /* happy */
1196                 } else if (!only_empty && !unlink(path->buf))
1197                         continue; /* happy, too */
1198
1199                 /* path too long, stat fails, or non-directory still exists */
1200                 ret = -1;
1201                 break;
1202         }
1203         closedir(dir);
1204
1205         strbuf_setlen(path, original_len);
1206         if (!ret)
1207                 ret = rmdir(path->buf);
1208         return ret;
1209 }
1210
1211 void setup_standard_excludes(struct dir_struct *dir)
1212 {
1213         const char *path;
1214
1215         dir->exclude_per_dir = ".gitignore";
1216         path = git_path("info/exclude");
1217         if (!access(path, R_OK))
1218                 add_excludes_from_file(dir, path);
1219         if (excludes_file && !access(excludes_file, R_OK))
1220                 add_excludes_from_file(dir, excludes_file);
1221 }
1222
1223 int remove_path(const char *name)
1224 {
1225         char *slash;
1226
1227         if (unlink(name) && errno != ENOENT)
1228                 return -1;
1229
1230         slash = strrchr(name, '/');
1231         if (slash) {
1232                 char *dirs = xstrdup(name);
1233                 slash = dirs + (slash - name);
1234                 do {
1235                         *slash = '\0';
1236                 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));
1237                 free(dirs);
1238         }
1239         return 0;
1240 }
1241
1242 static int pathspec_item_cmp(const void *a_, const void *b_)
1243 {
1244         struct pathspec_item *a, *b;
1245
1246         a = (struct pathspec_item *)a_;
1247         b = (struct pathspec_item *)b_;
1248         return strcmp(a->match, b->match);
1249 }
1250
1251 int init_pathspec(struct pathspec *pathspec, const char **paths)
1252 {
1253         const char **p = paths;
1254         int i;
1255
1256         memset(pathspec, 0, sizeof(*pathspec));
1257         if (!p)
1258                 return 0;
1259         while (*p)
1260                 p++;
1261         pathspec->raw = paths;
1262         pathspec->nr = p - paths;
1263         if (!pathspec->nr)
1264                 return 0;
1265
1266         pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
1267         for (i = 0; i < pathspec->nr; i++) {
1268                 struct pathspec_item *item = pathspec->items+i;
1269                 const char *path = paths[i];
1270
1271                 item->match = path;
1272                 item->len = strlen(path);
1273                 item->use_wildcard = !no_wildcard(path);
1274                 if (item->use_wildcard)
1275                         pathspec->has_wildcard = 1;
1276         }
1277
1278         qsort(pathspec->items, pathspec->nr,
1279               sizeof(struct pathspec_item), pathspec_item_cmp);
1280
1281         return 0;
1282 }
1283
1284 void free_pathspec(struct pathspec *pathspec)
1285 {
1286         free(pathspec->items);
1287         pathspec->items = NULL;
1288 }