Stack overflow from unexpected mutual constructor recursion on type alias


#1

Define

using DataStructures
const Bar = OrderedDict{Int64, Int64}
Bar() = Bar(1=>2, 2=>3)

Then calling Bar() gets me

**ERROR:** StackOverflowError:
Stacktrace:
 [1] **OrderedDict{Int64,Int64}()** at **./REPL[3]:1**
 [2] **OrderedDict{Int64,Int64}(** ::Pair{Int64,Int64}, ::Vararg{Pair{Int64,Int64},N} where N **)** at **/Users/andyjones/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:28**
 ... (the last 2 lines are repeated 39998 more times)
 [79999] **OrderedDict{Int64,Int64}()** at **./REPL[3]:1**

For reference, OrderedDict's implementation is here, and the relevant constructor is

function OrderedDict{K,V}(kv) where {K,V}
    h = OrderedDict{K,V}()
    # etc
end 

What’s happening here is that Bar() calls OrderedConstructor(kv) calls Bar() calls OrderedConstructor(kv), etc.

What I expected to happen is that Bar() calls OrderedConstructor(kv) calls OrderedConstructor(). I seem to have overridden OrderedConstructor() by defining the type alias, which is a surprise - I’d expect to have to define DataStructures.OrderedConstructor() = xyz to do that, going by this table.

So, two questions:

  • Which part of the documentation do I need to read more carefully to understand why this is happening?
  • How’d I get my expected behaviour? I’d ideally like to keep the names Bar and Bar().

Thanks!


#2

It looks like there is a difference between exported types and functions.

Extending a type constructor seems to work (and is indeed what happens in your case):

julia> using DataStructures

julia> methods(OrderedDict)
# 14 methods for generic function "(::Type)":
[1] (::Type{OrderedDict})() in OrderedCollections at /home/francois/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:43
[2] (::Type{OrderedDict})(kv::Tuple{}) in OrderedCollections at /home/francois/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:44
[3] (::Type{OrderedDict})(kv::Tuple{Vararg{Pair{K,V},N} where N}) where {K, V} in OrderedCollections at /home/francois/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:52                                                                                                                                                             
...

julia> OrderedDict() = "OK"
OrderedDict

julia> methods(OrderedDict)
# 14 methods for generic function "(::Type)":
[1] (::Type{OrderedDict})() in Main at REPL[3]:1
[2] (::Type{OrderedDict})(kv::Tuple{}) in OrderedCollections at /home/francois/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:44
[3] (::Type{OrderedDict})(kv::Tuple{Vararg{Pair{K,V},N} where N}) where {K, V} in OrderedCollections at /home/francois/.julia/packages/OrderedCollections/Pr9Pa/src/ordered_dict.jl:52
....

whereas extending functions does not work (as expected):

julia> methods(complement)
# 1 method for generic function "complement":
[1] complement(s::DataStructures.IntSet) in DataStructures at /home/francois/.julia/packages/DataStructures/6r6kb/src/int_set.jl:199

julia> complement() = "error"
ERROR: error in method definition: function DataStructures.complement must be explicitly imported to be extended
Stacktrace:
 [1] top-level scope at none:0

When looking at the documentation for modules, I found hints that the restriction forbidding methods extension might apply only to functions (maybe this means: “as opposed to type constructors”). For example (emphasis mine):

The statement using BigLib: thing1, thing2 brings just the identifiers thing1 and thing2 into scope from module BigLib . If these names refer to functions, adding methods to them will not be allowed (you may only “use” them, not extend them).

So I’m not sure if this difference is to be expected, but if it is, the documentation could perhaps be made more explicit.


#3

By doing const Bar = OrderedDict{Int64, Int64}, your Bar is OrderedDict{Int64, Int64}. They are now just two names for the exact same thing, so when you add a method to Bar you’re also adding a method to OrderedDict{Int, Int}. I do agree that it’s a bit confusing that this is possible for types, while achieving the same result with a function would require you to import it.

As to your question, I don’t think it’s possible to do exactly what you’re asking for, for the precise reason you’ve found. Perhaps if you can give more context it will be easier to come up with a solution to the problem you’re actually trying to solve in your code.

By the way, the reason that you’re seeing a change in the behavior of the ordereddict constructor is that your Bar() method definition is an example of “type piracy”. You’re defining a method of a function you don’t own (the ordereddict constructor) on arguments you don’t own (an empty argument list). We specifically discourage type piracy because it can cause errors at a distance just like what you’ve run into.


#4

Both of your replies are really helpful, thanks!

is an example of “type piracy”.

Bingo, that’s the Googlable phrase I was looking for. I’m still surprised that - as @ffevotte points out - I can add a method to the imported constructor without error, but adding a method to an imported function will raise an error. Are (outer) constructors special-cased in some way? So far I’ve assumed they’re just another method.

Perhaps if you can give more context it will be easier to come up with a solution to the problem you’re actually trying to solve in your code.

I’m after a way to pass a list of functions around, keyed by some identifier and (indirectly) by their insertion order. Specifically, I’d like

  • A type Actions that behaves exactly like OrderedDict{Symbol, Function}. Aliasing it like this makes a lot of function declarations more readable.
  • I’d like the default instantiation to be Actions(:f=>forward, :b=>backward). I’d like this because in the context of the program I’m writing, it’s what you’d expect Actions to contain - an empty Actions would be surprising.
  • I’d like to keep the idiom that to get the default instantiation of an object, you call the empty constructor Actions().

Having written that out I see the fundamental conflict - I want something that’s exactly like OrderedDict, but that isn’t like it in how it’s constructors are defined. If the constructors are part of the type (?), rather than just some random methods lying around, then replacing the constructors makes it not exactly like it.


#5

Couldn’t you just use an ordinary method to construct your OrderedDict:

julia> using OrderedCollections

julia> Bar() = OrderedDict(1=>2, 2=>3)
Bar (generic function with 1 method)

julia> Bar()
OrderedDict{Int64,Int64} with 2 entries:
  1 => 2
  2 => 3

?


#6

I can if I don’t have the type alias const Bar = OrderedDict{Int64, Int64}! But that’s a core part of what I’m after, because it’s much nicer to write foo(bar::Bar) than foo(bar::OrderedDict{Int64, Int64}).

If I do have the type alias, then Bar() pirates OrderedDict() and I get an infinite recursion.


#7

I wonder if you could name it something else then — eg bar.


#8

Yep, that’s the simplest solution. But it breaks the idiom that when you want a default Foo you call Foo(). Possibly unavoidable from what everyone here has said, but a bit annoying.


#9

You can also make Bar a thin wrapper of OrderedDict:

struct Foo{T <: OrderedDict}
    dict::T
end

# and then forward the methods to dict

IMO a function the creates a special/specifc value of T should not need to be called T — eg eps() is not called Float64.