1=============================================================== 2Tutorial for building tools using LibTooling and LibASTMatchers 3=============================================================== 4 5This document is intended to show how to build a useful source-to-source 6translation tool based on Clang's `LibTooling <LibTooling.html>`_. It is 7explicitly aimed at people who are new to Clang, so all you should need 8is a working knowledge of C++ and the command line. 9 10In order to work on the compiler, you need some basic knowledge of the 11abstract syntax tree (AST). To this end, the reader is incouraged to 12skim the :doc:`Introduction to the Clang 13AST <IntroductionToTheClangAST>` 14 15Step 0: Obtaining Clang 16======================= 17 18As Clang is part of the LLVM project, you'll need to download LLVM's 19source code first. Both Clang and LLVM are maintained as Subversion 20repositories, but we'll be accessing them through the git mirror. For 21further information, see the `getting started 22guide <http://llvm.org/docs/GettingStarted.html>`_. 23 24.. code-block:: console 25 26 mkdir ~/clang-llvm && cd ~/clang-llvm 27 git clone http://llvm.org/git/llvm.git 28 cd llvm/tools 29 git clone http://llvm.org/git/clang.git 30 cd clang/tools 31 git clone http://llvm.org/git/clang-tools-extra.git extra 32 33Next you need to obtain the CMake build system and Ninja build tool. You 34may already have CMake installed, but current binary versions of CMake 35aren't built with Ninja support. 36 37.. code-block:: console 38 39 cd ~/clang-llvm 40 git clone https://github.com/martine/ninja.git 41 cd ninja 42 git checkout release 43 ./bootstrap.py 44 sudo cp ninja /usr/bin/ 45 46 cd ~/clang-llvm 47 git clone git://cmake.org/stage/cmake.git 48 cd cmake 49 git checkout next 50 ./bootstrap 51 make 52 sudo make install 53 54Okay. Now we'll build Clang! 55 56.. code-block:: console 57 58 cd ~/clang-llvm 59 mkdir build && cd build 60 cmake -G Ninja ../llvm -DLLVM_BUILD_TESTS=ON # Enable tests; default is off. 61 ninja 62 ninja check # Test LLVM only. 63 ninja clang-test # Test Clang only. 64 ninja install 65 66And we're live. 67 68All of the tests should pass, though there is a (very) small chance that 69you can catch LLVM and Clang out of sync. Running ``'git svn rebase'`` 70in both the llvm and clang directories should fix any problems. 71 72Finally, we want to set Clang as its own compiler. 73 74.. code-block:: console 75 76 cd ~/clang-llvm/build 77 ccmake ../llvm 78 79The second command will bring up a GUI for configuring Clang. You need 80to set the entry for ``CMAKE_CXX_COMPILER``. Press ``'t'`` to turn on 81advanced mode. Scroll down to ``CMAKE_CXX_COMPILER``, and set it to 82``/usr/bin/clang++``, or wherever you installed it. Press ``'c'`` to 83configure, then ``'g'`` to generate CMake's files. 84 85Finally, run ninja one last time, and you're done. 86 87Step 1: Create a ClangTool 88========================== 89 90Now that we have enough background knowledge, it's time to create the 91simplest productive ClangTool in existence: a syntax checker. While this 92already exists as ``clang-check``, it's important to understand what's 93going on. 94 95First, we'll need to create a new directory for our tool and tell CMake 96that it exists. As this is not going to be a core clang tool, it will 97live in the ``tools/extra`` repository. 98 99.. code-block:: console 100 101 cd ~/clang-llvm/llvm/tools/clang 102 mkdir tools/extra/loop-convert 103 echo 'add_subdirectory(loop-convert)' >> tools/extra/CMakeLists.txt 104 vim tools/extra/loop-convert/CMakeLists.txt 105 106CMakeLists.txt should have the following contents: 107 108:: 109 110 set(LLVM_LINK_COMPONENTS support) 111 set(LLVM_USED_LIBS clangTooling clangBasic clangAST) 112 113 add_clang_executable(loop-convert 114 LoopConvert.cpp 115 ) 116 target_link_libraries(loop-convert 117 clangTooling 118 clangBasic 119 clangASTMatchers 120 ) 121 122With that done, Ninja will be able to compile our tool. Let's give it 123something to compile! Put the following into 124``tools/extra/loop-convert/LoopConvert.cpp``. A detailed explanation of 125why the different parts are needed can be found in the `LibTooling 126documentation <LibTooling.html>`_. 127 128.. code-block:: c++ 129 130 // Declares clang::SyntaxOnlyAction. 131 #include "clang/Frontend/FrontendActions.h" 132 #include "clang/Tooling/CommonOptionsParser.h" 133 #include "clang/Tooling/Tooling.h" 134 // Declares llvm::cl::extrahelp. 135 #include "llvm/Support/CommandLine.h" 136 137 using namespace clang::tooling; 138 using namespace llvm; 139 140 // Apply a custom category to all command-line options so that they are the 141 // only ones displayed. 142 static llvm::cl::OptionCategory MyToolCategory("my-tool options"); 143 144 // CommonOptionsParser declares HelpMessage with a description of the common 145 // command-line options related to the compilation database and input files. 146 // It's nice to have this help message in all tools. 147 static cl::extrahelp CommonHelp(CommonOptionsParser::HelpMessage); 148 149 // A help message for this specific tool can be added afterwards. 150 static cl::extrahelp MoreHelp("\nMore help text..."); 151 152 int main(int argc, const char **argv) { 153 CommonOptionsParser OptionsParser(argc, argv, MyToolCategory); 154 ClangTool Tool(OptionsParser.getCompilations(), 155 OptionsParser.getSourcePathList()); 156 return Tool.run(newFrontendActionFactory<clang::SyntaxOnlyAction>().get()); 157 } 158 159And that's it! You can compile our new tool by running ninja from the 160``build`` directory. 161 162.. code-block:: console 163 164 cd ~/clang-llvm/build 165 ninja 166 167You should now be able to run the syntax checker, which is located in 168``~/clang-llvm/build/bin``, on any source file. Try it! 169 170.. code-block:: console 171 172 cat "int main() { return 0; }" > test.cpp 173 bin/loop-convert test.cpp -- 174 175Note the two dashes after we specify the source file. The additional 176options for the compiler are passed after the dashes rather than loading 177them from a compilation database - there just aren't any options needed 178right now. 179 180Intermezzo: Learn AST matcher basics 181==================================== 182 183Clang recently introduced the :doc:`ASTMatcher 184library <LibASTMatchers>` to provide a simple, powerful, and 185concise way to describe specific patterns in the AST. Implemented as a 186DSL powered by macros and templates (see 187`ASTMatchers.h <../doxygen/ASTMatchers_8h_source.html>`_ if you're 188curious), matchers offer the feel of algebraic data types common to 189functional programming languages. 190 191For example, suppose you wanted to examine only binary operators. There 192is a matcher to do exactly that, conveniently named ``binaryOperator``. 193I'll give you one guess what this matcher does: 194 195.. code-block:: c++ 196 197 binaryOperator(hasOperatorName("+"), hasLHS(integerLiteral(equals(0)))) 198 199Shockingly, it will match against addition expressions whose left hand 200side is exactly the literal 0. It will not match against other forms of 2010, such as ``'\0'`` or ``NULL``, but it will match against macros that 202expand to 0. The matcher will also not match against calls to the 203overloaded operator ``'+'``, as there is a separate ``operatorCallExpr`` 204matcher to handle overloaded operators. 205 206There are AST matchers to match all the different nodes of the AST, 207narrowing matchers to only match AST nodes fulfilling specific criteria, 208and traversal matchers to get from one kind of AST node to another. For 209a complete list of AST matchers, take a look at the `AST Matcher 210References <LibASTMatchersReference.html>`_ 211 212All matcher that are nouns describe entities in the AST and can be 213bound, so that they can be referred to whenever a match is found. To do 214so, simply call the method ``bind`` on these matchers, e.g.: 215 216.. code-block:: c++ 217 218 variable(hasType(isInteger())).bind("intvar") 219 220Step 2: Using AST matchers 221========================== 222 223Okay, on to using matchers for real. Let's start by defining a matcher 224which will capture all ``for`` statements that define a new variable 225initialized to zero. Let's start with matching all ``for`` loops: 226 227.. code-block:: c++ 228 229 forStmt() 230 231Next, we want to specify that a single variable is declared in the first 232portion of the loop, so we can extend the matcher to 233 234.. code-block:: c++ 235 236 forStmt(hasLoopInit(declStmt(hasSingleDecl(varDecl())))) 237 238Finally, we can add the condition that the variable is initialized to 239zero. 240 241.. code-block:: c++ 242 243 forStmt(hasLoopInit(declStmt(hasSingleDecl(varDecl( 244 hasInitializer(integerLiteral(equals(0)))))))) 245 246It is fairly easy to read and understand the matcher definition ("match 247loops whose init portion declares a single variable which is initialized 248to the integer literal 0"), but deciding that every piece is necessary 249is more difficult. Note that this matcher will not match loops whose 250variables are initialized to ``'\0'``, ``0.0``, ``NULL``, or any form of 251zero besides the integer 0. 252 253The last step is giving the matcher a name and binding the ``ForStmt`` 254as we will want to do something with it: 255 256.. code-block:: c++ 257 258 StatementMatcher LoopMatcher = 259 forStmt(hasLoopInit(declStmt(hasSingleDecl(varDecl( 260 hasInitializer(integerLiteral(equals(0)))))))).bind("forLoop"); 261 262Once you have defined your matchers, you will need to add a little more 263scaffolding in order to run them. Matchers are paired with a 264``MatchCallback`` and registered with a ``MatchFinder`` object, then run 265from a ``ClangTool``. More code! 266 267Add the following to ``LoopConvert.cpp``: 268 269.. code-block:: c++ 270 271 #include "clang/ASTMatchers/ASTMatchers.h" 272 #include "clang/ASTMatchers/ASTMatchFinder.h" 273 274 using namespace clang; 275 using namespace clang::ast_matchers; 276 277 StatementMatcher LoopMatcher = 278 forStmt(hasLoopInit(declStmt(hasSingleDecl(varDecl( 279 hasInitializer(integerLiteral(equals(0)))))))).bind("forLoop"); 280 281 class LoopPrinter : public MatchFinder::MatchCallback { 282 public : 283 virtual void run(const MatchFinder::MatchResult &Result) { 284 if (const ForStmt *FS = Result.Nodes.getNodeAs<clang::ForStmt>("forLoop")) 285 FS->dump(); 286 } 287 }; 288 289And change ``main()`` to: 290 291.. code-block:: c++ 292 293 int main(int argc, const char **argv) { 294 CommonOptionsParser OptionsParser(argc, argv, MyToolCategory); 295 ClangTool Tool(OptionsParser.getCompilations(), 296 OptionsParser.getSourcePathList()); 297 298 LoopPrinter Printer; 299 MatchFinder Finder; 300 Finder.addMatcher(LoopMatcher, &Printer); 301 302 return Tool.run(newFrontendActionFactory(&Finder).get()); 303 } 304 305Now, you should be able to recompile and run the code to discover for 306loops. Create a new file with a few examples, and test out our new 307handiwork: 308 309.. code-block:: console 310 311 cd ~/clang-llvm/llvm/llvm_build/ 312 ninja loop-convert 313 vim ~/test-files/simple-loops.cc 314 bin/loop-convert ~/test-files/simple-loops.cc 315 316Step 3.5: More Complicated Matchers 317=================================== 318 319Our simple matcher is capable of discovering for loops, but we would 320still need to filter out many more ourselves. We can do a good portion 321of the remaining work with some cleverly chosen matchers, but first we 322need to decide exactly which properties we want to allow. 323 324How can we characterize for loops over arrays which would be eligible 325for translation to range-based syntax? Range based loops over arrays of 326size ``N`` that: 327 328- start at index ``0`` 329- iterate consecutively 330- end at index ``N-1`` 331 332We already check for (1), so all we need to add is a check to the loop's 333condition to ensure that the loop's index variable is compared against 334``N`` and another check to ensure that the increment step just 335increments this same variable. The matcher for (2) is straightforward: 336require a pre- or post-increment of the same variable declared in the 337init portion. 338 339Unfortunately, such a matcher is impossible to write. Matchers contain 340no logic for comparing two arbitrary AST nodes and determining whether 341or not they are equal, so the best we can do is matching more than we 342would like to allow, and punting extra comparisons to the callback. 343 344In any case, we can start building this sub-matcher. We can require that 345the increment step be a unary increment like this: 346 347.. code-block:: c++ 348 349 hasIncrement(unaryOperator(hasOperatorName("++"))) 350 351Specifying what is incremented introduces another quirk of Clang's AST: 352Usages of variables are represented as ``DeclRefExpr``'s ("declaration 353reference expressions") because they are expressions which refer to 354variable declarations. To find a ``unaryOperator`` that refers to a 355specific declaration, we can simply add a second condition to it: 356 357.. code-block:: c++ 358 359 hasIncrement(unaryOperator( 360 hasOperatorName("++"), 361 hasUnaryOperand(declRefExpr()))) 362 363Furthermore, we can restrict our matcher to only match if the 364incremented variable is an integer: 365 366.. code-block:: c++ 367 368 hasIncrement(unaryOperator( 369 hasOperatorName("++"), 370 hasUnaryOperand(declRefExpr(to(varDecl(hasType(isInteger()))))))) 371 372And the last step will be to attach an identifier to this variable, so 373that we can retrieve it in the callback: 374 375.. code-block:: c++ 376 377 hasIncrement(unaryOperator( 378 hasOperatorName("++"), 379 hasUnaryOperand(declRefExpr(to( 380 varDecl(hasType(isInteger())).bind("incrementVariable")))))) 381 382We can add this code to the definition of ``LoopMatcher`` and make sure 383that our program, outfitted with the new matcher, only prints out loops 384that declare a single variable initialized to zero and have an increment 385step consisting of a unary increment of some variable. 386 387Now, we just need to add a matcher to check if the condition part of the 388``for`` loop compares a variable against the size of the array. There is 389only one problem - we don't know which array we're iterating over 390without looking at the body of the loop! We are again restricted to 391approximating the result we want with matchers, filling in the details 392in the callback. So we start with: 393 394.. code-block:: c++ 395 396 hasCondition(binaryOperator(hasOperatorName("<")) 397 398It makes sense to ensure that the left-hand side is a reference to a 399variable, and that the right-hand side has integer type. 400 401.. code-block:: c++ 402 403 hasCondition(binaryOperator( 404 hasOperatorName("<"), 405 hasLHS(declRefExpr(to(varDecl(hasType(isInteger()))))), 406 hasRHS(expr(hasType(isInteger()))))) 407 408Why? Because it doesn't work. Of the three loops provided in 409``test-files/simple.cpp``, zero of them have a matching condition. A 410quick look at the AST dump of the first for loop, produced by the 411previous iteration of loop-convert, shows us the answer: 412 413:: 414 415 (ForStmt 0x173b240 416 (DeclStmt 0x173afc8 417 0x173af50 "int i = 418 (IntegerLiteral 0x173afa8 'int' 0)") 419 <<>> 420 (BinaryOperator 0x173b060 '_Bool' '<' 421 (ImplicitCastExpr 0x173b030 'int' 422 (DeclRefExpr 0x173afe0 'int' lvalue Var 0x173af50 'i' 'int')) 423 (ImplicitCastExpr 0x173b048 'int' 424 (DeclRefExpr 0x173b008 'const int' lvalue Var 0x170fa80 'N' 'const int'))) 425 (UnaryOperator 0x173b0b0 'int' lvalue prefix '++' 426 (DeclRefExpr 0x173b088 'int' lvalue Var 0x173af50 'i' 'int')) 427 (CompoundStatement ... 428 429We already know that the declaration and increments both match, or this 430loop wouldn't have been dumped. The culprit lies in the implicit cast 431applied to the first operand (i.e. the LHS) of the less-than operator, 432an L-value to R-value conversion applied to the expression referencing 433``i``. Thankfully, the matcher library offers a solution to this problem 434in the form of ``ignoringParenImpCasts``, which instructs the matcher to 435ignore implicit casts and parentheses before continuing to match. 436Adjusting the condition operator will restore the desired match. 437 438.. code-block:: c++ 439 440 hasCondition(binaryOperator( 441 hasOperatorName("<"), 442 hasLHS(ignoringParenImpCasts(declRefExpr( 443 to(varDecl(hasType(isInteger())))))), 444 hasRHS(expr(hasType(isInteger()))))) 445 446After adding binds to the expressions we wished to capture and 447extracting the identifier strings into variables, we have array-step-2 448completed. 449 450Step 4: Retrieving Matched Nodes 451================================ 452 453So far, the matcher callback isn't very interesting: it just dumps the 454loop's AST. At some point, we will need to make changes to the input 455source code. Next, we'll work on using the nodes we bound in the 456previous step. 457 458The ``MatchFinder::run()`` callback takes a 459``MatchFinder::MatchResult&`` as its parameter. We're most interested in 460its ``Context`` and ``Nodes`` members. Clang uses the ``ASTContext`` 461class to represent contextual information about the AST, as the name 462implies, though the most functionally important detail is that several 463operations require an ``ASTContext*`` parameter. More immediately useful 464is the set of matched nodes, and how we retrieve them. 465 466Since we bind three variables (identified by ConditionVarName, 467InitVarName, and IncrementVarName), we can obtain the matched nodes by 468using the ``getNodeAs()`` member function. 469 470In ``LoopConvert.cpp`` add 471 472.. code-block:: c++ 473 474 #include "clang/AST/ASTContext.h" 475 476Change ``LoopMatcher`` to 477 478.. code-block:: c++ 479 480 StatementMatcher LoopMatcher = 481 forStmt(hasLoopInit(declStmt( 482 hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0)))) 483 .bind("initVarName")))), 484 hasIncrement(unaryOperator( 485 hasOperatorName("++"), 486 hasUnaryOperand(declRefExpr( 487 to(varDecl(hasType(isInteger())).bind("incVarName")))))), 488 hasCondition(binaryOperator( 489 hasOperatorName("<"), 490 hasLHS(ignoringParenImpCasts(declRefExpr( 491 to(varDecl(hasType(isInteger())).bind("condVarName"))))), 492 hasRHS(expr(hasType(isInteger())))))).bind("forLoop"); 493 494And change ``LoopPrinter::run`` to 495 496.. code-block:: c++ 497 498 void LoopPrinter::run(const MatchFinder::MatchResult &Result) { 499 ASTContext *Context = Result.Context; 500 const ForStmt *FS = Result.Nodes.getStmtAs<ForStmt>("forLoop"); 501 // We do not want to convert header files! 502 if (!FS || !Context->getSourceManager().isFromMainFile(FS->getForLoc())) 503 return; 504 const VarDecl *IncVar = Result.Nodes.getNodeAs<VarDecl>("incVarName"); 505 const VarDecl *CondVar = Result.Nodes.getNodeAs<VarDecl>("condVarName"); 506 const VarDecl *InitVar = Result.Nodes.getNodeAs<VarDecl>("initVarName"); 507 508 if (!areSameVariable(IncVar, CondVar) || !areSameVariable(IncVar, InitVar)) 509 return; 510 llvm::outs() << "Potential array-based loop discovered.\n"; 511 } 512 513Clang associates a ``VarDecl`` with each variable to represent the variable's 514declaration. Since the "canonical" form of each declaration is unique by 515address, all we need to do is make sure neither ``ValueDecl`` (base class of 516``VarDecl``) is ``NULL`` and compare the canonical Decls. 517 518.. code-block:: c++ 519 520 static bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) { 521 return First && Second && 522 First->getCanonicalDecl() == Second->getCanonicalDecl(); 523 } 524 525If execution reaches the end of ``LoopPrinter::run()``, we know that the 526loop shell that looks like 527 528.. code-block:: c++ 529 530 for (int i= 0; i < expr(); ++i) { ... } 531 532For now, we will just print a message explaining that we found a loop. 533The next section will deal with recursively traversing the AST to 534discover all changes needed. 535 536As a side note, it's not as trivial to test if two expressions are the same, 537though Clang has already done the hard work for us by providing a way to 538canonicalize expressions: 539 540.. code-block:: c++ 541 542 static bool areSameExpr(ASTContext *Context, const Expr *First, 543 const Expr *Second) { 544 if (!First || !Second) 545 return false; 546 llvm::FoldingSetNodeID FirstID, SecondID; 547 First->Profile(FirstID, *Context, true); 548 Second->Profile(SecondID, *Context, true); 549 return FirstID == SecondID; 550 } 551 552This code relies on the comparison between two 553``llvm::FoldingSetNodeIDs``. As the documentation for 554``Stmt::Profile()`` indicates, the ``Profile()`` member function builds 555a description of a node in the AST, based on its properties, along with 556those of its children. ``FoldingSetNodeID`` then serves as a hash we can 557use to compare expressions. We will need ``areSameExpr`` later. Before 558you run the new code on the additional loops added to 559test-files/simple.cpp, try to figure out which ones will be considered 560potentially convertible. 561