Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / gcc / doc / cppinternals.texi
CommitLineData
003757ed
MD
1\input texinfo
2@setfilename cppinternals.info
3@settitle The GNU C Preprocessor Internals
4
5@ifinfo
6@dircategory Programming
7@direntry
8* Cpplib: (cppinternals). Cpplib internals.
9@end direntry
10@end ifinfo
11
12@c @smallbook
13@c @cropmarks
14@c @finalout
15@setchapternewpage odd
16@ifinfo
17This file documents the internals of the GNU C Preprocessor.
18
3a327f56 19Copyright 2000, 2001, 2002, 2004 Free Software Foundation, Inc.
003757ed
MD
20
21Permission is granted to make and distribute verbatim copies of
22this manual provided the copyright notice and this permission notice
23are preserved on all copies.
24
25@ignore
26Permission is granted to process this file through Tex and print the
27results, provided the printed document carries copying permission
28notice identical to this one except for the removal of this paragraph
29(this paragraph not being relevant to the printed manual).
30
31@end ignore
32Permission is granted to copy and distribute modified versions of this
33manual under the conditions for verbatim copying, provided also that
34the entire resulting derived work is distributed under the terms of a
35permission notice identical to this one.
36
37Permission is granted to copy and distribute translations of this manual
38into another language, under the above conditions for modified versions.
39@end ifinfo
40
41@titlepage
42@c @finalout
43@title Cpplib Internals
44@subtitle Last revised January 2002
45@subtitle for GCC version 3.1
46@author Neil Booth
47@page
48@vskip 0pt plus 1filll
49@c man begin COPYRIGHT
3a327f56 50Copyright @copyright{} 2000, 2001, 2002, 2004
003757ed
MD
51Free Software Foundation, Inc.
52
53Permission is granted to make and distribute verbatim copies of
54this manual provided the copyright notice and this permission notice
55are preserved on all copies.
56
57Permission is granted to copy and distribute modified versions of this
58manual under the conditions for verbatim copying, provided also that
59the entire resulting derived work is distributed under the terms of a
60permission notice identical to this one.
61
62Permission is granted to copy and distribute translations of this manual
63into another language, under the above conditions for modified versions.
64@c man end
65@end titlepage
66@contents
67@page
68
69@node Top
70@top
71@chapter Cpplib---the GNU C Preprocessor
72
73The GNU C preprocessor in GCC 3.x has been completely rewritten. It is
74now implemented as a library, @dfn{cpplib}, so it can be easily shared between
75a stand-alone preprocessor, and a preprocessor integrated with the C,
76C++ and Objective-C front ends. It is also available for use by other
77programs, though this is not recommended as its exposed interface has
78not yet reached a point of reasonable stability.
79
80The library has been written to be re-entrant, so that it can be used
81to preprocess many files simultaneously if necessary. It has also been
82written with the preprocessing token as the fundamental unit; the
83preprocessor in previous versions of GCC would operate on text strings
84as the fundamental unit.
85
86This brief manual documents the internals of cpplib, and explains some
87of the tricky issues. It is intended that, along with the comments in
88the source code, a reasonably competent C programmer should be able to
89figure out what the code is doing, and why things have been implemented
90the way they have.
91
92@menu
93* Conventions:: Conventions used in the code.
94* Lexer:: The combined C, C++ and Objective-C Lexer.
95* Hash Nodes:: All identifiers are entered into a hash table.
96* Macro Expansion:: Macro expansion algorithm.
97* Token Spacing:: Spacing and paste avoidance issues.
98* Line Numbering:: Tracking location within files.
99* Guard Macros:: Optimizing header files with guard macros.
100* Files:: File handling.
101* Index:: Index.
102@end menu
103
104@node Conventions
105@unnumbered Conventions
106@cindex interface
107@cindex header files
108
109cpplib has two interfaces---one is exposed internally only, and the
110other is for both internal and external use.
111
112The convention is that functions and types that are exposed to multiple
113files internally are prefixed with @samp{_cpp_}, and are to be found in
114the file @file{cpphash.h}. Functions and types exposed to external
115clients are in @file{cpplib.h}, and prefixed with @samp{cpp_}. For
116historical reasons this is no longer quite true, but we should strive to
117stick to it.
118
119We are striving to reduce the information exposed in @file{cpplib.h} to the
120bare minimum necessary, and then to keep it there. This makes clear
121exactly what external clients are entitled to assume, and allows us to
122change internals in the future without worrying whether library clients
123are perhaps relying on some kind of undocumented implementation-specific
124behavior.
125
126@node Lexer
127@unnumbered The Lexer
128@cindex lexer
129@cindex newlines
130@cindex escaped newlines
131
132@section Overview
133The lexer is contained in the file @file{cpplex.c}. It is a hand-coded
134lexer, and not implemented as a state machine. It can understand C, C++
135and Objective-C source code, and has been extended to allow reasonably
136successful preprocessing of assembly language. The lexer does not make
137an initial pass to strip out trigraphs and escaped newlines, but handles
138them as they are encountered in a single pass of the input file. It
139returns preprocessing tokens individually, not a line at a time.
140
141It is mostly transparent to users of the library, since the library's
142interface for obtaining the next token, @code{cpp_get_token}, takes care
143of lexing new tokens, handling directives, and expanding macros as
144necessary. However, the lexer does expose some functionality so that
145clients of the library can easily spell a given token, such as
146@code{cpp_spell_token} and @code{cpp_token_len}. These functions are
147useful when generating diagnostics, and for emitting the preprocessed
148output.
149
150@section Lexing a token
151Lexing of an individual token is handled by @code{_cpp_lex_direct} and
152its subroutines. In its current form the code is quite complicated,
153with read ahead characters and such-like, since it strives to not step
154back in the character stream in preparation for handling non-ASCII file
155encodings. The current plan is to convert any such files to UTF-8
156before processing them. This complexity is therefore unnecessary and
157will be removed, so I'll not discuss it further here.
158
159The job of @code{_cpp_lex_direct} is simply to lex a token. It is not
160responsible for issues like directive handling, returning lookahead
161tokens directly, multiple-include optimization, or conditional block
162skipping. It necessarily has a minor r@^ole to play in memory
163management of lexed lines. I discuss these issues in a separate section
164(@pxref{Lexing a line}).
165
166The lexer places the token it lexes into storage pointed to by the
167variable @code{cur_token}, and then increments it. This variable is
168important for correct diagnostic positioning. Unless a specific line
169and column are passed to the diagnostic routines, they will examine the
170@code{line} and @code{col} values of the token just before the location
171that @code{cur_token} points to, and use that location to report the
172diagnostic.
173
174The lexer does not consider whitespace to be a token in its own right.
175If whitespace (other than a new line) precedes a token, it sets the
176@code{PREV_WHITE} bit in the token's flags. Each token has its
177@code{line} and @code{col} variables set to the line and column of the
178first character of the token. This line number is the line number in
179the translation unit, and can be converted to a source (file, line) pair
180using the line map code.
181
182The first token on a logical, i.e.@: unescaped, line has the flag
183@code{BOL} set for beginning-of-line. This flag is intended for
184internal use, both to distinguish a @samp{#} that begins a directive
185from one that doesn't, and to generate a call-back to clients that want
186to be notified about the start of every non-directive line with tokens
187on it. Clients cannot reliably determine this for themselves: the first
188token might be a macro, and the tokens of a macro expansion do not have
189the @code{BOL} flag set. The macro expansion may even be empty, and the
190next token on the line certainly won't have the @code{BOL} flag set.
191
192New lines are treated specially; exactly how the lexer handles them is
193context-dependent. The C standard mandates that directives are
194terminated by the first unescaped newline character, even if it appears
195in the middle of a macro expansion. Therefore, if the state variable
196@code{in_directive} is set, the lexer returns a @code{CPP_EOF} token,
197which is normally used to indicate end-of-file, to indicate
198end-of-directive. In a directive a @code{CPP_EOF} token never means
199end-of-file. Conveniently, if the caller was @code{collect_args}, it
200already handles @code{CPP_EOF} as if it were end-of-file, and reports an
201error about an unterminated macro argument list.
202
203The C standard also specifies that a new line in the middle of the
204arguments to a macro is treated as whitespace. This white space is
205important in case the macro argument is stringified. The state variable
206@code{parsing_args} is nonzero when the preprocessor is collecting the
207arguments to a macro call. It is set to 1 when looking for the opening
208parenthesis to a function-like macro, and 2 when collecting the actual
209arguments up to the closing parenthesis, since these two cases need to
210be distinguished sometimes. One such time is here: the lexer sets the
211@code{PREV_WHITE} flag of a token if it meets a new line when
212@code{parsing_args} is set to 2. It doesn't set it if it meets a new
213line when @code{parsing_args} is 1, since then code like
214
215@smallexample
216#define foo() bar
217foo
218baz
219@end smallexample
220
221@noindent would be output with an erroneous space before @samp{baz}:
222
223@smallexample
224foo
225 baz
226@end smallexample
227
228This is a good example of the subtlety of getting token spacing correct
3a327f56 229in the preprocessor; there are plenty of tests in the testsuite for
003757ed
MD
230corner cases like this.
231
232The lexer is written to treat each of @samp{\r}, @samp{\n}, @samp{\r\n}
233and @samp{\n\r} as a single new line indicator. This allows it to
234transparently preprocess MS-DOS, Macintosh and Unix files without their
235needing to pass through a special filter beforehand.
236
237We also decided to treat a backslash, either @samp{\} or the trigraph
238@samp{??/}, separated from one of the above newline indicators by
239non-comment whitespace only, as intending to escape the newline. It
240tends to be a typing mistake, and cannot reasonably be mistaken for
241anything else in any of the C-family grammars. Since handling it this
242way is not strictly conforming to the ISO standard, the library issues a
243warning wherever it encounters it.
244
245Handling newlines like this is made simpler by doing it in one place
246only. The function @code{handle_newline} takes care of all newline
247characters, and @code{skip_escaped_newlines} takes care of arbitrarily
248long sequences of escaped newlines, deferring to @code{handle_newline}
249to handle the newlines themselves.
250
251The most painful aspect of lexing ISO-standard C and C++ is handling
252trigraphs and backlash-escaped newlines. Trigraphs are processed before
253any interpretation of the meaning of a character is made, and unfortunately
254there is a trigraph representation for a backslash, so it is possible for
255the trigraph @samp{??/} to introduce an escaped newline.
256
257Escaped newlines are tedious because theoretically they can occur
258anywhere---between the @samp{+} and @samp{=} of the @samp{+=} token,
259within the characters of an identifier, and even between the @samp{*}
260and @samp{/} that terminates a comment. Moreover, you cannot be sure
261there is just one---there might be an arbitrarily long sequence of them.
262
263So, for example, the routine that lexes a number, @code{parse_number},
264cannot assume that it can scan forwards until the first non-number
265character and be done with it, because this could be the @samp{\}
266introducing an escaped newline, or the @samp{?} introducing the trigraph
267sequence that represents the @samp{\} of an escaped newline. If it
268encounters a @samp{?} or @samp{\}, it calls @code{skip_escaped_newlines}
269to skip over any potential escaped newlines before checking whether the
270number has been finished.
271
272Similarly code in the main body of @code{_cpp_lex_direct} cannot simply
273check for a @samp{=} after a @samp{+} character to determine whether it
274has a @samp{+=} token; it needs to be prepared for an escaped newline of
275some sort. Such cases use the function @code{get_effective_char}, which
276returns the first character after any intervening escaped newlines.
277
278The lexer needs to keep track of the correct column position, including
279counting tabs as specified by the @option{-ftabstop=} option. This
280should be done even within C-style comments; they can appear in the
281middle of a line, and we want to report diagnostics in the correct
282position for text appearing after the end of the comment.
283
284@anchor{Invalid identifiers}
285Some identifiers, such as @code{__VA_ARGS__} and poisoned identifiers,
286may be invalid and require a diagnostic. However, if they appear in a
287macro expansion we don't want to complain with each use of the macro.
288It is therefore best to catch them during the lexing stage, in
289@code{parse_identifier}. In both cases, whether a diagnostic is needed
290or not is dependent upon the lexer's state. For example, we don't want
291to issue a diagnostic for re-poisoning a poisoned identifier, or for
292using @code{__VA_ARGS__} in the expansion of a variable-argument macro.
293Therefore @code{parse_identifier} makes use of state flags to determine
294whether a diagnostic is appropriate. Since we change state on a
295per-token basis, and don't lex whole lines at a time, this is not a
296problem.
297
298Another place where state flags are used to change behavior is whilst
299lexing header names. Normally, a @samp{<} would be lexed as a single
300token. After a @code{#include} directive, though, it should be lexed as
301a single token as far as the nearest @samp{>} character. Note that we
302don't allow the terminators of header names to be escaped; the first
303@samp{"} or @samp{>} terminates the header name.
304
305Interpretation of some character sequences depends upon whether we are
306lexing C, C++ or Objective-C, and on the revision of the standard in
307force. For example, @samp{::} is a single token in C++, but in C it is
308two separate @samp{:} tokens and almost certainly a syntax error. Such
309cases are handled by @code{_cpp_lex_direct} based upon command-line
310flags stored in the @code{cpp_options} structure.
311
312Once a token has been lexed, it leads an independent existence. The
313spelling of numbers, identifiers and strings is copied to permanent
314storage from the original input buffer, so a token remains valid and
315correct even if its source buffer is freed with @code{_cpp_pop_buffer}.
316The storage holding the spellings of such tokens remains until the
317client program calls cpp_destroy, probably at the end of the translation
318unit.
319
320@anchor{Lexing a line}
321@section Lexing a line
322@cindex token run
323
324When the preprocessor was changed to return pointers to tokens, one
325feature I wanted was some sort of guarantee regarding how long a
326returned pointer remains valid. This is important to the stand-alone
327preprocessor, the future direction of the C family front ends, and even
328to cpplib itself internally.
329
330Occasionally the preprocessor wants to be able to peek ahead in the
331token stream. For example, after the name of a function-like macro, it
332wants to check the next token to see if it is an opening parenthesis.
333Another example is that, after reading the first few tokens of a
334@code{#pragma} directive and not recognizing it as a registered pragma,
335it wants to backtrack and allow the user-defined handler for unknown
336pragmas to access the full @code{#pragma} token stream. The stand-alone
337preprocessor wants to be able to test the current token with the
338previous one to see if a space needs to be inserted to preserve their
339separate tokenization upon re-lexing (paste avoidance), so it needs to
340be sure the pointer to the previous token is still valid. The
341recursive-descent C++ parser wants to be able to perform tentative
342parsing arbitrarily far ahead in the token stream, and then to be able
343to jump back to a prior position in that stream if necessary.
344
345The rule I chose, which is fairly natural, is to arrange that the
346preprocessor lex all tokens on a line consecutively into a token buffer,
347which I call a @dfn{token run}, and when meeting an unescaped new line
348(newlines within comments do not count either), to start lexing back at
349the beginning of the run. Note that we do @emph{not} lex a line of
350tokens at once; if we did that @code{parse_identifier} would not have
351state flags available to warn about invalid identifiers (@pxref{Invalid
352identifiers}).
353
354In other words, accessing tokens that appeared earlier in the current
355line is valid, but since each logical line overwrites the tokens of the
356previous line, tokens from prior lines are unavailable. In particular,
357since a directive only occupies a single logical line, this means that
358the directive handlers like the @code{#pragma} handler can jump around
359in the directive's tokens if necessary.
360
361Two issues remain: what about tokens that arise from macro expansions,
362and what happens when we have a long line that overflows the token run?
363
364Since we promise clients that we preserve the validity of pointers that
365we have already returned for tokens that appeared earlier in the line,
366we cannot reallocate the run. Instead, on overflow it is expanded by
367chaining a new token run on to the end of the existing one.
368
369The tokens forming a macro's replacement list are collected by the
370@code{#define} handler, and placed in storage that is only freed by
3a327f56
JS
371@code{cpp_destroy}. So if a macro is expanded in the line of tokens,
372the pointers to the tokens of its expansion that are returned will always
003757ed
MD
373remain valid. However, macros are a little trickier than that, since
374they give rise to three sources of fresh tokens. They are the built-in
375macros like @code{__LINE__}, and the @samp{#} and @samp{##} operators
376for stringification and token pasting. I handled this by allocating
377space for these tokens from the lexer's token run chain. This means
378they automatically receive the same lifetime guarantees as lexed tokens,
379and we don't need to concern ourselves with freeing them.
380
381Lexing into a line of tokens solves some of the token memory management
382issues, but not all. The opening parenthesis after a function-like
383macro name might lie on a different line, and the front ends definitely
384want the ability to look ahead past the end of the current line. So
385cpplib only moves back to the start of the token run at the end of a
386line if the variable @code{keep_tokens} is zero. Line-buffering is
387quite natural for the preprocessor, and as a result the only time cpplib
388needs to increment this variable is whilst looking for the opening
389parenthesis to, and reading the arguments of, a function-like macro. In
390the near future cpplib will export an interface to increment and
391decrement this variable, so that clients can share full control over the
392lifetime of token pointers too.
393
394The routine @code{_cpp_lex_token} handles moving to new token runs,
395calling @code{_cpp_lex_direct} to lex new tokens, or returning
396previously-lexed tokens if we stepped back in the token stream. It also
397checks each token for the @code{BOL} flag, which might indicate a
398directive that needs to be handled, or require a start-of-line call-back
399to be made. @code{_cpp_lex_token} also handles skipping over tokens in
400failed conditional blocks, and invalidates the control macro of the
401multiple-include optimization if a token was successfully lexed outside
402a directive. In other words, its callers do not need to concern
403themselves with such issues.
404
405@node Hash Nodes
406@unnumbered Hash Nodes
407@cindex hash table
408@cindex identifiers
409@cindex macros
410@cindex assertions
411@cindex named operators
412
413When cpplib encounters an ``identifier'', it generates a hash code for
414it and stores it in the hash table. By ``identifier'' we mean tokens
415with type @code{CPP_NAME}; this includes identifiers in the usual C
416sense, as well as keywords, directive names, macro names and so on. For
417example, all of @code{pragma}, @code{int}, @code{foo} and
418@code{__GNUC__} are identifiers and hashed when lexed.
419
420Each node in the hash table contain various information about the
421identifier it represents. For example, its length and type. At any one
422time, each identifier falls into exactly one of three categories:
423
424@itemize @bullet
425@item Macros
426
427These have been declared to be macros, either on the command line or
428with @code{#define}. A few, such as @code{__TIME__} are built-ins
429entered in the hash table during initialization. The hash node for a
430normal macro points to a structure with more information about the
431macro, such as whether it is function-like, how many arguments it takes,
432and its expansion. Built-in macros are flagged as special, and instead
433contain an enum indicating which of the various built-in macros it is.
434
435@item Assertions
436
437Assertions are in a separate namespace to macros. To enforce this, cpp
438actually prepends a @code{#} character before hashing and entering it in
439the hash table. An assertion's node points to a chain of answers to
440that assertion.
441
442@item Void
443
444Everything else falls into this category---an identifier that is not
445currently a macro, or a macro that has since been undefined with
446@code{#undef}.
447
448When preprocessing C++, this category also includes the named operators,
449such as @code{xor}. In expressions these behave like the operators they
450represent, but in contexts where the spelling of a token matters they
451are spelt differently. This spelling distinction is relevant when they
452are operands of the stringizing and pasting macro operators @code{#} and
453@code{##}. Named operator hash nodes are flagged, both to catch the
454spelling distinction and to prevent them from being defined as macros.
455@end itemize
456
457The same identifiers share the same hash node. Since each identifier
458token, after lexing, contains a pointer to its hash node, this is used
459to provide rapid lookup of various information. For example, when
460parsing a @code{#define} statement, CPP flags each argument's identifier
461hash node with the index of that argument. This makes duplicated
462argument checking an O(1) operation for each argument. Similarly, for
463each identifier in the macro's expansion, lookup to see if it is an
464argument, and which argument it is, is also an O(1) operation. Further,
465each directive name, such as @code{endif}, has an associated directive
466enum stored in its hash node, so that directive lookup is also O(1).
467
468@node Macro Expansion
469@unnumbered Macro Expansion Algorithm
470@cindex macro expansion
471
472Macro expansion is a tricky operation, fraught with nasty corner cases
473and situations that render what you thought was a nifty way to
474optimize the preprocessor's expansion algorithm wrong in quite subtle
475ways.
476
477I strongly recommend you have a good grasp of how the C and C++
478standards require macros to be expanded before diving into this
479section, let alone the code!. If you don't have a clear mental
480picture of how things like nested macro expansion, stringification and
481token pasting are supposed to work, damage to your sanity can quickly
482result.
483
484@section Internal representation of macros
485@cindex macro representation (internal)
486
487The preprocessor stores macro expansions in tokenized form. This
488saves repeated lexing passes during expansion, at the cost of a small
489increase in memory consumption on average. The tokens are stored
490contiguously in memory, so a pointer to the first one and a token
491count is all you need to get the replacement list of a macro.
492
493If the macro is a function-like macro the preprocessor also stores its
494parameters, in the form of an ordered list of pointers to the hash
495table entry of each parameter's identifier. Further, in the macro's
496stored expansion each occurrence of a parameter is replaced with a
497special token of type @code{CPP_MACRO_ARG}. Each such token holds the
498index of the parameter it represents in the parameter list, which
499allows rapid replacement of parameters with their arguments during
500expansion. Despite this optimization it is still necessary to store
501the original parameters to the macro, both for dumping with e.g.,
502@option{-dD}, and to warn about non-trivial macro redefinitions when
503the parameter names have changed.
504
505@section Macro expansion overview
506The preprocessor maintains a @dfn{context stack}, implemented as a
507linked list of @code{cpp_context} structures, which together represent
508the macro expansion state at any one time. The @code{struct
509cpp_reader} member variable @code{context} points to the current top
510of this stack. The top normally holds the unexpanded replacement list
511of the innermost macro under expansion, except when cpplib is about to
512pre-expand an argument, in which case it holds that argument's
513unexpanded tokens.
514
515When there are no macros under expansion, cpplib is in @dfn{base
516context}. All contexts other than the base context contain a
517contiguous list of tokens delimited by a starting and ending token.
518When not in base context, cpplib obtains the next token from the list
519of the top context. If there are no tokens left in the list, it pops
520that context off the stack, and subsequent ones if necessary, until an
521unexhausted context is found or it returns to base context. In base
522context, cpplib reads tokens directly from the lexer.
523
524If it encounters an identifier that is both a macro and enabled for
525expansion, cpplib prepares to push a new context for that macro on the
526stack by calling the routine @code{enter_macro_context}. When this
527routine returns, the new context will contain the unexpanded tokens of
528the replacement list of that macro. In the case of function-like
529macros, @code{enter_macro_context} also replaces any parameters in the
530replacement list, stored as @code{CPP_MACRO_ARG} tokens, with the
531appropriate macro argument. If the standard requires that the
532parameter be replaced with its expanded argument, the argument will
533have been fully macro expanded first.
534
535@code{enter_macro_context} also handles special macros like
536@code{__LINE__}. Although these macros expand to a single token which
537cannot contain any further macros, for reasons of token spacing
538(@pxref{Token Spacing}) and simplicity of implementation, cpplib
539handles these special macros by pushing a context containing just that
540one token.
541
542The final thing that @code{enter_macro_context} does before returning
543is to mark the macro disabled for expansion (except for special macros
544like @code{__TIME__}). The macro is re-enabled when its context is
545later popped from the context stack, as described above. This strict
546ordering ensures that a macro is disabled whilst its expansion is
547being scanned, but that it is @emph{not} disabled whilst any arguments
548to it are being expanded.
549
550@section Scanning the replacement list for macros to expand
551The C standard states that, after any parameters have been replaced
552with their possibly-expanded arguments, the replacement list is
553scanned for nested macros. Further, any identifiers in the
554replacement list that are not expanded during this scan are never
555again eligible for expansion in the future, if the reason they were
556not expanded is that the macro in question was disabled.
557
558Clearly this latter condition can only apply to tokens resulting from
559argument pre-expansion. Other tokens never have an opportunity to be
560re-tested for expansion. It is possible for identifiers that are
561function-like macros to not expand initially but to expand during a
562later scan. This occurs when the identifier is the last token of an
563argument (and therefore originally followed by a comma or a closing
564parenthesis in its macro's argument list), and when it replaces its
565parameter in the macro's replacement list, the subsequent token
566happens to be an opening parenthesis (itself possibly the first token
567of an argument).
568
569It is important to note that when cpplib reads the last token of a
570given context, that context still remains on the stack. Only when
571looking for the @emph{next} token do we pop it off the stack and drop
572to a lower context. This makes backing up by one token easy, but more
573importantly ensures that the macro corresponding to the current
574context is still disabled when we are considering the last token of
575its replacement list for expansion (or indeed expanding it). As an
576example, which illustrates many of the points above, consider
577
578@smallexample
579#define foo(x) bar x
580foo(foo) (2)
581@end smallexample
582
583@noindent which fully expands to @samp{bar foo (2)}. During pre-expansion
584of the argument, @samp{foo} does not expand even though the macro is
585enabled, since it has no following parenthesis [pre-expansion of an
586argument only uses tokens from that argument; it cannot take tokens
587from whatever follows the macro invocation]. This still leaves the
588argument token @samp{foo} eligible for future expansion. Then, when
589re-scanning after argument replacement, the token @samp{foo} is
590rejected for expansion, and marked ineligible for future expansion,
591since the macro is now disabled. It is disabled because the
592replacement list @samp{bar foo} of the macro is still on the context
593stack.
594
595If instead the algorithm looked for an opening parenthesis first and
596then tested whether the macro were disabled it would be subtly wrong.
597In the example above, the replacement list of @samp{foo} would be
598popped in the process of finding the parenthesis, re-enabling
599@samp{foo} and expanding it a second time.
600
601@section Looking for a function-like macro's opening parenthesis
602Function-like macros only expand when immediately followed by a
603parenthesis. To do this cpplib needs to temporarily disable macros
604and read the next token. Unfortunately, because of spacing issues
605(@pxref{Token Spacing}), there can be fake padding tokens in-between,
606and if the next real token is not a parenthesis cpplib needs to be
607able to back up that one token as well as retain the information in
608any intervening padding tokens.
609
610Backing up more than one token when macros are involved is not
611permitted by cpplib, because in general it might involve issues like
612restoring popped contexts onto the context stack, which are too hard.
613Instead, searching for the parenthesis is handled by a special
614function, @code{funlike_invocation_p}, which remembers padding
615information as it reads tokens. If the next real token is not an
616opening parenthesis, it backs up that one token, and then pushes an
617extra context just containing the padding information if necessary.
618
619@section Marking tokens ineligible for future expansion
620As discussed above, cpplib needs a way of marking tokens as
621unexpandable. Since the tokens cpplib handles are read-only once they
622have been lexed, it instead makes a copy of the token and adds the
623flag @code{NO_EXPAND} to the copy.
624
625For efficiency and to simplify memory management by avoiding having to
626remember to free these tokens, they are allocated as temporary tokens
627from the lexer's current token run (@pxref{Lexing a line}) using the
628function @code{_cpp_temp_token}. The tokens are then re-used once the
629current line of tokens has been read in.
630
631This might sound unsafe. However, tokens runs are not re-used at the
632end of a line if it happens to be in the middle of a macro argument
633list, and cpplib only wants to back-up more than one lexer token in
634situations where no macro expansion is involved, so the optimization
635is safe.
636
637@node Token Spacing
638@unnumbered Token Spacing
639@cindex paste avoidance
640@cindex spacing
641@cindex token spacing
642
3a327f56
JS
643First, consider an issue that only concerns the stand-alone
644preprocessor: there needs to be a guarantee that re-reading its preprocessed
003757ed
MD
645output results in an identical token stream. Without taking special
646measures, this might not be the case because of macro substitution.
647For example:
648
649@smallexample
650#define PLUS +
651#define EMPTY
652#define f(x) =x=
653+PLUS -EMPTY- PLUS+ f(=)
654 @expansion{} + + - - + + = = =
655@emph{not}
656 @expansion{} ++ -- ++ ===
657@end smallexample
658
659One solution would be to simply insert a space between all adjacent
660tokens. However, we would like to keep space insertion to a minimum,
661both for aesthetic reasons and because it causes problems for people who
662still try to abuse the preprocessor for things like Fortran source and
663Makefiles.
664
665For now, just notice that when tokens are added (or removed, as shown by
666the @code{EMPTY} example) from the original lexed token stream, we need
667to check for accidental token pasting. We call this @dfn{paste
668avoidance}. Token addition and removal can only occur because of macro
669expansion, but accidental pasting can occur in many places: both before
670and after each macro replacement, each argument replacement, and
671additionally each token created by the @samp{#} and @samp{##} operators.
672
3a327f56 673Look at how the preprocessor gets whitespace output correct
003757ed
MD
674normally. The @code{cpp_token} structure contains a flags byte, and one
675of those flags is @code{PREV_WHITE}. This is flagged by the lexer, and
676indicates that the token was preceded by whitespace of some form other
677than a new line. The stand-alone preprocessor can use this flag to
678decide whether to insert a space between tokens in the output.
679
680Now consider the result of the following macro expansion:
681
682@smallexample
683#define add(x, y, z) x + y +z;
684sum = add (1,2, 3);
685 @expansion{} sum = 1 + 2 +3;
686@end smallexample
687
688The interesting thing here is that the tokens @samp{1} and @samp{2} are
689output with a preceding space, and @samp{3} is output without a
690preceding space, but when lexed none of these tokens had that property.
691Careful consideration reveals that @samp{1} gets its preceding
692whitespace from the space preceding @samp{add} in the macro invocation,
693@emph{not} replacement list. @samp{2} gets its whitespace from the
694space preceding the parameter @samp{y} in the macro replacement list,
695and @samp{3} has no preceding space because parameter @samp{z} has none
696in the replacement list.
697
698Once lexed, tokens are effectively fixed and cannot be altered, since
699pointers to them might be held in many places, in particular by
700in-progress macro expansions. So instead of modifying the two tokens
701above, the preprocessor inserts a special token, which I call a
702@dfn{padding token}, into the token stream to indicate that spacing of
703the subsequent token is special. The preprocessor inserts padding
704tokens in front of every macro expansion and expanded macro argument.
705These point to a @dfn{source token} from which the subsequent real token
706should inherit its spacing. In the above example, the source tokens are
707@samp{add} in the macro invocation, and @samp{y} and @samp{z} in the
708macro replacement list, respectively.
709
710It is quite easy to get multiple padding tokens in a row, for example if
711a macro's first replacement token expands straight into another macro.
712
713@smallexample
714#define foo bar
715#define bar baz
716[foo]
717 @expansion{} [baz]
718@end smallexample
719
720Here, two padding tokens are generated with sources the @samp{foo} token
721between the brackets, and the @samp{bar} token from foo's replacement
3a327f56
JS
722list, respectively. Clearly the first padding token is the one to
723use, so the output code should contain a rule that the first
003757ed
MD
724padding token in a sequence is the one that matters.
725
3a327f56 726But what if a macro expansion is left? Adjusting the above
003757ed
MD
727example slightly:
728
729@smallexample
730#define foo bar
731#define bar EMPTY baz
732#define EMPTY
733[foo] EMPTY;
734 @expansion{} [ baz] ;
735@end smallexample
736
737As shown, now there should be a space before @samp{baz} and the
738semicolon in the output.
739
740The rules we decided above fail for @samp{baz}: we generate three
741padding tokens, one per macro invocation, before the token @samp{baz}.
742We would then have it take its spacing from the first of these, which
743carries source token @samp{foo} with no leading space.
744
745It is vital that cpplib get spacing correct in these examples since any
746of these macro expansions could be stringified, where spacing matters.
747
748So, this demonstrates that not just entering macro and argument
749expansions, but leaving them requires special handling too. I made
750cpplib insert a padding token with a @code{NULL} source token when
751leaving macro expansions, as well as after each replaced argument in a
752macro's replacement list. It also inserts appropriate padding tokens on
753either side of tokens created by the @samp{#} and @samp{##} operators.
754I expanded the rule so that, if we see a padding token with a
755@code{NULL} source token, @emph{and} that source token has no leading
756space, then we behave as if we have seen no padding tokens at all. A
757quick check shows this rule will then get the above example correct as
758well.
759
760Now a relationship with paste avoidance is apparent: we have to be
761careful about paste avoidance in exactly the same locations we have
762padding tokens in order to get white space correct. This makes
763implementation of paste avoidance easy: wherever the stand-alone
764preprocessor is fixing up spacing because of padding tokens, and it
765turns out that no space is needed, it has to take the extra step to
766check that a space is not needed after all to avoid an accidental paste.
767The function @code{cpp_avoid_paste} advises whether a space is required
768between two consecutive tokens. To avoid excessive spacing, it tries
769hard to only require a space if one is likely to be necessary, but for
770reasons of efficiency it is slightly conservative and might recommend a
771space where one is not strictly needed.
772
773@node Line Numbering
774@unnumbered Line numbering
775@cindex line numbers
776
777@section Just which line number anyway?
778
779There are three reasonable requirements a cpplib client might have for
780the line number of a token passed to it:
781
782@itemize @bullet
783@item
784The source line it was lexed on.
785@item
786The line it is output on. This can be different to the line it was
787lexed on if, for example, there are intervening escaped newlines or
788C-style comments. For example:
789
790@smallexample
791foo /* A long
792comment */ bar \
793baz
794@result{}
795foo bar baz
796@end smallexample
797
798@item
799If the token results from a macro expansion, the line of the macro name,
800or possibly the line of the closing parenthesis in the case of
801function-like macro expansion.
802@end itemize
803
804The @code{cpp_token} structure contains @code{line} and @code{col}
805members. The lexer fills these in with the line and column of the first
806character of the token. Consequently, but maybe unexpectedly, a token
807from the replacement list of a macro expansion carries the location of
808the token within the @code{#define} directive, because cpplib expands a
809macro by returning pointers to the tokens in its replacement list. The
810current implementation of cpplib assigns tokens created from built-in
811macros and the @samp{#} and @samp{##} operators the location of the most
812recently lexed token. This is a because they are allocated from the
813lexer's token runs, and because of the way the diagnostic routines infer
814the appropriate location to report.
815
816The diagnostic routines in cpplib display the location of the most
817recently @emph{lexed} token, unless they are passed a specific line and
818column to report. For diagnostics regarding tokens that arise from
819macro expansions, it might also be helpful for the user to see the
820original location in the macro definition that the token came from.
821Since that is exactly the information each token carries, such an
822enhancement could be made relatively easily in future.
823
824The stand-alone preprocessor faces a similar problem when determining
825the correct line to output the token on: the position attached to a
826token is fairly useless if the token came from a macro expansion. All
827tokens on a logical line should be output on its first physical line, so
828the token's reported location is also wrong if it is part of a physical
829line other than the first.
830
831To solve these issues, cpplib provides a callback that is generated
832whenever it lexes a preprocessing token that starts a new logical line
833other than a directive. It passes this token (which may be a
834@code{CPP_EOF} token indicating the end of the translation unit) to the
835callback routine, which can then use the line and column of this token
836to produce correct output.
837
838@section Representation of line numbers
839
840As mentioned above, cpplib stores with each token the line number that
841it was lexed on. In fact, this number is not the number of the line in
842the source file, but instead bears more resemblance to the number of the
843line in the translation unit.
844
845The preprocessor maintains a monotonic increasing line count, which is
846incremented at every new line character (and also at the end of any
847buffer that does not end in a new line). Since a line number of zero is
848useful to indicate certain special states and conditions, this variable
849starts counting from one.
850
851This variable therefore uniquely enumerates each line in the translation
852unit. With some simple infrastructure, it is straight forward to map
853from this to the original source file and line number pair, saving space
854whenever line number information needs to be saved. The code the
855implements this mapping lies in the files @file{line-map.c} and
856@file{line-map.h}.
857
858Command-line macros and assertions are implemented by pushing a buffer
859containing the right hand side of an equivalent @code{#define} or
860@code{#assert} directive. Some built-in macros are handled similarly.
861Since these are all processed before the first line of the main input
862file, it will typically have an assigned line closer to twenty than to
863one.
864
865@node Guard Macros
866@unnumbered The Multiple-Include Optimization
867@cindex guard macros
868@cindex controlling macros
869@cindex multiple-include optimization
870
871Header files are often of the form
872
873@smallexample
874#ifndef FOO
875#define FOO
876@dots{}
877#endif
878@end smallexample
879
880@noindent
881to prevent the compiler from processing them more than once. The
882preprocessor notices such header files, so that if the header file
883appears in a subsequent @code{#include} directive and @code{FOO} is
884defined, then it is ignored and it doesn't preprocess or even re-open
885the file a second time. This is referred to as the @dfn{multiple
886include optimization}.
887
888Under what circumstances is such an optimization valid? If the file
889were included a second time, it can only be optimized away if that
890inclusion would result in no tokens to return, and no relevant
891directives to process. Therefore the current implementation imposes
892requirements and makes some allowances as follows:
893
894@enumerate
895@item
896There must be no tokens outside the controlling @code{#if}-@code{#endif}
897pair, but whitespace and comments are permitted.
898
899@item
900There must be no directives outside the controlling directive pair, but
901the @dfn{null directive} (a line containing nothing other than a single
902@samp{#} and possibly whitespace) is permitted.
903
904@item
905The opening directive must be of the form
906
907@smallexample
908#ifndef FOO
909@end smallexample
910
911or
912
913@smallexample
914#if !defined FOO [equivalently, #if !defined(FOO)]
915@end smallexample
916
917@item
918In the second form above, the tokens forming the @code{#if} expression
919must have come directly from the source file---no macro expansion must
920have been involved. This is because macro definitions can change, and
921tracking whether or not a relevant change has been made is not worth the
922implementation cost.
923
924@item
925There can be no @code{#else} or @code{#elif} directives at the outer
926conditional block level, because they would probably contain something
927of interest to a subsequent pass.
928@end enumerate
929
930First, when pushing a new file on the buffer stack,
931@code{_stack_include_file} sets the controlling macro @code{mi_cmacro} to
932@code{NULL}, and sets @code{mi_valid} to @code{true}. This indicates
933that the preprocessor has not yet encountered anything that would
934invalidate the multiple-include optimization. As described in the next
935few paragraphs, these two variables having these values effectively
936indicates top-of-file.
937
938When about to return a token that is not part of a directive,
939@code{_cpp_lex_token} sets @code{mi_valid} to @code{false}. This
940enforces the constraint that tokens outside the controlling conditional
941block invalidate the optimization.
942
943The @code{do_if}, when appropriate, and @code{do_ifndef} directive
944handlers pass the controlling macro to the function
945@code{push_conditional}. cpplib maintains a stack of nested conditional
946blocks, and after processing every opening conditional this function
947pushes an @code{if_stack} structure onto the stack. In this structure
948it records the controlling macro for the block, provided there is one
949and we're at top-of-file (as described above). If an @code{#elif} or
950@code{#else} directive is encountered, the controlling macro for that
951block is cleared to @code{NULL}. Otherwise, it survives until the
952@code{#endif} closing the block, upon which @code{do_endif} sets
953@code{mi_valid} to true and stores the controlling macro in
954@code{mi_cmacro}.
955
956@code{_cpp_handle_directive} clears @code{mi_valid} when processing any
957directive other than an opening conditional and the null directive.
958With this, and requiring top-of-file to record a controlling macro, and
959no @code{#else} or @code{#elif} for it to survive and be copied to
960@code{mi_cmacro} by @code{do_endif}, we have enforced the absence of
961directives outside the main conditional block for the optimization to be
962on.
963
964Note that whilst we are inside the conditional block, @code{mi_valid} is
965likely to be reset to @code{false}, but this does not matter since the
966the closing @code{#endif} restores it to @code{true} if appropriate.
967
968Finally, since @code{_cpp_lex_direct} pops the file off the buffer stack
969at @code{EOF} without returning a token, if the @code{#endif} directive
970was not followed by any tokens, @code{mi_valid} is @code{true} and
971@code{_cpp_pop_file_buffer} remembers the controlling macro associated
972with the file. Subsequent calls to @code{stack_include_file} result in
973no buffer being pushed if the controlling macro is defined, effecting
974the optimization.
975
976A quick word on how we handle the
977
978@smallexample
979#if !defined FOO
980@end smallexample
981
982@noindent
983case. @code{_cpp_parse_expr} and @code{parse_defined} take steps to see
984whether the three stages @samp{!}, @samp{defined-expression} and
985@samp{end-of-directive} occur in order in a @code{#if} expression. If
986so, they return the guard macro to @code{do_if} in the variable
987@code{mi_ind_cmacro}, and otherwise set it to @code{NULL}.
988@code{enter_macro_context} sets @code{mi_valid} to false, so if a macro
989was expanded whilst parsing any part of the expression, then the
990top-of-file test in @code{push_conditional} fails and the optimization
991is turned off.
992
993@node Files
994@unnumbered File Handling
995@cindex files
996
997Fairly obviously, the file handling code of cpplib resides in the file
998@file{cppfiles.c}. It takes care of the details of file searching,
999opening, reading and caching, for both the main source file and all the
1000headers it recursively includes.
1001
1002The basic strategy is to minimize the number of system calls. On many
1003systems, the basic @code{open ()} and @code{fstat ()} system calls can
1004be quite expensive. For every @code{#include}-d file, we need to try
1005all the directories in the search path until we find a match. Some
1006projects, such as glibc, pass twenty or thirty include paths on the
1007command line, so this can rapidly become time consuming.
1008
1009For a header file we have not encountered before we have little choice
1010but to do this. However, it is often the case that the same headers are
1011repeatedly included, and in these cases we try to avoid repeating the
1012filesystem queries whilst searching for the correct file.
1013
1014For each file we try to open, we store the constructed path in a splay
1015tree. This path first undergoes simplification by the function
1016@code{_cpp_simplify_pathname}. For example,
1017@file{/usr/include/bits/../foo.h} is simplified to
1018@file{/usr/include/foo.h} before we enter it in the splay tree and try
1019to @code{open ()} the file. CPP will then find subsequent uses of
1020@file{foo.h}, even as @file{/usr/include/foo.h}, in the splay tree and
1021save system calls.
1022
1023Further, it is likely the file contents have also been cached, saving a
1024@code{read ()} system call. We don't bother caching the contents of
1025header files that are re-inclusion protected, and whose re-inclusion
1026macro is defined when we leave the header file for the first time. If
1027the host supports it, we try to map suitably large files into memory,
1028rather than reading them in directly.
1029
1030The include paths are internally stored on a null-terminated
1031singly-linked list, starting with the @code{"header.h"} directory search
1032chain, which then links into the @code{<header.h>} directory chain.
1033
1034Files included with the @code{<foo.h>} syntax start the lookup directly
1035in the second half of this chain. However, files included with the
1036@code{"foo.h"} syntax start at the beginning of the chain, but with one
1037extra directory prepended. This is the directory of the current file;
1038the one containing the @code{#include} directive. Prepending this
1039directory on a per-file basis is handled by the function
1040@code{search_from}.
1041
1042Note that a header included with a directory component, such as
1043@code{#include "mydir/foo.h"} and opened as
1044@file{/usr/local/include/mydir/foo.h}, will have the complete path minus
1045the basename @samp{foo.h} as the current directory.
1046
1047Enough information is stored in the splay tree that CPP can immediately
1048tell whether it can skip the header file because of the multiple include
1049optimization, whether the file didn't exist or couldn't be opened for
1050some reason, or whether the header was flagged not to be re-used, as it
1051is with the obsolete @code{#import} directive.
1052
1053For the benefit of MS-DOS filesystems with an 8.3 filename limitation,
1054CPP offers the ability to treat various include file names as aliases
1055for the real header files with shorter names. The map from one to the
1056other is found in a special file called @samp{header.gcc}, stored in the
1057command line (or system) include directories to which the mapping
1058applies. This may be higher up the directory tree than the full path to
1059the file minus the base name.
1060
1061@node Index
1062@unnumbered Index
1063@printindex cp
1064
1065@bye