quickcheck: Arbitrary is derivable but Shrink is not

[bobzhang]

Is your feature request related to a problem? Please describe.

check requires both Arbitrary and Shrink, but only one of them can be derived:

pub struct Point { x : Int; y : Int } derive(Debug, @qc.Arbitrary)          // ok
pub struct Point { x : Int; y : Int } derive(Debug, @shrink.Shrink)         // error
// Don't know how to derive trait @shrink.Shrink for type Point

So the path of least resistance for a custom type is a hand-written no-op instance, which silently disables shrinking — the counterexample keeps irrelevant noise. Same seed, same property shape:

derived Arbitrary + no-op Shrink -> Falsified(counterexample={ x: 3, y: -8 }, shrinks=0, shrink_attempts=0)
Int (real Shrink instance)       -> Falsified(counterexample=3,              shrinks=0, shrink_attempts=2)

The y: -8 is unrelated to the failing predicate and would be minimized away by any structural shrinker. Nothing warns that shrinking is inert.

Describe the solution you'd like

derive(Shrink) for structs and enums:

• struct: shrink one field at a time, holding the others fixed;
• enum: shrink the payload within a constructor, optionally toward earlier constructors.

Important: for recursive types, field-wise shrinking alone is close to useless — it only ever shrinks leaves, so the structure never gets smaller and counterexamples stay large. A derived instance should also replace a node with its same-typed subterms (what Haskell's genericShrink does via subterms); the compiler knows which fields are Self-typed, and subterms are structurally smaller so well-foundedness is preserved. I would argue the feature is only worth shipping with that included.

Describe alternatives you've considered

Hand-writing instances (what we did — 97 lines for a two-type model, most of it mechanical field/entry plumbing), or accepting the no-op and losing shrinking.

Additional context

I understand this is a compiler-side change rather than a core-library one: derive is a closed set in moonc (a user-defined trait cannot be derived at all), and the table is Arbitrary, Compare, Debug, Default, FromJson, Hash, Show, ToJson. Filing here because that is where quickcheck lives and where the pain is felt — please move it if the compiler repo is the right home. Arbitrary already being in that table suggests the incremental cost is a table entry plus a codegen rule shaped like Arbitrary's.

Note that #4076 (Shrink for Map) blocks derive from being useful on map-shaped models regardless.

Verified against the 2026-08-11 toolchain. Related: #4076, #4077, #4078.

• I do think that this should be part of the core library and should be delivered to all the MoonBit developers.

[CAIMEOX]

Different from Arbitrary, I think there are more design choices here that are worth making explicit before adding derive(Shrink), because there is no single obviously correct notion of a "derived shrinker".

The first question is what the default semantics should be. There are several defensible choices. At one extreme, the default could be “do not shrink unless the user explicitly provides a Shrink implementation” (the Iter::empty()). At the other extreme, we could follow Haskell QuickCheck's genericShrink-style approach and derive a structural shrinker: shrink fields independently, and for recursive types additionally replace a value with structurally smaller subterms. The latter is much more useful in practice, but it also implicitly defines a notion of structural simplicity that may not coincide with the domain semantics of the type.

Enums make this especially visible. Shrinking the payload of the current constructor is relatively uncontroversial, but shrinking “toward earlier constructors” is not semantically stable. Constructor declaration order usually carries no meaning about which value is simpler. For example:

enum State {
  Running(...)
  Failed(...)
  Idle
}

There is no principled reason to say that Running is simpler than Failed, or that reordering the declarations should change the minimal counterexample produced by QuickCheck. A derived shrinker should therefore probably avoid constructor-to-constructor shrinking unless the user explicitly opts into or configures such an ordering.

Cross-constructor shrinking presents another issue: how do we generate the data out of thin air? Suppose, in the example below, we attempt to shrink B("hello") into some A(??); the question then becomes how to construct the Int inside A.

enum E {
  A(Int)
  B(String)
}

We may consider

• Default::default()
• Arbitrary::arbitrary(...)
• ...

However, these all implicitly introduce new semantic assumptions. And it introduces non-trivial dependencies between traits (which go beyond standard supertrait relationships, as they require a specific component of the type to have a certain instance).

This suggests that derive(Shrink) may be most useful if we think of it as providing a good structural default, while still allowing users to customize parts of the policy.

The above outlines some of the issues encountered when dealing with derive(Shrink). I will submit another proposal later regarding the design of this custom parts.

[CAIMEOX]

I propose a relatively simple set of default shrink rules.

Product Types

struct S {
  a: A
  b: B
} derive(Shrink)

Semantically equivalent to the following expansion:

shrink(a).map((a2) => { a: a2, b }) + shrink(b).map((b2) =>  { a, b: b2 })

Fields are processed in the order defined in the source code. This makes the branching factor additive and ensures stable behavior, consistent with Haskell QuickCheck's experience.

Sum Types

enum Tree[T] {
  Leaf
  Node(T, Tree[T], Tree[T])
} derive(Shrink)

For every constructor:

• If a direct Self subterm exists in the payload, then yield the subterm
• Keep the constructor C unchanged and shrink one payload field at a time

For term Node(x, l, r) it generates:

[| l, r |]  // subterms
+ shirnk(x).map(x1 => Node(x1, l, r))
+ shirnk(l).map(l1 => Node(x, l1, r))
+ shrink(r).map(r2 => Node(x, l, r2))

We do not assume which of the unrelated constructors is simpler. In theory, we could support additional configuration options, similar to FromJson and ToJson, but this would undoubtedly increase complexity, so we are not considering it for the time being.