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 <https://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 diagnostic (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<DiagnosticConsumer>` depending on how the ``DiagnosticConsumer`` interface is 58implemented. A representative example of a diagnostic is: 59 60.. code-block:: text 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``, ``REMARK``, 91``WARNING``, 92``EXTENSION``, ``EXTWARN``, ``ERROR``}. The ``ERROR`` severity is used for 93diagnostics indicating the program is never acceptable under any circumstances. 94When an error is emitted, the AST for the input code may not be fully built. 95The ``EXTENSION`` and ``EXTWARN`` severities are used for extensions to the 96language that Clang accepts. This means that Clang fully understands and can 97represent them in the AST, but we produce diagnostics to tell the user their 98code is non-portable. The difference is that the former are ignored by 99default, and the later warn by default. The ``WARNING`` severity is used for 100constructs that are valid in the currently selected source language but that 101are dubious in some way. The ``REMARK`` severity provides generic information 102about the compilation that is not necessarily related to any dubious code. The 103``NOTE`` level is used to staple more information onto previous diagnostics. 104 105These *severities* are mapped into a smaller set (the ``Diagnostic::Level`` 106enum, {``Ignored``, ``Note``, ``Remark``, ``Warning``, ``Error``, ``Fatal``}) of 107output 108*levels* by the diagnostics subsystem based on various configuration options. 109Clang internally supports a fully fine grained mapping mechanism that allows 110you to map almost any diagnostic to the output level that you want. The only 111diagnostics that cannot be mapped are ``NOTE``\ s, which always follow the 112severity of the previously emitted diagnostic and ``ERROR``\ s, which can only 113be mapped to ``Fatal`` (it is not possible to turn an error into a warning, for 114example). 115 116Diagnostic mappings are used in many ways. For example, if the user specifies 117``-pedantic``, ``EXTENSION`` maps to ``Warning``, if they specify 118``-pedantic-errors``, it turns into ``Error``. This is used to implement 119options like ``-Wunused_macros``, ``-Wundef`` etc. 120 121Mapping to ``Fatal`` should only be used for diagnostics that are considered so 122severe that error recovery won't be able to recover sensibly from them (thus 123spewing a ton of bogus errors). One example of this class of error are failure 124to ``#include`` a file. 125 126The Format String 127^^^^^^^^^^^^^^^^^ 128 129The format string for the diagnostic is very simple, but it has some power. It 130takes the form of a string in English with markers that indicate where and how 131arguments to the diagnostic are inserted and formatted. For example, here are 132some simple format strings: 133 134.. code-block:: c++ 135 136 "binary integer literals are an extension" 137 "format string contains '\\0' within the string body" 138 "more '%%' conversions than data arguments" 139 "invalid operands to binary expression (%0 and %1)" 140 "overloaded '%0' must be a %select{unary|binary|unary or binary}2 operator" 141 " (has %1 parameter%s1)" 142 143These examples show some important points of format strings. You can use any 144plain ASCII character in the diagnostic string except "``%``" without a 145problem, but these are C strings, so you have to use and be aware of all the C 146escape sequences (as in the second example). If you want to produce a "``%``" 147in the output, use the "``%%``" escape sequence, like the third diagnostic. 148Finally, Clang uses the "``%...[digit]``" sequences to specify where and how 149arguments to the diagnostic are formatted. 150 151Arguments to the diagnostic are numbered according to how they are specified by 152the C++ code that :ref:`produces them <internals-producing-diag>`, and are 153referenced by ``%0`` .. ``%9``. If you have more than 10 arguments to your 154diagnostic, you are doing something wrong :). Unlike ``printf``, there is no 155requirement that arguments to the diagnostic end up in the output in the same 156order as they are specified, you could have a format string with "``%1 %0``" 157that swaps them, for example. The text in between the percent and digit are 158formatting instructions. If there are no instructions, the argument is just 159turned into a string and substituted in. 160 161Here are some "best practices" for writing the English format string: 162 163* Keep the string short. It should ideally fit in the 80 column limit of the 164 ``DiagnosticKinds.td`` file. This avoids the diagnostic wrapping when 165 printed, and forces you to think about the important point you are conveying 166 with the diagnostic. 167* Take advantage of location information. The user will be able to see the 168 line and location of the caret, so you don't need to tell them that the 169 problem is with the 4th argument to the function: just point to it. 170* Do not capitalize the diagnostic string, and do not end it with a period. 171* If you need to quote something in the diagnostic string, use single quotes. 172 173Diagnostics should never take random English strings as arguments: you 174shouldn't use "``you have a problem with %0``" and pass in things like "``your 175argument``" or "``your return value``" as arguments. Doing this prevents 176:ref:`translating <internals-diag-translation>` the Clang diagnostics to other 177languages (because they'll get random English words in their otherwise 178localized diagnostic). The exceptions to this are C/C++ language keywords 179(e.g., ``auto``, ``const``, ``mutable``, etc) and C/C++ operators (``/=``). 180Note that things like "pointer" and "reference" are not keywords. On the other 181hand, you *can* include anything that comes from the user's source code, 182including variable names, types, labels, etc. The "``select``" format can be 183used to achieve this sort of thing in a localizable way, see below. 184 185Formatting a Diagnostic Argument 186^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 187 188Arguments to diagnostics are fully typed internally, and come from a couple 189different classes: integers, types, names, and random strings. Depending on 190the class of the argument, it can be optionally formatted in different ways. 191This gives the ``DiagnosticConsumer`` information about what the argument means 192without requiring it to use a specific presentation (consider this MVC for 193Clang :). 194 195Here are the different diagnostic argument formats currently supported by 196Clang: 197 198**"s" format** 199 200Example: 201 ``"requires %1 parameter%s1"`` 202Class: 203 Integers 204Description: 205 This is a simple formatter for integers that is useful when producing English 206 diagnostics. When the integer is 1, it prints as nothing. When the integer 207 is not 1, it prints as "``s``". This allows some simple grammatical forms to 208 be to be handled correctly, and eliminates the need to use gross things like 209 ``"requires %1 parameter(s)"``. 210 211**"select" format** 212 213Example: 214 ``"must be a %select{unary|binary|unary or binary}2 operator"`` 215Class: 216 Integers 217Description: 218 This format specifier is used to merge multiple related diagnostics together 219 into one common one, without requiring the difference to be specified as an 220 English string argument. Instead of specifying the string, the diagnostic 221 gets an integer argument and the format string selects the numbered option. 222 In this case, the "``%2``" value must be an integer in the range [0..2]. If 223 it is 0, it prints "unary", if it is 1 it prints "binary" if it is 2, it 224 prints "unary or binary". This allows other language translations to 225 substitute reasonable words (or entire phrases) based on the semantics of the 226 diagnostic instead of having to do things textually. The selected string 227 does undergo formatting. 228 229**"plural" format** 230 231Example: 232 ``"you have %1 %plural{1:mouse|:mice}1 connected to your computer"`` 233Class: 234 Integers 235Description: 236 This is a formatter for complex plural forms. It is designed to handle even 237 the requirements of languages with very complex plural forms, as many Baltic 238 languages have. The argument consists of a series of expression/form pairs, 239 separated by ":", where the first form whose expression evaluates to true is 240 the result of the modifier. 241 242 An expression can be empty, in which case it is always true. See the example 243 at the top. Otherwise, it is a series of one or more numeric conditions, 244 separated by ",". If any condition matches, the expression matches. Each 245 numeric condition can take one of three forms. 246 247 * number: A simple decimal number matches if the argument is the same as the 248 number. Example: ``"%plural{1:mouse|:mice}4"`` 249 * range: A range in square brackets matches if the argument is within the 250 range. Then range is inclusive on both ends. Example: 251 ``"%plural{0:none|1:one|[2,5]:some|:many}2"`` 252 * modulo: A modulo operator is followed by a number, and equals sign and 253 either a number or a range. The tests are the same as for plain numbers 254 and ranges, but the argument is taken modulo the number first. Example: 255 ``"%plural{%100=0:even hundred|%100=[1,50]:lower half|:everything else}1"`` 256 257 The parser is very unforgiving. A syntax error, even whitespace, will abort, 258 as will a failure to match the argument against any expression. 259 260**"ordinal" format** 261 262Example: 263 ``"ambiguity in %ordinal0 argument"`` 264Class: 265 Integers 266Description: 267 This is a formatter which represents the argument number as an ordinal: the 268 value ``1`` becomes ``1st``, ``3`` becomes ``3rd``, and so on. Values less 269 than ``1`` are not supported. This formatter is currently hard-coded to use 270 English ordinals. 271 272**"objcclass" format** 273 274Example: 275 ``"method %objcclass0 not found"`` 276Class: 277 ``DeclarationName`` 278Description: 279 This is a simple formatter that indicates the ``DeclarationName`` corresponds 280 to an Objective-C class method selector. As such, it prints the selector 281 with a leading "``+``". 282 283**"objcinstance" format** 284 285Example: 286 ``"method %objcinstance0 not found"`` 287Class: 288 ``DeclarationName`` 289Description: 290 This is a simple formatter that indicates the ``DeclarationName`` corresponds 291 to an Objective-C instance method selector. As such, it prints the selector 292 with a leading "``-``". 293 294**"q" format** 295 296Example: 297 ``"candidate found by name lookup is %q0"`` 298Class: 299 ``NamedDecl *`` 300Description: 301 This formatter indicates that the fully-qualified name of the declaration 302 should be printed, e.g., "``std::vector``" rather than "``vector``". 303 304**"diff" format** 305 306Example: 307 ``"no known conversion %diff{from $ to $|from argument type to parameter type}1,2"`` 308Class: 309 ``QualType`` 310Description: 311 This formatter takes two ``QualType``\ s and attempts to print a template 312 difference between the two. If tree printing is off, the text inside the 313 braces before the pipe is printed, with the formatted text replacing the $. 314 If tree printing is on, the text after the pipe is printed and a type tree is 315 printed after the diagnostic message. 316 317It is really easy to add format specifiers to the Clang diagnostics system, but 318they should be discussed before they are added. If you are creating a lot of 319repetitive diagnostics and/or have an idea for a useful formatter, please bring 320it up on the cfe-dev mailing list. 321 322**"sub" format** 323 324Example: 325 Given the following record definition of type ``TextSubstitution``: 326 327 .. code-block:: text 328 329 def select_ovl_candidate : TextSubstitution< 330 "%select{function|constructor}0%select{| template| %2}1">; 331 332 which can be used as 333 334 .. code-block:: text 335 336 def note_ovl_candidate : Note< 337 "candidate %sub{select_ovl_candidate}3,2,1 not viable">; 338 339 and will act as if it was written 340 ``"candidate %select{function|constructor}3%select{| template| %1}2 not viable"``. 341Description: 342 This format specifier is used to avoid repeating strings verbatim in multiple 343 diagnostics. The argument to ``%sub`` must name a ``TextSubstitution`` tblgen 344 record. The substitution must specify all arguments used by the substitution, 345 and the modifier indexes in the substitution are re-numbered accordingly. The 346 substituted text must itself be a valid format string before substitution. 347 348.. _internals-producing-diag: 349 350Producing the Diagnostic 351^^^^^^^^^^^^^^^^^^^^^^^^ 352 353Now that you've created the diagnostic in the ``Diagnostic*Kinds.td`` file, you 354need to write the code that detects the condition in question and emits the new 355diagnostic. Various components of Clang (e.g., the preprocessor, ``Sema``, 356etc.) provide a helper function named "``Diag``". It creates a diagnostic and 357accepts the arguments, ranges, and other information that goes along with it. 358 359For example, the binary expression error comes from code like this: 360 361.. code-block:: c++ 362 363 if (various things that are bad) 364 Diag(Loc, diag::err_typecheck_invalid_operands) 365 << lex->getType() << rex->getType() 366 << lex->getSourceRange() << rex->getSourceRange(); 367 368This shows that use of the ``Diag`` method: it takes a location (a 369:ref:`SourceLocation <SourceLocation>` object) and a diagnostic enum value 370(which matches the name from ``Diagnostic*Kinds.td``). If the diagnostic takes 371arguments, they are specified with the ``<<`` operator: the first argument 372becomes ``%0``, the second becomes ``%1``, etc. The diagnostic interface 373allows you to specify arguments of many different types, including ``int`` and 374``unsigned`` for integer arguments, ``const char*`` and ``std::string`` for 375string arguments, ``DeclarationName`` and ``const IdentifierInfo *`` for names, 376``QualType`` for types, etc. ``SourceRange``\ s are also specified with the 377``<<`` operator, but do not have a specific ordering requirement. 378 379As you can see, adding and producing a diagnostic is pretty straightforward. 380The hard part is deciding exactly what you need to say to help the user, 381picking a suitable wording, and providing the information needed to format it 382correctly. The good news is that the call site that issues a diagnostic should 383be completely independent of how the diagnostic is formatted and in what 384language it is rendered. 385 386Fix-It Hints 387^^^^^^^^^^^^ 388 389In some cases, the front end emits diagnostics when it is clear that some small 390change to the source code would fix the problem. For example, a missing 391semicolon at the end of a statement or a use of deprecated syntax that is 392easily rewritten into a more modern form. Clang tries very hard to emit the 393diagnostic and recover gracefully in these and other cases. 394 395However, for these cases where the fix is obvious, the diagnostic can be 396annotated with a hint (referred to as a "fix-it hint") that describes how to 397change the code referenced by the diagnostic to fix the problem. For example, 398it might add the missing semicolon at the end of the statement or rewrite the 399use of a deprecated construct into something more palatable. Here is one such 400example from the C++ front end, where we warn about the right-shift operator 401changing meaning from C++98 to C++11: 402 403.. code-block:: text 404 405 test.cpp:3:7: warning: use of right-shift operator ('>>') in template argument 406 will require parentheses in C++11 407 A<100 >> 2> *a; 408 ^ 409 ( ) 410 411Here, the fix-it hint is suggesting that parentheses be added, and showing 412exactly where those parentheses would be inserted into the source code. The 413fix-it hints themselves describe what changes to make to the source code in an 414abstract manner, which the text diagnostic printer renders as a line of 415"insertions" below the caret line. :ref:`Other diagnostic clients 416<DiagnosticConsumer>` might choose to render the code differently (e.g., as 417markup inline) or even give the user the ability to automatically fix the 418problem. 419 420Fix-it hints on errors and warnings need to obey these rules: 421 422* Since they are automatically applied if ``-Xclang -fixit`` is passed to the 423 driver, they should only be used when it's very likely they match the user's 424 intent. 425* Clang must recover from errors as if the fix-it had been applied. 426* Fix-it hints on a warning must not change the meaning of the code. 427 However, a hint may clarify the meaning as intentional, for example by adding 428 parentheses when the precedence of operators isn't obvious. 429 430If a fix-it can't obey these rules, put the fix-it on a note. Fix-its on notes 431are not applied automatically. 432 433All fix-it hints are described by the ``FixItHint`` class, instances of which 434should be attached to the diagnostic using the ``<<`` operator in the same way 435that highlighted source ranges and arguments are passed to the diagnostic. 436Fix-it hints can be created with one of three constructors: 437 438* ``FixItHint::CreateInsertion(Loc, Code)`` 439 440 Specifies that the given ``Code`` (a string) should be inserted before the 441 source location ``Loc``. 442 443* ``FixItHint::CreateRemoval(Range)`` 444 445 Specifies that the code in the given source ``Range`` should be removed. 446 447* ``FixItHint::CreateReplacement(Range, Code)`` 448 449 Specifies that the code in the given source ``Range`` should be removed, 450 and replaced with the given ``Code`` string. 451 452.. _DiagnosticConsumer: 453 454The ``DiagnosticConsumer`` Interface 455^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 456 457Once code generates a diagnostic with all of the arguments and the rest of the 458relevant information, Clang needs to know what to do with it. As previously 459mentioned, the diagnostic machinery goes through some filtering to map a 460severity onto a diagnostic level, then (assuming the diagnostic is not mapped 461to "``Ignore``") it invokes an object that implements the ``DiagnosticConsumer`` 462interface with the information. 463 464It is possible to implement this interface in many different ways. For 465example, the normal Clang ``DiagnosticConsumer`` (named 466``TextDiagnosticPrinter``) turns the arguments into strings (according to the 467various formatting rules), prints out the file/line/column information and the 468string, then prints out the line of code, the source ranges, and the caret. 469However, this behavior isn't required. 470 471Another implementation of the ``DiagnosticConsumer`` interface is the 472``TextDiagnosticBuffer`` class, which is used when Clang is in ``-verify`` 473mode. Instead of formatting and printing out the diagnostics, this 474implementation just captures and remembers the diagnostics as they fly by. 475Then ``-verify`` compares the list of produced diagnostics to the list of 476expected ones. If they disagree, it prints out its own output. Full 477documentation for the ``-verify`` mode can be found in the Clang API 478documentation for `VerifyDiagnosticConsumer 479</doxygen/classclang_1_1VerifyDiagnosticConsumer.html#details>`_. 480 481There are many other possible implementations of this interface, and this is 482why we prefer diagnostics to pass down rich structured information in 483arguments. For example, an HTML output might want declaration names be 484linkified to where they come from in the source. Another example is that a GUI 485might let you click on typedefs to expand them. This application would want to 486pass significantly more information about types through to the GUI than a 487simple flat string. The interface allows this to happen. 488 489.. _internals-diag-translation: 490 491Adding Translations to Clang 492^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 493 494Not possible yet! Diagnostic strings should be written in UTF-8, the client can 495translate to the relevant code page if needed. Each translation completely 496replaces the format string for the diagnostic. 497 498.. _SourceLocation: 499.. _SourceManager: 500 501The ``SourceLocation`` and ``SourceManager`` classes 502---------------------------------------------------- 503 504Strangely enough, the ``SourceLocation`` class represents a location within the 505source code of the program. Important design points include: 506 507#. ``sizeof(SourceLocation)`` must be extremely small, as these are embedded 508 into many AST nodes and are passed around often. Currently it is 32 bits. 509#. ``SourceLocation`` must be a simple value object that can be efficiently 510 copied. 511#. We should be able to represent a source location for any byte of any input 512 file. This includes in the middle of tokens, in whitespace, in trigraphs, 513 etc. 514#. A ``SourceLocation`` must encode the current ``#include`` stack that was 515 active when the location was processed. For example, if the location 516 corresponds to a token, it should contain the set of ``#include``\ s active 517 when the token was lexed. This allows us to print the ``#include`` stack 518 for a diagnostic. 519#. ``SourceLocation`` must be able to describe macro expansions, capturing both 520 the ultimate instantiation point and the source of the original character 521 data. 522 523In practice, the ``SourceLocation`` works together with the ``SourceManager`` 524class to encode two pieces of information about a location: its spelling 525location and its expansion location. For most tokens, these will be the 526same. However, for a macro expansion (or tokens that came from a ``_Pragma`` 527directive) these will describe the location of the characters corresponding to 528the token and the location where the token was used (i.e., the macro 529expansion point or the location of the ``_Pragma`` itself). 530 531The Clang front-end inherently depends on the location of a token being tracked 532correctly. If it is ever incorrect, the front-end may get confused and die. 533The reason for this is that the notion of the "spelling" of a ``Token`` in 534Clang depends on being able to find the original input characters for the 535token. This concept maps directly to the "spelling location" for the token. 536 537``SourceRange`` and ``CharSourceRange`` 538--------------------------------------- 539 540.. mostly taken from https://lists.llvm.org/pipermail/cfe-dev/2010-August/010595.html 541 542Clang represents most source ranges by [first, last], where "first" and "last" 543each point to the beginning of their respective tokens. For example consider 544the ``SourceRange`` of the following statement: 545 546.. code-block:: text 547 548 x = foo + bar; 549 ^first ^last 550 551To map from this representation to a character-based representation, the "last" 552location needs to be adjusted to point to (or past) the end of that token with 553either ``Lexer::MeasureTokenLength()`` or ``Lexer::getLocForEndOfToken()``. For 554the rare cases where character-level source ranges information is needed we use 555the ``CharSourceRange`` class. 556 557The Driver Library 558================== 559 560The clang Driver and library are documented :doc:`here <DriverInternals>`. 561 562Precompiled Headers 563=================== 564 565Clang supports precompiled headers (:doc:`PCH <PCHInternals>`), which uses a 566serialized representation of Clang's internal data structures, encoded with the 567`LLVM bitstream format <https://llvm.org/docs/BitCodeFormat.html>`_. 568 569The Frontend Library 570==================== 571 572The Frontend library contains functionality useful for building tools on top of 573the Clang libraries, for example several methods for outputting diagnostics. 574 575Compiler Invocation 576------------------- 577 578One of the classes provided by the Frontend library is ``CompilerInvocation``, 579which holds information that describe current invocation of the Clang ``-cc1`` 580frontend. The information typically comes from the command line constructed by 581the Clang driver or from clients performing custom initialization. The data 582structure is split into logical units used by different parts of the compiler, 583for example ``PreprocessorOptions``, ``LanguageOptions`` or ``CodeGenOptions``. 584 585Command Line Interface 586---------------------- 587 588The command line interface of the Clang ``-cc1`` frontend is defined alongside 589the driver options in ``clang/Driver/Options.td``. The information making up an 590option definition includes its prefix and name (for example ``-std=``), form and 591position of the option value, help text, aliases and more. Each option may 592belong to a certain group and can be marked with zero or more flags. Options 593accepted by the ``-cc1`` frontend are marked with the ``CC1Option`` flag. 594 595Command Line Parsing 596-------------------- 597 598Option definitions are processed by the ``-gen-opt-parser-defs`` tablegen 599backend during early stages of the build. Options are then used for querying an 600instance ``llvm::opt::ArgList``, a wrapper around the command line arguments. 601This is done in the Clang driver to construct individual jobs based on the 602driver arguments and also in the ``CompilerInvocation::CreateFromArgs`` function 603that parses the ``-cc1`` frontend arguments. 604 605Command Line Generation 606----------------------- 607 608Any valid ``CompilerInvocation`` created from a ``-cc1`` command line can be 609also serialized back into semantically equivalent command line in a 610deterministic manner. This enables features such as implicitly discovered, 611explicitly built modules. 612 613.. 614 TODO: Create and link corresponding section in Modules.rst. 615 616Adding new Command Line Option 617------------------------------ 618 619When adding a new command line option, the first place of interest is the header 620file declaring the corresponding options class (e.g. ``CodeGenOptions.h`` for 621command line option that affects the code generation). Create new member 622variable for the option value: 623 624.. code-block:: diff 625 626 class CodeGenOptions : public CodeGenOptionsBase { 627 628 + /// List of dynamic shared object files to be loaded as pass plugins. 629 + std::vector<std::string> PassPlugins; 630 631 } 632 633Next, declare the command line interface of the option in the tablegen file 634``clang/include/clang/Driver/Options.td``. This is done by instantiating the 635``Option`` class (defined in ``llvm/include/llvm/Option/OptParser.td``). The 636instance is typically created through one of the helper classes that encode the 637acceptable ways to specify the option value on the command line: 638 639* ``Flag`` - the option does not accept any value, 640* ``Joined`` - the value must immediately follow the option name within the same 641 argument, 642* ``Separate`` - the value must follow the option name in the next command line 643 argument, 644* ``JoinedOrSeparate`` - the value can be specified either as ``Joined`` or 645 ``Separate``, 646* ``CommaJoined`` - the values are comma-separated and must immediately follow 647 the option name within the same argument (see ``Wl,`` for an example). 648 649The helper classes take a list of acceptable prefixes of the option (e.g. 650``"-"``, ``"--"`` or ``"/"``) and the option name: 651 652.. code-block:: diff 653 654 // Options.td 655 656 + def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">; 657 658Then, specify additional attributes via mix-ins: 659 660* ``HelpText`` holds the text that will be printed besides the option name when 661 the user requests help (e.g. via ``clang --help``). 662* ``Group`` specifies the "category" of options this option belongs to. This is 663 used by various tools to filter certain options of interest. 664* ``Flags`` may contain a number of "tags" associated with the option. This 665 enables more granular filtering than the ``Group`` attribute. 666* ``Alias`` denotes that the option is an alias of another option. This may be 667 combined with ``AliasArgs`` that holds the implied value. 668 669.. code-block:: diff 670 671 // Options.td 672 673 def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">, 674 + Group<f_Group>, Flags<[CC1Option]>, 675 + HelpText<"Load pass plugin from a dynamic shared object file.">; 676 677New options are recognized by the Clang driver unless marked with the 678``NoDriverOption`` flag. On the other hand, options intended for the ``-cc1`` 679frontend must be explicitly marked with the ``CC1Option`` flag. 680 681Next, parse (or manufacture) the command line arguments in the Clang driver and 682use them to construct the ``-cc1`` job: 683 684.. code-block:: diff 685 686 void Clang::ConstructJob(const ArgList &Args /*...*/) const { 687 ArgStringList CmdArgs; 688 // ... 689 690 + for (const Arg *A : Args.filtered(OPT_fpass_plugin_EQ)) { 691 + CmdArgs.push_back(Args.MakeArgString(Twine("-fpass-plugin=") + A->getValue())); 692 + A->claim(); 693 + } 694 } 695 696The last step is implementing the ``-cc1`` command line argument 697parsing/generation that initializes/serializes the option class (in our case 698``CodeGenOptions``) stored within ``CompilerInvocation``. This can be done 699automatically by using the marshalling annotations on the option definition: 700 701.. code-block:: diff 702 703 // Options.td 704 705 def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">, 706 Group<f_Group>, Flags<[CC1Option]>, 707 HelpText<"Load pass plugin from a dynamic shared object file.">, 708 + MarshallingInfoStringVector<CodeGenOpts<"PassPlugins">>; 709 710Inner workings of the system are introduced in the :ref:`marshalling 711infrastructure <OptionMarshalling>` section and the available annotations are 712listed :ref:`here <OptionMarshallingAnnotations>`. 713 714In case the marshalling infrastructure does not support the desired semantics, 715consider simplifying it to fit the existing model. This makes the command line 716more uniform and reduces the amount of custom, manually written code. Remember 717that the ``-cc1`` command line interface is intended only for Clang developers, 718meaning it does not need to mirror the driver interface, maintain backward 719compatibility or be compatible with GCC. 720 721If the option semantics cannot be encoded via marshalling annotations, you can 722resort to parsing/serializing the command line arguments manually: 723 724.. code-block:: diff 725 726 // CompilerInvocation.cpp 727 728 static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args /*...*/) { 729 // ... 730 731 + Opts.PassPlugins = Args.getAllArgValues(OPT_fpass_plugin_EQ); 732 } 733 734 static void GenerateCodeGenArgs(const CodeGenOptions &Opts, 735 SmallVectorImpl<const char *> &Args, 736 CompilerInvocation::StringAllocator SA /*...*/) { 737 // ... 738 739 + for (const std::string &PassPlugin : Opts.PassPlugins) 740 + GenerateArg(Args, OPT_fpass_plugin_EQ, PassPlugin, SA); 741 } 742 743Finally, you can specify the argument on the command line: 744``clang -fpass-plugin=a -fpass-plugin=b`` and use the new member variable as 745desired. 746 747.. code-block:: diff 748 749 void EmitAssemblyHelper::EmitAssemblyWithNewPassManager(/*...*/) { 750 // ... 751 + for (auto &PluginFN : CodeGenOpts.PassPlugins) 752 + if (auto PassPlugin = PassPlugin::Load(PluginFN)) 753 + PassPlugin->registerPassBuilderCallbacks(PB); 754 } 755 756.. _OptionMarshalling: 757 758Option Marshalling Infrastructure 759--------------------------------- 760 761The option marshalling infrastructure automates the parsing of the Clang 762``-cc1`` frontend command line arguments into ``CompilerInvocation`` and their 763generation from ``CompilerInvocation``. The system replaces lots of repetitive 764C++ code with simple, declarative tablegen annotations and it's being used for 765the majority of the ``-cc1`` command line interface. This section provides an 766overview of the system. 767 768**Note:** The marshalling infrastructure is not intended for driver-only 769options. Only options of the ``-cc1`` frontend need to be marshalled to/from 770``CompilerInvocation`` instance. 771 772To read and modify contents of ``CompilerInvocation``, the marshalling system 773uses key paths, which are declared in two steps. First, a tablegen definition 774for the ``CompilerInvocation`` member is created by inheriting from 775``KeyPathAndMacro``: 776 777.. code-block:: text 778 779 // Options.td 780 781 class LangOpts<string field> : KeyPathAndMacro<"LangOpts->", field, "LANG_"> {} 782 // CompilerInvocation member ^^^^^^^^^^ 783 // OPTION_WITH_MARSHALLING prefix ^^^^^ 784 785The first argument to the parent class is the beginning of the key path that 786references the ``CompilerInvocation`` member. This argument ends with ``->`` if 787the member is a pointer type or with ``.`` if it's a value type. The child class 788takes a single parameter ``field`` that is forwarded as the second argument to 789the base class. The child class can then be used like so: 790``LangOpts<"IgnoreExceptions">``, constructing a key path to the field 791``LangOpts->IgnoreExceptions``. The third argument passed to the parent class is 792a string that the tablegen backend uses as a prefix to the 793``OPTION_WITH_MARSHALLING`` macro. Using the key path as a mix-in on an 794``Option`` instance instructs the backend to generate the following code: 795 796.. code-block:: c++ 797 798 // Options.inc 799 800 #ifdef LANG_OPTION_WITH_MARSHALLING 801 LANG_OPTION_WITH_MARSHALLING([...], LangOpts->IgnoreExceptions, [...]) 802 #endif // LANG_OPTION_WITH_MARSHALLING 803 804Such definition can be used used in the function for parsing and generating 805command line: 806 807.. code-block:: c++ 808 809 // clang/lib/Frontend/CompilerInvoation.cpp 810 811 bool CompilerInvocation::ParseLangArgs(LangOptions *LangOpts, ArgList &Args, 812 DiagnosticsEngine &Diags) { 813 bool Success = true; 814 815 #define LANG_OPTION_WITH_MARSHALLING( \ 816 PREFIX_TYPE, NAME, ID, KIND, GROUP, ALIAS, ALIASARGS, FLAGS, PARAM, \ 817 HELPTEXT, METAVAR, VALUES, SPELLING, SHOULD_PARSE, ALWAYS_EMIT, KEYPATH, \ 818 DEFAULT_VALUE, IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER, DENORMALIZER, \ 819 MERGER, EXTRACTOR, TABLE_INDEX) \ 820 PARSE_OPTION_WITH_MARSHALLING(Args, Diags, Success, ID, FLAGS, PARAM, \ 821 SHOULD_PARSE, KEYPATH, DEFAULT_VALUE, \ 822 IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER, \ 823 MERGER, TABLE_INDEX) 824 #include "clang/Driver/Options.inc" 825 #undef LANG_OPTION_WITH_MARSHALLING 826 827 // ... 828 829 return Success; 830 } 831 832 void CompilerInvocation::GenerateLangArgs(LangOptions *LangOpts, 833 SmallVectorImpl<const char *> &Args, 834 StringAllocator SA) { 835 #define LANG_OPTION_WITH_MARSHALLING( \ 836 PREFIX_TYPE, NAME, ID, KIND, GROUP, ALIAS, ALIASARGS, FLAGS, PARAM, \ 837 HELPTEXT, METAVAR, VALUES, SPELLING, SHOULD_PARSE, ALWAYS_EMIT, KEYPATH, \ 838 DEFAULT_VALUE, IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER, DENORMALIZER, \ 839 MERGER, EXTRACTOR, TABLE_INDEX) \ 840 GENERATE_OPTION_WITH_MARSHALLING( \ 841 Args, SA, KIND, FLAGS, SPELLING, ALWAYS_EMIT, KEYPATH, DEFAULT_VALUE, \ 842 IMPLIED_CHECK, IMPLIED_VALUE, DENORMALIZER, EXTRACTOR, TABLE_INDEX) 843 #include "clang/Driver/Options.inc" 844 #undef LANG_OPTION_WITH_MARSHALLING 845 846 // ... 847 } 848 849The ``PARSE_OPTION_WITH_MARSHALLING`` and ``GENERATE_OPTION_WITH_MARSHALLING`` 850macros are defined in ``CompilerInvocation.cpp`` and they implement the generic 851algorithm for parsing and generating command line arguments. 852 853.. _OptionMarshallingAnnotations: 854 855Option Marshalling Annotations 856------------------------------ 857 858How does the tablegen backend know what to put in place of ``[...]`` in the 859generated ``Options.inc``? This is specified by the ``Marshalling`` utilities 860described below. All of them take a key path argument and possibly other 861information required for parsing or generating the command line argument. 862 863**Note:** The marshalling infrastructure is not intended for driver-only 864options. Only options of the ``-cc1`` frontend need to be marshalled to/from 865``CompilerInvocation`` instance. 866 867**Positive Flag** 868 869The key path defaults to ``false`` and is set to ``true`` when the flag is 870present on command line. 871 872.. code-block:: text 873 874 def fignore_exceptions : Flag<["-"], "fignore-exceptions">, Flags<[CC1Option]>, 875 MarshallingInfoFlag<LangOpts<"IgnoreExceptions">>; 876 877**Negative Flag** 878 879The key path defaults to ``true`` and is set to ``false`` when the flag is 880present on command line. 881 882.. code-block:: text 883 884 def fno_verbose_asm : Flag<["-"], "fno-verbose-asm">, Flags<[CC1Option]>, 885 MarshallingInfoNegativeFlag<CodeGenOpts<"AsmVerbose">>; 886 887**Negative and Positive Flag** 888 889The key path defaults to the specified value (``false``, ``true`` or some 890boolean value that's statically unknown in the tablegen file). Then, the key 891path is set to the value associated with the flag that appears last on command 892line. 893 894.. code-block:: text 895 896 defm legacy_pass_manager : BoolOption<"f", "legacy-pass-manager", 897 CodeGenOpts<"LegacyPassManager">, DefaultFalse, 898 PosFlag<SetTrue, [], "Use the legacy pass manager in LLVM">, 899 NegFlag<SetFalse, [], "Use the new pass manager in LLVM">, 900 BothFlags<[CC1Option]>>; 901 902With most such pair of flags, the ``-cc1`` frontend accepts only the flag that 903changes the default key path value. The Clang driver is responsible for 904accepting both and either forwarding the changing flag or discarding the flag 905that would just set the key path to its default. 906 907The first argument to ``BoolOption`` is a prefix that is used to construct the 908full names of both flags. The positive flag would then be named 909``flegacy-pass-manager`` and the negative ``fno-legacy-pass-manager``. 910``BoolOption`` also implies the ``-`` prefix for both flags. It's also possible 911to use ``BoolFOption`` that implies the ``"f"`` prefix and ``Group<f_Group>``. 912The ``PosFlag`` and ``NegFlag`` classes hold the associated boolean value, an 913array of elements passed to the ``Flag`` class and the help text. The optional 914``BothFlags`` class holds an array of ``Flag`` elements that are common for both 915the positive and negative flag and their common help text suffix. 916 917**String** 918 919The key path defaults to the specified string, or an empty one, if omitted. When 920the option appears on the command line, the argument value is simply copied. 921 922.. code-block:: text 923 924 def isysroot : JoinedOrSeparate<["-"], "isysroot">, Flags<[CC1Option]>, 925 MarshallingInfoString<HeaderSearchOpts<"Sysroot">, [{"/"}]>; 926 927**List of Strings** 928 929The key path defaults to an empty ``std::vector<std::string>``. Values specified 930with each appearance of the option on the command line are appended to the 931vector. 932 933.. code-block:: text 934 935 def frewrite_map_file : Separate<["-"], "frewrite-map-file">, Flags<[CC1Option]>, 936 MarshallingInfoStringVector<CodeGenOpts<"RewriteMapFiles">>; 937 938**Integer** 939 940The key path defaults to the specified integer value, or ``0`` if omitted. When 941the option appears on the command line, its value gets parsed by ``llvm::APInt`` 942and the result is assigned to the key path on success. 943 944.. code-block:: text 945 946 def mstack_probe_size : Joined<["-"], "mstack-probe-size=">, Flags<[CC1Option]>, 947 MarshallingInfoInt<CodeGenOpts<"StackProbeSize">, "4096">; 948 949**Enumeration** 950 951The key path defaults to the value specified in ``MarshallingInfoEnum`` prefixed 952by the contents of ``NormalizedValuesScope`` and ``::``. This ensures correct 953reference to an enum case is formed even if the enum resides in different 954namespace or is an enum class. If the value present on command line does not 955match any of the comma-separated values from ``Values``, an error diagnostics is 956issued. Otherwise, the corresponding element from ``NormalizedValues`` at the 957same index is assigned to the key path (also correctly scoped). The number of 958comma-separated string values and elements of the array within 959``NormalizedValues`` must match. 960 961.. code-block:: text 962 963 def mthread_model : Separate<["-"], "mthread-model">, Flags<[CC1Option]>, 964 Values<"posix,single">, NormalizedValues<["POSIX", "Single"]>, 965 NormalizedValuesScope<"LangOptions::ThreadModelKind">, 966 MarshallingInfoEnum<LangOpts<"ThreadModel">, "POSIX">; 967 968.. 969 Intentionally omitting MarshallingInfoBitfieldFlag. It's adding some 970 complexity to the marshalling infrastructure and might be removed. 971 972It is also possible to define relationships between options. 973 974**Implication** 975 976The key path defaults to the default value from the primary ``Marshalling`` 977annotation. Then, if any of the elements of ``ImpliedByAnyOf`` evaluate to true, 978the key path value is changed to the specified value or ``true`` if missing. 979Finally, the command line is parsed according to the primary annotation. 980 981.. code-block:: text 982 983 def fms_extensions : Flag<["-"], "fms-extensions">, Flags<[CC1Option]>, 984 MarshallingInfoFlag<LangOpts<"MicrosoftExt">>, 985 ImpliedByAnyOf<[fms_compatibility.KeyPath], "true">; 986 987**Condition** 988 989The option is parsed only if the expression in ``ShouldParseIf`` evaluates to 990true. 991 992.. code-block:: text 993 994 def fopenmp_enable_irbuilder : Flag<["-"], "fopenmp-enable-irbuilder">, Flags<[CC1Option]>, 995 MarshallingInfoFlag<LangOpts<"OpenMPIRBuilder">>, 996 ShouldParseIf<fopenmp.KeyPath>; 997 998The Lexer and Preprocessor Library 999================================== 1000 1001The Lexer library contains several tightly-connected classes that are involved 1002with the nasty process of lexing and preprocessing C source code. The main 1003interface to this library for outside clients is the large ``Preprocessor`` 1004class. It contains the various pieces of state that are required to coherently 1005read tokens out of a translation unit. 1006 1007The core interface to the ``Preprocessor`` object (once it is set up) is the 1008``Preprocessor::Lex`` method, which returns the next :ref:`Token <Token>` from 1009the preprocessor stream. There are two types of token providers that the 1010preprocessor is capable of reading from: a buffer lexer (provided by the 1011:ref:`Lexer <Lexer>` class) and a buffered token stream (provided by the 1012:ref:`TokenLexer <TokenLexer>` class). 1013 1014.. _Token: 1015 1016The Token class 1017--------------- 1018 1019The ``Token`` class is used to represent a single lexed token. Tokens are 1020intended to be used by the lexer/preprocess and parser libraries, but are not 1021intended to live beyond them (for example, they should not live in the ASTs). 1022 1023Tokens most often live on the stack (or some other location that is efficient 1024to access) as the parser is running, but occasionally do get buffered up. For 1025example, macro definitions are stored as a series of tokens, and the C++ 1026front-end periodically needs to buffer tokens up for tentative parsing and 1027various pieces of look-ahead. As such, the size of a ``Token`` matters. On a 102832-bit system, ``sizeof(Token)`` is currently 16 bytes. 1029 1030Tokens occur in two forms: :ref:`annotation tokens <AnnotationToken>` and 1031normal tokens. Normal tokens are those returned by the lexer, annotation 1032tokens represent semantic information and are produced by the parser, replacing 1033normal tokens in the token stream. Normal tokens contain the following 1034information: 1035 1036* **A SourceLocation** --- This indicates the location of the start of the 1037 token. 1038 1039* **A length** --- This stores the length of the token as stored in the 1040 ``SourceBuffer``. For tokens that include them, this length includes 1041 trigraphs and escaped newlines which are ignored by later phases of the 1042 compiler. By pointing into the original source buffer, it is always possible 1043 to get the original spelling of a token completely accurately. 1044 1045* **IdentifierInfo** --- If a token takes the form of an identifier, and if 1046 identifier lookup was enabled when the token was lexed (e.g., the lexer was 1047 not reading in "raw" mode) this contains a pointer to the unique hash value 1048 for the identifier. Because the lookup happens before keyword 1049 identification, this field is set even for language keywords like "``for``". 1050 1051* **TokenKind** --- This indicates the kind of token as classified by the 1052 lexer. This includes things like ``tok::starequal`` (for the "``*=``" 1053 operator), ``tok::ampamp`` for the "``&&``" token, and keyword values (e.g., 1054 ``tok::kw_for``) for identifiers that correspond to keywords. Note that 1055 some tokens can be spelled multiple ways. For example, C++ supports 1056 "operator keywords", where things like "``and``" are treated exactly like the 1057 "``&&``" operator. In these cases, the kind value is set to ``tok::ampamp``, 1058 which is good for the parser, which doesn't have to consider both forms. For 1059 something that cares about which form is used (e.g., the preprocessor 1060 "stringize" operator) the spelling indicates the original form. 1061 1062* **Flags** --- There are currently four flags tracked by the 1063 lexer/preprocessor system on a per-token basis: 1064 1065 #. **StartOfLine** --- This was the first token that occurred on its input 1066 source line. 1067 #. **LeadingSpace** --- There was a space character either immediately before 1068 the token or transitively before the token as it was expanded through a 1069 macro. The definition of this flag is very closely defined by the 1070 stringizing requirements of the preprocessor. 1071 #. **DisableExpand** --- This flag is used internally to the preprocessor to 1072 represent identifier tokens which have macro expansion disabled. This 1073 prevents them from being considered as candidates for macro expansion ever 1074 in the future. 1075 #. **NeedsCleaning** --- This flag is set if the original spelling for the 1076 token includes a trigraph or escaped newline. Since this is uncommon, 1077 many pieces of code can fast-path on tokens that did not need cleaning. 1078 1079One interesting (and somewhat unusual) aspect of normal tokens is that they 1080don't contain any semantic information about the lexed value. For example, if 1081the token was a pp-number token, we do not represent the value of the number 1082that was lexed (this is left for later pieces of code to decide). 1083Additionally, the lexer library has no notion of typedef names vs variable 1084names: both are returned as identifiers, and the parser is left to decide 1085whether a specific identifier is a typedef or a variable (tracking this 1086requires scope information among other things). The parser can do this 1087translation by replacing tokens returned by the preprocessor with "Annotation 1088Tokens". 1089 1090.. _AnnotationToken: 1091 1092Annotation Tokens 1093----------------- 1094 1095Annotation tokens are tokens that are synthesized by the parser and injected 1096into the preprocessor's token stream (replacing existing tokens) to record 1097semantic information found by the parser. For example, if "``foo``" is found 1098to be a typedef, the "``foo``" ``tok::identifier`` token is replaced with an 1099``tok::annot_typename``. This is useful for a couple of reasons: 1) this makes 1100it easy to handle qualified type names (e.g., "``foo::bar::baz<42>::t``") in 1101C++ as a single "token" in the parser. 2) if the parser backtracks, the 1102reparse does not need to redo semantic analysis to determine whether a token 1103sequence is a variable, type, template, etc. 1104 1105Annotation tokens are created by the parser and reinjected into the parser's 1106token stream (when backtracking is enabled). Because they can only exist in 1107tokens that the preprocessor-proper is done with, it doesn't need to keep 1108around flags like "start of line" that the preprocessor uses to do its job. 1109Additionally, an annotation token may "cover" a sequence of preprocessor tokens 1110(e.g., "``a::b::c``" is five preprocessor tokens). As such, the valid fields 1111of an annotation token are different than the fields for a normal token (but 1112they are multiplexed into the normal ``Token`` fields): 1113 1114* **SourceLocation "Location"** --- The ``SourceLocation`` for the annotation 1115 token indicates the first token replaced by the annotation token. In the 1116 example above, it would be the location of the "``a``" identifier. 1117* **SourceLocation "AnnotationEndLoc"** --- This holds the location of the last 1118 token replaced with the annotation token. In the example above, it would be 1119 the location of the "``c``" identifier. 1120* **void* "AnnotationValue"** --- This contains an opaque object that the 1121 parser gets from ``Sema``. The parser merely preserves the information for 1122 ``Sema`` to later interpret based on the annotation token kind. 1123* **TokenKind "Kind"** --- This indicates the kind of Annotation token this is. 1124 See below for the different valid kinds. 1125 1126Annotation tokens currently come in three kinds: 1127 1128#. **tok::annot_typename**: This annotation token represents a resolved 1129 typename token that is potentially qualified. The ``AnnotationValue`` field 1130 contains the ``QualType`` returned by ``Sema::getTypeName()``, possibly with 1131 source location information attached. 1132#. **tok::annot_cxxscope**: This annotation token represents a C++ scope 1133 specifier, such as "``A::B::``". This corresponds to the grammar 1134 productions "*::*" and "*:: [opt] nested-name-specifier*". The 1135 ``AnnotationValue`` pointer is a ``NestedNameSpecifier *`` returned by the 1136 ``Sema::ActOnCXXGlobalScopeSpecifier`` and 1137 ``Sema::ActOnCXXNestedNameSpecifier`` callbacks. 1138#. **tok::annot_template_id**: This annotation token represents a C++ 1139 template-id such as "``foo<int, 4>``", where "``foo``" is the name of a 1140 template. The ``AnnotationValue`` pointer is a pointer to a ``malloc``'d 1141 ``TemplateIdAnnotation`` object. Depending on the context, a parsed 1142 template-id that names a type might become a typename annotation token (if 1143 all we care about is the named type, e.g., because it occurs in a type 1144 specifier) or might remain a template-id token (if we want to retain more 1145 source location information or produce a new type, e.g., in a declaration of 1146 a class template specialization). template-id annotation tokens that refer 1147 to a type can be "upgraded" to typename annotation tokens by the parser. 1148 1149As mentioned above, annotation tokens are not returned by the preprocessor, 1150they are formed on demand by the parser. This means that the parser has to be 1151aware of cases where an annotation could occur and form it where appropriate. 1152This is somewhat similar to how the parser handles Translation Phase 6 of C99: 1153String Concatenation (see C99 5.1.1.2). In the case of string concatenation, 1154the preprocessor just returns distinct ``tok::string_literal`` and 1155``tok::wide_string_literal`` tokens and the parser eats a sequence of them 1156wherever the grammar indicates that a string literal can occur. 1157 1158In order to do this, whenever the parser expects a ``tok::identifier`` or 1159``tok::coloncolon``, it should call the ``TryAnnotateTypeOrScopeToken`` or 1160``TryAnnotateCXXScopeToken`` methods to form the annotation token. These 1161methods will maximally form the specified annotation tokens and replace the 1162current token with them, if applicable. If the current tokens is not valid for 1163an annotation token, it will remain an identifier or "``::``" token. 1164 1165.. _Lexer: 1166 1167The ``Lexer`` class 1168------------------- 1169 1170The ``Lexer`` class provides the mechanics of lexing tokens out of a source 1171buffer and deciding what they mean. The ``Lexer`` is complicated by the fact 1172that it operates on raw buffers that have not had spelling eliminated (this is 1173a necessity to get decent performance), but this is countered with careful 1174coding as well as standard performance techniques (for example, the comment 1175handling code is vectorized on X86 and PowerPC hosts). 1176 1177The lexer has a couple of interesting modal features: 1178 1179* The lexer can operate in "raw" mode. This mode has several features that 1180 make it possible to quickly lex the file (e.g., it stops identifier lookup, 1181 doesn't specially handle preprocessor tokens, handles EOF differently, etc). 1182 This mode is used for lexing within an "``#if 0``" block, for example. 1183* The lexer can capture and return comments as tokens. This is required to 1184 support the ``-C`` preprocessor mode, which passes comments through, and is 1185 used by the diagnostic checker to identifier expect-error annotations. 1186* The lexer can be in ``ParsingFilename`` mode, which happens when 1187 preprocessing after reading a ``#include`` directive. This mode changes the 1188 parsing of "``<``" to return an "angled string" instead of a bunch of tokens 1189 for each thing within the filename. 1190* When parsing a preprocessor directive (after "``#``") the 1191 ``ParsingPreprocessorDirective`` mode is entered. This changes the parser to 1192 return EOD at a newline. 1193* The ``Lexer`` uses a ``LangOptions`` object to know whether trigraphs are 1194 enabled, whether C++ or ObjC keywords are recognized, etc. 1195 1196In addition to these modes, the lexer keeps track of a couple of other features 1197that are local to a lexed buffer, which change as the buffer is lexed: 1198 1199* The ``Lexer`` uses ``BufferPtr`` to keep track of the current character being 1200 lexed. 1201* The ``Lexer`` uses ``IsAtStartOfLine`` to keep track of whether the next 1202 lexed token will start with its "start of line" bit set. 1203* The ``Lexer`` keeps track of the current "``#if``" directives that are active 1204 (which can be nested). 1205* The ``Lexer`` keeps track of an :ref:`MultipleIncludeOpt 1206 <MultipleIncludeOpt>` object, which is used to detect whether the buffer uses 1207 the standard "``#ifndef XX`` / ``#define XX``" idiom to prevent multiple 1208 inclusion. If a buffer does, subsequent includes can be ignored if the 1209 "``XX``" macro is defined. 1210 1211.. _TokenLexer: 1212 1213The ``TokenLexer`` class 1214------------------------ 1215 1216The ``TokenLexer`` class is a token provider that returns tokens from a list of 1217tokens that came from somewhere else. It typically used for two things: 1) 1218returning tokens from a macro definition as it is being expanded 2) returning 1219tokens from an arbitrary buffer of tokens. The later use is used by 1220``_Pragma`` and will most likely be used to handle unbounded look-ahead for the 1221C++ parser. 1222 1223.. _MultipleIncludeOpt: 1224 1225The ``MultipleIncludeOpt`` class 1226-------------------------------- 1227 1228The ``MultipleIncludeOpt`` class implements a really simple little state 1229machine that is used to detect the standard "``#ifndef XX`` / ``#define XX``" 1230idiom that people typically use to prevent multiple inclusion of headers. If a 1231buffer uses this idiom and is subsequently ``#include``'d, the preprocessor can 1232simply check to see whether the guarding condition is defined or not. If so, 1233the preprocessor can completely ignore the include of the header. 1234 1235.. _Parser: 1236 1237The Parser Library 1238================== 1239 1240This library contains a recursive-descent parser that polls tokens from the 1241preprocessor and notifies a client of the parsing progress. 1242 1243Historically, the parser used to talk to an abstract ``Action`` interface that 1244had virtual methods for parse events, for example ``ActOnBinOp()``. When Clang 1245grew C++ support, the parser stopped supporting general ``Action`` clients -- 1246it now always talks to the :ref:`Sema library <Sema>`. However, the Parser 1247still accesses AST objects only through opaque types like ``ExprResult`` and 1248``StmtResult``. Only :ref:`Sema <Sema>` looks at the AST node contents of these 1249wrappers. 1250 1251.. _AST: 1252 1253The AST Library 1254=============== 1255 1256.. _ASTPhilosophy: 1257 1258Design philosophy 1259----------------- 1260 1261Immutability 1262^^^^^^^^^^^^ 1263 1264Clang AST nodes (types, declarations, statements, expressions, and so on) are 1265generally designed to be immutable once created. This provides a number of key 1266benefits: 1267 1268 * Canonicalization of the "meaning" of nodes is possible as soon as the nodes 1269 are created, and is not invalidated by later addition of more information. 1270 For example, we :ref:`canonicalize types <CanonicalType>`, and use a 1271 canonicalized representation of expressions when determining whether two 1272 function template declarations involving dependent expressions declare the 1273 same entity. 1274 * AST nodes can be reused when they have the same meaning. For example, we 1275 reuse ``Type`` nodes when representing the same type (but maintain separate 1276 ``TypeLoc``\s for each instance where a type is written), and we reuse 1277 non-dependent ``Stmt`` and ``Expr`` nodes across instantiations of a 1278 template. 1279 * Serialization and deserialization of the AST to/from AST files is simpler: 1280 we do not need to track modifications made to AST nodes imported from AST 1281 files and serialize separate "update records". 1282 1283There are unfortunately exceptions to this general approach, such as: 1284 1285 * The first declaration of a redeclarable entity maintains a pointer to the 1286 most recent declaration of that entity, which naturally needs to change as 1287 more declarations are parsed. 1288 * Name lookup tables in declaration contexts change after the namespace 1289 declaration is formed. 1290 * We attempt to maintain only a single declaration for an instantiation of a 1291 template, rather than having distinct declarations for an instantiation of 1292 the declaration versus the definition, so template instantiation often 1293 updates parts of existing declarations. 1294 * Some parts of declarations are required to be instantiated separately (this 1295 includes default arguments and exception specifications), and such 1296 instantiations update the existing declaration. 1297 1298These cases tend to be fragile; mutable AST state should be avoided where 1299possible. 1300 1301As a consequence of this design principle, we typically do not provide setters 1302for AST state. (Some are provided for short-term modifications intended to be 1303used immediately after an AST node is created and before it's "published" as 1304part of the complete AST, or where language semantics require after-the-fact 1305updates.) 1306 1307Faithfulness 1308^^^^^^^^^^^^ 1309 1310The AST intends to provide a representation of the program that is faithful to 1311the original source. We intend for it to be possible to write refactoring tools 1312using only information stored in, or easily reconstructible from, the Clang AST. 1313This means that the AST representation should either not desugar source-level 1314constructs to simpler forms, or -- where made necessary by language semantics 1315or a clear engineering tradeoff -- should desugar minimally and wrap the result 1316in a construct representing the original source form. 1317 1318For example, ``CXXForRangeStmt`` directly represents the syntactic form of a 1319range-based for statement, but also holds a semantic representation of the 1320range declaration and iterator declarations. It does not contain a 1321fully-desugared ``ForStmt``, however. 1322 1323Some AST nodes (for example, ``ParenExpr``) represent only syntax, and others 1324(for example, ``ImplicitCastExpr``) represent only semantics, but most nodes 1325will represent a combination of syntax and associated semantics. Inheritance 1326is typically used when representing different (but related) syntaxes for nodes 1327with the same or similar semantics. 1328 1329.. _Type: 1330 1331The ``Type`` class and its subclasses 1332------------------------------------- 1333 1334The ``Type`` class (and its subclasses) are an important part of the AST. 1335Types are accessed through the ``ASTContext`` class, which implicitly creates 1336and uniques them as they are needed. Types have a couple of non-obvious 1337features: 1) they do not capture type qualifiers like ``const`` or ``volatile`` 1338(see :ref:`QualType <QualType>`), and 2) they implicitly capture typedef 1339information. Once created, types are immutable (unlike decls). 1340 1341Typedefs in C make semantic analysis a bit more complex than it would be without 1342them. The issue is that we want to capture typedef information and represent it 1343in the AST perfectly, but the semantics of operations need to "see through" 1344typedefs. For example, consider this code: 1345 1346.. code-block:: c++ 1347 1348 void func() { 1349 typedef int foo; 1350 foo X, *Y; 1351 typedef foo *bar; 1352 bar Z; 1353 *X; // error 1354 **Y; // error 1355 **Z; // error 1356 } 1357 1358The code above is illegal, and thus we expect there to be diagnostics emitted 1359on the annotated lines. In this example, we expect to get: 1360 1361.. code-block:: text 1362 1363 test.c:6:1: error: indirection requires pointer operand ('foo' invalid) 1364 *X; // error 1365 ^~ 1366 test.c:7:1: error: indirection requires pointer operand ('foo' invalid) 1367 **Y; // error 1368 ^~~ 1369 test.c:8:1: error: indirection requires pointer operand ('foo' invalid) 1370 **Z; // error 1371 ^~~ 1372 1373While this example is somewhat silly, it illustrates the point: we want to 1374retain typedef information where possible, so that we can emit errors about 1375"``std::string``" instead of "``std::basic_string<char, std:...``". Doing this 1376requires properly keeping typedef information (for example, the type of ``X`` 1377is "``foo``", not "``int``"), and requires properly propagating it through the 1378various operators (for example, the type of ``*Y`` is "``foo``", not 1379"``int``"). In order to retain this information, the type of these expressions 1380is an instance of the ``TypedefType`` class, which indicates that the type of 1381these expressions is a typedef for "``foo``". 1382 1383Representing types like this is great for diagnostics, because the 1384user-specified type is always immediately available. There are two problems 1385with this: first, various semantic checks need to make judgements about the 1386*actual structure* of a type, ignoring typedefs. Second, we need an efficient 1387way to query whether two types are structurally identical to each other, 1388ignoring typedefs. The solution to both of these problems is the idea of 1389canonical types. 1390 1391.. _CanonicalType: 1392 1393Canonical Types 1394^^^^^^^^^^^^^^^ 1395 1396Every instance of the ``Type`` class contains a canonical type pointer. For 1397simple types with no typedefs involved (e.g., "``int``", "``int*``", 1398"``int**``"), the type just points to itself. For types that have a typedef 1399somewhere in their structure (e.g., "``foo``", "``foo*``", "``foo**``", 1400"``bar``"), the canonical type pointer points to their structurally equivalent 1401type without any typedefs (e.g., "``int``", "``int*``", "``int**``", and 1402"``int*``" respectively). 1403 1404This design provides a constant time operation (dereferencing the canonical type 1405pointer) that gives us access to the structure of types. For example, we can 1406trivially tell that "``bar``" and "``foo*``" are the same type by dereferencing 1407their canonical type pointers and doing a pointer comparison (they both point 1408to the single "``int*``" type). 1409 1410Canonical types and typedef types bring up some complexities that must be 1411carefully managed. Specifically, the ``isa``/``cast``/``dyn_cast`` operators 1412generally shouldn't be used in code that is inspecting the AST. For example, 1413when type checking the indirection operator (unary "``*``" on a pointer), the 1414type checker must verify that the operand has a pointer type. It would not be 1415correct to check that with "``isa<PointerType>(SubExpr->getType())``", because 1416this predicate would fail if the subexpression had a typedef type. 1417 1418The solution to this problem are a set of helper methods on ``Type``, used to 1419check their properties. In this case, it would be correct to use 1420"``SubExpr->getType()->isPointerType()``" to do the check. This predicate will 1421return true if the *canonical type is a pointer*, which is true any time the 1422type is structurally a pointer type. The only hard part here is remembering 1423not to use the ``isa``/``cast``/``dyn_cast`` operations. 1424 1425The second problem we face is how to get access to the pointer type once we 1426know it exists. To continue the example, the result type of the indirection 1427operator is the pointee type of the subexpression. In order to determine the 1428type, we need to get the instance of ``PointerType`` that best captures the 1429typedef information in the program. If the type of the expression is literally 1430a ``PointerType``, we can return that, otherwise we have to dig through the 1431typedefs to find the pointer type. For example, if the subexpression had type 1432"``foo*``", we could return that type as the result. If the subexpression had 1433type "``bar``", we want to return "``foo*``" (note that we do *not* want 1434"``int*``"). In order to provide all of this, ``Type`` has a 1435``getAsPointerType()`` method that checks whether the type is structurally a 1436``PointerType`` and, if so, returns the best one. If not, it returns a null 1437pointer. 1438 1439This structure is somewhat mystical, but after meditating on it, it will make 1440sense to you :). 1441 1442.. _QualType: 1443 1444The ``QualType`` class 1445---------------------- 1446 1447The ``QualType`` class is designed as a trivial value class that is small, 1448passed by-value and is efficient to query. The idea of ``QualType`` is that it 1449stores the type qualifiers (``const``, ``volatile``, ``restrict``, plus some 1450extended qualifiers required by language extensions) separately from the types 1451themselves. ``QualType`` is conceptually a pair of "``Type*``" and the bits 1452for these type qualifiers. 1453 1454By storing the type qualifiers as bits in the conceptual pair, it is extremely 1455efficient to get the set of qualifiers on a ``QualType`` (just return the field 1456of the pair), add a type qualifier (which is a trivial constant-time operation 1457that sets a bit), and remove one or more type qualifiers (just return a 1458``QualType`` with the bitfield set to empty). 1459 1460Further, because the bits are stored outside of the type itself, we do not need 1461to create duplicates of types with different sets of qualifiers (i.e. there is 1462only a single heap allocated "``int``" type: "``const int``" and "``volatile 1463const int``" both point to the same heap allocated "``int``" type). This 1464reduces the heap size used to represent bits and also means we do not have to 1465consider qualifiers when uniquing types (:ref:`Type <Type>` does not even 1466contain qualifiers). 1467 1468In practice, the two most common type qualifiers (``const`` and ``restrict``) 1469are stored in the low bits of the pointer to the ``Type`` object, together with 1470a flag indicating whether extended qualifiers are present (which must be 1471heap-allocated). This means that ``QualType`` is exactly the same size as a 1472pointer. 1473 1474.. _DeclarationName: 1475 1476Declaration names 1477----------------- 1478 1479The ``DeclarationName`` class represents the name of a declaration in Clang. 1480Declarations in the C family of languages can take several different forms. 1481Most declarations are named by simple identifiers, e.g., "``f``" and "``x``" in 1482the function declaration ``f(int x)``. In C++, declaration names can also name 1483class constructors ("``Class``" in ``struct Class { Class(); }``), class 1484destructors ("``~Class``"), overloaded operator names ("``operator+``"), and 1485conversion functions ("``operator void const *``"). In Objective-C, 1486declaration names can refer to the names of Objective-C methods, which involve 1487the method name and the parameters, collectively called a *selector*, e.g., 1488"``setWidth:height:``". Since all of these kinds of entities --- variables, 1489functions, Objective-C methods, C++ constructors, destructors, and operators 1490--- are represented as subclasses of Clang's common ``NamedDecl`` class, 1491``DeclarationName`` is designed to efficiently represent any kind of name. 1492 1493Given a ``DeclarationName`` ``N``, ``N.getNameKind()`` will produce a value 1494that describes what kind of name ``N`` stores. There are 10 options (all of 1495the names are inside the ``DeclarationName`` class). 1496 1497``Identifier`` 1498 1499 The name is a simple identifier. Use ``N.getAsIdentifierInfo()`` to retrieve 1500 the corresponding ``IdentifierInfo*`` pointing to the actual identifier. 1501 1502``ObjCZeroArgSelector``, ``ObjCOneArgSelector``, ``ObjCMultiArgSelector`` 1503 1504 The name is an Objective-C selector, which can be retrieved as a ``Selector`` 1505 instance via ``N.getObjCSelector()``. The three possible name kinds for 1506 Objective-C reflect an optimization within the ``DeclarationName`` class: 1507 both zero- and one-argument selectors are stored as a masked 1508 ``IdentifierInfo`` pointer, and therefore require very little space, since 1509 zero- and one-argument selectors are far more common than multi-argument 1510 selectors (which use a different structure). 1511 1512``CXXConstructorName`` 1513 1514 The name is a C++ constructor name. Use ``N.getCXXNameType()`` to retrieve 1515 the :ref:`type <QualType>` that this constructor is meant to construct. The 1516 type is always the canonical type, since all constructors for a given type 1517 have the same name. 1518 1519``CXXDestructorName`` 1520 1521 The name is a C++ destructor name. Use ``N.getCXXNameType()`` to retrieve 1522 the :ref:`type <QualType>` whose destructor is being named. This type is 1523 always a canonical type. 1524 1525``CXXConversionFunctionName`` 1526 1527 The name is a C++ conversion function. Conversion functions are named 1528 according to the type they convert to, e.g., "``operator void const *``". 1529 Use ``N.getCXXNameType()`` to retrieve the type that this conversion function 1530 converts to. This type is always a canonical type. 1531 1532``CXXOperatorName`` 1533 1534 The name is a C++ overloaded operator name. Overloaded operators are named 1535 according to their spelling, e.g., "``operator+``" or "``operator new []``". 1536 Use ``N.getCXXOverloadedOperator()`` to retrieve the overloaded operator (a 1537 value of type ``OverloadedOperatorKind``). 1538 1539``CXXLiteralOperatorName`` 1540 1541 The name is a C++11 user defined literal operator. User defined 1542 Literal operators are named according to the suffix they define, 1543 e.g., "``_foo``" for "``operator "" _foo``". Use 1544 ``N.getCXXLiteralIdentifier()`` to retrieve the corresponding 1545 ``IdentifierInfo*`` pointing to the identifier. 1546 1547``CXXUsingDirective`` 1548 1549 The name is a C++ using directive. Using directives are not really 1550 NamedDecls, in that they all have the same name, but they are 1551 implemented as such in order to store them in DeclContext 1552 effectively. 1553 1554``DeclarationName``\ s are cheap to create, copy, and compare. They require 1555only a single pointer's worth of storage in the common cases (identifiers, 1556zero- and one-argument Objective-C selectors) and use dense, uniqued storage 1557for the other kinds of names. Two ``DeclarationName``\ s can be compared for 1558equality (``==``, ``!=``) using a simple bitwise comparison, can be ordered 1559with ``<``, ``>``, ``<=``, and ``>=`` (which provide a lexicographical ordering 1560for normal identifiers but an unspecified ordering for other kinds of names), 1561and can be placed into LLVM ``DenseMap``\ s and ``DenseSet``\ s. 1562 1563``DeclarationName`` instances can be created in different ways depending on 1564what kind of name the instance will store. Normal identifiers 1565(``IdentifierInfo`` pointers) and Objective-C selectors (``Selector``) can be 1566implicitly converted to ``DeclarationNames``. Names for C++ constructors, 1567destructors, conversion functions, and overloaded operators can be retrieved 1568from the ``DeclarationNameTable``, an instance of which is available as 1569``ASTContext::DeclarationNames``. The member functions 1570``getCXXConstructorName``, ``getCXXDestructorName``, 1571``getCXXConversionFunctionName``, and ``getCXXOperatorName``, respectively, 1572return ``DeclarationName`` instances for the four kinds of C++ special function 1573names. 1574 1575.. _DeclContext: 1576 1577Declaration contexts 1578-------------------- 1579 1580Every declaration in a program exists within some *declaration context*, such 1581as a translation unit, namespace, class, or function. Declaration contexts in 1582Clang are represented by the ``DeclContext`` class, from which the various 1583declaration-context AST nodes (``TranslationUnitDecl``, ``NamespaceDecl``, 1584``RecordDecl``, ``FunctionDecl``, etc.) will derive. The ``DeclContext`` class 1585provides several facilities common to each declaration context: 1586 1587Source-centric vs. Semantics-centric View of Declarations 1588 1589 ``DeclContext`` provides two views of the declarations stored within a 1590 declaration context. The source-centric view accurately represents the 1591 program source code as written, including multiple declarations of entities 1592 where present (see the section :ref:`Redeclarations and Overloads 1593 <Redeclarations>`), while the semantics-centric view represents the program 1594 semantics. The two views are kept synchronized by semantic analysis while 1595 the ASTs are being constructed. 1596 1597Storage of declarations within that context 1598 1599 Every declaration context can contain some number of declarations. For 1600 example, a C++ class (represented by ``RecordDecl``) contains various member 1601 functions, fields, nested types, and so on. All of these declarations will 1602 be stored within the ``DeclContext``, and one can iterate over the 1603 declarations via [``DeclContext::decls_begin()``, 1604 ``DeclContext::decls_end()``). This mechanism provides the source-centric 1605 view of declarations in the context. 1606 1607Lookup of declarations within that context 1608 1609 The ``DeclContext`` structure provides efficient name lookup for names within 1610 that declaration context. For example, if ``N`` is a namespace we can look 1611 for the name ``N::f`` using ``DeclContext::lookup``. The lookup itself is 1612 based on a lazily-constructed array (for declaration contexts with a small 1613 number of declarations) or hash table (for declaration contexts with more 1614 declarations). The lookup operation provides the semantics-centric view of 1615 the declarations in the context. 1616 1617Ownership of declarations 1618 1619 The ``DeclContext`` owns all of the declarations that were declared within 1620 its declaration context, and is responsible for the management of their 1621 memory as well as their (de-)serialization. 1622 1623All declarations are stored within a declaration context, and one can query 1624information about the context in which each declaration lives. One can 1625retrieve the ``DeclContext`` that contains a particular ``Decl`` using 1626``Decl::getDeclContext``. However, see the section 1627:ref:`LexicalAndSemanticContexts` for more information about how to interpret 1628this context information. 1629 1630.. _Redeclarations: 1631 1632Redeclarations and Overloads 1633^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1634 1635Within a translation unit, it is common for an entity to be declared several 1636times. For example, we might declare a function "``f``" and then later 1637re-declare it as part of an inlined definition: 1638 1639.. code-block:: c++ 1640 1641 void f(int x, int y, int z = 1); 1642 1643 inline void f(int x, int y, int z) { /* ... */ } 1644 1645The representation of "``f``" differs in the source-centric and 1646semantics-centric views of a declaration context. In the source-centric view, 1647all redeclarations will be present, in the order they occurred in the source 1648code, making this view suitable for clients that wish to see the structure of 1649the source code. In the semantics-centric view, only the most recent "``f``" 1650will be found by the lookup, since it effectively replaces the first 1651declaration of "``f``". 1652 1653(Note that because ``f`` can be redeclared at block scope, or in a friend 1654declaration, etc. it is possible that the declaration of ``f`` found by name 1655lookup will not be the most recent one.) 1656 1657In the semantics-centric view, overloading of functions is represented 1658explicitly. For example, given two declarations of a function "``g``" that are 1659overloaded, e.g., 1660 1661.. code-block:: c++ 1662 1663 void g(); 1664 void g(int); 1665 1666the ``DeclContext::lookup`` operation will return a 1667``DeclContext::lookup_result`` that contains a range of iterators over 1668declarations of "``g``". Clients that perform semantic analysis on a program 1669that is not concerned with the actual source code will primarily use this 1670semantics-centric view. 1671 1672.. _LexicalAndSemanticContexts: 1673 1674Lexical and Semantic Contexts 1675^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1676 1677Each declaration has two potentially different declaration contexts: a 1678*lexical* context, which corresponds to the source-centric view of the 1679declaration context, and a *semantic* context, which corresponds to the 1680semantics-centric view. The lexical context is accessible via 1681``Decl::getLexicalDeclContext`` while the semantic context is accessible via 1682``Decl::getDeclContext``, both of which return ``DeclContext`` pointers. For 1683most declarations, the two contexts are identical. For example: 1684 1685.. code-block:: c++ 1686 1687 class X { 1688 public: 1689 void f(int x); 1690 }; 1691 1692Here, the semantic and lexical contexts of ``X::f`` are the ``DeclContext`` 1693associated with the class ``X`` (itself stored as a ``RecordDecl`` AST node). 1694However, we can now define ``X::f`` out-of-line: 1695 1696.. code-block:: c++ 1697 1698 void X::f(int x = 17) { /* ... */ } 1699 1700This definition of "``f``" has different lexical and semantic contexts. The 1701lexical context corresponds to the declaration context in which the actual 1702declaration occurred in the source code, e.g., the translation unit containing 1703``X``. Thus, this declaration of ``X::f`` can be found by traversing the 1704declarations provided by [``decls_begin()``, ``decls_end()``) in the 1705translation unit. 1706 1707The semantic context of ``X::f`` corresponds to the class ``X``, since this 1708member function is (semantically) a member of ``X``. Lookup of the name ``f`` 1709into the ``DeclContext`` associated with ``X`` will then return the definition 1710of ``X::f`` (including information about the default argument). 1711 1712Transparent Declaration Contexts 1713^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1714 1715In C and C++, there are several contexts in which names that are logically 1716declared inside another declaration will actually "leak" out into the enclosing 1717scope from the perspective of name lookup. The most obvious instance of this 1718behavior is in enumeration types, e.g., 1719 1720.. code-block:: c++ 1721 1722 enum Color { 1723 Red, 1724 Green, 1725 Blue 1726 }; 1727 1728Here, ``Color`` is an enumeration, which is a declaration context that contains 1729the enumerators ``Red``, ``Green``, and ``Blue``. Thus, traversing the list of 1730declarations contained in the enumeration ``Color`` will yield ``Red``, 1731``Green``, and ``Blue``. However, outside of the scope of ``Color`` one can 1732name the enumerator ``Red`` without qualifying the name, e.g., 1733 1734.. code-block:: c++ 1735 1736 Color c = Red; 1737 1738There are other entities in C++ that provide similar behavior. For example, 1739linkage specifications that use curly braces: 1740 1741.. code-block:: c++ 1742 1743 extern "C" { 1744 void f(int); 1745 void g(int); 1746 } 1747 // f and g are visible here 1748 1749For source-level accuracy, we treat the linkage specification and enumeration 1750type as a declaration context in which its enclosed declarations ("``Red``", 1751"``Green``", and "``Blue``"; "``f``" and "``g``") are declared. However, these 1752declarations are visible outside of the scope of the declaration context. 1753 1754These language features (and several others, described below) have roughly the 1755same set of requirements: declarations are declared within a particular lexical 1756context, but the declarations are also found via name lookup in scopes 1757enclosing the declaration itself. This feature is implemented via 1758*transparent* declaration contexts (see 1759``DeclContext::isTransparentContext()``), whose declarations are visible in the 1760nearest enclosing non-transparent declaration context. This means that the 1761lexical context of the declaration (e.g., an enumerator) will be the 1762transparent ``DeclContext`` itself, as will the semantic context, but the 1763declaration will be visible in every outer context up to and including the 1764first non-transparent declaration context (since transparent declaration 1765contexts can be nested). 1766 1767The transparent ``DeclContext``\ s are: 1768 1769* Enumerations (but not C++11 "scoped enumerations"): 1770 1771 .. code-block:: c++ 1772 1773 enum Color { 1774 Red, 1775 Green, 1776 Blue 1777 }; 1778 // Red, Green, and Blue are in scope 1779 1780* C++ linkage specifications: 1781 1782 .. code-block:: c++ 1783 1784 extern "C" { 1785 void f(int); 1786 void g(int); 1787 } 1788 // f and g are in scope 1789 1790* Anonymous unions and structs: 1791 1792 .. code-block:: c++ 1793 1794 struct LookupTable { 1795 bool IsVector; 1796 union { 1797 std::vector<Item> *Vector; 1798 std::set<Item> *Set; 1799 }; 1800 }; 1801 1802 LookupTable LT; 1803 LT.Vector = 0; // Okay: finds Vector inside the unnamed union 1804 1805* C++11 inline namespaces: 1806 1807 .. code-block:: c++ 1808 1809 namespace mylib { 1810 inline namespace debug { 1811 class X; 1812 } 1813 } 1814 mylib::X *xp; // okay: mylib::X refers to mylib::debug::X 1815 1816.. _MultiDeclContext: 1817 1818Multiply-Defined Declaration Contexts 1819^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1820 1821C++ namespaces have the interesting property that 1822the namespace can be defined multiple times, and the declarations provided by 1823each namespace definition are effectively merged (from the semantic point of 1824view). For example, the following two code snippets are semantically 1825indistinguishable: 1826 1827.. code-block:: c++ 1828 1829 // Snippet #1: 1830 namespace N { 1831 void f(); 1832 } 1833 namespace N { 1834 void f(int); 1835 } 1836 1837 // Snippet #2: 1838 namespace N { 1839 void f(); 1840 void f(int); 1841 } 1842 1843In Clang's representation, the source-centric view of declaration contexts will 1844actually have two separate ``NamespaceDecl`` nodes in Snippet #1, each of which 1845is a declaration context that contains a single declaration of "``f``". 1846However, the semantics-centric view provided by name lookup into the namespace 1847``N`` for "``f``" will return a ``DeclContext::lookup_result`` that contains a 1848range of iterators over declarations of "``f``". 1849 1850``DeclContext`` manages multiply-defined declaration contexts internally. The 1851function ``DeclContext::getPrimaryContext`` retrieves the "primary" context for 1852a given ``DeclContext`` instance, which is the ``DeclContext`` responsible for 1853maintaining the lookup table used for the semantics-centric view. Given a 1854DeclContext, one can obtain the set of declaration contexts that are 1855semantically connected to this declaration context, in source order, including 1856this context (which will be the only result, for non-namespace contexts) via 1857``DeclContext::collectAllContexts``. Note that these functions are used 1858internally within the lookup and insertion methods of the ``DeclContext``, so 1859the vast majority of clients can ignore them. 1860 1861Because the same entity can be defined multiple times in different modules, 1862it is also possible for there to be multiple definitions of (for instance) 1863a ``CXXRecordDecl``, all of which describe a definition of the same class. 1864In such a case, only one of those "definitions" is considered by Clang to be 1865the definition of the class, and the others are treated as non-defining 1866declarations that happen to also contain member declarations. Corresponding 1867members in each definition of such multiply-defined classes are identified 1868either by redeclaration chains (if the members are ``Redeclarable``) 1869or by simply a pointer to the canonical declaration (if the declarations 1870are not ``Redeclarable`` -- in that case, a ``Mergeable`` base class is used 1871instead). 1872 1873Error Handling 1874-------------- 1875 1876Clang produces an AST even when the code contains errors. Clang won't generate 1877and optimize code for it, but it's used as parsing continues to detect further 1878errors in the input. Clang-based tools also depend on such ASTs, and IDEs in 1879particular benefit from a high-quality AST for broken code. 1880 1881In presence of errors, clang uses a few error-recovery strategies to present the 1882broken code in the AST: 1883 1884- correcting errors: in cases where clang is confident about the fix, it 1885 provides a FixIt attaching to the error diagnostic and emits a corrected AST 1886 (reflecting the written code with FixIts applied). The advantage of that is to 1887 provide more accurate subsequent diagnostics. Typo correction is a typical 1888 example. 1889- representing invalid node: the invalid node is preserved in the AST in some 1890 form, e.g. when the "declaration" part of the declaration contains semantic 1891 errors, the Decl node is marked as invalid. 1892- dropping invalid node: this often happens for errors that we don’t have 1893 graceful recovery. Prior to Recovery AST, a mismatched-argument function call 1894 expression was dropped though a CallExpr was created for semantic analysis. 1895 1896With these strategies, clang surfaces better diagnostics, and provides AST 1897consumers a rich AST reflecting the written source code as much as possible even 1898for broken code. 1899 1900Recovery AST 1901^^^^^^^^^^^^ 1902 1903The idea of Recovery AST is to use recovery nodes which act as a placeholder to 1904maintain the rough structure of the parsing tree, preserve locations and 1905children but have no language semantics attached to them. 1906 1907For example, consider the following mismatched function call: 1908 1909.. code-block:: c++ 1910 1911 int NoArg(); 1912 void test(int abc) { 1913 NoArg(abc); // oops, mismatched function arguments. 1914 } 1915 1916Without Recovery AST, the invalid function call expression (and its child 1917expressions) would be dropped in the AST: 1918 1919:: 1920 1921 |-FunctionDecl <line:1:1, col:11> NoArg 'int ()' 1922 `-FunctionDecl <line:2:1, line:4:1> test 'void (int)' 1923 |-ParmVarDecl <col:11, col:15> col:15 used abc 'int' 1924 `-CompoundStmt <col:20, line:4:1> 1925 1926 1927With Recovery AST, the AST looks like: 1928 1929:: 1930 1931 |-FunctionDecl <line:1:1, col:11> NoArg 'int ()' 1932 `-FunctionDecl <line:2:1, line:4:1> test 'void (int)' 1933 |-ParmVarDecl <col:11, col:15> used abc 'int' 1934 `-CompoundStmt <col:20, line:4:1> 1935 `-RecoveryExpr <line:3:3, col:12> 'int' contains-errors 1936 |-UnresolvedLookupExpr <col:3> '<overloaded function type>' lvalue (ADL) = 'NoArg' 1937 `-DeclRefExpr <col:9> 'int' lvalue ParmVar 'abc' 'int' 1938 1939 1940An alternative is to use existing Exprs, e.g. CallExpr for the above example. 1941This would capture more call details (e.g. locations of parentheses) and allow 1942it to be treated uniformly with valid CallExprs. However, jamming the data we 1943have into CallExpr forces us to weaken its invariants, e.g. arg count may be 1944wrong. This would introduce a huge burden on consumers of the AST to handle such 1945"impossible" cases. So when we're representing (rather than correcting) errors, 1946we use a distinct recovery node type with extremely weak invariants instead. 1947 1948``RecoveryExpr`` is the only recovery node so far. In practice, broken decls 1949need more detailed semantics preserved (the current ``Invalid`` flag works 1950fairly well), and completely broken statements with interesting internal 1951structure are rare (so dropping the statements is OK). 1952 1953Types and dependence 1954^^^^^^^^^^^^^^^^^^^^ 1955 1956``RecoveryExpr`` is an ``Expr``, so it must have a type. In many cases the true 1957type can't really be known until the code is corrected (e.g. a call to a 1958function that doesn't exist). And it means that we can't properly perform type 1959checks on some containing constructs, such as ``return 42 + unknownFunction()``. 1960 1961To model this, we generalize the concept of dependence from C++ templates to 1962mean dependence on a template parameter or how an error is repaired. The 1963``RecoveryExpr`` ``unknownFunction()`` has the totally unknown type 1964``DependentTy``, and this suppresses type-based analysis in the same way it 1965would inside a template. 1966 1967In cases where we are confident about the concrete type (e.g. the return type 1968for a broken non-overloaded function call), the ``RecoveryExpr`` will have this 1969type. This allows more code to be typechecked, and produces a better AST and 1970more diagnostics. For example: 1971 1972.. code-block:: C++ 1973 1974 unknownFunction().size() // .size() is a CXXDependentScopeMemberExpr 1975 std::string(42).size() // .size() is a resolved MemberExpr 1976 1977Whether or not the ``RecoveryExpr`` has a dependent type, it is always 1978considered value-dependent, because its value isn't well-defined until the error 1979is resolved. Among other things, this means that clang doesn't emit more errors 1980where a RecoveryExpr is used as a constant (e.g. array size), but also won't try 1981to evaluate it. 1982 1983ContainsErrors bit 1984^^^^^^^^^^^^^^^^^^ 1985 1986Beyond the template dependence bits, we add a new “ContainsErrors” bit to 1987express “Does this expression or anything within it contain errors” semantic, 1988this bit is always set for RecoveryExpr, and propagated to other related nodes. 1989This provides a fast way to query whether any (recursive) child of an expression 1990had an error, which is often used to improve diagnostics. 1991 1992.. code-block:: C++ 1993 1994 // C++ 1995 void recoveryExpr(int abc) { 1996 unknownFunction(); // type-dependent, value-dependent, contains-errors 1997 1998 std::string(42).size(); // value-dependent, contains-errors, 1999 // not type-dependent, as we know the type is std::string 2000 } 2001 2002 2003.. code-block:: C 2004 2005 // C 2006 void recoveryExpr(int abc) { 2007 unknownVar + abc; // type-dependent, value-dependent, contains-errors 2008 } 2009 2010 2011The ASTImporter 2012--------------- 2013 2014The ``ASTImporter`` class imports nodes of an ``ASTContext`` into another 2015``ASTContext``. Please refer to the document :doc:`ASTImporter: Merging Clang 2016ASTs <LibASTImporter>` for an introduction. And please read through the 2017high-level `description of the import algorithm 2018<LibASTImporter.html#algorithm-of-the-import>`_, this is essential for 2019understanding further implementation details of the importer. 2020 2021.. _templated: 2022 2023Abstract Syntax Graph 2024^^^^^^^^^^^^^^^^^^^^^ 2025 2026Despite the name, the Clang AST is not a tree. It is a directed graph with 2027cycles. One example of a cycle is the connection between a 2028``ClassTemplateDecl`` and its "templated" ``CXXRecordDecl``. The *templated* 2029``CXXRecordDecl`` represents all the fields and methods inside the class 2030template, while the ``ClassTemplateDecl`` holds the information which is 2031related to being a template, i.e. template arguments, etc. We can get the 2032*templated* class (the ``CXXRecordDecl``) of a ``ClassTemplateDecl`` with 2033``ClassTemplateDecl::getTemplatedDecl()``. And we can get back a pointer of the 2034"described" class template from the *templated* class: 2035``CXXRecordDecl::getDescribedTemplate()``. So, this is a cycle between two 2036nodes: between the *templated* and the *described* node. There may be various 2037other kinds of cycles in the AST especially in case of declarations. 2038 2039.. _structural-eq: 2040 2041Structural Equivalency 2042^^^^^^^^^^^^^^^^^^^^^^ 2043 2044Importing one AST node copies that node into the destination ``ASTContext``. To 2045copy one node means that we create a new node in the "to" context then we set 2046its properties to be equal to the properties of the source node. Before the 2047copy, we make sure that the source node is not *structurally equivalent* to any 2048existing node in the destination context. If it happens to be equivalent then 2049we skip the copy. 2050 2051The informal definition of structural equivalency is the following: 2052Two nodes are **structurally equivalent** if they are 2053 2054- builtin types and refer to the same type, e.g. ``int`` and ``int`` are 2055 structurally equivalent, 2056- function types and all their parameters have structurally equivalent types, 2057- record types and all their fields in order of their definition have the same 2058 identifier names and structurally equivalent types, 2059- variable or function declarations and they have the same identifier name and 2060 their types are structurally equivalent. 2061 2062In C, two types are structurally equivalent if they are *compatible types*. For 2063a formal definition of *compatible types*, please refer to 6.2.7/1 in the C11 2064standard. However, there is no definition for *compatible types* in the C++ 2065standard. Still, we extend the definition of structural equivalency to 2066templates and their instantiations similarly: besides checking the previously 2067mentioned properties, we have to check for equivalent template 2068parameters/arguments, etc. 2069 2070The structural equivalent check can be and is used independently from the 2071ASTImporter, e.g. the ``clang::Sema`` class uses it also. 2072 2073The equivalence of nodes may depend on the equivalency of other pairs of nodes. 2074Thus, the check is implemented as a parallel graph traversal. We traverse 2075through the nodes of both graphs at the same time. The actual implementation is 2076similar to breadth-first-search. Let's say we start the traverse with the <A,B> 2077pair of nodes. Whenever the traversal reaches a pair <X,Y> then the following 2078statements are true: 2079 2080- A and X are nodes from the same ASTContext. 2081- B and Y are nodes from the same ASTContext. 2082- A and B may or may not be from the same ASTContext. 2083- if A == X and B == Y (pointer equivalency) then (there is a cycle during the 2084 traverse) 2085 2086 - A and B are structurally equivalent if and only if 2087 2088 - All dependent nodes on the path from <A,B> to <X,Y> are structurally 2089 equivalent. 2090 2091When we compare two classes or enums and one of them is incomplete or has 2092unloaded external lexical declarations then we cannot descend to compare their 2093contained declarations. So in these cases they are considered equal if they 2094have the same names. This is the way how we compare forward declarations with 2095definitions. 2096 2097.. TODO Should we elaborate the actual implementation of the graph traversal, 2098.. which is a very weird BFS traversal? 2099 2100Redeclaration Chains 2101^^^^^^^^^^^^^^^^^^^^ 2102 2103The early version of the ``ASTImporter``'s merge mechanism squashed the 2104declarations, i.e. it aimed to have only one declaration instead of maintaining 2105a whole redeclaration chain. This early approach simply skipped importing a 2106function prototype, but it imported a definition. To demonstrate the problem 2107with this approach let's consider an empty "to" context and the following 2108``virtual`` function declarations of ``f`` in the "from" context: 2109 2110.. code-block:: c++ 2111 2112 struct B { virtual void f(); }; 2113 void B::f() {} // <-- let's import this definition 2114 2115If we imported the definition with the "squashing" approach then we would 2116end-up having one declaration which is indeed a definition, but ``isVirtual()`` 2117returns ``false`` for it. The reason is that the definition is indeed not 2118virtual, it is the property of the prototype! 2119 2120Consequently, we must either set the virtual flag for the definition (but then 2121we create a malformed AST which the parser would never create), or we import 2122the whole redeclaration chain of the function. The most recent version of the 2123``ASTImporter`` uses the latter mechanism. We do import all function 2124declarations - regardless if they are definitions or prototypes - in the order 2125as they appear in the "from" context. 2126 2127.. One definition 2128 2129If we have an existing definition in the "to" context, then we cannot import 2130another definition, we will use the existing definition. However, we can import 2131prototype(s): we chain the newly imported prototype(s) to the existing 2132definition. Whenever we import a new prototype from a third context, that will 2133be added to the end of the redeclaration chain. This may result in long 2134redeclaration chains in certain cases, e.g. if we import from several 2135translation units which include the same header with the prototype. 2136 2137.. Squashing prototypes 2138 2139To mitigate the problem of long redeclaration chains of free functions, we 2140could compare prototypes to see if they have the same properties and if yes 2141then we could merge these prototypes. The implementation of squashing of 2142prototypes for free functions is future work. 2143 2144.. Exception: Cannot have more than 1 prototype in-class 2145 2146Chaining functions this way ensures that we do copy all information from the 2147source AST. Nonetheless, there is a problem with member functions: While we can 2148have many prototypes for free functions, we must have only one prototype for a 2149member function. 2150 2151.. code-block:: c++ 2152 2153 void f(); // OK 2154 void f(); // OK 2155 2156 struct X { 2157 void f(); // OK 2158 void f(); // ERROR 2159 }; 2160 void X::f() {} // OK 2161 2162Thus, prototypes of member functions must be squashed, we cannot just simply 2163attach a new prototype to the existing in-class prototype. Consider the 2164following contexts: 2165 2166.. code-block:: c++ 2167 2168 // "to" context 2169 struct X { 2170 void f(); // D0 2171 }; 2172 2173.. code-block:: c++ 2174 2175 // "from" context 2176 struct X { 2177 void f(); // D1 2178 }; 2179 void X::f() {} // D2 2180 2181When we import the prototype and the definition of ``f`` from the "from" 2182context, then the resulting redecl chain will look like this ``D0 -> D2'``, 2183where ``D2'`` is the copy of ``D2`` in the "to" context. 2184 2185.. Redecl chains of other declarations 2186 2187Generally speaking, when we import declarations (like enums and classes) we do 2188attach the newly imported declaration to the existing redeclaration chain (if 2189there is structural equivalency). We do not import, however, the whole 2190redeclaration chain as we do in case of functions. Up till now, we haven't 2191found any essential property of forward declarations which is similar to the 2192case of the virtual flag in a member function prototype. In the future, this 2193may change, though. 2194 2195Traversal during the Import 2196^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2197 2198The node specific import mechanisms are implemented in 2199``ASTNodeImporter::VisitNode()`` functions, e.g. ``VisitFunctionDecl()``. 2200When we import a declaration then first we import everything which is needed to 2201call the constructor of that declaration node. Everything which can be set 2202later is set after the node is created. For example, in case of a 2203``FunctionDecl`` we first import the declaration context in which the function 2204is declared, then we create the ``FunctionDecl`` and only then we import the 2205body of the function. This means there are implicit dependencies between AST 2206nodes. These dependencies determine the order in which we visit nodes in the 2207"from" context. As with the regular graph traversal algorithms like DFS, we 2208keep track which nodes we have already visited in 2209``ASTImporter::ImportedDecls``. Whenever we create a node then we immediately 2210add that to the ``ImportedDecls``. We must not start the import of any other 2211declarations before we keep track of the newly created one. This is essential, 2212otherwise, we would not be able to handle circular dependencies. To enforce 2213this, we wrap all constructor calls of all AST nodes in 2214``GetImportedOrCreateDecl()``. This wrapper ensures that all newly created 2215declarations are immediately marked as imported; also, if a declaration is 2216already marked as imported then we just return its counterpart in the "to" 2217context. Consequently, calling a declaration's ``::Create()`` function directly 2218would lead to errors, please don't do that! 2219 2220Even with the use of ``GetImportedOrCreateDecl()`` there is still a 2221probability of having an infinite import recursion if things are imported from 2222each other in wrong way. Imagine that during the import of ``A``, the import of 2223``B`` is requested before we could create the node for ``A`` (the constructor 2224needs a reference to ``B``). And the same could be true for the import of ``B`` 2225(``A`` is requested to be imported before we could create the node for ``B``). 2226In case of the :ref:`templated-described swing <templated>` we take 2227extra attention to break the cyclical dependency: we import and set the 2228described template only after the ``CXXRecordDecl`` is created. As a best 2229practice, before creating the node in the "to" context, avoid importing of 2230other nodes which are not needed for the constructor of node ``A``. 2231 2232Error Handling 2233^^^^^^^^^^^^^^ 2234 2235Every import function returns with either an ``llvm::Error`` or an 2236``llvm::Expected<T>`` object. This enforces to check the return value of the 2237import functions. If there was an error during one import then we return with 2238that error. (Exception: when we import the members of a class, we collect the 2239individual errors with each member and we concatenate them in one Error 2240object.) We cache these errors in cases of declarations. During the next import 2241call if there is an existing error we just return with that. So, clients of the 2242library receive an Error object, which they must check. 2243 2244During import of a specific declaration, it may happen that some AST nodes had 2245already been created before we recognize an error. In this case, we signal back 2246the error to the caller, but the "to" context remains polluted with those nodes 2247which had been created. Ideally, those nodes should not had been created, but 2248that time we did not know about the error, the error happened later. Since the 2249AST is immutable (most of the cases we can't remove existing nodes) we choose 2250to mark these nodes as erroneous. 2251 2252We cache the errors associated with declarations in the "from" context in 2253``ASTImporter::ImportDeclErrors`` and the ones which are associated with the 2254"to" context in ``ASTImporterSharedState::ImportErrors``. Note that, there may 2255be several ASTImporter objects which import into the same "to" context but from 2256different "from" contexts; in this case, they have to share the associated 2257errors of the "to" context. 2258 2259When an error happens, that propagates through the call stack, through all the 2260dependant nodes. However, in case of dependency cycles, this is not enough, 2261because we strive to mark the erroneous nodes so clients can act upon. In those 2262cases, we have to keep track of the errors for those nodes which are 2263intermediate nodes of a cycle. 2264 2265An **import path** is the list of the AST nodes which we visit during an Import 2266call. If node ``A`` depends on node ``B`` then the path contains an ``A->B`` 2267edge. From the call stack of the import functions, we can read the very same 2268path. 2269 2270Now imagine the following AST, where the ``->`` represents dependency in terms 2271of the import (all nodes are declarations). 2272 2273.. code-block:: text 2274 2275 A->B->C->D 2276 `->E 2277 2278We would like to import A. 2279The import behaves like a DFS, so we will visit the nodes in this order: ABCDE. 2280During the visitation we will have the following import paths: 2281 2282.. code-block:: text 2283 2284 A 2285 AB 2286 ABC 2287 ABCD 2288 ABC 2289 AB 2290 ABE 2291 AB 2292 A 2293 2294If during the visit of E there is an error then we set an error for E, then as 2295the call stack shrinks for B, then for A: 2296 2297.. code-block:: text 2298 2299 A 2300 AB 2301 ABC 2302 ABCD 2303 ABC 2304 AB 2305 ABE // Error! Set an error to E 2306 AB // Set an error to B 2307 A // Set an error to A 2308 2309However, during the import we could import C and D without any error and they 2310are independent of A,B and E. We must not set up an error for C and D. So, at 2311the end of the import we have an entry in ``ImportDeclErrors`` for A,B,E but 2312not for C,D. 2313 2314Now, what happens if there is a cycle in the import path? Let's consider this 2315AST: 2316 2317.. code-block:: text 2318 2319 A->B->C->A 2320 `->E 2321 2322During the visitation, we will have the below import paths and if during the 2323visit of E there is an error then we will set up an error for E,B,A. But what's 2324up with C? 2325 2326.. code-block:: text 2327 2328 A 2329 AB 2330 ABC 2331 ABCA 2332 ABC 2333 AB 2334 ABE // Error! Set an error to E 2335 AB // Set an error to B 2336 A // Set an error to A 2337 2338This time we know that both B and C are dependent on A. This means we must set 2339up an error for C too. As the call stack reverses back we get to A and we must 2340set up an error to all nodes which depend on A (this includes C). But C is no 2341longer on the import path, it just had been previously. Such a situation can 2342happen only if during the visitation we had a cycle. If we didn't have any 2343cycle, then the normal way of passing an Error object through the call stack 2344could handle the situation. This is why we must track cycles during the import 2345process for each visited declaration. 2346 2347Lookup Problems 2348^^^^^^^^^^^^^^^ 2349 2350When we import a declaration from the source context then we check whether we 2351already have a structurally equivalent node with the same name in the "to" 2352context. If the "from" node is a definition and the found one is also a 2353definition, then we do not create a new node, instead, we mark the found node 2354as the imported node. If the found definition and the one we want to import 2355have the same name but they are structurally in-equivalent, then we have an ODR 2356violation in case of C++. If the "from" node is not a definition then we add 2357that to the redeclaration chain of the found node. This behaviour is essential 2358when we merge ASTs from different translation units which include the same 2359header file(s). For example, we want to have only one definition for the class 2360template ``std::vector``, even if we included ``<vector>`` in several 2361translation units. 2362 2363To find a structurally equivalent node we can use the regular C/C++ lookup 2364functions: ``DeclContext::noload_lookup()`` and 2365``DeclContext::localUncachedLookup()``. These functions do respect the C/C++ 2366name hiding rules, thus you cannot find certain declarations in a given 2367declaration context. For instance, unnamed declarations (anonymous structs), 2368non-first ``friend`` declarations and template specializations are hidden. This 2369is a problem, because if we use the regular C/C++ lookup then we create 2370redundant AST nodes during the merge! Also, having two instances of the same 2371node could result in false :ref:`structural in-equivalencies <structural-eq>` 2372of other nodes which depend on the duplicated node. Because of these reasons, 2373we created a lookup class which has the sole purpose to register all 2374declarations, so later they can be looked up by subsequent import requests. 2375This is the ``ASTImporterLookupTable`` class. This lookup table should be 2376shared amongst the different ``ASTImporter`` instances if they happen to import 2377to the very same "to" context. This is why we can use the importer specific 2378lookup only via the ``ASTImporterSharedState`` class. 2379 2380ExternalASTSource 2381~~~~~~~~~~~~~~~~~ 2382 2383The ``ExternalASTSource`` is an abstract interface associated with the 2384``ASTContext`` class. It provides the ability to read the declarations stored 2385within a declaration context either for iteration or for name lookup. A 2386declaration context with an external AST source may load its declarations 2387on-demand. This means that the list of declarations (represented as a linked 2388list, the head is ``DeclContext::FirstDecl``) could be empty. However, member 2389functions like ``DeclContext::lookup()`` may initiate a load. 2390 2391Usually, external sources are associated with precompiled headers. For example, 2392when we load a class from a PCH then the members are loaded only if we do want 2393to look up something in the class' context. 2394 2395In case of LLDB, an implementation of the ``ExternalASTSource`` interface is 2396attached to the AST context which is related to the parsed expression. This 2397implementation of the ``ExternalASTSource`` interface is realized with the help 2398of the ``ASTImporter`` class. This way, LLDB can reuse Clang's parsing 2399machinery while synthesizing the underlying AST from the debug data (e.g. from 2400DWARF). From the view of the ``ASTImporter`` this means both the "to" and the 2401"from" context may have declaration contexts with external lexical storage. If 2402a ``DeclContext`` in the "to" AST context has external lexical storage then we 2403must take extra attention to work only with the already loaded declarations! 2404Otherwise, we would end up with an uncontrolled import process. For instance, 2405if we used the regular ``DeclContext::lookup()`` to find the existing 2406declarations in the "to" context then the ``lookup()`` call itself would 2407initiate a new import while we are in the middle of importing a declaration! 2408(By the time we initiate the lookup we haven't registered yet that we already 2409started to import the node of the "from" context.) This is why we use 2410``DeclContext::noload_lookup()`` instead. 2411 2412Class Template Instantiations 2413^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2414 2415Different translation units may have class template instantiations with the 2416same template arguments, but with a different set of instantiated 2417``MethodDecls`` and ``FieldDecls``. Consider the following files: 2418 2419.. code-block:: c++ 2420 2421 // x.h 2422 template <typename T> 2423 struct X { 2424 int a{0}; // FieldDecl with InitListExpr 2425 X(char) : a(3) {} // (1) 2426 X(int) {} // (2) 2427 }; 2428 2429 // foo.cpp 2430 void foo() { 2431 // ClassTemplateSpec with ctor (1): FieldDecl without InitlistExpr 2432 X<char> xc('c'); 2433 } 2434 2435 // bar.cpp 2436 void bar() { 2437 // ClassTemplateSpec with ctor (2): FieldDecl WITH InitlistExpr 2438 X<char> xc(1); 2439 } 2440 2441In ``foo.cpp`` we use the constructor with number ``(1)``, which explicitly 2442initializes the member ``a`` to ``3``, thus the ``InitListExpr`` ``{0}`` is not 2443used here and the AST node is not instantiated. However, in the case of 2444``bar.cpp`` we use the constructor with number ``(2)``, which does not 2445explicitly initialize the ``a`` member, so the default ``InitListExpr`` is 2446needed and thus instantiated. When we merge the AST of ``foo.cpp`` and 2447``bar.cpp`` we must create an AST node for the class template instantiation of 2448``X<char>`` which has all the required nodes. Therefore, when we find an 2449existing ``ClassTemplateSpecializationDecl`` then we merge the fields of the 2450``ClassTemplateSpecializationDecl`` in the "from" context in a way that the 2451``InitListExpr`` is copied if not existent yet. The same merge mechanism should 2452be done in the cases of instantiated default arguments and exception 2453specifications of functions. 2454 2455.. _visibility: 2456 2457Visibility of Declarations 2458^^^^^^^^^^^^^^^^^^^^^^^^^^ 2459 2460During import of a global variable with external visibility, the lookup will 2461find variables (with the same name) but with static visibility (linkage). 2462Clearly, we cannot put them into the same redeclaration chain. The same is true 2463the in case of functions. Also, we have to take care of other kinds of 2464declarations like enums, classes, etc. if they are in anonymous namespaces. 2465Therefore, we filter the lookup results and consider only those which have the 2466same visibility as the declaration we currently import. 2467 2468We consider two declarations in two anonymous namespaces to have the same 2469visibility only if they are imported from the same AST context. 2470 2471Strategies to Handle Conflicting Names 2472^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2473 2474During the import we lookup existing declarations with the same name. We filter 2475the lookup results based on their :ref:`visibility <visibility>`. If any of the 2476found declarations are not structurally equivalent then we bumped to a name 2477conflict error (ODR violation in C++). In this case, we return with an 2478``Error`` and we set up the ``Error`` object for the declaration. However, some 2479clients of the ``ASTImporter`` may require a different, perhaps less 2480conservative and more liberal error handling strategy. 2481 2482E.g. static analysis clients may benefit if the node is created even if there 2483is a name conflict. During the CTU analysis of certain projects, we recognized 2484that there are global declarations which collide with declarations from other 2485translation units, but they are not referenced outside from their translation 2486unit. These declarations should be in an unnamed namespace ideally. If we treat 2487these collisions liberally then CTU analysis can find more results. Note, the 2488feature be able to choose between name conflict handling strategies is still an 2489ongoing work. 2490 2491.. _CFG: 2492 2493The ``CFG`` class 2494----------------- 2495 2496The ``CFG`` class is designed to represent a source-level control-flow graph 2497for a single statement (``Stmt*``). Typically instances of ``CFG`` are 2498constructed for function bodies (usually an instance of ``CompoundStmt``), but 2499can also be instantiated to represent the control-flow of any class that 2500subclasses ``Stmt``, which includes simple expressions. Control-flow graphs 2501are especially useful for performing `flow- or path-sensitive 2502<https://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities>`_ program 2503analyses on a given function. 2504 2505Basic Blocks 2506^^^^^^^^^^^^ 2507 2508Concretely, an instance of ``CFG`` is a collection of basic blocks. Each basic 2509block is an instance of ``CFGBlock``, which simply contains an ordered sequence 2510of ``Stmt*`` (each referring to statements in the AST). The ordering of 2511statements within a block indicates unconditional flow of control from one 2512statement to the next. :ref:`Conditional control-flow 2513<ConditionalControlFlow>` is represented using edges between basic blocks. The 2514statements within a given ``CFGBlock`` can be traversed using the 2515``CFGBlock::*iterator`` interface. 2516 2517A ``CFG`` object owns the instances of ``CFGBlock`` within the control-flow 2518graph it represents. Each ``CFGBlock`` within a CFG is also uniquely numbered 2519(accessible via ``CFGBlock::getBlockID()``). Currently the number is based on 2520the ordering the blocks were created, but no assumptions should be made on how 2521``CFGBlocks`` are numbered other than their numbers are unique and that they 2522are numbered from 0..N-1 (where N is the number of basic blocks in the CFG). 2523 2524Entry and Exit Blocks 2525^^^^^^^^^^^^^^^^^^^^^ 2526 2527Each instance of ``CFG`` contains two special blocks: an *entry* block 2528(accessible via ``CFG::getEntry()``), which has no incoming edges, and an 2529*exit* block (accessible via ``CFG::getExit()``), which has no outgoing edges. 2530Neither block contains any statements, and they serve the role of providing a 2531clear entrance and exit for a body of code such as a function body. The 2532presence of these empty blocks greatly simplifies the implementation of many 2533analyses built on top of CFGs. 2534 2535.. _ConditionalControlFlow: 2536 2537Conditional Control-Flow 2538^^^^^^^^^^^^^^^^^^^^^^^^ 2539 2540Conditional control-flow (such as those induced by if-statements and loops) is 2541represented as edges between ``CFGBlocks``. Because different C language 2542constructs can induce control-flow, each ``CFGBlock`` also records an extra 2543``Stmt*`` that represents the *terminator* of the block. A terminator is 2544simply the statement that caused the control-flow, and is used to identify the 2545nature of the conditional control-flow between blocks. For example, in the 2546case of an if-statement, the terminator refers to the ``IfStmt`` object in the 2547AST that represented the given branch. 2548 2549To illustrate, consider the following code example: 2550 2551.. code-block:: c++ 2552 2553 int foo(int x) { 2554 x = x + 1; 2555 if (x > 2) 2556 x++; 2557 else { 2558 x += 2; 2559 x *= 2; 2560 } 2561 2562 return x; 2563 } 2564 2565After invoking the parser+semantic analyzer on this code fragment, the AST of 2566the body of ``foo`` is referenced by a single ``Stmt*``. We can then construct 2567an instance of ``CFG`` representing the control-flow graph of this function 2568body by single call to a static class method: 2569 2570.. code-block:: c++ 2571 2572 Stmt *FooBody = ... 2573 std::unique_ptr<CFG> FooCFG = CFG::buildCFG(FooBody); 2574 2575Along with providing an interface to iterate over its ``CFGBlocks``, the 2576``CFG`` class also provides methods that are useful for debugging and 2577visualizing CFGs. For example, the method ``CFG::dump()`` dumps a 2578pretty-printed version of the CFG to standard error. This is especially useful 2579when one is using a debugger such as gdb. For example, here is the output of 2580``FooCFG->dump()``: 2581 2582.. code-block:: text 2583 2584 [ B5 (ENTRY) ] 2585 Predecessors (0): 2586 Successors (1): B4 2587 2588 [ B4 ] 2589 1: x = x + 1 2590 2: (x > 2) 2591 T: if [B4.2] 2592 Predecessors (1): B5 2593 Successors (2): B3 B2 2594 2595 [ B3 ] 2596 1: x++ 2597 Predecessors (1): B4 2598 Successors (1): B1 2599 2600 [ B2 ] 2601 1: x += 2 2602 2: x *= 2 2603 Predecessors (1): B4 2604 Successors (1): B1 2605 2606 [ B1 ] 2607 1: return x; 2608 Predecessors (2): B2 B3 2609 Successors (1): B0 2610 2611 [ B0 (EXIT) ] 2612 Predecessors (1): B1 2613 Successors (0): 2614 2615For each block, the pretty-printed output displays for each block the number of 2616*predecessor* blocks (blocks that have outgoing control-flow to the given 2617block) and *successor* blocks (blocks that have control-flow that have incoming 2618control-flow from the given block). We can also clearly see the special entry 2619and exit blocks at the beginning and end of the pretty-printed output. For the 2620entry block (block B5), the number of predecessor blocks is 0, while for the 2621exit block (block B0) the number of successor blocks is 0. 2622 2623The most interesting block here is B4, whose outgoing control-flow represents 2624the branching caused by the sole if-statement in ``foo``. Of particular 2625interest is the second statement in the block, ``(x > 2)``, and the terminator, 2626printed as ``if [B4.2]``. The second statement represents the evaluation of 2627the condition of the if-statement, which occurs before the actual branching of 2628control-flow. Within the ``CFGBlock`` for B4, the ``Stmt*`` for the second 2629statement refers to the actual expression in the AST for ``(x > 2)``. Thus 2630pointers to subclasses of ``Expr`` can appear in the list of statements in a 2631block, and not just subclasses of ``Stmt`` that refer to proper C statements. 2632 2633The terminator of block B4 is a pointer to the ``IfStmt`` object in the AST. 2634The pretty-printer outputs ``if [B4.2]`` because the condition expression of 2635the if-statement has an actual place in the basic block, and thus the 2636terminator is essentially *referring* to the expression that is the second 2637statement of block B4 (i.e., B4.2). In this manner, conditions for 2638control-flow (which also includes conditions for loops and switch statements) 2639are hoisted into the actual basic block. 2640 2641.. Implicit Control-Flow 2642.. ^^^^^^^^^^^^^^^^^^^^^ 2643 2644.. A key design principle of the ``CFG`` class was to not require any 2645.. transformations to the AST in order to represent control-flow. Thus the 2646.. ``CFG`` does not perform any "lowering" of the statements in an AST: loops 2647.. are not transformed into guarded gotos, short-circuit operations are not 2648.. converted to a set of if-statements, and so on. 2649 2650Constant Folding in the Clang AST 2651--------------------------------- 2652 2653There are several places where constants and constant folding matter a lot to 2654the Clang front-end. First, in general, we prefer the AST to retain the source 2655code as close to how the user wrote it as possible. This means that if they 2656wrote "``5+4``", we want to keep the addition and two constants in the AST, we 2657don't want to fold to "``9``". This means that constant folding in various 2658ways turns into a tree walk that needs to handle the various cases. 2659 2660However, there are places in both C and C++ that require constants to be 2661folded. For example, the C standard defines what an "integer constant 2662expression" (i-c-e) is with very precise and specific requirements. The 2663language then requires i-c-e's in a lot of places (for example, the size of a 2664bitfield, the value for a case statement, etc). For these, we have to be able 2665to constant fold the constants, to do semantic checks (e.g., verify bitfield 2666size is non-negative and that case statements aren't duplicated). We aim for 2667Clang to be very pedantic about this, diagnosing cases when the code does not 2668use an i-c-e where one is required, but accepting the code unless running with 2669``-pedantic-errors``. 2670 2671Things get a little bit more tricky when it comes to compatibility with 2672real-world source code. Specifically, GCC has historically accepted a huge 2673superset of expressions as i-c-e's, and a lot of real world code depends on 2674this unfortunate accident of history (including, e.g., the glibc system 2675headers). GCC accepts anything its "fold" optimizer is capable of reducing to 2676an integer constant, which means that the definition of what it accepts changes 2677as its optimizer does. One example is that GCC accepts things like "``case 2678X-X:``" even when ``X`` is a variable, because it can fold this to 0. 2679 2680Another issue are how constants interact with the extensions we support, such 2681as ``__builtin_constant_p``, ``__builtin_inf``, ``__extension__`` and many 2682others. C99 obviously does not specify the semantics of any of these 2683extensions, and the definition of i-c-e does not include them. However, these 2684extensions are often used in real code, and we have to have a way to reason 2685about them. 2686 2687Finally, this is not just a problem for semantic analysis. The code generator 2688and other clients have to be able to fold constants (e.g., to initialize global 2689variables) and have to handle a superset of what C99 allows. Further, these 2690clients can benefit from extended information. For example, we know that 2691"``foo() || 1``" always evaluates to ``true``, but we can't replace the 2692expression with ``true`` because it has side effects. 2693 2694Implementation Approach 2695^^^^^^^^^^^^^^^^^^^^^^^ 2696 2697After trying several different approaches, we've finally converged on a design 2698(Note, at the time of this writing, not all of this has been implemented, 2699consider this a design goal!). Our basic approach is to define a single 2700recursive evaluation method (``Expr::Evaluate``), which is implemented 2701in ``AST/ExprConstant.cpp``. Given an expression with "scalar" type (integer, 2702fp, complex, or pointer) this method returns the following information: 2703 2704* Whether the expression is an integer constant expression, a general constant 2705 that was folded but has no side effects, a general constant that was folded 2706 but that does have side effects, or an uncomputable/unfoldable value. 2707* If the expression was computable in any way, this method returns the 2708 ``APValue`` for the result of the expression. 2709* If the expression is not evaluatable at all, this method returns information 2710 on one of the problems with the expression. This includes a 2711 ``SourceLocation`` for where the problem is, and a diagnostic ID that explains 2712 the problem. The diagnostic should have ``ERROR`` type. 2713* If the expression is not an integer constant expression, this method returns 2714 information on one of the problems with the expression. This includes a 2715 ``SourceLocation`` for where the problem is, and a diagnostic ID that 2716 explains the problem. The diagnostic should have ``EXTENSION`` type. 2717 2718This information gives various clients the flexibility that they want, and we 2719will eventually have some helper methods for various extensions. For example, 2720``Sema`` should have a ``Sema::VerifyIntegerConstantExpression`` method, which 2721calls ``Evaluate`` on the expression. If the expression is not foldable, the 2722error is emitted, and it would return ``true``. If the expression is not an 2723i-c-e, the ``EXTENSION`` diagnostic is emitted. Finally it would return 2724``false`` to indicate that the AST is OK. 2725 2726Other clients can use the information in other ways, for example, codegen can 2727just use expressions that are foldable in any way. 2728 2729Extensions 2730^^^^^^^^^^ 2731 2732This section describes how some of the various extensions Clang supports 2733interacts with constant evaluation: 2734 2735* ``__extension__``: The expression form of this extension causes any 2736 evaluatable subexpression to be accepted as an integer constant expression. 2737* ``__builtin_constant_p``: This returns true (as an integer constant 2738 expression) if the operand evaluates to either a numeric value (that is, not 2739 a pointer cast to integral type) of integral, enumeration, floating or 2740 complex type, or if it evaluates to the address of the first character of a 2741 string literal (possibly cast to some other type). As a special case, if 2742 ``__builtin_constant_p`` is the (potentially parenthesized) condition of a 2743 conditional operator expression ("``?:``"), only the true side of the 2744 conditional operator is considered, and it is evaluated with full constant 2745 folding. 2746* ``__builtin_choose_expr``: The condition is required to be an integer 2747 constant expression, but we accept any constant as an "extension of an 2748 extension". This only evaluates one operand depending on which way the 2749 condition evaluates. 2750* ``__builtin_classify_type``: This always returns an integer constant 2751 expression. 2752* ``__builtin_inf, nan, ...``: These are treated just like a floating-point 2753 literal. 2754* ``__builtin_abs, copysign, ...``: These are constant folded as general 2755 constant expressions. 2756* ``__builtin_strlen`` and ``strlen``: These are constant folded as integer 2757 constant expressions if the argument is a string literal. 2758 2759.. _Sema: 2760 2761The Sema Library 2762================ 2763 2764This library is called by the :ref:`Parser library <Parser>` during parsing to 2765do semantic analysis of the input. For valid programs, Sema builds an AST for 2766parsed constructs. 2767 2768.. _CodeGen: 2769 2770The CodeGen Library 2771=================== 2772 2773CodeGen takes an :ref:`AST <AST>` as input and produces `LLVM IR code 2774<//llvm.org/docs/LangRef.html>`_ from it. 2775 2776How to change Clang 2777=================== 2778 2779How to add an attribute 2780----------------------- 2781Attributes are a form of metadata that can be attached to a program construct, 2782allowing the programmer to pass semantic information along to the compiler for 2783various uses. For example, attributes may be used to alter the code generation 2784for a program construct, or to provide extra semantic information for static 2785analysis. This document explains how to add a custom attribute to Clang. 2786Documentation on existing attributes can be found `here 2787<//clang.llvm.org/docs/AttributeReference.html>`_. 2788 2789Attribute Basics 2790^^^^^^^^^^^^^^^^ 2791Attributes in Clang are handled in three stages: parsing into a parsed attribute 2792representation, conversion from a parsed attribute into a semantic attribute, 2793and then the semantic handling of the attribute. 2794 2795Parsing of the attribute is determined by the various syntactic forms attributes 2796can take, such as GNU, C++11, and Microsoft style attributes, as well as other 2797information provided by the table definition of the attribute. Ultimately, the 2798parsed representation of an attribute object is an ``ParsedAttr`` object. 2799These parsed attributes chain together as a list of parsed attributes attached 2800to a declarator or declaration specifier. The parsing of attributes is handled 2801automatically by Clang, except for attributes spelled as keywords. When 2802implementing a keyword attribute, the parsing of the keyword and creation of the 2803``ParsedAttr`` object must be done manually. 2804 2805Eventually, ``Sema::ProcessDeclAttributeList()`` is called with a ``Decl`` and 2806a ``ParsedAttr``, at which point the parsed attribute can be transformed 2807into a semantic attribute. The process by which a parsed attribute is converted 2808into a semantic attribute depends on the attribute definition and semantic 2809requirements of the attribute. The end result, however, is that the semantic 2810attribute object is attached to the ``Decl`` object, and can be obtained by a 2811call to ``Decl::getAttr<T>()``. Similarly, for statement attributes, 2812``Sema::ProcessStmtAttributes()`` is called with a ``Stmt`` a list of 2813``ParsedAttr`` objects to be converted into a semantic attribute. 2814 2815The structure of the semantic attribute is also governed by the attribute 2816definition given in Attr.td. This definition is used to automatically generate 2817functionality used for the implementation of the attribute, such as a class 2818derived from ``clang::Attr``, information for the parser to use, automated 2819semantic checking for some attributes, etc. 2820 2821 2822``include/clang/Basic/Attr.td`` 2823^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2824The first step to adding a new attribute to Clang is to add its definition to 2825`include/clang/Basic/Attr.td 2826<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/Attr.td>`_. 2827This tablegen definition must derive from the ``Attr`` (tablegen, not 2828semantic) type, or one of its derivatives. Most attributes will derive from the 2829``InheritableAttr`` type, which specifies that the attribute can be inherited by 2830later redeclarations of the ``Decl`` it is associated with. 2831``InheritableParamAttr`` is similar to ``InheritableAttr``, except that the 2832attribute is written on a parameter instead of a declaration. If the attribute 2833applies to statements, it should inherit from ``StmtAttr``. If the attribute is 2834intended to apply to a type instead of a declaration, such an attribute should 2835derive from ``TypeAttr``, and will generally not be given an AST representation. 2836(Note that this document does not cover the creation of type attributes.) An 2837attribute that inherits from ``IgnoredAttr`` is parsed, but will generate an 2838ignored attribute diagnostic when used, which may be useful when an attribute is 2839supported by another vendor but not supported by clang. 2840 2841The definition will specify several key pieces of information, such as the 2842semantic name of the attribute, the spellings the attribute supports, the 2843arguments the attribute expects, and more. Most members of the ``Attr`` tablegen 2844type do not require definitions in the derived definition as the default 2845suffice. However, every attribute must specify at least a spelling list, a 2846subject list, and a documentation list. 2847 2848Spellings 2849~~~~~~~~~ 2850All attributes are required to specify a spelling list that denotes the ways in 2851which the attribute can be spelled. For instance, a single semantic attribute 2852may have a keyword spelling, as well as a C++11 spelling and a GNU spelling. An 2853empty spelling list is also permissible and may be useful for attributes which 2854are created implicitly. The following spellings are accepted: 2855 2856 ============ ================================================================ 2857 Spelling Description 2858 ============ ================================================================ 2859 ``GNU`` Spelled with a GNU-style ``__attribute__((attr))`` syntax and 2860 placement. 2861 ``CXX11`` Spelled with a C++-style ``[[attr]]`` syntax with an optional 2862 vendor-specific namespace. 2863 ``C2x`` Spelled with a C-style ``[[attr]]`` syntax with an optional 2864 vendor-specific namespace. 2865 ``Declspec`` Spelled with a Microsoft-style ``__declspec(attr)`` syntax. 2866 ``Keyword`` The attribute is spelled as a keyword, and required custom 2867 parsing. 2868 ``GCC`` Specifies two or three spellings: the first is a GNU-style 2869 spelling, the second is a C++-style spelling with the ``gnu`` 2870 namespace, and the third is an optional C-style spelling with 2871 the ``gnu`` namespace. Attributes should only specify this 2872 spelling for attributes supported by GCC. 2873 ``Clang`` Specifies two or three spellings: the first is a GNU-style 2874 spelling, the second is a C++-style spelling with the ``clang`` 2875 namespace, and the third is an optional C-style spelling with 2876 the ``clang`` namespace. By default, a C-style spelling is 2877 provided. 2878 ``Pragma`` The attribute is spelled as a ``#pragma``, and requires custom 2879 processing within the preprocessor. If the attribute is meant to 2880 be used by Clang, it should set the namespace to ``"clang"``. 2881 Note that this spelling is not used for declaration attributes. 2882 ============ ================================================================ 2883 2884Subjects 2885~~~~~~~~ 2886Attributes appertain to one or more subjects. If the attribute attempts to 2887attach to a subject that is not in the subject list, a diagnostic is issued 2888automatically. Whether the diagnostic is a warning or an error depends on how 2889the attribute's ``SubjectList`` is defined, but the default behavior is to warn. 2890The diagnostics displayed to the user are automatically determined based on the 2891subjects in the list, but a custom diagnostic parameter can also be specified in 2892the ``SubjectList``. The diagnostics generated for subject list violations are 2893calculated automatically or specified by the subject list itself. If a 2894previously unused Decl node is added to the ``SubjectList``, the logic used to 2895automatically determine the diagnostic parameter in `utils/TableGen/ClangAttrEmitter.cpp 2896<https://github.com/llvm/llvm-project/blob/main/clang/utils/TableGen/ClangAttrEmitter.cpp>`_ 2897may need to be updated. 2898 2899By default, all subjects in the SubjectList must either be a Decl node defined 2900in ``DeclNodes.td``, or a statement node defined in ``StmtNodes.td``. However, 2901more complex subjects can be created by creating a ``SubsetSubject`` object. 2902Each such object has a base subject which it appertains to (which must be a 2903Decl or Stmt node, and not a SubsetSubject node), and some custom code which is 2904called when determining whether an attribute appertains to the subject. For 2905instance, a ``NonBitField`` SubsetSubject appertains to a ``FieldDecl``, and 2906tests whether the given FieldDecl is a bit field. When a SubsetSubject is 2907specified in a SubjectList, a custom diagnostic parameter must also be provided. 2908 2909Diagnostic checking for attribute subject lists for declaration and statement 2910attributes is automated except when ``HasCustomParsing`` is set to ``1``. 2911 2912Documentation 2913~~~~~~~~~~~~~ 2914All attributes must have some form of documentation associated with them. 2915Documentation is table generated on the public web server by a server-side 2916process that runs daily. Generally, the documentation for an attribute is a 2917stand-alone definition in `include/clang/Basic/AttrDocs.td 2918<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/AttrDocs.td>`_ 2919that is named after the attribute being documented. 2920 2921If the attribute is not for public consumption, or is an implicitly-created 2922attribute that has no visible spelling, the documentation list can specify the 2923``Undocumented`` object. Otherwise, the attribute should have its documentation 2924added to AttrDocs.td. 2925 2926Documentation derives from the ``Documentation`` tablegen type. All derived 2927types must specify a documentation category and the actual documentation itself. 2928Additionally, it can specify a custom heading for the attribute, though a 2929default heading will be chosen when possible. 2930 2931There are four predefined documentation categories: ``DocCatFunction`` for 2932attributes that appertain to function-like subjects, ``DocCatVariable`` for 2933attributes that appertain to variable-like subjects, ``DocCatType`` for type 2934attributes, and ``DocCatStmt`` for statement attributes. A custom documentation 2935category should be used for groups of attributes with similar functionality. 2936Custom categories are good for providing overview information for the attributes 2937grouped under it. For instance, the consumed annotation attributes define a 2938custom category, ``DocCatConsumed``, that explains what consumed annotations are 2939at a high level. 2940 2941Documentation content (whether it is for an attribute or a category) is written 2942using reStructuredText (RST) syntax. 2943 2944After writing the documentation for the attribute, it should be locally tested 2945to ensure that there are no issues generating the documentation on the server. 2946Local testing requires a fresh build of clang-tblgen. To generate the attribute 2947documentation, execute the following command:: 2948 2949 clang-tblgen -gen-attr-docs -I /path/to/clang/include /path/to/clang/include/clang/Basic/Attr.td -o /path/to/clang/docs/AttributeReference.rst 2950 2951When testing locally, *do not* commit changes to ``AttributeReference.rst``. 2952This file is generated by the server automatically, and any changes made to this 2953file will be overwritten. 2954 2955Arguments 2956~~~~~~~~~ 2957Attributes may optionally specify a list of arguments that can be passed to the 2958attribute. Attribute arguments specify both the parsed form and the semantic 2959form of the attribute. For example, if ``Args`` is 2960``[StringArgument<"Arg1">, IntArgument<"Arg2">]`` then 2961``__attribute__((myattribute("Hello", 3)))`` will be a valid use; it requires 2962two arguments while parsing, and the Attr subclass' constructor for the 2963semantic attribute will require a string and integer argument. 2964 2965All arguments have a name and a flag that specifies whether the argument is 2966optional. The associated C++ type of the argument is determined by the argument 2967definition type. If the existing argument types are insufficient, new types can 2968be created, but it requires modifying `utils/TableGen/ClangAttrEmitter.cpp 2969<https://github.com/llvm/llvm-project/blob/main/clang/utils/TableGen/ClangAttrEmitter.cpp>`_ 2970to properly support the type. 2971 2972Other Properties 2973~~~~~~~~~~~~~~~~ 2974The ``Attr`` definition has other members which control the behavior of the 2975attribute. Many of them are special-purpose and beyond the scope of this 2976document, however a few deserve mention. 2977 2978If the parsed form of the attribute is more complex, or differs from the 2979semantic form, the ``HasCustomParsing`` bit can be set to ``1`` for the class, 2980and the parsing code in `Parser::ParseGNUAttributeArgs() 2981<https://github.com/llvm/llvm-project/blob/main/clang/lib/Parse/ParseDecl.cpp>`_ 2982can be updated for the special case. Note that this only applies to arguments 2983with a GNU spelling -- attributes with a __declspec spelling currently ignore 2984this flag and are handled by ``Parser::ParseMicrosoftDeclSpec``. 2985 2986Note that setting this member to 1 will opt out of common attribute semantic 2987handling, requiring extra implementation efforts to ensure the attribute 2988appertains to the appropriate subject, etc. 2989 2990If the attribute should not be propagated from a template declaration to an 2991instantiation of the template, set the ``Clone`` member to 0. By default, all 2992attributes will be cloned to template instantiations. 2993 2994Attributes that do not require an AST node should set the ``ASTNode`` field to 2995``0`` to avoid polluting the AST. Note that anything inheriting from 2996``TypeAttr`` or ``IgnoredAttr`` automatically do not generate an AST node. All 2997other attributes generate an AST node by default. The AST node is the semantic 2998representation of the attribute. 2999 3000The ``LangOpts`` field specifies a list of language options required by the 3001attribute. For instance, all of the CUDA-specific attributes specify ``[CUDA]`` 3002for the ``LangOpts`` field, and when the CUDA language option is not enabled, an 3003"attribute ignored" warning diagnostic is emitted. Since language options are 3004not table generated nodes, new language options must be created manually and 3005should specify the spelling used by ``LangOptions`` class. 3006 3007Custom accessors can be generated for an attribute based on the spelling list 3008for that attribute. For instance, if an attribute has two different spellings: 3009'Foo' and 'Bar', accessors can be created: 3010``[Accessor<"isFoo", [GNU<"Foo">]>, Accessor<"isBar", [GNU<"Bar">]>]`` 3011These accessors will be generated on the semantic form of the attribute, 3012accepting no arguments and returning a ``bool``. 3013 3014Attributes that do not require custom semantic handling should set the 3015``SemaHandler`` field to ``0``. Note that anything inheriting from 3016``IgnoredAttr`` automatically do not get a semantic handler. All other 3017attributes are assumed to use a semantic handler by default. Attributes 3018without a semantic handler are not given a parsed attribute ``Kind`` enumerator. 3019 3020"Simple" attributes, that require no custom semantic processing aside from what 3021is automatically provided, should set the ``SimpleHandler`` field to ``1``. 3022 3023Target-specific attributes may share a spelling with other attributes in 3024different targets. For instance, the ARM and MSP430 targets both have an 3025attribute spelled ``GNU<"interrupt">``, but with different parsing and semantic 3026requirements. To support this feature, an attribute inheriting from 3027``TargetSpecificAttribute`` may specify a ``ParseKind`` field. This field 3028should be the same value between all arguments sharing a spelling, and 3029corresponds to the parsed attribute's ``Kind`` enumerator. This allows 3030attributes to share a parsed attribute kind, but have distinct semantic 3031attribute classes. For instance, ``ParsedAttr`` is the shared 3032parsed attribute kind, but ARMInterruptAttr and MSP430InterruptAttr are the 3033semantic attributes generated. 3034 3035By default, attribute arguments are parsed in an evaluated context. If the 3036arguments for an attribute should be parsed in an unevaluated context (akin to 3037the way the argument to a ``sizeof`` expression is parsed), set 3038``ParseArgumentsAsUnevaluated`` to ``1``. 3039 3040If additional functionality is desired for the semantic form of the attribute, 3041the ``AdditionalMembers`` field specifies code to be copied verbatim into the 3042semantic attribute class object, with ``public`` access. 3043 3044If two or more attributes cannot be used in combination on the same declaration 3045or statement, a ``MutualExclusions`` definition can be supplied to automatically 3046generate diagnostic code. This will disallow the attribute combinations 3047regardless of spellings used. Additionally, it will diagnose combinations within 3048the same attribute list, different attribute list, and redeclarations, as 3049appropriate. 3050 3051Boilerplate 3052^^^^^^^^^^^ 3053All semantic processing of declaration attributes happens in `lib/Sema/SemaDeclAttr.cpp 3054<https://github.com/llvm/llvm-project/blob/main/clang/lib/Sema/SemaDeclAttr.cpp>`_, 3055and generally starts in the ``ProcessDeclAttribute()`` function. If the 3056attribute has the ``SimpleHandler`` field set to ``1`` then the function to 3057process the attribute will be automatically generated, and nothing needs to be 3058done here. Otherwise, write a new ``handleYourAttr()`` function, and add that to 3059the switch statement. Please do not implement handling logic directly in the 3060``case`` for the attribute. 3061 3062Unless otherwise specified by the attribute definition, common semantic checking 3063of the parsed attribute is handled automatically. This includes diagnosing 3064parsed attributes that do not appertain to the given ``Decl`` or ``Stmt``, 3065ensuring the correct minimum number of arguments are passed, etc. 3066 3067If the attribute adds additional warnings, define a ``DiagGroup`` in 3068`include/clang/Basic/DiagnosticGroups.td 3069<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/DiagnosticGroups.td>`_ 3070named after the attribute's ``Spelling`` with "_"s replaced by "-"s. If there 3071is only a single diagnostic, it is permissible to use ``InGroup<DiagGroup<"your-attribute">>`` 3072directly in `DiagnosticSemaKinds.td 3073<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/DiagnosticSemaKinds.td>`_ 3074 3075All semantic diagnostics generated for your attribute, including automatically- 3076generated ones (such as subjects and argument counts), should have a 3077corresponding test case. 3078 3079Semantic handling 3080^^^^^^^^^^^^^^^^^ 3081Most attributes are implemented to have some effect on the compiler. For 3082instance, to modify the way code is generated, or to add extra semantic checks 3083for an analysis pass, etc. Having added the attribute definition and conversion 3084to the semantic representation for the attribute, what remains is to implement 3085the custom logic requiring use of the attribute. 3086 3087The ``clang::Decl`` object can be queried for the presence or absence of an 3088attribute using ``hasAttr<T>()``. To obtain a pointer to the semantic 3089representation of the attribute, ``getAttr<T>`` may be used. 3090 3091The ``clang::AttributedStmt`` object can be queried for the presence or absence 3092of an attribute by calling ``getAttrs()`` and looping over the list of 3093attributes. 3094 3095How to add an expression or statement 3096------------------------------------- 3097 3098Expressions and statements are one of the most fundamental constructs within a 3099compiler, because they interact with many different parts of the AST, semantic 3100analysis, and IR generation. Therefore, adding a new expression or statement 3101kind into Clang requires some care. The following list details the various 3102places in Clang where an expression or statement needs to be introduced, along 3103with patterns to follow to ensure that the new expression or statement works 3104well across all of the C languages. We focus on expressions, but statements 3105are similar. 3106 3107#. Introduce parsing actions into the parser. Recursive-descent parsing is 3108 mostly self-explanatory, but there are a few things that are worth keeping 3109 in mind: 3110 3111 * Keep as much source location information as possible! You'll want it later 3112 to produce great diagnostics and support Clang's various features that map 3113 between source code and the AST. 3114 * Write tests for all of the "bad" parsing cases, to make sure your recovery 3115 is good. If you have matched delimiters (e.g., parentheses, square 3116 brackets, etc.), use ``Parser::BalancedDelimiterTracker`` to give nice 3117 diagnostics when things go wrong. 3118 3119#. Introduce semantic analysis actions into ``Sema``. Semantic analysis should 3120 always involve two functions: an ``ActOnXXX`` function that will be called 3121 directly from the parser, and a ``BuildXXX`` function that performs the 3122 actual semantic analysis and will (eventually!) build the AST node. It's 3123 fairly common for the ``ActOnCXX`` function to do very little (often just 3124 some minor translation from the parser's representation to ``Sema``'s 3125 representation of the same thing), but the separation is still important: 3126 C++ template instantiation, for example, should always call the ``BuildXXX`` 3127 variant. Several notes on semantic analysis before we get into construction 3128 of the AST: 3129 3130 * Your expression probably involves some types and some subexpressions. 3131 Make sure to fully check that those types, and the types of those 3132 subexpressions, meet your expectations. Add implicit conversions where 3133 necessary to make sure that all of the types line up exactly the way you 3134 want them. Write extensive tests to check that you're getting good 3135 diagnostics for mistakes and that you can use various forms of 3136 subexpressions with your expression. 3137 * When type-checking a type or subexpression, make sure to first check 3138 whether the type is "dependent" (``Type::isDependentType()``) or whether a 3139 subexpression is type-dependent (``Expr::isTypeDependent()``). If any of 3140 these return ``true``, then you're inside a template and you can't do much 3141 type-checking now. That's normal, and your AST node (when you get there) 3142 will have to deal with this case. At this point, you can write tests that 3143 use your expression within templates, but don't try to instantiate the 3144 templates. 3145 * For each subexpression, be sure to call ``Sema::CheckPlaceholderExpr()`` 3146 to deal with "weird" expressions that don't behave well as subexpressions. 3147 Then, determine whether you need to perform lvalue-to-rvalue conversions 3148 (``Sema::DefaultLvalueConversions``) or the usual unary conversions 3149 (``Sema::UsualUnaryConversions``), for places where the subexpression is 3150 producing a value you intend to use. 3151 * Your ``BuildXXX`` function will probably just return ``ExprError()`` at 3152 this point, since you don't have an AST. That's perfectly fine, and 3153 shouldn't impact your testing. 3154 3155#. Introduce an AST node for your new expression. This starts with declaring 3156 the node in ``include/Basic/StmtNodes.td`` and creating a new class for your 3157 expression in the appropriate ``include/AST/Expr*.h`` header. It's best to 3158 look at the class for a similar expression to get ideas, and there are some 3159 specific things to watch for: 3160 3161 * If you need to allocate memory, use the ``ASTContext`` allocator to 3162 allocate memory. Never use raw ``malloc`` or ``new``, and never hold any 3163 resources in an AST node, because the destructor of an AST node is never 3164 called. 3165 * Make sure that ``getSourceRange()`` covers the exact source range of your 3166 expression. This is needed for diagnostics and for IDE support. 3167 * Make sure that ``children()`` visits all of the subexpressions. This is 3168 important for a number of features (e.g., IDE support, C++ variadic 3169 templates). If you have sub-types, you'll also need to visit those 3170 sub-types in ``RecursiveASTVisitor``. 3171 * Add printing support (``StmtPrinter.cpp``) for your expression. 3172 * Add profiling support (``StmtProfile.cpp``) for your AST node, noting the 3173 distinguishing (non-source location) characteristics of an instance of 3174 your expression. Omitting this step will lead to hard-to-diagnose 3175 failures regarding matching of template declarations. 3176 * Add serialization support (``ASTReaderStmt.cpp``, ``ASTWriterStmt.cpp``) 3177 for your AST node. 3178 3179#. Teach semantic analysis to build your AST node. At this point, you can wire 3180 up your ``Sema::BuildXXX`` function to actually create your AST. A few 3181 things to check at this point: 3182 3183 * If your expression can construct a new C++ class or return a new 3184 Objective-C object, be sure to update and then call 3185 ``Sema::MaybeBindToTemporary`` for your just-created AST node to be sure 3186 that the object gets properly destructed. An easy way to test this is to 3187 return a C++ class with a private destructor: semantic analysis should 3188 flag an error here with the attempt to call the destructor. 3189 * Inspect the generated AST by printing it using ``clang -cc1 -ast-print``, 3190 to make sure you're capturing all of the important information about how 3191 the AST was written. 3192 * Inspect the generated AST under ``clang -cc1 -ast-dump`` to verify that 3193 all of the types in the generated AST line up the way you want them. 3194 Remember that clients of the AST should never have to "think" to 3195 understand what's going on. For example, all implicit conversions should 3196 show up explicitly in the AST. 3197 * Write tests that use your expression as a subexpression of other, 3198 well-known expressions. Can you call a function using your expression as 3199 an argument? Can you use the ternary operator? 3200 3201#. Teach code generation to create IR to your AST node. This step is the first 3202 (and only) that requires knowledge of LLVM IR. There are several things to 3203 keep in mind: 3204 3205 * Code generation is separated into scalar/aggregate/complex and 3206 lvalue/rvalue paths, depending on what kind of result your expression 3207 produces. On occasion, this requires some careful factoring of code to 3208 avoid duplication. 3209 * ``CodeGenFunction`` contains functions ``ConvertType`` and 3210 ``ConvertTypeForMem`` that convert Clang's types (``clang::Type*`` or 3211 ``clang::QualType``) to LLVM types. Use the former for values, and the 3212 latter for memory locations: test with the C++ "``bool``" type to check 3213 this. If you find that you are having to use LLVM bitcasts to make the 3214 subexpressions of your expression have the type that your expression 3215 expects, STOP! Go fix semantic analysis and the AST so that you don't 3216 need these bitcasts. 3217 * The ``CodeGenFunction`` class has a number of helper functions to make 3218 certain operations easy, such as generating code to produce an lvalue or 3219 an rvalue, or to initialize a memory location with a given value. Prefer 3220 to use these functions rather than directly writing loads and stores, 3221 because these functions take care of some of the tricky details for you 3222 (e.g., for exceptions). 3223 * If your expression requires some special behavior in the event of an 3224 exception, look at the ``push*Cleanup`` functions in ``CodeGenFunction`` 3225 to introduce a cleanup. You shouldn't have to deal with 3226 exception-handling directly. 3227 * Testing is extremely important in IR generation. Use ``clang -cc1 3228 -emit-llvm`` and `FileCheck 3229 <https://llvm.org/docs/CommandGuide/FileCheck.html>`_ to verify that you're 3230 generating the right IR. 3231 3232#. Teach template instantiation how to cope with your AST node, which requires 3233 some fairly simple code: 3234 3235 * Make sure that your expression's constructor properly computes the flags 3236 for type dependence (i.e., the type your expression produces can change 3237 from one instantiation to the next), value dependence (i.e., the constant 3238 value your expression produces can change from one instantiation to the 3239 next), instantiation dependence (i.e., a template parameter occurs 3240 anywhere in your expression), and whether your expression contains a 3241 parameter pack (for variadic templates). Often, computing these flags 3242 just means combining the results from the various types and 3243 subexpressions. 3244 * Add ``TransformXXX`` and ``RebuildXXX`` functions to the ``TreeTransform`` 3245 class template in ``Sema``. ``TransformXXX`` should (recursively) 3246 transform all of the subexpressions and types within your expression, 3247 using ``getDerived().TransformYYY``. If all of the subexpressions and 3248 types transform without error, it will then call the ``RebuildXXX`` 3249 function, which will in turn call ``getSema().BuildXXX`` to perform 3250 semantic analysis and build your expression. 3251 * To test template instantiation, take those tests you wrote to make sure 3252 that you were type checking with type-dependent expressions and dependent 3253 types (from step #2) and instantiate those templates with various types, 3254 some of which type-check and some that don't, and test the error messages 3255 in each case. 3256 3257#. There are some "extras" that make other features work better. It's worth 3258 handling these extras to give your expression complete integration into 3259 Clang: 3260 3261 * Add code completion support for your expression in 3262 ``SemaCodeComplete.cpp``. 3263 * If your expression has types in it, or has any "interesting" features 3264 other than subexpressions, extend libclang's ``CursorVisitor`` to provide 3265 proper visitation for your expression, enabling various IDE features such 3266 as syntax highlighting, cross-referencing, and so on. The 3267 ``c-index-test`` helper program can be used to test these features. 3268 3269