Shrinking

Description

Each generated Value can be shrunk to 2 new values. These are named a and b and wrapped in a Dichotomy.

This allows to take a different route when a shrunk value makes a test pass.

Usually the a strategy is the more aggressive shrinking strategy to try to find the smallest value as fast as possible. And b is the more fine grained one, but will take longer.

The difficult part of the shrinking mechanism is that values can be mapped/composed to new ones and must adhere to a predicate. And each low level shrunk value must be mapped/composed back and still adhere to the predicate.

To keep the shrinkers as simple as possible the mapping and predicates are hidden from them.

To do this a Value will always keep the original value, all the transformations steps (aka mapping) and the predicate it must adhere to. Then when a shrinker applies a shrinking strategy to a Value, the value can re-apply the transformations to the shrunk value and make sure the new value adheres to the predicate.

Sequence

graph TB
    Array -->|Next| RecursiveHalf{Either}
    RecursiveHalf -->|a| RemoveHalf
    RecursiveHalf -->|b| RemoveTail
    RemoveHalf -->|Next| RecursiveHalf
    RemoveTail -->|Next| RecursiveTail{Either}
    RecursiveTail -->|a| RemoveTail
    RecursiveTail -->|b| RemoveHead
    RemoveHead -->|Next| RecursiveHead{Either}
    RecursiveHead -->|a| RemoveHead
    RecursiveHead -->|b| RemoveNth
    RemoveNth -->|Next| RecursiveNth{Either}
    RecursiveNth -->|"a(n)"| RemoveNth
    RecursiveNth -->|"b(n+1)"| RemoveNth
    RemoveNth -->|When n overflows| ShrinkANth[Shrink nth element with strategy A]
    ShrinkANth -->|Next| RecursiveNthShrink{Either}
    RecursiveNthShrink -->|"a(n)"| ShrinkANth
    RecursiveNthShrink -->|"b(n+1)"| ShrinkANth
    ShrinkANth -->|When n overflows| ShrinkBNth[Shrink nth element with strategy B]
    ShrinkBNth -->|Next| RecursiveNthShrink
    ShrinkBNth -->|When no longer shrinkable| Identity

This design makes sure all elements are shrunk to their minimum values. It's assured when shrinking elements of the array with their a or b strategy. When we apply a strategy makes the test pass we try to shrink the next available value in the array. This privileges first shrinking values that do not affect the test.

This strategy means the values that affect the failing test are shrunk last. So it will take more shrinking steps to find the minimum values that make a test fail.

Composite

graph TB
    Composite -->|Next| RecursiveNthShrink{Either}
    RecursiveNthShrink -->|"a(n)"| ShrinkANth
    RecursiveNthShrink -->|"b(n+1)"| ShrinkANth
    ShrinkANth -->|When n overflows| ShrinkBNth[Shrink nth element with strategy B]
    ShrinkBNth -->|Next| RecursiveNthShrink
    ShrinkBNth -->|When no longer shrinkable| Identity

This design is identical to the Sequence one except it doesn't need to remove elements from the composite. It only shrinks elements of the composite.

Seeded values

The complexity of seeded values lies with the filtering of these values when shrinking.

Let's take a simple example:

use Innmind\BlackBox\Set;

Set::strings()->filter(static fn(string $string) => $string !== '');

The Set can apply this filter and not yield any empty string. And for any yielded ones if can access the predicate when shrinking the strings in order to not create Dichotomys with invalid strings.

The problem with seeded values can be expressed with this example:

use Innmind\BlackBox\Set;

Set::integers()
    ->flatMap(
        static fn(Set\Seed $int) => Set::strings()->map(
            static fn(string $string) => $int->map(
                static fn(int $int) => $int.$string,
            ),
        ),
    )
    ->filter(static fn(string $string) => $string !== '0');

Here when the filter is applied it abstracts that the string is seeded with a leading int. But in the implementation it can't know where the seed comes from. So it can't affect the way the int could be shrunk.

The problem here is that the Dichotomy attached to any Value is statically defined when yielding it.

To still correctly filter out seeded values the predicate is attached to the Value object and is check on both values generated by a Dichotomy to make sure both are acceptable. If not both are then it prevents shrinking the seed.

This design prevents shrinking to the minimum values in the case only one of the shrunk values is acceptable.

A research should be conducted to improve the shrinking system to fix this shortcoming of seeded values.