collect removes bounds-checks, even for broken custom types

[saolof]

Here's a basic gist, using the smallest approximate input sizes that consistently triggers the bug
https://gist.github.com/saolof/dcf785c559574b16d478db4632173096

The above implementation of pairing heaps is fairly robust when using linked lists (though copying to an array and sorting there is clearly going to be a lot faster if you don't specifically need a persistent heap), but attempting to make it use vectors instead (replacing cons/tail/head with push/pop/peek) will consistently cause Julia to crash on my machine even when using heapsort on just a hundred elements. It looks like this may be some memory allocator failure?

[Seelengrab]

What kind of error do you get? Is a stacktrace printed?

[saolof]

What kind of error do you get? Is a stacktrace printed?

Julia.exe crashes and gives me this:

Test fail

Please submit a bug report with steps to reproduce this fault, and any error messages that follow (in their entirety). Thanks.
Exception: EXCEPTION_ACCESS_VIOLATION at 0x1f7add9 -- jl_gc_pool_alloc at /cygdrive/c/buildbot/worker/package_win64/build/src\gc.c:1210 [inlined]
jl_gc_alloc_ at /cygdrive/c/buildbot/worker/package_win64/build/src\julia_internal.h:285 [inlined]
jl_gc_alloc at /cygdrive/c/buildbot/worker/package_win64/build/src\gc.c:3283
in expression starting at C:\Users\olofs\Documents\prologic\rkanren\pairingheap.jl:69
jl_gc_pool_alloc at /cygdrive/c/buildbot/worker/package_win64/build/src\gc.c:1210 [inlined]
jl_gc_alloc_ at /cygdrive/c/buildbot/worker/package_win64/build/src\julia_internal.h:285 [inlined]
jl_gc_alloc at /cygdrive/c/buildbot/worker/package_win64/build/src\gc.c:3283
_new_array_ at /cygdrive/c/buildbot/worker/package_win64/build/src\array.c:122
_new_array at /cygdrive/c/buildbot/worker/package_win64/build/src\array.c:188 [inlined]
jl_alloc_array_1d at /cygdrive/c/buildbot/worker/package_win64/build/src\array.c:459
Array at .\boot.jl:448 [inlined]
similar at .\array.jl:353 [inlined]
copymutable at .\abstractarray.jl:1081 [inlined]
#sort#9 at .\sort.jl:764 [inlined]
sort at .\sort.jl:764 [inlined]
top-level scope at C:\Users\olofs\Documents\prologic\rkanren\pairingheap.jl:75
jl_toplevel_eval_flex at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:871
jl_toplevel_eval_flex at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:825
jl_toplevel_eval at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:886 [inlined]
jl_toplevel_eval_in at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:929
eval at .\boot.jl:360 [inlined]
include_string at .\loading.jl:1094
_include at .\loading.jl:1148
include at .\Base.jl:386
exec_options at .\client.jl:285
_start at .\client.jl:485
jfptr__start_22922.clone_1 at c:\users\olofs\appdata\local\programs\julia-1.6.1\lib\julia\sys.dll (unknown line)
jl_apply at /cygdrive/c/buildbot/worker/package_win64/build/src\julia.h:1703 [inlined]
true_main at /cygdrive/c/buildbot/worker/package_win64/build/src\jlapi.c:560
repl_entrypoint at /cygdrive/c/buildbot/worker/package_win64/build/src\jlapi.c:702
mainCRTStartup at /cygdrive/c/buildbot/worker/package_win64/build/cli\loader_exe.c:51
BaseThreadInitThunk at C:\WINDOWS\System32\KERNEL32.DLL (unknown line)
RtlUserThreadStart at C:\WINDOWS\SYSTEM32\ntdll.dll (unknown line)
Allocations: 8821659 (Pool: 8819617; Big: 2042); GC: 11

(line numbers may be slightly off from gist)

[JeffBezanson]

With this kind of error it's often helpful to try --check-bounds=yes:

ERROR: LoadError: BoundsError: attempt to access 100-element Vector{Int64} at index [101]
Stacktrace:
 [1] setindex!
   @ ./array.jl:877 [inlined]
 [2] collect_to!(dest::Vector{Int64}, itr::Base.Generator{PairingTree{Int64}, typeof(identity)}, offs::Int64, st::PairingTree{Int64})
   @ Base ./array.jl:760
 [3] collect_to_with_first!(dest::Vector{Int64}, v1::Int64, itr::Base.Generator{PairingTree{Int64}, typeof(identity)}, st::PairingTree{Int64})
   @ Base ./array.jl:734
 [4] collect(itr::Base.Generator{PairingTree{Int64}, typeof(identity)})
   @ Base ./array.jl:715
 [5] heapsort
   @ ~/src/julia/i41214.jl:66 [inlined]
 [6] top-level scope
   @ ~/src/julia/i41214.jl:72

It looks like the length and iterate methods of PairingTree are not consistent. Unfortunately we are sometimes too optimistic with @inbounds, and one of our internal uses is causing a crash here. We should probably remove those sorts of @inbounds declarations, though it will have some performance cost.

[vtjnash]

We could perhaps try switching that loop:

xi, state = something(iterate(x))
a[1] = xi
for i in 2:length(a)
   xi, state = something(iterate(x, state))
   @inbounds a[i] = xi
end
iterate(x, state) === nothing || throw(BoundsError())

But I think that may be equivalent, in terms of branches and bounds

[vtjnash]

If we had the above with @inbounds iterate(x, state), then perhaps that iterator would skip the bounds check though?

[saolof]

I mean, arguably the root of this is the fact that everything is HasLength() by default, so that you effectively have to explicitly opt out of implementations that require the length to be safe, rather than the other way around.

[JeffBezanson]

HasLength is not about safety though; it's about whether length is defined at all. One can certainly debate what the default should be, but it's not causing the crash here.

[saolof]

Incidentally, I tracked down the source of the broken length in the first case: pop in FunctionalCollections.jl is broken, and there is an unmerged pull request from almost a year ago that would fix it. That was also the reason why the code worked for Lists but not Persistent vectors

[JeffBezanson]

From triage:

• If we want to fix this soon, we need to just take the performance hit and remove the @inbounds. But things have been like this for a while so it's not necessarily urgent.
• @oscardssmith Suggested a trait you define to more firmly assert that you think your length is correct (I believe this idea has come up before). Then we would need to add arguments to @inbounds, e.g. @inbounds x a[i] = b, which says x needs to be trusted to remove the bounds check. A bit complex but I don't have any better ideas.