Fossil Forum

When bisecting, you start with two commits: one is known to be "bad" — that is, it exposes the problem to be solved by bisecting, — and one is known to be "good", that is, it does not expose the problem.

The "bad" commit is usually known up front, and the "good" one is picked up empirically.

Now you have a subgraph of the commits between these two: that is, you can start with the "bad" commit and then traverse all the edges of that subgraph formed by the parent-child relationships between commits, and eventually arrive at the "good" commit. Note that there may be more than a single path through that subgraph.

Now the "bisecting" part. "Bi" stands for "two", and bisecting is literally splitting some set into two parts. So, how it works:

1. Take "bad" and "good" commits. Arbitrarily select some commit "in the middle" between these two.
2. Run a test on it (more on this below) to classify it either as good or as bad.
3. If the commit is good, you have a new, narrower, set, so go to 1.
4. If the commit is bad, you, again, have a new, narrower, set — just shrunk from the opposite side.
5. Repeat the process until you have a single bad commit, while all its parent commits are good: this makes you sure that very commit had introduced a bug.

Note that since there may be multiple paths between the initial good and bad commits through the subgraph they sit on, you need to apply the algorythm outlined above to all these paths.

As to testing — in its simplest form, bisecting engine checks out the commit to be tested and then asks the user to run whatever tests they have which expose the bug, and then tell the engine what was the outcome, at which point it takes note of that and resumes the process. Z c960fe52a

I can't tell what you are looking for.

Are you unfamiliar with walking a version tree/graph at all and don't know how bisection works. If this is your question:

https://en.wikipedia.org/wiki/Bisection_(software_engineering)

may help.

Do you know how bisection works and are looking for the details on how fossil walks the graph and chooses from one of possibly multiple paths through the version tree?

You should also support reversing the "good" and "bad" roles, to allow searching for where a bug was fixed rather than where it was introduced.

What use cases would this have? And how would this work conceptually in code?

I implemented git bisect from pseudocode in a research paper I saw:

1. Remove from D all non-ancestors of b.
2. If D has only one vertex, return this vertex.
3. Compute the score for each vertex of D.
4. Query the vertex with the maximum score. If there are several vertices which have the maximum score, select any one then query it.
5. If the queried vertex is bugged, remove from D all non-ancestors of the queried vertex. Otherwise, remove from D all ancestors of the queried vertex.
6. Go to Step 2.

Would I check if the commits marked as bad come before the ones marked as good, and then invert the DAG before bisecting?

What if there are good commits, then bad commits after those, but then more good commits after the bad ones? What happens then?

I eventually managed to implement the bisecting algorithm used by git from some pseudocode in a research paper online, so all is well with what I was originally requesting.

I was looking for how a bisect would actually take place in code. I knew that it tries to equally divide a graph in half by picking some node that has an equal number of ancestors and descendants, checking it, and then excluding ancestors if it's good and descendants if it's bad.