list: at least one other bug in the list
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)
About this issue
- Original URL
- State: closed
- Created 6 years ago
- Comments: 19 (19 by maintainers)
Commits related to this issue
- bug #67: fix corruption when using slice and offset is present — committed to emmanueltouzery/list by emmanueltouzery 6 years ago
@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:
One interesting thing to notice is that by switching
L.concat(src, L.from([...]))toL.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
Fixed in 2.0.16.