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