On Mon, Mar 16, 2015 at 11:53:08AM -0700, Junio C Hamano wrote:
> Because the history is not linear in Git, bisection works by
> shrinking a subgraph of the history DAG that contains "yet to be
> tested, suspected to have introduced a badness" commits.  The
> subgraph is defined as anything reachable from _the_ "bad" commit
> (initially, the one you give to the command when you start) that are
> not reachable from any of the "good" commits.
> 
> Suppose you started from this graph.  Time flows left to right as
> usual.
> 
>   ---0---2---4---6---8---9
>       \             /
>        1---3---5---7
> 
> Then mark the initial good and bad commits as G and B.
> 
>   ---G---2---4---6---8---B
>       \             /
>        1---3---5---7
> 
> And imagine that you are asked to check 4, which turns out to be
> good.  We do not _move_ G to 4; we mark 4 as good, while keeping
> 0 also as good.
> 
>   ---G---2---G---6---8---B
>       \             /
>        1---3---5---7
> 
> And if you are next asked to check 5, and mark it as good, the graph
> will become like this:
> 
>   ---G---2---G---6---8---B
>       \             /
>        1---3---G---7
> 
> Of course, at this point, the subgraph of suspects are 6, 7, 8 and
> 9, and the subgraph no longer is affected by the fact that 0 is
> good.  But it is crucial to keep 0 marked as good in the step before
> this one, before you tested 5, as that is what allows us not having
> to test any ancestors of 0 at all.
> 
> Now, one may wonder why we need multiple "good" commits but we do
> not need multiple "bad" commits.  This comes from the nature of
> "bisection", which is a tool to find a _single_ breakage [*1*], and
> a fundamental assumption is that a breakage does not fix itself.
> 
> Hence, if you have a history that looks like this:
> 
> 
>    G...1---2---3---4---6---8---B
>                     \
>                      5---7---B
> 
> it follows that 4 must also be "bad".  It used to be good long time
> ago somewhere before 1, and somewhere along way on the history,
> there was a single breakage event that we are hunting for.  That
> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
> not explain why the tip of the upper branch is broken---its breakage
> has no way to propagate there.  The breakage must have happened at 4
> or before that commit.

But what if 7 & 8 are the same patch, cherry-picked?  Or nearly the same
patch, but with some conflict resolution?

Couldn't that lead to the case that 4, 5, and 6 are good, while 7 & 8
are bad?  Or does that violate the "single breakage" rule in a way that
might be too subtle for some users?

-- 
Scott Schmit