DRMacIver's Notebook

Basic Reducer Design

Published: 2021-01-01

There’s a design of test-case reducer that I use and consider the natural way to do test-case reducers, but seems to be mildly idiosyncratic to me (though most of the details of it are found in other test-case reducers), which is basically this:

Test cases are given some total order, the reduction order, and the goal of test-case reduction is to (ideally) find the minimal interesting test case in that reduction order.
Test-case reduction is managed by a stateful object that automatically simplifies the book keeping of doing that.
Test-case reduction consists of a sequence of passes that are run until none of them lowers the current most interesting test case.

(the fact that there is a total reduction order plus some of the book keeping are the bits that seem not totally standard)

The reduction order lets us keep track of the current best test case and this significantly simplifies keeping track of the progress of the reducer. This can all be encapsulated as the following Python code:


class Reducer:

    def __init__(
        self,
        initial_test_case,
        is_interesting, 
        reduction_order,
        reduction_passes,
    ):
        self.best_test_case = initial_test_case
        self.__is_interesting = is_interesting
        self.reduction_order = reduction_order
        self.reduction_passes = reduction_passes

        # We cache the result of the interestingness test - this is pretty
        # standard in test-case reduction.
        self.__cache = {}

        if not self.is_interesting(initial_test_case):
            raise ValueError("Cannot reduce uninteresting initial test case")

    def is_interesting(self, test_case):
        try:
            return self.__cache[test_case]
        except KeyError:
            pass

        result = self.__is_interesting(test_case)
        self.__cache[test_case] = result

        # If this is a smaller interesting test case than our current best
        # known one, automatically update.
        if (
            result and
            self.reduction_order(test_case) < self.reduction_order(self.best_test_case)
        ):
            self.best_test_case = test_case
        return result

    def reduce(self):
        prev = None
        while prev is not self.best_test_case:
            prev = self.best_test_case
            # Each reduction pass calls self.is_interesting in order to do
            # any work, so we do not need to keep track of whether they
            # succeeded or failed.
            for f in self.reduction_passes:
                f(self)


def reduce(*args, **kwargs):
    reducer = Reducer(*args, **kwargs)
    reducer.reduce()
    return reducer.best_test_case

A reduction pass in this framework looks something like the following (this is a greedy algorithm for deleting elements from a list or other sequence, like delta debugging without the delta step):


def greedy_deletion(self):
    i = 0
    while i < len(self.best_test_case):
        attempt = self.best_test_case[:i] + self.best_test_case[i + 1:]
        if not self.is_interesting(attempt):
            i += 1

This design has a lot of flexibility to it. For example, it makes arbitrary reduction passes into an anytime algorithm, because you always know the current best test case, and so you can design it work with arbitrary interruptions. e.g. If you wanted to impose a limit on the maximum number of calls you could do it by modifying the reducer as follows:


class StopReducing(Exception):
    pass

class Reducer:

    def __init__(
        ...,
        max_calls=1000
    ):
        self.max_calls = max_calls
        self.call_count = 0
        ...

    def is_interesting(self, test_case):
        ...
        self.call_count += 1
        if self.call_count >= self.max_calls:
            raise StopReducing()
        return result

    def reduce(self):
        try:
            ...
        except StopReducing:
            pass

(People will, at this point, complain that I am using exceptions for control flow. Yes I am. What of it?)

One downside to this design is that it doesn’t play that well with multithreading. This isn’t a major problem in Python, so I haven’t spent much time working on it, but roughly there are two obvious things you can do with this design: You can make the best test case thread local and then merge by taking the minimum when you join threads, or you can make your reduction passes single-threaded but use speculative concurrency to speed them up. This latter approach is roughly what reducers like halfempty. I’ve experimented a bit with this in some reducer prototypes, but not in Hypothesis where it’s not especially useful because Python.