Julia gets stuck on recursive function

General Usage
1

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

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

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...)
end

_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)...), ()),
                      others...)
end

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

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

_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
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

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

2

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?

3

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.

4

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?

5

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.

6

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,
    'c'=>3.0,
    4=>2,
    4.0=>3)

x2 = IdDict{Any,Real}(
    "I'm other string" => 123,
    'c'=>3.0,
    4=>-2,
    4.0=>-3
)

x3 = IdDict{Any,Real}(
    "I'm  THE string" => 123,
    'd'=>3.0,
    4=>1,
    4.0=>1
)


merge!(+,x1,x2,x3)

julia>merge!(+,x1,x2)
IdDict{Any,Real} with 5 entries:
  "I'm a string"     => 123
  4.0                => 0
  "I'm other string" => 123
  'c'                => 6.0
  4                  => 0

merge!(+,x1,x2,x3)
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

7

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.

8

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

9

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
10

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.

11

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?

12

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