schemata

Documentation

Overview

Package schemata turns per-mutant source files into one instrumented file that selects a mutant at run time, so a release compiles once instead of once per mutant.

The measured reason it exists: the fixed cost of starting `go test` is 750-950 ms per mutant regardless of how fast the suite is, and it is the dominant cost of a run. See docs/experiments/test-invocation.md.

Index

• func Instrument(source []byte, gates []Gate) ([]byte, []int)
• type Gate
  • func Expand(source []byte, replacement Replacement) (Gate, bool)
• type Kind
• type Planned
  • func Plan(original []byte, mutants [][]byte) Planned
• type Replacement
  • func Difference(original, mutated []byte) (Replacement, bool)

Functions

func Instrument

func Instrument(source []byte, gates []Gate) ([]byte, []int)

Instrument rewrites every gate into one file that chooses a mutant at run time, and returns the selector value for each gate it was given — zero for one it could not gate.

A gate that gets zero is not lost: it keeps the path ditto has always taken, its own file and its own compilation. Every mutant that worked before still works, which is the constraint this whole change is under.

Types

type Gate

type Gate struct {
	Start, End int
	Original   string
	Mutated    string
	Kind       Kind
}

Gate is one mutant, expressed as an expression that can be swapped for another at run time.

func Expand

func Expand(source []byte, replacement Replacement) (Gate, bool)

Expand widens a replacement to the smallest expression that contains it, and admits it only if that expression is one a gate can stand in for.

Refusing is not a failure. A refused site keeps the path ditto has always taken — its own file, its own compilation — so every mutant that worked before still works, which is the constraint this whole change is under. What is admitted here is only what has been measured to reach the same verdicts: comparisons, and integer literals.

Arithmetic is deliberately absent. `a + b` is an expression, but not a bool, and the generated function it would need has not been measured against real verdicts. Statements are absent because no expression can replace one.

type Kind

type Kind int

Kind is how a mutant gets selected at run time, and there is one per shape of expression rather than one per virus.

const (
	// Boolean substitutes an expression of the same type:
	//
	//	a > b   ->   (m == id && a >= b) || (m != id && a > b)
	//
	// Short-circuiting reaches exactly one side, so each operand is evaluated
	// once — measured, because an operand evaluated twice would change any
	// expression whose operands have side effects.
	Boolean Kind = iota

	// Integer substitutes a call, because Go has no conditional expression and
	// an integer literal is not a bool. A call is never a constant, so this does
	// not stand where Go requires one — measured at 3 sites in 91.
	Integer
)

type Planned

type Planned struct {
	// Instrumented is the file to compile once. It equals the original when
	// nothing could be gated.
	Instrumented []byte

	// Selector holds one value per mutant handed in, in the same order: the
	// number to put in the environment to select it, or zero for a mutant that
	// has to keep its own file and its own compilation.
	Selector []int
}

Planned is the gated form of one source file.

func Plan

func Plan(original []byte, mutants [][]byte) Planned

Plan turns a file and its mutants into one instrumented file.

This is where ditto's own output meets the gated path: GoInfectedFile.Mutate already produces, per mutant, the original bytes and the mutated ones, and every mutation this can gate is read off that pair. No virus is re-implemented here, and there is no table of operators to fall out of step with the fourteen that own them.

The mutants must be rendered the same way the original is. Mutate prints the tree with format.Node while the original is the file's own bytes, so for a file that is not gofmt'd the difference between them carries formatting as well as the mutation. There is no gate in such a difference, and the answer is a zero selector rather than a wrong gate.

type Replacement

type Replacement struct {
	Start, End int
	Original   string
	Mutated    string
}

Replacement is the one stretch of bytes a mutation replaced, in the original's coordinates. An insertion has an empty Original; a deletion, an empty Mutated.

func Difference

func Difference(original, mutated []byte) (Replacement, bool)

Difference reports the single range in which two versions of a file differ.

It reads the answer off the mutated file rather than asking the viruses what they did. Teaching this package what each of the fourteen viruses replaces would be a second copy of knowledge that already lives in one place, and a second copy is one that goes stale without anything failing.

It reports false only when the two files are identical. Two edits in one file are reported as the single span that covers both, which is not something a gate can use — but refusing it here would need a real diff, and the check already has to exist further along: that span is not an expression, and the gate builder has the syntax tree to say so. One check, in the place that can make it.

An earlier version of this carried a guard that re-applied the replacement and compared. It could not fail: the range is derived from the two files, so rebuilding from it reproduces the second one by construction. A check that cannot fail reads like a guarantee and is not one.