deepcopy with non-trivial circular references fails in 1.11.2

[DrChainsaw]

Not sure if this is just a symptom of deepcopy not having much in terms of guaranteed behaviour, but it is no longer consistent with serialize => deserialize.

I tried to recreate it with a simpler structure (e.g. just Arrays which contain themselves) but couldn't. This is the most stripped down version I could create:

struct ProblemStruct{T}
    label::String # Just helps a bit when debugging
    inputs::T
end

using Serialization

let 
    problem = ProblemStruct("problem", ProblemStruct[])

    next = ProblemStruct("next", [problem])
    push!(problem.inputs, next) # Make a circular reference

    println("Original:")
    @show problem === next.inputs[1]
    @show problem.inputs[1] === next

    problemc, nextc = deepcopy((problem, next))
    println("\ndeepcopy:")
    @show problemc === nextc.inputs[1]
    @show problemc.inputs[1] === nextc

    println("\nserde:")
    problemds, nextds = let 
        io = PipeBuffer()
        serialize(io, (problem, next))
        deserialize(io)
    end
    @show problemds === nextds.inputs[1]
    @show problemds.inputs[1] === nextds

end;

Prints the following in Julia 1.11.2:

Original:
problem === next.inputs[1] = true    
problem.inputs[1] === next = true    

deepcopy:
problemc === nextc.inputs[1] = false 
problemc.inputs[1] === nextc = true  

serde:
problemds === nextds.inputs[1] = true
problemds.inputs[1] === nextds = true

And this in Julia 1.10.7:

Original:
problem === next.inputs[1] = true
problem.inputs[1] === next = true

deepcopy:
problemc === nextc.inputs[1] = true
problemc.inputs[1] === nextc = true

serde:
problemds === nextds.inputs[1] = true
problemds.inputs[1] === nextds = true

Fwiw: I can work around the problem on my side with the following:

function Base.deepcopy_internal(v::Vector{ProblemStruct}, stackdict::IdDict)
    v in keys(stackdict) && return stackdict[v]
    newv = similar(v)
    stackdict[v] = newv
    for (i, vi) in zip(eachindex(newv), v)
        newv[i] = Base.deepcopy_internal(vi, stackdict)
    end
    return newv
end

Versioninfo 1.11.2:

Julia Version 1.11.2
Commit 5e9a32e7af (2024-12-01 20:02 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 12 × Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, haswell)
Threads: 12 default, 0 interactive, 6 GC (on 12 virtual cores)
Environment:
  JULIA_DEPOT_PATH = E:/Programs/julia/.julia
  JULIA_PKG_DEVDIR = E:/Programs/julia/.julia/dev
  JULIA_EDITOR = code

Versioninfo 1.10.7:

Julia Version 1.10.7
Commit 4976d05258 (2024-11-26 15:57 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 12 × Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, haswell)
Threads: 1 default, 0 interactive, 1 GC (on 12 virtual cores)
Environment:
  JULIA_DEPOT_PATH = E:/Programs/julia/.julia
  JULIA_PKG_DEVDIR = E:/Programs/julia/.julia/dev

[nsajko]

Not sure if related: #26020

[willtebbutt]

To offer another example, this caused me some trouble when handling arrays containing circular references:

On 1.10.7 I see

julia> function make_circular_reference_array()
           p = Any[nothing]
           p[1] = p
           return p
       end
make_circular_reference_array (generic function with 1 method)

julia> p = make_circular_reference_array()
1-element Vector{Any}:
 1-element Vector{Any}:#= circular reference @-1 =#

julia> p2 = deepcopy(p)
1-element Vector{Any}:
1-element Vector{Any}:#= circular reference @-1 =#

julia> p === p[1]
true

julia> p2 === p2[1]
true

which is what I had expected. On 1.11.2 I see

julia> function make_circular_reference_array()
           p = Any[nothing]
           p[1] = p
           return p
       end
make_circular_reference_array (generic function with 1 method)

julia> p = make_circular_reference_array()
1-element Vector{Any}:
 1-element Vector{Any}:#= circular reference @-1 =#

julia> p2 = deepcopy(p)
1-element Vector{Any}:
 Any[Any[#= circular reference @-1 =#]]

julia> p === p[1]
true

julia> p2 === p2[1]
false

[bbrehm]

Good reproducer @willtebbutt !
The issue is in

julia/base/deepcopy.jl

Line 127 in 083b24e

stackdict[x] = $(Expr(:new, :(Array{T, N}), :(deepcopy_internal(x.ref, stackdict)), :(x.size)))

from commit 909bcea

The deepcopy_internal construction should register the new copied item in the stackdict before recursing to the children. Failing that, we need to check again when ascending from the stack. So the fix is

julia> @eval Base begin
       function deepcopy_internal(x::Array{T, N}, stackdict::IdDict) where {T, N}
           if haskey(stackdict, x)
               return stackdict[x]::typeof(x)
           end
           copied = $(Expr(:new, :(Array{T, N}), :(deepcopy_internal(x.ref, stackdict)), :(x.size)))
           #we need to check again, in case that we just recursed back to x
           get!(stackdict, x, copied)::typeof(x)
           end
           end

[willtebbutt]

Thanks for figuring this out @bbrehm -- are you interested in turning this fix into a PR?