Repository: dubzzz/fast-check
Pull request #1598 (2021-03-09 21:08:04)

✨ Add `withCrossShrink` constraint on `fc.frequency`
<!-- Why is this PR for? -->
<!-- Describe the reason why you opened this PR or give a link towards the associated issue. -->

## In a nutshell

✔️ New feature
❌ Fix an issue
❌ Documentation improvement
❌ Other: *please explain*

(✔️: yes, ❌: no)

## Potential impacts

No impact expected. But as it impacts the constructor phase of `frequency` we may have missed some unwanted side-effects affecting final users.

codesandbox[bot]: This pull request is automatically built and testable in [CodeSandbox](https://codesandbox.io).

  To see build info of the built libraries, click [here](https://ci.codesandbox.io/status/dubzzz/fast-check/pr/1598/builds/108364) or the icon next to each commit SHA.

Latest deployment of this branch, based on commit 9daec5b634d9c990fbe5c688be59fa9d510eb0c5:

|Sandbox| Source |
|--|--|
|[Vanilla](https://codesandbox.io/s/vanilla-43pde)| Configuration |
|[fast-check-examples](https://codesandbox.io/s/fast-check-examples-qvzuy)| Configuration |

codecov[bot]: # [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=h1) Report
> Merging [#1598](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=desc) (9daec5b) into [main](https://codecov.io/gh/dubzzz/fast-check/commit/590bfecadef13dec07a9c64abdb5442621047cc0?el=desc) (590bfec) will **increase** coverage by `0.01%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/dubzzz/fast-check/pull/1598/graphs/tree.svg?width=650&height=150&src=pr&token=fRi2fJN730)](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##             main    #1598      +/-   ##
==========================================
+ Coverage   97.43%   97.45%   +0.01%     
==========================================
  Files          92       92              
  Lines        3158     3178      +20     
  Branches      613      617       +4     
==========================================
+ Hits         3077     3097      +20     
  Misses         77       77              
  Partials        4        4              
```

| Flag | Coverage Δ | |
|---|---|---|
| unit-tests | `97.45% <100.00%> (+0.01%)` | :arrow_up: |
| unit-tests-10.x-Linux | `97.41% <100.00%> (-0.02%)` | :arrow_down: |
| unit-tests-12.x-Linux | `97.45% <100.00%> (+0.01%)` | :arrow_up: |
| unit-tests-14.x-Linux | `97.45% <100.00%> (+0.01%)` | :arrow_up: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/check/arbitrary/FrequencyArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1598/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9GcmVxdWVuY3lBcmJpdHJhcnkudHM=) | `98.03% <100.00%> (+1.26%)` | :arrow_up: |
| [src/fast-check-default.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1598/diff?src=pr&el=tree#diff-c3JjL2Zhc3QtY2hlY2stZGVmYXVsdC50cw==) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=footer). Last update [590bfec...9daec5b](https://codecov.io/gh/dubzzz/fast-check/pull/1598?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/documentation/Arbitraries.md b/documentation/Arbitraries.md
index 1f2cd343..c9e07dde 100644
--- a/documentation/Arbitraries.md
+++ b/documentation/Arbitraries.md
@@ -2147,14 +2147,18 @@ fc.oneof(fc.char(), fc.boolean(), fc.nat())
 > Generate one value based on one of the passed arbitraries
 >
 > Randomly chooses an arbitrary at each new generation. Should be provided with at least one arbitrary. Probability to select a specific arbitrary is based on its weight, the higher it is the more it will be probable. It preserves the shrinking capabilities of the underlying arbitrary.
+>
+> **Warning:** In the upcomping major releases of fast-check the first arbitrary specified on `frequency` will have a privileged position. Constraints like `withCrossShrink` tend to favor it over others and will probably be enabled by default.
 
 *&#8195;Signatures*
 
 - `fc.frequency(...{ arbitrary, weight })`
+- `fc.frequency({withCrossShrink?}, ...{ arbitrary, weight })`
 
 *&#8195;with:*
 
 - `...{ arbitrary, weight }` — _arbitraries that could be used to generate a value along their weight (the higher the weight, the higher the probability to select this arbitrary will be)_
+- `withCrossShrink?` — default: `false` — _in case of failure the shrinker will try to check if a failure can be found by using the first specified arbitrary (if and only if its weight is strictly greater than 0). It may be pretty useful for recursive structures as it can easily help reducing their depth in case of failure_
 
 *&#8195;Usages*
 
@@ -2164,6 +2168,16 @@ fc.frequency(
   { arbitrary: fc.boolean(), weight: 1 }
 )
 // Examples of generated values: true, "&", "8", false, "["…
+
+fc.frequency(
+  { withCrossShrink: true },
+  { arbitrary: fc.boolean(), weight: 2 },
+  { arbitrary: fc.array(fc.boolean()), weight: 1 }
+)
+// Note: In case of failure on an array of boolean values the shrinker will first try to check
+// if a failure can also be triggered with a simple boolean (the first arbitrary specified)
+// if not it will carry on the classical shrinking strategy defined for arrays of boolean.
+// Examples of generated values: true, [true,false], [true,false,false], [false,true,true], [false]…
 ```
 </details>
 
diff --git a/src/check/arbitrary/FrequencyArbitrary.ts b/src/check/arbitrary/FrequencyArbitrary.ts
index e8818d8e..e8d280fe 100644
--- a/src/check/arbitrary/FrequencyArbitrary.ts
+++ b/src/check/arbitrary/FrequencyArbitrary.ts
@@ -1,4 +1,5 @@
 import { Random } from '../../random/generator/Random';
+import { Stream } from '../../stream/Stream';
 import { Arbitrary } from './definition/Arbitrary';
 import { Shrinkable } from './definition/Shrinkable';
 
@@ -27,7 +28,7 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
   readonly summedWarbs: WeightedArbitrary<T>[];
   readonly totalWeight: number;
 
-  static from<T>(warbs: WeightedArbitrary<T>[]) {
+  static from<T>(warbs: WeightedArbitrary<T>[], constraints: FrequencyContraints) {
     if (warbs.length === 0) {
       throw new Error('fc.frequency expects at least one weigthed arbitrary');
     }
@@ -42,9 +43,9 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
     if (totalWeight <= 0) {
       throw new Error('fc.frequency expects the sum of weights to be strictly superior to 0');
     }
-    return new FrequencyArbitrary(warbs);
+    return new FrequencyArbitrary(warbs, constraints);
   }
-  private constructor(readonly warbs: WeightedArbitrary<T>[]) {
+  private constructor(readonly warbs: WeightedArbitrary<T>[], readonly constraints: FrequencyContraints) {
     super();
     let currentWeight = 0;
     this.summedWarbs = [];
@@ -57,12 +58,40 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
   generate(mrng: Random): Shrinkable<T> {
     const selected = mrng.nextInt(0, this.totalWeight - 1);
     for (let idx = 0; idx !== this.summedWarbs.length; ++idx) {
-      if (selected < this.summedWarbs[idx].weight) return this.summedWarbs[idx].arbitrary.generate(mrng);
+      if (selected < this.summedWarbs[idx].weight) {
+        const itemShrinkable = this.summedWarbs[idx].arbitrary.generate(mrng);
+        if (idx === 0 || !this.constraints.withCrossShrink || this.warbs[0].weight === 0) {
+          return itemShrinkable;
+        }
+        return this.enrichShrinkable(mrng.clone(), itemShrinkable);
+      }
     }
     throw new Error(`Unable to generate from fc.frequency`);
   }
   withBias(freq: number) {
-    return new FrequencyArbitrary(this.warbs.map((v) => ({ weight: v.weight, arbitrary: v.arbitrary.withBias(freq) })));
+    return new FrequencyArbitrary(
+      this.warbs.map((v) => ({ weight: v.weight, arbitrary: v.arbitrary.withBias(freq) })),
+      this.constraints
+    );
+  }
+
+  /**
+   * Enrich a shrinkable to add another shrink case into the list of possible ones:
+   * shrink towards a value coming from the first arbitrary passed to oneof
+   * @param mrng Cloned instance of the random number generator (will be used later so might not be impacted by others)
+   * @param shrinkable Shrinkable to be enriched
+   */
+  private enrichShrinkable(mrng: Random, shrinkable: Shrinkable<T>): Shrinkable<T> {
+    let shrinkableForFirst: Shrinkable<T> | null = null;
+    const getItemShrinkableForFirst = () => {
+      if (shrinkableForFirst === null) {
+        shrinkableForFirst = this.warbs[0].arbitrary.generate(mrng);
+      }
+      return shrinkableForFirst;
+    };
+    return new Shrinkable(shrinkable.value_, () => {
+      return Stream.of(getItemShrinkableForFirst()).join(shrinkable.shrink());
+    });
   }
 }
 
@@ -77,6 +106,46 @@ export type FrequencyValue<Ts extends WeightedArbitrary<unknown>[]> = {
   [K in keyof Ts]: Ts[K] extends WeightedArbitrary<infer U> ? U : never;
 }[number];
 
+/**
+ * Constraints to be applied on {@link frequency}
+ * @remarks Since 2.14.0
+ * @public
+ */
+export type FrequencyContraints = {
+  /**
+   * When set to true, the shrinker of frequency will try to check if the first arbitrary
+   * could have been used to discover an issue. It allows to shrink trees.
+   *
+   * Warning: First arbitrary must be the one resulting in the smallest structures
+   * for usages in deep tree-like structures.
+   *
+   * Warning: First arbitrary will not be used if its weight is set to zero.
+   *
+   * @remarks Since 2.14.0
+   */
+  withCrossShrink?: boolean;
+};
+
+/**
+ * @internal
+ */
+function isFrequencyContraints(
+  param: FrequencyContraints | WeightedArbitrary<unknown> | undefined
+): param is FrequencyContraints {
+  return param != null && typeof param === 'object' && !('arbitrary' in param);
+}
+
+/**
+ * For one of the values generated by `...warbs` - the probability of selecting the ith warb is of `warb[i].weight / sum(warb[j].weight)`
+ *
+ * **WARNING**: It expects at least one (Arbitrary, weight)
+ *
+ * @param warbs - (Arbitrary, weight)s that might be called to produce a value
+ *
+ * @remarks Since 0.0.7
+ * @public
+ */
+function frequency<Ts extends WeightedArbitrary<unknown>[]>(...warbs: Ts): Arbitrary<FrequencyValue<Ts>>;
 /**
  * For one of the values generated by `...warbs` - the probability of selecting the ith warb is of `warb[i].weight / sum(warb[j].weight)`
  *
@@ -87,8 +156,20 @@ export type FrequencyValue<Ts extends WeightedArbitrary<unknown>[]> = {
  * @remarks Since 0.0.7
  * @public
  */
-function frequency<Ts extends WeightedArbitrary<unknown>[]>(...warbs: Ts): Arbitrary<FrequencyValue<Ts>> {
-  return FrequencyArbitrary.from(warbs as WeightedArbitrary<FrequencyValue<Ts>>[]);
+function frequency<Ts extends WeightedArbitrary<unknown>[]>(
+  constraints: FrequencyContraints,
+  ...warbs: Ts
+): Arbitrary<FrequencyValue<Ts>>;
+function frequency<Ts extends WeightedArbitrary<unknown>[]>(
+  ...args: [...Ts] | [FrequencyContraints, ...Ts]
+): Arbitrary<FrequencyValue<Ts>> {
+  // TODO With TypeScript 4.0 it will be possible to properly define typings for `frequency(...arbs, constraints)`
+  const constraints = args[0];
+  if (isFrequencyContraints(constraints)) {
+    return FrequencyArbitrary.from(args.slice(1) as WeightedArbitrary<FrequencyValue<Ts>>[], constraints);
+  }
+
+  return FrequencyArbitrary.from(args as WeightedArbitrary<FrequencyValue<Ts>>[], {});
 }
 
 export { frequency };
diff --git a/src/fast-check-default.ts b/src/fast-check-default.ts
index a9f5995b..e57da1c3 100644
--- a/src/fast-check-default.ts
+++ b/src/fast-check-default.ts
@@ -41,7 +41,12 @@ import { Shrinkable } from './check/arbitrary/definition/Shrinkable';
 import { dictionary } from './check/arbitrary/DictionaryArbitrary';
 import { emailAddress } from './check/arbitrary/EmailArbitrary';
 import { double, float, DoubleConstraints, FloatConstraints } from './check/arbitrary/FloatingPointArbitrary';
-import { frequency, WeightedArbitrary, FrequencyValue } from './check/arbitrary/FrequencyArbitrary';
+import {
+  frequency,
+  WeightedArbitrary,
+  FrequencyValue,
+  FrequencyContraints,
+} from './check/arbitrary/FrequencyArbitrary';
 import { compareBooleanFunc, compareFunc, func } from './check/arbitrary/FunctionArbitrary';
 import { domain } from './check/arbitrary/HostArbitrary';
 import {
@@ -345,6 +350,7 @@ export {
   Float64ArrayConstraints,
   FloatConstraints,
   FloatNextConstraints,
+  FrequencyContraints,
   IntArrayConstraints,
   IntegerConstraints,
   JsonSharedConstraints,


Test patch:
diff --git a/test/e2e/RecursiveStructures.spec.ts b/test/e2e/RecursiveStructures.spec.ts
new file mode 100644
index 00000000..3b72d1c0
--- /dev/null
+++ b/test/e2e/RecursiveStructures.spec.ts
@@ -0,0 +1,59 @@
+import * as fc from '../../src/fast-check';
+import { seed } from './seed';
+
+describe(`RecursiveStructures (seed: ${seed})`, () => {
+  // Test shrinking capabilities on very simple scenario:
+  // >  The arbitrary used as base-case for the recursive structure is a constant.
+  // >  It either pass or fail. But we ca never geenrate the wrong one and miss shrinking opportunities.
+
+  it('Should shrink letrec/oneof towards the smallest case (on very simple scenario)', () => {
+    // Arrange
+    const failingLength = 2;
+    const dataArb = fc.letrec((tie) => ({
+      // TODO - Remove `weight:2` on base-case
+      data: fc.frequency(
+        { withCrossShrink: true },
+        { arbitrary: fc.constant([0]), weight: 2 },
+        { arbitrary: fc.tuple(tie('data'), tie('data')), weight: 1 }
+      ),
+    })).data;
+
+    // Act
+    const out = fc.check(fc.property(dataArb, (data) => flat(data).length < failingLength));
+
+    // Assert
+    expect(out.failed).toBe(true);
+    expect(flat(out.counterexample![0])).toHaveLength(failingLength);
+  });
+
+  it('Should shrink memo/oneof towards the smallest case (on very simple scenario)', () => {
+    // Arrange
+    const failingLength = 2;
+    const dataArb: fc.Memo<unknown[]> = fc.memo((n) => {
+      if (n <= 1) return fc.constant([0]);
+      else
+        return fc.frequency(
+          { withCrossShrink: true },
+          { arbitrary: fc.constant([0]), weight: 1 },
+          { arbitrary: fc.tuple(dataArb(), dataArb()), weight: 1 }
+        );
+    });
+
+    // Act
+    const out = fc.check(fc.property(dataArb(5), (data) => flat(data).length < failingLength));
+
+    // Assert
+    expect(out.failed).toBe(true);
+    expect(flat(out.counterexample![0])).toHaveLength(failingLength);
+  });
+});
+
+// Helpers
+
+function flat(arr: unknown[]): unknown[] {
+  return arr.reduce((acc: unknown[], cur: unknown) => {
+    if (Array.isArray(cur)) acc.push(...flat(cur));
+    else acc.push(cur);
+    return acc;
+  }, []);
+}
diff --git a/test/type/main.ts b/test/type/main.ts
index facd0542..a9113d59 100644
--- a/test/type/main.ts
+++ b/test/type/main.ts
@@ -261,6 +261,15 @@ expectType<fc.Arbitrary<number | string>>()(
   fc.frequency({ arbitrary: fc.string(), weight: 1 }, { arbitrary: fc.nat(), weight: 1 }),
   '"frequency" with a multiple arguments of different types'
 );
+expectType<fc.Arbitrary<string | number>>()(
+  fc.frequency({}, { arbitrary: fc.string(), weight: 1 }, { arbitrary: fc.nat(), weight: 1 }),
+  '"frequency" with different types and empty constraints'
+);
+expectType<fc.Arbitrary<string | number>>()(
+  fc.frequency({ withCrossShrink: true }, { arbitrary: fc.string(), weight: 1 }, { arbitrary: fc.nat(), weight: 1 }),
+  '"frequency" with different types and some constraints'
+);
+
 // @ts-expect-error - frequency expects arbitraries not raw values
 fc.frequency({ arbitrary: fc.string(), weight: 1 }, { arbitrary: '1', weight: 1 });
 
diff --git a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
index 1552af4f..e51f2515 100644
--- a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
+++ b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
@@ -11,41 +11,63 @@ import * as genericHelper from './generic/GenericArbitraryHelper';
 
 describe('FrequencyArbitrary', () => {
   describe('frequency', () => {
-    const seedGenerator = fc
-      .array(
-        fc.record({
-          type: fc.constantFrom('unique', 'range'),
-          value: fc.nat(),
-          weight: fc.nat(),
-        }),
-        { minLength: 1 }
-      )
-      .filter((config) => {
-        const totalWeight = config.reduce((acc, e) => acc + e.weight, 0);
-        return totalWeight > 0;
-      });
+    const seedGenerator = fc.record(
+      {
+        data: fc
+          .array(
+            fc.record({
+              type: fc.constantFrom('unique', 'range'),
+              value: fc.nat(),
+              weight: fc.nat(),
+            }),
+            { minLength: 1 }
+          )
+          .filter((config) => {
+            const totalWeight = config.reduce((acc, e) => acc + e.weight, 0);
+            return totalWeight > 0;
+          }),
+        constraints: fc.record({ withCrossShrink: fc.boolean() }, { requiredKeys: [] }),
+      },
+      { requiredKeys: ['data'] }
+    );
     type SeedGeneratorType = typeof seedGenerator extends fc.Arbitrary<infer T> ? T : never;
 
     genericHelper.isValidArbitrary(
       (metas: SeedGeneratorType) => {
-        const arbs = metas.map((m) =>
+        const arbs = metas.data.map((m) =>
           m.type === 'unique'
             ? { arbitrary: constant(m.value), weight: m.weight }
             : { arbitrary: integer(m.value - 10, m.value), weight: m.weight }
         );
-        return frequency(...arbs);
+        if (metas.constraints === undefined) {
+          return frequency(...arbs);
+        }
+        return frequency(metas.constraints, ...arbs);
       },
       {
         seedGenerator,
         isValidValue: (v: number, metas: SeedGeneratorType) => {
-          for (const m of metas) {
+          for (const m of metas.data) {
             if (m.weight === 0) continue;
             if (m.type === 'unique' && m.value === v) return true;
             if (m.type === 'range' && m.value - 10 <= v && v <= m.value) return true;
           }
           return false;
         },
-        isStrictlySmallerValue: (a: number, b: number) => {
+        isStrictlySmallerValue: (a: number, b: number, metas: SeedGeneratorType) => {
+          // When withCrossShrink is toggled, the shrinker can jump from one arbitrary to the first one on shrink
+          // But only if the weight associated to the first arbitrary is strictly greater than 0
+          if (metas.constraints !== undefined && metas.constraints.withCrossShrink && metas.data[0].weight > 0) {
+            const canBeInFirstArbitrary =
+              metas.data[0].type === 'unique'
+                ? metas.data[0].value === a
+                : metas.data[0].value - 10 <= a && a <= metas.data[0].value;
+            if (canBeInFirstArbitrary) {
+              // `a` is possibly coming from our first arbitrary
+              return true;
+            }
+          }
+          // Otherwise, shrinks are always coming from the arbitrary itself
           return Math.abs(b - a) <= 10 && b > 0 ? b - a > 0 : b - a < 0;
         },
       }