C# - Intrusive Baumstruktur, mit CRTP

Question

Ich arbeite derzeit an einer einfachen Möglichkeit, eine intrusive Baumstruktur in C# zu implementieren. Da ich hauptsächlich ein C++-Programmierer bin, wollte ich sofort CRTP verwenden. Hier ist mein 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;
}

Das funktioniert, aber... Ich kann nicht verstehen, warum ich casten muss, wenn ich a_node.SetParent((T)this) aufrufe, da ich eine generische Typbeschränkung verwende... C#-Cast hat einen Preis, und ich möchte nicht, dass dieser Cast in jeder aufdringlichen Auflistung Implementierung zu verbreiten...

Answer 1

Dies ist mindestens vom Typ TreeNode. Es könnte abgeleitet sein oder es könnte genau TreeNode sein. SetParent erwartet ein T. Aber T kann von einem anderen Typ sein als dieses. Wir wissen, dass this und T beide von TreeNode abgeleitet sind, aber sie können unterschiedliche Typen sein.

Beispiel:

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

Answer 2

Niemand garantiert, dass T und die Art der this sind identisch. Sie können sogar unverbundene Unterklassen sein von TreeNode .

Sie erwarten T in dem merkwürdigerweise wiederkehrenden Schablonenmuster verwendet werden, aber generische Beschränkungen können das nicht ausdrücken.

Eine dumme Implementierung könnte wie folgt definiert werden StupidNode:TreeNode<OtherNode> .

Answer 3

Das Problem liegt in dieser Zeile:

 TreeNode<T> where T : TreeNode<T>

T als TreeNode ist eine rekursive Definition, die nicht vor der Kompilierung bestimmt oder gar statisch geprüft werden kann. Verwenden Sie keine Vorlage, oder wenn Sie tun, müssen Sie refactor & trennen Sie den Knoten von der Nutzlast (Dh die Knoten-Daten aus dem Knoten selbst.)

 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)
     {
     }
 }

Ich bin auch nicht sicher, warum Sie a_node.SetParent(this) aufrufen. Es scheint, wie AddChild ist mehr treffend SetParent genannt, weil Sie diese Instanz als Elternteil von a_node setzen. Vielleicht ist es ein esoterischer Algorithmus, mit dem ich nicht vertraut bin, ansonsten sieht es nicht richtig aus.

Answer 4

Was passiert, wenn man von der CRTP-Konvention abweicht und schreibt...

public class Foo : TreeNode<Foo>
{
}

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

...und rufen dann den obigen Code wie folgt auf:

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

Les AddChild Aufruf löst eine InvalidCastException unter Unable to cast object of type 'Bar' to type 'Foo'.

Was das CRTP-Idiom angeht, so ist es reine Konvention, dass der generische Typ mit dem deklarierenden Typ identisch sein muss. Die Sprache muss die anderen Fälle unterstützen, in denen die CRTP-Konvention nicht eingehalten wird. Eric Lippert hat einen großartigen Blogbeitrag zu diesem Thema geschrieben, den er in diesem anderen Blog verlinkt hat crtp über c# Antwort .

Das heißt, wenn Sie die Umsetzung folgendermaßen ändern...

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;
}

...der obige Code, der zuvor die InvalidCastException funktioniert jetzt. Die Änderung macht m_Parent eine Art von TreeNode<T> Herstellung this entweder der Typ T wie in der Foo Klasse" oder einer Unterklasse von TreeNode<T> im Bar Klasse Fall seit Bar erbt von TreeNode<Foo> - In beiden Fällen können wir auf die Besetzung in SetParent und vermeiden dadurch die Ausnahme der ungültigen Besetzung, da die Zuweisung in jedem Fall legal ist. Der Preis dafür ist, dass man nicht mehr in der Lage ist, frei zu verwenden T an allen Orten, wie sie bisher verwendet wurden, was einen großen Teil des Wertes des CRTP einbüßt.

Ein Kollege/Freund von mir betrachtet sich selbst als Neuling in einer Sprache/Sprachfunktion, bis er ehrlich sagen kann, dass er sie "im Zorn" benutzt hat; das heißt, er kennt die Sprache gut genug, um frustriert zu sein, dass es entweder keine Möglichkeit gibt, das zu erreichen, was er braucht, oder dass es schmerzhaft ist, dies zu tun. Dies könnte sehr wohl einer dieser Fälle sein, da es hier Einschränkungen und Unterschiede gibt, die die Wahrheit widerspiegeln, dass Generika sind keine Vorlagen .

Answer 5

Wenn Sie mit Referenztypen arbeiten und sicher sind, dass Ihr Cast entlang der Typenhierarchie erfolgreich sein wird (kein benutzerdefinierter Cast hier), dann ist es nicht nötig, irgendetwas zu casten. Der Wert der Referenz-Ganzzahl ist vor und nach dem Cast derselbe, warum also nicht einfach den Cast überspringen?

Das heißt, Sie können diese verachtete AddChild-Methode in CIL/MSIL schreiben. Die Opcodes des Methodenkörpers lauten wie folgt:

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

.NET kümmert sich überhaupt nicht darum, dass Sie den Wert nicht gecastet haben. Der Jitter scheint sich nur darum zu kümmern, dass die Größe der Speicher konsistent ist, was sie bei Referenzen immer ist.

Laden Sie die IL-Support-Erweiterung für Visual Studio (möglicherweise müssen Sie die vsix-Datei öffnen und die unterstützte Version ändern) und deklarieren Sie die C#-Methode als extern mit dem Attribut MethodImpl.ForwardRef. Dann deklarieren Sie einfach die Klasse in einer .il-Datei neu und fügen Sie die eine Methodenimplementierung hinzu, die Sie benötigen und deren Body oben angegeben ist.

Beachten Sie, dass dadurch auch Ihre SetParent-Methode manuell in AddChild eingefügt wird.