Improved three-way blob merging code

This fleshes out the code that generates a three-way merge of a set of 
blobs.

It still actually does the three-way merge using an external executable 
(ie just calling "merge"), but the interfaces have been cleaned up a lot 
and are now fully based on the 'mmfile_t' interface, so if libxdiff were 
to ever grow a compatible three-way-merge, it could probably be directly
plugged in.

It also uses the previous XDL_EMIT_COMMON functionality extension to 
libxdiff to generate a made-up base file for the merge for the case where 
no base file previously existed. This should be equivalent to what we 
currently do in git-merge-one-file.sh:

	diff -u -La/$orig -Lb/$orig $orig $src2 | git-apply --no-add

except it should be much simpler and can be done using the direct libxdiff 
interfaces.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---

It would be lovely if libxdiff did a 3-way merge on its own, but this 
basically approximates it within that three_way_filemerge() function 
using external functionality.

The caller is, of course, still expected to do all the other proper magic 
(ie do things like resolve renames, mode differences, and all the trivial 
cases), and the example merge-tree.c code I posted earlier is obviously 
_not_ careful enough to be a real merge routine.

But we all have to start somewhere.

diff --git a/merge-file.c b/merge-file.c
index 4fedd6b..f32c653 100644
--- a/merge-file.c
+++ b/merge-file.c

@@ -1,19 +1,19 @@
 #include "cache.h"
 #include "run-command.h"
+#include "xdiff-interface.h"
 #include "blob.h"
 
 static void rm_temp_file(const char *filename)
 {
 	unlink(filename);
+	free((void *)filename);
 }
 
-static const char *write_temp_file(struct blob *blob)
+static const char *write_temp_file(mmfile_t *f)
 {
 	int fd;
 	const char *tmp = getenv("TMPDIR");
-	unsigned long size;
-	char *filename, type[20];
-	void *buf;
+	char *filename;
 
 	if (!tmp)
 		tmp = "/tmp";

@@ -22,13 +22,9 @@ static const char *write_temp_file(struc
 	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);
+	if (f->size != xwrite(fd, f->ptr, f->size)) {
+		rm_temp_file(filename);
+		return NULL;
 	}
 	close(fd);
 	return filename;

@@ -53,55 +49,118 @@ static void *read_temp_file(const char *
 	return buf;
 }
 
-void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)
+static int fill_mmfile_blob(mmfile_t *f, struct blob *obj)
 {
-	const char *t1, *t2, *t3;
+	void *buf;
+	unsigned long size;
 	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;
+	buf = read_sha1_file(obj->object.sha1, type, &size);
+	if (!buf)
+		return -1;
+	if (strcmp(type, blob_type))
+		return -1;
+	f->ptr = buf;
+	f->size = size;
+	return 0;
+}
+
+static void free_mmfile(mmfile_t *f)
+{
+	free(f->ptr);
+}
+
+static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t *their, unsigned long *size)
+{
+	void *res;
+	const char *t1, *t2, *t3;
+
+	t1 = write_temp_file(base);
+	t2 = write_temp_file(our);
+	t3 = write_temp_file(their);
+	res = NULL;
+	if (t1 && t2 && t3) {
+		int 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);
+static int common_outf(void *priv_, mmbuffer_t *mb, int nbuf)
+{
+	int i;
+	mmfile_t *dst = priv_;
+
+	for (i = 0; i < nbuf; i++) {
+		memcpy(dst->ptr + dst->size, mb[i].ptr, mb[i].size);
+		dst->size += mb[i].size;
+	}
+	return 0;
+}
+
+static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
+{
+	unsigned long size = f1->size < f2->size ? f1->size : f2->size;
+	void *ptr = xmalloc(size);
+	xpparam_t xpp;
+	xdemitconf_t xecfg;
+	xdemitcb_t ecb;
+
+	xpp.flags = XDF_NEED_MINIMAL;
+	xecfg.ctxlen = 3;
+	xecfg.flags = XDL_EMIT_COMMON;
+	ecb.outf = common_outf;
+
+	res->ptr = ptr;
+	res->size = 0;
+
+	ecb.priv = res;
+	return xdl_diff(f1, f2, &xpp, &xecfg, &ecb);
+}
+
+void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)
+{
+	void *res = NULL;
+	mmfile_t f1, f2, common;
 
 	/*
-	 * Added in both!
-	 *
-	 * This is nasty.
-	 *
-	 * We should do something like 
+	 * Removed in either branch?
 	 *
-	 *	git diff our their | git-apply --no-add
-	 *
-	 * to generate a "minimal common file" to be used
-	 * as a base. Right now we punt.
+	 * NOTE! This depends on the caller having done the
+	 * proper warning about removing a file that got
+	 * modified in the other branch!
 	 */
-	return NULL;
+	if (!our || !their) {
+		char type[20];
+		if (base)
+			return NULL;
+		if (!our)
+			our = their;
+		return read_sha1_file(our->object.sha1, type, size);
+	}
+
+	if (fill_mmfile_blob(&f1, our) < 0)
+		goto out_no_mmfile;
+	if (fill_mmfile_blob(&f2, their) < 0)
+		goto out_free_f1;
+
+	if (base) {
+		if (fill_mmfile_blob(&common, base) < 0)
+			goto out_free_f2_f1;
+	} else {
+		if (generate_common_file(&common, &f1, &f2) < 0)
+			goto out_free_f2_f1;
+	}
+	res = three_way_filemerge(&common, &f1, &f2, size);
+	free_mmfile(&common);
+out_free_f2_f1:
+	free_mmfile(&f2);
+out_free_f1:
+	free_mmfile(&f1);
+out_no_mmfile:
+	return res;
 }

On 6/29/06, Linus Torvalds [off-list ref] wrote:

+static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t *their, unsigned long *size)
+{

...

+       if (t1 && t2 && t3) {
+               int code = run_command("merge", t2, t1, t3, NULL);

This does not use the labels of merge(1) and the merged file will contain
the names of temporary files at conflict places, which is very confusing if
you happen to loose context while doing a merge with lots of conflicts.

On Thu, 29 Jun 2006, Alex Riesen wrote:

On 6/29/06, Linus Torvalds [off-list ref] wrote:

quoted

+static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t
*their, unsigned long *size)
+{

...

quoted

+       if (t1 && t2 && t3) {
+               int code = run_command("merge", t2, t1, t3, NULL);

This does not use the labels of merge(1) and the merged file will contain
the names of temporary files at conflict places, which is very confusing if
you happen to loose context while doing a merge with lots of conflicts.

Yes. 

I was really really _really_ just hoping that I could do the nasty core 
code that others might feel uncomfortable with, and get it working from a 
_technical_ level well enough that others (hint hint) would decide that 
they can fix up the details.

Getting the first version working is often the hardest. When you reach the 
point of "it works, but I want to extend it to do X", you've usually 
already gotten pretty far.

Anyway, all of this was really just preparatory work to show what 
git-merge-tree does. A few more improvements to git-merge-tree, and 
hopefully it can start being useful - perhaps not initially for actually 
merging, but for doing a tree-level three-way diff between two branches.

In other words, my current goal is really do make it possible to get good 
diffs out of git from two branches that aren't directly related. You and 
Dscho seem to be doing well on the git-merge-recursive front, so my 
personal goal is actually to be able to get a saner diff than what

	git diff mine..theirs

gives you.

The above "git diff" is a perfectly fine thing to do, but it's usually not 
what you actually _want_. Almost always, what you want a diff between two 
branches, what you want is actually the diff after a merge of the 
branches, not the raw _current_ differences.

For example, look at our current 

	Documentation/howto/using-topic-branches.txt

file, and realize that the current scripts it suggests are actually 
broken:

	To create diffstat and shortlog summaries of changes to include in 
	a "pleasepull" request to Linus you can use:

	 $ git-whatchanged -p release ^linus | diffstat -p1
	and
	 $ git-whatchanged release ^linus | git-shortlog

where that "git-whatchanged -p release ^linus | diffstat -p1" won't 
actually be what I see when I merge (although it will hopefully be close 
enough). Also, there's no indication that the merge will fail when I pull, 
something that _would_ be very useful.

IOW, what I'd like git-merge-tree to do is to be able to at a minimum say:

 - will a merge succeed cleanly, and if not, show me where the problem 
   spots are.
 - what will the result of the merge look like.

because that's actually what a downstream developer wants to do. He'd just 
do

	git fetch linus
	git show-changes linus..my-branch

which would basically be the preparatory thing for sending me an email 
saying "please merge 'my-branch', and you'll see this".

Now, obviously, I think that there's a _lot_ of overlap between doing this 
and actually doing the merge itself, so hopefully the things I do will at 
least have some things in common and perhaps help you do the proper 
recursive merger.

But one thing I was actually hoping to do was to literally be able to do 
this without either tree being checked out, exactly so that you can check 
the status of a branch that you may not even _be_ on (eg that "my-branch" 
in the example above may not even be your current HEAD: you might be on 
your development branch when you actually ask me to pull from your stable 
branch).

So the "show differences" has a lot in common with "merge them", but there 
are literally a few stages missing. One thing missing in just showing 
differences is that you can't actually fix up the merge clashes: if you 
don't have a checked-out tree, you're not going to be able to do a real 
merge. But you can see what a merge would _look_ like, and whether there 
are any clashes that you will have to fix..

		Linus

On Wed, 28 Jun 2006, Linus Torvalds wrote:

It would be lovely if libxdiff did a 3-way merge on its own, but this
basically approximates it within that three_way_filemerge() function
using external functionality.

This is my todo-list, that unfortunately is pretty crowded nowadays. I'll 
come graveling you main window once I have it ;)



- Davide

Linus Torvalds, Thu, Jun 29, 2006 19:45:20 +0200:

IOW, what I'd like git-merge-tree to do is to be able to at a minimum say:

 - will a merge succeed cleanly, and if not, show me where the problem 
   spots are.
 - what will the result of the merge look like.

because that's actually what a downstream developer wants to do. He'd just 
do

	git fetch linus
	git show-changes linus..my-branch

which would basically be the preparatory thing for sending me an email 
saying "please merge 'my-branch', and you'll see this".

it's a "git show-merge linus..my-branch" :)

Now, obviously, I think that there's a _lot_ of overlap between doing this 
and actually doing the merge itself, so hopefully the things I do will at 
least have some things in common and perhaps help you do the proper 
recursive merger.

I certanly hope so: only the last pass of the recursive merge seem to
really need the index. It's use in all the previuos recursions looks
more like abuse.