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...

I allowed myself to simplify your example. Please revert if you don't agree. — usr, Feb 20 '12 at 23:07
To be honest, this looks like a clever headf**k. What's wrong with the more traditional ways of representing trees using composition instead? What does this buy you? I hope that doesn't sound too antagonistic. I'm just curious. — spender, Feb 20 '12 at 23:12
@spender it halfs the number of allocations, and reduces the number of indirections you need to follow. So in high performance code it might be a reasonable trade-off. For smaller trees it's probably a bad idea. — CodesInChaos, Feb 20 '12 at 23:14
Yes, i'll use this implementation for a scene graph, so I'd like to avoid indirections if possible. — s0ubap, Feb 20 '12 at 23:19
OK. I see. This could be very handy for some rather large Trie type structures I maintain. +1 for learning me something new. — spender, Feb 21 '12 at 02:06
@spender what do you mean with "representing trees using composition", can you give me a example? Do you mean something like Node with a T Value property instead of T itself being the Node and then create a "wrapper" Node for every object? — R1PFake, May 24 '20 at 07:29

score 3 · Accepted Answer · answered Feb 20 '12 at 23:03

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'

score 1 · Answer 2 · answered Feb 20 '12 at 23:03

1

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>.

answered Feb 20 '12 at 23:03

CodesInChaos

106,488
23
218
262

Hmm I guess a type check could help a little in the TreeNode constructor to check if "this" is actually T and otherwise throw with a clear error message that the pattern was misused? Or is there a better/different pattern for a generic Tree implementation? – R1PFake May 24 '20 at 07:58

hoodaticus · Answer 3 · 2015-10-29T17:05:22.623

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.

score 0 · Answer 4 · answered Feb 20 '12 at 23:24

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.

While composition based collections are usually a better idea, intrusive collections have their place. The `TreeNode where T : TreeNode` constraint makes sense in this context. It can be satisfied by the curiously recurring template pattern. The `AddChild` implementation looks also fine to me. In a tree you either implement `SetParent` or `AddChild` explicitly, and then make the other one call the one you implemented. — CodesInChaos, Feb 20 '12 at 23:29

score 0 · Answer 5 · edited May 23 '17 at 12:29

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.

C# - Intrusive tree structure, using CRTP

5 Answers5