Web lists-archives.com

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.