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(the_repository, 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 hashcpy(info->name.oid.hash, (const unsigned char *)base + pathlen + 1); 182 info->prev = &dummy; 183 } 184} 185 186char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n) 187{ 188 int len = tree_entry_len(n); 189 int pathlen = info->pathlen; 190 191 path[pathlen + len] = 0; 192 for (;;) { 193 memcpy(path + pathlen, n->path, len); 194 if (!pathlen) 195 break; 196 path[--pathlen] = '/'; 197 n = &info->name; 198 len = tree_entry_len(n); 199 info = info->prev; 200 pathlen -= len; 201 } 202 return path; 203} 204 205struct tree_desc_skip { 206 struct tree_desc_skip *prev; 207 const void *ptr; 208}; 209 210struct tree_desc_x { 211 struct tree_desc d; 212 struct tree_desc_skip *skip; 213}; 214 215static int check_entry_match(const char *a, int a_len, const char *b, int b_len) 216{ 217 /* 218 * The caller wants to pick *a* from a tree or nothing. 219 * We are looking at *b* in a tree. 220 * 221 * (0) If a and b are the same name, we are trivially happy. 222 * 223 * There are three possibilities where *a* could be hiding 224 * behind *b*. 225 * 226 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no 227 * matter what. 228 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree; 229 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree. 230 * 231 * Otherwise we know *a* won't appear in the tree without 232 * scanning further. 233 */ 234 235 int cmp = name_compare(a, a_len, b, b_len); 236 237 /* Most common case first -- reading sync'd trees */ 238 if (!cmp) 239 return cmp; 240 241 if (0 < cmp) { 242 /* a comes after b; it does not matter if it is case (3) 243 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/') 244 return 1; 245 */ 246 return 1; /* keep looking */ 247 } 248 249 /* b comes after a; are we looking at case (2)? */ 250 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/') 251 return 1; /* keep looking */ 252 253 return -1; /* a cannot appear in the tree */ 254} 255 256/* 257 * From the extended tree_desc, extract the first name entry, while 258 * paying attention to the candidate "first" name. Most importantly, 259 * when looking for an entry, if there are entries that sorts earlier 260 * in the tree object representation than that name, skip them and 261 * process the named entry first. We will remember that we haven't 262 * processed the first entry yet, and in the later call skip the 263 * entry we processed early when update_extended_entry() is called. 264 * 265 * E.g. if the underlying tree object has these entries: 266 * 267 * blob "t-1" 268 * blob "t-2" 269 * tree "t" 270 * blob "t=1" 271 * 272 * and the "first" asks for "t", remember that we still need to 273 * process "t-1" and "t-2" but extract "t". After processing the 274 * entry "t" from this call, the caller will let us know by calling 275 * update_extended_entry() that we can remember "t" has been processed 276 * already. 277 */ 278 279static void extended_entry_extract(struct tree_desc_x *t, 280 struct name_entry *a, 281 const char *first, 282 int first_len) 283{ 284 const char *path; 285 int len; 286 struct tree_desc probe; 287 struct tree_desc_skip *skip; 288 289 /* 290 * Extract the first entry from the tree_desc, but skip the 291 * ones that we already returned in earlier rounds. 292 */ 293 while (1) { 294 if (!t->d.size) { 295 entry_clear(a); 296 break; /* not found */ 297 } 298 entry_extract(&t->d, a); 299 for (skip = t->skip; skip; skip = skip->prev) 300 if (a->path == skip->ptr) 301 break; /* found */ 302 if (!skip) 303 break; 304 /* We have processed this entry already. */ 305 update_tree_entry(&t->d); 306 } 307 308 if (!first || !a->path) 309 return; 310 311 /* 312 * The caller wants "first" from this tree, or nothing. 313 */ 314 path = a->path; 315 len = tree_entry_len(a); 316 switch (check_entry_match(first, first_len, path, len)) { 317 case -1: 318 entry_clear(a); 319 case 0: 320 return; 321 default: 322 break; 323 } 324 325 /* 326 * We need to look-ahead -- we suspect that a subtree whose 327 * name is "first" may be hiding behind the current entry "path". 328 */ 329 probe = t->d; 330 while (probe.size) { 331 entry_extract(&probe, a); 332 path = a->path; 333 len = tree_entry_len(a); 334 switch (check_entry_match(first, first_len, path, len)) { 335 case -1: 336 entry_clear(a); 337 case 0: 338 return; 339 default: 340 update_tree_entry(&probe); 341 break; 342 } 343 /* keep looking */ 344 } 345 entry_clear(a); 346} 347 348static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a) 349{ 350 if (t->d.entry.path == a->path) { 351 update_tree_entry(&t->d); 352 } else { 353 /* we have returned this entry early */ 354 struct tree_desc_skip *skip = xmalloc(sizeof(*skip)); 355 skip->ptr = a->path; 356 skip->prev = t->skip; 357 t->skip = skip; 358 } 359} 360 361static void free_extended_entry(struct tree_desc_x *t) 362{ 363 struct tree_desc_skip *p, *s; 364 365 for (s = t->skip; s; s = p) { 366 p = s->prev; 367 free(s); 368 } 369} 370 371static inline int prune_traversal(struct index_state *istate, 372 struct name_entry *e, 373 struct traverse_info *info, 374 struct strbuf *base, 375 int still_interesting) 376{ 377 if (!info->pathspec || still_interesting == 2) 378 return 2; 379 if (still_interesting < 0) 380 return still_interesting; 381 return tree_entry_interesting(istate, e, base, 382 0, info->pathspec); 383} 384 385int traverse_trees(struct index_state *istate, 386 int n, struct tree_desc *t, 387 struct traverse_info *info) 388{ 389 int error = 0; 390 struct name_entry *entry = xmalloc(n*sizeof(*entry)); 391 int i; 392 struct tree_desc_x *tx = xcalloc(n, sizeof(*tx)); 393 struct strbuf base = STRBUF_INIT; 394 int interesting = 1; 395 char *traverse_path; 396 397 for (i = 0; i < n; i++) 398 tx[i].d = t[i]; 399 400 if (info->prev) { 401 strbuf_grow(&base, info->pathlen); 402 make_traverse_path(base.buf, info->prev, &info->name); 403 base.buf[info->pathlen-1] = '/'; 404 strbuf_setlen(&base, info->pathlen); 405 traverse_path = xstrndup(base.buf, info->pathlen); 406 } else { 407 traverse_path = xstrndup(info->name.path, info->pathlen); 408 } 409 info->traverse_path = traverse_path; 410 for (;;) { 411 int trees_used; 412 unsigned long mask, dirmask; 413 const char *first = NULL; 414 int first_len = 0; 415 struct name_entry *e = NULL; 416 int len; 417 418 for (i = 0; i < n; i++) { 419 e = entry + i; 420 extended_entry_extract(tx + i, e, NULL, 0); 421 } 422 423 /* 424 * A tree may have "t-2" at the current location even 425 * though it may have "t" that is a subtree behind it, 426 * and another tree may return "t". We want to grab 427 * all "t" from all trees to match in such a case. 428 */ 429 for (i = 0; i < n; i++) { 430 e = entry + i; 431 if (!e->path) 432 continue; 433 len = tree_entry_len(e); 434 if (!first) { 435 first = e->path; 436 first_len = len; 437 continue; 438 } 439 if (name_compare(e->path, len, first, first_len) < 0) { 440 first = e->path; 441 first_len = len; 442 } 443 } 444 445 if (first) { 446 for (i = 0; i < n; i++) { 447 e = entry + i; 448 extended_entry_extract(tx + i, e, first, first_len); 449 /* Cull the ones that are not the earliest */ 450 if (!e->path) 451 continue; 452 len = tree_entry_len(e); 453 if (name_compare(e->path, len, first, first_len)) 454 entry_clear(e); 455 } 456 } 457 458 /* Now we have in entry[i] the earliest name from the trees */ 459 mask = 0; 460 dirmask = 0; 461 for (i = 0; i < n; i++) { 462 if (!entry[i].path) 463 continue; 464 mask |= 1ul << i; 465 if (S_ISDIR(entry[i].mode)) 466 dirmask |= 1ul << i; 467 e = &entry[i]; 468 } 469 if (!mask) 470 break; 471 interesting = prune_traversal(istate, e, info, &base, interesting); 472 if (interesting < 0) 473 break; 474 if (interesting) { 475 trees_used = info->fn(n, mask, dirmask, entry, info); 476 if (trees_used < 0) { 477 error = trees_used; 478 if (!info->show_all_errors) 479 break; 480 } 481 mask &= trees_used; 482 } 483 for (i = 0; i < n; i++) 484 if (mask & (1ul << i)) 485 update_extended_entry(tx + i, entry + i); 486 } 487 free(entry); 488 for (i = 0; i < n; i++) 489 free_extended_entry(tx + i); 490 free(tx); 491 free(traverse_path); 492 info->traverse_path = NULL; 493 strbuf_release(&base); 494 return error; 495} 496 497struct dir_state { 498 void *tree; 499 unsigned long size; 500 struct object_id oid; 501}; 502 503static int find_tree_entry(struct tree_desc *t, const char *name, struct object_id *result, unsigned short *mode) 504{ 505 int namelen = strlen(name); 506 while (t->size) { 507 const char *entry; 508 struct object_id oid; 509 int entrylen, cmp; 510 511 oidcpy(&oid, tree_entry_extract(t, &entry, mode)); 512 entrylen = tree_entry_len(&t->entry); 513 update_tree_entry(t); 514 if (entrylen > namelen) 515 continue; 516 cmp = memcmp(name, entry, entrylen); 517 if (cmp > 0) 518 continue; 519 if (cmp < 0) 520 break; 521 if (entrylen == namelen) { 522 oidcpy(result, &oid); 523 return 0; 524 } 525 if (name[entrylen] != '/') 526 continue; 527 if (!S_ISDIR(*mode)) 528 break; 529 if (++entrylen == namelen) { 530 oidcpy(result, &oid); 531 return 0; 532 } 533 return get_tree_entry(&oid, name + entrylen, result, mode); 534 } 535 return -1; 536} 537 538int get_tree_entry(const struct object_id *tree_oid, const char *name, struct object_id *oid, unsigned short *mode) 539{ 540 int retval; 541 void *tree; 542 unsigned long size; 543 struct object_id root; 544 545 tree = read_object_with_reference(the_repository, tree_oid, tree_type, &size, &root); 546 if (!tree) 547 return -1; 548 549 if (name[0] == '\0') { 550 oidcpy(oid, &root); 551 free(tree); 552 return 0; 553 } 554 555 if (!size) { 556 retval = -1; 557 } else { 558 struct tree_desc t; 559 init_tree_desc(&t, tree, size); 560 retval = find_tree_entry(&t, name, oid, mode); 561 } 562 free(tree); 563 return retval; 564} 565 566/* 567 * This is Linux's built-in max for the number of symlinks to follow. 568 * That limit, of course, does not affect git, but it's a reasonable 569 * choice. 570 */ 571#define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40 572 573/** 574 * Find a tree entry by following symlinks in tree_sha (which is 575 * assumed to be the root of the repository). In the event that a 576 * symlink points outside the repository (e.g. a link to /foo or a 577 * root-level link to ../foo), the portion of the link which is 578 * outside the repository will be returned in result_path, and *mode 579 * will be set to 0. It is assumed that result_path is uninitialized. 580 * If there are no symlinks, or the end result of the symlink chain 581 * points to an object inside the repository, result will be filled in 582 * with the sha1 of the found object, and *mode will hold the mode of 583 * the object. 584 * 585 * See the code for enum get_oid_result for a description of 586 * the return values. 587 */ 588enum 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) 589{ 590 int retval = MISSING_OBJECT; 591 struct dir_state *parents = NULL; 592 size_t parents_alloc = 0; 593 size_t i, parents_nr = 0; 594 struct object_id current_tree_oid; 595 struct strbuf namebuf = STRBUF_INIT; 596 struct tree_desc t; 597 int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS; 598 599 init_tree_desc(&t, NULL, 0UL); 600 strbuf_addstr(&namebuf, name); 601 oidcpy(¤t_tree_oid, tree_oid); 602 603 while (1) { 604 int find_result; 605 char *first_slash; 606 char *remainder = NULL; 607 608 if (!t.buffer) { 609 void *tree; 610 struct object_id root; 611 unsigned long size; 612 tree = read_object_with_reference(the_repository, 613 ¤t_tree_oid, 614 tree_type, &size, 615 &root); 616 if (!tree) 617 goto done; 618 619 ALLOC_GROW(parents, parents_nr + 1, parents_alloc); 620 parents[parents_nr].tree = tree; 621 parents[parents_nr].size = size; 622 oidcpy(&parents[parents_nr].oid, &root); 623 parents_nr++; 624 625 if (namebuf.buf[0] == '\0') { 626 oidcpy(result, &root); 627 retval = FOUND; 628 goto done; 629 } 630 631 if (!size) 632 goto done; 633 634 /* descend */ 635 init_tree_desc(&t, tree, size); 636 } 637 638 /* Handle symlinks to e.g. a//b by removing leading slashes */ 639 while (namebuf.buf[0] == '/') { 640 strbuf_remove(&namebuf, 0, 1); 641 } 642 643 /* Split namebuf into a first component and a remainder */ 644 if ((first_slash = strchr(namebuf.buf, '/'))) { 645 *first_slash = 0; 646 remainder = first_slash + 1; 647 } 648 649 if (!strcmp(namebuf.buf, "..")) { 650 struct dir_state *parent; 651 /* 652 * We could end up with .. in the namebuf if it 653 * appears in a symlink. 654 */ 655 656 if (parents_nr == 1) { 657 if (remainder) 658 *first_slash = '/'; 659 strbuf_add(result_path, namebuf.buf, 660 namebuf.len); 661 *mode = 0; 662 retval = FOUND; 663 goto done; 664 } 665 parent = &parents[parents_nr - 1]; 666 free(parent->tree); 667 parents_nr--; 668 parent = &parents[parents_nr - 1]; 669 init_tree_desc(&t, parent->tree, parent->size); 670 strbuf_remove(&namebuf, 0, remainder ? 3 : 2); 671 continue; 672 } 673 674 /* We could end up here via a symlink to dir/.. */ 675 if (namebuf.buf[0] == '\0') { 676 oidcpy(result, &parents[parents_nr - 1].oid); 677 retval = FOUND; 678 goto done; 679 } 680 681 /* Look up the first (or only) path component in the tree. */ 682 find_result = find_tree_entry(&t, namebuf.buf, 683 ¤t_tree_oid, mode); 684 if (find_result) { 685 goto done; 686 } 687 688 if (S_ISDIR(*mode)) { 689 if (!remainder) { 690 oidcpy(result, ¤t_tree_oid); 691 retval = FOUND; 692 goto done; 693 } 694 /* Descend the tree */ 695 t.buffer = NULL; 696 strbuf_remove(&namebuf, 0, 697 1 + first_slash - namebuf.buf); 698 } else if (S_ISREG(*mode)) { 699 if (!remainder) { 700 oidcpy(result, ¤t_tree_oid); 701 retval = FOUND; 702 } else { 703 retval = NOT_DIR; 704 } 705 goto done; 706 } else if (S_ISLNK(*mode)) { 707 /* Follow a symlink */ 708 unsigned long link_len; 709 size_t len; 710 char *contents, *contents_start; 711 struct dir_state *parent; 712 enum object_type type; 713 714 if (follows_remaining-- == 0) { 715 /* Too many symlinks followed */ 716 retval = SYMLINK_LOOP; 717 goto done; 718 } 719 720 /* 721 * At this point, we have followed at a least 722 * one symlink, so on error we need to report this. 723 */ 724 retval = DANGLING_SYMLINK; 725 726 contents = read_object_file(¤t_tree_oid, &type, 727 &link_len); 728 729 if (!contents) 730 goto done; 731 732 if (contents[0] == '/') { 733 strbuf_addstr(result_path, contents); 734 free(contents); 735 *mode = 0; 736 retval = FOUND; 737 goto done; 738 } 739 740 if (remainder) 741 len = first_slash - namebuf.buf; 742 else 743 len = namebuf.len; 744 745 contents_start = contents; 746 747 parent = &parents[parents_nr - 1]; 748 init_tree_desc(&t, parent->tree, parent->size); 749 strbuf_splice(&namebuf, 0, len, 750 contents_start, link_len); 751 if (remainder) 752 namebuf.buf[link_len] = '/'; 753 free(contents); 754 } 755 } 756done: 757 for (i = 0; i < parents_nr; i++) 758 free(parents[i].tree); 759 free(parents); 760 761 strbuf_release(&namebuf); 762 return retval; 763} 764 765static int match_entry(const struct pathspec_item *item, 766 const struct name_entry *entry, int pathlen, 767 const char *match, int matchlen, 768 enum interesting *never_interesting) 769{ 770 int m = -1; /* signals that we haven't called strncmp() */ 771 772 if (item->magic & PATHSPEC_ICASE) 773 /* 774 * "Never interesting" trick requires exact 775 * matching. We could do something clever with inexact 776 * matching, but it's trickier (and not to forget that 777 * strcasecmp is locale-dependent, at least in 778 * glibc). Just disable it for now. It can't be worse 779 * than the wildcard's codepath of '[Tt][Hi][Is][Ss]' 780 * pattern. 781 */ 782 *never_interesting = entry_not_interesting; 783 else if (*never_interesting != entry_not_interesting) { 784 /* 785 * We have not seen any match that sorts later 786 * than the current path. 787 */ 788 789 /* 790 * Does match sort strictly earlier than path 791 * with their common parts? 792 */ 793 m = strncmp(match, entry->path, 794 (matchlen < pathlen) ? matchlen : pathlen); 795 if (m < 0) 796 return 0; 797 798 /* 799 * If we come here even once, that means there is at 800 * least one pathspec that would sort equal to or 801 * later than the path we are currently looking at. 802 * In other words, if we have never reached this point 803 * after iterating all pathspecs, it means all 804 * pathspecs are either outside of base, or inside the 805 * base but sorts strictly earlier than the current 806 * one. In either case, they will never match the 807 * subsequent entries. In such a case, we initialized 808 * the variable to -1 and that is what will be 809 * returned, allowing the caller to terminate early. 810 */ 811 *never_interesting = entry_not_interesting; 812 } 813 814 if (pathlen > matchlen) 815 return 0; 816 817 if (matchlen > pathlen) { 818 if (match[pathlen] != '/') 819 return 0; 820 if (!S_ISDIR(entry->mode) && !S_ISGITLINK(entry->mode)) 821 return 0; 822 } 823 824 if (m == -1) 825 /* 826 * we cheated and did not do strncmp(), so we do 827 * that here. 828 */ 829 m = ps_strncmp(item, match, entry->path, pathlen); 830 831 /* 832 * If common part matched earlier then it is a hit, 833 * because we rejected the case where path is not a 834 * leading directory and is shorter than match. 835 */ 836 if (!m) 837 /* 838 * match_entry does not check if the prefix part is 839 * matched case-sensitively. If the entry is a 840 * directory and part of prefix, it'll be rematched 841 * eventually by basecmp with special treatment for 842 * the prefix. 843 */ 844 return 1; 845 846 return 0; 847} 848 849/* :(icase)-aware string compare */ 850static int basecmp(const struct pathspec_item *item, 851 const char *base, const char *match, int len) 852{ 853 if (item->magic & PATHSPEC_ICASE) { 854 int ret, n = len > item->prefix ? item->prefix : len; 855 ret = strncmp(base, match, n); 856 if (ret) 857 return ret; 858 base += n; 859 match += n; 860 len -= n; 861 } 862 return ps_strncmp(item, base, match, len); 863} 864 865static int match_dir_prefix(const struct pathspec_item *item, 866 const char *base, 867 const char *match, int matchlen) 868{ 869 if (basecmp(item, base, match, matchlen)) 870 return 0; 871 872 /* 873 * If the base is a subdirectory of a path which 874 * was specified, all of them are interesting. 875 */ 876 if (!matchlen || 877 base[matchlen] == '/' || 878 match[matchlen - 1] == '/') 879 return 1; 880 881 /* Just a random prefix match */ 882 return 0; 883} 884 885/* 886 * Perform matching on the leading non-wildcard part of 887 * pathspec. item->nowildcard_len must be greater than zero. Return 888 * non-zero if base is matched. 889 */ 890static int match_wildcard_base(const struct pathspec_item *item, 891 const char *base, int baselen, 892 int *matched) 893{ 894 const char *match = item->match; 895 /* the wildcard part is not considered in this function */ 896 int matchlen = item->nowildcard_len; 897 898 if (baselen) { 899 int dirlen; 900 /* 901 * Return early if base is longer than the 902 * non-wildcard part but it does not match. 903 */ 904 if (baselen >= matchlen) { 905 *matched = matchlen; 906 return !basecmp(item, base, match, matchlen); 907 } 908 909 dirlen = matchlen; 910 while (dirlen && match[dirlen - 1] != '/') 911 dirlen--; 912 913 /* 914 * Return early if base is shorter than the 915 * non-wildcard part but it does not match. Note that 916 * base ends with '/' so we are sure it really matches 917 * directory 918 */ 919 if (basecmp(item, base, match, baselen)) 920 return 0; 921 *matched = baselen; 922 } else 923 *matched = 0; 924 /* 925 * we could have checked entry against the non-wildcard part 926 * that is not in base and does similar never_interesting 927 * optimization as in match_entry. For now just be happy with 928 * base comparison. 929 */ 930 return entry_interesting; 931} 932 933/* 934 * Is a tree entry interesting given the pathspec we have? 935 * 936 * Pre-condition: either baselen == base_offset (i.e. empty path) 937 * or base[baselen-1] == '/' (i.e. with trailing slash). 938 */ 939static enum interesting do_match(struct index_state *istate, 940 const struct name_entry *entry, 941 struct strbuf *base, int base_offset, 942 const struct pathspec *ps, 943 int exclude) 944{ 945 int i; 946 int pathlen, baselen = base->len - base_offset; 947 enum interesting never_interesting = ps->has_wildcard ? 948 entry_not_interesting : all_entries_not_interesting; 949 950 GUARD_PATHSPEC(ps, 951 PATHSPEC_FROMTOP | 952 PATHSPEC_MAXDEPTH | 953 PATHSPEC_LITERAL | 954 PATHSPEC_GLOB | 955 PATHSPEC_ICASE | 956 PATHSPEC_EXCLUDE | 957 PATHSPEC_ATTR); 958 959 if (!ps->nr) { 960 if (!ps->recursive || 961 !(ps->magic & PATHSPEC_MAXDEPTH) || 962 ps->max_depth == -1) 963 return all_entries_interesting; 964 return within_depth(base->buf + base_offset, baselen, 965 !!S_ISDIR(entry->mode), 966 ps->max_depth) ? 967 entry_interesting : entry_not_interesting; 968 } 969 970 pathlen = tree_entry_len(entry); 971 972 for (i = ps->nr - 1; i >= 0; i--) { 973 const struct pathspec_item *item = ps->items+i; 974 const char *match = item->match; 975 const char *base_str = base->buf + base_offset; 976 int matchlen = item->len, matched = 0; 977 978 if ((!exclude && item->magic & PATHSPEC_EXCLUDE) || 979 ( exclude && !(item->magic & PATHSPEC_EXCLUDE))) 980 continue; 981 982 if (baselen >= matchlen) { 983 /* If it doesn't match, move along... */ 984 if (!match_dir_prefix(item, base_str, match, matchlen)) 985 goto match_wildcards; 986 987 if (!ps->recursive || 988 !(ps->magic & PATHSPEC_MAXDEPTH) || 989 ps->max_depth == -1) { 990 if (!item->attr_match_nr) 991 return all_entries_interesting; 992 else 993 goto interesting; 994 } 995 996 if (within_depth(base_str + matchlen + 1, 997 baselen - matchlen - 1, 998 !!S_ISDIR(entry->mode), 999 ps->max_depth))1000 goto interesting;1001 else1002 return entry_not_interesting;1003 }10041005 /* Either there must be no base, or the base must match. */1006 if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {1007 if (match_entry(item, entry, pathlen,1008 match + baselen, matchlen - baselen,1009 &never_interesting))1010 goto interesting;10111012 if (item->nowildcard_len < item->len) {1013 if (!git_fnmatch(item, match + baselen, entry->path,1014 item->nowildcard_len - baselen))1015 goto interesting;10161017 /*1018 * Match all directories. We'll try to1019 * match files later on.1020 */1021 if (ps->recursive && S_ISDIR(entry->mode))1022 return entry_interesting;10231024 /*1025 * When matching against submodules with1026 * wildcard characters, ensure that the entry1027 * at least matches up to the first wild1028 * character. More accurate matching can then1029 * be performed in the submodule itself.1030 */1031 if (ps->recurse_submodules &&1032 S_ISGITLINK(entry->mode) &&1033 !ps_strncmp(item, match + baselen,1034 entry->path,1035 item->nowildcard_len - baselen))1036 goto interesting;1037 }10381039 continue;1040 }10411042match_wildcards:1043 if (item->nowildcard_len == item->len)1044 continue;10451046 if (item->nowildcard_len &&1047 !match_wildcard_base(item, base_str, baselen, &matched))1048 continue;10491050 /*1051 * Concatenate base and entry->path into one and do1052 * fnmatch() on it.1053 *1054 * While we could avoid concatenation in certain cases1055 * [1], which saves a memcpy and potentially a1056 * realloc, it turns out not worth it. Measurement on1057 * linux-2.6 does not show any clear improvements,1058 * partly because of the nowildcard_len optimization1059 * in git_fnmatch(). Avoid micro-optimizations here.1060 *1061 * [1] if match_wildcard_base() says the base1062 * directory is already matched, we only need to match1063 * the rest, which is shorter so _in theory_ faster.1064 */10651066 strbuf_add(base, entry->path, pathlen);10671068 if (!git_fnmatch(item, match, base->buf + base_offset,1069 item->nowildcard_len)) {1070 strbuf_setlen(base, base_offset + baselen);1071 goto interesting;1072 }10731074 /*1075 * When matching against submodules with1076 * wildcard characters, ensure that the entry1077 * at least matches up to the first wild1078 * character. More accurate matching can then1079 * be performed in the submodule itself.1080 */1081 if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&1082 !ps_strncmp(item, match, base->buf + base_offset,1083 item->nowildcard_len)) {1084 strbuf_setlen(base, base_offset + baselen);1085 goto interesting;1086 }10871088 strbuf_setlen(base, base_offset + baselen);10891090 /*1091 * Match all directories. We'll try to match files1092 * later on.1093 * max_depth is ignored but we may consider support it1094 * in future, see1095 * https://public-inbox.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/1096 */1097 if (ps->recursive && S_ISDIR(entry->mode))1098 return entry_interesting;1099 continue;1100interesting:1101 if (item->attr_match_nr) {1102 int ret;11031104 /*1105 * Must not return all_entries_not_interesting1106 * prematurely. We do not know if all entries do not1107 * match some attributes with current attr API.1108 */1109 never_interesting = entry_not_interesting;11101111 /*1112 * Consider all directories interesting (because some1113 * of those files inside may match some attributes1114 * even though the parent dir does not)1115 *1116 * FIXME: attributes _can_ match directories and we1117 * can probably return all_entries_interesting or1118 * all_entries_not_interesting here if matched.1119 */1120 if (S_ISDIR(entry->mode))1121 return entry_interesting;11221123 strbuf_add(base, entry->path, pathlen);1124 ret = match_pathspec_attrs(istate, base->buf + base_offset,1125 base->len - base_offset, item);1126 strbuf_setlen(base, base_offset + baselen);1127 if (!ret)1128 continue;1129 }1130 return entry_interesting;1131 }1132 return never_interesting; /* No matches */1133}11341135/*1136 * Is a tree entry interesting given the pathspec we have?1137 *1138 * Pre-condition: either baselen == base_offset (i.e. empty path)1139 * or base[baselen-1] == '/' (i.e. with trailing slash).1140 */1141enum interesting tree_entry_interesting(struct index_state *istate,1142 const struct name_entry *entry,1143 struct strbuf *base, int base_offset,1144 const struct pathspec *ps)1145{1146 enum interesting positive, negative;1147 positive = do_match(istate, entry, base, base_offset, ps, 0);11481149 /*1150 * case | entry | positive | negative | result1151 * -----+-------+----------+----------+-------1152 * 1 | file | -1 | -1..2 | -11153 * 2 | file | 0 | -1..2 | 01154 * 3 | file | 1 | -1 | 11155 * 4 | file | 1 | 0 | 11156 * 5 | file | 1 | 1 | 01157 * 6 | file | 1 | 2 | 01158 * 7 | file | 2 | -1 | 21159 * 8 | file | 2 | 0 | 11160 * 9 | file | 2 | 1 | 01161 * 10 | file | 2 | 2 | -11162 * -----+-------+----------+----------+-------1163 * 11 | dir | -1 | -1..2 | -11164 * 12 | dir | 0 | -1..2 | 01165 * 13 | dir | 1 | -1 | 11166 * 14 | dir | 1 | 0 | 11167 * 15 | dir | 1 | 1 | 1 (*)1168 * 16 | dir | 1 | 2 | 01169 * 17 | dir | 2 | -1 | 21170 * 18 | dir | 2 | 0 | 11171 * 19 | dir | 2 | 1 | 1 (*)1172 * 20 | dir | 2 | 2 | -11173 *1174 * (*) An exclude pattern interested in a directory does not1175 * necessarily mean it will exclude all of the directory. In1176 * wildcard case, it can't decide until looking at individual1177 * files inside. So don't write such directories off yet.1178 */11791180 if (!(ps->magic & PATHSPEC_EXCLUDE) ||1181 positive <= entry_not_interesting) /* #1, #2, #11, #12 */1182 return positive;11831184 negative = do_match(istate, entry, base, base_offset, ps, 1);11851186 /* #8, #18 */1187 if (positive == all_entries_interesting &&1188 negative == entry_not_interesting)1189 return entry_interesting;11901191 /* #3, #4, #7, #13, #14, #17 */1192 if (negative <= entry_not_interesting)1193 return positive;11941195 /* #15, #19 */1196 if (S_ISDIR(entry->mode) &&1197 positive >= entry_interesting &&1198 negative == entry_interesting)1199 return entry_interesting;12001201 if ((positive == entry_interesting &&1202 negative >= entry_interesting) || /* #5, #6, #16 */1203 (positive == all_entries_interesting &&1204 negative == entry_interesting)) /* #9 */1205 return entry_not_interesting;12061207 return all_entries_not_interesting; /* #10, #20 */1208}