X10
  1. X10
  2. XTENLANG-2764

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

    Details

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

      Description

      The manual explains what should happen when an instantiation of a generic
      class makes method overloading ambiguous. This explanation
      ("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.

        Issue Links

          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
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated: