cppinternals.texi

理解和实践操作系统的一本好书

sequence that represents the @samp{\} of an escaped newline.  If it
encounters a @samp{?} or @samp{\}, it calls @code{skip_escaped_newlines}
to skip over any potential escaped newlines before checking whether the
number has been finished.

Similarly code in the main body of @code{_cpp_lex_direct} cannot simply
check for a @samp{=} after a @samp{+} character to determine whether it
has a @samp{+=} token; it needs to be prepared for an escaped newline of
some sort.  Such cases use the function @code{get_effective_char}, which
returns the first character after any intervening escaped newlines.

The lexer needs to keep track of the correct column position, including
counting tabs as specified by the @option{-ftabstop=} option.  This
should be done even within C-style comments; they can appear in the
middle of a line, and we want to report diagnostics in the correct
position for text appearing after the end of the comment.

@anchor{Invalid identifiers}
Some identifiers, such as @code{__VA_ARGS__} and poisoned identifiers,
may be invalid and require a diagnostic.  However, if they appear in a
macro expansion we don't want to complain with each use of the macro.
It is therefore best to catch them during the lexing stage, in
@code{parse_identifier}.  In both cases, whether a diagnostic is needed
or not is dependent upon the lexer's state.  For example, we don't want
to issue a diagnostic for re-poisoning a poisoned identifier, or for
using @code{__VA_ARGS__} in the expansion of a variable-argument macro.
Therefore @code{parse_identifier} makes use of state flags to determine
whether a diagnostic is appropriate.  Since we change state on a
per-token basis, and don't lex whole lines at a time, this is not a
problem.

Another place where state flags are used to change behavior is whilst
lexing header names.  Normally, a @samp{<} would be lexed as a single
token.  After a @code{#include} directive, though, it should be lexed as
a single token as far as the nearest @samp{>} character.  Note that we
don't allow the terminators of header names to be escaped; the first
@samp{"} or @samp{>} terminates the header name.

Interpretation of some character sequences depends upon whether we are
lexing C, C++ or Objective-C, and on the revision of the standard in
force.  For example, @samp{::} is a single token in C++, but in C it is
two separate @samp{:} tokens and almost certainly a syntax error.  Such
cases are handled by @code{_cpp_lex_direct} based upon command-line
flags stored in the @code{cpp_options} structure.

Once a token has been lexed, it leads an independent existence.  The
spelling of numbers, identifiers and strings is copied to permanent
storage from the original input buffer, so a token remains valid and
correct even if its source buffer is freed with @code{_cpp_pop_buffer}.
The storage holding the spellings of such tokens remains until the
client program calls cpp_destroy, probably at the end of the translation
unit.

@anchor{Lexing a line}
@section Lexing a line
@cindex token run

When the preprocessor was changed to return pointers to tokens, one
feature I wanted was some sort of guarantee regarding how long a
returned pointer remains valid.  This is important to the stand-alone
preprocessor, the future direction of the C family front ends, and even
to cpplib itself internally.

Occasionally the preprocessor wants to be able to peek ahead in the
token stream.  For example, after the name of a function-like macro, it
wants to check the next token to see if it is an opening parenthesis.
Another example is that, after reading the first few tokens of a
@code{#pragma} directive and not recognizing it as a registered pragma,
it wants to backtrack and allow the user-defined handler for unknown
pragmas to access the full @code{#pragma} token stream.  The stand-alone
preprocessor wants to be able to test the current token with the
previous one to see if a space needs to be inserted to preserve their
separate tokenization upon re-lexing (paste avoidance), so it needs to
be sure the pointer to the previous token is still valid.  The
recursive-descent C++ parser wants to be able to perform tentative
parsing arbitrarily far ahead in the token stream, and then to be able
to jump back to a prior position in that stream if necessary.

The rule I chose, which is fairly natural, is to arrange that the
preprocessor lex all tokens on a line consecutively into a token buffer,
which I call a @dfn{token run}, and when meeting an unescaped new line
(newlines within comments do not count either), to start lexing back at
the beginning of the run.  Note that we do @emph{not} lex a line of
tokens at once; if we did that @code{parse_identifier} would not have
state flags available to warn about invalid identifiers (@pxref{Invalid
identifiers}).

In other words, accessing tokens that appeared earlier in the current
line is valid, but since each logical line overwrites the tokens of the
previous line, tokens from prior lines are unavailable.  In particular,
since a directive only occupies a single logical line, this means that
the directive handlers like the @code{#pragma} handler can jump around
in the directive's tokens if necessary.

Two issues remain: what about tokens that arise from macro expansions,
and what happens when we have a long line that overflows the token run?

Since we promise clients that we preserve the validity of pointers that
we have already returned for tokens that appeared earlier in the line,
we cannot reallocate the run.  Instead, on overflow it is expanded by
chaining a new token run on to the end of the existing one.

The tokens forming a macro's replacement list are collected by the
@code{#define} handler, and placed in storage that is only freed by
@code{cpp_destroy}.  So if a macro is expanded in the line of tokens,
the pointers to the tokens of its expansion that are returned will always
remain valid.  However, macros are a little trickier than that, since
they give rise to three sources of fresh tokens.  They are the built-in
macros like @code{__LINE__}, and the @samp{#} and @samp{##} operators
for stringification and token pasting.  I handled this by allocating
space for these tokens from the lexer's token run chain.  This means
they automatically receive the same lifetime guarantees as lexed tokens,
and we don't need to concern ourselves with freeing them.

Lexing into a line of tokens solves some of the token memory management
issues, but not all.  The opening parenthesis after a function-like
macro name might lie on a different line, and the front ends definitely
want the ability to look ahead past the end of the current line.  So
cpplib only moves back to the start of the token run at the end of a
line if the variable @code{keep_tokens} is zero.  Line-buffering is
quite natural for the preprocessor, and as a result the only time cpplib
needs to increment this variable is whilst looking for the opening
parenthesis to, and reading the arguments of, a function-like macro.  In
the near future cpplib will export an interface to increment and
decrement this variable, so that clients can share full control over the
lifetime of token pointers too.

The routine @code{_cpp_lex_token} handles moving to new token runs,
calling @code{_cpp_lex_direct} to lex new tokens, or returning
previously-lexed tokens if we stepped back in the token stream.  It also
checks each token for the @code{BOL} flag, which might indicate a
directive that needs to be handled, or require a start-of-line call-back
to be made.  @code{_cpp_lex_token} also handles skipping over tokens in
failed conditional blocks, and invalidates the control macro of the
multiple-include optimization if a token was successfully lexed outside
a directive.  In other words, its callers do not need to concern
themselves with such issues.

@node Hash Nodes
@unnumbered Hash Nodes
@cindex hash table
@cindex identifiers
@cindex macros
@cindex assertions
@cindex named operators

When cpplib encounters an ``identifier'', it generates a hash code for
it and stores it in the hash table.  By ``identifier'' we mean tokens
with type @code{CPP_NAME}; this includes identifiers in the usual C
sense, as well as keywords, directive names, macro names and so on.  For
example, all of @code{pragma}, @code{int}, @code{foo} and
@code{__GNUC__} are identifiers and hashed when lexed.

Each node in the hash table contain various information about the
identifier it represents.  For example, its length and type.  At any one
time, each identifier falls into exactly one of three categories:

@itemize @bullet
@item Macros

These have been declared to be macros, either on the command line or
with @code{#define}.  A few, such as @code{__TIME__} are built-ins
entered in the hash table during initialization.  The hash node for a
normal macro points to a structure with more information about the
macro, such as whether it is function-like, how many arguments it takes,
and its expansion.  Built-in macros are flagged as special, and instead
contain an enum indicating which of the various built-in macros it is.

@item Assertions

Assertions are in a separate namespace to macros.  To enforce this, cpp
actually prepends a @code{#} character before hashing and entering it in
the hash table.  An assertion's node points to a chain of answers to
that assertion.

@item Void

Everything else falls into this category---an identifier that is not
currently a macro, or a macro that has since been undefined with
@code{#undef}.

When preprocessing C++, this category also includes the named operators,
such as @code{xor}.  In expressions these behave like the operators they
represent, but in contexts where the spelling of a token matters they
are spelt differently.  This spelling distinction is relevant when they
are operands of the stringizing and pasting macro operators @code{#} and
@code{##}.  Named operator hash nodes are flagged, both to catch the
spelling distinction and to prevent them from being defined as macros.
@end itemize

The same identifiers share the same hash node.  Since each identifier
token, after lexing, contains a pointer to its hash node, this is used
to provide rapid lookup of various information.  For example, when
parsing a @code{#define} statement, CPP flags each argument's identifier
hash node with the index of that argument.  This makes duplicated
argument checking an O(1) operation for each argument.  Similarly, for
each identifier in the macro's expansion, lookup to see if it is an
argument, and which argument it is, is also an O(1) operation.  Further,
each directive name, such as @code{endif}, has an associated directive
enum stored in its hash node, so that directive lookup is also O(1).

@node Macro Expansion
@unnumbered Macro Expansion Algorithm
@cindex macro expansion

Macro expansion is a tricky operation, fraught with nasty corner cases
and situations that render what you thought was a nifty way to
optimize the preprocessor's expansion algorithm wrong in quite subtle
ways.

I strongly recommend you have a good grasp of how the C and C++
standards require macros to be expanded before diving into this
section, let alone the code!.  If you don't have a clear mental
picture of how things like nested macro expansion, stringification and
token pasting are supposed to work, damage to your sanity can quickly
result.

@section Internal representation of macros
@cindex macro representation (internal)

The preprocessor stores macro expansions in tokenized form.  This
saves repeated lexing passes during expansion, at the cost of a small
increase in memory consumption on average.  The tokens are stored
contiguously in memory, so a pointer to the first one and a token
count is all you need to get the replacement list of a macro.

If the macro is a function-like macro the preprocessor also stores its
parameters, in the form of an ordered list of pointers to the hash
table entry of each parameter's identifier.  Further, in the macro's
stored expansion each occurrence of a parameter is replaced with a
special token of type @code{CPP_MACRO_ARG}.  Each such token holds the
index of the parameter it represents in the parameter list, which
allows rapid replacement of parameters with their arguments during
expansion.  Despite this optimization it is still necessary to store
the original parameters to the macro, both for dumping with e.g.,
@option{-dD}, and to warn about non-trivial macro redefinitions when
the parameter names have changed.

@section Macro expansion overview
The preprocessor maintains a @dfn{context stack}, implemented as a
linked list of @code{cpp_context} structures, which together represent
the macro expansion state at any one time.  The @code{struct
cpp_reader} member variable @code{context} points to the current top
of this stack.  The top normally holds the unexpanded replacement list
of the innermost macro under expansion, except when cpplib is about to
pre-expand an argument, in which case it holds that argument's
unexpanded tokens.

When there are no macros under expansion, cpplib is in @dfn{base
context}.  All contexts other than the base context contain a
contiguous list of tokens delimited by a starting and ending token.
When not in base context, cpplib obtains the next token from the list
of the top context.  If there are no tokens left in the list, it pops
that context off the stack, and subsequent ones if necessary, until an
unexhausted context is found or it returns to base context.  In base
context, cpplib reads tokens directly from the lexer.

If it encounters an identifier that is both a macro and enabled for
expansion, cpplib prepares to push a new context for that macro on the
stack by calling the routine @code{enter_macro_context}.  When this
routine returns, the new context will contain the unexpanded tokens of
the replacement list of that macro.  In the case of function-like
macros, @code{enter_macro_context} also replaces any parameters in the
replacement list, stored as @code{CPP_MACRO_ARG} tokens, with the
appropriate macro argument.  If the standard requires that the
parameter be replaced with its expanded argument, the argument will
have been fully macro expanded first.