threads / discuss / 4698

Prepare "git-merge-tree" for future work

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

## tl;dr

5 messages between Jun 28, 2006 and Jun 30, 2006.

replies: 4people: 2as markdown or json

Linus Torvalds· Jun 28, 2006, 18:18 UTC · lore

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

Linus Torvalds· Jun 28, 2006, 21:09 UTC · re: Linus Torvalds · lore

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

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

Junio C Hamano· Jun 30, 2006, 02:04 UTC · re: Linus Torvalds · lore

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

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?

Linus Torvalds· Jun 30, 2006, 02:32 UTC · re: Junio C Hamano · lore

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

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

Show 8 quoted lines

> 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

Junio C Hamano· Jun 30, 2006, 20:52 UTC · re: Linus Torvalds · lore

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

Linus Torvalds <torvalds@osdl.org> writes:

Show 7 quoted lines

> 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.