{"thread":{"id":"45167","subject":"Git bisect does not find commit introducing the bug","startedAt":"2017-02-17T22:29:40Z","lastAt":"2017-02-21T22:40:06Z","messageCount":26,"participants":["Alex Hoffman","Stephan Beyer","Johannes Sixt","Christian Couder","Philip Oakley","Hilco Wijbenga","Jacob Keller","Oleg Taranenko","Junio C Hamano","Jakub Narębski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"311952","messageId":"CAMX8fZWe2HO78ySonHX0adtPUxVPbj5_vo-NUGrjwpb7gPdGrQ@mail.gmail.com","threadId":"45167","inReplyTo":null,"subject":"Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-17T22:29:21Z","receivedAt":"2017-02-17T22:29:40Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"Hi there,\n\nAccording to the documentation \"git bisect\" is designed \"to find the\ncommit that introduced a bug\" .\nI have found a situation in which it does not returns the commit I expected.\nIn order to reproduce the problem:\n\n1. mkdir test; cd test;\ngit clone https://github.com/entbugger/git-bisect-issue.git\ncd git-bisect-issue\n\nThe tag \"v.bad\" is one bad version and tag \"v.good\" is the first good\nversion. A good version is one having the line \"FEATURE2\" in\nfile1.txt, which was introduced in \"v.good\".\n\n2. Copy test scripts to another folder to make sure they are not\noverridden by 'git bisect'\ncp *.sh ../\ncd ..\n./search-bug-git.sh\n\n3. Run ./search-bug-git.sh to search for the commit introducing the\nbug. It finds that the commit 04c6f4b9ed with the message \"Feature 1\"\nis the first one introducing the bug.\n\nFirst of all this is confusing, as this commit cannot be reached\nstarting from \"v.good\". Then I expected the commit with the message\n\"Introduce bug\" to be returned by 'git bisect', as it is the first\ncommit between \"v.good\" and \"v.bad\" that does not contain the line\n\"FEATURE2\" in file1.txt, which is what I understand by the commit\n\"that introduced a bug\" (cited from the manpage of git bisect).\n\nThanks for looking to this,\n\nBest regards,\nVG\n"},{"id":"311976","messageId":"d4991e4b-cbc4-da14-381a-88704e457a19@gmx.net","threadId":"45167","inReplyTo":"CAMX8fZWe2HO78ySonHX0adtPUxVPbj5_vo-NUGrjwpb7gPdGrQ@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2017-02-17T23:21:35Z","receivedAt":"2017-02-17T23:22:59Z","isPatch":false,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nOn 02/17/2017 11:29 PM, Alex Hoffman wrote:\n> According to the documentation \"git bisect\" is designed \"to find the\n> commit that introduced a bug\" .\n> I have found a situation in which it does not returns the commit I expected.\n> In order to reproduce the problem:\n\nFor the others who are too lazy to clone your repo and run the scripts,\nthe history is like that (read from bottom to top) and I marked the\ncommit found by git bisect and the on you expected:\n\n* 7a9e952 (bisect bad) \n|\\\n| * 671cec2 <--- expected\n| |\\\n| * | 04c6f4b <--- found\n* | | 3915157 \n|\\ \\ \\\n| | |/\n| |/|\n| * | f4154e9 (bisect good) \n| * | 85855bf \n| |/\n* | f1a36f5 \n|/\n* 1b7fb88 \n\nThe and markers are set by your definition of what good and\nwhat bad commits are.\n\n> First of all this is confusing, as this commit cannot be reached\n> starting from \"v.good\".\n\nHm, IMHO it shows that your example is pretty artificial (although you\nmight have come across it in a real-world scenario): you introduced a\nnew feature in f4154e9 (and it worked) and you broke that feature by\nmaking the merge 671cec2. However, the feature (that broke in 671cec2)\ndid not even exist in 04c6f4b; so a test on the feature would not fail\n(leading to \"bisect bad\" as in the example), it would not exist (leading\nto \"bisect skip\").\n\nAnd if we are not talking about passing or failing tests but about\ncrashing, bisect finds the right thing: f4154e9 was not crashing, but\n04c6f4b is crashing. Yes, it's not the commit that introduced the crash\n(which would be the first commit in the repo) but it's the first\ncrashing commit after the one marked as good.\n\nSo I'd consider this a feature or rather correct behavior, not a bug.\n\nIn other words: bisect assumes that your repo is usually in a good state\nand you have a commit that changes it to a bad state. In your case you\nhave a repo that is in a bad state and you have a commit that switches\nit to a good state and later you merge a bad-state branch and you have a\nbad state again. It is not made for that use-case, I think.\n\nCheers\n Stephan\n"},{"id":"312031","messageId":"3ff5ce3c-285f-cb9a-d1d4-46323524dab7@kdbg.org","threadId":"45167","inReplyTo":"d4991e4b-cbc4-da14-381a-88704e457a19@gmx.net","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-02-18T09:12:14Z","receivedAt":"2017-02-18T09:13:11Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 18.02.2017 um 00:21 schrieb Stephan Beyer:\n> On 02/17/2017 11:29 PM, Alex Hoffman wrote:\n> * 7a9e952 (bisect bad) \n> |\\\n> | * 671cec2 <--- expected\n> | |\\\n> | * | 04c6f4b <--- found\n> * | | 3915157 \n> |\\ \\ \\\n> | | |/\n> | |/|\n> | * | f4154e9 (bisect good) \n> | * | 85855bf \n> | |/\n> * | f1a36f5 \n> |/\n> * 1b7fb88 \n>\n> The and markers are set by your definition of what good and\n> what bad commits are.\n>\n> [...]\n> In other words: bisect assumes that your repo is usually in a good state\n> and you have a commit that changes it to a bad state. In your case you\n> have a repo that is in a bad state and you have a commit that switches\n> it to a good state and later you merge a bad-state branch and you have a\n> bad state again. It is not made for that use-case, I think.\n\nCorrect. The assumption of bisection is that there is only one \ntransition between GOOD and BAD. By violating that assumption, anything \ncan happen.\n\n-- Hannes\n\n"},{"id":"312032","messageId":"CAMX8fZVkBU6M8fkUcRr69V97_NTSOGGmPB1U-ObhmVv3i6wQhg@mail.gmail.com","threadId":"45167","inReplyTo":"3ff5ce3c-285f-cb9a-d1d4-46323524dab7@kdbg.org","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-18T11:15:13Z","receivedAt":"2017-02-18T11:19:25Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":">> First of all this is confusing, as this commit cannot be reached\n>> starting from \"v.good\".\n\n> Hm, IMHO it shows that your example is pretty artificial (although you\n> might have come across it in a real-world scenario): you introduced a\n> new feature in f4154e9 (and it worked) and you broke that feature by\n> making the merge 671cec2. However, the feature (that broke in 671cec2)\n> did not even exist in 04c6f4b; so a test on the feature would not fail\n> (leading to \"bisect bad\" as in the example), it would not exist (leading\n> to \"bisect skip\").\n\nNo one commented the fact, that I find this very confusing. Don't you\nfind this confusing? I will underline, that 'git bisect good v.good'\nwill fail if the commit 'v.good' is not a parent of the bad commit,\nmeaning there MUST be at least a path between 'v.good' and 'v.bad',\nthus I would expect it looks on this path ONLY. Beside that, this is\nwhat I understand by 'binary search' (to search on this commit path).\nYou might find this example artificial, but I doubt git is/was\nintentionally designed to work with 'natural' examples only (no\nmatter how you define 'natural' and 'artificial').\n\n\n\n>> In other words: bisect assumes that your repo is usually in a good state\n>> and you have a commit that changes it to a bad state. In your case you\n>> have a repo that is in a bad state and you have a commit that switches\n>> it to a good state and later you merge a bad-state branch and you have a\n>> bad state again. It is not made for that use-case, I think.\n\n> Correct. The assumption of bisection is that there is only one transition between GOOD and BAD. By violating that assumption, anything can happen.\n\nI did not find that in the manpage or did I miss it? Why would someone\nassume that the commit graph looks in a certain way? I assume, that\n'git bisect' was not thought through and that it considers the first\ndirected path between v.good and v.bad, instead of all paths (in my\nexample graph there are two such paths). I will also underline that\ngit bisect was designed to work with multiple good commits and one bad\ncommit (also multiple paths), but probably NOT with multiple paths\nbetween the same pair of good and bad commits.\n\nVG\n\n\n2017-02-18 10:12 GMT+01:00 Johannes Sixt :\n> Am 18.02.2017 um 00:21 schrieb Stephan Beyer:\n>>\n>> On 02/17/2017 11:29 PM, Alex Hoffman wrote:\n>> * 7a9e952 (bisect bad) \n>> |\\\n>> | * 671cec2 <--- expected\n>> | |\\\n>> | * | 04c6f4b <--- found\n>> * | | 3915157 \n>> |\\ \\ \\\n>> | | |/\n>> | |/|\n>> | * | f4154e9 (bisect good) \n>> | * | 85855bf \n>> | |/\n>> * | f1a36f5 \n>> |/\n>> * 1b7fb88 \n>>\n>> The and markers are set by your definition of what good and\n>> what bad commits are.\n>>\n>> [...]\n>> In other words: bisect assumes that your repo is usually in a good state\n>> and you have a commit that changes it to a bad state. In your case you\n>> have a repo that is in a bad state and you have a commit that switches\n>> it to a good state and later you merge a bad-state branch and you have a\n>> bad state again. It is not made for that use-case, I think.\n>\n>\n> Correct. The assumption of bisection is that there is only one transition\n> between GOOD and BAD. By violating that assumption, anything can happen.\n>\n> -- Hannes\n>\n"},{"id":"312051","messageId":"477d3533-d453-9499-e06e-72f45488d421@kdbg.org","threadId":"45167","inReplyTo":"CAMX8fZVkBU6M8fkUcRr69V97_NTSOGGmPB1U-ObhmVv3i6wQhg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-02-18T14:18:45Z","receivedAt":"2017-02-18T14:18:54Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 18.02.2017 um 12:15 schrieb Alex Hoffman:\n> No one commented the fact, that I find this very confusing. Don't you\n> find this confusing? I will underline, that 'git bisect good v.good'\n> will fail if the commit 'v.good' is not a parent of the bad commit,\n> meaning there MUST be at least a path between 'v.good' and 'v.bad',\n> thus I would expect it looks on this path ONLY. Beside that, this is\n> what I understand by 'binary search' (to search on this commit path).\n\nBut this is not how Git works. Git computes graph differences, i.e., it \nsubtracts from the commits reachable from v.bad those that are reachable \nfrom v.good. This leaves more than just those on some path from v.good \nto v.bad. And it should work this way. Consider this history:\n\n--o--o--o--G--X\n \\ \\\n x--x--x--x--X--B--\n\nWhen you find B bad and G good, than any one of the x or X may have \nintroduced the breakage, not just one of the X.\n\n>> Correct. The assumption of bisection is that there is only one\n>> transition between GOOD and BAD. By violating that assumption,\n>> anything can happen.\n>\n> I did not find that in the manpage or did I miss it? Why would someone\n> assume that the commit graph looks in a certain way?\n\nThere is no restriction in the commit graph. The only restriction, \nactually assumption, is that there is *one* transition from good to bad \nand no transition from bad to good. Otherwise, bisection cannot work.\n\n> I assume, that\n> 'git bisect' was not thought through and that it considers the first\n> directed path between v.good and v.bad, instead of all paths (in my\n> example graph there are two such paths). I will also underline that\n> git bisect was designed to work with multiple good commits and one bad\n> commit (also multiple paths), but probably NOT with multiple paths\n> between the same pair of good and bad commits.\n\nOh, IMO git bisect was well thought through. If it considered just paths \nfrom good to bad, it would not given the correct answer. See the example \nhistory above. Bisect authors would not have deemed that sufficiently \ngood ;)\n\n-- Hannes\n\n"},{"id":"312052","messageId":"CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com","threadId":"45167","inReplyTo":"477d3533-d453-9499-e06e-72f45488d421@kdbg.org","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-18T18:36:43Z","receivedAt":"2017-02-18T18:36:50Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"> But this is not how Git works. Git computes graph differences, i.e., it\n> subtracts from the commits reachable from v.bad those that are reachable\n> from v.good. This leaves more than just those on some path from v.good to\n> v.bad. And it should work this way. Consider this history:\n>\n> --o--o--o--G--X\n> \\ \\\n> x--x--x--x--X--B--\n>\n> When you find B bad and G good, than any one of the x or X may have\n> introduced the breakage, not just one of the X.\n>\n\nThank you for clarifying how git bisect works. How did you find that\nout? Did you check the source code? If that is not documented in the\nman page may be it worth documenting it in order to avoid future\nconfusion for other users.\n\nLet's consider your example with distinct names for nodes:\n\n--o1--o2--o3--G--X1\n \\ \\\n x1--x2--x3--x4--X1--B--\n\nIt makes sense that git bisect is expecting a single transition, as\nthis is a precondition for a binary search to work. My definition of\n\"the transition\" is a commit with at least one of its parents as a\ngood version, but the commit itself a bad version. I hope we agree\nthat git bisect's mission is to search for this transition (as I\nsuppose that most of people need such a functionality from git, if not\nexactly from git bisect). How could be x1 or x3 be the transition, if\nchances are that o1 is not a good version? Of course it would make\nsense to me if bisect would check o1 whether good and only then to\ncheck also x1-x3, but this is not what git makes (at least not in my\ninitial example).\n\nIf you consider that git bisect's mission is different from finding\nthe transition, could you please explain what exact commit git bisect\nis supposed to return (ideally with terms from the graph theory) and\nwhen it makes sense to return that? Because I do not see any sense in\nlooking in the path x1-x3 without knowing that those commits may be a\ntransition.\n\n\n> Oh, IMO git bisect was well thought through. If it considered just paths\n> from good to bad, it would not given the correct answer. See the example\n> history above. Bisect authors would not have deemed that sufficiently good\n\nYou definitely convinced me that git MUST search more than only in the\npaths between good and bad commits, as the good commit G does not have\nto be the first good commit (thank you for that). My problem/confusion\nis that it returns something that does not make sense to me, because\nit does not make sure it returns a transition.\n\nVG\n\nPS: thank you for continuing this discussion.\n"},{"id":"312054","messageId":"CAP8UFD3ngMvVy2XLzYNn9OFbS+zQpWTW=pravpHhA-0PcDVhfg@mail.gmail.com","threadId":"45167","inReplyTo":"CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2017-02-18T19:58:59Z","receivedAt":"2017-02-18T19:59:32Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sat, Feb 18, 2017 at 7:36 PM, Alex Hoffman wrote:\n>> But this is not how Git works. Git computes graph differences, i.e., it\n>> subtracts from the commits reachable from v.bad those that are reachable\n>> from v.good. This leaves more than just those on some path from v.good to\n>> v.bad. And it should work this way. Consider this history:\n>>\n>> --o--o--o--G--X\n>> \\ \\\n>> x--x--x--x--X--B--\n>>\n>> When you find B bad and G good, than any one of the x or X may have\n>> introduced the breakage, not just one of the X.\n>>\n>\n> Thank you for clarifying how git bisect works. How did you find that\n> out? Did you check the source code? If that is not documented in the\n> man page may be it worth documenting it in order to avoid future\n> confusion for other users.\n\nAt the end of the git-bisect man page (in the SEE ALSO section) there\nis a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt\nwhich has a lot of details about how bisect works.\n\n> Let's consider your example with distinct names for nodes:\n>\n> --o1--o2--o3--G--X1\n> \\ \\\n> x1--x2--x3--x4--X1--B--\n>\n> It makes sense that git bisect is expecting a single transition, as\n> this is a precondition for a binary search to work. My definition of\n> \"the transition\" is a commit with at least one of its parents as a\n> good version, but the commit itself a bad version.\n\nWhat if a commit C has one good parent A and one bad parent B?\nIsn't it more likely that the first bad commit is B instead of C?\n\n> I hope we agree\n> that git bisect's mission is to search for this transition (as I\n> suppose that most of people need such a functionality from git, if not\n> exactly from git bisect).\n\nThe goal is to find the first bad commit, which is a commit that has\nonly good parents.\n\n> How could be x1 or x3 be the transition, if\n> chances are that o1 is not a good version?\n\nAs o1 is an ancestor of G, then o1 is considered good by the bisect algorithm.\nIf it was bad, it would means that there is a transition from bad to\ngood between o1 and G.\nBut when a good commit is an ancestor of the bad commit, git bisect\nmakes the assumption that there is no transition from bad to good in\nthe graph.\n\n> Of course it would make\n> sense to me if bisect would check o1 whether good and only then to\n> check also x1-x3, but this is not what git makes (at least not in my\n> initial example).\n>\n> If you consider that git bisect's mission is different from finding\n> the transition, could you please explain what exact commit git bisect\n> is supposed to return (ideally with terms from the graph theory) and\n> when it makes sense to return that? Because I do not see any sense in\n> looking in the path x1-x3 without knowing that those commits may be a\n> transition.\n\nI hope it makes sense with the above explanations.\n\n>> Oh, IMO git bisect was well thought through. If it considered just paths\n>> from good to bad, it would not given the correct answer. See the example\n>> history above. Bisect authors would not have deemed that sufficiently good\n>\n> You definitely convinced me that git MUST search more than only in the\n> paths between good and bad commits, as the good commit G does not have\n> to be the first good commit (thank you for that). My problem/confusion\n> is that it returns something that does not make sense to me, because\n> it does not make sure it returns a transition.\n\ngit bisect makes some assumptions that are true most of the time, so\nin practice it works well most of the time.\n"},{"id":"312057","messageId":"6545FDC46D2741A289D0D5E9A84ADD75@PhilipOakley","threadId":"45167","inReplyTo":"CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2017-02-18T22:10:12Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Alex Hoffman\" \n>> But this is not how Git works. Git computes graph differences, i.e., it\n>> subtracts from the commits reachable from v.bad those that are reachable\n>> from v.good. This leaves more than just those on some path from v.good to\n>> v.bad. And it should work this way. Consider this history:\n>>\n>> --o--o--o--G--X\n>> \\ \\\n>> x--x--x--x--X--B--\n>>\n>> When you find B bad and G good, than any one of the x or X may have\n>> introduced the breakage, not just one of the X.\n>>\n>\n> Thank you for clarifying how git bisect works. How did you find that\n> out? Did you check the source code? If that is not documented in the\n> man page may be it worth documenting it in order to avoid future\n> confusion for other users.\n\nAny suggestions for improving the documentation are always worthwhile. As \nsomeone who asked, what extra info would have helped?\n\nEven beetter if it looks like a patch ;-)\n\n>\n> Let's consider your example with distinct names for nodes:\n>\n> --o1--o2--o3--G--X1\n> \\ \\\n> x1--x2--x3--x4--X1--B--\n>\n> It makes sense that git bisect is expecting a single transition, as\n> this is a precondition for a binary search to work. My definition of\n> \"the transition\" is a commit with at least one of its parents as a\n> good version, but the commit itself a bad version. I hope we agree\n> that git bisect's mission is to search for this transition (as I\n> suppose that most of people need such a functionality from git, if not\n> exactly from git bisect). How could be x1 or x3 be the transition, if\n> chances are that o1 is not a good version? Of course it would make\n> sense to me if bisect would check o1 whether good and only then to\n> check also x1-x3, but this is not what git makes (at least not in my\n> initial example).\n>\n> If you consider that git bisect's mission is different from finding\n> the transition, could you please explain what exact commit git bisect\n> is supposed to return (ideally with terms from the graph theory) and\n> when it makes sense to return that? Because I do not see any sense in\n> looking in the path x1-x3 without knowing that those commits may be a\n> transition.\n>\n>\n>> Oh, IMO git bisect was well thought through. If it considered just paths\n>> from good to bad, it would not given the correct answer. See the example\n>> history above. Bisect authors would not have deemed that sufficiently \n>> good\n>\n> You definitely convinced me that git MUST search more than only in the\n> paths between good and bad commits, as the good commit G does not have\n> to be the first good commit (thank you for that). My problem/confusion\n> is that it returns something that does not make sense to me, because\n> it does not make sure it returns a transition.\n>\n> VG\n>\n> PS: thank you for continuing this discussion.\n>\n--\nPhilip \n\n"},{"id":"312058","messageId":"CAE1pOi0rsY1eCS25fFsSiCZoKxfCJHfaxcauKd_dDxnG8u6DhA@mail.gmail.com","threadId":"45167","inReplyTo":"CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Hilco Wijbenga","fromEmail":"hilco.wijbenga@gmail.com","sentAt":"2017-02-18T22:36:34Z","receivedAt":"2017-02-18T22:37:01Z","isPatch":false,"sender":{"key":"hilco.wijbenga@gmail.com","avatar":null},"body":"On 18 February 2017 at 10:36, Alex Hoffman wrote:\n> You definitely convinced me that git MUST search more than only in the\n> paths between good and bad commits, as the good commit G does not have\n> to be the first good commit (thank you for that). My problem/confusion\n> is that it returns something that does not make sense to me, because\n> it does not make sure it returns a transition.\n\nIf multiple transitions from GOOD to BAD happen, then I don't see how\nbinary search is useful/possible. The same is true for a simple list\nof numbers, say, 1 5 6 2 3 4. You can't use binary search here because\nyou can't \"throw away\" all numbers to the left (or right) of your\npivot. Or am I missing your point?\n"},{"id":"312059","messageId":"148a585a-33df-1adb-6410-5c4fe09202b0@kdbg.org","threadId":"45167","inReplyTo":"CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-02-18T22:37:12Z","receivedAt":"2017-02-18T22:37:20Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 18.02.2017 um 19:36 schrieb Alex Hoffman:\n> Let's consider your example with distinct names for nodes:\n>\n> --o1--o2--o3--G--X1\n> \\ \\\n> x1--x2--x3--x4--X2--B--\n>\n> It makes sense that git bisect is expecting a single transition, as\n> this is a precondition for a binary search to work. My definition of\n> \"the transition\" is a commit with at least one of its parents as a\n> good version, but the commit itself a bad version.\n\nBut that is not the definition of transition that lets you pin-point the \nbreaking commit precisly. Assume x3 is the commit introducing the \nbreakage in the graph above. Even though you only know initially that G \nis good and B is bad, would you not prefer to find x3 instead of X2? As \nChristian said, a transition is when a commit is bad and all its parents \nare good, and this definition lets you find x3.\n\n> I hope we agree\n> that git bisect's mission is to search for this transition (as I\n> suppose that most of people need such a functionality from git, if not\n> exactly from git bisect). How could be x1 or x3 be the transition, if\n> chances are that o1 is not a good version?\n\nBy declaring G as good, it is implied that o1 is also good. If it is in \nfact bad, the assumptions of git bisect are violated (because there \nwould be a transition from bad to good at o2, o3, or G), and anything \ncan happen.\n\n> If you consider that git bisect's mission is different from finding\n> the transition, could you please explain what exact commit git bisect\n> is supposed to return (ideally with terms from the graph theory) and\n> when it makes sense to return that? Because I do not see any sense in\n> looking in the path x1-x3 without knowing that those commits may be a\n> transition.\n\nAnd I do not see a reason why git bisect should not look at those \ncommits. If x3 is the commit that broke my program, I do prefer to be \npointed at x3 rather than X2.\n\n-- Hannes\n\n"},{"id":"312080","messageId":"CAMX8fZVeAEJ5tfCO_4Pebnq=rysaJ2xDMjH-9pjmPeF4FziLFw@mail.gmail.com","threadId":"45167","inReplyTo":"CAP8UFD3ngMvVy2XLzYNn9OFbS+zQpWTW=pravpHhA-0PcDVhfg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-19T11:32:01Z","receivedAt":"2017-02-19T11:32:09Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"> At the end of the git-bisect man page (in the SEE ALSO section) there\n> is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt\n> which has a lot of details about how bisect works.\n>\n\nThanks for pointing out the SEE ALSO section. I think it makes sense\nto include/describe the entire algorithm in the man page itself,\nalthough I am not sure whether the graphs would be always correctly\nvisually represented in the man page format.\n\n> The goal is to find the first bad commit, which is a commit that has\n> only good parents.\n\nOK, bisect's mission is more exact than I thought, which is good. M\n\n> As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm.\n> If it was bad, it would means that there is a transition from bad to\n> good between o1 and G.\n> But when a good commit is an ancestor of the bad commit, git bisect\n> makes the assumption that there is no transition from bad to good in\n> the graph.\n\nThe assumption that there is no transition from bad to good in the\ngraph did not hold in my example and it does not hold when a feature\nwas recently introduced and gets broken relative shortly afterwards.\nBut I consider it is easy to change the algorithm not to assume, but\nrather to check it.\n\n> git bisect makes some assumptions that are true most of the time, so\n> in practice it works well most of the time.\n\nWhatever the definition of \"most of the time\" everyone might have, I\nthink there is room for improvement. Below I am trying to make a small\nchange to the current algorithm in order to deal with the assumption\nthat sometimes does not hold (e.g in my example), by explicitly\nvalidating the check.\n\n> --o1--o2--o3--G--X1\n> \\ \\\n> x1--x2--x3--x4--X2--B--\n> \\ /\n> y1--y2--y3\n\nStep 1a. (Unchanged) keep only the commits that:\n\n a) are ancestor of the \"bad\" commit (including the \"bad\" commit itself),\n b) are not ancestor of a \"good\" commit (excluding the \"good\" commits).\n\nThe following graph results:\n x1--x2--x3--x4--X2--B--\n \\ /\n y1--y2--y3\n\nStep 1b. (New) Mark all root commits of the resulting graph (i.e\ncommits without parents) as unconfirmed (unconfirmed=node that has\nonly bad parents). Remove all root commits that user already confirmed\n(e.g if user already marked its parent as good right before starting\nbisect run). For every unconfirmed root commit check if it has any\ngood parents. In the example above check whether x1 has good parents.\n If the current root element has any parents and none of them is\ngood, we can delete all paths from it until to the next commit that\nhas a parent in the ancestors of GOOD. In the example above to delete\nthe path x1-x3 and x1-y3. Also add new resulting root commits to the\nlist of unconfirmed commits (commit x4).\n Otherwise mark it as confirmed.\n\nStep2. Continue the existing algorithm.\n\n\nIf this improvement works (i.e you do not find any bugs in it and it\nis feasible to implement, which seems to me) the following would be\nits advantages:\n1. An assumption less, as we explicitly check the assumption.\n2. It might be quicker, because we delete parts of graph that cannot\ncontain transitions.\n3. It returns more exact results.\n\nVG\n"},{"id":"312081","messageId":"CAMX8fZWarm6wqtaazkWiUeSdsw_FThxWV1U6zV0iEtssdmvrOw@mail.gmail.com","threadId":"45167","inReplyTo":"CAMX8fZVeAEJ5tfCO_4Pebnq=rysaJ2xDMjH-9pjmPeF4FziLFw@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-19T12:43:36Z","receivedAt":"2017-02-19T12:45:37Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"Below is a correction of the first proposed algorithm:\n\n>--o1--o2--o3--G --X1\n> \\ \\\n> x1--x2--x3--x4--X2--B--\n> \\ /\n> y1--y2--y3\n>\nStep 1a. (Unchanged) keep only the commits that:\n\n a) are ancestor of the \"bad\" commit (including the \"bad\" commit itself),\n b) are not ancestor of a \"good\" commit (excluding the \"good\" commits).\n\nThe following graph results:\n x1--x2--x3--x4--X2--B--\n \\ /\n y1--y2--y3\n\nStep 1b. (New) Mark all commits of the resulting graph as unconfirmed\n(unconfirmed=node without good ancestors).\nMark as confirmed all descendants of commits that user marked\nexplicitly as good (e.g if user already marked its parent/grand\nparent/... as good right before starting bisect run).\nStep 1c. From all unconfirmed root commits build a set SET_GOOD of\nthose with any good parents in the original graph (root commit =\ncommit without parents in the resulting graph) and one SET_BAD for\ncommits with only BAD parents. To build a set means to ask explicitly\nthe user (or the command passed in git bisect run) whether any of its\nparents is good. In the example above find out whether x1 has any good\nparents or no parent at all and if so add it to SET_GOOD, otherwise to\nSET_BAD.\nMark as confirmed each commit in SET_GOOD and all its descendants.\nFor every commit in SET_BAD delete all paths from it until to the next\nconfirmed commit. In the example above if x1 is in SET_BAD delete the\npath x1-x3 and x1-y3. If any new root commits result (commit x4), redo\nstep 1c with them.\n\n\nStep2. Continue the existing algorithm.\n\nIf this improvement works (i.e you do not find any bugs in it and it\nis feasible to implement, which seems to me) the following would be\nits advantages:\n1. An assumption less, as we explicitly check the assumption.\n2. It might be quicker, because we delete parts of graph that cannot\ncontain transitions.\n3. It returns more exact results.\n\nVG\n"},{"id":"312082","messageId":"CAP8UFD2R94sPCd5i8NF1oZn+g8X6oYRqP7qYftmny2iXwh59Hw@mail.gmail.com","threadId":"45167","inReplyTo":"CAMX8fZVeAEJ5tfCO_4Pebnq=rysaJ2xDMjH-9pjmPeF4FziLFw@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2017-02-19T13:07:10Z","receivedAt":"2017-02-19T13:08:09Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Feb 19, 2017 at 12:32 PM, Alex Hoffman wrote:\n>> At the end of the git-bisect man page (in the SEE ALSO section) there\n>> is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt\n>> which has a lot of details about how bisect works.\n>\n> Thanks for pointing out the SEE ALSO section. I think it makes sense\n> to include/describe the entire algorithm in the man page itself,\n> although I am not sure whether the graphs would be always correctly\n> visually represented in the man page format.\n\nIt would possibly be very long to describe the entire algorithm, as it\ncan be quite complex in some cases and it is difficult to understand\nwithout graphs. Maybe we could describe it, or some parts of it, in a\nseparate document and provide links at different places in the man\npage.\nAnyway feel free to send patches.\n\n>> The goal is to find the first bad commit, which is a commit that has\n>> only good parents.\n>\n> OK, bisect's mission is more exact than I thought, which is good. M\n\nGood that you seem to agree with this goal.\n\n>> As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm.\n>> If it was bad, it would means that there is a transition from bad to\n>> good between o1 and G.\n>> But when a good commit is an ancestor of the bad commit, git bisect\n>> makes the assumption that there is no transition from bad to good in\n>> the graph.\n>\n> The assumption that there is no transition from bad to good in the\n> graph did not hold in my example and it does not hold when a feature\n> was recently introduced and gets broken relative shortly afterwards.\n> But I consider it is easy to change the algorithm not to assume, but\n> rather to check it.\n\nI don't think the default algorithm will change soon, but there have\nbeen discussions for a long time about adding options to use different\nalgorithms.\n\nFor example people have been discussing a \"--first-parent\" option for\nmany years as well as recently. It would bisect only along the first\nparents of the involved commits, and it could help find the merge\ncommit that introduced a bug in the mainline.\n\n>> git bisect makes some assumptions that are true most of the time, so\n>> in practice it works well most of the time.\n>\n> Whatever the definition of \"most of the time\" everyone might have, I\n> think there is room for improvement.\n\nSo feel free to send patches that would implement an option with the\nimprovements you want.\n\n> Below I am trying to make a small\n> change to the current algorithm in order to deal with the assumption\n> that sometimes does not hold (e.g in my example), by explicitly\n> validating the check.\n>\n>> --o1--o2--o3--G--X1\n>> \\ \\\n>> x1--x2--x3--x4--X2--B--\n>> \\ /\n>> y1--y2--y3\n>\n> Step 1a. (Unchanged) keep only the commits that:\n>\n> a) are ancestor of the \"bad\" commit (including the \"bad\" commit itself),\n> b) are not ancestor of a \"good\" commit (excluding the \"good\" commits).\n>\n> The following graph results:\n> x1--x2--x3--x4--X2--B--\n> \\ /\n> y1--y2--y3\n\nI would say that the above graph is missing X1.\n\n> Step 1b. (New) Mark all root commits of the resulting graph (i.e\n> commits without parents) as unconfirmed (unconfirmed=node that has\n> only bad parents). Remove all root commits that user already confirmed\n> (e.g if user already marked its parent as good right before starting\n> bisect run). For every unconfirmed root commit check if it has any\n> good parents. In the example above check whether x1 has good parents.\n\nI think I understand the above...\n\n> If the current root element has any parents and none of them is\n> good, we can delete all paths from it until to the next commit that\n> has a parent in the ancestors of GOOD. In the example above to delete\n> the path x1-x3 and x1-y3. Also add new resulting root commits to the\n> list of unconfirmed commits (commit x4).\n> Otherwise mark it as confirmed.\n\n... but I don't understand the logic of the above. If the root element\nhas a bad parent, then it means that the \"first bad commit\" is either\nthe bad parent or one of its ancestors, so it is not logical to delete\nit. In your example if x1 has one bad parent, this bad parent and its\nancestors should be included in the search of the first bad commit.\n\nOtherwise the goal is not any more to find the first bad commit.\n\nPS: I saw that you have just sent another version of the algorithm,\nbut I don't want to take a look at it right now. Anyway I am keeping\nmy above comments as they might still be useful.\n\n> Step2. Continue the existing algorithm.\n>\n>\n> If this improvement works (i.e you do not find any bugs in it and it\n> is feasible to implement, which seems to me)\n\nAs you describe it, I don't think it is compatible with the goal of\nfinding the first bad commit.\nAlso there are many things that are feasible to implement, but it\ndoesn't mean that someone will soon make the effort to implement them\nin a way that looks good enough to be deemed worth merging into the\ncurrent code base.\n\n> the following would be\n> its advantages:\n> 1. An assumption less, as we explicitly check the assumption.\n\nChecking can be costly. If the probability that the check will fail is\nvery low, while the cost of checking is high, it is less costly on\naverage to not check.\n\n> 2. It might be quicker, because we delete parts of graph that cannot\n> contain transitions.\n\nI don't agree that it's a good idea to delete what you suggest above.\nOr if you think that the goal should not be to find the \"first bad\ncommit\" in the above case, then you should explain what the goal\nshould be.\n\n> 3. It returns more exact results.\n\nYeah, but checking every commit related to the good and bad commits\nwould also return more exact results. (This can probably be done using\n`git rebase --exec ...` by the way.) One could even print a nice graph\nwith all the good and bad commits. The problem is that it would not be\nefficient. If git bisect makes some assumptions, it is because they\nhave been deemed reasonable and they have worked well in practice.\nIt's also because the goal of git bisect is to be efficient, otherwise\nthere would be no point in using a binary search algorithm in the\nfirst place.\n"},{"id":"312083","messageId":"d7bb866d-4a50-f75e-ff4c-bcdd54f75459@kdbg.org","threadId":"45167","inReplyTo":"CAMX8fZVeAEJ5tfCO_4Pebnq=rysaJ2xDMjH-9pjmPeF4FziLFw@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-02-19T14:13:12Z","receivedAt":"2017-02-19T14:13:21Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 19.02.2017 um 12:32 schrieb Alex Hoffman:\n> The assumption that there is no transition from bad to good in the\n> graph did not hold in my example and it does not hold when a feature\n> was recently introduced and gets broken relative shortly afterwards.\n\nThen you must adjust your definition of \"good\": All commits that do not \nhave the feature, yet, are \"good\": since they do not have the feature in \nthe first place, they cannot have the breakage that you found in the \nfeature.\n\nThat is exactly the situation in your original example! But you \nconstructed the condition of goodness in such a simplistic way \n(depending on the presence of a string), that it was impossible to \ndistinguish between \"does not have the feature at all\" and \"has the \nfeature, but it is broken\".\n\n-- Hannes\n\n"},{"id":"312087","messageId":"CAMX8fZWRgeK5XjSrFYzZea8YgT9Mqm0XJBxQGt1eqdWZU+DEnA@mail.gmail.com","threadId":"45167","inReplyTo":"d7bb866d-4a50-f75e-ff4c-bcdd54f75459@kdbg.org","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-19T19:05:00Z","receivedAt":"2017-02-19T19:05:12Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"> Then you must adjust your definition of \"good\": All commits that do not have\n> the feature, yet, are \"good\": since they do not have the feature in the\n> first place, they cannot have the breakage that you found in the feature.\n>\n> That is exactly the situation in your original example! But you constructed\n> the condition of goodness in such a simplistic way (depending on the\n> presence of a string), that it was impossible to distinguish between \"does\n> not have the feature at all\" and \"has the feature, but it is broken\".\n\nJohannes, thank you for correctly identifying the error in my logic.\nIndeed I was using the term 'bad' also for the commit without the\nfeature. In order to find the commit introducing the bug in my example\na new state is needed, which would make 'git bisect' a bit more\ncomplicated than the user 'most of the time' probably needs. Or do you\nthink, it would make sense to ask the user for this state (if e.g 'git\nbisect' would be started with a new parameter)?\n"},{"id":"312088","messageId":"CA+P7+xrch9WDo6OgU3vUEpXqAETZ07mkf76dC9nJctm0LTFQHQ@mail.gmail.com","threadId":"45167","inReplyTo":"CAMX8fZWRgeK5XjSrFYzZea8YgT9Mqm0XJBxQGt1eqdWZU+DEnA@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2017-02-19T19:25:14Z","receivedAt":"2017-02-19T19:25:44Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Sun, Feb 19, 2017 at 11:05 AM, Alex Hoffman wrote:\n>> Then you must adjust your definition of \"good\": All commits that do not have\n>> the feature, yet, are \"good\": since they do not have the feature in the\n>> first place, they cannot have the breakage that you found in the feature.\n>>\n>> That is exactly the situation in your original example! But you constructed\n>> the condition of goodness in such a simplistic way (depending on the\n>> presence of a string), that it was impossible to distinguish between \"does\n>> not have the feature at all\" and \"has the feature, but it is broken\".\n>\n> Johannes, thank you for correctly identifying the error in my logic.\n> Indeed I was using the term 'bad' also for the commit without the\n> feature. In order to find the commit introducing the bug in my example\n> a new state is needed, which would make 'git bisect' a bit more\n> complicated than the user 'most of the time' probably needs. Or do you\n> think, it would make sense to ask the user for this state (if e.g 'git\n> bisect' would be started with a new parameter)?\n\nIf a commit doesn't have the feature, then it is by definition, not\ncontaining a broken feature, and you can simply use the \"good\" state.\nThere is no need for a different state. If you can't test the commit\nbecause it's broken in some other way, you can use \"git bisect skip\"\nbut that isn't what you want in this case.\n\nThanks,\nJake\n"},{"id":"312124","messageId":"CABEd3j8sgDd8DXW8+2Q7pjANPTr-Ws1Xs1ap875mkxFOfnenYw@mail.gmail.com","threadId":"45167","inReplyTo":"CA+P7+xrch9WDo6OgU3vUEpXqAETZ07mkf76dC9nJctm0LTFQHQ@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Oleg Taranenko","fromEmail":"olegtaranenko@gmail.com","sentAt":"2017-02-20T07:38:11Z","receivedAt":"2017-02-20T07:46:31Z","isPatch":false,"sender":{"key":"olegtaranenko@gmail.com","avatar":"https://gravatar.com/avatar/016106c4926412cef4141b2d7cea4378aef44db0ca56c9462a5f4a71c7a80955?d=mp&s=160"},"body":">>> Then you must adjust your definition of \"good\": All commits that do not have\n>>> the feature, yet, are \"good\": since they do not have the feature in the\n>>> first place, they cannot have the breakage that you found in the feature.\n>>>\n>>> That is exactly the situation in your original example! But you constructed\n>>> the condition of goodness in such a simplistic way (depending on the\n>>> presence of a string), that it was impossible to distinguish between \"does\n>>> not have the feature at all\" and \"has the feature, but it is broken\".\n>>\n>> Johannes, thank you for correctly identifying the error in my logic.\n>> Indeed I was using the term 'bad' also for the commit without the\n>> feature. In order to find the commit introducing the bug in my example\n>> a new state is needed, which would make 'git bisect' a bit more\n>> complicated than the user 'most of the time' probably needs. Or do you\n>> think, it would make sense to ask the user for this state (if e.g 'git\n>> bisect' would be started with a new parameter)?\n\n\n> If a commit doesn't have the feature, then it is by definition, not\n> containing a broken feature, and you can simply use the \"good\" state.\n> There is no need for a different state. If you can't test the commit\n> because it's broken in some other way, you can use \"git bisect skip\"\n> but that isn't what you want in this case.\n\nCommits missing feature == 'good' commit is a very confusing one.\n\nLooks like in real life it happens much often, then git developers can\nimagine. For multi-branch/multi-feature workflow it's pretty easy not\nto recognize whether it is missing or not developed yet, especially on\nretrospective view where cherry-picking/squashing/merging is being\nused. My experience shows most annoying bugs are generating after a\nheavy merge (evil merge) with conflicts resolutions, where developer\nis not involved in the knowing what happens on counterpart changes.\nThen feature can be disappeared after it was worked & tested in its\nown branches.\n\n@Alex, I'm pretty interesting in fixing this weird bisect behaviour as\nwell, as far as I struggled on it last summer and continue struggling\nso far :) If you want we can join to your efforts on fixing.\n\nCheers, Oleg\n"},{"id":"312132","messageId":"xmqqy3x1jkuu.fsf@gitster.mtv.corp.google.com","threadId":"45167","inReplyTo":"CAP8UFD3ngMvVy2XLzYNn9OFbS+zQpWTW=pravpHhA-0PcDVhfg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-20T09:02:33Z","receivedAt":"2017-02-20T09:13:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> git bisect makes some assumptions that are true most of the time, so\n> in practice it works well most of the time.\n\nI think we need to clarify the documentation and ask you to stop\nusing such fuzzy phrases like \"assumptions\" and \"most of the time\"\n;-).\n\nFor bisection to work, \"git bisect\" requires a very simple thing,\nwhich is that your history is bisectable wrt one particular \"trait\",\ni.e. what you are interested in (e.g. the trait may be \"the commit\nhas this feature in a broken form\").\n\nWhat does it mean for a history to be \"bisectable\", then?\n\nA bisectable history has commits with the \"trait\" and commits\nwithout the \"trait\". Given any commit with the \"trait\", all commits\nthat are decendant of such commit must have the \"trait\". Also given\nany commit without the \"trait\", all commits that are ancestor of\nsuch a commit must not have the \"trait\".\n\nAnd your goal is to find one commit with the \"trait\" whose direct\nparent commits all lack the \"trait\".\n\nIf and only if you can formulate your problem into the above form,\n\"git bisect\" can help you by not requiring you to check each and\nevery commit in the history.\n\nDepending on the way you define the \"trait\", your history may not be\nbisectable, but by formulating the \"trait\" carefully, many such\nhistory can be made bisectable. In the \"Recently some commit broke\nfeature X. Before then the feature used to work. In an ancient\npast, the feature did not even exist\" example, if you set \"trying to\nuse feature X breaks\" as the \"trait\", your history is not bisectable\nunless you ignore the ancient part that did not even have the\nfeature. If you restate your \"trait\" to \"feature X does not exist\nin a broken form\", however, the history becomes bisectable.\n\nHistorically, we called commits with \"trait\" BAD and others GOOD,\nbecause bisection was used primarily to hunt for bugs. It may be\neasier to understand if the user thinks of commits without \"trait\"\nas OLD (i.e. commits in the older part of the history are not yet\ncontaminated), and commits with \"trait\" as NEW (i.e. at some point,\nthere is an event to introduce the \"trait\" and newer part of the\nhistory is contaminated by that event ever since).\n"},{"id":"312142","messageId":"58d25138-de2e-6995-444f-79c3ac0bbad2@gmail.com","threadId":"45167","inReplyTo":"CABEd3j8sgDd8DXW8+2Q7pjANPTr-Ws1Xs1ap875mkxFOfnenYw@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2017-02-20T12:27:23Z","receivedAt":"2017-02-20T12:27:41Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 20.02.2017 o 08:38, Oleg Taranenko pisze:\n\n>>>> Then you must adjust your definition of \"good\": All commits that do not have\n>>>> the feature, yet, are \"good\": since they do not have the feature in the\n>>>> first place, they cannot have the breakage that you found in the feature.\n>>>>\n>>>> That is exactly the situation in your original example! But you constructed\n>>>> the condition of goodness in such a simplistic way (depending on the\n>>>> presence of a string), that it was impossible to distinguish between \"does\n>>>> not have the feature at all\" and \"has the feature, but it is broken\".\n>>>\n>>> Johannes, thank you for correctly identifying the error in my logic.\n>>> Indeed I was using the term 'bad' also for the commit without the\n>>> feature. In order to find the commit introducing the bug in my example\n>>> a new state is needed, which would make 'git bisect' a bit more\n>>> complicated than the user 'most of the time' probably needs. Or do you\n>>> think, it would make sense to ask the user for this state (if e.g 'git\n>>> bisect' would be started with a new parameter)?\n> \n>> If a commit doesn't have the feature, then it is by definition, not\n>> containing a broken feature, and you can simply use the \"good\" state.\n>> There is no need for a different state. If you can't test the commit\n>> because it's broken in some other way, you can use \"git bisect skip\"\n>> but that isn't what you want in this case.\n> \n> Commits missing feature == 'good' commit is a very confusing one.\n\nNowadays you can change the names for 'old' and 'new' with\n`git bisect terms`. HTH.\n \n> Looks like in real life it happens much often, then git developers can\n> imagine. For multi-branch/multi-feature workflow it's pretty easy not\n> to recognize whether it is missing or not developed yet, especially on\n> retrospective view where cherry-picking/squashing/merging is being\n> used. My experience shows most annoying bugs are generating after a\n> heavy merge (evil merge) with conflicts resolutions, where developer\n> is not involved in the knowing what happens on counterpart changes.\n> Then feature can be disappeared after it was worked & tested in its\n> own branches.\n\nGood to know about this problem.\n\n> @Alex, I'm pretty interesting in fixing this weird bisect behaviour as\n> well, as far as I struggled on it last summer and continue struggling\n> so far :) If you want we can join to your efforts on fixing.\n\nAnyway, I don't think it is feasible to weaken the assumption that there\nis only one transition from 'old' ('good') to 'new' ('bad'); this is\nwhat allows O(log(N)) operations. See bisection method of root finding,\nthat is finding zeros of a continuous function.\n\nBest,\n-- \nJakub Narębski\n\n"},{"id":"312152","messageId":"CABEd3j8m5D=bBbUD+uzvE9c8AwdBEM79Np7Pnin-RLL=Hjq06A@mail.gmail.com","threadId":"45167","inReplyTo":"58d25138-de2e-6995-444f-79c3ac0bbad2@gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Oleg Taranenko","fromEmail":"olegtaranenko@gmail.com","sentAt":"2017-02-20T13:50:09Z","receivedAt":"2017-02-20T13:57:16Z","isPatch":false,"sender":{"key":"olegtaranenko@gmail.com","avatar":"https://gravatar.com/avatar/016106c4926412cef4141b2d7cea4378aef44db0ca56c9462a5f4a71c7a80955?d=mp&s=160"},"body":"> Anyway, I don't think it is feasible to weaken the assumption that there\n> is only one transition from 'old' ('good') to 'new' ('bad'); this is\n> what allows O(log(N)) operations. See bisection method of root finding,\n> that is finding zeros of a continuous function.\n\nI don't intended to change default behaviour of git bisect, I can\nestimate what drawback it could bring.\nI'd rather implement something like\n\ngit bisect start --bisect-strategy=missing-feature\n\nby default current state is being used.\n\ngit config value would be also useful.\n\nOleg\n"},{"id":"312165","messageId":"CAMX8fZUNHmouUsgEY3+0CmTaEp+y5b1-Cp8Nk3OttTc30v0R5A@mail.gmail.com","threadId":"45167","inReplyTo":"CABEd3j8m5D=bBbUD+uzvE9c8AwdBEM79Np7Pnin-RLL=Hjq06A@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-20T20:31:08Z","receivedAt":"2017-02-20T20:31:15Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"I see two different problems each with a different assumption (see the\ndefinition of \"bisectable\" in the email of Junio C Hamano):\n\n1. (Current) Assume the entire history graph is bisectable. DO: Search\nwhere in the entire graph the first 'trait'/transition occurs.\n2. (New) Assume only the graph between one good commit and one bad\ncommit is bisectable. DO: Search where the first transition occurs in\nthe graph between these two commits.\n\nIt seems that the real world needs a solution also for the second\nproblem (example if the good commit is the FIRST good commit of a\nfeature or if the good commit is not the first good commit, but you\ndefinitely know, that it broke first somewhere in between the good and\nbad commit).\n\nI find the way to go as Oleg proposed is gittish enough (with a new\nparameter --strategy). Beside I would underline that also the second\nproblem is a bisect problem, just for another graph, thus it makes\nperfect sense to extend 'git bisect' for this.\n\nDoes that look reasonably?\n"},{"id":"312167","messageId":"ca1ef8f6-58cf-4994-d1bf-39e04b42dd4c@gmail.com","threadId":"45167","inReplyTo":"CAMX8fZUNHmouUsgEY3+0CmTaEp+y5b1-Cp8Nk3OttTc30v0R5A@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2017-02-20T20:35:47Z","receivedAt":"2017-02-20T20:36:05Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 20.02.2017 o 21:31, Alex Hoffman pisze:\n> I see two different problems each with a different assumption (see the\n> definition of \"bisectable\" in the email of Junio C Hamano):\n> \n> 1. (Current) Assume the entire history graph is bisectable. DO: Search\n> where in the entire graph the first 'trait'/transition occurs.\n>\n> 2. (New) Assume only the graph between one good commit and one bad\n> commit is bisectable. DO: Search where the first transition occurs in\n> the graph between these two commits.\n\nIf `git bisect` is/would be affected by `git log` history-related options\nthen this is what `--strict-ancestor` option gives/would give.\n\n-- \nJakub Narębski\n\n"},{"id":"312168","messageId":"CAMX8fZUbZQiKF6aXa9BifU5vAwJ1wWR3CTUg70jUbjxahrGdAQ@mail.gmail.com","threadId":"45167","inReplyTo":"ca1ef8f6-58cf-4994-d1bf-39e04b42dd4c@gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-20T20:39:49Z","receivedAt":"2017-02-20T20:39:55Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"> If `git bisect` is/would be affected by `git log` history-related options\n> then this is what `--strict-ancestor` option gives/would give.\n\nExactly my thoughts. All that needs to be changed in the 2nd problem\nis the graph where to search.\n\nBut first we must agree about the usefulness of the 2nd problem. Any\nthoughts/comments/votes for/against?\n"},{"id":"312173","messageId":"4C20E99781EC4D6D82D48FBF9D9472A1@PhilipOakley","threadId":"45167","inReplyTo":"ca1ef8f6-58cf-4994-d1bf-39e04b42dd4c@gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2017-02-20T22:24:47Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Jakub Narębski\" \n>W dniu 20.02.2017 o 21:31, Alex Hoffman pisze:\n>> I see two different problems each with a different assumption (see the\n>> definition of \"bisectable\" in the email of Junio C Hamano):\n>>\n>> 1. (Current) Assume the entire history graph is bisectable. DO: Search\n>> where in the entire graph the first 'trait'/transition occurs.\n>>\n>> 2. (New) Assume only the graph between one good commit and one bad\n>> commit is bisectable. DO: Search where the first transition occurs in\n>> the graph between these two commits.\n>\n> If `git bisect` is/would be affected by `git log` history-related options\n> then this is what `--strict-ancestor` option gives/would give.\n>\nisn't that spelt `--ancestry-path` ?\n(--ancestry-path has it's own issues such as needing an --first-parent-show \noption, but that's possibly a by the by)\n--\nPhilip \n\n"},{"id":"312217","messageId":"CAMX8fZUR4h0T3hBmh6Z_0=f5LHFJetOi-vO_JJgnYPB7KjU_bg@mail.gmail.com","threadId":"45167","inReplyTo":"4C20E99781EC4D6D82D48FBF9D9472A1@PhilipOakley","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Alex Hoffman","fromEmail":"spec@gal.ro","sentAt":"2017-02-21T19:40:19Z","receivedAt":"2017-02-21T19:40:31Z","isPatch":false,"sender":{"key":"spec@gal.ro","avatar":null},"body":"> isn't that spelt `--ancestry-path` ?\n> (--ancestry-path has it's own issues such as needing an --first-parent-show\n> option, but that's possibly a by the by)\n\nIndeed it is spelled `--ancestry-path`. And interestingly enough you\nmay use it multiple times with the wanted effect in our case (e.g when\nthe user has multiple good commit and a single bad commit before\nrunning the bisect itself). Also it is `--first-parent` (not\n`--first-parent-show`), but I do not understand why do we need this\noption? What kind of issues does `--ancestry-path` have?\n\nBest regards,\nVG\n"},{"id":"312234","messageId":"2C3983FC41474DCC880C1E53149DFBE0@PhilipOakley","threadId":"45167","inReplyTo":"CAMX8fZUR4h0T3hBmh6Z_0=f5LHFJetOi-vO_JJgnYPB7KjU_bg@mail.gmail.com","subject":"Re: Git bisect does not find commit introducing the bug","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2017-02-21T22:40:06Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Alex Hoffman\" \n>> isn't that spelt `--ancestry-path` ?\n>> (--ancestry-path has it's own issues such as needing \n>> an --first-parent-show\n>> option, but that's possibly a by the by)\n>\n> Indeed it is spelled `--ancestry-path`. And interestingly enough you\n> may use it multiple times with the wanted effect in our case (e.g when\n> the user has multiple good commit and a single bad commit before\n> running the bisect itself).\n\n> Also it is `--first-parent` (not `--first-parent-show`),\n\nMy spelling was deliberate ;-)\n\nIf you use the currently coded --first-parent with a properly relevant \ncommit for --ancestry-path then you get nothing. The purpose of \nancestry-path is to find the ancestry chain that deviates from being a \nfirst-parent traversal [1], but the first-parent want to hold the walk to \njust the first parent chain - a contradiction.\n\nAdding the -show at the end is my attempt to indicate that it is for the \nsecond aspect, that of selecting which commits to show/use.\n\nI had an initial discussion back at [2], but failed then too.\n\n> but I do not understand why do we need this\n> option? What kind of issues does `--ancestry-path` have?\n>\n> Best regards,\n> VG\n>\n--\nPhilip\n\n[1] \\git\\Documentation\\technical\\api-revision-walking.txt [\"two \ndiff_options, one for path limiting, another for output\"]\n[2] \nhttps://public-inbox.org/git/2FA1998250474E76A386B82AD635E56A@PhilipOakley/ \n\n"}]}