1 Prologue

1 Prologue🔗ℹ

1.1 Mutation concepts🔗ℹ

1.1.1 Mutators🔗ℹ

This library centers around the concept of a mutator, which describes a small syntactic modification to a piece of syntax. A mutator can roughly be thought of as a function from syntax to syntax which does the modification. In typical mutation practice, the mutation is meant to introduce a possible change in program behavior — usually this means a bug. For example, a typical standard mutator negates the condition of if expressions, which we might abstractly write as a kind of pattern transformation like so:

(if c t e) ~> (if (not c) t e)

Using this library, we can concretely write such a mutator as follows:

(define-simple-mutator (if-negate stx)
#:pattern ({~datum if} c t e)
#'(if (not c) t e))

Applying this mutator to a fragment of program syntax can create a mutated variant of the fragment. For instance, the fragment

(if (= a b)
(f a)
(g a b))

can be mutated with our if negation to become

(if (not (= a b))
(f a)
(g a b))

1.1.2 Mutating full programs🔗ℹ

Usually, one wants to use mutators to mutate whole programs and create mutated variants of the program, called mutants.

But mutators only mutate certain fragments of program syntax, which might appear scattered deeply throughout a program. Hence, mutating full programs requires finding the expressions that could be mutated. Each of those places where mutators could create a mutation are called mutation points.

Furthermore, a mutator can also have several mutation points at the same place if it can mutate that piece of syntax in multiple ways.

For example, this program has two if expressions, each of which could be mutated by our if-negating mutator from before.

#lang racket
(define (abs x)
  (if (< x 0) ; mutation point
      (- x)
      x))
(define (f n)
  (if (< (abs n) 50) ; mutation point
      'ok
      'too-big))
(displayln (f (random)))

There are several mutation points in this program, but in typical mutation practice, one only wants to mutate one of them to create a mutant. (Check out The mutation literature for the details of why one usually wants just one mutation per mutant.)

This library provides a way to select a mutation point by assigning each point an index called the mutation index. The first mutation point in the above example has mutation index 0, and the second is 1. The order of mutation indexes is defined through a built-in traversal of program syntax.

All mutators accept a mutation index as well as the syntax to mutate, to select from the possibly multiple different mutations of the original syntax.

In the workflow of this library, you (the user) define one or more mutators (see Defining mutators) and then hand them over to the library’s syntax traversal engine to create a mutation engine (see build-mutation-engine). The mutation engine is a function that accepts the syntax of a program and a mutation index, and returns the mutant corresponding to the given index. (For a given program and engine, the mutation index serves as a sort of ID for a particular mutant.)

1.2 A full example🔗ℹ

This example illustrates using the high level apis to define simple mutators and build a mutation engine.

(require syntax/parse
         mutate ; provides both mutate/define and mutate/quick
         racket/stream)

(define program-mutations
  (build-mutation-engine
   #:mutators
   (define-simple-mutator (if-swap stx)
     #:pattern ({~datum if} cond t e)
     #'(if cond e t))
   (define-constant-mutator (constant-swap v)
     [(? number?) #:-> (- v)])
   #:syntax-only
   #:streaming
   #:module-mutator))

(define program-to-mutate
  #'(module test-program racket
      (#%module-begin
       (require "a.rkt")
       (define x (if (yes?) 0 42))
       (define y (if (negative? x)
                     "negative!"
                     (if (zero? x)
                         "zero!"
                         "positive!")))
       (displayln y))))

> (map syntax->datum (stream->list (program-mutations program-to-mutate)))
'((module test-program racket
    (#%module-begin
     (require "a.rkt")
     (define x (if (yes?) 42 0))
     (define y
       (if (negative? x) "negative!" (if (zero? x) "zero!" "positive!")))
     (displayln y)))
  (module test-program racket
    (#%module-begin
     (require "a.rkt")
     (define x (if (yes?) 0 -42))
     (define y
       (if (negative? x) "negative!" (if (zero? x) "zero!" "positive!")))
     (displayln y)))
  (module test-program racket
    (#%module-begin
     (require "a.rkt")
     (define x (if (yes?) 0 42))
     (define y
       (if (negative? x) (if (zero? x) "zero!" "positive!") "negative!"))
     (displayln y)))
  (module test-program racket
    (#%module-begin
     (require "a.rkt")
     (define x (if (yes?) 0 42))
     (define y
       (if (negative? x) "negative!" (if (zero? x) "positive!" "zero!")))
     (displayln y))))

1.3 The apis of this library🔗ℹ

This library provides three different tiers of interface to defining mutators that provide different levels of abstraction.

The High level mutator api offers pattern-based mutator definition forms and a convenient syntax for building a mutation engine in one step. This api should suffice for most mutators.
For more complex mutators, the Low-level mutator tools provides a low-level api for defining complex mutators that need fine-grained control of how to perform mutations.
Finally, the Mutator combinators provides a small combinator-like language for creating mutators out of other mutators (or plain functions) and otherwise manipulating mutators.

1	Prologue
2	High level mutator api
3	Low-level mutator tools
4	The mutation literature
5	Pre-defined mutators

1.1	Mutation concepts
1.2	A full example
1.3	The apis of this library