1#include"cache.h" 2#include"tree-walk.h" 3#include"unpack-trees.h" 4#include"dir.h" 5#include"tree.h" 6 7static const char*get_mode(const char*str,unsigned int*modep) 8{ 9unsigned char c; 10unsigned int mode =0; 11 12if(*str ==' ') 13return NULL; 14 15while((c = *str++) !=' ') { 16if(c <'0'|| c >'7') 17return NULL; 18 mode = (mode <<3) + (c -'0'); 19} 20*modep = mode; 21return str; 22} 23 24static voiddecode_tree_entry(struct tree_desc *desc,const char*buf,unsigned long size) 25{ 26const char*path; 27unsigned int mode, len; 28 29if(size <24|| buf[size -21]) 30die("corrupt tree file"); 31 32 path =get_mode(buf, &mode); 33if(!path || !*path) 34die("corrupt tree file"); 35 len =strlen(path) +1; 36 37/* Initialize the descriptor entry */ 38 desc->entry.path = path; 39 desc->entry.mode = mode; 40 desc->entry.sha1 = (const unsigned char*)(path + len); 41} 42 43voidinit_tree_desc(struct tree_desc *desc,const void*buffer,unsigned long size) 44{ 45 desc->buffer = buffer; 46 desc->size = size; 47if(size) 48decode_tree_entry(desc, buffer, size); 49} 50 51void*fill_tree_descriptor(struct tree_desc *desc,const unsigned char*sha1) 52{ 53unsigned long size =0; 54void*buf = NULL; 55 56if(sha1) { 57 buf =read_object_with_reference(sha1, tree_type, &size, NULL); 58if(!buf) 59die("unable to read tree%s",sha1_to_hex(sha1)); 60} 61init_tree_desc(desc, buf, size); 62return buf; 63} 64 65static voidentry_clear(struct name_entry *a) 66{ 67memset(a,0,sizeof(*a)); 68} 69 70static voidentry_extract(struct tree_desc *t,struct name_entry *a) 71{ 72*a = t->entry; 73} 74 75voidupdate_tree_entry(struct tree_desc *desc) 76{ 77const void*buf = desc->buffer; 78const unsigned char*end = desc->entry.sha1 +20; 79unsigned long size = desc->size; 80unsigned long len = end - (const unsigned char*)buf; 81 82if(size < len) 83die("corrupt tree file"); 84 buf = end; 85 size -= len; 86 desc->buffer = buf; 87 desc->size = size; 88if(size) 89decode_tree_entry(desc, buf, size); 90} 91 92inttree_entry(struct tree_desc *desc,struct name_entry *entry) 93{ 94if(!desc->size) 95return0; 96 97*entry = desc->entry; 98update_tree_entry(desc); 99return1; 100} 101 102voidsetup_traverse_info(struct traverse_info *info,const char*base) 103{ 104int pathlen =strlen(base); 105static struct traverse_info dummy; 106 107memset(info,0,sizeof(*info)); 108if(pathlen && base[pathlen-1] =='/') 109 pathlen--; 110 info->pathlen = pathlen ? pathlen +1:0; 111 info->name.path = base; 112 info->name.sha1 = (void*)(base + pathlen +1); 113if(pathlen) 114 info->prev = &dummy; 115} 116 117char*make_traverse_path(char*path,const struct traverse_info *info,const struct name_entry *n) 118{ 119int len =tree_entry_len(n->path, n->sha1); 120int pathlen = info->pathlen; 121 122 path[pathlen + len] =0; 123for(;;) { 124memcpy(path + pathlen, n->path, len); 125if(!pathlen) 126break; 127 path[--pathlen] ='/'; 128 n = &info->name; 129 len =tree_entry_len(n->path, n->sha1); 130 info = info->prev; 131 pathlen -= len; 132} 133return path; 134} 135 136struct tree_desc_skip { 137struct tree_desc_skip *prev; 138const void*ptr; 139}; 140 141struct tree_desc_x { 142struct tree_desc d; 143struct tree_desc_skip *skip; 144}; 145 146static intname_compare(const char*a,int a_len, 147const char*b,int b_len) 148{ 149int len = (a_len < b_len) ? a_len : b_len; 150int cmp =memcmp(a, b, len); 151if(cmp) 152return cmp; 153return(a_len - b_len); 154} 155 156static intcheck_entry_match(const char*a,int a_len,const char*b,int b_len) 157{ 158/* 159 * The caller wants to pick *a* from a tree or nothing. 160 * We are looking at *b* in a tree. 161 * 162 * (0) If a and b are the same name, we are trivially happy. 163 * 164 * There are three possibilities where *a* could be hiding 165 * behind *b*. 166 * 167 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no 168 * matter what. 169 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree; 170 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree. 171 * 172 * Otherwise we know *a* won't appear in the tree without 173 * scanning further. 174 */ 175 176int cmp =name_compare(a, a_len, b, b_len); 177 178/* Most common case first -- reading sync'd trees */ 179if(!cmp) 180return cmp; 181 182if(0< cmp) { 183/* a comes after b; it does not matter if it is case (3) 184 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/') 185 return 1; 186 */ 187return1;/* keep looking */ 188} 189 190/* b comes after a; are we looking at case (2)? */ 191if(a_len < b_len && !memcmp(a, b, a_len) && b[a_len] <'/') 192return1;/* keep looking */ 193 194return-1;/* a cannot appear in the tree */ 195} 196 197/* 198 * From the extended tree_desc, extract the first name entry, while 199 * paying attention to the candidate "first" name. Most importantly, 200 * when looking for an entry, if there are entries that sorts earlier 201 * in the tree object representation than that name, skip them and 202 * process the named entry first. We will remember that we haven't 203 * processed the first entry yet, and in the later call skip the 204 * entry we processed early when update_extended_entry() is called. 205 * 206 * E.g. if the underlying tree object has these entries: 207 * 208 * blob "t-1" 209 * blob "t-2" 210 * tree "t" 211 * blob "t=1" 212 * 213 * and the "first" asks for "t", remember that we still need to 214 * process "t-1" and "t-2" but extract "t". After processing the 215 * entry "t" from this call, the caller will let us know by calling 216 * update_extended_entry() that we can remember "t" has been processed 217 * already. 218 */ 219 220static voidextended_entry_extract(struct tree_desc_x *t, 221struct name_entry *a, 222const char*first, 223int first_len) 224{ 225const char*path; 226int len; 227struct tree_desc probe; 228struct tree_desc_skip *skip; 229 230/* 231 * Extract the first entry from the tree_desc, but skip the 232 * ones that we already returned in earlier rounds. 233 */ 234while(1) { 235if(!t->d.size) { 236entry_clear(a); 237break;/* not found */ 238} 239entry_extract(&t->d, a); 240for(skip = t->skip; skip; skip = skip->prev) 241if(a->path == skip->ptr) 242break;/* found */ 243if(!skip) 244break; 245/* We have processed this entry already. */ 246update_tree_entry(&t->d); 247} 248 249if(!first || !a->path) 250return; 251 252/* 253 * The caller wants "first" from this tree, or nothing. 254 */ 255 path = a->path; 256 len =tree_entry_len(a->path, a->sha1); 257switch(check_entry_match(first, first_len, path, len)) { 258case-1: 259entry_clear(a); 260case0: 261return; 262default: 263break; 264} 265 266/* 267 * We need to look-ahead -- we suspect that a subtree whose 268 * name is "first" may be hiding behind the current entry "path". 269 */ 270 probe = t->d; 271while(probe.size) { 272entry_extract(&probe, a); 273 path = a->path; 274 len =tree_entry_len(a->path, a->sha1); 275switch(check_entry_match(first, first_len, path, len)) { 276case-1: 277entry_clear(a); 278case0: 279return; 280default: 281update_tree_entry(&probe); 282break; 283} 284/* keep looking */ 285} 286entry_clear(a); 287} 288 289static voidupdate_extended_entry(struct tree_desc_x *t,struct name_entry *a) 290{ 291if(t->d.entry.path == a->path) { 292update_tree_entry(&t->d); 293}else{ 294/* we have returned this entry early */ 295struct tree_desc_skip *skip =xmalloc(sizeof(*skip)); 296 skip->ptr = a->path; 297 skip->prev = t->skip; 298 t->skip = skip; 299} 300} 301 302static voidfree_extended_entry(struct tree_desc_x *t) 303{ 304struct tree_desc_skip *p, *s; 305 306for(s = t->skip; s; s = p) { 307 p = s->prev; 308free(s); 309} 310} 311 312staticinlineintprune_traversal(struct name_entry *e, 313struct traverse_info *info, 314struct strbuf *base, 315int still_interesting) 316{ 317if(!info->pathspec || still_interesting ==2) 318return2; 319if(still_interesting <0) 320return still_interesting; 321returntree_entry_interesting(e, base,0, info->pathspec); 322} 323 324inttraverse_trees(int n,struct tree_desc *t,struct traverse_info *info) 325{ 326int ret =0; 327int error =0; 328struct name_entry *entry =xmalloc(n*sizeof(*entry)); 329int i; 330struct tree_desc_x *tx =xcalloc(n,sizeof(*tx)); 331struct strbuf base = STRBUF_INIT; 332int interesting =1; 333 334for(i =0; i < n; i++) 335 tx[i].d = t[i]; 336 337if(info->prev) { 338strbuf_grow(&base, info->pathlen); 339make_traverse_path(base.buf, info->prev, &info->name); 340 base.buf[info->pathlen-1] ='/'; 341strbuf_setlen(&base, info->pathlen); 342} 343for(;;) { 344unsigned long mask, dirmask; 345const char*first = NULL; 346int first_len =0; 347struct name_entry *e = NULL; 348int len; 349 350for(i =0; i < n; i++) { 351 e = entry + i; 352extended_entry_extract(tx + i, e, NULL,0); 353} 354 355/* 356 * A tree may have "t-2" at the current location even 357 * though it may have "t" that is a subtree behind it, 358 * and another tree may return "t". We want to grab 359 * all "t" from all trees to match in such a case. 360 */ 361for(i =0; i < n; i++) { 362 e = entry + i; 363if(!e->path) 364continue; 365 len =tree_entry_len(e->path, e->sha1); 366if(!first) { 367 first = e->path; 368 first_len = len; 369continue; 370} 371if(name_compare(e->path, len, first, first_len) <0) { 372 first = e->path; 373 first_len = len; 374} 375} 376 377if(first) { 378for(i =0; i < n; i++) { 379 e = entry + i; 380extended_entry_extract(tx + i, e, first, first_len); 381/* Cull the ones that are not the earliest */ 382if(!e->path) 383continue; 384 len =tree_entry_len(e->path, e->sha1); 385if(name_compare(e->path, len, first, first_len)) 386entry_clear(e); 387} 388} 389 390/* Now we have in entry[i] the earliest name from the trees */ 391 mask =0; 392 dirmask =0; 393for(i =0; i < n; i++) { 394if(!entry[i].path) 395continue; 396 mask |=1ul<< i; 397if(S_ISDIR(entry[i].mode)) 398 dirmask |=1ul<< i; 399 e = &entry[i]; 400} 401if(!mask) 402break; 403 interesting =prune_traversal(e, info, &base, interesting); 404if(interesting <0) 405break; 406if(interesting) { 407 ret = info->fn(n, mask, dirmask, entry, info); 408if(ret <0) { 409 error = ret; 410if(!info->show_all_errors) 411break; 412} 413 mask &= ret; 414} 415 ret =0; 416for(i =0; i < n; i++) 417if(mask & (1ul<< i)) 418update_extended_entry(tx + i, entry + i); 419} 420free(entry); 421for(i =0; i < n; i++) 422free_extended_entry(tx + i); 423free(tx); 424strbuf_release(&base); 425return error; 426} 427 428static intfind_tree_entry(struct tree_desc *t,const char*name,unsigned char*result,unsigned*mode) 429{ 430int namelen =strlen(name); 431while(t->size) { 432const char*entry; 433const unsigned char*sha1; 434int entrylen, cmp; 435 436 sha1 =tree_entry_extract(t, &entry, mode); 437update_tree_entry(t); 438 entrylen =tree_entry_len(entry, sha1); 439if(entrylen > namelen) 440continue; 441 cmp =memcmp(name, entry, entrylen); 442if(cmp >0) 443continue; 444if(cmp <0) 445break; 446if(entrylen == namelen) { 447hashcpy(result, sha1); 448return0; 449} 450if(name[entrylen] !='/') 451continue; 452if(!S_ISDIR(*mode)) 453break; 454if(++entrylen == namelen) { 455hashcpy(result, sha1); 456return0; 457} 458returnget_tree_entry(sha1, name + entrylen, result, mode); 459} 460return-1; 461} 462 463intget_tree_entry(const unsigned char*tree_sha1,const char*name,unsigned char*sha1,unsigned*mode) 464{ 465int retval; 466void*tree; 467unsigned long size; 468struct tree_desc t; 469unsigned char root[20]; 470 471 tree =read_object_with_reference(tree_sha1, tree_type, &size, root); 472if(!tree) 473return-1; 474 475if(name[0] =='\0') { 476hashcpy(sha1, root); 477free(tree); 478return0; 479} 480 481init_tree_desc(&t, tree, size); 482 retval =find_tree_entry(&t, name, sha1, mode); 483free(tree); 484return retval; 485} 486 487static intmatch_entry(const struct name_entry *entry,int pathlen, 488const char*match,int matchlen, 489int*never_interesting) 490{ 491int m = -1;/* signals that we haven't called strncmp() */ 492 493if(*never_interesting) { 494/* 495 * We have not seen any match that sorts later 496 * than the current path. 497 */ 498 499/* 500 * Does match sort strictly earlier than path 501 * with their common parts? 502 */ 503 m =strncmp(match, entry->path, 504(matchlen < pathlen) ? matchlen : pathlen); 505if(m <0) 506return0; 507 508/* 509 * If we come here even once, that means there is at 510 * least one pathspec that would sort equal to or 511 * later than the path we are currently looking at. 512 * In other words, if we have never reached this point 513 * after iterating all pathspecs, it means all 514 * pathspecs are either outside of base, or inside the 515 * base but sorts strictly earlier than the current 516 * one. In either case, they will never match the 517 * subsequent entries. In such a case, we initialized 518 * the variable to -1 and that is what will be 519 * returned, allowing the caller to terminate early. 520 */ 521*never_interesting =0; 522} 523 524if(pathlen > matchlen) 525return0; 526 527if(matchlen > pathlen) { 528if(match[pathlen] !='/') 529return0; 530if(!S_ISDIR(entry->mode)) 531return0; 532} 533 534if(m == -1) 535/* 536 * we cheated and did not do strncmp(), so we do 537 * that here. 538 */ 539 m =strncmp(match, entry->path, pathlen); 540 541/* 542 * If common part matched earlier then it is a hit, 543 * because we rejected the case where path is not a 544 * leading directory and is shorter than match. 545 */ 546if(!m) 547return1; 548 549return0; 550} 551 552static intmatch_dir_prefix(const char*base, 553const char*match,int matchlen) 554{ 555if(strncmp(base, match, matchlen)) 556return0; 557 558/* 559 * If the base is a subdirectory of a path which 560 * was specified, all of them are interesting. 561 */ 562if(!matchlen || 563 base[matchlen] =='/'|| 564 match[matchlen -1] =='/') 565return1; 566 567/* Just a random prefix match */ 568return0; 569} 570 571/* 572 * Is a tree entry interesting given the pathspec we have? 573 * 574 * Pre-condition: either baselen == base_offset (i.e. empty path) 575 * or base[baselen-1] == '/' (i.e. with trailing slash). 576 * 577 * Return: 578 * - 2 for "yes, and all subsequent entries will be" 579 * - 1 for yes 580 * - zero for no 581 * - negative for "no, and no subsequent entries will be either" 582 */ 583inttree_entry_interesting(const struct name_entry *entry, 584struct strbuf *base,int base_offset, 585const struct pathspec *ps) 586{ 587int i; 588int pathlen, baselen = base->len - base_offset; 589int never_interesting = ps->has_wildcard ?0: -1; 590 591if(!ps->nr) { 592if(!ps->recursive || ps->max_depth == -1) 593return2; 594return!!within_depth(base->buf + base_offset, baselen, 595!!S_ISDIR(entry->mode), 596 ps->max_depth); 597} 598 599 pathlen =tree_entry_len(entry->path, entry->sha1); 600 601for(i = ps->nr -1; i >=0; i--) { 602const struct pathspec_item *item = ps->items+i; 603const char*match = item->match; 604const char*base_str = base->buf + base_offset; 605int matchlen = item->len; 606 607if(baselen >= matchlen) { 608/* If it doesn't match, move along... */ 609if(!match_dir_prefix(base_str, match, matchlen)) 610goto match_wildcards; 611 612if(!ps->recursive || ps->max_depth == -1) 613return2; 614 615return!!within_depth(base_str + matchlen +1, 616 baselen - matchlen -1, 617!!S_ISDIR(entry->mode), 618 ps->max_depth); 619} 620 621/* Either there must be no base, or the base must match. */ 622if(baselen ==0|| !strncmp(base_str, match, baselen)) { 623if(match_entry(entry, pathlen, 624 match + baselen, matchlen - baselen, 625&never_interesting)) 626return1; 627 628if(ps->items[i].use_wildcard) { 629if(!fnmatch(match + baselen, entry->path,0)) 630return1; 631 632/* 633 * Match all directories. We'll try to 634 * match files later on. 635 */ 636if(ps->recursive &&S_ISDIR(entry->mode)) 637return1; 638} 639 640continue; 641} 642 643match_wildcards: 644if(!ps->items[i].use_wildcard) 645continue; 646 647/* 648 * Concatenate base and entry->path into one and do 649 * fnmatch() on it. 650 */ 651 652strbuf_add(base, entry->path, pathlen); 653 654if(!fnmatch(match, base->buf + base_offset,0)) { 655strbuf_setlen(base, base_offset + baselen); 656return1; 657} 658strbuf_setlen(base, base_offset + baselen); 659 660/* 661 * Match all directories. We'll try to match files 662 * later on. 663 */ 664if(ps->recursive &&S_ISDIR(entry->mode)) 665return1; 666} 667return never_interesting;/* No matches */ 668}