Это вторая часть перевода потрясающей статьи The Hardest Program I've Ever Written. В этой части рассказывается про подходы, которыми руководствуется скрипт форматирования dartfmt.
Ограничения
Объединение нескольких точек разбиений в одно правило помогает предотвратить появление неверных конфигураций в фактическом разбиении файла. Однако этого недостаточно: нам нужно было получить возможность для конструкицй типа "если точка разбиения попадает в список, то нужно разбить весь список тоже". Это поможет избежать такой ситуации:
[first, second +
third, fourth]В этом примере и список, и + имеют свои собственные правила разбиения, и мы должны совместить эти правила. То есть правила могут ограничивать друг друга. Обычно, это нужно для того чтобы ограничивать правила, которые наложены на внутренние конструкции правилами примененными ко внешним конструкциям[11]().
Кроме того, применение каждого правила имеет свою стоимость. Поэтому ограничения помогают нам определять какие наборы разбиений лучше, а какие хуже[12]().
Группа
Группа отмечает серию чанков, которые мы не хотим разбивать. Я предствляю это, как скотч которым связаны элементы. Если разбиение попадает внутрь группы, то группа считается сломанной. Это значит, что к стоимость разбиения нужно добавить дополнительную плату за сломанную группу.
Группа может объединять элементы любой ступени вложенности:
function(first(a, b), second(c, d))В этом примере несколько групп: одна объединяет a и b, вторая - c и d, третья - first(a, b), second(c, d), как аргументы функции. При этом, если точка разбиения будет между a и b, то сломаются сразу две группы.
Парсер исходного кода
Превращение исходного кода во внутреннее представление - это достаточно простая вещь. Для этого мы используем прекрасный анализатор, который возвращает нам AST дерево. В отличии от большинства AST деревьев, мы в дереве содерржим комментарии.
После получения дерева, начинается его обход с выделение отдельных чанков и групп, в соответствии с различными грамматическими правилами. В этом нет ничего сложного, но при этом учитывается большое количество эмпирических правил. Например иногда комментарии бывают в очень странных местах:
function(argument, // comment
argument)Обычно в такой ситуации нам нужно поставить перенос после первого аргумента функции, однако так как после , стоит комментарий, то мы помечаем его как место, после которого нужно ставить перенос.
Пробелы расставляются автоматически при проходе AST дерева. После первого прохода AST дерево превращается в дерево чанков с расставленными между ними пробелами.
Форматирование чанков
Таким образом мы получаем огромное дерево чанков. Работать с ним напрямую невозможно, так как даже небольшое количество кода приводит к экспоненциальному росту правил, которые могут описать форматирование. Поэтому первое что нужно сделать - это разделить дерево на независимые регионы. Каждый регион представляет собой кусок кода, который не будет влиять на другие регионы, при этом мы проверяем, что разбиение на регионы не может попасть внутрь какого-то выражения.
Каждый из этих регионов попадает в разделитель строк, который выбирает наилучший набор правил, для всех чанков в строке. Если строка попадает на экран целиком, то ничего не нужно делать. Если строка не помещается на экран целиком, то выбирается такая комбинация правил которая даёт лучший результат. Это могут быть:
- Набор правил при котором минимальное число символов нарушает ограничение по длинне строки
- Набор символов при котором получается минимальная стоимость
Однако даже для небольшого набора правил проверить все возможные комбинации грубым перебором не представляется возможным.
Как работает разделение по строкам
Как у любого человека, который бросил коледж, мои знания о алгоритмах элементарны. Поэтому перед интервью в гугл, я потратил два дня зубря алгоритмы работы с графами - в основном по обходу графов.
На интервью мне дали множество вопросов про оптимальные алгоритмы обхода графов. В то время, я считал, что это никогда не пригодится мне в моей работе...
После этого работая в гугл, я несколько лет открывал для себя, что каждая программа которую я пишу, может быть упрощена до поиска по какому-то графу[13](). Графы всюду среди нас. Сейчас даже во сне я могу написать BFS.
После нескольких неудачных вариантов, я понял, что разбиение строк может быть реализовано, как оптимальный поиск в графе. Каждый узел в графе представляет собой какое-то решение - набор правил. Решения могут быть частичными - какие-то правила могут быть не пременены.
От начального решения(ни одно правило не применено) существует ветка к новому решению. Каждая ветка добавляет одно правило к набору. Начав с начального набора и идя до конца, мы найдем позиции, где все правила будут премененны.
Поиск по графу прекрасно решается, если вы знаете направление и конечную точку, которую вам нужно достигнуть. К сожалению, в данной задаче мы не знаем конечную точку(иначе мы бы сразу ее написали).
После нескольких попыток, я построил дерево, которое находит нужное решение быстро. Мы пытаемся минимизировать две переменные одновременно:
- Мы пытаемся уменьшить количество символов, которые выступают за нужную длинну строки.
- Мы пытаемся найти решение с минимальной стоимостью
Первое ограничение более важно чем второе. Но на практике, мы ищем решение с минимальной стоимостью, а первое ограничение используем как условие выхода из поиска[14]().
Изначально, мы не знаем, стоимость наилучшего решения, однако мы знаем, что применение любого правила разбиения всегда увеличивает стоимость.
Если расматривать начальное решение, как решение с нулевой стоимостью, то каждое примененное правило будет увеличивать стоимость. Поэтому мы можем исследовать решения и правила по тому, как они увеличивают стоимость.
Это дает нам возможность использовать поиск в глубину. Если мы получили, что ограничение на длинну строки выполнено, то решение которое мы нашли будет оптимальным. Как только мы нашли первое подходящее решение, мы останавливаем поиск.
Уход от тупиковых решений
Все что написано выше звучит очень многообещающе, но может существовать большое число дешевых перегруженных решений. Когда алгоритм попробует разбить строку, ему придется перебрать их все. В конце концов, если решение дешевое, то оно не содержит большого количества разбиений.
Мы не хотим тратить время на ненужные разбиения. Например:
// Blog-friendly 40-char line limit: |
function(
firstCall(a, b, c, d, e, f, g, h),
secondCall("very long argument string here"));
Тут существует целая ветка разбиений связанных с firstCall(). Но на самом деле мы не должны смотреть их, потому что проблема есть только с secondCall().
Поэтому, когда мы смотрим на возможные группы решений, мы должны смотреть только те решения, которые влияют на слишком длинные строки. [16]()
Такой подход позволяет кардинально улучшить результаты. Даже если в текущем решени существует множество возможных правил, будет только небольшое количество разбиений, которые влияют на длинные строки.
Вывод ошибочных веток
Однако может сложиться ситуация, в которой форматер уйдет слишком глубоко в анализе отдельных веток. Обычно такая проблема возникает при анализе большого выражения состоящего из множества независимых частей. Например вот таком:
// Blog-friendly 40-char line limit: |
new Compiler(
assertions: options.has('checked-mode'),
annotations: options.has('annotations'),
primitives: options.has('primitives'),
minify: options.has('minify'),
preserve: options.has('preserve'),
liveAnalysis: check(options.has('live'), options.has('analysis')),
multi: options.has('multi'),
sourceMap: options.has('source-map'));Разбить эти аргументы можно множеством путей. И так как все они менее вложены чем liveAnalysis:, то вначале будут перебраны все варианты до того, как система дойдет до разбиения check().
Лучший способ разбить строку liveAnalysis: - это разбить ее в соответствии с теми же правилами что и строку с assertions: или annotations:. Другими словами, хотя разбиение длинной строки и отличается от разбиения короткой строки, но система должна прийти к использванию того же разбиения.
Для решения этой проблемы, нужно уметь сравнивать ветки решений. То есть мы можем сказать "ветка решений A лучше, чем ветка решений B", если каждое решение из ветки A превосходит любое решение из ветки B.
После некоторой работы, я понял что можно сделать сравнение ветвей в множестве случаев, например:
- если у двух решений есть одинаковый набор неиспользованных правил, но разная стоимость решений(связнная с тем, что правила применялись в разном порядке)
- Не одно из примененных правил не затрагивает строчки, которые будут обработаны необработанными правилами
- Не одно из примененных правил не ограничивает непримененные правила
Если все три условия выполняются, то ветка с более низкой стоимостью лучше более дорогой. Как только я реализовал эту логику, программа смогла форматировать любой объем кода за приемлемое время[17]().
Аварийное прерывание
Обычно, решения "где-то рядом" достаточно. Есть очень небольшое количество случаев, когда форматер работает долго. Например один раз я видел это на коде, который был написан другим скриптом:
class ResolutionCopier {
@override
bool visitClassDeclaration(ClassDeclaration node) {
ClassDeclaration toNode = this._toNode as ClassDeclaration;
return javaBooleanAnd(
javaBooleanAnd(
javaBooleanAnd(
javaBooleanAnd(javaBooleanAnd(javaBooleanAnd(
javaBooleanAnd(javaBooleanAnd(
javaBooleanAnd(javaBooleanAnd(javaBooleanAnd(
_isEqualNodes(node.documentationComment,
toNode.documentationComment),
_isEqualNodeLists(
node.metadata, toNode.metadata)),
_isEqualTokens(node.abstractKeyword,
toNode.abstractKeyword)), _isEqualTokens(
node.classKeyword, toNode.classKeyword)),
_isEqualNodes(
node.name, toNode.name)), _isEqualNodes(
node.typeParameters, toNode.typeParameters)),
_isEqualNodes(
node.extendsClause, toNode.extendsClause)),
_isEqualNodes(
node.withClause, toNode.withClause)), _isEqualNodes(
node.implementsClause, toNode.implementsClause)),
_isEqualTokens(node.leftBracket, toNode.leftBracket)),
_isEqualNodeLists(
node.members,
toNode.members)),
_isEqualTokens(
node.rightBracket,
toNode.rightBracket));
}
}Да, добро пожаловать в ад). Для того чтобы избежать этого используется аварийное прерывание: если скрипт просмотрит 5000 решений, то будет выбрано то у которого будет минимальная стоимость.
Заключение
После того как выбрано применение всех правил, все остальное легко. Форматер ходит по дереву и выводит текст, когда нужно вставляет пустую строчку(или две) и добавляет отступ.
В результате появляется красивая (я надеюсь) строка с кодом Dart. Вот так много всего нужно для того чтобы просто добавлять пробелы.
Сноски
11 Изначально использовался отдельный класс "суперразбинение", который раскалывал внешнее выражение так же, как было разбито внутреннее. Но после введения правил, от этого стало возможным отказаться, введя ограничения.
12 Я потратил очень много времени, чтобы оттюненговать стоимости, для различных выражений. Целью было создать такую стоимость, чтобы расщепление шло по самым общим местам в коде.
Тюненговать стоимость - это кошмар: поправляешь одно число и все остальные становятся опять несбалансированным. В какой-то момент я понял, что если я сделаю стоимость дробным, то я вообще могу сойти с ума.
13 Я знал, что clang-format работает похожим образом, но я не мог придумать как применить это к dart. Я достаточно долго пытался придумать как можно сделать правильный граф оптимизируя сразу два числа. В конце концов, я вывел правильную характеристику и все стало получаться.
14 Долгое время слишком длинные символы участвовали в стоимости: для каждого символа, который выступал за ограничения, ставилась дополнительная большая плата.
Переход на построение графа разбиения, как независимой метрики, позволил отказаться от дополнительной стоимости за выступающие символы.
16 Я попробовал наверное миллион способов сравнения групп решений, пока нашел верный способ их сравнивания.
17 Исключения самопересечений решений является очень тонкой оптимизацией. Корректное определение когда две ветки решения пересекаются требует много действий.