StackOverflowException when accessing member of generic type via dynamic: .NET/C# framework bug?

Question

In a program I'm using the dynamic keyword to invoke the best matching method. However, I have found that the framework crashes with a StackOverflowException under some circumstances.

I have tried to simplify my code as much as possible while still being able to re-produce this problem.

class Program
{
    static void Main(string[] args)
    {
        var obj = new SetTree<int>();
        var dyn = (dynamic)obj;
        Program.Print(dyn); // throws StackOverflowException!!
        // Note: this works just fine for 'everything else' but my SetTree<T>
    }
    static void Print(object obj)
    {
        Console.WriteLine("object");
    }

    static void Print<TKey>(ISortedSet<TKey> obj)
    {
        Console.WriteLine("set");
    }
}

That program would normally print "set" if the newed up instance implements the ISortedSet<TKey> interface and print "object" for anything else. But, with the following declarations a StackOverflowException is thrown instead (as noted in a comment above).

interface ISortedSet<TKey> { }

sealed class SetTree<TKey> : BalancedTree<SetTreeNode<TKey>>, ISortedSet<TKey> {}

abstract class BalancedTree<TNode> 
    where TNode : TreeNode<TNode> { }

abstract class SetTreeNode<TKey> : KeyTreeNode<SetTreeNode<TKey>, TKey> { }

abstract class KeyTreeNode<TNode, TKey> : TreeNode<TNode>
    where TNode : KeyTreeNode<TNode, TKey> { }

abstract class TreeNode<TNode>
    where TNode : TreeNode<TNode> { }

Whether this is a bug or not it is very troubling that a StackOverflowException is thrown as we are unable to catch it and also pretty much unable to determine in advance whether an exception will be thrown (and thereby terminate the process!).

Can someone please explain what's going on? Is this a bug in the framework?

When debugging and switching to "Disassembly mode" I'm seeing this:

Register dump at that location:

EAX = 02B811B4 EBX = 0641EA5C ECX = 02C3B0EC EDX = 02C3A504 ESI = 02C2564C
EDI = 0641E9AC EIP = 011027B9 ESP = 0641E91C EBP = 0641E9B8 EFL = 00000202

That doesn't tell me much more than being an indicator that this indeed must be some kind of bug in the framework.

I've filed a bug report on Microsoft Connect but I'm interested in knowing what's going on here. Are my class declarations unsupported in some way?

Not knowing WHY this is happening causes me to worry about other places where we are using the dynamic keyword. Can I not trust that at all?

Answer 1

The problem is that you are deriving a type from itself:

abstract class SetTreeNode<TKey> : KeyTreeNode<SetTreeNode<TKey>, TKey> { }

The type SetTreeNote<TKey> becomes KeyTreeNode<SetTreeNode<TKey>,TKey> which becomes KeyTreeNode<KeyTreeNode<SetTreeNode<TKey>,TKey>,TKey> and this goes on and on until the stack overflows.

I don't know what you are trying to accomplish by using this complex model, but that is your problem.

I managed to reduce it to this example which fails:

interface ISortedSet<TKey> { }

sealed class SetTree<TKey> : BalancedTree<SetTreeNode<TKey>>, ISortedSet<TKey> { }

abstract class BalancedTree<TNode> { }

abstract class SetTreeNode<TKey> : KeyTreeNode<SetTreeNode<TKey>, TKey> { }

abstract class KeyTreeNode<TNode, TKey> : TreeNode<TNode> { }

abstract class TreeNode<TNode> { }

And then I fixed it by doing this:

interface ISortedSet<TKey> { }

sealed class SetTree<TKey> : BalancedTree<SetTreeNode<TKey>>, ISortedSet<TKey> { }

abstract class BalancedTree<TNode> { }

abstract class SetTreeNode<TKey> : KeyTreeNode<TKey, TKey> { }

abstract class KeyTreeNode<TNode, TKey> : TreeNode<TNode> { }

abstract class TreeNode<TNode> { }

The only difference between the two is that I replaced KeyTreeNode<SetTreeNode<TKey>, TKey> with KeyTreeNode<TKey, TKey>

Answer 2

I created a shorter, more to-the-point SSCCE that illustrates the problem:

class Program
{
    static void Main()
    {
        dynamic obj = new Third<int>();
        Print(obj); // causes stack overflow
    }

    static void Print(object obj) { }
}

class First<T> where T : First<T> { }

class Second<T> : First<T> where T : First<T> { }

class Third<T> : Second<Third<T>> { }

Looking at the call stack, it seems to be bouncing between two pairs of symbols in the C# runtime binder:

Microsoft.CSharp.RuntimeBinder.SymbolTable.LoadSymbolsFromType(
    System.Type originalType
)

Microsoft.CSharp.RuntimeBinder.SymbolTable.GetConstructedType(
    System.Type type,
    Microsoft.CSharp.RuntimeBinder.Semantics.AggregateSymbol agg
)

and

Microsoft.CSharp.RuntimeBinder.Semantics.TypeManager.SubstTypeCore(
    Microsoft.CSharp.RuntimeBinder.Semantics.CType type, 
    Microsoft.CSharp.RuntimeBinder.Semantics.SubstContext pctx
)

Microsoft.CSharp.RuntimeBinder.Semantics.TypeManager.SubstTypeArray(
    Microsoft.CSharp.RuntimeBinder.Semantics.TypeArray taSrc,
    Microsoft.CSharp.RuntimeBinder.Semantics.SubstContext pctx
)

If I had to hazard a guess, some of the generic type constraint nesting you've got going on has managed to confuse the binder into recursively walking the types involved in the constraints along with the constraints themselves.

Go ahead and file a bug on Connect; if the compiler doesn't get caught by this, the runtime binder probably shouldn't either.

---

This code example runs correctly:

class Program
{
    static void Main()
    {
        dynamic obj = new Second<int>();
        Print(obj);
    }

    static void Print(object obj) { }
}

internal class First<T>
    where T : First<T> { }

internal class Second<T> : First<Second<T>> { }

This leads me to believe (without much knowledge of the internals of the runtime binder) that it's proactively checking for recursive constraints, but only one level deep. With an intermediary class in between, the binder ends up not detecting the recursion and tries to walk it instead. (But that's all just an educated guess. I'd add it to your Connect bug as additional information and see if it helps.)