C# - Estructura de árbol intrusiva, usando CRTP

Question

Actualmente estoy trabajando en una forma simple de implementar una estructura de árbol intrusiva en C#. Como soy principalmente un programador de C++, inmediatamente quise usar CRTP. Aquí está mi código:

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

Esto funciona, pero ... No puedo entender por qué tengo que echar al llamar a_node.SetParent ((T) esto), ya que estoy usando restricción de tipo genérico .. . C# fundido tiene un costo, y me gustaría no difundir este reparto en cada implementación de la colección intrusiva ...

Answer 1

esto es al menos del tipo TreeNode. Podría derivarse o podría ser exactamente TreeNode. SetParent espera una T. Pero T puede ser un tipo diferente de lo que es. Sabemos que esto y T provienen de TreeNode pero pueden ser de diferentes tipos.

Ejemplo:

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

Answer 2

Nadie garantiza que T y el tipo de this son los mismos. Incluso pueden ser subclases no relacionadas de TreeNode.

Se espera que T se use en el patrón de plantilla curiosamente recurrente, pero las restricciones genéricas no pueden expresar eso.

Una implementación estúpida podría definirse como StupidNode:TreeNode<OtherNode>.

Answer 3

El problema es con esta línea:

TreeNode<T> where T : TreeNode<T> 

siendo T un TreeNode es una definición recursiva que no se puede determinar pre-compilar o incluso estáticamente comprobado. No utilice la plantilla, o si se necesita para refactorizar & separar el nodo de la carga útil (Ie los datos del nodo desde el propio nodo.)

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

Además no estoy seguro de por qué está llamando a_node .SetParent (esto). Parece que AddChild se llama mejor SetParent, porque está configurando esta instancia como el padre de a_node. Puede ser algún algoritmo esotérico con el que no estoy familiarizado, de lo contrario no se ve bien.

Answer 4

considere lo que sucede si nos desviamos de la convención CRTP escribiendo ...

public class Foo : TreeNode<Foo> 
{ 
} 

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

... y luego llamar el código anterior de la siguiente manera:

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

La llamada AddChild lanza una InvalidCastException diciendo Unable to cast object of type 'Bar' to type 'Foo'.

En cuanto a la expresión idiomática CRTP, es solo una convención que requiere que el tipo genérico sea el mismo que el de declar tipo de ing. El lenguaje debe ser compatible con los otros casos donde no se sigue la convención de CRTP. Eric Lippert escribió una gran publicación de blog sobre este tema, que él vinculó desde este otro crtp via c# answer.

Todo eso dicho, si cambia la aplicación a este ...

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

... el código anterior que anteriormente arrojó el InvalidCastException ahora trabaja.El cambio hace m_Parent un tipo de TreeNode<T>; haciendo this ya sea del tipo T como en el caso Foo clase o una subclase de TreeNode<T> en el caso Bar clase ya Bar hereda de TreeNode<Foo> - de cualquier manera nos permite omitir el elenco en SetParent y por esa omisión evitamos la excepción de difusión inválida ya que la la asignación es legal en todos los casos. El costo de hacer esto ya no puede usar libremente T en todos los lugares como se había utilizado anteriormente, lo que sacrifica gran parte del valor de CRTP.

Un colega/amigo mío se considera un novato en un idioma/función de lenguaje hasta que honestamente puede decir que lo "usó con ira"; es decir, conoce el idioma lo suficientemente bien como para sentirse frustrado de que no hay forma de lograr lo que necesita o que hacerlo es doloroso. Esto muy bien podría ser uno de esos casos, ya que hay limitaciones y diferencias aquí que hacen eco de la verdad que generics are not templates.

Answer 5

Cuando trabaje con tipos de referencia, y sepa de hecho que su conversión a lo largo de la jerarquía de tipos tendrá éxito (no se realizará una conversión personalizada aquí), entonces no hay necesidad de transmitir nada. El valor del entero de referencia es el mismo antes y después del lanzamiento, entonces ¿por qué no solo omitir el elenco?

Eso significa que puede escribir este despreciado método AddChild en CIL/MSIL. Los códigos de operación cuerpo del método son las siguientes:

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

.NET no le importa en absoluto que no se había desechado el valor. Al Jitter parece que solo le importa que el tamaño de las tiendas sea consistente, lo cual siempre son referencias.

Cargue la extensión IL Support para Visual Studio (puede tener que abrir el archivo vsix y modificar la versión admitida) y declarar el método C# como extern con el atributo MethodImpl.ForwardRef. A continuación, vuelva a declarar la clase en un archivo .il y agregue la implementación de un método que necesita, cuyo cuerpo se proporciona más arriba.

Tenga en cuenta que esto también inserta manualmente su método SetParent en AddChild.