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