С введением причин для минусов к статье начинаешь пытаться искать корни проблемы.
Я не до конца понимаю, почему несколько людей отметили материал меткой "Низкий технический уровень материала". Если это более заметно со стороны, мне честно было бы интересно узнать, что подрывает техническую сторону статьи.
Эта статья по оценкам получилась провальной и демотивирует в том числе то, что я не знаю, как можно было бы сделать лучше.
Код в gist'е понятен (спасибо, что скинули его в дополнение к коду Вирта, иначе было бы сложнее). Мне субъективно больше нравятся парсеры Пратта тем, что там, на мой взгляд, лучше разделена логика парсинга.
Есть ещё возможность динамически определять грамматику и дополнять её программно: почти вся логика парсера сосредоточена в отображениях {токен => обработчик}. Не то, чтобы очень мне лично было полезно, но, выражаясь по-английски, it's fascinating. :)
P.S. — удалил из статьи абзац, который вы цитировали в первом комментарии. :)
В конце статьи я ссылаюсь на Pratt Parsers: Expression Parsing Made Easy . В целом, я старался в одно предложение выразить это:
You can do this with recursive descent, but it’s a chore. You have to write separate functions for each level of precedence (JavaScript has 17 of them, for example), manually handle associativity, and smear your grammar across a bunch of parsing code until it’s hard to see.
Зачем я это вообще пытался добавить? Изначально это планировалось переводом, а потом уже осталось как артефакт после множественных редактирований.
Алгоритм Пратта — тоже рекурсивный спуск, просто с определённым подходом (расширением?), чтобы более красиво обработать произвольные выражения.
Если без какой-то системы делать, парсер будет выглядеть как запутанный код.
Конкретных примеров под рукой нет, но почти все мои первые парсеры с рекурсивным спуском были ужасны. Я даже не уверен, что они правильно обрабатывали приоритеты операций, кажется, для этого я использовал Shunting-yard, который тоже мне не с первого дня дался. До ассоциативности я, возможно, в те дни даже не доходил. :)
Парсеры Пратта довольно аккуратно решают эту проблему.
Но опять же, возможно вы очень опытный специалист в области парсинга, тогда любой ваш парсер будет хорошо выглядеть. Но это не означает, что концепции рекурсивного спуска достаточно, чтобы написать всё элегантно.
Может, стоило написать, что создать хороший парсер выражений по одному лишь описанию рекурсивного спуска можно, но это требует или опыта, или дисциплины.
Аргументы в пользу использования генератора парсеров (имхо):
У вас уже есть грамматика на руках.
Вам важна производительность парсера.
Сложно написать парсер вручную.
Хотя стоит заметить, goyacc не генерирует слишком быстрый парсер, там будет очень много аллокаций. Но может его нужно просто правильно готовить.
То есть:
Да, можно.
Смотрите по ситуации.
Хотя бы разок написать парсер ручками точно полезно. :)
Потом это быстро надоест и вы будете уже более взвешенный выбор принимать, зная плюсы и минусы обоих подходов.
А ещё алгоритм Пратта — это не новый подход. :)
Но он вроде бы не очень популярен.
Так что я думаю польза для разработчиков может быть хотя бы из того, что можно подсмотреть в код и позаимствовать некоторые идеи.
Я постарался собрать список других проектов, которые так или иначе используют шаблоны для статического анализа. Можно туда так же добавить расширения ES Lint и подобные, но всё-таки там не AST-шаблоны, а своеобразный DSL из ключей-значений.
Также несколько раз делались разборы Open-Source проектов через NoVerify, после чего меинтейнерам отправлялись патчи с исправлениями багов. Тоже некоторая польза сообществу. :)
С моим опытом не согласуется, но минус за комментарий (не в карму) я поставил из-за того, что ваш комментарий довольно кусачий и некоторых может незаслуженно обидеть.
Решил дать вам знать. Возможно, кто-то еще поставил минус по той же причине.
Правильно ли я понимаю что старый ABI оставят только для ассемблерных функций?
По обсуждениям похоже на то, что как минимум планируется дать возможность указать у Go функции её ABI через магический комментарий (//go: прагму). Но я могу что-то упустить, там многовато сообщений. :)
Но для ассемблерных функций точно будет по умолчанию старый. Когда появится ABI1, видимо, его можно будет проставить через флаги ассемблерной функции.
Это действительно не самое оптимальное решение, но регистровая CC пока не дала прироста больше 5-10% на (синтетических) тестах, что неплохо для более-менее зрелого компилятора, но не так супер много, чтобы бить тревогу. :)
Go's calling convention as of Go 1.11 is simple and nearly universal across platforms, but also inefficient and inflexible. It is rife with opportunities for improving performance. For example, experiments with passing arguments and results in registers suggest a 5% performance win.
(Ниже только субъективные догадки.)
Видимо, простота для реализации и универсальность на большом количестве платформ. была достаточно хорошей причиной. Там не только даже в компиляторе дело, у Go есть GC и ему надо уметь работать с "локальными" данными (регистры и стек), чем сложнее логика CC и чем более она разная между платформами, тем сложнее будет реализация (или придётся больше платформозависимого кода писать). Рантайму, возможно, тоже проще с трейсами работать.
В последний раз у меня такая задача была года 3 назад и вроде бы отчасти решалось через компиляцию Go в c-archive.
Но гораздо надёжнее (если это возможно) инверсировать поток управления и сделать runtime Go основным, а C++ код уже оттуда использовать. Именно поэтому примеров такого подхожа и больше, сделать это корректно попроще, чем встроить Go в другое приложение. :)
Продолжение планировалось к публикации через неделю-две после первой части, к сожалению, у меня сейчас очень мало свободного времени и мотивации.
Изначально это вообще должно было быть одной большой публикацией, но я быстро понял, что сил дотянуть до полноценной статьи не хватит, вот и разделил на две части, выложив то, что уже было.
Статья интересная. Часто черпаю вдохновение из вашего блога, а потом адаптирую идеи для своих анализаторов.
(Ниже комментарий про Go, но концепция не привязана к нему, уже есть для PHP похожая реализация, остальные языки — тоже не проблема.)
Для сравнения, в ruleguard правило для "x==x" выглядело бы так:
m.Match(`$x == $x`).
Where(m["x"].Pure).
Report(`suspicious identical LHS and RHS`)
Условие pure нужно в основном для избежания false positives в случаях, где у нас $x — это выражение с побочными эффектами, типа вызова функции, которая модифицирует глобальный state.
Const folding ещё не доделан, но запланирован, поэтому эквивалентность x[0] и x[1-1] будет учтена.
В match через запятую можно перечислить остальные шаблоны, например $x != $x:
Хотя в PVS-Studio не так много синтаксических проверок, в основном самые лучшие — это связанные с data flow, что через шаблоны представить пока трудно. Но в CodeQL он есть, и там тоже похожая концепция поиска кода через запросы с условиями.
А дальше нужно понять, кто эту лишнюю копию удаляет: при каких условиях, точно ли удаляет, а не заменяет на что-то хитрое (я там видел вызовы DUFFCOPY на размер меньший массива при некоторых N, не сразу понятно, что это). Это может быть как в том же фронтенде (gc), либо в ssa.
Из комментария "array ranges use value multiple times. make copy." как будто бы следует, что эта копия им нужна, чтобы сгенерировать код, который обращается к этой "переменной" (на уровне кодогенерации) для взятия n-го элемента внутри цикла. То есть:
for i, v := range arr { <range body> }
Превращается во что-то типа:
{
tmp := arr // Вот здесь по семантике Go копирование массива
tmp_i := 0
for tmp_i < len(tmp_arr) {
i, v = tmp_i, tmp_arr[tmp_i]
<range body>
}
}
(Я слегка упростил.)
ha уже может быть копией после order.go.
Гипотетически, этой копии можно избежать, если мы можем доказать, что ha не изменяется. Это сложно, если ha — глобальная переменная. Для локальных массивов, наверное, и сейчас кто-то успешно копию удаляет.
В новых версиях компилятора, возможно, ввели оптимизацию при каком-то размере массива, надо посмотреть. Моя информация примерно годичной давности, но до ~1000 байтах копирование всё ещё есть.
Лучше в код компилятора посмотреть, конечно. Скорее всего, ответ стоит искать в cmd/compile/internal/gc. Если вдруг разберётесь, можете здесь написать ответ, думаю, многим полезно будет (в том числе мне).
Сам пример с arrayExprCopy был примером того, что можно детектировать через правила и что правится 1-им символом. Альтернативный фикс — делать слайс от массива, чтобы цикл шёл уже по слайсу.
(Про то, как трактовать тот параграф в спеке можно порассуждать, но ценность не очень высокая. Я на 100% не могу утверждать, но это та интерпретация, которую я видел в нескольких обсуждениях.)
Если отбросить спеку в сторону, так как не понятно, как её правильно читать, то a[i] имеет семантику, как в C. У нас массив — это просто указатель и длина только на этапе компиляции хранится. Чтобы взять элемент, копирования не нужно.
А в случае цикла иногда копия лучше, посмотрите мой update, пожалуйста:
Насколько мне известно, там ещё 1 нюанс есть: если массив маленький, по копии пройти может быть быстрее, потому что тогда у нас будет a[i] для доступа к элементу, который на каждой итерации генерируется для range value. А если это указатель, то будет (*a)[i] (массив — это указатель на данные под капотом, а указатель на массив будет указателем на указатель).
Там банально не так очевидно, стоит ли всегда оптимизировать.
При этом x должен быть addressable, чтобы от него можно было взять адрес. Если там вызов функции, то уже не прокатит.
Я не вижу в спеке информации о том, что for/range копирует свой аргумент. Можете процитировать, где это сказано?
В спеке явно не написано, но вот из этого выводится:
The range expression x is evaluated once before beginning the loop, with one exception: if at most one iteration variable is present and len(x) is constant, the range expression is not evaluated.
Если x — это массив, то его "evaluation" в контексте выражений — это копирование.
А вот почему нет копирования, когда используется только 1 range value, это отдельно описано:
If at most one iteration variable is present, the range loop produces iteration values from 0 up to len(a)-1 and does not index into the array or slice itself.
Прочитайте внимательно For statements with range clause, взял оттуда.
И чинить это в компиляторе никто не планирует (и чтобы не усложнять его, и потому что range по большим массивам это не такая уж частая ситуация), поэтому предлагается "оптимизировать" это вручную разработчикам.
А вот программы, производительность которых немного улучшится от этого изменения — скорее всего есть, и их немало.
Вы сами предположили, что это редкий кейс. Я могу это подтвердить, он реально редкий и проверял я на Go корпусе при тестировании go-critic, где эта диагностика есть. Имхо, это такой редкий зверь, что даже нашего диалога не стоит.
Я не буду говорить, хорошо это или плохо, что в gc компиляторе неохотно делают оптимизации, которые:
a) срабатывают очень редко и легко правятся в коде (явно, в 1 символ)
b) когда цикл работает 1 раз в каком-нибудь init, то разницы нет, есть эта оптимизация или нет
Такая вот политика. Она может нравиться или не нравиться, нам об этом спорить толку мало.
Насколько мне известно, там ещё 1 нюанс есть: если массив маленький, по копии пройти может быть быстрее, потому что тогда у нас будет a[i] для доступа к элементу, который на каждой итерации генерируется для range value. А если это указатель, то будет (*a)[i] (массив — это указатель на данные под капотом, а указатель на массив будет указателем на указатель). Мне больше нравится подход, где мы говорим программисту: "здесь может быть что-то подозрительное, разберись, пожалуйста" (как это делает go-critic).
И чинить это в компиляторе никто не планирует (и чтобы не усложнять его, и потому что range по большим массивам это не такая уж частая ситуация), поэтому предлагается "оптимизировать" это вручную разработчикам.
В общем, вы правы, но тут "чинить" не очень корректное слово. Это не баг, а поведение по спеке. Плюс, как вы уже тоже отметили, это редкий кейс, но если он появляется в программе, есть шанс, что это была ошибка программиста, а фикс очень простой...
Если "починить", сломается код, который ожидает, что массив копируется. Эти программы корректные по спецификации языка.
Если копию не делать, конкуррентные программы могут измениться. Можно, конечно, делать анализ, не доступен ли массив для такого доступа, но чаще всего массивы для оптимизаций — глобальны, а Go слабовато пока такое оптимизирует и анализирует. И не факт, что когда-либо gc (компилятор от Google) будет такое делать, потому что есть требование держать время компиляции под контролем, а флаги -O они не хотят.
На afterparty планируем делать live выпуск GenericTalks.
Это если кому-то захочется переключиться с основной комнаты для обсуждений.
С введением причин для минусов к статье начинаешь пытаться искать корни проблемы.
Я не до конца понимаю, почему несколько людей отметили материал меткой "Низкий технический уровень материала". Если это более заметно со стороны, мне честно было бы интересно узнать, что подрывает техническую сторону статьи.
Эта статья по оценкам получилась провальной и демотивирует в том числе то, что я не знаю, как можно было бы сделать лучше.
Спасибо, весьма познавательно.
Код в gist'е понятен (спасибо, что скинули его в дополнение к коду Вирта, иначе было бы сложнее). Мне субъективно больше нравятся парсеры Пратта тем, что там, на мой взгляд, лучше разделена логика парсинга.
Есть ещё возможность динамически определять грамматику и дополнять её программно: почти вся логика парсера сосредоточена в отображениях
{токен => обработчик}. Не то, чтобы очень мне лично было полезно, но, выражаясь по-английски, it's fascinating. :)P.S. — удалил из статьи абзац, который вы цитировали в первом комментарии. :)
В конце статьи я ссылаюсь на Pratt Parsers: Expression Parsing Made Easy . В целом, я старался в одно предложение выразить это:
Зачем я это вообще пытался добавить? Изначально это планировалось переводом, а потом уже осталось как артефакт после множественных редактирований.
Алгоритм Пратта — тоже рекурсивный спуск, просто с определённым подходом (расширением?), чтобы более красиво обработать произвольные выражения.
Если без какой-то системы делать, парсер будет выглядеть как запутанный код.
Конкретных примеров под рукой нет, но почти все мои первые парсеры с рекурсивным спуском были ужасны. Я даже не уверен, что они правильно обрабатывали приоритеты операций, кажется, для этого я использовал Shunting-yard, который тоже мне не с первого дня дался. До ассоциативности я, возможно, в те дни даже не доходил. :)
Парсеры Пратта довольно аккуратно решают эту проблему.
Но опять же, возможно вы очень опытный специалист в области парсинга, тогда любой ваш парсер будет хорошо выглядеть. Но это не означает, что концепции рекурсивного спуска достаточно, чтобы написать всё элегантно.
Может, стоило написать, что создать хороший парсер выражений по одному лишь описанию рекурсивного спуска можно, но это требует или опыта, или дисциплины.
Есть как минимум 2 версии
goyacc. Та, на которую вы ссылаетесь и более новая: https://gitlab.com/cznic/goyacc.Реальное применение можно увидеть в проекте github.com/z7zmey/php-parser. В NoVerify как раз используется такой парсер, сгенерированный goyacc.
Аргументы в пользу использования генератора парсеров (имхо):
Хотя стоит заметить,
goyaccне генерирует слишком быстрый парсер, там будет очень много аллокаций. Но может его нужно просто правильно готовить.То есть:
Хотя бы разок написать парсер ручками точно полезно. :)
Потом это быстро надоест и вы будете уже более взвешенный выбор принимать, зная плюсы и минусы обоих подходов.
А ещё алгоритм Пратта — это не новый подход. :)
Но он вроде бы не очень популярен.
Как минимум интересной может быть особенность линтера в плане расширяемости.
Не так много статических анализаторов позволяют описывать правила в виде синтаксических шаблонов. См. Как добавить проверки в NoVerify, не написав ни строчки Go-кода.
Так что я думаю польза для разработчиков может быть хотя бы из того, что можно подсмотреть в код и позаимствовать некоторые идеи.
Я постарался собрать список других проектов, которые так или иначе используют шаблоны для статического анализа. Можно туда так же добавить расширения ES Lint и подобные, но всё-таки там не AST-шаблоны, а своеобразный DSL из ключей-значений.
Также несколько раз делались разборы Open-Source проектов через NoVerify, после чего меинтейнерам отправлялись патчи с исправлениями багов. Тоже некоторая польза сообществу. :)
Ещё кто-то натолкнулся на эту особенность:
https://utcc.utoronto.ca/~cks/space/blog/programming/GoRangeCopying
https://utcc.utoronto.ca/~cks/space/blog/programming/GoForRangeNudging
С моим опытом не согласуется, но минус за комментарий (не в карму) я поставил из-за того, что ваш комментарий довольно кусачий и некоторых может незаслуженно обидеть.
Решил дать вам знать. Возможно, кто-то еще поставил минус по той же причине.
Добавил главу "Вызов Go функций из JIT-кода".
Натолкнулся на runtime: "unexpected return pc" with JIT-generated code и решил попробовать придумать решение.
По обсуждениям похоже на то, что как минимум планируется дать возможность указать у Go функции её ABI через магический комментарий (
//go:прагму). Но я могу что-то упустить, там многовато сообщений. :)Но для ассемблерных функций точно будет по умолчанию старый. Когда появится
ABI1, видимо, его можно будет проставить через флаги ассемблерной функции.Это действительно не самое оптимальное решение, но регистровая CC пока не дала прироста больше 5-10% на (синтетических) тестах, что неплохо для более-менее зрелого компилятора, но не так супер много, чтобы бить тревогу. :)
Ознакомьтесь, пожалуйста, с register-based CC for Go и internal calling convention. Эти ссылки затрагивают как историю, так и потенциальное будущее.
(Ниже только субъективные догадки.)
Видимо, простота для реализации и универсальность на большом количестве платформ. была достаточно хорошей причиной. Там не только даже в компиляторе дело, у Go есть GC и ему надо уметь работать с "локальными" данными (регистры и стек), чем сложнее логика CC и чем более она разная между платформами, тем сложнее будет реализация (или придётся больше платформозависимого кода писать). Рантайму, возможно, тоже проще с трейсами работать.
С этим сложнее.
В последний раз у меня такая задача была года 3 назад и вроде бы отчасти решалось через компиляцию Go в
c-archive.Но гораздо надёжнее (если это возможно) инверсировать поток управления и сделать runtime Go основным, а C++ код уже оттуда использовать. Именно поэтому примеров такого подхожа и больше, сделать это корректно попроще, чем встроить Go в другое приложение. :)
Продолжение планировалось к публикации через неделю-две после первой части, к сожалению, у меня сейчас очень мало свободного времени и мотивации.
Изначально это вообще должно было быть одной большой публикацией, но я быстро понял, что сил дотянуть до полноценной статьи не хватит, вот и разделил на две части, выложив то, что уже было.
Статья интересная. Часто черпаю вдохновение из вашего блога, а потом адаптирую идеи для своих анализаторов.
(Ниже комментарий про Go, но концепция не привязана к нему, уже есть для PHP похожая реализация, остальные языки — тоже не проблема.)
Для сравнения, в ruleguard правило для "x==x" выглядело бы так:
Условие
pureнужно в основном для избежания false positives в случаях, где у нас$x— это выражение с побочными эффектами, типа вызова функции, которая модифицирует глобальный state.Const folding ещё не доделан, но запланирован, поэтому эквивалентность
x[0]иx[1-1]будет учтена.В match через запятую можно перечислить остальные шаблоны, например
$x != $x:Хотя в PVS-Studio не так много синтаксических проверок, в основном самые лучшие — это связанные с data flow, что через шаблоны представить пока трудно. Но в CodeQL он есть, и там тоже похожая концепция поиска кода через запросы с условиями.
Больше примеров: https://github.com/quasilyte/go-ruleguard/blob/master/rules.go
Для удобства, вот сниппет из статьи, на который я делаю комментарий:
Я всё-таки полез в исходники.
Вот несколько подсказок, куда сначала стоит посмотреть:
А дальше нужно понять, кто эту лишнюю копию удаляет: при каких условиях, точно ли удаляет, а не заменяет на что-то хитрое (я там видел вызовы DUFFCOPY на размер меньший массива при некоторых N, не сразу понятно, что это). Это может быть как в том же фронтенде (gc), либо в ssa.
Из комментария "array ranges use value multiple times. make copy." как будто бы следует, что эта копия им нужна, чтобы сгенерировать код, который обращается к этой "переменной" (на уровне кодогенерации) для взятия n-го элемента внутри цикла. То есть:
haуже может быть копией после order.go.Гипотетически, этой копии можно избежать, если мы можем доказать, что ha не изменяется. Это сложно, если ha — глобальная переменная. Для локальных массивов, наверное, и сейчас кто-то успешно копию удаляет.
Попробуйте эти 2 функции и сравните их асм: https://play.golang.org/p/u4jQsQAKdHe
Для удобства, вот он: https://gist.github.com/quasilyte/99aa5bbff0906b38cdcd9525c25b11d4
Обратить внимание на то, что в первой функции есть DUFFCOPY.
Проверял на 1.13 и на go-tip.
В новых версиях компилятора, возможно, ввели оптимизацию при каком-то размере массива, надо посмотреть. Моя информация примерно годичной давности, но до ~1000 байтах копирование всё ещё есть.
Лучше в код компилятора посмотреть, конечно. Скорее всего, ответ стоит искать в cmd/compile/internal/gc. Если вдруг разберётесь, можете здесь написать ответ, думаю, многим полезно будет (в том числе мне).
Сам пример с arrayExprCopy был примером того, что можно детектировать через правила и что правится 1-им символом. Альтернативный фикс — делать слайс от массива, чтобы цикл шёл уже по слайсу.
(Про то, как трактовать тот параграф в спеке можно порассуждать, но ценность не очень высокая. Я на 100% не могу утверждать, но это та интерпретация, которую я видел в нескольких обсуждениях.)
Если отбросить спеку в сторону, так как не понятно, как её правильно читать, то
a[i]имеет семантику, как в C. У нас массив — это просто указатель и длина только на этапе компиляции хранится. Чтобы взять элемент, копирования не нужно.А в случае цикла иногда копия лучше, посмотрите мой update, пожалуйста:
Там банально не так очевидно, стоит ли всегда оптимизировать.
При этом
xдолжен быть addressable, чтобы от него можно было взять адрес. Если там вызов функции, то уже не прокатит.В спеке явно не написано, но вот из этого выводится:
Если x — это массив, то его "evaluation" в контексте выражений — это копирование.
А вот почему нет копирования, когда используется только 1 range value, это отдельно описано:
Прочитайте внимательно For statements with range clause, взял оттуда.
Вы сами предположили, что это редкий кейс. Я могу это подтвердить, он реально редкий и проверял я на Go корпусе при тестировании go-critic, где эта диагностика есть. Имхо, это такой редкий зверь, что даже нашего диалога не стоит.
Я не буду говорить, хорошо это или плохо, что в gc компиляторе неохотно делают оптимизации, которые:
a) срабатывают очень редко и легко правятся в коде (явно, в 1 символ)
b) когда цикл работает 1 раз в каком-нибудь init, то разницы нет, есть эта оптимизация или нет
Такая вот политика. Она может нравиться или не нравиться, нам об этом спорить толку мало.
Насколько мне известно, там ещё 1 нюанс есть: если массив маленький, по копии пройти может быть быстрее, потому что тогда у нас будет
a[i]для доступа к элементу, который на каждой итерации генерируется для range value. А если это указатель, то будет(*a)[i](массив — это указатель на данные под капотом, а указатель на массив будет указателем на указатель). Мне больше нравится подход, где мы говорим программисту: "здесь может быть что-то подозрительное, разберись, пожалуйста" (как это делает go-critic).В общем, вы правы, но тут "чинить" не очень корректное слово. Это не баг, а поведение по спеке. Плюс, как вы уже тоже отметили, это редкий кейс, но если он появляется в программе, есть шанс, что это была ошибка программиста, а фикс очень простой...
Если "починить", сломается код, который ожидает, что массив копируется. Эти программы корректные по спецификации языка.
Если копию не делать, конкуррентные программы могут измениться. Можно, конечно, делать анализ, не доступен ли массив для такого доступа, но чаще всего массивы для оптимизаций — глобальны, а Go слабовато пока такое оптимизирует и анализирует. И не факт, что когда-либо gc (компилятор от Google) будет такое делать, потому что есть требование держать время компиляции под контролем, а флаги -O они не хотят.
К gopls попробую прикрутить, в нём очень хорошая поддержка
go/analysis. А сам gopls в VS Code есть.