Loading this package breaks vcat(Union{}[])

[staticfloat]

In an empty Julia REPL:

vcat(Union{}[])

Should return Union{}[], however in the current release of AbstractAlgebra, it raises a BoundsError:

julia> using AbstractAlgebra; vcat(Union{}[])
ERROR: BoundsError: attempt to access 0-element Vector{Union{}} at index [1]
Stacktrace:
 [1] getindex(A::Vector{Union{}}, i1::Int64)
   @ Base ./essentials.jl:13
 [2] vcat(A::Vector{Union{}})
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/dsta0/src/NemoStuff.jl:0
 [3] top-level scope
   @ REPL[4]:1

[thofma]

Hm, yes, bad, but not unexpected (for the interested reader: JuliaLang/julia#47840 and the linked issues).

I understand why we have this function, but it is problematic. Apart from the error above, the problem is that the method we add to vcat violate swhat vcat generically wants to do, rendering it broken and useless.

Base promotes the use of reduce([hv]cat, vector), but we will run into the same ambiguity problems with Union{}[]:

julia> Base.reduce(::typeof(vcat), v::AbstractVector{<:MatrixElem}) = "asdsd"

julia> reduce(vcat, Union{}[])
ERROR: MethodError: reduce(::typeof(vcat), ::Vector{Union{}}) is ambiguous.

Candidates:
  reduce(::typeof(vcat), A::AbstractVector{<:AbstractVecOrMat})
    @ Base abstractarray.jl:1705
  reduce(::typeof(vcat), v::AbstractVector{<:MatrixElem})
    @ Main REPL[2]:1

Possible fix, define
  reduce(::typeof(vcat), ::AbstractVector{Union{}})

Stacktrace:
 [1] top-level scope
   @ REPL[3]:1

The correct error is:

julia> reduce(vcat, Union{}[])
ERROR: MethodError: reducing over an empty collection is not allowed; consider supplying `init` to the reducer

Any ideas? @fingolfin? @lgoettgens? Also happy to discuss it in person.

P.S.: Any method of the form Base.bla(x::T{OurType}) Base.bla(x::T{<: OurType}) (thanks @lgoettgens), where T is something like Type or Vector is problematic.

[lgoettgens]

P.S.: Any method of the form Base.bla(x::T{OurType}), where T is something like Type or Vector is problematic.

That shouldn't be the case, only for T{<:OurType} we have a problem with Union{}. I just learned that this is type piracy right before my vacation (see JuliaTesting/Aqua.jl#173 (comment)) and didn't have time yet to think about it or do some research.
Maybe let's talk about it on Friday before or after the oscar call (if that fits for you both).

[thofma]

Ah yes, I meant the UnionAll with <: OurType. I corrected it.

[thofma]

I will be available on Friday after the call.

[lgoettgens]

JuliaLang/julia#49349 added dispatches to base to deal with Type{Union{}} ambiguities in many cases. Maybe it would be easiest to do something similar for Vector{Union{}}?

[fingolfin]

There is also

  vcat(A::Vector{<:Hecke.PMat})
    @ Hecke ~/.julia/packages/Hecke/xXyd0/src/NumFieldOrd/NfOrd/LinearAlgebra.jl:1641

Anyway I made JuliaLang/julia#51718.

[thofma]

Yes, the one in Hecke also needs to be removed.

[fingolfin]

Note that we already define a reduce method for the vcat case in src/Matrix.jl:6499:

Base.reduce(::typeof(vcat), A::AbstractVector{<:MatrixElem}) = _vcat(A)

And of course it also causes this ambiguity:

julia> reduce(vcat, Union{}[])
ERROR: MethodError: reduce(::typeof(vcat), ::Vector{Union{}}) is ambiguous.

Candidates:
  reduce(::typeof(vcat), A::AbstractVector{<:AbstractVecOrMat})
    @ Base abstractarray.jl:1705
  reduce(::typeof(vcat), A::AbstractVector{<:MatrixElem})
    @ AbstractAlgebra ~/Projekte/OSCAR/AbstractAlgebra.jl/src/Matrix.jl:6499

Possible fix, define
  reduce(::typeof(vcat), ::AbstractVector{Union{}})

Stacktrace:
 [1] top-level scope
   @ REPL[2]:1

So what are we supposed to do then? To me it doesn't seem we are committing type piracy, as our own types are involved in the function signature and we are not otherwise overloading any existing Base functionality except for the Union{} case. The issue could then be "fixed" by adding something like this to Julia itself:

reduce(::typeof(vcat), A::AbstractVector{Union{}}) =
    _typed_vcat(mapreduce(eltype, promote_type, A), A)

reduce(::typeof(hcat), A::AbstractVector{Union{}}) =
    _typed_hcat(mapreduce(eltype, promote_type, A), A)

Indeed, experimentally:

julia> Base.reduce(::typeof(vcat), A::AbstractVector{Union{}}) =
           Base._typed_vcat(mapreduce(eltype, promote_type, A), A)

julia> Base.reduce(::typeof(hcat), A::AbstractVector{Union{}}) =
           Base._typed_hcat(mapreduce(eltype, promote_type, A), A)

julia> reduce(vcat, Union{}[])
ERROR: MethodError: reducing over an empty collection is not allowed; consider supplying `init` to the reducer
...

But would this be correct / acceptable ? Perhaps @vtjnash has a comment on that?

[lgoettgens]

@thofma and I decided to only fix the type piracy for *cat right now, as that changes the result. For reduce, we just added a comment to remind us in the future to find a solution. There are many packages doing similar things.

[thofma]

Keno said on slack that it is fine, which means it is fine for me too. If you are quick, you can read it at https://julialang.slack.com/archives/C67TK21LJ/p1697571176343309?thread_ts=1697567034.280449&cid=C67TK21LJ