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
<<attachment: smime.p7s>>