How to train your dragon. A short example on clang-c

Once, sitting in front of a computer in the evening and indulging in melancholy and thoughts about the frailty of everything, I thoughtfully typed the abbreviation “LLVM” in a search for a large job search site, not hoping, however, to see something special there, and began to look rather poor, directly let's say catch.

As expected, almost nothing special was found, but one announcement interested me. It contained the following lines:

“Who will we take“ without looking ”or the level of tasks to be performed:
You downloaded any open source project compiled with gcc (the amount of source code is more than 10 megabytes) and for the largest cpp file you were able to build an AST tree using clang with –fsyntax-only;
You downloaded any open source project built using Visual C ++ (the amount of source code is more than 10 megabytes) and for the largest cpp file you were able to build an AST tree using clang with –fsyntax-only;
You were able to write a utility that will highlight all places of declarations and use of local variables, as well as all functions not defined in this file . "

Well, I thought, no way, but entertainment for the evening.



The first two points are briefly reviewed, everything is very simple there.

How to build an AST

We take any project in c ++, you can clang itself (it is built on gcc and VC ++).

clang -std=c++11 -Xclang -ast-dump /путь/к/файлу/cpp -I/путь/к/директории/с/include/файлами -Dнужные_макросы -fsyntax-only

We get AST in text form. For a large file, AST is huge, I won’t give all ast-dump here, but for clarity, I’ll give a small piece:


You can also get the tree with another option: -ast-print. It will also be textual and huge, and I will not give it either.

Finally, you can get a graphical representation of the tree in Graphviz (widely used for debugging in LLVM). This is done using the -ast-view option. Of course, in this case Graphviz should be installed and the paths to the files 'dot' and 'gv' should be registered. In this case, many windows will open, in each of which there will be a small section of AST, for example, this:



However, before continuing, I would like to briefly tell you what AST is and what it is for. Readers with a degree in Computer Science can boldly skip through the next section, and the rest may be interesting.

Abstract Syntax Tree

You can see strict definitions on Wikipedia, and I will try to explain “on fingers”.
An abstract syntax tree is a structure by which the compiler presents the source code of a program in a form convenient for further compilation. In the leaves of the tree are variables (to be precise, links to variable declarations) and constants, at other vertices are operators, data type declarations, etc. The root of the tree is the "translation unit" of the program.

For example, a simple program:

// 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);
}

This gives rise to AST:

Using the clang-c API

In the clang compiler, each AST node is represented by an object of a particular class, and there are only three base classes: clang :: Decl (declaration class), clang :: Stmt, which includes all the operators, and the clang :: Type class, a data type class.

So, clang is written in C ++ and has an object oriented API. You can use it to write various utilities and tools using clang. However, knowledgeable people prefer another API, clang-c, which is a wrapper over the clang API written in pure C. The meaning is simple: firstly, it is simpler, secondly, the clang-c API is stable, unlike the clang API, which changes with every release. Finally, using clang-c does not preclude the use of the clang API, which we will soon see.

AST tree traversal

The first thing to do is write a tree walk in depth. This is a completely standard operation:

#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);
}

Everything is very clear here: clang_parseTranslationUnit is a function that performs all compilation steps up to and including building the AST. Any compilation options can be passed to it. In this case, the file name can be passed both in arguments and directly (source_filename). The source text can be transmitted not only as a file, but also as a CXUnsavedFile structure representing the text in memory. After parsing, the tree is traversed in depth, for each vertex, the visitor function is called, to which CXCursor, a structure representing the top of the tree, is passed. Also, the CXClientData parameter representing arbitrary user data can be passed to the visitor function.

We write the visitor function

Let's try to find all the local program variables.

 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);
            }
        }
    }

Everything here is also simple: CXCursor_VarDecl - the cursor points to a variable. dyn_cast_or_null - type conversion template in LLVM.


Next, we transform the cursor into an instance of the VarDecl class, and check whether the variable is local. If it is, we display the name of the cursor and its location in the source, using auxiliary functions for this:

//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);
}

To find the values ​​of Decl, Expr and Stmt, we use auxiliary functions:

// 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));
}

Next, we look for all uses of local variables:

// 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);
                }
            }
        }
    }

And finally, we find all calls to functions not defined in this file:

    // 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);
                }
            }
        }
    }

Here we check if the cursor is a function call (CXCursor_CallExpr). However, it should be noted that CXCursor_CallExpr is not only a function call, it is also a call to the constructor, destructor and method, so an additional check (isa) is needed. After that, we look for the definition of the function (clang_getCursorDefinition), and if we do not find (clang_equalCursors (Definition, clang_getNullCursor ())), then we found a function not defined in this file.

Test

For the test, we will write two simple programs, one in C, one in C ++.
So, the C program:

//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);
}

We run our utility, we get the output:

local variable: [email protected]:13:9
reference to local variable: [email protected]:14:5
function is not defined here: [email protected]:15:5
reference to local variable: [email protected]:16:16

Everything seems to be right. Now check on the file in C ++:

#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;
}

We get the output:

local variable: [email protected]:6:13
local variable: [email protected]:9:13
local variable: [email protected]:12:13
local variable: [email protected]:22:9
local variable: [email protected]:23:13
function is not defined here: [email protected]:25:5
reference to local variable: [email protected]:25:13

OK, everything seems to work.

How can this be used?

The extensive capabilities of clang can be used for a variety of purposes, which include parsing and transforming C, C ++, and Objective C sources.

Yet

You can also use it to search for work, but while I was writing all this, the ad disappeared from the site. Alas.

Literature

List of sources on the topic:

1. Project code on 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/