Teach SourceManager::getLocation() how to cope with a source file
[clang.git] / docs / InternalsManual.html
blob596c1b2f1243ba99e19b6754bccef1f7875f740c
1 <html>
2 <head>
3 <title>"Clang" CFE Internals Manual</title>
4 <link type="text/css" rel="stylesheet" href="../menu.css" />
5 <link type="text/css" rel="stylesheet" href="../content.css" />
6 <style type="text/css">
7 td {
8 vertical-align: top;
10 </style>
11 </head>
12 <body>
14 <!--#include virtual="../menu.html.incl"-->
16 <div id="content">
18 <h1>"Clang" CFE Internals Manual</h1>
20 <ul>
21 <li><a href="#intro">Introduction</a></li>
22 <li><a href="#libsystem">LLVM System and Support Libraries</a></li>
23 <li><a href="#libbasic">The Clang 'Basic' Library</a>
24 <ul>
25 <li><a href="#Diagnostics">The Diagnostics Subsystem</a></li>
26 <li><a href="#SourceLocation">The SourceLocation and SourceManager
27 classes</a></li>
28 <li><a href="#SourceRange">SourceRange and CharSourceRange</a></li>
29 </ul>
30 </li>
31 <li><a href="#libdriver">The Driver Library</a>
32 <ul>
33 </ul>
34 </li>
35 <li><a href="#pch">Precompiled Headers</a>
36 <li><a href="#libfrontend">The Frontend Library</a>
37 <ul>
38 </ul>
39 </li>
40 <li><a href="#liblex">The Lexer and Preprocessor Library</a>
41 <ul>
42 <li><a href="#Token">The Token class</a></li>
43 <li><a href="#Lexer">The Lexer class</a></li>
44 <li><a href="#AnnotationToken">Annotation Tokens</a></li>
45 <li><a href="#TokenLexer">The TokenLexer class</a></li>
46 <li><a href="#MultipleIncludeOpt">The MultipleIncludeOpt class</a></li>
47 </ul>
48 </li>
49 <li><a href="#libparse">The Parser Library</a>
50 <ul>
51 </ul>
52 </li>
53 <li><a href="#libast">The AST Library</a>
54 <ul>
55 <li><a href="#Type">The Type class and its subclasses</a></li>
56 <li><a href="#QualType">The QualType class</a></li>
57 <li><a href="#DeclarationName">Declaration names</a></li>
58 <li><a href="#DeclContext">Declaration contexts</a>
59 <ul>
60 <li><a href="#Redeclarations">Redeclarations and Overloads</a></li>
61 <li><a href="#LexicalAndSemanticContexts">Lexical and Semantic
62 Contexts</a></li>
63 <li><a href="#TransparentContexts">Transparent Declaration Contexts</a></li>
64 <li><a href="#MultiDeclContext">Multiply-Defined Declaration Contexts</a></li>
65 </ul>
66 </li>
67 <li><a href="#CFG">The CFG class</a></li>
68 <li><a href="#Constants">Constant Folding in the Clang AST</a></li>
69 </ul>
70 </li>
71 <li><a href="libIndex.html">The Index Library</a></li>
72 <li><a href="#Howtos">Howto guides</a>
73 <ul>
74 <li><a href="#AddingAttributes">How to add an attribute</a></li>
75 </ul>
76 </li>
77 </ul>
80 <!-- ======================================================================= -->
81 <h2 id="intro">Introduction</h2>
82 <!-- ======================================================================= -->
84 <p>This document describes some of the more important APIs and internal design
85 decisions made in the Clang C front-end. The purpose of this document is to
86 both capture some of this high level information and also describe some of the
87 design decisions behind it. This is meant for people interested in hacking on
88 Clang, not for end-users. The description below is categorized by
89 libraries, and does not describe any of the clients of the libraries.</p>
91 <!-- ======================================================================= -->
92 <h2 id="libsystem">LLVM System and Support Libraries</h2>
93 <!-- ======================================================================= -->
95 <p>The LLVM libsystem library provides the basic Clang system abstraction layer,
96 which is used for file system access. The LLVM libsupport library provides many
97 underlying libraries and <a
98 href="http://llvm.org/docs/ProgrammersManual.html">data-structures</a>,
99 including command line option
100 processing and various containers.</p>
102 <!-- ======================================================================= -->
103 <h2 id="libbasic">The Clang 'Basic' Library</h2>
104 <!-- ======================================================================= -->
106 <p>This library certainly needs a better name. The 'basic' library contains a
107 number of low-level utilities for tracking and manipulating source buffers,
108 locations within the source buffers, diagnostics, tokens, target abstraction,
109 and information about the subset of the language being compiled for.</p>
111 <p>Part of this infrastructure is specific to C (such as the TargetInfo class),
112 other parts could be reused for other non-C-based languages (SourceLocation,
113 SourceManager, Diagnostics, FileManager). When and if there is future demand
114 we can figure out if it makes sense to introduce a new library, move the general
115 classes somewhere else, or introduce some other solution.</p>
117 <p>We describe the roles of these classes in order of their dependencies.</p>
120 <!-- ======================================================================= -->
121 <h3 id="Diagnostics">The Diagnostics Subsystem</h3>
122 <!-- ======================================================================= -->
124 <p>The Clang Diagnostics subsystem is an important part of how the compiler
125 communicates with the human. Diagnostics are the warnings and errors produced
126 when the code is incorrect or dubious. In Clang, each diagnostic produced has
127 (at the minimum) a unique ID, an English translation associated with it, a <a
128 href="#SourceLocation">SourceLocation</a> to "put the caret", and a severity (e.g.
129 <tt>WARNING</tt> or <tt>ERROR</tt>). They can also optionally include a number
130 of arguments to the dianostic (which fill in "%0"'s in the string) as well as a
131 number of source ranges that related to the diagnostic.</p>
133 <p>In this section, we'll be giving examples produced by the Clang command line
134 driver, but diagnostics can be <a href="#DiagnosticClient">rendered in many
135 different ways</a> depending on how the DiagnosticClient interface is
136 implemented. A representative example of a diagnostic is:</p>
138 <pre>
139 t.c:38:15: error: invalid operands to binary expression ('int *' and '_Complex float')
140 <font color="darkgreen">P = (P-42) + Gamma*4;</font>
141 <font color="blue">~~~~~~ ^ ~~~~~~~</font>
142 </pre>
144 <p>In this example, you can see the English translation, the severity (error),
145 you can see the source location (the caret ("^") and file/line/column info),
146 the source ranges "~~~~", arguments to the diagnostic ("int*" and "_Complex
147 float"). You'll have to believe me that there is a unique ID backing the
148 diagnostic :).</p>
150 <p>Getting all of this to happen has several steps and involves many moving
151 pieces, this section describes them and talks about best practices when adding
152 a new diagnostic.</p>
154 <!-- ============================== -->
155 <h4>The Diagnostic*Kinds.def files</h4>
156 <!-- ============================== -->
158 <p>Diagnostics are created by adding an entry to one of the <tt>
159 clang/Basic/Diagnostic*Kinds.def</tt> files, depending on what library will
160 be using it. This file encodes the unique ID of the
161 diagnostic (as an enum, the first argument), the severity of the diagnostic
162 (second argument) and the English translation + format string.</p>
164 <p>There is little sanity with the naming of the unique ID's right now. Some
165 start with err_, warn_, ext_ to encode the severity into the name. Since the
166 enum is referenced in the C++ code that produces the diagnostic, it is somewhat
167 useful for it to be reasonably short.</p>
169 <p>The severity of the diagnostic comes from the set {<tt>NOTE</tt>,
170 <tt>WARNING</tt>, <tt>EXTENSION</tt>, <tt>EXTWARN</tt>, <tt>ERROR</tt>}. The
171 <tt>ERROR</tt> severity is used for diagnostics indicating the program is never
172 acceptable under any circumstances. When an error is emitted, the AST for the
173 input code may not be fully built. The <tt>EXTENSION</tt> and <tt>EXTWARN</tt>
174 severities are used for extensions to the language that Clang accepts. This
175 means that Clang fully understands and can represent them in the AST, but we
176 produce diagnostics to tell the user their code is non-portable. The difference
177 is that the former are ignored by default, and the later warn by default. The
178 <tt>WARNING</tt> severity is used for constructs that are valid in the currently
179 selected source language but that are dubious in some way. The <tt>NOTE</tt>
180 level is used to staple more information onto previous diagnostics.</p>
182 <p>These <em>severities</em> are mapped into a smaller set (the
183 Diagnostic::Level enum, {<tt>Ignored</tt>, <tt>Note</tt>, <tt>Warning</tt>,
184 <tt>Error</tt>, <tt>Fatal</tt> }) of output <em>levels</em> by the diagnostics
185 subsystem based on various configuration options. Clang internally supports a
186 fully fine grained mapping mechanism that allows you to map almost any
187 diagnostic to the output level that you want. The only diagnostics that cannot
188 be mapped are <tt>NOTE</tt>s, which always follow the severity of the previously
189 emitted diagnostic and <tt>ERROR</tt>s, which can only be mapped to
190 <tt>Fatal</tt> (it is not possible to turn an error into a warning,
191 for example).</p>
193 <p>Diagnostic mappings are used in many ways. For example, if the user
194 specifies <tt>-pedantic</tt>, <tt>EXTENSION</tt> maps to <tt>Warning</tt>, if
195 they specify <tt>-pedantic-errors</tt>, it turns into <tt>Error</tt>. This is
196 used to implement options like <tt>-Wunused_macros</tt>, <tt>-Wundef</tt> etc.
197 </p>
200 Mapping to <tt>Fatal</tt> should only be used for diagnostics that are
201 considered so severe that error recovery won't be able to recover sensibly from
202 them (thus spewing a ton of bogus errors). One example of this class of error
203 are failure to #include a file.
204 </p>
206 <!-- ================= -->
207 <h4>The Format String</h4>
208 <!-- ================= -->
210 <p>The format string for the diagnostic is very simple, but it has some power.
211 It takes the form of a string in English with markers that indicate where and
212 how arguments to the diagnostic are inserted and formatted. For example, here
213 are some simple format strings:</p>
215 <pre>
216 "binary integer literals are an extension"
217 "format string contains '\\0' within the string body"
218 "more '<b>%%</b>' conversions than data arguments"
219 "invalid operands to binary expression (<b>%0</b> and <b>%1</b>)"
220 "overloaded '<b>%0</b>' must be a <b>%select{unary|binary|unary or binary}2</b> operator"
221 " (has <b>%1</b> parameter<b>%s1</b>)"
222 </pre>
224 <p>These examples show some important points of format strings. You can use any
225 plain ASCII character in the diagnostic string except "%" without a problem,
226 but these are C strings, so you have to use and be aware of all the C escape
227 sequences (as in the second example). If you want to produce a "%" in the
228 output, use the "%%" escape sequence, like the third diagnostic. Finally,
229 Clang uses the "%...[digit]" sequences to specify where and how arguments to
230 the diagnostic are formatted.</p>
232 <p>Arguments to the diagnostic are numbered according to how they are specified
233 by the C++ code that <a href="#producingdiag">produces them</a>, and are
234 referenced by <tt>%0</tt> .. <tt>%9</tt>. If you have more than 10 arguments
235 to your diagnostic, you are doing something wrong :). Unlike printf, there
236 is no requirement that arguments to the diagnostic end up in the output in
237 the same order as they are specified, you could have a format string with
238 <tt>"%1 %0"</tt> that swaps them, for example. The text in between the
239 percent and digit are formatting instructions. If there are no instructions,
240 the argument is just turned into a string and substituted in.</p>
242 <p>Here are some "best practices" for writing the English format string:</p>
244 <ul>
245 <li>Keep the string short. It should ideally fit in the 80 column limit of the
246 <tt>DiagnosticKinds.def</tt> file. This avoids the diagnostic wrapping when
247 printed, and forces you to think about the important point you are conveying
248 with the diagnostic.</li>
249 <li>Take advantage of location information. The user will be able to see the
250 line and location of the caret, so you don't need to tell them that the
251 problem is with the 4th argument to the function: just point to it.</li>
252 <li>Do not capitalize the diagnostic string, and do not end it with a
253 period.</li>
254 <li>If you need to quote something in the diagnostic string, use single
255 quotes.</li>
256 </ul>
258 <p>Diagnostics should never take random English strings as arguments: you
259 shouldn't use <tt>"you have a problem with %0"</tt> and pass in things like
260 <tt>"your argument"</tt> or <tt>"your return value"</tt> as arguments. Doing
261 this prevents <a href="translation">translating</a> the Clang diagnostics to
262 other languages (because they'll get random English words in their otherwise
263 localized diagnostic). The exceptions to this are C/C++ language keywords
264 (e.g. auto, const, mutable, etc) and C/C++ operators (<tt>/=</tt>). Note
265 that things like "pointer" and "reference" are not keywords. On the other
266 hand, you <em>can</em> include anything that comes from the user's source code,
267 including variable names, types, labels, etc. The 'select' format can be
268 used to achieve this sort of thing in a localizable way, see below.</p>
270 <!-- ==================================== -->
271 <h4>Formatting a Diagnostic Argument</a></h4>
272 <!-- ==================================== -->
274 <p>Arguments to diagnostics are fully typed internally, and come from a couple
275 different classes: integers, types, names, and random strings. Depending on
276 the class of the argument, it can be optionally formatted in different ways.
277 This gives the DiagnosticClient information about what the argument means
278 without requiring it to use a specific presentation (consider this MVC for
279 Clang :).</p>
281 <p>Here are the different diagnostic argument formats currently supported by
282 Clang:</p>
284 <table>
285 <tr><td colspan="2"><b>"s" format</b></td></tr>
286 <tr><td>Example:</td><td><tt>"requires %1 parameter%s1"</tt></td></tr>
287 <tr><td>Class:</td><td>Integers</td></tr>
288 <tr><td>Description:</td><td>This is a simple formatter for integers that is
289 useful when producing English diagnostics. When the integer is 1, it prints
290 as nothing. When the integer is not 1, it prints as "s". This allows some
291 simple grammatical forms to be to be handled correctly, and eliminates the
292 need to use gross things like <tt>"requires %1 parameter(s)"</tt>.</td></tr>
294 <tr><td colspan="2"><b>"select" format</b></td></tr>
295 <tr><td>Example:</td><td><tt>"must be a %select{unary|binary|unary or binary}2
296 operator"</tt></td></tr>
297 <tr><td>Class:</td><td>Integers</td></tr>
298 <tr><td>Description:</td><td><p>This format specifier is used to merge multiple
299 related diagnostics together into one common one, without requiring the
300 difference to be specified as an English string argument. Instead of
301 specifying the string, the diagnostic gets an integer argument and the
302 format string selects the numbered option. In this case, the "%2" value
303 must be an integer in the range [0..2]. If it is 0, it prints 'unary', if
304 it is 1 it prints 'binary' if it is 2, it prints 'unary or binary'. This
305 allows other language translations to substitute reasonable words (or entire
306 phrases) based on the semantics of the diagnostic instead of having to do
307 things textually.</p>
308 <p>The selected string does undergo formatting.</p></td></tr>
310 <tr><td colspan="2"><b>"plural" format</b></td></tr>
311 <tr><td>Example:</td><td><tt>"you have %1 %plural{1:mouse|:mice}1 connected to
312 your computer"</tt></td></tr>
313 <tr><td>Class:</td><td>Integers</td></tr>
314 <tr><td>Description:</td><td><p>This is a formatter for complex plural forms.
315 It is designed to handle even the requirements of languages with very
316 complex plural forms, as many Baltic languages have. The argument consists
317 of a series of expression/form pairs, separated by ':', where the first form
318 whose expression evaluates to true is the result of the modifier.</p>
319 <p>An expression can be empty, in which case it is always true. See the
320 example at the top. Otherwise, it is a series of one or more numeric
321 conditions, separated by ','. If any condition matches, the expression
322 matches. Each numeric condition can take one of three forms.</p>
323 <ul>
324 <li>number: A simple decimal number matches if the argument is the same
325 as the number. Example: <tt>"%plural{1:mouse|:mice}4"</tt></li>
326 <li>range: A range in square brackets matches if the argument is within
327 the range. Then range is inclusive on both ends. Example:
328 <tt>"%plural{0:none|1:one|[2,5]:some|:many}2"</tt></li>
329 <li>modulo: A modulo operator is followed by a number, and
330 equals sign and either a number or a range. The tests are the
331 same as for plain
332 numbers and ranges, but the argument is taken modulo the number first.
333 Example: <tt>"%plural{%100=0:even hundred|%100=[1,50]:lower half|:everything
334 else}1"</tt></li>
335 </ul>
336 <p>The parser is very unforgiving. A syntax error, even whitespace, will
337 abort, as will a failure to match the argument against any
338 expression.</p></td></tr>
340 <tr><td colspan="2"><b>"ordinal" format</b></td></tr>
341 <tr><td>Example:</td><td><tt>"ambiguity in %ordinal0 argument"</tt></td></tr>
342 <tr><td>Class:</td><td>Integers</td></tr>
343 <tr><td>Description:</td><td><p>This is a formatter which represents the
344 argument number as an ordinal: the value <tt>1</tt> becomes <tt>1st</tt>,
345 <tt>3</tt> becomes <tt>3rd</tt>, and so on. Values less than <tt>1</tt>
346 are not supported.</p>
347 <p>This formatter is currently hard-coded to use English ordinals.</p></td></tr>
349 <tr><td colspan="2"><b>"objcclass" format</b></td></tr>
350 <tr><td>Example:</td><td><tt>"method %objcclass0 not found"</tt></td></tr>
351 <tr><td>Class:</td><td>DeclarationName</td></tr>
352 <tr><td>Description:</td><td><p>This is a simple formatter that indicates the
353 DeclarationName corresponds to an Objective-C class method selector. As
354 such, it prints the selector with a leading '+'.</p></td></tr>
356 <tr><td colspan="2"><b>"objcinstance" format</b></td></tr>
357 <tr><td>Example:</td><td><tt>"method %objcinstance0 not found"</tt></td></tr>
358 <tr><td>Class:</td><td>DeclarationName</td></tr>
359 <tr><td>Description:</td><td><p>This is a simple formatter that indicates the
360 DeclarationName corresponds to an Objective-C instance method selector. As
361 such, it prints the selector with a leading '-'.</p></td></tr>
363 <tr><td colspan="2"><b>"q" format</b></td></tr>
364 <tr><td>Example:</td><td><tt>"candidate found by name lookup is %q0"</tt></td></tr>
365 <tr><td>Class:</td><td>NamedDecl*</td></tr>
366 <tr><td>Description</td><td><p>This formatter indicates that the fully-qualified name of the declaration should be printed, e.g., "std::vector" rather than "vector".</p></td></tr>
368 </table>
370 <p>It is really easy to add format specifiers to the Clang diagnostics system,
371 but they should be discussed before they are added. If you are creating a lot
372 of repetitive diagnostics and/or have an idea for a useful formatter, please
373 bring it up on the cfe-dev mailing list.</p>
375 <!-- ===================================================== -->
376 <h4><a name="#producingdiag">Producing the Diagnostic</a></h4>
377 <!-- ===================================================== -->
379 <p>Now that you've created the diagnostic in the DiagnosticKinds.def file, you
380 need to write the code that detects the condition in question and emits the
381 new diagnostic. Various components of Clang (e.g. the preprocessor, Sema,
382 etc) provide a helper function named "Diag". It creates a diagnostic and
383 accepts the arguments, ranges, and other information that goes along with
384 it.</p>
386 <p>For example, the binary expression error comes from code like this:</p>
388 <pre>
389 if (various things that are bad)
390 Diag(Loc, diag::err_typecheck_invalid_operands)
391 &lt;&lt; lex-&gt;getType() &lt;&lt; rex-&gt;getType()
392 &lt;&lt; lex-&gt;getSourceRange() &lt;&lt; rex-&gt;getSourceRange();
393 </pre>
395 <p>This shows that use of the Diag method: they take a location (a <a
396 href="#SourceLocation">SourceLocation</a> object) and a diagnostic enum value
397 (which matches the name from DiagnosticKinds.def). If the diagnostic takes
398 arguments, they are specified with the &lt;&lt; operator: the first argument
399 becomes %0, the second becomes %1, etc. The diagnostic interface allows you to
400 specify arguments of many different types, including <tt>int</tt> and
401 <tt>unsigned</tt> for integer arguments, <tt>const char*</tt> and
402 <tt>std::string</tt> for string arguments, <tt>DeclarationName</tt> and
403 <tt>const IdentifierInfo*</tt> for names, <tt>QualType</tt> for types, etc.
404 SourceRanges are also specified with the &lt;&lt; operator, but do not have a
405 specific ordering requirement.</p>
407 <p>As you can see, adding and producing a diagnostic is pretty straightforward.
408 The hard part is deciding exactly what you need to say to help the user, picking
409 a suitable wording, and providing the information needed to format it correctly.
410 The good news is that the call site that issues a diagnostic should be
411 completely independent of how the diagnostic is formatted and in what language
412 it is rendered.
413 </p>
415 <!-- ==================================================== -->
416 <h4 id="code-modification-hints">Code Modification Hints</h4>
417 <!-- ==================================================== -->
419 <p>In some cases, the front end emits diagnostics when it is clear
420 that some small change to the source code would fix the problem. For
421 example, a missing semicolon at the end of a statement or a use of
422 deprecated syntax that is easily rewritten into a more modern form.
423 Clang tries very hard to emit the diagnostic and recover gracefully
424 in these and other cases.</p>
426 <p>However, for these cases where the fix is obvious, the diagnostic
427 can be annotated with a code
428 modification "hint" that describes how to change the code referenced
429 by the diagnostic to fix the problem. For example, it might add the
430 missing semicolon at the end of the statement or rewrite the use of a
431 deprecated construct into something more palatable. Here is one such
432 example C++ front end, where we warn about the right-shift operator
433 changing meaning from C++98 to C++0x:</p>
435 <pre>
436 test.cpp:3:7: warning: use of right-shift operator ('&gt;&gt;') in template argument will require parentheses in C++0x
437 A&lt;100 &gt;&gt; 2&gt; *a;
440 </pre>
442 <p>Here, the code modification hint is suggesting that parentheses be
443 added, and showing exactly where those parentheses would be inserted
444 into the source code. The code modification hints themselves describe
445 what changes to make to the source code in an abstract manner, which
446 the text diagnostic printer renders as a line of "insertions" below
447 the caret line. <a href="#DiagnosticClient">Other diagnostic
448 clients</a> might choose to render the code differently (e.g., as
449 markup inline) or even give the user the ability to automatically fix
450 the problem.</p>
452 <p>All code modification hints are described by the
453 <code>CodeModificationHint</code> class, instances of which should be
454 attached to the diagnostic using the &lt;&lt; operator in the same way
455 that highlighted source ranges and arguments are passed to the
456 diagnostic. Code modification hints can be created with one of three
457 constructors:</p>
459 <dl>
460 <dt><code>CodeModificationHint::CreateInsertion(Loc, Code)</code></dt>
461 <dd>Specifies that the given <code>Code</code> (a string) should be inserted
462 before the source location <code>Loc</code>.</dd>
464 <dt><code>CodeModificationHint::CreateRemoval(Range)</code></dt>
465 <dd>Specifies that the code in the given source <code>Range</code>
466 should be removed.</dd>
468 <dt><code>CodeModificationHint::CreateReplacement(Range, Code)</code></dt>
469 <dd>Specifies that the code in the given source <code>Range</code>
470 should be removed, and replaced with the given <code>Code</code> string.</dd>
471 </dl>
473 <!-- ============================================================= -->
474 <h4><a name="DiagnosticClient">The DiagnosticClient Interface</a></h4>
475 <!-- ============================================================= -->
477 <p>Once code generates a diagnostic with all of the arguments and the rest of
478 the relevant information, Clang needs to know what to do with it. As previously
479 mentioned, the diagnostic machinery goes through some filtering to map a
480 severity onto a diagnostic level, then (assuming the diagnostic is not mapped to
481 "<tt>Ignore</tt>") it invokes an object that implements the DiagnosticClient
482 interface with the information.</p>
484 <p>It is possible to implement this interface in many different ways. For
485 example, the normal Clang DiagnosticClient (named 'TextDiagnosticPrinter') turns
486 the arguments into strings (according to the various formatting rules), prints
487 out the file/line/column information and the string, then prints out the line of
488 code, the source ranges, and the caret. However, this behavior isn't required.
489 </p>
491 <p>Another implementation of the DiagnosticClient interface is the
492 'TextDiagnosticBuffer' class, which is used when Clang is in -verify mode.
493 Instead of formatting and printing out the diagnostics, this implementation just
494 captures and remembers the diagnostics as they fly by. Then -verify compares
495 the list of produced diagnostics to the list of expected ones. If they disagree,
496 it prints out its own output.
497 </p>
499 <p>There are many other possible implementations of this interface, and this is
500 why we prefer diagnostics to pass down rich structured information in arguments.
501 For example, an HTML output might want declaration names be linkified to where
502 they come from in the source. Another example is that a GUI might let you click
503 on typedefs to expand them. This application would want to pass significantly
504 more information about types through to the GUI than a simple flat string. The
505 interface allows this to happen.</p>
507 <!-- ====================================================== -->
508 <h4><a name="translation">Adding Translations to Clang</a></h4>
509 <!-- ====================================================== -->
511 <p>Not possible yet! Diagnostic strings should be written in UTF-8, the client
512 can translate to the relevant code page if needed. Each translation completely
513 replaces the format string for the diagnostic.</p>
516 <!-- ======================================================================= -->
517 <h3 id="SourceLocation">The SourceLocation and SourceManager classes</h3>
518 <!-- ======================================================================= -->
520 <p>Strangely enough, the SourceLocation class represents a location within the
521 source code of the program. Important design points include:</p>
523 <ol>
524 <li>sizeof(SourceLocation) must be extremely small, as these are embedded into
525 many AST nodes and are passed around often. Currently it is 32 bits.</li>
526 <li>SourceLocation must be a simple value object that can be efficiently
527 copied.</li>
528 <li>We should be able to represent a source location for any byte of any input
529 file. This includes in the middle of tokens, in whitespace, in trigraphs,
530 etc.</li>
531 <li>A SourceLocation must encode the current #include stack that was active when
532 the location was processed. For example, if the location corresponds to a
533 token, it should contain the set of #includes active when the token was
534 lexed. This allows us to print the #include stack for a diagnostic.</li>
535 <li>SourceLocation must be able to describe macro expansions, capturing both
536 the ultimate instantiation point and the source of the original character
537 data.</li>
538 </ol>
540 <p>In practice, the SourceLocation works together with the SourceManager class
541 to encode two pieces of information about a location: its spelling location
542 and its instantiation location. For most tokens, these will be the same.
543 However, for a macro expansion (or tokens that came from a _Pragma directive)
544 these will describe the location of the characters corresponding to the token
545 and the location where the token was used (i.e. the macro instantiation point
546 or the location of the _Pragma itself).</p>
548 <p>The Clang front-end inherently depends on the location of a token being
549 tracked correctly. If it is ever incorrect, the front-end may get confused and
550 die. The reason for this is that the notion of the 'spelling' of a Token in
551 Clang depends on being able to find the original input characters for the token.
552 This concept maps directly to the "spelling location" for the token.</p>
555 <!-- ======================================================================= -->
556 <h3 id="SourceRange">SourceRange and CharSourceRange</h3>
557 <!-- ======================================================================= -->
558 <!-- mostly taken from
559 http://lists.cs.uiuc.edu/pipermail/cfe-dev/2010-August/010595.html -->
561 <p>Clang represents most source ranges by [first, last], where first and last
562 each point to the beginning of their respective tokens. For example
563 consider the SourceRange of the following statement:</p>
564 <pre>
565 x = foo + bar;
566 ^first ^last
567 </pre>
569 <p>To map from this representation to a character-based
570 representation, the 'last' location needs to be adjusted to point to
571 (or past) the end of that token with either
572 <code>Lexer::MeasureTokenLength()</code> or
573 <code>Lexer::getLocForEndOfToken()</code>. For the rare cases
574 where character-level source ranges information is needed we use
575 the <code>CharSourceRange</code> class.</p>
578 <!-- ======================================================================= -->
579 <h2 id="libdriver">The Driver Library</h2>
580 <!-- ======================================================================= -->
582 <p>The clang Driver and library are documented <a
583 href="DriverInternals.html">here<a>.<p>
585 <!-- ======================================================================= -->
586 <h2 id="pch">Precompiled Headers</h2>
587 <!-- ======================================================================= -->
589 <p>Clang supports two implementations of precompiled headers. The
590 default implementation, precompiled headers (<a
591 href="PCHInternals.html">PCH</a>) uses a serialized representation
592 of Clang's internal data structures, encoded with the <a
593 href="http://llvm.org/docs/BitCodeFormat.html">LLVM bitstream
594 format</a>. Pretokenized headers (<a
595 href="PTHInternals.html">PTH</a>), on the other hand, contain a
596 serialized representation of the tokens encountered when
597 preprocessing a header (and anything that header includes).</p>
600 <!-- ======================================================================= -->
601 <h2 id="libfrontend">The Frontend Library</h2>
602 <!-- ======================================================================= -->
604 <p>The Frontend library contains functionality useful for building
605 tools on top of the clang libraries, for example several methods for
606 outputting diagnostics.</p>
608 <!-- ======================================================================= -->
609 <h2 id="liblex">The Lexer and Preprocessor Library</h2>
610 <!-- ======================================================================= -->
612 <p>The Lexer library contains several tightly-connected classes that are involved
613 with the nasty process of lexing and preprocessing C source code. The main
614 interface to this library for outside clients is the large <a
615 href="#Preprocessor">Preprocessor</a> class.
616 It contains the various pieces of state that are required to coherently read
617 tokens out of a translation unit.</p>
619 <p>The core interface to the Preprocessor object (once it is set up) is the
620 Preprocessor::Lex method, which returns the next <a href="#Token">Token</a> from
621 the preprocessor stream. There are two types of token providers that the
622 preprocessor is capable of reading from: a buffer lexer (provided by the <a
623 href="#Lexer">Lexer</a> class) and a buffered token stream (provided by the <a
624 href="#TokenLexer">TokenLexer</a> class).
627 <!-- ======================================================================= -->
628 <h3 id="Token">The Token class</h3>
629 <!-- ======================================================================= -->
631 <p>The Token class is used to represent a single lexed token. Tokens are
632 intended to be used by the lexer/preprocess and parser libraries, but are not
633 intended to live beyond them (for example, they should not live in the ASTs).<p>
635 <p>Tokens most often live on the stack (or some other location that is efficient
636 to access) as the parser is running, but occasionally do get buffered up. For
637 example, macro definitions are stored as a series of tokens, and the C++
638 front-end periodically needs to buffer tokens up for tentative parsing and
639 various pieces of look-ahead. As such, the size of a Token matter. On a 32-bit
640 system, sizeof(Token) is currently 16 bytes.</p>
642 <p>Tokens occur in two forms: "<a href="#AnnotationToken">Annotation
643 Tokens</a>" and normal tokens. Normal tokens are those returned by the lexer,
644 annotation tokens represent semantic information and are produced by the parser,
645 replacing normal tokens in the token stream. Normal tokens contain the
646 following information:</p>
648 <ul>
649 <li><b>A SourceLocation</b> - This indicates the location of the start of the
650 token.</li>
652 <li><b>A length</b> - This stores the length of the token as stored in the
653 SourceBuffer. For tokens that include them, this length includes trigraphs and
654 escaped newlines which are ignored by later phases of the compiler. By pointing
655 into the original source buffer, it is always possible to get the original
656 spelling of a token completely accurately.</li>
658 <li><b>IdentifierInfo</b> - If a token takes the form of an identifier, and if
659 identifier lookup was enabled when the token was lexed (e.g. the lexer was not
660 reading in 'raw' mode) this contains a pointer to the unique hash value for the
661 identifier. Because the lookup happens before keyword identification, this
662 field is set even for language keywords like 'for'.</li>
664 <li><b>TokenKind</b> - This indicates the kind of token as classified by the
665 lexer. This includes things like <tt>tok::starequal</tt> (for the "*="
666 operator), <tt>tok::ampamp</tt> for the "&amp;&amp;" token, and keyword values
667 (e.g. <tt>tok::kw_for</tt>) for identifiers that correspond to keywords. Note
668 that some tokens can be spelled multiple ways. For example, C++ supports
669 "operator keywords", where things like "and" are treated exactly like the
670 "&amp;&amp;" operator. In these cases, the kind value is set to
671 <tt>tok::ampamp</tt>, which is good for the parser, which doesn't have to
672 consider both forms. For something that cares about which form is used (e.g.
673 the preprocessor 'stringize' operator) the spelling indicates the original
674 form.</li>
676 <li><b>Flags</b> - There are currently four flags tracked by the
677 lexer/preprocessor system on a per-token basis:
679 <ol>
680 <li><b>StartOfLine</b> - This was the first token that occurred on its input
681 source line.</li>
682 <li><b>LeadingSpace</b> - There was a space character either immediately
683 before the token or transitively before the token as it was expanded
684 through a macro. The definition of this flag is very closely defined by
685 the stringizing requirements of the preprocessor.</li>
686 <li><b>DisableExpand</b> - This flag is used internally to the preprocessor to
687 represent identifier tokens which have macro expansion disabled. This
688 prevents them from being considered as candidates for macro expansion ever
689 in the future.</li>
690 <li><b>NeedsCleaning</b> - This flag is set if the original spelling for the
691 token includes a trigraph or escaped newline. Since this is uncommon,
692 many pieces of code can fast-path on tokens that did not need cleaning.
693 </p>
694 </ol>
695 </li>
696 </ul>
698 <p>One interesting (and somewhat unusual) aspect of normal tokens is that they
699 don't contain any semantic information about the lexed value. For example, if
700 the token was a pp-number token, we do not represent the value of the number
701 that was lexed (this is left for later pieces of code to decide). Additionally,
702 the lexer library has no notion of typedef names vs variable names: both are
703 returned as identifiers, and the parser is left to decide whether a specific
704 identifier is a typedef or a variable (tracking this requires scope information
705 among other things). The parser can do this translation by replacing tokens
706 returned by the preprocessor with "Annotation Tokens".</p>
708 <!-- ======================================================================= -->
709 <h3 id="AnnotationToken">Annotation Tokens</h3>
710 <!-- ======================================================================= -->
712 <p>Annotation Tokens are tokens that are synthesized by the parser and injected
713 into the preprocessor's token stream (replacing existing tokens) to record
714 semantic information found by the parser. For example, if "foo" is found to be
715 a typedef, the "foo" <tt>tok::identifier</tt> token is replaced with an
716 <tt>tok::annot_typename</tt>. This is useful for a couple of reasons: 1) this
717 makes it easy to handle qualified type names (e.g. "foo::bar::baz&lt;42&gt;::t")
718 in C++ as a single "token" in the parser. 2) if the parser backtracks, the
719 reparse does not need to redo semantic analysis to determine whether a token
720 sequence is a variable, type, template, etc.</p>
722 <p>Annotation Tokens are created by the parser and reinjected into the parser's
723 token stream (when backtracking is enabled). Because they can only exist in
724 tokens that the preprocessor-proper is done with, it doesn't need to keep around
725 flags like "start of line" that the preprocessor uses to do its job.
726 Additionally, an annotation token may "cover" a sequence of preprocessor tokens
727 (e.g. <tt>a::b::c</tt> is five preprocessor tokens). As such, the valid fields
728 of an annotation token are different than the fields for a normal token (but
729 they are multiplexed into the normal Token fields):</p>
731 <ul>
732 <li><b>SourceLocation "Location"</b> - The SourceLocation for the annotation
733 token indicates the first token replaced by the annotation token. In the example
734 above, it would be the location of the "a" identifier.</li>
736 <li><b>SourceLocation "AnnotationEndLoc"</b> - This holds the location of the
737 last token replaced with the annotation token. In the example above, it would
738 be the location of the "c" identifier.</li>
740 <li><b>void* "AnnotationValue"</b> - This contains an opaque object
741 that the parser gets from Sema. The parser merely preserves the
742 information for Sema to later interpret based on the annotation token
743 kind.</li>
745 <li><b>TokenKind "Kind"</b> - This indicates the kind of Annotation token this
746 is. See below for the different valid kinds.</li>
747 </ul>
749 <p>Annotation tokens currently come in three kinds:</p>
751 <ol>
752 <li><b>tok::annot_typename</b>: This annotation token represents a
753 resolved typename token that is potentially qualified. The
754 AnnotationValue field contains the <tt>QualType</tt> returned by
755 Sema::getTypeName(), possibly with source location information
756 attached.</li>
758 <li><b>tok::annot_cxxscope</b>: This annotation token represents a C++
759 scope specifier, such as "A::B::". This corresponds to the grammar
760 productions "::" and ":: [opt] nested-name-specifier". The
761 AnnotationValue pointer is a <tt>NestedNameSpecifier*</tt> returned by
762 the Sema::ActOnCXXGlobalScopeSpecifier and
763 Sema::ActOnCXXNestedNameSpecifier callbacks.</li>
765 <li><b>tok::annot_template_id</b>: This annotation token represents a
766 C++ template-id such as "foo&lt;int, 4&gt;", where "foo" is the name
767 of a template. The AnnotationValue pointer is a pointer to a malloc'd
768 TemplateIdAnnotation object. Depending on the context, a parsed
769 template-id that names a type might become a typename annotation token
770 (if all we care about is the named type, e.g., because it occurs in a
771 type specifier) or might remain a template-id token (if we want to
772 retain more source location information or produce a new type, e.g.,
773 in a declaration of a class template specialization). template-id
774 annotation tokens that refer to a type can be "upgraded" to typename
775 annotation tokens by the parser.</li>
777 </ol>
779 <p>As mentioned above, annotation tokens are not returned by the preprocessor,
780 they are formed on demand by the parser. This means that the parser has to be
781 aware of cases where an annotation could occur and form it where appropriate.
782 This is somewhat similar to how the parser handles Translation Phase 6 of C99:
783 String Concatenation (see C99 5.1.1.2). In the case of string concatenation,
784 the preprocessor just returns distinct tok::string_literal and
785 tok::wide_string_literal tokens and the parser eats a sequence of them wherever
786 the grammar indicates that a string literal can occur.</p>
788 <p>In order to do this, whenever the parser expects a tok::identifier or
789 tok::coloncolon, it should call the TryAnnotateTypeOrScopeToken or
790 TryAnnotateCXXScopeToken methods to form the annotation token. These methods
791 will maximally form the specified annotation tokens and replace the current
792 token with them, if applicable. If the current tokens is not valid for an
793 annotation token, it will remain an identifier or :: token.</p>
797 <!-- ======================================================================= -->
798 <h3 id="Lexer">The Lexer class</h3>
799 <!-- ======================================================================= -->
801 <p>The Lexer class provides the mechanics of lexing tokens out of a source
802 buffer and deciding what they mean. The Lexer is complicated by the fact that
803 it operates on raw buffers that have not had spelling eliminated (this is a
804 necessity to get decent performance), but this is countered with careful coding
805 as well as standard performance techniques (for example, the comment handling
806 code is vectorized on X86 and PowerPC hosts).</p>
808 <p>The lexer has a couple of interesting modal features:</p>
810 <ul>
811 <li>The lexer can operate in 'raw' mode. This mode has several features that
812 make it possible to quickly lex the file (e.g. it stops identifier lookup,
813 doesn't specially handle preprocessor tokens, handles EOF differently, etc).
814 This mode is used for lexing within an "<tt>#if 0</tt>" block, for
815 example.</li>
816 <li>The lexer can capture and return comments as tokens. This is required to
817 support the -C preprocessor mode, which passes comments through, and is
818 used by the diagnostic checker to identifier expect-error annotations.</li>
819 <li>The lexer can be in ParsingFilename mode, which happens when preprocessing
820 after reading a #include directive. This mode changes the parsing of '&lt;'
821 to return an "angled string" instead of a bunch of tokens for each thing
822 within the filename.</li>
823 <li>When parsing a preprocessor directive (after "<tt>#</tt>") the
824 ParsingPreprocessorDirective mode is entered. This changes the parser to
825 return EOM at a newline.</li>
826 <li>The Lexer uses a LangOptions object to know whether trigraphs are enabled,
827 whether C++ or ObjC keywords are recognized, etc.</li>
828 </ul>
830 <p>In addition to these modes, the lexer keeps track of a couple of other
831 features that are local to a lexed buffer, which change as the buffer is
832 lexed:</p>
834 <ul>
835 <li>The Lexer uses BufferPtr to keep track of the current character being
836 lexed.</li>
837 <li>The Lexer uses IsAtStartOfLine to keep track of whether the next lexed token
838 will start with its "start of line" bit set.</li>
839 <li>The Lexer keeps track of the current #if directives that are active (which
840 can be nested).</li>
841 <li>The Lexer keeps track of an <a href="#MultipleIncludeOpt">
842 MultipleIncludeOpt</a> object, which is used to
843 detect whether the buffer uses the standard "<tt>#ifndef XX</tt> /
844 <tt>#define XX</tt>" idiom to prevent multiple inclusion. If a buffer does,
845 subsequent includes can be ignored if the XX macro is defined.</li>
846 </ul>
848 <!-- ======================================================================= -->
849 <h3 id="TokenLexer">The TokenLexer class</h3>
850 <!-- ======================================================================= -->
852 <p>The TokenLexer class is a token provider that returns tokens from a list
853 of tokens that came from somewhere else. It typically used for two things: 1)
854 returning tokens from a macro definition as it is being expanded 2) returning
855 tokens from an arbitrary buffer of tokens. The later use is used by _Pragma and
856 will most likely be used to handle unbounded look-ahead for the C++ parser.</p>
858 <!-- ======================================================================= -->
859 <h3 id="MultipleIncludeOpt">The MultipleIncludeOpt class</h3>
860 <!-- ======================================================================= -->
862 <p>The MultipleIncludeOpt class implements a really simple little state machine
863 that is used to detect the standard "<tt>#ifndef XX</tt> / <tt>#define XX</tt>"
864 idiom that people typically use to prevent multiple inclusion of headers. If a
865 buffer uses this idiom and is subsequently #include'd, the preprocessor can
866 simply check to see whether the guarding condition is defined or not. If so,
867 the preprocessor can completely ignore the include of the header.</p>
871 <!-- ======================================================================= -->
872 <h2 id="libparse">The Parser Library</h2>
873 <!-- ======================================================================= -->
875 <!-- ======================================================================= -->
876 <h2 id="libast">The AST Library</h2>
877 <!-- ======================================================================= -->
879 <!-- ======================================================================= -->
880 <h3 id="Type">The Type class and its subclasses</h3>
881 <!-- ======================================================================= -->
883 <p>The Type class (and its subclasses) are an important part of the AST. Types
884 are accessed through the ASTContext class, which implicitly creates and uniques
885 them as they are needed. Types have a couple of non-obvious features: 1) they
886 do not capture type qualifiers like const or volatile (See
887 <a href="#QualType">QualType</a>), and 2) they implicitly capture typedef
888 information. Once created, types are immutable (unlike decls).</p>
890 <p>Typedefs in C make semantic analysis a bit more complex than it would
891 be without them. The issue is that we want to capture typedef information
892 and represent it in the AST perfectly, but the semantics of operations need to
893 "see through" typedefs. For example, consider this code:</p>
895 <code>
896 void func() {<br>
897 &nbsp;&nbsp;typedef int foo;<br>
898 &nbsp;&nbsp;foo X, *Y;<br>
899 &nbsp;&nbsp;typedef foo* bar;<br>
900 &nbsp;&nbsp;bar Z;<br>
901 &nbsp;&nbsp;*X; <i>// error</i><br>
902 &nbsp;&nbsp;**Y; <i>// error</i><br>
903 &nbsp;&nbsp;**Z; <i>// error</i><br>
904 }<br>
905 </code>
907 <p>The code above is illegal, and thus we expect there to be diagnostics emitted
908 on the annotated lines. In this example, we expect to get:</p>
910 <pre>
911 <b>test.c:6:1: error: indirection requires pointer operand ('foo' invalid)</b>
912 *X; // error
913 <font color="blue">^~</font>
914 <b>test.c:7:1: error: indirection requires pointer operand ('foo' invalid)</b>
915 **Y; // error
916 <font color="blue">^~~</font>
917 <b>test.c:8:1: error: indirection requires pointer operand ('foo' invalid)</b>
918 **Z; // error
919 <font color="blue">^~~</font>
920 </pre>
922 <p>While this example is somewhat silly, it illustrates the point: we want to
923 retain typedef information where possible, so that we can emit errors about
924 "<tt>std::string</tt>" instead of "<tt>std::basic_string&lt;char, std:...</tt>".
925 Doing this requires properly keeping typedef information (for example, the type
926 of "X" is "foo", not "int"), and requires properly propagating it through the
927 various operators (for example, the type of *Y is "foo", not "int"). In order
928 to retain this information, the type of these expressions is an instance of the
929 TypedefType class, which indicates that the type of these expressions is a
930 typedef for foo.
931 </p>
933 <p>Representing types like this is great for diagnostics, because the
934 user-specified type is always immediately available. There are two problems
935 with this: first, various semantic checks need to make judgements about the
936 <em>actual structure</em> of a type, ignoring typdefs. Second, we need an
937 efficient way to query whether two types are structurally identical to each
938 other, ignoring typedefs. The solution to both of these problems is the idea of
939 canonical types.</p>
941 <!-- =============== -->
942 <h4>Canonical Types</h4>
943 <!-- =============== -->
945 <p>Every instance of the Type class contains a canonical type pointer. For
946 simple types with no typedefs involved (e.g. "<tt>int</tt>", "<tt>int*</tt>",
947 "<tt>int**</tt>"), the type just points to itself. For types that have a
948 typedef somewhere in their structure (e.g. "<tt>foo</tt>", "<tt>foo*</tt>",
949 "<tt>foo**</tt>", "<tt>bar</tt>"), the canonical type pointer points to their
950 structurally equivalent type without any typedefs (e.g. "<tt>int</tt>",
951 "<tt>int*</tt>", "<tt>int**</tt>", and "<tt>int*</tt>" respectively).</p>
953 <p>This design provides a constant time operation (dereferencing the canonical
954 type pointer) that gives us access to the structure of types. For example,
955 we can trivially tell that "bar" and "foo*" are the same type by dereferencing
956 their canonical type pointers and doing a pointer comparison (they both point
957 to the single "<tt>int*</tt>" type).</p>
959 <p>Canonical types and typedef types bring up some complexities that must be
960 carefully managed. Specifically, the "isa/cast/dyncast" operators generally
961 shouldn't be used in code that is inspecting the AST. For example, when type
962 checking the indirection operator (unary '*' on a pointer), the type checker
963 must verify that the operand has a pointer type. It would not be correct to
964 check that with "<tt>isa&lt;PointerType&gt;(SubExpr-&gt;getType())</tt>",
965 because this predicate would fail if the subexpression had a typedef type.</p>
967 <p>The solution to this problem are a set of helper methods on Type, used to
968 check their properties. In this case, it would be correct to use
969 "<tt>SubExpr-&gt;getType()-&gt;isPointerType()</tt>" to do the check. This
970 predicate will return true if the <em>canonical type is a pointer</em>, which is
971 true any time the type is structurally a pointer type. The only hard part here
972 is remembering not to use the <tt>isa/cast/dyncast</tt> operations.</p>
974 <p>The second problem we face is how to get access to the pointer type once we
975 know it exists. To continue the example, the result type of the indirection
976 operator is the pointee type of the subexpression. In order to determine the
977 type, we need to get the instance of PointerType that best captures the typedef
978 information in the program. If the type of the expression is literally a
979 PointerType, we can return that, otherwise we have to dig through the
980 typedefs to find the pointer type. For example, if the subexpression had type
981 "<tt>foo*</tt>", we could return that type as the result. If the subexpression
982 had type "<tt>bar</tt>", we want to return "<tt>foo*</tt>" (note that we do
983 <em>not</em> want "<tt>int*</tt>"). In order to provide all of this, Type has
984 a getAsPointerType() method that checks whether the type is structurally a
985 PointerType and, if so, returns the best one. If not, it returns a null
986 pointer.</p>
988 <p>This structure is somewhat mystical, but after meditating on it, it will
989 make sense to you :).</p>
991 <!-- ======================================================================= -->
992 <h3 id="QualType">The QualType class</h3>
993 <!-- ======================================================================= -->
995 <p>The QualType class is designed as a trivial value class that is
996 small, passed by-value and is efficient to query. The idea of
997 QualType is that it stores the type qualifiers (const, volatile,
998 restrict, plus some extended qualifiers required by language
999 extensions) separately from the types themselves. QualType is
1000 conceptually a pair of "Type*" and the bits for these type qualifiers.</p>
1002 <p>By storing the type qualifiers as bits in the conceptual pair, it is
1003 extremely efficient to get the set of qualifiers on a QualType (just return the
1004 field of the pair), add a type qualifier (which is a trivial constant-time
1005 operation that sets a bit), and remove one or more type qualifiers (just return
1006 a QualType with the bitfield set to empty).</p>
1008 <p>Further, because the bits are stored outside of the type itself, we do not
1009 need to create duplicates of types with different sets of qualifiers (i.e. there
1010 is only a single heap allocated "int" type: "const int" and "volatile const int"
1011 both point to the same heap allocated "int" type). This reduces the heap size
1012 used to represent bits and also means we do not have to consider qualifiers when
1013 uniquing types (<a href="#Type">Type</a> does not even contain qualifiers).</p>
1015 <p>In practice, the two most common type qualifiers (const and
1016 restrict) are stored in the low bits of the pointer to the Type
1017 object, together with a flag indicating whether extended qualifiers
1018 are present (which must be heap-allocated). This means that QualType
1019 is exactly the same size as a pointer.</p>
1021 <!-- ======================================================================= -->
1022 <h3 id="DeclarationName">Declaration names</h3>
1023 <!-- ======================================================================= -->
1025 <p>The <tt>DeclarationName</tt> class represents the name of a
1026 declaration in Clang. Declarations in the C family of languages can
1027 take several different forms. Most declarations are named by
1028 simple identifiers, e.g., "<code>f</code>" and "<code>x</code>" in
1029 the function declaration <code>f(int x)</code>. In C++, declaration
1030 names can also name class constructors ("<code>Class</code>"
1031 in <code>struct Class { Class(); }</code>), class destructors
1032 ("<code>~Class</code>"), overloaded operator names ("operator+"),
1033 and conversion functions ("<code>operator void const *</code>"). In
1034 Objective-C, declaration names can refer to the names of Objective-C
1035 methods, which involve the method name and the parameters,
1036 collectively called a <i>selector</i>, e.g.,
1037 "<code>setWidth:height:</code>". Since all of these kinds of
1038 entities - variables, functions, Objective-C methods, C++
1039 constructors, destructors, and operators - are represented as
1040 subclasses of Clang's common <code>NamedDecl</code>
1041 class, <code>DeclarationName</code> is designed to efficiently
1042 represent any kind of name.</p>
1044 <p>Given
1045 a <code>DeclarationName</code> <code>N</code>, <code>N.getNameKind()</code>
1046 will produce a value that describes what kind of name <code>N</code>
1047 stores. There are 8 options (all of the names are inside
1048 the <code>DeclarationName</code> class)</p>
1049 <dl>
1050 <dt>Identifier</dt>
1051 <dd>The name is a simple
1052 identifier. Use <code>N.getAsIdentifierInfo()</code> to retrieve the
1053 corresponding <code>IdentifierInfo*</code> pointing to the actual
1054 identifier. Note that C++ overloaded operators (e.g.,
1055 "<code>operator+</code>") are represented as special kinds of
1056 identifiers. Use <code>IdentifierInfo</code>'s <code>getOverloadedOperatorID</code>
1057 function to determine whether an identifier is an overloaded
1058 operator name.</dd>
1060 <dt>ObjCZeroArgSelector, ObjCOneArgSelector,
1061 ObjCMultiArgSelector</dt>
1062 <dd>The name is an Objective-C selector, which can be retrieved as a
1063 <code>Selector</code> instance
1064 via <code>N.getObjCSelector()</code>. The three possible name
1065 kinds for Objective-C reflect an optimization within
1066 the <code>DeclarationName</code> class: both zero- and
1067 one-argument selectors are stored as a
1068 masked <code>IdentifierInfo</code> pointer, and therefore require
1069 very little space, since zero- and one-argument selectors are far
1070 more common than multi-argument selectors (which use a different
1071 structure).</dd>
1073 <dt>CXXConstructorName</dt>
1074 <dd>The name is a C++ constructor
1075 name. Use <code>N.getCXXNameType()</code> to retrieve
1076 the <a href="#QualType">type</a> that this constructor is meant to
1077 construct. The type is always the canonical type, since all
1078 constructors for a given type have the same name.</dd>
1080 <dt>CXXDestructorName</dt>
1081 <dd>The name is a C++ destructor
1082 name. Use <code>N.getCXXNameType()</code> to retrieve
1083 the <a href="#QualType">type</a> whose destructor is being
1084 named. This type is always a canonical type.</dd>
1086 <dt>CXXConversionFunctionName</dt>
1087 <dd>The name is a C++ conversion function. Conversion functions are
1088 named according to the type they convert to, e.g., "<code>operator void
1089 const *</code>". Use <code>N.getCXXNameType()</code> to retrieve
1090 the type that this conversion function converts to. This type is
1091 always a canonical type.</dd>
1093 <dt>CXXOperatorName</dt>
1094 <dd>The name is a C++ overloaded operator name. Overloaded operators
1095 are named according to their spelling, e.g.,
1096 "<code>operator+</code>" or "<code>operator new
1097 []</code>". Use <code>N.getCXXOverloadedOperator()</code> to
1098 retrieve the overloaded operator (a value of
1099 type <code>OverloadedOperatorKind</code>).</dd>
1100 </dl>
1102 <p><code>DeclarationName</code>s are cheap to create, copy, and
1103 compare. They require only a single pointer's worth of storage in
1104 the common cases (identifiers, zero-
1105 and one-argument Objective-C selectors) and use dense, uniqued
1106 storage for the other kinds of
1107 names. Two <code>DeclarationName</code>s can be compared for
1108 equality (<code>==</code>, <code>!=</code>) using a simple bitwise
1109 comparison, can be ordered
1110 with <code>&lt;</code>, <code>&gt;</code>, <code>&lt;=</code>,
1111 and <code>&gt;=</code> (which provide a lexicographical ordering for
1112 normal identifiers but an unspecified ordering for other kinds of
1113 names), and can be placed into LLVM <code>DenseMap</code>s
1114 and <code>DenseSet</code>s.</p>
1116 <p><code>DeclarationName</code> instances can be created in different
1117 ways depending on what kind of name the instance will store. Normal
1118 identifiers (<code>IdentifierInfo</code> pointers) and Objective-C selectors
1119 (<code>Selector</code>) can be implicitly converted
1120 to <code>DeclarationName</code>s. Names for C++ constructors,
1121 destructors, conversion functions, and overloaded operators can be retrieved from
1122 the <code>DeclarationNameTable</code>, an instance of which is
1123 available as <code>ASTContext::DeclarationNames</code>. The member
1124 functions <code>getCXXConstructorName</code>, <code>getCXXDestructorName</code>,
1125 <code>getCXXConversionFunctionName</code>, and <code>getCXXOperatorName</code>, respectively,
1126 return <code>DeclarationName</code> instances for the four kinds of
1127 C++ special function names.</p>
1129 <!-- ======================================================================= -->
1130 <h3 id="DeclContext">Declaration contexts</h3>
1131 <!-- ======================================================================= -->
1132 <p>Every declaration in a program exists within some <i>declaration
1133 context</i>, such as a translation unit, namespace, class, or
1134 function. Declaration contexts in Clang are represented by
1135 the <code>DeclContext</code> class, from which the various
1136 declaration-context AST nodes
1137 (<code>TranslationUnitDecl</code>, <code>NamespaceDecl</code>, <code>RecordDecl</code>, <code>FunctionDecl</code>,
1138 etc.) will derive. The <code>DeclContext</code> class provides
1139 several facilities common to each declaration context:</p>
1140 <dl>
1141 <dt>Source-centric vs. Semantics-centric View of Declarations</dt>
1142 <dd><code>DeclContext</code> provides two views of the declarations
1143 stored within a declaration context. The source-centric view
1144 accurately represents the program source code as written, including
1145 multiple declarations of entities where present (see the
1146 section <a href="#Redeclarations">Redeclarations and
1147 Overloads</a>), while the semantics-centric view represents the
1148 program semantics. The two views are kept synchronized by semantic
1149 analysis while the ASTs are being constructed.</dd>
1151 <dt>Storage of declarations within that context</dt>
1152 <dd>Every declaration context can contain some number of
1153 declarations. For example, a C++ class (represented
1154 by <code>RecordDecl</code>) contains various member functions,
1155 fields, nested types, and so on. All of these declarations will be
1156 stored within the <code>DeclContext</code>, and one can iterate
1157 over the declarations via
1158 [<code>DeclContext::decls_begin()</code>,
1159 <code>DeclContext::decls_end()</code>). This mechanism provides
1160 the source-centric view of declarations in the context.</dd>
1162 <dt>Lookup of declarations within that context</dt>
1163 <dd>The <code>DeclContext</code> structure provides efficient name
1164 lookup for names within that declaration context. For example,
1165 if <code>N</code> is a namespace we can look for the
1166 name <code>N::f</code>
1167 using <code>DeclContext::lookup</code>. The lookup itself is
1168 based on a lazily-constructed array (for declaration contexts
1169 with a small number of declarations) or hash table (for
1170 declaration contexts with more declarations). The lookup
1171 operation provides the semantics-centric view of the declarations
1172 in the context.</dd>
1174 <dt>Ownership of declarations</dt>
1175 <dd>The <code>DeclContext</code> owns all of the declarations that
1176 were declared within its declaration context, and is responsible
1177 for the management of their memory as well as their
1178 (de-)serialization.</dd>
1179 </dl>
1181 <p>All declarations are stored within a declaration context, and one
1182 can query
1183 information about the context in which each declaration lives. One
1184 can retrieve the <code>DeclContext</code> that contains a
1185 particular <code>Decl</code>
1186 using <code>Decl::getDeclContext</code>. However, see the
1187 section <a href="#LexicalAndSemanticContexts">Lexical and Semantic
1188 Contexts</a> for more information about how to interpret this
1189 context information.</p>
1191 <h4 id="Redeclarations">Redeclarations and Overloads</h4>
1192 <p>Within a translation unit, it is common for an entity to be
1193 declared several times. For example, we might declare a function "f"
1194 and then later re-declare it as part of an inlined definition:</p>
1196 <pre>
1197 void f(int x, int y, int z = 1);
1199 inline void f(int x, int y, int z) { /* ... */ }
1200 </pre>
1202 <p>The representation of "f" differs in the source-centric and
1203 semantics-centric views of a declaration context. In the
1204 source-centric view, all redeclarations will be present, in the
1205 order they occurred in the source code, making
1206 this view suitable for clients that wish to see the structure of
1207 the source code. In the semantics-centric view, only the most recent "f"
1208 will be found by the lookup, since it effectively replaces the first
1209 declaration of "f".</p>
1211 <p>In the semantics-centric view, overloading of functions is
1212 represented explicitly. For example, given two declarations of a
1213 function "g" that are overloaded, e.g.,</p>
1214 <pre>
1215 void g();
1216 void g(int);
1217 </pre>
1218 <p>the <code>DeclContext::lookup</code> operation will return
1219 an <code>OverloadedFunctionDecl</code> that contains both
1220 declarations of "g". Clients that perform semantic analysis on a
1221 program that is not concerned with the actual source code will
1222 primarily use this semantics-centric view.</p>
1224 <h4 id="LexicalAndSemanticContexts">Lexical and Semantic Contexts</h4>
1225 <p>Each declaration has two potentially different
1226 declaration contexts: a <i>lexical</i> context, which corresponds to
1227 the source-centric view of the declaration context, and
1228 a <i>semantic</i> context, which corresponds to the
1229 semantics-centric view. The lexical context is accessible
1230 via <code>Decl::getLexicalDeclContext</code> while the
1231 semantic context is accessible
1232 via <code>Decl::getDeclContext</code>, both of which return
1233 <code>DeclContext</code> pointers. For most declarations, the two
1234 contexts are identical. For example:</p>
1236 <pre>
1237 class X {
1238 public:
1239 void f(int x);
1241 </pre>
1243 <p>Here, the semantic and lexical contexts of <code>X::f</code> are
1244 the <code>DeclContext</code> associated with the
1245 class <code>X</code> (itself stored as a <code>RecordDecl</code> AST
1246 node). However, we can now define <code>X::f</code> out-of-line:</p>
1248 <pre>
1249 void X::f(int x = 17) { /* ... */ }
1250 </pre>
1252 <p>This definition of has different lexical and semantic
1253 contexts. The lexical context corresponds to the declaration
1254 context in which the actual declaration occurred in the source
1255 code, e.g., the translation unit containing <code>X</code>. Thus,
1256 this declaration of <code>X::f</code> can be found by traversing
1257 the declarations provided by
1258 [<code>decls_begin()</code>, <code>decls_end()</code>) in the
1259 translation unit.</p>
1261 <p>The semantic context of <code>X::f</code> corresponds to the
1262 class <code>X</code>, since this member function is (semantically) a
1263 member of <code>X</code>. Lookup of the name <code>f</code> into
1264 the <code>DeclContext</code> associated with <code>X</code> will
1265 then return the definition of <code>X::f</code> (including
1266 information about the default argument).</p>
1268 <h4 id="TransparentContexts">Transparent Declaration Contexts</h4>
1269 <p>In C and C++, there are several contexts in which names that are
1270 logically declared inside another declaration will actually "leak"
1271 out into the enclosing scope from the perspective of name
1272 lookup. The most obvious instance of this behavior is in
1273 enumeration types, e.g.,</p>
1274 <pre>
1275 enum Color {
1276 Red,
1277 Green,
1278 Blue
1280 </pre>
1282 <p>Here, <code>Color</code> is an enumeration, which is a declaration
1283 context that contains the
1284 enumerators <code>Red</code>, <code>Green</code>,
1285 and <code>Blue</code>. Thus, traversing the list of declarations
1286 contained in the enumeration <code>Color</code> will
1287 yield <code>Red</code>, <code>Green</code>,
1288 and <code>Blue</code>. However, outside of the scope
1289 of <code>Color</code> one can name the enumerator <code>Red</code>
1290 without qualifying the name, e.g.,</p>
1292 <pre>
1293 Color c = Red;
1294 </pre>
1296 <p>There are other entities in C++ that provide similar behavior. For
1297 example, linkage specifications that use curly braces:</p>
1299 <pre>
1300 extern "C" {
1301 void f(int);
1302 void g(int);
1304 // f and g are visible here
1305 </pre>
1307 <p>For source-level accuracy, we treat the linkage specification and
1308 enumeration type as a
1309 declaration context in which its enclosed declarations ("Red",
1310 "Green", and "Blue"; "f" and "g")
1311 are declared. However, these declarations are visible outside of the
1312 scope of the declaration context.</p>
1314 <p>These language features (and several others, described below) have
1315 roughly the same set of
1316 requirements: declarations are declared within a particular lexical
1317 context, but the declarations are also found via name lookup in
1318 scopes enclosing the declaration itself. This feature is implemented
1319 via <i>transparent</i> declaration contexts
1320 (see <code>DeclContext::isTransparentContext()</code>), whose
1321 declarations are visible in the nearest enclosing non-transparent
1322 declaration context. This means that the lexical context of the
1323 declaration (e.g., an enumerator) will be the
1324 transparent <code>DeclContext</code> itself, as will the semantic
1325 context, but the declaration will be visible in every outer context
1326 up to and including the first non-transparent declaration context (since
1327 transparent declaration contexts can be nested).</p>
1329 <p>The transparent <code>DeclContexts</code> are:</p>
1330 <ul>
1331 <li>Enumerations (but not C++0x "scoped enumerations"):
1332 <pre>
1333 enum Color {
1334 Red,
1335 Green,
1336 Blue
1338 // Red, Green, and Blue are in scope
1339 </pre></li>
1340 <li>C++ linkage specifications:
1341 <pre>
1342 extern "C" {
1343 void f(int);
1344 void g(int);
1346 // f and g are in scope
1347 </pre></li>
1348 <li>Anonymous unions and structs:
1349 <pre>
1350 struct LookupTable {
1351 bool IsVector;
1352 union {
1353 std::vector&lt;Item&gt; *Vector;
1354 std::set&lt;Item&gt; *Set;
1358 LookupTable LT;
1359 LT.Vector = 0; // Okay: finds Vector inside the unnamed union
1360 </pre>
1361 </li>
1362 <li>C++0x inline namespaces:
1363 <pre>
1364 namespace mylib {
1365 inline namespace debug {
1366 class X;
1369 mylib::X *xp; // okay: mylib::X refers to mylib::debug::X
1370 </pre>
1371 </li>
1372 </ul>
1375 <h4 id="MultiDeclContext">Multiply-Defined Declaration Contexts</h4>
1376 <p>C++ namespaces have the interesting--and, so far, unique--property that
1377 the namespace can be defined multiple times, and the declarations
1378 provided by each namespace definition are effectively merged (from
1379 the semantic point of view). For example, the following two code
1380 snippets are semantically indistinguishable:</p>
1381 <pre>
1382 // Snippet #1:
1383 namespace N {
1384 void f();
1386 namespace N {
1387 void f(int);
1390 // Snippet #2:
1391 namespace N {
1392 void f();
1393 void f(int);
1395 </pre>
1397 <p>In Clang's representation, the source-centric view of declaration
1398 contexts will actually have two separate <code>NamespaceDecl</code>
1399 nodes in Snippet #1, each of which is a declaration context that
1400 contains a single declaration of "f". However, the semantics-centric
1401 view provided by name lookup into the namespace <code>N</code> for
1402 "f" will return an <code>OverloadedFunctionDecl</code> that contains
1403 both declarations of "f".</p>
1405 <p><code>DeclContext</code> manages multiply-defined declaration
1406 contexts internally. The
1407 function <code>DeclContext::getPrimaryContext</code> retrieves the
1408 "primary" context for a given <code>DeclContext</code> instance,
1409 which is the <code>DeclContext</code> responsible for maintaining
1410 the lookup table used for the semantics-centric view. Given the
1411 primary context, one can follow the chain
1412 of <code>DeclContext</code> nodes that define additional
1413 declarations via <code>DeclContext::getNextContext</code>. Note that
1414 these functions are used internally within the lookup and insertion
1415 methods of the <code>DeclContext</code>, so the vast majority of
1416 clients can ignore them.</p>
1418 <!-- ======================================================================= -->
1419 <h3 id="CFG">The <tt>CFG</tt> class</h3>
1420 <!-- ======================================================================= -->
1422 <p>The <tt>CFG</tt> class is designed to represent a source-level
1423 control-flow graph for a single statement (<tt>Stmt*</tt>). Typically
1424 instances of <tt>CFG</tt> are constructed for function bodies (usually
1425 an instance of <tt>CompoundStmt</tt>), but can also be instantiated to
1426 represent the control-flow of any class that subclasses <tt>Stmt</tt>,
1427 which includes simple expressions. Control-flow graphs are especially
1428 useful for performing
1429 <a href="http://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities">flow-
1430 or path-sensitive</a> program analyses on a given function.</p>
1432 <!-- ============ -->
1433 <h4>Basic Blocks</h4>
1434 <!-- ============ -->
1436 <p>Concretely, an instance of <tt>CFG</tt> is a collection of basic
1437 blocks. Each basic block is an instance of <tt>CFGBlock</tt>, which
1438 simply contains an ordered sequence of <tt>Stmt*</tt> (each referring
1439 to statements in the AST). The ordering of statements within a block
1440 indicates unconditional flow of control from one statement to the
1441 next. <a href="#ConditionalControlFlow">Conditional control-flow</a>
1442 is represented using edges between basic blocks. The statements
1443 within a given <tt>CFGBlock</tt> can be traversed using
1444 the <tt>CFGBlock::*iterator</tt> interface.</p>
1447 A <tt>CFG</tt> object owns the instances of <tt>CFGBlock</tt> within
1448 the control-flow graph it represents. Each <tt>CFGBlock</tt> within a
1449 CFG is also uniquely numbered (accessible
1450 via <tt>CFGBlock::getBlockID()</tt>). Currently the number is
1451 based on the ordering the blocks were created, but no assumptions
1452 should be made on how <tt>CFGBlock</tt>s are numbered other than their
1453 numbers are unique and that they are numbered from 0..N-1 (where N is
1454 the number of basic blocks in the CFG).</p>
1456 <!-- ===================== -->
1457 <h4>Entry and Exit Blocks</h4>
1458 <!-- ===================== -->
1460 Each instance of <tt>CFG</tt> contains two special blocks:
1461 an <i>entry</i> block (accessible via <tt>CFG::getEntry()</tt>), which
1462 has no incoming edges, and an <i>exit</i> block (accessible
1463 via <tt>CFG::getExit()</tt>), which has no outgoing edges. Neither
1464 block contains any statements, and they serve the role of providing a
1465 clear entrance and exit for a body of code such as a function body.
1466 The presence of these empty blocks greatly simplifies the
1467 implementation of many analyses built on top of CFGs.
1469 <!-- ===================================================== -->
1470 <h4 id ="ConditionalControlFlow">Conditional Control-Flow</h4>
1471 <!-- ===================================================== -->
1473 <p>Conditional control-flow (such as those induced by if-statements
1474 and loops) is represented as edges between <tt>CFGBlock</tt>s.
1475 Because different C language constructs can induce control-flow,
1476 each <tt>CFGBlock</tt> also records an extra <tt>Stmt*</tt> that
1477 represents the <i>terminator</i> of the block. A terminator is simply
1478 the statement that caused the control-flow, and is used to identify
1479 the nature of the conditional control-flow between blocks. For
1480 example, in the case of an if-statement, the terminator refers to
1481 the <tt>IfStmt</tt> object in the AST that represented the given
1482 branch.</p>
1484 <p>To illustrate, consider the following code example:</p>
1486 <code>
1487 int foo(int x) {<br>
1488 &nbsp;&nbsp;x = x + 1;<br>
1489 <br>
1490 &nbsp;&nbsp;if (x > 2) x++;<br>
1491 &nbsp;&nbsp;else {<br>
1492 &nbsp;&nbsp;&nbsp;&nbsp;x += 2;<br>
1493 &nbsp;&nbsp;&nbsp;&nbsp;x *= 2;<br>
1494 &nbsp;&nbsp;}<br>
1495 <br>
1496 &nbsp;&nbsp;return x;<br>
1498 </code>
1500 <p>After invoking the parser+semantic analyzer on this code fragment,
1501 the AST of the body of <tt>foo</tt> is referenced by a
1502 single <tt>Stmt*</tt>. We can then construct an instance
1503 of <tt>CFG</tt> representing the control-flow graph of this function
1504 body by single call to a static class method:</p>
1506 <code>
1507 &nbsp;&nbsp;Stmt* FooBody = ...<br>
1508 &nbsp;&nbsp;CFG* FooCFG = <b>CFG::buildCFG</b>(FooBody);
1509 </code>
1511 <p>It is the responsibility of the caller of <tt>CFG::buildCFG</tt>
1512 to <tt>delete</tt> the returned <tt>CFG*</tt> when the CFG is no
1513 longer needed.</p>
1515 <p>Along with providing an interface to iterate over
1516 its <tt>CFGBlock</tt>s, the <tt>CFG</tt> class also provides methods
1517 that are useful for debugging and visualizing CFGs. For example, the
1518 method
1519 <tt>CFG::dump()</tt> dumps a pretty-printed version of the CFG to
1520 standard error. This is especially useful when one is using a
1521 debugger such as gdb. For example, here is the output
1522 of <tt>FooCFG->dump()</tt>:</p>
1524 <code>
1525 &nbsp;[ B5 (ENTRY) ]<br>
1526 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (0):<br>
1527 &nbsp;&nbsp;&nbsp;&nbsp;Successors (1): B4<br>
1528 <br>
1529 &nbsp;[ B4 ]<br>
1530 &nbsp;&nbsp;&nbsp;&nbsp;1: x = x + 1<br>
1531 &nbsp;&nbsp;&nbsp;&nbsp;2: (x > 2)<br>
1532 &nbsp;&nbsp;&nbsp;&nbsp;<b>T: if [B4.2]</b><br>
1533 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (1): B5<br>
1534 &nbsp;&nbsp;&nbsp;&nbsp;Successors (2): B3 B2<br>
1535 <br>
1536 &nbsp;[ B3 ]<br>
1537 &nbsp;&nbsp;&nbsp;&nbsp;1: x++<br>
1538 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (1): B4<br>
1539 &nbsp;&nbsp;&nbsp;&nbsp;Successors (1): B1<br>
1540 <br>
1541 &nbsp;[ B2 ]<br>
1542 &nbsp;&nbsp;&nbsp;&nbsp;1: x += 2<br>
1543 &nbsp;&nbsp;&nbsp;&nbsp;2: x *= 2<br>
1544 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (1): B4<br>
1545 &nbsp;&nbsp;&nbsp;&nbsp;Successors (1): B1<br>
1546 <br>
1547 &nbsp;[ B1 ]<br>
1548 &nbsp;&nbsp;&nbsp;&nbsp;1: return x;<br>
1549 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (2): B2 B3<br>
1550 &nbsp;&nbsp;&nbsp;&nbsp;Successors (1): B0<br>
1551 <br>
1552 &nbsp;[ B0 (EXIT) ]<br>
1553 &nbsp;&nbsp;&nbsp;&nbsp;Predecessors (1): B1<br>
1554 &nbsp;&nbsp;&nbsp;&nbsp;Successors (0):
1555 </code>
1557 <p>For each block, the pretty-printed output displays for each block
1558 the number of <i>predecessor</i> blocks (blocks that have outgoing
1559 control-flow to the given block) and <i>successor</i> blocks (blocks
1560 that have control-flow that have incoming control-flow from the given
1561 block). We can also clearly see the special entry and exit blocks at
1562 the beginning and end of the pretty-printed output. For the entry
1563 block (block B5), the number of predecessor blocks is 0, while for the
1564 exit block (block B0) the number of successor blocks is 0.</p>
1566 <p>The most interesting block here is B4, whose outgoing control-flow
1567 represents the branching caused by the sole if-statement
1568 in <tt>foo</tt>. Of particular interest is the second statement in
1569 the block, <b><tt>(x > 2)</tt></b>, and the terminator, printed
1570 as <b><tt>if [B4.2]</tt></b>. The second statement represents the
1571 evaluation of the condition of the if-statement, which occurs before
1572 the actual branching of control-flow. Within the <tt>CFGBlock</tt>
1573 for B4, the <tt>Stmt*</tt> for the second statement refers to the
1574 actual expression in the AST for <b><tt>(x > 2)</tt></b>. Thus
1575 pointers to subclasses of <tt>Expr</tt> can appear in the list of
1576 statements in a block, and not just subclasses of <tt>Stmt</tt> that
1577 refer to proper C statements.</p>
1579 <p>The terminator of block B4 is a pointer to the <tt>IfStmt</tt>
1580 object in the AST. The pretty-printer outputs <b><tt>if
1581 [B4.2]</tt></b> because the condition expression of the if-statement
1582 has an actual place in the basic block, and thus the terminator is
1583 essentially
1584 <i>referring</i> to the expression that is the second statement of
1585 block B4 (i.e., B4.2). In this manner, conditions for control-flow
1586 (which also includes conditions for loops and switch statements) are
1587 hoisted into the actual basic block.</p>
1589 <!-- ===================== -->
1590 <!-- <h4>Implicit Control-Flow</h4> -->
1591 <!-- ===================== -->
1593 <!--
1594 <p>A key design principle of the <tt>CFG</tt> class was to not require
1595 any transformations to the AST in order to represent control-flow.
1596 Thus the <tt>CFG</tt> does not perform any "lowering" of the
1597 statements in an AST: loops are not transformed into guarded gotos,
1598 short-circuit operations are not converted to a set of if-statements,
1599 and so on.</p>
1603 <!-- ======================================================================= -->
1604 <h3 id="Constants">Constant Folding in the Clang AST</h3>
1605 <!-- ======================================================================= -->
1607 <p>There are several places where constants and constant folding matter a lot to
1608 the Clang front-end. First, in general, we prefer the AST to retain the source
1609 code as close to how the user wrote it as possible. This means that if they
1610 wrote "5+4", we want to keep the addition and two constants in the AST, we don't
1611 want to fold to "9". This means that constant folding in various ways turns
1612 into a tree walk that needs to handle the various cases.</p>
1614 <p>However, there are places in both C and C++ that require constants to be
1615 folded. For example, the C standard defines what an "integer constant
1616 expression" (i-c-e) is with very precise and specific requirements. The
1617 language then requires i-c-e's in a lot of places (for example, the size of a
1618 bitfield, the value for a case statement, etc). For these, we have to be able
1619 to constant fold the constants, to do semantic checks (e.g. verify bitfield size
1620 is non-negative and that case statements aren't duplicated). We aim for Clang
1621 to be very pedantic about this, diagnosing cases when the code does not use an
1622 i-c-e where one is required, but accepting the code unless running with
1623 <tt>-pedantic-errors</tt>.</p>
1625 <p>Things get a little bit more tricky when it comes to compatibility with
1626 real-world source code. Specifically, GCC has historically accepted a huge
1627 superset of expressions as i-c-e's, and a lot of real world code depends on this
1628 unfortuate accident of history (including, e.g., the glibc system headers). GCC
1629 accepts anything its "fold" optimizer is capable of reducing to an integer
1630 constant, which means that the definition of what it accepts changes as its
1631 optimizer does. One example is that GCC accepts things like "case X-X:" even
1632 when X is a variable, because it can fold this to 0.</p>
1634 <p>Another issue are how constants interact with the extensions we support, such
1635 as __builtin_constant_p, __builtin_inf, __extension__ and many others. C99
1636 obviously does not specify the semantics of any of these extensions, and the
1637 definition of i-c-e does not include them. However, these extensions are often
1638 used in real code, and we have to have a way to reason about them.</p>
1640 <p>Finally, this is not just a problem for semantic analysis. The code
1641 generator and other clients have to be able to fold constants (e.g. to
1642 initialize global variables) and has to handle a superset of what C99 allows.
1643 Further, these clients can benefit from extended information. For example, we
1644 know that "foo()||1" always evaluates to true, but we can't replace the
1645 expression with true because it has side effects.</p>
1647 <!-- ======================= -->
1648 <h4>Implementation Approach</h4>
1649 <!-- ======================= -->
1651 <p>After trying several different approaches, we've finally converged on a
1652 design (Note, at the time of this writing, not all of this has been implemented,
1653 consider this a design goal!). Our basic approach is to define a single
1654 recursive method evaluation method (<tt>Expr::Evaluate</tt>), which is
1655 implemented in <tt>AST/ExprConstant.cpp</tt>. Given an expression with 'scalar'
1656 type (integer, fp, complex, or pointer) this method returns the following
1657 information:</p>
1659 <ul>
1660 <li>Whether the expression is an integer constant expression, a general
1661 constant that was folded but has no side effects, a general constant that
1662 was folded but that does have side effects, or an uncomputable/unfoldable
1663 value.
1664 </li>
1665 <li>If the expression was computable in any way, this method returns the APValue
1666 for the result of the expression.</li>
1667 <li>If the expression is not evaluatable at all, this method returns
1668 information on one of the problems with the expression. This includes a
1669 SourceLocation for where the problem is, and a diagnostic ID that explains
1670 the problem. The diagnostic should be have ERROR type.</li>
1671 <li>If the expression is not an integer constant expression, this method returns
1672 information on one of the problems with the expression. This includes a
1673 SourceLocation for where the problem is, and a diagnostic ID that explains
1674 the problem. The diagnostic should be have EXTENSION type.</li>
1675 </ul>
1677 <p>This information gives various clients the flexibility that they want, and we
1678 will eventually have some helper methods for various extensions. For example,
1679 Sema should have a <tt>Sema::VerifyIntegerConstantExpression</tt> method, which
1680 calls Evaluate on the expression. If the expression is not foldable, the error
1681 is emitted, and it would return true. If the expression is not an i-c-e, the
1682 EXTENSION diagnostic is emitted. Finally it would return false to indicate that
1683 the AST is ok.</p>
1685 <p>Other clients can use the information in other ways, for example, codegen can
1686 just use expressions that are foldable in any way.</p>
1688 <!-- ========== -->
1689 <h4>Extensions</h4>
1690 <!-- ========== -->
1692 <p>This section describes how some of the various extensions Clang supports
1693 interacts with constant evaluation:</p>
1695 <ul>
1696 <li><b><tt>__extension__</tt></b>: The expression form of this extension causes
1697 any evaluatable subexpression to be accepted as an integer constant
1698 expression.</li>
1699 <li><b><tt>__builtin_constant_p</tt></b>: This returns true (as a integer
1700 constant expression) if the operand is any evaluatable constant. As a
1701 special case, if <tt>__builtin_constant_p</tt> is the (potentially
1702 parenthesized) condition of a conditional operator expression ("?:"), only
1703 the true side of the conditional operator is considered, and it is evaluated
1704 with full constant folding.</li>
1705 <li><b><tt>__builtin_choose_expr</tt></b>: The condition is required to be an
1706 integer constant expression, but we accept any constant as an "extension of
1707 an extension". This only evaluates one operand depending on which way the
1708 condition evaluates.</li>
1709 <li><b><tt>__builtin_classify_type</tt></b>: This always returns an integer
1710 constant expression.</li>
1711 <li><b><tt>__builtin_inf,nan,..</tt></b>: These are treated just like a
1712 floating-point literal.</li>
1713 <li><b><tt>__builtin_abs,copysign,..</tt></b>: These are constant folded as
1714 general constant expressions.</li>
1715 <li><b><tt>__builtin_strlen</tt></b> and <b><tt>strlen</tt></b>: These are constant folded as integer constant expressions if the argument is a string literal.</li>
1716 </ul>
1719 <!-- ======================================================================= -->
1720 <h2 id="Howtos">How to change Clang</h2>
1721 <!-- ======================================================================= -->
1723 <!-- ======================================================================= -->
1724 <h3 id="AddingAttributes">How to add an attribute</h3>
1725 <!-- ======================================================================= -->
1727 <p>To add an attribute, you'll have to add it to the list of attributes, add it
1728 to the parsing phase, and look for it in the AST scan.
1729 <a href="http://llvm.org/viewvc/llvm-project?view=rev&revision=124217">r124217</a>
1730 has a good example of adding a warning attribute.</p>
1732 <p>(Beware that this hasn't been reviewed/fixed by the people who designed the
1733 attributes system yet.)</p>
1735 <h4><a
1736 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Basic/Attr.td?view=markup">include/clang/Basic/Attr.td</a></h4>
1738 <p>Each attribute gets a <tt>def</tt> inheriting from <tt>Attr</tt> or one of
1739 its subclasses. <tt>InheritableAttr</tt> means that the attribute also applies
1740 to subsequent declarations of the same name.</p>
1742 <p><tt>Spellings</tt> lists the strings that can appear in
1743 <tt>__attribute__((here))</tt> or <tt>[[here]]</tt>. All such strings
1744 will be synonymous. If you want to allow the <tt>[[]]</tt> C++0x
1745 syntax, you have to define a list of <tt>Namespaces</tt>, which will
1746 let users write <tt>[[namespace:spelling]]</tt>. Using the empty
1747 string for a namespace will allow users to write just the spelling
1748 with no "<tt>:</tt>".</p>
1750 <p><tt>Subjects</tt> restricts what kinds of AST node to which this attribute
1751 can appertain (roughly, attach).</p>
1753 <p><tt>Args</tt> names the arguments the attribute takes, in order. If
1754 <tt>Args</tt> is <tt>[StringArgument&lt;"Arg1">, IntArgument&lt;"Arg2">]</tt>
1755 then <tt>__attribute__((myattribute("Hello", 3)))</tt> will be a valid use.</p>
1757 <h4>Boilerplate</h4>
1759 <p>Add an element to the <tt>AttributeList::Kind</tt> enum in <a
1760 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Sema/AttributeList.h?view=markup">include/clang/Sema/AttributeList.h</a>
1761 named <tt>AT_lower_with_underscores</tt>. That is, a CamelCased
1762 <tt>AttributeName</tt> in <tt>Attr.td</tt> name should become
1763 <tt>AT_attribute_name</tt>.</p>
1765 <p>Add a case to the <tt>StringSwitch</tt> in <tt>AttributeList::getKind()</tt>
1766 in <a
1767 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Sema/AttributeList.cpp?view=markup">lib/Sema/AttributeList.cpp</a>
1768 for each spelling of your attribute. Less common attributes should come toward
1769 the end of that list.</p>
1771 <p>Write a new <tt>HandleYourAttr()</tt> function in <a
1772 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Sema/SemaDeclAttr.cpp?view=markup">lib/Sema/SemaDeclAttr.cpp</a>,
1773 and add a case to the switch in <tt>ProcessNonInheritableDeclAttr()</tt> or
1774 <tt>ProcessInheritableDeclAttr()</tt> forwarding to it.</p>
1776 <p>If your attribute causes extra warnings to fire, define a <tt>DiagGroup</tt>
1777 in <a
1778 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Basic/DiagnosticGroups.td?view=markup">include/clang/Basic/DiagnosticGroups.td</a>
1779 named after the attribute's <tt>Spelling</tt> with "_"s replaced by "-"s. If
1780 you're only defining one diagnostic, you can skip <tt>DiagnosticGroups.td</tt>
1781 and use <tt>InGroup&lt;DiagGroup&lt;"your-attribute">></tt> directly in <a
1782 href="http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Basic/DiagnosticSemaKinds.td?view=markup">DiagnosticSemaKinds.td</a></p>
1784 <h4>The meat of your attribute</h4>
1786 <p>Find an appropriate place in Clang to do whatever your attribute needs to do.
1787 Check for the attribute's presence using <tt>Decl::getAttr&lt;YourAttr>()</tt>.</p>
1789 <p>Update the <a href="LanguageExtensions.html">Clang Language Extensions</a>
1790 document to describe your new attribute.</p>
1792 </div>
1793 </body>
1794 </html>