Re: Feature request: Exponential search in git bisect

[Philip Oakley <philipoakley@iee.email>]

Hi Manuel,

On 10/10/2020 10:22, Christian Couder wrote:
> On Fri, Oct 9, 2020 at 9:35 PM Manuel Bärenz <manuel@enigmage.de> wrote:
>> This feature was requested 8 years ago and briefly discussed:
>> https://public-inbox.org/git/20120318212957.GS1219@chaosreigns.com/
>>
>>
>>   TL;DR
>>
>> Before doing git bisect, I want to use exponential search to
>> automatically find a good commit, in logarithmic time.
> Ok, but the conclusion of the above discussion is that the problem
> with this idea is being able to distinguish between a commit that is
> bad and a commit where the feature that you want to test cannot be
> tested for example because it hasn't been implemented yet.

Does any of the proposed improvement in the "bisect: loosen halfway()
check for a large number of commits"
https://lore.kernel.org/git/20201022103806.26680-1-szeder.dev@gmail.com/
assist in this.

Or is the problem still with the need for a three way test that shows
Too_Old / Good / Bad ?

>
>>   Scenario
>>
>>   * I have a bug in HEAD.
>>   * I strongly suspect that it was introduced some time ago, but I don't
>>     know when exactly.
>>   * I have an automated test that will find the bug if the test can run
>>     properly.
>>   * Most of the commits in the repository are not testable, i.e. the
>>     test doesn't run properly. (E.g. because the feature it tests wasn't
>>     introduced yet, refactoring, etc.)
>>   * I have no idea what a good commit might be, because I don't know
>>     when the first /testable/ good commit is.
> Ok, so your test cannot distinguish between a bad commit and a commit
> where the feature hasn't been implemented.
>
> When you say that most of the commits in the repository are not
> testable, it usually means that the feature has been implemented
> relatively recently compared to the history of the project.
>
>> This sounds like a standard application for git bisect. No matter how
>> big the repo, with binary search we would expect to find the first bad
>> commit in logarithmic time.
> Not necessarily. If you cannot distinguish in any way between a bad
> commit and a commit where the feature hasn't been implemented, then it
> might be very difficult to find a good commit. And you need a good
> commit before you can properly bisect.
>
> Suppose for example that the first bad commit (the commit that
> introduced the bug you are looking for) is a direct child of the
> commit that introduced the feature. Then unless you are very lucky any
> binary search using your script will only test either bad commits or
> commits where the feature hasn't been implemented yet, and it is
> unable to distinguish between them in your scenario.
>
>>   Failed attempt
>>
>> The zeroth idea might be trying to find the good commit by hand, by
>> reading changelogs, by trying some commits, whatever. In some
>> situations, this is not feasible. In fact, such situations occur
>> frequently for me, for example for undocumented features, unversioned
>> rolling releases, incidental complexity leading to older commits not
>> being testable, etc.
> I understand that it's not always easy to find a good commit.
>
>> The first idea that comes to mind - and it was recommended 8 years agos,
>> and I've tried it a few times already - is to simply mark the root
>> commit as good. (Now, there might be several roots, but that's a puzzle
>> you typically only have to figure out once per repo.) This sounds great
>> in theory because binary search should get through the good old commits
>> in logarithmic time.
> It is not necessarily a good idea to do that. And in the thread, what
> was actually suggested by Peff (Jeff King) was to test released
> versions (for example 1.6.0, 1.7.0, etc in the Git code base).
>
>> The problem with this approach is that if most older commits are
>> untestable, I have to git bisect skip them.
> Skipping untestable commits is not always the right thing to do. If
> you know that they are untestable because the feature has not been
> implemented yet, it might be better to mark them as good instead.
>
> This is by the way what an ideal script should do. It should mark
> commits where the feature has not been implemented yet as good, and
> should "skip" only the commits where the feature has already been
> implemented but that are not testable for another reason, like another
> "temporary" bug or "temporary" compile failures.
>
>> This basically kills the
>> logarithmic performance, because bisect skip doesn't do binary search,
>> but something rather random.
> I would say that the actual reason here is that bisect skip is used
> when it shouldn't be used.
>
>> Just yesterday I killed a bisect search
>> that took hours because it kept skipping and didn't find actual good
>> commits.
> Ok.
>
>> You might say that instead of skipping old commits, one should mark them
>> as good.
> Yes, they should be marked as good when the feature has not been
> implemented yet.
>
>> That's problematic because then I might accidentally mark a
>> commit as good that was already untestable bad. Given that bisect has no
>> undo functionality, that can quickly mess up my search. Distinguishing
>> untestable good from untestable bad is really hard automatically. I
>> shouldn't have to do that.
> Sometimes it's not very difficult to test if the feature has been
> implemented yet or not. For example with Git you could check if an
> option for a command has been implemented by just checking if it
> appears in the doc. So the bisection script could first check that and
> exit 0 (which means good) if the option doesn't appear in the doc. If
> it appears in the doc, then it could do the regular test: "skip" if
> untestable, "good" if there is no bug, "bad" otherwise.
>
>> Long story short: Going from the root commit typically isn't feasible.
>> I've tried it.
> It seems that you might not have tried in the best possible way.
>
>>   Proposal: Exponential search
>>
>> Instead of going from the root commit, what I do manually before
>> starting git bisect is this:
>>
>> git checkout HEAD~10
>> ./test.sh # Says: "Bug is present"
>> git checkout HEAD~20
>> ./test.sh # Says: "Bug is still present"
>> git checkout HEAD~40
>> ./test.sh # Says: "Bug is still present"
>> [...] # Proceed exponentially
>> git checkout HEAD~640
>> ./test.sh # Says: "Bug is GONE!"
>> git bisect good
> If your script cannot distinguish between a bad commit and a commit
> where the feature hasn't been implemented, then you were lucky that
> that HEAD~640 was good. If the feature had been introduced between
> HEAD~639 and HEAD~321 then your script would have said  "Bug is still
> present".
>
>> This technique is known as
>> https://en.wikipedia.org/wiki/Exponential_search, and it works very well
>> in practice. I find a good commit long before I enter the "untestable
>> good" region.
> If you are lucky, yes, you find a good commit long before you enter
> the "untestable good" region.
>
>> But it's tedious to do this manually. In this example, I
>> needed to run the script 8 times manually, but of course it can be more
>> often, and compiling and running the test may take time. This is ok for
>> a one-off search, but it's tedious for regular usages.
>>
>> Yes, I could wrap this up in a shell script, but I guess there are
>> caveats that I didn't think of when the history isn't linear. Maybe
>> someone even already has, and I'm unaware of that. But it feels like
>> this could be a proper git bisect feature, and a very useful one.
> I agree that it could be useful. It could be especially useful if
> people have a script that can actually distinguish between a bad
> commit and a commit where the feature hasn't been implemented.
>
> So if someone plans to implement that in Git, particular care in the
> documentation should be taken to explain the issues related to testing
> a feature when it might not be implemented yet.