Re: git bisect for reachable commits only

From: Stefan Beller <sbeller@google.com>
Date: Aug 2, 2016, 17:25 UTC
Message-ID: <CAGZ79kbx-eq=NPMYon5MV_T5cqiFmcZ_F6zGQO5p7mgLg8bQ4A@mail.gmail.com>
In-Reply-To: <CABEd3j_6DNgs1u5AdkkzWt7U=J2fZ4a-2jewVjkfExt0KPvWiQ@mail.gmail.com>

On Tue, Aug 2, 2016 at 3:15 AM, Oleg Taranenko <olegtaranenko@gmail.com> wrote:

Show 10 quoted lines

> Guys,
>
> thanks for discussion, I will try to reply in bulk here.
> First, assuming the common ancestor is GOOD based on the fact that
> some descendant given as GOOD is pretty bad idea.
> It may be, but may not be. In the git-flow like workflows new features
> (aka branches) are created from trunk (master/develop/...)
> sporadically,
> but later they will mutual merging. I would say more probably they
> have not common base, then have.

git bisect has the underlying assumption that the BUG is not there initially and introduced by one specific commit, and continues to be there until B. With this assumption you can do a binary search, which allows searching in O(log n), which is optimal for the number of iterations needed.

Show 14 quoted lines

>
> Second, I don't ask "create a new algorithm to find all transition
> from good/old to bad/new", not nesessary. If programmer feels
> something
> suspicious, he/she can create another bisect session with narrowed commit range.
>
> Third, testing of any specific commit can be very expensive operation.
> In my case - shutdown servers/refresh dbs/clean/rebuild in
> eclipse/running servers/dropping browser cache/running app in
> browser/going through some pages/view UI.
> Some of steps of course are automated, but some not. Anyway I spend
> 5-10 min for every iteration. So knowing what commit is bad or good is
> very valuable, then I'm very interested to hunt the bug-introduced
> commit with minimal count of testing.

As you point out each iteration is a burden to the user, so they should be kept to a minimum.

Show 19 quoted lines

>
> Scenario 4 (I will keep my previous mail numbering for possible later reference)
>                  z1----z2---z3
>                 /     /      \
>     G----x1----x2----/---x3---x4--B
>           \         /   /
>            y1--y2--y3--y4
>
> This is the happy straight case with closed DAG (hehe, git for
> scientists) between given G good and B bad commits.
> Ideal bisect will check first the shortest way between G & B:
> x1/x2/x3/x4. Let name first-bug commit we are really hunting H and
> current first-bug candidate as h.
> If h == x1 or x2 -> stop, found
> If h == x3, bisect will try to test y2/y3/y4 path only
> If h == x4, bisect will select shortest path z1/z2 (keeping in mind,
> that x2 is already tested and is good)
>   If h == z1 - found
>   if h == z2 - looking in path y1/y2/y3

* git is agnostic of the workflow, i.e. it doesn't know the notion of
topic branches or such.
* What is the worst case in you strategy?
  (h=y4 means 7 tests by the user IIUC)

Given the assumptions as laid out above such that we are able to do a binary search, the ideal candidate for scenario 4 is y4 or z3 as these split the set of commits to be investigated into 2 equally sized sets of ancestors and non-ancestors.

When a specific workflow is given, it may make sense to weight commits differently. Also some people asked for a strategy that only checks merge commits first, as there are far fewer merge commits and these generally are used for introducing a new feature or refactoring.