Однажды, сидя вечером перед компьютером и предаваясь меланхолии и мыслям о бренности всего сущего, я задумчиво набрал в поиске одного крупного сайта по поиску работы аббревиатуру «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-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:

Используем 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.


Далее преобразуем курсор в экземпляр класса 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://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/