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

J’ai jeté un coup d’œil à Roslyn CTP et, tout en résolvant un problème similaire à l’ API d’expression , les deux sont immuables, mais Roslyn le fait de manière très différente:

Où cela se termine? Document ? Project ? ISolution ? L’API favorise un changement pas à pas de l’arborescence (au lieu d’un bouton), mais chaque étape fait-elle une copie complète?

Pourquoi ont-ils fait un tel choix? Y a-t-il un truc intéressant qui me manque?

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


Bonne question Nous avons débattu des questions que vous soulevez depuis longtemps.

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

  • Immuable
  • La forme d’un arbre
  • Accès à bas prix aux nœuds parents à partir des nœuds enfants.
  • Possibilité de mapper d’un nœud dans l’arborescence à un décalage de caractère dans le texte.
  • Persistant .

Par persistance, j’entends la possibilité de réutiliser la plupart des noeuds existants dans l’arborescence lors d’une modification du tampon de texte. Comme les nœuds sont immuables, il n’y a pas d’obstacle à les réutiliser. Nous avons besoin de cela pour la performance; Nous ne pouvons pas parsingr à nouveau les énormes inconvénients du fichier chaque fois que vous appuyez sur une touche. Nous devons relancer et ré-parsingr uniquement les parties de l’arbre qui ont été affectées par la modification.

Maintenant, lorsque vous essayez de mettre 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, alors quel est le premier construit?
  • En supposant 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.
  • En supposant 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 modification peut changer la scope de la plupart des nœuds!

Mais sur l’équipe de Roslyn, nous faisons systématiquement des choses impossibles. Nous faisons effectivement l’impossible en gardant deux arbres d’parsing. L’arbre “vert” est immuable, persistant, n’a pas de référence parent, est construit “bottom-up”, et chaque nœud suit sa largeur mais pas sa position absolue . Lorsqu’une modification se produit, nous reconstruisons uniquement les parties de l’arbre vert qui ont été affectées par la modification, ce qui correspond généralement à O (log n) du nombre total de noeuds d’parsing dans l’arborescence.

L’arbre rouge est une façade immuable 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 parentales en les fabriquant à la demande lorsque vous traversez l’arborescence du haut vers le bas . Il fabrique des positions absolues en les calculant à partir des largeurs, là encore, 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’parsing, vous verrez qu’il y a une référence à un autre nœud d’parsing d’un type différent. c’est le nœud d’arbre vert.

Incidemment, ils sont appelés “arbres rouges / verts” car ce sont les couleurs des marqueurs de tableau blanc que nous avons utilisées pour dessiner la structure de données lors de la réunion de conception. Il n’y a pas d’autre sens aux couleurs.

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