Mise à JOUR: Cette question a été l'objet de mon blog sur 8 juin 2012. Merci pour la grande question!
Grande question. Nous avons discuté des questions que vous soulevez pour un long, long temps.
Nous aimerions avoir une structure de données qui présente les caractéristiques suivantes:
- Immuable.
- La forme d'un arbre.
- Un accès bon marché aux nœuds parents de nœuds enfants.
- Possible à la carte à partir d'un nœud dans l'arbre pour un décalage de caractères dans le texte.
-
Persistant.
Par la persistance , je veux dire la possibilité de réutiliser la plupart des nœuds dans l'arbre lorsqu'une modification est apportée au texte de la mémoire tampon. Étant donné que les nœuds sont immuables, il n'y a pas de barrière pour les réutiliser. Nous avons besoin de ce pour la performance, on ne peut pas être ré-analyse énorme wodges du fichier à chaque fois que vous appuyez sur une touche. Nous avons besoin de re-lex et ré-analyser uniquement les parties de l'arbre qui ont été touchés par la modification.
Maintenant, quand vous essayez de mettre tous les cinq de ces choses dans une structure de données vous lancer immédiatement dans des problèmes:
- Comment faire un nœud en premier lieu? Le parent et l'enfant sont tous deux font référence les uns aux autres, et sont immuables, alors, qui se construit d'abord?
- En supposant que vous parvenez à résoudre ce problème: comment voulez-vous faire persistante? Vous ne pouvez pas réutiliser un nœud enfant dans un autre parent parce que cela impliquerait de dire à l'enfant qu'il a un nouveau parent. Mais l'enfant est immuable.
- En supposant que vous parvenez à résoudre ce problème: lorsque vous insérez un nouveau personnage dans le tampon d'édition, la position absolue de chaque nœud est associé à une position à partir de ce point les changements. De ce fait, il est très difficile de faire une persistance de la structure de données, car toute modification peut modifier la portée de la plupart des nœuds!
Mais sur le Roslyn équipe nous avons l'habitude de faire des choses impossibles. Nous faisons l'impossible en gardant les deux analyser les arbres. Le "vert" de l'arbre est immuable, persistante, n'a pas de parent références, est construit "bottom-up", et chaque noeud de pistes de sa largeur , mais pas sa position absolue. Lorsqu'une modification se produit, nous reconstruire, seules les parties de l'arbre vert qui ont été touchés par la modification, qui est typiquement de l'ordre de O(log n) du total analyser les nœuds dans l'arbre.
Le "rouge" de l'arbre est un immuable de la façade qui est construit autour de l'arbre vert; il est construit "top-down" sur la demande et que l'on jette sur tous les modifier. Il calcule parent références par la fabrication à la demande lorsque l'on descend dans l'arborescence à partir du haut. Il fabrique des positions absolues par le calcul de la largeur, de nouveau, que l'on descend.
Vous, l'utilisateur, sans ne jamais voir le rouge de l'arbre; l'arbre vert est un détail d'implémentation. Si vous les pairs dans l'état interne d'un parse nœud, vous aurez en fait voir qu'il y a une référence à un autre analyser nœud d'un type différent; c'est le vert nœud de l'arborescence.
D'ailleurs, on les appelle les "rouge/vert des arbres", parce que ceux qui ont été le marqueur tableau blanc couleurs que nous avons utilisé pour dessiner la structure de données dans la conception de réunion. Il n'y a pas d'autre sens pour les couleurs.
L'avantage de cette stratégie est que nous ayons toutes ces grandes choses: l'immuabilité, la persistance, la mère de références, et ainsi de suite. Le coût est que ce système est complexe et peut consommer beaucoup de mémoire si le "rouge" façades deviennent grands. Nous sommes à l'heure actuelle de faire des expériences pour voir si nous pouvons réduire les coûts sans perdre les avantages.
