Я уже где-то про них писал, но не могу найти ту тему. Всё равно мне на неё никто не ответил.

В общем смысл такой:
- существует (в мире Java) самый передовой в мире парсер Antlr с алгоритмом ALL(*)

его альтернативной (в мире C#) является ещё более продвинутая платформа парсинга Roslyn (под лицензией Apache 2.0)
Microsoft Visual Studio 2015 was completely redesigned to use the .NET Compiler Platform. Refactorings, diagnostics, code fixes, find references, go to definition and so on are re-implemented using Roslyn.

Вот в этом рослине и применяются красно-зелёные деревья.

Из смысл в том, что при редактировании текста он сьезжает (позции меняются), поэтому синтаксические узлы разделены на две части - зелёную, которую можно сохранить, и красную, которая при сьезжании пересоздаётся (хм, а просто индекс нельзя было поправить?).

см. также
  https://wiki.haskell.org/Zipper
  BCL immutable collections

2012-08-26, русский перевод, Персистентность, фасады и красно-зеленые деревья в Roslyn
    2012-06-08, Eric Lippert, Persistence, Facades and Roslyn’s Red-Green Trees

class SyntaxNode - http://source.roslyn.codeplex.com/ #Microsoft.CodeAnalysis/Syntax/SyntaxNode.cs,849dc6029695ef7b

part of the reason for making these nodes immutable was so they could be used from multiple threads without need for any locks (or even for lock-free techniques, for that matter). But if the red nodes are created on demand, I take it that must mean you *do* have some locking around that lazy-creation?
I've heard rumors about Roslyn being parallel, but have never seen definitive information about that. What parts of Roslyn can run in parallel? Parsing? Typechecking? IL emission? Are there any benchmarks that compare Roslyn-based compilers with old ("native") ones?

https://roslyn.codeplex.com/discussions/541953

As you may notice from descriptions and from the actual implementation, green nodes are immutable and self-contained. In particular, green node does not know its position in text and does not know its parent. As a result the same green node for "2 - 2 " can represent any occurrence of "2 - 2 ", - as long as it is parses into identically shaped green sub-tree, why not just use the same sub-tree?
That is achieved in green node factories - before creating a green node for "2 - 2 " the factory will check if it has already seen a binary expression with same children "2 ", "- ", "2 " and if answer is yes, the it will just return a cached node. One can see it as a kind of memorization.

a very large fraction of nodes in the green tree are tokens - terminal nodes like punctuation, keywords, identifiers, literals. They are also ones with the most repetitions - once you use variable "x" in code you are likely to use it more than once.

Red nodes are the public façade to the syntax model. Unlike a green node, red node:
    knows its location span in the tree
    knows not only children, but the parent too
    knows the syntax tree to which the node belongs.

red nodes cannot be reused within a tree (all nodes have different spans) or between trees (different parents). The problem arises – if there is a red tree for every version of the text, how can we afford a new tree every time when user types a character? The solution is to build the red tree lazily.

Laziness helps tremendously in scenarios like typing. - When user is furiously typing, no one has the time or need to examine the entire red tree. Once user types another character the current tree becomes irrelevant and any analysis, if started, tend to be cancelled and restarted with the new tree (often with a small delay – in case user will continue typing, no need to start anything too eagerly). As a result intermediate red trees, while fully "available", will generally see only a tiny fraction of nodes realized.

Red nodes are remembered by their parent red nodes in most circumstances and the root is held by the syntax tree, so they are shared by all users of the same tree instance, but are not otherwise cached.

There is a "new tree" for every edit, but remember that most of the green nodes are shared across successive edits. If the tree is of depth 'h', then on average only new O(h) green nodes are created. There could be a distinct red node in each version of the tree, but red nodes are created lazily

We do cache trees, based on the contents of the file, but it isn't an unlimited cache. On undo (or any edit) we check if a tree corresponding to the editor's content exists, and use it if it does, or else create a new tree with the incremental lexer and parser. Any time we create a new tree, we add it to the cache, which may cause other, less used trees to be evicted from the cache.

https://github.com/dotnet/roslyn/issues/6296

Отредактировано Лис (2017-07-10 12:09:41)