diff options
| -rw-r--r-- | include/git2/tree.h | 46 | ||||
| -rw-r--r-- | src/tree.c | 245 | ||||
| -rw-r--r-- | tests/object/tree/update.c | 167 |
3 files changed, 458 insertions, 0 deletions
diff --git a/include/git2/tree.h b/include/git2/tree.h index 8a2be2102..2e4735c4b 100644 --- a/include/git2/tree.h +++ b/include/git2/tree.h @@ -418,6 +418,52 @@ GIT_EXTERN(int) git_tree_walk( */ GIT_EXTERN(int) git_tree_dup(git_tree **out, git_tree *source); +/** + * The kind of update to perform + */ +typedef enum { + /** Update or insert an entry at the specified path */ + GIT_TREE_UPDATE_UPSERT, + /** Remove an entry from the specified path */ + GIT_TREE_UPDATE_REMOVE, +} git_tree_update_t; + +/** + * An action to perform during the update of a tree + */ +typedef struct { + /** Update action. If it's an removal, only the path is looked at */ + git_tree_update_t action; + /** The entry's id */ + git_oid id; + /** The filemode/kind of object */ + git_filemode_t filemode; + /** The full path from the root tree */ + const char *path; +} git_tree_update; + +/** + * Create a tree based on another one with the specified modifications + * + * Given the `baseline` perform the changes described in the list of + * `updates` and create a new tree. + * + * This function is optimized for common file/directory addition, removal and + * replacement in trees. It is much more efficient than reading the tree into a + * `git_index` and modifying that, but in exchange it is not as flexible. + * + * Deleting and adding the same entry is undefined behaviour, changing + * a tree to a blob or viceversa is not supported. + * + * @param out id of the new tree + * @param repo the repository in which to create the tree, must be the + * same as for `baseline` + * @param baseline the tree to base these changes on + * @param nupdates the number of elements in the update list + * @param updates the list of updates to perform + */ +GIT_EXTERN(int) git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates); + /** @} */ GIT_END_DECL diff --git a/src/tree.c b/src/tree.c index 6ce460c6d..af293d264 100644 --- a/src/tree.c +++ b/src/tree.c @@ -1034,3 +1034,248 @@ int git_tree_walk( return error; } +static int compare_entries(const void *_a, const void *_b) +{ + const git_tree_update *a = (git_tree_update *) _a; + const git_tree_update *b = (git_tree_update *) _b; + + return strcmp(a->path, b->path); +} + +static int on_dup_entry(void **old, void *new) +{ + GIT_UNUSED(old); GIT_UNUSED(new); + + giterr_set(GITERR_TREE, "duplicate entries given for update"); + return -1; +} + +/* + * We keep the previous tree and the new one at each level of the + * stack. When we leave a level we're done with that tree and we can + * write it out to the odb. + */ +typedef struct { + git_treebuilder *bld; + git_tree *tree; + char *name; +} tree_stack_entry; + +/** Count how many slashes (i.e. path components) there are in this string */ +GIT_INLINE(size_t) count_slashes(const char *path) +{ + size_t count = 0; + const char *slash; + + while ((slash = strchr(path, '/')) != NULL) { + count++; + path = slash + 1; + } + + return count; +} + +static bool next_component(git_buf *out, const char *in) +{ + const char *slash = strchr(in, '/'); + + git_buf_clear(out); + + if (slash) + git_buf_put(out, in, slash - in); + + return !!slash; +} + +static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_buf *component) +{ + int error; + git_oid new_tree; + + git_tree_free(popped->tree); + error = git_treebuilder_write(&new_tree, popped->bld); + git_treebuilder_free(popped->bld); + + if (error < 0) { + git__free(popped->name); + return error; + } + + /* We've written out the tree, now we have to put the new value into its parent */ + git_buf_clear(component); + git_buf_puts(component, popped->name); + git__free(popped->name); + + GITERR_CHECK_ALLOC(component->ptr); + + /* Error out if this would create a D/F conflict in this update */ + if (current->tree) { + const git_tree_entry *to_replace; + to_replace = git_tree_entry_byname(current->tree, component->ptr); + if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJ_TREE) { + giterr_set(GITERR_TREE, "D/F conflict when updating tree"); + return -1; + } + } + + return git_treebuilder_insert(NULL, current->bld, component->ptr, &new_tree, GIT_FILEMODE_TREE); +} + +int git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates) +{ + git_array_t(tree_stack_entry) stack = GIT_ARRAY_INIT; + tree_stack_entry *root_elem; + git_vector entries; + int error; + size_t i; + git_buf component = GIT_BUF_INIT; + + if ((error = git_vector_init(&entries, nupdates, compare_entries)) < 0) + return error; + + /* Sort the entries for treversal */ + for (i = 0 ; i < nupdates; i++) { + if ((error = git_vector_insert_sorted(&entries, (void *) &updates[i], on_dup_entry)) < 0) + goto cleanup; + } + + root_elem = git_array_alloc(stack); + GITERR_CHECK_ALLOC(root_elem); + memset(root_elem, 0, sizeof(*root_elem)); + + if (baseline && (error = git_tree_dup(&root_elem->tree, baseline)) < 0) + goto cleanup; + + if ((error = git_treebuilder_new(&root_elem->bld, repo, root_elem->tree)) < 0) + goto cleanup; + + for (i = 0; i < nupdates; i++) { + const git_tree_update *last_update = i == 0 ? NULL : &updates[i-1]; + const git_tree_update *update = &updates[i]; + size_t common_prefix = 0, steps_up, j; + const char *path; + + /* Figure out how much we need to change from the previous tree */ + if (last_update) + common_prefix = git_path_common_dirlen(last_update->path, update->path); + + /* + * The entries are sorted, so when we find we're no + * longer in the same directory, we need to abandon + * the old tree (steps up) and dive down to the next + * one. + */ + steps_up = last_update == NULL ? 0 : count_slashes(&last_update->path[common_prefix]); + + for (j = 0; j < steps_up; j++) { + tree_stack_entry *current, *popped = git_array_pop(stack); + assert(popped); + + current = git_array_last(stack); + assert(current); + + if ((error = create_popped_tree(current, popped, &component)) < 0) + goto cleanup; + } + + /* Now that we've created the trees we popped from the stack, let's go back down */ + path = &update->path[common_prefix]; + while (next_component(&component, path)) { + tree_stack_entry *last, *new_entry; + const git_tree_entry *entry; + + last = git_array_last(stack); + entry = last->tree ? git_tree_entry_byname(last->tree, component.ptr) : NULL; + if (entry && git_tree_entry_type(entry) != GIT_OBJ_TREE) { + giterr_set(GITERR_TREE, "D/F conflict when updating tree"); + error = -1; + goto cleanup; + } + + new_entry = git_array_alloc(stack); + GITERR_CHECK_ALLOC(new_entry); + memset(new_entry, 0, sizeof(*new_entry)); + + new_entry->tree = NULL; + if (entry && (error = git_tree_lookup(&new_entry->tree, repo, git_tree_entry_id(entry))) < 0) + goto cleanup; + + if ((error = git_treebuilder_new(&new_entry->bld, repo, new_entry->tree)) < 0) + goto cleanup; + + new_entry->name = git__strdup(component.ptr); + GITERR_CHECK_ALLOC(new_entry->name); + + /* Get to the start of the next component */ + path += component.size + 1; + } + + /* After all that, we're finally at the place where we want to perform the update */ + switch (update->action) { + case GIT_TREE_UPDATE_UPSERT: + { + /* Make sure we're replacing something of the same type */ + tree_stack_entry *last = git_array_last(stack); + const char *basename = git_path_basename(update->path); + const git_tree_entry *e = git_treebuilder_get(last->bld, basename); + if (e && git_tree_entry_type(e) != git_object__type_from_filemode(update->filemode)) { + giterr_set(GITERR_TREE, "Cannot replace '%s' with '%s' at '%s'", + git_object_type2string(git_tree_entry_type(e)), + git_object_type2string(git_object__type_from_filemode(update->filemode)), + update->path); + return -1; + } + + error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode); + break; + } + case GIT_TREE_UPDATE_REMOVE: + error = git_treebuilder_remove(git_array_last(stack)->bld, update->path); + break; + default: + giterr_set(GITERR_TREE, "unkown action for update"); + error = -1; + goto cleanup; + } + + if (error < 0) + goto cleanup; + } + + /* We're done, go up the stack again and write out the tree */ + { + tree_stack_entry *current = NULL, *popped = NULL; + while ((popped = git_array_pop(stack)) != NULL) { + current = git_array_last(stack); + /* We've reached the top, current is the root tree */ + if (!current) + break; + + if ((error = create_popped_tree(current, popped, &component)) < 0) + goto cleanup; + } + + /* Write out the root tree */ + git__free(popped->name); + git_tree_free(popped->tree); + + error = git_treebuilder_write(out, popped->bld); + git_treebuilder_free(popped->bld); + if (error < 0) + goto cleanup; + } + +cleanup: + { + tree_stack_entry *e; + while ((e = git_array_pop(stack)) != NULL) { + git_treebuilder_free(e->bld); + git_tree_free(e->tree); + git__free(e->name); + } + } + + git_array_clear(stack); + git_vector_free(&entries); + return error; +} diff --git a/tests/object/tree/update.c b/tests/object/tree/update.c new file mode 100644 index 000000000..210a50474 --- /dev/null +++ b/tests/object/tree/update.c @@ -0,0 +1,167 @@ +#include "clar_libgit2.h" +#include "tree.h" + +static git_repository *g_repo; + +void test_object_tree_update__initialize(void) +{ + g_repo = cl_git_sandbox_init("testrepo"); +} + +void test_object_tree_update__cleanup(void) +{ + cl_git_sandbox_cleanup(); +} + +void test_object_tree_update__remove_blob(void) +{ + git_oid tree_index_id, tree_updater_id, base_id; + git_tree *base_tree; + git_index *idx; + const char *path = "README"; + + git_tree_update updates[] = { + { GIT_TREE_UPDATE_REMOVE, {{0}}, GIT_FILEMODE_BLOB /* ignored */, path}, + }; + + cl_git_pass(git_oid_fromstr(&base_id, "45dd856fdd4d89b884c340ba0e047752d9b085d6")); + cl_git_pass(git_tree_lookup(&base_tree, g_repo, &base_id)); + + /* Create it with an index */ + cl_git_pass(git_index_new(&idx)); + cl_git_pass(git_index_read_tree(idx, base_tree)); + cl_git_pass(git_index_remove(idx, path, 0)); + cl_git_pass(git_index_write_tree_to(&tree_index_id, idx, g_repo)); + git_index_free(idx); + + /* Perform the same operation via the tree updater */ + cl_git_pass(git_tree_create_updated(&tree_updater_id, g_repo, base_tree, 1, updates)); + + cl_assert_equal_oid(&tree_index_id, &tree_updater_id); + + git_tree_free(base_tree); +} + +void test_object_tree_update__replace_blob(void) +{ + git_oid tree_index_id, tree_updater_id, base_id; + git_tree *base_tree; + git_index *idx; + const char *path = "README"; + git_index_entry entry = { {0} }; + + git_tree_update updates[] = { + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, path}, + }; + + cl_git_pass(git_oid_fromstr(&base_id, "45dd856fdd4d89b884c340ba0e047752d9b085d6")); + cl_git_pass(git_tree_lookup(&base_tree, g_repo, &base_id)); + + /* Create it with an index */ + cl_git_pass(git_index_new(&idx)); + cl_git_pass(git_index_read_tree(idx, base_tree)); + + entry.path = path; + cl_git_pass(git_oid_fromstr(&entry.id, "3697d64be941a53d4ae8f6a271e4e3fa56b022cc")); + entry.mode = GIT_FILEMODE_BLOB; + cl_git_pass(git_index_add(idx, &entry)); + + cl_git_pass(git_index_write_tree_to(&tree_index_id, idx, g_repo)); + git_index_free(idx); + + /* Perform the same operation via the tree updater */ + cl_git_pass(git_oid_fromstr(&updates[0].id, "3697d64be941a53d4ae8f6a271e4e3fa56b022cc")); + cl_git_pass(git_tree_create_updated(&tree_updater_id, g_repo, base_tree, 1, updates)); + + cl_assert_equal_oid(&tree_index_id, &tree_updater_id); + + git_tree_free(base_tree); +} + +void test_object_tree_update__add_blobs(void) +{ + git_oid tree_index_id, tree_updater_id, base_id; + git_tree *base_tree; + git_index *idx; + git_index_entry entry = { {0} }; + int i; + const char *paths[] = { + "some/deep/path", + "some/other/path", + "a/path/elsewhere", + }; + + git_tree_update updates[] = { + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, paths[0]}, + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, paths[1]}, + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, paths[2]}, + }; + + cl_git_pass(git_oid_fromstr(&base_id, "45dd856fdd4d89b884c340ba0e047752d9b085d6")); + cl_git_pass(git_tree_lookup(&base_tree, g_repo, &base_id)); + + entry.mode = GIT_FILEMODE_BLOB; + cl_git_pass(git_oid_fromstr(&entry.id, "a71586c1dfe8a71c6cbf6c129f404c5642ff31bd")); + + for (i = 0; i < 3; i++) { + cl_git_pass(git_oid_fromstr(&updates[i].id, "a71586c1dfe8a71c6cbf6c129f404c5642ff31bd")); + } + + for (i = 0; i < 2; i++) { + int j; + + /* Create it with an index */ + cl_git_pass(git_index_new(&idx)); + + base_tree = NULL; + if (i == 1) { + cl_git_pass(git_tree_lookup(&base_tree, g_repo, &base_id)); + cl_git_pass(git_index_read_tree(idx, base_tree)); + } + + for (j = 0; j < 3; j++) { + entry.path = paths[j]; + cl_git_pass(git_index_add(idx, &entry)); + } + + cl_git_pass(git_index_write_tree_to(&tree_index_id, idx, g_repo)); + git_index_free(idx); + + /* Perform the same operations via the tree updater */ + cl_git_pass(git_tree_create_updated(&tree_updater_id, g_repo, base_tree, 3, updates)); + + cl_assert_equal_oid(&tree_index_id, &tree_updater_id); + } +} + +void test_object_tree_update__add_conflict(void) +{ + int i; + git_oid tree_updater_id; + git_tree_update updates[] = { + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, "a/dir/blob"}, + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, "a/dir"}, + }; + + for (i = 0; i < 2; i++) { + cl_git_pass(git_oid_fromstr(&updates[i].id, "a71586c1dfe8a71c6cbf6c129f404c5642ff31bd")); + } + + cl_git_fail(git_tree_create_updated(&tree_updater_id, g_repo, NULL, 2, updates)); +} + +void test_object_tree_update__add_conflict2(void) +{ + int i; + git_oid tree_updater_id; + git_tree_update updates[] = { + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_BLOB, "a/dir/blob"}, + { GIT_TREE_UPDATE_UPSERT, {{0}}, GIT_FILEMODE_TREE, "a/dir/blob"}, + }; + + for (i = 0; i < 2; i++) { + cl_git_pass(git_oid_fromstr(&updates[i].id, "a71586c1dfe8a71c6cbf6c129f404c5642ff31bd")); + } + + cl_git_fail(git_tree_create_updated(&tree_updater_id, g_repo, NULL, 2, updates)); +} |