Bisection testing using Quilt

Having produced a nice little series of 124 patches (yes, really), I recently had to find out what patch introduced a problem for distcheck to pass. Since distcheck takes quite some time to execute, I want to make as few runs as possible.

In Git, there is the bisect command that can be used to perform bisection testing of a series of patches, but quilt does not have anything like that, so to simplify my job, I needed to implement that for quilt.

I started by defining a shell function that did the actual test, and returned the result.

do_test () {
    echo -n "running distcheck..."
    make -j6 distcheck >/dev/null 2>&1
}

After that, I added code to add values for some variables used and to process options to the script. The script supports two options: --lower and --upper. Both accept a number of a patch: the lowest patch that was good and the number of the last known patch to fail the test. I could have supplied the patch names here, but this was good enough for my purposes.

Note that I am using Bash since it has support.

series=(`quilt series`)                  # Array of the patch names
lower=0                                  # Lowest item in tested range
upper=$((${#series[@]} - 1))             # Upper limit of range

while true; do
    case "$1" in
        -l|--lower)
            lower="$1"
            shift
            ;;
        -u|--upper)
            upper="$1"
            shift
            ;;
        *)
            shift
            break
            ;;
    esac
done

middle=$(($lower + ($upper - $lower) / 2))

Then we start by preparing the looping by moving to the middle of the patches in the range.

quilt pop -a >/dev/null
quilt push $middle >/dev/null

The main loop will keep pushing or popping depending on whether the current patch fails the test or succeeds. The invariant for the loop is that that $middle holds the number of the current patch to be tested (the patch that quilt top would report) and we keep looping until $lower == $upper. Just to ensure that the right patch is tested, we test the invariant in the loop.

• If the test succeeds, we know that the first failing test is somewhere between this patch and the last known failing test. So, we compute the next midpoint to be between this patch and the last known unsuccessful patch and store it in middle. We then push patches to reach this patch.
• If the test fails, we know that the first failing test is somewhere between the current patch and the last known successful patch. So, we compute the next midpoint to be between this patch and the last successful patch and store it in middle. We then pop patches to reach this patch.

while test $lower -lt $upper
do
    top=`quilt top`
    echo -n "$top..."

    if test "$top" != "${series[$(($middle-1))]}"; then
        echo "invariant failed ($top != ${series[$(($middle-1))]})!" 1>&2
        exit 2
    fi

    if do_test $lower $upper; then
        lower=$(($middle + 1))
        middle=$(($lower + ($upper - $lower) / 2))
        cnt=$(($middle - $lower + 1))
        echo -n "succeeded..."
        if test $cnt -gt 0; then
            echo -n "pushing $cnt patches..."
            quilt push $cnt >/dev/null
            echo "done"
        fi
    else
        upper=$middle
        middle=$(($lower + ($upper - $lower) / 2))
        cnt=$(($upper - $middle))
        echo -n "failed..."
        if test $cnt -gt 0; then
            echo -n "popping $cnt patches..."
            quilt pop $cnt >/dev/null
            echo "done"
        fi
    fi
done

Next task: extend quilt to support the bisect command.