Repository: dubzzz/fast-check
Pull request #1706 (2021-04-07 22:39:54)

♻️ Migrate array/set to NextArbitrary
<!-- 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: *refactor*

(✔️: yes, ❌: no)

## Potential impacts

None expected. But if any, we may have some on array/set and any derived arbitrary (string) regarding:
- Generated values impact,
- Shrink values impact

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

Latest deployment of this branch, based on commit 7edc0a2e759783cb49a9009c3fcb5758312efee6:

|Sandbox| Source |
|--|--|
|[Vanilla](https://codesandbox.io/s/vanilla-1iopv)| Configuration |
|[fast-check-examples](https://codesandbox.io/s/fast-check-examples-5fh3v)| Configuration |

codecov[bot]: # [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1706?src=pr&el=h1) Report
> Merging [#1706](https://codecov.io/gh/dubzzz/fast-check/pull/1706?src=pr&el=desc) (7edc0a2) into [main](https://codecov.io/gh/dubzzz/fast-check/commit/19a64ae2dddef272071e01613e2332f9bd83611d?el=desc) (19a64ae) will **decrease** coverage by `0.29%`.
> The diff coverage is `84.50%`.

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

```diff
@@            Coverage Diff             @@
##             main    #1706      +/-   ##
==========================================
- Coverage   97.25%   96.95%   -0.30%     
==========================================
  Files          98       98              
  Lines        3496     3519      +23     
  Branches      693      697       +4     
==========================================
+ Hits         3400     3412      +12     
- Misses         92      103      +11     
  Partials        4        4              
```

| Flag | Coverage Δ | |
|---|---|---|
| unit-tests | `96.95% <84.50%> (-0.30%)` | :arrow_down: |
| unit-tests-10.x-Linux | `?` | |
| unit-tests-12.x-Linux | `96.95% <84.50%> (-0.27%)` | :arrow_down: |
| 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/1706?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/check/arbitrary/ArrayArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1706/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9BcnJheUFyYml0cmFyeS50cw==) | `85.96% <83.33%> (-8.66%)` | :arrow_down: |
| [src/check/arbitrary/SetArbitrary.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1706/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9TZXRBcmJpdHJhcnkudHM=) | `100.00% <100.00%> (ø)` | |
| [src/check/arbitrary/helpers/BuildCompareFilter.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1706/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9oZWxwZXJzL0J1aWxkQ29tcGFyZUZpbHRlci50cw==) | `100.00% <100.00%> (ø)` | |

------

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


Patch:
diff --git a/src/check/arbitrary/ArrayArbitrary.ts b/src/check/arbitrary/ArrayArbitrary.ts
index 330ca8cd..bbfc966e 100644
--- a/src/check/arbitrary/ArrayArbitrary.ts
+++ b/src/check/arbitrary/ArrayArbitrary.ts
@@ -1,21 +1,28 @@
 import { Random } from '../../random/generator/Random';
 import { Stream } from '../../stream/Stream';
-import { cloneMethod } from '../symbols';
+import { cloneIfNeeded, cloneMethod } from '../symbols';
 import { Arbitrary } from './definition/Arbitrary';
-import { ArbitraryWithContextualShrink } from './definition/ArbitraryWithContextualShrink';
-import { biasWrapper } from './definition/BiasedArbitraryWrapper';
-import { Shrinkable } from './definition/Shrinkable';
 import { integer } from './IntegerArbitrary';
 import { makeLazy } from '../../stream/LazyIterableIterator';
 import { buildCompareFilter } from './helpers/BuildCompareFilter';
+import { NextArbitrary } from './definition/NextArbitrary';
+import { convertFromNext, convertToNext } from './definition/Converters';
+import { NextValue } from './definition/NextValue';
 
 /** @internal */
-export class ArrayArbitrary<T> extends Arbitrary<T[]> {
-  readonly lengthArb: ArbitraryWithContextualShrink<number>;
-  readonly preFilter: (tab: Shrinkable<T>[]) => Shrinkable<T>[];
+type ArrayArbitraryContext = {
+  shrunkOnce: boolean;
+  lengthContext: unknown;
+  itemsContexts: unknown[];
+};
+
+/** @internal */
+export class ArrayArbitrary<T> extends NextArbitrary<T[]> {
+  readonly lengthArb: NextArbitrary<number>;
+  readonly preFilter: (tab: NextValue<T>[]) => NextValue<T>[];
 
   constructor(
-    readonly arb: Arbitrary<T>,
+    readonly arb: NextArbitrary<T>,
     readonly minLength: number,
     readonly maxLength: number,
     // Whenever passing a isEqual to ArrayArbitrary, you also have to filter
@@ -23,10 +30,11 @@ export class ArrayArbitrary<T> extends Arbitrary<T[]> {
     readonly isEqual?: (valueA: T, valueB: T) => boolean
   ) {
     super();
-    this.lengthArb = integer(minLength, maxLength);
-    this.preFilter = this.isEqual !== undefined ? buildCompareFilter(this.isEqual) : (tab: Shrinkable<T>[]) => tab;
+    this.lengthArb = convertToNext(integer(minLength, maxLength));
+    this.preFilter = this.isEqual !== undefined ? buildCompareFilter(this.isEqual) : (tab: NextValue<T>[]) => tab;
   }
-  private static makeItCloneable<T>(vs: T[], shrinkables: Shrinkable<T>[]) {
+
+  private static makeItCloneable<T>(vs: T[], shrinkables: NextValue<T>[]) {
     (vs as any)[cloneMethod] = () => {
       const cloned = [];
       for (let idx = 0; idx !== shrinkables.length; ++idx) {
@@ -37,7 +45,8 @@ export class ArrayArbitrary<T> extends Arbitrary<T[]> {
     };
     return vs;
   }
-  private canAppendItem(items: Shrinkable<T>[], newItem: Shrinkable<T>): boolean {
+
+  private canAppendItem(items: NextValue<T>[], newItem: NextValue<T>): boolean {
     if (this.isEqual === undefined) {
       return true;
     }
@@ -48,7 +57,8 @@ export class ArrayArbitrary<T> extends Arbitrary<T[]> {
     }
     return true;
   }
-  private wrapper(itemsRaw: Shrinkable<T>[], shrunkOnce: boolean, itemsRawLengthContext: unknown): Shrinkable<T[]> {
+
+  private wrapper(itemsRaw: NextValue<T>[], shrunkOnce: boolean, itemsRawLengthContext: unknown): NextValue<T[]> {
     // We need to explicitly apply filtering on shrink items
     // has they might have duplicates (on non shrunk it is not the case by construct)
     const items = shrunkOnce ? this.preFilter(itemsRaw) : itemsRaw;
@@ -62,31 +72,30 @@ export class ArrayArbitrary<T> extends Arbitrary<T[]> {
     if (cloneable) {
       ArrayArbitrary.makeItCloneable(vs, items);
     }
-    const itemsLengthContext =
-      itemsRaw.length === items.length && itemsRawLengthContext !== undefined
-        ? itemsRawLengthContext // items and itemsRaw have the same length context is applicable
-        : shrunkOnce // otherwise we fallback to default contexts
-        ? this.lengthArb.shrunkOnceContext() // in case we shrunk once we use a dedicated context that should reduce shrink size
-        : undefined;
-    return new Shrinkable(vs, () =>
-      this.shrinkImpl(items, itemsLengthContext).map((contextualValue) =>
-        this.wrapper(contextualValue[0], true, contextualValue[1])
-      )
-    );
+    const context: ArrayArbitraryContext = {
+      shrunkOnce,
+      lengthContext:
+        itemsRaw.length === items.length && itemsRawLengthContext !== undefined
+          ? itemsRawLengthContext // items and itemsRaw have the same length context is applicable
+          : undefined,
+      itemsContexts: items.map((v) => v.context),
+    };
+    return new NextValue(vs, context);
   }
-  generate(mrng: Random): Shrinkable<T[]> {
-    const targetSizeShrinkable = this.lengthArb.generate(mrng);
-    const targetSize = targetSizeShrinkable.value;
+
+  generate(mrng: Random, biasFactor: number | undefined): NextValue<T[]> {
+    const biasMeta = this.applyBias(mrng, biasFactor);
+    const targetSize = biasMeta.size;
 
     let numSkippedInRow = 0;
-    const items: Shrinkable<T>[] = [];
+    const items: NextValue<T>[] = [];
     // Try to append into items up to the target size
     // In the case of a set we may reject some items as they are already part of the set
     // so we need to retry and generate other ones. In order to prevent infinite loop,
     // we accept a max of maxLength consecutive failures. This circuit breaker may cause
     // generated to be smaller than the minimal accepted one.
     while (items.length < targetSize && numSkippedInRow < this.maxLength) {
-      const current = this.arb.generate(mrng);
+      const current = this.arb.generate(mrng, biasMeta.biasFactorItems);
       if (this.canAppendItem(items, current)) {
         numSkippedInRow = 0;
         items.push(current);
@@ -96,67 +105,115 @@ export class ArrayArbitrary<T> extends Arbitrary<T[]> {
     }
     return this.wrapper(items, false, undefined);
   }
-  private shrinkImpl(items: Shrinkable<T>[], itemsLengthContext: unknown): Stream<[Shrinkable<T>[], unknown]> {
-    if (items.length === 0) {
-      return Stream.nil<[Shrinkable<T>[], unknown]>();
+
+  private applyBias(mrng: Random, biasFactor: number | undefined): { size: number; biasFactorItems?: number } {
+    if (biasFactor === undefined || mrng.nextInt(1, biasFactor) !== 1) {
+      // We don't bias anything
+      return { size: this.lengthArb.generate(mrng, undefined).value };
+    }
+    // We apply bias (1 chance over biasFactor)
+    if (mrng.nextInt(1, biasFactor) !== 1 || this.minLength === this.maxLength) {
+      // We only apply bias on items ((biasFactor-1) chances over biasFactor²)
+      return { size: this.lengthArb.generate(mrng, undefined).value, biasFactorItems: biasFactor };
+    }
+    // We apply bias for both items and length (1 chance over biasFactor²)
+    const maxBiasedLength = this.minLength + Math.floor(Math.log(this.maxLength - this.minLength) / Math.log(2));
+    const targetSizeValue = convertToNext(integer(this.minLength, maxBiasedLength)).generate(mrng, undefined);
+    return { size: targetSizeValue.value, biasFactorItems: biasFactor };
+  }
+
+  canGenerate(value: unknown): value is T[] {
+    if (!Array.isArray(value) || this.minLength > value.length || value.length > this.maxLength) {
+      return false;
+    }
+    for (let index = 0; index !== value.length; ++index) {
+      if (!(index in value)) {
+        // sparse array cannot be produced by this instance
+        return false;
+      }
+      if (!this.arb.canGenerate(value[index])) {
+        // item at index cannot be produced by our arbitrary
+        return false;
+      }
+    }
+    // `preFilter` only drops items, it does not reorder them or add some more
+    // if calling it with `value` results into a smaller array it means that the value was not generated by this instance
+    const filtered = this.preFilter(value.map((item) => new NextValue(item)));
+    return filtered.length === value.length;
+  }
+
+  private shrinkImpl(value: T[], context?: unknown): Stream<[NextValue<T>[], unknown]> {
+    if (value.length === 0) {
+      return Stream.nil();
     }
+
+    const safeContext: ArrayArbitraryContext =
+      context !== undefined
+        ? (context as ArrayArbitraryContext)
+        : { shrunkOnce: false, lengthContext: undefined, itemsContexts: [] };
+
     return (
       this.lengthArb
-        .contextualShrink(
-          items.length,
-          // itemsLengthContext is a context returned by a previous call to the integer
+        .shrink(
+          value.length,
+          // lengthContext is a context returned by a previous call to the integer
           // arbitrary and the integer value items.length.
-          itemsLengthContext
+          safeContext.lengthContext
         )
-        .map((contextualValue): [Shrinkable<T>[], unknown] => {
+        // in case we already shrunk once but don't have any dedicated context to help the shrinker, we drop the first item
+        // except if reached we have the minimal size +1, in that case we apply a last chance try policy
+        .drop(
+          safeContext.shrunkOnce && safeContext.lengthContext === undefined && value.length > this.minLength + 1 ? 1 : 0
+        )
+        .map((lengthValue): [NextValue<T>[], unknown] => {
+          const sliceStart = value.length - lengthValue.value;
           return [
-            items.slice(items.length - contextualValue[0]), // array of length contextualValue[0]
-            contextualValue[1], // integer context for value contextualValue[0] (the length)
+            value
+              .slice(sliceStart)
+              .map((v, index) => new NextValue(cloneIfNeeded(v), safeContext.itemsContexts[index + sliceStart])), // array of length lengthValue.value
+            lengthValue.context, // integer context for value lengthValue.value (the length)
           ];
         })
         // Context value will be set to undefined for remaining shrinking values
         // as they are outside of our shrinking process focused on items.length.
         // None of our computed contexts will apply for them.
-        .join(items[0].shrink().map((v) => [[v].concat(items.slice(1)), undefined]))
         .join(
-          items.length > this.minLength
+          this.arb.shrink(value[0], safeContext.itemsContexts[0]).map((v) => {
+            return [
+              [v].concat(
+                value.slice(1).map((v, index) => new NextValue(cloneIfNeeded(v), safeContext.itemsContexts[index + 1]))
+              ),
+              undefined, // no length context
+            ];
+          })
+        )
+        .join(
+          value.length > this.minLength
             ? makeLazy(() =>
                 // We pass itemsLengthContext=undefined to next shrinker to start shrinking
                 // without any assumptions on the current state (we never explored that one)
-                this.shrinkImpl(items.slice(1), undefined)
-                  .filter((contextualValue) => this.minLength <= contextualValue[0].length + 1)
-                  .map((contextualValue) => [[items[0]].concat(contextualValue[0]), undefined])
+                this.shrinkImpl(value.slice(1), {
+                  shrunkOnce: false,
+                  lengthContext: undefined,
+                  itemsContexts: safeContext.itemsContexts.slice(1),
+                })
+                  .filter((v) => this.minLength <= v[0].length + 1)
+                  .map((v): [NextValue<T>[], unknown] => {
+                    return [
+                      [new NextValue(cloneIfNeeded(value[0]), safeContext.itemsContexts[0])].concat(v[0]),
+                      undefined,
+                    ];
+                  })
               )
-            : Stream.nil<[Shrinkable<T>[], unknown]>()
+            : Stream.nil<[NextValue<T>[], unknown]>()
         )
     );
   }
-  withBias(freq: number): Arbitrary<T[]> {
-    return biasWrapper(freq, this, (originalArbitrary: ArrayArbitrary<T>) => {
-      const lowBiased = new ArrayArbitrary(
-        originalArbitrary.arb.withBias(freq),
-        originalArbitrary.minLength,
-        originalArbitrary.maxLength,
-        originalArbitrary.isEqual
-      );
-      const highBiasedArbBuilder = () => {
-        return originalArbitrary.minLength !== originalArbitrary.maxLength
-          ? new ArrayArbitrary(
-              originalArbitrary.arb.withBias(freq),
-              originalArbitrary.minLength,
-              originalArbitrary.minLength +
-                Math.floor(Math.log(originalArbitrary.maxLength - originalArbitrary.minLength) / Math.log(2)),
-              originalArbitrary.isEqual
-            )
-          : new ArrayArbitrary(
-              originalArbitrary.arb.withBias(freq),
-              originalArbitrary.minLength,
-              originalArbitrary.maxLength,
-              originalArbitrary.isEqual
-            );
-      };
-      return biasWrapper(freq, lowBiased, highBiasedArbBuilder);
-    });
+
+  shrink(value: T[], context?: unknown): Stream<NextValue<T[]>> {
+    return this.shrinkImpl(value, context).map((contextualValue) =>
+      this.wrapper(contextualValue[0], true, contextualValue[1])
+    );
   }
 }
 
@@ -233,19 +290,20 @@ function array<T>(arb: Arbitrary<T>, minLength: number, maxLength: number): Arbi
  */
 function array<T>(arb: Arbitrary<T>, constraints: ArrayConstraints): Arbitrary<T[]>;
 function array<T>(arb: Arbitrary<T>, ...args: [] | [number] | [number, number] | [ArrayConstraints]): Arbitrary<T[]> {
+  const nextArb = convertToNext(arb);
   // fc.array(arb)
-  if (args[0] === undefined) return new ArrayArbitrary<T>(arb, 0, maxLengthFromMinLength(0));
+  if (args[0] === undefined) return convertFromNext(new ArrayArbitrary<T>(nextArb, 0, maxLengthFromMinLength(0)));
   // fc.array(arb, constraints)
   if (typeof args[0] === 'object') {
     const minLength = args[0].minLength || 0;
     const specifiedMaxLength = args[0].maxLength;
     const maxLength = specifiedMaxLength !== undefined ? specifiedMaxLength : maxLengthFromMinLength(minLength);
-    return new ArrayArbitrary<T>(arb, minLength, maxLength);
+    return convertFromNext(new ArrayArbitrary<T>(nextArb, minLength, maxLength));
   }
   // fc.array(arb, minLength, maxLength)
-  if (args[1] !== undefined) return new ArrayArbitrary<T>(arb, args[0], args[1]);
+  if (args[1] !== undefined) return convertFromNext(new ArrayArbitrary<T>(nextArb, args[0], args[1]));
   // fc.array(arb, maxLength)
-  return new ArrayArbitrary<T>(arb, 0, args[0]);
+  return convertFromNext(new ArrayArbitrary<T>(nextArb, 0, args[0]));
 }
 
 export { array };
diff --git a/src/check/arbitrary/SetArbitrary.ts b/src/check/arbitrary/SetArbitrary.ts
index b10b4b4e..eead573a 100644
--- a/src/check/arbitrary/SetArbitrary.ts
+++ b/src/check/arbitrary/SetArbitrary.ts
@@ -1,5 +1,6 @@
 import { ArrayArbitrary, maxLengthFromMinLength } from './ArrayArbitrary';
 import { Arbitrary } from './definition/Arbitrary';
+import { convertFromNext, convertToNext } from './definition/Converters';
 
 /**
  * Build fully set SetConstraints from a partial data
@@ -186,7 +187,8 @@ function set<T>(
   const maxLength = constraints.maxLength;
   const compare = constraints.compare;
 
-  const arrayArb = new ArrayArbitrary<T>(arb, minLength, maxLength, compare);
+  const nextArb = convertToNext(arb);
+  const arrayArb = convertFromNext(new ArrayArbitrary<T>(nextArb, minLength, maxLength, compare));
   if (minLength === 0) return arrayArb;
   return arrayArb.filter((tab) => tab.length >= minLength);
 }
diff --git a/src/check/arbitrary/helpers/BuildCompareFilter.ts b/src/check/arbitrary/helpers/BuildCompareFilter.ts
index 886b1a91..6760f58c 100644
--- a/src/check/arbitrary/helpers/BuildCompareFilter.ts
+++ b/src/check/arbitrary/helpers/BuildCompareFilter.ts
@@ -1,4 +1,4 @@
-import { Shrinkable } from '../definition/Shrinkable';
+import { NextValue } from '../definition/NextValue';
 
 /** @internal */
 function subArrayContains<T>(tab: T[], upperBound: number, includeValue: (v: T) => boolean): boolean {
@@ -23,8 +23,8 @@ function swap<T>(tab: T[], idx1: number, idx2: number): void {
  * It returns the array without any duplicates.
  * @internal
  */
-export function buildCompareFilter<T>(compare: (a: T, b: T) => boolean): (tab: Shrinkable<T>[]) => Shrinkable<T>[] {
-  return (tab: Shrinkable<T>[]): Shrinkable<T>[] => {
+export function buildCompareFilter<T>(compare: (a: T, b: T) => boolean): (tab: NextValue<T>[]) => NextValue<T>[] {
+  return (tab: NextValue<T>[]): NextValue<T>[] => {
     let finalLength = tab.length;
     for (let idx = tab.length - 1; idx !== -1; --idx) {
       if (subArrayContains(tab, idx, (t) => compare(t.value_, tab[idx].value_))) {


Test patch:
diff --git a/test/unit/check/arbitrary/helpers/BuildCompareFilter.spec.ts b/test/unit/check/arbitrary/helpers/BuildCompareFilter.spec.ts
deleted file mode 100644
index 08b3ec23..00000000
--- a/test/unit/check/arbitrary/helpers/BuildCompareFilter.spec.ts
+++ /dev/null
@@ -1,19 +0,0 @@
-import * as fc from '../../../../../lib/fast-check';
-
-import { Shrinkable } from '../../../../../src/check/arbitrary/definition/Shrinkable';
-
-import { buildCompareFilter } from '../../../../../src/check/arbitrary/helpers/BuildCompareFilter';
-
-const validSet = (s: number[]) => s.length === new Set(s).size && s.every((e) => typeof e === 'number');
-
-describe('buildCompareFilter', () => {
-  it('Should filter array from duplicated values', () =>
-    fc.assert(
-      fc.property(fc.array(fc.nat()), (tab) => {
-        const filter = buildCompareFilter<number>((a, b) => a === b);
-        const adaptedTab = tab.map((v) => new Shrinkable(v));
-        const filteredTab = filter(adaptedTab);
-        expect(validSet(filteredTab.map((s) => s.value))).toBe(true);
-      })
-    ));
-});
diff --git a/test/unit/check/arbitrary/helpers/BuildCompareFilter.utest.spec.ts b/test/unit/check/arbitrary/helpers/BuildCompareFilter.utest.spec.ts
new file mode 100644
index 00000000..1de48d90
--- /dev/null
+++ b/test/unit/check/arbitrary/helpers/BuildCompareFilter.utest.spec.ts
@@ -0,0 +1,23 @@
+import * as fc from '../../../../../lib/fast-check';
+import { NextValue } from '../../../../../src/check/arbitrary/definition/NextValue';
+
+import { buildCompareFilter } from '../../../../../src/check/arbitrary/helpers/BuildCompareFilter';
+
+describe('buildCompareFilter', () => {
+  it('should filter array from duplicated values', () =>
+    fc.assert(
+      fc.property(fc.array(fc.nat()), (tab) => {
+        // Arrange
+        const filter = buildCompareFilter<number>((a, b) => a === b);
+        const adaptedTab = tab.map((v) => new NextValue(v));
+
+        // Act
+        const filteredTab = filter(adaptedTab);
+        const filteredTabValues = filteredTab.map((s) => s.value);
+
+        // Assert
+        expect(filteredTabValues).toHaveLength(new Set(filteredTabValues).size); // no duplicates
+        expect(filteredTabValues.every((e) => typeof e === 'number')).toBe(true);
+      })
+    ));
+});