How to train your dragon. Short example on clang-c

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

As expected, almost nothing was found, but one ad interested me. It had the following lines:

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



We will take a brief look at the first two points; everything is very simple there.

How to build AST

We take any project in c ++, you can clang itself (it is built on both 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 AST file has a huge size, I will not give the whole ast-dump here, but for clarity I will give a small piece:


You can also get a tree with another option: -ast-print. It will also be text 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, this should set up Graphviz and set the paths to the 'dot' and 'gv' files. In this case, many windows will open, each of which will have a small section of AST, for example, like this:



However, before continuing, I would like to briefly tell you what AST is and why it is needed. Readers with a degree in Computer Science can safely browse through the next section, and others may be interested.

Abstract Syntax Tree

Strict definitions you can see in Wikipedia, and I will try to explain "on the fingers."
An abstract syntax tree is a structure with which the compiler presents the source code of a program in a form convenient for further compilation. There are variables in the leaves of the tree (to be exact, references to variable declarations) and constants, in other vertices - 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); } 

It generates an AST:

We use clang-c API

In the clang compiler, each AST node is represented by an object of a particular class, with only three base classes: clang :: Decl (declaration class), clang :: Stmt, which includes all operators, and the clang :: Type class, the 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: first, it is simpler, and secondly, the clang-c API is stable, unlike the clang API, which changes with each release. Finally, the use of clang-c does not exclude the use of the clang API, which we will see shortly.

AST tree traversal

The first thing to do is to write a deep tree traversal. This is a completely standard operation:

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

Here, everything is very clear: clang_parseTranslationUnit is a function that performs all compilation steps before building an AST inclusive. Any compilation options can be passed to it. In this case, the file name can be passed either in arguments or directly (source_filename). The source text can be transferred not only as a file, but also as a CXUnsavedFile structure representing the text in memory. After the parsing, the tree is traversed in depth. For each vertex, the visitor function is called, to which CXCursor is passed - a structure representing the top of the tree. Also, a visitor parameter CXClientData representing arbitrary user data may be passed to the visitor function.

We write the visitor function

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

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

Here, too, everything is simple: CXCursor_VarDecl - the cursor points to a variable. dyn_cast_or_null - type conversion pattern in LLVM.


Next, we convert the cursor to an instance of the VarDecl class, and check whether the variable is local. If so, we display the name of the cursor and its location in the source code, 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 Decl, Expr and Stmt values, we use auxiliary functions:

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

Further we look for all uses of local variables:

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

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

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

Here we check whether 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 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 have found a function that is not defined in this file.

Test

For the test, we will write two simple programs, one for C, one for 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); } 

Run our utility, we get at the output:

 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 

It seems that's right. Now let's 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 at the output:

 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, it seems it works.

How can this be used?

The wide range of clang features can be used for various purposes, which include analyzing and converting source code in C, C ++ and Objective C.

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/