AST based mutations

The following is a proof of concept that generates mutations (see Mutation Testing) based on the Abstract Syntax Tree of a given file. The idea is to use nikic/PHP-Parser to generate an AST for a given file. By using mutation operators that act on a Node of the AST we can create specific mutations for that Node.

An advantage of using nikic/PHP-Parser over a custom tokenizer is that the mutations will always generate valid PHP.

Creating mutations for a given source code can be done in 3 steps,

1. Convert the source code to an AST
2. Generate mutations based on mutation operators
3. Apply the mutations one at a time and take action (e.g. store the mutated AST or run tests on the mutated AST)

The following example illustrates these steps,

use PhpParser\Lexer;
use PhpParser\ParserFactory;
use PhpParser\PrettyPrinter\Standard;
use Renamed\ApplyMutation;
use Renamed\GenerateMutations;
use Renamed\Mutation;
use Renamed\MutationOperator;
use Renamed\Mutations;

// The orginal source code for which we want to create mutations
$source = "<?php echo 1 * 2 * 3;";

// Setup a parser to generate the AST
$parser = (new ParserFactory)->create(ParserFactory::PREFER_PHP7, new Lexer);

$ast = $paser->parse($source);

$applyMutation = new ApplyMutation($ast);

$generator = new GenerateMutations(
    function(Mutation $mutation) use ($applyMutation) {
        $applyMutation->apply($mutation, function($mutation, $ast) {
            echo (new Standard)->prettyPrint($ast);
        })
    },
    new Mutations\Multiplication,
    new Mutations\DateTimeFromFormat // ... you can add as many operators as you want
);

// Generate and store the applied mutations
$generator->generate($ast);

You may also use the Renamed\MutateSourceCode class to create mutations.

use PhpParser\PrettyPrinter\Standard;
use Renamed\MutateSourceCode;
use Renamed\Mutations;

$source = file_get_contents("SomeFile.php");
$mutate = new MutateSourceCode(
    new Mutations\Multiplication
);

// After a mutation has been applied, echo the pretty printed code
$mutate->mutate($source, function ($mutation, $ast) {
    echo (new Standard)->prettyPrint($ast);
});

Example

Suppose we have the following code,

<?php echo 1 * 2 * 3;";

Running the mutation tester with a ChangeMultiplicationToDivision operator will result in the following mutations

<?php echo 1 / 2 * 3;";

<?php echo 1 * 2 / 3;";

The code of the operator is quite simple (though it does require some understanding of nikic/PHP-Parser).

final class ChangeMultiplicationToDivision implements MutationOperator
{
    /**
     * Replace (*) with (/)
     * @param Node $node
     */
    public function mutate(Node $node)
    {
        if (! $node instanceof BinaryOp\Mul) {
            return;
        }

        yield new BinaryOp\Div($node->left, $node->right, $node->getAttributes());
    }
}

Anatomy of a mutation operator

A mutation operator implements the MutationOperator interface. Note that its only input is a Node and it does not have a return value, instead each operator will yield one or more nodes.

interface MutationOperator {

    public function mutate(Node $node);
}

The advantage of yielding a mutation over returning (an array of) mutation(s) is that the latter gives us more opportunities to improve performance (see Synchronous vs asynchronous mutation testing). If you want to test your mutation operator be sure to extend the abstract Renamed\Tests\MutationOperatorTest testcase.

Issues / notes

Synchronous vs asynchronous mutation testing

The current implementation of GenerateMutations uses a Closure that is called after each mutation is generated. It is up to the user to decide what he or she wants to do with it. In general a Closure is given that calls the apply method on an ApplyMutation instance. Another approach would be to store the mutations and apply the mutations after all mutations have been generated. The later approach will probably be more memory intensive.

Performance when applying a mutation

Traverse twice, or clone during traversal

When applying a mutation on an ASt we have two options. We can traverse the AST twice, where in the first time we apply the mutation and in the second we reverse the mutation.

Another option would be to clone each node during traversal. This will probably be less efficient since it requires copying a whole AST.

✔ DONE Stop traversing after mutation has been applied

Once a mutation has been applied we can stop traversing the AST.

A simple fix could be to add a second visitor that is visited after the first one and returns NodeTraverserInterface::DONT_TRAVERSE_CHILDREN.

An even simpler fix could be returning NodeTraverserInterface::DONT_TRAVERSE_CHILDREN in enterNode of each mutation, however this will require each mutation to extend a base class.

I don’t like extending a mutation since that makes writing a mutation somewhat more complex.

In the end I would prefer to combine the traverser and visitor.

Combine traverser and visitors

Currently we require both a AST traverser and an NodeVisitor for both generating and applying a mutation. Since in both cases we only need 1 visitor it does not make much sense to have a traverser that can have multiple visitors. Moreover applying and generating mutations could probably use different traversers since applying won’t have to traverse the whole AST.

Higher order mutants

Higher order mutants are mutants that have been created by more than one mutation. It would be nice to have support for higher order mutations, and I don’t think it will require a lot of effort to implement this. But higher order mutations will result in a lot more mutations, making the overall process slower. I should probably read some research papers about HOMs.