# FuzzTest Implementation Notes

IMPORTANT: this document is an internal team document for extending
FuzzTest. Do not extend your own types for FuzzTest without first
consulting the
FuzzTest team.
Instead, use the existing domains or combinators of existing domains as noted
within the [Domains Reference](../domains-reference.md).

FuzzTest is an extensible framework. This guide documents how to extend
FuzzTest to fuzz types appropriately and intelligently using custom
domains.

## Domains

This is a skeleton for a Domain implementation. Note that a Domain object is not
designed to retain state, but only to create an instance of a type, and provide
mutation services for an existing object of that type.

Conceptually, a Domain represents a space of possible values, and a method for
traversing that space. A concept of 'nearness' is useful if possible; for
example, a Domain that mutates the string `cheese` to `chease` is useful in a
way that one which is as likely to mutate it to `xyzzy` is not.

```c++
template <typename T>
class MyDomain {
 public:
  using value_type = T;

  MyDomain(/* params */) {
    /* set up space of possible values here */
  }

  template <typename PRNG>
  T Init(PRNG& prng) {}

  template <typename PRNG>
  void Mutate(T& val, PRNG& prng, bool only_shrink) {}

 private:
  /* params stored here */
}
```

The `PRNG` type parameter is filled by a uniform random bit generator, such as
[absl::BitGen](https://abseil.io/docs/cpp/guides/random).

### Init

```c++
template <typename PRNG>
T Init(PRNG& prng);
```

The `Init` method returns an arbitrary value in the domain. This may be, for
example, an empty container for a container type, or a random element for an
`ElementOf` domain. Note that this is separate from a *constructor*; a
constructor sets up a Domain, and `Init` produces an initial value from it.

### Mutate

```c++
template <typename PRNG>
void Mutate(T& val, PRNG& prng, bool only_shrink);
```

The `Mutate` method makes a small change on an existing value. The `only_shrink`
parameter is used for case reduction; the precise semantics of what it means to
grow or shrink a value of a given type are type-specific.

There is no guarantee that `val` is within the Domain's possibility space. For
example, a Domain representing positive integers could be given the number -1.
In cases where this is possible, it is recommended that `Mutate` simply call
`Init` on nonconforming inputs.

## Custom `corpus_type`

Domains have a `value_type`; in many cases--for example, a domain consisting of
integers--this value uniquely defines a point in the space of possible values.
However, other types may not allow for this; for example, a domain which chooses
one element from a list where they're not all necessarily unique. In this case,
the domain can have a `corpus_type` representing its internal state, and a
`value_type` representing its output.

The `DomainTraits` class, which takes a `Domain` as a type parameter, wraps this
idea. If your `Domain` sets `has_custom_corpus_type` to `true`, you can set a
custom `corpus_type` property different from the `value_type`, and add a
`GetValue` function to convert a `corpus_type` value into the corresponding
`value_type`.

For example, consider a domain which represents strings generated by a regular
expression. It's much easier to mutate an explicit DFA path than to convert a
string back and forth, so we use `std::string` as the `value_type` and a
representation of the path as the `corpus_type`.

```c++
class RegexDomain {
 public:
  using value_type = std::string;
  static constexpr bool has_custom_corpus_type = true;
  using corpus_type = DFAPath;

  MyVectorDomain(std::string regex) : dfa_(DFA::Parse(regex)) {}

  template <typename PRNG>
  corpus_type Init(PRNG& prng) {
    return dfa_.Generate(prng);
  }

  template <typename PRNG>
  void Mutate(corpus_type& val, PRNG& prng, bool only_shrink) {
    dfa_.Mutate(prng, val);
  }

  value_type GetValue(const corpus_type& value) const {
    static_assert(has_custom_corpus_type);
    return dfa_.ToString(value);
  }

 private:
  DFA dfa_;
}
```

Whether or not your domain (say, `MyDomain`) defines these explicitly, you can
evaluate:

| Function                                         | Default value          |
| ------------------------------------------------ | ---------------------- |
| `DomainTraits<MyDomain>::has_custom_corpus_type` | `false`                |
| `DomainTraits<MyDomain>::corpus_type`            | `MyDomain::value_type` |
| `DomainTraits<MyDomain>::GetValue(Domain& d,     | Returns `value`.       |
: const corpus_type& value)`                       :                        :