{"thread":{"id":"33185","subject":"[RFD] Combine diff improvements","startedAt":"2013-03-14T22:32:35Z","lastAt":"2013-03-23T17:23:28Z","messageCount":9,"participants":["Antoine Pelisse","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"211334","messageId":"CALWbr2zY3uo==QTd69t1eXNS4-CX1w3T-AaMjOLVmxj-SMJyvg@mail.gmail.com","threadId":"33185","inReplyTo":null,"subject":"[RFD] Combine diff improvements","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-14T22:32:35Z","receivedAt":"2013-03-14T22:32:35Z","isPatch":false,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"Hi,\nI've been working on combine diff recently and have seen that the current\nimplementation does not produce optimal results for coalescing lost lines.\n\nI would like to discuss some improvements.\n\nI think we can define an optimal solution as the shortest diff\noutput. That is that we coalesced as much line as we could.\nIt means that if each parent has the same file removed, the output will\nbe n lines long (all lines coalesce to each others).\n\nThe current implementation doesn't look for optimal solution but for the\neasiest/greedy solution. It also stops matching with a parent if it\ncan't find a match. As an example, it means that losing [1, 2, 3, 4] from\nparent A, and [3, 1, 2, 4] from parent B would give:\n- 1\n- 2\n--3\n- 4\n -1\n -2\n -4\n\nWhile if we invert the two parents order we will have:\n- 3\n--1\n--2\n- 4\n -3\n -4\n\nWhile clearly, in both cases, the optimal solution would be close to:\n- 3\n--1\n--2\n -3\n--4\n\nLet's say we have only one empty file (deleted), with p parents. In each\nparent, the file was n lines long, but the lines don't have to be the\nsame.\n\nIt clearly looks like an extension/variation of the Longest Common\nSubsequence (LCS) problem, but with p sequences (and the common\nsubsequences doesn't have to be common to all sequences).\n\nLCS dynamic programming is O(n²) in time and space complexity for two\nsequences.\n\nWe could extend it this way:\nAfter processing two of the p parents, let's find LCS and build a new\noptimal list of removals. Then find LCS again between this new list and\nthe third parent removals. And repeat until we made each parents.\n\nBest-case analysis:\nAll p parents have the same n lines.\nWe will find LCS and provide a n lines (the same lines) new list in\nO(n²), and then run it again in O(n²) with the next parent, etc.\nIt will end-up being O(pn²).\n\nWorst-case analysis:\nAll p parents have no lines in common.\nWe will find LCS and provide a 2n new list in O(n²).\nThen we run it again in O(2n x n), and again O(3n x n), etc, until\nO(pn x n).\nWhen we sum these all, we end-up with O(p² x n²)\n\nDoes it make any sense ? And is it worth implementing ?\n\nCheers,\nAntoine\n"},{"id":"211337","messageId":"7vfvzxwq5a.fsf@alter.siamese.dyndns.org","threadId":"33185","inReplyTo":"CALWbr2zY3uo==QTd69t1eXNS4-CX1w3T-AaMjOLVmxj-SMJyvg@mail.gmail.com","subject":"Re: [RFD] Combine diff improvements","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-14T22:52:17Z","receivedAt":"2013-03-14T22:52:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antoine Pelisse <apelisse@gmail.com> writes:\n\n> I would like to discuss some improvements.\n\n;-)\n\n> The current implementation doesn't look for optimal solution but for the\n> easiest/greedy solution.\n\nYes, you nailed it.\n\n> Does it make any sense? And is it worth implementing?\n\nProbably yes, and definitely.\n"},{"id":"211343","messageId":"7vboalw6lt.fsf@alter.siamese.dyndns.org","threadId":"33185","inReplyTo":"CALWbr2zY3uo==QTd69t1eXNS4-CX1w3T-AaMjOLVmxj-SMJyvg@mail.gmail.com","subject":"Re: [RFD] Combine diff improvements","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-15T05:54:22Z","receivedAt":"2013-03-15T05:54:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antoine Pelisse <apelisse@gmail.com> writes:\n\n> While if we invert the two parents order we will have:\n> - 3\n> --1\n> --2\n> - 4\n>  -3\n>  -4\n>\n> While clearly, in both cases, the optimal solution would be close to:\n> - 3\n> --1\n> --2\n>  -3\n> --4\n\nWe should shoot for better readability as the primary goal.  When I\nam viewing \"--cc\" output, I find it easier to read if the lines for\nthe same parent are consecutive.  That is, I find the right one far\neasier to grok than the left one:\n\n     - 1                - 1\n      -2                - 3\n     - 3                 -2\n      -4                 -4\n\nwhen trying to see what got changed from the first parent (we had 1\nand then 3 and whatever comes after this block; 2 and 4 are noise\nand it makes it easier to skip them because they are together).\n\nThis can probably be done as a post-process phase after you find the\ncoalescing matches to express the result in the smallest number of\nlines, but I thought it is worth mentioning that not all solutions\nwith the same number of lines are equally good.\n"},{"id":"211516","messageId":"1363525436-21667-1-git-send-email-apelisse@gmail.com","threadId":"33185","inReplyTo":"7vboalw6lt.fsf@alter.siamese.dyndns.org","subject":"[PATCH] combine-diff: coalesce lost lines optimally","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-17T13:03:56Z","receivedAt":"2013-03-17T13:03:56Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"This replaces the greedy implementation to coalesce lost lines by using\ndynamic programming to find the Longest Common Subsequence.\n\nThe O(n²) time complexity is obviously bigger than previous\nimplementation but it can produce shorter diff results (and most likely\neasier to read).\n\nList of lost lines is now doubly-linked because we reverse-read it when\nreading the direction matrix.\n\nSigned-off-by: Antoine Pelisse <apelisse@gmail.com>\n---\nHi,\nThis is a very first draft for improving the way we coalesce lost\nlines. It has only been tested with the two scenarios below.\n\nWhat is left to do:\n- Test it more extensively\n- Had some tests scenarios\n\nI'm also having a hard time trying it with more than two parents. How I\nam supposed to have more than two parents while octopus merge refuses if\nthere are conflicts ?\n\nTested scenarios:\ngit init\n>test\ngit add test\ngit commit -m initial\n\ngit checkout -b side1\nseq 10 >>test\ngit commit -m all -a\ngit checkout master\nseq 1 2 10 >test\ngit commit -m three -a\n\ngit merge side1\n>test\ngit commit -m merge -a\ngit show\n\nAND\n\ngit init\n>test\ngit add test\ngit commit -m initial\n\necho \"3\\n1\\n2\\n4\" >test\ngit commit -m shuffled -a\n\ngit checkout -b side HEAD^\necho \"1\\n2\\n3\\n4\" >test\ngit commit -m sorted -a\n\ngit merge master\n>test\ngit commit -m merge -a\ngit show\n\n combine-diff.c |  192 ++++++++++++++++++++++++++++++++++++++++++++++----------\n 1 file changed, 160 insertions(+), 32 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 35d41cd..252dd72 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -73,16 +73,24 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n\n /* Lines lost from parent */\n struct lline {\n-\tstruct lline *next;\n+\tstruct lline *next, *prev;\n \tint len;\n \tunsigned long parent_map;\n \tchar line[FLEX_ARRAY];\n };\n\n+/* Lines lost from current parent (before coalescing) */\n+struct plost {\n+\tstruct lline *lost_head, *lost_tail;\n+\tint len;\n+};\n+\n /* Lines surviving in the merge result */\n struct sline {\n-\tstruct lline *lost_head, **lost_tail;\n-\tstruct lline *next_lost;\n+\t/* Accumulated and coalesced lost lines */\n+\tstruct lline *lost;\n+\tint lenlost;\n+\tstruct plost plost;\n \tchar *bol;\n \tint len;\n \t/* bit 0 up to (N-1) are on if the parent has this line (i.e.\n@@ -94,6 +102,132 @@ struct sline {\n \tunsigned long *p_lno;\n };\n\n+enum coalesce_direction { MATCH, BASE, NEW };\n+\n+/* Coalesce new lines into base by finding LCS */\n+static struct lline *coalesce_lines(struct lline *base, int *lenbase,\n+\t\t\t\t    struct lline *new, int lennew,\n+\t\t\t\t    unsigned long parent)\n+{\n+\tint **lcs;\n+\tenum coalesce_direction **directions;\n+\tstruct lline *baseend, *newend;\n+\tint i, j, origbaselen = *lenbase;\n+\n+\tif (new == NULL)\n+\t\treturn base;\n+\n+\tif (base == NULL) {\n+\t\t*lenbase = lennew;\n+\t\treturn new;\n+\t}\n+\n+\t/*\n+\t * Coalesce new lines into base by finding the LCS\n+\t * - Create the table to run dynamic programing\n+\t * - Compute the LCS\n+\t * - Then reverse read the direction structure:\n+\t *   - If we have MATCH, assign parent to base flag, and consume\n+\t *   both baseend and newend\n+\t *   - Else if we have BASE, consume baseend\n+\t *   - Else if we have NEW, insert newend lline into base and\n+\t *   consume newend\n+\t */\n+\tlcs = xcalloc(origbaselen + 1, sizeof(int*));\n+\tdirections = xcalloc(origbaselen + 1, sizeof(enum coalesce_direction*));\n+\tfor (i = 0; i < origbaselen + 1; i++) {\n+\t\tlcs[i] = xcalloc(lennew + 1, sizeof(int));\n+\t\tdirections[i] = xcalloc(lennew + 1, sizeof(enum coalesce_direction));\n+\t\tdirections[i][0] = BASE;\n+\t}\n+\tfor (j = 1; j < lennew + 1; j++)\n+\t\tdirections[0][j] = NEW;\n+\n+\tfor (i = 1, baseend = base; i < origbaselen + 1; i++) {\n+\t\tfor (j = 1, newend = new; j < lennew + 1; j++) {\n+\t\t\tif (baseend->len == newend->len &&\n+\t\t\t    !memcmp(baseend->line, newend->line, baseend->len)) {\n+\t\t\t\tlcs[i][j] = lcs[i - 1][j - 1] + 1;\n+\t\t\t\tdirections[i][j] = MATCH;\n+\t\t\t} else if (lcs[i][j - 1] >= lcs[i - 1][j]) {\n+\t\t\t\tlcs[i][j] = lcs[i][j - 1];\n+\t\t\t\tdirections[i][j] = NEW;\n+\t\t\t} else {\n+\t\t\t\tlcs[i][j] = lcs[i - 1][j];\n+\t\t\t\tdirections[i][j] = BASE;\n+\t\t\t}\n+\t\t\tif (newend->next)\n+\t\t\t\tnewend = newend->next;\n+\t\t}\n+\t\tif (baseend->next)\n+\t\t\tbaseend = baseend->next;\n+\t}\n+\n+\tfor (i = 0; i < origbaselen + 1; i++)\n+\t\tfree(lcs[i]);\n+\tfree(lcs);\n+\n+\t/* At this point, baseend and newend point to the end of each lists */\n+\ti--;\n+\tj--;\n+\twhile (i != 0 || j != 0) {\n+\t\tif (directions[i][j] == MATCH) {\n+\t\t\tbaseend->parent_map |= 1<<parent;\n+\t\t\tbaseend = baseend->prev;\n+\t\t\tnewend = newend->prev;\n+\t\t\ti--;\n+\t\t\tj--;\n+\t\t} else if (directions[i][j] == NEW) {\n+\t\t\tstruct lline *lline;\n+\n+\t\t\tlline = newend;\n+\t\t\t/* Remove lline from new list and update newend */\n+\t\t\tif (lline->prev)\n+\t\t\t\tlline->prev->next = lline->next;\n+\t\t\telse\n+\t\t\t\tnew = lline->next;\n+\t\t\tif (lline->next)\n+\t\t\t\tlline->next->prev = lline->prev;\n+\n+\t\t\tnewend = lline->prev;\n+\t\t\tj--;\n+\n+\t\t\t/* Add lline to base list */\n+\t\t\tif (baseend) {\n+\t\t\t\tlline->next = baseend->next;\n+\t\t\t\tlline->prev = baseend;\n+\t\t\t\tif (lline->prev)\n+\t\t\t\t\tlline->prev->next = lline;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tlline->next = base;\n+\t\t\t\tbase = lline;\n+\t\t\t}\n+\t\t\t(*lenbase)++;\n+\n+\t\t\tif (lline->next)\n+\t\t\t\tlline->next->prev = lline;\n+\n+\t\t} else {\n+\t\t\tbaseend = baseend->prev;\n+\t\t\ti--;\n+\t\t}\n+\t}\n+\n+\tnewend = new;\n+\twhile (newend) {\n+\t\tstruct lline *lline = newend;\n+\t\tnewend = newend->next;\n+\t\tfree(lline);\n+\t}\n+\n+\tfor (i = 0; i < origbaselen + 1; i++)\n+\t\tfree(directions[i]);\n+\tfree(directions);\n+\n+\treturn base;\n+}\n+\n static char *grab_blob(const unsigned char *sha1, unsigned int mode,\n \t\t       unsigned long *size, struct userdiff_driver *textconv,\n \t\t       const char *path)\n@@ -129,29 +263,19 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)\n \tif (line[len-1] == '\\n')\n \t\tlen--;\n\n-\t/* Check to see if we can squash things */\n-\tif (sline->lost_head) {\n-\t\tlline = sline->next_lost;\n-\t\twhile (lline) {\n-\t\t\tif (lline->len == len &&\n-\t\t\t    !memcmp(lline->line, line, len)) {\n-\t\t\t\tlline->parent_map |= this_mask;\n-\t\t\t\tsline->next_lost = lline->next;\n-\t\t\t\treturn;\n-\t\t\t}\n-\t\t\tlline = lline->next;\n-\t\t}\n-\t}\n-\n \tlline = xmalloc(sizeof(*lline) + len + 1);\n \tlline->len = len;\n \tlline->next = NULL;\n+\tlline->prev = sline->plost.lost_tail;\n+\tif (lline->prev)\n+\t\tlline->prev->next = lline;\n+\telse\n+\t\tsline->plost.lost_head = lline;\n+\tsline->plost.lost_tail = lline;\n+\tsline->plost.len++;\n \tlline->parent_map = this_mask;\n \tmemcpy(lline->line, line, len);\n \tlline->line[len] = 0;\n-\t*sline->lost_tail = lline;\n-\tsline->lost_tail = &lline->next;\n-\tsline->next_lost = NULL;\n }\n\n struct combine_diff_state {\n@@ -194,7 +318,6 @@ static void consume_line(void *state_, char *line, unsigned long len)\n \t\t\t\txcalloc(state->num_parent,\n \t\t\t\t\tsizeof(unsigned long));\n \t\tstate->sline[state->nb-1].p_lno[state->n] = state->ob;\n-\t\tstate->lost_bucket->next_lost = state->lost_bucket->lost_head;\n \t\treturn;\n \t}\n \tif (!state->lost_bucket)\n@@ -255,8 +378,17 @@ static void combine_diff(const unsigned char *parent, unsigned int mode,\n \t\tstruct lline *ll;\n \t\tsline[lno].p_lno[n] = p_lno;\n\n+\t\t/* Coalesce new lines */\n+\t\tif (sline[lno].plost.lost_head) {\n+\t\t\tstruct sline *sl = &sline[lno];\n+\t\t\tsl->lost = coalesce_lines(sl->lost, &sl->lenlost,\n+\t\t\t\t\t\t  sl->plost.lost_head, sl->plost.len, n);\n+\t\t\tsl->plost.lost_head = sl->plost.lost_tail = NULL;\n+\t\t\tsl->plost.len = 0;\n+\t\t}\n+\n \t\t/* How many lines would this sline advance the p_lno? */\n-\t\tll = sline[lno].lost_head;\n+\t\tll = sline[lno].lost;\n \t\twhile (ll) {\n \t\t\tif (ll->parent_map & nmask)\n \t\t\t\tp_lno++; /* '-' means parent had it */\n@@ -276,7 +408,7 @@ static int interesting(struct sline *sline, unsigned long all_mask)\n \t/* If some parents lost lines here, or if we have added to\n \t * some parent, it is interesting.\n \t */\n-\treturn ((sline->flag & all_mask) || sline->lost_head);\n+\treturn ((sline->flag & all_mask) || sline->lost);\n }\n\n static unsigned long adjust_hunk_tail(struct sline *sline,\n@@ -459,7 +591,7 @@ static int make_hunks(struct sline *sline, unsigned long cnt,\n \t\thas_interesting = 0;\n \t\tfor (j = i; j < hunk_end && !has_interesting; j++) {\n \t\t\tunsigned long this_diff = sline[j].flag & all_mask;\n-\t\t\tstruct lline *ll = sline[j].lost_head;\n+\t\t\tstruct lline *ll = sline[j].lost;\n \t\t\tif (this_diff) {\n \t\t\t\t/* This has some changes.  Is it the\n \t\t\t\t * same as others?\n@@ -613,7 +745,7 @@ static void dump_sline(struct sline *sline, const char *line_prefix,\n \t\t\tint j;\n \t\t\tunsigned long p_mask;\n \t\t\tstruct sline *sl = &sline[lno++];\n-\t\t\tll = (sl->flag & no_pre_delete) ? NULL : sl->lost_head;\n+\t\t\tll = (sl->flag & no_pre_delete) ? NULL : sl->lost;\n \t\t\twhile (ll) {\n \t\t\t\tprintf(\"%s%s\", line_prefix, c_old);\n \t\t\t\tfor (j = 0; j < num_parent; j++) {\n@@ -664,7 +796,7 @@ static void reuse_combine_diff(struct sline *sline, unsigned long cnt,\n \tjmask = (1UL<<j);\n\n \tfor (lno = 0; lno <= cnt; lno++) {\n-\t\tstruct lline *ll = sline->lost_head;\n+\t\tstruct lline *ll = sline->lost;\n \t\tsline->p_lno[i] = sline->p_lno[j];\n \t\twhile (ll) {\n \t\t\tif (ll->parent_map & jmask)\n@@ -923,10 +1055,6 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,\n\n \tsline = xcalloc(cnt+2, sizeof(*sline));\n \tsline[0].bol = result;\n-\tfor (lno = 0; lno <= cnt + 1; lno++) {\n-\t\tsline[lno].lost_tail = &sline[lno].lost_head;\n-\t\tsline[lno].flag = 0;\n-\t}\n \tfor (lno = 0, cp = result; cp < result + result_size; cp++) {\n \t\tif (*cp == '\\n') {\n \t\t\tsline[lno].len = cp - sline[lno].bol;\n@@ -976,8 +1104,8 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,\n \tfree(result);\n\n \tfor (lno = 0; lno < cnt; lno++) {\n-\t\tif (sline[lno].lost_head) {\n-\t\t\tstruct lline *ll = sline[lno].lost_head;\n+\t\tif (sline[lno].lost) {\n+\t\t\tstruct lline *ll = sline[lno].lost;\n \t\t\twhile (ll) {\n \t\t\t\tstruct lline *tmp = ll;\n \t\t\t\tll = ll->next;\n--\n1.7.9.5\n"},{"id":"211519","messageId":"CALWbr2xWYiFULLDVA7b9WrVtmfdAvZC9SKBHjZE9aRc6kfRMGA@mail.gmail.com","threadId":"33185","inReplyTo":"1363525436-21667-1-git-send-email-apelisse@gmail.com","subject":"Re: [PATCH] combine-diff: coalesce lost lines optimally","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-17T13:58:59Z","receivedAt":"2013-03-17T13:58:59Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"> I'm also having a hard time trying it with more than two parents. How I\n> am supposed to have more than two parents while octopus merge refuses if\n> there are conflicts ?\n\nOK, creating the merge commit myself solves the issue:\n\ngit init\n>test\ngit add test\ngit commit -m initial\n\nseq 100 >test\ngit commit -m all -a\n\ngit checkout -b side1 HEAD^1\nseq 1 2 100 >test\ngit commit -m side1 -a\n\ngit checkout -b side2 HEAD^1\nseq 1 4 100 >test\ngit commit -m side2 -a\n\ngit checkout -b side3 HEAD^1\nseq 1 8 100 >test\ngit commit -m side3 -a\n\ngit checkout -b side4 HEAD^1\nseq 1 16 100 >test\ngit commit -m side4 -a\n\ngit checkout master\n>test\ngit add test\nTREE=$(git write-tree)\nCOMMIT=$(git commit-tree $TREE -p master -p side1 -p side2 -p side3 -p\nside4 -m merge)\ngit show $COMMIT\n\nThis will work with the basic greedy implementation if all parents are\nin this order. But the optimal result will be lost if we change the\norder of -p parameters in git-commit-tree.\nThe patch seems to be correct, always finding the best result (we\nalways have 100 lines diff) whatever the order of parents.\n"},{"id":"211526","messageId":"7vhak9rdne.fsf@alter.siamese.dyndns.org","threadId":"33185","inReplyTo":"1363525436-21667-1-git-send-email-apelisse@gmail.com","subject":"Re: [PATCH] combine-diff: coalesce lost lines optimally","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-17T20:10:13Z","receivedAt":"2013-03-17T20:10:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antoine Pelisse <apelisse@gmail.com> writes:\n\n> This replaces the greedy implementation to coalesce lost lines by using\n> dynamic programming to find the Longest Common Subsequence.\n>\n> The O(n²) time complexity is obviously bigger than previous\n> implementation but it can produce shorter diff results (and most likely\n> easier to read).\n>\n> List of lost lines is now doubly-linked because we reverse-read it when\n> reading the direction matrix.\n>\n> Signed-off-by: Antoine Pelisse <apelisse@gmail.com>\n> ---\n> Hi,\n> This is a very first draft for improving the way we coalesce lost\n> lines. It has only been tested with the two scenarios below.\n>\n> What is left to do:\n> - Test it more extensively\n> - Had some tests scenarios\n>\n> I'm also having a hard time trying it with more than two parents. How I\n> am supposed to have more than two parents while octopus merge refuses if\n> there are conflicts ?\n\n9fdb62af92c7 ([ACPI] merge 3549 4320 4485 4588 4980 5483 5651 acpica\nasus fops pnpacpi branches into release, 2006-01-24) is one of the\namusing examples ;-)  Cf.\n\n    http://thread.gmane.org/gmane.comp.version-control.git/15486\n"},{"id":"211528","messageId":"CALWbr2yfgA8kvtn4yxzPD5cencAPmwMqx=A6n4ohsjdzfAE1bQ@mail.gmail.com","threadId":"33185","inReplyTo":"7vhak9rdne.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] combine-diff: coalesce lost lines optimally","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-17T20:37:09Z","receivedAt":"2013-03-17T20:37:09Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"Hopefully, my patch takes about the same time as git 1.7.9.5 and\nproduces the same output on that commit ;)\nUnfortunately on a commit that would remove A LOT of lines (10000)\nfrom 7 parents, the times goes from 0.01s to 1.5s... I'm pretty sure\nthat scenario is quite uncommon though.\n\nOn Sun, Mar 17, 2013 at 9:10 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Antoine Pelisse <apelisse@gmail.com> writes:\n>\n>> This replaces the greedy implementation to coalesce lost lines by using\n>> dynamic programming to find the Longest Common Subsequence.\n>>\n>> The O(n²) time complexity is obviously bigger than previous\n>> implementation but it can produce shorter diff results (and most likely\n>> easier to read).\n>>\n>> List of lost lines is now doubly-linked because we reverse-read it when\n>> reading the direction matrix.\n>>\n>> Signed-off-by: Antoine Pelisse <apelisse@gmail.com>\n>> ---\n>> Hi,\n>> This is a very first draft for improving the way we coalesce lost\n>> lines. It has only been tested with the two scenarios below.\n>>\n>> What is left to do:\n>> - Test it more extensively\n>> - Had some tests scenarios\n>>\n>> I'm also having a hard time trying it with more than two parents. How I\n>> am supposed to have more than two parents while octopus merge refuses if\n>> there are conflicts ?\n>\n> 9fdb62af92c7 ([ACPI] merge 3549 4320 4485 4588 4980 5483 5651 acpica\n> asus fops pnpacpi branches into release, 2006-01-24) is one of the\n> amusing examples ;-)  Cf.\n>\n>     http://thread.gmane.org/gmane.comp.version-control.git/15486\n"},{"id":"211536","messageId":"7vhak9ps8w.fsf@alter.siamese.dyndns.org","threadId":"33185","inReplyTo":"1363525436-21667-1-git-send-email-apelisse@gmail.com","subject":"Re: [PATCH] combine-diff: coalesce lost lines optimally","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-17T22:37:51Z","receivedAt":"2013-03-17T22:37:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antoine Pelisse <apelisse@gmail.com> writes:\n\n> +/* Coalesce new lines into base by finding LCS */\n> +static struct lline *coalesce_lines(struct lline *base, int *lenbase,\n> +\t\t\t\t    struct lline *new, int lennew,\n> +\t\t\t\t    unsigned long parent)\n> +{\n\nDon't you want to pass flags so that you can use match_string_spaces()\nat places like this:\n\n> +\tfor (i = 1, baseend = base; i < origbaselen + 1; i++) {\n> +\t\tfor (j = 1, newend = new; j < lennew + 1; j++) {\n> +\t\t\tif (baseend->len == newend->len &&\n> +\t\t\t    !memcmp(baseend->line, newend->line, baseend->len)) {\n\nIOW, it looks to me that this wants to be rebuilt on top of\nfa04ae0be8cc (Allow combined diff to ignore white-spaces,\n2013-03-14).\n"},{"id":"212061","messageId":"1364059408-22346-1-git-send-email-apelisse@gmail.com","threadId":"33185","inReplyTo":"7vhak9ps8w.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] combine-diff: coalesce lost lines optimally","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2013-03-23T17:23:28Z","receivedAt":"2013-03-23T17:23:28Z","isPatch":true,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"This replaces the greedy implementation to coalesce lost lines by using\ndynamic programming to find the Longest Common Subsequence.\n\nThe O(n²) time complexity is obviously bigger than previous\nimplementation but it can produce shorter diff results (and most likely\neasier to read).\n\nList of lost lines is now doubly-linked because we reverse-read it when\nreading the direction matrix.\n\nSigned-off-by: Antoine Pelisse <apelisse@gmail.com>\n---\nHey,\nThis version includes some tests and is based on\nap/combine-diff-ignore-whitespace.\nAs you can see the last test is broken because the solution is not\noptimal for more than two parents. It would probably require to extend\nthe dynamic programming to a k-dimension matrix (for k parents) but the\nresult would end-up being O(n^k) (when removing n consecutives lines\nfrom p parents). I'm not sure there is any better solution known yet to\nthe k-LCS problem.\nImplementing the dynamic solution with the k-dimension matrix would\nprobably require to re-hash the strings (I guess it's already done by\nxdiff), as the number of string comparisons would increase.\n\nAnyway I'm not exactly sure where to go from here :)\n\nCheers,\nAntoine\n\n combine-diff.c           |  255 ++++++++++++++++++++++++++++++++++------------\n t/t4038-diff-combined.sh |  129 +++++++++++++++++++++++\n 2 files changed, 320 insertions(+), 64 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 6288485..77d7872 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -74,16 +74,24 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n\n /* Lines lost from parent */\n struct lline {\n-\tstruct lline *next;\n+\tstruct lline *next, *prev;\n \tint len;\n \tunsigned long parent_map;\n \tchar line[FLEX_ARRAY];\n };\n\n+/* Lines lost from current parent (before coalescing) */\n+struct plost {\n+\tstruct lline *lost_head, *lost_tail;\n+\tint len;\n+};\n+\n /* Lines surviving in the merge result */\n struct sline {\n-\tstruct lline *lost_head, **lost_tail;\n-\tstruct lline *next_lost;\n+\t/* Accumulated and coalesced lost lines */\n+\tstruct lline *lost;\n+\tint lenlost;\n+\tstruct plost plost;\n \tchar *bol;\n \tint len;\n \t/* bit 0 up to (N-1) are on if the parent has this line (i.e.\n@@ -95,34 +103,6 @@ struct sline {\n \tunsigned long *p_lno;\n };\n\n-static char *grab_blob(const unsigned char *sha1, unsigned int mode,\n-\t\t       unsigned long *size, struct userdiff_driver *textconv,\n-\t\t       const char *path)\n-{\n-\tchar *blob;\n-\tenum object_type type;\n-\n-\tif (S_ISGITLINK(mode)) {\n-\t\tblob = xmalloc(100);\n-\t\t*size = snprintf(blob, 100,\n-\t\t\t\t \"Subproject commit %s\\n\", sha1_to_hex(sha1));\n-\t} else if (is_null_sha1(sha1)) {\n-\t\t/* deleted blob */\n-\t\t*size = 0;\n-\t\treturn xcalloc(1, 1);\n-\t} else if (textconv) {\n-\t\tstruct diff_filespec *df = alloc_filespec(path);\n-\t\tfill_filespec(df, sha1, 1, mode);\n-\t\t*size = fill_textconv(textconv, df, &blob);\n-\t\tfree_filespec(df);\n-\t} else {\n-\t\tblob = read_sha1_file(sha1, &type, size);\n-\t\tif (type != OBJ_BLOB)\n-\t\t\tdie(\"object '%s' is not a blob!\", sha1_to_hex(sha1));\n-\t}\n-\treturn blob;\n-}\n-\n static int match_string_spaces(const char *line1, int len1,\n \t\t\t       const char *line2, int len2,\n \t\t\t       long flags)\n@@ -163,36 +143,180 @@ static int match_string_spaces(const char *line1, int len1,\n \treturn 0;\n }\n\n-static void append_lost(struct sline *sline, int n, const char *line, int len, long flags)\n+enum coalesce_direction { MATCH, BASE, NEW };\n+\n+/* Coalesce new lines into base by finding LCS */\n+static struct lline *coalesce_lines(struct lline *base, int *lenbase,\n+\t\t\t\t    struct lline *new, int lennew,\n+\t\t\t\t    unsigned long parent, long flags)\n {\n-\tstruct lline *lline;\n-\tunsigned long this_mask = (1UL<<n);\n-\tif (line[len-1] == '\\n')\n-\t\tlen--;\n+\tint **lcs;\n+\tenum coalesce_direction **directions;\n+\tstruct lline *baseend, *newend = NULL;\n+\tint i, j, origbaselen = *lenbase;\n\n-\t/* Check to see if we can squash things */\n-\tif (sline->lost_head) {\n-\t\tlline = sline->next_lost;\n-\t\twhile (lline) {\n-\t\t\tif (match_string_spaces(lline->line, lline->len,\n-\t\t\t\t\t\tline, len, flags)) {\n-\t\t\t\tlline->parent_map |= this_mask;\n-\t\t\t\tsline->next_lost = lline->next;\n-\t\t\t\treturn;\n+\tif (new == NULL)\n+\t\treturn base;\n+\n+\tif (base == NULL) {\n+\t\t*lenbase = lennew;\n+\t\treturn new;\n+\t}\n+\n+\t/*\n+\t * Coalesce new lines into base by finding the LCS\n+\t * - Create the table to run dynamic programing\n+\t * - Compute the LCS\n+\t * - Then reverse read the direction structure:\n+\t *   - If we have MATCH, assign parent to base flag, and consume\n+\t *   both baseend and newend\n+\t *   - Else if we have BASE, consume baseend\n+\t *   - Else if we have NEW, insert newend lline into base and\n+\t *   consume newend\n+\t */\n+\tlcs = xcalloc(origbaselen + 1, sizeof(int*));\n+\tdirections = xcalloc(origbaselen + 1, sizeof(enum coalesce_direction*));\n+\tfor (i = 0; i < origbaselen + 1; i++) {\n+\t\tlcs[i] = xcalloc(lennew + 1, sizeof(int));\n+\t\tdirections[i] = xcalloc(lennew + 1, sizeof(enum coalesce_direction));\n+\t\tdirections[i][0] = BASE;\n+\t}\n+\tfor (j = 1; j < lennew + 1; j++)\n+\t\tdirections[0][j] = NEW;\n+\n+\tfor (i = 1, baseend = base; i < origbaselen + 1; i++) {\n+\t\tfor (j = 1, newend = new; j < lennew + 1; j++) {\n+\t\t\tif (match_string_spaces(baseend->line, baseend->len,\n+\t\t\t\t\t\tnewend->line, newend->len, flags)) {\n+\t\t\t\tlcs[i][j] = lcs[i - 1][j - 1] + 1;\n+\t\t\t\tdirections[i][j] = MATCH;\n+\t\t\t} else if (lcs[i][j - 1] >= lcs[i - 1][j]) {\n+\t\t\t\tlcs[i][j] = lcs[i][j - 1];\n+\t\t\t\tdirections[i][j] = NEW;\n+\t\t\t} else {\n+\t\t\t\tlcs[i][j] = lcs[i - 1][j];\n+\t\t\t\tdirections[i][j] = BASE;\n+\t\t\t}\n+\t\t\tif (newend->next)\n+\t\t\t\tnewend = newend->next;\n+\t\t}\n+\t\tif (baseend->next)\n+\t\t\tbaseend = baseend->next;\n+\t}\n+\n+\tfor (i = 0; i < origbaselen + 1; i++)\n+\t\tfree(lcs[i]);\n+\tfree(lcs);\n+\n+\t/* At this point, baseend and newend point to the end of each lists */\n+\ti--;\n+\tj--;\n+\twhile (i != 0 || j != 0) {\n+\t\tif (directions[i][j] == MATCH) {\n+\t\t\tbaseend->parent_map |= 1<<parent;\n+\t\t\tbaseend = baseend->prev;\n+\t\t\tnewend = newend->prev;\n+\t\t\ti--;\n+\t\t\tj--;\n+\t\t} else if (directions[i][j] == NEW) {\n+\t\t\tstruct lline *lline;\n+\n+\t\t\tlline = newend;\n+\t\t\t/* Remove lline from new list and update newend */\n+\t\t\tif (lline->prev)\n+\t\t\t\tlline->prev->next = lline->next;\n+\t\t\telse\n+\t\t\t\tnew = lline->next;\n+\t\t\tif (lline->next)\n+\t\t\t\tlline->next->prev = lline->prev;\n+\n+\t\t\tnewend = lline->prev;\n+\t\t\tj--;\n+\n+\t\t\t/* Add lline to base list */\n+\t\t\tif (baseend) {\n+\t\t\t\tlline->next = baseend->next;\n+\t\t\t\tlline->prev = baseend;\n+\t\t\t\tif (lline->prev)\n+\t\t\t\t\tlline->prev->next = lline;\n \t\t\t}\n-\t\t\tlline = lline->next;\n+\t\t\telse {\n+\t\t\t\tlline->next = base;\n+\t\t\t\tbase = lline;\n+\t\t\t}\n+\t\t\t(*lenbase)++;\n+\n+\t\t\tif (lline->next)\n+\t\t\t\tlline->next->prev = lline;\n+\n+\t\t} else {\n+\t\t\tbaseend = baseend->prev;\n+\t\t\ti--;\n \t\t}\n \t}\n\n+\tnewend = new;\n+\twhile (newend) {\n+\t\tstruct lline *lline = newend;\n+\t\tnewend = newend->next;\n+\t\tfree(lline);\n+\t}\n+\n+\tfor (i = 0; i < origbaselen + 1; i++)\n+\t\tfree(directions[i]);\n+\tfree(directions);\n+\n+\treturn base;\n+}\n+\n+static char *grab_blob(const unsigned char *sha1, unsigned int mode,\n+\t\t       unsigned long *size, struct userdiff_driver *textconv,\n+\t\t       const char *path)\n+{\n+\tchar *blob;\n+\tenum object_type type;\n+\n+\tif (S_ISGITLINK(mode)) {\n+\t\tblob = xmalloc(100);\n+\t\t*size = snprintf(blob, 100,\n+\t\t\t\t \"Subproject commit %s\\n\", sha1_to_hex(sha1));\n+\t} else if (is_null_sha1(sha1)) {\n+\t\t/* deleted blob */\n+\t\t*size = 0;\n+\t\treturn xcalloc(1, 1);\n+\t} else if (textconv) {\n+\t\tstruct diff_filespec *df = alloc_filespec(path);\n+\t\tfill_filespec(df, sha1, 1, mode);\n+\t\t*size = fill_textconv(textconv, df, &blob);\n+\t\tfree_filespec(df);\n+\t} else {\n+\t\tblob = read_sha1_file(sha1, &type, size);\n+\t\tif (type != OBJ_BLOB)\n+\t\t\tdie(\"object '%s' is not a blob!\", sha1_to_hex(sha1));\n+\t}\n+\treturn blob;\n+}\n+\n+static void append_lost(struct sline *sline, int n, const char *line, int len)\n+{\n+\tstruct lline *lline;\n+\tunsigned long this_mask = (1UL<<n);\n+\tif (line[len-1] == '\\n')\n+\t\tlen--;\n+\n \tlline = xmalloc(sizeof(*lline) + len + 1);\n \tlline->len = len;\n \tlline->next = NULL;\n+\tlline->prev = sline->plost.lost_tail;\n+\tif (lline->prev)\n+\t\tlline->prev->next = lline;\n+\telse\n+\t\tsline->plost.lost_head = lline;\n+\tsline->plost.lost_tail = lline;\n+\tsline->plost.len++;\n \tlline->parent_map = this_mask;\n \tmemcpy(lline->line, line, len);\n \tlline->line[len] = 0;\n-\t*sline->lost_tail = lline;\n-\tsline->lost_tail = &lline->next;\n-\tsline->next_lost = NULL;\n }\n\n struct combine_diff_state {\n@@ -203,7 +327,6 @@ struct combine_diff_state {\n \tint n;\n \tstruct sline *sline;\n \tstruct sline *lost_bucket;\n-\tlong flags;\n };\n\n static void consume_line(void *state_, char *line, unsigned long len)\n@@ -236,14 +359,13 @@ static void consume_line(void *state_, char *line, unsigned long len)\n \t\t\t\txcalloc(state->num_parent,\n \t\t\t\t\tsizeof(unsigned long));\n \t\tstate->sline[state->nb-1].p_lno[state->n] = state->ob;\n-\t\tstate->lost_bucket->next_lost = state->lost_bucket->lost_head;\n \t\treturn;\n \t}\n \tif (!state->lost_bucket)\n \t\treturn; /* not in any hunk yet */\n \tswitch (line[0]) {\n \tcase '-':\n-\t\tappend_lost(state->lost_bucket, state->n, line+1, len-1, state->flags);\n+\t\tappend_lost(state->lost_bucket, state->n, line+1, len-1);\n \t\tbreak;\n \tcase '+':\n \t\tstate->sline[state->lno-1].flag |= state->nmask;\n@@ -276,7 +398,6 @@ static void combine_diff(const unsigned char *parent, unsigned int mode,\n \txpp.flags = flags;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \tmemset(&state, 0, sizeof(state));\n-\tstate.flags = flags;\n \tstate.nmask = nmask;\n \tstate.sline = sline;\n \tstate.lno = 1;\n@@ -298,8 +419,18 @@ static void combine_diff(const unsigned char *parent, unsigned int mode,\n \t\tstruct lline *ll;\n \t\tsline[lno].p_lno[n] = p_lno;\n\n+\t\t/* Coalesce new lines */\n+\t\tif (sline[lno].plost.lost_head) {\n+\t\t\tstruct sline *sl = &sline[lno];\n+\t\t\tsl->lost = coalesce_lines(sl->lost, &sl->lenlost,\n+\t\t\t\t\t\t  sl->plost.lost_head,\n+\t\t\t\t\t\t  sl->plost.len, n, flags);\n+\t\t\tsl->plost.lost_head = sl->plost.lost_tail = NULL;\n+\t\t\tsl->plost.len = 0;\n+\t\t}\n+\n \t\t/* How many lines would this sline advance the p_lno? */\n-\t\tll = sline[lno].lost_head;\n+\t\tll = sline[lno].lost;\n \t\twhile (ll) {\n \t\t\tif (ll->parent_map & nmask)\n \t\t\t\tp_lno++; /* '-' means parent had it */\n@@ -319,7 +450,7 @@ static int interesting(struct sline *sline, unsigned long all_mask)\n \t/* If some parents lost lines here, or if we have added to\n \t * some parent, it is interesting.\n \t */\n-\treturn ((sline->flag & all_mask) || sline->lost_head);\n+\treturn ((sline->flag & all_mask) || sline->lost);\n }\n\n static unsigned long adjust_hunk_tail(struct sline *sline,\n@@ -502,7 +633,7 @@ static int make_hunks(struct sline *sline, unsigned long cnt,\n \t\thas_interesting = 0;\n \t\tfor (j = i; j < hunk_end && !has_interesting; j++) {\n \t\t\tunsigned long this_diff = sline[j].flag & all_mask;\n-\t\t\tstruct lline *ll = sline[j].lost_head;\n+\t\t\tstruct lline *ll = sline[j].lost;\n \t\t\tif (this_diff) {\n \t\t\t\t/* This has some changes.  Is it the\n \t\t\t\t * same as others?\n@@ -656,7 +787,7 @@ static void dump_sline(struct sline *sline, const char *line_prefix,\n \t\t\tint j;\n \t\t\tunsigned long p_mask;\n \t\t\tstruct sline *sl = &sline[lno++];\n-\t\t\tll = (sl->flag & no_pre_delete) ? NULL : sl->lost_head;\n+\t\t\tll = (sl->flag & no_pre_delete) ? NULL : sl->lost;\n \t\t\twhile (ll) {\n \t\t\t\tprintf(\"%s%s\", line_prefix, c_old);\n \t\t\t\tfor (j = 0; j < num_parent; j++) {\n@@ -707,7 +838,7 @@ static void reuse_combine_diff(struct sline *sline, unsigned long cnt,\n \tjmask = (1UL<<j);\n\n \tfor (lno = 0; lno <= cnt; lno++) {\n-\t\tstruct lline *ll = sline->lost_head;\n+\t\tstruct lline *ll = sline->lost;\n \t\tsline->p_lno[i] = sline->p_lno[j];\n \t\twhile (ll) {\n \t\t\tif (ll->parent_map & jmask)\n@@ -966,10 +1097,6 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,\n\n \tsline = xcalloc(cnt+2, sizeof(*sline));\n \tsline[0].bol = result;\n-\tfor (lno = 0; lno <= cnt + 1; lno++) {\n-\t\tsline[lno].lost_tail = &sline[lno].lost_head;\n-\t\tsline[lno].flag = 0;\n-\t}\n \tfor (lno = 0, cp = result; cp < result + result_size; cp++) {\n \t\tif (*cp == '\\n') {\n \t\t\tsline[lno].len = cp - sline[lno].bol;\n@@ -1019,8 +1146,8 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,\n \tfree(result);\n\n \tfor (lno = 0; lno < cnt; lno++) {\n-\t\tif (sline[lno].lost_head) {\n-\t\t\tstruct lline *ll = sline[lno].lost_head;\n+\t\tif (sline[lno].lost) {\n+\t\t\tstruct lline *ll = sline[lno].lost;\n \t\t\twhile (ll) {\n \t\t\t\tstruct lline *tmp = ll;\n \t\t\t\tll = ll->next;\ndiff --git a/t/t4038-diff-combined.sh b/t/t4038-diff-combined.sh\nindex b7e16a7..1261dbb 100755\n--- a/t/t4038-diff-combined.sh\n+++ b/t/t4038-diff-combined.sh\n@@ -224,4 +224,133 @@ test_expect_success 'check combined output (ignore all spaces)' '\n \tcompare_diff_patch expected actual\n '\n\n+test_expect_success 'combine diff coalesce simple' '\n+\t>test &&\n+\tgit add test &&\n+\tgit commit -m initial &&\n+\ttest_seq 4 >test &&\n+\tgit commit -a -m empty1 &&\n+\tgit branch side1 &&\n+\tgit checkout HEAD^ &&\n+\ttest_seq 5 >test &&\n+\tgit commit -a -m empty2 &&\n+\ttest_must_fail git merge side1 &&\n+\t>test &&\n+\tgit commit -a -m merge &&\n+\tgit show >actual.tmp &&\n+\tsed -e \"1,/^@@@/d\" < actual.tmp >actual &&\n+\ttr -d Q <<-\\EOF >expected &&\n+\t--1\n+\t--2\n+\t--3\n+\t--4\n+\t- 5\n+\tEOF\n+\tcompare_diff_patch expected actual\n+'\n+\n+test_expect_success 'combine diff coalesce tricky' '\n+\t>test &&\n+\tgit add test &&\n+\tgit commit -m initial --allow-empty &&\n+\tcat <<-\\EOF >test &&\n+\t3\n+\t1\n+\t2\n+\t3\n+\t4\n+\tEOF\n+\tgit commit -a -m empty1 &&\n+\tgit branch -f side1 &&\n+\tgit checkout HEAD^ &&\n+\tcat <<-\\EOF >test &&\n+\t1\n+\t3\n+\t5\n+\t4\n+\tEOF\n+\tgit commit -a -m empty2 &&\n+\tgit branch -f side2 &&\n+\ttest_must_fail git merge side1 &&\n+\t>test &&\n+\tgit commit -a -m merge &&\n+\tgit show >actual.tmp &&\n+\tsed -e \"1,/^@@@/d\" < actual.tmp >actual &&\n+\ttr -d Q <<-\\EOF >expected &&\n+\t -3\n+\t--1\n+\t -2\n+\t--3\n+\t- 5\n+\t--4\n+\tEOF\n+\tcompare_diff_patch expected actual &&\n+\tgit checkout -f side1 &&\n+\ttest_must_fail git merge side2 &&\n+\t>test &&\n+\tgit commit -a -m merge &&\n+\tgit show >actual.tmp &&\n+\tsed -e \"1,/^@@@/d\" < actual.tmp >actual &&\n+\ttr -d Q <<-\\EOF >expected &&\n+\t- 3\n+\t--1\n+\t- 2\n+\t--3\n+\t -5\n+\t--4\n+\tEOF\n+\tcompare_diff_patch expected actual\n+'\n+\n+test_expect_failure 'combine diff coalesce three parents' '\n+\t>test &&\n+\tgit add test &&\n+\tgit commit -m initial --allow-empty &&\n+\tcat <<-\\EOF >test &&\n+\t3\n+\t1\n+\t2\n+\t3\n+\t4\n+\tEOF\n+\tgit commit -a -m empty1 &&\n+\tgit checkout -B side1 &&\n+\tgit checkout HEAD^ &&\n+\tcat <<-\\EOF >test &&\n+\t1\n+\t3\n+\t7\n+\t5\n+\t4\n+\tEOF\n+\tgit commit -a -m empty2 &&\n+\tgit branch -f side2 &&\n+\tgit checkout HEAD^ &&\n+\tcat <<-\\EOF >test &&\n+\t3\n+\t1\n+\t6\n+\t5\n+\t4\n+\tEOF\n+\tgit commit -a -m empty3 &&\n+\t>test &&\n+\tgit add test &&\n+\tTREE=$(git write-tree) &&\n+\tCOMMIT=$(git commit-tree -p HEAD -p side1 -p side2 -m merge $TREE) &&\n+\tgit show $COMMIT >actual.tmp &&\n+\tsed -e \"1,/^@@@/d\" < actual.tmp >actual &&\n+\ttr -d Q <<-\\EOF >expected &&\n+\t-- 3\n+\t---1\n+\t-  6\n+\t - 2\n+\t --3\n+\t  -7\n+\t- -5\n+\t---4\n+\tEOF\n+\tcompare_diff_patch expected actual\n+'\n+\n test_done\n--\n1.7.9.5\n"}]}