[PATCH 26/32] Add upload-narrow-base command

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

A narrow repo only has enough trees within a given subtree. That would
mean even a trivial three-way merge is impossible because it needs
full tree walk.

On the other hand, doing merge remotely is non-sense because conflicts
can happen, and there would be no index on remote side for people to
inspect/resolve conflicts. Such a merge in narrow repo would be
splitted into two phases: 3-way trivial merge for everything outside
narrow tree, and real merge within narrow tree.

The first phase is done in server by this command. Given two commits,
it will do 3-way merge and return result trees of the merge (no blob
should be created because this is trivial merge). No new objects will
be stored in server after this operation.

For local repo, parent trees of narrow tree should be enough for
join_narrow_tree() to do its job. But because remote side does not
store any result objects, in order to push a merge, we would need to
send all necessary trees that the remote side does not have.

For this reason, upload-narrow-base would return a pack of all new
trees (those that are not in either merge parents). It is expected
that git client would push all these trees back to server when it does
a push.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile                     |    1 +
 builtin.h                    |    1 +
 builtin/upload-narrow-base.c |  215 ++++++++++++++++++++++++++++++++++++++++++
 git.c                        |    1 +
 4 files changed, 218 insertions(+), 0 deletions(-)
 create mode 100644 builtin/upload-narrow-base.c

diff --git a/Makefile b/Makefile
index 54c435e..7b33a0e 100644
--- a/Makefile
+++ b/Makefile
@@ -737,6 +737,7 @@ BUILTIN_OBJS += builtin/update-index.o
 BUILTIN_OBJS += builtin/update-ref.o
 BUILTIN_OBJS += builtin/update-server-info.o
 BUILTIN_OBJS += builtin/upload-archive.o
+BUILTIN_OBJS += builtin/upload-narrow-base.o
 BUILTIN_OBJS += builtin/var.o
 BUILTIN_OBJS += builtin/verify-pack.o
 BUILTIN_OBJS += builtin/verify-tag.o
diff --git a/builtin.h b/builtin.h
index ed6ee26..0383328 100644
--- a/builtin.h
+++ b/builtin.h
@@ -131,6 +131,7 @@ extern int cmd_update_index(int argc, const char **argv, const char *prefix);
 extern int cmd_update_ref(int argc, const char **argv, const char *prefix);
 extern int cmd_update_server_info(int argc, const char **argv, const char *prefix);
 extern int cmd_upload_archive(int argc, const char **argv, const char *prefix);
+extern int cmd_upload_narrow_base(int argc, const char **argv, const char *prefix);
 extern int cmd_upload_tar(int argc, const char **argv, const char *prefix);
 extern int cmd_var(int argc, const char **argv, const char *prefix);
 extern int cmd_verify_tag(int argc, const char **argv, const char *prefix);
diff --git a/builtin/upload-narrow-base.c b/builtin/upload-narrow-base.c
new file mode 100644
index 0000000..f31f03e
--- /dev/null
+++ b/builtin/upload-narrow-base.c
@@ -0,0 +1,215 @@
+#include "cache.h"
+#include "builtin.h"
+#include "cache-tree.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "commit.h"
+#include "revision.h"
+#include "unpack-trees.h"
+#include "pkt-line.h"
+#include "pack.h"
+#include "transport.h"
+#include "sideband.h"
+
+const char *narrow_prefix;
+
+#define PARENT1		(1u<<16)
+#define PARENT2		(1u<<17)
+
+static void write_object(struct tree *t,
+			 const char *base,
+			 struct simple_pack *pack)
+{
+	struct name_entry entry;
+	struct tree *subtree;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	int len = 0;
+	void *buffer;
+	char *path = xmalloc(PATH_MAX);
+
+	if (base) {
+		len = strlen(base);
+		memcpy(path, base, len);
+		path[len++] = '/';
+	}
+
+	buffer = read_sha1_file(t->object.sha1, &type, &size);
+	if (!buffer || type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(t->object.sha1));
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+
+		subtree = lookup_tree(entry.sha1);
+		strcpy(path+len, entry.path);
+		if (!strcmp(path, narrow_prefix))
+			;
+		else if (!prefixcmp(narrow_prefix, path) && /* subtree predecessor */
+			 narrow_prefix[strlen(path)] == '/')
+			;
+		else if (!(subtree->object.flags & (PARENT1 | PARENT2))) {
+			subtree->object.flags |= TMP_MARK; /* non recursive */
+			write_object_to_pack(pack, entry.sha1, subtree->buffer,
+					     subtree->size, OBJ_TREE);
+		}
+
+		write_object(subtree, path, pack);
+	}
+	free(path);
+	free(buffer);
+}
+
+static int read_tree_trivial(struct tree *trees[3])
+{
+	int i;
+	struct tree_desc t[3];
+	struct unpack_trees_options opts;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = 2;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.merge = 1;
+	opts.fn = threeway_merge;
+	cache_tree_free(&active_cache_tree);
+	for (i = 0; i < 3; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(3, t, &opts))
+		return -1;
+	return 0;
+}
+
+static int create_tree_object(const void *buf, unsigned long len,
+			      const char *type, unsigned char *sha1)
+{
+	struct tree *t;
+	if (type != tree_type)
+		die("Invalid type %s", type);
+	hash_sha1_file(buf, len, tree_type, sha1);
+	t = lookup_tree(sha1);
+	if (!t->object.parsed) {
+		t->buffer = xmalloc(len);
+		memcpy(t->buffer, buf, len);
+		t->size = len;
+		t->object.parsed = 1;
+	}
+	return 0;
+}
+
+int cmd_upload_narrow_base(int argc, const char **argv, const char *prefix)
+{
+	char buf[LARGE_PACKET_MAX];
+	unsigned char sha1[2][20];
+	struct tree *t[3];
+	struct commit_list *common;
+	struct simple_pack pack;
+	int i, len;
+
+	strcpy(buf, argv[1]); /* enter-repo smudges its argument */
+
+	if (!enter_repo(buf, 0))
+		die("'%s' does not appear to be a git repository", buf);
+
+	len = packet_read_line(0, buf, sizeof(buf));
+	if (!len)
+		die("narrow-merge: narrow-tree missing");
+	if (!prefixcmp(buf, "narrow-tree ")) {
+		narrow_prefix = xstrdup(buf+12);
+		len = strlen(narrow_prefix);
+		if (!len)
+			die("narrow-merge: empty narrow-tree");
+		if (narrow_prefix[len-1] == '/')
+			die("narrow-merge: trailing slash not allowed %s", narrow_prefix);
+	}
+	else
+		die("narrow-merge: invalid narrow-tree %s", buf);
+
+	for (i = 0; i < 2; i++) {
+		len = packet_read_line(0, buf, sizeof(buf));
+		if (!len)
+			die("narrow-merge: parent missing");
+		if (!prefixcmp(buf, "parent ")) {
+			if (get_sha1_hex(buf+7, sha1[i]))
+				die("narrow-merge: invalid SHA1 %s", buf);
+			if (!lookup_commit_reference(sha1[i]))
+				return 1;
+		}
+		else
+			die("narrow-merge: invalid parent %s", buf);
+	}
+	len = packet_read_line(0, buf, sizeof(buf));
+	if (len)
+		die("narrow-merge: expected a flush");
+
+	common = get_merge_bases(lookup_commit(sha1[0]),
+				 lookup_commit(sha1[1]),
+				 1);
+	if (!common || common->next)
+		die("narrow-merge: no common or too many common found, can't merge");
+
+	t[0] = common->item->tree;
+	t[1] = lookup_commit(sha1[0])->tree;
+	t[2] = lookup_commit(sha1[1])->tree;
+
+	/* Three way merge to index */
+	discard_index(&the_index);
+	if (read_tree_trivial(t))
+		die("narrow-merge: non trivial merge");
+
+	/* Make sure merge is good (no conflicts outside subtree) */
+	len = strlen(narrow_prefix);
+	for (i = 0; i < the_index.cache_nr; i++) {
+		struct cache_entry *ce = the_index.cache[i];
+
+		/*
+		 * No staged entries within subtree, prefer stage 1:
+		 * (the goal is no staged entries, the content is
+		 * not really important as subtree client must do
+		 * a real merge within subtree)
+		 * stage 0: move on
+		 * stage 1: turn it to stage 0,
+		 * stage 2: mark CE_REMOVE
+		 */
+		if (!prefixcmp(ce->name, narrow_prefix) &&
+		    ce->name[len] == '/') {
+			switch (ce_stage(ce)) {
+			case 1: ce->ce_flags &= ~CE_STAGEMASK; break;
+			case 2: ce->ce_flags |= CE_REMOVE; break;
+			}
+			continue;
+		}
+		if (ce_stage(ce))
+			die("git upload-pack: unmerged entry %s", ce->name);
+	}
+
+	/* Generate trees in memory */
+	the_index.cache_tree = cache_tree();
+	if (cache_tree_update_fn(the_index.cache_tree,
+				 the_index.cache,
+				 the_index.cache_nr,
+				 create_tree_object,
+				 0, 0))
+		die("narrow-merge: error generating trees");
+
+	/* Everything is OK. Send root SHA-1 */
+	packet_write(1, "ACK %s\n", sha1_to_hex(the_index.cache_tree->sha1));
+
+	/* Traverse and send only missing trees */
+	memset(&pack, 0, sizeof(pack));
+	pack.fd = 1;
+	create_pack(&pack);
+
+	t[0] = lookup_tree(the_index.cache_tree->sha1);
+	set_tree_marks(t[1], PARENT1);
+	set_tree_marks(t[2], PARENT2);
+	write_object(t[0], NULL, &pack);
+
+	close_pack(&pack);
+	return 0;
+}
diff --git a/git.c b/git.c
index f37028b..edb379f 100644
--- a/git.c
+++ b/git.c
@@ -392,6 +392,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "update-ref", cmd_update_ref, RUN_SETUP },
 		{ "update-server-info", cmd_update_server_info, RUN_SETUP },
 		{ "upload-archive", cmd_upload_archive },
+		{ "upload-narrow-base", cmd_upload_narrow_base },
 		{ "var", cmd_var },
 		{ "verify-tag", cmd_verify_tag, RUN_SETUP },
 		{ "version", cmd_version },
-- 
1.7.1.rc1.69.g24c2f7