Повторяются ли SyntaxNodes от Roslyn?

Question

Я принимаю взгляд на Roslyn CTP и, в то время как он решает подобную проблему к Expression tree API, как неизменны, но Рослины делают это совершенно иначе:

• Expression узлы не имеет никакого отношения к родительский узел, модифицируются с использованием ExpressionVisitor, и поэтому большие части могут быть повторно использованы.

• У Roslyn's SyntaxNode, с другой стороны, есть ссылка на его родителя, поэтому все узлы эффективно становятся блоком, который невозможно повторно использовать. Для внесения изменений предлагаются такие методы, как Update, ReplaceNode и т. Д.

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

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

Answer 1

ОБНОВЛЕНИЕ: Этот вопрос был the subject of my blog on June 8th, 2012. Спасибо за большой вопрос!

---

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

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

• Неизменный.
• Форма дерева.
• Недорогой доступ к родительским узлам из дочерних узлов.
• Возможна карта с узла в дереве до смещения символа в тексте.
• Постоянный.

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

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

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

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

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

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

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

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