testgen: Simple Exhaustive Testing

You should brute force your testing whenever you can afford to. Computers are fast. Use them.

testgen is a simple library for exhaustive testing of tractable state spaces:

• simple: under 600 lines of code
• exhaustive testing: brute forcing every test case for a set of variables
• state space: the full set of combinations of variable values under test; each is a test case
• tractable: whatever your threshold for combinatorial explosion of possibilities is (in terms of test cost)

Rationale

Go unit tests should be fast and usually are. It's fairly typical to have test cases that execute in 1/10,000th of a second. That means even a test with 100,000 cases can run in 10 seconds. Since many unit tests are only covering a relatively small number of variables and possible values, it makes sense to test all of them.

Unfortunately, writing out 1000s of test cases by hand is so painful and time consuming that nobody ever does it, and we needlessly miss test combinations as a result. This is especially unfortunate in cases, like security policy, where you really want as comprehensive coverage as possible.

So, instead, spend your effort on defining the bounds of the state space that make sense to test for your scenario, and let the computer brute force all the cases for you.

Brief Library Tour

A few key pieces worth knowing:

• func NewBuilder[W, G any](t *testing.T, in World) *Builder[W, G] is the main harness for setting up a test. It uses the "builder" pattern to make it easy to construct tests with a chain of function calls. The builder is generic in terms of the "got" and "want" types that you define as the test author.
• type World map[string]Values is your description of the "state space" that should be completely covered by the set of generated test cases. It's a map of variable names to the range of Values those variables can assume during the test.
• func (r *Builder[W, G]) Want(pattern Pattern, set func(*W)) *Builder[W, G]: lets you configure the expected result for the set of test cases that match the Pattern. A Pattern is just a map[string]any that describes which values to consider, just like setting up a World.
• func (r *Builder[W, G]) DefaultWant(set func(*W)) *Builder[W, G]: like Want, but sets a global default.
• func (r *Builder[W, G]) Check(doc string, f func(got *G, want *W) bool) *Builder[W, G]: is how you define the test result evaluator. The function passed to Check will be evaluated to compare the got and want, and should return true when they match.
• func (r *Builder[W, G]) Cases() *TestCases[W, G] finalizes the Builder and returns a TestCases that holds the set of cases to execute.
• func (cs *TestCases[W, G]) Eval(test func(input Input) *G) Results executes the "guts" of your test for each generated case. This is where you map the generated Input test case to the actual system you're testing. The function passed to Eval is evaluated for each test case and should return the "got" type that you defined for your World, so it can be compared to the "want" by Check. To render the results in Go subtests for output purposes, call the Run() method on the Results returned by Eval.

There are a few other convenience features, and these two are particularly useful:

• func (cs *TestCases[W, G]) CheckNumCases(want int) *TestCases[W, G]: It's pretty easy to do the napkin math on how many combinations exist, and you can plug that number into CheckNumCases to confirm that the library is generating the same number of cases you expect.
• func (cs *TestCases[W, G]) LockFile(create bool) *TestCases[W, G]: The LockFile feature writes all generated test cases out to a file in the testdata/ dir next to your *_test.go file. This allows you to commit the generated test cases in source control, allowing detailed review and preserving granular history of changes to generated tests. Pass true to generate the file. testgen will then fail when the runtime- generated tests do not match this file, enabling you to more easily detect subtle differences. It is recommended to always use LockFile(false) in normal operation so that accidental deletion of the lockfile causes tests to fail, rather than pass with changes due to regenerating the file.

Usage

The below pseudo-Go examples describe how to use testgen. You can also find real examples of testgen usage in the testgen_test.go file, which uses testgen to test itself.

High-level structure of a testgen test

import gen ".../testgen"

func TestSomething(t *testing.T) {
  // define output schema
  type want struct {...}
  type got want

  // define state space
  world := gen.World{...}

  // start Builder
  gen.NewBuilder[want, got](t, world).
    // set default expectation
    DefaultWant(func(w *want) { ... }).
    // set custom expectations for specific patterns
    Want(gen.Pattern{ ... }, func(w *want) { ... }).
    Want(gen.Pattern{ ... }, func(w *want) { ... }).
    // define got vs. want equality
    Check("got matches want", func(g *got, w *want) bool { ... }).
    // generate the test cases
    Cases().
    // check the number of cases against your own math
    CheckNumCases( ... ).
    // save generated cases to a lockfile
    LockFile( ... ).
    // execute this function for every generated case
    Eval(func(in gen.Input) *got { ... }).
    // uses Go subtests to output the test results
    Run(t)
}

Setting up a World

A World is a list of variables to test and a list of values that should be tested for each variable. Each list of values should be a Range. It looks like this:

world := gen.World{
  "name": gen.Range[string]{"foo", "bar"},
  "someLabel": gen.Range[string]{
    "nil", // test author's convention: label key not set
    "",
    "invalid",
    "12345",
  },
  "enabled": gen.Range[bool]{true, false},
}

Constructing the Builder

Tests produce a "got" type as the result, which gets compared to a "want" type afterwards to determine if the test passed or failed. It's up to you how to define these tests. In the below example, the test author is testing a policy system that can return policy violations or errors. The author doesn't care about the exact violations, just that invalid cases are blocked, so they adopted a convention that Violations can be set to a []string{"+"} in "want" definitions to indicate that at least one violation is expected.

Then the custom types, along with the world defined above, are passed in to the NewBuilder function to construct the Builder. Subsequent methods chain off of this object.

type want struct {
  // test author convention: set Violations to []string{"+"}
  // to indicate that at least one violation is expected
  Violations []string `json:"violations"`
  Error      error    `json:"error"`
}
type got want

// pass in the testing.T and world
gen.NewBuilder[want, got](t, world). // ...

Want and Patterns

Chaining onto the Builder set up above, the author defines a default expectation that the policy under test rejects all input. This enables the author to specify just the Patterns where the policy should allow the action. Here, they expect it to be allowed when someLabel is "12345", or whenever the policy is disabled.

  // set default expectation
  DefaultWant(func(w *want) {
    w.Violations = []string{"+"}
  }).
  // set custom expectations for specific patterns
  Want(
    gen.Pattern{
      "enabled": false,
  }, func(w *want) { w.Violations = nil }).
  Want(
    gen.Pattern{
      "name":      gen.Range[string]{"foo", "bar"},
      "someLabel": "12345",
      "enabled": true,
  }, func(w *want) { w.Violations = nil }). // ...

Defining pass vs. fail with Check

In order to actually implement their convention for expecting "one or more violation," the test author adds some custom logic in Check:

  Check("got matches want", func(g *got, w *want) bool {
    if len(w.Violations) == 1 && w.Violations[0] == "+" {
      // expect at least one violation
      if len(g.Violations) == 0 {
        return false
      }
      return cmp.Equal(g.Error, w.Error)
    }
    return cmp.Equal(g, (*got)(w),
      // Also a good time to allow unexported fields or make
      // other modifications to equality checks if necessary.
      cmp.Exporter(func(_ reflect.Type) bool { return true }))
  }).
  Cases(). // ...

Generate the cases

After Check is defined, call Cases to generate the test cases before continuing.

Using the CheckNumCases feature

After test cases are generated, you can do the following to confirm you got the number you expected:

  CheckNumCases(16). // ...

Using the LockFile feature

After test cases are generated, you can toggle the LockFile feature in order to save tests to a file so that testgen can confirm future test runs use the same set of test cases. This is also helpful for code reviewers who still want to see all the cases in expanded form.

Generate the lockfile by passing true:

  LockFile(true). // ...

Retain checking against the lockfile without regenerating by passing false:

  LockFile(false). // ...

The lockfile will be written to testdata/{test_name}.json in the same location as the *_test.go file. It is recommended to always use LockFile(false) in normal operation so that accidental deletion of the lockfile causes tests to fail, rather than pass with changes due to regenerating the file.

A lockfile records the input and want in the following format:

[
{"input":{"name":"foo","someLabel":"nil"},"want":{"violations":["+"],"error":null}},
// ...
]

Executing tests with Eval

Tests are executed by calling Eval. The contents of Eval are similar to the for loop you would typically write for table-driven tests. This is where you wire each test case up to the actual system under test. Here, the test author sets up their policy system (enabling it only if the "enabled" test variable is true) and a request, derived from the test case input, to validate. Then, they check for violations and errors in the result, and use these to construct the appropriate got, which is returned to testgen so that testgen can check it with Check.

  Eval(func(in gen.Input) *got) {
    ps := NewPolicySystem(in.["enabled"].(bool))
    req := Request{
      Name: in["name"].(string),
      Label: in["someLabel"].(string),
    }
    resp, err := s.Validate(req)
    if err != nil {
       return &got{
         Error: err,
       }
     }
     if resp == nil {
       return &got{} // no violations and no errors
     }
     return &got{
       Violations: resp.Violations,
     }
  }). // ...

Output via Go subtests

Finally, call Run() to output results per test case using Go subtests, against the testing.T that the Builder was originally constructed with.

// ...
gen.NewBuilder[want, got](t, world).
  // ...
  Run() // and we're done!

Disclaimer

This is not an officially supported Google product. This project is not eligible for the Google Open Source Software Vulnerability Rewards Program.