Incorrect overload selected for Array(Array(T)) vs Array(T) #8973
Comments
asterite
added
kind:bug
|
Without the dependency on class Gen(T)
end
def foo(a : Gen(T)) forall T
puts "one"
end
def foo(a)
puts "two"
end
z = Gen(Int32).new.as(Gen(Gen(Int32)) | Gen(Int32))
foo(z) |
|
Not sure if it's relevant, but the bug appears inconsistent.
|
|
I'm not enough of a mathematician to do this correctly, but bear with me. If any of that makes sense and is factual, the compiler's actions are surprising but correct. The expected output would only be possible if the compiler waits to define the unit type T until all possible recursion is done. |
|
It might be a correct guess but there's no recursion going on. It works wrong because we have a bug in our code. |
|
Recursion might be the wrong term for the algorithm process, but it does seem to have something to do with the recursive union type. |
|
Doing some old-fashioned puts debugging in the compiler and discovered this when I ran it against @stevensonmt's example code:
|
|
Interesting bug, if I try this: https://carc.in/#/r/8t59 def foo(a : Array(T)) forall T
a.each_with_index do |a, i|
p "first call for #{a} of class #{a.class}"
foo(a)
end
end
def foo(a : Array(Array(Int32)))
a.each_with_index do |a, i|
p "first call for #{a} of class #{a.class}"
foo(a)
end
end
def foo(a : T) forall T
p "second call for #{a} of class #{a.class}"
p a
end
foo([1, [2, [[3]], [4, [[5]]]]])Then I get this: |
|
Looks like the bug is somewhere in this file. Haven't found it yet. I'll look some more after work today. |
|
The problem is that this is a bug where the problem is not the code. We need to define how we want it to work first. Here's the code again: class Gen(T)
end
def foo(a : Gen(T)) forall T
puts "one"
end
def foo(a)
puts "two"
end
z = Gen(Int32).new.as(Gen(Gen(Int32)) | Gen(Int32))
foo(z)The type of
When the compiler tries to match that union type against
The only match is the first one, Then the next overload is considered, and the entire union matches. That's why we are seeing that behavior. How it should work? Should We basically need to dispatch the union type to two different instantiations of the same overload. But the code never does that in any place of the compiler. So this is a huge change, if we want to implement it. Or... other ideas of how this should match? |
|
This makes me question whether I understand def foo(a : T) forall T
end
foo [1, "b"].firstIn this example, it seems that there would be 2 overloads for |
|
@jgaskins there is just one, for the union type. It works exactly the same way without |
|
Exactly. That said, in my mind Another thing to consider: class Gen(T)
end
def foo(a : Gen(T)) forall T
p T
end
foo(Gen(Int32).new || Gen(Char).new)Currently fails: It's because The entire situation is very confusing. My advice is to avoid using |
Thanks for the clear delineation of the problem. I never expected to uncover such a fundamental bug. How important is this corner case? |
There's lucky framework, amber, athena and thousand of shards out there. We have a compiler. There's the standard library with a lot of features. It's a bug but it's not preventing people from creating wonderful things. I think this is a very low priority bug. It's pretty rare to have to match against |
Ahh, okay, similar to the idea of |
If we dispatch here, the same can be said about a plain free var restriction: def foo(x : T) forall T
p T
end
foo(1 || 'a') # => Int32
foo('a' || 1) # => Charas dynamic dispatch would generate separate overloads for def foo(x : T) forall T
[x]
end
# without dynamic dispatch:
foo(1 || 'a').class # => Array(Char | Int32)
foo('a' || 1).class # => Array(Char | Int32)
typeof(foo(1 || 'a')) # => Array(Char | Int32)
typeof(foo('a' || 1)) # => Array(Char | Int32)
# with dynamic dispatch:
foo(1 || 'a').class # => Array(Int32)
foo('a' || 1).class # => Array(Char)
typeof(foo(1 || 'a')) # => (Array(Char) | Array(Int32))
typeof(foo('a' || 1)) # => (Array(Char) | Array(Int32))So I am inclined towards not allowing dynamic dispatch here; when one writes class Gen(T)
end
def foo_impl(a : Gen(T)) forall T
p T
end
def foo(x : T) forall T
{% begin %}
case x
{% for t in T.union_types %}
in {{ t }} then foo_impl(x)
{% end %}
end
{% end %}
end
foo(Gen(Int32).new || Gen(Char).new) # => Int32
foo(Gen(Char).new || Gen(Int32).new) # => Char
foo(1) # Error: no overload matches 'foo_impl' with type Int32Perhaps we could extract this idiom into a pseudo-method. A regular method probably wouldn't work; if we replace |
|
Great analysis, thank you! And I agree with you. |
|
This issue is probably the same as mine, which does not involve generics: record Child, str : String = "bar"
record Parent, str : String = "foo", nested : Child = Child.new
def serialize(obj : T, de_unionize = false) forall T
String.build do |io|
each_ivar obj do |ivar|
io << (de_unionize ? de_unionize(ivar) : serialize(ivar))
end
end
end
def serialize(str : String)
str
end
def each_ivar(object : O, &) forall O
{% for ivar in O.instance_vars %}
yield object.@{{ivar}}
{% end %}
end
def de_unionize(object : U) forall U
{% for u in U.union_types %}
return serialize object if object.is_a? {{u}}
{% end %}
end
p serialize Parent.new # => "foo"
p serialize Parent.new, de_unionize: true # => "foobar"As @HertzDevil suggested, I did have to implement a method to de-unionize. |
|
So if |
|
There is also the following: def foo(x : Array(Array(T))) forall T
puts "1, #{T}"
end
def foo(x : Array(T)) forall T
puts "2, #{T}"
end
def foo(x : T) forall T
puts "3, #{T}"
end
foo([[1]] || [1]) # => 1, Int32
foo([1] || [[1]]) # => 3, (Array(Array(Int32)) | Array(Int32))If we follow the no dispatches approach, both calls should print 3, because def foo(x : Array(Array(Int32)))
puts "1, #{Int32}"
end
def foo(x : Array(T)) forall T
puts "2, #{T}"
end
foo([[1]] || [1]) # Error: no overload matches 'foo' with type (Array(Array(Int32)) | Array(Int32))
foo([1] || [[1]]) # Error: no overload matches 'foo' with type (Array(Array(Int32)) | Array(Int32))then the calls should print 1 and 2 respectively; that is, we still want to perform union dispatch in the same way the following is supported: def foo(x : Array(Array(Int32)) | Array(T)) forall T
puts "#{x}, #{T}"
end
foo([1] || [[1]]) # [1], Int32
foo([[1]] || [1]) # [[1]], Int32 |
|
We could perform dispatch over free variables only when the usual unification fails. More specifically, suppose we have: def foo(x : Array(T), y : Array(T)) forall T
endIf a type like def foo(
x : Array(T_11) | Array(T_12) | Array(T_13) | ... ,
y : Array(T_21) | Array(T_22) | Array(T_23) | ...
) forall T_ij...
endThese # T_1* = {Int32}
# T_2* = {Int32}
# T = {Int32}
foo([1], [1]) # note that normal unification should also succeed here
# T_1* = {Int32, String}
# T_2* = {Int32, String}
# T = {Int32, String}
# missing overloads for `foo([1], [""])` and `foo([""], [1])`
foo([1] || [""], [1] || [""])
# T_1* = {Int32, Char}
# T_2* = {Int32, String}
# T = {Int32}
# missing overloads for `foo([1], [""])`, `foo(['a'], [1])`, and `foo(['a'], [""])`
foo([1] || ['a'], [1] || [""])
# T_1* = {Int32 | String}
# T_2* = {String}
# T = ø
# missing overloads for everything
foo([1 || ""], [""])
def bar(x : Array(T), y : Array(U)) forall T, U
end
# T_1* = {Int32, String}
# U_1* = {Int32, String}
# T × U = {(Int32, Int32), (Int32, String), (String, Int32), (String, String)}
bar([1] || [""], [1] || [""])
# T_1* = {Int32 | String}
# U_1* = {String}
# T × U = {((Int32 | String), String)}
bar([1 || ""], [""])At this stage any bare free variable restrictions expand union types to their power sets: (a similar treatment could be done for def foo(x : T, y : Array(T)) forall T
end
# T_1* = {NoReturn, Int32}
# T_2* = {Int32 | String}
# T = ø
# missing overloads for everything
foo(1, [1 || ""])
# T_1* = {NoReturn, Int32, String, Int32 | String}
# T_2* = {Int32 | String}
# T = {Int32 | String}
foo(1 || "", [1 || ""])
# T_1* = {NoReturn, Int32, String, Int32 | String}
# T_2* = {Int32}
# T = {Int32}
# missing overloads for `foo("", [1])`
foo(1 || "", [1])These unions and power sets are only needed for a formal definition; the compiler probably won't create them. I would like to add that the following should unify normally for any pairs of argument types (it currently doesn't): def foo(x : T, y : T) forall T
T
end
foo(1, "") # => Int32 | StringThe standard library, to my knowledge, doesn't do this outside the |
|
Hm, I'm wondering if this would actually be correct. I would interpret On the other hand, you can also just cast both arguments to What's the point in restricting both arguments to the same type then, if any pair of types would be acceptable? |
|
Revisiting this issue and you're probably right that def foo(x : T, y : Array(T)) forall T
end
# T_1* = {Int32}
# T_2* = {Int32 | String}
# T = ø
# missing overloads for everything
foo(1, [1 || ""])
# T_1* = {Int32 | String}
# T_2* = {Int32 | String}
# T = {Int32 | String}
foo(1 || "", [1 || ""])
# T_1* = {Int32 | String}
# T_2* = {Int32}
# T = ø
# missing overloads for everything
foo(1 || "", [1])
# T_1* = {Int32 | String}
# T_2* = {Int32, String}
# T = ø
# missing overloads for everything
foo(1 || "", [1] || [""]) |
Prints "two" but should print "one". I'm still not exactly sure why this happens.
The text was updated successfully, but these errors were encountered: