MutableLinkedList append! iterating infinitely

[synthfi]

When I run the following segment of code:

julia> using DataStructures
julia> a = MutableLinkedList{Int}(1,2,3)
MutableLinkedList{Int64}(1, 2, 3)
julia> b = MutableLinkedList{Int}(3,4,5)
MutableLinkedList{Int64}(3, 4, 5)
julia> append!(a, b)

This seemingly infinite object gets printed to my screen:

MutableLinkedList{Int64}(1, 2, 3, 3, 4, 5, 0, 3, 4, 5, 0, 3, 4, 5, 0, 3, 4, 5, ... # the 0,3,4,5 repeats endlessly until I hit Ctrl-C

length(a) gives me the correct size of 6 though. I also tried running collect(a) and that seg-faulted my Julia REPL. Am I just stupid and missed something completely obvious here?

I'm running on macOS with DataStructures v0.18.9.

Edit: still seeing this with v0.19-DEV in WSL2 Ubuntu:

julia> using DataStructures

julia> l1, l2 = MutableLinkedList{Int}(1,2), MutableLinkedList{Int}(3,4)
(MutableLinkedList{Int64}(1, 2), MutableLinkedList{Int64}(3, 4))

julia> append!(l1, l2)
MutableLinkedList{Int64}(1, 2, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4, 0, 3, 4,
# this continues endlessly, I have to hit Ctrl-C

when I enter collect(l1)

julia> collect(l1)

[8693] signal (11.1): Segmentation fault
in expression starting at none:0
jl_object_id__cold at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/builtins.c:417
immut_id_ at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/builtins.c:376
type_hash at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1332
typekey_hash at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1344
jl_precompute_memoized_dt at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1409
inst_datatype_inner at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1731
inst_type_w_ at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:2000
ijl_instantiate_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1216
rename_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:510
unalias_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:774 [inlined]
subtype_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:785
subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1257
subtype_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:800
subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1254
subtype_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:800
subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1254
exists_subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1442 [inlined]
_forall_exists_subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1474
forall_exists_subtype at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:1490 [inlined]
ijl_types_equal at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/subtype.c:2046
inst_datatype_inner at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1601
inst_type_w_ at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:2000
ijl_instantiate_unionall at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1216
jl_inst_arg_tuple_type at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jltypes.c:1819
arg_type_tuple at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2100 [inlined]
jl_lookup_generic_ at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2884 [inlined]
ijl_apply_generic at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2936
#current_exceptions#81 at ./error.jl:157
current_exceptions at ./error.jl:150 [inlined]
current_exceptions at ./error.jl:150 [inlined]
eval_user_input at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:164
repl_backend_loop at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:249
#start_repl_backend#46 at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:234
start_repl_backend at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:231
_jl_invoke at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2940
#run_repl#59 at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:379
run_repl at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:365
jfptr_run_repl_59978.clone_1 at /home/kelly/julia-1.9.2/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2940
#1017 at ./client.jl:421
jfptr_YY.1017_37237.clone_1 at /home/kelly/julia-1.9.2/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2940
jl_apply at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/julia.h:1879 [inlined]
jl_f__call_latest at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/builtins.c:774
#invokelatest#2 at ./essentials.jl:816 [inlined]
invokelatest at ./essentials.jl:813 [inlined]
run_main_repl at ./client.jl:405
exec_options at ./client.jl:322
_start at ./client.jl:522
jfptr__start_43375.clone_1 at /home/kelly/julia-1.9.2/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/gf.c:2940
jl_apply at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/julia.h:1879 [inlined]
true_main at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jlapi.c:573
jl_repl_entrypoint at /cache/build/default-amdci5-2/julialang/julia-release-1-dot-9/src/jlapi.c:717
main at julia (unknown line)
unknown function (ip: 0x7f351a79bd8f)
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x401098)
Allocations: 3000 (Pool: 2988; Big: 12); GC: 0
Segmentation fault

[synthfi]

I tried fixing this issue on my windows machine by changing this function:

function Base.append!(l1::MutableLinkedList{T}, l2::MutableLinkedList{T}) where T
    l1.node.prev.next = l2.node.next # l1's last's next is now l2's first
    l2.node.prev.next = l1.node # l2's last's next is now l1.node
    l1.len += length(l2)
    return l1
end

to this:

function Base.append!(l1::MutableLinkedList{T}, l2::MutableLinkedList{T}) where T
    l1.node.prev.next = l2.node.next # l1's last's next is now l2's first
    l2.node.prev.next = l1.node  # l2's last's next is now l1.node
    l2.node.next.prev = l1.node.prev # l2's first's prev is now l1's last
    l1.node.prev      = l2.node.prev # l1's first's prev is now l2's last
    l1.len += length(l2)
    # make l2 empty
    l2.node.prev = l2.node
    l2.node.next = l2.node
    l2.len = 0
    return l1
end

It boils down to updating the prev references in the l1 elements and making l2 empty to make it clear that l1 took the elements (and also because otherwise printing the var passed as l2 afterwards did the endless print to the screen).

Does this seem like the right sort of fix? Here's an example on windows after the change:

julia> using DataStructures

julia> a = MutableLinkedList{Int}(1,2,3)
MutableLinkedList{Int64}(1, 2, 3)

julia> b = MutableLinkedList{Int}(4,5,6)
MutableLinkedList{Int64}(4, 5, 6)

julia> append!(a, b)
MutableLinkedList{Int64}(1, 2, 3, 4, 5, 6)

julia> b
MutableLinkedList{Int64}()

julia> collect(a)
6-element Vector{Int64}:
 1
 2
 3
 4
 5
 6

julia> collect(b)
Int64[]