Repository: dubzzz/fast-check
Pull request #1443 (2021-02-03 08:13:36)

✨ Support sparse arrays in stringify
<!-- 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

Possible impact on stringified values but actually no problems expected.


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

Latest deployment of this branch, based on commit e157ffe3be7aa8275aad5bc261ae6cb194a1ff5e:

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

codecov[bot]: # [Codecov](https://codecov.io/gh/dubzzz/fast-check/pull/1443?src=pr&el=h1) Report
> Merging [#1443](https://codecov.io/gh/dubzzz/fast-check/pull/1443?src=pr&el=desc) (e157ffe) into [master](https://codecov.io/gh/dubzzz/fast-check/commit/5433e9147024e88a196c1419830a44db126745fd?el=desc) (5433e91) will **decrease** coverage by `9.54%`.
> The diff coverage is `26.31%`.

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

```diff
@@            Coverage Diff             @@
##           master    #1443      +/-   ##
==========================================
- Coverage   98.27%   88.73%   -9.55%     
==========================================
  Files          91       91              
  Lines        3080     3097      +17     
  Branches      595      601       +6     
==========================================
- Hits         3027     2748     -279     
- Misses         50      341     +291     
- Partials        3        8       +5     
```

| Flag | Coverage Δ | |
|---|---|---|
| e2e-tests | `88.73% <26.31%> (-0.40%)` | :arrow_down: |
| e2e-tests-10.x-Linux | `88.73% <26.31%> (-0.40%)` | :arrow_down: |
| e2e-tests-10.x-Windows | `?` | |
| e2e-tests-10.x-macOS | `?` | |
| e2e-tests-12.x-Linux | `?` | |
| e2e-tests-12.x-Windows | `?` | |
| e2e-tests-12.x-macOS | `?` | |
| e2e-tests-14.x-Linux | `?` | |
| e2e-tests-14.x-Windows | `?` | |
| e2e-tests-14.x-macOS | `?` | |
| unit-tests | `?` | |
| unit-tests-10.x-Linux | `?` | |
| 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/1443?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/utils/stringify.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL3V0aWxzL3N0cmluZ2lmeS50cw==) | `67.85% <26.31%> (-31.10%)` | :arrow_down: |
| [src/check/property/TimeoutProperty.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL3Byb3BlcnR5L1RpbWVvdXRQcm9wZXJ0eS50cw==) | `11.76% <0.00%> (-88.24%)` | :arrow_down: |
| [src/check/model/commands/ScheduledCommand.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL21vZGVsL2NvbW1hbmRzL1NjaGVkdWxlZENvbW1hbmQudHM=) | `7.14% <0.00%> (-82.15%)` | :arrow_down: |
| [src/utils/hash.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL3V0aWxzL2hhc2gudHM=) | `29.62% <0.00%> (-70.38%)` | :arrow_down: |
| [...itrary/definition/ArbitraryWithContextualShrink.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9kZWZpbml0aW9uL0FyYml0cmFyeVdpdGhDb250ZXh0dWFsU2hyaW5rLnRz) | `46.66% <0.00%> (-53.34%)` | :arrow_down: |
| [.../check/arbitrary/definition/ArbitraryWithShrink.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL2FyYml0cmFyeS9kZWZpbml0aW9uL0FyYml0cmFyeVdpdGhTaHJpbmsudHM=) | `60.00% <0.00%> (-40.00%)` | :arrow_down: |
| [src/stream/LazyIterableIterator.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL3N0cmVhbS9MYXp5SXRlcmFibGVJdGVyYXRvci50cw==) | `63.63% <0.00%> (-36.37%)` | :arrow_down: |
| [src/check/property/AsyncProperty.generic.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL3Byb3BlcnR5L0FzeW5jUHJvcGVydHkuZ2VuZXJpYy50cw==) | `66.66% <0.00%> (-33.34%)` | :arrow_down: |
| [src/check/model/ModelRunner.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL21vZGVsL01vZGVsUnVubmVyLnRz) | `58.33% <0.00%> (-31.26%)` | :arrow_down: |
| [src/check/property/Property.generic.ts](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree#diff-c3JjL2NoZWNrL3Byb3BlcnR5L1Byb3BlcnR5LmdlbmVyaWMudHM=) | `70.58% <0.00%> (-29.42%)` | :arrow_down: |
| ... and [31 more](https://codecov.io/gh/dubzzz/fast-check/pull/1443/diff?src=pr&el=tree-more) | |

------

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


Patch:
diff --git a/src/utils/stringify.ts b/src/utils/stringify.ts
index ede27b51..83f95a0d 100644
--- a/src/utils/stringify.ts
+++ b/src/utils/stringify.ts
@@ -30,6 +30,17 @@ function stringifyNumber(numValue: number) {
   }
 }
 
+/** @internal */
+function isSparseArray(arr: unknown[]): boolean {
+  let previousNumberedIndex = -1;
+  for (const index in arr) {
+    const numberedIndex = Number(index);
+    if (numberedIndex !== previousNumberedIndex + 1) return true; // we've got a hole
+    previousNumberedIndex = numberedIndex;
+  }
+  return previousNumberedIndex + 1 !== arr.length; // we've got a hole if length does not match
+}
+
 /** @internal */
 export function stringifyInternal<Ts>(value: Ts, previousValues: any[]): string {
   const currentValues = previousValues.concat([value]);
@@ -38,8 +49,27 @@ export function stringifyInternal<Ts>(value: Ts, previousValues: any[]): string
     if (previousValues.indexOf(value) !== -1) return '[cyclic]';
   }
   switch (Object.prototype.toString.call(value)) {
-    case '[object Array]':
-      return `[${(value as any).map((v: any) => stringifyInternal(v, currentValues)).join(',')}]`;
+    case '[object Array]': {
+      const arr = (value as unknown) as unknown[];
+      if (arr.length >= 50 && isSparseArray(arr)) {
+        const assignments: string[] = [];
+        // Discarded: map then join will still show holes
+        // Discarded: forEach is very long on large sparse arrays, but only iterates on non-holes integer keys
+        for (const index in arr) {
+          if (!Number.isNaN(Number(index)))
+            assignments.push(`${index}:${stringifyInternal(arr[index], currentValues)}`);
+        }
+        return assignments.length !== 0
+          ? `Object.assign(Array(${arr.length}),{${assignments.join(',')}})`
+          : `Array(${arr.length})`;
+      }
+      // stringifiedArray results in: '' for [,]
+      // stringifiedArray results in: ',' for [,,]
+      // stringifiedArray results in: '1,' for [1,,]
+      // stringifiedArray results in: '1,,2' for [1,,2]
+      const stringifiedArray = arr.map((v) => stringifyInternal(v, currentValues)).join(',');
+      return arr.length === 0 || arr.length - 1 in arr ? `[${stringifiedArray}]` : `[${stringifiedArray},]`;
+    }
     case '[object BigInt]':
       return `${value}n`;
     case '[object Boolean]':


Test patch:
diff --git a/test/unit/utils/stringify.spec.ts b/test/unit/utils/stringify.spec.ts
index 2fb1b2fc..780f2d45 100644
--- a/test/unit/utils/stringify.spec.ts
+++ b/test/unit/utils/stringify.spec.ts
@@ -89,6 +89,44 @@ describe('stringify', () => {
     const repr = stringify(cyclic);
     expect(repr).toEqual('[1,2,3,[cyclic],4]');
   });
+  it('Should be able to stringify small sparse arrays', () => {
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([,])).toEqual('[,]'); // empty with one hole
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([, ,])).toEqual('[,,]'); // empty with two holes
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([, , , ,])).toEqual('[,,,,]'); // empty with four holes
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([1, , ,])).toEqual('[1,,,]'); // one value then two holes
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([, , 1, , 2])).toEqual('[,,1,,2]'); // two holes non-trailing holes
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([1, , 2])).toEqual('[1,,2]'); // one hole non-trailing hole
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([1, 2, ,])).toEqual('[1,2,,]'); // two values then one hole
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify([1, 2, , ,])).toEqual('[1,2,,,]'); // two values then two holes
+  });
+  it('Should be able to stringify large sparse arrays', () => {
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify(Array(10000))).toEqual('Array(10000)');
+    // eslint-disable-next-line no-sparse-arrays
+    expect(stringify(Array(4294967295))).toEqual('Array(4294967295)');
+    // eslint-disable-next-line no-sparse-arrays
+    const sparseNonEmpty: any[] = Array(10000);
+    sparseNonEmpty[150] = 5;
+    sparseNonEmpty[21] = 1;
+    sparseNonEmpty[200] = 10;
+    expect(stringify(sparseNonEmpty)).toEqual('Object.assign(Array(10000),{21:1,150:5,200:10})');
+    // Here are some possibilities for sparse versions:
+    // > (s=Array(10000),s[21]=1,s[150]=5,s[200]=10,s)
+    // > (()=>{const s=Array(10000);s[21]=1;s[150]=5;s[200]=10;return s;})()
+    // > Object.assign(Array(10000), {21:1,150:5,200:10})
+    // > [<20 empty slots>, 1,...] [cannot be copy-pasted]
+    const sparseNonEmptyB: any[] = Array(4294967295);
+    sparseNonEmptyB[1234567890] = 5;
+    expect(stringify(sparseNonEmptyB)).toEqual('Object.assign(Array(4294967295),{1234567890:5})');
+  });
   it('Should be able to stringify cyclic sets', () => {
     const cyclic: Set<any> = new Set([1, 2, 3]);
     cyclic.add(cyclic);