Одна из самых интересных особенностей программирования - это невозможность заранее предсказать фактическую структуру программы в подавляющем большинстве случаев. Зачастую только при написании программы приходит понимание того, как программа должна работать. Поэтому когда я увидел честный и откровенный рассказ о том как работают программы форматирования кода, я понял что его нужно перевести. Так как сама стать и тем более перевод очень большие, то я разбил его на 2 части.
Самая сложная программа, которую я написал, состоит из 3,835 строчек кода. Написать эту горстку кода заняло у меня больше года. История коммитов говорит, что за это время я удалил 20,704 строчки. Таким образом, получается, что на каждую оставшуюся строчку было не меньше 3 погибших товарища.
Учитывая, как много удаленных строчек, можно ожидать, что я сделал что-то глубокое, так? Возможно это низкоуровневый интерфейс или хитрая графическая демка с кучей математики в стиле 90-х? Или даже дьявольская машина, которая создаст Скайнет?
Не угадали. Программа просто читает и пишет строчки. Единственное отличие между входной и выходной строкой в расстановке пробелов. Конечно, я говоря про форматирование кода.
Введение в dartfmt
Я пишу на Dart. Часть моей работы - это делать код Dart более понятным, читаемым и самодостаточным, поэтому я решил записать наш code style. Это была хорошая попытка, но каждый code style, написанный на английском, получается слишком коротким, чтобы все обхватить, и слишком длинным, чтобы его читали.
Gofmt из go показал лучший вариант: автоматически форматировать весь код. Код легче читать и писать, так как он уже в том виде в котором должен быть. Даже если форматирование не идеально, то все равно не возникает бесконечных споров при код ревью.
Конечно, я не отношусь к человеку для которого самое главное - это форматирование: суть прежде всего. С другой стороны, я достаточно трепетно отношусь к форматированию своего собственного кода, и я не стал бы советовать инструмент, которым я не пользуюсь сам.
Достаточное качество форматирование требует применения достаточно большого количества правил, что в свою очередь сказывается на производительности. Я понимал, что соблюдение баланса между скоростью и качеством - это сложная проблема, но я даже не мог представить насколько. Сейчас я доволен результатом: 2 миллиона строчек кода обрабатываются за 45 секунд на одном ядре.
Почему форматирование - это сложно?
В этот момент вы можете спросить, почему форматирование - это сложно? В конце концов, можно же перевести все в AST дерево, потом просто обойти его и расставить пробелы?
Если каждое выражение остается расположено на своей строке, то да. Но это только вершина айсберга. Мой форматер, кроме всего прочего, оставляет после себя только строки с ограниченной длинной. А это означает, что нужно вставлять переносы строк (разделять выражение на несколько), и определять лучший вариант переноса.
Посмотрите на этот вариант:
experimentalBootstrap = document.querySelectorAll('link').any((link) =>
link.attributes['rel'] == 'import' &&
link.attributes['href'] == POLYMER_EXPERIMENTAL_HTML);В этом варианте есть 13 мест, где можно поставит перенос строки в соответствии со стандартом кодирования: это 8,192 различных комбинации, если перебирать их все1. Это задача с экспоненциальным ростом сложности: даже просто проранжировать результаты - уже сложная проблема. Как лучше разделить код до или после .any()? А почему?
Сноски.
Когда я писал эту статью, я преследовал две цели: объяснить, как работает dartfmt, и показать, как на самом деле разработчики постепенно решают сложную задачу, состоящую из множества частей. Так как первая цель и так очень обширна, то я спрятал вторую за сносками. Нажимая на сноски вы сможете получить удовольствие наблюдая за моими неудачными решениями)
Работая с дартом, мы делаем вещи, которые не всегда можем понять. Мы используем анонимные функции, множество функций высокого порядка и,в конце концов мы добавили async и await, функции, которые работают в будущем для многопоточности. Все это означает огромное число длинных цепочек вызовов. Отдельные дарт-разработчики сильно углубились в функциональный стиль и кажется, что играют в игру, кто напишет самую длинную цепочку.
Это пример реального кода написанного любителем:
_bindAssignablePropsOn.forEach((String eventName) => node
.addEventListener(eventName, (_) => zone.run(() => bindAssignableProps
.forEach((propAndExp) => propAndExp[1].assign(
scope.context, jsNode[propAndExp[0]])))));Тут 4 вложенных функции и 1,048,576 способов форматирования. А это уже код написанный профессионалом:
return doughnutFryer
.start()
.then((_) => _frostingGlazer.start())
.then((_) => Future.wait([
_conveyorBelts.start(),
sprinkleSprinkler.start(),
sauceDripper.start()
]))
.catchError(cannotGetConveyorBeltRunning)
.then((_) => tellEveryoneDonutsAreJustAboutDone())
.then((_) => Future.wait([
croissantFactory.start(),
_giantBakingOvens.start(),
butterbutterer.start()
])
.catchError(_handleBakingFailures)
.timeout(scriptLoadingTimeout, onTimeout: _handleBakingFailures)
.catchError(cannotGetConveyorBeltRunning))
.catchError(cannotGetConveyorBeltRunning)
.then((_) {
_logger.info("Let's eat!");
});(Смешные имена в коде появились потому, что мы обработали код.) Это одно выражение, 565 символов и 549 миллиардов способов форматирования.
Форматировщик применит набор определнных правил, для того чтобы выбрать лучший вариант из экспоненциально растущего количества. Заметьте, что оценка "лучший" относится только к тому утверждению, которое будет отформатированно. Разрыв строки меняет отступ, что в свою очередь повлияет на все следующие строки. Тут нет места для динамического программирования2.
Как программа для форматирования видит ваш код
Как и следовало ожидать, программа для форматирования кода устроена почти так же, как и компилятор. У нее есть часть, которая парсит код, и часть, которая переводит результат в промежуточное представление3 4 5. Главные части в этом представлении - это чанки, правила и блоки.
Чанки
Чанки - это единицы форматированного текста. Они представляют из себя группы символов, которые не должны разрываться, например:
format /* comment */ this;Мы разорвем на чанки: format /* comment */ this;.
Чанки схожи с [токенами]() обычных компиляторов, но обычно они больше. Обычно текст заканчивается на какие-то определенные токены, например this или ;. Если разрыв строки не может быть вставлен между токенами, то его нужно поставить после токена.6
Обычно чанки небольшие, например:
some(nested, function(ca + ll))Мы можем разделить их так: some( nested, function( ca + ll)).
Мы могли бы рассматривать весь файл, как одну последовательность чанков, но тогда разбиенкие будет длиться слишком долго7. Для цепочки асинхронного кода одно утверждение может содержать сотни строчек кода в которых будут десятки встроенных функций и колекций, каждая из которых будет содержать свои кучи кода.
Мы не можем рассматривать эти встроенные функции полностью независимо, так как окружение влияет на их отступы. Это в свою очередь создает очень длинную строку для обработки.
Поэтому мы рассматриваем встроенные функции, как независимые кусочки, которые форматируются в зависимости только от своего кода, но встраиваются в зависимости от окружения. Чанки которые начинаются с символов { содержат список под чанков. Таким образом чанки образуют дерево, которое отражает вложенность одного блока перед другим.
Конец чанка помечается точкой в которой можно сделать разбиение в финальном коде, чтобы при этом чанк имел какой-то смысл. 8. При этом нужно проверять сколько пустых строчек нужно добавить между чанками (например между двумя определениями классов), какой отступ должен быть на следующей строке.
Самое важная информация в чанке - это правило, которое определяет его разбиение9.
Правила
Каждое потенциальное разбиение в программе определяется своим правилом. Например для цепочки сложений a + b + c + d использовать правило "разбивать по +".
Правила определяет как происходит разбиение. Оно определяет это на основе состояния, которое хранит, называемого значением. Задавая значения, вы определяете как чанки должны быть разбиты.
Самое простое правило полное разбиение. Оно говорит, что каждый чанк постоянно разбит, и значение этого правила 0. Это полезно для таких вещей как строки комментариев, после которых нужно поставить разбиение после чанка, даже если это середина выражения10.
Дальше идёт простое правило разбиения. У него есть 2 значения: 0 - значит, что ни один из его чанков не разбит, и 1 - которое означает, что все чанки разбиты. С тех пор как большинство разбиений независит друг от друга, то это правило используется для большинства разбиений.
Кроме этого есть еще правила особого случая. Они используются для тех мест, где необходим более тонкий контроль разбиения. Например для определения позиций аргументов фунции
function(first, second, third)После разбиения получаем блоки: function( first, second, и third). Все эти блоки будут управляться простым правилом, которое допускает следующие форматирования:
// 0: Don't split at all.
function(first, second, third)
// 1: Split before the first.
function(
first, second, third)
// 2: Split before only the last argument.
function(first, second,
third)
// 3: Split before only the middle argument.
function(first,
second, third)
// 4: Split before all of them.
function(
first,
second,
third)Наличие единого правила для всех аргументов в свою очередь запрещает следующее форматирование:
function(
first, second,
third)Сноски
1 Да, я на самом деле делал форматирование брут-форсом вначале. Это позволило сконцентрироваться на правильности кода, а не на быстродействии. Для большинства варинтов быстродействие было приемлимым, для остальных - для форматирования нужно было больше времени, чем существует вселенная.
2 В основном для форматирования используется динамическое программирование. Я чувствовал себя волшебником, когда понял как это сделать. Это работает очень круто, хотя отладка была кошмаром.
С течением времени, объем данных которые нужны для верного определения состояния подзадачи вырос и производительность решения становилась все хуже и хуже.
3 Система постоянно менялась. Спаны и правила добавлялись по мере необходимости. Даже способ, которым чанки отмечали свой отступ, менялся: изначально чанку ставилось в соответствие какое-то количество отступов, а каждый отступ был равен двум пробелам, потом чанку сразу ставились в соответствие пробелы.
В общем система балансировалась между простым парсеров и эффективной работой с представлением. Система форматирования строится так, чтобы работа с представлением была максимально эффективной.
4 Это одно из самых сложных мест. Изначально программа предполагала что в определенных местах не может быть разрывов и переносов строк. Кто может вставить перенос строки в инструкции abstract class? Тем не менее, никто не запрещает сделать так:
abstract // Oh, crap. A line comment.
class Foo {}Огромных усилий стоило добавление обработки таких мест, хотя все равно обработка строится на большом колличестве специальных правил.
5 Основная проблема в производительности возникла в части работающей с промежуточным представлением, потребовалось два раза переписать ее полностью, чтобы добиться преемлимых результатов.
6 Я начал с простейшего форматера, который обходил текст по пробелам и разделял его как будто он весь состоит из чанков. Я обощил это так, что каждый текст содержил непустой текст, информацию о своем разбиене и пустую информацию, если чанк не разбит.
7 Когда я дабоавил поддержку вложенных функций, это сломало код который разделяет функцию на независимые области. Поэтому некоторое время, оператор верхнего уровня считался неделимым, даже если он состоял из сотен строк кода. Это было очень долго.
8 В идеале, информация о разбиении, должна быть записана до самомго текста чанка. Это бы исправило ошибку отступа самого перевого фрагмента и избавило бы от необходимости хранить информаци о разбиении последнего фрагмента. Я пробовал сделать так много раз, но каждый раз возникали ошибки, и у меня не было столько времени, чтобы исправить их все.
9 Правила - это позднее нововведение. Изначально каждый чанк обрабатывался независимо. При этом можно было давать некоторые зависимости между ними, например "каждый чанк разбивается по тем же правилам, что и остальные". Однако такая система не позволяла сделать так "только в одном чанке из этих трех нужно сделать переносы". В конце концов, я понял, что такие конструкции нужны для форматирования аргументов функций. Тогда я сформулировал концепцию правил и ввел ее в код.
10 Сначала я думал, что нет необходимости в жестких разбиениях. Любая новая строчка может быть точкой разбиения чанков. Это работало прекрасно, кроме случая строчек с комментариями:
some(expression,
// with a line comment
rightInTheMiddleOfIt);