{"thread":{"id":"42327","subject":"[BUG] A part of an edge from an octopus merge gets colored, even with --color=never","startedAt":"2016-05-15T13:05:25Z","lastAt":"2018-10-10T00:42:54Z","messageCount":22,"participants":["Noam Postavsky","Johannes Sixt","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"286593","messageId":"CAM-tV-_Easz+HA0GX0YkY4FZ2LithQy0+omq64D-OoHKkRe55A@mail.gmail.com","threadId":"42327","inReplyTo":null,"subject":"[BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2016-05-15T13:05:25Z","receivedAt":"2016-05-15T13:05:25Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"With a certain topology involving an octopus merge, git log --graph\n--oneline --all --color=never produces output which includes some ANSI\nescape code coloring. Attached is a script to reproduce the problem\n(creates a git repository in subdir log-format-test), along with\nsample graph and valgrind output (indicates some unitialialized memory\naccess).\n\nI've observed the problem with Windows git versions 2.7.0, 2.5.3.\nI've NOT observed it with 1.9.5,\n\nOn GNU/Linux the symptom only appears when running with valgrind, I\ntried versions\n2.8.0, and 2.8.2.402.gedec370 (the last is where the valgrind output comes from)\n\n\n* e98205a c\n| *\u001b[31m-\u001b[m\u001b[31m.\u001b[m 808603b merge a b\n| |\\ \\ \n|/ / / \n| | * 8886a4e b\n| * | 2d8743f a\n| |/ \n* | e09af19 1\n|/ \n* 773004e 0\n\n\n==11287== Memcheck, a memory error detector\n==11287== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.\n==11287== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info\n==11287== Command: /home/npostavs/src/git/git log --oneline --graph --color=never --all\n==11287== \n==11287== Conditional jump or move depends on uninitialised value(s)\n==11287== at 0x4B0A48: strbuf_write_column (graph.c:79)\n==11287== by 0x4B0B3F: graph_draw_octopus_merge (graph.c:799)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== by 0x4055AA: run_argv (git.c:582)\n==11287== \n==11287== Use of uninitialised value of size 8\n==11287== at 0x4B05A0: column_get_color_code (graph.c:73)\n==11287== by 0x4B0A51: strbuf_write_column (graph.c:80)\n==11287== by 0x4B0B3F: graph_draw_octopus_merge (graph.c:799)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== \n==11287== Conditional jump or move depends on uninitialised value(s)\n==11287== at 0x4B0AC5: strbuf_write_column (graph.c:82)\n==11287== by 0x4B0B3F: graph_draw_octopus_merge (graph.c:799)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== by 0x4055AA: run_argv (git.c:582)\n==11287== \n==11287== Conditional jump or move depends on uninitialised value(s)\n==11287== at 0x4B0A48: strbuf_write_column (graph.c:79)\n==11287== by 0x4B0B6F: graph_draw_octopus_merge (graph.c:802)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== by 0x4055AA: run_argv (git.c:582)\n==11287== \n==11287== Use of uninitialised value of size 8\n==11287== at 0x4B05A0: column_get_color_code (graph.c:73)\n==11287== by 0x4B0A51: strbuf_write_column (graph.c:80)\n==11287== by 0x4B0B6F: graph_draw_octopus_merge (graph.c:802)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== \n==11287== Conditional jump or move depends on uninitialised value(s)\n==11287== at 0x4B0AC5: strbuf_write_column (graph.c:82)\n==11287== by 0x4B0B6F: graph_draw_octopus_merge (graph.c:802)\n==11287== by 0x4B1440: graph_output_commit_line (graph.c:837)\n==11287== by 0x4B1726: graph_next_line (graph.c:1126)\n==11287== by 0x4B1A5F: graph_show_commit (graph.c:1197)\n==11287== by 0x4BCF37: show_log (log-tree.c:601)\n==11287== by 0x4BD723: log_tree_commit (log-tree.c:879)\n==11287== by 0x441E8C: cmd_log_walk (log.c:345)\n==11287== by 0x443961: cmd_log (log.c:660)\n==11287== by 0x4050F9: run_builtin (git.c:350)\n==11287== by 0x405218: handle_builtin (git.c:536)\n==11287== by 0x4055AA: run_argv (git.c:582)\n==11287== \n==11287== \n==11287== HEAP SUMMARY:\n==11287== in use at exit: 651,170 bytes in 191 blocks\n==11287== total heap usage: 414 allocs, 223 frees, 1,756,967 bytes allocated\n==11287== \n==11287== LEAK SUMMARY:\n==11287== definitely lost: 825 bytes in 8 blocks\n==11287== indirectly lost: 1,515 bytes in 10 blocks\n==11287== possibly lost: 0 bytes in 0 blocks\n==11287== still reachable: 648,830 bytes in 173 blocks\n==11287== suppressed: 0 bytes in 0 blocks\n==11287== Rerun with --leak-check=full to see details of leaked memory\n==11287== \n==11287== For counts of detected and suppressed errors, rerun with: -v\n==11287== Use --track-origins=yes to see where uninitialised values come from\n==11287== ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 0 from 0)\n"},{"id":"286819","messageId":"573B6BF5.1090004@kdbg.org","threadId":"42327","inReplyTo":"CAM-tV-_Easz+HA0GX0YkY4FZ2LithQy0+omq64D-OoHKkRe55A@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2016-05-17T19:07:33Z","receivedAt":"2016-05-17T19:07:33Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 15.05.2016 um 15:05 schrieb Noam Postavsky:\n> With a certain topology involving an octopus merge, git log --graph\n> --oneline --all --color=never produces output which includes some ANSI\n> escape code coloring. Attached is a script to reproduce the problem\n> (creates a git repository in subdir log-format-test), along with\n> sample graph and valgrind output (indicates some unitialialized memory\n> access).\n>\n> I've observed the problem with Windows git versions 2.7.0, 2.5.3.\n> I've NOT observed it with 1.9.5,\n>\n> On GNU/Linux the symptom only appears when running with valgrind, I\n> tried versions\n> 2.8.0, and 2.8.2.402.gedec370 (the last is where the valgrind output comes from)\n>\n\nSorry, I can't reproduce your observation. I ran the script you provided \nwith HOME=$PWD and a minimal .gitconfig that only sets user.email. But \nvalgrind is happy with both 2.8.0 and v2.8.2-402-gedec370 on my Linux box.\n\n-- Hannes\n"},{"id":"286827","messageId":"20160517194533.GA11289@sigill.intra.peff.net","threadId":"42327","inReplyTo":"573B6BF5.1090004@kdbg.org","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-05-17T19:45:34Z","receivedAt":"2016-05-17T19:45:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 17, 2016 at 09:07:33PM +0200, Johannes Sixt wrote:\n\n> Am 15.05.2016 um 15:05 schrieb Noam Postavsky:\n> > With a certain topology involving an octopus merge, git log --graph\n> > --oneline --all --color=never produces output which includes some ANSI\n> > escape code coloring. Attached is a script to reproduce the problem\n> > (creates a git repository in subdir log-format-test), along with\n> > sample graph and valgrind output (indicates some unitialialized memory\n> > access).\n> > \n> > I've observed the problem with Windows git versions 2.7.0, 2.5.3.\n> > I've NOT observed it with 1.9.5,\n> > \n> > On GNU/Linux the symptom only appears when running with valgrind, I\n> > tried versions\n> > 2.8.0, and 2.8.2.402.gedec370 (the last is where the valgrind output comes from)\n> > \n> \n> Sorry, I can't reproduce your observation. I ran the script you provided\n> with HOME=$PWD and a minimal .gitconfig that only sets user.email. But\n> valgrind is happy with both 2.8.0 and v2.8.2-402-gedec370 on my Linux box.\n\nInteresting. It replicates out of the box for me. It looks like the\ncolumn pointer we are passing is bogus. If I instrument git like this:\n\ndiff --git a/graph.c b/graph.c\nindex 1350bdd..62a5810 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -76,6 +76,7 @@ static const char *column_get_color_code(unsigned short color)\n static void strbuf_write_column(struct strbuf *sb, const struct column *c,\n \t\t\t\tchar col_char)\n {\n+\twarning(\"c=%p, c->color = %d, max=%d\", c, c->color, column_colors_max);\n \tif (c->color < column_colors_max)\n \t\tstrbuf_addstr(sb, column_get_color_code(c->color));\n \tstrbuf_addch(sb, col_char);\n@@ -390,6 +391,9 @@ static void graph_insert_into_new_columns(struct git_graph *graph,\n \t */\n \tgraph->new_columns[graph->num_new_columns].commit = commit;\n \tgraph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);\n+\twarning(\"assigned %p, %d\",\n+\t\t&graph->new_columns[graph->num_new_columns],\n+\t\tgraph->new_columns[graph->num_new_columns].color);\n \tgraph->mapping[*mapping_index] = graph->num_new_columns;\n \t*mapping_index += 2;\n \tgraph->num_new_columns++;\n\nThen I get this output:\n\n warning: assigned 0x20d21d0, 12\n * 163b784 (c) c\n warning: assigned 0x20d8f90, 12\n warning: assigned 0x20d8fa0, 12\n warning: assigned 0x20d8fb0, 12\n warning: c=0x20d21d0, c->color = 12, max=12\n warning: c=0x20d8fc0, c->color = 0, max=12\n warning: c=0x20d8fc0, c->color = 0, max=12\n | *-. a9a6975 (HEAD -> m) merge a b\n\nNote that we set up f90, fa0, and fb0, but then pass fc0 into\nstrbuf_write_column (and it has bogus color values). It looks like we're\nreading one past the end of our array, but I haven't figured out where\nor why.\n\n-Peff\n"},{"id":"286828","messageId":"20160517195136.GB11289@sigill.intra.peff.net","threadId":"42327","inReplyTo":"20160517194533.GA11289@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-05-17T19:51:37Z","receivedAt":"2016-05-17T19:51:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 17, 2016 at 03:45:34PM -0400, Jeff King wrote:\n\n> Note that we set up f90, fa0, and fb0, but then pass fc0 into\n> strbuf_write_column (and it has bogus color values). It looks like we're\n> reading one past the end of our array, but I haven't figured out where\n> or why.\n\nLooking at the valgrind output reveals that. Here's an assert() that\ncatches it reliably for me:\n\ndiff --git a/graph.c b/graph.c\nindex 1350bdd..964bbd1 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -794,9 +794,11 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n \tfor (i = 0; i < num_dashes; i++) {\n \t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n+\t\tassert(col_num < graph->num_new_columns);\n \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n \t}\n \tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n+\tassert(col_num < graph->num_new_columns);\n \tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n \treturn num_dashes + 1;\n }\n\n(It's actually the first one which triggers). I'm not familiar enough\nwith the code to know whether the col_num computation is bogus, or\nwhether we needed to earlier increase the size of the \"new_columns\"\nfield.\n\n-Peff\n"},{"id":"286829","messageId":"20160517195541.GC11289@sigill.intra.peff.net","threadId":"42327","inReplyTo":"20160517195136.GB11289@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-05-17T19:55:41Z","receivedAt":"2016-05-17T19:55:41Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 17, 2016 at 03:51:37PM -0400, Jeff King wrote:\n\n> On Tue, May 17, 2016 at 03:45:34PM -0400, Jeff King wrote:\n> \n> > Note that we set up f90, fa0, and fb0, but then pass fc0 into\n> > strbuf_write_column (and it has bogus color values). It looks like we're\n> > reading one past the end of our array, but I haven't figured out where\n> > or why.\n> \n> Looking at the valgrind output reveals that. Here's an assert() that\n> catches it reliably for me:\n> \n> diff --git a/graph.c b/graph.c\n> index 1350bdd..964bbd1 100644\n> --- a/graph.c\n> +++ b/graph.c\n> @@ -794,9 +794,11 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n> \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n> \tfor (i = 0; i < num_dashes; i++) {\n> \t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n> +\t\tassert(col_num < graph->num_new_columns);\n> \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n> \t}\n> \tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n> +\tassert(col_num < graph->num_new_columns);\n> \tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n> \treturn num_dashes + 1;\n> }\n> \n> (It's actually the first one which triggers). I'm not familiar enough\n> with the code to know whether the col_num computation is bogus, or\n> whether we needed to earlier increase the size of the \"new_columns\"\n> field.\n\nAnd unsurprisingly, reverting 339c17bc7690b5436ac61c996cede3d52c85b50d\nseems to fix this (author cc'd). It's the extra \"commit_index\" addition\nthat causes the problem. But I'm still not sure what the correct\nsolution is.\n\n-Peff\n"},{"id":"286831","messageId":"573B78CE.1080200@kdbg.org","threadId":"42327","inReplyTo":"20160517194533.GA11289@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2016-05-17T20:02:22Z","receivedAt":"2016-05-17T20:02:22Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 17.05.2016 um 21:45 schrieb Jeff King:\n> On Tue, May 17, 2016 at 09:07:33PM +0200, Johannes Sixt wrote:\n>\n>> Am 15.05.2016 um 15:05 schrieb Noam Postavsky:\n>>> With a certain topology involving an octopus merge, git log --graph\n>>> --oneline --all --color=never produces output which includes some ANSI\n>>> escape code coloring. Attached is a script to reproduce the problem\n>>> (creates a git repository in subdir log-format-test), along with\n>>> sample graph and valgrind output (indicates some unitialialized memory\n>>> access).\n>>>\n>>> I've observed the problem with Windows git versions 2.7.0, 2.5.3.\n>>> I've NOT observed it with 1.9.5,\n>>>\n>>> On GNU/Linux the symptom only appears when running with valgrind, I\n>>> tried versions\n>>> 2.8.0, and 2.8.2.402.gedec370 (the last is where the valgrind output comes from)\n>>>\n>>\n>> Sorry, I can't reproduce your observation. I ran the script you provided\n>> with HOME=$PWD and a minimal .gitconfig that only sets user.email. But\n>> valgrind is happy with both 2.8.0 and v2.8.2-402-gedec370 on my Linux box.\n>\n> Interesting. It replicates out of the box for me.\n\n\"Out of the box\" are the magic words. I usually compile with -O0, which \ndoesn't trigger the valgrind report.\n\nWhen I compile with a 3.x based gcc on Windows, I see these warnings:\n\n CC color.o\ncolor.c: In function 'color_parse_mem':\ncolor.c:203: warning: 'c.value' may be used uninitialized in this function\ncolor.c:203: warning: 'c.blue' may be used uninitialized in this function\ncolor.c:203: warning: 'c.green' may be used uninitialized in this function\ncolor.c:203: warning: 'c.red' may be used uninitialized in this function\n\n(which triggered my curiosity in this bug report). But they seem to be \nunrelated and are most likely false positives.\n\n-- Hannes\n"},{"id":"286839","messageId":"20160517215749.GB16905@sigill.intra.peff.net","threadId":"42327","inReplyTo":"573B78CE.1080200@kdbg.org","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-05-17T21:57:49Z","receivedAt":"2016-05-17T21:57:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 17, 2016 at 10:02:22PM +0200, Johannes Sixt wrote:\n\n> > Interesting. It replicates out of the box for me.\n> \n> \"Out of the box\" are the magic words. I usually compile with -O0, which\n> doesn't trigger the valgrind report.\n\nHeh, I meant that Noam's test worked out of the box. I also build with\n-O0. I was able to replicate with different optimization levels.\n\nI think the interesting thing here is actually the libc (and therefore\npossibly your valgrind version). I tried compiling with ASAN and get a\ncolor value of \"48830\". But no ASAN warning!\n\nI think what is happening is that we over-allocate the new_columns array\nbased on a power of 2, but only initialize up to num_new_columns. So the\noff-by-one accesses heap memory that is allocated but which we have\nnever written to.\n\n> When I compile with a 3.x based gcc on Windows, I see these warnings:\n> \n> CC color.o\n> color.c: In function 'color_parse_mem':\n> color.c:203: warning: 'c.value' may be used uninitialized in this function\n> color.c:203: warning: 'c.blue' may be used uninitialized in this function\n> color.c:203: warning: 'c.green' may be used uninitialized in this function\n> color.c:203: warning: 'c.red' may be used uninitialized in this function\n> \n> (which triggered my curiosity in this bug report). But they seem to be\n> unrelated and are most likely false positives.\n\nYeah, I think that's unrelated. I'd be highly distrustful of\n-Wuninitialized in gcc 3.x. We had to mark quite a few false positives\nback then, that were later corrected in the 4.x series.\n\n-Peff\n"},{"id":"287134","messageId":"CAM-tV-9gAGBLsEh3=aa-bHT2DmJb=dfahq+kUW+0GLoc7eFq0w@mail.gmail.com","threadId":"42327","inReplyTo":"20160517195541.GC11289@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2016-05-20T22:12:59Z","receivedAt":"2016-05-20T22:12:59Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On Tue, May 17, 2016 at 3:55 PM, Jeff King wrote:\n>> (It's actually the first one which triggers). I'm not familiar enough\n>> with the code to know whether the col_num computation is bogus, or\n>> whether we needed to earlier increase the size of the \"new_columns\"\n>> field.\n>\n> And unsurprisingly, reverting 339c17bc7690b5436ac61c996cede3d52c85b50d\n> seems to fix this (author cc'd). It's the extra \"commit_index\" addition\n> that causes the problem. But I'm still not sure what the correct\n> solution is.\n\nLooking at the coloured output, for some octopus merges where the\nfirst parent edge immediately merges into the next column to the left,\ncol_num should be decremented by 1 (otherwise the colour of the \"-.\"\ndoesn't match the rest of that edge).\n\n| | *-.\n| | |\\ \\\n| |/ / /\n\nFor the other case where the first parent edge stays straight, the\ncurrent col_num computation is correct.\n\n| *-.\n| |\\ \\\n| | | *\n\nI'm not sure how to distinguish these cases in the code though. Is it\nenough to just compare against graph->num_new_columns?\n"},{"id":"350791","messageId":"CAM-tV--dHGJbxfWGKrRde+Q2-cnmCXNshQtX4PN7jnMWER_+bg@mail.gmail.com","threadId":"42327","inReplyTo":"CAM-tV-9gAGBLsEh3=aa-bHT2DmJb=dfahq+kUW+0GLoc7eFq0w@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-06-23T21:45:19Z","receivedAt":"2018-06-23T21:45:23Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"Archive link to previous discussion:\nhttps://marc.info/?l=git&m=146331754420554&w=2\n\nOn 20 May 2016 at 18:12, Noam Postavsky wrote:\n\n> Looking at the coloured output, for some octopus merges where the\n> first parent edge immediately merges into the next column to the left,\n> col_num should be decremented by 1 (otherwise the colour of the \"-.\"\n> doesn't match the rest of that edge).\n>\n> | | *-.\n> | | |\\ \\\n> | |/ / /\n>\n> For the other case where the first parent edge stays straight, the\n> current col_num computation is correct.\n>\n> | *-.\n> | |\\ \\\n> | | | *\n>\n> I'm not sure how to distinguish these cases in the code though. Is it\n> enough to just compare against graph->num_new_columns?\n\nI was recently reminded of this, here's a patch which does that.\n\n\nFrom d0c4f19ff162e63d5d23d456d0fc4fe9a32029ee Mon Sep 17 00:00:00 2001\nFrom: Noam Postavsky \nDate: Sat, 23 Jun 2018 16:56:43 -0400\nSubject: [PATCH v1] log: Fix coloring of certain octupus merge shapes\n\nFor octopus merges where the first parent edge immediately merges into\nthe next column to the left:\n\n| | *-.\n| | |\\ \\\n| |/ / /\n\nthen the number of columns should be one less than the usual case:\n\n| *-.\n| |\\ \\\n| | | *\n\nSigned-off-by: Noam Postavsky \n---\n graph.c | 12 ++++++++----\n 1 file changed, 8 insertions(+), 4 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex e1f6d3bdd..c919c86e8 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -856,12 +856,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n \tint col_num, i;\n \tint num_dashes =\n \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n-\tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n+\tint first_col = dashless_commits + graph->commit_index;\n+\tint last_col = first_col + (num_dashes / 2);\n+\tif (last_col >= graph->num_new_columns) {\n+\t\tfirst_col--;\n+\t\tlast_col--;\n+\t}\n+\tfor (i = 0, col_num = first_col; i < num_dashes; i++, col_num++) {\n \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n+\tstrbuf_write_column(sb, &graph->new_columns[last_col], '.');\n \treturn num_dashes + 1;\n }\n \n-- \n2.11.0\n\n"},{"id":"350847","messageId":"20180625162308.GA13719@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV--dHGJbxfWGKrRde+Q2-cnmCXNshQtX4PN7jnMWER_+bg@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-25T16:23:09Z","receivedAt":"2018-06-25T16:23:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 23, 2018 at 05:45:19PM -0400, Noam Postavsky wrote:\n\n> On 20 May 2016 at 18:12, Noam Postavsky wrote:\n\nMy, this is a blast from the past. :)\n\n> Subject: [PATCH v1] log: Fix coloring of certain octupus merge shapes\n> \n> For octopus merges where the first parent edge immediately merges into\n> the next column to the left:\n> \n> | | *-.\n> | | |\\ \\\n> | |/ / /\n> \n> then the number of columns should be one less than the usual case:\n> \n> | *-.\n> | |\\ \\\n> | | | *\n\nThese diagrams confused me for a minute, because I see two differences:\n\n 1. The first one has an extra apparently unrelated parallel branch on\n the far left.\n\n 2. The first has the first-parent of the \"*\" merge commit immediately\n join the branch.\n\nBut if I understand correctly, we only care about the second property.\nSo would it be accurate to show them as:\n\n | *-.\n | |\\ \\\n |/ / /\n\n | *-.\n | |\\ \\\n | | | *\n\n?\n\nI think that makes it easier to compare them.\n\nI don't remember much about our prior discussion, so let me try to talk\nmyself through the patch itself:\n\n> diff --git a/graph.c b/graph.c\n> index e1f6d3bdd..c919c86e8 100644\n> --- a/graph.c\n> +++ b/graph.c\n> @@ -856,12 +856,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n> \tint col_num, i;\n> \tint num_dashes =\n> \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n> -\tfor (i = 0; i < num_dashes; i++) {\n> -\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n\nOK, so the old code emitted num_dashes, and every pair was done with the\nsame column. Our highest iteration of this loop would use the column at\n(num_dashes-1) / 2. We know that num_dashes is always odd, so:\n\n num_dashes = 1 puts our last column at 0\n num_dashes = 3 puts our last column at 1\n\nAnd so on. So far so good.\n\n> +\tint first_col = dashless_commits + graph->commit_index;\n\nThis corresponds to the i=0 case, makes sense.\n\n> +\tint last_col = first_col + (num_dashes / 2);\n\nBut here our last_col misses the \"-1\". I don't think it matters because\nwe know num_dashes is always odd, and therefore due to integer\ntruncation (num_dashes-1)/2 == (num_dashes/2).\n\n> +\tif (last_col >= graph->num_new_columns) {\n> +\t\tfirst_col--;\n> +\t\tlast_col--;\n> +\t}\n\nThe shifting of last_col I expect as part of the fix. I was surprised by\nshifting first_col, though. Wouldn't it always start at 0 (offset by the\nprevious commits)? It definitely seems to be necessary, but I'm not sure\nI understand why.\n\n> +\tfor (i = 0, col_num = first_col; i < num_dashes; i++, col_num++) {\n> \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n> \t}\n> -\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n> -\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n> +\tstrbuf_write_column(sb, &graph->new_columns[last_col], '.');\n\nIn this new loop we count up our dashes and our columns. But now we have\n1-to-1 correspondence as we increment! I don't think that can be right.\nAnd indeed, if I take your original problem report and add an extra \"d\"\nbranch and make the octopus \"a b d\", then the problem comes back. You\ndon't notice with a 3-parent merge because \n\nWe need to increment col_num only half as much as num_dashes. Should we\nbe doing:\n\n for (col_num = first_col; col_num < last_col; col_num++) {\n\t strbuf_write_column(sb, &graph->new_columns[col_num], '-');\n\t strbuf_write_column(sb, &graph->new_columns[col_num], '-');\n }\n strbuf_write_column(sb, &graph->new_columns[last_col], '-');\n strbuf_write_column(sb, &graph->new_columns[last_col], '.');\n\nI.e., write \"--\" for each interior column, and then \"-.\" for the last\none?\n\n-Peff\n"},{"id":"351451","messageId":"CAM-tV-8sbbht7NUwf87-gq=+P=LNPyiEcv3zL+1BxfXK+ktmVA@mail.gmail.com","threadId":"42327","inReplyTo":"20180625162308.GA13719@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-06-30T12:47:16Z","receivedAt":"2018-06-30T12:47:21Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On 25 June 2018 at 12:23, Jeff King wrote:\n\n> These diagrams confused me for a minute, because I see two differences:\n>\n> 1. The first one has an extra apparently unrelated parallel branch on\n> the far left.\n>\n> 2. The first has the first-parent of the \"*\" merge commit immediately\n> join the branch.\n>\n> But if I understand correctly, we only care about the second property.\n\nYeah, sorry about that, I just copied them from \"natural\" occurences\nand didn't remove all the non-relevant detail.\n\n> I don't remember much about our prior discussion, so let me try to talk\n> myself through the patch itself:\n\nI didn't remember all that much either, but I did know that I didn't\nhave a very strong grasp on the code at the time. But your\ntalk-through convinced me that I really have no clue what's going on\n:)\n\nI'm still having trouble getting a big picture understanding of how\nthe graph struct relates the what gets drawn on screen, but through\nsome poking around with the debugger + trial & error, I've arrived at\na new patch which seems to work. It's also a lot simpler. I hope you\ncan tell me if it makes sense.\n\nAlso attached an updated test-multiway-merge.sh which allows adding\nmore branches to test different sized merges more easily.\n\n\nFrom ad40c5986264af1f5934b05082e16a3ce314caab Mon Sep 17 00:00:00 2001\nFrom: Noam Postavsky \nDate: Sat, 23 Jun 2018 16:56:43 -0400\nSubject: [PATCH v2] log: Fix coloring of certain octupus merge shapes\n\nThe graph->new_columns index should depend on graph->commit_index.\n\nSigned-off-by: Noam Postavsky \n---\n graph.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex e1f6d3bdd..c78259020 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -857,10 +857,10 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n \tint num_dashes =\n \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n \tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n+\t\tcol_num = (i / 2) + dashless_commits;\n \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n+\tcol_num = (i / 2) + dashless_commits;\n \tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n \treturn num_dashes + 1;\n }\n-- \n2.11.0\n\n"},{"id":"354664","messageId":"CAM-tV-_=nbo8T4krCRoni9F5JyZ41oxHZLGnuPgshHw3ZZMRWA@mail.gmail.com","threadId":"42327","inReplyTo":"CAM-tV-8sbbht7NUwf87-gq=+P=LNPyiEcv3zL+1BxfXK+ktmVA@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-08-06T18:34:45Z","receivedAt":"2018-08-06T18:34:48Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On 30 June 2018 at 08:47, Noam Postavsky wrote:\n\n> I'm still having trouble getting a big picture understanding of how\n> the graph struct relates the what gets drawn on screen, but through\n> some poking around with the debugger + trial & error, I've arrived at\n> a new patch which seems to work. It's also a lot simpler. I hope you\n> can tell me if it makes sense.\n>\n> Also attached an updated test-multiway-merge.sh which allows adding\n> more branches to test different sized merges more easily.\n\nPing? (I got some bounce message regarding test-multiway-merge.sh, but\nit does show up in the mailing list archive, so I think my message has\ngone through)\n\nhttps://marc.info/?l=git&m=153036284214253&w=2\n"},{"id":"354684","messageId":"20180806212603.GA21026@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV-8sbbht7NUwf87-gq=+P=LNPyiEcv3zL+1BxfXK+ktmVA@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-06T21:26:03Z","receivedAt":"2018-08-06T21:26:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 30, 2018 at 08:47:16AM -0400, Noam Postavsky wrote:\n\n> I'm still having trouble getting a big picture understanding of how\n> the graph struct relates the what gets drawn on screen, but through\n> some poking around with the debugger + trial & error, I've arrived at\n> a new patch which seems to work. It's also a lot simpler. I hope you\n> can tell me if it makes sense.\n> [...]\n> \tint num_dashes =\n> \t\t((graph->num_parents - dashless_commits) * 2) - 1;\n> \tfor (i = 0; i < num_dashes; i++) {\n> -\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n> +\t\tcol_num = (i / 2) + dashless_commits;\n> \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n> \t}\n> -\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n> +\tcol_num = (i / 2) + dashless_commits;\n\nHmm. So this seems to work because in your example, we're showing the\nmerge in slot 1. So the index is 1, and we have an off-by-one problem,\nand getting rid of that solves it.\n\nBut what if we had another line of development to the left of that?\nI.e., if the \"c\" in your script was itself on the right-hand side of a\nmerge.\n\nWe can simulate that by adding this to your script, right before the\ninvocation of log:\n\n # We traverse in commit-date order, so make sure the new commit is\n # more recent than the others. This is also the cause of your \"calling\n # it x doesn't work\" comment, I think (all of these commits are\n # created in a single second, so the order we hit the refs in --all\n # matters).\n sleep 1\n\n git checkout -b a-prime master^\n git commit --allow-empty -m a-prime\n\nThat gives me a graph like this (for d-e-f):\n\n * d342ed8 (HEAD -> a-prime) a-prime\n | * 14aae3a (c) c\n | | *-------. 4bacae1 (m) merge a b d e f\n | | |\\ \\ \\ \\ \\ \n | |/ / / / / / \n | | | | | | * f19c3a9 (f) f\n | |_|_|_|_|/ \n |/| | | | | \n | | | | | * 48fd961 (e) e\n | |_|_|_|/ \n |/| | | | \n | | | | * 3f4914f (d) d\n | |_|_|/ \n |/| | | \n | | | * 8bef98c (b) b\n | |_|/ \n |/| | \n | | * 253e7ba (a) a\n | |/ \n |/| \n | * 8a60f32 (master) 1\n |/ \n * b00ba42 0\n\nand graph->commit_index is 2.\n\nThat doesn't trigger valgrind, but all the colors are off-by-one (which\nmakes sense; we're off-by-one towards the beginning of the array now).\nUsing \"graph->commit_index - 1\" seems to yield the right results, but it\nfeels like we're just hacking around it. And my understanding was that\nthe \"straight edge\" case actually works with the current code, and we'd\nprobably be breaking that.\n\nI still think it makes more sense to iterate over the columns rather\nthan over the dashes, which removes a lot of these confusing cases. This\nis what I came up with:\n\ndiff --git a/graph.c b/graph.c\nindex c782590202..d0a3e0858b 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -847,22 +847,24 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)\n static int graph_draw_octopus_merge(struct git_graph *graph,\n \t\t\t\t struct strbuf *sb)\n {\n+\tint col_num, first_col, last_col;\n+\n+\t/* Skip the current commit, since we've already drawn its asterisk. */\n+\tfirst_col = graph->commit_index + 1;\n \t/*\n-\t * Here dashless_commits represents the number of parents\n-\t * which don't need to have dashes (because their edges fit\n-\t * neatly under the commit).\n+\t * We subtract three, one each for:\n+\t * - the commit we're directly on top of\n+\t * - the commit to our left that we're merged into\n+\t * - we want to point to the final column, not one past\n \t */\n-\tconst int dashless_commits = 2;\n-\tint col_num, i;\n-\tint num_dashes =\n-\t\t((graph->num_parents - dashless_commits) * 2) - 1;\n-\tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits;\n+\tlast_col = first_col + graph->num_parents - 3;\n+\n+\tfor (col_num = first_col; col_num <= last_col; col_num++) {\n \t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n+\t\tstrbuf_write_column(sb, &graph->new_columns[col_num],\n+\t\t\t\t col_num == last_col ? '.' : '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits;\n-\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n-\treturn num_dashes + 1;\n+\treturn 2 * (last_col - first_col + 1);\n }\n \n static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n\nI suspect it still has a bug, which is that it is handling this\nfirst-parent-goes-left case, but probably gets the straight-parent case\nwrong. But at least in this form, I think it is obvious to see where\nthat bug is (the \"three\" in the comment is not accurate in that latter\ncase, and it should be two). Which I think is what your original fix was\ngetting at: we need to set first/last to start off with, and then\n\"shrink\" them with a conditional depending on which form we're seeing.\n\n-Peff\n"},{"id":"354685","messageId":"20180806212825.GB21026@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV-_=nbo8T4krCRoni9F5JyZ41oxHZLGnuPgshHw3ZZMRWA@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-06T21:28:25Z","receivedAt":"2018-08-06T21:28:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 06, 2018 at 02:34:45PM -0400, Noam Postavsky wrote:\n\n> On 30 June 2018 at 08:47, Noam Postavsky wrote:\n> \n> > I'm still having trouble getting a big picture understanding of how\n> > the graph struct relates the what gets drawn on screen, but through\n> > some poking around with the debugger + trial & error, I've arrived at\n> > a new patch which seems to work. It's also a lot simpler. I hope you\n> > can tell me if it makes sense.\n> >\n> > Also attached an updated test-multiway-merge.sh which allows adding\n> > more branches to test different sized merges more easily.\n> \n> Ping? (I got some bounce message regarding test-multiway-merge.sh, but\n> it does show up in the mailing list archive, so I think my message has\n> gone through)\n> \n> https://marc.info/?l=git&m=153036284214253&w=2\n\nNo, it made it. It just got shuffled to the bottom of my pile (for\nfuture reference, you can ping more frequently than once a month if you\nthink something was dropped ;) ).\n\n-Peff\n"},{"id":"357171","messageId":"CAM-tV-_=4WuMGemm6RTB902-m8JfMKGp_OkQFuJMagPE8bOOtg@mail.gmail.com","threadId":"42327","inReplyTo":"20180806212603.GA21026@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-09-02T00:34:41Z","receivedAt":"2018-09-02T00:35:31Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On 6 August 2018 at 17:26, Jeff King wrote:\n\n> I suspect it still has a bug, which is that it is handling this\n> first-parent-goes-left case, but probably gets the straight-parent case\n> wrong. But at least in this form, I think it is obvious to see where\n> that bug is (the \"three\" in the comment is not accurate in that latter\n> case, and it should be two).\n\nYes, thanks, it makes a lot more sense this way. I believe the\nattached handles both parent types correctly.\n\n\nFrom a841a50b016c0cfc9183384e6c3ca85a23d1e11f Mon Sep 17 00:00:00 2001\nFrom: Noam Postavsky \nDate: Sat, 1 Sep 2018 20:07:16 -0400\nSubject: [PATCH v3] log: Fix coloring of certain octupus merge shapes\n\nFor octopus merges where the first parent edge immediately merges into\nthe next column to the left:\n\n| *-.\n| |\\ \\\n|/ / /\n\nthen the number of columns should be one less than the usual case:\n\n| *-.\n| |\\ \\\n| | | *\n\nAlso refactor the code to iterate over columns rather than dashes,\nbuilding from an initial patch suggestion by Jeff King.\n\nSigned-off-by: Noam Postavsky \n---\n graph.c | 48 ++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 36 insertions(+), 12 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex e1f6d3bdd..478c86dfb 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -848,21 +848,45 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n \t\t\t\t struct strbuf *sb)\n {\n \t/*\n-\t * Here dashless_commits represents the number of parents\n-\t * which don't need to have dashes (because their edges fit\n-\t * neatly under the commit).\n+\t * Here dashless_commits represents the number of parents which don't\n+\t * need to have dashes (because their edges fit neatly under the\n+\t * commit). And dashful_commits are the remaining ones.\n \t */\n \tconst int dashless_commits = 2;\n-\tint col_num, i;\n-\tint num_dashes =\n-\t\t((graph->num_parents - dashless_commits) * 2) - 1;\n-\tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n+\tint dashful_commits = graph->num_parents - dashless_commits;\n+\n+\t/*\n+\t * Usually, each parent gets its own column, like this:\n+\t *\n+\t * | *-.\n+\t * | |\\ \\\n+\t * | | | *\n+\t *\n+\t * Sometimes the first parent goes into an existing column, like this:\n+\t *\n+\t * | *-.\n+\t * | |\\ \\\n+\t * |/ / /\n+\t *\n+\t */\n+\tint parent_in_existing_cols = graph->num_parents -\n+\t\t(graph->num_new_columns - graph->num_columns);\n+\n+\t/*\n+\t * Draw the dashes. We start in the column following the\n+\t * dashless_commits, but subtract out the parent which goes to an\n+\t * existing column: we've already counted that column in commit_index.\n+\t */\n+\tint first_col = graph->commit_index + dashless_commits\n+\t\t- parent_in_existing_cols;\n+\tint i;\n+\n+\tfor (i = 0; i < dashful_commits; i++) {\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col],\n+\t\t\t\t i == dashful_commits-1 ? '.' : '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n-\treturn num_dashes + 1;\n+\treturn 2 * dashful_commits;\n }\n \n static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n-- \n2.11.0\n\n"},{"id":"357697","messageId":"20180908161316.GA326@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV-_=4WuMGemm6RTB902-m8JfMKGp_OkQFuJMagPE8bOOtg@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-08T16:13:16Z","receivedAt":"2018-09-08T16:13:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Sep 01, 2018 at 08:34:41PM -0400, Noam Postavsky wrote:\n\n> On 6 August 2018 at 17:26, Jeff King wrote:\n> \n> > I suspect it still has a bug, which is that it is handling this\n> > first-parent-goes-left case, but probably gets the straight-parent case\n> > wrong. But at least in this form, I think it is obvious to see where\n> > that bug is (the \"three\" in the comment is not accurate in that latter\n> > case, and it should be two).\n> \n> Yes, thanks, it makes a lot more sense this way. I believe the\n> attached handles both parent types correctly.\n\nGreat (and sorry for the delayed response).\n\nLet me see if I understand it...\n\n> diff --git a/graph.c b/graph.c\n> index e1f6d3bdd..478c86dfb 100644\n> --- a/graph.c\n> +++ b/graph.c\n> @@ -848,21 +848,45 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n> \t\t\t\t struct strbuf *sb)\n> {\n> \t/*\n> -\t * Here dashless_commits represents the number of parents\n> -\t * which don't need to have dashes (because their edges fit\n> -\t * neatly under the commit).\n> +\t * Here dashless_commits represents the number of parents which don't\n> +\t * need to have dashes (because their edges fit neatly under the\n> +\t * commit). And dashful_commits are the remaining ones.\n> \t */\n> \tconst int dashless_commits = 2;\n\nWhy is dashless commits always going to be 2? I thought at first that it\nwas representing the merge commit itself, plus the line of development\nto the left. But the latter could be arbitrarily sized.\n\nBut that's not what it is, because we handle that by using\ngraph->commit_index in the iteration below. So I get that the merge\ncommit itself does not need a dash. What's the other one?\n\n> +\tint dashful_commits = graph->num_parents - dashless_commits;\n\nOK, this makes sense.\n\n> +\t/*\n> +\t * Usually, each parent gets its own column, like this:\n> +\t *\n> +\t * | *-.\n> +\t * | |\\ \\\n> +\t * | | | *\n> +\t *\n> +\t * Sometimes the first parent goes into an existing column, like this:\n> +\t *\n> +\t * | *-.\n> +\t * | |\\ \\\n> +\t * |/ / /\n> +\t *\n> +\t */\n> +\tint parent_in_existing_cols = graph->num_parents -\n> +\t\t(graph->num_new_columns - graph->num_columns);\n\nAh, OK, this is the magic part: we compare num_new_columns versus\nnum_columns to see which case we have. Makes sense. And this comment is\nvery welcome to explain it visually.\n\n> +\t/*\n> +\t * Draw the dashes. We start in the column following the\n> +\t * dashless_commits, but subtract out the parent which goes to an\n> +\t * existing column: we've already counted that column in commit_index.\n> +\t */\n> +\tint first_col = graph->commit_index + dashless_commits\n> +\t\t- parent_in_existing_cols;\n> +\tint i;\n\nOK, so we start at the commit_index, which makes sense. We skip past the\ndashless commits (which includes the merge itself, plus the other\nmystery one). And then we go back by the parents in existing columns,\nwhich I think is either 1 or 2.\n\nAnd I think that may be the root of my confusion. The other \"dashless\"\ncommit is the parent we've already printed before hitting this function,\nthe left-hand line that goes all the way down below where we print the\nother parents.\n\nSo I think this is doing the right thing. I'm not sure if there's a\nbetter way to explain \"dashless\" or not.\n\n> +\tfor (i = 0; i < dashful_commits; i++) {\n> +\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n> +\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col],\n> +\t\t\t\t i == dashful_commits-1 ? '.' : '-');\n> \t}\n\nAnd this loop is nice and simple now. Good.\n\nSo I think this patch looks right. This is all sufficiently complex that\nwe probably want to add something to the test suite. For reference,\nhere's how I hacked up your original script to put more commits on the\nleft:\n\n--- test-multiway-merge.sh.orig\t2018-09-08 12:04:23.007468601 -0400\n+++ test-multiway-merge.sh\t2018-09-08 12:11:02.267750789 -0400\n@@ -25,6 +25,11 @@\n \n \n \"$GIT\" init\n+for base in 1 2 3 4; do\n+ echo base-$base >foo\n+ git add foo\n+ git commit -m base-$base\n+done\n echo 0 > foo\n \"$GIT\" add foo\n \"$GIT\" commit -m 0\n@@ -47,4 +52,10 @@\n \"$GIT\" checkout m\n \"$GIT\" merge -m \"merge a b $*\" a b \"$@\"\n \n+sleep 1\n+for i in 1 2 3 4; do\n+ git checkout -b $i-prime master~$i\n+ git commit --allow-empty -m side-$i\n+done\n+\n valgrind \"$GIT\" log --oneline --graph --all\n\nThen running it as \"test-multiway-merge d e f\" gives a nice wide graph\nthat should show any off-by-one mistakes. We should be able to do away\nwith the \"sleep\" in a real test if we make use of test_commit(), which\nadvances GIT_COMMITTER_DATE by one second for each commit.\n\nDo you feel comfortable trying to add something to the test suite for\nthis?\n\n-Peff\n"},{"id":"358809","messageId":"CAM-tV-9N36puQHKQ38JxAxNR5Zen=3jM7pG7vHioYvvGTxLHCg@mail.gmail.com","threadId":"42327","inReplyTo":"20180908161316.GA326@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-09-25T00:27:47Z","receivedAt":"2018-09-25T00:28:04Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On Sat, 8 Sep 2018 at 12:13, Jeff King wrote:\n\n> Great (and sorry for the delayed response).\n\nNo problem, I know it's not the most urgent bug ever :)\n\n> So I think this is doing the right thing. I'm not sure if there's a\n> better way to explain \"dashless\" or not.\n\nI've updated the comments and renamed a few variables, see if that helps.\n\n> Do you feel comfortable trying to add something to the test suite for\n> this?\n\nUm, sort of. I managed to recast my script into the framework of the\nother tests (see attached t4299-octopus.sh); it seems like it should\ngo into t4202-log.sh, but it's not clear to me how I can do this\nwithout breaking all the other tests which expect a certain sequence\nof commits.\n\n\nFrom ade526d32f692cae06000bb413ff29dad3f6109e Mon Sep 17 00:00:00 2001\nFrom: Noam Postavsky \nDate: Sat, 1 Sep 2018 20:07:16 -0400\nSubject: [PATCH v4] log: Fix coloring of certain octupus merge shapes\n\nFor octopus merges where the first parent edge immediately merges into\nthe next column to the left:\n\n| *-.\n| |\\ \\\n|/ / /\n\nthen the number of columns should be one less than the usual case:\n\n| *-.\n| |\\ \\\n| | | *\n\nAlso refactor the code to iterate over columns rather than dashes,\nbuilding from an initial patch suggestion by Jeff King.\n\nSigned-off-by: Noam Postavsky \n---\n graph.c | 56 +++++++++++++++++++++++++++++++++++++++++---------------\n 1 file changed, 41 insertions(+), 15 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex e1f6d3bdd..a3366f6da 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -842,27 +842,53 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)\n }\n \n /*\n- * Draw an octopus merge and return the number of characters written.\n+ * Draw the horizontal dashes of an octopus merge and return the number of\n+ * characters written.\n */\n static int graph_draw_octopus_merge(struct git_graph *graph,\n \t\t\t\t struct strbuf *sb)\n {\n \t/*\n-\t * Here dashless_commits represents the number of parents\n-\t * which don't need to have dashes (because their edges fit\n-\t * neatly under the commit).\n-\t */\n-\tconst int dashless_commits = 2;\n-\tint col_num, i;\n-\tint num_dashes =\n-\t\t((graph->num_parents - dashless_commits) * 2) - 1;\n-\tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n+\t * Here dashless_parents represents the number of parents which don't\n+\t * need to have dashes (the edges labeled \"0\" and \"1\"). And\n+\t * dashful_parents are the remaining ones.\n+\t *\n+\t * | *---.\n+\t * | |\\ \\ \\\n+\t * | | | | |\n+\t * x 0 1 2 3\n+\t *\n+\t */\n+\tconst int dashless_parents = 2;\n+\tint dashful_parents = graph->num_parents - dashless_parents;\n+\n+\t/*\n+\t * Usually, each parent gets its own column, like the diagram above, but\n+\t * sometimes the first parent goes into an existing column, like this:\n+\t *\n+\t * | *---.\n+\t * | |\\ \\ \\\n+\t * |/ / / /\n+\t * x 0 1 2\n+\t *\n+\t * In which case there will be more parents than the delta of columns.\n+\t */\n+\tint delta_cols = (graph->num_new_columns - graph->num_columns);\n+\tint parent_in_old_cols = graph->num_parents - delta_cols;\n+\n+\t/*\n+\t * In both cases, commit_index corresponds to the edge labeled \"0\".\n+\t */\n+\tint first_col = graph->commit_index + dashless_parents\n+\t - parent_in_old_cols;\n+\n+\tint i;\n+\tfor (i = 0; i < dashful_parents; i++) {\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col],\n+\t\t\t\t i == dashful_parents-1 ? '.' : '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n-\treturn num_dashes + 1;\n+\treturn 2 * dashful_parents;\n }\n \n static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n-- \n2.11.0\n\n"},{"id":"359487","messageId":"CAM-tV-8PRAPdrQie=Vy8hiRuDr6FaQzsJFuwMtR5PS6Y+Lbo+w@mail.gmail.com","threadId":"42327","inReplyTo":"CAM-tV-9N36puQHKQ38JxAxNR5Zen=3jM7pG7vHioYvvGTxLHCg@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-10-03T00:09:46Z","receivedAt":"2018-10-03T00:10:07Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On Mon, 24 Sep 2018 at 20:27, Noam Postavsky\n wrote:\n>\n> On Sat, 8 Sep 2018 at 12:13, Jeff King wrote:\n>\n> > Great (and sorry for the delayed response).\n>\n> No problem, I know it's not the most urgent bug ever :)\n\nPing. :)\n\n> I managed to recast my script into the framework of the\n> other tests (see attached t4299-octopus.sh); it seems like it should\n> go into t4202-log.sh, but it's not clear to me how I can do this\n> without breaking all the other tests which expect a certain sequence\n> of commits.\n"},{"id":"359493","messageId":"20181003042437.GA27034@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV-9N36puQHKQ38JxAxNR5Zen=3jM7pG7vHioYvvGTxLHCg@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-03T04:24:37Z","receivedAt":"2018-10-03T04:26:52Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 24, 2018 at 08:27:47PM -0400, Noam Postavsky wrote:\n\n> > So I think this is doing the right thing. I'm not sure if there's a\n> > better way to explain \"dashless\" or not.\n> \n> I've updated the comments and renamed a few variables, see if that helps.\n\nYeah, I really like your explanations/diagrams in the comments. It makes\nthe logic very clear.\n\n> > Do you feel comfortable trying to add something to the test suite for\n> > this?\n> \n> Um, sort of. I managed to recast my script into the framework of the\n> other tests (see attached t4299-octopus.sh); it seems like it should\n> go into t4202-log.sh, but it's not clear to me how I can do this\n> without breaking all the other tests which expect a certain sequence\n> of commits.\n\nIt's OK to start a new script if you have some tricky or complicated\nsetup. Probably it ought to be t4214-log-graph-octopus to keep it near\nthe other log tests. And it should be added in the actual patch, but I\nassume you just kept it out here since you weren't sure where to put it\nyet.\n\nI'll try to comment on the test script itself.\n\n> #!/bin/sh\n> \n> test_description='git log'\n\nThis should actually describe what's going on in the test. Usually a\none-sentence is OK, but I think it might be good to specifically mention\nthat we're handling this special octopus case.\n\n> . ./test-lib.sh\n> \n> make_octopus_merge () {\n> \tfor i ; do\n> \t\tgit checkout master -b $i || return $?\n> \t\t# Make tag name different from branch name.\n> \t\ttest_commit $i $i $i tag$i || return $?\n> \tdone\n\nPlease use:\n\n for i in \"$@\"\n\nwhich is a bit less subtle (there's also only one caller of this\nfunction, so it could be inlined; note that it's OK to use \"return\" in a\ntest_expect block).\n\nWhy do we need the tag name to be different?\n\n> \tgit checkout 1 -b merge &&\n\nThis is assuming we just made a branch called \"1\", but that's one of the\narguments. Probably this should be \"$1\" (or the whole thing should just\nbe inlined so it is clear that what the set of parameters we expect is).\n\n> \ttest_tick &&\n> \tgit merge -m octopus-merge \"$@\"\n\nGood use of test_tick so that we have predictable traversal ordering.\n\n> test_expect_success 'set up merge history' '\n> \ttest_commit initial &&\n> \tmake_octopus_merge 1 2 3 4 &&\n> \tgit checkout 1 -b L &&\n> \ttest_commit left\n> '\n\nIt might actually be worth setting up the uncolored expect file as part\nof this, since it so neatly diagrams the graph you're trying to produce.\n\nI.e., something like (completely untested; note that the leading\nindentation is all tabs, which will be removed by the \"<<-\" operator):\n\ntest_expect_success 'set up merge history' '\n\t# This is the graph we expect to generate here.\n\tcat >expect.uncolored <<-\\EOF &&\n\t* left\n\t| *---. octopus-merge\n\t| |\\ \\ \\\n\t|/ / / /\n\t| | | * 4\n\t| | * | 3\n\t| | |/\n\t| * | 2\n\t| |/\n\t* | 1\n\t|/\n\t* initial\n\tEOF\n\tfor i in 1 2 3 4; do\n\t\tgit checkout -b $i $master || return $?\n\t\t# Make tag name different from branch name.\n\t\ttest_commit $i $i $i tag$i || return $?\n\tdone &&\n\tgit checkout -b merge 1 &&\n\ttest_tick &&\n\tgit merge -m octopus-merge 1 2 3 4\n'\n\n> cat > expect.colors <<\\EOF\n\nA few style bits: we prefer to keep even setup steps like this inside a\ntest_expect block (though you may see some very old tests which have not\nbeen fixed yet). Also, we omit the space after \">\".\n\n> * left\n> | *---. octopus-merge\n> | |\\ \\ \\\n> |/ / / /\n> | | | * 4\n> | | * | 3\n> | | |/\n> | * | 2\n> | |/\n> * | 1\n> |/\n> * initial\n\nYikes. :) This one is pretty hard to read. I'm not sure if there's a\ngood alternative. If you pipe the output of test_decode through\nthis:\n\n sed '\n\ts/./R/g;\n\ts/./B/g;\n\ts/./M/g;\n\ts/./Y/g;\n '\n\nyou get this:\n\n * left\n R *BBMM octopus-merge\n R RY B M\n RR Y B M\n R Y B * 4\n R Y * M 3\n R Y MM\n R * M 2\n R MM\n * M 1\n MM\n * initial\n\nwhich is admittedly pretty horrible, too, but at least resembles a\ngraph. I dunno.\n\nI'm also not thrilled that we depend on the exact sequence of default\ncolors, but I suspect it's not the first time. And it wouldn't be too\nhard to update it if that default changes.\n\n> test_expect_success 'log --graph with tricky octopus merge' '\n> \tgit log --color=always --graph --date-order --pretty=tformat:%s --all |\n> \t\ttest_decode_color | sed \"s/ *\\$//\" >actual &&\n\nTry not to put \"git\" on the left-hand side of a pipe, since it means\nwe'll miss its exit code (and especially we'd miss its death due to ASan\nor Valgrind problems, which I think was one of the major ways of\ndetecting the original problem). So:\n\n git log ... >actual.raw &&\n test_decode_color actual &&\n test_cmp expect.colors actual\n\n> cat > expect <<\\EOF\n> * left\n> | *---. octopus-merge\n> | |\\ \\ \\\n> |/ / / /\n> | | | * 4\n> | | * | 3\n> | | |/\n> | * | 2\n> | |/\n> * | 1\n> |/\n> * initial\n> EOF\n\nThis is the expect output that I suggested showing earlier. :)\n\n> test_expect_success 'log --graph with tricky octopus merge' '\n> \tdebug git log --color=never --graph --date-order --pretty=tformat:%s --all |\n> \t\tsed \"s/ *\\$//\" >actual &&\n\nLeftover \"debug\" cruft?\n\nThe same pipe comment applies as above.\n\n> test_done\n> test_done\n\nTwo dones; we exit after the first one (so everything after this is\nignored).\n\nI think it's OK to have a dedicated script for even these two tests, if\nit makes things easier to read. However, would we also want to test the\noctopus without the problematic graph here? I think if we just omit\n\"left\" we get that, don't we?\n\n-Peff\n"},{"id":"359593","messageId":"CAM-tV-88J3ZAALwZeEqTuvKXRwLzb848G0AET2Ec6ic85=7o8Q@mail.gmail.com","threadId":"42327","inReplyTo":"20181003042437.GA27034@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-10-03T22:32:06Z","receivedAt":"2018-10-03T22:32:23Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"On Wed, 3 Oct 2018 at 00:24, Jeff King wrote:\n\n> Yeah, I really like your explanations/diagrams in the comments. It makes\n> the logic very clear.\n\nOk good, I did have the feeling that the logic became actually clearer\nto me after I wrestled with the test code, so I think this means I\ndidn't just imagine that. :)\n\n> (there's also only one caller of this\n> function, so it could be inlined; note that it's OK to use \"return\" in a\n> test_expect block).\n\nOh, I think had run into some trouble with the test runner complaining\nabout a broken &&-chain, but it seems to work fine now (perhaps I\nmissing the && somewhere else that I fixed later).\n\n> Why do we need the tag name to be different?\n\nOtherwise the 'git checkout' command complains about an ambiguous ref\n(added that to the comment).\n\n> > git checkout 1 -b merge &&\n>\n> This is assuming we just made a branch called \"1\", but that's one of the\n> arguments. Probably this should be \"$1\" (or the whole thing should just\n> be inlined so it is clear that what the set of parameters we expect is).\n\nOops, right. I've inlined it.\n\n> It might actually be worth setting up the uncolored expect file as part\n> of this, since it so neatly diagrams the graph you're trying to produce.\n>\n> I.e., something like (completely untested; note that the leading\n> indentation is all tabs, which will be removed by the \"<<-\" operator):\n\nYup, works (I again had run into some problems with &&-chaining\nearlier, but now it works fine)\n\n> > * left\n> > | *---. octopus-merge\n[...]\n>\n> Yikes. :) This one is pretty hard to read. I'm not sure if there's a\n> good alternative. If you pipe the output of test_decode through\n> this:\n>\n> sed '\n> s/./R/g;\n[...]\n> you get this:\n>\n> * left\n> R *BBMM octopus-merge\n> R RY B M\n[...]\n> which is admittedly pretty horrible, too, but at least resembles a\n> graph. I dunno.\n\nYeah, but it's lossy, so it doesn't seem usable for the test. Maybe\ndoubling up some characters?\n\n** left\nR| **B-B-M-M. octopus-merge\nR| R|Y\\ B\\ M\\\nR|R/ Y/ B/ M/\nR| Y| B| ** 4\nR| Y| ** M| 3\nR| Y| M|M/\nR| ** M| 2\nR| M|M/\n** M| 1\nM|M/\n** initial\n\n> I'm also not thrilled that we depend on the exact sequence of default\n> colors, but I suspect it's not the first time. And it wouldn't be too\n> hard to update it if that default changes.\n\nWell, it's easy enough to set the colors explicitly. After doing this\nI noticed that green seems to be skipped. Not sure if that's a bug or\nnot.\n\n> Try not to put \"git\" on the left-hand side of a pipe, since it means\n> we'll miss its exit code\n\nOk.\n\n> Leftover \"debug\" cruft?\n>\n> The same pipe comment applies as above.\n>\n> > test_done\n> > test_done\n>\n> Two dones; we exit after the first one (so everything after this is\n> ignored).\n\nOops, yeah, this script was still a bit of a rough draft.\n\n> I think it's OK to have a dedicated script for even these two tests, if\n> it makes things easier to read. However, would we also want to test the\n> octopus without the problematic graph here? I think if we just omit\n> \"left\" we get that, don't we?\n\nt4202-log.sh already does test a \"normal\" octopus merge (starting\naround line 615, search for \"octopus-a\"). But that is only a 3-parent\nmerge. And adding another test is easy enough.\n\n\nFrom cd9415b524357c2c8b9b20a63032c94e01d46a15 Mon Sep 17 00:00:00 2001\nFrom: Noam Postavsky \nDate: Sat, 1 Sep 2018 20:07:16 -0400\nSubject: [PATCH v5] log: Fix coloring of certain octupus merge shapes\n\nFor octopus merges where the first parent edge immediately merges into\nthe next column to the left:\n\n| *-.\n| |\\ \\\n|/ / /\n\nthen the number of columns should be one less than the usual case:\n\n| *-.\n| |\\ \\\n| | | *\n\nAlso refactor the code to iterate over columns rather than dashes,\nbuilding from an initial patch suggestion by Jeff King.\n\nSigned-off-by: Noam Postavsky \n---\n graph.c | 56 +++++++++++++++++-------\n t/t4214-log-graph-octopus.sh | 102 +++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 143 insertions(+), 15 deletions(-)\n create mode 100755 t/t4214-log-graph-octopus.sh\n\ndiff --git a/graph.c b/graph.c\nindex e1f6d3bdd..a3366f6da 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -842,27 +842,53 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)\n }\n \n /*\n- * Draw an octopus merge and return the number of characters written.\n+ * Draw the horizontal dashes of an octopus merge and return the number of\n+ * characters written.\n */\n static int graph_draw_octopus_merge(struct git_graph *graph,\n \t\t\t\t struct strbuf *sb)\n {\n \t/*\n-\t * Here dashless_commits represents the number of parents\n-\t * which don't need to have dashes (because their edges fit\n-\t * neatly under the commit).\n-\t */\n-\tconst int dashless_commits = 2;\n-\tint col_num, i;\n-\tint num_dashes =\n-\t\t((graph->num_parents - dashless_commits) * 2) - 1;\n-\tfor (i = 0; i < num_dashes; i++) {\n-\t\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\t\tstrbuf_write_column(sb, &graph->new_columns[col_num], '-');\n+\t * Here dashless_parents represents the number of parents which don't\n+\t * need to have dashes (the edges labeled \"0\" and \"1\"). And\n+\t * dashful_parents are the remaining ones.\n+\t *\n+\t * | *---.\n+\t * | |\\ \\ \\\n+\t * | | | | |\n+\t * x 0 1 2 3\n+\t *\n+\t */\n+\tconst int dashless_parents = 2;\n+\tint dashful_parents = graph->num_parents - dashless_parents;\n+\n+\t/*\n+\t * Usually, each parent gets its own column, like the diagram above, but\n+\t * sometimes the first parent goes into an existing column, like this:\n+\t *\n+\t * | *---.\n+\t * | |\\ \\ \\\n+\t * |/ / / /\n+\t * x 0 1 2\n+\t *\n+\t * In which case there will be more parents than the delta of columns.\n+\t */\n+\tint delta_cols = (graph->num_new_columns - graph->num_columns);\n+\tint parent_in_old_cols = graph->num_parents - delta_cols;\n+\n+\t/*\n+\t * In both cases, commit_index corresponds to the edge labeled \"0\".\n+\t */\n+\tint first_col = graph->commit_index + dashless_parents\n+\t - parent_in_old_cols;\n+\n+\tint i;\n+\tfor (i = 0; i < dashful_parents; i++) {\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col],\n+\t\t\t\t i == dashful_parents-1 ? '.' : '-');\n \t}\n-\tcol_num = (i / 2) + dashless_commits + graph->commit_index;\n-\tstrbuf_write_column(sb, &graph->new_columns[col_num], '.');\n-\treturn num_dashes + 1;\n+\treturn 2 * dashful_parents;\n }\n \n static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\ndiff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh\nnew file mode 100755\nindex 000000000..dab96c89a\n--- /dev/null\n+++ b/t/t4214-log-graph-octopus.sh\n@@ -0,0 +1,102 @@\n+#!/bin/sh\n+\n+test_description='git log --graph of skewed left octopus merge.'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'set up merge history' '\n+\tcat >expect.uncolored <<-\\EOF &&\n+\t* left\n+\t| *---. octopus-merge\n+\t| |\\ \\ \\\n+\t|/ / / /\n+\t| | | * 4\n+\t| | * | 3\n+\t| | |/\n+\t| * | 2\n+\t| |/\n+\t* | 1\n+\t|/\n+\t* initial\n+\tEOF\n+\tcat >expect.colors <<-\\EOF &&\n+\t* left\n+\t| *---. octopus-merge\n+\t| |\\ \\ \\\n+\t|/ / / /\n+\t| | | * 4\n+\t| | * | 3\n+\t| | |/\n+\t| * | 2\n+\t| |/\n+\t* | 1\n+\t|/\n+\t* initial\n+\tEOF\n+\ttest_commit initial &&\n+\tfor i in 1 2 3 4 ; do\n+\t\tgit checkout master -b $i || return $?\n+\t\t# Make tag name different from branch name, to avoid\n+\t\t# ambiguity error when calling checkout.\n+\t\ttest_commit $i $i $i tag$i || return $?\n+\tdone &&\n+\tgit checkout 1 -b merge &&\n+\ttest_tick &&\n+\tgit merge -m octopus-merge 1 2 3 4 &&\n+\tgit checkout 1 -b L &&\n+\ttest_commit left\n+'\n+\n+test_expect_success 'log --graph with tricky octopus merge with colors' '\n+\ttest_config log.graphColors red,green,yellow,blue,magenta,cyan &&\n+\tgit log --color=always --graph --date-order --pretty=tformat:%s --all >actual.colors.raw &&\n+\ttest_decode_color actual.colors &&\n+\ttest_cmp expect.colors actual.colors\n+'\n+\n+test_expect_success 'log --graph with tricky octopus merge, no color' '\n+\tgit log --color=never --graph --date-order --pretty=tformat:%s --all >actual.raw &&\n+\tsed \"s/ *\\$//\" actual.raw >actual &&\n+\ttest_cmp expect.uncolored actual\n+'\n+\n+# Repeat the previous two tests with \"normal\" octopus merge (i.e.,\n+# without the first parent skewing to the \"left\" branch column).\n+\n+test_expect_success 'log --graph with normal octopus merge, no color' '\n+\tcat >expect.uncolored <<-\\EOF &&\n+\t*---. octopus-merge\n+\t|\\ \\ \\\n+\t| | | * 4\n+\t| | * | 3\n+\t| | |/\n+\t| * | 2\n+\t| |/\n+\t* | 1\n+\t|/\n+\t* initial\n+\tEOF\n+\tgit log --color=never --graph --date-order --pretty=tformat:%s merge >actual.raw &&\n+\tsed \"s/ *\\$//\" actual.raw >actual &&\n+\ttest_cmp expect.uncolored actual\n+'\n+\n+test_expect_success 'log --graph with normal octopus merge with colors' '\n+\tcat >expect.colors <<-\\EOF &&\n+\t*---. octopus-merge\n+\t|\\ \\ \\\n+\t| | | * 4\n+\t| | * | 3\n+\t| | |/\n+\t| * | 2\n+\t| |/\n+\t* | 1\n+\t|/\n+\t* initial\n+\tEOF\n+\ttest_config log.graphColors red,green,yellow,blue,magenta,cyan &&\n+\tgit log --color=always --graph --date-order --pretty=tformat:%s merge >actual.colors.raw &&\n+\ttest_decode_color actual.colors &&\n+\ttest_cmp expect.colors actual.colors\n+'\n+test_done\n-- \n2.11.0\n\n"},{"id":"359898","messageId":"20181009045138.GA11376@sigill.intra.peff.net","threadId":"42327","inReplyTo":"CAM-tV-88J3ZAALwZeEqTuvKXRwLzb848G0AET2Ec6ic85=7o8Q@mail.gmail.com","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-09T04:51:39Z","receivedAt":"2018-10-09T04:51:43Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2018 at 06:32:06PM -0400, Noam Postavsky wrote:\n\n> > which is admittedly pretty horrible, too, but at least resembles a\n> > graph. I dunno.\n> \n> Yeah, but it's lossy, so it doesn't seem usable for the test. Maybe\n> doubling up some characters?\n> \n> ** left\n> R| **B-B-M-M. octopus-merge\n> R| R|Y\\ B\\ M\\\n> R|R/ Y/ B/ M/\n> R| Y| B| ** 4\n> R| Y| ** M| 3\n> R| Y| M|M/\n> R| ** M| 2\n> R| M|M/\n> ** M| 1\n> M|M/\n> ** initial\n\nYeah, I tried something similar, but it's hard to read as a graph since\nthe alignment is lost between lines. I agree the single-char version is\nlossy, but I think in combination with checking the literal, uncolored\nversion, we'd be OK.\n\nHowever, it may be best to just leave the original verbose version you\nhad. It's hard to read and to modify, but we don't plan for people to do\nthat very often. And it's at least simple.\n\n> > I'm also not thrilled that we depend on the exact sequence of default\n> > colors, but I suspect it's not the first time. And it wouldn't be too\n> > hard to update it if that default changes.\n> \n> Well, it's easy enough to set the colors explicitly. After doing this\n> I noticed that green seems to be skipped. Not sure if that's a bug or\n> not.\n\nHmm, yeah, that is weird. I think it's an artifact of the way we\nincrement the color selector, though, and not related to your patch (the\nsame thing happens before your fix, as well).\n\n> > I think it's OK to have a dedicated script for even these two tests, if\n> > it makes things easier to read. However, would we also want to test the\n> > octopus without the problematic graph here? I think if we just omit\n> > \"left\" we get that, don't we?\n> \n> t4202-log.sh already does test a \"normal\" octopus merge (starting\n> around line 615, search for \"octopus-a\"). But that is only a 3-parent\n> merge. And adding another test is easy enough.\n> [...]\n\nThanks, what you have here looks good.\n\n> From cd9415b524357c2c8b9b20a63032c94e01d46a15 Mon Sep 17 00:00:00 2001\n> From: Noam Postavsky \n> Date: Sat, 1 Sep 2018 20:07:16 -0400\n> Subject: [PATCH v5] log: Fix coloring of certain octupus merge shapes\n\nThis whole version looks good to me. \"git am\" is supposed to understand\nattachments, but it seems to want to apply our whole conversation as the\ncommit message.\n\nYou may want to repost one more time with this subject in the email\nsubject line to fix that and to get the maintainer's attention. Feel\nfree to add my:\n\n Reviewed-by: Jeff King \n\nafter your signoff. Thanks for sticking with this topic!\n\n-Peff\n"},{"id":"359968","messageId":"CAM-tV-97PJMGvaY_U=OmC36RXQ0KuxT1POj0ADgzeMv_8=iUxQ@mail.gmail.com","threadId":"42327","inReplyTo":"20181009045138.GA11376@sigill.intra.peff.net","subject":"Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never","fromName":"Noam Postavsky","fromEmail":"npostavs@users.sourceforge.net","sentAt":"2018-10-10T00:42:38Z","receivedAt":"2018-10-10T00:42:54Z","isPatch":false,"sender":{"key":"npostavs@users.sourceforge.net","avatar":"https://avatars.githubusercontent.com/u/287742?v=4"},"body":"> This whole version looks good to me. \"git am\" is supposed to understand\n> attachments, but it seems to want to apply our whole conversation as the\n> commit message.\n>\n> You may want to repost one more time with this subject in the email\n> subject line to fix that and to get the maintainer's attention. Feel\n> free to add my:\n>\n> Reviewed-by: Jeff King \n>\n> after your signoff.\n\nResent with git send-email. https://marc.info/?l=git&m=153913190617067&w=2\n\n> Thanks for sticking with this topic!\n\nThank you for all your patient reviewing!\n"}]}