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