The sound distributed version control system

#452 [FEATURE REQUEST] Pijul equivalent to `git bisect`

Opened by quickdudley on June 13, 2021 Feature request
quickdudley on June 13, 2021

The canonical use case of git bisect is finding which commit introduced a particular bug, which it does by performing a modified binary search. We probably don’t want the same algorithm in Pijul due to the state being a set of changes rather than a single commit, but it would be nice to have a semi-automated way to track down which change or minimal set of changes introduced some property (such as a bug) to a repository.

I’d be happy to try implementing this myself but might need some guidance on how to store data used by the subcommand.

quickdudley on June 14, 2021

I think I’ve figured out the basic algorithm: in the situation where we can test any state for the property of interest it would be O(log(n) ^ r) where n is the number of changes in the channel being inspected and r is the number of changes in the set which gives rise to the property of interest. In most cases r would be 1; but software bugs originating from interactions between 2 or 3 different changes probably aren’t uncommon.


I have thought of a scenario where not only the algorithm I’d thought of would fail but the thing it’s meant to find needs a more general definition. I’ll spec it out over the next few days and then try thinking of an algorithm using that.

pmeunier on August 3, 2021

This is a duplicate of #126, but I’ll close #126 in favour of this, since an algorithm for this would be cool. A potential algorithm for this could look at the DAG of dependencies, and use cuts of that graph as bisections.

You might also want to talk to the authors of the following internship proposal (for last year, the internship already happened):

pmeunier added tag Feature request on December 7, 2021