Repository: dubzzz/fast-check
Pull request #1601 (2021-03-11 21:51:40)

✨ Add `maxDepth` 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

None

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/1601/builds/108979) or the icon next to each commit SHA.

Latest deployment of this branch, based on commit 667ac725bf848bba1cf40da2998b79f974cb38a7:

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

dubzzz: @github-actions deploy
codecov[bot]: # [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1601?src=pr&el=h1) Report
> Merging [#1601](https://codecov.io/gh/dubzzz/fast-check/pull/1601?src=pr&el=desc) (667ac72) into [main](https://codecov.io/gh/dubzzz/fast-check/commit/29b51e8740a617784f76c4155415f4714b62d704?el=desc) (29b51e8) will **decrease** coverage by `0.02%`.
> The diff coverage is `100.00%`.

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

```diff
@@            Coverage Diff             @@
##             main    #1601      +/-   ##
==========================================
- Coverage   97.46%   97.44%   -0.03%     
==========================================
  Files          93       93              
  Lines        3195     3204       +9     
  Branches      619      620       +1     
==========================================
+ Hits         3114     3122       +8     
- Misses         77       78       +1     
  Partials        4        4              
```

| Flag | Coverage Δ | |
|---|---|---|
| unit-tests | `97.44% <100.00%> (-0.03%)` | :arrow_down: |
| unit-tests-10.x-Linux | `97.44% <100.00%> (-0.03%)` | :arrow_down: |
| unit-tests-12.x-Linux | `?` | |
| unit-tests-14.x-Linux | `?` | |

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/1601?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/check/arbitrary/FrequencyArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1601/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9GcmVxdWVuY3lBcmJpdHJhcnkudHM=) | `98.33% <100.00%> (+0.29%)` | :arrow_up: |
| [src/check/arbitrary/ArrayArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1601/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9BcnJheUFyYml0cmFyeS50cw==) | `93.54% <0.00%> (-1.08%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1601?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/1601?src=pr&el=footer). Last update [29b51e8...667ac72](https://codecov.io/gh/dubzzz/fast-check/pull/1601?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

github-actions[bot]: Give a try to https://github.com/dubzzz/fast-check/pull/1601/commits/667ac725bf848bba1cf40da2998b79f974cb38a7 with:

```bash
yarn add https://604a91a13520194cd6227ea1--dazzling-goodall-4f0e38.netlify.app/fast-check.tgz
npm i https://604a91a13520194cd6227ea1--dazzling-goodall-4f0e38.netlify.app/fast-check.tgz
```

Or have a look to the [generated documentation](https://604a91a13520194cd6227ea1--dazzling-goodall-4f0e38.netlify.app).

Patch:
diff --git a/documentation/Arbitraries.md b/documentation/Arbitraries.md
index c9e07dde..96b117de 100644
--- a/documentation/Arbitraries.md
+++ b/documentation/Arbitraries.md
@@ -2153,12 +2153,13 @@ fc.oneof(fc.char(), fc.boolean(), fc.nat())
 *&#8195;Signatures*
 
 - `fc.frequency(...{ arbitrary, weight })`
-- `fc.frequency({withCrossShrink?}, ...{ arbitrary, weight })`
+- `fc.frequency({withCrossShrink?, maxDepth?}, ...{ 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_
+- `maxDepth?` — default: `Number.POSITIVE_INFINITY` — _when reaching maxDepth, the first arbitrary will be used to generate the value even if its weight is zero_
 
 *&#8195;Usages*
 
@@ -2178,6 +2179,47 @@ fc.frequency(
 // 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]…
+
+// fc.frequency fits very well with recursive stuctures built using fc.letrec
+// here are some examples:
+
+fc.letrec(tie => ({
+  list: fc.record({
+    head: fc.nat(),
+    queue: fc.frequency(
+      { maxDepth: 2 },
+      { arbitrary: fc.constant([]), weight: 1 },
+      { arbitrary: tie('list'), weight: 2 }
+    )
+  })
+})).list
+// Note: Create a linked-list having a max-length of 3.
+// Examples of generated values:
+// • {"head":22,"queue":{"head":19,"queue":[]}}
+// • {"head":1525860351,"queue":{"head":27,"queue":{"head":2147483642,"queue":[]}}}
+// • {"head":150027580,"queue":{"head":4,"queue":{"head":1111036126,"queue":[]}}}
+// • {"head":1777171327,"queue":[]}
+// • {"head":6,"queue":{"head":2029127408,"queue":{"head":1041976777,"queue":[]}}}
+// • …
+
+fc.letrec(tie => ({
+  list: fc.record({
+    head: fc.nat(),
+    queue: fc.frequency(
+      { maxDepth: 2 },
+      { arbitrary: fc.constant([]), weight: 0 },
+      { arbitrary: tie('list'), weight: 1 }
+    )
+  })
+})).list
+// Note: Create a linked-list having a length of 3 (not more, not less).
+// Examples of generated values:
+// • {"head":22,"queue":{"head":19,"queue":{"head":2147483640,"queue":[]}}}
+// • {"head":1525860351,"queue":{"head":27,"queue":{"head":2147483642,"queue":[]}}}
+// • {"head":150027580,"queue":{"head":4,"queue":{"head":1111036126,"queue":[]}}}
+// • {"head":1777171327,"queue":{"head":1226266757,"queue":{"head":2147483632,"queue":[]}}}
+// • {"head":6,"queue":{"head":2029127408,"queue":{"head":1041976777,"queue":[]}}}
+// • …
 ```
 </details>
 
diff --git a/src/check/arbitrary/FrequencyArbitrary.ts b/src/check/arbitrary/FrequencyArbitrary.ts
index e8d280fe..b7d4a647 100644
--- a/src/check/arbitrary/FrequencyArbitrary.ts
+++ b/src/check/arbitrary/FrequencyArbitrary.ts
@@ -3,6 +3,12 @@ import { Stream } from '../../stream/Stream';
 import { Arbitrary } from './definition/Arbitrary';
 import { Shrinkable } from './definition/Shrinkable';
 
+/** @internal */
+type DepthContext = {
+  /** Current depth (starts at 0) */
+  depth: number;
+};
+
 /**
  * Conjonction of a weight and an arbitrary used by {@link frequency}
  * in order to generate values
@@ -43,9 +49,13 @@ 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, constraints);
+    return new FrequencyArbitrary(warbs, constraints, { depth: 0 });
   }
-  private constructor(readonly warbs: WeightedArbitrary<T>[], readonly constraints: FrequencyContraints) {
+  private constructor(
+    readonly warbs: WeightedArbitrary<T>[],
+    readonly constraints: FrequencyContraints,
+    readonly context: DepthContext
+  ) {
     super();
     let currentWeight = 0;
     this.summedWarbs = [];
@@ -56,14 +66,14 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
     this.totalWeight = currentWeight;
   }
   generate(mrng: Random): Shrinkable<T> {
+    if (this.constraints.maxDepth !== undefined && this.constraints.maxDepth <= this.context.depth) {
+      // index=0 can be selected even if it has a weight equal to zero
+      return this.safeGenerateForIndex(mrng, 0);
+    }
     const selected = mrng.nextInt(0, this.totalWeight - 1);
     for (let idx = 0; idx !== this.summedWarbs.length; ++idx) {
       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);
+        return this.safeGenerateForIndex(mrng, idx);
       }
     }
     throw new Error(`Unable to generate from fc.frequency`);
@@ -71,10 +81,25 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
   withBias(freq: number) {
     return new FrequencyArbitrary(
       this.warbs.map((v) => ({ weight: v.weight, arbitrary: v.arbitrary.withBias(freq) })),
-      this.constraints
+      this.constraints,
+      this.context
     );
   }
 
+  /** Generate using Arbitrary at index idx and safely handle depth context */
+  private safeGenerateForIndex(mrng: Random, idx: number): Shrinkable<T> {
+    ++this.context.depth; // increase depth
+    try {
+      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);
+    } finally {
+      --this.context.depth; // decrease depth (reset depth)
+    }
+  }
+
   /**
    * 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
@@ -124,6 +149,15 @@ export type FrequencyContraints = {
    * @remarks Since 2.14.0
    */
   withCrossShrink?: boolean;
+  /**
+   * Maximal authorized depth.
+   * Once this depth has been reached only the first arbitrary will be used.
+   *
+   * Warning: First arbitrary will be used even if its weight is set to zero.
+   *
+   * @remarks Since 2.14.0
+   */
+  maxDepth?: number;
 };
 
 /**


Test patch:
diff --git a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
index e51f2515..677baac3 100644
--- a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
+++ b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
@@ -26,7 +26,7 @@ describe('FrequencyArbitrary', () => {
             const totalWeight = config.reduce((acc, e) => acc + e.weight, 0);
             return totalWeight > 0;
           }),
-        constraints: fc.record({ withCrossShrink: fc.boolean() }, { requiredKeys: [] }),
+        constraints: fc.record({ withCrossShrink: fc.boolean(), maxDepth: fc.nat() }, { requiredKeys: [] }),
       },
       { requiredKeys: ['data'] }
     );
@@ -47,7 +47,10 @@ describe('FrequencyArbitrary', () => {
       {
         seedGenerator,
         isValidValue: (v: number, metas: SeedGeneratorType) => {
-          for (const m of metas.data) {
+          // If maxDepth is 0, then only the first arbitrary can be called
+          const data =
+            metas.constraints !== undefined && metas.constraints.maxDepth === 0 ? [metas.data[0]] : metas.data;
+          for (const m of 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;
diff --git a/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts b/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
index a3d0ad38..13570e1d 100644
--- a/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
+++ b/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
@@ -1,5 +1,7 @@
 import * as fc from '../../../../lib/fast-check';
 
+import { Arbitrary } from '../../../../src/check/arbitrary/definition/Arbitrary';
+import { Shrinkable } from '../../../../src/check/arbitrary/definition/Shrinkable';
 import { frequency } from '../../../../src/check/arbitrary/FrequencyArbitrary';
 import { Random } from '../../../../src/random/generator/Random';
 
@@ -67,6 +69,81 @@ describe('FrequencyArbitrary', () => {
           }
         )
       ));
+    it('Should call the first arbitrary to generate the value when maxDepth of 0', () =>
+      fc.assert(
+        fc.property(frequencyValidInputsArb, (validInputs) => {
+          // Arrange
+          const arb = frequency({ maxDepth: 0 }, ...validInputs);
+          const nextInt: jest.Mock<number, [] | [number] | [number, number]> = jest.fn();
+          const fakeRandom = { nextInt: nextInt as Random['nextInt'] } as Random;
+
+          // Act
+          const g = arb.generate(fakeRandom).value_;
+
+          // Assert
+          expect(nextInt).not.toHaveBeenCalled();
+          expect(g).toBe(validInputs[0].expectedValue);
+        })
+      ));
+    it('Should call the first arbitrary to generate the value as soon as maxDepth has been reached', () => {
+      // Arrange
+      class LazyArb extends Arbitrary<any> {
+        constructor(readonly arbBuilder: () => Arbitrary<any>) {
+          super();
+        }
+        generate(mrng: Random): Shrinkable<any, any> {
+          return this.arbBuilder().generate(mrng);
+        }
+        withBias(freq: number) {
+          return this.arbBuilder().withBias(freq);
+        }
+      }
+      const arb: Arbitrary<any> = frequency(
+        { maxDepth: 5 },
+        { weight: 0, arbitrary: stubArb.single(0) },
+        { weight: 1, arbitrary: new LazyArb(() => arb).map((d) => [d]) }
+      );
+      const nextInt: jest.Mock<number, [] | [number] | [number, number]> = jest.fn().mockReturnValue(0);
+      const fakeRandom = { nextInt: nextInt as Random['nextInt'] } as Random;
+
+      // Act
+      const g = arb.generate(fakeRandom).value_;
+
+      // Assert
+      expect(nextInt).toHaveBeenCalledTimes(5); // maxDepth
+      expect(g).toEqual([[[[[0]]]]]); // const mapper = (d) => [d]; mapper(mapper(mapper(mapper(mapper(0))))) is [[[[[0]]]]]
+    });
+    it('Should not share depth accross distinct instances of frequency (if not requested)', () => {
+      // Arrange
+      const arb: Arbitrary<any> = frequency(
+        { maxDepth: 1 },
+        { weight: 0, arbitrary: stubArb.single(0) },
+        {
+          weight: 1,
+          arbitrary: frequency(
+            { maxDepth: 1 },
+            { weight: 0, arbitrary: stubArb.single(0) },
+            {
+              weight: 1,
+              arbitrary: frequency(
+                { maxDepth: 1 },
+                { weight: 0, arbitrary: stubArb.single(0) },
+                { weight: 1, arbitrary: stubArb.single(1) }
+              ).map((d) => [d]),
+            }
+          ).map((d) => [d]),
+        }
+      );
+      const nextInt: jest.Mock<number, [] | [number] | [number, number]> = jest.fn().mockReturnValue(0);
+      const fakeRandom = { nextInt: nextInt as Random['nextInt'] } as Random;
+
+      // Act
+      const g = arb.generate(fakeRandom).value_;
+
+      // Assert
+      expect(nextInt).toHaveBeenCalledTimes(3); // once per instance of frequency
+      expect(g).toEqual([[1]]);
+    });
 
     it('Should reject calls without any weighted arbitraries', () => {
       expect(() => frequency()).toThrowError();