Prepare "git-merge-tree" for future work

Prepare "git-merge-tree" for future work

[Linus Torvalds]

This changes how "git-merge-tree" works in two ways:

 - instead of printing things out as we walk the trees, we save the 
   results in memory
 - when we've walked the tree fully, we print out the results in a more 
   explicit way, describing the data.

This is basically preparatory work for extending the git-merge-tree 
functionality in interestign directions.

In particular, git-merge-tree is also how you would create a diff between 
two trees _without_ necessarily creating the merge commit itself. In other 
words, if you were to just wonder what another branch adds, you should be 
able to (eventually) just do

	git merge-tree -p $base HEAD $otherbranch

to generate a diff of what the merge would look like. The current merge 
tree already basically has all the smarts for this, and the explanation of 
the results just means that hopefully somebody else than me could do the 
boring work.

(You'd basically be able to do the above diff by just changing the 
printout format for the explanation, and making the "changed in both" 
first do a three-way merge before it diffs the result).

The other thing that the in-memory format allows is rename detection 
(which the current code does not do). That's the basic reason why we don't 
want to just explain the differences as we go along - because we want to 
be able to look at the _other_ differences to see whether the reason an 
entry got deleted in either branch was perhaps because it got added in 
another place..

Rename detection should be a fairly trivial pass in between the tree 
diffing and the explanation.

In the meantime, this doesn't actually do anything new, it just outputs 
the information in a more verbose manner. 

For an example merge, commit 5ab2c0a47574c92f92ea3709b23ca35d96319edd in 
the git tree works well and shows renames, along with true removals and 
additions and files that got changed in both branches. Too see that as a 
tree merge, do:

	git-merge-tree 64e86c57 c5c23745 928e47e3

where the two last ones are the tips that got merged, and the first one is 
the merge base.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
diff --git a/merge-tree.c b/merge-tree.c
index 9dcaab7..fd0c211 100644
--- a/merge-tree.c
+++ b/merge-tree.c
@@ -1,11 +1,79 @@
 #include "cache.h"
 #include "tree-walk.h"
+#include "blob.h"
 
 static const char merge_tree_usage[] = "git-merge-tree <base-tree> <branch1> <branch2>";
 static int resolve_directories = 1;
 
+struct merge_list {
+	struct merge_list *next;
+	struct merge_list *link;	/* other stages for this object */
+
+	unsigned int stage : 2,
+		     flags : 30;
+	unsigned int mode;
+	const char *path;
+	struct blob *blob;
+};
+
+static struct merge_list *merge_result, **merge_result_end = &merge_result;
+
+static void add_merge_entry(struct merge_list *entry)
+{
+	*merge_result_end = entry;
+	merge_result_end = &entry->next;
+}
+
 static void merge_trees(struct tree_desc t[3], const char *base);
 
+static const char *explanation(struct merge_list *entry)
+{
+	switch (entry->stage) {
+	case 0:
+		return "merged";
+	case 3:
+		return "added in remote";
+	case 2:
+		if (entry->link)
+			return "added in both";
+		return "added in local";
+	}
+
+	/* Existed in base */
+	entry = entry->link;
+	if (!entry)
+		return "removed in both";
+
+	if (entry->link)
+		return "changed in both";
+
+	if (entry->stage == 3)
+		return "removed in local";
+	return "removed in remote";
+}
+
+static void show_result_list(struct merge_list *entry)
+{
+	printf("%s\n", explanation(entry));
+	do {
+		struct merge_list *link = entry->link;
+		static const char *desc[4] = { "result", "base", "our", "their" };
+		printf("  %-6s %o %s %s\n", desc[entry->stage], entry->mode, sha1_to_hex(entry->blob->object.sha1), entry->path);
+		entry = link;
+	} while (entry);
+}
+
+static void show_result(void)
+{
+	struct merge_list *walk;
+
+	walk = merge_result;
+	while (walk) {
+		show_result_list(walk);
+		walk = walk->next;
+	}
+}
+
 /* An empty entry never compares same, not even to another empty entry */
 static int same_entry(struct name_entry *a, struct name_entry *b)
 {
@@ -15,24 +83,34 @@ static int same_entry(struct name_entry 
 		a->mode == b->mode;
 }
 
-static const char *sha1_to_hex_zero(const unsigned char *sha1)
+static struct merge_list *create_entry(unsigned stage, unsigned mode, const unsigned char *sha1, const char *path)
 {
-	if (sha1)
-		return sha1_to_hex(sha1);
-	return "0000000000000000000000000000000000000000";
+	struct merge_list *res = xmalloc(sizeof(*res));
+
+	memset(res, 0, sizeof(*res));
+	res->stage = stage;
+	res->path = path;
+	res->mode = mode;
+	res->blob = lookup_blob(sha1);
+	return res;
 }
 
 static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result)
 {
+	struct merge_list *orig, *final;
+	const char *path;
+
 	/* If it's already branch1, don't bother showing it */
 	if (!branch1)
 		return;
 
-	printf("0 %06o->%06o %s->%s %s%s\n",
-		branch1->mode, result->mode,
-		sha1_to_hex_zero(branch1->sha1),
-		sha1_to_hex_zero(result->sha1),
-		base, result->path);
+	path = strdup(mkpath("%s%s", base, result->path));
+	orig = create_entry(2, branch1->mode, branch1->sha1, path);
+	final = create_entry(0, result->mode, result->sha1, path);
+
+	final->link = orig;
+
+	add_merge_entry(final);
 }
 
 static int unresolved_directory(const char *base, struct name_entry n[3])
@@ -71,16 +149,40 @@ static int unresolved_directory(const ch
 	return 1;
 }
 
+
+static struct merge_list *link_entry(unsigned stage, const char *base, struct name_entry *n, struct merge_list *entry)
+{
+	const char *path;
+	struct merge_list *link;
+
+	if (!n->mode)
+		return entry;
+	if (entry)
+		path = entry->path;
+	else
+		path = strdup(mkpath("%s%s", base, n->path));
+	link = create_entry(stage, n->mode, n->sha1, path);
+	link->link = entry;
+	return link;
+}
+
 static void unresolved(const char *base, struct name_entry n[3])
 {
+	struct merge_list *entry = NULL;
+
 	if (unresolved_directory(base, n))
 		return;
-	if (n[0].sha1)
-		printf("1 %06o %s %s%s\n", n[0].mode, sha1_to_hex(n[0].sha1), base, n[0].path);
-	if (n[1].sha1)
-		printf("2 %06o %s %s%s\n", n[1].mode, sha1_to_hex(n[1].sha1), base, n[1].path);
-	if (n[2].sha1)
-		printf("3 %06o %s %s%s\n", n[2].mode, sha1_to_hex(n[2].sha1), base, n[2].path);
+
+	/*
+	 * Do them in reverse order so that the resulting link
+	 * list has the stages in order - link_entry adds new
+	 * links at the front.
+	 */
+	entry = link_entry(3, base, n + 2, entry);
+	entry = link_entry(2, base, n + 1, entry);
+	entry = link_entry(1, base, n + 0, entry);
+
+	add_merge_entry(entry);
 }
 
 /*
@@ -172,5 +274,7 @@ int main(int argc, char **argv)
 	free(buf1);
 	free(buf2);
 	free(buf3);
+
+	show_result();
 	return 0;
 }

Re: Prepare "git-merge-tree" for future work

[Linus Torvalds]

On Wed, 28 Jun 2006, Linus Torvalds wrote:
> 
> This changes how "git-merge-tree" works in two ways:

Ok, and here is a totally bogus (but hopefully instructive) patch on how 
to actually use this to prepare a diff.

I punted on trying to use the proper git diff interfaces (they are very 
tightly tied into the "diff_filespec" model - Junio, it might be nice if 
there was some way to use them in a setting where that isn't necessarily 
as natural). So the "diff" is actually just the raw output from xlib, but 
that wasn't really the point of this. 

It was more meant to do part of the the the "git-merge-one-file" logic, 
and use that logic together with the git-merge-tree logic to do a "merge" 
to diff against.

As an example, with this you can now do

	git-merge-tree $(git-merge-base HEAD next) HEAD next

to generate a "kind of" diff between the current HEAD and what would 
happen if it got merged with "next".

What (a properly done version of) this would be actually useful for is 
when you want to see what the merge results would be. For example, that's 
an integral part of sending a "please pull" request: telling the receiver 
what the diffstat should be after the pull (even though we don't _locally_ 
want to actually execute that merge - we expect the remote side to do so).

Anybody want to actually make this useful for something like that?

		Linus

----
diff --git a/Makefile b/Makefile
index cde619c..e880457 100644
--- a/Makefile
+++ b/Makefile
@@ -217,7 +217,7 @@ LIB_OBJS = \
 	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
 	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
 	fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
-	alloc.o $(DIFF_OBJS)
+	alloc.o merge-file.o $(DIFF_OBJS)
 
 BUILTIN_OBJS = \
 	builtin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \
diff --git a/merge-file.c b/merge-file.c
new file mode 100644
index 0000000..4fedd6b
--- /dev/null
+++ b/merge-file.c
@@ -0,0 +1,107 @@
+#include "cache.h"
+#include "run-command.h"
+#include "blob.h"
+
+static void rm_temp_file(const char *filename)
+{
+	unlink(filename);
+}
+
+static const char *write_temp_file(struct blob *blob)
+{
+	int fd;
+	const char *tmp = getenv("TMPDIR");
+	unsigned long size;
+	char *filename, type[20];
+	void *buf;
+
+	if (!tmp)
+		tmp = "/tmp";
+	filename = mkpath("%s/%s", tmp, "git-tmp-XXXXXX");
+	fd = mkstemp(filename);
+	if (fd < 0)
+		return NULL;
+	filename = strdup(filename);
+	buf = read_sha1_file(blob->object.sha1, type, &size);
+	if (buf) {
+		if (size != xwrite(fd, buf, size)) {
+			rm_temp_file(filename);
+			return NULL;
+		}
+		free(buf);
+	}
+	close(fd);
+	return filename;
+}
+
+static void *read_temp_file(const char *filename, unsigned long *size)
+{
+	struct stat st;
+	char *buf = NULL;
+	int fd = open(filename, O_RDONLY);
+	if (fd < 0)
+		return NULL;
+	if (!fstat(fd, &st)) {
+		*size = st.st_size;
+		buf = xmalloc(st.st_size);
+		if (st.st_size != xread(fd, buf, st.st_size)) {
+			free(buf);
+			buf = NULL;
+		}
+	}
+	close(fd);
+	return buf;
+}
+
+void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)
+{
+	const char *t1, *t2, *t3;
+	char type[20];
+
+	if (base) {
+		int code;
+		void *res;
+
+		/*
+		 * Removed in either branch?
+		 *
+		 * NOTE! This depends on the caller having done the
+		 * proper warning about removing a file that got
+		 * modified in the other branch!
+		 */
+		if (!our || !their)
+			return NULL;
+		t1 = write_temp_file(base);
+		t2 = write_temp_file(our);
+		t3 = write_temp_file(their);
+		res = NULL;
+		if (t1 && t2 && t3) {
+			code = run_command("merge", t2, t1, t3, NULL);
+			if (!code || code == -1)
+				res = read_temp_file(t2, size);
+		}
+		rm_temp_file(t1);
+		rm_temp_file(t2);
+		rm_temp_file(t3);
+		return res;
+	}
+
+	if (!our)
+		return read_sha1_file(their->object.sha1, type, size);
+	if (!their)
+		return read_sha1_file(our->object.sha1, type, size);
+
+	/*
+	 * Added in both!
+	 *
+	 * This is nasty.
+	 *
+	 * We should do something like 
+	 *
+	 *	git diff our their | git-apply --no-add
+	 *
+	 * to generate a "minimal common file" to be used
+	 * as a base. Right now we punt.
+	 */
+	return NULL;
+}
diff --git a/merge-tree.c b/merge-tree.c
index fd0c211..7cf00be 100644
--- a/merge-tree.c
+++ b/merge-tree.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "tree-walk.h"
+#include "xdiff-interface.h"
 #include "blob.h"
 
 static const char merge_tree_usage[] = "git-merge-tree <base-tree> <branch1> <branch2>";
@@ -52,6 +53,77 @@ static const char *explanation(struct me
 	return "removed in remote";
 }
 
+extern void *merge_file(struct blob *, struct blob *, struct blob *, unsigned long *);
+
+static void *result(struct merge_list *entry, unsigned long *size)
+{
+	char type[20];
+	struct blob *base, *our, *their;
+
+	if (!entry->stage)
+		return read_sha1_file(entry->blob->object.sha1, type, size);
+	base = NULL;
+	if (entry->stage == 1) {
+		base = entry->blob;
+		entry = entry->link;
+	}
+	our = NULL;
+	if (entry && entry->stage == 2) {
+		our = entry->blob;
+		entry = entry->link;
+	}
+	their = NULL;
+	if (entry)
+		their = entry->blob;
+	return merge_file(base, our, their, size);
+}
+
+static void *origin(struct merge_list *entry, unsigned long *size)
+{
+	char type[20];
+	while (entry) {
+		if (entry->stage == 2)
+			return read_sha1_file(entry->blob->object.sha1, type, size);
+		entry = entry->link;
+	}
+	return NULL;
+}
+
+static int show_outf(void *priv_, mmbuffer_t *mb, int nbuf)
+{
+	int i;
+	for (i = 0; i < nbuf; i++)
+		printf("%.*s", (int) mb[i].size, mb[i].ptr);
+	return 0;
+}
+
+static void show_diff(struct merge_list *entry)
+{
+	unsigned long size;
+	mmfile_t src, dst;
+	xpparam_t xpp;
+	xdemitconf_t xecfg;
+	xdemitcb_t ecb;
+
+	xpp.flags = XDF_NEED_MINIMAL;
+	xecfg.ctxlen = 3;
+	xecfg.flags = 0;
+	ecb.outf = show_outf;
+	ecb.priv = NULL;
+
+	src.ptr = origin(entry, &size);
+	if (!src.ptr)
+		size = 0;
+	src.size = size;
+	dst.ptr = result(entry, &size);
+	if (!dst.ptr)
+		size = 0;
+	dst.size = size;
+	xdl_diff(&src, &dst, &xpp, &xecfg, &ecb);
+	free(src.ptr);
+	free(dst.ptr);
+}
+
 static void show_result_list(struct merge_list *entry)
 {
 	printf("%s\n", explanation(entry));
@@ -70,6 +142,7 @@ static void show_result(void)
 	walk = merge_result;
 	while (walk) {
 		show_result_list(walk);
+		show_diff(walk);
 		walk = walk->next;
 	}
 }

Re: Prepare "git-merge-tree" for future work

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> I punted on trying to use the proper git diff interfaces (they are very 
> tightly tied into the "diff_filespec" model - Junio, it might be nice if 
> there was some way to use them in a setting where that isn't necessarily 
> as natural).

I am not quite sure what you mean.  You have a sets of
filepairs, each of which is a pair of filespec, each of which
describes the blob.  And diff is about comparing them, possibly
after running rename detection, pickaxe filtering and such.  If
the merge-tree's internal representation for each blob is more
efficient or easier to use we could switch to use it as an
improved implementation of filespec but I do not think that is
what you meant, because I suspect that approach does not break
diff from the "model".  Care to elaborate a bit more please?

Re: Prepare "git-merge-tree" for future work

[Linus Torvalds]

On Thu, 29 Jun 2006, Junio C Hamano wrote:

> Linus Torvalds <torvalds@osdl.org> writes:
> 
> > I punted on trying to use the proper git diff interfaces (they are very 
> > tightly tied into the "diff_filespec" model - Junio, it might be nice if 
> > there was some way to use them in a setting where that isn't necessarily 
> > as natural).
> 
> I am not quite sure what you mean.

For what I wanted to do, I didn't see an easy way to add/populate a new 
filespec. It was easier to just use the raw libxdiff interfaces, but 
that's really just because I know the interfaces.

In contrast, the ones to diff_filespec I've never really used, and I did 
not want to compare blob objects, I very much wanted to compare in-memory 
buffers (_and_ potentially blobs).

So if you can show an easy example of how to populate a set of filespec 
pairs (not with blobs - with in-memory generated data) and insert them 
onto the lists, that would be good.

In fact, maybe you can show me what git-merge-tree needs to do..

Hint hint.

		Linus

Re: Prepare "git-merge-tree" for future work

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> In contrast, the ones to diff_filespec I've never really used, and I did 
> not want to compare blob objects, I very much wanted to compare in-memory 
> buffers (_and_ potentially blobs).
>
> So if you can show an easy example of how to populate a set of filespec 
> pairs (not with blobs - with in-memory generated data) and insert them 
> onto the lists, that would be good.

Ah, I see.  Your origin() function always returns a in-core
buffer from an existing blob (or NULL if it is a new file) but
result() returns either an existing blob resulting from the
tree-level merge, or a 3-way content merge result that does not
have an existing blob, and it is not obvious how to express the
latter as a filespec (all other cases you can stuff the blob
object name in the sha1[] member and if you choose to do the
read_sha1_file() yourself store the result in data member or you
can let diff_populate_filespec() read the data when diff
machinery needs it).

I think a filespec that has 0{40} sha1, with data already
populated and should_free/should_munmap members both set to
false might work for the in-memory data but I haven't tried.

I'd take the hint, and I will (eventually) take a look at it
if nobody beats me to it, but most likely not now, sorry.