at least one other bug in the list about list HOT 19 CLOSED

@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

from list.

Fixed in 2.0.16.

from list.

another failing repro the fuzzer turned up previously btw:

Seq fuzzer

from list.

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.

from list.

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;

3. npm install && tsc
4. ./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.

from list.

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 emmanueltouzery@15f3845

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.

from list.

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

from list.

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

from list.

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.

from list.

I've now fixed the specific bug in #67 (comment) 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.

from list.

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)

from list.

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)

from list.

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

from list.

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

from list.

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

from list.

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

EDIT discard, caused by buggy pull request

from list.

The code in #67 (comment) is a really nice reproduction. I don't think it can be made much shorter. Thank a lot for it 😄

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.

from list.

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.

from list.

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

from list.