Повторяются ли SyntaxNodes от Roslyn? - программирование

Я смотрю Roslyn CTP и, хотя он решает аналогичную проблему с API дерева выражений, оба неизменяемы, но Roslyn делает это совершенно по-другому:

Expression узлы не имеют ссылки на родительский node, модифицируются с помощью ExpressionVisitor и поэтому большие части могут быть повторно использованы.
Roslyn SyntaxNode, с другой стороны, имеет ссылку на своего родителя, поэтому все узлы эффективно становятся блоком, который невозможно повторно использовать. Для внесения изменений предлагаются такие методы, как Update, ReplaceNode и т.д.

Где это заканчивается? Document? Project? ISolution? API поддерживает пошаговое изменение дерева (вместо кнопки вверх), но делает ли каждый шаг полную копию?

Почему они сделали такой выбор? Есть ли какой-то интересный трюк, который мне не хватает?

Ответ 1

UPDATE: этот вопрос был тема моего блога 8 июня 2012 года. Спасибо за отличный вопрос!

Отличный вопрос. Мы обсуждали вопросы, которые вы поднимаете в течение долгого времени.

Мы хотели бы иметь структуру данных, которая имеет следующие характеристики:

Неизменный.
Форма дерева.
Дешевый доступ к родительским узлам из дочерних узлов.
Возможно сопоставление с node в дереве с смещением символов в тексте.
Persistent.

По стойкости я имею в виду возможность повторного использования большинства существующих узлов в дереве, когда редактирование делается в текстовом буфере. Поскольку узлы являются неизменными, нет никаких препятствий для их повторного использования. Нам это нужно для производительности; мы не можем повторно разыгрывать огромные искажения файла каждый раз, когда вы нажимаете клавишу. Нам нужно повторно lex и повторно проанализировать только части дерева, на которые повлияло изменение.

Теперь, когда вы пытаетесь поместить все пять из этих вещей в одну структуру данных, вы сразу сталкиваетесь с проблемами:

Как вы строите node в первую очередь? Родитель и ребенок оба ссылаются друг на друга и неизменны, и какой из них сначала создается?
Предположим, что вам удастся решить эту проблему: как вы это делаете? Вы не можете повторно использовать дочерний элемент node в другом родителе, потому что это связано с сообщением ребенку, что у него есть новый родитель. Но ребенок неизменен.
Предположим, что вам удастся решить эту проблему: когда вы вставляете новый символ в буфер редактирования, абсолютная позиция каждого node, которая отображается в позицию после этой точки, изменяется. Это затрудняет создание постоянной структуры данных, поскольку любое редактирование может изменять длины большинства узлов!

Но в команде Roslyn мы обычно делаем невозможные вещи. Мы фактически делаем невозможное, сохраняя два дерева разбора. "Зеленое" дерево неизменно, постоянно, не имеет родительских ссылок, построено "снизу вверх", и каждый node отслеживает его ширину, но не ее абсолютную позицию. Когда происходит редактирование, мы восстанавливаем только части зеленого дерева, на которые повлияло редактирование, которое обычно составляет около O (log n) общих узлов синтаксического разбора в дереве.

"Красное" дерево - неизменный фасад, который построен вокруг зеленого дерева; он построен по принципу "сверху вниз" по запросу и отбрасывается при каждом редактировании. Он вычисляет родительские ссылки, производя их по требованию, когда вы спускаетесь через дерево сверху. Он производит абсолютные позиции, вычисляя их по ширине, опять же, когда вы спускаетесь.

Вы, пользователь, только когда-либо видите красное дерево; зеленое дерево - это деталь реализации. Если вы заглянете во внутреннее состояние анализа node, вы действительно увидите, что существует ссылка на другой синтаксис node в другом типе; что зеленое дерево node.

Кстати, они называются "красными/зелеными деревьями", потому что это были цвета маркеров доски, которые мы использовали для создания структуры данных на проектной встрече. Нет никакого другого значения для цветов.

Преимущество этой стратегии состоит в том, что мы получаем все эти великие вещи: неизменность, настойчивость, родительские ссылки и т.д. Стоимость заключается в том, что эта система сложна и может потреблять много памяти, если "красные" фасады становятся большими. В настоящее время мы проводим эксперименты, чтобы выяснить, можем ли мы сократить некоторые из расходов без потери преимуществ.