Let’s see an example of how simple it is to generate mutations on the Erlang AST. We want to replace the + operator in the expression a + b. To help generate Erlang AST expressions (something which is unreasonably complex using the default functions in the erlang compiler library), I’ve written the Darwin.expression!/2 function, which does exactly that.
iex(1)> expr = Darwin.ErlUtils.expression!("a + b.")
{:op, 1, :+, {:atom, 1, :a}, {:atom, 1, :b}}
iex(2)> Darwin.mutate(expr)
23:18:37.812 [debug] Darwin.mutate/1
>>> Input:
a + b
>>> Output:
fun (_darwin_a@1, _darwin_b@1) ->
case
'Elixir.Darwin.Mutator.Helpers':do_get_active_mutation()
of
1 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_sub(_darwin_a@1,
_darwin_b@1);
2 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_mul(_darwin_a@1,
_darwin_b@1);
3 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_div(_darwin_a@1,
_darwin_b@1);
_ ->
'Elixir.Darwin.Mutator.Helpers':do_arith_add(_darwin_a@1,
_darwin_b@1)
end
end(a, b)
{:call, 0,
{:fun, 0,
{:clauses,
[
{:clause, 0, [{:var, 0, :_darwin_a@1}, {:var, 0, :_darwin_b@1}], [],
[
{:case, 0,
{:call, 0,
{:remote, 0, {:atom, 0, Darwin.Mutator.Helpers},
{:atom, 0, :do_get_active_mutation}}, []},
[
{:clause, [generated: true, location: 0], [{:integer, 0, 1}], [],
[
{:call, 0,
{:remote, 0, {:atom, 0, Darwin.Mutator.Helpers},
{:atom, 0, :do_arith_sub}},
[{:var, 0, :_darwin_a@1}, {:var, 0, :_darwin_b@1}]}
]},
{:clause, [generated: true, location: 0], [{:integer, 0, 2}], [],
[
{:call, 0,
{:remote, 0, {:atom, 0, Darwin.Mutator.Helpers},
{:atom, 0, :do_arith_mul}},
[{:var, 0, :_darwin_a@1}, {:var, 0, :_darwin_b@1}]}
]},
{:clause, [generated: true, location: 0], [{:integer, 0, 3}], [],
[
{:call, 0,
{:remote, 0, {:atom, 0, Darwin.Mutator.Helpers},
{:atom, 0, :do_arith_div}},
[{:var, 0, :_darwin_a@1}, {:var, 0, :_darwin_b@1}]}
]},
{:clause, [generated: true, location: 0], [{:var, 0, :_}], [],
[
{:call, 0,
{:remote, 0, {:atom, 0, Darwin.Mutator.Helpers},
{:atom, 0, :do_arith_add}},
[{:var, 0, :_darwin_a@1}, {:var, 0, :_darwin_b@1}]}
]}
]}
]}
]}}, [{:atom, 1, :a}, {:atom, 1, :b}]}
The returned expression is Erlang AST, which is of course pretty much unreadable. The interesting part happens in the logs, where I show the corresponding Erlang code. I reproduce it below for clarity:
fun (_darwin_a@1, _darwin_b@1) ->
case
'Elixir.Darwin.Mutator.Helpers':do_get_active_mutation()
of
1 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_sub(_darwin_a@1,
_darwin_b@1);
2 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_mul(_darwin_a@1,
_darwin_b@1);
3 ->
'Elixir.Darwin.Mutator.Helpers':do_arith_div(_darwin_a@1,
_darwin_b@1);
_ ->
'Elixir.Darwin.Mutator.Helpers':do_arith_add(_darwin_a@1,
_darwin_b@1)
end
end(a, b)
The above is an anonymous function which is called on a and b. The anonymous function uses 'Elixir.Darwin.Mutator.Helpers':do_get_active_mutation() to decide which branch to use. The do_get_active_mutation() function requests the current mutation number from a genserver (using an ETS table is probably slightly faster but it can lead to race conditions, so I’ll stick with a genserver for now). Depending on the mutation number, the anonymous function will pick a branch from the case statement.
The branches of the case statement are a little odd. For example, I’m using 'Elixir.Darwin.Mutator.Helpers':do_arith_sub/2 instead of simply a - b. These functions are just thin wrappers around the Erlang operators (+, -, * and /) because the AST is slightly easier to manipulate that way. Unlike Elixir, where {+, [], args} is a simple to manipulate as {f, [], args}, in Erlang the AST for these expressions is very different, and using named functions makes it simpler to treat operators and functions in the same way (everything is just a function…). Because there are no macros at this point (everything made from simple referentially transparent function calls), using a function or an operator is equivalent.
Sanity check
Now, the truth istaht I don’t have an end-to-end system yet. I’m working from the bottom up first generating mutations, then recompiling the code and then integrating the code into a test suite. The roeadmap is more or less the following:
- Implement all kinds of commonly used mutations. This seems to be very simple, as Erlang is very easy to manipulate. In particular, it’s trivial to determine whether the
+ operator in Erlang is the actual plus sign from mathematics, because it does not depend on whether you’re importing some weird module or whether you’re using it insid e of a macro that actually compiles you code into Java or something like that. This means that mutating the + operator is always “safe” and won’t cause weird compiler errors.
- Important question: Should mutations be deterministic? One mutation I want to have is to replace some values (constants, expressions and variables) by constant values. Maybe I should generate random values like
StreamData does. Or maybe I should use seom simple values that often break code, like booleans, 1, 0, etc.
-
Traverse the Erlang AST in order to find places that can be mutated. This is tricky, because the Erlang AST is not as simple as Elixir’s. There are some good docs on the format, so it shouldn’t be too hard. Unfortunately, it seems like Erlang’s AST is actually an implementation detail, so you should be using the erl_syntax module to work with it. This module adds a pretty heavy layer of indirection, which can sometimes stand in the way of actually doing interesting things… I’ll work directly with the Erlang AST until everything is stable enough for me to switch to the supposedly stable erl_syntax module.
-
Map mutations to lines of code. This seems doable, although I haven’t tried it yet. The Erlnag AST is annotated with location information, so I guess I can make it work.
-
Integrate the mutation framework with a test suite. The obvious integration point is ExUnit, of course.
-
Rewrite the whole thing in Erlang, because there isn’t a good reason this should be in Elixir. Rewriting this in Erlang (except for the part that integrates with ExUnit, of course) would make sense, becaus eI’m not working with Elixir’s AST. This means that the quoting and unquoting mechanisms we all love in Elixir are not needed here. This leaves me with few reasons why this should be written in Elixir. The main reason is that the current iteration of Darwin uses some custom macros to cut down on pointless repetition (it cuts the code size into about 1/5 of what it would be without macros), but I can always compile those modules into Erlang and distribute the Erlang code 
Regarding point 4 (integration with ExUnit), I’m thinking of something like this:
defmodule MyModuleTest do
# Mutate MyModule and run it through the test suite
use Darwin.Test, module: MyModule
test "some test cases" do
# ...
end
end
The use Darwin.Test statement would define customized test macros, as well as other APi compatible versions of ExUnit functions and macros.
The test macro could expand into something like this:
# mutation indices are consecutive integers (they could be anything else, though...)
for mutation_index <- 0..mutation_max_index do
# Activate the mutation
Darwin.ActiveMutation.set(mutation)
# Run the code inside the test case
# The mutated code knows how to run the correct branch from the active mutation
# No need to recompile anything!
end
# Turn off all mutations
Darwin.ActiveMutation.set(nil)
As you can see, this avoids recompiling code. It will generate some very large modules, as it must inject code for all mutaions, but it makes testing the mutations very fast! The runtime overhead for each mutation point (each of which can contain several mutations) is a genserver call. It can even cache the mutated modules somewhere so you don’t pay the compilation price for modules you haven’t changed.
Disadvantages
Working with the fully macro-expanded Erlang abstract format means it’s not very easy to map the changes back into Elixir code. For example, I’ll probably never be able to get coverage reports as explicit and informative as these. I’ll be able to report the information on the table to the right, though (line number and kind of mutation performed).
For some perspective, even very simple Elixir modules take about 10ms to compile. If I had to recompile a module each time I wanted to test a mutation, I wouldn’t be able to test more than 10 mutations per second, which is very slow for any reasonable codebase… This could be made faster by starting other Erlang nodes in parallel and distributing the work between the nodes, but it’s probably not worth the effort.
