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 312inttraverse_trees(int n,struct tree_desc *t,struct traverse_info *info) 313{ 314int ret =0; 315int error =0; 316struct name_entry *entry =xmalloc(n*sizeof(*entry)); 317int i; 318struct tree_desc_x *tx =xcalloc(n,sizeof(*tx)); 319 320for(i =0; i < n; i++) 321 tx[i].d = t[i]; 322 323for(;;) { 324unsigned long mask, dirmask; 325const char*first = NULL; 326int first_len =0; 327struct name_entry *e; 328int len; 329 330for(i =0; i < n; i++) { 331 e = entry + i; 332extended_entry_extract(tx + i, e, NULL,0); 333} 334 335/* 336 * A tree may have "t-2" at the current location even 337 * though it may have "t" that is a subtree behind it, 338 * and another tree may return "t". We want to grab 339 * all "t" from all trees to match in such a case. 340 */ 341for(i =0; i < n; i++) { 342 e = entry + i; 343if(!e->path) 344continue; 345 len =tree_entry_len(e->path, e->sha1); 346if(!first) { 347 first = e->path; 348 first_len = len; 349continue; 350} 351if(name_compare(e->path, len, first, first_len) <0) { 352 first = e->path; 353 first_len = len; 354} 355} 356 357if(first) { 358for(i =0; i < n; i++) { 359 e = entry + i; 360extended_entry_extract(tx + i, e, first, first_len); 361/* Cull the ones that are not the earliest */ 362if(!e->path) 363continue; 364 len =tree_entry_len(e->path, e->sha1); 365if(name_compare(e->path, len, first, first_len)) 366entry_clear(e); 367} 368} 369 370/* Now we have in entry[i] the earliest name from the trees */ 371 mask =0; 372 dirmask =0; 373for(i =0; i < n; i++) { 374if(!entry[i].path) 375continue; 376 mask |=1ul<< i; 377if(S_ISDIR(entry[i].mode)) 378 dirmask |=1ul<< i; 379} 380if(!mask) 381break; 382 ret = info->fn(n, mask, dirmask, entry, info); 383if(ret <0) { 384 error = ret; 385if(!info->show_all_errors) 386break; 387} 388 mask &= ret; 389 ret =0; 390for(i =0; i < n; i++) 391if(mask & (1ul<< i)) 392update_extended_entry(tx + i, entry + i); 393} 394free(entry); 395for(i =0; i < n; i++) 396free_extended_entry(tx + i); 397free(tx); 398return error; 399} 400 401static intfind_tree_entry(struct tree_desc *t,const char*name,unsigned char*result,unsigned*mode) 402{ 403int namelen =strlen(name); 404while(t->size) { 405const char*entry; 406const unsigned char*sha1; 407int entrylen, cmp; 408 409 sha1 =tree_entry_extract(t, &entry, mode); 410update_tree_entry(t); 411 entrylen =tree_entry_len(entry, sha1); 412if(entrylen > namelen) 413continue; 414 cmp =memcmp(name, entry, entrylen); 415if(cmp >0) 416continue; 417if(cmp <0) 418break; 419if(entrylen == namelen) { 420hashcpy(result, sha1); 421return0; 422} 423if(name[entrylen] !='/') 424continue; 425if(!S_ISDIR(*mode)) 426break; 427if(++entrylen == namelen) { 428hashcpy(result, sha1); 429return0; 430} 431returnget_tree_entry(sha1, name + entrylen, result, mode); 432} 433return-1; 434} 435 436intget_tree_entry(const unsigned char*tree_sha1,const char*name,unsigned char*sha1,unsigned*mode) 437{ 438int retval; 439void*tree; 440unsigned long size; 441struct tree_desc t; 442unsigned char root[20]; 443 444 tree =read_object_with_reference(tree_sha1, tree_type, &size, root); 445if(!tree) 446return-1; 447 448if(name[0] =='\0') { 449hashcpy(sha1, root); 450free(tree); 451return0; 452} 453 454init_tree_desc(&t, tree, size); 455 retval =find_tree_entry(&t, name, sha1, mode); 456free(tree); 457return retval; 458} 459 460static intmatch_entry(const struct name_entry *entry,int pathlen, 461const char*match,int matchlen, 462int*never_interesting) 463{ 464int m = -1;/* signals that we haven't called strncmp() */ 465 466if(*never_interesting) { 467/* 468 * We have not seen any match that sorts later 469 * than the current path. 470 */ 471 472/* 473 * Does match sort strictly earlier than path 474 * with their common parts? 475 */ 476 m =strncmp(match, entry->path, 477(matchlen < pathlen) ? matchlen : pathlen); 478if(m <0) 479return0; 480 481/* 482 * If we come here even once, that means there is at 483 * least one pathspec that would sort equal to or 484 * later than the path we are currently looking at. 485 * In other words, if we have never reached this point 486 * after iterating all pathspecs, it means all 487 * pathspecs are either outside of base, or inside the 488 * base but sorts strictly earlier than the current 489 * one. In either case, they will never match the 490 * subsequent entries. In such a case, we initialized 491 * the variable to -1 and that is what will be 492 * returned, allowing the caller to terminate early. 493 */ 494*never_interesting =0; 495} 496 497if(pathlen > matchlen) 498return0; 499 500if(matchlen > pathlen) { 501if(match[pathlen] !='/') 502return0; 503if(!S_ISDIR(entry->mode)) 504return0; 505} 506 507if(m == -1) 508/* 509 * we cheated and did not do strncmp(), so we do 510 * that here. 511 */ 512 m =strncmp(match, entry->path, pathlen); 513 514/* 515 * If common part matched earlier then it is a hit, 516 * because we rejected the case where path is not a 517 * leading directory and is shorter than match. 518 */ 519if(!m) 520return1; 521 522return0; 523} 524 525static intmatch_dir_prefix(const char*base,int baselen, 526const char*match,int matchlen) 527{ 528if(strncmp(base, match, matchlen)) 529return0; 530 531/* 532 * If the base is a subdirectory of a path which 533 * was specified, all of them are interesting. 534 */ 535if(!matchlen || 536 base[matchlen] =='/'|| 537 match[matchlen -1] =='/') 538return1; 539 540/* Just a random prefix match */ 541return0; 542} 543 544/* 545 * Is a tree entry interesting given the pathspec we have? 546 * 547 * Pre-condition: either baselen == base_offset (i.e. empty path) 548 * or base[baselen-1] == '/' (i.e. with trailing slash). 549 * 550 * Return: 551 * - 2 for "yes, and all subsequent entries will be" 552 * - 1 for yes 553 * - zero for no 554 * - negative for "no, and no subsequent entries will be either" 555 */ 556inttree_entry_interesting(const struct name_entry *entry, 557struct strbuf *base,int base_offset, 558const struct pathspec *ps) 559{ 560int i; 561int pathlen, baselen = base->len - base_offset; 562int never_interesting = ps->has_wildcard ?0: -1; 563 564if(!ps->nr) { 565if(!ps->recursive || ps->max_depth == -1) 566return2; 567return!!within_depth(base->buf + base_offset, baselen, 568!!S_ISDIR(entry->mode), 569 ps->max_depth); 570} 571 572 pathlen =tree_entry_len(entry->path, entry->sha1); 573 574for(i = ps->nr -1; i >=0; i--) { 575const struct pathspec_item *item = ps->items+i; 576const char*match = item->match; 577const char*base_str = base->buf + base_offset; 578int matchlen = item->len; 579 580if(baselen >= matchlen) { 581/* If it doesn't match, move along... */ 582if(!match_dir_prefix(base_str, baselen, match, matchlen)) 583goto match_wildcards; 584 585if(!ps->recursive || ps->max_depth == -1) 586return2; 587 588return!!within_depth(base_str + matchlen +1, 589 baselen - matchlen -1, 590!!S_ISDIR(entry->mode), 591 ps->max_depth); 592} 593 594/* Does the base match? */ 595if(!strncmp(base_str, match, baselen)) { 596if(match_entry(entry, pathlen, 597 match + baselen, matchlen - baselen, 598&never_interesting)) 599return1; 600 601if(ps->items[i].use_wildcard) { 602if(!fnmatch(match + baselen, entry->path,0)) 603return1; 604 605/* 606 * Match all directories. We'll try to 607 * match files later on. 608 */ 609if(ps->recursive &&S_ISDIR(entry->mode)) 610return1; 611} 612 613continue; 614} 615 616match_wildcards: 617if(!ps->items[i].use_wildcard) 618continue; 619 620/* 621 * Concatenate base and entry->path into one and do 622 * fnmatch() on it. 623 */ 624 625strbuf_add(base, entry->path, pathlen); 626 627if(!fnmatch(match, base->buf + base_offset,0)) { 628strbuf_setlen(base, base_offset + baselen); 629return1; 630} 631strbuf_setlen(base, base_offset + baselen); 632 633/* 634 * Match all directories. We'll try to match files 635 * later on. 636 */ 637if(ps->recursive &&S_ISDIR(entry->mode)) 638return1; 639} 640return never_interesting;/* No matches */ 641}