Call stack overflow with particular inheritance pattern

[mattjphillips]

Came across this problem in 0.8. Consider the following:

public class TestCase
{
    public static void Run()
    {
        Four top = new Four();
        top.Foo();
    }
}

class One
{
    public virtual void Foo() {}
}

class Two : One
{
    public override void Foo()
    {
        base.Foo();
    }
}

class Three : Two
{
}

class Four : Three
{
}

The base.Foo() method in Two.Foo() compiles to:

  ss.base(this, 'foo').call(this);

And in the test case, 'this' is the Four object. However, the logic in ss.base() is such that it returns Two.Foo, so the call() ends up calling itself, resulting in infinite recursion and a call stack overflow.

I've hacked around this in my copy of S# by modifying GenerateMethodExpression to pass the BaseExpression's EvaluatedType.FullGeneratedName as a third parameter to ss.base(), then modifying ss.base() to favor that third parameter as the starting base class in its search for the base method. That's a total stab in the dark, but starting with the base class seems more reasonable than starting with 'this.'

[nikhilk]

I seem to remember seeing this and fixing this. See the commit for #295 at 876fed5

Did you pick up the latest, as in the latest commits from the cc branch? Just checking before spending time looking deeper into this.

[mattjphillips]

Yes, I have that change. The fix for #295 addresses the special case where a subclass doesn't override a method that its parent overrides. But it fails in the general case where there's more than one level of non-overriding subclass.

[mattjphillips]

After looking at the code for a while, it seems like the current approach of passing 'this' to ss.base() and then searching up the inheritance chain doesn't work in the general case. In fact, 'this' probably isn't the right first argument; it should be the class itself (in the example above, Two). And we can do better than that: you know the base class at expression generation time, so the walk up the inheritance chain can start there.

I'll see if I can clean up my hack into a proposed fix.

[mattjphillips]

OK, a proposed fix is this. I'll describe it and if you want me to work it up into a pull request I'll try to figure out how one does that. :-)

A new version of ss.base() requires the caller to pass the initial class at which to start the search:

function base(type, method) {
    var m;
    while (!(m = type.prototype[method])) type = type.constructor.$base || type.$base;
    return m;
}

The expression generator is then modified to pass the base class rather than ThisIdentifier for the BaseExpression cases, eg:

            ...
            writer.Write("ss.base(");
            // writer.Write(generator.CurrentImplementation.ThisIdentifier);
            writer.Write(((BaseExpression)expression.ObjectReference).EvaluatedType.FullGeneratedName);
            writer.Write(", '");
            ...

That's it. Presumably this could be improved more by searching at expression generation time rather than at runtime, so that instead of generating

 ss.base(One, 'foo').call(this);

it would generate

 One.prototype.foo.call(this);

which is much more efficient. Although I'm making a lot of assumptions about what's really known at generation time.

[nikhilk]

Thanks for sharing the research. I do have some followup questions, since I haven't yet had the chance to run the scenario myself and debug through it.

Here is the current implementation:

function base(instanceOrType, method) {
  var baseType = instanceOrType.constructor.$base || instanceOrType.$base;
  var m = baseType.prototype[method];
  return m !== instanceOrType[method] ? m : base(baseType, method);
}

Isn't this effectively looking up the type of an instance and starting with its base type if the first parameter is an instance, or just the base type if the first parameter is a type, i.e. exactly what you're achieving by passing in One as the 1st arg through the change to the generator, or by using One.prototype directly? So I'd love to understand why you mention

it seems like the current approach of passing 'this' to ss.base() and then searching up the inheritance chain doesn't work in the general case

The reason I liked for ss.base take in this as the first param, is it is much more readable (I think). It says find the specified method on the base class of "this" ... as opposed to seeing the literal base type there to begin with (if we opt for that, then the method should no longer be called base).

Furthermore, I wouldn't expect a walk up the type chain shouldn't be required, since prototypes chain (which has to be the case for One.prototype.foo to work). Yes, that raises the same question on even the current implementation's call to base recursively. Trying to remember what edge case I was trying to handle...

Thanks

[mattjphillips]

The problem with using 'this' as the arg to base() is that 'this' could be an object of your class, or any descendant class. So the infinite recursion bug in the example arises because Two.foo() is asking 'top' for the first ancestor class that implements 'foo' different from it -- which is Two. Instead, Two.foo() should ask for the first ancestor class of itself. The object reference isn't of any interest except as the scope for the call().

Here's a slightly simpler example that also blows up:

class One { virtual void foo() {} }
class Two : One { override void foo() { base.foo(); } }
class Three: Two { override void foo() { base.foo(); } }
(new Three()).foo();

Because again, the implementation of Two.foo() will try to find the base of 'this', which is a Three, and the result is Two.foo().

I have to admit that even though I've stared at it for a while now, I don't understand that last line of ss.base(). In particular, if instanceOrType is a type, then instanceOrType[method] will always be undefined, so it's not obvious why that's being compared to baseType.prototype[method]. Perhaps that's intentional, but I don't get why.

In any case, I believe you're right that you could use prototype chaining to identify the base class without walking the hierarchy at expression generation time -- with modern JS optimizations that ends up being similar in performance anyway. Ie, the fix could be as simple as

        ...
        writer.Write(((BaseExpression)expression.ObjectReference).EvaluatedType.FullGeneratedName);
        writer.Write(".prototype.");
        writer.Write(expression.Method.GeneratedName);
        writer.Write(".call('");
        ...

and there would be no need for ss.base() at all.

[nikhilk]

Ah, yes, that makes sense. Thanks for spending the time on this and explaining.

I like the latest change you have where we can simply drop the need for ss.base, so lets remove that and change the generator to pre-resolve and call the right method.

If you'd like feel free to make a change and create a pull request. Otherwise I'll try to get to it later today or tomorrow.

[mattjphillips]

OK, there's my attempt at a pull request. I have no idea whether it's done correctly. :-)

[nikhilk]

Overall this looks really great. Did you go to your repository and actually submit a pull request, for me to be able to merge via the github UI?

As I looked through your commit, I think I spotted a related bug in a different part of the code - specifically in GeneratePropertyExpression the code tries to optimize expressions such as someType.prototype to someType$ for types that are in the same assembly. However on quick look, based on the context of the discussion we've had so far, that probably doesn't do the right thing when the member we want isn't right on the base class but on some other ancestor type, and might need to undo that optimization.

[mattjphillips]

Ah, I think I figured out what step I was missing earlier. Although it's now created another issue (#382). Maybe that's expected.. sorry for being so newbie at this github stuff.

I had noticed that optimization and wasn't sure what it was about. But I agree that if it's assuming that the base implements it, and it doesn't, then it'll fail. I'll see if I can figure it out and find a failure case, and if so, fit it if possible.

The other thing I'll look into today is adding test cases for all of this inheritance chaining. All I did was fix up the baselines to match the new generator code.

[mattjphillips]

Yep, the someType$ optimization is flawed. Eg:

class PropA { public virtual string Foo { get { return "PropA"; } } }
class PropB : PropA { }
class PropC : PropB { public override string Foo { get { return base.Foo + "PropC"; } } }
...
string s = (new PropC()).Foo; // fails: cannot call method 'call' of undefined

I'll submit a fix (#384).

[mattjphillips]

A naive question: I started looking into adding some tests for validating inheritance scenarios but I'm not seeing any tests that verify the behavior of generated code. Is that accurate?