Add Resizable AbstractArray interface for push! and append!?

General Usage
, ,
1

On Julia 1.10, the following AbstractVector implementation supports push! and append!:

julia> begin
       struct MyVector <: AbstractVector{Int}
           v::Vector{Int}
           function MyVector(args...)
               new(Vector{Int}(args...))
           end
       end
       Base.size(mv::MyVector) = size(mv.v)
       Base.getindex(v::MyVector, i::Int) = getindex(v.v, i)
       Base.setindex!(mv::MyVector, v, i::Int) = mv.v[i] = v
       Base.resize!(mv::MyVector, nl::Integer) = resize!(mv.v, nl)
       end

julia> v = MyVector(undef, 5)
5-element MyVector:
 0
 0
 0
 0
 0

julia> push!(v, 6)
6-element MyVector:
 0
 0
 0
 0
 0
 6

julia> append!(v, [1,2,3])
9-element MyVector:
 0
 0
 0
 0
 0
 6
 1
 2
 3

Beyond the AbstractArray interface, the only other method needed was resize!. On Julia 1.11, this appears to be no longer the case:

julia> begin
       struct MyVector <: AbstractVector{Int}
           v::Vector{Int}
           function MyVector(args...)
               new(Vector{Int}(args...))
           end
       end
       Base.size(mv::MyVector) = size(mv.v)
       Base.getindex(v::MyVector, i::Int) = getindex(v.v, i)
       Base.setindex!(mv::MyVector, v, i::Int) = mv.v[i] = v
       Base.resize!(mv::MyVector, nl::Integer) = resize!(mv.v, nl)
       end

julia> v = MyVector(undef, 5)
5-element MyVector:
 0
 0
 0
 0
 0

julia> push!(v, 6)
ERROR: MethodError: no method matching sizehint!(::MyVector, ::Int64)
The function `sizehint!` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  sizehint!(::BitSet, ::Integer; first, shrink)
   @ Base bitset.jl:58
  sizehint!(::BitVector, ::Integer)
   @ Base bitarray.jl:809
  sizehint!(::Dict{T}, ::Any; shrink) where T
   @ Base dict.jl:193
  ...

Stacktrace:
 [1] _append!(a::MyVector, ::Base.HasLength, iter::Tuple{Int64})
   @ Base ./array.jl:1320
 [2] append!(a::MyVector, iter::Tuple{Int64})
   @ Base ./array.jl:1313
 [3] push!(a::MyVector, iter::Int64)
   @ Base ./array.jl:1314
 [4] top-level scope
   @ REPL[3]:1

If I follow the suggestion and implement sizehint!, I then get a stack overflow.

julia> Base.sizehint!(v::MyVector, nl::Integer) = sizehint!(v.v, nl)

julia> push!(v, 6)
ERROR: StackOverflowError:
Stacktrace:
      [1] sizehint!(a::Vector{Int64}, sz::Int64; first::Bool, shrink::Bool)
        @ Base ./array.jl:1480
      [2] sizehint!
        @ ./array.jl:1480 [inlined]
      [3] sizehint!
        @ ./REPL[4]:1 [inlined]
      [4] sizehint!
        @ ./array.jl:1519 [inlined]
      [5] _append!
        @ ./array.jl:1320 [inlined]
      [6] append!
        @ ./array.jl:1313 [inlined]
      [7] push!(a::MyVector, iter::Int64)
        @ Base ./array.jl:1314
      [8] _append!
        @ ./array.jl:1322 [inlined]
--- the above 3 lines are repeated 79981 more times ---
 [239952] append!
        @ ./array.jl:1313 [inlined]

The stack overflow is due to push! calling append! which in turn calls push!. This appears to be due to the following pull request that is in Julia 1.11.0-rc2:

I discovered this while I was doing some maintenance on UInt12Arrays.jl, and I noticed that my tests were failing on Julia 1.11.0-rc2. There I noticed that push! and append! no longer work like above. I wonder if this might affect other AbstractArray or AbstractVector implementations.

Perhaps resize! and sizehint! should be added to the AbstractArray interface as an optional method to enable push! and append!.

If we only wanted to depend on resize! for push! and append! to work, perhaps we should consider adding the following to Base:

import Base: push!, sizehint!

function push!(vec::AbstractVector, v)
    new_length = length(vec) + 1
    resize!(vec, new_length)
    vec[new_length] = v
    return vec
end

# do nothing
sizehint!(vec::AbstractVector, nl::Integer) = vec
1 Like
2

Looking closer at the fixed issues by @Sukera and @Mason where the array would grow despite push! or append! failing perhaps we need the following.

import Base: push!, sizehint!
using Base: @_terminates_locally_meta

function push!(a::AbstractVector{T}, item) where T
    # convert first so we don't grow the array if the assignment won't work
    itemT = item isa T ? item : convert(T, item)::T
    new_length = length(a) + 1
    resize!(a, new_length)
    a[length(a)] = itemT
    return a
end

# specialize and optimize the single argument case
function push!(a::AbstractVector{Any}, @nospecialize x)
    new_length = length(a) + 1
    resize!(a, new_length)
    a[length(a)] = x
    return a
end
function push!(a::AbstractVector{Any}, @nospecialize x...)
    @_terminates_locally_meta
    na = length(a)
    nx = length(x)
    resize!(a, na + nx)
    for i = 1:nx
        a[na+i] = x[i]
    end
    return a
end

# do nothing
sizehint!(vec::AbstractVector, nl::Integer) = vec
3

That would also require re-adding setindex! to the interface, no? IIRC that has been removed from the interface a while ago, since not all AbstractArrays necessarily support mutation (e.g. 0:10).

1 Like
4

setindex! is listed as an optional method of the interface. It seems clear to me that push! will not work if setindex! is not defined, but perhaps that could also be made explicit.

1 Like
5

The other thing is that neither of push! nor append! work on actual N-dimensional arrays, they’re really only suitable for AbstractVector at best.

I personally don’t like that we have such β€œoptional” parts of an interface at all. This is more indicative of a lack of formal interfaces.

1 Like
6

append! works on N-dimensional ElasticArrays.jl, but you can only append! elements of a particular number and shape so that the last dimension increments, as if the last dimension could be the length of a vector that holds N-1-dimension arrays with a shape omitting the last dimension.