Introduce a function to create a tree based on a different onecmn/tree-update

Instead of going through the usual steps of reading a tree recursively
into an index, modifying it and writing it back out as a tree, introduce
a function to perform simple updates more efficiently.

`git_tree_create_updated` avoids reading trees which are not modified
and supports upsert and delete operations. It is not as versatile as
modifying the index, but it makes some common operations much more
efficient.

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));
+}