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