{"thread":{"id":"4705","subject":"Improved three-way blob merging code","startedAt":"2006-06-29T05:06:36Z","lastAt":"2006-06-29T23:07:22Z","messageCount":5,"participants":["Linus Torvalds","Alex Riesen","Davide Libenzi"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22773","messageId":"Pine.LNX.4.64.0606282157210.12404@g5.osdl.org","threadId":"4705","inReplyTo":null,"subject":"Improved three-way blob merging code","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-29T05:06:36Z","receivedAt":"2006-06-29T05:06:36Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis fleshes out the code that generates a three-way merge of a set of \nblobs.\n\nIt still actually does the three-way merge using an external executable \n(ie just calling \"merge\"), but the interfaces have been cleaned up a lot \nand are now fully based on the 'mmfile_t' interface, so if libxdiff were \nto ever grow a compatible three-way-merge, it could probably be directly\nplugged in.\n\nIt also uses the previous XDL_EMIT_COMMON functionality extension to \nlibxdiff to generate a made-up base file for the merge for the case where \nno base file previously existed. This should be equivalent to what we \ncurrently do in git-merge-one-file.sh:\n\n\tdiff -u -La/$orig -Lb/$orig $orig $src2 | git-apply --no-add\n\nexcept it should be much simpler and can be done using the direct libxdiff \ninterfaces.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nIt would be lovely if libxdiff did a 3-way merge on its own, but this \nbasically approximates it within that three_way_filemerge() function \nusing external functionality.\n\nThe caller is, of course, still expected to do all the other proper magic \n(ie do things like resolve renames, mode differences, and all the trivial \ncases), and the example merge-tree.c code I posted earlier is obviously \n_not_ careful enough to be a real merge routine.\n\nBut we all have to start somewhere.\n\n\ndiff --git a/merge-file.c b/merge-file.c\nindex 4fedd6b..f32c653 100644\n--- a/merge-file.c\n+++ b/merge-file.c\n@@ -1,19 +1,19 @@\n #include \"cache.h\"\n #include \"run-command.h\"\n+#include \"xdiff-interface.h\"\n #include \"blob.h\"\n \n static void rm_temp_file(const char *filename)\n {\n \tunlink(filename);\n+\tfree((void *)filename);\n }\n \n-static const char *write_temp_file(struct blob *blob)\n+static const char *write_temp_file(mmfile_t *f)\n {\n \tint fd;\n \tconst char *tmp = getenv(\"TMPDIR\");\n-\tunsigned long size;\n-\tchar *filename, type[20];\n-\tvoid *buf;\n+\tchar *filename;\n \n \tif (!tmp)\n \t\ttmp = \"/tmp\";\n@@ -22,13 +22,9 @@ static const char *write_temp_file(struc\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+\tif (f->size != xwrite(fd, f->ptr, f->size)) {\n+\t\trm_temp_file(filename);\n+\t\treturn NULL;\n \t}\n \tclose(fd);\n \treturn filename;\n@@ -53,55 +49,118 @@ static void *read_temp_file(const char *\n \treturn buf;\n }\n \n-void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)\n+static int fill_mmfile_blob(mmfile_t *f, struct blob *obj)\n {\n-\tconst char *t1, *t2, *t3;\n+\tvoid *buf;\n+\tunsigned long size;\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+\tbuf = read_sha1_file(obj->object.sha1, type, &size);\n+\tif (!buf)\n+\t\treturn -1;\n+\tif (strcmp(type, blob_type))\n+\t\treturn -1;\n+\tf->ptr = buf;\n+\tf->size = size;\n+\treturn 0;\n+}\n+\n+static void free_mmfile(mmfile_t *f)\n+{\n+\tfree(f->ptr);\n+}\n+\n+static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t *their, unsigned long *size)\n+{\n+\tvoid *res;\n+\tconst char *t1, *t2, *t3;\n+\n+\tt1 = write_temp_file(base);\n+\tt2 = write_temp_file(our);\n+\tt3 = write_temp_file(their);\n+\tres = NULL;\n+\tif (t1 && t2 && t3) {\n+\t\tint code = run_command(\"merge\", t2, t1, t3, NULL);\n+\t\tif (!code || code == -1)\n+\t\t\tres = read_temp_file(t2, size);\n \t}\n+\trm_temp_file(t1);\n+\trm_temp_file(t2);\n+\trm_temp_file(t3);\n+\treturn res;\n+}\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+static int common_outf(void *priv_, mmbuffer_t *mb, int nbuf)\n+{\n+\tint i;\n+\tmmfile_t *dst = priv_;\n+\n+\tfor (i = 0; i < nbuf; i++) {\n+\t\tmemcpy(dst->ptr + dst->size, mb[i].ptr, mb[i].size);\n+\t\tdst->size += mb[i].size;\n+\t}\n+\treturn 0;\n+}\n+\n+static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)\n+{\n+\tunsigned long size = f1->size < f2->size ? f1->size : f2->size;\n+\tvoid *ptr = xmalloc(size);\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 = XDL_EMIT_COMMON;\n+\tecb.outf = common_outf;\n+\n+\tres->ptr = ptr;\n+\tres->size = 0;\n+\n+\tecb.priv = res;\n+\treturn xdl_diff(f1, f2, &xpp, &xecfg, &ecb);\n+}\n+\n+void *merge_file(struct blob *base, struct blob *our, struct blob *their, unsigned long *size)\n+{\n+\tvoid *res = NULL;\n+\tmmfile_t f1, f2, common;\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 * Removed in either branch?\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 * NOTE! This depends on the caller having done the\n+\t * proper warning about removing a file that got\n+\t * modified in the other branch!\n \t */\n-\treturn NULL;\n+\tif (!our || !their) {\n+\t\tchar type[20];\n+\t\tif (base)\n+\t\t\treturn NULL;\n+\t\tif (!our)\n+\t\t\tour = their;\n+\t\treturn read_sha1_file(our->object.sha1, type, size);\n+\t}\n+\n+\tif (fill_mmfile_blob(&f1, our) < 0)\n+\t\tgoto out_no_mmfile;\n+\tif (fill_mmfile_blob(&f2, their) < 0)\n+\t\tgoto out_free_f1;\n+\n+\tif (base) {\n+\t\tif (fill_mmfile_blob(&common, base) < 0)\n+\t\t\tgoto out_free_f2_f1;\n+\t} else {\n+\t\tif (generate_common_file(&common, &f1, &f2) < 0)\n+\t\t\tgoto out_free_f2_f1;\n+\t}\n+\tres = three_way_filemerge(&common, &f1, &f2, size);\n+\tfree_mmfile(&common);\n+out_free_f2_f1:\n+\tfree_mmfile(&f2);\n+out_free_f1:\n+\tfree_mmfile(&f1);\n+out_no_mmfile:\n+\treturn res;\n }\n"},{"id":"22779","messageId":"81b0412b0606290043s15e19b9fl853627e815f009ff@mail.gmail.com","threadId":"4705","inReplyTo":"Pine.LNX.4.64.0606282157210.12404@g5.osdl.org","subject":"Re: Improved three-way blob merging code","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-29T07:43:02Z","receivedAt":"2006-06-29T07:43:02Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/29/06, Linus Torvalds <torvalds@osdl.org> wrote:\n> +static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t *their, unsigned long *size)\n> +{\n...\n> +       if (t1 && t2 && t3) {\n> +               int code = run_command(\"merge\", t2, t1, t3, NULL);\n\nThis does not use the labels of merge(1) and the merged file will contain\nthe names of temporary files at conflict places, which is very confusing if\nyou happen to loose context while doing a merge with lots of conflicts.\n"},{"id":"22806","messageId":"Pine.LNX.4.64.0606291028010.12404@g5.osdl.org","threadId":"4705","inReplyTo":"81b0412b0606290043s15e19b9fl853627e815f009ff@mail.gmail.com","subject":"Re: Improved three-way blob merging code","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-29T17:45:20Z","receivedAt":"2006-06-29T17:45:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Jun 2006, Alex Riesen wrote:\n>\n> On 6/29/06, Linus Torvalds <torvalds@osdl.org> wrote:\n> > +static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t\n> > *their, unsigned long *size)\n> > +{\n> ...\n> > +       if (t1 && t2 && t3) {\n> > +               int code = run_command(\"merge\", t2, t1, t3, NULL);\n> \n> This does not use the labels of merge(1) and the merged file will contain\n> the names of temporary files at conflict places, which is very confusing if\n> you happen to loose context while doing a merge with lots of conflicts.\n\nYes. \n\nI was really really _really_ just hoping that I could do the nasty core \ncode that others might feel uncomfortable with, and get it working from a \n_technical_ level well enough that others (hint hint) would decide that \nthey can fix up the details.\n\nGetting the first version working is often the hardest. When you reach the \npoint of \"it works, but I want to extend it to do X\", you've usually \nalready gotten pretty far.\n\nAnyway, all of this was really just preparatory work to show what \ngit-merge-tree does. A few more improvements to git-merge-tree, and \nhopefully it can start being useful - perhaps not initially for actually \nmerging, but for doing a tree-level three-way diff between two branches.\n\nIn other words, my current goal is really do make it possible to get good \ndiffs out of git from two branches that aren't directly related. You and \nDscho seem to be doing well on the git-merge-recursive front, so my \npersonal goal is actually to be able to get a saner diff than what\n\n\tgit diff mine..theirs\n\ngives you.\n\nThe above \"git diff\" is a perfectly fine thing to do, but it's usually not \nwhat you actually _want_. Almost always, what you want a diff between two \nbranches, what you want is actually the diff after a merge of the \nbranches, not the raw _current_ differences.\n\nFor example, look at our current \n\n\tDocumentation/howto/using-topic-branches.txt\n\nfile, and realize that the current scripts it suggests are actually \nbroken:\n\n\tTo create diffstat and shortlog summaries of changes to include in \n\ta \"pleasepull\" request to Linus you can use:\n\n\t $ git-whatchanged -p release ^linus | diffstat -p1\n\tand\n\t $ git-whatchanged release ^linus | git-shortlog\n\nwhere that \"git-whatchanged -p release ^linus | diffstat -p1\" won't \nactually be what I see when I merge (although it will hopefully be close \nenough). Also, there's no indication that the merge will fail when I pull, \nsomething that _would_ be very useful.\n\nIOW, what I'd like git-merge-tree to do is to be able to at a minimum say:\n\n - will a merge succeed cleanly, and if not, show me where the problem \n   spots are.\n - what will the result of the merge look like.\n\nbecause that's actually what a downstream developer wants to do. He'd just \ndo\n\n\tgit fetch linus\n\tgit show-changes linus..my-branch\n\nwhich would basically be the preparatory thing for sending me an email \nsaying \"please merge 'my-branch', and you'll see this\".\n\nNow, obviously, I think that there's a _lot_ of overlap between doing this \nand actually doing the merge itself, so hopefully the things I do will at \nleast have some things in common and perhaps help you do the proper \nrecursive merger.\n\nBut one thing I was actually hoping to do was to literally be able to do \nthis without either tree being checked out, exactly so that you can check \nthe status of a branch that you may not even _be_ on (eg that \"my-branch\" \nin the example above may not even be your current HEAD: you might be on \nyour development branch when you actually ask me to pull from your stable \nbranch).\n\nSo the \"show differences\" has a lot in common with \"merge them\", but there \nare literally a few stages missing. One thing missing in just showing \ndifferences is that you can't actually fix up the merge clashes: if you \ndon't have a checked-out tree, you're not going to be able to do a real \nmerge. But you can see what a merge would _look_ like, and whether there \nare any clashes that you will have to fix..\n\n\t\tLinus\n"},{"id":"22812","messageId":"Pine.LNX.4.64.0606291118110.8615@alien.or.mcafeemobile.com","threadId":"4705","inReplyTo":"Pine.LNX.4.64.0606282157210.12404@g5.osdl.org","subject":"Re: Improved three-way blob merging code","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-06-29T18:21:00Z","receivedAt":"2006-06-29T18:21:00Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 28 Jun 2006, Linus Torvalds wrote:\n\n> It would be lovely if libxdiff did a 3-way merge on its own, but this\n> basically approximates it within that three_way_filemerge() function\n> using external functionality.\n\nThis is my todo-list, that unfortunately is pretty crowded nowadays. I'll \ncome graveling you main window once I have it ;)\n\n\n\n- Davide\n"},{"id":"22857","messageId":"20060629230722.GA7216@steel.home","threadId":"4705","inReplyTo":"Pine.LNX.4.64.0606291028010.12404@g5.osdl.org","subject":"Re: Improved three-way blob merging code","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-29T23:07:22Z","receivedAt":"2006-06-29T23:07:22Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Linus Torvalds, Thu, Jun 29, 2006 19:45:20 +0200:\n> IOW, what I'd like git-merge-tree to do is to be able to at a minimum say:\n> \n>  - will a merge succeed cleanly, and if not, show me where the problem \n>    spots are.\n>  - what will the result of the merge look like.\n> \n> because that's actually what a downstream developer wants to do. He'd just \n> do\n> \n> \tgit fetch linus\n> \tgit show-changes linus..my-branch\n> \n> which would basically be the preparatory thing for sending me an email \n> saying \"please merge 'my-branch', and you'll see this\".\n\nit's a \"git show-merge linus..my-branch\" :)\n\n> Now, obviously, I think that there's a _lot_ of overlap between doing this \n> and actually doing the merge itself, so hopefully the things I do will at \n> least have some things in common and perhaps help you do the proper \n> recursive merger.\n\nI certanly hope so: only the last pass of the recursive merge seem to\nreally need the index. It's use in all the previuos recursions looks\nmore like abuse.\n"}]}