TheDiagnostic*Kinds.td files¶

Diagnostics are created by adding an entry to one of theclang/Basic/Diagnostic*Kinds.td files, depending on what library will beusing it. From this file,tblgen generates the unique ID of thediagnostic, the severity of the diagnostic and the English translation + formatstring.

There is little sanity with the naming of the unique ID’s right now. Somestart witherr_,warn_,ext_ to encode the severity into the name.Since the enum is referenced in the C++ code that produces the diagnostic, itis somewhat useful for it to be reasonably short.

The severity of the diagnostic comes from the set {NOTE,REMARK,WARNING,EXTENSION,EXTWARN,ERROR}. TheERROR severity is used fordiagnostics indicating the program is never acceptable under any circumstances.When an error is emitted, the AST for the input code may not be fully built.TheEXTENSION andEXTWARN severities are used for extensions to thelanguage that Clang accepts. This means that Clang fully understands and canrepresent them in the AST, but we produce diagnostics to tell the user theircode is non-portable. The difference is that the former are ignored bydefault, and the later warn by default. TheWARNING severity is used forconstructs that are valid in the currently selected source language but thatare dubious in some way. TheREMARK severity provides generic informationabout the compilation that is not necessarily related to any dubious code. TheNOTE level is used to staple more information onto previous diagnostics.

Theseseverities are mapped into a smaller set (theDiagnostic::Levelenum, {Ignored,Note,Remark,Warning,Error,Fatal}) ofoutputlevels by the diagnostics subsystem based on various configuration options.Clang internally supports a fully fine grained mapping mechanism that allowsyou to map almost any diagnostic to the output level that you want. The onlydiagnostics that cannot be mapped areNOTEs, which always follow theseverity of the previously emitted diagnostic andERRORs, which can onlybe mapped toFatal (it is not possible to turn an error into a warning, forexample).

Diagnostic mappings are used in many ways. For example, if the user specifies-pedantic,EXTENSION maps toWarning, if they specify-pedantic-errors, it turns intoError. This is used to implementoptions like-Wunused_macros,-Wundef etc.

Mapping toFatal should only be used for diagnostics that are considered sosevere that error recovery won’t be able to recover sensibly from them (thusspewing a ton of bogus errors). One example of this class of error are failureto#include a file.

Diagnostic Wording¶

The wording used for a diagnostic is critical because it is the only way for auser to know how to correct their code. Use the following suggestions whenwording a diagnostic.

• Diagnostics in Clang do not start with a capital letter and do not end withpunctuation.

  • This does not apply to proper nouns likeClang orOpenMP, toacronyms likeGCC orARC, or to language standards likeC23orC++17.

  • A trailing question mark is allowed. e.g.,unknownidentifier%0;didyoumean%1?.

• Appropriately capitalize proper nouns likeClang,OpenCL,GCC,Objective-C, etc and language standard versions likeC11 orC++11.

• The wording should be succinct. If necessary, use a semicolon to combinesentence fragments instead of using complete sentences. e.g., prefer wordinglike'%0'isdeprecated;itwillberemovedinafuturereleaseofClangover wording like'%0'isdeprecated.ItwillberemovedinafuturereleaseofClang.

• The wording should be actionable and avoid using standards terms or grammarproductions that a new user would not be familiar with. e.g., prefer wordinglikemissingsemicolon over wording likesyntaxerror (which is notactionable) orexpectedunqualified-id (which uses standards terminology).

• The wording should clearly explain what is wrong with the code rather thanrestating what the code does. e.g., prefer wording liketype%0requiresavalueintherange%1to%2 over wording like%0isinvalid.

• The wording should have enough contextual information to help the useridentify the issue in a complex expression. e.g., prefer wording likebothsidesofthe%0binaryoperatorareidentical over wording likeidenticaloperandstobinaryoperator.

• Use single quotes to denote syntactic constructs or command line argumentsnamed in a diagnostic message. e.g., prefer wording like'this'pointercannotbenullinwell-definedC++code over wording likethispointercannotbenullinwell-definedC++code.

• Prefer diagnostic wording without contractions whenever possible. The singlequote in a contraction can be visually distracting due to its use withsyntactic constructs and contractions can be harder to understand for non-native English speakers.

The Format String¶

The format string for the diagnostic is very simple, but it has some power. Ittakes the form of a string in English with markers that indicate where and howarguments to the diagnostic are inserted and formatted. For example, here aresome simple format strings:

"binary integer literals are an extension""format string contains '\\0' within the string body""more '%%' conversions than data arguments""invalid operands to binary expression (%0 and %1)""overloaded '%0' must be a %select{unary|binary|unary or binary}2 operator"" (has %1 parameter%s1)"

These examples show some important points of format strings. You can use anyplain ASCII character in the diagnostic string except “%” without aproblem, but these are C strings, so you have to use and be aware of all the Cescape sequences (as in the second example). If you want to produce a “%”in the output, use the “%%” escape sequence, like the third diagnostic.Finally, Clang uses the “%...[digit]” sequences to specify where and howarguments to the diagnostic are formatted.

Arguments to the diagnostic are numbered according to how they are specified bythe C++ code thatproduces them, and arereferenced by%0 ..%9. If you have more than 10 arguments to yourdiagnostic, you are doing something wrong :). Unlikeprintf, there is norequirement that arguments to the diagnostic end up in the output in the sameorder as they are specified, you could have a format string with “%1%0”that swaps them, for example. The text in between the percent and digit areformatting instructions. If there are no instructions, the argument is justturned into a string and substituted in.

Here are some “best practices” for writing the English format string:

• Keep the string short. It should ideally fit in the 80 column limit of theDiagnosticKinds.td file. This avoids the diagnostic wrapping whenprinted, and forces you to think about the important point you are conveyingwith the diagnostic.

• Take advantage of location information. The user will be able to see theline and location of the caret, so you don’t need to tell them that theproblem is with the 4th argument to the function: just point to it.

• Do not capitalize the diagnostic string, and do not end it with a period.

• If you need to quote something in the diagnostic string, use single quotes.

Diagnostics should never take random English strings as arguments: youshouldn’t use “youhaveaproblemwith%0” and pass in things like “yourargument” or “yourreturnvalue” as arguments. Doing this preventstranslating the Clang diagnostics to otherlanguages (because they’ll get random English words in their otherwiselocalized diagnostic). The exceptions to this are C/C++ language keywords(e.g.,auto,const,mutable, etc) and C/C++ operators (/=).Note that things like “pointer” and “reference” are not keywords. On the otherhand, youcan include anything that comes from the user’s source code,including variable names, types, labels, etc. The “select” format can beused to achieve this sort of thing in a localizable way, see below.

Formatting a Diagnostic Argument¶

Arguments to diagnostics are fully typed internally, and come from a coupledifferent classes: integers, types, names, and random strings. Depending onthe class of the argument, it can be optionally formatted in different ways.This gives theDiagnosticConsumer information about what the argument meanswithout requiring it to use a specific presentation (consider this MVC forClang :).

It is really easy to add format specifiers to the Clang diagnostics system, butthey should be discussed before they are added. If you are creating a lot ofrepetitive diagnostics and/or have an idea for a useful formatter, please bringit up on the cfe-dev mailing list.

Here are the different diagnostic argument formats currently supported byClang:

“s” format

Example:

"requires%0parameter%s0"

Class:

Integers

Description:

This is a simple formatter for integers that is useful when producing Englishdiagnostics. When the integer is 1, it prints as nothing. When the integeris not 1, it prints as “s”. This allows some simple grammatical forms tobe to be handled correctly, and eliminates the need to use gross things like"requires%1parameter(s)". Note, this only handles adding a simple“s” character, it will not handle situations where pluralization is morecomplicated such as turningfancy intofancies ormouse intomice. You can use the “plural” format specifier to handle such situations.

“select” format

Example:

"mustbea%select{unary|binary|unaryorbinary}0operator"

Class:

Integers

Description:

This format specifier is used to merge multiple related diagnostics togetherinto one common one, without requiring the difference to be specified as anEnglish string argument. Instead of specifying the string, the diagnosticgets an integer argument and the format string selects the numbered option.In this case, the “%0” value must be an integer in the range [0..2]. Ifit is 0, it prints “unary”, if it is 1 it prints “binary” if it is 2, itprints “unary or binary”. This allows other language translations tosubstitute reasonable words (or entire phrases) based on the semantics of thediagnostic instead of having to do things textually. The selected stringdoes undergo formatting.

“enum_select format

Example:

unknownfrobblingofa%enum_select<FrobbleKind>{%VarDecl{variabledeclaration}|%FuncDecl{functiondeclaration}}0whenblarging

Class:

Integers

Description:

This format specifier is used exactly like aselect specifier, except itadditionally generates a namespace, enumeration, and enumerator list based onthe format string given. In the above case, a namespace is generated namedFrobbleKind that has an unscoped enumeration with the enumeratorsVarDecl andFuncDecl which correspond to the values 0 and 1. Thispermits a clearer use of theDiag in source code, as the above could becalled as:Diag(Loc,diag::frobble)<<diag::FrobbleKind::VarDecl.

“plural” format

Example:

"youhave%0%plural{1:mouse|:mice}0connectedtoyourcomputer"

Class:

Integers

Description:

This is a formatter for complex plural forms. It is designed to handle eventhe requirements of languages with very complex plural forms, as many Balticlanguages have. The argument consists of a series of expression/form pairs,separated by “:”, where the first form whose expression evaluates to true isthe result of the modifier.

An expression can be empty, in which case it is always true. See the exampleat the top. Otherwise, it is a series of one or more numeric conditions,separated by “,”. If any condition matches, the expression matches. Eachnumeric condition can take one of three forms.

• number: A simple decimal number matches if the argument is the same as thenumber. Example:"%plural{1:mouse|:mice}0"

• range: A range in square brackets matches if the argument is within therange. Then range is inclusive on both ends. Example:"%plural{0:none|1:one|[2,5]:some|:many}0"

• modulo: A modulo operator is followed by a number, and equals sign andeither a number or a range. The tests are the same as for plain numbersand ranges, but the argument is taken modulo the number first. Example:"%plural{%100=0:evenhundred|%100=[1,50]:lowerhalf|:everythingelse}1"

The parser is very unforgiving. A syntax error, even whitespace, will abort,as will a failure to match the argument against any expression.

“ordinal” format

Example:

"ambiguityin%ordinal0argument"

Class:

Integers

Description:

This is a formatter which represents the argument number as an ordinal: thevalue1 becomes1st,3 becomes3rd, and so on. Values lessthan1 are not supported. This formatter is currently hard-coded to useEnglish ordinals.

“human” format

Example:

"totalsizeis%human0bytes"

Class:

Integers

Description:

This is a formatter which represents the argument number in a human readableformat: the value123 stays123,12345 becomes12.34k,6666666`becomes``6.67M, and so on for ‘G’ and ‘T’.

“objcclass” format

Example:

"method%objcclass0notfound"

Class:

DeclarationName

Description:

This is a simple formatter that indicates theDeclarationName correspondsto an Objective-C class method selector. As such, it prints the selectorwith a leading “+”.

“objcinstance” format

Example:

"method%objcinstance0notfound"

Class:

DeclarationName

Description:

This is a simple formatter that indicates theDeclarationName correspondsto an Objective-C instance method selector. As such, it prints the selectorwith a leading “-“.

“q” format

Example:

"candidatefoundbynamelookupis%q0"

Class:

NamedDecl*

Description:

This formatter indicates that the fully-qualified name of the declarationshould be printed, e.g., “std::vector” rather than “vector”.

“diff” format

Example:

"noknownconversion%diff{from$to$|fromargumenttypetoparametertype}1,2"

Class:

QualType

Description:

This formatter takes twoQualTypes and attempts to print a templatedifference between the two. If tree printing is off, the text inside thebraces before the pipe is printed, with the formatted text replacing the $.If tree printing is on, the text after the pipe is printed and a type tree isprinted after the diagnostic message.

“sub” format

Example:

Given the following record definition of typeTextSubstitution:

def select_ovl_candidate : TextSubstitution<  "%select{function|constructor}0%select{| template| %2}1">;

which can be used as

def note_ovl_candidate : Note<  "candidate %sub{select_ovl_candidate}3,2,1 not viable">;

and will act as if it was written"candidate%select{function|constructor}3%select{|template|%1}2notviable".

Description:

This format specifier is used to avoid repeating strings verbatim in multiplediagnostics. The argument to%sub must name aTextSubstitution tblgenrecord. The substitution must specify all arguments used by the substitution,and the modifier indexes in the substitution are re-numbered accordingly. Thesubstituted text must itself be a valid format string before substitution.

Producing the Diagnostic¶

Now that you’ve created the diagnostic in theDiagnostic*Kinds.td file, youneed to write the code that detects the condition in question and emits the newdiagnostic. Various components of Clang (e.g., the preprocessor,Sema,etc.) provide a helper function named “Diag”. It creates a diagnostic andaccepts the arguments, ranges, and other information that goes along with it.

For example, the binary expression error comes from code like this:

if(variousthingsthatarebad)Diag(Loc,diag::err_typecheck_invalid_operands)<<lex->getType()<<rex->getType()<<lex->getSourceRange()<<rex->getSourceRange();

This shows that use of theDiag method: it takes a location (aSourceLocation object) and a diagnostic enum value(which matches the name fromDiagnostic*Kinds.td). If the diagnostic takesarguments, they are specified with the<< operator: the first argumentbecomes%0, the second becomes%1, etc. The diagnostic interfaceallows you to specify arguments of many different types, includingint andunsigned for integer arguments,constchar* andstd::string forstring arguments,DeclarationName andconstIdentifierInfo* for names,QualType for types, etc.SourceRanges are also specified with the<< operator, but do not have a specific ordering requirement.

As you can see, adding and producing a diagnostic is pretty straightforward.The hard part is deciding exactly what you need to say to help the user,picking a suitable wording, and providing the information needed to format itcorrectly. The good news is that the call site that issues a diagnostic shouldbe completely independent of how the diagnostic is formatted and in whatlanguage it is rendered.

Fix-It Hints¶

In some cases, the front end emits diagnostics when it is clear that some smallchange to the source code would fix the problem. For example, a missingsemicolon at the end of a statement or a use of deprecated syntax that iseasily rewritten into a more modern form. Clang tries very hard to emit thediagnostic and recover gracefully in these and other cases.

However, for these cases where the fix is obvious, the diagnostic can beannotated with a hint (referred to as a “fix-it hint”) that describes how tochange the code referenced by the diagnostic to fix the problem. For example,it might add the missing semicolon at the end of the statement or rewrite theuse of a deprecated construct into something more palatable. Here is one suchexample from the C++ front end, where we warn about the right-shift operatorchanging meaning from C++98 to C++11:

test.cpp:3:7: warning: use of right-shift operator ('>>') in template argument                       will require parentheses in C++11A<100 >> 2> *a;      ^  (       )

Here, the fix-it hint is suggesting that parentheses be added, and showingexactly where those parentheses would be inserted into the source code. Thefix-it hints themselves describe what changes to make to the source code in anabstract manner, which the text diagnostic printer renders as a line of“insertions” below the caret line.Other diagnostic clients might choose to render the code differently (e.g., asmarkup inline) or even give the user the ability to automatically fix theproblem.

Fix-it hints on errors and warnings need to obey these rules:

• Since they are automatically applied if-Xclang-fixit is passed to thedriver, they should only be used when it’s very likely they match the user’sintent.

• Clang must recover from errors as if the fix-it had been applied.

• Fix-it hints on a warning must not change the meaning of the code.However, a hint may clarify the meaning as intentional, for example by addingparentheses when the precedence of operators isn’t obvious.

If a fix-it can’t obey these rules, put the fix-it on a note. Fix-its on notesare not applied automatically.

All fix-it hints are described by theFixItHint class, instances of whichshould be attached to the diagnostic using the<< operator in the same waythat highlighted source ranges and arguments are passed to the diagnostic.Fix-it hints can be created with one of three constructors:

• FixItHint::CreateInsertion(Loc,Code)

  Specifies that the givenCode (a string) should be inserted before thesource locationLoc.

• FixItHint::CreateRemoval(Range)

  Specifies that the code in the given sourceRange should be removed.

• FixItHint::CreateReplacement(Range,Code)

  Specifies that the code in the given sourceRange should be removed,and replaced with the givenCode string.

TheDiagnosticConsumer Interface¶

Once code generates a diagnostic with all of the arguments and the rest of therelevant information, Clang needs to know what to do with it. As previouslymentioned, the diagnostic machinery goes through some filtering to map aseverity onto a diagnostic level, then (assuming the diagnostic is not mappedto “Ignore”) it invokes an object that implements theDiagnosticConsumerinterface with the information.

It is possible to implement this interface in many different ways. Forexample, the normal ClangDiagnosticConsumer (namedTextDiagnosticPrinter) turns the arguments into strings (according to thevarious formatting rules), prints out the file/line/column information and thestring, then prints out the line of code, the source ranges, and the caret.However, this behavior isn’t required.

Another implementation of theDiagnosticConsumer interface is theTextDiagnosticBuffer class, which is used when Clang is in-verifymode. Instead of formatting and printing out the diagnostics, thisimplementation just captures and remembers the diagnostics as they fly by.Then-verify compares the list of produced diagnostics to the list ofexpected ones. If they disagree, it prints out its own output. Fulldocumentation for the-verify mode can be found atVerifying Diagnostics.

There are many other possible implementations of this interface, and this iswhy we prefer diagnostics to pass down rich structured information inarguments. For example, an HTML output might want declaration names belinkified to where they come from in the source. Another example is that a GUImight let you click on typedefs to expand them. This application would want topass significantly more information about types through to the GUI than asimple flat string. The interface allows this to happen.

Adding Translations to Clang¶

Not possible yet! Diagnostic strings should be written in UTF-8, the client cantranslate to the relevant code page if needed. Each translation completelyreplaces the format string for the diagnostic.

Immutability¶

Clang AST nodes (types, declarations, statements, expressions, and so on) aregenerally designed to be immutable once created. This provides a number of keybenefits:

• Canonicalization of the “meaning” of nodes is possible as soon as the nodesare created, and is not invalidated by later addition of more information.For example, wecanonicalize types, and use acanonicalized representation of expressions when determining whether twofunction template declarations involving dependent expressions declare thesame entity.

• AST nodes can be reused when they have the same meaning. For example, wereuseType nodes when representing the same type (but maintain separateTypeLocs for each instance where a type is written), and we reusenon-dependentStmt andExpr nodes across instantiations of atemplate.

• Serialization and deserialization of the AST to/from AST files is simpler:we do not need to track modifications made to AST nodes imported from ASTfiles and serialize separate “update records”.

There are unfortunately exceptions to this general approach, such as:

• The first declaration of a redeclarable entity maintains a pointer to themost recent declaration of that entity, which naturally needs to change asmore declarations are parsed.

• Name lookup tables in declaration contexts change after the namespacedeclaration is formed.

• We attempt to maintain only a single declaration for an instantiation of atemplate, rather than having distinct declarations for an instantiation ofthe declaration versus the definition, so template instantiation oftenupdates parts of existing declarations.

• Some parts of declarations are required to be instantiated separately (thisincludes default arguments and exception specifications), and suchinstantiations update the existing declaration.

These cases tend to be fragile; mutable AST state should be avoided wherepossible.

As a consequence of this design principle, we typically do not provide settersfor AST state. (Some are provided for short-term modifications intended to beused immediately after an AST node is created and before it’s “published” aspart of the complete AST, or where language semantics require after-the-factupdates.)

Faithfulness¶

The AST intends to provide a representation of the program that is faithful tothe original source. We intend for it to be possible to write refactoring toolsusing only information stored in, or easily reconstructible from, the Clang AST.This means that the AST representation should either not desugar source-levelconstructs to simpler forms, or – where made necessary by language semanticsor a clear engineering tradeoff – should desugar minimally and wrap the resultin a construct representing the original source form.

For example,CXXForRangeStmt directly represents the syntactic form of arange-based for statement, but also holds a semantic representation of therange declaration and iterator declarations. It does not contain afully-desugaredForStmt, however.

Some AST nodes (for example,ParenExpr) represent only syntax, and others(for example,ImplicitCastExpr) represent only semantics, but most nodeswill represent a combination of syntax and associated semantics. Inheritanceis typically used when representing different (but related) syntaxes for nodeswith the same or similar semantics.

Canonical Types¶

Every instance of theType class contains a canonical type pointer. Forsimple types with no typedefs involved (e.g., “int”, “int*”,“int**”), the type just points to itself. For types that have a typedefsomewhere in their structure (e.g., “foo”, “foo*”, “foo**”,“bar”), the canonical type pointer points to their structurally equivalenttype without any typedefs (e.g., “int”, “int*”, “int**”, and“int*” respectively).

This design provides a constant time operation (dereferencing the canonical typepointer) that gives us access to the structure of types. For example, we cantrivially tell that “bar” and “foo*” are the same type by dereferencingtheir canonical type pointers and doing a pointer comparison (they both pointto the single “int*” type).

Canonical types and typedef types bring up some complexities that must becarefully managed. Specifically, theisa/cast/dyn_cast operatorsgenerally shouldn’t be used in code that is inspecting the AST. For example,when type checking the indirection operator (unary “*” on a pointer), thetype checker must verify that the operand has a pointer type. It would not becorrect to check that with “isa<PointerType>(SubExpr->getType())”, becausethis predicate would fail if the subexpression had a typedef type.

The solution to this problem are a set of helper methods onType, used tocheck their properties. In this case, it would be correct to use“SubExpr->getType()->isPointerType()” to do the check. This predicate willreturn true if thecanonical type is a pointer, which is true any time thetype is structurally a pointer type. The only hard part here is rememberingnot to use theisa/cast/dyn_cast operations.

The second problem we face is how to get access to the pointer type once weknow it exists. To continue the example, the result type of the indirectionoperator is the pointee type of the subexpression. In order to determine thetype, we need to get the instance ofPointerType that best captures thetypedef information in the program. If the type of the expression is literallyaPointerType, we can return that, otherwise we have to dig through thetypedefs to find the pointer type. For example, if the subexpression had type“foo*”, we could return that type as the result. If the subexpression hadtype “bar”, we want to return “foo*” (note that we donot want“int*”). In order to provide all of this,Type has agetAsPointerType() method that checks whether the type is structurally aPointerType and, if so, returns the best one. If not, it returns a nullpointer.

This structure is somewhat mystical, but after meditating on it, it will makesense to you :).

Redeclarations and Overloads¶

Within a translation unit, it is common for an entity to be declared severaltimes. For example, we might declare a function “f” and then laterre-declare it as part of an inlined definition:

voidf(intx,inty,intz=1);inlinevoidf(intx,inty,intz){/* ...  */}

The representation of “f” differs in the source-centric andsemantics-centric views of a declaration context. In the source-centric view,all redeclarations will be present, in the order they occurred in the sourcecode, making this view suitable for clients that wish to see the structure ofthe source code. In the semantics-centric view, only the most recent “f”will be found by the lookup, since it effectively replaces the firstdeclaration of “f”.

(Note that becausef can be redeclared at block scope, or in a frienddeclaration, etc. it is possible that the declaration off found by namelookup will not be the most recent one.)

In the semantics-centric view, overloading of functions is representedexplicitly. For example, given two declarations of a function “g” that areoverloaded, e.g.,

voidg();voidg(int);

theDeclContext::lookup operation will return aDeclContext::lookup_result that contains a range of iterators overdeclarations of “g”. Clients that perform semantic analysis on a programthat is not concerned with the actual source code will primarily use thissemantics-centric view.

Lexical and Semantic Contexts¶

Each declaration has two potentially different declaration contexts: alexical context, which corresponds to the source-centric view of thedeclaration context, and asemantic context, which corresponds to thesemantics-centric view. The lexical context is accessible viaDecl::getLexicalDeclContext while the semantic context is accessible viaDecl::getDeclContext, both of which returnDeclContext pointers. Formost declarations, the two contexts are identical. For example:

classX{public:voidf(intx);};

Here, the semantic and lexical contexts ofX::f are theDeclContextassociated with the classX (itself stored as aRecordDecl AST node).However, we can now defineX::f out-of-line:

voidX::f(intx=17){/* ...  */}

This definition of “f” has different lexical and semantic contexts. Thelexical context corresponds to the declaration context in which the actualdeclaration occurred in the source code, e.g., the translation unit containingX. Thus, this declaration ofX::f can be found by traversing thedeclarations provided by [decls_begin(),decls_end()) in thetranslation unit.

The semantic context ofX::f corresponds to the classX, since thismember function is (semantically) a member ofX. Lookup of the namefinto theDeclContext associated withX will then return the definitionofX::f (including information about the default argument).

Transparent Declaration Contexts¶

In C and C++, there are several contexts in which names that are logicallydeclared inside another declaration will actually “leak” out into the enclosingscope from the perspective of name lookup. The most obvious instance of thisbehavior is in enumeration types, e.g.,

enumColor{Red,Green,Blue};

Here,Color is an enumeration, which is a declaration context that containsthe enumeratorsRed,Green, andBlue. Thus, traversing the list ofdeclarations contained in the enumerationColor will yieldRed,Green, andBlue. However, outside of the scope ofColor one canname the enumeratorRed without qualifying the name, e.g.,

Colorc=Red;

There are other entities in C++ that provide similar behavior. For example,linkage specifications that use curly braces:

extern"C"{voidf(int);voidg(int);}// f and g are visible here

For source-level accuracy, we treat the linkage specification and enumerationtype as a declaration context in which its enclosed declarations (”Red”,“Green”, and “Blue”; “f” and “g”) are declared. However, thesedeclarations are visible outside of the scope of the declaration context.

These language features (and several others, described below) have roughly thesame set of requirements: declarations are declared within a particular lexicalcontext, but the declarations are also found via name lookup in scopesenclosing the declaration itself. This feature is implemented viatransparent declaration contexts (seeDeclContext::isTransparentContext()), whose declarations are visible in thenearest enclosing non-transparent declaration context. This means that thelexical context of the declaration (e.g., an enumerator) will be thetransparentDeclContext itself, as will the semantic context, but thedeclaration will be visible in every outer context up to and including thefirst non-transparent declaration context (since transparent declarationcontexts can be nested).

The transparentDeclContexts are:

• Enumerations (but not C++11 “scoped enumerations”):

  enumColor{Red,Green,Blue};// Red, Green, and Blue are in scope

• C++ linkage specifications:

  extern"C"{voidf(int);voidg(int);}// f and g are in scope

• Anonymous unions and structs:

  structLookupTable{boolIsVector;union{std::vector<Item>*Vector;std::set<Item>*Set;};};LookupTableLT;LT.Vector=0;// Okay: finds Vector inside the unnamed union

• C++11 inline namespaces:

  namespacemylib{inlinenamespacedebug{classX;}}mylib::X*xp;// okay: mylib::X refers to mylib::debug::X

Multiply-Defined Declaration Contexts¶

C++ namespaces have the interesting property thatthe namespace can be defined multiple times, and the declarations provided byeach namespace definition are effectively merged (from the semantic point ofview). For example, the following two code snippets are semanticallyindistinguishable:

// Snippet #1:namespaceN{voidf();}namespaceN{voidf(int);}// Snippet #2:namespaceN{voidf();voidf(int);}

In Clang’s representation, the source-centric view of declaration contexts willactually have two separateNamespaceDecl nodes in Snippet #1, each of whichis a declaration context that contains a single declaration of “f”.However, the semantics-centric view provided by name lookup into the namespaceN for “f” will return aDeclContext::lookup_result that contains arange of iterators over declarations of “f”.

DeclContext manages multiply-defined declaration contexts internally. ThefunctionDeclContext::getPrimaryContext retrieves the “primary” context fora givenDeclContext instance, which is theDeclContext responsible formaintaining the lookup table used for the semantics-centric view. Given aDeclContext, one can obtain the set of declaration contexts that aresemantically connected to this declaration context, in source order, includingthis context (which will be the only result, for non-namespace contexts) viaDeclContext::collectAllContexts. Note that these functions are usedinternally within the lookup and insertion methods of theDeclContext, sothe vast majority of clients can ignore them.

Because the same entity can be defined multiple times in different modules,it is also possible for there to be multiple definitions of (for instance)aCXXRecordDecl, all of which describe a definition of the same class.In such a case, only one of those “definitions” is considered by Clang to bethe definition of the class, and the others are treated as non-definingdeclarations that happen to also contain member declarations. Correspondingmembers in each definition of such multiply-defined classes are identifiedeither by redeclaration chains (if the members areRedeclarable)or by simply a pointer to the canonical declaration (if the declarationsare notRedeclarable – in that case, aMergeable base class is usedinstead).

Recovery AST¶

The idea of Recovery AST is to use recovery nodes which act as a placeholder tomaintain the rough structure of the parsing tree, preserve locations andchildren but have no language semantics attached to them.

For example, consider the following mismatched function call:

intNoArg();voidtest(intabc){NoArg(abc);// oops, mismatched function arguments.}

Without Recovery AST, the invalid function call expression (and its childexpressions) would be dropped in the AST:

|-FunctionDecl <line:1:1, col:11> NoArg 'int ()'`-FunctionDecl <line:2:1, line:4:1> test 'void (int)' |-ParmVarDecl <col:11, col:15> col:15 used abc 'int' `-CompoundStmt <col:20, line:4:1>

With Recovery AST, the AST looks like:

|-FunctionDecl <line:1:1, col:11> NoArg 'int ()'`-FunctionDecl <line:2:1, line:4:1> test 'void (int)'  |-ParmVarDecl <col:11, col:15> used abc 'int'  `-CompoundStmt <col:20, line:4:1>    `-RecoveryExpr <line:3:3, col:12> 'int' contains-errors      |-UnresolvedLookupExpr <col:3> '<overloaded function type>' lvalue (ADL) = 'NoArg'      `-DeclRefExpr <col:9> 'int' lvalue ParmVar 'abc' 'int'

An alternative is to use existing Exprs, e.g. CallExpr for the above example.This would capture more call details (e.g. locations of parentheses) and allowit to be treated uniformly with valid CallExprs. However, jamming the data wehave into CallExpr forces us to weaken its invariants, e.g. arg count may bewrong. This would introduce a huge burden on consumers of the AST to handle such“impossible” cases. So when we’re representing (rather than correcting) errors,we use a distinct recovery node type with extremely weak invariants instead.

RecoveryExpr is the only recovery node so far. In practice, broken declsneed more detailed semantics preserved (the currentInvalid flag worksfairly well), and completely broken statements with interesting internalstructure are rare (so dropping the statements is OK).

Types and dependence¶

RecoveryExpr is anExpr, so it must have a type. In many cases the truetype can’t really be known until the code is corrected (e.g. a call to afunction that doesn’t exist). And it means that we can’t properly perform typechecks on some containing constructs, such asreturn42+unknownFunction().

To model this, we generalize the concept of dependence from C++ templates tomean dependence on a template parameter or how an error is repaired. TheRecoveryExprunknownFunction() has the totally unknown typeDependentTy, and this suppresses type-based analysis in the same way itwould inside a template.

In cases where we are confident about the concrete type (e.g. the return typefor a broken non-overloaded function call), theRecoveryExpr will have thistype. This allows more code to be typechecked, and produces a better AST andmore diagnostics. For example:

unknownFunction().size()// .size() is a CXXDependentScopeMemberExprstd::string(42).size()// .size() is a resolved MemberExpr

Whether or not theRecoveryExpr has a dependent type, it is alwaysconsidered value-dependent, because its value isn’t well-defined until the erroris resolved. Among other things, this means that clang doesn’t emit more errorswhere a RecoveryExpr is used as a constant (e.g. array size), but also won’t tryto evaluate it.

ContainsErrors bit¶

Beyond the template dependence bits, we add a new “ContainsErrors” bit toexpress “Does this expression or anything within it contain errors” semantic,this bit is always set for RecoveryExpr, and propagated to other related nodes.This provides a fast way to query whether any (recursive) child of an expressionhad an error, which is often used to improve diagnostics.

// C++voidrecoveryExpr(intabc){unknownFunction();// type-dependent, value-dependent, contains-errorsstd::string(42).size();// value-dependent, contains-errors,// not type-dependent, as we know the type is std::string}

// CvoidrecoveryExpr(intabc){unknownVar+abc;// type-dependent, value-dependent, contains-errors}

Abstract Syntax Graph¶

Despite the name, the Clang AST is not a tree. It is a directed graph withcycles. One example of a cycle is the connection between aClassTemplateDecl and its “templated”CXXRecordDecl. ThetemplatedCXXRecordDecl represents all the fields and methods inside the classtemplate, while theClassTemplateDecl holds the information which isrelated to being a template, i.e. template arguments, etc. We can get thetemplated class (theCXXRecordDecl) of aClassTemplateDecl withClassTemplateDecl::getTemplatedDecl(). And we can get back a pointer of the“described” class template from thetemplated class:CXXRecordDecl::getDescribedTemplate(). So, this is a cycle between twonodes: between thetemplated and thedescribed node. There may be variousother kinds of cycles in the AST especially in case of declarations.

Structural Equivalency¶

Importing one AST node copies that node into the destinationASTContext. Tocopy one node means that we create a new node in the “to” context then we setits properties to be equal to the properties of the source node. Before thecopy, we make sure that the source node is notstructurally equivalent to anyexisting node in the destination context. If it happens to be equivalent thenwe skip the copy.

The informal definition of structural equivalency is the following:Two nodes arestructurally equivalent if they are

• builtin types and refer to the same type, e.g.int andint arestructurally equivalent,

• function types and all their parameters have structurally equivalent types,

• record types and all their fields in order of their definition have the sameidentifier names and structurally equivalent types,

• variable or function declarations and they have the same identifier name andtheir types are structurally equivalent.

In C, two types are structurally equivalent if they arecompatible types. Fora formal definition ofcompatible types, please refer to 6.2.7/1 in the C11standard. However, there is no definition forcompatible types in the C++standard. Still, we extend the definition of structural equivalency totemplates and their instantiations similarly: besides checking the previouslymentioned properties, we have to check for equivalent templateparameters/arguments, etc.

The structural equivalent check can be and is used independently from theASTImporter, e.g. theclang::Sema class uses it also.

The equivalence of nodes may depend on the equivalency of other pairs of nodes.Thus, the check is implemented as a parallel graph traversal. We traversethrough the nodes of both graphs at the same time. The actual implementation issimilar to breadth-first-search. Let’s say we start the traverse with the <A,B>pair of nodes. Whenever the traversal reaches a pair <X,Y> then the followingstatements are true:

• A and X are nodes from the same ASTContext.

• B and Y are nodes from the same ASTContext.

• A and B may or may not be from the same ASTContext.

• if A == X and B == Y (pointer equivalency) then (there is a cycle during thetraverse)

  • A and B are structurally equivalent if and only if

    • All dependent nodes on the path from <A,B> to <X,Y> are structurallyequivalent.

When we compare two classes or enums and one of them is incomplete or hasunloaded external lexical declarations then we cannot descend to compare theircontained declarations. So in these cases they are considered equal if theyhave the same names. This is the way how we compare forward declarations withdefinitions.

Redeclaration Chains¶

The early version of theASTImporter’s merge mechanism squashed thedeclarations, i.e. it aimed to have only one declaration instead of maintaininga whole redeclaration chain. This early approach simply skipped importing afunction prototype, but it imported a definition. To demonstrate the problemwith this approach let’s consider an empty “to” context and the followingvirtual function declarations off in the “from” context:

structB{virtualvoidf();};voidB::f(){}// <-- let's import this definition

If we imported the definition with the “squashing” approach then we wouldend-up having one declaration which is indeed a definition, butisVirtual()returnsfalse for it. The reason is that the definition is indeed notvirtual, it is the property of the prototype!

Consequently, we must either set the virtual flag for the definition (but thenwe create a malformed AST which the parser would never create), or we importthe whole redeclaration chain of the function. The most recent version of theASTImporter uses the latter mechanism. We do import all functiondeclarations - regardless if they are definitions or prototypes - in the orderas they appear in the “from” context.

If we have an existing definition in the “to” context, then we cannot importanother definition, we will use the existing definition. However, we can importprototype(s): we chain the newly imported prototype(s) to the existingdefinition. Whenever we import a new prototype from a third context, that willbe added to the end of the redeclaration chain. This may result in longredeclaration chains in certain cases, e.g. if we import from severaltranslation units which include the same header with the prototype.

To mitigate the problem of long redeclaration chains of free functions, wecould compare prototypes to see if they have the same properties and if yesthen we could merge these prototypes. The implementation of squashing ofprototypes for free functions is future work.

Chaining functions this way ensures that we do copy all information from thesource AST. Nonetheless, there is a problem with member functions: While we canhave many prototypes for free functions, we must have only one prototype for amember function.

voidf();// OKvoidf();// OKstructX{voidf();// OKvoidf();// ERROR};voidX::f(){}// OK

Thus, prototypes of member functions must be squashed, we cannot just simplyattach a new prototype to the existing in-class prototype. Consider thefollowing contexts:

// "to" contextstructX{voidf();// D0};

// "from" contextstructX{voidf();// D1};voidX::f(){}// D2

When we import the prototype and the definition off from the “from”context, then the resulting redecl chain will look like thisD0->D2',whereD2' is the copy ofD2 in the “to” context.

Generally speaking, when we import declarations (like enums and classes) we doattach the newly imported declaration to the existing redeclaration chain (ifthere is structural equivalency). We do not import, however, the wholeredeclaration chain as we do in case of functions. Up till now, we haven’tfound any essential property of forward declarations which is similar to thecase of the virtual flag in a member function prototype. In the future, thismay change, though.

Traversal during the Import¶

The node specific import mechanisms are implemented inASTNodeImporter::VisitNode() functions, e.g.VisitFunctionDecl().When we import a declaration then first we import everything which is needed tocall the constructor of that declaration node. Everything which can be setlater is set after the node is created. For example, in case of aFunctionDecl we first import the declaration context in which the functionis declared, then we create theFunctionDecl and only then we import thebody of the function. This means there are implicit dependencies between ASTnodes. These dependencies determine the order in which we visit nodes in the“from” context. As with the regular graph traversal algorithms like DFS, wekeep track which nodes we have already visited inASTImporter::ImportedDecls. Whenever we create a node then we immediatelyadd that to theImportedDecls. We must not start the import of any otherdeclarations before we keep track of the newly created one. This is essential,otherwise, we would not be able to handle circular dependencies. To enforcethis, we wrap all constructor calls of all AST nodes inGetImportedOrCreateDecl(). This wrapper ensures that all newly createddeclarations are immediately marked as imported; also, if a declaration isalready marked as imported then we just return its counterpart in the “to”context. Consequently, calling a declaration’s::Create() function directlywould lead to errors, please don’t do that!

Even with the use ofGetImportedOrCreateDecl() there is still aprobability of having an infinite import recursion if things are imported fromeach other in wrong way. Imagine that during the import ofA, the import ofB is requested before we could create the node forA (the constructorneeds a reference toB). And the same could be true for the import ofB(A is requested to be imported before we could create the node forB).In case of thetemplated-described swing we takeextra attention to break the cyclical dependency: we import and set thedescribed template only after theCXXRecordDecl is created. As a bestpractice, before creating the node in the “to” context, avoid importing ofother nodes which are not needed for the constructor of nodeA.

Error Handling¶

Every import function returns with either anllvm::Error or anllvm::Expected<T> object. This enforces to check the return value of theimport functions. If there was an error during one import then we return withthat error. (Exception: when we import the members of a class, we collect theindividual errors with each member and we concatenate them in one Errorobject.) We cache these errors in cases of declarations. During the next importcall if there is an existing error we just return with that. So, clients of thelibrary receive an Error object, which they must check.

During import of a specific declaration, it may happen that some AST nodes hadalready been created before we recognize an error. In this case, we signal backthe error to the caller, but the “to” context remains polluted with those nodeswhich had been created. Ideally, those nodes should not had been created, butthat time we did not know about the error, the error happened later. Since theAST is immutable (most of the cases we can’t remove existing nodes) we chooseto mark these nodes as erroneous.

We cache the errors associated with declarations in the “from” context inASTImporter::ImportDeclErrors and the ones which are associated with the“to” context inASTImporterSharedState::ImportErrors. Note that, there maybe several ASTImporter objects which import into the same “to” context but fromdifferent “from” contexts; in this case, they have to share the associatederrors of the “to” context.

When an error happens, that propagates through the call stack, through all thedependant nodes. However, in case of dependency cycles, this is not enough,because we strive to mark the erroneous nodes so clients can act upon. In thosecases, we have to keep track of the errors for those nodes which areintermediate nodes of a cycle.

Animport path is the list of the AST nodes which we visit during an Importcall. If nodeA depends on nodeB then the path contains anA->Bedge. From the call stack of the import functions, we can read the very samepath.

Now imagine the following AST, where the-> represents dependency in termsof the import (all nodes are declarations).

A->B->C->D   `->E

We would like to import A.The import behaves like a DFS, so we will visit the nodes in this order: ABCDE.During the visitation we will have the following import paths:

AABABCABCDABCABABEABA

If during the visit of E there is an error then we set an error for E, then asthe call stack shrinks for B, then for A:

AABABCABCDABCABABE // Error! Set an error to EAB  // Set an error to BA   // Set an error to A

However, during the import we could import C and D without any error and theyare independent of A,B and E. We must not set up an error for C and D. So, atthe end of the import we have an entry inImportDeclErrors for A,B,E butnot for C,D.

Now, what happens if there is a cycle in the import path? Let’s consider thisAST:

A->B->C->A   `->E

During the visitation, we will have the below import paths and if during thevisit of E there is an error then we will set up an error for E,B,A. But what’sup with C?

AABABCABCAABCABABE // Error! Set an error to EAB  // Set an error to BA   // Set an error to A

This time we know that both B and C are dependent on A. This means we must setup an error for C too. As the call stack reverses back we get to A and we mustset up an error to all nodes which depend on A (this includes C). But C is nolonger on the import path, it just had been previously. Such a situation canhappen only if during the visitation we had a cycle. If we didn’t have anycycle, then the normal way of passing an Error object through the call stackcould handle the situation. This is why we must track cycles during the importprocess for each visited declaration.

Lookup Problems¶

When we import a declaration from the source context then we check whether wealready have a structurally equivalent node with the same name in the “to”context. If the “from” node is a definition and the found one is also adefinition, then we do not create a new node, instead, we mark the found nodeas the imported node. If the found definition and the one we want to importhave the same name but they are structurally in-equivalent, then we have an ODRviolation in case of C++. If the “from” node is not a definition then we addthat to the redeclaration chain of the found node. This behaviour is essentialwhen we merge ASTs from different translation units which include the sameheader file(s). For example, we want to have only one definition for the classtemplatestd::vector, even if we included<vector> in severaltranslation units.

To find a structurally equivalent node we can use the regular C/C++ lookupfunctions:DeclContext::noload_lookup() andDeclContext::localUncachedLookup(). These functions do respect the C/C++name hiding rules, thus you cannot find certain declarations in a givendeclaration context. For instance, unnamed declarations (anonymous structs),non-firstfriend declarations and template specializations are hidden. Thisis a problem, because if we use the regular C/C++ lookup then we createredundant AST nodes during the merge! Also, having two instances of the samenode could result in falsestructural in-equivalenciesof other nodes which depend on the duplicated node. Because of these reasons,we created a lookup class which has the sole purpose to register alldeclarations, so later they can be looked up by subsequent import requests.This is theASTImporterLookupTable class. This lookup table should beshared amongst the differentASTImporter instances if they happen to importto the very same “to” context. This is why we can use the importer specificlookup only via theASTImporterSharedState class.

Class Template Instantiations¶

Different translation units may have class template instantiations with thesame template arguments, but with a different set of instantiatedMethodDecls andFieldDecls. Consider the following files:

// x.htemplate<typenameT>structX{inta{0};// FieldDecl with InitListExprX(char):a(3){}// (1)X(int){}// (2)};// foo.cppvoidfoo(){// ClassTemplateSpec with ctor (1): FieldDecl without InitlistExprX<char>xc('c');}// bar.cppvoidbar(){// ClassTemplateSpec with ctor (2): FieldDecl WITH InitlistExprX<char>xc(1);}

Infoo.cpp we use the constructor with number(1), which explicitlyinitializes the membera to3, thus theInitListExpr{0} is notused here and the AST node is not instantiated. However, in the case ofbar.cpp we use the constructor with number(2), which does notexplicitly initialize thea member, so the defaultInitListExpr isneeded and thus instantiated. When we merge the AST offoo.cpp andbar.cpp we must create an AST node for the class template instantiation ofX<char> which has all the required nodes. Therefore, when we find anexistingClassTemplateSpecializationDecl then we merge the fields of theClassTemplateSpecializationDecl in the “from” context in a way that theInitListExpr is copied if not existent yet. The same merge mechanism shouldbe done in the cases of instantiated default arguments and exceptionspecifications of functions.

Visibility of Declarations¶

During import of a global variable with external visibility, the lookup willfind variables (with the same name) but with static visibility (linkage).Clearly, we cannot put them into the same redeclaration chain. The same is truethe in case of functions. Also, we have to take care of other kinds ofdeclarations like enums, classes, etc. if they are in anonymous namespaces.Therefore, we filter the lookup results and consider only those which have thesame visibility as the declaration we currently import.

We consider two declarations in two anonymous namespaces to have the samevisibility only if they are imported from the same AST context.

Strategies to Handle Conflicting Names¶

During the import we lookup existing declarations with the same name. We filterthe lookup results based on theirvisibility. If any of thefound declarations are not structurally equivalent then we bumped to a nameconflict error (ODR violation in C++). In this case, we return with anError and we set up theError object for the declaration. However, someclients of theASTImporter may require a different, perhaps lessconservative and more liberal error handling strategy.

E.g. static analysis clients may benefit if the node is created even if thereis a name conflict. During the CTU analysis of certain projects, we recognizedthat there are global declarations which collide with declarations from othertranslation units, but they are not referenced outside from their translationunit. These declarations should be in an unnamed namespace ideally. If we treatthese collisions liberally then CTU analysis can find more results. Note, thefeature be able to choose between name conflict handling strategies is still anongoing work.

Basic Blocks¶

Concretely, an instance ofCFG is a collection of basic blocks. Each basicblock is an instance ofCFGBlock, which simply contains an ordered sequenceofStmt* (each referring to statements in the AST). The ordering ofstatements within a block indicates unconditional flow of control from onestatement to the next.Conditional control-flow is represented using edges between basic blocks. Thestatements within a givenCFGBlock can be traversed using theCFGBlock::*iterator interface.

ACFG object owns the instances ofCFGBlock within the control-flowgraph it represents. EachCFGBlock within a CFG is also uniquely numbered(accessible viaCFGBlock::getBlockID()). Currently the number is based onthe ordering the blocks were created, but no assumptions should be made on howCFGBlocks are numbered other than their numbers are unique and that theyare numbered from 0..N-1 (where N is the number of basic blocks in the CFG).

Entry and Exit Blocks¶

Each instance ofCFG contains two special blocks: anentry block(accessible viaCFG::getEntry()), which has no incoming edges, and anexit block (accessible viaCFG::getExit()), which has no outgoing edges.Neither block contains any statements, and they serve the role of providing aclear entrance and exit for a body of code such as a function body. Thepresence of these empty blocks greatly simplifies the implementation of manyanalyses built on top of CFGs.

Conditional Control-Flow¶

Conditional control-flow (such as those induced by if-statements and loops) isrepresented as edges betweenCFGBlocks. Because different C languageconstructs can induce control-flow, eachCFGBlock also records an extraStmt* that represents theterminator of the block. A terminator issimply the statement that caused the control-flow, and is used to identify thenature of the conditional control-flow between blocks. For example, in thecase of an if-statement, the terminator refers to theIfStmt object in theAST that represented the given branch.

To illustrate, consider the following code example:

intfoo(intx){x=x+1;if(x>2)x++;else{x+=2;x*=2;}returnx;}

After invoking the parser+semantic analyzer on this code fragment, the AST ofthe body offoo is referenced by a singleStmt*. We can then constructan instance ofCFG representing the control-flow graph of this functionbody by single call to a static class method:

Stmt*FooBody=...std::unique_ptr<CFG>FooCFG=CFG::buildCFG(FooBody);

Along with providing an interface to iterate over itsCFGBlocks, theCFG class also provides methods that are useful for debugging andvisualizing CFGs. For example, the methodCFG::dump() dumps apretty-printed version of the CFG to standard error. This is especially usefulwhen one is using a debugger such as gdb. For example, here is the output ofFooCFG->dump():

[ B5 (ENTRY) ]   Predecessors (0):   Successors (1): B4[ B4 ]   1: x = x + 1   2: (x > 2)   T: if [B4.2]   Predecessors (1): B5   Successors (2): B3 B2[ B3 ]   1: x++   Predecessors (1): B4   Successors (1): B1[ B2 ]   1: x += 2   2: x *= 2   Predecessors (1): B4   Successors (1): B1[ B1 ]   1: return x;   Predecessors (2): B2 B3   Successors (1): B0[ B0 (EXIT) ]   Predecessors (1): B1   Successors (0):

For each block, the pretty-printed output displays for each block the number ofpredecessor blocks (blocks that have outgoing control-flow to the givenblock) andsuccessor blocks (blocks that have control-flow that have incomingcontrol-flow from the given block). We can also clearly see the special entryand exit blocks at the beginning and end of the pretty-printed output. For theentry block (block B5), the number of predecessor blocks is 0, while for theexit block (block B0) the number of successor blocks is 0.

The most interesting block here is B4, whose outgoing control-flow representsthe branching caused by the sole if-statement infoo. Of particularinterest is the second statement in the block,(x>2), and the terminator,printed asif[B4.2]. The second statement represents the evaluation ofthe condition of the if-statement, which occurs before the actual branching ofcontrol-flow. Within theCFGBlock for B4, theStmt* for the secondstatement refers to the actual expression in the AST for(x>2). Thuspointers to subclasses ofExpr can appear in the list of statements in ablock, and not just subclasses ofStmt that refer to proper C statements.

The terminator of block B4 is a pointer to theIfStmt object in the AST.The pretty-printer outputsif[B4.2] because the condition expression ofthe if-statement has an actual place in the basic block, and thus theterminator is essentiallyreferring to the expression that is the secondstatement of block B4 (i.e., B4.2). In this manner, conditions forcontrol-flow (which also includes conditions for loops and switch statements)are hoisted into the actual basic block.

Implementation Approach¶

After trying several different approaches, we’ve finally converged on a design(Note, at the time of this writing, not all of this has been implemented,consider this a design goal!). Our basic approach is to define a singlerecursive evaluation method (Expr::Evaluate), which is implementedinAST/ExprConstant.cpp. Given an expression with “scalar” type (integer,fp, complex, or pointer) this method returns the following information:

• Whether the expression is an integer constant expression, a general constantthat was folded but has no side effects, a general constant that was foldedbut that does have side effects, or an uncomputable/unfoldable value.

• If the expression was computable in any way, this method returns theAPValue for the result of the expression.

• If the expression is not evaluatable at all, this method returns informationon one of the problems with the expression. This includes aSourceLocation for where the problem is, and a diagnostic ID that explainsthe problem. The diagnostic should haveERROR type.

• If the expression is not an integer constant expression, this method returnsinformation on one of the problems with the expression. This includes aSourceLocation for where the problem is, and a diagnostic ID thatexplains the problem. The diagnostic should haveEXTENSION type.

This information gives various clients the flexibility that they want, and wewill eventually have some helper methods for various extensions. For example,Sema should have aSema::VerifyIntegerConstantExpression method, whichcallsEvaluate on the expression. If the expression is not foldable, theerror is emitted, and it would returntrue. If the expression is not ani-c-e, theEXTENSION diagnostic is emitted. Finally it would returnfalse to indicate that the AST is OK.

Other clients can use the information in other ways, for example, codegen canjust use expressions that are foldable in any way.

Extensions¶

This section describes how some of the various extensions Clang supportsinteracts with constant evaluation:

• __extension__: The expression form of this extension causes anyevaluatable subexpression to be accepted as an integer constant expression.

• __builtin_constant_p: This returns true (as an integer constantexpression) if the operand evaluates to either a numeric value (that is, nota pointer cast to integral type) of integral, enumeration, floating orcomplex type, or if it evaluates to the address of the first character of astring literal (possibly cast to some other type). As a special case, if__builtin_constant_p is the (potentially parenthesized) condition of aconditional operator expression (”?:”), only the true side of theconditional operator is considered, and it is evaluated with full constantfolding.

• __builtin_choose_expr: The condition is required to be an integerconstant expression, but we accept any constant as an “extension of anextension”. This only evaluates one operand depending on which way thecondition evaluates.

• __builtin_classify_type: This always returns an integer constantexpression.

• __builtin_inf,nan,...: These are treated just like a floating-pointliteral.

• __builtin_abs,copysign,...: These are constant folded as generalconstant expressions.

• __builtin_strlen andstrlen: These are constant folded as integerconstant expressions if the argument is a string literal.

Attribute Basics¶

Attributes in Clang are handled in three stages: parsing into a parsed attributerepresentation, conversion from a parsed attribute into a semantic attribute,and then the semantic handling of the attribute.

Parsing of the attribute is determined by the various syntactic forms attributescan take, such as GNU, C++11, and Microsoft style attributes, as well as otherinformation provided by the table definition of the attribute. Ultimately, theparsed representation of an attribute object is aParsedAttr object.These parsed attributes chain together as a list of parsed attributes attachedto a declarator or declaration specifier. The parsing of attributes is handledautomatically by Clang, except for attributes spelled as so-called “custom”keywords. When implementing a custom keyword attribute, the parsing of thekeyword and creation of theParsedAttr object must be done manually.

Eventually,Sema::ProcessDeclAttributeList() is called with aDecl andaParsedAttr, at which point the parsed attribute can be transformedinto a semantic attribute. The process by which a parsed attribute is convertedinto a semantic attribute depends on the attribute definition and semanticrequirements of the attribute. The end result, however, is that the semanticattribute object is attached to theDecl object, and can be obtained by acall toDecl::getAttr<T>(). Similarly, for statement attributes,Sema::ProcessStmtAttributes() is called with aStmt a list ofParsedAttr objects to be converted into a semantic attribute.

The structure of the semantic attribute is also governed by the attributedefinition given in Attr.td. This definition is used to automatically generatefunctionality used for the implementation of the attribute, such as a classderived fromclang::Attr, information for the parser to use, automatedsemantic checking for some attributes, etc.

include/clang/Basic/Attr.td¶

The first step to adding a new attribute to Clang is to add its definition toinclude/clang/Basic/Attr.td.This tablegen definition must derive from theAttr (tablegen, notsemantic) type, or one of its derivatives. Most attributes will derive from theInheritableAttr type, which specifies that the attribute can be inherited bylater redeclarations of theDecl it is associated with.InheritableParamAttr is similar toInheritableAttr, except that theattribute is written on a parameter instead of a declaration. If the attributeapplies to statements, it should inherit fromStmtAttr. If the attribute isintended to apply to a type instead of a declaration, such an attribute shouldderive fromTypeAttr, and will generally not be given an AST representation.(Note that this document does not cover the creation of type attributes.) Anattribute that inherits fromIgnoredAttr is parsed, but will generate anignored attribute diagnostic when used, which may be useful when an attribute issupported by another vendor but not supported by clang.

The definition will specify several key pieces of information, such as thesemantic name of the attribute, the spellings the attribute supports, thearguments the attribute expects, and more. Most members of theAttr tablegentype do not require definitions in the derived definition as the defaultsuffice. However, every attribute must specify at least a spelling list, asubject list, and a documentation list.

clang-tblgen-gen-attr-docs-I/path/to/clang/include/path/to/clang/include/clang/Basic/Attr.td-o/path/to/clang/docs/AttributeReference.rst

Boilerplate¶

All semantic processing of declaration attributes happens inlib/Sema/SemaDeclAttr.cpp,and generally starts in theProcessDeclAttribute() function. If theattribute has theSimpleHandler field set to1 then the function toprocess the attribute will be automatically generated, and nothing needs to bedone here. Otherwise, write a newhandleYourAttr() function, and add that tothe switch statement. Please do not implement handling logic directly in thecase for the attribute.

Unless otherwise specified by the attribute definition, common semantic checkingof the parsed attribute is handled automatically. This includes diagnosingparsed attributes that do not appertain to the givenDecl orStmt,ensuring the correct minimum number of arguments are passed, etc.

If the attribute adds additional warnings, define aDiagGroup ininclude/clang/Basic/DiagnosticGroups.tdnamed after the attribute’sSpelling with “_”s replaced by “-“s. If thereis only a single diagnostic, it is permissible to useInGroup<DiagGroup<"your-attribute">>directly inDiagnosticSemaKinds.td

All semantic diagnostics generated for your attribute, including automatically-generated ones (such as subjects and argument counts), should have acorresponding test case.

Semantic handling¶

Most attributes are implemented to have some effect on the compiler. Forinstance, to modify the way code is generated, or to add extra semantic checksfor an analysis pass, etc. Having added the attribute definition and conversionto the semantic representation for the attribute, what remains is to implementthe custom logic requiring use of the attribute.

Theclang::Decl object can be queried for the presence or absence of anattribute usinghasAttr<T>(). To obtain a pointer to the semanticrepresentation of the attribute,getAttr<T> may be used.

Theclang::AttributedStmt object can be queried for the presence or absenceof an attribute by callinggetAttrs() and looping over the list ofattributes.

Verifying Diagnostics¶

Clang-cc1 supports the-verify command line option as a way tovalidate diagnostic behavior. This option will use special comments within thetest file to verify that expected diagnostics appear in the correct sourcelocations. If all of the expected diagnostics match the actual output of Clang,then the invocation will return normally. If there are discrepancies betweenthe expected and actual output, Clang will emit detailed information aboutwhich expected diagnostics were not seen or which unexpected diagnostics wereseen, etc. A complete example is:

If the test is run and the expected error is emitted on the expected line, thediagnostic verifier will pass. However, if the expected error does not appearor appears in a different location than expected, or if additional diagnosticsappear, the diagnostic verifier will fail and emit information as to why.

The-verify command optionally accepts a comma-delimited list of one ormore verification prefixes that can be used to craft those special comments.Each prefix must start with a letter and contain only alphanumeric characters,hyphens, and underscores.-verify by itself is equivalent to-verify=expected, meaning that special comments will start withexpected. Using different prefixes makes it easier to have separateRUN: lines in the same test file which result in differing diagnosticbehavior. For example:

// RUN: %clang_cc1 -verify=foo,bar %sintA=B;// foo-error {{use of undeclared identifier 'B'}}intC=D;// bar-error {{use of undeclared identifier 'D'}}intE=F;// expected-error {{use of undeclared identifier 'F'}}

The verifier will recognizefoo-error andbar-error as special commentsbut will not recognizeexpected-error as one because the-verify linedoes not contain that as a prefix. Thus, this test would fail verificationbecause an unexpected diagnostic would appear on the declaration ofE.

Multiple occurrences accumulate prefixes. For example,-verify-verify=foo,bar-verify=baz is equivalent to-verify=expected,foo,bar,baz.

Specifying Diagnostics¶

Indicating that a line expects an error or a warning is easy. Put a commenton the line that has the diagnostic, useexpected-{error,warning,remark,note} to tag if it’s an expected error,warning, remark, or note (respectively), and place the expected text between{{ and}} markers. The full text doesn’t have to be included, onlyenough to ensure that the correct diagnostic was emitted. (Note: full textshould be included in test cases unless there is a compelling reason to usetruncated text instead.)

For a full description of the matching behavior, including more complexmatching scenarios, seematching below.

Here’s an example of the most commonly used way to specify expecteddiagnostics:

intA=B;// expected-error {{use of undeclared identifier 'B'}}

You can place as many diagnostics on one line as you wish. To make the codemore readable, you can use slash-newline to separate out the diagnostics.

Alternatively, it is possible to specify the line on which the diagnosticshould appear by appending@<line> toexpected-<type>, for example:

#warning some text// expected-warning@10 {{some text}}

The line number may be absolute (as above), or relative to the current line byprefixing the number with either+ or-.

If the diagnostic is generated in a separate file, for example in a sharedheader file, it may be beneficial to be able to declare the file in which thediagnostic will appear, rather than placing theexpected-* directive in theactual file itself. This can be done using the following syntax:

// expected-error@path/include.h:15 {{error message}}

The path can be absolute or relative and the same search paths will be used asfor#include directives. The line number in an external file may besubstituted with* meaning that any line number will match (useful wherethe included file is, for example, a system header where the actual line numbermay change and is not critical).

As an alternative to specifying a fixed line number, the location of adiagnostic can instead be indicated by a marker of the form#<marker>.Markers are specified by including them in a comment, and then referenced byappending the marker to the diagnostic with@#<marker>, as with:

#warning some text// #1// ... other code ...// expected-warning@#1 {{some text}}

The name of a marker used in a directive must be unique within the compilation.

The simple syntax above allows each specification to match exactly onediagnostic. You can use the extended syntax to customize this. The extendedsyntax isexpected-<type><n>{{diagtext}}, where<type> is one oferror,warning,remark, ornote, and<n> is a positiveinteger. This allows the diagnostic to appear as many times as specified. Forexample:

voidf();// expected-note 2 {{previous declaration is here}}

Where the diagnostic is expected to occur a minimum number of times, this canbe specified by appending a+ to the number. For example:

voidf();// expected-note 0+ {{previous declaration is here}}voidg();// expected-note 1+ {{previous declaration is here}}

In the first example, the diagnostic becomes optional, i.e. it will beswallowed if it occurs, but will not generate an error if it does not occur. Inthe second example, the diagnostic must occur at least once. As a short-hand,“one or more” can be specified simply by+. For example:

voidg();// expected-note + {{previous declaration is here}}

A range can also be specified by<n>-<m>. For example:

voidf();// expected-note 0-1 {{previous declaration is here}}

In this example, the diagnostic may appear only once, if at all.

// expected-note {{{evaluates to '{{2, 3, 4}} == {0, 3, 4}'}}}

expected-error-re {{format specifies type 'wchar_t **' (aka '{{.+}}')}}

// expected-error {{variable has incomplete type 'struct s'}}// expected-error {{variable has incomplete type}}// expected-error {{{variable has incomplete type}}}// expected-error {{{{variable has incomplete type}}}}// expected-error-re {{variable has type 'struct {{.}}'}}// expected-error-re {{variable has type 'struct {{.*}}'}}// expected-error-re {{variable has type 'struct {{(.*)}}'}}// expected-error-re {{variable has type 'struct{{[[:space:]](.*)}}'}}