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 16struct path_simplify { 17 int len; 18 const char *path; 19}; 20 21/* 22 * Tells read_directory_recursive how a file or directory should be treated. 23 * Values are ordered by significance, e.g. if a directory contains both 24 * excluded and untracked files, it is listed as untracked because 25 * path_untracked > path_excluded. 26 */ 27enum path_treatment { 28 path_none = 0, 29 path_recurse, 30 path_excluded, 31 path_untracked 32}; 33 34static enum path_treatment read_directory_recursive(struct dir_struct *dir, 35 const char *path, int len, 36 int check_only, const struct path_simplify *simplify); 37static int get_dtype(struct dirent *de, const char *path, int len); 38 39/* helper string functions with support for the ignore_case flag */ 40int strcmp_icase(const char *a, const char *b) 41{ 42 return ignore_case ? strcasecmp(a, b) : strcmp(a, b); 43} 44 45int strncmp_icase(const char *a, const char *b, size_t count) 46{ 47 return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count); 48} 49 50int fnmatch_icase(const char *pattern, const char *string, int flags) 51{ 52 return fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0)); 53} 54 55inline int git_fnmatch(const char *pattern, const char *string, 56 int flags, int prefix) 57{ 58 int fnm_flags = 0; 59 if (flags & GFNM_PATHNAME) 60 fnm_flags |= FNM_PATHNAME; 61 if (prefix > 0) { 62 if (strncmp(pattern, string, prefix)) 63 return FNM_NOMATCH; 64 pattern += prefix; 65 string += prefix; 66 } 67 if (flags & GFNM_ONESTAR) { 68 int pattern_len = strlen(++pattern); 69 int string_len = strlen(string); 70 return string_len < pattern_len || 71 strcmp(pattern, 72 string + string_len - pattern_len); 73 } 74 return fnmatch(pattern, string, fnm_flags); 75} 76 77static int fnmatch_icase_mem(const char *pattern, int patternlen, 78 const char *string, int stringlen, 79 int flags) 80{ 81 int match_status; 82 struct strbuf pat_buf = STRBUF_INIT; 83 struct strbuf str_buf = STRBUF_INIT; 84 const char *use_pat = pattern; 85 const char *use_str = string; 86 87 if (pattern[patternlen]) { 88 strbuf_add(&pat_buf, pattern, patternlen); 89 use_pat = pat_buf.buf; 90 } 91 if (string[stringlen]) { 92 strbuf_add(&str_buf, string, stringlen); 93 use_str = str_buf.buf; 94 } 95 96 if (ignore_case) 97 flags |= WM_CASEFOLD; 98 match_status = wildmatch(use_pat, use_str, flags, NULL); 99 100 strbuf_release(&pat_buf); 101 strbuf_release(&str_buf); 102 103 return match_status; 104} 105 106static size_t common_prefix_len(const struct pathspec *pathspec) 107{ 108 int n; 109 size_t max = 0; 110 111 GUARD_PATHSPEC(pathspec, PATHSPEC_FROMTOP | PATHSPEC_MAXDEPTH); 112 113 for (n = 0; n < pathspec->nr; n++) { 114 size_t i = 0, len = 0; 115 while (i < pathspec->items[n].nowildcard_len && 116 (n == 0 || i < max)) { 117 char c = pathspec->items[n].match[i]; 118 if (c != pathspec->items[0].match[i]) 119 break; 120 if (c == '/') 121 len = i + 1; 122 i++; 123 } 124 if (n == 0 || len < max) { 125 max = len; 126 if (!max) 127 break; 128 } 129 } 130 return max; 131} 132 133/* 134 * Returns a copy of the longest leading path common among all 135 * pathspecs. 136 */ 137char *common_prefix(const struct pathspec *pathspec) 138{ 139 unsigned long len = common_prefix_len(pathspec); 140 141 return len ? xmemdupz(pathspec->items[0].match, len) : NULL; 142} 143 144int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec) 145{ 146 size_t len; 147 148 /* 149 * Calculate common prefix for the pathspec, and 150 * use that to optimize the directory walk 151 */ 152 len = common_prefix_len(pathspec); 153 154 /* Read the directory and prune it */ 155 read_directory(dir, pathspec->nr ? pathspec->raw[0] : "", len, pathspec); 156 return len; 157} 158 159int within_depth(const char *name, int namelen, 160 int depth, int max_depth) 161{ 162 const char *cp = name, *cpe = name + namelen; 163 164 while (cp < cpe) { 165 if (*cp++ != '/') 166 continue; 167 depth++; 168 if (depth > max_depth) 169 return 0; 170 } 171 return 1; 172} 173 174/* 175 * Does 'match' match the given name? 176 * A match is found if 177 * 178 * (1) the 'match' string is leading directory of 'name', or 179 * (2) the 'match' string is a wildcard and matches 'name', or 180 * (3) the 'match' string is exactly the same as 'name'. 181 * 182 * and the return value tells which case it was. 183 * 184 * It returns 0 when there is no match. 185 */ 186static int match_one(const char *match, const char *name, int namelen) 187{ 188 int matchlen; 189 int literal = limit_pathspec_to_literal(); 190 191 /* If the match was just the prefix, we matched */ 192 if (!*match) 193 return MATCHED_RECURSIVELY; 194 195 if (ignore_case) { 196 for (;;) { 197 unsigned char c1 = tolower(*match); 198 unsigned char c2 = tolower(*name); 199 if (c1 == '\0' || (!literal && is_glob_special(c1))) 200 break; 201 if (c1 != c2) 202 return 0; 203 match++; 204 name++; 205 namelen--; 206 } 207 } else { 208 for (;;) { 209 unsigned char c1 = *match; 210 unsigned char c2 = *name; 211 if (c1 == '\0' || (!literal && is_glob_special(c1))) 212 break; 213 if (c1 != c2) 214 return 0; 215 match++; 216 name++; 217 namelen--; 218 } 219 } 220 221 /* 222 * If we don't match the matchstring exactly, 223 * we need to match by fnmatch 224 */ 225 matchlen = strlen(match); 226 if (strncmp_icase(match, name, matchlen)) { 227 if (literal) 228 return 0; 229 return !fnmatch_icase(match, name, 0) ? MATCHED_FNMATCH : 0; 230 } 231 232 if (namelen == matchlen) 233 return MATCHED_EXACTLY; 234 if (match[matchlen-1] == '/' || name[matchlen] == '/') 235 return MATCHED_RECURSIVELY; 236 return 0; 237} 238 239/* 240 * Given a name and a list of pathspecs, returns the nature of the 241 * closest (i.e. most specific) match of the name to any of the 242 * pathspecs. 243 * 244 * The caller typically calls this multiple times with the same 245 * pathspec and seen[] array but with different name/namelen 246 * (e.g. entries from the index) and is interested in seeing if and 247 * how each pathspec matches all the names it calls this function 248 * with. A mark is left in the seen[] array for each pathspec element 249 * indicating the closest type of match that element achieved, so if 250 * seen[n] remains zero after multiple invocations, that means the nth 251 * pathspec did not match any names, which could indicate that the 252 * user mistyped the nth pathspec. 253 */ 254int match_pathspec(const char **pathspec, const char *name, int namelen, 255 int prefix, char *seen) 256{ 257 int i, retval = 0; 258 259 if (!pathspec) 260 return 1; 261 262 name += prefix; 263 namelen -= prefix; 264 265 for (i = 0; pathspec[i] != NULL; i++) { 266 int how; 267 const char *match = pathspec[i] + prefix; 268 if (seen && seen[i] == MATCHED_EXACTLY) 269 continue; 270 how = match_one(match, name, namelen); 271 if (how) { 272 if (retval < how) 273 retval = how; 274 if (seen && seen[i] < how) 275 seen[i] = how; 276 } 277 } 278 return retval; 279} 280 281/* 282 * Does 'match' match the given name? 283 * A match is found if 284 * 285 * (1) the 'match' string is leading directory of 'name', or 286 * (2) the 'match' string is a wildcard and matches 'name', or 287 * (3) the 'match' string is exactly the same as 'name'. 288 * 289 * and the return value tells which case it was. 290 * 291 * It returns 0 when there is no match. 292 */ 293static int match_pathspec_item(const struct pathspec_item *item, int prefix, 294 const char *name, int namelen) 295{ 296 /* name/namelen has prefix cut off by caller */ 297 const char *match = item->match + prefix; 298 int matchlen = item->len - prefix; 299 300 /* If the match was just the prefix, we matched */ 301 if (!*match) 302 return MATCHED_RECURSIVELY; 303 304 if (matchlen <= namelen && !strncmp(match, name, matchlen)) { 305 if (matchlen == namelen) 306 return MATCHED_EXACTLY; 307 308 if (match[matchlen-1] == '/' || name[matchlen] == '/') 309 return MATCHED_RECURSIVELY; 310 } 311 312 if (item->nowildcard_len < item->len && 313 !git_fnmatch(match, name, 314 item->flags & PATHSPEC_ONESTAR ? GFNM_ONESTAR : 0, 315 item->nowildcard_len - prefix)) 316 return MATCHED_FNMATCH; 317 318 return 0; 319} 320 321/* 322 * Given a name and a list of pathspecs, returns the nature of the 323 * closest (i.e. most specific) match of the name to any of the 324 * pathspecs. 325 * 326 * The caller typically calls this multiple times with the same 327 * pathspec and seen[] array but with different name/namelen 328 * (e.g. entries from the index) and is interested in seeing if and 329 * how each pathspec matches all the names it calls this function 330 * with. A mark is left in the seen[] array for each pathspec element 331 * indicating the closest type of match that element achieved, so if 332 * seen[n] remains zero after multiple invocations, that means the nth 333 * pathspec did not match any names, which could indicate that the 334 * user mistyped the nth pathspec. 335 */ 336int match_pathspec_depth(const struct pathspec *ps, 337 const char *name, int namelen, 338 int prefix, char *seen) 339{ 340 int i, retval = 0; 341 342 GUARD_PATHSPEC(ps, PATHSPEC_FROMTOP | PATHSPEC_MAXDEPTH); 343 344 if (!ps->nr) { 345 if (!ps->recursive || 346 !(ps->magic & PATHSPEC_MAXDEPTH) || 347 ps->max_depth == -1) 348 return MATCHED_RECURSIVELY; 349 350 if (within_depth(name, namelen, 0, ps->max_depth)) 351 return MATCHED_EXACTLY; 352 else 353 return 0; 354 } 355 356 name += prefix; 357 namelen -= prefix; 358 359 for (i = ps->nr - 1; i >= 0; i--) { 360 int how; 361 if (seen && seen[i] == MATCHED_EXACTLY) 362 continue; 363 how = match_pathspec_item(ps->items+i, prefix, name, namelen); 364 if (ps->recursive && 365 (ps->magic & PATHSPEC_MAXDEPTH) && 366 ps->max_depth != -1 && 367 how && how != MATCHED_FNMATCH) { 368 int len = ps->items[i].len; 369 if (name[len] == '/') 370 len++; 371 if (within_depth(name+len, namelen-len, 0, ps->max_depth)) 372 how = MATCHED_EXACTLY; 373 else 374 how = 0; 375 } 376 if (how) { 377 if (retval < how) 378 retval = how; 379 if (seen && seen[i] < how) 380 seen[i] = how; 381 } 382 } 383 return retval; 384} 385 386/* 387 * Return the length of the "simple" part of a path match limiter. 388 */ 389int simple_length(const char *match) 390{ 391 int len = -1; 392 393 for (;;) { 394 unsigned char c = *match++; 395 len++; 396 if (c == '\0' || is_glob_special(c)) 397 return len; 398 } 399} 400 401int no_wildcard(const char *string) 402{ 403 return string[simple_length(string)] == '\0'; 404} 405 406void parse_exclude_pattern(const char **pattern, 407 int *patternlen, 408 int *flags, 409 int *nowildcardlen) 410{ 411 const char *p = *pattern; 412 size_t i, len; 413 414 *flags = 0; 415 if (*p == '!') { 416 *flags |= EXC_FLAG_NEGATIVE; 417 p++; 418 } 419 len = strlen(p); 420 if (len && p[len - 1] == '/') { 421 len--; 422 *flags |= EXC_FLAG_MUSTBEDIR; 423 } 424 for (i = 0; i < len; i++) { 425 if (p[i] == '/') 426 break; 427 } 428 if (i == len) 429 *flags |= EXC_FLAG_NODIR; 430 *nowildcardlen = simple_length(p); 431 /* 432 * we should have excluded the trailing slash from 'p' too, 433 * but that's one more allocation. Instead just make sure 434 * nowildcardlen does not exceed real patternlen 435 */ 436 if (*nowildcardlen > len) 437 *nowildcardlen = len; 438 if (*p == '*' && no_wildcard(p + 1)) 439 *flags |= EXC_FLAG_ENDSWITH; 440 *pattern = p; 441 *patternlen = len; 442} 443 444void add_exclude(const char *string, const char *base, 445 int baselen, struct exclude_list *el, int srcpos) 446{ 447 struct exclude *x; 448 int patternlen; 449 int flags; 450 int nowildcardlen; 451 452 parse_exclude_pattern(&string, &patternlen, &flags, &nowildcardlen); 453 if (flags & EXC_FLAG_MUSTBEDIR) { 454 char *s; 455 x = xmalloc(sizeof(*x) + patternlen + 1); 456 s = (char *)(x+1); 457 memcpy(s, string, patternlen); 458 s[patternlen] = '\0'; 459 x->pattern = s; 460 } else { 461 x = xmalloc(sizeof(*x)); 462 x->pattern = string; 463 } 464 x->patternlen = patternlen; 465 x->nowildcardlen = nowildcardlen; 466 x->base = base; 467 x->baselen = baselen; 468 x->flags = flags; 469 x->srcpos = srcpos; 470 ALLOC_GROW(el->excludes, el->nr + 1, el->alloc); 471 el->excludes[el->nr++] = x; 472 x->el = el; 473} 474 475static void *read_skip_worktree_file_from_index(const char *path, size_t *size) 476{ 477 int pos, len; 478 unsigned long sz; 479 enum object_type type; 480 void *data; 481 struct index_state *istate = &the_index; 482 483 len = strlen(path); 484 pos = index_name_pos(istate, path, len); 485 if (pos < 0) 486 return NULL; 487 if (!ce_skip_worktree(istate->cache[pos])) 488 return NULL; 489 data = read_sha1_file(istate->cache[pos]->sha1, &type, &sz); 490 if (!data || type != OBJ_BLOB) { 491 free(data); 492 return NULL; 493 } 494 *size = xsize_t(sz); 495 return data; 496} 497 498/* 499 * Frees memory within el which was allocated for exclude patterns and 500 * the file buffer. Does not free el itself. 501 */ 502void clear_exclude_list(struct exclude_list *el) 503{ 504 int i; 505 506 for (i = 0; i < el->nr; i++) 507 free(el->excludes[i]); 508 free(el->excludes); 509 free(el->filebuf); 510 511 el->nr = 0; 512 el->excludes = NULL; 513 el->filebuf = NULL; 514} 515 516int add_excludes_from_file_to_list(const char *fname, 517 const char *base, 518 int baselen, 519 struct exclude_list *el, 520 int check_index) 521{ 522 struct stat st; 523 int fd, i, lineno = 1; 524 size_t size = 0; 525 char *buf, *entry; 526 527 fd = open(fname, O_RDONLY); 528 if (fd < 0 || fstat(fd, &st) < 0) { 529 if (errno != ENOENT) 530 warn_on_inaccessible(fname); 531 if (0 <= fd) 532 close(fd); 533 if (!check_index || 534 (buf = read_skip_worktree_file_from_index(fname, &size)) == NULL) 535 return -1; 536 if (size == 0) { 537 free(buf); 538 return 0; 539 } 540 if (buf[size-1] != '\n') { 541 buf = xrealloc(buf, size+1); 542 buf[size++] = '\n'; 543 } 544 } 545 else { 546 size = xsize_t(st.st_size); 547 if (size == 0) { 548 close(fd); 549 return 0; 550 } 551 buf = xmalloc(size+1); 552 if (read_in_full(fd, buf, size) != size) { 553 free(buf); 554 close(fd); 555 return -1; 556 } 557 buf[size++] = '\n'; 558 close(fd); 559 } 560 561 el->filebuf = buf; 562 entry = buf; 563 for (i = 0; i < size; i++) { 564 if (buf[i] == '\n') { 565 if (entry != buf + i && entry[0] != '#') { 566 buf[i - (i && buf[i-1] == '\r')] = 0; 567 add_exclude(entry, base, baselen, el, lineno); 568 } 569 lineno++; 570 entry = buf + i + 1; 571 } 572 } 573 return 0; 574} 575 576struct exclude_list *add_exclude_list(struct dir_struct *dir, 577 int group_type, const char *src) 578{ 579 struct exclude_list *el; 580 struct exclude_list_group *group; 581 582 group = &dir->exclude_list_group[group_type]; 583 ALLOC_GROW(group->el, group->nr + 1, group->alloc); 584 el = &group->el[group->nr++]; 585 memset(el, 0, sizeof(*el)); 586 el->src = src; 587 return el; 588} 589 590/* 591 * Used to set up core.excludesfile and .git/info/exclude lists. 592 */ 593void add_excludes_from_file(struct dir_struct *dir, const char *fname) 594{ 595 struct exclude_list *el; 596 el = add_exclude_list(dir, EXC_FILE, fname); 597 if (add_excludes_from_file_to_list(fname, "", 0, el, 0) < 0) 598 die("cannot use %s as an exclude file", fname); 599} 600 601int match_basename(const char *basename, int basenamelen, 602 const char *pattern, int prefix, int patternlen, 603 int flags) 604{ 605 if (prefix == patternlen) { 606 if (patternlen == basenamelen && 607 !strncmp_icase(pattern, basename, basenamelen)) 608 return 1; 609 } else if (flags & EXC_FLAG_ENDSWITH) { 610 /* "*literal" matching against "fooliteral" */ 611 if (patternlen - 1 <= basenamelen && 612 !strncmp_icase(pattern + 1, 613 basename + basenamelen - (patternlen - 1), 614 patternlen - 1)) 615 return 1; 616 } else { 617 if (fnmatch_icase_mem(pattern, patternlen, 618 basename, basenamelen, 619 0) == 0) 620 return 1; 621 } 622 return 0; 623} 624 625int match_pathname(const char *pathname, int pathlen, 626 const char *base, int baselen, 627 const char *pattern, int prefix, int patternlen, 628 int flags) 629{ 630 const char *name; 631 int namelen; 632 633 /* 634 * match with FNM_PATHNAME; the pattern has base implicitly 635 * in front of it. 636 */ 637 if (*pattern == '/') { 638 pattern++; 639 patternlen--; 640 prefix--; 641 } 642 643 /* 644 * baselen does not count the trailing slash. base[] may or 645 * may not end with a trailing slash though. 646 */ 647 if (pathlen < baselen + 1 || 648 (baselen && pathname[baselen] != '/') || 649 strncmp_icase(pathname, base, baselen)) 650 return 0; 651 652 namelen = baselen ? pathlen - baselen - 1 : pathlen; 653 name = pathname + pathlen - namelen; 654 655 if (prefix) { 656 /* 657 * if the non-wildcard part is longer than the 658 * remaining pathname, surely it cannot match. 659 */ 660 if (prefix > namelen) 661 return 0; 662 663 if (strncmp_icase(pattern, name, prefix)) 664 return 0; 665 pattern += prefix; 666 patternlen -= prefix; 667 name += prefix; 668 namelen -= prefix; 669 670 /* 671 * If the whole pattern did not have a wildcard, 672 * then our prefix match is all we need; we 673 * do not need to call fnmatch at all. 674 */ 675 if (!patternlen && !namelen) 676 return 1; 677 } 678 679 return fnmatch_icase_mem(pattern, patternlen, 680 name, namelen, 681 WM_PATHNAME) == 0; 682} 683 684/* 685 * Scan the given exclude list in reverse to see whether pathname 686 * should be ignored. The first match (i.e. the last on the list), if 687 * any, determines the fate. Returns the exclude_list element which 688 * matched, or NULL for undecided. 689 */ 690static struct exclude *last_exclude_matching_from_list(const char *pathname, 691 int pathlen, 692 const char *basename, 693 int *dtype, 694 struct exclude_list *el) 695{ 696 int i; 697 698 if (!el->nr) 699 return NULL; /* undefined */ 700 701 for (i = el->nr - 1; 0 <= i; i--) { 702 struct exclude *x = el->excludes[i]; 703 const char *exclude = x->pattern; 704 int prefix = x->nowildcardlen; 705 706 if (x->flags & EXC_FLAG_MUSTBEDIR) { 707 if (*dtype == DT_UNKNOWN) 708 *dtype = get_dtype(NULL, pathname, pathlen); 709 if (*dtype != DT_DIR) 710 continue; 711 } 712 713 if (x->flags & EXC_FLAG_NODIR) { 714 if (match_basename(basename, 715 pathlen - (basename - pathname), 716 exclude, prefix, x->patternlen, 717 x->flags)) 718 return x; 719 continue; 720 } 721 722 assert(x->baselen == 0 || x->base[x->baselen - 1] == '/'); 723 if (match_pathname(pathname, pathlen, 724 x->base, x->baselen ? x->baselen - 1 : 0, 725 exclude, prefix, x->patternlen, x->flags)) 726 return x; 727 } 728 return NULL; /* undecided */ 729} 730 731/* 732 * Scan the list and let the last match determine the fate. 733 * Return 1 for exclude, 0 for include and -1 for undecided. 734 */ 735int is_excluded_from_list(const char *pathname, 736 int pathlen, const char *basename, int *dtype, 737 struct exclude_list *el) 738{ 739 struct exclude *exclude; 740 exclude = last_exclude_matching_from_list(pathname, pathlen, basename, dtype, el); 741 if (exclude) 742 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1; 743 return -1; /* undecided */ 744} 745 746static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir, 747 const char *pathname, int pathlen, const char *basename, 748 int *dtype_p) 749{ 750 int i, j; 751 struct exclude_list_group *group; 752 struct exclude *exclude; 753 for (i = EXC_CMDL; i <= EXC_FILE; i++) { 754 group = &dir->exclude_list_group[i]; 755 for (j = group->nr - 1; j >= 0; j--) { 756 exclude = last_exclude_matching_from_list( 757 pathname, pathlen, basename, dtype_p, 758 &group->el[j]); 759 if (exclude) 760 return exclude; 761 } 762 } 763 return NULL; 764} 765 766/* 767 * Loads the per-directory exclude list for the substring of base 768 * which has a char length of baselen. 769 */ 770static void prep_exclude(struct dir_struct *dir, const char *base, int baselen) 771{ 772 struct exclude_list_group *group; 773 struct exclude_list *el; 774 struct exclude_stack *stk = NULL; 775 int current; 776 777 group = &dir->exclude_list_group[EXC_DIRS]; 778 779 /* Pop the exclude lists from the EXCL_DIRS exclude_list_group 780 * which originate from directories not in the prefix of the 781 * path being checked. */ 782 while ((stk = dir->exclude_stack) != NULL) { 783 if (stk->baselen <= baselen && 784 !strncmp(dir->basebuf, base, stk->baselen)) 785 break; 786 el = &group->el[dir->exclude_stack->exclude_ix]; 787 dir->exclude_stack = stk->prev; 788 dir->exclude = NULL; 789 free((char *)el->src); /* see strdup() below */ 790 clear_exclude_list(el); 791 free(stk); 792 group->nr--; 793 } 794 795 /* Skip traversing into sub directories if the parent is excluded */ 796 if (dir->exclude) 797 return; 798 799 /* Read from the parent directories and push them down. */ 800 current = stk ? stk->baselen : -1; 801 while (current < baselen) { 802 struct exclude_stack *stk = xcalloc(1, sizeof(*stk)); 803 const char *cp; 804 805 if (current < 0) { 806 cp = base; 807 current = 0; 808 } 809 else { 810 cp = strchr(base + current + 1, '/'); 811 if (!cp) 812 die("oops in prep_exclude"); 813 cp++; 814 } 815 stk->prev = dir->exclude_stack; 816 stk->baselen = cp - base; 817 stk->exclude_ix = group->nr; 818 el = add_exclude_list(dir, EXC_DIRS, NULL); 819 memcpy(dir->basebuf + current, base + current, 820 stk->baselen - current); 821 822 /* Abort if the directory is excluded */ 823 if (stk->baselen) { 824 int dt = DT_DIR; 825 dir->basebuf[stk->baselen - 1] = 0; 826 dir->exclude = last_exclude_matching_from_lists(dir, 827 dir->basebuf, stk->baselen - 1, 828 dir->basebuf + current, &dt); 829 dir->basebuf[stk->baselen - 1] = '/'; 830 if (dir->exclude && 831 dir->exclude->flags & EXC_FLAG_NEGATIVE) 832 dir->exclude = NULL; 833 if (dir->exclude) { 834 dir->basebuf[stk->baselen] = 0; 835 dir->exclude_stack = stk; 836 return; 837 } 838 } 839 840 /* Try to read per-directory file unless path is too long */ 841 if (dir->exclude_per_dir && 842 stk->baselen + strlen(dir->exclude_per_dir) < PATH_MAX) { 843 strcpy(dir->basebuf + stk->baselen, 844 dir->exclude_per_dir); 845 /* 846 * dir->basebuf gets reused by the traversal, but we 847 * need fname to remain unchanged to ensure the src 848 * member of each struct exclude correctly 849 * back-references its source file. Other invocations 850 * of add_exclude_list provide stable strings, so we 851 * strdup() and free() here in the caller. 852 */ 853 el->src = strdup(dir->basebuf); 854 add_excludes_from_file_to_list(dir->basebuf, 855 dir->basebuf, stk->baselen, el, 1); 856 } 857 dir->exclude_stack = stk; 858 current = stk->baselen; 859 } 860 dir->basebuf[baselen] = '\0'; 861} 862 863/* 864 * Loads the exclude lists for the directory containing pathname, then 865 * scans all exclude lists to determine whether pathname is excluded. 866 * Returns the exclude_list element which matched, or NULL for 867 * undecided. 868 */ 869struct exclude *last_exclude_matching(struct dir_struct *dir, 870 const char *pathname, 871 int *dtype_p) 872{ 873 int pathlen = strlen(pathname); 874 const char *basename = strrchr(pathname, '/'); 875 basename = (basename) ? basename+1 : pathname; 876 877 prep_exclude(dir, pathname, basename-pathname); 878 879 if (dir->exclude) 880 return dir->exclude; 881 882 return last_exclude_matching_from_lists(dir, pathname, pathlen, 883 basename, dtype_p); 884} 885 886/* 887 * Loads the exclude lists for the directory containing pathname, then 888 * scans all exclude lists to determine whether pathname is excluded. 889 * Returns 1 if true, otherwise 0. 890 */ 891int is_excluded(struct dir_struct *dir, const char *pathname, int *dtype_p) 892{ 893 struct exclude *exclude = 894 last_exclude_matching(dir, pathname, dtype_p); 895 if (exclude) 896 return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1; 897 return 0; 898} 899 900static struct dir_entry *dir_entry_new(const char *pathname, int len) 901{ 902 struct dir_entry *ent; 903 904 ent = xmalloc(sizeof(*ent) + len + 1); 905 ent->len = len; 906 memcpy(ent->name, pathname, len); 907 ent->name[len] = 0; 908 return ent; 909} 910 911static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len) 912{ 913 if (cache_name_exists(pathname, len, ignore_case)) 914 return NULL; 915 916 ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc); 917 return dir->entries[dir->nr++] = dir_entry_new(pathname, len); 918} 919 920struct dir_entry *dir_add_ignored(struct dir_struct *dir, const char *pathname, int len) 921{ 922 if (!cache_name_is_other(pathname, len)) 923 return NULL; 924 925 ALLOC_GROW(dir->ignored, dir->ignored_nr+1, dir->ignored_alloc); 926 return dir->ignored[dir->ignored_nr++] = dir_entry_new(pathname, len); 927} 928 929enum exist_status { 930 index_nonexistent = 0, 931 index_directory, 932 index_gitdir 933}; 934 935/* 936 * Do not use the alphabetically stored index to look up 937 * the directory name; instead, use the case insensitive 938 * name hash. 939 */ 940static enum exist_status directory_exists_in_index_icase(const char *dirname, int len) 941{ 942 struct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case); 943 unsigned char endchar; 944 945 if (!ce) 946 return index_nonexistent; 947 endchar = ce->name[len]; 948 949 /* 950 * The cache_entry structure returned will contain this dirname 951 * and possibly additional path components. 952 */ 953 if (endchar == '/') 954 return index_directory; 955 956 /* 957 * If there are no additional path components, then this cache_entry 958 * represents a submodule. Submodules, despite being directories, 959 * are stored in the cache without a closing slash. 960 */ 961 if (!endchar && S_ISGITLINK(ce->ce_mode)) 962 return index_gitdir; 963 964 /* This should never be hit, but it exists just in case. */ 965 return index_nonexistent; 966} 967 968/* 969 * The index sorts alphabetically by entry name, which 970 * means that a gitlink sorts as '\0' at the end, while 971 * a directory (which is defined not as an entry, but as 972 * the files it contains) will sort with the '/' at the 973 * end. 974 */ 975static enum exist_status directory_exists_in_index(const char *dirname, int len) 976{ 977 int pos; 978 979 if (ignore_case) 980 return directory_exists_in_index_icase(dirname, len); 981 982 pos = cache_name_pos(dirname, len); 983 if (pos < 0) 984 pos = -pos-1; 985 while (pos < active_nr) { 986 struct cache_entry *ce = active_cache[pos++]; 987 unsigned char endchar; 988 989 if (strncmp(ce->name, dirname, len)) 990 break; 991 endchar = ce->name[len]; 992 if (endchar > '/') 993 break; 994 if (endchar == '/') 995 return index_directory; 996 if (!endchar && S_ISGITLINK(ce->ce_mode)) 997 return index_gitdir; 998 } 999 return index_nonexistent;1000}10011002/*1003 * When we find a directory when traversing the filesystem, we1004 * have three distinct cases:1005 *1006 * - ignore it1007 * - see it as a directory1008 * - recurse into it1009 *1010 * and which one we choose depends on a combination of existing1011 * git index contents and the flags passed into the directory1012 * traversal routine.1013 *1014 * Case 1: If we *already* have entries in the index under that1015 * directory name, we always recurse into the directory to see1016 * all the files.1017 *1018 * Case 2: If we *already* have that directory name as a gitlink,1019 * we always continue to see it as a gitlink, regardless of whether1020 * there is an actual git directory there or not (it might not1021 * be checked out as a subproject!)1022 *1023 * Case 3: if we didn't have it in the index previously, we1024 * have a few sub-cases:1025 *1026 * (a) if "show_other_directories" is true, we show it as1027 * just a directory, unless "hide_empty_directories" is1028 * also true, in which case we need to check if it contains any1029 * untracked and / or ignored files.1030 * (b) if it looks like a git directory, and we don't have1031 * 'no_gitlinks' set we treat it as a gitlink, and show it1032 * as a directory.1033 * (c) otherwise, we recurse into it.1034 */1035static enum path_treatment treat_directory(struct dir_struct *dir,1036 const char *dirname, int len, int exclude,1037 const struct path_simplify *simplify)1038{1039 /* The "len-1" is to strip the final '/' */1040 switch (directory_exists_in_index(dirname, len-1)) {1041 case index_directory:1042 return path_recurse;10431044 case index_gitdir:1045 return path_none;10461047 case index_nonexistent:1048 if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)1049 break;1050 if (!(dir->flags & DIR_NO_GITLINKS)) {1051 unsigned char sha1[20];1052 if (resolve_gitlink_ref(dirname, "HEAD", sha1) == 0)1053 return path_untracked;1054 }1055 return path_recurse;1056 }10571058 /* This is the "show_other_directories" case */10591060 if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))1061 return exclude ? path_excluded : path_untracked;10621063 return read_directory_recursive(dir, dirname, len, 1, simplify);1064}10651066/*1067 * This is an inexact early pruning of any recursive directory1068 * reading - if the path cannot possibly be in the pathspec,1069 * return true, and we'll skip it early.1070 */1071static int simplify_away(const char *path, int pathlen, const struct path_simplify *simplify)1072{1073 if (simplify) {1074 for (;;) {1075 const char *match = simplify->path;1076 int len = simplify->len;10771078 if (!match)1079 break;1080 if (len > pathlen)1081 len = pathlen;1082 if (!memcmp(path, match, len))1083 return 0;1084 simplify++;1085 }1086 return 1;1087 }1088 return 0;1089}10901091/*1092 * This function tells us whether an excluded path matches a1093 * list of "interesting" pathspecs. That is, whether a path matched1094 * by any of the pathspecs could possibly be ignored by excluding1095 * the specified path. This can happen if:1096 *1097 * 1. the path is mentioned explicitly in the pathspec1098 *1099 * 2. the path is a directory prefix of some element in the1100 * pathspec1101 */1102static int exclude_matches_pathspec(const char *path, int len,1103 const struct path_simplify *simplify)1104{1105 if (simplify) {1106 for (; simplify->path; simplify++) {1107 if (len == simplify->len1108 && !memcmp(path, simplify->path, len))1109 return 1;1110 if (len < simplify->len1111 && simplify->path[len] == '/'1112 && !memcmp(path, simplify->path, len))1113 return 1;1114 }1115 }1116 return 0;1117}11181119static int get_index_dtype(const char *path, int len)1120{1121 int pos;1122 struct cache_entry *ce;11231124 ce = cache_name_exists(path, len, 0);1125 if (ce) {1126 if (!ce_uptodate(ce))1127 return DT_UNKNOWN;1128 if (S_ISGITLINK(ce->ce_mode))1129 return DT_DIR;1130 /*1131 * Nobody actually cares about the1132 * difference between DT_LNK and DT_REG1133 */1134 return DT_REG;1135 }11361137 /* Try to look it up as a directory */1138 pos = cache_name_pos(path, len);1139 if (pos >= 0)1140 return DT_UNKNOWN;1141 pos = -pos-1;1142 while (pos < active_nr) {1143 ce = active_cache[pos++];1144 if (strncmp(ce->name, path, len))1145 break;1146 if (ce->name[len] > '/')1147 break;1148 if (ce->name[len] < '/')1149 continue;1150 if (!ce_uptodate(ce))1151 break; /* continue? */1152 return DT_DIR;1153 }1154 return DT_UNKNOWN;1155}11561157static int get_dtype(struct dirent *de, const char *path, int len)1158{1159 int dtype = de ? DTYPE(de) : DT_UNKNOWN;1160 struct stat st;11611162 if (dtype != DT_UNKNOWN)1163 return dtype;1164 dtype = get_index_dtype(path, len);1165 if (dtype != DT_UNKNOWN)1166 return dtype;1167 if (lstat(path, &st))1168 return dtype;1169 if (S_ISREG(st.st_mode))1170 return DT_REG;1171 if (S_ISDIR(st.st_mode))1172 return DT_DIR;1173 if (S_ISLNK(st.st_mode))1174 return DT_LNK;1175 return dtype;1176}11771178static enum path_treatment treat_one_path(struct dir_struct *dir,1179 struct strbuf *path,1180 const struct path_simplify *simplify,1181 int dtype, struct dirent *de)1182{1183 int exclude;1184 if (dtype == DT_UNKNOWN)1185 dtype = get_dtype(de, path->buf, path->len);11861187 /* Always exclude indexed files */1188 if (dtype != DT_DIR &&1189 cache_name_exists(path->buf, path->len, ignore_case))1190 return path_none;11911192 exclude = is_excluded(dir, path->buf, &dtype);11931194 /*1195 * Excluded? If we don't explicitly want to show1196 * ignored files, ignore it1197 */1198 if (exclude && !(dir->flags & (DIR_SHOW_IGNORED|DIR_SHOW_IGNORED_TOO)))1199 return path_excluded;12001201 switch (dtype) {1202 default:1203 return path_none;1204 case DT_DIR:1205 strbuf_addch(path, '/');1206 return treat_directory(dir, path->buf, path->len, exclude,1207 simplify);1208 case DT_REG:1209 case DT_LNK:1210 return exclude ? path_excluded : path_untracked;1211 }1212}12131214static enum path_treatment treat_path(struct dir_struct *dir,1215 struct dirent *de,1216 struct strbuf *path,1217 int baselen,1218 const struct path_simplify *simplify)1219{1220 int dtype;12211222 if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))1223 return path_none;1224 strbuf_setlen(path, baselen);1225 strbuf_addstr(path, de->d_name);1226 if (simplify_away(path->buf, path->len, simplify))1227 return path_none;12281229 dtype = DTYPE(de);1230 return treat_one_path(dir, path, simplify, dtype, de);1231}12321233/*1234 * Read a directory tree. We currently ignore anything but1235 * directories, regular files and symlinks. That's because git1236 * doesn't handle them at all yet. Maybe that will change some1237 * day.1238 *1239 * Also, we ignore the name ".git" (even if it is not a directory).1240 * That likely will not change.1241 *1242 * Returns the most significant path_treatment value encountered in the scan.1243 */1244static enum path_treatment read_directory_recursive(struct dir_struct *dir,1245 const char *base, int baselen,1246 int check_only,1247 const struct path_simplify *simplify)1248{1249 DIR *fdir;1250 enum path_treatment state, subdir_state, dir_state = path_none;1251 struct dirent *de;1252 struct strbuf path = STRBUF_INIT;12531254 strbuf_add(&path, base, baselen);12551256 fdir = opendir(path.len ? path.buf : ".");1257 if (!fdir)1258 goto out;12591260 while ((de = readdir(fdir)) != NULL) {1261 /* check how the file or directory should be treated */1262 state = treat_path(dir, de, &path, baselen, simplify);1263 if (state > dir_state)1264 dir_state = state;12651266 /* recurse into subdir if instructed by treat_path */1267 if (state == path_recurse) {1268 subdir_state = read_directory_recursive(dir, path.buf,1269 path.len, check_only, simplify);1270 if (subdir_state > dir_state)1271 dir_state = subdir_state;1272 }12731274 if (check_only) {1275 /* abort early if maximum state has been reached */1276 if (dir_state == path_untracked)1277 break;1278 /* skip the dir_add_* part */1279 continue;1280 }12811282 /* add the path to the appropriate result list */1283 switch (state) {1284 case path_excluded:1285 if (dir->flags & DIR_SHOW_IGNORED)1286 dir_add_name(dir, path.buf, path.len);1287 else if ((dir->flags & DIR_SHOW_IGNORED_TOO) ||1288 ((dir->flags & DIR_COLLECT_IGNORED) &&1289 exclude_matches_pathspec(path.buf, path.len,1290 simplify)))1291 dir_add_ignored(dir, path.buf, path.len);1292 break;12931294 case path_untracked:1295 if (!(dir->flags & DIR_SHOW_IGNORED))1296 dir_add_name(dir, path.buf, path.len);1297 break;12981299 default:1300 break;1301 }1302 }1303 closedir(fdir);1304 out:1305 strbuf_release(&path);13061307 return dir_state;1308}13091310static int cmp_name(const void *p1, const void *p2)1311{1312 const struct dir_entry *e1 = *(const struct dir_entry **)p1;1313 const struct dir_entry *e2 = *(const struct dir_entry **)p2;13141315 return cache_name_compare(e1->name, e1->len,1316 e2->name, e2->len);1317}13181319static struct path_simplify *create_simplify(const char **pathspec)1320{1321 int nr, alloc = 0;1322 struct path_simplify *simplify = NULL;13231324 if (!pathspec)1325 return NULL;13261327 for (nr = 0 ; ; nr++) {1328 const char *match;1329 if (nr >= alloc) {1330 alloc = alloc_nr(alloc);1331 simplify = xrealloc(simplify, alloc * sizeof(*simplify));1332 }1333 match = *pathspec++;1334 if (!match)1335 break;1336 simplify[nr].path = match;1337 simplify[nr].len = simple_length(match);1338 }1339 simplify[nr].path = NULL;1340 simplify[nr].len = 0;1341 return simplify;1342}13431344static void free_simplify(struct path_simplify *simplify)1345{1346 free(simplify);1347}13481349static int treat_leading_path(struct dir_struct *dir,1350 const char *path, int len,1351 const struct path_simplify *simplify)1352{1353 struct strbuf sb = STRBUF_INIT;1354 int baselen, rc = 0;1355 const char *cp;1356 int old_flags = dir->flags;13571358 while (len && path[len - 1] == '/')1359 len--;1360 if (!len)1361 return 1;1362 baselen = 0;1363 dir->flags &= ~DIR_SHOW_OTHER_DIRECTORIES;1364 while (1) {1365 cp = path + baselen + !!baselen;1366 cp = memchr(cp, '/', path + len - cp);1367 if (!cp)1368 baselen = len;1369 else1370 baselen = cp - path;1371 strbuf_setlen(&sb, 0);1372 strbuf_add(&sb, path, baselen);1373 if (!is_directory(sb.buf))1374 break;1375 if (simplify_away(sb.buf, sb.len, simplify))1376 break;1377 if (treat_one_path(dir, &sb, simplify,1378 DT_DIR, NULL) == path_none)1379 break; /* do not recurse into it */1380 if (len <= baselen) {1381 rc = 1;1382 break; /* finished checking */1383 }1384 }1385 strbuf_release(&sb);1386 dir->flags = old_flags;1387 return rc;1388}13891390int read_directory(struct dir_struct *dir, const char *path, int len, const struct pathspec *pathspec)1391{1392 struct path_simplify *simplify;13931394 /*1395 * Check out create_simplify()1396 */1397 if (pathspec)1398 GUARD_PATHSPEC(pathspec, PATHSPEC_FROMTOP | PATHSPEC_MAXDEPTH);13991400 if (has_symlink_leading_path(path, len))1401 return dir->nr;14021403 simplify = create_simplify(pathspec ? pathspec->raw : NULL);1404 if (!len || treat_leading_path(dir, path, len, simplify))1405 read_directory_recursive(dir, path, len, 0, simplify);1406 free_simplify(simplify);1407 qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);1408 qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);1409 return dir->nr;1410}14111412int file_exists(const char *f)1413{1414 struct stat sb;1415 return lstat(f, &sb) == 0;1416}14171418/*1419 * Given two normalized paths (a trailing slash is ok), if subdir is1420 * outside dir, return -1. Otherwise return the offset in subdir that1421 * can be used as relative path to dir.1422 */1423int dir_inside_of(const char *subdir, const char *dir)1424{1425 int offset = 0;14261427 assert(dir && subdir && *dir && *subdir);14281429 while (*dir && *subdir && *dir == *subdir) {1430 dir++;1431 subdir++;1432 offset++;1433 }14341435 /* hel[p]/me vs hel[l]/yeah */1436 if (*dir && *subdir)1437 return -1;14381439 if (!*subdir)1440 return !*dir ? offset : -1; /* same dir */14411442 /* foo/[b]ar vs foo/[] */1443 if (is_dir_sep(dir[-1]))1444 return is_dir_sep(subdir[-1]) ? offset : -1;14451446 /* foo[/]bar vs foo[] */1447 return is_dir_sep(*subdir) ? offset + 1 : -1;1448}14491450int is_inside_dir(const char *dir)1451{1452 char cwd[PATH_MAX];1453 if (!dir)1454 return 0;1455 if (!getcwd(cwd, sizeof(cwd)))1456 die_errno("can't find the current directory");1457 return dir_inside_of(cwd, dir) >= 0;1458}14591460int is_empty_dir(const char *path)1461{1462 DIR *dir = opendir(path);1463 struct dirent *e;1464 int ret = 1;14651466 if (!dir)1467 return 0;14681469 while ((e = readdir(dir)) != NULL)1470 if (!is_dot_or_dotdot(e->d_name)) {1471 ret = 0;1472 break;1473 }14741475 closedir(dir);1476 return ret;1477}14781479static int remove_dir_recurse(struct strbuf *path, int flag, int *kept_up)1480{1481 DIR *dir;1482 struct dirent *e;1483 int ret = 0, original_len = path->len, len, kept_down = 0;1484 int only_empty = (flag & REMOVE_DIR_EMPTY_ONLY);1485 int keep_toplevel = (flag & REMOVE_DIR_KEEP_TOPLEVEL);1486 unsigned char submodule_head[20];14871488 if ((flag & REMOVE_DIR_KEEP_NESTED_GIT) &&1489 !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {1490 /* Do not descend and nuke a nested git work tree. */1491 if (kept_up)1492 *kept_up = 1;1493 return 0;1494 }14951496 flag &= ~REMOVE_DIR_KEEP_TOPLEVEL;1497 dir = opendir(path->buf);1498 if (!dir) {1499 /* an empty dir could be removed even if it is unreadble */1500 if (!keep_toplevel)1501 return rmdir(path->buf);1502 else1503 return -1;1504 }1505 if (path->buf[original_len - 1] != '/')1506 strbuf_addch(path, '/');15071508 len = path->len;1509 while ((e = readdir(dir)) != NULL) {1510 struct stat st;1511 if (is_dot_or_dotdot(e->d_name))1512 continue;15131514 strbuf_setlen(path, len);1515 strbuf_addstr(path, e->d_name);1516 if (lstat(path->buf, &st))1517 ; /* fall thru */1518 else if (S_ISDIR(st.st_mode)) {1519 if (!remove_dir_recurse(path, flag, &kept_down))1520 continue; /* happy */1521 } else if (!only_empty && !unlink(path->buf))1522 continue; /* happy, too */15231524 /* path too long, stat fails, or non-directory still exists */1525 ret = -1;1526 break;1527 }1528 closedir(dir);15291530 strbuf_setlen(path, original_len);1531 if (!ret && !keep_toplevel && !kept_down)1532 ret = rmdir(path->buf);1533 else if (kept_up)1534 /*1535 * report the uplevel that it is not an error that we1536 * did not rmdir() our directory.1537 */1538 *kept_up = !ret;1539 return ret;1540}15411542int remove_dir_recursively(struct strbuf *path, int flag)1543{1544 return remove_dir_recurse(path, flag, NULL);1545}15461547void setup_standard_excludes(struct dir_struct *dir)1548{1549 const char *path;1550 char *xdg_path;15511552 dir->exclude_per_dir = ".gitignore";1553 path = git_path("info/exclude");1554 if (!excludes_file) {1555 home_config_paths(NULL, &xdg_path, "ignore");1556 excludes_file = xdg_path;1557 }1558 if (!access_or_warn(path, R_OK, 0))1559 add_excludes_from_file(dir, path);1560 if (excludes_file && !access_or_warn(excludes_file, R_OK, 0))1561 add_excludes_from_file(dir, excludes_file);1562}15631564int remove_path(const char *name)1565{1566 char *slash;15671568 if (unlink(name) && errno != ENOENT && errno != ENOTDIR)1569 return -1;15701571 slash = strrchr(name, '/');1572 if (slash) {1573 char *dirs = xstrdup(name);1574 slash = dirs + (slash - name);1575 do {1576 *slash = '\0';1577 } while (rmdir(dirs) == 0 && (slash = strrchr(dirs, '/')));1578 free(dirs);1579 }1580 return 0;1581}15821583int limit_pathspec_to_literal(void)1584{1585 static int flag = -1;1586 if (flag < 0)1587 flag = git_env_bool(GIT_LITERAL_PATHSPECS_ENVIRONMENT, 0);1588 return flag;1589}15901591/*1592 * Frees memory within dir which was allocated for exclude lists and1593 * the exclude_stack. Does not free dir itself.1594 */1595void clear_directory(struct dir_struct *dir)1596{1597 int i, j;1598 struct exclude_list_group *group;1599 struct exclude_list *el;1600 struct exclude_stack *stk;16011602 for (i = EXC_CMDL; i <= EXC_FILE; i++) {1603 group = &dir->exclude_list_group[i];1604 for (j = 0; j < group->nr; j++) {1605 el = &group->el[j];1606 if (i == EXC_DIRS)1607 free((char *)el->src);1608 clear_exclude_list(el);1609 }1610 free(group->el);1611 }16121613 stk = dir->exclude_stack;1614 while (stk) {1615 struct exclude_stack *prev = stk->prev;1616 free(stk);1617 stk = prev;1618 }1619}