Как приручить дракона. Краткий пример на 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/http://ift.tt/2jgWYoM, 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/http://ift.tt/2kuPbJ0, <scratch space>:3:1> col:1 class BlockDecl
| |-CXXRecordDecl 0x57cc820 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:4:1> col:1 class CapturedDecl
| |-CXXRecordDecl 0x57cc8e0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:5:1> col:1 referenced class ClassScopeFunctionSpecializationDecl
| |-CXXRecordDecl 0x57cc9a0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:6:1> col:1 class EmptyDecl
| |-CXXRecordDecl 0x57cca60 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:7:1> col:1 class ExternCContextDecl
| |-CXXRecordDecl 0x57ccb20 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:8:1> col:1 class FileScopeAsmDecl
| |-CXXRecordDecl 0x57ccbe0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:9:1> col:1 referenced class FriendDecl
| |-CXXRecordDecl 0x57ccca0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:10:1> col:1 referenced class FriendTemplateDecl
| |-CXXRecordDecl 0x57ccd60 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:11:1> col:1 class ImportDecl
| |-CXXRecordDecl 0x57cce20 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:12:1> col:1 class LinkageSpecDecl
| |-CXXRecordDecl 0x57ccee0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:13:1> col:1 class NamedDecl
| |-CXXRecordDecl 0x57ccfa0 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:14:1> col:1 class LabelDecl
| |-CXXRecordDecl 0x57cd060 </home/user/LLVM/http://ift.tt/2kuPbJ0, <scratch space>:15:1> col:1 class NamespaceDecl
| |-CXXRecordDecl 0x57cd120 </home/user/LLVM/http://ift.tt/2kuPbJ0, <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<const CallExpr). После этого мы ищем определение функции (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://ift.tt/2kv71M9
3. http://ift.tt/2jh2ojJ
4. http://ift.tt/2kv6hX6
5. http://ift.tt/2jgWjDA

Let's block ads! (Why?)