> At the end of the git-bisect man page (in the SEE ALSO section) there > is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt > which has a lot of details about how bisect works. > Thanks for pointing out the SEE ALSO section. I think it makes sense to include/describe the entire algorithm in the man page itself, although I am not sure whether the graphs would be always correctly visually represented in the man page format. > The goal is to find the first bad commit, which is a commit that has > only good parents. OK, bisect's mission is more exact than I thought, which is good. M > As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm. > If it was bad, it would means that there is a transition from bad to > good between o1 and G. > But when a good commit is an ancestor of the bad commit, git bisect > makes the assumption that there is no transition from bad to good in > the graph. The assumption that there is no transition from bad to good in the graph did not hold in my example and it does not hold when a feature was recently introduced and gets broken relative shortly afterwards. But I consider it is easy to change the algorithm not to assume, but rather to check it. > git bisect makes some assumptions that are true most of the time, so > in practice it works well most of the time. Whatever the definition of "most of the time" everyone might have, I think there is room for improvement. Below I am trying to make a small change to the current algorithm in order to deal with the assumption that sometimes does not hold (e.g in my example), by explicitly validating the check. > --o1--o2--o3--G--X1 > \ \ > x1--x2--x3--x4--X2--B-- > \ / > y1--y2--y3 Step 1a. (Unchanged) keep only the commits that: a) are ancestor of the "bad" commit (including the "bad" commit itself), b) are not ancestor of a "good" commit (excluding the "good" commits). The following graph results: x1--x2--x3--x4--X2--B-- \ / y1--y2--y3 Step 1b. (New) Mark all root commits of the resulting graph (i.e commits without parents) as unconfirmed (unconfirmed=node that has only bad parents). Remove all root commits that user already confirmed (e.g if user already marked its parent as good right before starting bisect run). For every unconfirmed root commit check if it has any good parents. In the example above check whether x1 has good parents. If the current root element has any parents and none of them is good, we can delete all paths from it until to the next commit that has a parent in the ancestors of GOOD. In the example above to delete the path x1-x3 and x1-y3. Also add new resulting root commits to the list of unconfirmed commits (commit x4). Otherwise mark it as confirmed. Step2. Continue the existing algorithm. If this improvement works (i.e you do not find any bugs in it and it is feasible to implement, which seems to me) the following would be its advantages: 1. An assumption less, as we explicitly check the assumption. 2. It might be quicker, because we delete parts of graph that cannot contain transitions. 3. It returns more exact results. VG