Re: bisect-helper: we do not bisect --objects
- Date: Fri, 03 Mar 2017 15:51:58 -0800
- From: Junio C Hamano <gitster@xxxxxxxxx>
- Subject: Re: bisect-helper: we do not bisect --objects
"Philip Oakley" <philipoakley@xxxxxxx> 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.