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