1#include "cache.h" 2#include "tree-walk.h" 3#include "unpack-trees.h" 4#include "dir.h" 5#include "object-store.h" 6#include "tree.h" 7#include "pathspec.h" 8 9static const char *get_mode(const char *str, unsigned int *modep) 10{ 11 unsigned char c; 12 unsigned int mode = 0; 13 14 if (*str == ' ') 15 return NULL; 16 17 while ((c = *str++) != ' ') { 18 if (c < '0' || c > '7') 19 return NULL; 20 mode = (mode << 3) + (c - '0'); 21 } 22 *modep = mode; 23 return str; 24} 25 26static int decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size, struct strbuf *err) 27{ 28 const char *path; 29 unsigned int mode, len; 30 const unsigned hashsz = the_hash_algo->rawsz; 31 32 if (size < hashsz + 3 || buf[size - (hashsz + 1)]) { 33 strbuf_addstr(err, _("too-short tree object")); 34 return -1; 35 } 36 37 path = get_mode(buf, &mode); 38 if (!path) { 39 strbuf_addstr(err, _("malformed mode in tree entry")); 40 return -1; 41 } 42 if (!*path) { 43 strbuf_addstr(err, _("empty filename in tree entry")); 44 return -1; 45 } 46 len = strlen(path) + 1; 47 48 /* Initialize the descriptor entry */ 49 desc->entry.path = path; 50 desc->entry.mode = canon_mode(mode); 51 desc->entry.pathlen = len - 1; 52 hashcpy(desc->entry.oid.hash, (const unsigned char *)path + len); 53 54 return 0; 55} 56 57static int init_tree_desc_internal(struct tree_desc *desc, const void *buffer, unsigned long size, struct strbuf *err) 58{ 59 desc->buffer = buffer; 60 desc->size = size; 61 if (size) 62 return decode_tree_entry(desc, buffer, size, err); 63 return 0; 64} 65 66void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size) 67{ 68 struct strbuf err = STRBUF_INIT; 69 if (init_tree_desc_internal(desc, buffer, size, &err)) 70 die("%s", err.buf); 71 strbuf_release(&err); 72} 73 74int init_tree_desc_gently(struct tree_desc *desc, const void *buffer, unsigned long size) 75{ 76 struct strbuf err = STRBUF_INIT; 77 int result = init_tree_desc_internal(desc, buffer, size, &err); 78 if (result) 79 error("%s", err.buf); 80 strbuf_release(&err); 81 return result; 82} 83 84void *fill_tree_descriptor(struct tree_desc *desc, const struct object_id *oid) 85{ 86 unsigned long size = 0; 87 void *buf = NULL; 88 89 if (oid) { 90 buf = read_object_with_reference(oid, tree_type, &size, NULL); 91 if (!buf) 92 die("unable to read tree %s", oid_to_hex(oid)); 93 } 94 init_tree_desc(desc, buf, size); 95 return buf; 96} 97 98static void entry_clear(struct name_entry *a) 99{ 100 memset(a, 0, sizeof(*a)); 101} 102 103static void entry_extract(struct tree_desc *t, struct name_entry *a) 104{ 105 *a = t->entry; 106} 107 108static int update_tree_entry_internal(struct tree_desc *desc, struct strbuf *err) 109{ 110 const void *buf = desc->buffer; 111 const unsigned char *end = (const unsigned char *)desc->entry.path + desc->entry.pathlen + 1 + the_hash_algo->rawsz; 112 unsigned long size = desc->size; 113 unsigned long len = end - (const unsigned char *)buf; 114 115 if (size < len) 116 die(_("too-short tree file")); 117 buf = end; 118 size -= len; 119 desc->buffer = buf; 120 desc->size = size; 121 if (size) 122 return decode_tree_entry(desc, buf, size, err); 123 return 0; 124} 125 126void update_tree_entry(struct tree_desc *desc) 127{ 128 struct strbuf err = STRBUF_INIT; 129 if (update_tree_entry_internal(desc, &err)) 130 die("%s", err.buf); 131 strbuf_release(&err); 132} 133 134int update_tree_entry_gently(struct tree_desc *desc) 135{ 136 struct strbuf err = STRBUF_INIT; 137 if (update_tree_entry_internal(desc, &err)) { 138 error("%s", err.buf); 139 strbuf_release(&err); 140 /* Stop processing this tree after error */ 141 desc->size = 0; 142 return -1; 143 } 144 strbuf_release(&err); 145 return 0; 146} 147 148int tree_entry(struct tree_desc *desc, struct name_entry *entry) 149{ 150 if (!desc->size) 151 return 0; 152 153 *entry = desc->entry; 154 update_tree_entry(desc); 155 return 1; 156} 157 158int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry) 159{ 160 if (!desc->size) 161 return 0; 162 163 *entry = desc->entry; 164 if (update_tree_entry_gently(desc)) 165 return 0; 166 return 1; 167} 168 169void setup_traverse_info(struct traverse_info *info, const char *base) 170{ 171 int pathlen = strlen(base); 172 static struct traverse_info dummy; 173 174 memset(info, 0, sizeof(*info)); 175 if (pathlen && base[pathlen-1] == '/') 176 pathlen--; 177 info->pathlen = pathlen ? pathlen + 1 : 0; 178 info->name.path = base; 179 info->name.pathlen = pathlen; 180 if (pathlen) 181 info->prev = &dummy; 182} 183 184char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n) 185{ 186 int len = tree_entry_len(n); 187 int pathlen = info->pathlen; 188 189 path[pathlen + len] = 0; 190 for (;;) { 191 memcpy(path + pathlen, n->path, len); 192 if (!pathlen) 193 break; 194 path[--pathlen] = '/'; 195 n = &info->name; 196 len = tree_entry_len(n); 197 info = info->prev; 198 pathlen -= len; 199 } 200 return path; 201} 202 203struct tree_desc_skip { 204 struct tree_desc_skip *prev; 205 const void *ptr; 206}; 207 208struct tree_desc_x { 209 struct tree_desc d; 210 struct tree_desc_skip *skip; 211}; 212 213static int check_entry_match(const char *a, int a_len, const char *b, int b_len) 214{ 215 /* 216 * The caller wants to pick *a* from a tree or nothing. 217 * We are looking at *b* in a tree. 218 * 219 * (0) If a and b are the same name, we are trivially happy. 220 * 221 * There are three possibilities where *a* could be hiding 222 * behind *b*. 223 * 224 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no 225 * matter what. 226 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree; 227 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree. 228 * 229 * Otherwise we know *a* won't appear in the tree without 230 * scanning further. 231 */ 232 233 int cmp = name_compare(a, a_len, b, b_len); 234 235 /* Most common case first -- reading sync'd trees */ 236 if (!cmp) 237 return cmp; 238 239 if (0 < cmp) { 240 /* a comes after b; it does not matter if it is case (3) 241 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/') 242 return 1; 243 */ 244 return 1; /* keep looking */ 245 } 246 247 /* b comes after a; are we looking at case (2)? */ 248 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/') 249 return 1; /* keep looking */ 250 251 return -1; /* a cannot appear in the tree */ 252} 253 254/* 255 * From the extended tree_desc, extract the first name entry, while 256 * paying attention to the candidate "first" name. Most importantly, 257 * when looking for an entry, if there are entries that sorts earlier 258 * in the tree object representation than that name, skip them and 259 * process the named entry first. We will remember that we haven't 260 * processed the first entry yet, and in the later call skip the 261 * entry we processed early when update_extended_entry() is called. 262 * 263 * E.g. if the underlying tree object has these entries: 264 * 265 * blob "t-1" 266 * blob "t-2" 267 * tree "t" 268 * blob "t=1" 269 * 270 * and the "first" asks for "t", remember that we still need to 271 * process "t-1" and "t-2" but extract "t". After processing the 272 * entry "t" from this call, the caller will let us know by calling 273 * update_extended_entry() that we can remember "t" has been processed 274 * already. 275 */ 276 277static void extended_entry_extract(struct tree_desc_x *t, 278 struct name_entry *a, 279 const char *first, 280 int first_len) 281{ 282 const char *path; 283 int len; 284 struct tree_desc probe; 285 struct tree_desc_skip *skip; 286 287 /* 288 * Extract the first entry from the tree_desc, but skip the 289 * ones that we already returned in earlier rounds. 290 */ 291 while (1) { 292 if (!t->d.size) { 293 entry_clear(a); 294 break; /* not found */ 295 } 296 entry_extract(&t->d, a); 297 for (skip = t->skip; skip; skip = skip->prev) 298 if (a->path == skip->ptr) 299 break; /* found */ 300 if (!skip) 301 break; 302 /* We have processed this entry already. */ 303 update_tree_entry(&t->d); 304 } 305 306 if (!first || !a->path) 307 return; 308 309 /* 310 * The caller wants "first" from this tree, or nothing. 311 */ 312 path = a->path; 313 len = tree_entry_len(a); 314 switch (check_entry_match(first, first_len, path, len)) { 315 case -1: 316 entry_clear(a); 317 case 0: 318 return; 319 default: 320 break; 321 } 322 323 /* 324 * We need to look-ahead -- we suspect that a subtree whose 325 * name is "first" may be hiding behind the current entry "path". 326 */ 327 probe = t->d; 328 while (probe.size) { 329 entry_extract(&probe, a); 330 path = a->path; 331 len = tree_entry_len(a); 332 switch (check_entry_match(first, first_len, path, len)) { 333 case -1: 334 entry_clear(a); 335 case 0: 336 return; 337 default: 338 update_tree_entry(&probe); 339 break; 340 } 341 /* keep looking */ 342 } 343 entry_clear(a); 344} 345 346static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a) 347{ 348 if (t->d.entry.path == a->path) { 349 update_tree_entry(&t->d); 350 } else { 351 /* we have returned this entry early */ 352 struct tree_desc_skip *skip = xmalloc(sizeof(*skip)); 353 skip->ptr = a->path; 354 skip->prev = t->skip; 355 t->skip = skip; 356 } 357} 358 359static void free_extended_entry(struct tree_desc_x *t) 360{ 361 struct tree_desc_skip *p, *s; 362 363 for (s = t->skip; s; s = p) { 364 p = s->prev; 365 free(s); 366 } 367} 368 369static inline int prune_traversal(struct index_state *istate, 370 struct name_entry *e, 371 struct traverse_info *info, 372 struct strbuf *base, 373 int still_interesting) 374{ 375 if (!info->pathspec || still_interesting == 2) 376 return 2; 377 if (still_interesting < 0) 378 return still_interesting; 379 return tree_entry_interesting(istate, e, base, 380 0, info->pathspec); 381} 382 383int traverse_trees(struct index_state *istate, 384 int n, struct tree_desc *t, 385 struct traverse_info *info) 386{ 387 int error = 0; 388 struct name_entry *entry = xmalloc(n*sizeof(*entry)); 389 int i; 390 struct tree_desc_x *tx = xcalloc(n, sizeof(*tx)); 391 struct strbuf base = STRBUF_INIT; 392 int interesting = 1; 393 char *traverse_path; 394 395 for (i = 0; i < n; i++) 396 tx[i].d = t[i]; 397 398 if (info->prev) { 399 strbuf_grow(&base, info->pathlen); 400 make_traverse_path(base.buf, info->prev, &info->name); 401 base.buf[info->pathlen-1] = '/'; 402 strbuf_setlen(&base, info->pathlen); 403 traverse_path = xstrndup(base.buf, info->pathlen); 404 } else { 405 traverse_path = xstrndup(info->name.path, info->pathlen); 406 } 407 info->traverse_path = traverse_path; 408 for (;;) { 409 int trees_used; 410 unsigned long mask, dirmask; 411 const char *first = NULL; 412 int first_len = 0; 413 struct name_entry *e = NULL; 414 int len; 415 416 for (i = 0; i < n; i++) { 417 e = entry + i; 418 extended_entry_extract(tx + i, e, NULL, 0); 419 } 420 421 /* 422 * A tree may have "t-2" at the current location even 423 * though it may have "t" that is a subtree behind it, 424 * and another tree may return "t". We want to grab 425 * all "t" from all trees to match in such a case. 426 */ 427 for (i = 0; i < n; i++) { 428 e = entry + i; 429 if (!e->path) 430 continue; 431 len = tree_entry_len(e); 432 if (!first) { 433 first = e->path; 434 first_len = len; 435 continue; 436 } 437 if (name_compare(e->path, len, first, first_len) < 0) { 438 first = e->path; 439 first_len = len; 440 } 441 } 442 443 if (first) { 444 for (i = 0; i < n; i++) { 445 e = entry + i; 446 extended_entry_extract(tx + i, e, first, first_len); 447 /* Cull the ones that are not the earliest */ 448 if (!e->path) 449 continue; 450 len = tree_entry_len(e); 451 if (name_compare(e->path, len, first, first_len)) 452 entry_clear(e); 453 } 454 } 455 456 /* Now we have in entry[i] the earliest name from the trees */ 457 mask = 0; 458 dirmask = 0; 459 for (i = 0; i < n; i++) { 460 if (!entry[i].path) 461 continue; 462 mask |= 1ul << i; 463 if (S_ISDIR(entry[i].mode)) 464 dirmask |= 1ul << i; 465 e = &entry[i]; 466 } 467 if (!mask) 468 break; 469 interesting = prune_traversal(istate, e, info, &base, interesting); 470 if (interesting < 0) 471 break; 472 if (interesting) { 473 trees_used = info->fn(n, mask, dirmask, entry, info); 474 if (trees_used < 0) { 475 error = trees_used; 476 if (!info->show_all_errors) 477 break; 478 } 479 mask &= trees_used; 480 } 481 for (i = 0; i < n; i++) 482 if (mask & (1ul << i)) 483 update_extended_entry(tx + i, entry + i); 484 } 485 free(entry); 486 for (i = 0; i < n; i++) 487 free_extended_entry(tx + i); 488 free(tx); 489 free(traverse_path); 490 info->traverse_path = NULL; 491 strbuf_release(&base); 492 return error; 493} 494 495struct dir_state { 496 void *tree; 497 unsigned long size; 498 struct object_id oid; 499}; 500 501static int find_tree_entry(struct tree_desc *t, const char *name, struct object_id *result, unsigned short *mode) 502{ 503 int namelen = strlen(name); 504 while (t->size) { 505 const char *entry; 506 struct object_id oid; 507 int entrylen, cmp; 508 509 oidcpy(&oid, tree_entry_extract(t, &entry, mode)); 510 entrylen = tree_entry_len(&t->entry); 511 update_tree_entry(t); 512 if (entrylen > namelen) 513 continue; 514 cmp = memcmp(name, entry, entrylen); 515 if (cmp > 0) 516 continue; 517 if (cmp < 0) 518 break; 519 if (entrylen == namelen) { 520 oidcpy(result, &oid); 521 return 0; 522 } 523 if (name[entrylen] != '/') 524 continue; 525 if (!S_ISDIR(*mode)) 526 break; 527 if (++entrylen == namelen) { 528 oidcpy(result, &oid); 529 return 0; 530 } 531 return get_tree_entry(&oid, name + entrylen, result, mode); 532 } 533 return -1; 534} 535 536int get_tree_entry(const struct object_id *tree_oid, const char *name, struct object_id *oid, unsigned short *mode) 537{ 538 int retval; 539 void *tree; 540 unsigned long size; 541 struct object_id root; 542 543 tree = read_object_with_reference(tree_oid, tree_type, &size, &root); 544 if (!tree) 545 return -1; 546 547 if (name[0] == '\0') { 548 oidcpy(oid, &root); 549 free(tree); 550 return 0; 551 } 552 553 if (!size) { 554 retval = -1; 555 } else { 556 struct tree_desc t; 557 init_tree_desc(&t, tree, size); 558 retval = find_tree_entry(&t, name, oid, mode); 559 } 560 free(tree); 561 return retval; 562} 563 564/* 565 * This is Linux's built-in max for the number of symlinks to follow. 566 * That limit, of course, does not affect git, but it's a reasonable 567 * choice. 568 */ 569#define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40 570 571/** 572 * Find a tree entry by following symlinks in tree_sha (which is 573 * assumed to be the root of the repository). In the event that a 574 * symlink points outside the repository (e.g. a link to /foo or a 575 * root-level link to ../foo), the portion of the link which is 576 * outside the repository will be returned in result_path, and *mode 577 * will be set to 0. It is assumed that result_path is uninitialized. 578 * If there are no symlinks, or the end result of the symlink chain 579 * points to an object inside the repository, result will be filled in 580 * with the sha1 of the found object, and *mode will hold the mode of 581 * the object. 582 * 583 * See the code for enum get_oid_result for a description of 584 * the return values. 585 */ 586enum get_oid_result get_tree_entry_follow_symlinks(struct object_id *tree_oid, const char *name, struct object_id *result, struct strbuf *result_path, unsigned short *mode) 587{ 588 int retval = MISSING_OBJECT; 589 struct dir_state *parents = NULL; 590 size_t parents_alloc = 0; 591 size_t i, parents_nr = 0; 592 struct object_id current_tree_oid; 593 struct strbuf namebuf = STRBUF_INIT; 594 struct tree_desc t; 595 int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS; 596 597 init_tree_desc(&t, NULL, 0UL); 598 strbuf_addstr(&namebuf, name); 599 oidcpy(¤t_tree_oid, tree_oid); 600 601 while (1) { 602 int find_result; 603 char *first_slash; 604 char *remainder = NULL; 605 606 if (!t.buffer) { 607 void *tree; 608 struct object_id root; 609 unsigned long size; 610 tree = read_object_with_reference(¤t_tree_oid, 611 tree_type, &size, 612 &root); 613 if (!tree) 614 goto done; 615 616 ALLOC_GROW(parents, parents_nr + 1, parents_alloc); 617 parents[parents_nr].tree = tree; 618 parents[parents_nr].size = size; 619 oidcpy(&parents[parents_nr].oid, &root); 620 parents_nr++; 621 622 if (namebuf.buf[0] == '\0') { 623 oidcpy(result, &root); 624 retval = FOUND; 625 goto done; 626 } 627 628 if (!size) 629 goto done; 630 631 /* descend */ 632 init_tree_desc(&t, tree, size); 633 } 634 635 /* Handle symlinks to e.g. a//b by removing leading slashes */ 636 while (namebuf.buf[0] == '/') { 637 strbuf_remove(&namebuf, 0, 1); 638 } 639 640 /* Split namebuf into a first component and a remainder */ 641 if ((first_slash = strchr(namebuf.buf, '/'))) { 642 *first_slash = 0; 643 remainder = first_slash + 1; 644 } 645 646 if (!strcmp(namebuf.buf, "..")) { 647 struct dir_state *parent; 648 /* 649 * We could end up with .. in the namebuf if it 650 * appears in a symlink. 651 */ 652 653 if (parents_nr == 1) { 654 if (remainder) 655 *first_slash = '/'; 656 strbuf_add(result_path, namebuf.buf, 657 namebuf.len); 658 *mode = 0; 659 retval = FOUND; 660 goto done; 661 } 662 parent = &parents[parents_nr - 1]; 663 free(parent->tree); 664 parents_nr--; 665 parent = &parents[parents_nr - 1]; 666 init_tree_desc(&t, parent->tree, parent->size); 667 strbuf_remove(&namebuf, 0, remainder ? 3 : 2); 668 continue; 669 } 670 671 /* We could end up here via a symlink to dir/.. */ 672 if (namebuf.buf[0] == '\0') { 673 oidcpy(result, &parents[parents_nr - 1].oid); 674 retval = FOUND; 675 goto done; 676 } 677 678 /* Look up the first (or only) path component in the tree. */ 679 find_result = find_tree_entry(&t, namebuf.buf, 680 ¤t_tree_oid, mode); 681 if (find_result) { 682 goto done; 683 } 684 685 if (S_ISDIR(*mode)) { 686 if (!remainder) { 687 oidcpy(result, ¤t_tree_oid); 688 retval = FOUND; 689 goto done; 690 } 691 /* Descend the tree */ 692 t.buffer = NULL; 693 strbuf_remove(&namebuf, 0, 694 1 + first_slash - namebuf.buf); 695 } else if (S_ISREG(*mode)) { 696 if (!remainder) { 697 oidcpy(result, ¤t_tree_oid); 698 retval = FOUND; 699 } else { 700 retval = NOT_DIR; 701 } 702 goto done; 703 } else if (S_ISLNK(*mode)) { 704 /* Follow a symlink */ 705 unsigned long link_len; 706 size_t len; 707 char *contents, *contents_start; 708 struct dir_state *parent; 709 enum object_type type; 710 711 if (follows_remaining-- == 0) { 712 /* Too many symlinks followed */ 713 retval = SYMLINK_LOOP; 714 goto done; 715 } 716 717 /* 718 * At this point, we have followed at a least 719 * one symlink, so on error we need to report this. 720 */ 721 retval = DANGLING_SYMLINK; 722 723 contents = read_object_file(¤t_tree_oid, &type, 724 &link_len); 725 726 if (!contents) 727 goto done; 728 729 if (contents[0] == '/') { 730 strbuf_addstr(result_path, contents); 731 free(contents); 732 *mode = 0; 733 retval = FOUND; 734 goto done; 735 } 736 737 if (remainder) 738 len = first_slash - namebuf.buf; 739 else 740 len = namebuf.len; 741 742 contents_start = contents; 743 744 parent = &parents[parents_nr - 1]; 745 init_tree_desc(&t, parent->tree, parent->size); 746 strbuf_splice(&namebuf, 0, len, 747 contents_start, link_len); 748 if (remainder) 749 namebuf.buf[link_len] = '/'; 750 free(contents); 751 } 752 } 753done: 754 for (i = 0; i < parents_nr; i++) 755 free(parents[i].tree); 756 free(parents); 757 758 strbuf_release(&namebuf); 759 return retval; 760} 761 762static int match_entry(const struct pathspec_item *item, 763 const struct name_entry *entry, int pathlen, 764 const char *match, int matchlen, 765 enum interesting *never_interesting) 766{ 767 int m = -1; /* signals that we haven't called strncmp() */ 768 769 if (item->magic & PATHSPEC_ICASE) 770 /* 771 * "Never interesting" trick requires exact 772 * matching. We could do something clever with inexact 773 * matching, but it's trickier (and not to forget that 774 * strcasecmp is locale-dependent, at least in 775 * glibc). Just disable it for now. It can't be worse 776 * than the wildcard's codepath of '[Tt][Hi][Is][Ss]' 777 * pattern. 778 */ 779 *never_interesting = entry_not_interesting; 780 else if (*never_interesting != entry_not_interesting) { 781 /* 782 * We have not seen any match that sorts later 783 * than the current path. 784 */ 785 786 /* 787 * Does match sort strictly earlier than path 788 * with their common parts? 789 */ 790 m = strncmp(match, entry->path, 791 (matchlen < pathlen) ? matchlen : pathlen); 792 if (m < 0) 793 return 0; 794 795 /* 796 * If we come here even once, that means there is at 797 * least one pathspec that would sort equal to or 798 * later than the path we are currently looking at. 799 * In other words, if we have never reached this point 800 * after iterating all pathspecs, it means all 801 * pathspecs are either outside of base, or inside the 802 * base but sorts strictly earlier than the current 803 * one. In either case, they will never match the 804 * subsequent entries. In such a case, we initialized 805 * the variable to -1 and that is what will be 806 * returned, allowing the caller to terminate early. 807 */ 808 *never_interesting = entry_not_interesting; 809 } 810 811 if (pathlen > matchlen) 812 return 0; 813 814 if (matchlen > pathlen) { 815 if (match[pathlen] != '/') 816 return 0; 817 if (!S_ISDIR(entry->mode) && !S_ISGITLINK(entry->mode)) 818 return 0; 819 } 820 821 if (m == -1) 822 /* 823 * we cheated and did not do strncmp(), so we do 824 * that here. 825 */ 826 m = ps_strncmp(item, match, entry->path, pathlen); 827 828 /* 829 * If common part matched earlier then it is a hit, 830 * because we rejected the case where path is not a 831 * leading directory and is shorter than match. 832 */ 833 if (!m) 834 /* 835 * match_entry does not check if the prefix part is 836 * matched case-sensitively. If the entry is a 837 * directory and part of prefix, it'll be rematched 838 * eventually by basecmp with special treatment for 839 * the prefix. 840 */ 841 return 1; 842 843 return 0; 844} 845 846/* :(icase)-aware string compare */ 847static int basecmp(const struct pathspec_item *item, 848 const char *base, const char *match, int len) 849{ 850 if (item->magic & PATHSPEC_ICASE) { 851 int ret, n = len > item->prefix ? item->prefix : len; 852 ret = strncmp(base, match, n); 853 if (ret) 854 return ret; 855 base += n; 856 match += n; 857 len -= n; 858 } 859 return ps_strncmp(item, base, match, len); 860} 861 862static int match_dir_prefix(const struct pathspec_item *item, 863 const char *base, 864 const char *match, int matchlen) 865{ 866 if (basecmp(item, base, match, matchlen)) 867 return 0; 868 869 /* 870 * If the base is a subdirectory of a path which 871 * was specified, all of them are interesting. 872 */ 873 if (!matchlen || 874 base[matchlen] == '/' || 875 match[matchlen - 1] == '/') 876 return 1; 877 878 /* Just a random prefix match */ 879 return 0; 880} 881 882/* 883 * Perform matching on the leading non-wildcard part of 884 * pathspec. item->nowildcard_len must be greater than zero. Return 885 * non-zero if base is matched. 886 */ 887static int match_wildcard_base(const struct pathspec_item *item, 888 const char *base, int baselen, 889 int *matched) 890{ 891 const char *match = item->match; 892 /* the wildcard part is not considered in this function */ 893 int matchlen = item->nowildcard_len; 894 895 if (baselen) { 896 int dirlen; 897 /* 898 * Return early if base is longer than the 899 * non-wildcard part but it does not match. 900 */ 901 if (baselen >= matchlen) { 902 *matched = matchlen; 903 return !basecmp(item, base, match, matchlen); 904 } 905 906 dirlen = matchlen; 907 while (dirlen && match[dirlen - 1] != '/') 908 dirlen--; 909 910 /* 911 * Return early if base is shorter than the 912 * non-wildcard part but it does not match. Note that 913 * base ends with '/' so we are sure it really matches 914 * directory 915 */ 916 if (basecmp(item, base, match, baselen)) 917 return 0; 918 *matched = baselen; 919 } else 920 *matched = 0; 921 /* 922 * we could have checked entry against the non-wildcard part 923 * that is not in base and does similar never_interesting 924 * optimization as in match_entry. For now just be happy with 925 * base comparison. 926 */ 927 return entry_interesting; 928} 929 930/* 931 * Is a tree entry interesting given the pathspec we have? 932 * 933 * Pre-condition: either baselen == base_offset (i.e. empty path) 934 * or base[baselen-1] == '/' (i.e. with trailing slash). 935 */ 936static enum interesting do_match(struct index_state *istate, 937 const struct name_entry *entry, 938 struct strbuf *base, int base_offset, 939 const struct pathspec *ps, 940 int exclude) 941{ 942 int i; 943 int pathlen, baselen = base->len - base_offset; 944 enum interesting never_interesting = ps->has_wildcard ? 945 entry_not_interesting : all_entries_not_interesting; 946 947 GUARD_PATHSPEC(ps, 948 PATHSPEC_FROMTOP | 949 PATHSPEC_MAXDEPTH | 950 PATHSPEC_LITERAL | 951 PATHSPEC_GLOB | 952 PATHSPEC_ICASE | 953 PATHSPEC_EXCLUDE | 954 PATHSPEC_ATTR); 955 956 if (!ps->nr) { 957 if (!ps->recursive || 958 !(ps->magic & PATHSPEC_MAXDEPTH) || 959 ps->max_depth == -1) 960 return all_entries_interesting; 961 return within_depth(base->buf + base_offset, baselen, 962 !!S_ISDIR(entry->mode), 963 ps->max_depth) ? 964 entry_interesting : entry_not_interesting; 965 } 966 967 pathlen = tree_entry_len(entry); 968 969 for (i = ps->nr - 1; i >= 0; i--) { 970 const struct pathspec_item *item = ps->items+i; 971 const char *match = item->match; 972 const char *base_str = base->buf + base_offset; 973 int matchlen = item->len, matched = 0; 974 975 if ((!exclude && item->magic & PATHSPEC_EXCLUDE) || 976 ( exclude && !(item->magic & PATHSPEC_EXCLUDE))) 977 continue; 978 979 if (baselen >= matchlen) { 980 /* If it doesn't match, move along... */ 981 if (!match_dir_prefix(item, base_str, match, matchlen)) 982 goto match_wildcards; 983 984 if (!ps->recursive || 985 !(ps->magic & PATHSPEC_MAXDEPTH) || 986 ps->max_depth == -1) { 987 if (!item->attr_match_nr) 988 return all_entries_interesting; 989 else 990 goto interesting; 991 } 992 993 if (within_depth(base_str + matchlen + 1, 994 baselen - matchlen - 1, 995 !!S_ISDIR(entry->mode), 996 ps->max_depth)) 997 goto interesting; 998 else 999 return entry_not_interesting;1000 }10011002 /* Either there must be no base, or the base must match. */1003 if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {1004 if (match_entry(item, entry, pathlen,1005 match + baselen, matchlen - baselen,1006 &never_interesting))1007 goto interesting;10081009 if (item->nowildcard_len < item->len) {1010 if (!git_fnmatch(item, match + baselen, entry->path,1011 item->nowildcard_len - baselen))1012 goto interesting;10131014 /*1015 * Match all directories. We'll try to1016 * match files later on.1017 */1018 if (ps->recursive && S_ISDIR(entry->mode))1019 return entry_interesting;10201021 /*1022 * When matching against submodules with1023 * wildcard characters, ensure that the entry1024 * at least matches up to the first wild1025 * character. More accurate matching can then1026 * be performed in the submodule itself.1027 */1028 if (ps->recurse_submodules &&1029 S_ISGITLINK(entry->mode) &&1030 !ps_strncmp(item, match + baselen,1031 entry->path,1032 item->nowildcard_len - baselen))1033 goto interesting;1034 }10351036 continue;1037 }10381039match_wildcards:1040 if (item->nowildcard_len == item->len)1041 continue;10421043 if (item->nowildcard_len &&1044 !match_wildcard_base(item, base_str, baselen, &matched))1045 continue;10461047 /*1048 * Concatenate base and entry->path into one and do1049 * fnmatch() on it.1050 *1051 * While we could avoid concatenation in certain cases1052 * [1], which saves a memcpy and potentially a1053 * realloc, it turns out not worth it. Measurement on1054 * linux-2.6 does not show any clear improvements,1055 * partly because of the nowildcard_len optimization1056 * in git_fnmatch(). Avoid micro-optimizations here.1057 *1058 * [1] if match_wildcard_base() says the base1059 * directory is already matched, we only need to match1060 * the rest, which is shorter so _in theory_ faster.1061 */10621063 strbuf_add(base, entry->path, pathlen);10641065 if (!git_fnmatch(item, match, base->buf + base_offset,1066 item->nowildcard_len)) {1067 strbuf_setlen(base, base_offset + baselen);1068 goto interesting;1069 }10701071 /*1072 * When matching against submodules with1073 * wildcard characters, ensure that the entry1074 * at least matches up to the first wild1075 * character. More accurate matching can then1076 * be performed in the submodule itself.1077 */1078 if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&1079 !ps_strncmp(item, match, base->buf + base_offset,1080 item->nowildcard_len)) {1081 strbuf_setlen(base, base_offset + baselen);1082 goto interesting;1083 }10841085 strbuf_setlen(base, base_offset + baselen);10861087 /*1088 * Match all directories. We'll try to match files1089 * later on.1090 * max_depth is ignored but we may consider support it1091 * in future, see1092 * https://public-inbox.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/1093 */1094 if (ps->recursive && S_ISDIR(entry->mode))1095 return entry_interesting;1096 continue;1097interesting:1098 if (item->attr_match_nr) {1099 int ret;11001101 /*1102 * Must not return all_entries_not_interesting1103 * prematurely. We do not know if all entries do not1104 * match some attributes with current attr API.1105 */1106 never_interesting = entry_not_interesting;11071108 /*1109 * Consider all directories interesting (because some1110 * of those files inside may match some attributes1111 * even though the parent dir does not)1112 *1113 * FIXME: attributes _can_ match directories and we1114 * can probably return all_entries_interesting or1115 * all_entries_not_interesting here if matched.1116 */1117 if (S_ISDIR(entry->mode))1118 return entry_interesting;11191120 strbuf_add(base, entry->path, pathlen);1121 ret = match_pathspec_attrs(istate, base->buf + base_offset,1122 base->len - base_offset, item);1123 strbuf_setlen(base, base_offset + baselen);1124 if (!ret)1125 continue;1126 }1127 return entry_interesting;1128 }1129 return never_interesting; /* No matches */1130}11311132/*1133 * Is a tree entry interesting given the pathspec we have?1134 *1135 * Pre-condition: either baselen == base_offset (i.e. empty path)1136 * or base[baselen-1] == '/' (i.e. with trailing slash).1137 */1138enum interesting tree_entry_interesting(struct index_state *istate,1139 const struct name_entry *entry,1140 struct strbuf *base, int base_offset,1141 const struct pathspec *ps)1142{1143 enum interesting positive, negative;1144 positive = do_match(istate, entry, base, base_offset, ps, 0);11451146 /*1147 * case | entry | positive | negative | result1148 * -----+-------+----------+----------+-------1149 * 1 | file | -1 | -1..2 | -11150 * 2 | file | 0 | -1..2 | 01151 * 3 | file | 1 | -1 | 11152 * 4 | file | 1 | 0 | 11153 * 5 | file | 1 | 1 | 01154 * 6 | file | 1 | 2 | 01155 * 7 | file | 2 | -1 | 21156 * 8 | file | 2 | 0 | 11157 * 9 | file | 2 | 1 | 01158 * 10 | file | 2 | 2 | -11159 * -----+-------+----------+----------+-------1160 * 11 | dir | -1 | -1..2 | -11161 * 12 | dir | 0 | -1..2 | 01162 * 13 | dir | 1 | -1 | 11163 * 14 | dir | 1 | 0 | 11164 * 15 | dir | 1 | 1 | 1 (*)1165 * 16 | dir | 1 | 2 | 01166 * 17 | dir | 2 | -1 | 21167 * 18 | dir | 2 | 0 | 11168 * 19 | dir | 2 | 1 | 1 (*)1169 * 20 | dir | 2 | 2 | -11170 *1171 * (*) An exclude pattern interested in a directory does not1172 * necessarily mean it will exclude all of the directory. In1173 * wildcard case, it can't decide until looking at individual1174 * files inside. So don't write such directories off yet.1175 */11761177 if (!(ps->magic & PATHSPEC_EXCLUDE) ||1178 positive <= entry_not_interesting) /* #1, #2, #11, #12 */1179 return positive;11801181 negative = do_match(istate, entry, base, base_offset, ps, 1);11821183 /* #8, #18 */1184 if (positive == all_entries_interesting &&1185 negative == entry_not_interesting)1186 return entry_interesting;11871188 /* #3, #4, #7, #13, #14, #17 */1189 if (negative <= entry_not_interesting)1190 return positive;11911192 /* #15, #19 */1193 if (S_ISDIR(entry->mode) &&1194 positive >= entry_interesting &&1195 negative == entry_interesting)1196 return entry_interesting;11971198 if ((positive == entry_interesting &&1199 negative >= entry_interesting) || /* #5, #6, #16 */1200 (positive == all_entries_interesting &&1201 negative == entry_interesting)) /* #9 */1202 return entry_not_interesting;12031204 return all_entries_not_interesting; /* #10, #20 */1205}