Regression finding via bzr bisection (with application to a cc-mode bug)

[Daniel Colascione]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been frustrated by a cc-mode bug, and had no idea where to look in
order to fix it. So, I wrote a bisection tool that will find bugs
automatically called, imaginatively, emacs-bisect.

To use the program, you'll need a bzr checkout and a rough idea of when
the bug appeared. Below is a typescript that demonstrates how to use the
program. Its usage information has more details.

The cc-mode bug I was looking for manifests itself by raising an error
after typing a '>' in a cpp macro. In batch mode, that will make Emacs
exit with a non-zero status. Here's my test.el:

(message "Testing cc-mode insertion bug")
(with-temp-buffer
  "test"
  (c++-mode)
  (insert "#include <foo>"))

(By the way: the program assumes revision numbers within a branch are
monotonically increasing. Can a bzr expert tell me whether that's a
valid assumption?)

Usage example:

~/software/emacs$ time MAKE='make -j2' CC='ccache cc' ./emacs-bisect -t foo 
test.el 'date:2009-12-01'
emacs-bisect: high revision is 99342 (2010-01-16 10:40:57 +0100)
emacs-bisect: building revision 99342 (2010-01-16 10:40:57 +0100)
emacs-bisect: good: bug present in revision 99342 (2010-01-16 10:40:57 +0100)
emacs-bisect: low revision is 98887 (2009-12-01 07:07:13 +0000)
emacs-bisect: building revision 98887 (2009-12-01 07:07:13 +0000)
emacs-bisect: good: bug not present in revision 98887 (2009-12-01 07:07:13 
+0000)
emacs-bisect: examining revisions 98887 - 99342:  455 revisions
emacs-bisect:     --> 98887 (2009-12-01 07:07:13 +0000) - 99342 (2010-01-16 
10:40:57 +0100)
emacs-bisect: building revision 99114 (2009-12-14 06:39:39 +0000)
emacs-bisect: testing 99114 (2009-12-14 06:39:39 +0000)...
emacs-bisect: bug present in 99114 (2009-12-14 06:39:39 +0000)
emacs-bisect: examining revisions 98887 - 99114:  227 revisions
emacs-bisect:     --> 98887 (2009-12-01 07:07:13 +0000) - 99114 (2009-12-14 
06:39:39 +0000)
emacs-bisect: building revision 99000 (2009-12-06 15:33:09 +0000)
emacs-bisect: testing 99000 (2009-12-06 15:33:09 +0000)...
emacs-bisect: bug present in 99000 (2009-12-06 15:33:09 +0000)
emacs-bisect: examining revisions 98887 - 99000:  113 revisions
emacs-bisect:     --> 98887 (2009-12-01 07:07:13 +0000) - 99000 (2009-12-06 
15:33:09 +0000)
emacs-bisect: building revision 98943 (2009-12-03 19:12:52 +0000)
emacs-bisect: testing 98943 (2009-12-03 19:12:52 +0000)...
emacs-bisect: bug present in 98943 (2009-12-03 19:12:52 +0000)
emacs-bisect: examining revisions 98887 - 98943:  56 revisions
emacs-bisect:     --> 98887 (2009-12-01 07:07:13 +0000) - 98943 (2009-12-03 
19:12:52 +0000)
emacs-bisect: building revision 98915 (2009-12-02 03:05:14 +0000)
emacs-bisect: testing 98915 (2009-12-02 03:05:14 +0000)...
emacs-bisect: bug not present in revision 98915 (2009-12-02 03:05:14 +0000)
emacs-bisect: examining revisions 98915 - 98943:  28 revisions
emacs-bisect:     --> 98915 (2009-12-02 03:05:14 +0000) - 98943 (2009-12-03 
19:12:52 +0000)
emacs-bisect: building revision 98929 (2009-12-03 05:41:17 +0000)
emacs-bisect: testing 98929 (2009-12-03 05:41:17 +0000)...
emacs-bisect: bug not present in revision 98929 (2009-12-03 05:41:17 +0000)
emacs-bisect: examining revisions 98929 - 98943:  14 revisions
emacs-bisect:     --> 98929 (2009-12-03 05:41:17 +0000) - 98943 (2009-12-03 
19:12:52 +0000)
emacs-bisect: building revision 98936 (2009-12-03 14:34:04 +0000)
emacs-bisect: testing 98936 (2009-12-03 14:34:04 +0000)...
emacs-bisect: bug not present in revision 98936 (2009-12-03 14:34:04 +0000)
emacs-bisect: examining revisions 98936 - 98943:  7 revisions
emacs-bisect:     --> 98936 (2009-12-03 14:34:04 +0000) - 98943 (2009-12-03 
19:12:52 +0000)
emacs-bisect: building revision 98939 (2009-12-03 16:02:10 +0000)
emacs-bisect: testing 98939 (2009-12-03 16:02:10 +0000)...
emacs-bisect: bug present in 98939 (2009-12-03 16:02:10 +0000)
emacs-bisect: examining revisions 98936 - 98939:  3 revisions
emacs-bisect:     --> 98936 (2009-12-03 14:34:04 +0000) - 98939 (2009-12-03 
16:02:10 +0000)
emacs-bisect: building revision 98937 (2009-12-03 15:52:37 +0000)
emacs-bisect: testing 98937 (2009-12-03 15:52:37 +0000)...
emacs-bisect: bug not present in revision 98937 (2009-12-03 15:52:37 +0000)
emacs-bisect: examining revisions 98937 - 98939:  2 revisions
emacs-bisect:     --> 98937 (2009-12-03 15:52:37 +0000) - 98939 (2009-12-03 
16:02:10 +0000)
emacs-bisect: building revision 98938 (2009-12-03 15:56:29 +0000)
emacs-bisect: testing 98938 (2009-12-03 15:56:29 +0000)...
emacs-bisect: bug not present in revision 98938 (2009-12-03 15:56:29 +0000)
emacs-bisect: examining revisions 98938 - 98939:  1 revisions
emacs-bisect:     --> 98938 (2009-12-03 15:56:29 +0000) - 98939 (2009-12-03 
16:02:10 +0000)
emacs-bisect: DONE: bug was introduced between revisions 98938 (2009-12-03 
15:56:29 +0000) and 98939 (2009-12-03 16:02:10 +0000)

real    17m21.698s
user    8m46.602s
sys     4m21.798s


Program:

#!/bin/bash
set -e

##########
#
# Automated bug detection for Emacs using bisection from bzr repositories.
#
# See usage message for details.
#
##########

############
# Globals

declare BZR=bzr
declare LOG="$PWD/emacs-bisect.log"

if [[ -z $MAKE ]]; then
    declare MAKE='make'
fi

# Temporary branch name
declare tmp='bisect-tmp'

# Parent branch name
declare parent='trunk'

# Name of file containing elisp test code
declare test=

# If true, the build itself is the test
declare buildonly=0

# Current revision number, date, and human-readable description
declare current_revno=
declare current_devdate=
declare current_revdesc=

# whether the current checkout is built
declare built=0

# Whether we actually do cleanup on exit
declare do_cleanup=1

# If true, always build a fully bootstrapped and byte-compiled
# Emacs before testing
declare fullbuild=0

# where user-visible messages go
declare msgfd=2

# internal tempory directory
declare tmpdir=$(mktemp -d -t emacs-bisect)

###########
# Code


msg() {
    echo >&$msgfd "$(basename $0): $*"
}

err() {
    local help=0
    local usage=0

    if [[ $1 = '-h' ]]; then
        help=1
        shift
    fi

    if [[ $1 = '-u' ]]; then
        usage=1
        shift
    fi

    if [[ -n $1 ]]; then
        msg "$1"
    fi

    if ((usage)); then
        cat >&$msgfd <<EOF
$(basename $0) [-df] [-b BRANCH] [-t TMP] TEST LOW [HIGH]: find a bug
EOF
    fi

    if ((help)); then
cat >&$msgfd <<EOF
Locates a bug by running a binary search on a branch's history.

TEST is the name of an elisp file loaded into Emacs running in batch
mode. The bug is considered to be present if and only if emacs exits
with a non-zero status.

If, however, TEST is the word "build-only", then the build itself is
the test. That is, the bug is considered to be present iff the build
succeeds, and $(basename $0) detects the revision that broke the
build.

LOW and HIGH are the bounds of the search range, and are arbitrary
revision specifications and can be revision numbers, dates, or strings
like 'date:yesterday'. See 'bzr help revisionspec' for details.

HIGH defaults to the latest revision.

$(basename $0) records all commands executed and their output to
emacs-bisect.log in the current directory.

Flags:

- -d: is given, don't clean up the temporary branch directory on exit.

- -f: normally, $(basename $0) only performs an Emacs bootstrap and not
    a full build. It's wasteful to byte-compile everything for just one
    run of Emacs. If -f is supplied, always perform a full build.

- -b BRANCH: specify the branch that the bisection is run against.
    Defaults to 'trunk'.

- -t TMP: use this directory as the name of the temporary branch.
    Defaults to 'bisect-tmp'.

EOF
    fi
    exit 1
}

# Based on the currently check out revision, set current_revno,
# current_revdate, and current_revdesc by side effect.
update_revstate() {
    current_revno=$($BZR version-info "$tmp" | sed -ne 's/^revno: //p')
    current_revdate=$($BZR version-info "$tmp" | sed -ne 's/^date: //p')
    current_revdesc="$current_revno ($current_revdate)"
}

# Check out revision $1 (which can be an arbitrary revision
# specification), overwriting the previous one and resetting the
# state.
checkout() {
    local rev=$1
    shift

    if ! [[ $current_revno = $rev ]]; then
        rm -rf "$tmp"
        (( built = 0 ))
        #msg "checking out revision $rev"
        ( set -x
            exec $BZR branch --stacked --revision \
                "$rev" "$parent" "$tmp"; )
        update_revstate
    fi
}

cleanup() {
    trap '' SIGINT # Ignore overzealous control-c

    if (( do_cleanup )); then
        rm -rf "$tmp"
    fi

    if [[ -n $tmpdir ]]; then
        rm -rf "$tmpdir"
    fi
}

# Builds emacs. Update built status by side effect.
build_emacs() {
    pushd "$tmp"

    msg "building revision $current_revdesc"

    if ! ( set -x; exec ./configure --without-x ); then
        return 1
    fi

    # Just running 'temacs' doesn't seem to work this decade?
    if (( fullbuild )); then
        if ! ( set -x; exec $MAKE ); then
            return 1
        fi
    else
        if ! ( set -x; exec $MAKE -C src bootstrap-emacs ); then
            return 1
        fi
    fi

    popd
    (( built = 1 ))
}

# Is the currently checked-out revision suitable testing? Succeeds if
# it is, fails otherwise. Builds emacs by side effect.
is_feasible_rev() {
    if [[ $test = 'build-only' ]]; then
        return 0
    fi

    if (( ! built )); then
        build_emacs
    fi

    return 0
}

# Is the bug contained in the current revision?
is_good_rev() {
    if [[ $test = 'build-only' ]]; then
        if (( ! built )); then
            build_emacs || true
        fi

        (( built == 1 ))
        return
    fi

    if (( ! built )); then
        err 'not built?!'
    fi

    if ! "$tmp"/src/bootstrap-emacs -nw -Q \
        --batch -l "$test"
    then
        return 1
    fi

    return 0
}

# Find a feasible revision between $1 and $2 (which are revision
# numbers). On success, the pivot is the current revision, and it is
# built.
find_pivot() {
    local low=$1
    shift

    local high=$1
    shift

    local middle=$(( (low + high) / 2 ))

    # Try revision middle, then middle -1 1, then middle + 1, middle -
    # 2, middle + 2, etc. until we either find a feasible revision or
    # exceed our bounds.
    for ((i = 0; ; ++i )); do
        local candidate=$(( middle + -1*(i%2)*(i/2) ))

        if ! (( low < candidate && candidate < high )); then
            return 1
        fi

        checkout $candidate
        if is_feasible_rev; then
            return 0
        fi
    done
}

bisect() {
    local low=$1
    shift

    local high=$1
    shift

    # Test for impossible conditions
}

# Parse argument list. Arguments are the program's arguments.
#
# Sets variables do_cleanup, low, high, parent, tmp, and test by
# side-effect to the corresponding command-line parameters
parse-args() {
    low=
    high=-1 # bzr for "current version"

    while getopts 'fdp:t:h' flag; do
        case $flag in
            d)
                (( do_cleanup=0 ))
                ;;
            b)
                parent=$OPTARG
                ;;
            t)
                tmp=$OPTARG
                ;;
            h)
                err -u -h
                ;;
            f)
                fullbuild=1
                ;;
            *)
                err -u
                ;;
        esac
    done

    shift $((OPTIND-1))

    # Get revisions

    test=$1
    if ! shift; then
        err -u 'TEST not given'
    fi

    low=$1
    if ! shift; then
        err -u 'LOW not given'
    fi

    if [[ -n $1 ]]; then
        high=$1
        shift

        if [[ -n $1 ]]; then
            err -u 'too many arguments'
        fi
    fi

    if [[ $test != 'build-only' ]] && [[ ! -r $test ]]; then
        err -u "cannot read '$test' as elisp"
    fi

    tmp="$PWD/$tmp"
    if [[ -a $tmp ]]; then
        err "path '$tmp' exists, exiting"
    fi
}

main() {
    local low
    local high

    parse-args "$@"

    # We don't expect user input
    exec 0</dev/null

    # FD 6 goes to user
    exec 6>&2

    # FD 7 goes to log
    exec 7>"$LOG"

    # FD 8 goes to both (process substitution doesn't work on OS X)
    mkfifo "$tmpdir/log-and-user"
    <"$tmpdir/log-and-user" tee /dev/fd/7 &
    exec 8>"$tmpdir/log-and-user"

    # stdout and stderr go to the log
    exec 1>&7
    exec 2>&7

    msgfd=8

    trap cleanup 0

    checkout "$high"
    unset high

    local highrevno=$current_revno
    local highrevdesc=$current_revdesc
    msg "high revision is $current_revdesc"

    if ! is_feasible_rev; then
        err "couldn't build HIGH revision $current_revdesc"
    fi

    if is_good_rev; then
        err "bug not present in HIGH revision $current_revdesc"
    fi

    msg "good: bug present in revision $current_revdesc"

    checkout "$low"
    unset low

    local lowrevno=$current_revno
    local lowrevdesc=$current_revdesc
    msg "low revision is $current_revdesc"

    # Find the first usable branch
    while ! is_feasible_rev && (( lowrevno < highrevno )); do
        msg "skipping infeasible revision $current_revdesc"
        (( lowrevno++ ))
    done

    if (( lowrevno == highrevno )); then
        err 'no feasible revisions'
    fi

    if ! is_good_rev; then
        err "bug present in LOW revision $current_revdesc Try going further 
back."
    fi

    msg "good: bug not present in revision $current_revdesc"

    while true; do
        msg "examining revisions $lowrevno - $highrevno: " \
            "$((highrevno - lowrevno)) revisions"
        msg "    --> $lowrevdesc - $highrevdesc"
        if ! find_pivot $lowrevno $highrevno; then
            break
        fi

        msg "testing $current_revdesc..."

        if is_good_rev; then
            msg "bug not present in revision $current_revdesc"
            lowrevno=$current_revno
            lowrevdesc=$current_revdesc
        else
            msg "bug present in $current_revdesc"
            highrevno=$current_revno
            highrevdesc=$current_revdesc
        fi
    done

    msg "DONE: bug was introduced between revisions $lowrevdesc and 
$highrevdesc"
}

main "$@"



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (Darwin)

iEYEARECAAYFAktR+eAACgkQ17c2LVA10Vv7cgCfToY7KHhE21nfSTZN12AAKc/s
cHIAnR8U0E/ZsScQgW9o7LE3EDx7hcPH
=sEgu
-----END PGP SIGNATURE-----