Как приручить дракона. Краткий пример на clang-c

Однажды, сидя вечером перед компьютером и предаваясь меланхолии и мыслям о бренности всего сущего, я задумчиво набрал в поиске одного крупного сайта по поиску работы аббревиатуру «LLVM», не надеясь, впрочем, увидеть там что-то особенное, и стал просматривать небогатый, прямо скажем, улов.
Как и следовало ожидать, почти ничего особенного не нашлось, однако одно объявление меня заинтересовало. В нём были такие строки:
«Кого мы возьмем «не глядя» или уровень выполняемых задач:
Вы скачали любой open source проект, собираемый при помощи gcc (объем исходного кода более 10 мегабайт) и для самого большого файла cpp смогли построить AST дерево при помощи clang с –fsyntax-only;
Вы скачали любой open source проект, собираемый при помощи Visual C++ (объем исходного кода более 10 мегабайт) и для самого большого файла cpp смогли построить AST дерево при помощи clang с –fsyntax-only;
Вы смогли написать утилиту, которая выделит все места деклараций и использования локальных переменных, а также все функции, не определенные в данном файле
»

Ну что же, подумал я, какое-никакое, а развлечение на вечер.

40a2a414a89a4eb7980f162b1be3c55d.jpg

Первые два пункта рассмотрим кратко, там всё очень просто.

Как построить AST


Берем любой проект на c++, можно сам clang (он собирается и на gcc, и на VC++).
clang -std=c++11 -Xclang -ast-dump /путь/к/файлу/cpp -I/путь/к/директории/с/include/файлами -Dнужные_макросы -fsyntax-only

Получаем AST в текстовом виде. Для большого файла AST имеет огромный размер, я не буду приводить здесь весь ast-dump, но для наглядности приведу небольшой кусочек:
Фрагмент AST самого clang
TranslationUnitDecl 0x576e190 <>
|-TypedefDecl 0x576e718 <> implicit __int128_t '__int128'
| `-BuiltinType 0x576e400 '__int128'
|-TypedefDecl 0x576e778 <> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0x576e420 'unsigned __int128'
|-TypedefDecl 0x576eaa8 <> implicit __NSConstantString 'struct __NSConstantString_tag'
| `-RecordType 0x576e860 'struct __NSConstantString_tag'
|   `-CXXRecord 0x576e7c8 '__NSConstantString_tag'
|-TypedefDecl 0x576eb38 <> implicit __builtin_ms_va_list 'char *'
| `-PointerType 0x576eb00 'char *'
|   `-BuiltinType 0x576e220 'char'
|-TypedefDecl 0x576ee58 <> implicit referenced __builtin_va_list 'struct __va_list_tag [1]'
| `-ConstantArrayType 0x576ee00 'struct __va_list_tag [1]' 1
|   `-RecordType 0x576ec20 'struct __va_list_tag'
|     `-CXXRecord 0x576eb88 '__va_list_tag'
|-NamespaceDecl 0x57cc578 line:18:11 clang
| |-CXXRecordDecl 0x57cc5e0 col:7 class Decl
| |-CXXRecordDecl 0x57cc6a0 :2:1> col:1 referenced class AccessSpecDecl
| |-CXXRecordDecl 0x57cc760 :3:1> col:1 class BlockDecl
| |-CXXRecordDecl 0x57cc820 :4:1> col:1 class CapturedDecl
| |-CXXRecordDecl 0x57cc8e0 :5:1> col:1 referenced class ClassScopeFunctionSpecializationDecl
| |-CXXRecordDecl 0x57cc9a0 :6:1> col:1 class EmptyDecl
| |-CXXRecordDecl 0x57cca60 :7:1> col:1 class ExternCContextDecl
| |-CXXRecordDecl 0x57ccb20 :8:1> col:1 class FileScopeAsmDecl
| |-CXXRecordDecl 0x57ccbe0 :9:1> col:1 referenced class FriendDecl
| |-CXXRecordDecl 0x57ccca0 :10:1> col:1 referenced class FriendTemplateDecl
| |-CXXRecordDecl 0x57ccd60 :11:1> col:1 class ImportDecl
| |-CXXRecordDecl 0x57cce20 :12:1> col:1 class LinkageSpecDecl
| |-CXXRecordDecl 0x57ccee0 :13:1> col:1 class NamedDecl
| |-CXXRecordDecl 0x57ccfa0 :14:1> col:1 class LabelDecl
| |-CXXRecordDecl 0x57cd060 :15:1> col:1 class NamespaceDecl
| |-CXXRecordDecl 0x57cd120 :16:1> col:1 class NamespaceAliasDecl


Можно также получить дерево с помощью другой опции: -ast-print. Оно тоже будет текстовым и огромным, и я тоже не буду его приводить.
И наконец, можно получить графическое представление дерева в Graphviz (широко используемый для отладки в LLVM). Это делается с помощью опции -ast-view. Разумеется, при этом должен быть установлен Graphviz и прописаны пути к файлам «dot» и «gv'. В данном случае откроется множество окон, в каждом из которых будет небольшой участок AST, например, такой:

b2170d887fc54f8a9e9267fb8ad649ab.jpg

Однако, прежде чем продолжить, я хотел бы кратко рассказать, что такое AST и для чего оно нужно. Читатели, имеющие степень в Computer Science, могут смело пролистывать следующий раздел, а остальным, возможно, будет интересно.

Abstract Syntax Tree


Строгие определения вы можете посмотреть в википедии, а я постараюсь объяснить «на пальцах».
Абстрактное синтаксическое дерево — структура, с помощью которой компилятор представляет исходный текст программы в удобной для дальнейшей компиляции форме. В листьях дерева находятся переменные (если быть точным, то ссылки на декларации переменных) и константы, в других вершинах — операторы, объявления типов данных и т.п. Корнем дерева является «единица трансляции» программы.
Например, простая программа:
// file foo.h
void foo(int x, int y);
// file main.c
#include "foo.h"
typedef struct {
	int x, y;
} st_coord;
int main() {
	st_coord coord;
	foo(coord.x, coord.y);
}

порождает такое AST:
Много букв
TranslationUnitDecl 0×4e64ad0 <>
|-TypedefDecl 0×4e65018 <> implicit __int128_t '__int128'
| `-BuiltinType 0×4e64d40 '__int128'
|-TypedefDecl 0×4e65078 <> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0×4e64d60 'unsigned __int128'
|-TypedefDecl 0×4e65338 <> implicit __NSConstantString 'struct __NSConstantString_tag'
| `-RecordType 0×4e65150 'struct __NSConstantString_tag'
|   `-Record 0×4e650c8 '__NSConstantString_tag'
|-TypedefDecl 0×4e653c8 <> implicit __builtin_ms_va_list 'char *'
| `-PointerType 0×4e65390 'char *'
|   `-BuiltinType 0×4e64b60 'char'
|-TypedefDecl 0×4e65678 <> implicit __builtin_va_list 'struct __va_list_tag [1]'
| `-ConstantArrayType 0×4e65620 'struct __va_list_tag [1]' 1
|   `-RecordType 0×4e654a0 'struct __va_list_tag'
|     `-Record 0×4e65418 '__va_list_tag'
|-FunctionDecl 0×4ebc390 col:6 used foo 'void (int, int)'
| |-ParmVarDecl 0×4e656d8 col:14 x 'int'
| `-ParmVarDecl 0×4e65748 col:21 y 'int'
|-RecordDecl 0×4ebc488 line:3:9 struct definition
| |-FieldDecl 0×4ebc540 col:6 referenced x 'int'
| `-FieldDecl 0×4ebc598 col:9 referenced y 'int'
|-TypedefDecl 0×4ebc630 col:3 referenced st_coord 'struct st_coord':'st_coord'
| `-ElaboratedType 0×4ebc5e0 'struct st_coord' sugar
|   `-RecordType 0×4ebc510 'st_coord'
|     `-Record 0×4ebc488 ''
`-FunctionDecl 0×4ebc6e8 line:7:5 main 'int ()'
`-CompoundStmt 0×4ebc9c8
|-DeclStmt 0×4ebc820
| `-VarDecl 0×4ebc7c0 col:11 used coord 'st_coord':'st_coord'
`-CallExpr 0×4ebc960 'void'
|-ImplicitCastExpr 0×4ebc948 'void (*)(int, int)'
| `-DeclRefExpr 0×4ebc838 'void (int, int)' Function 0×4ebc390 'foo' 'void (int, int)'
|-ImplicitCastExpr 0×4ebc998 'int'
| `-MemberExpr 0×4ebc888 'int' lvalue .x 0×4ebc540
|   `-DeclRefExpr 0×4ebc860 'st_coord':'st_coord' lvalue Var 0×4ebc7c0 'coord' 'st_coord':'st_coord'
`-ImplicitCastExpr 0×4ebc9b0 'int'
`-MemberExpr 0×4ebc8e8 'int' lvalue .y 0×4ebc598
  `-DeclRefExpr 0×4ebc8c0 'st_coord':'st_coord' lvalue Var 0×4ebc7c0 'coord' 'st_coord':'st_coord'

Используем clang-c API


В компиляторе clang каждый узел AST представлен объектом определённого класса, причем базовых классов всего три: clang: Decl (класс объявлений), clang: Stmt, в который входят все операторы, и класс clang: Type, класс типов данных.
Итак, clang написан на C++ и имеет объектно-ориентированный API. Для написания различных утилит и инструментов с использованием clang можно пользоваться им. Однако знающие люди предпочитают другой API, clang-c, который представляет собой обёртку над clang API, написанную на чистом C. Смысл здесь простой: во-первых, это проще, во-вторых clang-c API стабильно, в отличие от clang API, которое меняется с каждым релизом. И наконец, использование clang-c не исключает использование clang API, что мы вскоре увидим.

4a1e939716b049e6a211775a2d3b8b68.jpg

Обход дерева AST


Первое, что нужно сделать, это написать обход дерева в глубину. Это совершенно стандартная операция:
#include 
#include 
#include 

using namespace clang;

void printCursor(CXCursor cursor) {
    CXString displayName = clang_getCursorDisplayName(cursor);
    std::cout << clang_getCString(displayName) << "\n";
    clang_disposeString(displayName);
}

CXChildVisitResult visitor( CXCursor cursor, CXCursor /* parent */, CXClientData /*clientData*/ )
{
    CXSourceLocation location = clang_getCursorLocation( cursor );
    if( clang_Location_isFromMainFile( location ) == 0 )
        return CXChildVisit_Continue;
   
    printCursor(cursor);

    clang_visitChildren( cursor, visitor, nullptr );
    return CXChildVisit_Continue;
}

int main (int argc, char** argv) {
    CXIndex index = clang_createIndex (
        0, // excludeDeclarationFromPCH
        1  // displayDiagnostics
        );
    CXTranslationUnit unit = clang_parseTranslationUnit (
        index, // CIdx
        0, // source_filename
        argv, // command_line_args
        argc, // num_command_line_args
        0, // unsave_files
        0, // num_unsaved_files
        CXTranslationUnit_None // options
        );
    if (!unit) {
        std::cout << "Translation unit was not created\n";
    }
    else {
        CXCursor root = clang_getTranslationUnitCursor(unit);
        clang_visitChildren(root, visitor, nullptr);
    }
    clang_disposeTranslationUnit(unit);
    clang_disposeIndex(index);
}

Здесь всё очень ясно: clang_parseTranslationUnit — функция, выполняющая все этапы компиляции до построения AST включительно. Ей могут передаваться любые опции компиляции. При этом имя файла можно передавать как в аргументах, так и напрямую (source_filename). Исходный текст может быть передан не только в виде файла, но и в виде структуры CXUnsavedFile, представляющей тескт в памяти. После парсинга происходит обход дерева в глубину, для каждой вершины вызывается функция visitor, которой передаётся CXCursor — структура, представляющая вершину дерева. Также функции visitor может быть передан параметр CXClientData, представляющий произвольные пользовательские данные.

Пишем функцию visitor


Попробуем найти все локальные переменные программы.
 CXCursorKind cursorKind = clang_getCursorKind( cursor );
    // finding local variables    
    if(clang_getCursorKind(cursor) == CXCursor_VarDecl) {
        if(const VarDecl* VD = dyn_cast_or_null(getCursorDecl(cursor))) {
            if( VD->isLocalVarDecl()) {
                std::cout << "local variable: ";
                printCursor(cursor);
            }
        }
    }

Здесь тоже всё просто: CXCursor_VarDecl — курсор указывает на переменную. dyn_cast_or_null — шаблон преобразования типов в LLVM.
LLVM и RTTI
LLVM не использует RTTI и обычный dynamic_cast работать не будет.
Для приведения типов в LLVM используются следующие шаблоны:
isa(A) — проверка принадлежности объекта A к типу В.
cast(A) — преобразование объекта A к типу В. Проверка принадлежности типа А типу В не выполняется. Проверка A на nullptr не выполняется.
cast_or_null(A) — преобразование объекта A к типу В. Проверка принадлежности типа А типу В не выполняется. Если A == nullptr, результат будет nullptr.
dyn_cast(A) — преобразование объекта A к типу В c проверкой типа. Проверка A на nullptr не выполняется.
dyn_cast_or_null(A) — преобразование объекта A к типу В c проверкой типа. Если A == nullptr, результат будет nullptr.
О том, как использовать LLVM-реализацию RTTI в своих классах, написано здесь

Далее преобразуем курсор в экземпляр класса VarDecl, и проверяем, является ли переменная локальной. Если является, выводим имя курсора и его расположение в исходнике, используя для этого вспомогательные функции:
//logging functions
std::string getLocationString(CXSourceLocation Loc) {
    CXFile File;
    unsigned Line, Column;
    clang_getFileLocation(Loc, &File, &Line, &Column, nullptr);
    CXString FileName = clang_getFileName(File);
    std::ostringstream ostr;
    ostr << clang_getCString(FileName) << ":" << Line << ":" << Column;
    clang_disposeString(FileName);
    return ostr.str();
}

void printCursor(CXCursor cursor) {
    CXString displayName = clang_getCursorDisplayName(cursor);
    std::cout << clang_getCString(displayName) << "@" << getLocationString(clang_getCursorLocation(cursor)) << "\n";
    clang_disposeString(displayName);
}

Для нахождения значений Decl, Expr и Stmt используем вспомогательные функции:
// extracted from CXCursor.cpp
const Decl *getCursorDecl(CXCursor Cursor) {
    return static_cast(Cursor.data[0]);
}

const Stmt *getCursorStmt(CXCursor Cursor) {
    if (Cursor.kind == CXCursor_ObjCSuperClassRef ||
            Cursor.kind == CXCursor_ObjCProtocolRef ||
            Cursor.kind == CXCursor_ObjCClassRef)
        return nullptr;
    return static_cast(Cursor.data[1]);
}

const Expr *getCursorExpr(CXCursor Cursor) {
    return dyn_cast_or_null(getCursorStmt(Cursor));
}

Далее ищем все использования локальных переменных:
// finding referenced variables
    if(cursorKind == CXCursor_DeclRefExpr) {
        if(const DeclRefExpr* DRE = dyn_cast_or_null(getCursorExpr(cursor))) {
            if(const VarDecl* VD = dyn_cast_or_null(DRE->getDecl())) {
                if(VD->isLocalVarDecl()) {
                    std::cout << "reference to local variable: ";
                    printCursor(cursor);
                }
            }
        }
    }

И наконец, находим все вызовы функций, не определённых в этом файле:
    // finding functions not defined in the module
    if(cursorKind == CXCursor_CallExpr) {
        if (const Expr *E = getCursorExpr(cursor)) {
            if(isa(E)) {
                CXCursor Definition = clang_getCursorDefinition(cursor);
                if (clang_equalCursors(Definition, clang_getNullCursor())) {
                    std::cout << "function is not defined here: ";
                    printCursor(cursor);
                }
            }
        }
    }

Здесь мы проверяем, является ли курсор вызовом функции (CXCursor_CallExpr). Однако, следует учесть, что CXCursor_CallExpr, это не только вызов функции, это ещё и вызов конструктора, деструктора и метода, поэтому нужна дополнительная проверка (isa103301553c414455a5dea3e2b20c1e65.jpg

Тест


Для теста напишем две простых программы, одну на С, одну на С++.
Итак, программа на С:
//file func.h
void foo_ext(int x);

//file simple.c
#include "func.h"
int global1;

int foo(int x)
{
    return x;
}

int global2;

int main(int arg)
{
    int local;
    local = arg;
    foo_ext(arg);
    return foo(local);
}

Запускаем нашу утилиту, получаем на выходе:
local variable: local@simple.c:13:9
reference to local variable: local@simple.c:14:5
function is not defined here: foo_ext@simple.c:15:5
reference to local variable: local@simple.c:16:16

Вроде всё верно. Теперь проверим на файле на С++:
#include "func.h"

class MyClass {
    public:
    MyClass() {
        int SomeLocal_1;
    }
    void foo() {
        int SomeLocal_2;
    }
    ~MyClass() {
        int SomeLocal_3;
    }
};

MyClass myClass_global;

int foo(int x) {return 0;}

int main(int argc, char** argv)
{
    int local;
    MyClass myClass_local;
    foo(argc);
    foo_ext(local);
    return 1;
}

Получаем на выходе:
local variable: SomeLocal_1@cpptest.cpp:6:13
local variable: SomeLocal_2@cpptest.cpp:9:13
local variable: SomeLocal_3@cpptest.cpp:12:13
local variable: local@cpptest.cpp:22:9
local variable: myClass_local@cpptest.cpp:23:13
function is not defined here: foo_ext@cpptest.cpp:25:5
reference to local variable: local@cpptest.cpp:25:13

OK, кажется, всё работает.

Как это можно использовать?


Широкие возможности clang можно использовать для разных целей, которые включают в себя анализ и преобразования исходных текстов на C, C++ и Objective C.
Ещё
Ещё можно использовать для поиска работы, но пока я всё это писал, объявление исчезло с сайта. Увы.

Литература


Список источников по теме:
1. Код проекта на Gihub.
2. http://bastian.rieck.ru/blog/posts/2015/baby_steps_libclang_ast/
3. http://bastian.rieck.ru/blog/posts/2016/baby_steps_libclang_function_extents/
4. https://jonasdevlieghere.com/understanding-the-clang-ast/
5. https://habrahabr.ru/post/148508/

Комментарии (0)

© Habrahabr.ru