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

    Однажды, сидя вечером перед компьютером и предаваясь меланхолии и мыслям о бренности всего сущего, я задумчиво набрал в поиске одного крупного сайта по поиску работы аббревиатуру «LLVM», не надеясь, впрочем, увидеть там что-то особенное, и стал просматривать небогатый, прямо скажем, улов.

    Как и следовало ожидать, почти ничего особенного не нашлось, однако одно объявление меня заинтересовало. В нём были такие строки:

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

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



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

    Как построить 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 <<invalid sloc>> <invalid sloc>
    |-TypedefDecl 0x576e718 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
    | `-BuiltinType 0x576e400 '__int128'
    |-TypedefDecl 0x576e778 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
    | `-BuiltinType 0x576e420 'unsigned __int128'
    |-TypedefDecl 0x576eaa8 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'
    | `-RecordType 0x576e860 'struct __NSConstantString_tag'
    |   `-CXXRecord 0x576e7c8 '__NSConstantString_tag'
    |-TypedefDecl 0x576eb38 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'
    | `-PointerType 0x576eb00 'char *'
    |   `-BuiltinType 0x576e220 'char'
    |-TypedefDecl 0x576ee58 <<invalid sloc>> <invalid sloc> 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 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:18:1, line:31:1> line:18:11 clang
    | |-CXXRecordDecl 0x57cc5e0 <line:20:1, col:7> col:7 class Decl
    | |-CXXRecordDecl 0x57cc6a0 <line:21:29, <scratch space>:2:1> col:1 referenced class AccessSpecDecl
    | |-CXXRecordDecl 0x57cc760 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:3:1> col:1 class BlockDecl
    | |-CXXRecordDecl 0x57cc820 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:4:1> col:1 class CapturedDecl
    | |-CXXRecordDecl 0x57cc8e0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:5:1> col:1 referenced class ClassScopeFunctionSpecializationDecl
    | |-CXXRecordDecl 0x57cc9a0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:6:1> col:1 class EmptyDecl
    | |-CXXRecordDecl 0x57cca60 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:7:1> col:1 class ExternCContextDecl
    | |-CXXRecordDecl 0x57ccb20 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:8:1> col:1 class FileScopeAsmDecl
    | |-CXXRecordDecl 0x57ccbe0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:9:1> col:1 referenced class FriendDecl
    | |-CXXRecordDecl 0x57ccca0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:10:1> col:1 referenced class FriendTemplateDecl
    | |-CXXRecordDecl 0x57ccd60 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:11:1> col:1 class ImportDecl
    | |-CXXRecordDecl 0x57cce20 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:12:1> col:1 class LinkageSpecDecl
    | |-CXXRecordDecl 0x57ccee0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:13:1> col:1 class NamedDecl
    | |-CXXRecordDecl 0x57ccfa0 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:14:1> col:1 class LabelDecl
    | |-CXXRecordDecl 0x57cd060 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:15:1> col:1 class NamespaceDecl
    | |-CXXRecordDecl 0x57cd120 </home/user/LLVM/llvm-3.7.1.src/tools/cfe-3.7.1.src/include/clang/AST/ASTFwd.h:21:29, <scratch space>:16:1> col:1 class NamespaceAliasDecl


    Можно также получить дерево с помощью другой опции: -ast-print. Оно тоже будет текстовым и огромным, и я тоже не буду его приводить.

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



    Однако, прежде чем продолжить, я хотел бы кратко рассказать, что такое 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 0x4e64ad0 <<invalid sloc>> <invalid sloc>
    |-TypedefDecl 0x4e65018 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
    | `-BuiltinType 0x4e64d40 '__int128'
    |-TypedefDecl 0x4e65078 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
    | `-BuiltinType 0x4e64d60 'unsigned __int128'
    |-TypedefDecl 0x4e65338 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'
    | `-RecordType 0x4e65150 'struct __NSConstantString_tag'
    |   `-Record 0x4e650c8 '__NSConstantString_tag'
    |-TypedefDecl 0x4e653c8 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'
    | `-PointerType 0x4e65390 'char *'
    |   `-BuiltinType 0x4e64b60 'char'
    |-TypedefDecl 0x4e65678 <<invalid sloc>> <invalid sloc> implicit __builtin_va_list 'struct __va_list_tag [1]'
    | `-ConstantArrayType 0x4e65620 'struct __va_list_tag [1]' 1
    |   `-RecordType 0x4e654a0 'struct __va_list_tag'
    |     `-Record 0x4e65418 '__va_list_tag'
    |-FunctionDecl 0x4ebc390 </home/user/llvm3.9/foo.h:1:1, col:22> col:6 used foo 'void (int, int)'
    | |-ParmVarDecl 0x4e656d8 <col:10, col:14> col:14 x 'int'
    | `-ParmVarDecl 0x4e65748 <col:17, col:21> col:21 y 'int'
    |-RecordDecl 0x4ebc488 </home/user/llvm3.9/test.c:3:9, line:5:1> line:3:9 struct definition
    | |-FieldDecl 0x4ebc540 <line:4:2, col:6> col:6 referenced x 'int'
    | `-FieldDecl 0x4ebc598 <col:2, col:9> col:9 referenced y 'int'
    |-TypedefDecl 0x4ebc630 <line:3:1, line:5:3> col:3 referenced st_coord 'struct st_coord':'st_coord'
    | `-ElaboratedType 0x4ebc5e0 'struct st_coord' sugar
    |   `-RecordType 0x4ebc510 'st_coord'
    |     `-Record 0x4ebc488 ''
    `-FunctionDecl 0x4ebc6e8 <line:7:1, line:10:1> line:7:5 main 'int ()'
    `-CompoundStmt 0x4ebc9c8 <col:12, line:10:1>
    |-DeclStmt 0x4ebc820 <line:8:2, col:16>
    | `-VarDecl 0x4ebc7c0 <col:2, col:11> col:11 used coord 'st_coord':'st_coord'
    `-CallExpr 0x4ebc960 <line:9:2, col:22> 'void'
    |-ImplicitCastExpr 0x4ebc948 <col:2> 'void (*)(int, int)' <FunctionToPointerDecay>
    | `-DeclRefExpr 0x4ebc838 <col:2> 'void (int, int)' Function 0x4ebc390 'foo' 'void (int, int)'
    |-ImplicitCastExpr 0x4ebc998 <col:6, col:12> 'int' <LValueToRValue>
    | `-MemberExpr 0x4ebc888 <col:6, col:12> 'int' lvalue .x 0x4ebc540
    |   `-DeclRefExpr 0x4ebc860 <col:6> 'st_coord':'st_coord' lvalue Var 0x4ebc7c0 'coord' 'st_coord':'st_coord'
    `-ImplicitCastExpr 0x4ebc9b0 <col:15, col:21> 'int' <LValueToRValue>
    `-MemberExpr 0x4ebc8e8 <col:15, col:21> 'int' lvalue .y 0x4ebc598
      `-DeclRefExpr 0x4ebc8c0 <col:15> 'st_coord':'st_coord' lvalue Var 0x4ebc7c0 '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, что мы вскоре увидим.



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


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

    #include <clang-c/Index.h>
    #include <iostream>
    #include <string>
    
    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<const VarDecl>(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<B>(A) — проверка принадлежности объекта A к типу В.
    cast<B>(A) — преобразование объекта A к типу В. Проверка принадлежности типа А типу В не выполняется. Проверка A на nullptr не выполняется.
    cast_or_null<B>(A) — преобразование объекта A к типу В. Проверка принадлежности типа А типу В не выполняется. Если A == nullptr, результат будет nullptr.
    dyn_cast<B>(A) — преобразование объекта A к типу В c проверкой типа. Проверка A на nullptr не выполняется.
    dyn_cast_or_null<B>(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<const Decl *>(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<const Stmt *>(Cursor.data[1]);
    }
    
    const Expr *getCursorExpr(CXCursor Cursor) {
        return dyn_cast_or_null<Expr>(getCursorStmt(Cursor));
    }

    Далее ищем все использования локальных переменных:

    // finding referenced variables
        if(cursorKind == CXCursor_DeclRefExpr) {
            if(const DeclRefExpr* DRE = dyn_cast_or_null<const DeclRefExpr>(getCursorExpr(cursor))) {
                if(const VarDecl* VD = dyn_cast_or_null<const VarDecl>(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<const CallExpr>(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, это не только вызов функции, это ещё и вызов конструктора, деструктора и метода, поэтому нужна дополнительная проверка (isa). После этого мы ищем определение функции (clang_getCursorDefinition), и если не находим (clang_equalCursors(Definition, clang_getNullCursor())), то мы нашли функцию, не определённую в данном файле.


    Тест


    Для теста напишем две простых программы, одну на С, одну на С++.
    Итак, программа на С:

    //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/
    Метки:
    • +45
    • 8,1k
    • 9
    Поделиться публикацией
    Похожие публикации
    Комментарии 9
    • +1
      на работу-то взяли?
      • +1
        В конце я же написал.
        Нет, пока я всё это делал, объявление исчезло.
      • 0
        .
        • +1

          Хоть цель и была "потыкать самому", всёж советую clang-query и ASTMatchers для таких задач.

          • 0
            Спасибо, буду иметь в виду.
          • 0

            Почему вы пишете, что это распарсить любой проект на Visual C++ это "очень просто"? У нас вот гигантский проект и кланг отказывается его понимать в куче мест. И это вроде бы известная тема, что MS не требует строгого выполнения стандарта во многих местах (самый яркий пример — двухфазная обработка шаблонов). В чём ваш секрет?

            • +1
              Разумеется, соответствие стандартам должно иметь место.
              • 0

                Ах, ну тогда конечно. К сожалению, для проектов, разрабатываемых только под Windows — это явление крайне редкое.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.