Home | History | Annotate | Download | only in docs
      1 ========================================
      2 Precompiled Header and Modules Internals
      3 ========================================
      4 
      5 .. contents::
      6    :local:
      7 
      8 This document describes the design and implementation of Clang's precompiled
      9 headers (PCH) and modules.  If you are interested in the end-user view, please
     10 see the :ref:`User's Manual <usersmanual-precompiled-headers>`.
     11 
     12 Using Precompiled Headers with ``clang``
     13 ----------------------------------------
     14 
     15 The Clang compiler frontend, ``clang -cc1``, supports two command line options
     16 for generating and using PCH files.
     17 
     18 To generate PCH files using ``clang -cc1``, use the option `-emit-pch`:
     19 
     20 .. code-block:: bash
     21 
     22   $ clang -cc1 test.h -emit-pch -o test.h.pch
     23 
     24 This option is transparently used by ``clang`` when generating PCH files.  The
     25 resulting PCH file contains the serialized form of the compiler's internal
     26 representation after it has completed parsing and semantic analysis.  The PCH
     27 file can then be used as a prefix header with the `-include-pch`
     28 option:
     29 
     30 .. code-block:: bash
     31 
     32   $ clang -cc1 -include-pch test.h.pch test.c -o test.s
     33 
     34 Design Philosophy
     35 -----------------
     36 
     37 Precompiled headers are meant to improve overall compile times for projects, so
     38 the design of precompiled headers is entirely driven by performance concerns.
     39 The use case for precompiled headers is relatively simple: when there is a
     40 common set of headers that is included in nearly every source file in the
     41 project, we *precompile* that bundle of headers into a single precompiled
     42 header (PCH file).  Then, when compiling the source files in the project, we
     43 load the PCH file first (as a prefix header), which acts as a stand-in for that
     44 bundle of headers.
     45 
     46 A precompiled header implementation improves performance when:
     47 
     48 * Loading the PCH file is significantly faster than re-parsing the bundle of
     49   headers stored within the PCH file.  Thus, a precompiled header design
     50   attempts to minimize the cost of reading the PCH file.  Ideally, this cost
     51   should not vary with the size of the precompiled header file.
     52 
     53 * The cost of generating the PCH file initially is not so large that it
     54   counters the per-source-file performance improvement due to eliminating the
     55   need to parse the bundled headers in the first place.  This is particularly
     56   important on multi-core systems, because PCH file generation serializes the
     57   build when all compilations require the PCH file to be up-to-date.
     58 
     59 Modules, as implemented in Clang, use the same mechanisms as precompiled
     60 headers to save a serialized AST file (one per module) and use those AST
     61 modules.  From an implementation standpoint, modules are a generalization of
     62 precompiled headers, lifting a number of restrictions placed on precompiled
     63 headers.  In particular, there can only be one precompiled header and it must
     64 be included at the beginning of the translation unit.  The extensions to the
     65 AST file format required for modules are discussed in the section on
     66 :ref:`modules <pchinternals-modules>`.
     67 
     68 Clang's AST files are designed with a compact on-disk representation, which
     69 minimizes both creation time and the time required to initially load the AST
     70 file.  The AST file itself contains a serialized representation of Clang's
     71 abstract syntax trees and supporting data structures, stored using the same
     72 compressed bitstream as `LLVM's bitcode file format
     73 <http://llvm.org/docs/BitCodeFormat.html>`_.
     74 
     75 Clang's AST files are loaded "lazily" from disk.  When an AST file is initially
     76 loaded, Clang reads only a small amount of data from the AST file to establish
     77 where certain important data structures are stored.  The amount of data read in
     78 this initial load is independent of the size of the AST file, such that a
     79 larger AST file does not lead to longer AST load times.  The actual header data
     80 in the AST file --- macros, functions, variables, types, etc. --- is loaded
     81 only when it is referenced from the user's code, at which point only that
     82 entity (and those entities it depends on) are deserialized from the AST file.
     83 With this approach, the cost of using an AST file for a translation unit is
     84 proportional to the amount of code actually used from the AST file, rather than
     85 being proportional to the size of the AST file itself.
     86 
     87 When given the `-print-stats` option, Clang produces statistics
     88 describing how much of the AST file was actually loaded from disk.  For a
     89 simple "Hello, World!" program that includes the Apple ``Cocoa.h`` header
     90 (which is built as a precompiled header), this option illustrates how little of
     91 the actual precompiled header is required:
     92 
     93 .. code-block:: none
     94 
     95   *** AST File Statistics:
     96     895/39981 source location entries read (2.238563%)
     97     19/15315 types read (0.124061%)
     98     20/82685 declarations read (0.024188%)
     99     154/58070 identifiers read (0.265197%)
    100     0/7260 selectors read (0.000000%)
    101     0/30842 statements read (0.000000%)
    102     4/8400 macros read (0.047619%)
    103     1/4995 lexical declcontexts read (0.020020%)
    104     0/4413 visible declcontexts read (0.000000%)
    105     0/7230 method pool entries read (0.000000%)
    106     0 method pool misses
    107 
    108 For this small program, only a tiny fraction of the source locations, types,
    109 declarations, identifiers, and macros were actually deserialized from the
    110 precompiled header.  These statistics can be useful to determine whether the
    111 AST file implementation can be improved by making more of the implementation
    112 lazy.
    113 
    114 Precompiled headers can be chained.  When you create a PCH while including an
    115 existing PCH, Clang can create the new PCH by referencing the original file and
    116 only writing the new data to the new file.  For example, you could create a PCH
    117 out of all the headers that are very commonly used throughout your project, and
    118 then create a PCH for every single source file in the project that includes the
    119 code that is specific to that file, so that recompiling the file itself is very
    120 fast, without duplicating the data from the common headers for every file.  The
    121 mechanisms behind chained precompiled headers are discussed in a :ref:`later
    122 section <pchinternals-chained>`.
    123 
    124 AST File Contents
    125 -----------------
    126 
    127 An AST file produced by clang is an object file container with a ``clangast``
    128 (COFF) or ``__clangast`` (ELF and Mach-O) section containing the serialized AST.
    129 Other target-specific sections in the object file container are used to hold
    130 debug information for the data types defined in the AST.  Tools built on top of
    131 libclang that do not need debug information may also produce raw AST files that
    132 only contain the serialized AST.
    133 
    134 The ``clangast`` section is organized into several different blocks, each of
    135 which contains the serialized representation of a part of Clang's internal
    136 representation.  Each of the blocks corresponds to either a block or a record
    137 within `LLVM's bitstream format <http://llvm.org/docs/BitCodeFormat.html>`_.
    138 The contents of each of these logical blocks are described below.
    139 
    140 .. image:: PCHLayout.png
    141 
    142 The ``llvm-objdump`` utility provides a ``-raw-clang-ast`` option to extract the
    143 binary contents of the AST section from an object file container.
    144 
    145 The `llvm-bcanalyzer <http://llvm.org/docs/CommandGuide/llvm-bcanalyzer.html>`_
    146 utility can be used to examine the actual structure of the bitstream for the AST
    147 section.  This information can be used both to help understand the structure of
    148 the AST section and to isolate areas where the AST representation can still be
    149 optimized, e.g., through the introduction of abbreviations.
    150 
    151 
    152 Metadata Block
    153 ^^^^^^^^^^^^^^
    154 
    155 The metadata block contains several records that provide information about how
    156 the AST file was built.  This metadata is primarily used to validate the use of
    157 an AST file.  For example, a precompiled header built for a 32-bit x86 target
    158 cannot be used when compiling for a 64-bit x86 target.  The metadata block
    159 contains information about:
    160 
    161 Language options
    162   Describes the particular language dialect used to compile the AST file,
    163   including major options (e.g., Objective-C support) and more minor options
    164   (e.g., support for "``//``" comments).  The contents of this record correspond to
    165   the ``LangOptions`` class.
    166 
    167 Target architecture
    168   The target triple that describes the architecture, platform, and ABI for
    169   which the AST file was generated, e.g., ``i386-apple-darwin9``.
    170 
    171 AST version
    172   The major and minor version numbers of the AST file format.  Changes in the
    173   minor version number should not affect backward compatibility, while changes
    174   in the major version number imply that a newer compiler cannot read an older
    175   precompiled header (and vice-versa).
    176 
    177 Original file name
    178   The full path of the header that was used to generate the AST file.
    179 
    180 Predefines buffer
    181   Although not explicitly stored as part of the metadata, the predefines buffer
    182   is used in the validation of the AST file.  The predefines buffer itself
    183   contains code generated by the compiler to initialize the preprocessor state
    184   according to the current target, platform, and command-line options.  For
    185   example, the predefines buffer will contain "``#define __STDC__ 1``" when we
    186   are compiling C without Microsoft extensions.  The predefines buffer itself
    187   is stored within the :ref:`pchinternals-sourcemgr`, but its contents are
    188   verified along with the rest of the metadata.
    189 
    190 A chained PCH file (that is, one that references another PCH) and a module
    191 (which may import other modules) have additional metadata containing the list
    192 of all AST files that this AST file depends on.  Each of those files will be
    193 loaded along with this AST file.
    194 
    195 For chained precompiled headers, the language options, target architecture and
    196 predefines buffer data is taken from the end of the chain, since they have to
    197 match anyway.
    198 
    199 .. _pchinternals-sourcemgr:
    200 
    201 Source Manager Block
    202 ^^^^^^^^^^^^^^^^^^^^
    203 
    204 The source manager block contains the serialized representation of Clang's
    205 :ref:`SourceManager <SourceManager>` class, which handles the mapping from
    206 source locations (as represented in Clang's abstract syntax tree) into actual
    207 column/line positions within a source file or macro instantiation.  The AST
    208 file's representation of the source manager also includes information about all
    209 of the headers that were (transitively) included when building the AST file.
    210 
    211 The bulk of the source manager block is dedicated to information about the
    212 various files, buffers, and macro instantiations into which a source location
    213 can refer.  Each of these is referenced by a numeric "file ID", which is a
    214 unique number (allocated starting at 1) stored in the source location.  Clang
    215 serializes the information for each kind of file ID, along with an index that
    216 maps file IDs to the position within the AST file where the information about
    217 that file ID is stored.  The data associated with a file ID is loaded only when
    218 required by the front end, e.g., to emit a diagnostic that includes a macro
    219 instantiation history inside the header itself.
    220 
    221 The source manager block also contains information about all of the headers
    222 that were included when building the AST file.  This includes information about
    223 the controlling macro for the header (e.g., when the preprocessor identified
    224 that the contents of the header dependent on a macro like
    225 ``LLVM_CLANG_SOURCEMANAGER_H``).
    226 
    227 .. _pchinternals-preprocessor:
    228 
    229 Preprocessor Block
    230 ^^^^^^^^^^^^^^^^^^
    231 
    232 The preprocessor block contains the serialized representation of the
    233 preprocessor.  Specifically, it contains all of the macros that have been
    234 defined by the end of the header used to build the AST file, along with the
    235 token sequences that comprise each macro.  The macro definitions are only read
    236 from the AST file when the name of the macro first occurs in the program.  This
    237 lazy loading of macro definitions is triggered by lookups into the
    238 :ref:`identifier table <pchinternals-ident-table>`.
    239 
    240 .. _pchinternals-types:
    241 
    242 Types Block
    243 ^^^^^^^^^^^
    244 
    245 The types block contains the serialized representation of all of the types
    246 referenced in the translation unit.  Each Clang type node (``PointerType``,
    247 ``FunctionProtoType``, etc.) has a corresponding record type in the AST file.
    248 When types are deserialized from the AST file, the data within the record is
    249 used to reconstruct the appropriate type node using the AST context.
    250 
    251 Each type has a unique type ID, which is an integer that uniquely identifies
    252 that type.  Type ID 0 represents the NULL type, type IDs less than
    253 ``NUM_PREDEF_TYPE_IDS`` represent predefined types (``void``, ``float``, etc.),
    254 while other "user-defined" type IDs are assigned consecutively from
    255 ``NUM_PREDEF_TYPE_IDS`` upward as the types are encountered.  The AST file has
    256 an associated mapping from the user-defined types block to the location within
    257 the types block where the serialized representation of that type resides,
    258 enabling lazy deserialization of types.  When a type is referenced from within
    259 the AST file, that reference is encoded using the type ID shifted left by 3
    260 bits.  The lower three bits are used to represent the ``const``, ``volatile``,
    261 and ``restrict`` qualifiers, as in Clang's :ref:`QualType <QualType>` class.
    262 
    263 .. _pchinternals-decls:
    264 
    265 Declarations Block
    266 ^^^^^^^^^^^^^^^^^^
    267 
    268 The declarations block contains the serialized representation of all of the
    269 declarations referenced in the translation unit.  Each Clang declaration node
    270 (``VarDecl``, ``FunctionDecl``, etc.) has a corresponding record type in the
    271 AST file.  When declarations are deserialized from the AST file, the data
    272 within the record is used to build and populate a new instance of the
    273 corresponding ``Decl`` node.  As with types, each declaration node has a
    274 numeric ID that is used to refer to that declaration within the AST file.  In
    275 addition, a lookup table provides a mapping from that numeric ID to the offset
    276 within the precompiled header where that declaration is described.
    277 
    278 Declarations in Clang's abstract syntax trees are stored hierarchically.  At
    279 the top of the hierarchy is the translation unit (``TranslationUnitDecl``),
    280 which contains all of the declarations in the translation unit but is not
    281 actually written as a specific declaration node.  Its child declarations (such
    282 as functions or struct types) may also contain other declarations inside them,
    283 and so on.  Within Clang, each declaration is stored within a :ref:`declaration
    284 context <DeclContext>`, as represented by the ``DeclContext`` class.
    285 Declaration contexts provide the mechanism to perform name lookup within a
    286 given declaration (e.g., find the member named ``x`` in a structure) and
    287 iterate over the declarations stored within a context (e.g., iterate over all
    288 of the fields of a structure for structure layout).
    289 
    290 In Clang's AST file format, deserializing a declaration that is a
    291 ``DeclContext`` is a separate operation from deserializing all of the
    292 declarations stored within that declaration context.  Therefore, Clang will
    293 deserialize the translation unit declaration without deserializing the
    294 declarations within that translation unit.  When required, the declarations
    295 stored within a declaration context will be deserialized.  There are two
    296 representations of the declarations within a declaration context, which
    297 correspond to the name-lookup and iteration behavior described above:
    298 
    299 * When the front end performs name lookup to find a name ``x`` within a given
    300   declaration context (for example, during semantic analysis of the expression
    301   ``p->x``, where ``p``'s type is defined in the precompiled header), Clang
    302   refers to an on-disk hash table that maps from the names within that
    303   declaration context to the declaration IDs that represent each visible
    304   declaration with that name.  The actual declarations will then be
    305   deserialized to provide the results of name lookup.
    306 * When the front end performs iteration over all of the declarations within a
    307   declaration context, all of those declarations are immediately
    308   de-serialized.  For large declaration contexts (e.g., the translation unit),
    309   this operation is expensive; however, large declaration contexts are not
    310   traversed in normal compilation, since such a traversal is unnecessary.
    311   However, it is common for the code generator and semantic analysis to
    312   traverse declaration contexts for structs, classes, unions, and
    313   enumerations, although those contexts contain relatively few declarations in
    314   the common case.
    315 
    316 Statements and Expressions
    317 ^^^^^^^^^^^^^^^^^^^^^^^^^^
    318 
    319 Statements and expressions are stored in the AST file in both the :ref:`types
    320 <pchinternals-types>` and the :ref:`declarations <pchinternals-decls>` blocks,
    321 because every statement or expression will be associated with either a type or
    322 declaration.  The actual statement and expression records are stored
    323 immediately following the declaration or type that owns the statement or
    324 expression.  For example, the statement representing the body of a function
    325 will be stored directly following the declaration of the function.
    326 
    327 As with types and declarations, each statement and expression kind in Clang's
    328 abstract syntax tree (``ForStmt``, ``CallExpr``, etc.) has a corresponding
    329 record type in the AST file, which contains the serialized representation of
    330 that statement or expression.  Each substatement or subexpression within an
    331 expression is stored as a separate record (which keeps most records to a fixed
    332 size).  Within the AST file, the subexpressions of an expression are stored, in
    333 reverse order, prior to the expression that owns those expression, using a form
    334 of `Reverse Polish Notation
    335 <http://en.wikipedia.org/wiki/Reverse_Polish_notation>`_.  For example, an
    336 expression ``3 - 4 + 5`` would be represented as follows:
    337 
    338 +-----------------------+
    339 | ``IntegerLiteral(5)`` |
    340 +-----------------------+
    341 | ``IntegerLiteral(4)`` |
    342 +-----------------------+
    343 | ``IntegerLiteral(3)`` |
    344 +-----------------------+
    345 | ``IntegerLiteral(-)`` |
    346 +-----------------------+
    347 | ``IntegerLiteral(+)`` |
    348 +-----------------------+
    349 |       ``STOP``        |
    350 +-----------------------+
    351 
    352 When reading this representation, Clang evaluates each expression record it
    353 encounters, builds the appropriate abstract syntax tree node, and then pushes
    354 that expression on to a stack.  When a record contains *N* subexpressions ---
    355 ``BinaryOperator`` has two of them --- those expressions are popped from the
    356 top of the stack.  The special STOP code indicates that we have reached the end
    357 of a serialized expression or statement; other expression or statement records
    358 may follow, but they are part of a different expression.
    359 
    360 .. _pchinternals-ident-table:
    361 
    362 Identifier Table Block
    363 ^^^^^^^^^^^^^^^^^^^^^^
    364 
    365 The identifier table block contains an on-disk hash table that maps each
    366 identifier mentioned within the AST file to the serialized representation of
    367 the identifier's information (e.g, the ``IdentifierInfo`` structure).  The
    368 serialized representation contains:
    369 
    370 * The actual identifier string.
    371 * Flags that describe whether this identifier is the name of a built-in, a
    372   poisoned identifier, an extension token, or a macro.
    373 * If the identifier names a macro, the offset of the macro definition within
    374   the :ref:`pchinternals-preprocessor`.
    375 * If the identifier names one or more declarations visible from translation
    376   unit scope, the :ref:`declaration IDs <pchinternals-decls>` of these
    377   declarations.
    378 
    379 When an AST file is loaded, the AST file reader mechanism introduces itself
    380 into the identifier table as an external lookup source.  Thus, when the user
    381 program refers to an identifier that has not yet been seen, Clang will perform
    382 a lookup into the identifier table.  If an identifier is found, its contents
    383 (macro definitions, flags, top-level declarations, etc.) will be deserialized,
    384 at which point the corresponding ``IdentifierInfo`` structure will have the
    385 same contents it would have after parsing the headers in the AST file.
    386 
    387 Within the AST file, the identifiers used to name declarations are represented
    388 with an integral value.  A separate table provides a mapping from this integral
    389 value (the identifier ID) to the location within the on-disk hash table where
    390 that identifier is stored.  This mapping is used when deserializing the name of
    391 a declaration, the identifier of a token, or any other construct in the AST
    392 file that refers to a name.
    393 
    394 .. _pchinternals-method-pool:
    395 
    396 Method Pool Block
    397 ^^^^^^^^^^^^^^^^^
    398 
    399 The method pool block is represented as an on-disk hash table that serves two
    400 purposes: it provides a mapping from the names of Objective-C selectors to the
    401 set of Objective-C instance and class methods that have that particular
    402 selector (which is required for semantic analysis in Objective-C) and also
    403 stores all of the selectors used by entities within the AST file.  The design
    404 of the method pool is similar to that of the :ref:`identifier table
    405 <pchinternals-ident-table>`: the first time a particular selector is formed
    406 during the compilation of the program, Clang will search in the on-disk hash
    407 table of selectors; if found, Clang will read the Objective-C methods
    408 associated with that selector into the appropriate front-end data structure
    409 (``Sema::InstanceMethodPool`` and ``Sema::FactoryMethodPool`` for instance and
    410 class methods, respectively).
    411 
    412 As with identifiers, selectors are represented by numeric values within the AST
    413 file.  A separate index maps these numeric selector values to the offset of the
    414 selector within the on-disk hash table, and will be used when de-serializing an
    415 Objective-C method declaration (or other Objective-C construct) that refers to
    416 the selector.
    417 
    418 AST Reader Integration Points
    419 -----------------------------
    420 
    421 The "lazy" deserialization behavior of AST files requires their integration
    422 into several completely different submodules of Clang.  For example, lazily
    423 deserializing the declarations during name lookup requires that the name-lookup
    424 routines be able to query the AST file to find entities stored there.
    425 
    426 For each Clang data structure that requires direct interaction with the AST
    427 reader logic, there is an abstract class that provides the interface between
    428 the two modules.  The ``ASTReader`` class, which handles the loading of an AST
    429 file, inherits from all of these abstract classes to provide lazy
    430 deserialization of Clang's data structures.  ``ASTReader`` implements the
    431 following abstract classes:
    432 
    433 ``ExternalSLocEntrySource``
    434   This abstract interface is associated with the ``SourceManager`` class, and
    435   is used whenever the :ref:`source manager <pchinternals-sourcemgr>` needs to
    436   load the details of a file, buffer, or macro instantiation.
    437 
    438 ``IdentifierInfoLookup``
    439   This abstract interface is associated with the ``IdentifierTable`` class, and
    440   is used whenever the program source refers to an identifier that has not yet
    441   been seen.  In this case, the AST reader searches for this identifier within
    442   its :ref:`identifier table <pchinternals-ident-table>` to load any top-level
    443   declarations or macros associated with that identifier.
    444 
    445 ``ExternalASTSource``
    446   This abstract interface is associated with the ``ASTContext`` class, and is
    447   used whenever the abstract syntax tree nodes need to loaded from the AST
    448   file.  It provides the ability to de-serialize declarations and types
    449   identified by their numeric values, read the bodies of functions when
    450   required, and read the declarations stored within a declaration context
    451   (either for iteration or for name lookup).
    452 
    453 ``ExternalSemaSource``
    454   This abstract interface is associated with the ``Sema`` class, and is used
    455   whenever semantic analysis needs to read information from the :ref:`global
    456   method pool <pchinternals-method-pool>`.
    457 
    458 .. _pchinternals-chained:
    459 
    460 Chained precompiled headers
    461 ---------------------------
    462 
    463 Chained precompiled headers were initially intended to improve the performance
    464 of IDE-centric operations such as syntax highlighting and code completion while
    465 a particular source file is being edited by the user.  To minimize the amount
    466 of reparsing required after a change to the file, a form of precompiled header
    467 --- called a precompiled *preamble* --- is automatically generated by parsing
    468 all of the headers in the source file, up to and including the last
    469 ``#include``.  When only the source file changes (and none of the headers it
    470 depends on), reparsing of that source file can use the precompiled preamble and
    471 start parsing after the ``#include``\ s, so parsing time is proportional to the
    472 size of the source file (rather than all of its includes).  However, the
    473 compilation of that translation unit may already use a precompiled header: in
    474 this case, Clang will create the precompiled preamble as a chained precompiled
    475 header that refers to the original precompiled header.  This drastically
    476 reduces the time needed to serialize the precompiled preamble for use in
    477 reparsing.
    478 
    479 Chained precompiled headers get their name because each precompiled header can
    480 depend on one other precompiled header, forming a chain of dependencies.  A
    481 translation unit will then include the precompiled header that starts the chain
    482 (i.e., nothing depends on it).  This linearity of dependencies is important for
    483 the semantic model of chained precompiled headers, because the most-recent
    484 precompiled header can provide information that overrides the information
    485 provided by the precompiled headers it depends on, just like a header file
    486 ``B.h`` that includes another header ``A.h`` can modify the state produced by
    487 parsing ``A.h``, e.g., by ``#undef``'ing a macro defined in ``A.h``.
    488 
    489 There are several ways in which chained precompiled headers generalize the AST
    490 file model:
    491 
    492 Numbering of IDs
    493   Many different kinds of entities --- identifiers, declarations, types, etc.
    494   --- have ID numbers that start at 1 or some other predefined constant and
    495   grow upward.  Each precompiled header records the maximum ID number it has
    496   assigned in each category.  Then, when a new precompiled header is generated
    497   that depends on (chains to) another precompiled header, it will start
    498   counting at the next available ID number.  This way, one can determine, given
    499   an ID number, which AST file actually contains the entity.
    500 
    501 Name lookup
    502   When writing a chained precompiled header, Clang attempts to write only
    503   information that has changed from the precompiled header on which it is
    504   based.  This changes the lookup algorithm for the various tables, such as the
    505   :ref:`identifier table <pchinternals-ident-table>`: the search starts at the
    506   most-recent precompiled header.  If no entry is found, lookup then proceeds
    507   to the identifier table in the precompiled header it depends on, and so one.
    508   Once a lookup succeeds, that result is considered definitive, overriding any
    509   results from earlier precompiled headers.
    510 
    511 Update records
    512   There are various ways in which a later precompiled header can modify the
    513   entities described in an earlier precompiled header.  For example, later
    514   precompiled headers can add entries into the various name-lookup tables for
    515   the translation unit or namespaces, or add new categories to an Objective-C
    516   class.  Each of these updates is captured in an "update record" that is
    517   stored in the chained precompiled header file and will be loaded along with
    518   the original entity.
    519 
    520 .. _pchinternals-modules:
    521 
    522 Modules
    523 -------
    524 
    525 Modules generalize the chained precompiled header model yet further, from a
    526 linear chain of precompiled headers to an arbitrary directed acyclic graph
    527 (DAG) of AST files.  All of the same techniques used to make chained
    528 precompiled headers work --- ID number, name lookup, update records --- are
    529 shared with modules.  However, the DAG nature of modules introduce a number of
    530 additional complications to the model:
    531 
    532 Numbering of IDs
    533   The simple, linear numbering scheme used in chained precompiled headers falls
    534   apart with the module DAG, because different modules may end up with
    535   different numbering schemes for entities they imported from common shared
    536   modules.  To account for this, each module file provides information about
    537   which modules it depends on and which ID numbers it assigned to the entities
    538   in those modules, as well as which ID numbers it took for its own new
    539   entities.  The AST reader then maps these "local" ID numbers into a "global"
    540   ID number space for the current translation unit, providing a 1-1 mapping
    541   between entities (in whatever AST file they inhabit) and global ID numbers.
    542   If that translation unit is then serialized into an AST file, this mapping
    543   will be stored for use when the AST file is imported.
    544 
    545 Declaration merging
    546   It is possible for a given entity (from the language's perspective) to be
    547   declared multiple times in different places.  For example, two different
    548   headers can have the declaration of ``printf`` or could forward-declare
    549   ``struct stat``.  If each of those headers is included in a module, and some
    550   third party imports both of those modules, there is a potentially serious
    551   problem: name lookup for ``printf`` or ``struct stat`` will find both
    552   declarations, but the AST nodes are unrelated.  This would result in a
    553   compilation error, due to an ambiguity in name lookup.  Therefore, the AST
    554   reader performs declaration merging according to the appropriate language
    555   semantics, ensuring that the two disjoint declarations are merged into a
    556   single redeclaration chain (with a common canonical declaration), so that it
    557   is as if one of the headers had been included before the other.
    558 
    559 Name Visibility
    560   Modules allow certain names that occur during module creation to be "hidden",
    561   so that they are not part of the public interface of the module and are not
    562   visible to its clients.  The AST reader maintains a "visible" bit on various
    563   AST nodes (declarations, macros, etc.) to indicate whether that particular
    564   AST node is currently visible; the various name lookup mechanisms in Clang
    565   inspect the visible bit to determine whether that entity, which is still in
    566   the AST (because other, visible AST nodes may depend on it), can actually be
    567   found by name lookup.  When a new (sub)module is imported, it may make
    568   existing, non-visible, already-deserialized AST nodes visible; it is the
    569   responsibility of the AST reader to find and update these AST nodes when it
    570   is notified of the import.
    571 
    572