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