generic method substitutions and unification

generic method substitutions and unification

Rate This
  • Comments 6

It's been a while since I've last written - my apologies. We've been hard at work figuring out what the next release of C# will look like, and I'm happy to say that I'm very excited about what we're working on. Great minds are at work figuring out things like integration of C# with the DLR, dynamic late binding, and better debugging experiences as we speak. Don't worry, I'll be sure to report to you about what they determine. :)

I'm always fascinated by discovering subtle details in the language that baffle me. Today I came across such a case. Consider the following code:

using System;

abstract class A<T>
{
    public abstract void Foo(T x);
}

abstract class B<T, S> : A<T>
{
    public virtual void Foo(S x){}
}

abstract class C<T, S> : B<T, S>
{
    public abstract override void Foo(T x);
}

class D : C<int, int>
{
    public override void Foo(int x) {}

    static void Main()
    {
        new D().Foo(1);
    }
}

What happens here?

Well, on the surface, this looks like it should be correct right? A's Foo and B's Foo are different, since they have different generic type parameters, and C clearly overrides A's Foo. But the weird part is D's Foo. Does it override A::Foo? Or B::Foo?

Well, it turns out that the specification outlines that when we look up members to override, we look from our current parent up - that is, when we find a method in one base class, we use that, regardless of other matches in higher ancestral classes. So since C is D's direct base class, D::Foo overrides C::Foo, which overrides the abstract A::Foo.

So we should be good here right? A::Foo has an implementation in D::Foo, and B::Foo has its own implementation as well. But we're not. We get a runtime type load exception, which complains that D has a method Foo with no body.

Well that's odd! I thought we just said that everything has an implementation!

So, being the inquisitive minded person that I am, (and of course, having a bug open to fix this issue), I went and poked around, and discovered that we could fix this problem by having the compiler emit the .override instruction, so that the CLR will know exactly which method we're overriding.

Well neat, that fixes that problem. Or so I thought!

Bug number two looks a little different, but very similar.

using System;

class A<T>
{
    protected virtual void Foo(T x){}
}

class B<T, S> : A<T>
{
    public virtual void Foo(S x) {}
}

class C<T, S> : B<T, S>
{
    protected override void Foo(T x) { }
}

class D : C<int, int>
{
    protected override void Foo(int x) {}
    
    static void Main()
    {
        new D();
    }
}

In this scenario, the compiler again allows us to compile the code without problems, and once again we get a runtime exception. This time, we get an exception saying that we're attempting to lower the access of B::Foo. Interesting. This looks like my first bug! So what do I do? I apply the fix to my first bug and see what happens.

No luck.

"But why not?", you ask? Well, after more digging (and finding the right contacts on the CLR team to chat with), we discovered that the initial fix was wrong! It turns out that by specifying the .override command, we tell the CLR to override A::Foo, but the CLR also finds B::Foo and tells D:Foo to override that as well.

At the end of it all, we discovered that the entire scenario is an error. Why? The CLI spec, chapter 11.9.9 "Inheritance and overriding" outlines:

Type definitions are invalid if, after substituting base class generic arguments, two methods result in the same name and signature (including return type). The following illustrates this point:
[Example:
.class B`1<T>
{ .method public virtual void V(!0 t) { … }
.method public virtual void V(string x) { … }
}
.class D extends B`1<string> { } // Invalid
Class D is invalid, because it will inherit from B<string> two methods with identical signatures:
void V(string)

At the end of it all, we discovered that we have a disconnect between the CLR and the C# compiler here. We're currently working on determining what C# spec changes we'll need to make to clarify this case, and from there we'll put a fix together.

So what did I learn today? Two things:

1) Our customer that found this bug (I only know them as nikov) is great at finding an exploit, and then massaging it in all possible ways to find other problems (which I might add, is phenomenal).

2) People should just not code like this cause its confusing and doesn't work :)

Leave a Comment
  • Please add 7 and 5 and type the answer here:
  • Post
  • Thanks for the greate post!

    I just want to add that that's a typical multiple-inheritance problem. IMO, whenever there's an ambiguity, the compiler should treat it as invalid code. This way, you'll also eliminate the possible ambiguity of the writer's intention when you read his code. The CLI spec does a good job here.

    We've always the possibility to explicitly implement the methods and create a new method with clear definitions of our intentions when we run into such problems.

    Keep blogging!

    Thomas

  • Hi Thomas,

    The problem with treating all ambiguity as invalid code however, is that there are many cases where ambiguity is hard to avoid, and yet we want some tie-breaking rule to allow us to write seemingly unambiguous code, and yet have it work in a consistent manner. For instance, the overload resolution rules are a fairly complex set of rules that define exactly how to deal with ambiguities, so that we dont have to have different method names for every overload that we'd like to have.

    While I agree that its often nice to name methods clearly, sometimes its unavoidable to have overloads (overloaded operators for example). Dont get me wrong - I'm definitely in the camp that prefers methods named descriptively and without abbreviations, but there are definitely times where simply overloading the parameters is descriptive enough.

    Thanks for your comments!

    - Sam

  • To me, this similar (in a more sophisticated way) to the inconsistency you can create with the 'new' keyword:

    //Illegal in C#, will not compile

    class Z{

    private void Display(){ Console.WriteLine("private Display"); }

    public void Display(){ Console.WriteLine("public Display"); }

    }

    --------------------------------------------

    //Will compile just fine and produce an equivalent result to the illegal bit above

    class Program {

           static void Main(string[] args) {

               B b = new B();

               b.Display();

           }

       }

       class A {

           public void Display() {

               Console.WriteLine("from A");

           }

       }

       class B : A {

           new void Display() {

               Console.WriteLine("from B");

           }

       }

  • Hi Sam,

    Nikov's real name is Vladimir Reshetnikov and yes, he is amazing at finding such things. You can read more at

    http://nikov-thoughts.blogspot.com/

    Kirill

  • Hi fjeannin,

    You're absolutely right about the scenario you described. That is exactly the purpose of the "new" keyword when specifying methods on derived classes. The behavior that you're contrasting this to is different. Consider the following example:

    using System;

    class A

    {

       public void Foo()

       {

           Console.WriteLine("A");

       }

    }

    class B : A

    {

       public new void Foo()

       {

           Console.WriteLine("B");

       }

       static void Main(string[] args)

       {

           B b = new B();

           A a = b;

           a.Foo();

           b.Foo();

       }

    }

    This program prints out "A" followed by "B". This is exactly what the new keyword is for - to specify that whatever type the reference is that you're using, thats the method that will get called. Notice that if the methods were declared virtual and override respectively, we would produce "B" followed by "B" instead.

  • Welcome to the forty-first Community Convergence. The big news this week is that we have moved Future

Page 1 of 1 (6 items)