Les SyntaxNodes Roslyn sont-ils réutilisés?

c# expression-trees roslyn

Question

J’ai jeté un coup d’œil à Roslyn CTP et, bien qu’il résolve un problème similaire à celui de l’ API Expression Tree , les deux sont immuables, mais Roslyn le fait d’une toute autre manière:

  • Expression nœuds d' Expression ne font pas référence au nœud parent, sont modifiés à l'aide d'un ExpressionVisitor , ce qui permet de réutiliser de grandes pièces.

  • Le SyntaxNode de Roslyn, de l’autre côté, contient une référence à son parent. Tous les nœuds deviennent donc un bloc impossible à réutiliser. Des méthodes telles que Update , ReplaceNode , etc. sont fournies pour apporter des modifications.

Où cela finit-il? Document ? Project ? ISolution ? L'API favorise un changement pas à pas de l'arborescence (au lieu d'un bouton vers le haut), mais chaque étape crée-t-elle une copie complète?

Pourquoi ont-ils fait un tel choix? Y a-t-il une astuce intéressante qui me manque?

Réponse acceptée

MISE À JOUR: Cette question a été le sujet de mon blog le 8 juin 2012 . Merci pour la bonne question!


Excellente question. Nous avons débattu des questions que vous soulevez depuis très longtemps.

Nous aimerions avoir une structure de données qui présente les caractéristiques suivantes:

  • Immuable.
  • La forme d'un arbre.
  • Accès bon marché aux nœuds parents à partir des nœuds enfants.
  • Possibilité de mapper depuis un nœud de l’arbre vers un caractère décalé dans le texte.
  • Persistant .

Par persistance, j'entends la possibilité de réutiliser la plupart des nœuds existants dans l'arborescence lorsqu'une modification est apportée au tampon de texte. Les nœuds étant immuables, il n’ya pas d’obstacle à les réutiliser. Nous avons besoin de cela pour la performance; nous ne pouvons pas ré-analyser de gros fichiers du fichier chaque fois que vous appuyez sur une touche. Nous devons analyser et analyser à nouveau uniquement les parties de l'arbre affectées par la modification.

Désormais, lorsque vous essayez de regrouper ces cinq éléments dans une structure de données, vous rencontrez immédiatement des problèmes:

  • Comment construisez-vous un nœud en premier lieu? Le parent et l'enfant se réfèrent l'un à l'autre et sont immuables. Lequel se construit en premier?
  • Supposons que vous parveniez à résoudre ce problème: comment le rendez-vous persistant? Vous ne pouvez pas réutiliser un nœud enfant dans un autre parent car cela impliquerait de dire à l'enfant qu'il a un nouveau parent. Mais l'enfant est immuable.
  • Supposons que vous parveniez à résoudre ce problème: lorsque vous insérez un nouveau caractère dans le tampon d'édition, la position absolue de chaque nœud mappé sur une position après ce point change. Cela rend très difficile la création d'une structure de données persistante, car toute édition peut modifier les étendues de la plupart des nœuds!

Mais dans l’équipe de Roslyn, nous faisons régulièrement des choses impossibles. En fait, nous faisons l'impossible en conservant deux arbres d'analyse. L'arbre "vert" est immuable, persistant, n'a pas de références parent, est construit "de bas en haut", et chaque nœud suit sa largeur mais pas sa position absolue . Lorsqu'une modification est effectuée, nous ne reconstruisons que les parties de l'arborescence verte affectées par la modification, ce qui correspond généralement à environ O (log n) du nombre total de nœuds d'analyse dans l'arborescence.

L'arbre "rouge" est une façade immuable qui est construite autour de l'arbre vert; il est construit "de haut en bas" à la demande et jeté à chaque édition. Il calcule les références parent en les fabriquant à la demande lorsque vous descendez de l'arborescence . Il fabrique des positions absolues en les calculant à partir des largeurs, à nouveau, en descendant.

Vous, l'utilisateur, ne voyez jamais que l'arbre rouge; l'arbre vert est un détail d'implémentation. Si vous examinez l'état interne d'un nœud d'analyse, vous constaterez qu'il existe une référence à un autre nœud d'analyse d'un type différent. c'est le noeud de l'arbre vert.

Incidemment, on les appelle "arbres rouges / verts", car c’est la couleur des marqueurs de tableau blanc utilisée pour dessiner la structure de données lors de la réunion de conception. Il n'y a pas d'autre signification aux couleurs.

L'avantage de cette stratégie est que nous obtenons toutes ces grandes choses: immuabilité, persistance, références parentales, etc. Le coût est que ce système est complexe et peut consommer beaucoup de mémoire si les façades "rouges" deviennent grandes. Nous faisons actuellement des expériences pour voir si nous pouvons réduire une partie des coûts sans perdre les avantages.



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow