Bug in OrderedDict (unlike in LittleDict, and Dict)

[PallHaraldsson]

Copied the test from Base, where with Dict is ok, here renamed to OrderedDict not:

using Tests
@testset "shallow and deep copying" begin
           a = Any[[1]]
           q = QuoteNode([1])
           ca = copy(a); dca = @inferred(deepcopy(a))
           @test ca !== a
           @test ca[1] === a[1]
           @test dca !== a
           @test dca[1] !== a[1]
           @test deepcopy(q).value !== q.value
       
           @test_throws ErrorException("deepcopy of Modules not supported") deepcopy(Base)
       
           # deepcopy recursive dicts
           x = OrderedDict{OrderedDict, Int}()
           x[x] = 0
           @test length(deepcopy(x)) == 1
       end

[PallHaraldsson]

The problematic line seems to be this one:

julia> x[x] = 0
ERROR: StackOverflowError:

but note, for either Dict or OrderedDict:

julia> x[x]
ERROR: KeyError: key OrderedDict{OrderedDict, Int64}() not found

so is the former for sure supposed to work?

[kmsquire]

The x[x] = 0 line is supposed to "work" (i.e., not give a stack overflow), but it isn't exactly useful:

1. If you mutate a key in a way that changes its hash value, then the Dict / OrderedDict won't be able to find it again (it depends on the hash value being stable).
2. Even if there were a way around this, the hash function is recursive and doesn't detect cycles (that would be too expensive), so it's not possible to get a hash value for x after x[x] = 0:

   julia> d = Dict{Dict, Int}()
   Dict{Dict, Int64}()
   
   julia> d[d] = 0
   0
   
   julia> hash(d)
   ERROR: StackOverflowError:
   ...

I'll post a fix for the original issue shortly.