Repository: dubzzz/fast-check
Pull request #1603 (2021-03-11 22:34:09)

✨ Add `depthFactor` 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/1603/builds/108990) or the icon next to each commit SHA.

Latest deployment of this branch, based on commit df11fcb4cfc204cb46783b28a90e7dedfd42c23b:

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

codecov[bot]: # [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1603?src=pr&el=h1) Report
> Merging [#1603](https://codecov.io/gh/dubzzz/fast-check/pull/1603?src=pr&el=desc) (13f42d0) into [main](https://codecov.io/gh/dubzzz/fast-check/commit/132c0930f06f4f55e87d4086de5ab3013e54c1fe?el=desc) (132c093) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

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

```diff
@@           Coverage Diff           @@
##             main    #1603   +/-   ##
=======================================
  Coverage   97.47%   97.48%           
=======================================
  Files          93       93           
  Lines        3204     3215   +11     
  Branches      620      624    +4     
=======================================
+ Hits         3123     3134   +11     
  Misses         77       77           
  Partials        4        4           
```

| Flag | Coverage Δ | |
|---|---|---|
| unit-tests | `97.48% <100.00%> (+<0.01%)` | :arrow_up: |
| unit-tests-10.x-Linux | `?` | |
| unit-tests-12.x-Linux | `97.48% <100.00%> (+0.03%)` | :arrow_up: |
| 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/1603?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/check/arbitrary/FrequencyArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1603/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9GcmVxdWVuY3lBcmJpdHJhcnkudHM=) | `98.59% <100.00%> (+0.25%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1603?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/1603?src=pr&el=footer). Last update [132c093...13f42d0](https://codecov.io/gh/dubzzz/fast-check/pull/1603?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 96b117de..02718e13 100644
--- a/documentation/Arbitraries.md
+++ b/documentation/Arbitraries.md
@@ -2159,6 +2159,7 @@ fc.oneof(fc.char(), fc.boolean(), fc.nat())
 
 - `...{ 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_
+- `depthFactor?` — default: `0` — _this factor will be used to increase the probability to generate instances of the first passed arbitrary if its weight is not zero_
 - `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*
diff --git a/src/check/arbitrary/FrequencyArbitrary.ts b/src/check/arbitrary/FrequencyArbitrary.ts
index a2214772..54d61908 100644
--- a/src/check/arbitrary/FrequencyArbitrary.ts
+++ b/src/check/arbitrary/FrequencyArbitrary.ts
@@ -77,7 +77,7 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
       // 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);
+    const selected = mrng.nextInt(this.computeNegDepthBenefit(), this.totalWeight - 1);
     for (let idx = 0; idx !== this.summedWarbs.length; ++idx) {
       if (selected < this.summedWarbs[idx].weight) {
         return this.safeGenerateForIndex(mrng, idx);
@@ -107,6 +107,19 @@ class FrequencyArbitrary<T> extends Arbitrary<T> {
     }
   }
 
+  /** Compute the benefit for the current depth */
+  private computeNegDepthBenefit(): number {
+    const depthFactor = this.constraints.depthFactor;
+    if (depthFactor === undefined || depthFactor <= 0) {
+      return 0;
+    }
+    // We use a pow-based biased benefit as the deeper we go the more chance we have
+    // to encounter thousands of instances of the current arbitrary.
+    const depthBenefit = Math.floor(Math.pow(1 + depthFactor, this.context.depth)) - 1;
+    // -0 has to be converted into 0 thus we call ||0
+    return -Math.min(this.warbs[0].weight * depthBenefit, Number.MAX_SAFE_INTEGER) || 0;
+  }
+
   /**
    * 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
@@ -156,11 +169,23 @@ export type FrequencyContraints = {
    * @remarks Since 2.14.0
    */
   withCrossShrink?: boolean;
+  /**
+   * While going deeper and deeper within a recursive structure,
+   * this factor will be used to increase the probability to generate instances
+   * of the first passed arbitrary.
+   *
+   * Example of values: 0.1 (small impact as depth increases), 0.5, 1 (huge impact as depth increases).
+   *
+   * Warning: First arbitrary will not be used if its weight is set to zero.
+   *
+   * @remarks Since 2.14.0
+   */
+  depthFactor?: number;
   /**
    * 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.
+   * Warning: Contrary to others, first arbitrary will be used even if its weight is set to zero.
    *
    * @remarks Since 2.14.0
    */


Test patch:
diff --git a/test/e2e/RecursiveStructures.spec.ts b/test/e2e/RecursiveStructures.spec.ts
index 3b72d1c0..6760fe19 100644
--- a/test/e2e/RecursiveStructures.spec.ts
+++ b/test/e2e/RecursiveStructures.spec.ts
@@ -10,10 +10,9 @@ describe(`RecursiveStructures (seed: ${seed})`, () => {
     // 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 },
+        { withCrossShrink: true, depthFactor: 0.5 },
+        { arbitrary: fc.constant([0]), weight: 1 },
         { arbitrary: fc.tuple(tie('data'), tie('data')), weight: 1 }
       ),
     })).data;
diff --git a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
index 677baac3..7898d598 100644
--- a/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
+++ b/test/unit/check/arbitrary/FrequencyArbitrary.itest.spec.ts
@@ -26,7 +26,14 @@ describe('FrequencyArbitrary', () => {
             const totalWeight = config.reduce((acc, e) => acc + e.weight, 0);
             return totalWeight > 0;
           }),
-        constraints: fc.record({ withCrossShrink: fc.boolean(), maxDepth: fc.nat() }, { requiredKeys: [] }),
+        constraints: fc.record(
+          {
+            withCrossShrink: fc.boolean(),
+            depthFactor: fc.double({ min: 0, max: Number.MAX_VALUE, noNaN: true }),
+            maxDepth: fc.nat(),
+          },
+          { requiredKeys: [] }
+        ),
       },
       { requiredKeys: ['data'] }
     );
diff --git a/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts b/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
index a1f06dc9..95a60e84 100644
--- a/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
+++ b/test/unit/check/arbitrary/FrequencyArbitrary.utest.spec.ts
@@ -21,6 +21,18 @@ const frequencyValidInputsArb = fc
     }));
   });
 
+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);
+  }
+}
+
 describe('FrequencyArbitrary', () => {
   describe('frequency', () => {
     it('Should call Random generator to generate values between 0 and total weight (not included)', () =>
@@ -87,17 +99,6 @@ describe('FrequencyArbitrary', () => {
       ));
     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) },
@@ -144,6 +145,55 @@ describe('FrequencyArbitrary', () => {
       expect(nextInt).toHaveBeenCalledTimes(3); // once per instance of frequency
       expect(g).toEqual([[1]]);
     });
+    it('Should ask ranges containing negative values as we go deeper in the structure if depthFactor', () => {
+      // Arrange
+      const arb: Arbitrary<any> = frequency(
+        { depthFactor: 0.1 },
+        { weight: 1, arbitrary: stubArb.single(0) },
+        { weight: 1000, arbitrary: new LazyArb(() => arb).map((d) => [d]) }
+      );
+      const nextInt: jest.Mock<number, [] | [number] | [number, number]> = jest.fn().mockImplementation((a, b) => {
+        // we stop on the first negative value of a
+        if (a < 0) return a;
+        // otherwise we return b to go deeper in the tree
+        else return b;
+      });
+      const fakeRandom = { nextInt: nextInt as Random['nextInt'] } as Random;
+
+      // Act
+      arb.generate(fakeRandom).value_;
+
+      // Assert
+      expect(nextInt).toHaveBeenCalledWith(0, 1000); // first calls: 0-1000 contains 1001 values
+      expect(nextInt).toHaveBeenCalledWith(-1, 1000); // as we go deeper (too deep)
+    });
+    it('Should never ask ranges containing negative values as we go deeper in the structure if depthFactor with weight of 0 on first arbitrary', () => {
+      // Arrange
+      const arb: Arbitrary<any> = frequency(
+        { depthFactor: 0.1 },
+        { weight: 0, arbitrary: stubArb.single(0) },
+        { weight: 1000, arbitrary: new LazyArb(() => arb).map((d) => [d]) }
+      );
+      const nextInt: jest.Mock<number, [] | [number] | [number, number]> = jest.fn().mockImplementation((a, b) => {
+        // we stop on the first negative value of a
+        if (a < 0) return a;
+        // otherwise we return b to go deeper in the tree
+        else return b;
+      });
+      const fakeRandom = { nextInt: nextInt as Random['nextInt'] } as Random;
+
+      // Act
+      try {
+        arb.generate(fakeRandom).value_;
+        fail('Stack overflow expected as the structure is going deeper and deeper without any end case');
+      } catch (err) {
+        // noop
+      }
+
+      // Assert
+      expect(nextInt).toHaveBeenCalledWith(0, 999); // first calls: 0-999 contains 1000 values
+      expect(nextInt).not.toHaveBeenCalledWith(-1, 999); // never called as first arbitrary has a weight of zero
+    });
 
     it('Should reject calls without any weighted arbitraries', () => {
       expect(() => frequency()).toThrowError();