1 /* 2 * Copyright (C) the libgit2 contributors. All rights reserved. 3 * 4 * This file is part of libgit2, distributed under the GNU GPL v2 with 5 * a Linking Exception. For full terms see the included COPYING file. 6 */ 7 8 #include "tree.h" 9 10 #include "commit.h" 11 #include "git2/repository.h" 12 #include "git2/object.h" 13 #include "futils.h" 14 #include "tree-cache.h" 15 #include "index.h" 16 17 #define DEFAULT_TREE_SIZE 16 18 #define MAX_FILEMODE_BYTES 6 19 20 #define TREE_ENTRY_CHECK_NAMELEN(n) \ 21 if (n > UINT16_MAX) { git_error_set(GIT_ERROR_INVALID, "tree entry path too long"); } 22 23 static bool valid_filemode(const int filemode) 24 { 25 return (filemode == GIT_FILEMODE_TREE 26 || filemode == GIT_FILEMODE_BLOB 27 || filemode == GIT_FILEMODE_BLOB_EXECUTABLE 28 || filemode == GIT_FILEMODE_LINK 29 || filemode == GIT_FILEMODE_COMMIT); 30 } 31 32 GIT_INLINE(git_filemode_t) normalize_filemode(git_filemode_t filemode) 33 { 34 /* Tree bits set, but it's not a commit */ 35 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_TREE) 36 return GIT_FILEMODE_TREE; 37 38 /* If any of the x bits are set */ 39 if (GIT_PERMS_IS_EXEC(filemode)) 40 return GIT_FILEMODE_BLOB_EXECUTABLE; 41 42 /* 16XXXX means commit */ 43 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_COMMIT) 44 return GIT_FILEMODE_COMMIT; 45 46 /* 12XXXX means symlink */ 47 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_LINK) 48 return GIT_FILEMODE_LINK; 49 50 /* Otherwise, return a blob */ 51 return GIT_FILEMODE_BLOB; 52 } 53 54 static int valid_entry_name(git_repository *repo, const char *filename) 55 { 56 return *filename != '\0' && 57 git_path_isvalid(repo, filename, 0, 58 GIT_PATH_REJECT_TRAVERSAL | GIT_PATH_REJECT_DOT_GIT | GIT_PATH_REJECT_SLASH); 59 } 60 61 static int entry_sort_cmp(const void *a, const void *b) 62 { 63 const git_tree_entry *e1 = (const git_tree_entry *)a; 64 const git_tree_entry *e2 = (const git_tree_entry *)b; 65 66 return git_path_cmp( 67 e1->filename, e1->filename_len, git_tree_entry__is_tree(e1), 68 e2->filename, e2->filename_len, git_tree_entry__is_tree(e2), 69 git__strncmp); 70 } 71 72 int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2) 73 { 74 return entry_sort_cmp(e1, e2); 75 } 76 77 /** 78 * Allocate a new self-contained entry, with enough space after it to 79 * store the filename and the id. 80 */ 81 static git_tree_entry *alloc_entry(const char *filename, size_t filename_len, const git_oid *id) 82 { 83 git_tree_entry *entry = NULL; 84 size_t tree_len; 85 86 TREE_ENTRY_CHECK_NAMELEN(filename_len); 87 88 if (GIT_ADD_SIZET_OVERFLOW(&tree_len, sizeof(git_tree_entry), filename_len) || 89 GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, 1) || 90 GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, GIT_OID_RAWSZ)) 91 return NULL; 92 93 entry = git__calloc(1, tree_len); 94 if (!entry) 95 return NULL; 96 97 { 98 char *filename_ptr; 99 void *id_ptr; 100 101 filename_ptr = ((char *) entry) + sizeof(git_tree_entry); 102 memcpy(filename_ptr, filename, filename_len); 103 entry->filename = filename_ptr; 104 105 id_ptr = filename_ptr + filename_len + 1; 106 git_oid_cpy(id_ptr, id); 107 entry->oid = id_ptr; 108 } 109 110 entry->filename_len = (uint16_t)filename_len; 111 112 return entry; 113 } 114 115 struct tree_key_search { 116 const char *filename; 117 uint16_t filename_len; 118 }; 119 120 static int homing_search_cmp(const void *key, const void *array_member) 121 { 122 const struct tree_key_search *ksearch = key; 123 const git_tree_entry *entry = array_member; 124 125 const uint16_t len1 = ksearch->filename_len; 126 const uint16_t len2 = entry->filename_len; 127 128 return memcmp( 129 ksearch->filename, 130 entry->filename, 131 len1 < len2 ? len1 : len2 132 ); 133 } 134 135 /* 136 * Search for an entry in a given tree. 137 * 138 * Note that this search is performed in two steps because 139 * of the way tree entries are sorted internally in git: 140 * 141 * Entries in a tree are not sorted alphabetically; two entries 142 * with the same root prefix will have different positions 143 * depending on whether they are folders (subtrees) or normal files. 144 * 145 * Consequently, it is not possible to find an entry on the tree 146 * with a binary search if you don't know whether the filename 147 * you're looking for is a folder or a normal file. 148 * 149 * To work around this, we first perform a homing binary search 150 * on the tree, using the minimal length root prefix of our filename. 151 * Once the comparisons for this homing search start becoming 152 * ambiguous because of folder vs file sorting, we look linearly 153 * around the area for our target file. 154 */ 155 static int tree_key_search( 156 size_t *at_pos, 157 const git_tree *tree, 158 const char *filename, 159 size_t filename_len) 160 { 161 struct tree_key_search ksearch; 162 const git_tree_entry *entry; 163 size_t homing, i; 164 165 TREE_ENTRY_CHECK_NAMELEN(filename_len); 166 167 ksearch.filename = filename; 168 ksearch.filename_len = (uint16_t)filename_len; 169 170 /* Initial homing search; find an entry on the tree with 171 * the same prefix as the filename we're looking for */ 172 173 if (git_array_search(&homing, 174 tree->entries, &homing_search_cmp, &ksearch) < 0) 175 return GIT_ENOTFOUND; /* just a signal error; not passed back to user */ 176 177 /* We found a common prefix. Look forward as long as 178 * there are entries that share the common prefix */ 179 for (i = homing; i < tree->entries.size; ++i) { 180 entry = git_array_get(tree->entries, i); 181 182 if (homing_search_cmp(&ksearch, entry) < 0) 183 break; 184 185 if (entry->filename_len == filename_len && 186 memcmp(filename, entry->filename, filename_len) == 0) { 187 if (at_pos) 188 *at_pos = i; 189 190 return 0; 191 } 192 } 193 194 /* If we haven't found our filename yet, look backwards 195 * too as long as we have entries with the same prefix */ 196 if (homing > 0) { 197 i = homing - 1; 198 199 do { 200 entry = git_array_get(tree->entries, i); 201 202 if (homing_search_cmp(&ksearch, entry) > 0) 203 break; 204 205 if (entry->filename_len == filename_len && 206 memcmp(filename, entry->filename, filename_len) == 0) { 207 if (at_pos) 208 *at_pos = i; 209 210 return 0; 211 } 212 } while (i-- > 0); 213 } 214 215 /* The filename doesn't exist at all */ 216 return GIT_ENOTFOUND; 217 } 218 219 void git_tree_entry_free(git_tree_entry *entry) 220 { 221 if (entry == NULL) 222 return; 223 224 git__free(entry); 225 } 226 227 int git_tree_entry_dup(git_tree_entry **dest, const git_tree_entry *source) 228 { 229 git_tree_entry *cpy; 230 231 GIT_ASSERT_ARG(source); 232 233 cpy = alloc_entry(source->filename, source->filename_len, source->oid); 234 if (cpy == NULL) 235 return -1; 236 237 cpy->attr = source->attr; 238 239 *dest = cpy; 240 return 0; 241 } 242 243 void git_tree__free(void *_tree) 244 { 245 git_tree *tree = _tree; 246 247 git_odb_object_free(tree->odb_obj); 248 git_array_clear(tree->entries); 249 git__free(tree); 250 } 251 252 git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry) 253 { 254 return normalize_filemode(entry->attr); 255 } 256 257 git_filemode_t git_tree_entry_filemode_raw(const git_tree_entry *entry) 258 { 259 return entry->attr; 260 } 261 262 const char *git_tree_entry_name(const git_tree_entry *entry) 263 { 264 GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL); 265 return entry->filename; 266 } 267 268 const git_oid *git_tree_entry_id(const git_tree_entry *entry) 269 { 270 GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL); 271 return entry->oid; 272 } 273 274 git_object_t git_tree_entry_type(const git_tree_entry *entry) 275 { 276 GIT_ASSERT_ARG_WITH_RETVAL(entry, GIT_OBJECT_INVALID); 277 278 if (S_ISGITLINK(entry->attr)) 279 return GIT_OBJECT_COMMIT; 280 else if (S_ISDIR(entry->attr)) 281 return GIT_OBJECT_TREE; 282 else 283 return GIT_OBJECT_BLOB; 284 } 285 286 int git_tree_entry_to_object( 287 git_object **object_out, 288 git_repository *repo, 289 const git_tree_entry *entry) 290 { 291 GIT_ASSERT_ARG(entry); 292 GIT_ASSERT_ARG(object_out); 293 294 return git_object_lookup(object_out, repo, entry->oid, GIT_OBJECT_ANY); 295 } 296 297 static const git_tree_entry *entry_fromname( 298 const git_tree *tree, const char *name, size_t name_len) 299 { 300 size_t idx; 301 302 if (tree_key_search(&idx, tree, name, name_len) < 0) 303 return NULL; 304 305 return git_array_get(tree->entries, idx); 306 } 307 308 const git_tree_entry *git_tree_entry_byname( 309 const git_tree *tree, const char *filename) 310 { 311 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL); 312 GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL); 313 314 return entry_fromname(tree, filename, strlen(filename)); 315 } 316 317 const git_tree_entry *git_tree_entry_byindex( 318 const git_tree *tree, size_t idx) 319 { 320 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL); 321 return git_array_get(tree->entries, idx); 322 } 323 324 const git_tree_entry *git_tree_entry_byid( 325 const git_tree *tree, const git_oid *id) 326 { 327 size_t i; 328 const git_tree_entry *e; 329 330 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL); 331 332 git_array_foreach(tree->entries, i, e) { 333 if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0) 334 return e; 335 } 336 337 return NULL; 338 } 339 340 size_t git_tree_entrycount(const git_tree *tree) 341 { 342 GIT_ASSERT_ARG_WITH_RETVAL(tree, 0); 343 return tree->entries.size; 344 } 345 346 size_t git_treebuilder_entrycount(git_treebuilder *bld) 347 { 348 GIT_ASSERT_ARG_WITH_RETVAL(bld, 0); 349 350 return git_strmap_size(bld->map); 351 } 352 353 static int tree_error(const char *str, const char *path) 354 { 355 if (path) 356 git_error_set(GIT_ERROR_TREE, "%s - %s", str, path); 357 else 358 git_error_set(GIT_ERROR_TREE, "%s", str); 359 return -1; 360 } 361 362 static int parse_mode(uint16_t *mode_out, const char *buffer, size_t buffer_len, const char **buffer_out) 363 { 364 int32_t mode; 365 int error; 366 367 if (!buffer_len || git__isspace(*buffer)) 368 return -1; 369 370 if ((error = git__strntol32(&mode, buffer, buffer_len, buffer_out, 8)) < 0) 371 return error; 372 373 if (mode < 0 || mode > UINT16_MAX) 374 return -1; 375 376 *mode_out = mode; 377 378 return 0; 379 } 380 381 int git_tree__parse_raw(void *_tree, const char *data, size_t size) 382 { 383 git_tree *tree = _tree; 384 const char *buffer; 385 const char *buffer_end; 386 387 buffer = data; 388 buffer_end = buffer + size; 389 390 tree->odb_obj = NULL; 391 git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE); 392 GIT_ERROR_CHECK_ARRAY(tree->entries); 393 394 while (buffer < buffer_end) { 395 git_tree_entry *entry; 396 size_t filename_len; 397 const char *nul; 398 uint16_t attr; 399 400 if (parse_mode(&attr, buffer, buffer_end - buffer, &buffer) < 0 || !buffer) 401 return tree_error("failed to parse tree: can't parse filemode", NULL); 402 403 if (buffer >= buffer_end || (*buffer++) != ' ') 404 return tree_error("failed to parse tree: missing space after filemode", NULL); 405 406 if ((nul = memchr(buffer, 0, buffer_end - buffer)) == NULL) 407 return tree_error("failed to parse tree: object is corrupted", NULL); 408 409 if ((filename_len = nul - buffer) == 0 || filename_len > UINT16_MAX) 410 return tree_error("failed to parse tree: can't parse filename", NULL); 411 412 if ((buffer_end - (nul + 1)) < GIT_OID_RAWSZ) 413 return tree_error("failed to parse tree: can't parse OID", NULL); 414 415 /* Allocate the entry */ 416 { 417 entry = git_array_alloc(tree->entries); 418 GIT_ERROR_CHECK_ALLOC(entry); 419 420 entry->attr = attr; 421 entry->filename_len = (uint16_t)filename_len; 422 entry->filename = buffer; 423 entry->oid = (git_oid *) ((char *) buffer + filename_len + 1); 424 } 425 426 buffer += filename_len + 1; 427 buffer += GIT_OID_RAWSZ; 428 } 429 430 return 0; 431 } 432 433 int git_tree__parse(void *_tree, git_odb_object *odb_obj) 434 { 435 git_tree *tree = _tree; 436 437 if ((git_tree__parse_raw(tree, 438 git_odb_object_data(odb_obj), 439 git_odb_object_size(odb_obj))) < 0) 440 return -1; 441 442 if (git_odb_object_dup(&tree->odb_obj, odb_obj) < 0) 443 return -1; 444 445 return 0; 446 } 447 448 static size_t find_next_dir(const char *dirname, git_index *index, size_t start) 449 { 450 size_t dirlen, i, entries = git_index_entrycount(index); 451 452 dirlen = strlen(dirname); 453 for (i = start; i < entries; ++i) { 454 const git_index_entry *entry = git_index_get_byindex(index, i); 455 if (strlen(entry->path) < dirlen || 456 memcmp(entry->path, dirname, dirlen) || 457 (dirlen > 0 && entry->path[dirlen] != '/')) { 458 break; 459 } 460 } 461 462 return i; 463 } 464 465 static git_object_t otype_from_mode(git_filemode_t filemode) 466 { 467 switch (filemode) { 468 case GIT_FILEMODE_TREE: 469 return GIT_OBJECT_TREE; 470 case GIT_FILEMODE_COMMIT: 471 return GIT_OBJECT_COMMIT; 472 default: 473 return GIT_OBJECT_BLOB; 474 } 475 } 476 477 static int check_entry(git_repository *repo, const char *filename, const git_oid *id, git_filemode_t filemode) 478 { 479 if (!valid_filemode(filemode)) 480 return tree_error("failed to insert entry: invalid filemode for file", filename); 481 482 if (!valid_entry_name(repo, filename)) 483 return tree_error("failed to insert entry: invalid name for a tree entry", filename); 484 485 if (git_oid_is_zero(id)) 486 return tree_error("failed to insert entry: invalid null OID", filename); 487 488 if (filemode != GIT_FILEMODE_COMMIT && 489 !git_object__is_valid(repo, id, otype_from_mode(filemode))) 490 return tree_error("failed to insert entry: invalid object specified", filename); 491 492 return 0; 493 } 494 495 static int append_entry( 496 git_treebuilder *bld, 497 const char *filename, 498 const git_oid *id, 499 git_filemode_t filemode, 500 bool validate) 501 { 502 git_tree_entry *entry; 503 int error = 0; 504 505 if (validate && ((error = check_entry(bld->repo, filename, id, filemode)) < 0)) 506 return error; 507 508 entry = alloc_entry(filename, strlen(filename), id); 509 GIT_ERROR_CHECK_ALLOC(entry); 510 511 entry->attr = (uint16_t)filemode; 512 513 if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) { 514 git_tree_entry_free(entry); 515 git_error_set(GIT_ERROR_TREE, "failed to append entry %s to the tree builder", filename); 516 return -1; 517 } 518 519 return 0; 520 } 521 522 static int write_tree( 523 git_oid *oid, 524 git_repository *repo, 525 git_index *index, 526 const char *dirname, 527 size_t start, 528 git_buf *shared_buf) 529 { 530 git_treebuilder *bld = NULL; 531 size_t i, entries = git_index_entrycount(index); 532 int error; 533 size_t dirname_len = strlen(dirname); 534 const git_tree_cache *cache; 535 536 cache = git_tree_cache_get(index->tree, dirname); 537 if (cache != NULL && cache->entry_count >= 0){ 538 git_oid_cpy(oid, &cache->oid); 539 return (int)find_next_dir(dirname, index, start); 540 } 541 542 if ((error = git_treebuilder_new(&bld, repo, NULL)) < 0 || bld == NULL) 543 return -1; 544 545 /* 546 * This loop is unfortunate, but necessary. The index doesn't have 547 * any directores, so we need to handle that manually, and we 548 * need to keep track of the current position. 549 */ 550 for (i = start; i < entries; ++i) { 551 const git_index_entry *entry = git_index_get_byindex(index, i); 552 const char *filename, *next_slash; 553 554 /* 555 * If we've left our (sub)tree, exit the loop and return. The 556 * first check is an early out (and security for the 557 * third). The second check is a simple prefix comparison. The 558 * third check catches situations where there is a directory 559 * win32/sys and a file win32mmap.c. Without it, the following 560 * code believes there is a file win32/mmap.c 561 */ 562 if (strlen(entry->path) < dirname_len || 563 memcmp(entry->path, dirname, dirname_len) || 564 (dirname_len > 0 && entry->path[dirname_len] != '/')) { 565 break; 566 } 567 568 filename = entry->path + dirname_len; 569 if (*filename == '/') 570 filename++; 571 next_slash = strchr(filename, '/'); 572 if (next_slash) { 573 git_oid sub_oid; 574 int written; 575 char *subdir, *last_comp; 576 577 subdir = git__strndup(entry->path, next_slash - entry->path); 578 GIT_ERROR_CHECK_ALLOC(subdir); 579 580 /* Write out the subtree */ 581 written = write_tree(&sub_oid, repo, index, subdir, i, shared_buf); 582 if (written < 0) { 583 git__free(subdir); 584 goto on_error; 585 } else { 586 i = written - 1; /* -1 because of the loop increment */ 587 } 588 589 /* 590 * We need to figure out what we want toinsert 591 * into this tree. If we're traversing 592 * deps/zlib/, then we only want to write 593 * 'zlib' into the tree. 594 */ 595 last_comp = strrchr(subdir, '/'); 596 if (last_comp) { 597 last_comp++; /* Get rid of the '/' */ 598 } else { 599 last_comp = subdir; 600 } 601 602 error = append_entry(bld, last_comp, &sub_oid, S_IFDIR, true); 603 git__free(subdir); 604 if (error < 0) 605 goto on_error; 606 } else { 607 error = append_entry(bld, filename, &entry->id, entry->mode, true); 608 if (error < 0) 609 goto on_error; 610 } 611 } 612 613 if (git_treebuilder_write_with_buffer(oid, bld, shared_buf) < 0) 614 goto on_error; 615 616 git_treebuilder_free(bld); 617 return (int)i; 618 619 on_error: 620 git_treebuilder_free(bld); 621 return -1; 622 } 623 624 int git_tree__write_index( 625 git_oid *oid, git_index *index, git_repository *repo) 626 { 627 int ret; 628 git_tree *tree; 629 git_buf shared_buf = GIT_BUF_INIT; 630 bool old_ignore_case = false; 631 632 GIT_ASSERT_ARG(oid); 633 GIT_ASSERT_ARG(index); 634 GIT_ASSERT_ARG(repo); 635 636 if (git_index_has_conflicts(index)) { 637 git_error_set(GIT_ERROR_INDEX, 638 "cannot create a tree from a not fully merged index."); 639 return GIT_EUNMERGED; 640 } 641 642 if (index->tree != NULL && index->tree->entry_count >= 0) { 643 git_oid_cpy(oid, &index->tree->oid); 644 return 0; 645 } 646 647 /* The tree cache didn't help us; we'll have to write 648 * out a tree. If the index is ignore_case, we must 649 * make it case-sensitive for the duration of the tree-write 650 * operation. */ 651 652 if (index->ignore_case) { 653 old_ignore_case = true; 654 git_index__set_ignore_case(index, false); 655 } 656 657 ret = write_tree(oid, repo, index, "", 0, &shared_buf); 658 git_buf_dispose(&shared_buf); 659 660 if (old_ignore_case) 661 git_index__set_ignore_case(index, true); 662 663 index->tree = NULL; 664 665 if (ret < 0) 666 return ret; 667 668 git_pool_clear(&index->tree_pool); 669 670 if ((ret = git_tree_lookup(&tree, repo, oid)) < 0) 671 return ret; 672 673 /* Read the tree cache into the index */ 674 ret = git_tree_cache_read_tree(&index->tree, tree, &index->tree_pool); 675 git_tree_free(tree); 676 677 return ret; 678 } 679 680 int git_treebuilder_new( 681 git_treebuilder **builder_p, 682 git_repository *repo, 683 const git_tree *source) 684 { 685 git_treebuilder *bld; 686 size_t i; 687 688 GIT_ASSERT_ARG(builder_p); 689 GIT_ASSERT_ARG(repo); 690 691 bld = git__calloc(1, sizeof(git_treebuilder)); 692 GIT_ERROR_CHECK_ALLOC(bld); 693 694 bld->repo = repo; 695 696 if (git_strmap_new(&bld->map) < 0) { 697 git__free(bld); 698 return -1; 699 } 700 701 if (source != NULL) { 702 git_tree_entry *entry_src; 703 704 git_array_foreach(source->entries, i, entry_src) { 705 if (append_entry( 706 bld, entry_src->filename, 707 entry_src->oid, 708 entry_src->attr, 709 false) < 0) 710 goto on_error; 711 } 712 } 713 714 *builder_p = bld; 715 return 0; 716 717 on_error: 718 git_treebuilder_free(bld); 719 return -1; 720 } 721 722 int git_treebuilder_insert( 723 const git_tree_entry **entry_out, 724 git_treebuilder *bld, 725 const char *filename, 726 const git_oid *id, 727 git_filemode_t filemode) 728 { 729 git_tree_entry *entry; 730 int error; 731 732 GIT_ASSERT_ARG(bld); 733 GIT_ASSERT_ARG(id); 734 GIT_ASSERT_ARG(filename); 735 736 if ((error = check_entry(bld->repo, filename, id, filemode)) < 0) 737 return error; 738 739 if ((entry = git_strmap_get(bld->map, filename)) != NULL) { 740 git_oid_cpy((git_oid *) entry->oid, id); 741 } else { 742 entry = alloc_entry(filename, strlen(filename), id); 743 GIT_ERROR_CHECK_ALLOC(entry); 744 745 if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) { 746 git_tree_entry_free(entry); 747 git_error_set(GIT_ERROR_TREE, "failed to insert %s", filename); 748 return -1; 749 } 750 } 751 752 entry->attr = filemode; 753 754 if (entry_out) 755 *entry_out = entry; 756 757 return 0; 758 } 759 760 static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename) 761 { 762 GIT_ASSERT_ARG_WITH_RETVAL(bld, NULL); 763 GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL); 764 765 return git_strmap_get(bld->map, filename); 766 } 767 768 const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename) 769 { 770 return treebuilder_get(bld, filename); 771 } 772 773 int git_treebuilder_remove(git_treebuilder *bld, const char *filename) 774 { 775 git_tree_entry *entry = treebuilder_get(bld, filename); 776 777 if (entry == NULL) 778 return tree_error("failed to remove entry: file isn't in the tree", filename); 779 780 git_strmap_delete(bld->map, filename); 781 git_tree_entry_free(entry); 782 783 return 0; 784 } 785 786 int git_treebuilder_write(git_oid *oid, git_treebuilder *bld) 787 { 788 int error; 789 git_buf buffer = GIT_BUF_INIT; 790 791 error = git_treebuilder_write_with_buffer(oid, bld, &buffer); 792 793 git_buf_dispose(&buffer); 794 return error; 795 } 796 797 int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_buf *tree) 798 { 799 int error = 0; 800 size_t i, entrycount; 801 git_odb *odb; 802 git_tree_entry *entry; 803 git_vector entries = GIT_VECTOR_INIT; 804 805 GIT_ASSERT_ARG(bld); 806 GIT_ASSERT_ARG(tree); 807 808 git_buf_clear(tree); 809 810 entrycount = git_strmap_size(bld->map); 811 if ((error = git_vector_init(&entries, entrycount, entry_sort_cmp)) < 0) 812 goto out; 813 814 if (tree->asize == 0 && 815 (error = git_buf_grow(tree, entrycount * 72)) < 0) 816 goto out; 817 818 git_strmap_foreach_value(bld->map, entry, { 819 if ((error = git_vector_insert(&entries, entry)) < 0) 820 goto out; 821 }); 822 823 git_vector_sort(&entries); 824 825 for (i = 0; i < entries.length && !error; ++i) { 826 entry = git_vector_get(&entries, i); 827 828 git_buf_printf(tree, "%o ", entry->attr); 829 git_buf_put(tree, entry->filename, entry->filename_len + 1); 830 git_buf_put(tree, (char *)entry->oid->id, GIT_OID_RAWSZ); 831 832 if (git_buf_oom(tree)) { 833 error = -1; 834 goto out; 835 } 836 } 837 838 if ((error = git_repository_odb__weakptr(&odb, bld->repo)) == 0) 839 error = git_odb_write(oid, odb, tree->ptr, tree->size, GIT_OBJECT_TREE); 840 841 out: 842 git_vector_free(&entries); 843 844 return error; 845 } 846 847 int git_treebuilder_filter( 848 git_treebuilder *bld, 849 git_treebuilder_filter_cb filter, 850 void *payload) 851 { 852 const char *filename; 853 git_tree_entry *entry; 854 855 GIT_ASSERT_ARG(bld); 856 GIT_ASSERT_ARG(filter); 857 858 git_strmap_foreach(bld->map, filename, entry, { 859 if (filter(entry, payload)) { 860 git_strmap_delete(bld->map, filename); 861 git_tree_entry_free(entry); 862 } 863 }); 864 865 return 0; 866 } 867 868 int git_treebuilder_clear(git_treebuilder *bld) 869 { 870 git_tree_entry *e; 871 872 GIT_ASSERT_ARG(bld); 873 874 git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e)); 875 git_strmap_clear(bld->map); 876 877 return 0; 878 } 879 880 void git_treebuilder_free(git_treebuilder *bld) 881 { 882 if (bld == NULL) 883 return; 884 885 git_treebuilder_clear(bld); 886 git_strmap_free(bld->map); 887 git__free(bld); 888 } 889 890 static size_t subpath_len(const char *path) 891 { 892 const char *slash_pos = strchr(path, '/'); 893 if (slash_pos == NULL) 894 return strlen(path); 895 896 return slash_pos - path; 897 } 898 899 int git_tree_entry_bypath( 900 git_tree_entry **entry_out, 901 const git_tree *root, 902 const char *path) 903 { 904 int error = 0; 905 git_tree *subtree; 906 const git_tree_entry *entry; 907 size_t filename_len; 908 909 /* Find how long is the current path component (i.e. 910 * the filename between two slashes */ 911 filename_len = subpath_len(path); 912 913 if (filename_len == 0) { 914 git_error_set(GIT_ERROR_TREE, "invalid tree path given"); 915 return GIT_ENOTFOUND; 916 } 917 918 entry = entry_fromname(root, path, filename_len); 919 920 if (entry == NULL) { 921 git_error_set(GIT_ERROR_TREE, 922 "the path '%.*s' does not exist in the given tree", (int) filename_len, path); 923 return GIT_ENOTFOUND; 924 } 925 926 switch (path[filename_len]) { 927 case '/': 928 /* If there are more components in the path... 929 * then this entry *must* be a tree */ 930 if (!git_tree_entry__is_tree(entry)) { 931 git_error_set(GIT_ERROR_TREE, 932 "the path '%.*s' exists but is not a tree", (int) filename_len, path); 933 return GIT_ENOTFOUND; 934 } 935 936 /* If there's only a slash left in the path, we 937 * return the current entry; otherwise, we keep 938 * walking down the path */ 939 if (path[filename_len + 1] != '\0') 940 break; 941 /* fall through */ 942 case '\0': 943 /* If there are no more components in the path, return 944 * this entry */ 945 return git_tree_entry_dup(entry_out, entry); 946 } 947 948 if (git_tree_lookup(&subtree, root->object.repo, entry->oid) < 0) 949 return -1; 950 951 error = git_tree_entry_bypath( 952 entry_out, 953 subtree, 954 path + filename_len + 1 955 ); 956 957 git_tree_free(subtree); 958 return error; 959 } 960 961 static int tree_walk( 962 const git_tree *tree, 963 git_treewalk_cb callback, 964 git_buf *path, 965 void *payload, 966 bool preorder) 967 { 968 int error = 0; 969 size_t i; 970 const git_tree_entry *entry; 971 972 git_array_foreach(tree->entries, i, entry) { 973 if (preorder) { 974 error = callback(path->ptr, entry, payload); 975 if (error < 0) { /* negative value stops iteration */ 976 git_error_set_after_callback_function(error, "git_tree_walk"); 977 break; 978 } 979 if (error > 0) { /* positive value skips this entry */ 980 error = 0; 981 continue; 982 } 983 } 984 985 if (git_tree_entry__is_tree(entry)) { 986 git_tree *subtree; 987 size_t path_len = git_buf_len(path); 988 989 error = git_tree_lookup(&subtree, tree->object.repo, entry->oid); 990 if (error < 0) 991 break; 992 993 /* append the next entry to the path */ 994 git_buf_puts(path, entry->filename); 995 git_buf_putc(path, '/'); 996 997 if (git_buf_oom(path)) 998 error = -1; 999 else 1000 error = tree_walk(subtree, callback, path, payload, preorder); 1001 1002 git_tree_free(subtree); 1003 if (error != 0) 1004 break; 1005 1006 git_buf_truncate(path, path_len); 1007 } 1008 1009 if (!preorder) { 1010 error = callback(path->ptr, entry, payload); 1011 if (error < 0) { /* negative value stops iteration */ 1012 git_error_set_after_callback_function(error, "git_tree_walk"); 1013 break; 1014 } 1015 error = 0; 1016 } 1017 } 1018 1019 return error; 1020 } 1021 1022 int git_tree_walk( 1023 const git_tree *tree, 1024 git_treewalk_mode mode, 1025 git_treewalk_cb callback, 1026 void *payload) 1027 { 1028 int error = 0; 1029 git_buf root_path = GIT_BUF_INIT; 1030 1031 if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) { 1032 git_error_set(GIT_ERROR_INVALID, "invalid walking mode for tree walk"); 1033 return -1; 1034 } 1035 1036 error = tree_walk( 1037 tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE)); 1038 1039 git_buf_dispose(&root_path); 1040 1041 return error; 1042 } 1043 1044 static int compare_entries(const void *_a, const void *_b) 1045 { 1046 const git_tree_update *a = (git_tree_update *) _a; 1047 const git_tree_update *b = (git_tree_update *) _b; 1048 1049 return strcmp(a->path, b->path); 1050 } 1051 1052 static int on_dup_entry(void **old, void *new) 1053 { 1054 GIT_UNUSED(old); GIT_UNUSED(new); 1055 1056 git_error_set(GIT_ERROR_TREE, "duplicate entries given for update"); 1057 return -1; 1058 } 1059 1060 /* 1061 * We keep the previous tree and the new one at each level of the 1062 * stack. When we leave a level we're done with that tree and we can 1063 * write it out to the odb. 1064 */ 1065 typedef struct { 1066 git_treebuilder *bld; 1067 git_tree *tree; 1068 char *name; 1069 } tree_stack_entry; 1070 1071 /** Count how many slashes (i.e. path components) there are in this string */ 1072 GIT_INLINE(size_t) count_slashes(const char *path) 1073 { 1074 size_t count = 0; 1075 const char *slash; 1076 1077 while ((slash = strchr(path, '/')) != NULL) { 1078 count++; 1079 path = slash + 1; 1080 } 1081 1082 return count; 1083 } 1084 1085 static bool next_component(git_buf *out, const char *in) 1086 { 1087 const char *slash = strchr(in, '/'); 1088 1089 git_buf_clear(out); 1090 1091 if (slash) 1092 git_buf_put(out, in, slash - in); 1093 1094 return !!slash; 1095 } 1096 1097 static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_buf *component) 1098 { 1099 int error; 1100 git_oid new_tree; 1101 1102 git_tree_free(popped->tree); 1103 1104 /* If the tree would be empty, remove it from the one higher up */ 1105 if (git_treebuilder_entrycount(popped->bld) == 0) { 1106 git_treebuilder_free(popped->bld); 1107 error = git_treebuilder_remove(current->bld, popped->name); 1108 git__free(popped->name); 1109 return error; 1110 } 1111 1112 error = git_treebuilder_write(&new_tree, popped->bld); 1113 git_treebuilder_free(popped->bld); 1114 1115 if (error < 0) { 1116 git__free(popped->name); 1117 return error; 1118 } 1119 1120 /* We've written out the tree, now we have to put the new value into its parent */ 1121 git_buf_clear(component); 1122 git_buf_puts(component, popped->name); 1123 git__free(popped->name); 1124 1125 GIT_ERROR_CHECK_ALLOC(component->ptr); 1126 1127 /* Error out if this would create a D/F conflict in this update */ 1128 if (current->tree) { 1129 const git_tree_entry *to_replace; 1130 to_replace = git_tree_entry_byname(current->tree, component->ptr); 1131 if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJECT_TREE) { 1132 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree"); 1133 return -1; 1134 } 1135 } 1136 1137 return git_treebuilder_insert(NULL, current->bld, component->ptr, &new_tree, GIT_FILEMODE_TREE); 1138 } 1139 1140 int git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates) 1141 { 1142 git_array_t(tree_stack_entry) stack = GIT_ARRAY_INIT; 1143 tree_stack_entry *root_elem; 1144 git_vector entries; 1145 int error; 1146 size_t i; 1147 git_buf component = GIT_BUF_INIT; 1148 1149 if ((error = git_vector_init(&entries, nupdates, compare_entries)) < 0) 1150 return error; 1151 1152 /* Sort the entries for treversal */ 1153 for (i = 0 ; i < nupdates; i++) { 1154 if ((error = git_vector_insert_sorted(&entries, (void *) &updates[i], on_dup_entry)) < 0) 1155 goto cleanup; 1156 } 1157 1158 root_elem = git_array_alloc(stack); 1159 GIT_ERROR_CHECK_ALLOC(root_elem); 1160 memset(root_elem, 0, sizeof(*root_elem)); 1161 1162 if (baseline && (error = git_tree_dup(&root_elem->tree, baseline)) < 0) 1163 goto cleanup; 1164 1165 if ((error = git_treebuilder_new(&root_elem->bld, repo, root_elem->tree)) < 0) 1166 goto cleanup; 1167 1168 for (i = 0; i < nupdates; i++) { 1169 const git_tree_update *last_update = i == 0 ? NULL : git_vector_get(&entries, i-1); 1170 const git_tree_update *update = git_vector_get(&entries, i); 1171 size_t common_prefix = 0, steps_up, j; 1172 const char *path; 1173 1174 /* Figure out how much we need to change from the previous tree */ 1175 if (last_update) 1176 common_prefix = git_path_common_dirlen(last_update->path, update->path); 1177 1178 /* 1179 * The entries are sorted, so when we find we're no 1180 * longer in the same directory, we need to abandon 1181 * the old tree (steps up) and dive down to the next 1182 * one. 1183 */ 1184 steps_up = last_update == NULL ? 0 : count_slashes(&last_update->path[common_prefix]); 1185 1186 for (j = 0; j < steps_up; j++) { 1187 tree_stack_entry *current, *popped = git_array_pop(stack); 1188 GIT_ASSERT(popped); 1189 1190 current = git_array_last(stack); 1191 GIT_ASSERT(current); 1192 1193 if ((error = create_popped_tree(current, popped, &component)) < 0) 1194 goto cleanup; 1195 } 1196 1197 /* Now that we've created the trees we popped from the stack, let's go back down */ 1198 path = &update->path[common_prefix]; 1199 while (next_component(&component, path)) { 1200 tree_stack_entry *last, *new_entry; 1201 const git_tree_entry *entry; 1202 1203 last = git_array_last(stack); 1204 entry = last->tree ? git_tree_entry_byname(last->tree, component.ptr) : NULL; 1205 if (!entry) 1206 entry = treebuilder_get(last->bld, component.ptr); 1207 1208 if (entry && git_tree_entry_type(entry) != GIT_OBJECT_TREE) { 1209 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree"); 1210 error = -1; 1211 goto cleanup; 1212 } 1213 1214 new_entry = git_array_alloc(stack); 1215 GIT_ERROR_CHECK_ALLOC(new_entry); 1216 memset(new_entry, 0, sizeof(*new_entry)); 1217 1218 new_entry->tree = NULL; 1219 if (entry && (error = git_tree_lookup(&new_entry->tree, repo, git_tree_entry_id(entry))) < 0) 1220 goto cleanup; 1221 1222 if ((error = git_treebuilder_new(&new_entry->bld, repo, new_entry->tree)) < 0) 1223 goto cleanup; 1224 1225 new_entry->name = git__strdup(component.ptr); 1226 GIT_ERROR_CHECK_ALLOC(new_entry->name); 1227 1228 /* Get to the start of the next component */ 1229 path += component.size + 1; 1230 } 1231 1232 /* After all that, we're finally at the place where we want to perform the update */ 1233 switch (update->action) { 1234 case GIT_TREE_UPDATE_UPSERT: 1235 { 1236 /* Make sure we're replacing something of the same type */ 1237 tree_stack_entry *last = git_array_last(stack); 1238 char *basename = git_path_basename(update->path); 1239 const git_tree_entry *e = git_treebuilder_get(last->bld, basename); 1240 if (e && git_tree_entry_type(e) != git_object__type_from_filemode(update->filemode)) { 1241 git__free(basename); 1242 git_error_set(GIT_ERROR_TREE, "cannot replace '%s' with '%s' at '%s'", 1243 git_object_type2string(git_tree_entry_type(e)), 1244 git_object_type2string(git_object__type_from_filemode(update->filemode)), 1245 update->path); 1246 error = -1; 1247 goto cleanup; 1248 } 1249 1250 error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode); 1251 git__free(basename); 1252 break; 1253 } 1254 case GIT_TREE_UPDATE_REMOVE: 1255 { 1256 char *basename = git_path_basename(update->path); 1257 error = git_treebuilder_remove(git_array_last(stack)->bld, basename); 1258 git__free(basename); 1259 break; 1260 } 1261 default: 1262 git_error_set(GIT_ERROR_TREE, "unknown action for update"); 1263 error = -1; 1264 goto cleanup; 1265 } 1266 1267 if (error < 0) 1268 goto cleanup; 1269 } 1270 1271 /* We're done, go up the stack again and write out the tree */ 1272 { 1273 tree_stack_entry *current = NULL, *popped = NULL; 1274 while ((popped = git_array_pop(stack)) != NULL) { 1275 current = git_array_last(stack); 1276 /* We've reached the top, current is the root tree */ 1277 if (!current) 1278 break; 1279 1280 if ((error = create_popped_tree(current, popped, &component)) < 0) 1281 goto cleanup; 1282 } 1283 1284 /* Write out the root tree */ 1285 git__free(popped->name); 1286 git_tree_free(popped->tree); 1287 1288 error = git_treebuilder_write(out, popped->bld); 1289 git_treebuilder_free(popped->bld); 1290 if (error < 0) 1291 goto cleanup; 1292 } 1293 1294 cleanup: 1295 { 1296 tree_stack_entry *e; 1297 while ((e = git_array_pop(stack)) != NULL) { 1298 git_treebuilder_free(e->bld); 1299 git_tree_free(e->tree); 1300 git__free(e->name); 1301 } 1302 } 1303 1304 git_buf_dispose(&component); 1305 git_array_clear(stack); 1306 git_vector_free(&entries); 1307 return error; 1308 } 1309