# Need to reconsider fine points of instantiating a generic type in a way that makes method overloading ambiguous

## Details

• Type: Bug
• Status: Open
• Priority: Critical
• Resolution: Unresolved
• Affects Version/s: X10 2.1.2
• Fix Version/s:
• Component/s:
• Labels:
None
• Number of attachments :
0

## Description

The manual explains what should happen when an instantiation of a generic
("complain-on-call"), while sensible, will require us to massively rework our
C++ back end implementation. So, Bard and Igor propose we switch to a somewhat
different approach, "complain-on-instantiation".

Both concepts concern ambiguous overloadings. If we have a type C[T] with
methods def m(x:T)=1; and def m(x:Int)=2;, then C[Int] has two
methods with the same signature.

"complain-on-call" says that it is illegal to use an ambiguous method. So
we could create an instance of C[Int], but not call it's m method.

"complain-on-instantiation" says that it is illegal to use a type with
ambiguous methods. So we can't even create an instance of C[Int].

• Complain-on-instantiation is more restrictive than complain-on-call. So, if
we make this change in 2.2, we can go to complain-on-call later if we want
to.
• But it's not much more restrictive. Bard hasn't, as of the time of
writing, come up with any plausible example where complain-on-call allows
something sensible but complain-on-instantiation doesn't.
• Complain-on-instantiation can be checked in the front end, which ought to be
easier and less troublesome than the back-end matters that complain-on-call
requires.

(The original motivation for complain-on-call is worth mentioning here.
Originally Bard had written something far more restrictive in the spec –
something that was restrictive enough to exclude some vaguely useful cases.
When this was pointed out, Bard went to the other extreme, of allowing as many
calls as possible. This decision was discussed very casually, but nobody
thought deeply about it until now. In particular, the material in the spec as
of today is not there because anyone needs that behavior in particular, or
because we have any reason to think it is right – it simply seemed like a
good idea at the time. So making this change is unlikely to have much
software-engineering impact.)

Here's what the spec says now. This is complain-on-call:

A class definition may include methods which are ambiguous in some
generic instantiation. (It is a compile-time error if the methods are
ambiguous in every generic instantiation, but excluding class
definitions which are are ambiguous in some instantiation would exclude
useful cases.) It is a compile-time error to use an ambiguous method
call.

The following class definition is acceptable. However, the marked method
calls are ambiguous, and hence not acceptable.

package Classes4d5e;
class Two[T,U]{
def m(x:T)=1;
def m(x:Int)=2;
def m[X](x:X)=3;
def m(x:U)=4;
static def example() {
val t12 = new Two[Int, Any]();
// ERROR: t12.m(2);
val t13  = new Two[String, Any]();
t13.m("ferret");
val t14 = new Two[Boolean,Boolean]();
// ERROR: t14.m(true);
}
}


The call t12.m(2) could refer to either the 1 or 2
definition of m, so it is not allowed.
The call t14.m(true) could refer to either the 1 or 4
definition, so it, too, is not allowed.

The call t13.m("ferret") refers only to the 1 definition. If
the 1 definition were absent, type argument inference would make it
refer to the 3 definition. However, X10 will choose a fully-specified
call if there is one, before trying type inference, so this call unambiguously
refers to 1.
\end

Unknown macro: {ex}

This test case has been failing for a while.

Under the proposed new rules, the types Two[Int,Any] and
Two[Boolean,Boolean] will become illegal. The errors will be caught at the
val t12 and val t14 lines. Two[String,Any] will remain legal.

## Activity

Hide
Bard Bloom added a comment -

bard_todo

Show
Bard Bloom added a comment - bard_todo
Hide
Yoav Zibin added a comment -

How will you type-check this:

class A[T]{
def m(T)=1;
def m(Int)=2;
static def example() {
val t = new A[Int](); // you want this to be illegal, because t.m(1) is problematic
example2[Int]();
}
static def example2[U]() {
val t = new A[U](); // is this legal? will it cause a similar problem in the C++ backend?
// t.m(1) is not problematic here because we resolve it to m(Int)=2
}
}

Show
Yoav Zibin added a comment - How will you type-check this: class A[T]{ def m(T)=1; def m(Int)=2; static def example() { val t = new A[Int](); // you want this to be illegal, because t.m(1) is problematic example2[Int](); } static def example2[U]() { val t = new A[U](); // is this legal? will it cause a similar problem in the C++ backend? // t.m(1) is not problematic here because we resolve it to m(Int)=2 } }
Hide
Igor Peshansky added a comment -

For every class, we can build a list of problem instantiations (as a pseudo type constraint in terms of the type parameters, so we can catch overloading ambiguities between type parameters). Whenever classes or methods instantiate generic types based on their type parameters, they will inherit these restrictions on their type arguments as well. In this case, the error would be reported on both new A[Int]() and example2[Int]() — the first because of the direct conflict, and the second because example2() will inherit the restriction base(U)!=Int.

Show
Igor Peshansky added a comment - For every class, we can build a list of problem instantiations (as a pseudo type constraint in terms of the type parameters, so we can catch overloading ambiguities between type parameters). Whenever classes or methods instantiate generic types based on their type parameters, they will inherit these restrictions on their type arguments as well. In this case, the error would be reported on both new A[Int]() and example2[Int]() — the first because of the direct conflict, and the second because example2() will inherit the restriction base(U)!=Int .
Hide
David Grove added a comment -

bulk defer of open issues to 2.2.2.

Show
David Grove added a comment - bulk defer of open issues to 2.2.2.
Hide
Vijay Saraswat added a comment -

Dave, Igor: this jira is silent on why "complain-on-call" is problematic for the C++ backend.

Is it?

What are the problems?

(Bard – I dont understand your comment "Complain-on-instantiation can be checked in the front end, which ought to be easier and less troublesome than the back-end matters that complain-on-call requires." Both can be checked in the front end.)

Show
Vijay Saraswat added a comment - Dave, Igor: this jira is silent on why "complain-on-call" is problematic for the C++ backend. Is it? What are the problems? (Bard – I dont understand your comment "Complain-on-instantiation can be checked in the front end, which ought to be easier and less troublesome than the back-end matters that complain-on-call requires." Both can be checked in the front end.)
Hide
David Grove added a comment -

I believe the issue is that when you instantiate a templatized C++ class, you have to instantiate all of its instance methods so the vtable can be filled in. If a particular instantiation of the class results in ambiguous methods, it doesn't matter whether or not the program actually ever calls them; the post compiler will reject the instantiation because it isn't valid C++.

We don't have this problem for static methods, since they get instantiated on a per-method basis (no vtable).

My recollection is that to support complain-on-call for instance methods we would need to give up on using the C++ object model to implement instance methods, and I don't see this as being a viable option.

Show
David Grove added a comment - I believe the issue is that when you instantiate a templatized C++ class, you have to instantiate all of its instance methods so the vtable can be filled in. If a particular instantiation of the class results in ambiguous methods, it doesn't matter whether or not the program actually ever calls them; the post compiler will reject the instantiation because it isn't valid C++. We don't have this problem for static methods, since they get instantiated on a per-method basis (no vtable). My recollection is that to support complain-on-call for instance methods we would need to give up on using the C++ object model to implement instance methods, and I don't see this as being a viable option.
Hide
Vijay Saraswat added a comment -

I see. I agree that giving up the C++ object model is not a viable option.

Will the following definition suffice to rule out such C++ post-compilation errors? Recall that a unit is a class, struct or interface.

A unit definition U may include method definitions which are ambiguous for some choice of types for its type parameters. It is an error for a unit type to be such that all its instantiations have ambiguous members.

(Here, of course, we consider a type T to be an instance of T if T has no type parameters.)

This definition would mark Foo[S, T] as an error if it is defined thus:

class Foo[S,T]{S==T} {
def m(S):void{}
def m(T):void{}
}

Show
Vijay Saraswat added a comment - I see. I agree that giving up the C++ object model is not a viable option. Will the following definition suffice to rule out such C++ post-compilation errors? Recall that a unit is a class, struct or interface. A unit definition U may include method definitions which are ambiguous for some choice of types for its type parameters. It is an error for a unit type to be such that all its instantiations have ambiguous members. (Here, of course, we consider a type T to be an instance of T if T has no type parameters.) This definition would mark Foo[S, T] as an error if it is defined thus: class Foo[S,T]{S==T} { def m(S):void{} def m(T):void{} }
Hide
Vijay Saraswat added a comment -

Igor –

Have you thought through the design of the type constraints necessary (cf your message of May 29, 2011). This needs to be worked out carefully.

Show
Vijay Saraswat added a comment - Igor – Have you thought through the design of the type constraints necessary (cf your message of May 29, 2011). This needs to be worked out carefully.
Hide
David Grove added a comment - - edited

To make it concrete, here's an example of an X10 program that can't be supported with the current C++ codegen strategy. So, ideally we would reject this in the front end. The most precise checking of this would allow the call to trouble[Int,Double]() but reject the call to trouble[Int,Int]().

class Foo[S,T] {
def m(S):void{ Console.OUT.println("S's m"); }
def m(T):void{ Console.OUT.println("T's m"); }
}

public class GenericFun {
public static def trouble[A,B]() = new Foo[A,B]();

public static def main(Array[String]) {
// this is ok
trouble[Int,Double]();

// this is not ok.
//
// Generated C++ code fails postcompilation because Foo[Int,Int]
//   has two identical methods.
// Does not matter that the methods are never called,
// C++ needs to instantiate them to put them in the vtable.
trouble[Int,Int]();
}
}


The C++ level error when this class is compiled is as expected:

x10c++: In file included from GenericFun.cc:3:
/home/dgrove/x10-trunk/myTests/Foo.h: In instantiation of ‘Foo<int, int>’:
/home/dgrove/x10-trunk/myTests/GenericFun.h:71: instantiated from ‘static x10aux::ref<Foo<x10tp__S, x10tp__T> > GenericFun::trouble() [with x10tp__A = int, x10tp__B = int]’
GenericFun.cc:23: instantiated from here
/home/dgrove/x10-trunk/myTests/Foo.h:77: error: ‘void Foo<x10tp__S, x10tp__T>::m(x10tp__T) [with x10tp__S = int, x10tp__T = int]’ cannot be overloaded
/home/dgrove/x10-trunk/myTests/Foo.h:69: error: with ‘void Foo<x10tp__S, x10tp__T>::m(x10tp__S) [with x10tp__S = int, x10tp__T = int]’


This simple case could be caught by analyzing Foo and having the compiler add the constraint S!=T to the class invariants. One can also construct variations like:

class Foo[S,T] {
def m(S):void{ Console.OUT.println("S's m"); }
def m(T):void{ Console.OUT.println("T's m"); }
def m(Complex):void { ... }
}


So you would need S!=T and S!=Complex and T!=Complex in the class invariants.

It might be possible for the typechecker to formulate all the necessary constraints by looking at overloaded virtual methods that have type parameters as arguments. I haven't worked out the details (and they may be too complex to make it practical), but I think that is probably the only solution that will catch all potential post-compilation errors at X10 compile time and safely allow overloading of instance methods whose formal types include a type parameter of the class.

Show
David Grove added a comment - - edited To make it concrete, here's an example of an X10 program that can't be supported with the current C++ codegen strategy. So, ideally we would reject this in the front end. The most precise checking of this would allow the call to trouble [Int,Double] () but reject the call to trouble [Int,Int] (). class Foo[S,T] { def m(S):void{ Console.OUT.println( "S's m" ); } def m(T):void{ Console.OUT.println( "T's m" ); } } public class GenericFun { public static def trouble[A,B]() = new Foo[A,B](); public static def main(Array[ String ]) { // this is ok trouble[Int, Double ](); // this is not ok. // // Generated C++ code fails postcompilation because Foo[Int,Int] // has two identical methods. // Does not matter that the methods are never called, // C++ needs to instantiate them to put them in the vtable. trouble[Int,Int](); } } The C++ level error when this class is compiled is as expected: x10c++: In file included from GenericFun.cc:3: /home/dgrove/x10-trunk/myTests/Foo.h: In instantiation of ‘Foo< int , int >’: /home/dgrove/x10-trunk/myTests/GenericFun.h:71: instantiated from ‘ static x10aux::ref<Foo<x10tp__S, x10tp__T> > GenericFun::trouble() [with x10tp__A = int , x10tp__B = int ]’ GenericFun.cc:23: instantiated from here /home/dgrove/x10-trunk/myTests/Foo.h:77: error: ‘void Foo<x10tp__S, x10tp__T>::m(x10tp__T) [with x10tp__S = int , x10tp__T = int ]’ cannot be overloaded /home/dgrove/x10-trunk/myTests/Foo.h:69: error: with ‘void Foo<x10tp__S, x10tp__T>::m(x10tp__S) [with x10tp__S = int , x10tp__T = int ]’ This simple case could be caught by analyzing Foo and having the compiler add the constraint S!=T to the class invariants. One can also construct variations like: class Foo[S,T] { def m(S):void{ Console.OUT.println( "S's m" ); } def m(T):void{ Console.OUT.println( "T's m" ); } def m(Complex):void { ... } } So you would need S!=T and S!=Complex and T!=Complex in the class invariants. It might be possible for the typechecker to formulate all the necessary constraints by looking at overloaded virtual methods that have type parameters as arguments. I haven't worked out the details (and they may be too complex to make it practical), but I think that is probably the only solution that will catch all potential post-compilation errors at X10 compile time and safely allow overloading of instance methods whose formal types include a type parameter of the class.
Hide
Igor Peshansky added a comment -

So you would need S!=T and S!=Complex and T!=Complex in the class invariants.

Actually, that is not enough. Because constraints are stripped away, you would need to express (S!=T)mod constraints. Last year I proposed both the != operation for types, and the RawType operator (or whatever name we choose to give it). I also proposed a CanBeOverloaded predicate on two types, with essentially the above motivating example. Both were rejected.

Show
Igor Peshansky added a comment - So you would need S!=T and S!=Complex and T!=Complex in the class invariants. Actually, that is not enough. Because constraints are stripped away, you would need to express (S!=T) mod constraints . Last year I proposed both the != operation for types, and the RawType operator (or whatever name we choose to give it). I also proposed a CanBeOverloaded predicate on two types, with essentially the above motivating example. Both were rejected.
Hide
David Grove added a comment -

bulk defer of issues to 2.2.3.

Show
David Grove added a comment - bulk defer of issues to 2.2.3.
Hide
David Grove added a comment -

bulk defer of 2.3.0 open issues to 2.3.1.

Show
David Grove added a comment - bulk defer of 2.3.0 open issues to 2.3.1.
Hide
David Grove added a comment -

bulk defer to 2.3.2

Show
David Grove added a comment - bulk defer to 2.3.2
Hide
David Grove added a comment -

bulk defer to 2.4.1.

Show
David Grove added a comment - bulk defer to 2.4.1.
Hide
David Grove added a comment -

By default, targeting all language design issues at next major release (X10 2.5) or later.

Show
David Grove added a comment - By default, targeting all language design issues at next major release (X10 2.5) or later.
Hide
David Grove added a comment -

bulk defer features from X10 2.5 to X10 2.6.

Show
David Grove added a comment - bulk defer features from X10 2.5 to X10 2.6.

## People

• Assignee:
Vijay Saraswat
Reporter:
Bard Bloom