Julia gets stuck on recursive function

I defined the following merge function for a custom Dict type:

struct MixedKeyDict{T<:Tuple} #<: AbstractDict{Any,Any}

Base.merge(f::Function, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)
Base.merge(f, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)

function _merge(f, res, d, others...)
    ofsametype, remaining = _alloftype(Base.heads(d), ((),), others...)
    return _merge(f, (res..., merge(f, ofsametype...)), Base.tail(d), remaining...)

_merge(f, res, ::Tuple{}, others...) = _merge(f, res, others...)
_merge(f, res, d) = MixedKeyDict((res..., d...))
_merge(f, res, ::Tuple{}) = MixedKeyDict(res)

function _alloftype(ofdesiredtype::Tuple{Vararg{D}}, accumulated, d::Tuple{D,Vararg}, others...) where D
    return _alloftype((ofdesiredtype..., first(d)),
                      (Base.front(accumulated)..., (last(accumulated)..., Base.tail(d)...), ()),

function _alloftype(ofdesiredtype, accumulated, d, others...)
    return _alloftype(ofdesiredtype,
                      (Base.front(accumulated)..., (last(accumulated)..., first(d))),
                      Base.tail(d), others...)

function _alloftype(ofdesiredtype, accumulated, ::Tuple{}, others...)
    return _alloftype(ofdesiredtype,
                      (accumulated..., ()),

_alloftype(ofdesiredtype, accumulated) = ofdesiredtype, Base.front(accumulated)

For two dicts, this works perfectly well:

julia> d = MixedKeyDict((Dict(1=>3),Dict(4. => 2)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  1   => 3
  4.0 => 2

julia> e = MixedKeyDict((Dict(1=>7),Dict(5. => 9)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  1   => 7
  5.0 => 9

julia> merge(+, d, e)
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 3 entries:
  1   => 10
  4.0 => 2
  5.0 => 9

But as soon as I add another one, Julia gets completely stuck and I have to kill the whole process.

julia> f = MixedKeyDict((Dict(2=>7),Dict(5. => 9)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  2   => 7
  5.0 => 9

julia> merge(+, d, e, f) #gets stuck

I thought there might be a bug in my code, so I tried debugging it with Debugger.jl, but the weird part is,that it works just fine if I just @enter the function and let it continue without any breakpoints set:

julia> using Debugger

julia> @enter merge(+, d, e, f)
In merge(f, d, others) at /home/simeon/Documents/Julia/TypeStableDicts/src/TypeStableDicts.jl:33
>33  Base.merge(f::Function, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)

About to run: (getproperty)(<suppressed 71 bytes of output>, :dicts)
1|debug> c
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 4 entries:
  2   => 7
  1   => 10
  4.0 => 2
  5.0 => 18

If I tell Debugger.jl to use the compiled mode, it gets stuck again. This seems to be a bug in the compiler. Is this a known bug – should I open an issue? Are there any workarounds for this to work?

My Julia version:

julia> versioninfo()
Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

I’ve also tried it with the latest nightly, but no luck there either.

for what i’m looking, every pair(key,value) its is own dict, and you want a struct that allows binary operations on merge, thats correct? have you considered storing directly the pairs (key,value) as NTuples?

That’s just a simplification for testing purposes. The goal is to allow for type stable dicts with different key types, which are efficient if there are a lot more items than different key types.

but the part about the operation is still true? what i understand about your merge, is that also does a reduce over the variables of the same key, that is correct?

It works exactly the same as merge with a combine function on regular dicts, so it calls f on all items with the same keys.

have you tried IdDicts? those are dicts that check the value and the type (=== comparison), so IdDict[4]!=IdDIct[4.0], a demonstration:

x1 = IdDict{Any,Real}(
    "I'm a string" => 123,

x2 = IdDict{Any,Real}(
    "I'm other string" => 123,

x3 = IdDict{Any,Real}(
    "I'm  THE string" => 123,


IdDict{Any,Real} with 5 entries:
  "I'm a string"     => 123
  4.0                => 0
  "I'm other string" => 123
  'c'                => 6.0
  4                  => 0

IdDict{Any,Real} with 6 entries:
  "I'm a string"     => 123
  4.0                => 1
  "I'm other string" => 123
  'c'                => 9.0
  4                  => 1
  "I'm  THE string"  => 123

merge(+,x1,x2,x3) works too

The point is that the output type can be inferred only from the key type, which IdDict doesn’t allow. It also returns just a regular Dict when merging IdDicts. My example shouldn’t be thought to be representative of the actual usecase, it’s just do demonstrate the issue I ran into. My question was why this code example gets stuck, when it clearly should work, as described above.

yes, you are right, it is an issue, maybe file an issue on github?

That would be my next step. I just thought this might be related to an already opened issue and thought people might have additional input before I opened an issue.

1 Like

If the debugger (or rather the interpreter) and standard julia execution gives different answers, one of them has a bug. And while the interpreter is quite new it does very little fancy stuff so it could be that there is a bug in julia here from one of the different optimizations julia runs.

How would I then go about tracking down this particular issues? Are there tools to help with that? I’m not really familiar with Julia internals, so should I rather just open an issue on Github with this particular code example?

Yup, opening an issue on the Julia github repo seems totally reasonable.