InternalsManual.rst source code [clang_source_code/docs/InternalsManual.rst]

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

Clang Project