at least one other bug in the list

[emmanueltouzery]

so i've been a been worried because of the bug I found previously in list and decided to write a fuzzer to search for bugs. The fuzzer is relavitely easier to write for me because I have several collections with the same API (vector, linkedlist, stream).

And actually it found at least one bug in list 2.0.14. There could be several, it's hard to tell. I've extracted a reproduction from a run of the fuzzer where the reproduction was a little shorter... But obviously it's not exactly a minimal reproduction.

Here's the reproduction, I run actions on both list and a plain JS array. The actions should result in the same result, but they don't.

notice that both lists have the same value up to the last computation. So in the end to convince yourself there's a bug you only need to review the last lines.

The final lists are completely different, list returning a list starting with [ 2704, 2688, 2672, .. and JS arrays by [ 1136, 1128, 1120, ....

const L = require("list")

let f = L.list()
let g = []

function arrayOfLength(l:number) {
    const r = [];
    for (let i=0;i<l;i++) {
        r.push(i);
    }
    return r;
}

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.concat(f, L.from(arrayOfLength(176)));
g = [...g,...arrayOfLength(176)];

f = L.concat(f, L.from(arrayOfLength(230)));
g = [...g,...arrayOfLength(230)];

f = L.take(24, f);
g = g.slice(0,24)

f = L.take(116, f);
g = g.slice(0,116)

f = L.concat(f, L.from(arrayOfLength(125)));
g = [...g, ...arrayOfLength(125)];

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.concat(f, L.from(arrayOfLength(192)));
g = [...g, ...arrayOfLength(192)];

f = L.concat(f, L.from(arrayOfLength(211)));
g = [...g, ...arrayOfLength(211)];

f = L.concat(L.from(arrayOfLength(243)), f);
g = [...arrayOfLength(243),...g];

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.reverse(f)
g = g.reverse()

f = L.concat(f, L.from(arrayOfLength(236)));
g = [...g, ...arrayOfLength(236)];

f = L.reverse(f)
g = g.reverse()

f = L.concat(f, L.from(arrayOfLength(231)));
g = [...g, ...arrayOfLength(231)];

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.drop(81, f)
g = g.slice(81)

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.concat(f, L.from(arrayOfLength(142)));
g = [...g, ...arrayOfLength(142)];

f = L.reverse(f)
g = g.reverse()

f = L.map(x=>x*2, f)
g = g.map(x=>x*2)

f = L.concat(f, L.from(arrayOfLength(112)));
g = [...g, ...arrayOfLength(112)];

f = L.concat(f, L.from(arrayOfLength(121)));
g = [...g, ...arrayOfLength(121)];

// up to here both lists are equal

f = L.drop(230, f)
g = g.slice(230)

console.log(L.toArray(f))
console.log(g)

[emmanueltouzery]

another failing repro the fuzzer turned up previously btw:

Seq fuzzer

*** vector/llist BUG [ 'drop 113', 'reverse', 'take 61', 'take 38', 'map *2', 'prepend 84', 'append 9', 'take 83', 'drop 196', 'take 188', 'filter >=72', 'filter >=178', 'take 236', 'append 195', 'reverse', 'append 117', 'drop 58', 'drop 111', 'take 194', 'filter >=141', 'drop 19', 'map *2', 'filter >=199', 'take 84', 'filter >=24', 'append 129', 'append 93', 'append 88', 'reverse', 'append 132', 'prepend 208', 'reverse', 'prepend 212', 'append 174', 'map *2', 'append 178', 'map *2', 'drop 80', 'append 77', 'reverse', 'append 17', 'map *2', 'append 68', 'drop 158' ]

[paldepind]

decided to write a fuzzer to search for bugs.

That's really awesome! I've been meaning to create a similar thing myself. If you're interested in submitting the fuzzer as a PR I'd very much appreciate it.

I'll look into the examples with bugs. Over the weekend most likely.

[emmanueltouzery]

currently it's not hard to use the fuzzer built in prelude git repo. maybe i'll find some time to make a PR for funkia too, but i'll see.

to use the fuzzer in prelude...

1. fetch the prelude source, master

2. potentially edit the package.json to point to your funkia list install folder instead of 2.0.14

3. probably edit in tests/Seq.ts =>

   -    const testsToRun = 200;
   +    const testsToRun = 2000;

4. npm install && tsc

5. ./node_modules/mocha/bin/mocha --throw-deprecation --timeout 60000 ./dist/tests/Seq.js -g fuzz (could run the whole npm test but this runs this test only)

but otherwise the fuzzer's not much code, really.

[emmanueltouzery]

if that's useful i made a start of a raw port of the prelude's fuzzer to list, but I won't have time to finish it.

what i have is https://github.com/emmanueltouzery/list/commit/15f38451d2e2a4def821ceced482f54e46ddc10a

actually i have trouble building list after fetching it from git. but even if that was smooth for me, i won't have time i believe. but you could start with that if you're interested.

[dubzzz]

You should maybe try to benefit from property based testing in order to get back a smaller corner case. fast-check comes with a useful built-in to run tests like that: fc.commands.

@paldepind I can try to find the above failure with fast-check and see if we can get back a shorter test case

More at https://github.com/dubzzz/fast-check/tree/master/example/model-based-testing

[emmanueltouzery]

yes, property-based frameworks offer shrinking and that helps. good idea if you make it.

[dubzzz]

@paldepind I implemented the property based test using https://github.com/dubzzz/fast-check/. I will clean a little bit the test code before issuing a PR to add it.

By the way, this is an interesting case for fast-check as it reaches the limits where shrinker of arrays becomes problematic. I think that I will add a limiter on the number of suggested shrunk values.

It converges on the following case:

let src = L.from([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]); // 1089
src = L.reverse(src);
src = L.concat(src, L.from([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])); // 34
src = L.take(2, src);
console.log(L.toArray(src).length); // => expected 2 got 994

One interesting thing to notice is that by switching L.concat(src, L.from([...])) to L.concat(src, [...]) the code above passed. I have not checked yet if it is enough to make it works.

Runkit code: https://runkit.com/dubzzz/5b92a935f11fe20011ed2fba

[emmanueltouzery]

otherwise I'm not convinced that there's only one bug. There could possibly be several of them but we'll know when the first one gets fixed.

[paldepind]

I've now fixed the specific bug in https://github.com/funkia/list/issues/67#issuecomment-419504257 and I've released a new patch release 2.0.15. @emmanueltouzery please let me know if this affects any of the other bugs you've reported.

Unfortunately, I'm currently busy with my university courses which mean I don't have much spare time for coding 😭 My current plan is to chip away at the reported bugs and after they've been fixed look at and merge #69. I'm very excited about the model based property testing. It's ideal for the situation in List where different functions can affect each other in subtle ways.

[emmanueltouzery]

first great that one issue is down! unfortunately I confirmed that the bug #68 is still present and also I still got a crash with 2.0.15, here is the reproduction I have (maybe @dubzzz can get a shorter reproduction) =>

  Seq fuzzer
*** vector/llist BUG
[ 'prepend 26',
  'reverse',
  'reverse',
  'take 190',
  'append 40',
  'map *2',
  'take 5',
  'map *2',
  'drop 98',
  'reverse',
  'reverse',
  'filter >=142',
  'prepend 107',
  'map *2',
  'append 0',
  'drop 15',
  'prepend 53',
  'reverse',
  'take 36',
  'drop 231',
  'map *2',
  'drop 63',
  'take 62',
  'take 46',
  'append 57',
  'prepend 99',
  'drop 226',
  'append 213',
  'append 113',
  'drop 172',
  'append 62',
  'drop 137',
  'map *2',
  'prepend 179',
  'drop 91',
  'append 94',
  'take 61',
  'append 133',
  'append 88',
  'append 246',
  'prepend 182',
  'map *2',
  'prepend 155',
  'append 225',
  'reverse',
  'append 107',
  'take 118' ]
    1) should pass the fuzzer

  0 passing (6s)
  1 failing

  1) Seq fuzzer should pass the fuzzer:

      AssertionError [ERR_ASSERTION]: [ 224,
  223,
  222,
  221,
  220,
  219,
  218,
  217,
  216,
  215,
  214,
  213,
  212,
  211,
  210,
  209,
  208,
  207,
   deepEqual [ 224,
  223,
  222,
  221,
  220,
  219,
  218,
  217,
  216,
  215,
  214,
  213,
  212,
  211,
  210,
  209,
  208,
  207,

      + expected - actual

         142
         141
         140
         139
      +  138
      +  137
      +  136
      +  135
      +  134
      +  133
      +  132
      +  131
      +  130
      +  129
      +  128
      +  127
      +  126
      +  125
      +  124
      +  123
      +  122
      +  121
      +  120
      +  119
      +  118
      +  117
      +  116
      +  115
      +  114
      +  113
      +  112
      +  111
      +  110
      +  109
      +  108
      +  107
       ]

      at _loop_2 (dist/tests/Seq.js:408:28)
      at _loop_1 (dist/tests/Seq.js:417:17)
      at Context.<anonymous> (dist/tests/Seq.js:421:13)

[emmanueltouzery]

I tuned my test to try to get shorter reproductions.

-    const testsToRun = 0; 
-    const opsToRun = 64;
-    const randomArrayMaxLength = 256;
+    const testsToRun = 300000; 
+    const opsToRun = 7;
+    const randomArrayMaxLength = 8196;

I got this in 4 steps with 2.0.15 =>

Seq fuzzer *** vector/llist BUG [ 'append 5440', 'append 6338', 'drop 4194', 'drop 6229' ]

and here's a short repro program =>

const L = require("list")

let f = L.list()
let g = []

function arrayOfLength(l:number) {
    const r = [];
    for (let i=0;i<l;i++) {
        r.push(i);
    }
    return r;
}

f = L.concat(f, L.from(arrayOfLength(5440)));
g = [...g,...arrayOfLength(5440)];

f = L.concat(f, L.from(arrayOfLength(6338)));
g = [...g,...arrayOfLength(6338)];

f = L.drop(4194, f)
g = g.slice(4194)

f = L.drop(6229, f)
g = g.slice(6229)

console.log("LIST")
console.log(L.toArray(f))
console.log("ARRAY")
console.log(g)

[paldepind]

Thanks a lot @emmanueltouzery. That test case is quite a lot nicer.

[emmanueltouzery]

i think it's about the offset.

in the example...

f = L.drop(4194, f) g = g.slice(4194)

<-- here the list offset is 128

f = L.drop(6229, f) g = g.slice(6229)

<-- here the list offset is 0, but the list is missing the first 128 elements

[emmanueltouzery]

I think this would be the next bug, even after #71 is applied...

[ 'append 2144', 'map *2', 'drop 1092', 'take 1671', 'drop 183' ]

it's quite bad, clearly there were quite some gremlins hiding...

EDIT discard, possibly caused by buggy pull request

[emmanueltouzery]

a shorter one => [ 'append 2891', 'reverse', 'drop 267' ]

EDIT discard, caused by buggy pull request

[paldepind]

The code in https://github.com/funkia/list/issues/67#issuecomment-423718420 is a really nice reproduction. I don't think it can be made much shorter. Thank a lot for it :smile:

i think it's about the offset.

That turned out to be true! A combination of offset and the size tables used for concatenation caused the problem. I've opened #73 which should fix the issue. If you have the time feel free to try the code in the PR. Before I merge it I want to experiment with some other ways to solve the problem to see if there is a cleaner solution.

[emmanueltouzery]

I think #73 is the right fix for all. With #73 I can't reproduce any issue with the fuzzer. I think also #68 is probably fixed. I recommend you merge #73 and then try to merge #69 and I assume #69 will not find any issues anymore! And once your merge #73 I think you can close #67 and #68.

[paldepind]

Fixed in 2.0.16.

[dubzzz]

Great job :) I can rework on #69 if you need to. Let me know if you need help with it