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

124

J'ai jeté un coup d'œil à Roslyn CTP et, bien qu'il résout un problème similaire à l' API de l'arbre d'expression , les deux sont immuables, mais Roslyn le fait d'une manière assez différente:

  • Expressionles nœuds n'ont aucune référence au nœud parent, sont modifiés à l'aide de a ExpressionVisitoret c'est pourquoi de grandes parties peuvent être réutilisées.

  • Roslyn SyntaxNode, de l'autre côté, a une référence à son parent, de sorte que tous les nœuds deviennent effectivement un bloc impossible à réutiliser. Des méthodes telles que Update, ReplaceNode, etc, sont fournis pour apporter des modifications.

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

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

Olmo
la source

Réponses:

181

MISE À JOUR: Cette question a fait l'objet de mon blog le 8 juin 2012 . Merci pour la bonne question!


Excellente question. Nous avons débattu des questions que vous soulevez pendant très, 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 d'un nœud dans l'arborescence vers un décalage de caractère 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. Étant donné que les nœuds sont immuables, il n'y a aucun obstacle à leur réutilisation. Nous en avons besoin pour la performance; nous ne pouvons pas ré-analyser d'énormes wodges du fichier chaque fois que vous appuyez sur une touche. Nous devons re-lex et ré-analyser uniquement les parties de l'arbre qui ont été affectées par l'édition.

Maintenant, lorsque vous essayez de mettre ces cinq éléments dans une seule 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, alors lequel est construit en premier?
  • Supposons que vous parveniez à résoudre ce problème: comment le rendre persistant? Vous ne pouvez pas réutiliser un nœud enfant dans un parent différent, car cela impliquerait d'indiquer à 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 qui est mappé à une position après ce point change. Cela rend très difficile la création d'une structure de données persistante, car toute modification peut modifier les étendues de la plupart des nœuds!

Mais dans l'équipe de Roslyn, nous faisons régulièrement des choses impossibles. Nous faisons en fait l'impossible en conservant deux arbres d'analyse. L'arbre "vert" est immuable, persistant, n'a pas de références parentes, est construit "de bas en haut", et chaque nœud suit sa largeur mais pas sa position absolue . Lorsqu'une modification se produit, nous ne reconstruisons que les parties de l'arbre vert qui ont été affectées par la modification, ce qui correspond généralement à O (log n) du total des 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 parentes en les fabriquant à la demande lorsque vous descendez dans l'arborescence depuis le haut . Il fabrique des positions absolues en les calculant à partir des largeurs, encore une fois, lorsque vous descendez.

Vous, l'utilisateur, ne voyez 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 verrez en fait qu'il y a une référence à un autre nœud d'analyse d'un type différent; c'est le nœud de l'arbre vert.

Incidemment, on les appelle «arbres rouges / verts» parce que ce sont les couleurs des marqueurs du tableau blanc que nous avons utilisées pour dessiner la structure des 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: l'immuabilité, la persistance, les 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 certains des coûts sans perdre les avantages.

Eric Lippert
la source
3
Et pour répondre à la partie de votre question sur les IProjects et les IDocuments: nous utilisons un modèle similaire dans la couche services. En interne, il existe des types "DocumentState" et "ProjectState" qui sont moralement équivalents aux nœuds verts de l'arbre de syntaxe. Les objets IProject / IDocument que vous obtenez sont les façades de nœuds rouges pour ceux-ci. Si vous regardez l'implémentation de Roslyn.Services.Project dans un décompilateur, vous verrez que presque tous les appels sont transférés vers les objets d'état internes.
Jason Malinowski
@Eric désolé pour la remarque, mais vous vous contredisez. The expense and difficulty of building a complex persistent data structure doesn't pay for itself.ref: stackoverflow.com/questions/6742923/... Si vous aviez des objectifs de haute performance, pourquoi l'avez-vous rendu immuable en premier lieu? N'y a-t-il qu'une autre raison en dehors des raisons évidentes? par exemple, plus facile de rendre threadsafe, de raisonner, etc.
Lukasz Madon
2
@lukas Vous prenez cette citation hors de son contexte. La phrase précédente était "Parce que lorsque vous regardez les opérations qui sont généralement effectuées sur des chaînes dans les programmes .NET, il n'est guère pire du tout de créer simplement une chaîne entièrement nouvelle." OTOH, quand vous regardez les opérations qui sont généralement effectuées sur un arbre d'expression - par exemple en tapant quelques caractères dans le fichier source - il est bien pire de construire un arbre d'expression entièrement nouveau. Ils n'en construisent donc que la moitié.
Timbo
1
@lukas Ma conjecture: étant donné que Roslyn est censé fonctionner sur les threads d'arrière-plan, l'immuabilité permet à plusieurs threads d'analyser le même code source en même temps sans se soucier qu'il sera changé lorsque l'utilisateur appuiera sur une touche. En réponse à l'entrée de l'utilisateur, les arborescences immuables peuvent être mises à jour sans arrêter les tâches d'analyse en cours d'exécution. J'imagine donc que l'objectif principal de l'immuabilité est de rendre Roslyn plus facile à écrire (et peut-être plus facile à utiliser pour les clients).
Qwertie
3
@lukas Les structures de données persistantes sont plus efficaces que la copie, lorsque la structure de données est généralement beaucoup plus grande que les modifications qui y sont apportées. Votre argument, si vous en avez un, est perdu pour moi.
Qwertie