C# - Intrusive tree structure, using CRTP

Question

I'm currently working on a simple way to implement a intrusive tree structure in C#. As I'm mainly a C++ programmer, I immediatly wanted to use CRTP. Here is my code:

public class TreeNode<T> where T : TreeNode<T>
{
    public void AddChild(T a_node)
    {
        a_node.SetParent((T)this); // This is the part I hate
    }

    void SetParent(T a_parent)
    {
        m_parent = a_parent;
    }

    T m_parent;
}

This works but... I can't understand why I have to cast when calling a_node.SetParent((T)this), as I'm using generic type restriction... C# cast has a cost, and I'd like not to spread this cast in each intrusive collection implementation...

Answer 1

this is at least of type TreeNode. It could be derived or it could be exactly TreeNode. SetParent expects a T. But T can be a different type than this is of. We know that this and T both derive from TreeNode but they can be different types.

Example:

class A : TreeNode<A> { }
new TreeNode<A>() //'this' is of type 'TreeNode<A>' but required is type 'A'

Answer 2

Nobody guaranteed that T and the type of this are the same. They can even be unrelated subclasses of TreeNode.

You expect T to be used in the curiously recurring template pattern, but generic constraints can't express that.

A stupid implementation could be defined as StupidNode:TreeNode<OtherNode>.

Answer 3

The problem is with this line:

 TreeNode<T> where T : TreeNode<T>

T being a TreeNode is a recursive definition it can't be determined pre-compile or even statically checked. Do not use template, or if you do you need to refactor & separate the node from the payload (Ie the node data from the node itself.)

 public class TreeNode<TPayload>
 {
     TPayload NodeStateInfo{get;set;}

     public void AddChild(TreeNode<TPayload> a_node)
     {
         a_node.SetParent(this); // This is the part I hate
     }

     void SetParent(TreeNode<TPayload> a_parent)
     {
     }
 }

Also I'm not sure why you're calling a_node.SetParent(this). It seems like AddChild is more aptly named SetParent, because you're setting this instance as the parent of a_node. May be it's some esoteric algorithm I'm not familiar with, otherwise it doesn't look right.

Answer 4

Consider what happens if we deviate from CRTP convention by writing...

public class Foo : TreeNode<Foo>
{
}

public class Bar : TreeNode<Foo> // parting from convention
{
}

...and then call the above code as follows:

var foo = new Foo();
var foobar = new Bar();
foobar.AddChild(foo);

The AddChild call throws an InvalidCastException saying Unable to cast object of type 'Bar' to type 'Foo'.

Regarding the CRTP idiom - it is convention alone requiring the generic type to be the same as the declaring type. The language must support the other cases where CRTP convention is not followed. Eric Lippert wrote a great blog post on this topic, that he linked from this other crtp via c# answer.

All of that said, if you change the implementation to this...

public class TreeNode<T> where T : TreeNode<T>
{
    public void AddChild(T a_node)
    {
        a_node.SetParent(this);
    }

    void SetParent(TreeNode<T> a_parent)
    {
        m_parent = a_parent;
    }

    TreeNode<T> m_parent;
}

...the above code that previously threw the InvalidCastException now works. The change makes m_Parent a type of TreeNode<T>; making this either the type T as in the Foo class' case or a subclass of TreeNode<T> in the Bar class case since Bar inherits from TreeNode<Foo> - either way allows us to omit the cast in SetParent and by that omission avoid the invalid cast exception since the assignment is legal in all cases. The cost of doing this is no longer being able to freely use T in all places as it had previously been used which sacrifices much of the value of CRTP.

A colleague/friend of mine considers himself a newbie to a language/language-feature until he can honestly say that he's "used it in anger;" that is, he knows the language well enough to be frustrated that there is either no way of accomplishing what he needs or that doing so is painful. This very well could be one of those cases, as there are limitations and differences here that echo the truth that generics are not templates.

Answer 5

When you are working with reference types, and you know for a fact that your cast along the type hierarchy will succeed (no custom casting here), then there is no need to actually cast anything. The value of the reference integer is the same before and after the cast, so why not just skip the cast?

That means you can write this despised AddChild method in CIL/MSIL. The method body opcodes are as follows:

ldarg.1
ldarg.0
stfld TreeNode<class T>::m_parent
ret

.NET will not care at all that you did not cast the value. The Jitter seems to only care about the size of stores being consistent, which they always are for references.

Load up the IL Support extension for Visual Studio (may have to open the vsix file and modify supported version) and declare the C# method as extern with MethodImpl.ForwardRef attribute. Then just re-declare the class in a .il file and add the one method implementation you need, the body of which is provided above.

Note that this also manually inlines your SetParent method into AddChild.