push!, append! AbstractVector implementations no longer work on Julia 1.11+

[mkitti]

Implementing Base.resize! used to be sufficient for push! and append! to work on Julia 1.10 and prior.

Consider the following Vector wrapper.

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

Attempting to use push! would suggest the implementation of resize!:

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

julia> push!(v, 1)
ERROR: MethodError: no method matching resize!(::MyVector, ::Int64)

Closest candidates are:
  resize!(::BitVector, ::Integer)
   @ Base bitarray.jl:814
  resize!(::Vector, ::Integer)
   @ Base array.jl:1312

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

After implmenting resize! as follows,

Base.resize!(mv::MyVector, nl::Integer) = resize!(mv.v, nl)

this allows push! to work on Julia 1.10.

julia> v = MyVector(undef, 5)
5-element MyVector:
               3
 124051546992229
             160
               6
  45253729152848

julia> push!(v, 6)
6-element MyVector:
               3
 124051546992229
             160
               6
  45253729152848
               6

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

On Julia 1.11-rc2, this no longer works:

julia> v = MyVector(undef, 5)
5-element MyVector:
                  15
 9223372036854775807
                  16
                   0
                  -1

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[15]:1

Following the suggestion, an implementation of sizehint! leads to StackOverflow error on Julia 1.11:

julia> Base.sizehint!(mv::MyVector, nl::Integer) = sizehint!(mv.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[16]: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]

julia> append!(v, [1,2,3])
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[16]: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]

As of #51903, append!(a::AbstractVector, iter) depends on push!(a::AbstractVector, iter...). This is problematic because push!(a::AbstractVector, iter...) depends on append!(a::AbstractVector, iter) which leads to the above stack overflow condition.

julia/base/array.jl

Lines 1305 to 1329 in 786caaa

	append!(a::AbstractVector, iter) = _append!(a, IteratorSize(iter), iter)
	push!(a::AbstractVector, iter...) = append!(a, iter)
	append!(a::AbstractVector, iter...) = foldl(append!, iter, init=a)
	function _append!(a::AbstractVector, ::Union{HasLength,HasShape}, iter)
	@_terminates_locally_meta
	n = length(a)
	i = lastindex(a)
	resize!(a, n+Int(length(iter))::Int)
	for (i, item) in zip(i+1:lastindex(a), iter)
	if isa(a, Vector) # give better effects for builtin vectors
	@_safeindex a[i] = item
	else
	a[i] = item
	end
	end
	a
	end
	function _append!(a::AbstractVector, ::IteratorSize, iter)
	for item in iter
	push!(a, item)
	end
	a
	end

The new implementation of append! suggests that we should modify the generic implementation of push! for AbstractVector:

import Base: push!

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

push!(a::AbstractVector, iter...) = append!(a, iter)

Importantly, this new implementation of push! now only depends on the AbstractArray interface and an implementation of resize!.