hvncat miscomputes output bounds for empty Vectors

[mfalt]

On: Version 1.7.0-DEV.1222 (2021-06-01)
Commit 4a8572f

Tried to figure out the new syntax for hvncat and ran into this bug:

julia> [[];;7;8]
2×2 Matrix{Any}:
 1  #undef
 2  #undef

Not sure what the expected behavior is, but since [7;8;;[]] throws an error, I assume that some boundscheck is missing.

This seems to be an almost equivalent call

 julia> hvncat(((1,2),(3,)), false, zeros(Int,0,), 7, 8)
2×2 Matrix{Int64}:
 7  0
 8  0

Trying to debug, these works as expected:

julia> hvncat(((1,2),(3,)), false, zeros(Int,2,0), 7.0, 8.0)
2×1 Matrix{Float64}:
 7.0
 8.0

julia> hvncat(((1,2),(3,)), false, zeros(Int, 2,), 7, 8)
2×2 Matrix{Int64}:
 0  7
 0  8

However, you can quickly cause a segfault:

julia> hvncat(((1,2),(3,)), false, zeros(Int,0,0,0), 7, 8)

Trace:

julia> hvncat(((1,2),(3,)), false, zeros(Int,0,0,0), 7, 8)
signal (11): Segmentation fault
in expression starting at none:0
jl_gc_pool_alloc at /work/mattiasf/juliagit_dev/src/gc.c:1211
jl_gc_alloc_ at /work/mattiasf/juliagit_dev/src/julia_internal.h:315 [inlined]
jl_gc_alloc at /work/mattiasf/juliagit_dev/src/gc.c:3278
_new_array_ at /work/mattiasf/juliagit_dev/src/array.c:122 [inlined]
_new_array at /work/mattiasf/juliagit_dev/src/array.c:188 [inlined]
jl_alloc_array_1d at /work/mattiasf/juliagit_dev/src/array.c:459
Array at ./boot.jl:453 [inlined]
Array at ./boot.jl:472 [inlined]
getindex at ./array.jl:411 [inlined]
with_repl_linfo at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:503
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
display at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:254
display at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:266
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
display at ./multimedia.jl:328
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
jl_apply at /work/mattiasf/juliagit_dev/src/julia.h:1760 [inlined]
jl_f__call_latest at /work/mattiasf/juliagit_dev/src/builtins.c:751
#invokelatest#2 at ./essentials.jl:726 [inlined]
invokelatest at ./essentials.jl:724 [inlined]
print_response at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:288
#45 at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:272
jfptr_YY.45_20661 at /work/mattiasf/juliagit_dev/usr/lib/julia/sys.so (unknown line)
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
with_repl_linfo at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:505
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
print_response at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:270
do_respond at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:841
jfptr_do_respond_20618 at /work/mattiasf/juliagit_dev/usr/lib/julia/sys.so (unknown line)
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
jl_apply at /work/mattiasf/juliagit_dev/src/julia.h:1760 [inlined]
jl_f__call_latest at /work/mattiasf/juliagit_dev/src/builtins.c:751
#invokelatest#2 at ./essentials.jl:726 [inlined]
invokelatest at ./essentials.jl:724 [inlined]
run_interface at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/LineEdit.jl:2493
jfptr_run_interface_20024 at /work/mattiasf/juliagit_dev/usr/lib/julia/sys.so (unknown line)
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
run_frontend at /work/mattiasf/juliagit_dev/usr/share/julia/stdlib/v1.7/REPL/src/REPL.jl:1227
#49 at ./task.jl:411
jfptr_YY.49_20803 at /work/mattiasf/juliagit_dev/usr/lib/julia/sys.so (unknown line)
_jl_invoke at /work/mattiasf/juliagit_dev/src/gf.c:2244 [inlined]
jl_apply_generic at /work/mattiasf/juliagit_dev/src/gf.c:2426
jl_apply at /work/mattiasf/juliagit_dev/src/julia.h:1760 [inlined]
start_task at /work/mattiasf/juliagit_dev/src/task.c:822
Allocations: 10796169 (Pool: 10791934; Big: 4235); GC: 13
[1]    3143063 segmentation fault (core dumped)  ./julia

Edit: Bug generalizes to higher dims: [zeros(Int,2,0);;;7;8]

[JeffBezanson]

With --check-bounds=yes:

julia> Base.hvncat(((1,2),(3,)), false, zeros(Int,0,0,0), 7, 8)
ERROR: BoundsError: attempt to access 2×1×0 Array{Int64, 3} at index [1]
Stacktrace:
 [1] setindex!
   @ ./array.jl:877 [inlined]
 [2] hvncat_fill!(A::Array{Int64, 3}, scratch1::Vector{Int64}, scratch2::Vector{Int64}, d1::Int64, d2::Int64, as::Tuple{Array{Int64, 3}, Int64, Int64})
   @ Base ./abstractarray.jl:2361
 [3] _typed_hvncat(::Type{Int64}, ::Tuple{Tuple{Int64, Int64}, Tuple{Int64}}, ::Bool, ::Array{Int64, 3}, ::Vararg{Any})
   @ Base ./abstractarray.jl:2339
 [4] _hvncat(::Tuple{Tuple{Int64, Int64}, Tuple{Int64}}, ::Bool, ::Array{Int64, 3}, ::Vararg{Any})
   @ Base ./abstractarray.jl:2108
 [5] hvncat(::Tuple{Tuple{Int64, Int64}, Tuple{Int64}}, ::Bool, ::Array{Int64, 3}, ::Vararg{Any})
   @ Base ./abstractarray.jl:2104
 [6] top-level scope
   @ REPL[1]:1

[vtjnash]

Looks like the new hvncat code is littered with @inbounds markers (half of which seem be on code that never even does indexing), yet it never bothers to make sure that those accesses are inbounds. This leads to arbitrary memory corruption, which leads to the crashes observed here. I'll make a PR to delete them, then someone can re-add corrected ones more methodically.

[BioTurboNick]

Just seeing this.

With respect to @inbounds I was experimenting and measuring what seemed to help performance; I know about lower functions being able to propagate inbounds, but I didn't bother looking to see if they all particularly did.

The loop discovering the array bounds is what (is supposed to) guarantee no out of bounds accesses, so I take issue with saying hvncat never bothers to check. But clearly, empty arrays break an assumption I was implicitly making that each item being concatenated has at least one element in it.

[BioTurboNick]

Turns out there were two separate issues with the shape variant of hvncat.

One was handling of zero-length arrays, leading to an underfilled array.

The second, which led to the segfault, was a dumb error on my part, where I did not expand the shape argument and check higher dimensions, to account for the case where one or more concatenated elements has ndims greater than the maximum concatenation dimension. Both are fixed in the linked PR.

[vtjnash]

@BioTurboNick to be clear, your PR and dedication are great and much appreciated! I'm sometimes annoyed at code, but not usually at the people behind it.

[BioTurboNick]

Fair enough 😁

[simeonschaub]

@BioTurboNick Does one of your broken up PRs fix this issue? If so, would be good to link back to here.

[BioTurboNick]

Yes, partially. #41196 catches the one that leads to an underfilled array and works for dims and int cases, but I haven't found a general solution for detecting and erroring when improperly-shaped 0-size arrays are input for the shape form.

Currently, it treats them like they're nothing. e.g. [zeros(Int, 0,0,0) ;;; a b] == [a b;;;]. Which is not terrible but also not formally correct.

[JeffBezanson]

I believe this is fixed by #41196; plz reopen if I'm mistaken.

[BioTurboNick]

Yes. I'll open another issue for the zero-length array inputs.