An Inheritance Puzzle, Part Two

An Inheritance Puzzle, Part Two

  • Comments 12

Today, the answer to Friday's puzzle. It prints "Int32". But why?

Some readers hypothesized that M would print out "Int32" because the declaration B : A<int> somehow tells B that T is to be treated as int, now and forever. Though the answer is right, the explanation is not quite right. One can illustrate this by taking C out of the picture. If you say (new A<string>.B()).M(), you'll get "String". The fact that B is an A<int> doesn't make T always int inside B!

The always-keen Stuart Ballard was the first to put his finger upon the real crux of the problem -- but he's seen this problem before, so he had an advantage. Eamon Nerbonne was the first to post a complete and correct explanation.

The really thorny issue here is that the declaration class C : B is upon close inspection, somewhat ambiguous. Is that equivalent to class C : A<T>.B or class C : A<int>.B?

Clearly it matters which we choose. A method group can only be treated as a member if the method is on a base class. Merely being on an outer class doesn't cut it:

public class X { public void M(){} }
public class Y {
  public void N() {}
  public class Z : X {}
}
...
(new Y.Z()).M(); // legal, from base class
(new Y.Z()).N(); // illegal -- outer class members are not members of inner classes.

In our example, when we called M on an instance of A<string>.B.C, it was calling a method of the base class of C. If the base class of C is A<T>.B, then that should call A<T>.B.M, and it should print out whatever the current value of T is -- in this case, "String". If the base class of C is A<int>.B, then that should call A<int>.B.M, so it should print out "Int32".

We choose the latter as the base class. That was certainly a surprise to me. And Stuart Ballard. And, amusingly enough, when I sprang this one upon Anders and didn't give him time to think about it carefully, it was a surprise to him as well. When I sprang it on Cyrus, he cheerfully pointed out that he already posted a harder version of this problem back in 2005, the solution of which Stuart characterized back then as "Insanely complex, but it makes perfect sense." I couldn't agree more, though at least my version of the puzzle is somewhat simpler.

Anyway, why on earth ought that to be the case? Surely the B in class C : B means the immediately containing class, which is A<T>.B, not A<int>.B! And yet it does not.

These generics are screwing up our intuitions. Let's look at an example which has no generics at all:

public class D {
    public class E {}
}
public class F {
    public class E { }
    public class G {
        public E e; // clearly F.E
    }
}
public class H : D {
    public E e; // clearly D.E
}

This is all legal so far, and should be pretty clear. When we are binding a name to a type, the type we get is allowed to be a member of any base class or a member of any outer class. But what if we have both to choose from?

public class J {
    public class E {}
    public class K : D {
        public E e; // Is this J.E or D.E?
    }
}

We could just throw up our hands and say that this is ambiguous and therefore illegal, but we'd rather not do that if we can avoid it. We have to prefer one of them, and we've decided that we will give priority to base classes over outer classes. Derived classes have an "is a kind of" relationship with their base classes, and that is logically a "tighter" binding than the "is contained in" relationship that inner classes have with outer classes.

Another way to think about it is that all the members you get from your base class are all "in the current scope"; therefore all the members you get from outer scopes are given lower priority, since stuff inside inner scopes takes priority over stuff in outer scopes.

The algorithm we use to search for a name used in the context of a type S is as follows:

  • search S's type parameters
  • search S's accessible inner classes
  • search accessible inner classes of all of S's base classes, going in order from most to least derived
  • S←S's outer class, start over

(And if that fails then we invoke the whole mechanism of searching the namespaces that are in scope, checking alias clauses, etc.)

With that in mind, now the solution should finally make some sense. At the point where we are resolving the base class of C we know that C has no type parameters. We do not know what the base class or inner classes of C are -- that's what we're trying to figure out -- so we skip checking them.

The next thing we check is the outer class, which is A<T>.B, but we do NOT say, aha, the outer class is called B, we're done. That is not at all what the algorithm above says. Instead, it says check A<T>.B to see if it has a type variable called B or an inner type called B. It does not, so we keep searching.

The base type of A<T>.B is A<int>. The outer type of A<T>.B is A<T>. Both have an accessible inner class called B. Which do we pick? The base type gets searched first, so B resolves to A<int>.B. Obviously.

Having members of base classes bind tighter than members from outer scopes can lead to bizarre situations but they are generally pretty contrived. For example:

public class K { public class L {} }
public class L : K {
  L myL; // this is K.L!
}

And of course, you can always get around these problems by eliminating the ambiguity:

public class A<T> {
  public class B : A<int> {
    public void M() { ... }
    public class C : A<T>.B { } // no longer ambiguous which B is picked.

Finally, the specification of this behaviour is a bit tricky to understand:

Otherwise, if T contains a nested accessible type having name I and K type parameters, then the namespace-or-type-name refers to that type constructed with the given type arguments. If there is more than one such type, the type declared within the more derived type is selected.

By "if T contains a nested accessible type", it means "if T, or any of its base classes, contains a nested accessible type". I completely failed to comprehend that the first n times I read that section. I'll see if I can get that clarified in the next version of the standard.

 

  • Here's the thing that bothers me about the whole example.  The T being referenced inside B does not belong to the base class.  It belongs to the outer class.  This can be illustrated by modifying the example as below, with the class B now outside the class A<T>, but still deriving from A<int>.  This code refuses to compile because T has no meaning within B.

    This is the reason I was so confused.  T is being evaluated as int because of the base class, even though it really "belongs" to the _outer_ class, where it should be T, which yield string in the example.

    Does what I'm saying make sense to anyone, or am I just off my rocker???

    Here's the code:

    public class A<T>

    {

    }

    public class B : A<int>

    {

    public void M()

    {

    System.Console.WriteLine(typeof(T).ToString());

    }

    public class C : B { }

    }

    static void Main(string[] args)

    {

    B.C c = new B.C();

    c.M();

    }

  • I see your point, but there is no contradiction.  Let me spell it out for you.

    * The base class of A<string>.B.C is A<int>.B.

    * The outer class of A<string>.B.C is A<string>.B

    * A method call on an object is always called on the class or one of its base classes, never on its outer class.

    * Therefore the call to M is a call to A<int>.B.M

    * Therefore, M prints out "int".

    Or, think about it this way. Sure "T belongs to the outer class". But _which_ outer class? The outer class of A<int>.B is A<int>, the outer class of A<string>.B is A<string>.  The outer class which is relevant for the purposes of a method call is the outer class of the base class of C. The base class of C is A<int>.B.

  • The behaviour of (new A<string>.B()).M() is unexpected.

    It will require a careful reading of Eric's post to understand how the scoping rules for generic type T work.

  • > The outer class of A<int>.B is A<int>, the outer class of A<string>.B is A<string>.  The outer class which is relevant for the purposes of a method call is the outer class of the base class of C. The base class of C is A<int>.B.

    So, we are asking for an object of type A<string>.B.C, but when we call the method M on our variable we are getting the method A<int>.B.C.M.

    I never would have expected it, and I still think its unintuitive.  But I understand.

    Sorry for being dense, and thanks very much for taking the time to spell it out.

  • Actually, I have a few more questions....  Why is the base class of C A<int>.B, instead of A<string>.B, when we specifically instantiated it via A<string>?  Are we somehow transported from the outer class A<string> to A<int> by the act of deriving B from A<int>?  Does it have to do with the order in which the classes are compiled or constructed?

    Is there any way at all to get at the C inside A<string>.B, to yield "string" as the output instead of "int32", or is that class an artifact of the code layout and not actually a valid construction?

  • I think I see the answer to my previous question in your post, here:

    >The base type of A<T>.B is A<int>. The outer type of A<T>.B is A<T>. Both have an accessible inner class called B. Which do we pick? The base type gets searched first, so B resolves to A<int>.B. Obviously.

    So let me see if I've got this right....  C is being constructed "from the bottom up", so to speak.  So even though we've specified A<string>.B.C, that really just specifies a starting point.  What we get is the result of the scope searching algorithm for resolving B.  And this may not necessarily reflect the exact "path" laid out in the types of the variable decalration, or the precise nesting of the code itself.  Instead, it all comes down to the tree structure of outer and base classes of C, and the algorithm for traversing that tree.

  • Right.  The situation where we have class C : B is exactly the same as if we had

    class C : A<int>.B

    So the base class of A<string>.B.C is A<int>.B.  Therefore all method calls to M on an A<string>.B.C are method calls on an A<int>.B.M.

    If we had said

    class C : A<T>.B

    then method calls to M on A<string>.B.C would be to A<string>.B.M

  • Damn!  My submission got lost.

    In any case, it is a shame that "we've decided that we will give priority to base classes over outer classes".  Variable shadowing without an error, or even a warning, is an unfortunate source of bugs.  But it does make for a good mind teaser.

  • The base class of A.<string>.B is A<int>

    The inner class of A<string>.B is C: A<Int>.B

    The outer class of A.<string>.B is A<string>

    Why is A<string>.B.M() equal to "string"? Shoulldn't it be int?

  • > The base class of A.<string>.B is A<int>

    Correct.

    > The inner class of A<string>.B is C: A<Int>.B

    Wrong. The inner class of A<string>.B is A<string>.B.C.

    > The outer class of A.<string>.B is A<string>

    Correct.

    > Why is A<string>.B.M() equal to "string"? Shoulldn't it be int?

    No. In A<string>, clearly T is string. So printing out the name of type T should be "string".

  • 如果我们的代码中同时出现泛型、继承、嵌套类这三种语言元素,那么在根据名称解析类型的时候可能就会有歧义了。本文中的问题及其结论是非常有意思的,其分析过程也非常的绕,大家一起来讨论下吧:)

  • 如果我们的代码中同时出现泛型、继承、嵌套类这三种语言元素,那么在根据名称解析类型的时候可能就会有歧义了。本文中的问题及其结论是非常有意思的,其分析过程也非常的绕,大家一起来讨论下吧:)

Page 1 of 1 (12 items)