{"thread":{"id":"47298","subject":"Bisect marking new commits incorrectly","startedAt":"2017-11-22T14:39:11Z","lastAt":"2017-11-24T05:29:20Z","messageCount":5,"participants":["Adam Dinwoodie","Christian Couder","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"333277","messageId":"20171122143902.GO20681@dinwoodie.org","threadId":"47298","inReplyTo":null,"subject":"Bisect marking new commits incorrectly","fromName":"Adam Dinwoodie","fromEmail":"adam@dinwoodie.org","sentAt":"2017-11-22T14:39:02Z","receivedAt":"2017-11-22T14:39:11Z","isPatch":false,"sender":{"key":"adam@dinwoodie.org","avatar":"https://avatars.githubusercontent.com/u/1397507?v=4"},"body":"In trying to do a bisect on the Git repository, I seem to have come\nacross surprising behavior where the order in which `git bisect` appears\nto forget that previous commits were marked as new.\n\nYou can see this behaviour in the following commands, run on the Git\nrepository, where the order of the `git bisect new` commands affects the\nresults.\n\nCase 1:\n\n    $ git bisect start; git bisect old v2.15.0\n\n    $ git bisect new 95a731ce\n    Bisecting: 40 revisions left to test after this (roughly 5 steps)\n    [934e330c9d0d12f7a0dd82b9699456c891e4dd4a] Merge branch 'ad/5580-unc-tests-on-cygwin' into maint\n\n    $ git bisect new 14c63a9d\n    Bisecting: 153 revisions left to test after this (roughly 7 steps)\n    [421f21c98f8b515412ca683ae3743013a8b3bda2] Merge branch 'js/mingw-redirect-std-handles'\n\n    $ for h in 95a731ce 14c63a9d; do git log -1 --format=oneline --decorate \"$h\"; done\n    95a731ce92c7576d927f0d8a9b27c206cb58c2e6 (origin/maint) Almost ready for 2.15.1\n    14c63a9dc093d6738454f6369a4f5663ca732cf7 (origin/master, origin/HEAD, refs/bisect/new) Sync with maint\n\nCase 2:\n\n    $ git bisect start; git bisect old v2.15.0\n\n    $ git bisect new 14c63a9d\n    Bisecting: 153 revisions left to test after this (roughly 7 steps)\n    [421f21c98f8b515412ca683ae3743013a8b3bda2] Merge branch 'js/mingw-redirect-std-handles'\n\n    $ git bisect new 95a731ce\n    Bisecting: 40 revisions left to test after this (roughly 5 steps)\n    [934e330c9d0d12f7a0dd82b9699456c891e4dd4a] Merge branch 'ad/5580-unc-tests-on-cygwin' into maint\n\n    $ for h in 95a731ce 14c63a9d; do git log -1 --format=oneline --decorate \"$h\"; done\n    95a731ce92c7576d927f0d8a9b27c206cb58c2e6 (origin/maint, refs/bisect/new) Almost ready for 2.15.1\n    14c63a9dc093d6738454f6369a4f5663ca732cf7 (origin/master, origin/HEAD) Sync with maint\n\nAs you can see, in both cases, only the most recent \"new\" command\nappears to have any effect.  I'd have expected that both commits would\nhave been marked as \"new\", and the bisect run would use both facts to\nwork out which commit is the target of the bisection.\n\nThis is using v2.15.0.  It's possibly relevant that 95a731ce is a\ndirect parent of 14c63a9d.\n\nIs this a bug, or intentional behaviour?  Am I missing something that\nmeans it's actually sensible to have Git silently discard some bisect\ncommands in this sort of circumstance?\n"},{"id":"333288","messageId":"CAP8UFD35-z9qA_m28EbpvN-X_HVcDvEirn69DJNESikJ=Txg7g@mail.gmail.com","threadId":"47298","inReplyTo":"20171122143902.GO20681@dinwoodie.org","subject":"Re: Bisect marking new commits incorrectly","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2017-11-22T16:21:29Z","receivedAt":"2017-11-22T16:21:36Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Wed, Nov 22, 2017 at 3:39 PM, Adam Dinwoodie <adam@dinwoodie.org> wrote:\n> In trying to do a bisect on the Git repository, I seem to have come\n> across surprising behavior where the order in which `git bisect` appears\n> to forget that previous commits were marked as new.\n\nYeah, the algorithm uses many \"old\" commits and only one \"new\" commit.\n\n[...]\n\n> As you can see, in both cases, only the most recent \"new\" command\n> appears to have any effect.  I'd have expected that both commits would\n> have been marked as \"new\", and the bisect run would use both facts to\n> work out which commit is the target of the bisection.\n\nI didn't look at your test case, but the algorithm to find another\ncommit to test is described here:\n\nhttps://git-scm.com/docs/git-bisect-lk2009.html#_bisection_algorithm\n\nand you can see that the first rule of the algorithm is to keep only\nthe commits that are ancestors of the \"new\" commit (including the\n\"new\" commit itself).\n\nThe reason for this rule is that other commits cannot have introduced\nthe behavior we are looking for. The result of this rule is that git\nbisect will always ask you to test a commit that is an ancestor of the\n\"new\" commit.\n\nSo if you test a commit that git bisect asks you to test, and it\nappears that this commit is \"new\", then you can just discard the\nprevious \"new\" commit because it will give you less information than\nthe new \"new\" one.\n(The old \"new\" will not let you discard any commits that the new \"new\"\ncommit allows you to discard, because it is a descendant of the new\n\"new\" commit.)\n\nIf you don't test the commit that git bisect asks you to test, then\ngit bisect assumes that you know better and discards the old \"new\".\n\n> This is using v2.15.0.  It's possibly relevant that 95a731ce is a\n> direct parent of 14c63a9d.\n>\n> Is this a bug, or intentional behaviour?  Am I missing something that\n> means it's actually sensible to have Git silently discard some bisect\n> commands in this sort of circumstance?\n\nWell, instead of silently discarding a the old \"new\" commit when the\nnew \"new\" commit is not an ancestor of it, git bisect could perhaps\nwarn or ask you to confirm that you know what you are doing.\n"},{"id":"333297","messageId":"20171122170129.GS20681@dinwoodie.org","threadId":"47298","inReplyTo":"CAP8UFD35-z9qA_m28EbpvN-X_HVcDvEirn69DJNESikJ=Txg7g@mail.gmail.com","subject":"Re: Bisect marking new commits incorrectly","fromName":"Adam Dinwoodie","fromEmail":"adam@dinwoodie.org","sentAt":"2017-11-22T17:01:29Z","receivedAt":"2017-11-22T17:01:36Z","isPatch":false,"sender":{"key":"adam@dinwoodie.org","avatar":"https://avatars.githubusercontent.com/u/1397507?v=4"},"body":"On Wednesday 22 November 2017 at 05:21 pm +0100, Christian Couder wrote:\n> On Wed, Nov 22, 2017 at 3:39 PM, Adam Dinwoodie <adam@dinwoodie.org> wrote:\n> > In trying to do a bisect on the Git repository, I seem to have come\n> > across surprising behavior where the order in which `git bisect` appears\n> > to forget that previous commits were marked as new.\n> \n> Yeah, the algorithm uses many \"old\" commits and only one \"new\" commit.\n> \n> [...]\n> \n> > As you can see, in both cases, only the most recent \"new\" command\n> > appears to have any effect.  I'd have expected that both commits would\n> > have been marked as \"new\", and the bisect run would use both facts to\n> > work out which commit is the target of the bisection.\n> \n> I didn't look at your test case, but the algorithm to find another\n> commit to test is described here:\n> \n> https://git-scm.com/docs/git-bisect-lk2009.html#_bisection_algorithm\n> \n> and you can see that the first rule of the algorithm is to keep only\n> the commits that are ancestors of the \"new\" commit (including the\n> \"new\" commit itself).\n> \n> The reason for this rule is that other commits cannot have introduced\n> the behavior we are looking for. The result of this rule is that git\n> bisect will always ask you to test a commit that is an ancestor of the\n> \"new\" commit.\n> \n> So if you test a commit that git bisect asks you to test, and it\n> appears that this commit is \"new\", then you can just discard the\n> previous \"new\" commit because it will give you less information than\n> the new \"new\" one.\n> (The old \"new\" will not let you discard any commits that the new \"new\"\n> commit allows you to discard, because it is a descendant of the new\n> \"new\" commit.)\n> \n> If you don't test the commit that git bisect asks you to test, then\n> git bisect assumes that you know better and discards the old \"new\".\n\nAh, that makes sense, thank you for the explanation.\n\nIn my case, I knew two commits were \"new\", but didn't know which would\nprovide more information to the bisect algorithm; I'd assumed if I\nprovided both, Git would work out the appropriate thing to do with the\ncombined information without me needing to work it out.\n\n> > This is using v2.15.0.  It's possibly relevant that 95a731ce is a\n> > direct parent of 14c63a9d.\n> >\n> > Is this a bug, or intentional behaviour?  Am I missing something that\n> > means it's actually sensible to have Git silently discard some bisect\n> > commands in this sort of circumstance?\n> \n> Well, instead of silently discarding a the old \"new\" commit when the\n> new \"new\" commit is not an ancestor of it, git bisect could perhaps\n> warn or ask you to confirm that you know what you are doing.\n\nWarning the user seems a sensible suggestion to me.  I'll add it to my\nlist of things to spend some time on at some point in the future :)\n"},{"id":"333327","messageId":"20171122213751.GC2854@sigill","threadId":"47298","inReplyTo":"20171122170129.GS20681@dinwoodie.org","subject":"Re: Bisect marking new commits incorrectly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-11-22T21:37:52Z","receivedAt":"2017-11-22T21:37:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 22, 2017 at 05:01:29PM +0000, Adam Dinwoodie wrote:\n\n> > So if you test a commit that git bisect asks you to test, and it\n> > appears that this commit is \"new\", then you can just discard the\n> > previous \"new\" commit because it will give you less information than\n> > the new \"new\" one.\n> > (The old \"new\" will not let you discard any commits that the new \"new\"\n> > commit allows you to discard, because it is a descendant of the new\n> > \"new\" commit.)\n> > \n> > If you don't test the commit that git bisect asks you to test, then\n> > git bisect assumes that you know better and discards the old \"new\".\n> \n> Ah, that makes sense, thank you for the explanation.\n> \n> In my case, I knew two commits were \"new\", but didn't know which would\n> provide more information to the bisect algorithm; I'd assumed if I\n> provided both, Git would work out the appropriate thing to do with the\n> combined information without me needing to work it out.\n\nYeah, I really would have expected this to work, too. Should we be\ntaking the merge base of the set of \"new\" commits, and using that as the\ntrue \"new\"?\n\nI.e., with this graph:\n\n  A--B--C--D\n      \\\n       E--F\n\nif I mark D and F as bad, can we assume that B, C, and E are \"new\", too,\nand treat \"B\" as the new single \"new\"? That breaks down if the bug was\nintroduced independently on each branch, but I think bisect explicitly\ndoesn't handle such a case.\n\nWhat might give it trouble is if there are multiple merge bases, like:\n\n\n    G--H-----\n   /      \\  \\\n  A--B--C--D  \\\n      \\        \\\n       E--------F\n\nThe flip to \"new\" could have been on the G-H branch, or in B.\n\nSo maybe that's not workable.\n\n(I've never really dug into the bisect algorithm, and this is written\nlargely off the cuff, so I'm fine if the response is \"nope, you have no\nidea what you are talking about\").\n\n-Peff\n"},{"id":"333409","messageId":"xmqq8tewp7mg.fsf@gitster.mtv.corp.google.com","threadId":"47298","inReplyTo":"20171122213751.GC2854@sigill","subject":"Re: Bisect marking new commits incorrectly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-24T05:29:11Z","receivedAt":"2017-11-24T05:29:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Yeah, I really would have expected this to work, too. Should we be\n> taking the merge base of the set of \"new\" commits, and using that as the\n> true \"new\"?\n> ...\n> So maybe that's not workable.\n>\n> (I've never really dug into the bisect algorithm, and this is written\n> largely off the cuff, so I'm fine if the response is \"nope, you have no\n> idea what you are talking about\").\n\nYou reached the right conclusion, I think.  \n\nA single merge-base case still might be worth optimizing for (and\nIIRC, unlike the \"git log A..B\" traversal that could be fooled by\nclock skew, merge-base reliably rejects falsely independent bases in\nthe presence of clock skew, so it should be safe to do), but in a\nscenario your second illustration depicts, the merge-bases would not\nhelp us that much.  \n\nWhen starting from D and F, both of which are known to be \"bad\", all\nwe know is that some of the merge bases between them are \"bad\",\nwhile other bases are not \"bad\" as they do not inherit the badness\nin the common ancestor of those \"bad\" bases.  \n\nAnd taking a merge base of these multiple merge-bases recursively\nwould not help us there.  We started from \"all of these, i.e. D and\nF, are known to be bad\", which is different from \"some of these\namong multiple bases are bad, but we do not know which ones\", so\neven if we were to go recursive, the first step needs to be \"now\nlet's see which one of these multiple bases are bad, so that we can\ntake merge-base across them\".\n\n      \n"}]}