# What is the maximum number of steps to find a bug using bisecting?

Assume that a node A in the commit tree of a codebase contains a bug but some ancestor B of A is clean from that very bug. Given the topology of the commit tree [B,A] leading from B to A, can we predict c the maximum number of steps needed to locate the commit where the bug appeared, in terms of number of vertices, arrows, merges or cycles and other simple graph invariants?

There is two easy cases:

1. If the history from B to A is linear, then c is the binary logarithm of the number of nodes between B and A.

2. If the history is totally parallel, i.e. a family of independent commits A → Mᵢ → B, then c is the number of such commits.

From the two examples, we learn that linear history leads to cheaper bisection processes, but can we be more precise than this? It is easy to write a program to compute c – which I still haven't done yet – but I am looking for a pretty algebraic formula. If the problem is hard, it could be interesting and easier to have expected value of c given, for instance, the number of vertices, arrows and merges, or something similar.

• If I got this right, if you have 2 parallel commits, you may not be able to assign the bug to one of the commits - it is totally possible that the bug only results from the combination of the two. Commented Apr 26, 2015 at 16:47
• Commented Apr 26, 2015 at 23:45
• @DocBrown If you choose the wrong order, the bug can disappear and then reappear in the linear ordering. Bisect at its most basic works as a binary search; those intermediate "fixed" commits would make it go in the wrong direction if it landed on one of them, so I don't think the simplification works here Commented Apr 27, 2015 at 0:16
• @DocBrown This is awkward to do in comments, but if the commit tree is `A -> B -> D` and `A -> C -> D` (a diamond), and the bug is in `B` and `D`, then your arbitrary linearization cannot choose `A, B, C, D` and still work - even though `B` and `C` are still independent Commented Apr 27, 2015 at 23:21
• @Izkata: That depends on how commits are stored in the SCM system. If they are stored as snapshots, then your objections are valid. But if they are stored as differences, then the linearisation `A, B, C, D` would have the bug also show up in `C'` (the snapshot created by applying differences `B` and `C` to the snapshot at `A`). Commented Apr 28, 2015 at 5:30

Files in various code versioning systems typically gain bugs at one commit and remain bugged until they are fixed in another commit. This is because there are two popular methods for using versioning: file locks and merges. In the case of a file lock, developers lock files they're working on so nobody else can make changes. After unlocking, the other developers must then checkout the same file, ensuring that those changes won't be lost.

In a merging code versioning system, the main branch stores all of the commits from all branches merged into it, creating a linear history. This usually works on the concepts of diffs/patches, meaning that a commit that introduces a bug from one branch won't be automatically wiped out from a commit in another branch that is merged in later. In some rare cases, conflicts occur, and then a manual resolution is required. Bugs usually survive such merges, too, so they still appear continuously through the master branch's timeline.

No matter how many branches or developers you have working on a project, you can practically guarantee that simply by identifying the last known good commit before the bug, and last known bad commit for a bug (usually the current ref position), you can clearly isolate the commit that caused the bug, no matter which branch it occurred in. This is a side-effect of the linear nature of the logs and how they integrate to the main branch.

You can always identify the maximum search time for finding a bug by counting the number of commits from the last known good to the last known bad commit, and finding log2(x). You can often search an entire repository's history for a bug in well less than 20 iterations (16,000 commits, for example, is just 14 iterations). If you know the release a bug appeared in, that's usually in the order of about 5-10 iterations (your mileage may vary).

I only have experience with SVN and Git, but it's clear that any system that uses something better than "zip all the files in the repo into a hidden commit folder" (e.g. using literal file system snapshots) should have roughly the same logarithmic performance for finding bugs. There will always be just one linear log that needs to be read, ignoring all branches, even those that were later discarded or rebased, because the timeline will always appear linear.

For a crazy example, take a look at this image:

In this image, they show how Git works. And while Git is doing the job it was given, this is not a pretty sight. However, you'll notice how each commit nicely lines up linearly, despite merging from a ton of different branches at different times. Of course, there are tools to fix this history so its legible again (for example, this article about how they ended up in that mess).

The point is, the versioning system will keep things straight for you, so a simple binary search in a simple linear history is really all that's required.

• Can you clarify “so a linear search is really all that's required” ? It seems that you mean that each case can be replaced (for bisecting purposes) by an equivalent linear case, which is wrong. Commented May 21, 2015 at 11:48
• You're right. I meant to say that a simple binary search along a linear history is ask that's required to find bugs. Edited. Commented May 21, 2015 at 13:48