{"thread":{"id":"4698","subject":"Prepare \"git-merge-tree\" for future work","startedAt":"2006-06-28T18:18:27Z","lastAt":"2006-06-30T20:52:27Z","messageCount":5,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22747","messageId":"Pine.LNX.4.64.0606281054470.3782@g5.osdl.org","threadId":"4698","inReplyTo":null,"subject":"Prepare \"git-merge-tree\" for future work","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-28T18:18:27Z","receivedAt":"2006-06-28T18:18:27Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis changes how \"git-merge-tree\" works in two ways:\n\n - instead of printing things out as we walk the trees, we save the \n   results in memory\n - when we've walked the tree fully, we print out the results in a more \n   explicit way, describing the data.\n\nThis is basically preparatory work for extending the git-merge-tree \nfunctionality in interestign directions.\n\nIn particular, git-merge-tree is also how you would create a diff between \ntwo trees _without_ necessarily creating the merge commit itself. In other \nwords, if you were to just wonder what another branch adds, you should be \nable to (eventually) just do\n\n\tgit merge-tree -p $base HEAD $otherbranch\n\nto generate a diff of what the merge would look like. The current merge \ntree already basically has all the smarts for this, and the explanation of \nthe results just means that hopefully somebody else than me could do the \nboring work.\n\n(You'd basically be able to do the above diff by just changing the \nprintout format for the explanation, and making the \"changed in both\" \nfirst do a three-way merge before it diffs the result).\n\nThe other thing that the in-memory format allows is rename detection \n(which the current code does not do). That's the basic reason why we don't \nwant to just explain the differences as we go along - because we want to \nbe able to look at the _other_ differences to see whether the reason an \nentry got deleted in either branch was perhaps because it got added in \nanother place..\n\nRename detection should be a fairly trivial pass in between the tree \ndiffing and the explanation.\n\nIn the meantime, this doesn't actually do anything new, it just outputs \nthe information in a more verbose manner. \n\nFor an example merge, commit 5ab2c0a47574c92f92ea3709b23ca35d96319edd in \nthe git tree works well and shows renames, along with true removals and \nadditions and files that got changed in both branches. Too see that as a \ntree merge, do:\n\n\tgit-merge-tree 64e86c57 c5c23745 928e47e3\n\nwhere the two last ones are the tips that got merged, and the first one is \nthe merge base.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\ndiff --git a/merge-tree.c b/merge-tree.c\nindex 9dcaab7..fd0c211 100644\n--- a/merge-tree.c\n+++ b/merge-tree.c\n@@ -1,11 +1,79 @@\n #include \"cache.h\"\n #include \"tree-walk.h\"\n+#include \"blob.h\"\n \n static const char merge_tree_usage[] = \"git-merge-tree <base-tree> <branch1> <branch2>\";\n static int resolve_directories = 1;\n \n+struct merge_list {\n+\tstruct merge_list *next;\n+\tstruct merge_list *link;\t/* other stages for this object */\n+\n+\tunsigned int stage : 2,\n+\t\t     flags : 30;\n+\tunsigned int mode;\n+\tconst char *path;\n+\tstruct blob *blob;\n+};\n+\n+static struct merge_list *merge_result, **merge_result_end = &merge_result;\n+\n+static void add_merge_entry(struct merge_list *entry)\n+{\n+\t*merge_result_end = entry;\n+\tmerge_result_end = &entry->next;\n+}\n+\n static void merge_trees(struct tree_desc t[3], const char *base);\n \n+static const char *explanation(struct merge_list *entry)\n+{\n+\tswitch (entry->stage) {\n+\tcase 0:\n+\t\treturn \"merged\";\n+\tcase 3:\n+\t\treturn \"added in remote\";\n+\tcase 2:\n+\t\tif (entry->link)\n+\t\t\treturn \"added in both\";\n+\t\treturn \"added in local\";\n+\t}\n+\n+\t/* Existed in base */\n+\tentry = entry->link;\n+\tif (!entry)\n+\t\treturn \"removed in both\";\n+\n+\tif (entry->link)\n+\t\treturn \"changed in both\";\n+\n+\tif (entry->stage == 3)\n+\t\treturn \"removed in local\";\n+\treturn \"removed in remote\";\n+}\n+\n+static void show_result_list(struct merge_list *entry)\n+{\n+\tprintf(\"%s\\n\", explanation(entry));\n+\tdo {\n+\t\tstruct merge_list *link = entry->link;\n+\t\tstatic const char *desc[4] = { \"result\", \"base\", \"our\", \"their\" };\n+\t\tprintf(\"  %-6s %o %s %s\\n\", desc[entry->stage], entry->mode, sha1_to_hex(entry->blob->object.sha1), entry->path);\n+\t\tentry = link;\n+\t} while (entry);\n+}\n+\n+static void show_result(void)\n+{\n+\tstruct merge_list *walk;\n+\n+\twalk = merge_result;\n+\twhile (walk) {\n+\t\tshow_result_list(walk);\n+\t\twalk = walk->next;\n+\t}\n+}\n+\n /* An empty entry never compares same, not even to another empty entry */\n static int same_entry(struct name_entry *a, struct name_entry *b)\n {\n@@ -15,24 +83,34 @@ static int same_entry(struct name_entry \n \t\ta->mode == b->mode;\n }\n \n-static const char *sha1_to_hex_zero(const unsigned char *sha1)\n+static struct merge_list *create_entry(unsigned stage, unsigned mode, const unsigned char *sha1, const char *path)\n {\n-\tif (sha1)\n-\t\treturn sha1_to_hex(sha1);\n-\treturn \"0000000000000000000000000000000000000000\";\n+\tstruct merge_list *res = xmalloc(sizeof(*res));\n+\n+\tmemset(res, 0, sizeof(*res));\n+\tres->stage = stage;\n+\tres->path = path;\n+\tres->mode = mode;\n+\tres->blob = lookup_blob(sha1);\n+\treturn res;\n }\n \n static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result)\n {\n+\tstruct merge_list *orig, *final;\n+\tconst char *path;\n+\n \t/* If it's already branch1, don't bother showing it */\n \tif (!branch1)\n \t\treturn;\n \n-\tprintf(\"0 %06o->%06o %s->%s %s%s\\n\",\n-\t\tbranch1->mode, result->mode,\n-\t\tsha1_to_hex_zero(branch1->sha1),\n-\t\tsha1_to_hex_zero(result->sha1),\n-\t\tbase, result->path);\n+\tpath = strdup(mkpath(\"%s%s\", base, result->path));\n+\torig = create_entry(2, branch1->mode, branch1->sha1, path);\n+\tfinal = create_entry(0, result->mode, result->sha1, path);\n+\n+\tfinal->link = orig;\n+\n+\tadd_merge_entry(final);\n }\n \n static int unresolved_directory(const char *base, struct name_entry n[3])\n@@ -71,16 +149,40 @@ static int unresolved_directory(const ch\n \treturn 1;\n }\n \n+\n+static struct merge_list *link_entry(unsigned stage, const char *base, struct name_entry *n, struct merge_list *entry)\n+{\n+\tconst char *path;\n+\tstruct merge_list *link;\n+\n+\tif (!n->mode)\n+\t\treturn entry;\n+\tif (entry)\n+\t\tpath = entry->path;\n+\telse\n+\t\tpath = strdup(mkpath(\"%s%s\", base, n->path));\n+\tlink = create_entry(stage, n->mode, n->sha1, path);\n+\tlink->link = entry;\n+\treturn link;\n+}\n+\n static void unresolved(const char *base, struct name_entry n[3])\n {\n+\tstruct merge_list *entry = NULL;\n+\n \tif (unresolved_directory(base, n))\n \t\treturn;\n-\tif (n[0].sha1)\n-\t\tprintf(\"1 %06o %s %s%s\\n\", n[0].mode, sha1_to_hex(n[0].sha1), base, n[0].path);\n-\tif (n[1].sha1)\n-\t\tprintf(\"2 %06o %s %s%s\\n\", n[1].mode, sha1_to_hex(n[1].sha1), base, n[1].path);\n-\tif (n[2].sha1)\n-\t\tprintf(\"3 %06o %s %s%s\\n\", n[2].mode, sha1_to_hex(n[2].sha1), base, n[2].path);\n+\n+\t/*\n+\t * Do them in reverse order so that the resulting link\n+\t * list has the stages in order - link_entry adds new\n+\t * links at the front.\n+\t */\n+\tentry = link_entry(3, base, n + 2, entry);\n+\tentry = link_entry(2, base, n + 1, entry);\n+\tentry = link_entry(1, base, n + 0, entry);\n+\n+\tadd_merge_entry(entry);\n }\n \n /*\n@@ -172,5 +274,7 @@ int main(int argc, char **argv)\n \tfree(buf1);\n \tfree(buf2);\n \tfree(buf3);\n+\n+\tshow_result();\n \treturn 0;\n }\n"},{"id":"22757","messageId":"Pine.LNX.4.64.0606281401540.12404@g5.osdl.org","threadId":"4698","inReplyTo":"Pine.LNX.4.64.0606281054470.3782@g5.osdl.org","subject":"Re: Prepare \"git-merge-tree\" for future work","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-28T21:09:54Z","receivedAt":"2006-06-28T21:09:54Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 28 Jun 2006, Linus Torvalds wrote:\n> \n> This changes how \"git-merge-tree\" works in two ways:\n\nOk, and here is a totally bogus (but hopefully instructive) patch on how \nto actually use this to prepare a diff.\n\nI punted on trying to use the proper git diff interfaces (they are very \ntightly tied into the \"diff_filespec\" model - Junio, it might be nice if \nthere was some way to use them in a setting where that isn't necessarily \nas natural). So the \"diff\" is actually just the raw output from xlib, but \nthat wasn't really the point of this. \n\nIt was more meant to do part of the the the \"git-merge-one-file\" logic, \nand use that logic together with the git-merge-tree logic to do a \"merge\" \nto diff against.\n\nAs an example, with this you can now do\n\n\tgit-merge-tree $(git-merge-base HEAD next) HEAD next\n\nto generate a \"kind of\" diff between the current HEAD and what would \nhappen if it got merged with \"next\".\n\nWhat (a properly done version of) this would be actually useful for is \nwhen you want to see what the merge results would be. For example, that's \nan integral part of sending a \"please pull\" request: telling the receiver \nwhat the diffstat should be after the pull (even though we don't _locally_ \nwant to actually execute that merge - we expect the remote side to do so).\n\nAnybody want to actually make this useful for something like that?\n\n\t\tLinus\n\n----\ndiff --git a/Makefile b/Makefile\nindex cde619c..e880457 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -217,7 +217,7 @@ LIB_OBJS = \\\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\n-\talloc.o $(DIFF_OBJS)\n+\talloc.o merge-file.o $(DIFF_OBJS)\n \n BUILTIN_OBJS = \\\n \tbuiltin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \\\ndiff --git a/merge-file.c b/merge-file.c\nnew file mode 100644\nindex 0000000..4fedd6b\n--- /dev/null\n+++ b/merge-file.c\n@@ -0,0 +1,107 @@\n+#include \"cache.h\"\n+#include \"run-command.h\"\n+#include \"blob.h\"\n+\n+static void rm_temp_file(const char *filename)\n+{\n+\tunlink(filename);\n+}\n+\n+static const char *write_temp_file(struct blob *blob)\n+{\n+\tint fd;\n+\tconst char *tmp = getenv(\"TMPDIR\");\n+\tunsigned long size;\n+\tchar *filename, type[20];\n+\tvoid *buf;\n+\n+\tif (!tmp)\n+\t\ttmp = \"/tmp\";\n+\tfilename = mkpath(\"%s/%s\", tmp, \"git-tmp-XXXXXX\");\n+\tfd = mkstemp(filename);\n+\tif (fd < 0)\n+\t\treturn NULL;\n+\tfilename = strdup(filename);\n+\tbuf = read_sha1_file(blob->object.sha1, type, &size);\n+\tif (buf) {\n+\t\tif (size != xwrite(fd, buf, size)) {\n+\t\t\trm_temp_file(filename);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tfree(buf);\n+\t}\n+\tclose(fd);\n+\treturn filename;\n+}\n+\n+static void *read_temp_file(const char *filename, unsigned long *size)\n+{\n+\tstruct stat st;\n+\tchar *buf = NULL;\n+\tint fd = open(filename, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn NULL;\n+\tif (!fstat(fd, &st)) {\n+\t\t*size = st.st_size;\n+\t\tbuf = xmalloc(st.st_size);\n+\t\tif (st.st_size != xread(fd, buf, st.st_size)) {\n+\t\t\tfree(buf);\n+\t\t\tbuf = NULL;\n+\t\t}\n+\t}\n+\tclose(fd);\n+\treturn buf;\n+}\n+\n+void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)\n+{\n+\tconst char *t1, *t2, *t3;\n+\tchar type[20];\n+\n+\tif (base) {\n+\t\tint code;\n+\t\tvoid *res;\n+\n+\t\t/*\n+\t\t * Removed in either branch?\n+\t\t *\n+\t\t * NOTE! This depends on the caller having done the\n+\t\t * proper warning about removing a file that got\n+\t\t * modified in the other branch!\n+\t\t */\n+\t\tif (!our || !their)\n+\t\t\treturn NULL;\n+\t\tt1 = write_temp_file(base);\n+\t\tt2 = write_temp_file(our);\n+\t\tt3 = write_temp_file(their);\n+\t\tres = NULL;\n+\t\tif (t1 && t2 && t3) {\n+\t\t\tcode = run_command(\"merge\", t2, t1, t3, NULL);\n+\t\t\tif (!code || code == -1)\n+\t\t\t\tres = read_temp_file(t2, size);\n+\t\t}\n+\t\trm_temp_file(t1);\n+\t\trm_temp_file(t2);\n+\t\trm_temp_file(t3);\n+\t\treturn res;\n+\t}\n+\n+\tif (!our)\n+\t\treturn read_sha1_file(their->object.sha1, type, size);\n+\tif (!their)\n+\t\treturn read_sha1_file(our->object.sha1, type, size);\n+\n+\t/*\n+\t * Added in both!\n+\t *\n+\t * This is nasty.\n+\t *\n+\t * We should do something like \n+\t *\n+\t *\tgit diff our their | git-apply --no-add\n+\t *\n+\t * to generate a \"minimal common file\" to be used\n+\t * as a base. Right now we punt.\n+\t */\n+\treturn NULL;\n+}\ndiff --git a/merge-tree.c b/merge-tree.c\nindex fd0c211..7cf00be 100644\n--- a/merge-tree.c\n+++ b/merge-tree.c\n@@ -1,5 +1,6 @@\n #include \"cache.h\"\n #include \"tree-walk.h\"\n+#include \"xdiff-interface.h\"\n #include \"blob.h\"\n \n static const char merge_tree_usage[] = \"git-merge-tree <base-tree> <branch1> <branch2>\";\n@@ -52,6 +53,77 @@ static const char *explanation(struct me\n \treturn \"removed in remote\";\n }\n \n+extern void *merge_file(struct blob *, struct blob *, struct blob *, unsigned long *);\n+\n+static void *result(struct merge_list *entry, unsigned long *size)\n+{\n+\tchar type[20];\n+\tstruct blob *base, *our, *their;\n+\n+\tif (!entry->stage)\n+\t\treturn read_sha1_file(entry->blob->object.sha1, type, size);\n+\tbase = NULL;\n+\tif (entry->stage == 1) {\n+\t\tbase = entry->blob;\n+\t\tentry = entry->link;\n+\t}\n+\tour = NULL;\n+\tif (entry && entry->stage == 2) {\n+\t\tour = entry->blob;\n+\t\tentry = entry->link;\n+\t}\n+\ttheir = NULL;\n+\tif (entry)\n+\t\ttheir = entry->blob;\n+\treturn merge_file(base, our, their, size);\n+}\n+\n+static void *origin(struct merge_list *entry, unsigned long *size)\n+{\n+\tchar type[20];\n+\twhile (entry) {\n+\t\tif (entry->stage == 2)\n+\t\t\treturn read_sha1_file(entry->blob->object.sha1, type, size);\n+\t\tentry = entry->link;\n+\t}\n+\treturn NULL;\n+}\n+\n+static int show_outf(void *priv_, mmbuffer_t *mb, int nbuf)\n+{\n+\tint i;\n+\tfor (i = 0; i < nbuf; i++)\n+\t\tprintf(\"%.*s\", (int) mb[i].size, mb[i].ptr);\n+\treturn 0;\n+}\n+\n+static void show_diff(struct merge_list *entry)\n+{\n+\tunsigned long size;\n+\tmmfile_t src, dst;\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\txdemitcb_t ecb;\n+\n+\txpp.flags = XDF_NEED_MINIMAL;\n+\txecfg.ctxlen = 3;\n+\txecfg.flags = 0;\n+\tecb.outf = show_outf;\n+\tecb.priv = NULL;\n+\n+\tsrc.ptr = origin(entry, &size);\n+\tif (!src.ptr)\n+\t\tsize = 0;\n+\tsrc.size = size;\n+\tdst.ptr = result(entry, &size);\n+\tif (!dst.ptr)\n+\t\tsize = 0;\n+\tdst.size = size;\n+\txdl_diff(&src, &dst, &xpp, &xecfg, &ecb);\n+\tfree(src.ptr);\n+\tfree(dst.ptr);\n+}\n+\n static void show_result_list(struct merge_list *entry)\n {\n \tprintf(\"%s\\n\", explanation(entry));\n@@ -70,6 +142,7 @@ static void show_result(void)\n \twalk = merge_result;\n \twhile (walk) {\n \t\tshow_result_list(walk);\n+\t\tshow_diff(walk);\n \t\twalk = walk->next;\n \t}\n }\n"},{"id":"22875","messageId":"7vejx7mmaj.fsf@assigned-by-dhcp.cox.net","threadId":"4698","inReplyTo":"Pine.LNX.4.64.0606281401540.12404@g5.osdl.org","subject":"Re: Prepare \"git-merge-tree\" for future work","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-30T02:04:20Z","receivedAt":"2006-06-30T02:04:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> I punted on trying to use the proper git diff interfaces (they are very \n> tightly tied into the \"diff_filespec\" model - Junio, it might be nice if \n> there was some way to use them in a setting where that isn't necessarily \n> as natural).\n\nI am not quite sure what you mean.  You have a sets of\nfilepairs, each of which is a pair of filespec, each of which\ndescribes the blob.  And diff is about comparing them, possibly\nafter running rename detection, pickaxe filtering and such.  If\nthe merge-tree's internal representation for each blob is more\nefficient or easier to use we could switch to use it as an\nimproved implementation of filespec but I do not think that is\nwhat you meant, because I suspect that approach does not break\ndiff from the \"model\".  Care to elaborate a bit more please?\n"},{"id":"22878","messageId":"Pine.LNX.4.64.0606291925230.12404@g5.osdl.org","threadId":"4698","inReplyTo":"7vejx7mmaj.fsf@assigned-by-dhcp.cox.net","subject":"Re: Prepare \"git-merge-tree\" for future work","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-30T02:32:22Z","receivedAt":"2006-06-30T02:32:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Jun 2006, Junio C Hamano wrote:\n\n> Linus Torvalds <torvalds@osdl.org> writes:\n> \n> > I punted on trying to use the proper git diff interfaces (they are very \n> > tightly tied into the \"diff_filespec\" model - Junio, it might be nice if \n> > there was some way to use them in a setting where that isn't necessarily \n> > as natural).\n> \n> I am not quite sure what you mean.\n\nFor what I wanted to do, I didn't see an easy way to add/populate a new \nfilespec. It was easier to just use the raw libxdiff interfaces, but \nthat's really just because I know the interfaces.\n\nIn contrast, the ones to diff_filespec I've never really used, and I did \nnot want to compare blob objects, I very much wanted to compare in-memory \nbuffers (_and_ potentially blobs).\n\nSo if you can show an easy example of how to populate a set of filespec \npairs (not with blobs - with in-memory generated data) and insert them \nonto the lists, that would be good.\n\nIn fact, maybe you can show me what git-merge-tree needs to do..\n\nHint hint.\n\n\t\tLinus\n"},{"id":"22948","messageId":"7vbqsagyd0.fsf@assigned-by-dhcp.cox.net","threadId":"4698","inReplyTo":"Pine.LNX.4.64.0606291925230.12404@g5.osdl.org","subject":"Re: Prepare \"git-merge-tree\" for future work","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-30T20:52:27Z","receivedAt":"2006-06-30T20:52:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> In contrast, the ones to diff_filespec I've never really used, and I did \n> not want to compare blob objects, I very much wanted to compare in-memory \n> buffers (_and_ potentially blobs).\n>\n> So if you can show an easy example of how to populate a set of filespec \n> pairs (not with blobs - with in-memory generated data) and insert them \n> onto the lists, that would be good.\n\nAh, I see.  Your origin() function always returns a in-core\nbuffer from an existing blob (or NULL if it is a new file) but\nresult() returns either an existing blob resulting from the\ntree-level merge, or a 3-way content merge result that does not\nhave an existing blob, and it is not obvious how to express the\nlatter as a filespec (all other cases you can stuff the blob\nobject name in the sha1[] member and if you choose to do the\nread_sha1_file() yourself store the result in data member or you\ncan let diff_populate_filespec() read the data when diff\nmachinery needs it).\n\nI think a filespec that has 0{40} sha1, with data already\npopulated and should_free/should_munmap members both set to\nfalse might work for the in-memory data but I haven't tried.\n\nI'd take the hint, and I will (eventually) take a look at it\nif nobody beats me to it, but most likely not now, sorry.\n"}]}