script to automate binary search for regression

[Janis Johnson <janis187@us.ibm.com>]

[-- Attachment #1: Type: text/plain, Size: 1068 bytes --]

Here's the script I'm using to do binary searches to locate regressions.
It invokes separate scripts to do the real work: update CVS, build GCC,
and run the test.  It starts with two specified dates and calls the
user-provided scripts in a binary search to narrow the time range where
the test behaviour changed to a specified time range, one hour by
default.  There are no restrictions on the starting dates, they just
need to be recognized by the date command.  It uses an extension in GNU
date to convert a date to seconds from the epoch, but on a system where
GNU date isn't an option that part could be replaced by a small C
program to do the conversion.

Since you provide the other scripts, they can do whatever you want: use
a CVS branch, build only cc1plus or do a full bootstrap, and whatever it
takes to run the test.

The length of the script is mostly due to comments and lots of error
checking.  I've tested it fairly thoroughly.  If you find this helpful,
let me know and I'll ask about adding it to contrib.

Janis Johnson
IBM Linux Technology Center


[-- Attachment #2: regsearch --]
[-- Type: text/plain, Size: 7929 bytes --]

#! /bin/sh

########################################################################
#
# File:    regsearch
# Author:  Janis Johnson <janis187@us.ibm.com>
# Date:    2002/12/15
#
# Search for a small time interval within a range of dates in which
# results for a test changed, using a binary search.  The functionality
# for getting GCC sources, building a compiler, and running the test are
# in other scripts that are run from here.  Before the search begins, we
# verify that we get the expected behavior for the first and last dates.
#
# Define these in a file whose name is the argument to this script:
#   LOW_DATE:   Date string recognized by the date command.
#   HIGH_DATE:  Date string recognized by the date command.
#   UPDATE_CVS: Script to update your GCC source tree.
#   BUILD_GCC:  Script to build enough of GCC to run the test.
#   RUN_TEST:   Script to run the test; returns 1 if we should search
#               later dates, 0 if we should search earlier dates.
# Optional:
#   DELTA:      Search to an interval within this many seconds; default
#               is one hour.
#   SKIP_ENDS   Skip verifying the end points of the range if this is 1;
#               define this only if you're restarting and have already
#               tested the low and high dates.
#   FIRST_MID   Use this as the first midpoint, for avoiding a midpoint
#               that is known not to build.
#   VERBOSITY   Default is 0, to print only errors and final message.
#   DATE_IN_MSG If defined, include the time and date in messages.
#
# Janis has scripts to test this one, including error checking.
#
#
# Copyright (c) 2002 Free Software Foundation, Inc.
#
# This file is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# For a copy of the GNU General Public License, write the the
# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
# Boston, MA 02111-1307, USA.
# 
########################################################################

########################################################################
# Functions
########################################################################

# Issue a message if it's verbosity level is high enough.

msg() {
  test ${1} -gt ${VERBOSITY}  && return

  if [ "x${DATE_IN_MSG}" = "x" ]; then
    echo "${2}"
  else
    echo "`date`  ${2}"
  fi
}

# Issue an error message and exit with a non-zero status.  If there
# is a valid current range whose end points have been tested, report
# it so the user can start again from there.

error() {
  msg 0 "error: ${1}"
  test ${VALID_RANGE} -eq 1 && \
    echo "current range is between ${LATER_THAN} and ${EARLIER_THAN}"
  exit 1
}

# Turn seconds since the epoch into a date we can use with CVS and
# report to the user.

make_date() {
  MADE_DATE="`date +\"%Y-%m-%d %H:%M\" --date \"1970-01-01 00:00:${1} UTC\"`" \
    || error "make_date: date command failed"
}

# Build a compiler using sources as of a particular date and run a
# test case.  Pass each of the scripts the date that we're testing;
# the first one needs it, the others can ignore it if they want.

process_date() {
  DATE="${1}"

  ${UPDATE_CVS} "${DATE}" || error "cvs update failed for ${DATE}"
  ${BUILD_GCC} "${DATE}"  || error "compiler build failed for ${DATE}"
  ${RUN_TEST} "${DATE}"
  LATER=$?
}

# Perform a binary search on dates within the range specified by
# the arguments, bounded by the number of seconds in DELTA.

search_dates() {
  let LOW=$1
  let HIGH=$2
  let DIFF=HIGH-LOW

  # Get the date in the middle of the range; MID is in seconds since
  # the epoch, DATE is readable by humans and CVS.  The user can
  # override the initial mid date if it is known to have problems,
  # e.g., if GCC doesn't build on that date.

  if [ ${FIRST_MID} -ne 0 ]; then
    let MID=${FIRST_MID}
  else
    let MID=LOW/2+HIGH/2
  fi

  while [ ${DIFF} -ge ${DELTA} ]; do
    make_date ${MID}
    DATE="${MADE_DATE}"

    # Test it.

    process_date "${DATE}"

    # Narrow the search based on the outcome of testing DATE.

    if [ ${LATER} -eq 1 ]; then
      msg 1 "search dates later than ${DATE}"
      LATER_THAN="${DATE}"
      let LOW=MID
    else
      msg 1 "search dates earlier than ${DATE}"
      EARLIER_THAN="${DATE}"
      let HIGH=MID
    fi

    let DIFF=HIGH-LOW
    let MID=LOW/2+HIGH/2
  done
}

########################################################################
# Main program (so to speak)
########################################################################

# The error function uses this.

VALID_RANGE=0

# Process the configuration file.

if [ $# != 1 ]; then
  echo Usage: $0 config_file
  exit 1
fi

CONFIG=${1}
if [ ! -f ${CONFIG} ]; then
  error "configuration file ${CONFIG} does not exist"
fi

# OK, the config file exists.  Source it, make sure required parameters
# are defined and their files exist, and give default values to optional
# parameters.

. ${CONFIG}

test "x${UPDATE_CVS}" = "x" && error "UPDATE_CVS is not defined"
test "x${BUILD_GCC}" = "x" && error "BUILD_GCC is not defined"
test "x${RUN_TEST}" = "x" && error "RUN_TEST is not defined"
test -x ${RUN_TEST} || error "RUN_TEST is not an executable file"
test "x${SKIP_ENDS}" = "x" && SKIP_ENDS=0
test "x${DELTA}" = "x" && DELTA=3600
test "x${VERBOSITY}" = "x" && VERBOSITY=0

msg 2 "LOW_DATE   = ${LOW_DATE}"
msg 2 "HIGH_DATE  = ${HIGH_DATE}"
msg 2 "UPDATE_CVS = ${UPDATE_CVS}"
msg 2 "BUILD_GCC  = ${BUILD_GCC}"
msg 2 "RUN_TEST   = ${RUN_TEST}"
msg 2 "SKIP_ENDS  = ${SKIP_ENDS}"
msg 2 "FIRST_MID  = ${FIRST_MID}"
msg 2 "VERBOSITY  = ${VERBOSITY}"
msg 2 "DELTA      = ${DELTA}"

# Verify that DELTA is at least two minutes.

test ${DELTA} -le 120 && \
  error "DELTA is ${DELTA}, must be at least 120 (two minutes)"

# Change the dates into seconds since the epoch.  This uses an extension
# in GNU date.

LOW_DATE=`date +%s --date "${LOW_DATE}"` || \
  error "date command failed for \"${LOW_DATE}\""
HIGH_DATE=`date +%s --date "${HIGH_DATE}"` || \
  error "date command failed for \"${LOW_DATE}\""

# If FIRST_MID was defined, convert it and make sure it's in the range.

if [ "x${FIRST_MID}" != "x" ]; then
  FIRST_MID=`date +%s --date "${FIRST_MID}"` || \
    error "date command failed for \"${FIRST_MID}\""
  test ${FIRST_MID} -le ${LOW_DATE}  && \
    error "FIRST_MID date is earlier than LOW_DATE"
  test ${FIRST_MID} -ge ${HIGH_DATE} && \
    error "FIRST_MID is later than HIGH_DATE"
else
  FIRST_MID=0
fi 

# Keep track of the bounds of the range where the test behavior changes,
# using a human-readable version of each date.

make_date ${LOW_DATE}
LATER_THAN="${MADE_DATE}"
make_date ${HIGH_DATE}
EARLIER_THAN="${MADE_DATE}"

# Verify that the range isn't backwards.

test ${LOW_DATE} -lt ${HIGH_DATE} || error "date range is backwards"

# Verify that the first and last date in the range get the results we
# expect.  If not, quit, because any of several things could be wrong.

if [ ${SKIP_ENDS} -eq 0 ]; then
  process_date "${LATER_THAN}"
  test ${LATER} -ne 1 && \
    error "unexpected result for low date ${LATER_THAN}"
  msg 1 "result for low date is as expected"

  process_date "${EARLIER_THAN}"
  test ${LATER} -ne 0 && \
    error "unexpected result for high date ${EARLIER_THAN}"
  msg 1 "result for high date is as expected"
fi

# Search within the range, now that we know that the end points are valid.

VALID_RANGE=1
search_dates ${LOW_DATE} ${HIGH_DATE}

# Report the range that's left to investigate.

echo "Continue search between ${LATER_THAN} and ${EARLIER_THAN}"