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 tree_desc *desc,const struct object_id *oid) 85{ 86unsigned long size =0; 87void*buf = NULL; 88 89if(oid) { 90 buf =read_object_with_reference(oid, tree_type, &size, NULL); 91if(!buf) 92die("unable to read tree%s",oid_to_hex(oid)); 93} 94init_tree_desc(desc, buf, size); 95return buf; 96} 97 98static voidentry_clear(struct name_entry *a) 99{ 100memset(a,0,sizeof(*a)); 101} 102 103static voidentry_extract(struct tree_desc *t,struct name_entry *a) 104{ 105*a = t->entry; 106} 107 108static intupdate_tree_entry_internal(struct tree_desc *desc,struct strbuf *err) 109{ 110const void*buf = desc->buffer; 111const unsigned char*end = (const unsigned char*)desc->entry.path + desc->entry.pathlen +1+ the_hash_algo->rawsz; 112unsigned long size = desc->size; 113unsigned long len = end - (const unsigned char*)buf; 114 115if(size < len) 116die(_("too-short tree file")); 117 buf = end; 118 size -= len; 119 desc->buffer = buf; 120 desc->size = size; 121if(size) 122returndecode_tree_entry(desc, buf, size, err); 123return0; 124} 125 126voidupdate_tree_entry(struct tree_desc *desc) 127{ 128struct strbuf err = STRBUF_INIT; 129if(update_tree_entry_internal(desc, &err)) 130die("%s", err.buf); 131strbuf_release(&err); 132} 133 134intupdate_tree_entry_gently(struct tree_desc *desc) 135{ 136struct strbuf err = STRBUF_INIT; 137if(update_tree_entry_internal(desc, &err)) { 138error("%s", err.buf); 139strbuf_release(&err); 140/* Stop processing this tree after error */ 141 desc->size =0; 142return-1; 143} 144strbuf_release(&err); 145return0; 146} 147 148inttree_entry(struct tree_desc *desc,struct name_entry *entry) 149{ 150if(!desc->size) 151return0; 152 153*entry = desc->entry; 154update_tree_entry(desc); 155return1; 156} 157 158inttree_entry_gently(struct tree_desc *desc,struct name_entry *entry) 159{ 160if(!desc->size) 161return0; 162 163*entry = desc->entry; 164if(update_tree_entry_gently(desc)) 165return0; 166return1; 167} 168 169voidsetup_traverse_info(struct traverse_info *info,const char*base) 170{ 171int pathlen =strlen(base); 172static struct traverse_info dummy; 173 174memset(info,0,sizeof(*info)); 175if(pathlen && base[pathlen-1] =='/') 176 pathlen--; 177 info->pathlen = pathlen ? pathlen +1:0; 178 info->name.path = base; 179 info->name.pathlen = pathlen; 180if(pathlen) 181 info->prev = &dummy; 182} 183 184char*make_traverse_path(char*path,const struct traverse_info *info,const struct name_entry *n) 185{ 186int len =tree_entry_len(n); 187int pathlen = info->pathlen; 188 189 path[pathlen + len] =0; 190for(;;) { 191memcpy(path + pathlen, n->path, len); 192if(!pathlen) 193break; 194 path[--pathlen] ='/'; 195 n = &info->name; 196 len =tree_entry_len(n); 197 info = info->prev; 198 pathlen -= len; 199} 200return path; 201} 202 203struct tree_desc_skip { 204struct tree_desc_skip *prev; 205const void*ptr; 206}; 207 208struct tree_desc_x { 209struct tree_desc d; 210struct tree_desc_skip *skip; 211}; 212 213static intcheck_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 233int cmp =name_compare(a, a_len, b, b_len); 234 235/* Most common case first -- reading sync'd trees */ 236if(!cmp) 237return cmp; 238 239if(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 */ 244return1;/* keep looking */ 245} 246 247/* b comes after a; are we looking at case (2)? */ 248if(a_len < b_len && !memcmp(a, b, a_len) && b[a_len] <'/') 249return1;/* keep looking */ 250 251return-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 voidextended_entry_extract(struct tree_desc_x *t, 278struct name_entry *a, 279const char*first, 280int first_len) 281{ 282const char*path; 283int len; 284struct tree_desc probe; 285struct 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 */ 291while(1) { 292if(!t->d.size) { 293entry_clear(a); 294break;/* not found */ 295} 296entry_extract(&t->d, a); 297for(skip = t->skip; skip; skip = skip->prev) 298if(a->path == skip->ptr) 299break;/* found */ 300if(!skip) 301break; 302/* We have processed this entry already. */ 303update_tree_entry(&t->d); 304} 305 306if(!first || !a->path) 307return; 308 309/* 310 * The caller wants "first" from this tree, or nothing. 311 */ 312 path = a->path; 313 len =tree_entry_len(a); 314switch(check_entry_match(first, first_len, path, len)) { 315case-1: 316entry_clear(a); 317case0: 318return; 319default: 320break; 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; 328while(probe.size) { 329entry_extract(&probe, a); 330 path = a->path; 331 len =tree_entry_len(a); 332switch(check_entry_match(first, first_len, path, len)) { 333case-1: 334entry_clear(a); 335case0: 336return; 337default: 338update_tree_entry(&probe); 339break; 340} 341/* keep looking */ 342} 343entry_clear(a); 344} 345 346static voidupdate_extended_entry(struct tree_desc_x *t,struct name_entry *a) 347{ 348if(t->d.entry.path == a->path) { 349update_tree_entry(&t->d); 350}else{ 351/* we have returned this entry early */ 352struct 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 voidfree_extended_entry(struct tree_desc_x *t) 360{ 361struct tree_desc_skip *p, *s; 362 363for(s = t->skip; s; s = p) { 364 p = s->prev; 365free(s); 366} 367} 368 369staticinlineintprune_traversal(struct index_state *istate, 370struct name_entry *e, 371struct traverse_info *info, 372struct strbuf *base, 373int still_interesting) 374{ 375if(!info->pathspec || still_interesting ==2) 376return2; 377if(still_interesting <0) 378return still_interesting; 379returntree_entry_interesting(istate, e, base, 3800, info->pathspec); 381} 382 383inttraverse_trees(struct index_state *istate, 384int n,struct tree_desc *t, 385struct traverse_info *info) 386{ 387int error =0; 388struct name_entry *entry =xmalloc(n*sizeof(*entry)); 389int i; 390struct tree_desc_x *tx =xcalloc(n,sizeof(*tx)); 391struct strbuf base = STRBUF_INIT; 392int interesting =1; 393char*traverse_path; 394 395for(i =0; i < n; i++) 396 tx[i].d = t[i]; 397 398if(info->prev) { 399strbuf_grow(&base, info->pathlen); 400make_traverse_path(base.buf, info->prev, &info->name); 401 base.buf[info->pathlen-1] ='/'; 402strbuf_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; 408for(;;) { 409int trees_used; 410unsigned long mask, dirmask; 411const char*first = NULL; 412int first_len =0; 413struct name_entry *e = NULL; 414int len; 415 416for(i =0; i < n; i++) { 417 e = entry + i; 418extended_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 */ 427for(i =0; i < n; i++) { 428 e = entry + i; 429if(!e->path) 430continue; 431 len =tree_entry_len(e); 432if(!first) { 433 first = e->path; 434 first_len = len; 435continue; 436} 437if(name_compare(e->path, len, first, first_len) <0) { 438 first = e->path; 439 first_len = len; 440} 441} 442 443if(first) { 444for(i =0; i < n; i++) { 445 e = entry + i; 446extended_entry_extract(tx + i, e, first, first_len); 447/* Cull the ones that are not the earliest */ 448if(!e->path) 449continue; 450 len =tree_entry_len(e); 451if(name_compare(e->path, len, first, first_len)) 452entry_clear(e); 453} 454} 455 456/* Now we have in entry[i] the earliest name from the trees */ 457 mask =0; 458 dirmask =0; 459for(i =0; i < n; i++) { 460if(!entry[i].path) 461continue; 462 mask |=1ul<< i; 463if(S_ISDIR(entry[i].mode)) 464 dirmask |=1ul<< i; 465 e = &entry[i]; 466} 467if(!mask) 468break; 469 interesting =prune_traversal(istate, e, info, &base, interesting); 470if(interesting <0) 471break; 472if(interesting) { 473 trees_used = info->fn(n, mask, dirmask, entry, info); 474if(trees_used <0) { 475 error = trees_used; 476if(!info->show_all_errors) 477break; 478} 479 mask &= trees_used; 480} 481for(i =0; i < n; i++) 482if(mask & (1ul<< i)) 483update_extended_entry(tx + i, entry + i); 484} 485free(entry); 486for(i =0; i < n; i++) 487free_extended_entry(tx + i); 488free(tx); 489free(traverse_path); 490 info->traverse_path = NULL; 491strbuf_release(&base); 492return error; 493} 494 495struct dir_state { 496void*tree; 497unsigned long size; 498struct object_id oid; 499}; 500 501static intfind_tree_entry(struct tree_desc *t,const char*name,struct object_id *result,unsigned short*mode) 502{ 503int namelen =strlen(name); 504while(t->size) { 505const char*entry; 506struct object_id oid; 507int entrylen, cmp; 508 509oidcpy(&oid,tree_entry_extract(t, &entry, mode)); 510 entrylen =tree_entry_len(&t->entry); 511update_tree_entry(t); 512if(entrylen > namelen) 513continue; 514 cmp =memcmp(name, entry, entrylen); 515if(cmp >0) 516continue; 517if(cmp <0) 518break; 519if(entrylen == namelen) { 520oidcpy(result, &oid); 521return0; 522} 523if(name[entrylen] !='/') 524continue; 525if(!S_ISDIR(*mode)) 526break; 527if(++entrylen == namelen) { 528oidcpy(result, &oid); 529return0; 530} 531returnget_tree_entry(&oid, name + entrylen, result, mode); 532} 533return-1; 534} 535 536intget_tree_entry(const struct object_id *tree_oid,const char*name,struct object_id *oid,unsigned short*mode) 537{ 538int retval; 539void*tree; 540unsigned long size; 541struct object_id root; 542 543 tree =read_object_with_reference(tree_oid, tree_type, &size, &root); 544if(!tree) 545return-1; 546 547if(name[0] =='\0') { 548oidcpy(oid, &root); 549free(tree); 550return0; 551} 552 553if(!size) { 554 retval = -1; 555}else{ 556struct tree_desc t; 557init_tree_desc(&t, tree, size); 558 retval =find_tree_entry(&t, name, oid, mode); 559} 560free(tree); 561return 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{ 588int retval = MISSING_OBJECT; 589struct dir_state *parents = NULL; 590size_t parents_alloc =0; 591size_t i, parents_nr =0; 592struct object_id current_tree_oid; 593struct strbuf namebuf = STRBUF_INIT; 594struct tree_desc t; 595int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS; 596 597init_tree_desc(&t, NULL,0UL); 598strbuf_addstr(&namebuf, name); 599oidcpy(¤t_tree_oid, tree_oid); 600 601while(1) { 602int find_result; 603char*first_slash; 604char*remainder = NULL; 605 606if(!t.buffer) { 607void*tree; 608struct object_id root; 609unsigned long size; 610 tree =read_object_with_reference(¤t_tree_oid, 611 tree_type, &size, 612&root); 613if(!tree) 614goto done; 615 616ALLOC_GROW(parents, parents_nr +1, parents_alloc); 617 parents[parents_nr].tree = tree; 618 parents[parents_nr].size = size; 619oidcpy(&parents[parents_nr].oid, &root); 620 parents_nr++; 621 622if(namebuf.buf[0] =='\0') { 623oidcpy(result, &root); 624 retval = FOUND; 625goto done; 626} 627 628if(!size) 629goto done; 630 631/* descend */ 632init_tree_desc(&t, tree, size); 633} 634 635/* Handle symlinks to e.g. a//b by removing leading slashes */ 636while(namebuf.buf[0] =='/') { 637strbuf_remove(&namebuf,0,1); 638} 639 640/* Split namebuf into a first component and a remainder */ 641if((first_slash =strchr(namebuf.buf,'/'))) { 642*first_slash =0; 643 remainder = first_slash +1; 644} 645 646if(!strcmp(namebuf.buf,"..")) { 647struct dir_state *parent; 648/* 649 * We could end up with .. in the namebuf if it 650 * appears in a symlink. 651 */ 652 653if(parents_nr ==1) { 654if(remainder) 655*first_slash ='/'; 656strbuf_add(result_path, namebuf.buf, 657 namebuf.len); 658*mode =0; 659 retval = FOUND; 660goto done; 661} 662 parent = &parents[parents_nr -1]; 663free(parent->tree); 664 parents_nr--; 665 parent = &parents[parents_nr -1]; 666init_tree_desc(&t, parent->tree, parent->size); 667strbuf_remove(&namebuf,0, remainder ?3:2); 668continue; 669} 670 671/* We could end up here via a symlink to dir/.. */ 672if(namebuf.buf[0] =='\0') { 673oidcpy(result, &parents[parents_nr -1].oid); 674 retval = FOUND; 675goto 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); 681if(find_result) { 682goto done; 683} 684 685if(S_ISDIR(*mode)) { 686if(!remainder) { 687oidcpy(result, ¤t_tree_oid); 688 retval = FOUND; 689goto done; 690} 691/* Descend the tree */ 692 t.buffer = NULL; 693strbuf_remove(&namebuf,0, 6941+ first_slash - namebuf.buf); 695}else if(S_ISREG(*mode)) { 696if(!remainder) { 697oidcpy(result, ¤t_tree_oid); 698 retval = FOUND; 699}else{ 700 retval = NOT_DIR; 701} 702goto done; 703}else if(S_ISLNK(*mode)) { 704/* Follow a symlink */ 705unsigned long link_len; 706size_t len; 707char*contents, *contents_start; 708struct dir_state *parent; 709enum object_type type; 710 711if(follows_remaining-- ==0) { 712/* Too many symlinks followed */ 713 retval = SYMLINK_LOOP; 714goto 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 726if(!contents) 727goto done; 728 729if(contents[0] =='/') { 730strbuf_addstr(result_path, contents); 731free(contents); 732*mode =0; 733 retval = FOUND; 734goto done; 735} 736 737if(remainder) 738 len = first_slash - namebuf.buf; 739else 740 len = namebuf.len; 741 742 contents_start = contents; 743 744 parent = &parents[parents_nr -1]; 745init_tree_desc(&t, parent->tree, parent->size); 746strbuf_splice(&namebuf,0, len, 747 contents_start, link_len); 748if(remainder) 749 namebuf.buf[link_len] ='/'; 750free(contents); 751} 752} 753done: 754for(i =0; i < parents_nr; i++) 755free(parents[i].tree); 756free(parents); 757 758strbuf_release(&namebuf); 759return retval; 760} 761 762static intmatch_entry(const struct pathspec_item *item, 763const struct name_entry *entry,int pathlen, 764const char*match,int matchlen, 765enum interesting *never_interesting) 766{ 767int m = -1;/* signals that we haven't called strncmp() */ 768 769if(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; 780else 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); 792if(m <0) 793return0; 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 811if(pathlen > matchlen) 812return0; 813 814if(matchlen > pathlen) { 815if(match[pathlen] !='/') 816return0; 817if(!S_ISDIR(entry->mode) && !S_ISGITLINK(entry->mode)) 818return0; 819} 820 821if(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 */ 833if(!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 */ 841return1; 842 843return0; 844} 845 846/* :(icase)-aware string compare */ 847static intbasecmp(const struct pathspec_item *item, 848const char*base,const char*match,int len) 849{ 850if(item->magic & PATHSPEC_ICASE) { 851int ret, n = len > item->prefix ? item->prefix : len; 852 ret =strncmp(base, match, n); 853if(ret) 854return ret; 855 base += n; 856 match += n; 857 len -= n; 858} 859returnps_strncmp(item, base, match, len); 860} 861 862static intmatch_dir_prefix(const struct pathspec_item *item, 863const char*base, 864const char*match,int matchlen) 865{ 866if(basecmp(item, base, match, matchlen)) 867return0; 868 869/* 870 * If the base is a subdirectory of a path which 871 * was specified, all of them are interesting. 872 */ 873if(!matchlen || 874 base[matchlen] =='/'|| 875 match[matchlen -1] =='/') 876return1; 877 878/* Just a random prefix match */ 879return0; 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 intmatch_wildcard_base(const struct pathspec_item *item, 888const char*base,int baselen, 889int*matched) 890{ 891const char*match = item->match; 892/* the wildcard part is not considered in this function */ 893int matchlen = item->nowildcard_len; 894 895if(baselen) { 896int dirlen; 897/* 898 * Return early if base is longer than the 899 * non-wildcard part but it does not match. 900 */ 901if(baselen >= matchlen) { 902*matched = matchlen; 903return!basecmp(item, base, match, matchlen); 904} 905 906 dirlen = matchlen; 907while(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 */ 916if(basecmp(item, base, match, baselen)) 917return0; 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 */ 927return 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, 937const struct name_entry *entry, 938struct strbuf *base,int base_offset, 939const struct pathspec *ps, 940int exclude) 941{ 942int i; 943int pathlen, baselen = base->len - base_offset; 944enum interesting never_interesting = ps->has_wildcard ? 945 entry_not_interesting : all_entries_not_interesting; 946 947GUARD_PATHSPEC(ps, 948 PATHSPEC_FROMTOP | 949 PATHSPEC_MAXDEPTH | 950 PATHSPEC_LITERAL | 951 PATHSPEC_GLOB | 952 PATHSPEC_ICASE | 953 PATHSPEC_EXCLUDE | 954 PATHSPEC_ATTR); 955 956if(!ps->nr) { 957if(!ps->recursive || 958!(ps->magic & PATHSPEC_MAXDEPTH) || 959 ps->max_depth == -1) 960return all_entries_interesting; 961returnwithin_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 969for(i = ps->nr -1; i >=0; i--) { 970const struct pathspec_item *item = ps->items+i; 971const char*match = item->match; 972const char*base_str = base->buf + base_offset; 973int matchlen = item->len, matched =0; 974 975if((!exclude && item->magic & PATHSPEC_EXCLUDE) || 976( exclude && !(item->magic & PATHSPEC_EXCLUDE))) 977continue; 978 979if(baselen >= matchlen) { 980/* If it doesn't match, move along... */ 981if(!match_dir_prefix(item, base_str, match, matchlen)) 982goto match_wildcards; 983 984if(!ps->recursive || 985!(ps->magic & PATHSPEC_MAXDEPTH) || 986 ps->max_depth == -1) { 987if(!item->attr_match_nr) 988return all_entries_interesting; 989else 990goto interesting; 991} 992 993if(within_depth(base_str + matchlen +1, 994 baselen - matchlen -1, 995!!S_ISDIR(entry->mode), 996 ps->max_depth)) 997goto interesting; 998else 999return entry_not_interesting;1000}10011002/* Either there must be no base, or the base must match. */1003if(baselen ==0|| !basecmp(item, base_str, match, baselen)) {1004if(match_entry(item, entry, pathlen,1005 match + baselen, matchlen - baselen,1006&never_interesting))1007goto interesting;10081009if(item->nowildcard_len < item->len) {1010if(!git_fnmatch(item, match + baselen, entry->path,1011 item->nowildcard_len - baselen))1012goto interesting;10131014/*1015 * Match all directories. We'll try to1016 * match files later on.1017 */1018if(ps->recursive &&S_ISDIR(entry->mode))1019return 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 */1028if(ps->recurse_submodules &&1029S_ISGITLINK(entry->mode) &&1030!ps_strncmp(item, match + baselen,1031 entry->path,1032 item->nowildcard_len - baselen))1033goto interesting;1034}10351036continue;1037}10381039match_wildcards:1040if(item->nowildcard_len == item->len)1041continue;10421043if(item->nowildcard_len &&1044!match_wildcard_base(item, base_str, baselen, &matched))1045continue;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 */10621063strbuf_add(base, entry->path, pathlen);10641065if(!git_fnmatch(item, match, base->buf + base_offset,1066 item->nowildcard_len)) {1067strbuf_setlen(base, base_offset + baselen);1068goto 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 */1078if(ps->recurse_submodules &&S_ISGITLINK(entry->mode) &&1079!ps_strncmp(item, match, base->buf + base_offset,1080 item->nowildcard_len)) {1081strbuf_setlen(base, base_offset + baselen);1082goto interesting;1083}10841085strbuf_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 */1094if(ps->recursive &&S_ISDIR(entry->mode))1095return entry_interesting;1096continue;1097interesting:1098if(item->attr_match_nr) {1099int 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 */1117if(S_ISDIR(entry->mode))1118return entry_interesting;11191120strbuf_add(base, entry->path, pathlen);1121 ret =match_pathspec_attrs(istate, base->buf + base_offset,1122 base->len - base_offset, item);1123strbuf_setlen(base, base_offset + baselen);1124if(!ret)1125continue;1126}1127return entry_interesting;1128}1129return 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,1139const struct name_entry *entry,1140struct strbuf *base,int base_offset,1141const struct pathspec *ps)1142{1143enum 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 */11761177if(!(ps->magic & PATHSPEC_EXCLUDE) ||1178 positive <= entry_not_interesting)/* #1, #2, #11, #12 */1179return positive;11801181 negative =do_match(istate, entry, base, base_offset, ps,1);11821183/* #8, #18 */1184if(positive == all_entries_interesting &&1185 negative == entry_not_interesting)1186return entry_interesting;11871188/* #3, #4, #7, #13, #14, #17 */1189if(negative <= entry_not_interesting)1190return positive;11911192/* #15, #19 */1193if(S_ISDIR(entry->mode) &&1194 positive >= entry_interesting &&1195 negative == entry_interesting)1196return entry_interesting;11971198if((positive == entry_interesting &&1199 negative >= entry_interesting) ||/* #5, #6, #16 */1200(positive == all_entries_interesting &&1201 negative == entry_interesting))/* #9 */1202return entry_not_interesting;12031204return all_entries_not_interesting;/* #10, #20 */1205}