Re: bisect-helper: we do not bisect --objects

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 3, 2017, 23:51 UTC
Message-ID: <xmqqd1dx7wbl.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <D9E30A61FAC84D3B90981B388C9699D0@PhilipOakley>

"Philip Oakley" <philipoakley@iee.org> writes:

> Bikeshedding: If the given boundary is a tag, it could be tagging a
> blob or tree rather than a commit. Would that be a scenario that
> reaches this part of the code?

I do not think it is relevant.

Bisection is an operation over a "bisectable" commit DAG, where commits can be partitioned into "new" (aka "bad") and "old" (aka "good") camp, all descendants of a "new" commit are all "new", all ancestors of an "old" commit are all "old". Think of the "new"-ness as a 100% inheritable disease that happens spontaneously and without cure. Once you are infected with "new"-ness, all your descendants are forever "new". If you know you are free of the "new"-ness, you know that all your ancestors are not with the "new"-ness, either.

The goal of the operation is to find a "new" commit whose parents are all "old".

The bisectability of the commit DAG is what allows you to say "this commit is new" to a commit somewhere in the middle of the history and avoid having to test any descendants, as they all inherit the "new"-ness from it (similarly when you have one commit that is "old", you do not have to test any ancestor), thereby reducing the number of test from N (all commits in good..bad range) to log(N).

There is no room for a tree or a blob to participate in this graph partitioning problem. A "bad" tree that is "new" cannot infect its children with the "new"-ness and a "good" tree cannot guarantee the lack of "new"-ness of its parents, because a tree or a blob does not have parent or child commits.