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