brintos / llvm-project-archived public Read only

1============================2"Clang" CFE Internals Manual3============================4 5.. contents::6   :local:7 8Introduction9============10 11This document describes some of the more important APIs and internal design12decisions made in the Clang C front-end.  The purpose of this document is to13both capture some of this high-level information and also describe some of the14design decisions behind it.  This is meant for people interested in hacking on15Clang, 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 Library19====================20 21The LLVM ``libSupport`` library provides many underlying libraries and22`data-structures <https://llvm.org/docs/ProgrammersManual.html>`_, including23command line option processing, various containers, and a system abstraction24layer, which is used for file system access.25 26The Clang "Basic" Library27=========================28 29This library certainly needs a better name.  The "basic" library contains a30number 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 languages36(``SourceLocation``, ``SourceManager``, ``Diagnostics``, ``FileManager``).37When and if there is future demand, we can figure out if it makes sense to38introduce a new library, move the general classes somewhere else, or introduce39some other solution.40 41We describe the roles of these classes in order of their dependencies.42 43The Diagnostics Subsystem44-------------------------45 46The Clang Diagnostics subsystem is an important part of how the compiler47communicates with the human.  Diagnostics are the warnings and errors produced48when the code is incorrect or dubious.  In Clang, each diagnostic produced has49(at the minimum) a unique ID, an English translation associated with it, a50:ref:`SourceLocation <SourceLocation>` to "put the caret", and a severity51(e.g., ``WARNING`` or ``ERROR``).  They can also optionally include a number of52arguments to the diagnostic (which fill in "%0"'s in the string) as well as a53number of source ranges that related to the diagnostic.54 55In this section, we'll be giving examples produced by the Clang command line56driver, but diagnostics can be :ref:`rendered in many different ways57<DiagnosticConsumer>` depending on how the ``DiagnosticConsumer`` interface is58implemented.  A representative example of a diagnostic is:59 60.. code-block:: text61 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), you67can see the source location (the caret ("``^``") and file/line/column info),68the source ranges "``~~~~``", arguments to the diagnostic ("``int*``" and69"``_Complex float``").  You'll have to believe me that there is a unique ID70backing the diagnostic :).71 72Getting all of this to happen has several steps and involves many moving73pieces, this section describes them and talks about best practices when adding74a new diagnostic.75 76The ``Diagnostic*Kinds.td`` files77^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^78 79Diagnostics are created by adding an entry to one of the80``clang/Basic/Diagnostic*Kinds.td`` files, depending on what library will be81using it.  From this file, :program:`tblgen` generates the unique ID of the82diagnostic, the severity of the diagnostic and the English translation + format83string.84 85There is little sanity with the naming of the unique ID's right now.  Some86start with ``err_``, ``warn_``, ``ext_`` to encode the severity into the name.87Since the enum is referenced in the C++ code that produces the diagnostic, it88is 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 for93diagnostics 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 the96language that Clang accepts.  This means that Clang fully understands and can97represent them in the AST, but we produce diagnostics to tell the user their98code is non-portable.  The difference is that the former are ignored by99default, and the latter warn by default.  The ``WARNING`` severity is used for100constructs that are valid in the currently selected source language but that101are dubious in some way.  The ``REMARK`` severity provides generic information102about the compilation that is not necessarily related to any dubious code.  The103``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``}) of107output108*levels* by the diagnostics subsystem based on various configuration options.109Clang internally supports a fully fine-grained mapping mechanism that allows110you to map almost any diagnostic to the output level that you want.  The only111diagnostics that cannot be mapped are ``NOTE``\ s, which always follow the112severity of the previously emitted diagnostic and ``ERROR``\ s, which can only113be mapped to ``Fatal`` (it is not possible to turn an error into a warning, for114example).115 116Diagnostic mappings are used in many ways.  For example, if the user specifies117``-pedantic``, ``EXTENSION`` maps to ``Warning``, if they specify118``-pedantic-errors``, it turns into ``Error``.  This is used to implement119options like ``-Wunused_macros``, ``-Wundef``, etc.120 121Mapping to ``Fatal`` should only be used for diagnostics that are considered so122severe that error recovery won't be able to recover sensibly from them (thus123spewing a ton of bogus errors).  One example of this class of error is failure124to ``#include`` a file.125 126Diagnostic Wording127^^^^^^^^^^^^^^^^^^128The wording used for a diagnostic is critical because it is the only way for a129user to know how to correct their code. Use the following suggestions when130wording a diagnostic:131 132* Diagnostics in Clang do not start with a capital letter and do not end with133  punctuation.134 135    * This does not apply to proper nouns like ``Clang`` or ``OpenMP``, to136      acronyms like ``GCC`` or ``ARC``, or to language standards like ``C23``137      or ``C++17``.138    * A trailing question mark is allowed. e.g., ``unknown identifier %0; did139      you mean %1?``.140 141* Appropriately capitalize proper nouns like ``Clang``, ``OpenCL``, ``GCC``,142  ``Objective-C``, etc. and language standard versions like ``C11`` or ``C++11``.143* The wording should be succinct. If necessary, use a semicolon to combine144  sentence fragments instead of using complete sentences. e.g., prefer wording145  like ``'%0' is deprecated; it will be removed in a future release of Clang``146  over wording like ``'%0' is deprecated. It will be removed in a future release147  of Clang``.148* The wording should be actionable and avoid using standards terms or grammar149  productions that a new user would not be familiar with. e.g., prefer wording150  like ``missing semicolon`` over wording like ``syntax error`` (which is not151  actionable) or ``expected unqualified-id`` (which uses standards terminology).152* The wording should clearly explain what is wrong with the code rather than153  restating what the code does. e.g., prefer wording like ``type %0 requires a154  value in the range %1 to %2`` over wording like ``%0 is invalid``.155* The wording should have enough contextual information to help the user156  identify the issue in a complex expression. e.g., prefer wording like157  ``both sides of the %0 binary operator are identical`` over wording like158  ``identical operands to binary operator``.159* Use single quotes to denote syntactic constructs or command line arguments160  named in a diagnostic message. e.g., prefer wording like ``'this' pointer161  cannot be null in well-defined C++ code`` over wording like ``this pointer162  cannot be null in well-defined C++ code``.163* Prefer diagnostic wording without contractions whenever possible. The single164  quote in a contraction can be visually distracting due to its use with165  syntactic constructs, and contractions can be harder to understand for non-166  native English speakers.167 168The Format String169^^^^^^^^^^^^^^^^^170 171The format string for the diagnostic is very simple, but it has some power.  It172takes the form of a string in English with markers that indicate where and how173arguments to the diagnostic are inserted and formatted.  For example, here are174some simple format strings:175 176.. code-block:: c++177 178  "binary integer literals are an extension"179  "format string contains '\\0' within the string body"180  "more '%%' conversions than data arguments"181  "invalid operands to binary expression (%0 and %1)"182  "overloaded '%0' must be a %select{unary|binary|unary or binary}2 operator"183       " (has %1 parameter%s1)"184 185These examples show some important points of format strings.  You can use any186plain ASCII character in the diagnostic string except "``%``" without a187problem, but these are C strings, so you have to use and be aware of all the C188escape sequences (as in the second example).  If you want to produce a "``%``"189in the output, use the "``%%``" escape sequence, like the third diagnostic.190Finally, Clang uses the "``%...[digit]``" sequences to specify where and how191arguments to the diagnostic are formatted.192 193Arguments to the diagnostic are numbered according to how they are specified by194the C++ code that :ref:`produces them <internals-producing-diag>`, and are195referenced by ``%0`` .. ``%9``.  If you have more than 10 arguments to your196diagnostic, you are doing something wrong :).  Unlike ``printf``, there is no197requirement that arguments to the diagnostic end up in the output in the same198order as they are specified; you could have a format string with "``%1 %0``"199that swaps them, for example.  The text in between the percent and digit are200formatting instructions.  If there are no instructions, the argument is just201turned into a string and substituted in.202 203Here are some "best practices" for writing the English format string:204 205* Keep the string short.  It should ideally fit in the 80-column limit of the206  ``DiagnosticKinds.td`` file.  This avoids the diagnostic wrapping when207  printed, and forces you to think about the important point you are conveying208  with the diagnostic.209* Take advantage of location information.  The user will be able to see the210  line and location of the caret, so you don't need to tell them that the211  problem is with the 4th argument to the function: just point to it.212* Do not capitalize the diagnostic string, and do not end it with a period.213* If you need to quote something in the diagnostic string, use single quotes.214 215Diagnostics should never take random English strings as arguments: you216shouldn't use "``you have a problem with %0``" and pass in things like "``your217argument``" or "``your return value``" as arguments.  Doing this prevents218:ref:`translating <internals-diag-translation>` the Clang diagnostics to other219languages (because they'll get random English words in their otherwise220localized diagnostic).  The exceptions to this are C/C++ language keywords221(e.g., ``auto``, ``const``, ``mutable``, etc) and C/C++ operators (``/=``).222Note that things like "pointer" and "reference" are not keywords.  On the other223hand, you *can* include anything that comes from the user's source code,224including variable names, types, labels, etc.  The "``select``" format can be225used to achieve this sort of thing in a localizable way, see below.226 227Formatting a Diagnostic Argument228^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^229 230Arguments to diagnostics are fully typed internally and come from a couple of231different classes: integers, types, names, and random strings.  Depending on232the class of the argument, it can be optionally formatted in different ways.233This gives the ``DiagnosticConsumer`` information about what the argument means234without requiring it to use a specific presentation (consider this MVC for235Clang :).236 237It is really easy to add format specifiers to the Clang diagnostics system, but238they should be discussed before they are added.  If you are creating a lot of239repetitive diagnostics and/or have an idea for a useful formatter, please bring240it up on the cfe-dev mailing list.241 242Here are the different diagnostic argument formats currently supported by243Clang:244 245**"s" format**246 247Example:248  ``"requires %0 parameter%s0"``249Class:250  Integers251Description:252  This is a simple formatter for integers that is useful when producing English253  diagnostics.  When the integer is 1, it prints as nothing.  When the integer254  is not 1, it prints as "``s``".  This allows some simple grammatical forms to255  be to be handled correctly, and eliminates the need to use gross things like256  ``"requires %1 parameter(s)"``. Note, this only handles adding a simple257  "``s``" character, it will not handle situations where pluralization is more258  complicated such as turning ``fancy`` into ``fancies`` or ``mouse`` into259  ``mice``. You can use the "plural" format specifier to handle such situations.260 261**"select" format**262 263Example:264  ``"must be a %select{unary|binary|unary or binary}0 operator"``265Class:266  Integers267Description:268  This format specifier is used to merge multiple related diagnostics together269  into one common one, without requiring the difference to be specified as an270  English string argument.  Instead of specifying the string, the diagnostic271  gets an integer argument, and the format string selects the numbered option.272  In this case, the "``%0``" value must be an integer in the range [0..2].  If273  it is 0, it prints "unary", if it is 1 it prints "binary" if it is 2, it274  prints "unary or binary".  This allows other language translations to275  substitute reasonable words (or entire phrases) based on the semantics of the276  diagnostic instead of having to do things textually.  The selected string277  does undergo formatting.278 279**"enum_select" format**280 281Example:282  ``unknown frobbling of a %enum_select<FrobbleKind>{%VarDecl{variable declaration}|%FuncDecl{function declaration}}0 when blarging``283Class:284  Integers285Description:286  This format specifier is used exactly like a ``select`` specifier, except it287  additionally generates a namespace, enumeration, and enumerator list based on288  the format string given. In the above case, a namespace is generated named289  ``FrobbleKind`` that has an unscoped enumeration with the enumerators290  ``VarDecl`` and ``FuncDecl``, which correspond to the values 0 and 1. This291  permits a clearer use of the ``Diag`` in source code, as the above could be292  called as: ``Diag(Loc, diag::frobble) << diag::FrobbleKind::VarDecl``.293 294**"plural" format**295 296Example:297  ``"you have %0 %plural{1:mouse|:mice}0 connected to your computer"``298Class:299  Integers300Description:301  This is a formatter for complex plural forms. It is designed to handle even302  the requirements of languages with very complex plural forms, as many Baltic303  languages have.  The argument consists of a series of expression/form pairs,304  separated by ":", where the first form whose expression evaluates to true is305  the result of the modifier.306 307  An expression can be empty, in which case it is always true.  See the example308  at the top.  Otherwise, it is a series of one or more numeric conditions,309  separated by ",".  If any condition matches, the expression matches.  Each310  numeric condition can take one of three forms.311 312  * number: A simple decimal number matches if the argument is the same as the313    number.  Example: ``"%plural{1:mouse|:mice}0"``314  * range: A range in square brackets matches if the argument is within the315    range.  The range is inclusive on both ends.  Example:316    ``"%plural{0:none|1:one|[2,5]:some|:many}0"``317  * modulo: A modulo operator is followed by a number, and equals sign and318    either a number or a range.  The tests are the same as for plain numbers319    and ranges, but the argument is taken modulo the number first.  Example:320    ``"%plural{%100=0:even hundred|%100=[1,50]:lower half|:everything else}1"``321 322  The parser is very unforgiving.  A syntax error, even whitespace, will abort,323  as will a failure to match the argument against any expression.324 325**"ordinal" format**326 327Example:328  ``"ambiguity in %ordinal0 argument"``329Class:330  Integers331Description:332  This is a formatter which represents the argument number as an ordinal: the333  value ``1`` becomes ``1st``, ``3`` becomes ``3rd``, and so on.  Values less334  than ``1`` are not supported.  This formatter is currently hard-coded to use335  English ordinals.336 337**"human" format**338 339Example:340  ``"total size is %human0 bytes"``341Class:342  Integers343Description:344  This is a formatter which represents the argument number in a human-readable345  format: the value ``123`` stays ``123``, ``12345`` becomes ``12.34k``,346  ``6666666`` becomes ``6.67M``, and so on for 'G' and 'T'.347 348**"objcclass" format**349 350Example:351  ``"method %objcclass0 not found"``352Class:353  ``DeclarationName``354Description:355  This is a simple formatter that indicates the ``DeclarationName`` corresponds356  to an Objective-C class method selector.  As such, it prints the selector357  with a leading "``+``".358 359**"objcinstance" format**360 361Example:362  ``"method %objcinstance0 not found"``363Class:364  ``DeclarationName``365Description:366  This is a simple formatter that indicates the ``DeclarationName`` corresponds367  to an Objective-C instance method selector.  As such, it prints the selector368  with a leading "``-``".369 370**"q" format**371 372Example:373  ``"candidate found by name lookup is %q0"``374Class:375  ``NamedDecl *``376Description:377  This formatter indicates that the fully-qualified name of the declaration378  should be printed, e.g., "``std::vector``" rather than "``vector``".379 380**"diff" format**381 382Example:383  ``"no known conversion %diff{from $ to $|from argument type to parameter type}1,2"``384Class:385  ``QualType``386Description:387  This formatter takes two ``QualType``\ s and attempts to print a template388  difference between the two.  If tree printing is off, the text inside the389  braces before the pipe is printed, with the formatted text replacing the $.390  If tree printing is on, the text after the pipe is printed and a type tree is391  printed after the diagnostic message.392 393**"sub" format**394 395Example:396  Given the following record definition of type ``TextSubstitution``:397 398  .. code-block:: text399 400    def select_ovl_candidate : TextSubstitution<401      "%select{function|constructor}0%select{| template| %2}1">;402 403  which can be used as404 405  .. code-block:: text406 407    def note_ovl_candidate : Note<408      "candidate %sub{select_ovl_candidate}3,2,1 not viable">;409 410  and will act as if it were written411  ``"candidate %select{function|constructor}3%select{| template| %1}2 not viable"``.412Description:413  This format specifier is used to avoid repeating strings verbatim in multiple414  diagnostics. The argument to ``%sub`` must name a ``TextSubstitution`` tblgen415  record. The substitution must specify all arguments used by the substitution,416  and the modifier indexes in the substitution are re-numbered accordingly. The417  substituted text must itself be a valid format string before substitution.418 419**"quoted" format**420 421Example:422  ``"expression %quoted0 evaluates to 0"``423Class:424  ``String``425Description:426  This is a simple formatter which adds quotes around the given string.427  This is useful when the argument could be a string in some cases, but428  another class in other cases, and it needs to be quoted consistently.429 430.. _internals-producing-diag:431 432Producing the Diagnostic433^^^^^^^^^^^^^^^^^^^^^^^^434 435Now that you've created the diagnostic in the ``Diagnostic*Kinds.td`` file, you436need to write the code that detects the condition in question and emits the new437diagnostic.  Various components of Clang (e.g., the preprocessor, ``Sema``,438etc.) provide a helper function named "``Diag``".  It creates a diagnostic and439accepts the arguments, ranges, and other information that goes along with it.440 441For example, the binary expression error comes from code like this:442 443.. code-block:: c++444 445  if (various things that are bad)446    Diag(Loc, diag::err_typecheck_invalid_operands)447      << lex->getType() << rex->getType()448      << lex->getSourceRange() << rex->getSourceRange();449 450This shows the use of the ``Diag`` method: it takes a location (a451:ref:`SourceLocation <SourceLocation>` object) and a diagnostic enum value452(which matches the name from ``Diagnostic*Kinds.td``).  If the diagnostic takes453arguments, they are specified with the ``<<`` operator: the first argument454becomes ``%0``, the second becomes ``%1``, etc.  The diagnostic interface455allows you to specify arguments of many different types, including ``int`` and456``unsigned`` for integer arguments, ``const char*`` and ``std::string`` for457string arguments, ``DeclarationName`` and ``const IdentifierInfo *`` for names,458``QualType`` for types, etc.  ``SourceRange``\ s are also specified with the459``<<`` operator, but do not have a specific ordering requirement.460 461As you can see, adding and producing a diagnostic is pretty straightforward.462The hard part is deciding exactly what you need to say to help the user,463picking a suitable wording, and providing the information needed to format it464correctly.  The good news is that the call site that issues a diagnostic should465be completely independent of how the diagnostic is formatted and in what466language it is rendered.467 468Fix-It Hints469^^^^^^^^^^^^470 471In some cases, the front end emits diagnostics when it is clear that some small472change to the source code would fix the problem.  For example, a missing473semicolon at the end of a statement or a use of deprecated syntax that is474easily rewritten into a more modern form.  Clang tries very hard to emit the475diagnostic and recover gracefully in these and other cases.476 477However, for these cases where the fix is obvious, the diagnostic can be478annotated with a hint (referred to as a "fix-it hint") that describes how to479change the code referenced by the diagnostic to fix the problem.  For example,480it might add the missing semicolon at the end of the statement or rewrite the481use of a deprecated construct into something more palatable.  Here is one such482example from the C++ front end, where we warn about the right-shift operator483changing meaning from C++98 to C++11:484 485.. code-block:: text486 487  test.cpp:3:7: warning: use of right-shift operator ('>>') in template argument488                         will require parentheses in C++11489  A<100 >> 2> *a;490        ^491    (       )492 493Here, the fix-it hint is suggesting that parentheses be added, and showing494exactly where those parentheses would be inserted into the source code.  The495fix-it hints themselves describe what changes to make to the source code in an496abstract manner, which the text diagnostic printer renders as a line of497"insertions" below the caret line.  :ref:`Other diagnostic clients498<DiagnosticConsumer>` might choose to render the code differently (e.g., as499markup inline) or even give the user the ability to automatically fix the500problem.501 502Fix-it hints on errors and warnings need to obey these rules:503 504* Since they are automatically applied if ``-Xclang -fixit`` is passed to the505  driver, they should only be used when it's very likely they match the user's506  intent.507* Clang must recover from errors as if the fix-it had been applied.508* Fix-it hints on a warning must not change the meaning of the code.509  However, a hint may clarify the meaning as intentional, for example by adding510  parentheses when the precedence of operators isn't obvious.511 512If a fix-it can't obey these rules, put the fix-it on a note.  Fix-its on notes513are not applied automatically.514 515All fix-it hints are described by the ``FixItHint`` class, instances of which516should be attached to the diagnostic using the ``<<`` operator in the same way517that highlighted source ranges and arguments are passed to the diagnostic.518Fix-it hints can be created with one of three constructors:519 520* ``FixItHint::CreateInsertion(Loc, Code)``521 522    Specifies that the given ``Code`` (a string) should be inserted before the523    source location ``Loc``.524 525* ``FixItHint::CreateRemoval(Range)``526 527    Specifies that the code in the given source ``Range`` should be removed.528 529* ``FixItHint::CreateReplacement(Range, Code)``530 531    Specifies that the code in the given source ``Range`` should be removed,532    and replaced with the given ``Code`` string.533 534.. _DiagnosticConsumer:535 536The ``DiagnosticConsumer`` Interface537^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^538 539Once code generates a diagnostic with all of the arguments and the rest of the540relevant information, Clang needs to know what to do with it.  As previously541mentioned, the diagnostic machinery goes through some filtering to map a542severity onto a diagnostic level, then (assuming the diagnostic is not mapped543to "``Ignore``") it invokes an object that implements the ``DiagnosticConsumer``544interface with the information.545 546It is possible to implement this interface in many different ways.  For547example, the normal Clang ``DiagnosticConsumer`` (named548``TextDiagnosticPrinter``) turns the arguments into strings (according to the549various formatting rules), prints out the file/line/column information and the550string, then prints out the line of code, the source ranges, and the caret.551However, this behavior isn't required.552 553Another implementation of the ``DiagnosticConsumer`` interface is the554``TextDiagnosticBuffer`` class, which is used when Clang is in ``-verify``555mode.  Instead of formatting and printing out the diagnostics, this556implementation just captures and remembers the diagnostics as they fly by.557Then ``-verify`` compares the list of produced diagnostics to the list of558expected ones.  If they disagree, it prints out its own output.  Full559documentation for the ``-verify`` mode can be found at560:ref:`verifying-diagnostics`.561 562There are many other possible implementations of this interface, and this is563why we prefer diagnostics to pass down rich structured information in564arguments.  For example, an HTML output might want declaration names to be565linkified to where they come from in the source.  Another example is that a GUI566might let you click on typedefs to expand them.  This application would want to567pass significantly more information about types through to the GUI than a568simple flat string.  The interface allows this to happen.569 570.. _internals-diag-translation:571 572Adding Translations to Clang573^^^^^^^^^^^^^^^^^^^^^^^^^^^^574 575Not possible yet! Diagnostic strings should be written in UTF-8, the client can576translate to the relevant code page if needed.  Each translation completely577replaces the format string for the diagnostic.578 579.. _SourceLocation:580.. _SourceManager:581 582The ``SourceLocation`` and ``SourceManager`` classes583----------------------------------------------------584 585Strangely enough, the ``SourceLocation`` class represents a location within the586source code of the program.  Important design points include:587 588#. ``sizeof(SourceLocation)`` must be extremely small, as these are embedded589   into many AST nodes and are passed around often.  Currently, it is 32 bits.590#. ``SourceLocation`` must be a simple value object that can be efficiently591   copied.592#. We should be able to represent a source location for any byte of any input593   file.  This includes in the middle of tokens, in whitespace, in trigraphs,594   etc.595#. A ``SourceLocation`` must encode the current ``#include`` stack that was596   active when the location was processed.  For example, if the location597   corresponds to a token, it should contain the set of ``#include``\ s active598   when the token was lexed.  This allows us to print the ``#include`` stack599   for a diagnostic.600#. ``SourceLocation`` must be able to describe macro expansions, capturing both601   the ultimate instantiation point and the source of the original character602   data.603 604In practice, the ``SourceLocation`` works together with the ``SourceManager``605class to encode two pieces of information about a location: its spelling606location and its expansion location.  For most tokens, these will be the607same.  However, for a macro expansion (or tokens that came from a ``_Pragma``608directive), these will describe the location of the characters corresponding to609the token and the location where the token was used (i.e., the macro610expansion point or the location of the ``_Pragma`` itself).611 612The Clang front-end inherently depends on the location of a token being tracked613correctly.  If it is ever incorrect, the front-end may get confused and die.614The reason for this is that the notion of the "spelling" of a ``Token`` in615Clang depends on being able to find the original input characters for the616token.  This concept maps directly to the "spelling location" for the token.617 618``SourceRange`` and ``CharSourceRange``619---------------------------------------620 621.. mostly taken from https://discourse.llvm.org/t/code-ranges-of-tokens-ast-elements/16893/2622 623Clang represents most source ranges by [first, last], where "first" and "last"624each point to the beginning of their respective tokens.  For example, consider625the ``SourceRange`` of the following statement:626 627.. code-block:: text628 629  x = foo + bar;630  ^first    ^last631 632To map from this representation to a character-based representation, the "last"633location needs to be adjusted to point to (or past) the end of that token with634either ``Lexer::MeasureTokenLength()`` or ``Lexer::getLocForEndOfToken()``.  For635the rare cases where character-level source ranges information is needed, we use636the ``CharSourceRange`` class.637 638The Driver Library639==================640 641The clang Driver and library are documented :doc:`here <DriverInternals>`.642 643Precompiled Headers644===================645 646Clang supports precompiled headers (:doc:`PCH <PCHInternals>`), which  uses a647serialized representation of Clang's internal data structures, encoded with the648`LLVM bitstream format <https://llvm.org/docs/BitCodeFormat.html>`_.649 650The Frontend Library651====================652 653The Frontend library contains functionality useful for building tools on top of654the Clang libraries, including several methods for outputting diagnostics.655 656Compiler Invocation657-------------------658 659One of the classes provided by the Frontend library is ``CompilerInvocation``,660which holds information that describes the current invocation of the Clang ``-cc1``661frontend. The information typically comes from the command line constructed by662the Clang driver or from clients performing custom initialization. The data663structure is split into logical units used by different parts of the compiler,664for example, ``PreprocessorOptions``, ``LanguageOptions``, or ``CodeGenOptions``.665 666Command Line Interface667----------------------668 669The command line interface of the Clang ``-cc1`` frontend is defined alongside670the driver options in ``clang/Options/Options.td``. The information making up an671option definition includes its prefix and name (for example ``-std=``), form and672position of the option value, help text, aliases and more. Each option may673belong to a certain group and can be marked with zero or more flags. Options674accepted by the ``-cc1`` frontend are marked with the ``CC1Option`` flag.675 676Command Line Parsing677--------------------678 679Option definitions are processed by the ``-gen-opt-parser-defs`` tablegen680backend during early stages of the build. Options are then used for querying an681instance ``llvm::opt::ArgList``, a wrapper around the command line arguments.682This is done in the Clang driver to construct individual jobs based on the683driver arguments and also in the ``CompilerInvocation::CreateFromArgs`` function684that parses the ``-cc1`` frontend arguments.685 686Command Line Generation687-----------------------688 689Any valid ``CompilerInvocation`` created from a ``-cc1`` command line  can be690also serialized back into semantically equivalent command line in a691deterministic manner. This enables features such as implicitly discovered,692explicitly built modules.693 694..695  TODO: Create and link corresponding section in Modules.rst.696 697Adding new Command Line Option698------------------------------699 700When adding a new command line option, the first place of interest is the header701file declaring the corresponding options class (e.g., ``CodeGenOptions.h`` for702command line option that affects the code generation). Create new member703variable for the option value:704 705.. code-block:: diff706 707    class CodeGenOptions : public CodeGenOptionsBase {708 709  +   /// List of dynamic shared object files to be loaded as pass plugins.710  +   std::vector<std::string> PassPlugins;711 712    }713 714Next, declare the command line interface of the option in the tablegen file715``clang/include/clang/Options/Options.td``. This is done by instantiating the716``Option`` class (defined in ``llvm/include/llvm/Option/OptParser.td``). The717instance is typically created through one of the helper classes that encode the718acceptable ways to specify the option value on the command line:719 720* ``Flag`` - the option does not accept any value,721* ``Joined`` - the value must immediately follow the option name within the same722  argument,723* ``Separate`` - the value must follow the option name in the next command line724  argument,725* ``JoinedOrSeparate`` - the value can be specified either as ``Joined`` or726  ``Separate``,727* ``CommaJoined`` - the values are comma-separated and must immediately follow728  the option name within the same argument (see ``Wl,`` for an example).729 730The helper classes take a list of acceptable prefixes of the option (e.g.731``"-"``, ``"--"`` or ``"/"``) and the option name:732 733.. code-block:: diff734 735    // Options.td736 737  + def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">;738 739Then, specify additional attributes via mix-ins:740 741* ``HelpText`` holds the text that will be printed besides the option name when742  the user requests help (e.g., via ``clang --help``).743* ``Group`` specifies the "category" of options this option belongs to. This is744  used by various tools to categorize and sometimes filter options.745* ``Flags`` may contain "tags" associated with the option. These may affect how746  the option is rendered, or if it's hidden in some contexts.747* ``Visibility`` should be used to specify the drivers in which a particular748  option would be available. This attribute will impact tool --help749* ``Alias`` denotes that the option is an alias of another option. This may be750  combined with ``AliasArgs`` that holds the implied value.751 752.. code-block:: diff753 754    // Options.td755 756    def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">,757  +   Group<f_Group>, Visibility<[ClangOption, CC1Option]>,758  +   HelpText<"Load pass plugin from a dynamic shared object file.">;759 760New options are recognized by the ``clang`` driver mode if ``Visibility`` is761not specified or contains ``ClangOption``. Options intended for ``clang -cc1``762must be explicitly marked with the ``CC1Option`` flag. Flags that specify763``CC1Option`` but not ``ClangOption`` will only be accessible via ``-cc1``.764This is similar for other driver modes, such as ``clang-cl`` or ``flang``.765 766Next, parse (or manufacture) the command line arguments in the Clang driver and767use them to construct the ``-cc1`` job:768 769.. code-block:: diff770 771    void Clang::ConstructJob(const ArgList &Args /*...*/) const {772      ArgStringList CmdArgs;773      // ...774 775  +   for (const Arg *A : Args.filtered(OPT_fpass_plugin_EQ)) {776  +     CmdArgs.push_back(Args.MakeArgString(Twine("-fpass-plugin=") + A->getValue()));777  +     A->claim();778  +   }779    }780 781The last step is implementing the ``-cc1`` command line argument782parsing/generation that initializes/serializes the option class (in our case,783``CodeGenOptions``) stored within ``CompilerInvocation``. This can be done784automatically by using the marshalling annotations on the option definition:785 786.. code-block:: diff787 788    // Options.td789 790    def fpass_plugin_EQ : Joined<["-"], "fpass-plugin=">,791      Group<f_Group>, Flags<[CC1Option]>,792      HelpText<"Load pass plugin from a dynamic shared object file.">,793  +   MarshallingInfoStringVector<CodeGenOpts<"PassPlugins">>;794 795Inner workings of the system are introduced in the :ref:`marshalling796infrastructure <OptionMarshalling>` section and the available annotations are797listed :ref:`here <OptionMarshallingAnnotations>`.798 799In case the marshalling infrastructure does not support the desired semantics,800consider simplifying it to fit the existing model. This makes the command line801more uniform and reduces the amount of custom, manually written code. Remember802that the ``-cc1`` command line interface is intended only for Clang developers,803meaning it does not need to mirror the driver interface, maintain backward804compatibility or be compatible with GCC.805 806If the option semantics cannot be encoded via marshalling annotations, you can807resort to parsing/serializing the command line arguments manually:808 809.. code-block:: diff810 811    // CompilerInvocation.cpp812 813    static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args /*...*/) {814      // ...815 816  +   Opts.PassPlugins = Args.getAllArgValues(OPT_fpass_plugin_EQ);817    }818 819    static void GenerateCodeGenArgs(const CodeGenOptions &Opts,820                                    SmallVectorImpl<const char *> &Args,821                                    CompilerInvocation::StringAllocator SA /*...*/) {822      // ...823 824  +   for (const std::string &PassPlugin : Opts.PassPlugins)825  +     GenerateArg(Args, OPT_fpass_plugin_EQ, PassPlugin, SA);826    }827 828Finally, you can specify the argument on the command line:829``clang -fpass-plugin=a -fpass-plugin=b`` and use the new member variable as830desired.831 832.. code-block:: diff833 834    void EmitAssemblyHelper::EmitAssemblyWithNewPassManager(/*...*/) {835      // ...836  +   for (auto &PluginFN : CodeGenOpts.PassPlugins)837  +     if (auto PassPlugin = PassPlugin::Load(PluginFN))838  +        PassPlugin->registerPassBuilderCallbacks(PB);839    }840 841.. _OptionMarshalling:842 843Option Marshalling Infrastructure844---------------------------------845 846The option marshalling infrastructure automates the parsing of the Clang847``-cc1`` frontend command line arguments into ``CompilerInvocation`` and their848generation from ``CompilerInvocation``. The system replaces lots of repetitive849C++ code with simple, declarative tablegen annotations and is being used for850the majority of the ``-cc1`` command line interface. This section provides an851overview of the system.852 853**Note:** The marshalling infrastructure is not intended for driver-only854options. Only options of the ``-cc1`` frontend need to be marshalled to/from855``CompilerInvocation`` instance.856 857To read and modify contents of ``CompilerInvocation``, the marshalling system858uses key paths, which are declared in two steps. First, a tablegen definition859for the ``CompilerInvocation`` member is created by inheriting from860``KeyPathAndMacro``:861 862.. code-block:: text863 864  // Options.td865 866  class LangOpts<string field> : KeyPathAndMacro<"LangOpts->", field, "LANG_"> {}867  //                   CompilerInvocation member  ^^^^^^^^^^868  //                                    OPTION_WITH_MARSHALLING prefix ^^^^^869 870The first argument to the parent class is the beginning of the key path that871references the ``CompilerInvocation`` member. This argument ends with ``->`` if872the member is a pointer type or with ``.`` if it's a value type. The child class873takes a single parameter ``field`` that is forwarded as the second argument to874the base class. The child class can then be used like so:875``LangOpts<"IgnoreExceptions">``, constructing a key path to the field876``LangOpts->IgnoreExceptions``. The third argument passed to the parent class is877a string that the tablegen backend uses as a prefix to the878``OPTION_WITH_MARSHALLING`` macro. Using the key path as a mix-in on an879``Option`` instance instructs the backend to generate the following code:880 881.. code-block:: c++882 883  // Options.inc884 885  #ifdef LANG_OPTION_WITH_MARSHALLING886  LANG_OPTION_WITH_MARSHALLING([...], LangOpts->IgnoreExceptions, [...])887  #endif // LANG_OPTION_WITH_MARSHALLING888 889Such definition can be used in the function for parsing and generating890command line:891 892.. code-block:: c++893 894  // clang/lib/Frontend/CompilerInvoation.cpp895 896  bool CompilerInvocation::ParseLangArgs(LangOptions *LangOpts, ArgList &Args,897                                         DiagnosticsEngine &Diags) {898    bool Success = true;899 900  #define LANG_OPTION_WITH_MARSHALLING(                                          \901      PREFIX_TYPE, NAME, ID, KIND, GROUP, ALIAS, ALIASARGS, FLAGS, PARAM,        \902      HELPTEXT, METAVAR, VALUES, SPELLING, SHOULD_PARSE, ALWAYS_EMIT, KEYPATH,   \903      DEFAULT_VALUE, IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER, DENORMALIZER,     \904      MERGER, EXTRACTOR, TABLE_INDEX)                                            \905    PARSE_OPTION_WITH_MARSHALLING(Args, Diags, Success, ID, FLAGS, PARAM,        \906                                  SHOULD_PARSE, KEYPATH, DEFAULT_VALUE,          \907                                  IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER,      \908                                  MERGER, TABLE_INDEX)909  #include "clang/Options/Options.inc"910  #undef LANG_OPTION_WITH_MARSHALLING911 912    // ...913 914    return Success;915  }916 917  void CompilerInvocation::GenerateLangArgs(LangOptions *LangOpts,918                                            SmallVectorImpl<const char *> &Args,919                                            StringAllocator SA) {920  #define LANG_OPTION_WITH_MARSHALLING(                                          \921      PREFIX_TYPE, NAME, ID, KIND, GROUP, ALIAS, ALIASARGS, FLAGS, PARAM,        \922      HELPTEXT, METAVAR, VALUES, SPELLING, SHOULD_PARSE, ALWAYS_EMIT, KEYPATH,   \923      DEFAULT_VALUE, IMPLIED_CHECK, IMPLIED_VALUE, NORMALIZER, DENORMALIZER,     \924      MERGER, EXTRACTOR, TABLE_INDEX)                                            \925    GENERATE_OPTION_WITH_MARSHALLING(                                            \926        Args, SA, KIND, FLAGS, SPELLING, ALWAYS_EMIT, KEYPATH, DEFAULT_VALUE,    \927        IMPLIED_CHECK, IMPLIED_VALUE, DENORMALIZER, EXTRACTOR, TABLE_INDEX)928  #include "clang/Options/Options.inc"929  #undef LANG_OPTION_WITH_MARSHALLING930 931    // ...932  }933 934The ``PARSE_OPTION_WITH_MARSHALLING`` and ``GENERATE_OPTION_WITH_MARSHALLING``935macros are defined in ``CompilerInvocation.cpp`` and they implement the generic936algorithm for parsing and generating command line arguments.937 938.. _OptionMarshallingAnnotations:939 940Option Marshalling Annotations941------------------------------942 943How does the tablegen backend know what to put in place of ``[...]`` in the944generated ``Options.inc``? This is specified by the ``Marshalling`` utilities945described below. All of them take a key path argument and possibly other946information required for parsing or generating the command line argument.947 948**Note:** The marshalling infrastructure is not intended for driver-only949options. Only options of the ``-cc1`` frontend need to be marshalled to/from a950``CompilerInvocation`` instance.951 952**Positive Flag**953 954The key path defaults to ``false`` and is set to ``true`` when the flag is955present on the command line.956 957.. code-block:: text958 959  def fignore_exceptions : Flag<["-"], "fignore-exceptions">,960    Visibility<[ClangOption, CC1Option]>,961    MarshallingInfoFlag<LangOpts<"IgnoreExceptions">>;962 963**Negative Flag**964 965The key path defaults to ``true`` and is set to ``false`` when the flag is966present on the command line.967 968.. code-block:: text969 970  def fno_verbose_asm : Flag<["-"], "fno-verbose-asm">,971    Visibility<[ClangOption, CC1Option]>,972    MarshallingInfoNegativeFlag<CodeGenOpts<"AsmVerbose">>;973 974**Negative and Positive Flag**975 976The key path defaults to the specified value (``false``, ``true`` or some977boolean value that's statically unknown in the tablegen file). Then, the key978path is set to the value associated with the flag that appears last on command979line.980 981.. code-block:: text982 983  defm legacy_pass_manager : BoolOption<"f", "legacy-pass-manager",984    CodeGenOpts<"LegacyPassManager">, DefaultFalse,985    PosFlag<SetTrue, [], [], "Use the legacy pass manager in LLVM">,986    NegFlag<SetFalse, [], [], "Use the new pass manager in LLVM">,987    BothFlags<[], [ClangOption, CC1Option]>>;988 989With most such pairs of flags, the ``-cc1`` frontend accepts only the flag that990changes the default key path value. The Clang driver is responsible for991accepting both and either forwarding the changing flag or discarding the flag992that would just set the key path to its default.993 994The first argument to ``BoolOption`` is a prefix that is used to construct the995full names of both flags. The positive flag would then be named996``flegacy-pass-manager`` and the negative ``fno-legacy-pass-manager``.997``BoolOption`` also implies the ``-`` prefix for both flags. It's also possible998to use ``BoolFOption`` that implies the ``"f"`` prefix and ``Group<f_Group>``.999The ``PosFlag`` and ``NegFlag`` classes hold the associated boolean value,1000arrays of elements passed to the ``Flag`` and ``Visibility`` classes and the1001help text. The optional ``BothFlags`` class holds arrays of ``Flag`` and1002``Visibility`` elements that are common for both the positive and negative flag1003and their common help text suffix.1004 1005**String**1006 1007The key path defaults to the specified string, or an empty one, if omitted. When1008the option appears on the command line, the argument value is simply copied.1009 1010.. code-block:: text1011 1012  def isysroot : JoinedOrSeparate<["-"], "isysroot">,1013    Visibility<[ClangOption, CC1Option, FlangOption]>,1014    MarshallingInfoString<HeaderSearchOpts<"Sysroot">, [{"/"}]>;1015 1016**List of Strings**1017 1018The key path defaults to an empty ``std::vector<std::string>``. Values specified1019with each appearance of the option on the command line are appended to the1020vector.1021 1022.. code-block:: text1023 1024  def frewrite_map_file : Separate<["-"], "frewrite-map-file">,1025    Visibility<[ClangOption, CC1Option]>,1026    MarshallingInfoStringVector<CodeGenOpts<"RewriteMapFiles">>;1027 1028**Integer**1029 1030The key path defaults to the specified integer value, or ``0`` if omitted. When1031the option appears on the command line, its value gets parsed by ``llvm::APInt``1032and the result is assigned to the key path on success.1033 1034.. code-block:: text1035 1036  def mstack_probe_size : Joined<["-"], "mstack-probe-size=">,1037    Visibility<[ClangOption, CC1Option]>,1038    MarshallingInfoInt<CodeGenOpts<"StackProbeSize">, "4096">;1039 1040**Enumeration**1041 1042The key path defaults to the value specified in ``MarshallingInfoEnum`` prefixed1043by the contents of ``NormalizedValuesScope`` and ``::``. This ensures correct1044reference to an enum case is formed even if the enum resides in a different1045namespace or is an enum class. If the value present on the command line does not1046match any of the comma-separated values from ``Values``, an error diagnostic is1047issued. Otherwise, the corresponding element from ``NormalizedValues`` at the1048same index is assigned to the key path (also correctly scoped). The number of1049comma-separated string values and elements of the array within1050``NormalizedValues`` must match.1051 1052.. code-block:: text1053 1054  def mthread_model : Separate<["-"], "mthread-model">,1055    Visibility<[ClangOption, CC1Option]>,1056    Values<"posix,single">, NormalizedValues<["POSIX", "Single"]>,1057    NormalizedValuesScope<"LangOptions::ThreadModelKind">,1058    MarshallingInfoEnum<LangOpts<"ThreadModel">, "POSIX">;1059 1060..1061  Intentionally omitting MarshallingInfoBitfieldFlag. It's adding some1062  complexity to the marshalling infrastructure and might be removed.1063 1064It is also possible to define relationships between options.1065 1066**Implication**1067 1068The key path defaults to the default value from the primary ``Marshalling``1069annotation. Then, if any of the elements of ``ImpliedByAnyOf`` evaluate to true,1070the key path value is changed to the specified value or ``true`` if missing.1071Finally, the command line is parsed according to the primary annotation.1072 1073.. code-block:: text1074 1075  def fms_extensions : Flag<["-"], "fms-extensions">,1076    Visibility<[ClangOption, CC1Option]>,1077    MarshallingInfoFlag<LangOpts<"MicrosoftExt">>,1078    ImpliedByAnyOf<[fms_compatibility.KeyPath], "true">;1079 1080**Condition**1081 1082The option is parsed only if the expression in ``ShouldParseIf`` evaluates to1083true.1084 1085.. code-block:: text1086 1087  def fopenmp_enable_irbuilder : Flag<["-"], "fopenmp-enable-irbuilder">,1088    Visibility<[ClangOption, CC1Option]>,1089    MarshallingInfoFlag<LangOpts<"OpenMPIRBuilder">>,1090    ShouldParseIf<fopenmp.KeyPath>;1091 1092The Lexer and Preprocessor Library1093==================================1094 1095The Lexer library contains several tightly-connected classes that are involved1096with the nasty process of lexing and preprocessing C source code.  The main1097interface to this library for outside clients is the large ``Preprocessor``1098class.  It contains the various pieces of state that are required to coherently1099read tokens out of a translation unit.1100 1101The core interface to the ``Preprocessor`` object (once it is set up) is the1102``Preprocessor::Lex`` method, which returns the next :ref:`Token <Token>` from1103the preprocessor stream.  There are two types of token providers that the1104preprocessor is capable of reading from: a buffer lexer (provided by the1105:ref:`Lexer <Lexer>` class) and a buffered token stream (provided by the1106:ref:`TokenLexer <TokenLexer>` class).1107 1108.. _Token:1109 1110The Token class1111---------------1112 1113The ``Token`` class is used to represent a single lexed token.  Tokens are1114intended to be used by the lexer/preprocessor and parser libraries, but are not1115intended to live beyond them (for example, they should not live in the ASTs).1116 1117Tokens most often live on the stack (or some other location that is efficient1118to access) as the parser is running, but occasionally do get buffered up.  For1119example, macro definitions are stored as a series of tokens, and the C++1120front-end periodically needs to buffer tokens up for tentative parsing and1121various pieces of look-ahead.  As such, the size of a ``Token`` matters.  On a112232-bit system, ``sizeof(Token)`` is currently 16 bytes.1123 1124Tokens occur in two forms: :ref:`annotation tokens <AnnotationToken>` and1125normal tokens.  Normal tokens are those returned by the lexer, annotation1126tokens represent semantic information and are produced by the parser, replacing1127normal tokens in the token stream.  Normal tokens contain the following1128information:1129 1130* **A SourceLocation** --- This indicates the location of the start of the1131  token.1132 1133* **A length** --- This stores the length of the token as stored in the1134  ``SourceBuffer``.  For tokens that include them, this length includes1135  trigraphs and escaped newlines which are ignored by later phases of the1136  compiler.  By pointing into the original source buffer, it is always possible1137  to get the original spelling of a token completely accurately.1138 1139* **IdentifierInfo** --- If a token takes the form of an identifier, and if1140  identifier lookup was enabled when the token was lexed (e.g., the lexer was1141  not reading in "raw" mode) this contains a pointer to the unique hash value1142  for the identifier.  Because the lookup happens before keyword1143  identification, this field is set even for language keywords like "``for``".1144 1145* **TokenKind** --- This indicates the kind of token as classified by the1146  lexer.  This includes things like ``tok::starequal`` (for the "``*=``"1147  operator), ``tok::ampamp`` for the "``&&``" token, and keyword values (e.g.,1148  ``tok::kw_for``) for identifiers that correspond to keywords.  Note that1149  some tokens can be spelled multiple ways.  For example, C++ supports1150  "operator keywords", where things like "``and``" are treated exactly like the1151  "``&&``" operator.  In these cases, the kind value is set to ``tok::ampamp``,1152  which is good for the parser, which doesn't have to consider both forms.  For1153  something that cares about which form is used (e.g., the preprocessor1154  "stringize" operator) the spelling indicates the original form.1155 1156* **Flags** --- There are currently four flags tracked by the1157  lexer/preprocessor system on a per-token basis:1158 1159  #. **StartOfLine** --- This was the first token that occurred on its input1160     source line.1161  #. **LeadingSpace** --- There was a space character either immediately before1162     the token or transitively before the token as it was expanded through a1163     macro.  The definition of this flag is very closely defined by the1164     stringizing requirements of the preprocessor.1165  #. **DisableExpand** --- This flag is used internally to the preprocessor to1166     represent identifier tokens which have macro expansion disabled.  This1167     prevents them from being considered as candidates for macro expansion ever1168     in the future.1169  #. **NeedsCleaning** --- This flag is set if the original spelling for the1170     token includes a trigraph or escaped newline.  Since this is uncommon,1171     many pieces of code can fast-path on tokens that did not need cleaning.1172 1173One interesting (and somewhat unusual) aspect of normal tokens is that they1174don't contain any semantic information about the lexed value.  For example, if1175the token was a pp-number token, we do not represent the value of the number1176that was lexed (this is left for later pieces of code to decide).1177Additionally, the lexer library has no notion of typedef names vs variable1178names: both are returned as identifiers, and the parser is left to decide1179whether a specific identifier is a typedef or a variable (tracking this1180requires scope information among other things).  The parser can do this1181translation by replacing tokens returned by the preprocessor with "Annotation1182Tokens".1183 1184.. _AnnotationToken:1185 1186Annotation Tokens1187-----------------1188 1189Annotation tokens are tokens that are synthesized by the parser and injected1190into the preprocessor's token stream (replacing existing tokens) to record1191semantic information found by the parser.  For example, if "``foo``" is found1192to be a typedef, the "``foo``" ``tok::identifier`` token is replaced with an1193``tok::annot_typename``.  This is useful for a couple of reasons: 1) this makes1194it easy to handle qualified type names (e.g., "``foo::bar::baz<42>::t``") in1195C++ as a single "token" in the parser.  2) if the parser backtracks, the1196reparse does not need to redo semantic analysis to determine whether a token1197sequence is a variable, type, template, etc.1198 1199Annotation tokens are created by the parser and reinjected into the parser's1200token stream (when backtracking is enabled).  Because they can only exist in1201tokens that the preprocessor-proper is done with, it doesn't need to keep1202around flags like "start of line" that the preprocessor uses to do its job.1203Additionally, an annotation token may "cover" a sequence of preprocessor tokens1204(e.g., "``a::b::c``" is five preprocessor tokens).  As such, the valid fields1205of an annotation token are different than the fields for a normal token (but1206they are multiplexed into the normal ``Token`` fields):1207 1208* **SourceLocation "Location"** --- The ``SourceLocation`` for the annotation1209  token indicates the first token replaced by the annotation token.  In the1210  example above, it would be the location of the "``a``" identifier.1211* **SourceLocation "AnnotationEndLoc"** --- This holds the location of the last1212  token replaced with the annotation token.  In the example above, it would be1213  the location of the "``c``" identifier.1214* **void* "AnnotationValue"** --- This contains an opaque object that the1215  parser gets from ``Sema``.  The parser merely preserves the information for1216  ``Sema`` to later interpret based on the annotation token kind.1217* **TokenKind "Kind"** --- This indicates the kind of Annotation token this is.1218  See below for the different valid kinds.1219 1220Annotation tokens currently come in three kinds:1221 1222#. **tok::annot_typename**: This annotation token represents a resolved1223   typename token that is potentially qualified.  The ``AnnotationValue`` field1224   contains the ``QualType`` returned by ``Sema::getTypeName()``, possibly with1225   source location information attached.1226#. **tok::annot_cxxscope**: This annotation token represents a C++ scope1227   specifier, such as "``A::B::``".  This corresponds to the grammar1228   productions "*::*" and "*:: [opt] nested-name-specifier*".  The1229   ``AnnotationValue`` pointer is a ``NestedNameSpecifier *`` returned by the1230   ``Sema::ActOnCXXGlobalScopeSpecifier`` and1231   ``Sema::ActOnCXXNestedNameSpecifier`` callbacks.1232#. **tok::annot_template_id**: This annotation token represents a C++1233   template-id such as "``foo<int, 4>``", where "``foo``" is the name of a1234   template.  The ``AnnotationValue`` pointer is a pointer to a ``malloc``'d1235   ``TemplateIdAnnotation`` object.  Depending on the context, a parsed1236   template-id that names a type might become a typename annotation token (if1237   all we care about is the named type, e.g., because it occurs in a type1238   specifier) or might remain a template-id token (if we want to retain more1239   source location information or produce a new type, e.g., in a declaration of1240   a class template specialization).  template-id annotation tokens that refer1241   to a type can be "upgraded" to typename annotation tokens by the parser.1242 1243As mentioned above, annotation tokens are not returned by the preprocessor,1244they are formed on demand by the parser.  This means that the parser has to be1245aware of cases where an annotation could occur and form it where appropriate.1246This is somewhat similar to how the parser handles Translation Phase 6 of C99:1247String Concatenation (see C99 5.1.1.2).  In the case of string concatenation,1248the preprocessor just returns distinct ``tok::string_literal`` and1249``tok::wide_string_literal`` tokens and the parser eats a sequence of them1250wherever the grammar indicates that a string literal can occur.1251 1252In order to do this, whenever the parser expects a ``tok::identifier`` or1253``tok::coloncolon``, it should call the ``TryAnnotateTypeOrScopeToken`` or1254``TryAnnotateCXXScopeToken`` methods to form the annotation token.  These1255methods will maximally form the specified annotation tokens and replace the1256current token with them, if applicable.  If the current token is not valid for1257an annotation token, it will remain an identifier or "``::``" token.1258 1259.. _Lexer:1260 1261The ``Lexer`` class1262-------------------1263 1264The ``Lexer`` class provides the mechanics of lexing tokens out of a source1265buffer and deciding what they mean.  The ``Lexer`` is complicated by the fact1266that it operates on raw buffers that have not had spelling eliminated (this is1267a necessity to get decent performance), but this is countered with careful1268coding as well as standard performance techniques (for example, the comment1269handling code is vectorized on X86 and PowerPC hosts).1270 1271The lexer has a couple of interesting modal features:1272 1273* The lexer can operate in "raw" mode.  This mode has several features that1274  make it possible to quickly lex the file (e.g., it stops identifier lookup,1275  doesn't specially handle preprocessor tokens, handles EOF differently, etc).1276  This mode is used for lexing within an "``#if 0``" block, for example.1277* The lexer can capture and return comments as tokens.  This is required to1278  support the ``-C`` preprocessor mode, which passes comments through, and is1279  used by the diagnostic checker to identify expect-error annotations.1280* The lexer can be in ``ParsingFilename`` mode, which happens when1281  preprocessing after reading a ``#include`` directive.  This mode changes the1282  parsing of "``<``" to return an "angled string" instead of a bunch of tokens1283  for each thing within the filename.1284* When parsing a preprocessor directive (after "``#``") the1285  ``ParsingPreprocessorDirective`` mode is entered.  This changes the parser to1286  return EOD at a newline.1287* The ``Lexer`` uses a ``LangOptions`` object to know whether trigraphs are1288  enabled, whether C++ or ObjC keywords are recognized, etc.1289 1290In addition to these modes, the lexer keeps track of a couple of other features1291that are local to a lexed buffer, which change as the buffer is lexed:1292 1293* The ``Lexer`` uses ``BufferPtr`` to keep track of the current character being1294  lexed.1295* The ``Lexer`` uses ``IsAtStartOfLine`` to keep track of whether the next1296  lexed token will start with its "start of line" bit set.1297* The ``Lexer`` keeps track of the current "``#if``" directives that are active1298  (which can be nested).1299* The ``Lexer`` keeps track of an :ref:`MultipleIncludeOpt1300  <MultipleIncludeOpt>` object, which is used to detect whether the buffer uses1301  the standard "``#ifndef XX`` / ``#define XX``" idiom to prevent multiple1302  inclusion.  If a buffer does, subsequent includes can be ignored if the1303  "``XX``" macro is defined.1304 1305.. _TokenLexer:1306 1307The ``TokenLexer`` class1308------------------------1309 1310The ``TokenLexer`` class is a token provider that returns tokens from a list of1311tokens that came from somewhere else.  It is typically used for two things: 1)1312returning tokens from a macro definition as it is being expanded 2) returning1313tokens from an arbitrary buffer of tokens.  The later use is used by1314``_Pragma`` and will most likely be used to handle unbounded look-ahead for the1315C++ parser.1316 1317.. _MultipleIncludeOpt:1318 1319The ``MultipleIncludeOpt`` class1320--------------------------------1321 1322The ``MultipleIncludeOpt`` class implements a really simple little state1323machine that is used to detect the standard "``#ifndef XX`` / ``#define XX``"1324idiom that people typically use to prevent multiple inclusion of headers.  If a1325buffer uses this idiom and is subsequently ``#include``'d, the preprocessor can1326simply check to see whether the guarding condition is defined or not.  If so,1327the preprocessor can completely ignore the include of the header.1328 1329.. _Parser:1330 1331The Parser Library1332==================1333 1334This library contains a recursive-descent parser that polls tokens from the1335preprocessor and notifies a client of the parsing progress.1336 1337Historically, the parser used to talk to an abstract ``Action`` interface that1338had virtual methods for parse events, for example ``ActOnBinOp()``.  When Clang1339grew C++ support, the parser stopped supporting general ``Action`` clients --1340it now always talks to the :ref:`Sema library <Sema>`.  However, the Parser1341still accesses AST objects only through opaque types like ``ExprResult`` and1342``StmtResult``.  Only :ref:`Sema <Sema>` looks at the AST node contents of these1343wrappers.1344 1345.. _AST:1346 1347The AST Library1348===============1349 1350.. _ASTPhilosophy:1351 1352Design philosophy1353-----------------1354 1355Immutability1356^^^^^^^^^^^^1357 1358Clang AST nodes (types, declarations, statements, expressions, and so on) are1359generally designed to be immutable once created. This provides a number of key1360benefits:1361 1362  * Canonicalization of the "meaning" of nodes is possible as soon as the nodes1363    are created, and is not invalidated by later addition of more information.1364    For example, we :ref:`canonicalize types <CanonicalType>`, and use a1365    canonicalized representation of expressions when determining whether two1366    function template declarations involving dependent expressions declare the1367    same entity.1368  * AST nodes can be reused when they have the same meaning. For example, we1369    reuse ``Type`` nodes when representing the same type (but maintain separate1370    ``TypeLoc``\s for each instance where a type is written), and we reuse1371    non-dependent ``Stmt`` and ``Expr`` nodes across instantiations of a1372    template.1373  * Serialization and deserialization of the AST to/from AST files is simpler:1374    we do not need to track modifications made to AST nodes imported from AST1375    files and serialize separate "update records".1376 1377There are unfortunately exceptions to this general approach, such as:1378 1379  * The first declaration of a redeclarable entity maintains a pointer to the1380    most recent declaration of that entity, which naturally needs to change as1381    more declarations are parsed.1382  * Name lookup tables in declaration contexts change after the namespace1383    declaration is formed.1384  * We attempt to maintain only a single declaration for an instantiation of a1385    template, rather than having distinct declarations for an instantiation of1386    the declaration versus the definition, so template instantiation often1387    updates parts of existing declarations.1388  * Some parts of declarations are required to be instantiated separately (this1389    includes default arguments and exception specifications), and such1390    instantiations update the existing declaration.1391 1392These cases tend to be fragile; mutable AST state should be avoided where1393possible.1394 1395As a consequence of this design principle, we typically do not provide setters1396for AST state. (Some are provided for short-term modifications intended to be1397used immediately after an AST node is created and before it's "published" as1398part of the complete AST, or where language semantics require after-the-fact1399updates.)1400 1401Faithfulness1402^^^^^^^^^^^^1403 1404The AST intends to provide a representation of the program that is faithful to1405the original source. We intend for it to be possible to write refactoring tools1406using only information stored in, or easily reconstructible from, the Clang AST.1407This means that the AST representation should either not desugar source-level1408constructs to simpler forms, or -- where made necessary by language semantics1409or a clear engineering tradeoff -- should desugar minimally and wrap the result1410in a construct representing the original source form.1411 1412For example, ``CXXForRangeStmt`` directly represents the syntactic form of a1413range-based for statement but also holds a semantic representation of the1414range declaration and iterator declarations. It does not contain a1415fully-desugared ``ForStmt``, however.1416 1417Some AST nodes (for example, ``ParenExpr``) represent only syntax, and others1418(for example, ``ImplicitCastExpr``) represent only semantics, but most nodes1419will represent a combination of syntax and associated semantics. Inheritance1420is typically used when representing different (but related) syntaxes for nodes1421with the same or similar semantics.1422 1423.. _Type:1424 1425The ``Type`` class and its subclasses1426-------------------------------------1427 1428The ``Type`` class (and its subclasses) is an important part of the AST.1429Types are accessed through the ``ASTContext`` class, which implicitly creates1430and uniques them as they are needed.  Types have a couple of non-obvious1431features: 1) they do not capture type qualifiers like ``const`` or ``volatile``1432(see :ref:`QualType <QualType>`), and 2) they implicitly capture typedef1433information.  Once created, types are immutable (unlike decls).1434 1435Typedefs in C make semantic analysis a bit more complex than it would be without1436them.  The issue is that we want to capture typedef information and represent it1437in the AST perfectly, but the semantics of operations need to "see through"1438typedefs.  For example, consider this code:1439 1440.. code-block:: c++1441 1442  void func() {1443    typedef int foo;1444    foo X, *Y;1445    typedef foo *bar;1446    bar Z;1447    *X; // error1448    **Y; // error1449    **Z; // error1450  }1451 1452The code above is illegal, and thus we expect there to be diagnostics emitted1453on the annotated lines.  In this example, we expect to get:1454 1455.. code-block:: text1456 1457  test.c:6:1: error: indirection requires pointer operand ('foo' invalid)1458    *X; // error1459    ^~1460  test.c:7:1: error: indirection requires pointer operand ('foo' invalid)1461    **Y; // error1462    ^~~1463  test.c:8:1: error: indirection requires pointer operand ('foo' invalid)1464    **Z; // error1465    ^~~1466 1467While this example is somewhat silly, it illustrates the point: we want to1468retain typedef information where possible, so that we can emit errors about1469"``std::string``" instead of "``std::basic_string<char, std:...``".  Doing this1470requires properly keeping typedef information (for example, the type of ``X``1471is "``foo``", not "``int``"), and requires properly propagating it through the1472various operators (for example, the type of ``*Y`` is "``foo``", not1473"``int``").  In order to retain this information, the type of these expressions1474is an instance of the ``TypedefType`` class, which indicates that the type of1475these expressions is a typedef for "``foo``".1476 1477Representing types like this is great for diagnostics because the1478user-specified type is always immediately available.  There are two problems1479with this: first, various semantic checks need to make judgements about the1480*actual structure* of a type, ignoring typedefs.  Second, we need an efficient1481way to query whether two types are structurally identical to each other,1482ignoring typedefs.  The solution to both of these problems is the idea of1483canonical types.1484 1485.. _CanonicalType:1486 1487Canonical Types1488^^^^^^^^^^^^^^^1489 1490Every instance of the ``Type`` class contains a canonical type pointer.  For1491simple types with no typedefs involved (e.g., "``int``", "``int*``",1492"``int**``"), the type just points to itself.  For types that have a typedef1493somewhere in their structure (e.g., "``foo``", "``foo*``", "``foo**``",1494"``bar``"), the canonical type pointer points to their structurally equivalent1495type without any typedefs (e.g., "``int``", "``int*``", "``int**``", and1496"``int*``" respectively).1497 1498This design provides a constant time operation (dereferencing the canonical type1499pointer) that gives us access to the structure of types.  For example, we can1500trivially tell that "``bar``" and "``foo*``" are the same type by dereferencing1501their canonical type pointers and doing a pointer comparison (they both point1502to the single "``int*``" type).1503 1504Canonical types and typedef types bring up some complexities that must be1505carefully managed.  Specifically, the ``isa``/``cast``/``dyn_cast`` operators1506generally shouldn't be used in code that is inspecting the AST.  For example,1507when type checking the indirection operator (unary "``*``" on a pointer), the1508type checker must verify that the operand has a pointer type.  It would not be1509correct to check that with "``isa<PointerType>(SubExpr->getType())``", because1510this predicate would fail if the subexpression had a typedef type.1511 1512The solution to this problem is a set of helper methods on ``Type``, used to1513check their properties.  In this case, it would be correct to use1514"``SubExpr->getType()->isPointerType()``" to do the check.  This predicate will1515return true if the *canonical type is a pointer*, which is true any time the1516type is structurally a pointer type.  The only hard part here is remembering1517not to use the ``isa``/``cast``/``dyn_cast`` operations.1518 1519The second problem we face is how to get access to the pointer type once we1520know it exists.  To continue the example, the result type of the indirection1521operator is the pointee type of the subexpression.  In order to determine the1522type, we need to get the instance of ``PointerType`` that best captures the1523typedef information in the program.  If the type of the expression is literally1524a ``PointerType``, we can return that; otherwise, we have to dig through the1525typedefs to find the pointer type.  For example, if the subexpression had type1526"``foo*``", we could return that type as the result.  If the subexpression had1527type "``bar``", we want to return "``foo*``" (note that we do *not* want1528"``int*``").  In order to provide all of this, ``Type`` has a1529``getAsPointerType()`` method that checks whether the type is structurally a1530``PointerType`` and, if so, returns the best one.  If not, it returns a null1531pointer.1532 1533This structure is somewhat mystical, but after meditating on it, it will make1534sense to you :).1535 1536.. _QualType:1537 1538The ``QualType`` class1539----------------------1540 1541The ``QualType`` class is designed as a trivial value class that is small,1542passed by-value and is efficient to query.  The idea of ``QualType`` is that it1543stores the type qualifiers (``const``, ``volatile``, ``restrict``, plus some1544extended qualifiers required by language extensions) separately from the types1545themselves.  ``QualType`` is conceptually a pair of "``Type*``" and the bits1546for these type qualifiers.1547 1548By storing the type qualifiers as bits in the conceptual pair, it is extremely1549efficient to get the set of qualifiers on a ``QualType`` (just return the field1550of the pair), add a type qualifier (which is a trivial constant-time operation1551that sets a bit), and remove one or more type qualifiers (just return a1552``QualType`` with the bitfield set to empty).1553 1554Further, because the bits are stored outside of the type itself, we do not need1555to create duplicates of types with different sets of qualifiers (i.e., there is1556only a single heap allocated "``int``" type: "``const int``" and "``volatile1557const int``" both point to the same heap allocated "``int``" type).  This1558reduces the heap size used to represent bits and also means we do not have to1559consider qualifiers when uniquing types (:ref:`Type <Type>` does not even1560contain qualifiers).1561 1562In practice, the two most common type qualifiers (``const`` and ``restrict``)1563are stored in the low bits of the pointer to the ``Type`` object, together with1564a flag indicating whether extended qualifiers are present (which must be1565heap-allocated).  This means that ``QualType`` is exactly the same size as a1566pointer.1567 1568.. _DeclarationName:1569 1570Declaration names1571-----------------1572 1573The ``DeclarationName`` class represents the name of a declaration in Clang.1574Declarations in the C family of languages can take several different forms.1575Most declarations are named by simple identifiers, e.g., "``f``" and "``x``" in1576the function declaration ``f(int x)``.  In C++, declaration names can also name1577class constructors ("``Class``" in ``struct Class { Class(); }``), class1578destructors ("``~Class``"), overloaded operator names ("``operator+``"), and1579conversion functions ("``operator void const *``").  In Objective-C,1580declaration names can refer to the names of Objective-C methods, which involve1581the method name and the parameters, collectively called a *selector*, e.g.,1582"``setWidth:height:``".  Since all of these kinds of entities --- variables,1583functions, Objective-C methods, C++ constructors, destructors, and operators1584--- are represented as subclasses of Clang's common ``NamedDecl`` class,1585``DeclarationName`` is designed to efficiently represent any kind of name.1586 1587Given a ``DeclarationName`` ``N``, ``N.getNameKind()`` will produce a value1588that describes what kind of name ``N`` stores.  There are 10 options (all of1589the names are inside the ``DeclarationName`` class).1590 1591``Identifier``1592 1593  The name is a simple identifier.  Use ``N.getAsIdentifierInfo()`` to retrieve1594  the corresponding ``IdentifierInfo*`` pointing to the actual identifier.1595 1596``ObjCZeroArgSelector``, ``ObjCOneArgSelector``, ``ObjCMultiArgSelector``1597 1598  The name is an Objective-C selector, which can be retrieved as a ``Selector``1599  instance via ``N.getObjCSelector()``.  The three possible name kinds for1600  Objective-C reflect an optimization within the ``DeclarationName`` class:1601  both zero- and one-argument selectors are stored as a masked1602  ``IdentifierInfo`` pointer, and therefore require very little space, since1603  zero- and one-argument selectors are far more common than multi-argument1604  selectors (which use a different structure).1605 1606``CXXConstructorName``1607 1608  The name is a C++ constructor name.  Use ``N.getCXXNameType()`` to retrieve1609  the :ref:`type <QualType>` that this constructor is meant to construct.  The1610  type is always the canonical type, since all constructors for a given type1611  have the same name.1612 1613``CXXDestructorName``1614 1615  The name is a C++ destructor name.  Use ``N.getCXXNameType()`` to retrieve1616  the :ref:`type <QualType>` whose destructor is being named.  This type is1617  always a canonical type.1618 1619``CXXConversionFunctionName``1620 1621  The name is a C++ conversion function.  Conversion functions are named1622  according to the type they convert to, e.g., "``operator void const *``".1623  Use ``N.getCXXNameType()`` to retrieve the type that this conversion function1624  converts to.  This type is always a canonical type.1625 1626``CXXOperatorName``1627 1628  The name is a C++ overloaded operator name.  Overloaded operators are named1629  according to their spelling, e.g., "``operator+``" or "``operator new []``".1630  Use ``N.getCXXOverloadedOperator()`` to retrieve the overloaded operator (a1631  value of type ``OverloadedOperatorKind``).1632 1633``CXXLiteralOperatorName``1634 1635  The name is a C++11 user-defined literal operator.  User-defined1636  Literal operators are named according to the suffix they define,1637  e.g., "``_foo``" for "``operator "" _foo``".  Use1638  ``N.getCXXLiteralIdentifier()`` to retrieve the corresponding1639  ``IdentifierInfo*`` pointing to the identifier.1640 1641``CXXUsingDirective``1642 1643  The name is a C++ using directive.  Using directives are not really1644  NamedDecls, in that they all have the same name, but they are1645  implemented as such in order to store them in DeclContext1646  effectively.1647 1648``DeclarationName``\ s are cheap to create, copy, and compare.  They require1649only a single pointer's worth of storage in the common cases (identifiers,1650zero- and one-argument Objective-C selectors) and use dense, uniqued storage1651for the other kinds of names.  Two ``DeclarationName``\ s can be compared for1652equality (``==``, ``!=``) using a simple bitwise comparison, can be ordered1653with ``<``, ``>``, ``<=``, and ``>=`` (which provide a lexicographical ordering1654for normal identifiers but an unspecified ordering for other kinds of names),1655and can be placed into LLVM ``DenseMap``\ s and ``DenseSet``\ s.1656 1657``DeclarationName`` instances can be created in different ways depending on1658what kind of name the instance will store.  Normal identifiers1659(``IdentifierInfo`` pointers) and Objective-C selectors (``Selector``) can be1660implicitly converted to ``DeclarationNames``.  Names for C++ constructors,1661destructors, conversion functions, and overloaded operators can be retrieved1662from the ``DeclarationNameTable``, an instance of which is available as1663``ASTContext::DeclarationNames``.  The member functions1664``getCXXConstructorName``, ``getCXXDestructorName``,1665``getCXXConversionFunctionName``, and ``getCXXOperatorName``, respectively,1666return ``DeclarationName`` instances for the four kinds of C++ special function1667names.1668 1669.. _DeclContext:1670 1671Declaration contexts1672--------------------1673 1674Every declaration in a program exists within some *declaration context*, such1675as a translation unit, namespace, class, or function.  Declaration contexts in1676Clang are represented by the ``DeclContext`` class, from which the various1677declaration-context AST nodes (``TranslationUnitDecl``, ``NamespaceDecl``,1678``RecordDecl``, ``FunctionDecl``, etc.) will derive.  The ``DeclContext`` class1679provides several facilities common to each declaration context:1680 1681Source-centric vs. Semantics-centric View of Declarations1682 1683  ``DeclContext`` provides two views of the declarations stored within a1684  declaration context.  The source-centric view accurately represents the1685  program source code as written, including multiple declarations of entities1686  where present (see the section :ref:`Redeclarations and Overloads1687  <Redeclarations>`), while the semantics-centric view represents the program1688  semantics.  The two views are kept synchronized by semantic analysis while1689  the ASTs are being constructed.1690 1691Storage of declarations within that context1692 1693  Every declaration context can contain some number of declarations.  For1694  example, a C++ class (represented by ``RecordDecl``) contains various member1695  functions, fields, nested types, and so on.  All of these declarations will1696  be stored within the ``DeclContext``, and one can iterate over the1697  declarations via [``DeclContext::decls_begin()``,1698  ``DeclContext::decls_end()``).  This mechanism provides the source-centric1699  view of declarations in the context.1700 1701Lookup of declarations within that context1702 1703  The ``DeclContext`` structure provides efficient name lookup for names within1704  that declaration context.  For example, if ``N`` is a namespace we can look1705  for the name ``N::f`` using ``DeclContext::lookup``.  The lookup itself is1706  based on a lazily-constructed array (for declaration contexts with a small1707  number of declarations) or hash table (for declaration contexts with more1708  declarations).  The lookup operation provides the semantics-centric view of1709  the declarations in the context.1710 1711Ownership of declarations1712 1713  The ``DeclContext`` owns all of the declarations that were declared within1714  its declaration context, and is responsible for the management of their1715  memory as well as their (de-)serialization.1716 1717All declarations are stored within a declaration context, and one can query1718information about the context in which each declaration lives.  One can1719retrieve the ``DeclContext`` that contains a particular ``Decl`` using1720``Decl::getDeclContext``.  However, see the section1721:ref:`LexicalAndSemanticContexts` for more information about how to interpret1722this context information.1723 1724.. _Redeclarations:1725 1726Redeclarations and Overloads1727^^^^^^^^^^^^^^^^^^^^^^^^^^^^1728 1729Within a translation unit, it is common for an entity to be declared several1730times.  For example, we might declare a function "``f``" and then later1731re-declare it as part of an inlined definition:1732 1733.. code-block:: c++1734 1735  void f(int x, int y, int z = 1);1736 1737  inline void f(int x, int y, int z) { /* ...  */ }1738 1739The representation of "``f``" differs in the source-centric and1740semantics-centric views of a declaration context.  In the source-centric view,1741all redeclarations will be present, in the order they occurred in the source1742code, making this view suitable for clients that wish to see the structure of1743the source code.  In the semantics-centric view, only the most recent "``f``"1744will be found by the lookup, since it effectively replaces the first1745declaration of "``f``".1746 1747(Note that because ``f`` can be redeclared at block scope, or in a friend1748declaration, etc., it is possible that the declaration of ``f`` found by name1749lookup will not be the most recent one.)1750 1751In the semantics-centric view, overloading of functions is represented1752explicitly.  For example, given two declarations of a function "``g``" that are1753overloaded, e.g.,1754 1755.. code-block:: c++1756 1757  void g();1758  void g(int);1759 1760the ``DeclContext::lookup`` operation will return a1761``DeclContext::lookup_result`` that contains a range of iterators over1762declarations of "``g``".  Clients that perform semantic analysis on a program1763that is not concerned with the actual source code will primarily use this1764semantics-centric view.1765 1766.. _LexicalAndSemanticContexts:1767 1768Lexical and Semantic Contexts1769^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1770 1771Each declaration has two potentially different declaration contexts: a1772*lexical* context, which corresponds to the source-centric view of the1773declaration context, and a *semantic* context, which corresponds to the1774semantics-centric view.  The lexical context is accessible via1775``Decl::getLexicalDeclContext`` while the semantic context is accessible via1776``Decl::getDeclContext``, both of which return ``DeclContext`` pointers.  For1777most declarations, the two contexts are identical.  For example:1778 1779.. code-block:: c++1780 1781  class X {1782  public:1783    void f(int x);1784  };1785 1786Here, the semantic and lexical contexts of ``X::f`` are the ``DeclContext``1787associated with the class ``X`` (itself stored as a ``RecordDecl`` AST node).1788However, we can now define ``X::f`` out-of-line:1789 1790.. code-block:: c++1791 1792  void X::f(int x = 17) { /* ...  */ }1793 1794This definition of "``f``" has different lexical and semantic contexts.  The1795lexical context corresponds to the declaration context in which the actual1796declaration occurred in the source code, e.g., the translation unit containing1797``X``.  Thus, this declaration of ``X::f`` can be found by traversing the1798declarations provided by [``decls_begin()``, ``decls_end()``) in the1799translation unit.1800 1801The semantic context of ``X::f`` corresponds to the class ``X``, since this1802member function is (semantically) a member of ``X``.  Lookup of the name ``f``1803into the ``DeclContext`` associated with ``X`` will then return the definition1804of ``X::f`` (including information about the default argument).1805 1806Transparent Declaration Contexts1807^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1808 1809In C and C++, there are several contexts in which names that are logically1810declared inside another declaration will actually "leak" out into the enclosing1811scope from the perspective of name lookup.  The most obvious instance of this1812behavior is in enumeration types, e.g.,1813 1814.. code-block:: c++1815 1816  enum Color {1817    Red,1818    Green,1819    Blue1820  };1821 1822Here, ``Color`` is an enumeration, which is a declaration context that contains1823the enumerators ``Red``, ``Green``, and ``Blue``.  Thus, traversing the list of1824declarations contained in the enumeration ``Color`` will yield ``Red``,1825``Green``, and ``Blue``.  However, outside of the scope of ``Color`` one can1826name the enumerator ``Red`` without qualifying the name, e.g.,1827 1828.. code-block:: c++1829 1830  Color c = Red;1831 1832There are other entities in C++ that provide similar behavior.  For example,1833linkage specifications that use curly braces:1834 1835.. code-block:: c++1836 1837  extern "C" {1838    void f(int);1839    void g(int);1840  }1841  // f and g are visible here1842 1843For source-level accuracy, we treat the linkage specification and enumeration1844type as a declaration context in which its enclosed declarations ("``Red``",1845"``Green``", and "``Blue``"; "``f``" and "``g``") are declared.  However, these1846declarations are visible outside of the scope of the declaration context.1847 1848These language features (and several others, described below) have roughly the1849same set of requirements: declarations are declared within a particular lexical1850context, but the declarations are also found via name lookup in scopes1851enclosing the declaration itself.  This feature is implemented via1852*transparent* declaration contexts (see1853``DeclContext::isTransparentContext()``), whose declarations are visible in the1854nearest enclosing non-transparent declaration context.  This means that the1855lexical context of the declaration (e.g., an enumerator) will be the1856transparent ``DeclContext`` itself, as will the semantic context, but the1857declaration will be visible in every outer context up to and including the1858first non-transparent declaration context (since transparent declaration1859contexts can be nested).1860 1861The transparent ``DeclContext``\ s are:1862 1863* Enumerations (but not C++11 "scoped enumerations"):1864 1865  .. code-block:: c++1866 1867    enum Color {1868      Red,1869      Green,1870      Blue1871    };1872    // Red, Green, and Blue are in scope1873 1874* C++ linkage specifications:1875 1876  .. code-block:: c++1877 1878    extern "C" {1879      void f(int);1880      void g(int);1881    }1882    // f and g are in scope1883 1884* Anonymous unions and structs:1885 1886  .. code-block:: c++1887 1888    struct LookupTable {1889      bool IsVector;1890      union {1891        std::vector<Item> *Vector;1892        std::set<Item> *Set;1893      };1894    };1895 1896    LookupTable LT;1897    LT.Vector = 0; // Okay: finds Vector inside the unnamed union1898 1899* C++11 inline namespaces:1900 1901  .. code-block:: c++1902 1903    namespace mylib {1904      inline namespace debug {1905        class X;1906      }1907    }1908    mylib::X *xp; // okay: mylib::X refers to mylib::debug::X1909 1910.. _MultiDeclContext:1911 1912Multiply-Defined Declaration Contexts1913^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1914 1915C++ namespaces have the interesting property that1916the namespace can be defined multiple times, and the declarations provided by1917each namespace definition are effectively merged (from the semantic point of1918view).  For example, the following two code snippets are semantically1919indistinguishable:1920 1921.. code-block:: c++1922 1923  // Snippet #1:1924  namespace N {1925    void f();1926  }1927  namespace N {1928    void f(int);1929  }1930 1931  // Snippet #2:1932  namespace N {1933    void f();1934    void f(int);1935  }1936 1937In Clang's representation, the source-centric view of declaration contexts will1938actually have two separate ``NamespaceDecl`` nodes in Snippet #1, each of which1939is a declaration context that contains a single declaration of "``f``".1940However, the semantics-centric view provided by name lookup into the namespace1941``N`` for "``f``" will return a ``DeclContext::lookup_result`` that contains a1942range of iterators over declarations of "``f``".1943 1944``DeclContext`` manages multiply-defined declaration contexts internally.  The1945function ``DeclContext::getPrimaryContext`` retrieves the "primary" context for1946a given ``DeclContext`` instance, which is the ``DeclContext`` responsible for1947maintaining the lookup table used for the semantics-centric view.  Given a1948``DeclContext``, one can obtain the set of declaration contexts that are1949semantically connected to this declaration context, in source order, including1950this context (which will be the only result, for non-namespace contexts) via1951``DeclContext::collectAllContexts``. Note that these functions are used1952internally within the lookup and insertion methods of the ``DeclContext``, so1953the vast majority of clients can ignore them.1954 1955Because the same entity can be defined multiple times in different modules,1956it is also possible for there to be multiple definitions of (for instance)1957a ``CXXRecordDecl``, all of which describe a definition of the same class.1958In such a case, only one of those "definitions" is considered by Clang to be1959the definition of the class, and the others are treated as non-defining1960declarations that happen to also contain member declarations. Corresponding1961members in each definition of such multiply-defined classes are identified1962either by redeclaration chains (if the members are ``Redeclarable``)1963or by simply a pointer to the canonical declaration (if the declarations1964are not ``Redeclarable`` -- in that case, a ``Mergeable`` base class is used1965instead).1966 1967Error Handling1968--------------1969 1970Clang produces an AST even when the code contains errors. Clang won't generate1971and optimize code for it, but it's used as parsing continues to detect further1972errors in the input. Clang-based tools also depend on such ASTs, and IDEs in1973particular benefit from a high-quality AST for broken code.1974 1975In the presence of errors, clang uses a few error-recovery strategies to present the1976broken code in the AST:1977 1978- correcting errors: in cases where clang is confident about the fix, it1979  provides a FixIt attaching to the error diagnostic and emits a corrected AST1980  (reflecting the written code with FixIts applied). The advantage of that is to1981  provide more accurate subsequent diagnostics. Typo correction is a typical1982  example.1983- representing invalid node: the invalid node is preserved in the AST in some1984  form, e.g., when the "declaration" part of the declaration contains semantic1985  errors, the Decl node is marked as invalid.1986- dropping invalid node: this often happens for errors that we don’t have1987  graceful recovery. Prior to Recovery AST, a mismatched-argument function call1988  expression was dropped though a ``CallExpr`` was created for semantic analysis.1989 1990With these strategies, clang surfaces better diagnostics, and provides AST1991consumers a rich AST reflecting the written source code as much as possible even1992for broken code.1993 1994Recovery AST1995^^^^^^^^^^^^1996 1997The idea of Recovery AST is to use recovery nodes, which act as a placeholder to1998maintain the rough structure of the parsing tree, preserve locations and1999children, but have no language semantics attached to them.2000 2001For example, consider the following mismatched function call:2002 2003.. code-block:: c++2004 2005   int NoArg();2006   void test(int abc) {2007     NoArg(abc); // oops, mismatched function arguments.2008   }2009 2010Without Recovery AST, the invalid function call expression (and its child2011expressions) would be dropped in the AST:2012 2013::2014 2015    |-FunctionDecl <line:1:1, col:11> NoArg 'int ()'2016    `-FunctionDecl <line:2:1, line:4:1> test 'void (int)'2017     |-ParmVarDecl <col:11, col:15> col:15 used abc 'int'2018     `-CompoundStmt <col:20, line:4:1>2019 2020 2021With Recovery AST, the AST looks like:2022 2023::2024 2025    |-FunctionDecl <line:1:1, col:11> NoArg 'int ()'2026    `-FunctionDecl <line:2:1, line:4:1> test 'void (int)'2027      |-ParmVarDecl <col:11, col:15> used abc 'int'2028      `-CompoundStmt <col:20, line:4:1>2029        `-RecoveryExpr <line:3:3, col:12> 'int' contains-errors2030          |-UnresolvedLookupExpr <col:3> '<overloaded function type>' lvalue (ADL) = 'NoArg'2031          `-DeclRefExpr <col:9> 'int' lvalue ParmVar 'abc' 'int'2032 2033 2034An alternative is to use existing Exprs, e.g., CallExpr for the above example.2035This would capture more call details (e.g., locations of parentheses) and allow2036it to be treated uniformly with valid CallExprs. However, jamming the data we2037have into CallExpr forces us to weaken its invariants, e.g., arg count may be2038wrong. This would introduce a huge burden on consumers of the AST to handle such2039"impossible" cases. So when we're representing (rather than correcting) errors,2040we use a distinct recovery node type with extremely weak invariants instead.2041 2042``RecoveryExpr`` is the only recovery node so far. In practice, broken decls2043need more detailed semantics preserved (the current ``Invalid`` flag works2044fairly well), and completely broken statements with interesting internal2045structure are rare (so dropping the statements is OK).2046 2047Types and dependence2048^^^^^^^^^^^^^^^^^^^^2049 2050``RecoveryExpr`` is an ``Expr``, so it must have a type. In many cases the true2051type can't really be known until the code is corrected (e.g., a call to a2052function that doesn't exist). And it means that we can't properly perform type2053checks on some containing constructs, such as ``return 42 + unknownFunction()``.2054 2055To model this, we generalize the concept of dependence from C++ templates to2056mean dependence on a template parameter or how an error is repaired. The2057``RecoveryExpr`` ``unknownFunction()`` has the totally unknown type2058``DependentTy``, and this suppresses type-based analysis in the same way it2059would inside a template.2060 2061In cases where we are confident about the concrete type (e.g., the return type2062for a broken non-overloaded function call), the ``RecoveryExpr`` will have this2063type. This allows more code to be typechecked, and produces a better AST and2064more diagnostics. For example:2065 2066.. code-block:: C++2067 2068   unknownFunction().size() // .size() is a CXXDependentScopeMemberExpr2069   std::string(42).size() // .size() is a resolved MemberExpr2070 2071Whether or not the ``RecoveryExpr`` has a dependent type, it is always2072considered value-dependent, because its value isn't well-defined until the error2073is resolved. Among other things, this means that clang doesn't emit more errors2074where a RecoveryExpr is used as a constant (e.g., array size), but also won't try2075to evaluate it.2076 2077ContainsErrors bit2078^^^^^^^^^^^^^^^^^^2079 2080Beyond the template dependence bits, we add a new “ContainsErrors” bit to2081express “Does this expression or anything within it contain errors” semantic,2082this bit is always set for RecoveryExpr, and propagated to other related nodes.2083This provides a fast way to query whether any (recursive) child of an expression2084had an error, which is often used to improve diagnostics.2085 2086.. code-block:: C++2087 2088   // C++2089   void recoveryExpr(int abc) {2090    unknownFunction(); // type-dependent, value-dependent, contains-errors2091 2092    std::string(42).size(); // value-dependent, contains-errors,2093                            // not type-dependent, as we know the type is std::string2094   }2095 2096 2097.. code-block:: C2098 2099   // C2100   void recoveryExpr(int abc) {2101     unknownVar + abc; // type-dependent, value-dependent, contains-errors2102   }2103 2104 2105The ASTImporter2106---------------2107 2108The ``ASTImporter`` class imports nodes of an ``ASTContext`` into another2109``ASTContext``. Please refer to the document :doc:`ASTImporter: Merging Clang2110ASTs <LibASTImporter>` for an introduction. And please read through the2111high-level `description of the import algorithm2112<LibASTImporter.html#algorithm-of-the-import>`_, this is essential for2113understanding further implementation details of the importer.2114 2115.. _templated:2116 2117Abstract Syntax Graph2118^^^^^^^^^^^^^^^^^^^^^2119 2120Despite the name, the Clang AST is not a tree. It is a directed graph with2121cycles. One example of a cycle is the connection between a2122``ClassTemplateDecl`` and its "templated" ``CXXRecordDecl``. The *templated*2123``CXXRecordDecl`` represents all the fields and methods inside the class2124template, while the ``ClassTemplateDecl`` holds the information which is2125related to being a template, i.e., template arguments, etc. We can get the2126*templated* class (the ``CXXRecordDecl``) of a ``ClassTemplateDecl`` with2127``ClassTemplateDecl::getTemplatedDecl()``. And we can get back a pointer of the2128"described" class template from the *templated* class:2129``CXXRecordDecl::getDescribedTemplate()``. So, this is a cycle between two2130nodes: between the *templated* and the *described* node. There may be various2131other kinds of cycles in the AST especially in case of declarations.2132 2133.. _structural-eq:2134 2135Structural Equivalency2136^^^^^^^^^^^^^^^^^^^^^^2137 2138Importing one AST node copies that node into the destination ``ASTContext``. To2139copy one node means that we create a new node in the "to" context then we set2140its properties to be equal to the properties of the source node. Before the2141copy, we make sure that the source node is not *structurally equivalent* to any2142existing node in the destination context. If it happens to be equivalent then2143we skip the copy.2144 2145The informal definition of structural equivalency is the following:2146Two nodes are **structurally equivalent** if they are2147 2148- builtin types and refer to the same type, e.g., ``int`` and ``int`` are2149  structurally equivalent,2150- function types and all their parameters have structurally equivalent types,2151- record types and all their fields in order of their definition have the same2152  identifier names and structurally equivalent types,2153- variable or function declarations and they have the same identifier name and2154  their types are structurally equivalent.2155 2156In C, two types are structurally equivalent if they are *compatible types*. For2157a formal definition of *compatible types*, please refer to 6.2.7/1 in the C112158standard. However, there is no definition for *compatible types* in the C++2159standard. Still, we extend the definition of structural equivalency to2160templates and their instantiations similarly: besides checking the previously2161mentioned properties, we have to check for equivalent template2162parameters/arguments, etc.2163 2164The structural equivalent check can be and is used independently from the2165ASTImporter, e.g., the ``clang::Sema`` class uses it also.2166 2167The equivalence of nodes may depend on the equivalency of other pairs of nodes.2168Thus, the check is implemented as a parallel graph traversal. We traverse2169through the nodes of both graphs at the same time. The actual implementation is2170similar to breadth-first-search. Let's say we start the traverse with the <A,B>2171pair of nodes. Whenever the traversal reaches a pair <X,Y> then the following2172statements are true:2173 2174- A and X are nodes from the same ASTContext.2175- B and Y are nodes from the same ASTContext.2176- A and B may or may not be from the same ASTContext.2177- if A == X and B == Y (pointer equivalency) then (there is a cycle during the2178  traverse)2179 2180  - A and B are structurally equivalent if and only if2181 2182    - All dependent nodes on the path from <A,B> to <X,Y> are structurally2183      equivalent.2184 2185When we compare two classes or enums and one of them is incomplete or has2186unloaded external lexical declarations then we cannot descend to compare their2187contained declarations. So in these cases they are considered equal if they2188have the same names. This is the way how we compare forward declarations with2189definitions.2190 2191.. TODO Should we elaborate the actual implementation of the graph traversal,2192.. which is a very weird BFS traversal?2193 2194Redeclaration Chains2195^^^^^^^^^^^^^^^^^^^^2196 2197The early version of the ``ASTImporter``'s merge mechanism squashed the2198declarations, i.e., it aimed to have only one declaration instead of maintaining2199a whole redeclaration chain. This early approach simply skipped importing a2200function prototype, but it imported a definition. To demonstrate the problem2201with this approach let's consider an empty "to" context and the following2202``virtual`` function declarations of ``f`` in the "from" context:2203 2204.. code-block:: c++2205 2206  struct B { virtual void f(); };2207  void B::f() {} // <-- let's import this definition2208 2209If we imported the definition with the "squashing" approach then we would2210end-up having one declaration which is indeed a definition, but ``isVirtual()``2211returns ``false`` for it. The reason is that the definition is indeed not2212virtual, it is the property of the prototype!2213 2214Consequently, we must either set the virtual flag for the definition (but then2215we create a malformed AST which the parser would never create), or we import2216the whole redeclaration chain of the function. The most recent version of the2217``ASTImporter`` uses the latter mechanism. We do import all function2218declarations - regardless of whether they are definitions or prototypes - in the order2219as they appear in the "from" context.2220 2221.. One definition2222 2223If we have an existing definition in the "to" context, then we cannot import2224another definition, we will use the existing definition. However, we can import2225prototype(s): we chain the newly imported prototype(s) to the existing2226definition. Whenever we import a new prototype from a third context, that will2227be added to the end of the redeclaration chain. This may result in long2228redeclaration chains in certain cases, e.g., if we import from several2229translation units which include the same header with the prototype.2230 2231.. Squashing prototypes2232 2233To mitigate the problem of long redeclaration chains of free functions, we2234could compare prototypes to see if they have the same properties and if yes2235then we could merge these prototypes. The implementation of squashing of2236prototypes for free functions is future work.2237 2238.. Exception: Cannot have more than 1 prototype in-class2239 2240Chaining functions this way ensures that we do copy all information from the2241source AST. Nonetheless, there is a problem with member functions: While we can2242have many prototypes for free functions, we must have only one prototype for a2243member function.2244 2245.. code-block:: c++2246 2247  void f(); // OK2248  void f(); // OK2249 2250  struct X {2251    void f(); // OK2252    void f(); // ERROR2253  };2254  void X::f() {} // OK2255 2256Thus, prototypes of member functions must be squashed, we cannot just simply2257attach a new prototype to the existing in-class prototype. Consider the2258following contexts:2259 2260.. code-block:: c++2261 2262  // "to" context2263  struct X {2264    void f(); // D02265  };2266 2267.. code-block:: c++2268 2269  // "from" context2270  struct X {2271    void f(); // D12272  };2273  void X::f() {} // D22274 2275When we import the prototype and the definition of ``f`` from the "from"2276context, then the resulting redecl chain will look like this ``D0 -> D2'``,2277where ``D2'`` is the copy of ``D2`` in the "to" context.2278 2279.. Redecl chains of other declarations2280 2281Generally speaking, when we import declarations (like enums and classes) we do2282attach the newly imported declaration to the existing redeclaration chain (if2283there is structural equivalency). We do not import, however, the whole2284redeclaration chain as we do in case of functions. Up till now, we haven't2285found any essential property of forward declarations which is similar to the2286case of the virtual flag in a member function prototype. In the future, this2287may change, though.2288 2289Traversal during the Import2290^^^^^^^^^^^^^^^^^^^^^^^^^^^2291 2292The node specific import mechanisms are implemented in2293``ASTNodeImporter::VisitNode()`` functions, e.g., ``VisitFunctionDecl()``.2294When we import a declaration then first we import everything which is needed to2295call the constructor of that declaration node. Everything which can be set2296later is set after the node is created. For example, in case of  a2297``FunctionDecl`` we first import the declaration context in which the function2298is declared, then we create the ``FunctionDecl`` and only then we import the2299body of the function. This means there are implicit dependencies between AST2300nodes. These dependencies determine the order in which we visit nodes in the2301"from" context. As with the regular graph traversal algorithms like DFS, we2302keep track which nodes we have already visited in2303``ASTImporter::ImportedDecls``. Whenever we create a node then we immediately2304add that to the ``ImportedDecls``. We must not start the import of any other2305declarations before we keep track of the newly created one. This is essential,2306otherwise, we would not be able to handle circular dependencies. To enforce2307this, we wrap all constructor calls of all AST nodes in2308``GetImportedOrCreateDecl()``. This wrapper ensures that all newly created2309declarations are immediately marked as imported; also, if a declaration is2310already marked as imported then we just return its counterpart in the "to"2311context. Consequently, calling a declaration's ``::Create()`` function directly2312would lead to errors, please don't do that!2313 2314Even with the use of ``GetImportedOrCreateDecl()`` there is still a2315probability of having an infinite import recursion if things are imported from2316each other in wrong way. Imagine that during the import of ``A``, the import of2317``B`` is requested before we could create the node for ``A`` (the constructor2318needs a reference to ``B``). And the same could be true for the import of ``B``2319(``A`` is requested to be imported before we could create the node for ``B``).2320In case of the :ref:`templated-described swing <templated>` we take2321extra attention to break the cyclical dependency: we import and set the2322described template only after the ``CXXRecordDecl`` is created. As a best2323practice, before creating the node in the "to" context, avoid importing of2324other nodes which are not needed for the constructor of node ``A``.2325 2326Error Handling2327^^^^^^^^^^^^^^2328 2329Every import function returns with either an ``llvm::Error`` or an2330``llvm::Expected<T>`` object. This enforces to check the return value of the2331import functions. If there was an error during one import then we return with2332that error. (Exception: when we import the members of a class, we collect the2333individual errors with each member and we concatenate them in one Error2334object.) We cache these errors in cases of declarations. During the next import2335call if there is an existing error we just return with that. So, clients of the2336library receive an Error object, which they must check.2337 2338During import of a specific declaration, it may happen that some AST nodes had2339already been created before we recognize an error. In this case, we signal back2340the error to the caller, but the "to" context remains polluted with those nodes2341which had been created. Ideally, those nodes should not have been created, but2342that time we did not know about the error, the error happened later. Since the2343AST is immutable (most of the cases we can't remove existing nodes) we choose2344to mark these nodes as erroneous.2345 2346We cache the errors associated with declarations in the "from" context in2347``ASTImporter::ImportDeclErrors`` and the ones which are associated with the2348"to" context in ``ASTImporterSharedState::ImportErrors``. Note that, there may2349be several ASTImporter objects which import into the same "to" context but from2350different "from" contexts; in this case, they have to share the associated2351errors of the "to" context.2352 2353When an error happens, that propagates through the call stack, through all the2354dependent nodes. However, in case of dependency cycles, this is not enough,2355because we strive to mark the erroneous nodes so clients can act upon. In those2356cases, we have to keep track of the errors for those nodes which are2357intermediate nodes of a cycle.2358 2359An **import path** is the list of the AST nodes which we visit during an Import2360call. If node ``A`` depends on node ``B`` then the path contains an ``A->B``2361edge. From the call stack of the import functions, we can read the very same2362path.2363 2364Now imagine the following AST, where the ``->`` represents dependency in terms2365of the import (all nodes are declarations).2366 2367.. code-block:: text2368 2369  A->B->C->D2370     `->E2371 2372We would like to import A.2373The import behaves like a DFS, so we will visit the nodes in this order: ABCDE.2374During the visitation we will have the following import paths:2375 2376.. code-block:: text2377 2378  A2379  AB2380  ABC2381  ABCD2382  ABC2383  AB2384  ABE2385  AB2386  A2387 2388If during the visit of E there is an error then we set an error for E, then as2389the call stack shrinks for B, then for A:2390 2391.. code-block:: text2392 2393  A2394  AB2395  ABC2396  ABCD2397  ABC2398  AB2399  ABE // Error! Set an error to E2400  AB  // Set an error to B2401  A   // Set an error to A2402 2403However, during the import we could import C and D without any error and they2404are independent of A,B and E. We must not set up an error for C and D. So, at2405the end of the import we have an entry in ``ImportDeclErrors`` for A,B,E but2406not for C,D.2407 2408Now, what happens if there is a cycle in the import path? Let's consider this2409AST:2410 2411.. code-block:: text2412 2413  A->B->C->A2414     `->E2415 2416During the visitation, we will have the below import paths and if during the2417visit of E there is an error then we will set up an error for E,B,A. But what's2418up with C?2419 2420.. code-block:: text2421 2422  A2423  AB2424  ABC2425  ABCA2426  ABC2427  AB2428  ABE // Error! Set an error to E2429  AB  // Set an error to B2430  A   // Set an error to A2431 2432This time we know that both B and C are dependent on A. This means we must set2433up an error for C too. As the call stack reverses back we get to A and we must2434set up an error to all nodes which depend on A (this includes C). But C is no2435longer on the import path, it just had been previously. Such a situation can2436happen only if during the visitation we had a cycle. If we didn't have any2437cycle, then the normal way of passing an Error object through the call stack2438could handle the situation. This is why we must track cycles during the import2439process for each visited declaration.2440 2441Lookup Problems2442^^^^^^^^^^^^^^^2443 2444When we import a declaration from the source context then we check whether we2445already have a structurally equivalent node with the same name in the "to"2446context. If the "from" node is a definition and the found one is also a2447definition, then we do not create a new node, instead, we mark the found node2448as the imported node. If the found definition and the one we want to import2449have the same name but they are structurally in-equivalent, then we have an ODR2450violation in case of C++. If the "from" node is not a definition then we add2451that to the redeclaration chain of the found node. This behaviour is essential2452when we merge ASTs from different translation units which include the same2453header file(s). For example, we want to have only one definition for the class2454template ``std::vector``, even if we included ``<vector>`` in several2455translation units.2456 2457To find a structurally equivalent node we can use the regular C/C++ lookup2458functions: ``DeclContext::noload_lookup()`` and2459``DeclContext::localUncachedLookup()``. These functions do respect the C/C++2460name hiding rules, thus you cannot find certain declarations in a given2461declaration context. For instance, unnamed declarations (anonymous structs),2462non-first ``friend`` declarations and template specializations are hidden. This2463is a problem, because if we use the regular C/C++ lookup then we create2464redundant AST nodes during the merge! Also, having two instances of the same2465node could result in false :ref:`structural in-equivalencies <structural-eq>`2466of other nodes which depend on the duplicated node. Because of these reasons,2467we created a lookup class which has the sole purpose to register all2468declarations, so later they can be looked up by subsequent import requests.2469This is the ``ASTImporterLookupTable`` class. This lookup table should be2470shared amongst the different ``ASTImporter`` instances if they happen to import2471to the very same "to" context. This is why we can use the importer specific2472lookup only via the ``ASTImporterSharedState`` class.2473 2474ExternalASTSource2475~~~~~~~~~~~~~~~~~2476 2477The ``ExternalASTSource`` is an abstract interface associated with the2478``ASTContext`` class. It provides the ability to read the declarations stored2479within a declaration context either for iteration or for name lookup. A2480declaration context with an external AST source may load its declarations2481on-demand. This means that the list of declarations (represented as a linked2482list, the head is ``DeclContext::FirstDecl``) could be empty. However, member2483functions like ``DeclContext::lookup()`` may initiate a load.2484 2485Usually, external sources are associated with precompiled headers. For example,2486when we load a class from a PCH then the members are loaded only if we do want2487to look up something in the class' context.2488 2489In case of LLDB, an implementation of the ``ExternalASTSource`` interface is2490attached to the AST context which is related to the parsed expression. This2491implementation of the ``ExternalASTSource`` interface is realized with the help2492of the ``ASTImporter`` class. This way, LLDB can reuse Clang's parsing2493machinery while synthesizing the underlying AST from the debug data (e.g., from2494DWARF). From the view of the ``ASTImporter`` this means both the "to" and the2495"from" context may have declaration contexts with external lexical storage. If2496a ``DeclContext`` in the "to" AST context has external lexical storage then we2497must take extra attention to work only with the already loaded declarations!2498Otherwise, we would end up with an uncontrolled import process. For instance,2499if we used the regular ``DeclContext::lookup()`` to find the existing2500declarations in the "to" context then the ``lookup()`` call itself would2501initiate a new import while we are in the middle of importing a declaration!2502(By the time we initiate the lookup we haven't registered yet that we already2503started to import the node of the "from" context.) This is why we use2504``DeclContext::noload_lookup()`` instead.2505 2506Class Template Instantiations2507^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2508 2509Different translation units may have class template instantiations with the2510same template arguments, but with a different set of instantiated2511``MethodDecls`` and ``FieldDecls``. Consider the following files:2512 2513.. code-block:: c++2514 2515  // x.h2516  template <typename T>2517  struct X {2518      int a{0}; // FieldDecl with InitListExpr2519      X(char) : a(3) {}     // (1)2520      X(int) {}             // (2)2521  };2522 2523  // foo.cpp2524  void foo() {2525      // ClassTemplateSpec with ctor (1): FieldDecl without InitlistExpr2526      X<char> xc('c');2527  }2528 2529  // bar.cpp2530  void bar() {2531      // ClassTemplateSpec with ctor (2): FieldDecl WITH InitlistExpr2532      X<char> xc(1);2533  }2534 2535In ``foo.cpp`` we use the constructor with number ``(1)``, which explicitly2536initializes the member ``a`` to ``3``, thus the ``InitListExpr`` ``{0}`` is not2537used here and the AST node is not instantiated. However, in the case of2538``bar.cpp`` we use the constructor with number ``(2)``, which does not2539explicitly initialize the ``a`` member, so the default ``InitListExpr`` is2540needed and thus instantiated. When we merge the AST of ``foo.cpp`` and2541``bar.cpp`` we must create an AST node for the class template instantiation of2542``X<char>`` which has all the required nodes. Therefore, when we find an2543existing ``ClassTemplateSpecializationDecl`` then we merge the fields of the2544``ClassTemplateSpecializationDecl`` in the "from" context in a way that the2545``InitListExpr`` is copied if not existent yet. The same merge mechanism should2546be done in the cases of instantiated default arguments and exception2547specifications of functions.2548 2549.. _visibility:2550 2551Visibility of Declarations2552^^^^^^^^^^^^^^^^^^^^^^^^^^2553 2554During import of a global variable with external visibility, the lookup will2555find variables (with the same name) but with static visibility (linkage).2556Clearly, we cannot put them into the same redeclaration chain. The same is true2557the in case of functions. Also, we have to take care of other kinds of2558declarations like enums, classes, etc. if they are in anonymous namespaces.2559Therefore, we filter the lookup results and consider only those which have the2560same visibility as the declaration we currently import.2561 2562We consider two declarations in two anonymous namespaces to have the same2563visibility only if they are imported from the same AST context.2564 2565Strategies to Handle Conflicting Names2566^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2567 2568During the import we lookup existing declarations with the same name. We filter2569the lookup results based on their :ref:`visibility <visibility>`. If any of the2570found declarations are not structurally equivalent then we bumped to a name2571conflict error (ODR violation in C++). In this case, we return with an2572``Error`` and we set up the ``Error`` object for the declaration. However, some2573clients of the ``ASTImporter`` may require a different, perhaps less2574conservative and more liberal error handling strategy.2575 2576E.g., static analysis clients may benefit if the node is created even if there2577is a name conflict. During the CTU analysis of certain projects, we recognized2578that there are global declarations which collide with declarations from other2579translation units, but they are not referenced outside from their translation2580unit. These declarations should be in an unnamed namespace ideally. If we treat2581these collisions liberally then CTU analysis can find more results. Note, the2582feature to be able to choose between name conflict handling strategies is still an2583ongoing work.2584 2585.. _CFG:2586 2587The ``CFG`` class2588-----------------2589 2590The ``CFG`` class is designed to represent a source-level control-flow graph2591for a single statement (``Stmt*``).  Typically instances of ``CFG`` are2592constructed for function bodies (usually an instance of ``CompoundStmt``), but2593can also be instantiated to represent the control-flow of any class that2594subclasses ``Stmt``, which includes simple expressions.  Control-flow graphs2595are especially useful for performing `flow- or path-sensitive2596<https://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities>`_ program2597analyses on a given function.2598 2599Basic Blocks2600^^^^^^^^^^^^2601 2602Concretely, an instance of ``CFG`` is a collection of basic blocks.  Each basic2603block is an instance of ``CFGBlock``, which simply contains an ordered sequence2604of ``Stmt*`` (each referring to statements in the AST).  The ordering of2605statements within a block indicates unconditional flow of control from one2606statement to the next.  :ref:`Conditional control-flow2607<ConditionalControlFlow>` is represented using edges between basic blocks.  The2608statements within a given ``CFGBlock`` can be traversed using the2609``CFGBlock::*iterator`` interface.2610 2611A ``CFG`` object owns the instances of ``CFGBlock`` within the control-flow2612graph it represents.  Each ``CFGBlock`` within a CFG is also uniquely numbered2613(accessible via ``CFGBlock::getBlockID()``).  Currently the number is based on2614the ordering the blocks were created, but no assumptions should be made on how2615``CFGBlocks`` are numbered other than their numbers are unique and that they2616are numbered from 0..N-1 (where N is the number of basic blocks in the CFG).2617 2618Entry and Exit Blocks2619^^^^^^^^^^^^^^^^^^^^^2620 2621Each instance of ``CFG`` contains two special blocks: an *entry* block2622(accessible via ``CFG::getEntry()``), which has no incoming edges, and an2623*exit* block (accessible via ``CFG::getExit()``), which has no outgoing edges.2624Neither block contains any statements, and they serve the role of providing a2625clear entrance and exit for a body of code such as a function body.  The2626presence of these empty blocks greatly simplifies the implementation of many2627analyses built on top of CFGs.2628 2629.. _ConditionalControlFlow:2630 2631Conditional Control-Flow2632^^^^^^^^^^^^^^^^^^^^^^^^2633 2634Conditional control-flow (such as those induced by if-statements and loops) is2635represented as edges between ``CFGBlocks``.  Because different C language2636constructs can induce control-flow, each ``CFGBlock`` also records an extra2637``Stmt*`` that represents the *terminator* of the block.  A terminator is2638simply the statement that caused the control-flow, and is used to identify the2639nature of the conditional control-flow between blocks.  For example, in the2640case of an if-statement, the terminator refers to the ``IfStmt`` object in the2641AST that represented the given branch.2642 2643To illustrate, consider the following code example:2644 2645.. code-block:: c++2646 2647  int foo(int x) {2648    x = x + 1;2649    if (x > 2)2650      x++;2651    else {2652      x += 2;2653      x *= 2;2654    }2655 2656    return x;2657  }2658 2659After invoking the parser+semantic analyzer on this code fragment, the AST of2660the body of ``foo`` is referenced by a single ``Stmt*``.  We can then construct2661an instance of ``CFG`` representing the control-flow graph of this function2662body by single call to a static class method:2663 2664.. code-block:: c++2665 2666  Stmt *FooBody = ...2667  std::unique_ptr<CFG> FooCFG = CFG::buildCFG(FooBody);2668 2669Along with providing an interface to iterate over its ``CFGBlocks``, the2670``CFG`` class also provides methods that are useful for debugging and2671visualizing CFGs.  For example, the method ``CFG::dump()`` dumps a2672pretty-printed version of the CFG to standard error.  This is especially useful2673when one is using a debugger such as gdb.  For example, here is the output of2674``FooCFG->dump()``:2675 2676.. code-block:: text2677 2678 [ B5 (ENTRY) ]2679    Predecessors (0):2680    Successors (1): B42681 2682 [ B4 ]2683    1: x = x + 12684    2: (x > 2)2685    T: if [B4.2]2686    Predecessors (1): B52687    Successors (2): B3 B22688 2689 [ B3 ]2690    1: x++2691    Predecessors (1): B42692    Successors (1): B12693 2694 [ B2 ]2695    1: x += 22696    2: x *= 22697    Predecessors (1): B42698    Successors (1): B12699 2700 [ B1 ]2701    1: return x;2702    Predecessors (2): B2 B32703    Successors (1): B02704 2705 [ B0 (EXIT) ]2706    Predecessors (1): B12707    Successors (0):2708 2709For each block, the pretty-printed output displays for each block the number of2710*predecessor* blocks (blocks that have outgoing control-flow to the given2711block) and *successor* blocks (blocks that have control-flow that have incoming2712control-flow from the given block).  We can also clearly see the special entry2713and exit blocks at the beginning and end of the pretty-printed output.  For the2714entry block (block B5), the number of predecessor blocks is 0, while for the2715exit block (block B0) the number of successor blocks is 0.2716 2717The most interesting block here is B4, whose outgoing control-flow represents2718the branching caused by the sole if-statement in ``foo``.  Of particular2719interest is the second statement in the block, ``(x > 2)``, and the terminator,2720printed as ``if [B4.2]``.  The second statement represents the evaluation of2721the condition of the if-statement, which occurs before the actual branching of2722control-flow.  Within the ``CFGBlock`` for B4, the ``Stmt*`` for the second2723statement refers to the actual expression in the AST for ``(x > 2)``.  Thus2724pointers to subclasses of ``Expr`` can appear in the list of statements in a2725block, and not just subclasses of ``Stmt`` that refer to proper C statements.2726 2727The terminator of block B4 is a pointer to the ``IfStmt`` object in the AST.2728The pretty-printer outputs ``if [B4.2]`` because the condition expression of2729the if-statement has an actual place in the basic block, and thus the2730terminator is essentially *referring* to the expression that is the second2731statement of block B4 (i.e., B4.2).  In this manner, conditions for2732control-flow (which also includes conditions for loops and switch statements)2733are hoisted into the actual basic block.2734 2735.. Implicit Control-Flow2736.. ^^^^^^^^^^^^^^^^^^^^^2737 2738.. A key design principle of the ``CFG`` class was to not require any2739.. transformations to the AST in order to represent control-flow.  Thus the2740.. ``CFG`` does not perform any "lowering" of the statements in an AST: loops2741.. are not transformed into guarded gotos, short-circuit operations are not2742.. converted to a set of if-statements, and so on.2743 2744Constant Folding in the Clang AST2745---------------------------------2746 2747There are several places where constants and constant folding matter a lot to2748the Clang front-end.  First, in general, we prefer the AST to retain the source2749code as close to how the user wrote it as possible.  This means that if they2750wrote "``5+4``", we want to keep the addition and two constants in the AST, we2751don't want to fold to "``9``".  This means that constant folding in various2752ways turns into a tree walk that needs to handle the various cases.2753 2754However, there are places in both C and C++ that require constants to be2755folded.  For example, the C standard defines what an "integer constant2756expression" (i-c-e) is with very precise and specific requirements.  The2757language then requires i-c-e's in a lot of places (for example, the size of a2758bitfield, the value for a case statement, etc).  For these, we have to be able2759to constant fold the constants, to do semantic checks (e.g., verify bitfield2760size is non-negative and that case statements aren't duplicated).  We aim for2761Clang to be very pedantic about this, diagnosing cases when the code does not2762use an i-c-e where one is required, but accepting the code unless running with2763``-pedantic-errors``.2764 2765Things get a little bit more tricky when it comes to compatibility with2766real-world source code.  Specifically, GCC has historically accepted a huge2767superset of expressions as i-c-e's, and a lot of real world code depends on2768this unfortunate accident of history (including, e.g., the glibc system2769headers).  GCC accepts anything its "fold" optimizer is capable of reducing to2770an integer constant, which means that the definition of what it accepts changes2771as its optimizer does.  One example is that GCC accepts things like "``case2772X-X:``" even when ``X`` is a variable, because it can fold this to 0.2773 2774Another issue are how constants interact with the extensions we support, such2775as ``__builtin_constant_p``, ``__builtin_inf``, ``__extension__`` and many2776others.  C99 obviously does not specify the semantics of any of these2777extensions, and the definition of i-c-e does not include them.  However, these2778extensions are often used in real code, and we have to have a way to reason2779about them.2780 2781Finally, this is not just a problem for semantic analysis.  The code generator2782and other clients have to be able to fold constants (e.g., to initialize global2783variables) and have to handle a superset of what C99 allows.  Further, these2784clients can benefit from extended information.  For example, we know that2785"``foo() || 1``" always evaluates to ``true``, but we can't replace the2786expression with ``true`` because it has side effects.2787 2788Implementation Approach2789^^^^^^^^^^^^^^^^^^^^^^^2790 2791After trying several different approaches, we've finally converged on a design2792(Note, at the time of this writing, not all of this has been implemented,2793consider this a design goal!).  Our basic approach is to define a single2794recursive evaluation method (``Expr::Evaluate``), which is implemented2795in ``AST/ExprConstant.cpp``.  Given an expression with "scalar" type (integer,2796fp, complex, or pointer) this method returns the following information:2797 2798* Whether the expression is an integer constant expression, a general constant2799  that was folded but has no side effects, a general constant that was folded2800  but that does have side effects, or an uncomputable/unfoldable value.2801* If the expression was computable in any way, this method returns the2802  ``APValue`` for the result of the expression.2803* If the expression is not evaluatable at all, this method returns information2804  on one of the problems with the expression.  This includes a2805  ``SourceLocation`` for where the problem is, and a diagnostic ID that explains2806  the problem.  The diagnostic should have ``ERROR`` type.2807* If the expression is not an integer constant expression, this method returns2808  information on one of the problems with the expression.  This includes a2809  ``SourceLocation`` for where the problem is, and a diagnostic ID that2810  explains the problem.  The diagnostic should have ``EXTENSION`` type.2811 2812This information gives various clients the flexibility that they want, and we2813will eventually have some helper methods for various extensions.  For example,2814``Sema`` should have a ``Sema::VerifyIntegerConstantExpression`` method, which2815calls ``Evaluate`` on the expression.  If the expression is not foldable, the2816error is emitted, and it would return ``true``.  If the expression is not an2817i-c-e, the ``EXTENSION`` diagnostic is emitted.  Finally it would return2818``false`` to indicate that the AST is OK.2819 2820Other clients can use the information in other ways, for example, codegen can2821just use expressions that are foldable in any way.2822 2823Extensions2824^^^^^^^^^^2825 2826This section describes how some of the various extensions Clang supports2827interacts with constant evaluation:2828 2829* ``__extension__``: The expression form of this extension causes any2830  evaluatable subexpression to be accepted as an integer constant expression.2831* ``__builtin_constant_p``: This returns true (as an integer constant2832  expression) if the operand evaluates to either a numeric value (that is, not2833  a pointer cast to integral type) of integral, enumeration, floating or2834  complex type, or if it evaluates to the address of the first character of a2835  string literal (possibly cast to some other type).  As a special case, if2836  ``__builtin_constant_p`` is the (potentially parenthesized) condition of a2837  conditional operator expression ("``?:``"), only the true side of the2838  conditional operator is considered, and it is evaluated with full constant2839  folding.2840* ``__builtin_choose_expr``: The condition is required to be an integer2841  constant expression, but we accept any constant as an "extension of an2842  extension".  This only evaluates one operand depending on which way the2843  condition evaluates.2844* ``__builtin_classify_type``: This always returns an integer constant2845  expression.2846* ``__builtin_inf, nan, ...``: These are treated just like a floating-point2847  literal.2848* ``__builtin_abs, copysign, ...``: These are constant folded as general2849  constant expressions.2850* ``__builtin_strlen`` and ``strlen``: These are constant folded as integer2851  constant expressions if the argument is a string literal.2852 2853.. _Sema:2854 2855The Sema Library2856================2857 2858This library is called by the :ref:`Parser library <Parser>` during parsing to2859do semantic analysis of the input.  For valid programs, Sema builds an AST for2860parsed constructs.2861 2862 2863Concept Satisfaction Checking and Subsumption2864---------------------------------------------2865 2866As per the C++ standard, constraints are `normalized <https://eel.is/c++draft/temp.constr.normal>`_2867and the normal form is used both for subsumption, and constraint checking.2868Both depend on a parameter mapping that substitutes lazily. In particular,2869we should not substitute in unused arguments.2870 2871Clang follows the order of operations prescribed by the standard.2872 2873Normalization happens prior to satisfaction and subsumption2874and is handled by ``NormalizedConstraint``.2875 2876Clang preserves in the normalized form intermediate concept-ids2877(``ConceptIdConstraint``) This is used for diagnostics only and no substitution2878happens in a ConceptIdConstraint if its expression is satisfied.2879 2880The normal form of the associated constraints of a declaration is cached in2881Sema::NormalizationCache such that it is only computed once.2882 2883A ``NormalizedConstraint`` is a recursive data structure, where each node2884contains a parameter mapping, represented by the indexes of all parameter2885being used.2886 2887Checking satisfaction is done by ``ConstraintSatisfactionChecker``, recursively2888walking ``NormalizedConstraint``. At each level, we substitute the outermost2889level of the template arguments referenced in the parameter mapping of a2890normalized expression (``MultiLevelTemplateArgumentList``).2891 2892For the following example,2893 2894.. code-block:: c++2895 2896  template <typename T>2897  concept A = __is_same(T, int);2898 2899  template <typename U>2900  concept B = A<U> && __is_same(U, int);2901 2902The normal form of B is2903 2904.. code-block:: c++2905 2906    __is_same(T, int) /*T->U, innermost level*/2907 && __is_same(U, int) {U->U} /*T->U, outermost level*/2908 2909After substitution in the mapping, we substitute in the constraint expression2910using that copy of the ``MultiLevelTemplateArgumentList``, and then evaluate it.2911 2912Because this is expensive, it is cached in2913``UnsubstitutedConstraintSatisfactionCache``.2914 2915Any error during satisfaction is recorded in ``ConstraintSatisfaction``.2916for nested requirements, ``ConstraintSatisfaction`` is stored (including2917diagnostics) in the AST, which is something we might want to improve.2918 2919When an atomic constraint is not satisfied, we try to substitute into any2920enclosing concept-id using the same mechanism described above, for2921diagnostics purpose, and inject that in the ``ConstraintSatisfaction``.2922 2923.. _CodeGen:2924 2925The CodeGen Library2926===================2927 2928CodeGen takes an :ref:`AST <AST>` as input and produces `LLVM IR code2929<//llvm.org/docs/LangRef.html>`_ from it.2930 2931How to change Clang2932===================2933 2934How to add an attribute2935-----------------------2936Attributes are a form of metadata that can be attached to a program construct,2937allowing the programmer to pass semantic information along to the compiler for2938various uses. For example, attributes may be used to alter the code generation2939for a program construct, or to provide extra semantic information for static2940analysis. This document explains how to add a custom attribute to Clang.2941Documentation on existing attributes can be found `here2942<//clang.llvm.org/docs/AttributeReference.html>`_.2943 2944Attribute Basics2945^^^^^^^^^^^^^^^^2946Attributes in Clang are handled in three stages: parsing into a parsed attribute2947representation, conversion from a parsed attribute into a semantic attribute,2948and then the semantic handling of the attribute.2949 2950Parsing of the attribute is determined by the various syntactic forms attributes2951can take, such as GNU, C++11, and Microsoft style attributes, as well as other2952information provided by the table definition of the attribute. Ultimately, the2953parsed representation of an attribute object is a ``ParsedAttr`` object.2954These parsed attributes chain together as a list of parsed attributes attached2955to a declarator or declaration specifier. The parsing of attributes is handled2956automatically by Clang, except for attributes spelled as so-called “custom”2957keywords. When implementing a custom keyword attribute, the parsing of the2958keyword and creation of the ``ParsedAttr`` object must be done manually.2959 2960Eventually, ``Sema::ProcessDeclAttributeList()`` is called with a ``Decl`` and2961a ``ParsedAttr``, at which point the parsed attribute can be transformed2962into a semantic attribute. The process by which a parsed attribute is converted2963into a semantic attribute depends on the attribute definition and semantic2964requirements of the attribute. The end result, however, is that the semantic2965attribute object is attached to the ``Decl`` object, and can be obtained by a2966call to ``Decl::getAttr<T>()``. Similarly, for statement attributes,2967``Sema::ProcessStmtAttributes()`` is called with a ``Stmt`` a list of2968``ParsedAttr`` objects to be converted into a semantic attribute.2969 2970The structure of the semantic attribute is also governed by the attribute2971definition given in Attr.td. This definition is used to automatically generate2972functionality used for the implementation of the attribute, such as a class2973derived from ``clang::Attr``, information for the parser to use, automated2974semantic checking for some attributes, etc.2975 2976 2977``include/clang/Basic/Attr.td``2978^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2979The first step to adding a new attribute to Clang is to add its definition to2980`include/clang/Basic/Attr.td2981<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/Attr.td>`_.2982This tablegen definition must derive from the ``Attr`` (tablegen, not2983semantic) type, or one of its derivatives. Most attributes will derive from the2984``InheritableAttr`` type, which specifies that the attribute can be inherited by2985later redeclarations of the ``Decl`` it is associated with.2986``InheritableParamAttr`` is similar to ``InheritableAttr``, except that the2987attribute is written on a parameter instead of a declaration. If the attribute2988applies to statements, it should inherit from ``StmtAttr``. If the attribute is2989intended to apply to a type instead of a declaration, such an attribute should2990derive from ``TypeAttr``, and will generally not be given an AST representation.2991(Note that this document does not cover the creation of type attributes.) An2992attribute that inherits from ``IgnoredAttr`` is parsed, but will generate an2993ignored attribute diagnostic when used, which may be useful when an attribute is2994supported by another vendor but not supported by clang.2995 2996The definition will specify several key pieces of information, such as the2997semantic name of the attribute, the spellings the attribute supports, the2998arguments the attribute expects, and more. Most members of the ``Attr`` tablegen2999type do not require definitions in the derived definition as the default3000suffice. However, every attribute must specify at least a spelling list, a3001subject list, and a documentation list.3002 3003Spellings3004~~~~~~~~~3005All attributes are required to specify a spelling list that denotes the ways in3006which the attribute can be spelled. For instance, a single semantic attribute3007may have a keyword spelling, as well as a C++11 spelling and a GNU spelling. An3008empty spelling list is also permissible and may be useful for attributes which3009are created implicitly. The following spellings are accepted:3010 3011  ==================  =========================================================3012  Spelling            Description3013  ==================  =========================================================3014  ``GNU``             Spelled with a GNU-style ``__attribute__((attr))``3015                      syntax and placement.3016  ``CXX11``           Spelled with a C++-style ``[[attr]]`` syntax with an3017                      optional vendor-specific namespace.3018  ``C23``             Spelled with a C-style ``[[attr]]`` syntax with an3019                      optional vendor-specific namespace.3020  ``Declspec``        Spelled with a Microsoft-style ``__declspec(attr)``3021                      syntax.3022  ``CustomKeyword``   The attribute is spelled as a keyword, and requires3023                      custom parsing.3024  ``RegularKeyword``  The attribute is spelled as a keyword. It can be3025                      used in exactly the places that the standard3026                      ``[[attr]]`` syntax can be used, and appertains to3027                      exactly the same thing that a standard attribute3028                      would appertain to. Lexing and parsing of the keyword3029                      are handled automatically.3030  ``GCC``             Specifies two or three spellings: the first is a3031                      GNU-style spelling, the second is a C++-style spelling3032                      with the ``gnu`` namespace, and the third is an optional3033                      C-style spelling with the ``gnu`` namespace. Attributes3034                      should only specify this spelling for attributes3035                      supported by GCC.3036  ``Clang``           Specifies two or three spellings: the first is a3037                      GNU-style spelling, the second is a C++-style spelling3038                      with the ``clang`` namespace, and the third is an3039                      optional C-style spelling with the ``clang`` namespace.3040                      By default, a C-style spelling is provided.3041  ``Pragma``          The attribute is spelled as a ``#pragma``, and requires3042                      custom processing within the preprocessor. If the3043                      attribute is meant to be used by Clang, it should3044                      set the namespace to ``"clang"``. Note that this3045                      spelling is not used for declaration attributes.3046  ==================  =========================================================3047 3048The C++ standard specifies that “any [non-standard attribute] that is not3049recognized by the implementation is ignored” (``[dcl.attr.grammar]``).3050The rule for C is similar. This makes ``CXX11`` and ``C23`` spellings3051unsuitable for attributes that affect the type system, that change the3052binary interface of the code, or that have other similar semantic meaning.3053 3054``RegularKeyword`` provides an alternative way of spelling such attributes.3055It reuses the production rules for standard attributes, but it applies them3056to plain keywords rather than to ``[[…]]`` sequences. Compilers that don't3057recognize the keyword are likely to report an error of some kind.3058 3059For example, the ``ArmStreaming`` function type attribute affects3060both the type system and the binary interface of the function.3061It cannot therefore be spelled ``[[arm::streaming]]``, since compilers3062that don't understand ``arm::streaming`` would ignore it and miscompile3063the code. ``ArmStreaming`` is instead spelled ``__arm_streaming``, but it3064can appear wherever a hypothetical ``[[arm::streaming]]`` could appear.3065 3066Subjects3067~~~~~~~~3068Attributes appertain to one or more subjects. If the attribute attempts to3069attach to a subject that is not in the subject list, a diagnostic is issued3070automatically. Whether the diagnostic is a warning or an error depends on how3071the attribute's ``SubjectList`` is defined, but the default behavior is to warn.3072The diagnostics displayed to the user are automatically determined based on the3073subjects in the list, but a custom diagnostic parameter can also be specified in3074the ``SubjectList``. The diagnostics generated for subject list violations are3075calculated automatically or specified by the subject list itself. If a3076previously unused Decl node is added to the ``SubjectList``, the logic used to3077automatically determine the diagnostic parameter in `utils/TableGen/ClangAttrEmitter.cpp3078<https://github.com/llvm/llvm-project/blob/main/clang/utils/TableGen/ClangAttrEmitter.cpp>`_3079may need to be updated.3080 3081By default, all subjects in the SubjectList must either be a Decl node defined3082in ``DeclNodes.td``, or a statement node defined in ``StmtNodes.td``. However,3083more complex subjects can be created by creating a ``SubsetSubject`` object.3084Each such object has a base subject which it appertains to (which must be a3085Decl or Stmt node, and not a SubsetSubject node), and some custom code which is3086called when determining whether an attribute appertains to the subject. For3087instance, a ``NonBitField`` SubsetSubject appertains to a ``FieldDecl``, and3088tests whether the given FieldDecl is a bit field. When a SubsetSubject is3089specified in a SubjectList, a custom diagnostic parameter must also be provided.3090 3091Diagnostic checking for attribute subject lists for declaration and statement3092attributes is automated except when ``HasCustomParsing`` is set to ``1``.3093 3094Documentation3095~~~~~~~~~~~~~3096All attributes must have some form of documentation associated with them.3097Documentation is table generated on the public web server by a server-side3098process that runs daily. Generally, the documentation for an attribute is a3099stand-alone definition in `include/clang/Basic/AttrDocs.td3100<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/AttrDocs.td>`_3101that is named after the attribute being documented.3102 3103If the attribute is not for public consumption, or is an implicitly-created3104attribute that has no visible spelling, the documentation list can specify the3105``InternalOnly`` object. Otherwise, the attribute should have its documentation3106added to AttrDocs.td.3107 3108Documentation derives from the ``Documentation`` tablegen type. All derived3109types must specify a documentation category and the actual documentation itself.3110Additionally, it can specify a custom heading for the attribute, though a3111default heading will be chosen when possible.3112 3113There are four predefined documentation categories: ``DocCatFunction`` for3114attributes that appertain to function-like subjects, ``DocCatVariable`` for3115attributes that appertain to variable-like subjects, ``DocCatType`` for type3116attributes, and ``DocCatStmt`` for statement attributes. A custom documentation3117category should be used for groups of attributes with similar functionality.3118Custom categories are good for providing overview information for the attributes3119grouped under it. For instance, the consumed annotation attributes define a3120custom category, ``DocCatConsumed``, that explains what consumed annotations are3121at a high level.3122 3123Documentation content (whether it is for an attribute or a category) is written3124using reStructuredText (RST) syntax.3125 3126After writing the documentation for the attribute, it should be locally tested3127to ensure that there are no issues generating the documentation on the server.3128Local testing requires a fresh build of clang-tblgen. To generate the attribute3129documentation, execute the following command::3130 3131  clang-tblgen -gen-attr-docs -I /path/to/clang/include /path/to/clang/include/clang/Basic/Attr.td -o /path/to/clang/docs/AttributeReference.rst3132 3133When testing locally, *do not* commit changes to ``AttributeReference.rst``.3134This file is generated by the server automatically, and any changes made to this3135file will be overwritten.3136 3137Arguments3138~~~~~~~~~3139Attributes may optionally specify a list of arguments that can be passed to the3140attribute. Attribute arguments specify both the parsed form and the semantic3141form of the attribute. For example, if ``Args`` is3142``[StringArgument<"Arg1">, IntArgument<"Arg2">]`` then3143``__attribute__((myattribute("Hello", 3)))`` will be a valid use; it requires3144two arguments while parsing, and the Attr subclass' constructor for the3145semantic attribute will require a string and integer argument.3146 3147All arguments have a name and a flag that specifies whether the argument is3148optional. The associated C++ type of the argument is determined by the argument3149definition type. If the existing argument types are insufficient, new types can3150be created, but it requires modifying `utils/TableGen/ClangAttrEmitter.cpp3151<https://github.com/llvm/llvm-project/blob/main/clang/utils/TableGen/ClangAttrEmitter.cpp>`_3152to properly support the type.3153 3154Other Properties3155~~~~~~~~~~~~~~~~3156The ``Attr`` definition has other members which control the behavior of the3157attribute. Many of them are special-purpose and beyond the scope of this3158document, however a few deserve mention.3159 3160If the parsed form of the attribute is more complex, or differs from the3161semantic form, the ``HasCustomParsing`` bit can be set to ``1`` for the class,3162and the parsing code in `Parser::ParseGNUAttributeArgs()3163<https://github.com/llvm/llvm-project/blob/main/clang/lib/Parse/ParseDecl.cpp>`_3164can be updated for the special case. Note that this only applies to arguments3165with a GNU spelling -- attributes with a __declspec spelling currently ignore3166this flag and are handled by ``Parser::ParseMicrosoftDeclSpec``.3167 3168Note that setting this member to 1 will opt out of common attribute semantic3169handling, requiring extra implementation efforts to ensure the attribute3170appertains to the appropriate subject, etc.3171 3172If the attribute should not be propagated from a template declaration to an3173instantiation of the template, set the ``Clone`` member to 0. By default, all3174attributes will be cloned to template instantiations.3175 3176Attributes that do not require an AST node should set the ``ASTNode`` field to3177``0`` to avoid polluting the AST. Note that anything inheriting from3178``TypeAttr`` or ``IgnoredAttr`` automatically do not generate an AST node. All3179other attributes generate an AST node by default. The AST node is the semantic3180representation of the attribute.3181 3182The ``LangOpts`` field specifies a list of language options required by the3183attribute.  For instance, all of the CUDA-specific attributes specify ``[CUDA]``3184for the ``LangOpts`` field, and when the CUDA language option is not enabled, an3185"attribute ignored" warning diagnostic is emitted. Since language options are3186not table generated nodes, new language options must be created manually and3187should specify the spelling used by ``LangOptions`` class.3188 3189Custom accessors can be generated for an attribute based on the spelling list3190for that attribute. For instance, if an attribute has two different spellings:3191'Foo' and 'Bar', accessors can be created:3192``[Accessor<"isFoo", [GNU<"Foo">]>, Accessor<"isBar", [GNU<"Bar">]>]``3193These accessors will be generated on the semantic form of the attribute,3194accepting no arguments and returning a ``bool``.3195 3196Attributes that do not require custom semantic handling should set the3197``SemaHandler`` field to ``0``. Note that anything inheriting from3198``IgnoredAttr`` automatically do not get a semantic handler. All other3199attributes are assumed to use a semantic handler by default. Attributes3200without a semantic handler are not given a parsed attribute ``Kind`` enumerator.3201 3202"Simple" attributes, that require no custom semantic processing aside from what3203is automatically provided, should set the ``SimpleHandler`` field to ``1``.3204 3205Target-specific attributes may share a spelling with other attributes in3206different targets. For instance, the ARM and MSP430 targets both have an3207attribute spelled ``GNU<"interrupt">``, but with different parsing and semantic3208requirements. To support this feature, an attribute inheriting from3209``TargetSpecificAttribute`` may specify a ``ParseKind`` field. This field3210should be the same value between all arguments sharing a spelling, and3211corresponds to the parsed attribute's ``Kind`` enumerator. This allows3212attributes to share a parsed attribute kind, but have distinct semantic3213attribute classes. For instance, ``ParsedAttr`` is the shared3214parsed attribute kind, but ARMInterruptAttr and MSP430InterruptAttr are the3215semantic attributes generated.3216 3217By default, attribute arguments are parsed in an evaluated context. If the3218arguments for an attribute should be parsed in an unevaluated context (akin to3219the way the argument to a ``sizeof`` expression is parsed), set3220``ParseArgumentsAsUnevaluated`` to ``1``.3221 3222If additional functionality is desired for the semantic form of the attribute,3223the ``AdditionalMembers`` field specifies code to be copied verbatim into the3224semantic attribute class object, with ``public`` access.3225 3226If two or more attributes cannot be used in combination on the same declaration3227or statement, a ``MutualExclusions`` definition can be supplied to automatically3228generate diagnostic code. This will disallow the attribute combinations3229regardless of spellings used. Additionally, it will diagnose combinations within3230the same attribute list, different attribute list, and redeclarations, as3231appropriate.3232 3233Boilerplate3234^^^^^^^^^^^3235All semantic processing of declaration attributes happens in `lib/Sema/SemaDeclAttr.cpp3236<https://github.com/llvm/llvm-project/blob/main/clang/lib/Sema/SemaDeclAttr.cpp>`_,3237and generally starts in the ``ProcessDeclAttribute()`` function. If the3238attribute has the ``SimpleHandler`` field set to ``1`` then the function to3239process the attribute will be automatically generated, and nothing needs to be3240done here. Otherwise, write a new ``handleYourAttr()`` function, and add that to3241the switch statement. Please do not implement handling logic directly in the3242``case`` for the attribute.3243 3244Unless otherwise specified by the attribute definition, common semantic checking3245of the parsed attribute is handled automatically. This includes diagnosing3246parsed attributes that do not appertain to the given ``Decl`` or ``Stmt``,3247ensuring the correct minimum number of arguments are passed, etc.3248 3249If the attribute adds additional warnings, define a ``DiagGroup`` in3250`include/clang/Basic/DiagnosticGroups.td3251<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/DiagnosticGroups.td>`_3252named after the attribute's ``Spelling`` with "_"s replaced by "-"s. If there3253is only a single diagnostic, it is permissible to use ``InGroup<DiagGroup<"your-attribute">>``3254directly in `DiagnosticSemaKinds.td3255<https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Basic/DiagnosticSemaKinds.td>`_3256 3257All semantic diagnostics generated for your attribute, including automatically-3258generated ones (such as subjects and argument counts), should have a3259corresponding test case.3260 3261Semantic handling3262^^^^^^^^^^^^^^^^^3263Most attributes are implemented to have some effect on the compiler. For3264instance, to modify the way code is generated, or to add extra semantic checks3265for an analysis pass, etc. Having added the attribute definition and conversion3266to the semantic representation for the attribute, what remains is to implement3267the custom logic requiring use of the attribute.3268 3269The ``clang::Decl`` object can be queried for the presence or absence of an3270attribute using ``hasAttr<T>()``. To obtain a pointer to the semantic3271representation of the attribute, ``getAttr<T>`` may be used.3272 3273The ``clang::AttributedStmt`` object can  be queried for the presence or absence3274of an attribute by calling ``getAttrs()`` and looping over the list of3275attributes.3276 3277How to add an expression or statement3278-------------------------------------3279 3280Expressions and statements are one of the most fundamental constructs within a3281compiler, because they interact with many different parts of the AST, semantic3282analysis, and IR generation.  Therefore, adding a new expression or statement3283kind into Clang requires some care.  The following list details the various3284places in Clang where an expression or statement needs to be introduced, along3285with patterns to follow to ensure that the new expression or statement works3286well across all of the C languages.  We focus on expressions, but statements3287are similar.3288 3289#. Introduce parsing actions into the parser.  Recursive-descent parsing is3290   mostly self-explanatory, but there are a few things that are worth keeping3291   in mind:3292 3293   * Keep as much source location information as possible! You'll want it later3294     to produce great diagnostics and support Clang's various features that map3295     between source code and the AST.3296   * Write tests for all of the "bad" parsing cases, to make sure your recovery3297     is good.  If you have matched delimiters (e.g., parentheses, square3298     brackets, etc.), use ``Parser::BalancedDelimiterTracker`` to give nice3299     diagnostics when things go wrong.3300 3301#. Introduce semantic analysis actions into ``Sema``.  Semantic analysis should3302   always involve two functions: an ``ActOnXXX`` function that will be called3303   directly from the parser, and a ``BuildXXX`` function that performs the3304   actual semantic analysis and will (eventually!) build the AST node.  It's3305   fairly common for the ``ActOnXXX`` function to do very little (often just3306   some minor translation from the parser's representation to ``Sema``'s3307   representation of the same thing), but the separation is still important:3308   C++ template instantiation, for example, should always call the ``BuildXXX``3309   variant.  Several notes on semantic analysis before we get into construction3310   of the AST:3311 3312   * Your expression probably involves some types and some subexpressions.3313     Make sure to fully check that those types, and the types of those3314     subexpressions, meet your expectations.  Add implicit conversions where3315     necessary to make sure that all of the types line up exactly the way you3316     want them.  Write extensive tests to check that you're getting good3317     diagnostics for mistakes and that you can use various forms of3318     subexpressions with your expression.3319   * When type-checking a type or subexpression, make sure to first check3320     whether the type is "dependent" (``Type::isDependentType()``) or whether a3321     subexpression is type-dependent (``Expr::isTypeDependent()``).  If any of3322     these return ``true``, then you're inside a template and you can't do much3323     type-checking now.  That's normal, and your AST node (when you get there)3324     will have to deal with this case.  At this point, you can write tests that3325     use your expression within templates, but don't try to instantiate the3326     templates.3327   * For each subexpression, be sure to call ``Sema::CheckPlaceholderExpr()``3328     to deal with "weird" expressions that don't behave well as subexpressions.3329     Then, determine whether you need to perform lvalue-to-rvalue conversions3330     (``Sema::DefaultLvalueConversions``) or the usual unary conversions3331     (``Sema::UsualUnaryConversions``), for places where the subexpression is3332     producing a value you intend to use.3333   * Your ``BuildXXX`` function will probably just return ``ExprError()`` at3334     this point, since you don't have an AST.  That's perfectly fine, and3335     shouldn't impact your testing.3336 3337#. Introduce an AST node for your new expression.  This starts with declaring3338   the node in ``include/Basic/StmtNodes.td`` and creating a new class for your3339   expression in the appropriate ``include/AST/Expr*.h`` header.  It's best to3340   look at the class for a similar expression to get ideas, and there are some3341   specific things to watch for:3342 3343   * If you need to allocate memory, use the ``ASTContext`` allocator to3344     allocate memory.  Never use raw ``malloc`` or ``new``, and never hold any3345     resources in an AST node, because the destructor of an AST node is never3346     called.3347   * Make sure that ``getSourceRange()`` covers the exact source range of your3348     expression.  This is needed for diagnostics and for IDE support.3349   * Make sure that ``children()`` visits all of the subexpressions.  This is3350     important for a number of features (e.g., IDE support, C++ variadic3351     templates).  If you have sub-types, you'll also need to visit those3352     sub-types in ``RecursiveASTVisitor``.3353   * Add printing support (``StmtPrinter.cpp``) for your expression.3354   * Add profiling support (``StmtProfile.cpp``) for your AST node, noting the3355     distinguishing (non-source location) characteristics of an instance of3356     your expression.  Omitting this step will lead to hard-to-diagnose3357     failures regarding matching of template declarations.3358   * Add serialization support (``ASTReaderStmt.cpp``, ``ASTWriterStmt.cpp``)3359     for your AST node.3360 3361#. Teach semantic analysis to build your AST node.  At this point, you can wire3362   up your ``Sema::BuildXXX`` function to actually create your AST.  A few3363   things to check at this point:3364 3365   * If your expression can construct a new C++ class or return a new3366     Objective-C object, be sure to update and then call3367     ``Sema::MaybeBindToTemporary`` for your just-created AST node to be sure3368     that the object gets properly destructed.  An easy way to test this is to3369     return a C++ class with a private destructor: semantic analysis should3370     flag an error here with the attempt to call the destructor.3371   * Inspect the generated AST by printing it using ``clang -cc1 -ast-print``,3372     to make sure you're capturing all of the important information about how3373     the AST was written.3374   * Inspect the generated AST under ``clang -cc1 -ast-dump`` to verify that3375     all of the types in the generated AST line up the way you want them.3376     Remember that clients of the AST should never have to "think" to3377     understand what's going on.  For example, all implicit conversions should3378     show up explicitly in the AST.3379   * Write tests that use your expression as a subexpression of other,3380     well-known expressions.  Can you call a function using your expression as3381     an argument?  Can you use the ternary operator?3382 3383#. Teach code generation to create IR to your AST node.  This step is the first3384   (and only) that requires knowledge of LLVM IR.  There are several things to3385   keep in mind:3386 3387   * Code generation is separated into scalar/aggregate/complex and3388     lvalue/rvalue paths, depending on what kind of result your expression3389     produces.  On occasion, this requires some careful factoring of code to3390     avoid duplication.3391   * ``CodeGenFunction`` contains functions ``ConvertType`` and3392     ``ConvertTypeForMem`` that convert Clang's types (``clang::Type*`` or3393     ``clang::QualType``) to LLVM types.  Use the former for values, and the3394     latter for memory locations: test with the C++ "``bool``" type to check3395     this.  If you find that you are having to use LLVM bitcasts to make the3396     subexpressions of your expression have the type that your expression3397     expects, STOP!  Go fix semantic analysis and the AST so that you don't3398     need these bitcasts.3399   * The ``CodeGenFunction`` class has a number of helper functions to make3400     certain operations easy, such as generating code to produce an lvalue or3401     an rvalue, or to initialize a memory location with a given value.  Prefer3402     to use these functions rather than directly writing loads and stores,3403     because these functions take care of some of the tricky details for you3404     (e.g., for exceptions).3405   * If your expression requires some special behavior in the event of an3406     exception, look at the ``push*Cleanup`` functions in ``CodeGenFunction``3407     to introduce a cleanup.  You shouldn't have to deal with3408     exception-handling directly.3409   * Testing is extremely important in IR generation.  Use ``clang -cc13410     -emit-llvm`` and `FileCheck3411     <https://llvm.org/docs/CommandGuide/FileCheck.html>`_ to verify that you're3412     generating the right IR.3413 3414#. Teach template instantiation how to cope with your AST node, which requires3415   some fairly simple code:3416 3417   * Make sure that your expression's constructor properly computes the flags3418     for type dependence (i.e., the type your expression produces can change3419     from one instantiation to the next), value dependence (i.e., the constant3420     value your expression produces can change from one instantiation to the3421     next), instantiation dependence (i.e., a template parameter occurs3422     anywhere in your expression), and whether your expression contains a3423     parameter pack (for variadic templates).  Often, computing these flags3424     just means combining the results from the various types and3425     subexpressions.3426   * Add ``TransformXXX`` and ``RebuildXXX`` functions to the ``TreeTransform``3427     class template in ``Sema``.  ``TransformXXX`` should (recursively)3428     transform all of the subexpressions and types within your expression,3429     using ``getDerived().TransformYYY``.  If all of the subexpressions and3430     types transform without error, it will then call the ``RebuildXXX``3431     function, which will in turn call ``getSema().BuildXXX`` to perform3432     semantic analysis and build your expression.3433   * To test template instantiation, take those tests you wrote to make sure3434     that you were type checking with type-dependent expressions and dependent3435     types (from step #2) and instantiate those templates with various types,3436     some of which type-check and some that don't, and test the error messages3437     in each case.3438 3439#. There are some "extras" that make other features work better.  It's worth3440   handling these extras to give your expression complete integration into3441   Clang:3442 3443   * Add code completion support for your expression in3444     ``SemaCodeComplete.cpp``.3445   * If your expression has types in it, or has any "interesting" features3446     other than subexpressions, extend libclang's ``CursorVisitor`` to provide3447     proper visitation for your expression, enabling various IDE features such3448     as syntax highlighting, cross-referencing, and so on.  The3449     ``c-index-test`` helper program can be used to test these features.3450 3451Testing3452-------3453All functional changes to Clang should come with test coverage demonstrating3454the change in behavior.3455 3456.. _verifying-diagnostics:3457 3458Verifying Diagnostics3459^^^^^^^^^^^^^^^^^^^^^3460Clang ``-cc1`` supports the ``-verify`` command line option as a way to3461validate diagnostic behavior. This option will use special comments within the3462test file to verify that expected diagnostics appear in the correct source3463locations. If all of the expected diagnostics match the actual output of Clang,3464then the invocation will return normally. If there are discrepancies between3465the expected and actual output, Clang will emit detailed information about3466which expected diagnostics were not seen or which unexpected diagnostics were3467seen, etc. A complete example is:3468 3469.. code-block: c++3470 3471  // RUN: %clang_cc1 -verify %s3472  int A = B; // expected-error {{use of undeclared identifier 'B'}}3473 3474If the test is run and the expected error is emitted on the expected line, the3475diagnostic verifier will pass. However, if the expected error does not appear3476or appears in a different location than expected, or if additional diagnostics3477appear, the diagnostic verifier will fail and emit information as to why.3478 3479The ``-verify`` command optionally accepts a comma-delimited list of one or3480more verification prefixes that can be used to craft those special comments.3481Each prefix must start with a letter and contain only alphanumeric characters,3482hyphens, and underscores. ``-verify`` by itself is equivalent to3483``-verify=expected``, meaning that special comments will start with3484``expected``. Using different prefixes makes it easier to have separate3485``RUN:`` lines in the same test file which result in differing diagnostic3486behavior. For example:3487 3488.. code-block:: c++3489 3490  // RUN: %clang_cc1 -verify=foo,bar %s3491 3492  int A = B; // foo-error {{use of undeclared identifier 'B'}}3493  int C = D; // bar-error {{use of undeclared identifier 'D'}}3494  int E = F; // expected-error {{use of undeclared identifier 'F'}}3495 3496The verifier will recognize ``foo-error`` and ``bar-error`` as special comments3497but will not recognize ``expected-error`` as one because the ``-verify`` line3498does not contain that as a prefix. Thus, this test would fail verification3499because an unexpected diagnostic would appear on the declaration of ``E``.3500 3501Multiple occurrences accumulate prefixes.  For example,3502``-verify -verify=foo,bar -verify=baz`` is equivalent to3503``-verify=expected,foo,bar,baz``.3504 3505Specifying Diagnostics3506^^^^^^^^^^^^^^^^^^^^^^3507Indicating that a line expects an error or a warning is easy. Put a comment3508on the line that has the diagnostic, use3509``expected-{error,warning,remark,note}`` to tag if it's an expected error,3510warning, remark, or note (respectively), and place the expected text between3511``{{`` and ``}}`` markers. The full text doesn't have to be included, only3512enough to ensure that the correct diagnostic was emitted. (Note: full text3513should be included in test cases unless there is a compelling reason to use3514truncated text instead.)3515 3516For a full description of the matching behavior, including more complex3517matching scenarios, see :ref:`matching <DiagnosticMatching>` below.3518 3519Here's an example of the most commonly used way to specify expected3520diagnostics:3521 3522.. code-block:: c++3523 3524  int A = B; // expected-error {{use of undeclared identifier 'B'}}3525 3526You can place as many diagnostics on one line as you wish. To make the code3527more readable, you can use slash-newline to separate out the diagnostics.3528 3529Alternatively, it is possible to specify the line on which the diagnostic3530should appear by appending ``@<line>`` to ``expected-<type>``, for example:3531 3532.. code-block:: c++3533 3534  #warning some text3535  // expected-warning@10 {{some text}}3536 3537The line number may be absolute (as above), or relative to the current line by3538prefixing the number with either ``+`` or ``-``.3539 3540If the diagnostic is generated in a separate file, for example in a shared3541header file, it may be beneficial to be able to declare the file in which the3542diagnostic will appear, rather than placing the ``expected-*`` directive in the3543actual file itself. This can be done using the following syntax:3544 3545.. code-block:: c++3546 3547  // expected-error@path/include.h:15 {{error message}}3548 3549The path can be absolute or relative and the same search paths will be used as3550for ``#include`` directives. The line number in an external file may be3551substituted with ``*`` meaning that any line number will match (useful where3552the included file is, for example, a system header where the actual line number3553may change and is not critical).3554 3555As an alternative to specifying a fixed line number, the location of a3556diagnostic can instead be indicated by a marker of the form ``#<marker>``.3557Markers are specified by including them in a comment, and then referenced by3558appending the marker to the diagnostic with ``@#<marker>``, as with:3559 3560.. code-block:: c++3561 3562  #warning some text  // #13563  // ... other code ...3564  // expected-warning@#1 {{some text}}3565 3566The name of a marker used in a directive must be unique within the compilation.3567 3568The simple syntax above allows each specification to match exactly one3569diagnostic. You can use the extended syntax to customize this. The extended3570syntax is ``expected-<type> <n> {{diag text}}``, where ``<type>`` is one of3571``error``, ``warning``, ``remark``, or ``note``, and ``<n>`` is a positive3572integer. This allows the diagnostic to appear as many times as specified. For3573example:3574 3575.. code-block:: c++3576 3577  void f(); // expected-note 2 {{previous declaration is here}}3578 3579Where the diagnostic is expected to occur a minimum number of times, this can3580be specified by appending a ``+`` to the number. For example:3581 3582.. code-block:: c++3583 3584  void f(); // expected-note 0+ {{previous declaration is here}}3585  void g(); // expected-note 1+ {{previous declaration is here}}3586 3587In the first example, the diagnostic becomes optional, i.e., it will be3588swallowed if it occurs, but will not generate an error if it does not occur. In3589the second example, the diagnostic must occur at least once. As a short-hand,3590"one or more" can be specified simply by ``+``. For example:3591 3592.. code-block:: c++3593 3594  void g(); // expected-note + {{previous declaration is here}}3595 3596A range can also be specified by ``<n>-<m>``. For example:3597 3598.. code-block:: c++3599 3600  void f(); // expected-note 0-1 {{previous declaration is here}}3601 3602In this example, the diagnostic may appear only once, if at all.3603 3604.. _DiagnosticMatching:3605 3606Matching Modes3607~~~~~~~~~~~~~~3608 3609The default matching mode is simple string, which looks for the expected text3610that appears between the first `{{` and `}}` pair of the comment. The string is3611interpreted just as-is, with one exception: the sequence `\n` is converted to a3612single newline character. This mode matches the emitted diagnostic when the3613text appears as a substring at any position of the emitted message.3614 3615To enable matching against desired strings that contain `}}` or `{{`, the3616string-mode parser accepts opening delimiters of more than two curly braces,3617like `{{{`. It then looks for a closing delimiter of equal "width" (i.e `}}}`).3618For example:3619 3620.. code-block:: c++3621 3622  // expected-note {{{evaluates to '{{2, 3, 4}} == {0, 3, 4}'}}}3623 3624The intent is to allow the delimiter to be wider than the longest `{` or `}`3625brace sequence in the content, so that if your expected text contains `{{{`3626(three braces) it may be delimited with `{{{{` (four braces), and so on.3627 3628Regex matching mode may be selected by appending ``-re`` to the diagnostic type3629and including regexes wrapped in double curly braces (`{{` and `}}`) in the3630directive, such as:3631 3632.. code-block:: text3633 3634  expected-error-re {{format specifies type 'wchar_t **' (aka '{{.+}}')}}3635 3636Examples matching error: "variable has incomplete type 'struct s'"3637 3638.. code-block:: c++3639 3640  // expected-error {{variable has incomplete type 'struct s'}}3641  // expected-error {{variable has incomplete type}}3642  // expected-error {{{variable has incomplete type}}}3643  // expected-error {{{{variable has incomplete type}}}}3644 3645  // expected-error-re {{variable has type 'struct {{.}}'}}3646  // expected-error-re {{variable has type 'struct {{.*}}'}}3647  // expected-error-re {{variable has type 'struct {{(.*)}}'}}3648  // expected-error-re {{variable has type 'struct{{[[:space:]](.*)}}'}}3649 3650Feature Test Macros3651===================3652Clang implements several ways to test whether a feature is supported or not.3653Some of these feature tests are standardized, like ``__has_cpp_attribute`` or3654``__cpp_lambdas``, while others are Clang extensions, like ``__has_builtin``.3655The common theme among all the various feature tests is that they are a utility3656to tell users that we think a particular feature is complete. However,3657completeness is a difficult property to define because features may still have3658lingering bugs, may only work on some targets, etc. We use the following3659criteria when deciding whether to expose a feature test macro (or particular3660result value for the feature test):3661 3662  * Are there known issues where we reject valid code that should be accepted?3663  * Are there known issues where we accept invalid code that should be rejected?3664  * Are there known crashes, failed assertions, or miscompilations?3665  * Are there known issues on a particular relevant target?3666 3667If the answer to any of these is "yes", the feature test macro should either3668not be defined or there should be very strong rationale for why the issues3669should not prevent defining it. Note, it is acceptable to define the feature3670test macro on a per-target basis if needed.3671 3672When in doubt, being conservative is better than being aggressive. If we don't3673claim support for the feature but it does useful things, users can still use it3674and provide us with useful feedback on what is missing. But if we claim support3675for a feature that has significant bugs, we've eliminated most of the utility3676of having a feature testing macro at all because users are then forced to test3677what compiler version is in use to get a more accurate answer.3678 3679The status reported by the feature test macro should always be reflected in the3680language support page for the corresponding feature (`C++3681<https://clang.llvm.org/cxx_status.html>`_, `C3682<https://clang.llvm.org/c_status.html>`_) if applicable. This page can give3683more nuanced information to the user as well, such as claiming partial support3684for a feature and specifying details as to what remains to be done.3685