Redux is a set of tools inspired by Delta to help applying the idea of delta debugging to Python programs. The main use case is reduction of test cases when reproducing bugs to assist reporting issues with the simplest steps to reproduce.
This is an early version, which has some limitations:
- Works only on 1 file at the moment
- The refactoring options are limited, for example no re-structuring of classes and functions
- There are known limitations in some of the filters, usually listed with a TODO tag
- There are probably a lot of cases that redux doesn't handle, if you find issues, please open a ticket in the issue tracker with an example.
How does it work?
The reduction process happens in different steps
- The target code is run through a tracer to collect coverage data and identify the failure.
- A number of "safe" modifications are made to the code to simplify it with no change to its behaviour
- The code is analysed for hypotheses about things that are likely not related to the bug
- Each hypothese is tested individually by modifying the code, with 2 possible outcomes: - The failure is still present, the hypothese was right, the change to the code is kept - The failure disappeared, the hypothese was wrong as the change affected the failure, the change is discarded
Steps 3 and 4 are repeated until no more valid hypotheses can be found, at which point the resulting code is the minimal test case to reproduce the failure that redux can find.
Running the code
The target file is compiled to a Python abstract syntax tree (ast) then run with exec (See
You can specify a function to be called when running the code as well, see below for examples.
The ast of the ast is then used as the representation of the code through steps 2 to 4 as implementing modification to asts is easy.
A failure is assumed to be an exception raised by the code you're testing. As the hypotheses modify the code, they might introduce other failures than the one the code is trying to reproduce, so it's important to identify the right failure. You can specify a detector to compare exceptions raised during execution of the code to the one expected to be raised, to make sure the failure is still present.
At the moment 2 types of detectors are supported (see
- A detector that verifies the class of the raised exception. Use this one if the exception raised is specific enough so false positive are not likely.
- A detector that matches the error message of raised exception, you can use it to have more control over what is matched if your exception is common
You can also explicitely raise a
redux/exc.py) if your failure isn't an exception, or if it's too common, for example AssertException.
The tracer (See
redux/tracer.py) is used to collect information about the code as it runs:
- Line coverage
- Return values of function calls
This information is then used to come up with hypotheses (See
It is implemented by setting a tracing function using
sys.settrace, like other code coverage tools.
Filters are subclasses of
ast.NodeTransformer that can identify patterns of code and modify them. A
BaseFilter is provided with to provide some helpers for subclasses, but any class compatible with
NodeTransformer can be used.
Hypotheses are implemented by filters. For example the hypothese "The function log_error doesn't affect the failure" will be tested by running a filter
RemoveFunctionCall on each node calling
log_error and verifying that the failure still exists.
The available filters are in
Some of them are safe to apply (they shouldn't affect the failure), for example:
RemoveUnusedDeclarationswill remove class and function declaration that are not used.
RemoveUnusedLineswill remove lines that are not used by the test, for example branches of
ifblocks or the body of unused functions.
SimplifyFormatswill remove uninteresting parts of
Some are more destructive
RemoveFunctionCallwill remove a given function call completely.
RemoveAssertswill remove all
The first type of filters are general simplification/cleanup filters and are run during step 3 without re-running the code in between.
Adding new filters
Detecting a pattern
Each filter implements a method
check which returns
True if the given node is a candidate for modification.
BaseFilter provides a simple check on the current node class against a white list.
Modifying the node
If a node passes the check, the
apply method of the filter is called, and its return value will be used to modify the node or not.
BaseFilter will run
generic_visit on the children of the node before calling apply on the node itself, if you do not want that, re-implement
visit in your filter.
Removing a node
Sometimes a node can't be removed directly, as its deletion could affect other filters being run.
def fn1(): pass (a, b) = fn1(), fn1()
In that case
fn1 is called twice. If we suspect that
fn1 is irrelevant to the failure, we could run the following 2 filters:
RemoveFunctionCall("test.py", 4, "fn1", 0)
RemoveFunctionCall("test.py", 4, "fn1", 1)
to remove each call separately (0 and 1 are the index of list of calls to
fn1 on line 4). If the first filter removed the node completely, the resulting code would become
def fn1(): pass (a, b) = (fn1(), )
and the second filter would be looking for the second call to
fn1 on line 4 (index 1) but wouldn't find it as there is only one call now.
To avoid this issue, a new node type
Deleted is introduced to maintain the structure of the code in a run of filters. It is then removed in step 3 by
reduxrun.py is a command line tool that runs the reduction steps on a given filename. You can specify how to detect the failure and if a function needs to be called in the script.
$ python reduxrun.py --help Usage: reduxrun.py [options] file Options: -h, --help show this help message and exit -f FUNCTION, --function=FUNCTION function to call to trigger the bug -e EXCEPTION, --exception=EXCEPTION name of the exception raised by the bug -m MESSAGE, --message=MESSAGE message of the exception raised by the bug
The examples below assume that all dependencies are installed properly (see
requirements.txt). You can setup a virtualenv for that:
$ virtualenv venv $ source venv/bin/activate $ pip install -r requirements
Using a function call and exception match on message
$ python reduxrun.py --function "trigger" --message ".* zero" redux/test/data/source3.py import sys sys.path.insert(0, 'redux/test/data') def fn2(x): return (x / 0) def trigger(): fn2(1)
Same but with exception match on name
$ python reduxrun.py --function "trigger" --exception ZeroDivisionError redux/test/data/source3.py import sys sys.path.insert(0, 'redux/test/data') def fn2(x): return (x / 0) def trigger(): fn2(1)
Same script without function call
The failure in this example script only happens when calling the
$ python reduxrun.py --exception ZeroDivisionError redux/test/data/source3.py Error: The code didn't fail as expected Error: Could not verify the failure, make sure the code raises SentinelException or uses the right failure detector
This doesn't work as the script didn't raise a
ZeroDivisionError or a
Example with SentinelException
$ python reduxrun.py --function redux_start redux/test/data/source1.py import sys sys.path.insert(0, 'redux/test/data') from redux.exc import SentinelException from source1module.a import function3 def buggy_func(a): raise NotImplementedError() def redux_start(): try: buggy_func(1) except NotImplementedError: raise SentinelException()
You can compare the output to the original code in
Most of the code is tested under
redux/test. Most of the tests consist of running the filters against some code and checking the output for errors.
You can run all the tests with regular test runners, and you can also use
make run_tests to run the tests with
nose and see coverage stats.
Reading list and related tools
- The original delta
- Delta debugging
- Python internals: Working with Python ASTs
- Be careful with exec and eval in Python