{"thread":{"id":"22719","subject":"Re: [RFC] (reverse) combined diff conflict style","startedAt":"2010-02-18T19:36:29Z","lastAt":"2010-02-19T07:15:15Z","messageCount":3,"participants":["Junio C Hamano","Bert Wesarg"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"299146","messageId":"1266521789-3617-1-git-send-email-bert.wesarg@googlemail.com","threadId":"22719","inReplyTo":null,"subject":"[RFC] (reverse) combined diff conflict style","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-02-18T19:36:29Z","receivedAt":"2010-02-18T19:36:29Z","isPatch":false,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"Hi All,\n\nas I mentioned in my reply[1] to Junio about a reversed combined diff, I've\ndone this with the intended use case to display merge conflicts this way.\n\nThe algorithm is pretty much the same as the diff --cc/-c one and most of the\ncode too. I have currently too proof-of-concept tools for this:\n\n * git cdiff <base> <targets>..\n   This command takes files as parameters and generates a combined diff from\n   the <base> to all <targets>. No hunking is done.\n\n * git cdiff-conflict-filter\n   This filters it input stream and looks for merge conflict markers and\n   replaces the conflict with the output of the cdiff. It needs the diff3\n   conflict style for this. Here is a simple example:\n\n----- input -----\n\n1\n<<<<<<<\n2\n|||||||\n2\n3\n=======\n3\n>>>>>>>\n4\n\n----- output ----\n\n1\n<<<<<<<\n -2\n- 3\n>>>>>>>\n4\n\n------ end ------\n\nAs you can see, the conflict region is way smaller as the diff3 one, but keeps\nall information.\n\nI'm not doing much merges myself, so there are probably people out there who\ncan better judge the usefulness of this style.\n\nBert\n\n[1]: http://article.gmane.org/gmane.comp.version-control.git/138108\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n---\n .gitignore      |    2 +\n Makefile        |    2 +\n builtin-cdiff.c |  387 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n builtin.h       |    2 +\n git.c           |    2 +\n 5 files changed, 395 insertions(+), 0 deletions(-)\n\ndiff --git a/.gitignore b/.gitignore\nindex 8df8f88..ce685ce 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -17,6 +17,8 @@\n /git-branch\n /git-bundle\n /git-cat-file\n+/git-cdiff\n+/git-cdiff-conflict-filter\n /git-check-attr\n /git-check-ref-format\n /git-checkout\ndiff --git a/Makefile b/Makefile\nindex 7bf2fca..cd5df9e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -384,6 +384,7 @@ BUILT_INS += git-show$X\n BUILT_INS += git-stage$X\n BUILT_INS += git-status$X\n BUILT_INS += git-whatchanged$X\n+BUILT_INS += git-cdiff-conflict-filter$X\n \n # what 'all' will build and 'install' will install in gitexecdir,\n # excluding programs for built-in commands\n@@ -681,6 +682,7 @@ BUILTIN_OBJS += builtin-var.o\n BUILTIN_OBJS += builtin-verify-pack.o\n BUILTIN_OBJS += builtin-verify-tag.o\n BUILTIN_OBJS += builtin-write-tree.o\n+BUILTIN_OBJS += builtin-cdiff.o\n \n GITLIBS = $(LIB_FILE) $(XDIFF_LIB)\n EXTLIBS =\ndiff --git a/builtin-cdiff.c b/builtin-cdiff.c\nnew file mode 100644\nindex 0000000..950065a\n--- /dev/null\n+++ b/builtin-cdiff.c\n@@ -0,0 +1,387 @@\n+#include \"cache.h\"\n+#include \"builtin.h\"\n+#include \"xdiff-interface.h\"\n+#include \"strbuf.h\"\n+\n+/* new line in target */\n+struct nline {\n+\tstruct nline *next;\n+\tint len;\n+\tunsigned long targets_map;\n+\tchar line[FLEX_ARRAY];\n+};\n+\n+/* Origin lines */\n+struct oline {\n+\tstruct nline *new_head, **new_tail;\n+\tchar *bol; /* buffer of line */\n+\tint len;\n+\t/* bit 0 up to (N-1) are on if the target has not this line (i.e.\n+\t * it will be removed).\n+\t */\n+\tunsigned long targets_map;\n+\t/* unsigned long *p_lno; */ /* ?parent line number */\n+};\n+\n+struct combine_diff_state {\n+\tunsigned long lno;\n+\t/* int num_parent; */\n+\tint n;\n+\tstruct oline *oline;\n+};\n+\n+static void append_new(struct oline *oline, int n, const char *line, int len)\n+{\n+\tstruct nline *nline;\n+\tunsigned long this_mask = (1UL<<n);\n+\tif (line[len-1] == '\\n')\n+\t\tlen--;\n+\n+\tnline = xmalloc(sizeof(*nline) + len + 1);\n+\tnline->len = len;\n+\tnline->next = NULL;\n+\tnline->targets_map = this_mask;\n+\tmemcpy(nline->line, line, len);\n+\tnline->line[len] = 0;\n+\t*oline->new_tail = nline;\n+\toline->new_tail = &nline->next;\n+}\n+\n+static void consume_line(void *state_, char *line, unsigned long len)\n+{\n+\tstruct combine_diff_state *state = state_;\n+\n+\tif (5 < len && !memcmp(\"@@ -\", line, 4)) {\n+\t\tint ob, on, nb, nn;\n+\t\tif (parse_hunk_header(line, len, &ob, &on, &nb, &nn))\n+\t\t\treturn;\n+\t\tif (!on)\n+\t\t\tstate->lno = ob;\n+\t\telse\n+\t\t\tstate->lno = ob - !!ob;\n+\t\treturn;\n+\t}\n+\tswitch (line[0]) {\n+\tcase '-':\n+\t\tstate->oline[++state->lno].targets_map |= (1lu << state->n);\n+\t\tbreak;\n+\tcase '+':\n+\t\tappend_new(&state->oline[state->lno], state->n, line+1, len-1);\n+\t\tbreak;\n+\t}\n+}\n+\n+static void build_oline(mmfile_t *origin_file, struct oline **oline_p,\n+\t\tunsigned long *cnt_p)\n+{\n+\tstruct oline *oline;\n+\tunsigned long cnt, lno, origin_size;\n+\tchar *origin, *cp;\n+\n+\torigin      = origin_file->ptr;\n+\torigin_size = origin_file->size;\n+\n+\tfor (cnt = 0, cp = origin; cp < origin + origin_size; cp++) {\n+\t\tif (*cp == '\\n')\n+\t\t\tcnt++;\n+\t}\n+\tif (origin_size && origin[origin_size-1] != '\\n')\n+\t\tcnt++; /* incomplete line */\n+\n+\toline = xcalloc(cnt+1, sizeof(*oline));\n+\t*oline_p = oline;\n+\t*cnt_p = cnt;\n+\n+\tfor (lno = 0; lno <= cnt; lno++) {\n+\t\toline[lno].new_tail = &oline[lno].new_head;\n+\t\toline[lno].targets_map = 0;\n+\t}\n+\n+\tif (!origin_size)\n+\t\treturn;\n+\n+\toline[1].bol = origin;\n+\tfor (lno = 1, cp = origin; cp < origin + origin_size; cp++) {\n+\t\tif (*cp == '\\n') {\n+\t\t\toline[lno].len = cp - oline[lno].bol;\n+\t\t\tlno++;\n+\t\t\tif (lno <= cnt)\n+\t\t\t\toline[lno].bol = cp + 1;\n+\t\t}\n+\t}\n+\tif (origin_size && origin[origin_size-1] != '\\n')\n+\t\toline[cnt].len = origin_size - (oline[cnt].bol - origin);\n+\n+}\n+\n+static void dump_oline(const struct oline *oline, unsigned long cnt,\n+\t\tint num_targets)\n+{\n+\tunsigned long lno;\n+\tint i;\n+\tstruct nline *nline;\n+\n+\tfor (lno = 0; lno <= cnt; lno++) {\n+\t\tif (1 <= lno) {\n+\t\t\tfor (i = 0; i < num_targets; i++)\n+\t\t\t\tif (oline[lno].targets_map & (1lu << i))\n+\t\t\t\t\tputchar('-');\n+\t\t\t\telse\n+\t\t\t\t\tputchar(' ');\n+\t\t\tprintf(\"%.*s\\n\", (int)oline[lno].len, oline[lno].bol);\n+\t\t}\n+\n+\t\tnline = oline[lno].new_head;\n+\t\twhile (nline) {\n+\t\t\tfor (i = 0; i < num_targets; i++)\n+\t\t\t\tif (nline->targets_map & (1lu << i))\n+\t\t\t\t\tputchar('+');\n+\t\t\t\telse\n+\t\t\t\t\tputchar(' ');\n+\t\t\tprintf(\"%s\\n\", nline->line);\n+\n+\t\t\tnline = nline->next;\n+\t\t}\n+\t}\n+}\n+\n+static void free_oline(struct oline *oline, unsigned long cnt)\n+{\n+\tunsigned long lno;\n+\n+\tfor (lno = 0; lno <= cnt; lno++) {\n+\t\twhile (oline[lno].new_head) {\n+\t\t\tstruct nline *nline = oline[lno].new_head;\n+\t\t\toline[lno].new_head = nline->next;\n+\t\t\tfree(nline);\n+\t\t}\n+\t}\n+\tfree(oline);\n+}\n+\n+static void do_cdiff_step(struct oline *oline, mmfile_t *origin_file,\n+\t\tmmfile_t *target_file, int i)\n+{\n+\txdemitconf_t xecfg;\n+\txdemitcb_t ecb;\n+\txpparam_t xpp;\n+\tstruct combine_diff_state state;\n+\n+\tmemset(&state, 0, sizeof(state));\n+\tstate.oline = oline;\n+\tstate.lno = 1;\n+\tstate.n = i;\n+\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\txpp.flags = XDF_NEED_MINIMAL;\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\tmemset(&ecb, 0, sizeof(ecb));\n+\n+\txdi_diff_outf(origin_file, target_file, consume_line, &state,\n+\t\t\t&xpp, &xecfg, &ecb);\n+}\n+\n+static void do_path_cdiff(const char *origin_name, const char **target_names,\n+\t\tint num_targets)\n+{\n+\tmmfile_t origin_file, target_file;\n+\tstruct oline *oline = NULL; /* origin lines */\n+\tunsigned long cnt;\n+\tint i;\n+\n+\tif (num_targets > (sizeof(unsigned long) * 8))\n+\t\tdie(\"Can only handle %zu targets.\", (sizeof(unsigned long) * 8));\n+\n+\tif (read_mmfile(&origin_file, origin_name))\n+\t\tdie_errno(\"can't read `%s'\", origin_name);\n+\n+\t/* build origin image */\n+\tbuild_oline(&origin_file, &oline, &cnt);\n+\n+\tfor (i = 0; i < num_targets; i++) {\n+\n+\t\tif (read_mmfile(&target_file, target_names[i]))\n+\t\t\tdie_errno(\"can't read `%s'\", target_names[i]);\n+\n+\t\tdo_cdiff_step(oline, &origin_file, &target_file, i);\n+\n+\t\tfree(target_file.ptr);\n+\t}\n+\tdump_oline(oline, cnt, num_targets);\n+\n+\tfree_oline(oline, cnt);\n+\n+\tfree(origin_file.ptr);\n+}\n+\n+static unsigned long put_line(char *dest, char *line, unsigned long len,\n+\t\tunsigned long map, int marker, int num_targets)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < num_targets; i++)\n+\t\tif (map & (1lu << i))\n+\t\t\t*dest++ = marker;\n+\t\telse\n+\t\t\t*dest++ = ' ';\n+\tmemcpy(dest, line, len);\n+\tdest[len] = '\\n';\n+\n+\treturn len + num_targets + 1;\n+}\n+\n+static unsigned long oline_to_buf(const struct oline *oline, unsigned long cnt,\n+\t\tint num_targets, char *dest)\n+{\n+\tunsigned long lno;\n+\tstruct nline *nline;\n+\tunsigned long size = 0;\n+\n+\tfor (lno = 0; lno <= cnt; lno++) {\n+\t\tif (1 <= lno) {\n+\t\t\tif (!dest) {\n+\t\t\t\tsize += num_targets + oline[lno].len + 1;\n+\t\t\t} else {\n+\t\t\t\tsize += put_line(dest + size, oline[lno].bol,\n+\t\t\t\t\t\toline[lno].len,\n+\t\t\t\t\t\toline[lno].targets_map, '-',\n+\t\t\t\t\t\tnum_targets);\n+\t\t\t}\n+\t\t}\n+\n+\t\tnline = oline[lno].new_head;\n+\t\twhile (nline) {\n+\t\t\tif (!dest) {\n+\t\t\t\tsize += num_targets + nline->len + 1;\n+\t\t\t} else {\n+\t\t\t\tsize += put_line(dest + size, nline->line,\n+\t\t\t\t\t\tnline->len, nline->targets_map,\n+\t\t\t\t\t\t'+', num_targets);\n+\t\t\t}\n+\n+\t\t\tnline = nline->next;\n+\t\t}\n+\t}\n+\n+\treturn size;\n+}\n+\n+unsigned long do_buf_cdiff(mmfile_t *origin_file, mmfile_t *target_files,\n+\t\tint num_targets, char *dest)\n+{\n+\tstruct oline *oline = NULL; /* origin lines */\n+\tunsigned long cnt, size;\n+\tint i;\n+\n+\tif (num_targets > (sizeof(unsigned long) * 8))\n+\t\tdie(\"Can only handle %zu targets.\", (sizeof(unsigned long) * 8));\n+\n+\t/* build origin image */\n+\tbuild_oline(origin_file, &oline, &cnt);\n+\n+\tfor (i = 0; i < num_targets; i++)\n+\t\tdo_cdiff_step(oline, origin_file, &target_files[i], i);\n+\n+\tsize = oline_to_buf(oline, cnt, num_targets, dest);\n+\n+\tfree_oline(oline, cnt);\n+\n+\treturn size;\n+}\n+\n+int cmd_cdiff(int argc, const char **argv, const char *prefix)\n+{\n+\tdo_path_cdiff(argv[1], argv + 2, argc - 2);\n+\n+\treturn 0;\n+}\n+\n+static void mmfile_from_strbuf(mmfile_t *mmfile, struct strbuf *strbuf)\n+{\n+\tsize_t sz;\n+\n+\t/* force allocated buffer */\n+\tstrbuf_grow(strbuf, 0);\n+\tmmfile->ptr  = strbuf_detach(strbuf, &sz);\n+\tmmfile->size = sz;\n+}\n+\n+int cmd_cdiff_conflict_filter(int argc, const char **argv, const char *prefix)\n+{\n+\tstruct strbuf input = STRBUF_INIT;\n+\tstruct strbuf collector = STRBUF_INIT;\n+\tmmfile_t base_file, target_files[2];\n+\tenum {\n+\t\tIN_CONTEXT,\n+\t\tIN_OURS,\n+\t\tIN_BASE,\n+\t\tIN_THEIRS\n+\t} state = IN_CONTEXT;\n+\tunsigned long lno = 0;\n+\n+\twhile (strbuf_getwholeline(&input, stdin, '\\n') != EOF) {\n+\t\tlno++;\n+\n+\t\tif (input.len > 7 && !memcmp(input.buf, \"<<<<<<<\", 7)) {\n+\t\t\tif (state != IN_CONTEXT)\n+\t\t\t\tdie(\"Malformed input:%lu: unexpected start of conflict.\", lno);\n+\t\t\tstate = IN_OURS;\n+\n+\t\t\tgoto do_put;\n+\t\t} else if (input.len > 7 && !memcmp(input.buf, \"|||||||\", 7)) {\n+\t\t\tif (state != IN_OURS)\n+\t\t\t\tdie(\"Malformed input:%lu: unexpected start of pre image.\", lno);\n+\t\t\tstate = IN_BASE;\n+\n+\t\t\tmmfile_from_strbuf(&target_files[0], &collector);\n+\n+\t\t\tgoto no_put;\n+\t\t} else if (input.len > 7 && !memcmp(input.buf, \"=======\", 7)) {\n+\t\t\tif (state != IN_BASE)\n+\t\t\t\tdie(\"Malformed input:%lu: expected diff3 conflict style.\", lno);\n+\t\t\tstate = IN_THEIRS;\n+\n+\t\t\tmmfile_from_strbuf(&base_file, &collector);\n+\n+\t\t\tgoto no_put;\n+\t\t} else if (input.len > 7 && !memcmp(input.buf, \">>>>>>>\", 7)) {\n+\t\t\tunsigned long len;\n+\t\t\tchar *dest;\n+\n+\t\t\tif (state != IN_THEIRS)\n+\t\t\t\tdie(\"Malformed input:%lu: unexpected end of conflict.\", lno);\n+\t\t\tstate = IN_CONTEXT;\n+\n+\t\t\tmmfile_from_strbuf(&target_files[1], &collector);\n+\n+\t\t\tlen = do_buf_cdiff(&base_file, target_files, 2, NULL);\n+\t\t\tdest = xmalloc(len);\n+\t\t\tdo_buf_cdiff(&base_file, target_files, 2, dest);\n+\t\t\twrite_or_die(fileno(stdout), dest, len);\n+\t\t\tfree(dest);\n+\t\t\tfree(base_file.ptr);\n+\t\t\tfree(target_files[0].ptr);\n+\t\t\tfree(target_files[1].ptr);\n+\n+\t\t\tgoto do_put;\n+\t\t}\n+\n+\t\tswitch (state) {\n+\t\tcase IN_OURS:\n+\t\tcase IN_BASE:\n+\t\tcase IN_THEIRS:\n+\t\t\tstrbuf_addbuf(&collector, &input);\n+\t\t\tgoto no_put;\n+\t\t}\n+\n+\tdo_put:\n+\t\twrite_or_die(fileno(stdout), input.buf, input.len);\n+\tno_put:\n+\t\tstrbuf_reset(&input);\n+\t}\n+\n+\tif (state != IN_CONTEXT)\n+\t\tdie(\"Malformed input:%lu: unexpected end of input.\", lno);\n+\n+\treturn 0;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex e8202f3..5ec84b8 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -121,5 +121,7 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);\n extern int cmd_show_ref(int argc, const char **argv, const char *prefix);\n extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);\n extern int cmd_replace(int argc, const char **argv, const char *prefix);\n+extern int cmd_cdiff(int argc, const char **argv, const char *prefix);\n+extern int cmd_cdiff_conflict_filter(int argc, const char **argv, const char *prefix);\n \n #endif\ndiff --git a/git.c b/git.c\nindex 90c6daf..6fb7d84 100644\n--- a/git.c\n+++ b/git.c\n@@ -386,6 +386,8 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"verify-pack\", cmd_verify_pack },\n \t\t{ \"show-ref\", cmd_show_ref, RUN_SETUP },\n \t\t{ \"pack-refs\", cmd_pack_refs, RUN_SETUP },\n+\t\t{ \"cdiff\", cmd_cdiff },\n+\t\t{ \"cdiff-conflict-filter\", cmd_cdiff_conflict_filter },\n \t};\n \tint i;\n \tstatic const char ext[] = STRIP_EXTENSION;\n-- \ntg: (6d81630..) bw/cdiff-conflict-style (depends on: master)\n"},{"id":"135005","messageId":"7v1vgi8eqw.fsf@alter.siamese.dyndns.org","threadId":"22719","inReplyTo":"1266521789-3617-1-git-send-email-bert.wesarg@googlemail.com","subject":"Re: [RFC] (reverse) combined diff conflict style","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-02-18T20:34:31Z","receivedAt":"2010-02-18T20:34:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Bert Wesarg <bert.wesarg@googlemail.com> writes:\n\n> ----- output ----\n>\n> 1\n> <<<<<<<\n>  -2\n> - 3\n> >>>>>>>\n> 4\n>\n> ------ end ------\n>\n> As you can see, the conflict region is way smaller as the diff3 one, but\n> keeps all information.\n>\n> I'm not doing much merges myself, so there are probably people out there who\n> can better judge the usefulness of this style.\n\nAs a format to review conflicted regions in a pager, this might be a good\nalternative representation.\n\nBut I doubt I would want to use this as a way for \"git merge\", \"git am -3\"\nand their friends to write a half-merged result out to the work tree for\nme to resolve.  With either --conflict=merge or --conflict=diff3, it is\neasy to pick lines from either side (you remove what is not needed in the\nfinal result), but with this format you always have to not just pick but\nremove the change marker at the beginning from the \"these are good, I'd\nuse them\" lines.  And you have to do so for every single line you reuse\nfrom either side.\n"},{"id":"135052","messageId":"36ca99e91002182315i25ad527dt553d79628734b02f@mail.gmail.com","threadId":"22719","inReplyTo":"7vocjlx056.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] (reverse) combined diff conflict style","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-02-19T07:15:15Z","receivedAt":"2010-02-19T07:15:15Z","isPatch":false,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"[ Sorry, I removed the list by mistake. CC'ed again ]\n\nOn Fri, Feb 19, 2010 at 06:30, Junio C Hamano <gitster@pobox.com> wrote:\n> Bert Wesarg <bert.wesarg@googlemail.com> writes:\n>> I use two programmed short-cuts in my editor for this. The first\n>> 'applies' the diff, i.e. it keeps all lines prefixed with ' ' or '+'\n>> and deletes lines with '-', and then removes the first column. The\n>> second 'reverses' a diff, i.e. exchanges '+' with '-' and vice versa.\n>> With these two operations I find it easier to resolve the conflict\n>> than with the mege/diff3 presentation.\n>>\n>> I'm also convinced, that it is currently impossible to implement this\n>> conflict style in the xdiff library. So it will probably be forever\n>> some 'external solution'.\n>\n> Why not?\n>\n> IIUC, your approach is to postprocess output diff3 style merge.\n>\n>  - First define your style as a new \"conflict style\" and store it in\n>   git_xmerge_style to pass it around.  \"checkout --conflict=bert\" would\n>   learn this style automatically.\n>\n>  - In ll_xdl_merge(), we usually call xdl_merge() and return directly its\n>   return value.  When style is \"bert\", instead of doing that, you pass\n>   \"diff3 style\" and drive xdl_merge(), _but_ you do not return.  Instead,\n>   you do your postprocessing right there and then return the result.\nThanks for this pointer. That looks really doable. Will report back later.\n\nBert\n"}]}