В продолжение темы кастомизации компилятора С++ публикую перевод еще одной интересной статьи от Eli Bendersky AST matchers and Clang refactoring tools.
Инструментарий Clang вызывает большой интерес и внимание к разработке в последние годы. Наконец-то у нас есть удобный, точный, с открытым исходным кодом и хорошо поддерживаемый фреймворк для программного анализа и рефакторинга кода C++ и это я нахожу это очень захватывающим!
Прекрасным результатом этого быстрого темпа разработки является то, что постоянно появляются новые API и инструменты.
Например, некоторое время назад разработчики инструментария Clang выяснили, что людям, выполняющим обходы AST, приходится писать много повторяющегося кода, чтобы найти нужные им узлы AST, поэтому они придумали отличный новый API под названием AST matchers.
Посетители против сопоставителей (visitors vs. matchers)
Вот мотивирующий пример. Предположим, мы ищем переменные типа указателя, используемые в сравнениях if. Чтобы сделать это более конкретным, предположим, что мы ищем случаи, когда переменная типа указателя находится в левой части сравнения равенства ( == ). Чтобы найти такие узлы в рекурсивном посетителе, нам пришлось бы написать что-то вроде этого:
bool VisitIfStmt(IfStmt *s) {
if (const BinaryOperator *BinOP =
llvm::dyn_cast<BinaryOperator>(s->getCond())) {
if (BinOP->getOpcode() == BO_EQ) {
const Expr *LHS = BinOP->getLHS();
if (const ImplicitCastExpr *Cast =
llvm::dyn_cast<ImplicitCastExpr>(LHS)) {
LHS = Cast->getSubExpr();
}
if (const DeclRefExpr *DeclRef = llvm::dyn_cast<DeclRefExpr>(LHS)) {
if (const VarDecl *Var =
llvm::dyn_cast<VarDecl>(DeclRef->getDecl())) {
if (Var->getType()->isPointerType()) {
Var->dump(); // УРА, нашел!!!!!!!!!
}
}
}
}
}
return true;
}Это довольно много кода, но ничего необычного, если вы работали с Clang AST некоторое время. Возможно, его можно сжать до более короткой формы, но главная проблема в том, что для написания этого кода нужно просмотреть довольно много документации и заголовочных файлов, чтобы выяснить, какие методы нужно вызывать и какие типы объектов они возвращают.
А вот эквивалентный код для AST matcher`a (далее буду использовать термин сопоставитель):
Finder.addMatcher(
ifStmt(hasCondition(binaryOperator(
hasOperatorName("=="),
hasLHS(ignoringParenImpCasts(declRefExpr(
to(varDecl(hasType(pointsTo(AnyType))).bind("lhs"))
)))
))),
&HandlerForIf);Есть некоторая разница, не так ли? Декларативная природа определений для AST сопоставителей делает их код очень естественным для чтения и сопоставления с фактической проблемой. HandlerForIf — это объект MatchCallback, который имеет прямой доступ к связанным узлам сопоставителя:
struct IfStmtHandler : public MatchFinder::MatchCallback {
virtual void run(const MatchFinder::MatchResult &Result) {
const VarDecl *lhs = Result.Nodes.getNodeAs<VarDecl>("lhs");
lhs->dump(); // УРА, нашел!!!!!!!!!
}
};На самом деле, на официальном сайте Clang доступно довольно много документации о сопоставителях AST. Для полного примера, который может быть построен вне дерева LLVM, я переделал пример инструментария из предыдущей статьи, теперь с сопоставителями AST (все доступно в репозитории llvm-clang-samples ). *
*) Так как проект llvm и clang, как его часть, развиваются очень стремительно, а статья была написана далеко не вчера, то ссылка автора ведет на уже не поддерживамый репозиторий. Тем не менее код в статье и сам принцип анализа AST являются актуальными.
Использование clang-query для проверки сопоставителей и исследования AST
Для упрощения использования сопоставителей при анализе AST в проекте Clang был разработан новый инструмент — clang-query. Это интерактивный вычислитель для сопоставителей AST, который можно использовать как для их быстрого тестирования без компиляции кода, так и для изучения AST.
Допустим, мы хотим разработать сопоставитель AST для сравнения указателей, похожий на показанный выше. Вот пример входного файла, над которым мы будем работать:
int foo(int* p, int v) {
if (p == 0) {
return v + 1;
} else {
return v - 1;
}
}Давайте запустим clang-query и посмотрим, что он может сделать:
$ clang-query /tmp/iflhsptr.c --
clang-query> set output diag
clang-query> match functionDecl()
Match #1:
/tmp/iflhsptr.c:1:1: note: "root" binds here
int foo(int* p, int v) {
^~~~~~~~~~~~~~~~~~~~~~~~
1 match.Это базовый smoke тест (простой тест, который подтверждает корректную работу ключевых функций), чтобы увидеть, как он найдет объявление функции. Режим вывода установлен при вызове программы в первой команде. Также можно настроить инструмент для выгрузки или печати AST, но для нашей цели удобен диагностический вывод.
Вот как мы можем сопоставить более глубокие узлы и связать их:
clang-query> match ifStmt(hasCondition(binaryOperator(hasOperatorName("==")).bind("op")))
Match #1:
/tmp/iflhsptr.c:2:7: note: "op" binds here
if (p == 0) {
^~~~~~
/tmp/iflhsptr.c:2:3: note: "root" binds here
if (p == 0) {
^~~~~~~~~~~~~
1 match.Если мы намерены предоставить собственные привязки, корневую привязку можно отключить:
clang-query> set bind-root false
Давайте посмотрим несколько совпадений:
clang-query> match varDecl().bind("var")
Match #1:
/tmp/iflhsptr.c:1:9: note: "var" binds here
int foo(int* p, int v) {
^~~~~~
Match #2:
/tmp/iflhsptr.c:1:17: note: "var" binds here
int foo(int* p, int v) {
^~~~~
2 matches.На этом я остановлюсь, потому что длинные сопоставители не очень удобно форматировать в блоге, но я уверен, что вы поняли идею. Совершенно очевидно, насколько будет полезен этот инструмент для разработки сопоставителей. Он все еще новый и имеет некоторые грубые края, но уже весьма полезен.
Инструменты рефакторинга и замены
С ростом использования libTooling неудивительно, что его разработчики продолжают придумывать более высокие уровни абстракции, которые помогают писать новые инструменты с меньшими усилиями. Представленная выше структура сопоставлений AST является одним из примеров. Другим примером является RefactoringTool, подкласс ClangTool, который позволяет создавать новые инструменты с очень небольшим количеством кода. Скоро я покажу пример, но сначала несколько слов о заменах.
Инструменты, которые я демонстрировал до сих пор, использовали Rewriter для изменения базового исходного кода в ответ на обнаружение интересных вещей в AST. Это хороший подход, но у него есть проблема масштабирования для больших проектов.
Представьте себе запуск инструмента в большом проекте с множеством исходных файлов и множеством заголовочных файлов. Некоторые переписывания, возможно, придется выполнять в заголовочных файлах, но как это сделать, учитывая, что одни и те же заголовки включаются в несколько единиц трансляции? Некоторые правки могут оказаться дублированными или даже конфликтующими, и это проблема.
Решением являются замены (Replacements). Задача преобразования источника делится на два отдельных этапа:
-
Пользовательские инструменты проходят через исходную базу, находят шаблоны рефакторинга для применения и генерируют сериализованные замены в файлы. Думайте о заменах как о чем-то вроде файлов исправлений (точных указаний о том, как изменить исходный файл), но в несколько более удобном формате.
-
clang-apply-replacementsможет запуститься с доступом ко всем заменам, выполнить необходимую дедупликацию и разрешение конфликтов, а затем фактически применить изменения к источнику.
Такой подход также позволяет эффективно распараллеливать рефакторинг на огромных базах кода, хотя в мире не так много проектов и компаний с исходным кодом настолько большим, чтобы это стало реальной проблемой.
Тогда вернемся к примеру. Я взял простой пример инструмента из предыдущей статьи (просто нашел интересные узлы if и добавил в них несколько комментариев) и переписал его еще раз, используя RefactoringTool и Replacements. Полный код доступен в проекте примеров, но он настолько короткий, что я могу показать большую его часть здесь.
Вот полная функция main. Для простоты она только выводит замены в stdout вместо их сериализации или применения:
int main(int argc, const char **argv) {
CommonOptionsParser op(argc, argv, ToolingSampleCategory);
RefactoringTool Tool(op.getCompilations(), op.getSourcePathList());
// Настройка обратных вызовов сопоставления AST.
IfStmtHandler HandlerForIf(&Tool.getReplacements());
MatchFinder Finder;
Finder.addMatcher(ifStmt().bind("ifStmt"), &HandlerForIf);
// Запустить инструмент и собрать список замен. Мы могли бы вызвать
// runAndSave, который деструктивно перезапишет файлы с помощью
// их новое содержимое. Однако, для демонстрационных целей это
// интересно показать замены.
if (int Result = Tool.run(newFrontendActionFactory(&Finder).get())) {
return Result;
}
llvm::outs() << "Replacements collected by the tool:\n";
for (auto &r : Tool.getReplacements()) {
llvm::outs() << r.toString() << "\n";
}
return 0;
}IfStmtHandler — это просто MatchCallback, который срабатывает в операторах if:
class IfStmtHandler : public MatchFinder::MatchCallback {
public:
IfStmtHandler(Replacements *Replace) : Replace(Replace) {}
virtual void run(const MatchFinder::MatchResult &Result) {
// Соответствующий оператор 'if' был привязан к 'ifStmt'
if (const IfStmt *IfS =
Result.Nodes.getNodeAs<clang::IfStmt>("ifStmt")) {
const Stmt *Then = IfS->getThen();
Replacement Rep(*(Result.SourceManager), Then->getLocStart(), 0,
"// the 'if' part\n");
Replace->insert(Rep);
if (const Stmt *Else = IfS->getElse()) {
Replacement Rep(*(Result.SourceManager), Else->getLocStart(), 0,
"// the 'else' part\n");
Replace->insert(Rep);
}
}
}
private:
Replacements *Replace;
};Обратите внимание, как мало повторяющихся участков содержит этот код. Инструмент настраивается всего в несколько строк кода и большая его часть связана с реальным рефакторингом. Это определенно делает написание инструментов для анализа кода более быстрым и простым, чем когда-либо прежде.
Комментарии (20)
MasterMentor
02.01.2025 13:40В продолжение комментаторов выше: дохляк полнейший. Попытка натянуть очередную сову на очередной глобус.
Сова - С++, глобус - всеядность.
Конкретно:
Си изначально разработан для максимального попадания конструкциями в архитектуру машин фон Неймана .
С++ - лишь "синтактический сахар", облегчающий группировку полей и функций внутри Си-структуры (ключевое слово - struct): работу по составлению таблиц, которую в Си можно сделать руками - перекладывают на компилятор.
А для доменного использования (математика, лексеры/парсеры, итд.) - нужны доменные языки ( см. https://ru.wikipedia.org/wiki/Языково-ориентированное_программирование ).
Никогда не было и не будет никаких "языков общего назначения". Вот и мучают этот бедный Си.
rsashka Автор
02.01.2025 13:40Причем тут сова, глобус и Си?
В статье речь о синтаксическом анализе исходного текста программы с помощью описанных инструментов. И сравнение двух подходов (visitors vs. matchers) при поиске нужных данных в абстрактном синтаксическом дереве.
А уж нужен ли вам чистый С, С++ или Objevtive-С - это уже дело десятое.
vadimr
02.01.2025 13:40Да, но фильтр мультисписка средствами C++ просто выглядит неуклюже, как его ни пиши.
rsashka Автор
02.01.2025 13:40Да, но фильтр мультисписка средствами C++ просто выглядит неуклюже, как его ни пиши.
С этим я полностью согласен.
Но к сожалению, тут идет выбор не на каком языке писать фильтр, а как писать фильтр на С++ с учетом используемого инструментария.
MasterMentor
02.01.2025 13:40О том и речь: хочешь рабирать грамматики - бери BNF/Bison/PEG и иже с ними, хочешь анализировать AST (он же - маркированый граф) - делай соответствующий DSL с паттэрн мэтчингом и специализацией.
Си не предназначен ни для первого ни для второго, и реализация перечисленного на нём будет кривой и корявой.
PS ИМХО. :)
rsashka Автор
02.01.2025 13:40Вообще-то мне нужно компилировать С++ код, но с некоторыми пользовательским атрибутами и дополнительными проверками. Для этих целей нужен анализ AST с помощью плагина под clang и финальным результатом в виде объектного файла.
Во вторых, разбирать грамматики современного С++ на BNF/Bison/PEG и иже с ними, это адовый ад, который гораздо хуже, чем писать фильтр для узлов AST на С++ как в примерах из данной статьи (и это не говоря уже про то, что придется делать ненужную работу по написанию парсера, вместо того, чтобы взять уже готовый).
MasterMentor
02.01.2025 13:40Значит, мы рассматриваем разные аспекты дела.
Я говорю об "академической" стороне дела в терминах научно-теоретического обоснования. Вы - о "здесь, сейчас и быстро" в терминах "лепим из того, что есть".
Такие пассажи:
class IfStmtHandler : public MatchFinder::MatchCallback ... Tool.run(newFrontendActionFactory(&Finder).get()где уже только на изучении документации по классам и наследованию можно сломать голову, не говоря уже о будущей поддержке кода, я отношу к костыльно-ориентированному программированию.
Но, как известно из практики, оно - "наше всё" при решении "задач бизнеса". Особенно "прямо сейчас" - а другого бизнесу и не надо.
Поэтому, коль инструмент есть, проблемы - решает, - пользуйте. Я ж не отговариваю.
Просто говорю, что выглядит всё это криво и коряво, соглашаясь с предыдущим комментатором и Вами (прочтите, что сами писали выше).
Да, но фильтр мультисписка средствами C++ просто выглядит неуклюже, как его ни пиши.
...С этим я полностью согласен.
и ранее.
rsashka Автор
02.01.2025 13:40Я решаю именно "академический" вопрос, но с использованием имеющихся инструментов и прицелом на будущее реальное применение. Писать свой парсер для всех возможных диалектов C++, да еще и на Bison, как вы предлагаете, это просто ужасное решение с любой стороны. Хоть с точки зрения трудоемкости и сложности разработки, хоть с точки зрения последующей поддержки такого решения, хоть с точки зрения скорости получения первого результата.
Если вы называете костылем, решение использовать уже существующий парсер, то все ваши рассуждения "... как известно из практики, оно - "наше всё" при решении "задач бизнеса". Особенно "прямо сейчас" - а другого бизнесу и не надо." , наверно обычное шапозакидательство и популизм, ничего не имеющий с реальной жизнью.
vadimr
02.01.2025 13:40Если б мне пришлось решать эту задачу, я б рассмотрел такой вариант, как выгрузить AST дерево, обработать его программой на Lisp/Scheme и загрузить обратно.
Парсить C++ бизоном, конечно, не вариант из-за темплейтов.
rsashka Автор
02.01.2025 13:40Выгружать ничего не хочется, а тем более потом загружать обратно. Планирую сделать все в рамка работы компилятора с загружаемым плагином.
Настроить поиск для заданных узлов AST тот еще геморрой, но все равно на порядки проще разработки собственного парсера или использования дополнительного внешнего инструмента.
MasterMentor
02.01.2025 13:401.
Писать свой парсер для всех возможных диалектов C++, да еще и на Bison...
Передёргиваете. Разница между тем, что Вы написали и "хочешь разбирать грамматики - бери BNF/Bison/PEG и иже с ними" - ясна?
Если не совсем очевидна, то я доносил мысль, что писать парсеры на Си - это плохая затея, а парсер Clang написан на Си.
Это была критика Clang-а, а не то, что Вы подумали.
2.
Если вы называете костылем, решение использовать уже существующий парсер...
Опять осечка. Давайте внимательно читать, и попробуем вместе подумать, что я называю не костылём, а "костыльно-ориентированным программированием".
Подсказка:
...главная проблема в том, что для написания этого кода нужно просмотреть довольно много документации и заголовочных файлов, чтобы выяснить, какие методы нужно вызывать и какие типы объектов они возвращают.
Для решения этой проблемы разработчики Clang-а лепят "из того, что есть" костыль в виде - "IfStmtHandler, MatchFinder, MatchCallback, newFrontendActionFactory" и прочей трухи, что не на много лучше того, что было. А Вы его вынуждены брать и лепить из него костыли дальше (ибо куда деваться?).
По-моему это оно: "костыльно-ориентированное программирование".
...шото Вы меня разочаровываете.
mentin
02.01.2025 13:40Проблема тут что кроме доменного языка для поиску по AST, для рефакторинга нужно написать собственно код с логикой как найденный AST менять.
И тут придется либо делать этот DSL полным по Тьюрингу, и включать в него императивные элементы, что проект и похоронит. Либо делать что-то вроде встроенного SQL, когда доменный язык вызывается из императивной программы, что обычно тоже ужасно. Либо как в статье. Все решения довольно корявые. Я не видел решений делающих это сильно чище, чем в статье.
MasterMentor
02.01.2025 13:40Все решения довольно корявые.
Значит, очевидно, пользуемый инструментарий не подходит к этим задачам.
И вот это, говорит о попытке создания полу-меры - недо-DSL-я:
Для упрощения использования сопоставителей при анализе AST в проекте Clang был разработан новый инструмент — clang-query
Далее, глубоко не убеждён, что анализировать/модифицировать алгоритмы на этапе парсера (ака Clang) - есть хорошо. Ибо не его это функция.
Выгрузить дерево и работать с ним специальным инструментом, как писал выше @vadimr - гораздо лучше. Собственно, оно так и работает: Clang (функция: парсинг)->выгрузка дерева (в байткод)->анализ и оптимизация алгоритма в LLVM. А уж та простроит из байткода нужные ей графы, и с учётом выбранных опций проведёт над ними оптимизацию. Всё сделано "академически", по науке.
Деревья Clang-а разве что для статистического/эвристического анализа пригодятся (но опять же в отдельном специальном модуле такого анализа). Но если вы на этом этапе хотите отлавливать некоторые узлы и ставить в них свои метки, либо что-то сливать в свои бинарники, - так ставьте. Я что, где-то запрещал это делать?! :)))
Что по DSL-лям для работы c AST-ами (то есть структурами на графах), то они были и будут. Пример:
GraphIt - A High-Performance Domain Specific Language for Graph Analytics https://graphit-lang.org/ https://github.com/GraphIt-DSL/graphit
mentin
02.01.2025 13:40глубоко не убеждён, что анализировать/модифицировать алгоритмы на этапе парсера (ака Clang) - есть хорошо. Ибо не его это функция.
Это не этап парсера в компиляторе, это отдельная программа, использующая результат парсера. Остальных частей компилятора там нет, а в случае рефакторинга - превращают AST дерево обратно в код.
Для чего-то монументального наверно можно и DSL прикрутить, но он должен работать точно так же - превращать AST Clang в дерево и скармливать его DSL.
MasterMentor
02.01.2025 13:40Это не этап парсера в компиляторе, это отдельная программа, использующая результат парсера.
Возможно. В этом я не специалист. Поэтому делил не по программам, а по этапам. AST же, вроде, сделал парсер, но не отдал ещё компилятору. Поэтому работу с AST-ом я отнёс к этапу парсинга кода.
С другой стороны, почему бы работу с AST не вынести в отдельный этап?
Давайте условно назовём этот этап "Дерево", и даже, не просто "Этап Дерево", а как у того Льва Толстого Дубище "...с огромными своими неуклюже, несимметрично растопыренными корявыми руками и пальцами, он старым, сердитым и презрительным уродом стоял между улыбающимися березами".
Назовём этот этап "Дерево на костылях" или "Костыльное дерево". Полагаю, на этом все наши разноглася по наименованию этапов сняты.
PS Вступая в дискуссии под темами с Дубо-кодом, где ождаешь кислые мины и душные речи... весь этот (конечно, кодовый) бред, изначально думаешь, а сколько минусов это принесёт в карму. Сия принесла -2. Но и обогатила идеями.
Выводы: карма - это Бог (тот самый)! Сам Бог подсказывает нужно ли ходить по таким путям, если признаки итога проглядывают уже в коде. :)
rsashka Автор
02.01.2025 13:40Вы получили минусы в карму (один из них мой), не за саму дискуссию. Ведь известно, что в споре рождается истина, а за форму подачи своих мыслей и навешивание ярлыков.
Причем, я его поставил только после нескольких сообщений о том, что ваши аргументы в принципе правильные, но не относятся к данному конкретном случаю, но вы все равно продолжали упорствовать в своих утверждениях, которые самый обычный спор рано или поздно переводят на личности, вместо обсуждения изначальной темы.
vadimr
Лисп своими руками.
rsashka Автор
Количество закрывающих скобок коде примера меня тоже мутило.
Прямо как в том анекдоте: