{"thread":{"id":"48555","subject":"Weird revision walk behaviour","startedAt":"2018-05-23T17:11:02Z","lastAt":"2018-05-31T15:10:41Z","messageCount":12,"participants":["SZEDER Gábor","Jeff King","Kevin Bracey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"348379","messageId":"CAM0VKjkr71qLfksxZy59o4DYCM-x=podsCf6Qv+PzZuSe1gXZw@mail.gmail.com","threadId":"48555","inReplyTo":null,"subject":"Weird revision walk behaviour","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2018-05-23T17:10:58Z","receivedAt":"2018-05-23T17:11:02Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"There is this topic 'jt/partial-clone-proto-v2' currently cooking in\n'next' and pointing to ba95710a3b ({fetch,upload}-pack: support filter\nin protocol v2, 2018-05-03).  This topic is built on top of the merge\ncommit ea44c0a594 (Merge branch 'bw/protocol-v2' into\njt/partial-clone-proto-v2, 2018-05-02), which gives me the creeps,\nbecause it shows up in some pathspec-limited revision walks where in\nmy opinion it should not:\n\n  $ git log --oneline master..ba95710a3b -- ci/\n  ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n\nBut as far as I can tell, there are no changes in the 'ci/' directory\non any of the merge's parents:\n\n  $ git log --oneline master..ea44c0a594^1 -- ci/\n  # Nothing.\n  $ git log --oneline master..ea44c0a594^2 -- ci/\n  # Nothing!\n\nAnd to add to my confusion:\n\n  $ git log -1 --oneline master@{1.week.ago}\n  ccdcbd54c4 The fifth batch for 2.18\n  $ git log --oneline master@{1.week.ago}..ea44c0a594 -- ci/\n  ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n  $ git log -1 --oneline master@{3.week.ago}\n  1f1cddd558 The fourth batch for 2.18\n  $ git log --oneline master@{3.week.ago}..ea44c0a594 -- ci/\n  # Nothing, as it is supposed to be, IMHO.\n\nThis is not specific to the 'ci/' directory, it seems that any\nuntouched directory does the trick:\n\n  $ git log --oneline master..ea44c0a594 -- contrib/coccinelle/ t/lib-httpd/\n  ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n  $ git log --oneline master..ea44c0a594^1 -- contrib/coccinelle/ t/lib-httpd/\n  # Nothing.\n  $ git log --oneline master..ea44c0a594^2 -- contrib/coccinelle/ t/lib-httpd/\n  # Nothing.\n  $ git log --oneline master@{3.week.ago}..ea44c0a594 --\ncontrib/coccinelle/ t/lib-httpd/\n  # Nothing, but this is what I would expect.\n\nI get the same behavior with Git built from current master and from\npast releases as well (tried it as far back as v2.0.0).\n\nSo...  what's going on here? :)\nA bug?  Or am I missing something?  Some history simplification corner\ncase that I'm unaware of?\n"},{"id":"348380","messageId":"20180523173246.GA10299@sigill.intra.peff.net","threadId":"48555","inReplyTo":"CAM0VKjkr71qLfksxZy59o4DYCM-x=podsCf6Qv+PzZuSe1gXZw@mail.gmail.com","subject":"Re: Weird revision walk behaviour","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-23T17:32:46Z","receivedAt":"2018-05-23T17:32:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 23, 2018 at 07:10:58PM +0200, SZEDER Gábor wrote:\n\n>   $ git log --oneline master..ba95710a3b -- ci/\n>   ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n> \n> But as far as I can tell, there are no changes in the 'ci/' directory\n> on any of the merge's parents:\n> \n>   $ git log --oneline master..ea44c0a594^1 -- ci/\n>   # Nothing.\n>   $ git log --oneline master..ea44c0a594^2 -- ci/\n>   # Nothing!\n\nHmm. That commit does touch \"ci/\" with respect to one of its parents.\nIt should get simplified away because it completely matches the other\nparent, so it does sound like a bug.\n\n> This is not specific to the 'ci/' directory, it seems that any\n> untouched directory does the trick:\n> \n>   $ git log --oneline master..ea44c0a594 -- contrib/coccinelle/ t/lib-httpd/\n>   ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n\nBoth of those directories also differ between one parent. If you try it\nwith \"contrib/remote-helpers\", which does not, then the commit does not\nappear.\n\nSo it does seem like a bug where we should be simplifying away the merge\nbut are not (or I'm missing the corner case, too ;) ).\n\n> I get the same behavior with Git built from current master and from\n> past releases as well (tried it as far back as v2.0.0).\n\nI keep some older builds around, and it does not reproduce with v1.6.6.3\n(that's my usual goto for \"old\"). Bisecting turns up d0af663e42\n(revision.c: Make --full-history consider more merges, 2013-05-16).  It\nlooks like an unintended change (the commit message claims that the\nnon-full-history case shouldn't be affected).\n\n-Peff\n"},{"id":"348381","messageId":"20180523173523.GB10299@sigill.intra.peff.net","threadId":"48555","inReplyTo":"20180523173246.GA10299@sigill.intra.peff.net","subject":"Re: Weird revision walk behaviour","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-23T17:35:23Z","receivedAt":"2018-05-23T17:35:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 23, 2018 at 01:32:46PM -0400, Jeff King wrote:\n\n> On Wed, May 23, 2018 at 07:10:58PM +0200, SZEDER Gábor wrote:\n> \n> >   $ git log --oneline master..ba95710a3b -- ci/\n> >   ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n> > \n> > But as far as I can tell, there are no changes in the 'ci/' directory\n> > on any of the merge's parents:\n> > \n> >   $ git log --oneline master..ea44c0a594^1 -- ci/\n> >   # Nothing.\n> >   $ git log --oneline master..ea44c0a594^2 -- ci/\n> >   # Nothing!\n> \n> Hmm. That commit does touch \"ci/\" with respect to one of its parents.\n> It should get simplified away because it completely matches the other\n> parent, so it does sound like a bug.\n> \n> > This is not specific to the 'ci/' directory, it seems that any\n> > untouched directory does the trick:\n> > \n> >   $ git log --oneline master..ea44c0a594 -- contrib/coccinelle/ t/lib-httpd/\n> >   ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n> \n> Both of those directories also differ between one parent. If you try it\n> with \"contrib/remote-helpers\", which does not, then the commit does not\n> appear.\n> \n> So it does seem like a bug where we should be simplifying away the merge\n> but are not (or I'm missing the corner case, too ;) ).\n> \n> > I get the same behavior with Git built from current master and from\n> > past releases as well (tried it as far back as v2.0.0).\n> \n> I keep some older builds around, and it does not reproduce with v1.6.6.3\n> (that's my usual goto for \"old\"). Bisecting turns up d0af663e42\n> (revision.c: Make --full-history consider more merges, 2013-05-16).  It\n> looks like an unintended change (the commit message claims that the\n> non-full-history case shouldn't be affected).\n\nThere's more discussion in the thread at:\n\n  https://public-inbox.org/git/1366658602-12254-1-git-send-email-kevin@bracey.fi/\n\nI haven't absorbed it all yet, but I'm adding Junio to the cc.\n\n-Peff\n"},{"id":"348471","messageId":"88f96a35-6368-de24-60ed-ad015f16f127@bracey.fi","threadId":"48555","inReplyTo":"20180523173523.GB10299@sigill.intra.peff.net","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-24T18:54:37Z","receivedAt":"2018-05-24T19:32:34Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 23/05/2018 20:35, Jeff King wrote:\n> There's more discussion in the thread at:\n>\n>    https://public-inbox.org/git/1366658602-12254-1-git-send-email-kevin@bracey.fi/\n>\n> I haven't absorbed it all yet, but I'm adding Junio to the cc.\n\nJust to ack that I've seen the discussion, but I can't identify the \ncode's reasoning at the moment. My recollection is that I accepted while \ncoming up with the algorithm that it might err slightly on the side of \nfalse positives in the display - there were some merge cases I was \nunable to fully distinguish whether or not the merge had lost a change \nit shouldn't have done, and if I was uncertain I'd rather show it than not.\n\nThe first commit was not originally intended to alter behaviour for \nanything other than --full-history, but later in the chain there was \nspecific consideration into tracking the path to the specified \"bottom\" \ncommit. It may be that's part of what's happening here.\n\nKevin\n\n\n\n\n"},{"id":"348490","messageId":"869a4045-0527-3dcf-33b3-90de2a45cd51@bracey.fi","threadId":"48555","inReplyTo":"20180523173523.GB10299@sigill.intra.peff.net","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-24T20:26:24Z","receivedAt":"2018-05-24T21:06:14Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 23/05/2018 20:35, Jeff King wrote:\n> On Wed, May 23, 2018 at 01:32:46PM -0400, Jeff King wrote:\n>\n>> On Wed, May 23, 2018 at 07:10:58PM +0200, SZEDER Gábor wrote:\n>>\n>>>    $ git log --oneline master..ba95710a3b -- ci/\n>>>    ea44c0a594 Merge branch 'bw/protocol-v2' into jt/partial-clone-proto-v2\n>>>\n>>>\n>>> I keep some older builds around, and it does not reproduce with v1.6.6.3\n>>> (that's my usual goto for \"old\"). Bisecting turns up d0af663e42\n>>> (revision.c: Make --full-history consider more merges, 2013-05-16).  It\n>>> looks like an unintended change (the commit message claims that the\n>>> non-full-history case shouldn't be affected).\n> There's more discussion in the thread at:\n>\n>    https://public-inbox.org/git/1366658602-12254-1-git-send-email-kevin@bracey.fi/\n>\n> I haven't absorbed it all yet, but I'm adding Junio to the cc.\n>\n\nIn this case, we're hitting a merge commit which is not on master, but \nit has two parents which both are. Which, IIRC, means the merge commit \nis INTERESTING with two UNINTERESTING parents; and we are TREESAME to \nonly one of them.\n\nThe commit changing the logic of TREESAME you identified believes that \nthose TREESAME changes for merges which were intended to improve fuller \nhistory modes shouldn't affect the simple history \"because partially \nTREESAME merges are turned into normal commits\". Clearly that didn't \nhappen here.\n\nI think we need to look at why that isn't happening, and if it can be \nmade to happen. The problem is that this commit is effectively the base \nof the graph - it's got a double-connection to the UNINTERESTING set, \nand maybe that prevented the simple history \"follow 1 TREESAME\" logic \nfrom kicking in. Maybe it won't follow 1 TREESAME to UNINTERESTING.\n\nI know there were quite a few changes later in the series to try to \nreconcile the simple and full history, for the cases where the simple \nhistory takes a weird path because of its love of TREESAME parents, \nhiding evil merges. But I believe the simple history behaviour was \nsupposed to remain as-is - take first TREESAME always.\n\nKevin\n\n\n"},{"id":"348636","messageId":"cb1d7c86-a989-300a-01d2-923e9c29e834@bracey.fi","threadId":"48555","inReplyTo":"869a4045-0527-3dcf-33b3-90de2a45cd51@bracey.fi","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-27T17:37:00Z","receivedAt":"2018-05-27T17:54:30Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 24/05/2018 23:26, Kevin Bracey wrote:\n>\n>>> On Wed, May 23, 2018 at 07:10:58PM +0200, SZEDER Gábor wrote:\n>>>\n>>>>    $ git log --oneline master..ba95710a3b -- ci/\n>>>>    ea44c0a594 Merge branch 'bw/protocol-v2' into \n>>>> jt/partial-clone-proto-v2\n>>>>\n> In this case, we're hitting a merge commit which is not on master, but \n> it has two parents which both are. Which, IIRC, means the merge commit \n> is INTERESTING with two UNINTERESTING parents; and we are TREESAME to \n> only one of them.\n>\n> The commit changing the logic of TREESAME you identified believes that \n> those TREESAME changes for merges which were intended to improve \n> fuller history modes shouldn't affect the simple history \"because \n> partially TREESAME merges are turned into normal commits\". Clearly \n> that didn't happen here.\n>\nHaven't currently got a development environment set up here, but I've \nbeen looking at the code.Here's a proposal, untested, as a potential \nstarting point if anyone wants to consider a proper patch.\n\nThe simplify_history first-scan logic never actually turned merges into \nsimple commits unless they were TREESAME to a relevant/interesting \nparent.  Anything where the TREESAME parent was UNINTERESTING was \nretained as a merge, but had its TREESAME flag set, and that permitted \nlater simplification.\n\nWith the redefinition of the TREESAME flag, this merge commit is no \nlonger TREESAME, and as the decoration logic to refine TREESAME isn't \nactive for simplify_history, it doesn't get cleaned up (even if it would \nbe in full history?)\n\nI think the answer may be to add an extra post-process step on the \ninitial loop to handle this special case. Something like:\n\n         case REV_TREE_SAME:\n             if (!revs->simplify_history || !relevant_commit(p)) {\n                 /* Even if a merge with an uninteresting\n                  * side branch brought the entire change\n                  * we are interested in, we do not want\n                  * to lose the other branches of this\n                  * merge, so we just keep going.\n                  */\n                 if (ts)\n                     ts->treesame[nth_parent] = 1;\n+               /* But we note it for potential later simplification */\n+               if (!treesame_parent)\n+                    treesame_parent = p;\n                 continue;\n              }\n\n...\n\nAfter loop:\n\n+     if (relevant_parents == 0 && revs->simplify_history && \ntreesame_parent) {\n+           treesame_parent->next = NULL;// Repeats code from loop - \nshare somehow?\n+           commit->parents = treesame_parent;\n+           commit->object.flags |= TREESAME;\n+           return;\n+    }\n\n      /*\n       * TREESAME is straightforward for single-parent commits. For merge\n\nThe other option would be to take off the \" || !relevant_commit(p)\" \ntest, but I'm assuming that is still needed for other cases.\n\nKevin\n\n\n"},{"id":"348686","messageId":"20180528220651.20287-1-szeder.dev@gmail.com","threadId":"48555","inReplyTo":"cb1d7c86-a989-300a-01d2-923e9c29e834@bracey.fi","subject":"Re: Weird revision walk behaviour","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2018-05-28T22:06:51Z","receivedAt":"2018-05-28T22:07:11Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"\n> On 24/05/2018 23:26, Kevin Bracey wrote:\n> >\n> >>> On Wed, May 23, 2018 at 07:10:58PM +0200, SZEDER Gábor wrote:\n> >>>\n> >>>>    $ git log --oneline master..ba95710a3b -- ci/\n> >>>>    ea44c0a594 Merge branch 'bw/protocol-v2' into \n> >>>> jt/partial-clone-proto-v2\n> >>>>\n> > In this case, we're hitting a merge commit which is not on master, but \n> > it has two parents which both are.\n\nIndeed, I didn't notice this important detail amidst the complexity of\nthe git history.  Thanks, with this info I could come up with a small\ntest case to demonstrate the issue, see below.\n\n> Which, IIRC, means the merge commit \n> > is INTERESTING with two UNINTERESTING parents; and we are TREESAME to \n> > only one of them.\n> >\n> > The commit changing the logic of TREESAME you identified believes that \n> > those TREESAME changes for merges which were intended to improve \n> > fuller history modes shouldn't affect the simple history \"because \n> > partially TREESAME merges are turned into normal commits\". Clearly \n> > that didn't happen here.\n> >\n> Haven't currently got a development environment set up here, but I've \n> been looking at the code.Here's a proposal, untested, as a potential \n> starting point if anyone wants to consider a proper patch.\n> \n> The simplify_history first-scan logic never actually turned merges into \n> simple commits unless they were TREESAME to a relevant/interesting \n> parent.  Anything where the TREESAME parent was UNINTERESTING was \n> retained as a merge, but had its TREESAME flag set, and that permitted \n> later simplification.\n> \n> With the redefinition of the TREESAME flag, this merge commit is no \n> longer TREESAME, and as the decoration logic to refine TREESAME isn't \n> active for simplify_history, it doesn't get cleaned up (even if it would \n> be in full history?)\n> \n> I think the answer may be to add an extra post-process step on the \n> initial loop to handle this special case. Something like:\n> \n>          case REV_TREE_SAME:\n>              if (!revs->simplify_history || !relevant_commit(p)) {\n>                  /* Even if a merge with an uninteresting\n>                   * side branch brought the entire change\n>                   * we are interested in, we do not want\n>                   * to lose the other branches of this\n>                   * merge, so we just keep going.\n>                   */\n>                  if (ts)\n>                      ts->treesame[nth_parent] = 1;\n> +               /* But we note it for potential later simplification */\n> +               if (!treesame_parent)\n> +                    treesame_parent = p;\n>                  continue;\n>               }\n> \n> ...\n> \n> After loop:\n> \n> +     if (relevant_parents == 0 && revs->simplify_history && \n> treesame_parent) {\n> +           treesame_parent->next = NULL;// Repeats code from loop - \n> share somehow?\n> +           commit->parents = treesame_parent;\n> +           commit->object.flags |= TREESAME;\n> +           return;\n> +    }\n> \n>       /*\n>        * TREESAME is straightforward for single-parent commits. For merge\n\nSo, without investing nearly enough time to understand what is going\non, I massaged the above diffs into this:\n\n  ---  >8 ---\n\ndiff --git a/revision.c b/revision.c\nindex 4e0e193e57..0ddd2c1e8a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -605,7 +605,7 @@ static inline int limiting_can_increase_treesame(const struct rev_info *revs)\n \n static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n {\n-\tstruct commit_list **pp, *parent;\n+\tstruct commit_list **pp, *parent, *treesame_parents = NULL;\n \tstruct treesame_state *ts = NULL;\n \tint relevant_change = 0, irrelevant_change = 0;\n \tint relevant_parents, nth_parent;\n@@ -672,6 +672,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tswitch (rev_compare_tree(revs, p, commit)) {\n \t\tcase REV_TREE_SAME:\n \t\t\tif (!revs->simplify_history || !relevant_commit(p)) {\n+\t\t\t\tstruct commit_list *tp;\n \t\t\t\t/* Even if a merge with an uninteresting\n \t\t\t\t * side branch brought the entire change\n \t\t\t\t * we are interested in, we do not want\n@@ -680,6 +681,13 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t\t */\n \t\t\t\tif (ts)\n \t\t\t\t\tts->treesame[nth_parent] = 1;\n+\t\t\t\t/* But we note it for potential later\n+\t\t\t\t * simplification\n+\t\t\t\t */\n+\t\t\t\ttp = treesame_parents;\n+\t\t\t\ttreesame_parents = xmalloc(sizeof(*treesame_parents));\n+\t\t\t\ttreesame_parents->item = p;\n+\t\t\t\ttreesame_parents->next = tp;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tparent->next = NULL;\n@@ -716,6 +724,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tdie(\"bad tree compare for commit %s\", oid_to_hex(&commit->object.oid));\n \t}\n \n+\tif (relevant_parents == 0 && revs->simplify_history &&\n+\t    treesame_parents) {\n+\t\tcommit->parents = treesame_parents;\n+\t\tcommit->object.flags |= TREESAME;\n+\t\treturn;\n+\t} else\n+\t\tfree_commit_list(treesame_parents);\n+\n \t/*\n \t * TREESAME is straightforward for single-parent commits. For merge\n \t * commits, it is most useful to define it so that \"irrelevant\"\n\n  ---  >8 ---\n\nFWIW, the test suite passes with the above patch applied.\n\nAnd here is the small PoC test case to illustrate the issue, which\nfails without but succeeds with the above patch.  Eventually it should\nbe part of 't6012-rev-list-simplify.sh', of course, but I haven't\nlooked into that yet.\n\n\n  ---  >8 ---\n\ndiff --git a/t/t9999-weird-revision-walk-behaviour.sh b/t/t9999-weird-revision-walk-behaviour.sh\nnew file mode 100755\nindex 0000000000..22820f845b\n--- /dev/null\n+++ b/t/t9999-weird-revision-walk-behaviour.sh\n@@ -0,0 +1,38 @@\n+#!/bin/sh\n+\n+test_description='PoC weird revision walk behaviour test'\n+\n+. ./test-lib.sh\n+\n+# Create the following history, i.e. where both parents of merge 'M1'\n+# are in 'master':\n+#\n+#   B---M2   master\n+#  / \\ /\n+# A   X\n+#  \\ / \\\n+#   C---M1   b2\n+#\n+# and modify 'file' in commits 'A' and 'B', so one of 'M1's parents\n+# ('B') is TREESAME wrt. 'file'.\n+test_expect_success 'setup' '\n+\ttest_commit initial file &&\t# A\n+\ttest_commit modified file &&\t# B\n+\tgit checkout -b b1 master^ &&\n+\ttest_commit other-file &&\t# C\n+\tgit checkout -b b2 master &&\n+\tgit merge --no-ff b1 &&\t\t# M1\n+\tgit checkout master &&\n+\tgit merge --no-ff b1\t\t# M2\n+'\n+\n+test_expect_success 'debug' '\n+\tgit log --oneline --graph --all\n+'\n+\n+test_expect_success \"\\\"Merge branch 'b1' into b2\\\" should not be shown\" '\n+\tgit log master..b2 -- file >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_done\n\n\n"},{"id":"348693","messageId":"7de5c4b3-800c-960d-2942-7aa562df8879@bracey.fi","threadId":"48555","inReplyTo":"20180528220651.20287-1-szeder.dev@gmail.com","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-29T06:11:44Z","receivedAt":"2018-05-29T08:41:01Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 29/05/2018 01:06, SZEDER Gábor wrote:\n>\n> So, without investing nearly enough time to understand what is going\n> on, I massaged the above diffs into this:\nCool.\n\n> +\t\t\t\ttreesame_parents = xmalloc(sizeof(*treesame_parents));\nThere's no need to actually record a list here. This is just for the \nsimple history. We are only interested into becoming a non-merge to 1 \ntreesame parent, so I think we just need to record a pointer to the \nfirst one we see, just as this would exit immediately for the first \nrelevant one. For the full-history case, we already have the full \"which \nparents are treesame\" recording mechanism just above, but it only kicks \nin for merge commits and only when settings require it. Adding a malloc \nhere would be significant machinery overhead.\n> FWIW, the test suite passes with the above patch applied.\nI doubt there's an existing case like this anywhere in the revision test \nsuite :) . And this patch is focused enough that it *should* only be \nchanging the behaviour of this very specific case. As such, it does feel \na little like a kludge, but I think it's fine because it's aligning the \nsimple-history analysis with the \"analyse relevant parents if any, else \nanalyse irrelevant\" rule of the full-history.\n>\n> And here is the small PoC test case to illustrate the issue, which\n> fails without but succeeds with the above patch.  Eventually it should\n> be part of 't6012-rev-list-simplify.sh', of course, but I haven't\n> looked into that yet.\nIt may be there's enough criss-crossy history to test here to merit \nbreaking out into a second test series.\n\n+#   B---M2   master\n+#  / \\ /\n+# A   X\n+#  \\ / \\\n+#   C---M1   b2\n+#\n+# and modify 'file' in commits 'A' and 'B', so one of 'M1's parents\n+# ('B') is TREESAME wrt. 'file'.\n\nI guess we'll be wanting test cases for A..B2, B..B2 and C..B2, and some \nwhere the the base is \"some other child of B or C\".  \"B..B2\" is no \nlonger a pure set subtraction for simplification as B is UNINTERESTING \n(ie not in the set) but RELEVANT (because you named it as a bottom \ncommit), so B..B2 actually still leaves M1 with 2 relevant parents. \nYou'd want test cases covering B relevant+C irrelevant and B \nirrelevant+C relevant, which means subtracting them without naming them \n- so name a child of one.\n\nAnd then we need to think about whether we want it displayed in each of \nthe other modes for each of those queries...\n\nKevin\n\n"},{"id":"348721","messageId":"20180529210434.GA3857@sigill.intra.peff.net","threadId":"48555","inReplyTo":"20180528220651.20287-1-szeder.dev@gmail.com","subject":"Re: Weird revision walk behaviour","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-29T21:04:35Z","receivedAt":"2018-05-29T21:04:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 29, 2018 at 12:06:51AM +0200, SZEDER Gábor wrote:\n\n> diff --git a/revision.c b/revision.c\n> index 4e0e193e57..0ddd2c1e8a 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -605,7 +605,7 @@ static inline int limiting_can_increase_treesame(const struct rev_info *revs)\n>  \n>  static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n>  {\n> -\tstruct commit_list **pp, *parent;\n> +\tstruct commit_list **pp, *parent, *treesame_parents = NULL;\n>  \tstruct treesame_state *ts = NULL;\n>  \tint relevant_change = 0, irrelevant_change = 0;\n>  \tint relevant_parents, nth_parent;\n> @@ -672,6 +672,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n>  \t\tswitch (rev_compare_tree(revs, p, commit)) {\n>  \t\tcase REV_TREE_SAME:\n>  \t\t\tif (!revs->simplify_history || !relevant_commit(p)) {\n> +\t\t\t\tstruct commit_list *tp;\n>  \t\t\t\t/* Even if a merge with an uninteresting\n>  \t\t\t\t * side branch brought the entire change\n>  \t\t\t\t * we are interested in, we do not want\n> @@ -680,6 +681,13 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n>  \t\t\t\t */\n>  \t\t\t\tif (ts)\n>  \t\t\t\t\tts->treesame[nth_parent] = 1;\n> +\t\t\t\t/* But we note it for potential later\n> +\t\t\t\t * simplification\n> +\t\t\t\t */\n> +\t\t\t\ttp = treesame_parents;\n> +\t\t\t\ttreesame_parents = xmalloc(sizeof(*treesame_parents));\n> +\t\t\t\ttreesame_parents->item = p;\n> +\t\t\t\ttreesame_parents->next = tp;\n>  \t\t\t\tcontinue;\n>  \t\t\t}\n\nWe hit this \"if\" if !relevant_commit(p), which I think is what we want.\nBut we'd also hit it if !revs->simplify_history. Would we want to avoid\ndoing the simplification in that case?\n\nI guess later we do:\n\n> @@ -716,6 +724,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n>  \t\tdie(\"bad tree compare for commit %s\", oid_to_hex(&commit->object.oid));\n>  \t}\n>  \n> +\tif (relevant_parents == 0 && revs->simplify_history &&\n> +\t    treesame_parents) {\n> +\t\tcommit->parents = treesame_parents;\n> +\t\tcommit->object.flags |= TREESAME;\n> +\t\treturn;\n> +\t} else\n> +\t\tfree_commit_list(treesame_parents);\n> +\n\n...which blocks the !simplify_history case from triggering. But then we\ncould avoid the allocation above in that case, I think (though I agree\nwith Kevin's later email that we may not need it at all).\n\nDo we even need to do the parent rewriting here? By definition those\nparents aren't interesting, and we're TREESAME to whatever is in\ntreesame_parents. So conceptually it seems like we just need a flag \"I\nfound a treesame parent\", but we only convert that into a TREESAME flag\nif there are no relevant parents.\n\nI wouldn't be surprised, though, if some code path really cares whether\nwe've simplified to a single uninteresting parent here, versus\nsimplifying to a root commit (I admit that the simplification code is\none of the areas of Git I'm least familiar with).\n\n-Peff\n"},{"id":"348793","messageId":"97644280-2187-d314-37ce-2c79935a63bc@bracey.fi","threadId":"48555","inReplyTo":"20180529210434.GA3857@sigill.intra.peff.net","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-30T08:20:40Z","receivedAt":"2018-05-30T08:40:37Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 30/05/2018 00:04, Jeff King wrote:\n>\n> Do we even need to do the parent rewriting here? By definition those\n> parents aren't interesting, and we're TREESAME to whatever is in\n> treesame_parents. So conceptually it seems like we just need a flag \"I\n> found a treesame parent\", but we only convert that into a TREESAME flag\n> if there are no relevant parents.\n\nI think it's necessary to make the rules consistent. To mark the commit \nas TREESAME here when it's not TREESAME to all its parents would be \ninconsistent with the definition of the TREESAME flag used everywhere else:\n\n* Original definition: \"A commit is TREESAME if it is treesame to any \nparent\"\n* d0af66 definition: \"A commit is TREESAME if it is treesame to all parents\"\n* Current 4d8266 definition: \"A commit is TREESAME if it is treesame to \nall relevant parents; if no relevant parents then if it is treesame to \nall (irrelevant) parents.\"\n\nThe current problem is that the node is not marked TREESAME, but that's \nconsistent with the definition. I think we do have to rewrite the commit \nso it is TREESAME as per the definition. Not flag it as TREESAME in \nviolation of it.\n\nIt's possible you *could* get away with just flagging, because we never \nrecompute the TREESAME flag in simple history mode. But it would be a \ncheat, and it may have other side effects. It means this node would \nremain a special rare case for others to trip up on later.  And I don't \nthink it simplifies the scan. Remembering \n\"pointer-to-first-treesame-parent\" (not a list) for the rewrite is no \nmore complex than remembering \"bool-there-was-a-treesame-parent\".  (A \nbool is what earlier code did - it worked for the original TREESAME \ndefinition. My patch series dropped that bool without replacement - \nmissing this all-irrelevant case).\n\nIn the simple history mode, the assumption is we're \"simplifying away \nmerges up-front\" here; we won't (and can't) rewrite parents later in a \nway that needs to recompute TREESAME. In the initial scan when all \nparents are relevant and we matched one, the commit became TREESAME as \nper the new definition immediately because of the rewrite.  This applies \nthe equivalent rewrite when no relevant parents, consistent with the \ngeneral concept, and without changing the TREESAME definition.\n\nKevin\n\n\n"},{"id":"348868","messageId":"20180531054355.GA17344@sigill.intra.peff.net","threadId":"48555","inReplyTo":"97644280-2187-d314-37ce-2c79935a63bc@bracey.fi","subject":"Re: Weird revision walk behaviour","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-31T05:43:55Z","receivedAt":"2018-05-31T05:44:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 30, 2018 at 11:20:40AM +0300, Kevin Bracey wrote:\n\n> On 30/05/2018 00:04, Jeff King wrote:\n> > \n> > Do we even need to do the parent rewriting here? By definition those\n> > parents aren't interesting, and we're TREESAME to whatever is in\n> > treesame_parents. So conceptually it seems like we just need a flag \"I\n> > found a treesame parent\", but we only convert that into a TREESAME flag\n> > if there are no relevant parents.\n> \n> I think it's necessary to make the rules consistent. To mark the commit as\n> TREESAME here when it's not TREESAME to all its parents would be\n> inconsistent with the definition of the TREESAME flag used everywhere else:\n> \n> * Original definition: \"A commit is TREESAME if it is treesame to any\n> parent\"\n> * d0af66 definition: \"A commit is TREESAME if it is treesame to all parents\"\n> * Current 4d8266 definition: \"A commit is TREESAME if it is treesame to all\n> relevant parents; if no relevant parents then if it is treesame to all\n> (irrelevant) parents.\"\n> \n> The current problem is that the node is not marked TREESAME, but that's\n> consistent with the definition. I think we do have to rewrite the commit so\n> it is TREESAME as per the definition. Not flag it as TREESAME in violation\n> of it.\n\nIf there are zero parents (neither relevant nor irrelevant), is it still\nTREESAME? I would say in theory yes. So what I was proposing would be to\nrewrite the parents to the empty set.\n\nBut anyway, I agree with you that the first-treesame-parent strategy is\nnot any more complex than the boolean, and is probably less likely to\ncause unintended headaches later on.\n\nWhat next here? It looks like we have a proposed solution. Do you want\nto try to work up a set of tests based on what you wrote earlier?\n\nI'd also love to hear from Junio as the expert in this area, but I think\nhe's been a bit busy with maintainer stuff recently. So maybe I should\njust be patient. :)\n\n-Peff\n"},{"id":"348898","messageId":"28359a94-e584-a963-428d-2cf11f2cb895@bracey.fi","threadId":"48555","inReplyTo":"20180531054355.GA17344@sigill.intra.peff.net","subject":"Re: Weird revision walk behaviour","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2018-05-31T14:54:07Z","receivedAt":"2018-05-31T15:10:41Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 31/05/2018 08:43, Jeff King wrote:\n>\n> If there are zero parents (neither relevant nor irrelevant), is it still\n> TREESAME? I would say in theory yes.\n\nNot sure - I think roots are such a special case that TREESAME \neffectively doesn't matter. We always test for roots first.\n>   So what I was proposing would be to\n> rewrite the parents to the empty set.\nThat feels a bit radical - I believe we need to retain (some) parent \ninformation for modes that show it (eg the dangling unfilled circles in \ngitk). And making it a root I think could cause other problems with \nmaking it look like we have a disjoint history. I believe the next \nsimplification step may be trying to follow down to the common root.\n> What next here? It looks like we have a proposed solution. Do you want\n> to try to work up a set of tests based on what you wrote earlier?\nI was hoping Gábor would carry on, as he's made a start... I was just \nplanning to back-seat drive.\n> I'd also love to hear from Junio as the expert in this area, but I think\n> he's been a bit busy with maintainer stuff recently. So maybe I should\n> just be patient. :)\n>\nLikewise - I have been quite deep into this, but it was a quite short \nwindow of investigation a long time ago, and I've not looked at it \nsince. Would like input from someone with more active knowledge.\n\nKevin\n\n"}]}