OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [doc/] [cppinternals.info] - Blame information for rev 823

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
This is doc/cppinternals.info, produced by makeinfo version 4.8 from
2
/scratch/mitchell/gcc-releases/gcc-4.2.2/gcc-4.2.2/gcc/doc/cppinternals.texi.
3
 
4
INFO-DIR-SECTION Software development
5
START-INFO-DIR-ENTRY
6
* Cpplib: (cppinternals).      Cpplib internals.
7
END-INFO-DIR-ENTRY
8
 
9
   This file documents the internals of the GNU C Preprocessor.
10
 
11
   Copyright 2000, 2001, 2002, 2004, 2005 Free Software Foundation, Inc.
12
 
13
   Permission is granted to make and distribute verbatim copies of this
14
manual provided the copyright notice and this permission notice are
15
preserved on all copies.
16
 
17
   Permission is granted to copy and distribute modified versions of
18
this manual under the conditions for verbatim copying, provided also
19
that the entire resulting derived work is distributed under the terms
20
of a permission notice identical to this one.
21
 
22
   Permission is granted to copy and distribute translations of this
23
manual into another language, under the above conditions for modified
24
versions.
25
 
26

27
File: cppinternals.info,  Node: Top,  Next: Conventions,  Up: (dir)
28
 
29
The GNU C Preprocessor Internals
30
********************************
31
 
32
1 Cpplib--the GNU C Preprocessor
33
********************************
34
 
35
The GNU C preprocessor is implemented as a library, "cpplib", so it can
36
be easily shared between a stand-alone preprocessor, and a preprocessor
37
integrated with the C, C++ and Objective-C front ends.  It is also
38
available for use by other programs, though this is not recommended as
39
its exposed interface has not yet reached a point of reasonable
40
stability.
41
 
42
   The library has been written to be re-entrant, so that it can be used
43
to preprocess many files simultaneously if necessary.  It has also been
44
written with the preprocessing token as the fundamental unit; the
45
preprocessor in previous versions of GCC would operate on text strings
46
as the fundamental unit.
47
 
48
   This brief manual documents the internals of cpplib, and explains
49
some of the tricky issues.  It is intended that, along with the
50
comments in the source code, a reasonably competent C programmer should
51
be able to figure out what the code is doing, and why things have been
52
implemented the way they have.
53
 
54
* Menu:
55
 
56
* Conventions::         Conventions used in the code.
57
* Lexer::               The combined C, C++ and Objective-C Lexer.
58
* Hash Nodes::          All identifiers are entered into a hash table.
59
* Macro Expansion::     Macro expansion algorithm.
60
* Token Spacing::       Spacing and paste avoidance issues.
61
* Line Numbering::      Tracking location within files.
62
* Guard Macros::        Optimizing header files with guard macros.
63
* Files::               File handling.
64
* Concept Index::       Index.
65
 
66

67
File: cppinternals.info,  Node: Conventions,  Next: Lexer,  Prev: Top,  Up: Top
68
 
69
Conventions
70
***********
71
 
72
cpplib has two interfaces--one is exposed internally only, and the
73
other is for both internal and external use.
74
 
75
   The convention is that functions and types that are exposed to
76
multiple files internally are prefixed with `_cpp_', and are to be
77
found in the file `internal.h'.  Functions and types exposed to external
78
clients are in `cpplib.h', and prefixed with `cpp_'.  For historical
79
reasons this is no longer quite true, but we should strive to stick to
80
it.
81
 
82
   We are striving to reduce the information exposed in `cpplib.h' to
83
the bare minimum necessary, and then to keep it there.  This makes clear
84
exactly what external clients are entitled to assume, and allows us to
85
change internals in the future without worrying whether library clients
86
are perhaps relying on some kind of undocumented implementation-specific
87
behavior.
88
 
89

90
File: cppinternals.info,  Node: Lexer,  Next: Hash Nodes,  Prev: Conventions,  Up: Top
91
 
92
The Lexer
93
*********
94
 
95
Overview
96
========
97
 
98
The lexer is contained in the file `lex.c'.  It is a hand-coded lexer,
99
and not implemented as a state machine.  It can understand C, C++ and
100
Objective-C source code, and has been extended to allow reasonably
101
successful preprocessing of assembly language.  The lexer does not make
102
an initial pass to strip out trigraphs and escaped newlines, but handles
103
them as they are encountered in a single pass of the input file.  It
104
returns preprocessing tokens individually, not a line at a time.
105
 
106
   It is mostly transparent to users of the library, since the library's
107
interface for obtaining the next token, `cpp_get_token', takes care of
108
lexing new tokens, handling directives, and expanding macros as
109
necessary.  However, the lexer does expose some functionality so that
110
clients of the library can easily spell a given token, such as
111
`cpp_spell_token' and `cpp_token_len'.  These functions are useful when
112
generating diagnostics, and for emitting the preprocessed output.
113
 
114
Lexing a token
115
==============
116
 
117
Lexing of an individual token is handled by `_cpp_lex_direct' and its
118
subroutines.  In its current form the code is quite complicated, with
119
read ahead characters and such-like, since it strives to not step back
120
in the character stream in preparation for handling non-ASCII file
121
encodings.  The current plan is to convert any such files to UTF-8
122
before processing them.  This complexity is therefore unnecessary and
123
will be removed, so I'll not discuss it further here.
124
 
125
   The job of `_cpp_lex_direct' is simply to lex a token.  It is not
126
responsible for issues like directive handling, returning lookahead
127
tokens directly, multiple-include optimization, or conditional block
128
skipping.  It necessarily has a minor ro^le to play in memory
129
management of lexed lines.  I discuss these issues in a separate section
130
(*note Lexing a line::).
131
 
132
   The lexer places the token it lexes into storage pointed to by the
133
variable `cur_token', and then increments it.  This variable is
134
important for correct diagnostic positioning.  Unless a specific line
135
and column are passed to the diagnostic routines, they will examine the
136
`line' and `col' values of the token just before the location that
137
`cur_token' points to, and use that location to report the diagnostic.
138
 
139
   The lexer does not consider whitespace to be a token in its own
140
right.  If whitespace (other than a new line) precedes a token, it sets
141
the `PREV_WHITE' bit in the token's flags.  Each token has its `line'
142
and `col' variables set to the line and column of the first character
143
of the token.  This line number is the line number in the translation
144
unit, and can be converted to a source (file, line) pair using the line
145
map code.
146
 
147
   The first token on a logical, i.e. unescaped, line has the flag
148
`BOL' set for beginning-of-line.  This flag is intended for internal
149
use, both to distinguish a `#' that begins a directive from one that
150
doesn't, and to generate a call-back to clients that want to be
151
notified about the start of every non-directive line with tokens on it.
152
Clients cannot reliably determine this for themselves: the first token
153
might be a macro, and the tokens of a macro expansion do not have the
154
`BOL' flag set.  The macro expansion may even be empty, and the next
155
token on the line certainly won't have the `BOL' flag set.
156
 
157
   New lines are treated specially; exactly how the lexer handles them
158
is context-dependent.  The C standard mandates that directives are
159
terminated by the first unescaped newline character, even if it appears
160
in the middle of a macro expansion.  Therefore, if the state variable
161
`in_directive' is set, the lexer returns a `CPP_EOF' token, which is
162
normally used to indicate end-of-file, to indicate end-of-directive.
163
In a directive a `CPP_EOF' token never means end-of-file.
164
Conveniently, if the caller was `collect_args', it already handles
165
`CPP_EOF' as if it were end-of-file, and reports an error about an
166
unterminated macro argument list.
167
 
168
   The C standard also specifies that a new line in the middle of the
169
arguments to a macro is treated as whitespace.  This white space is
170
important in case the macro argument is stringified.  The state variable
171
`parsing_args' is nonzero when the preprocessor is collecting the
172
arguments to a macro call.  It is set to 1 when looking for the opening
173
parenthesis to a function-like macro, and 2 when collecting the actual
174
arguments up to the closing parenthesis, since these two cases need to
175
be distinguished sometimes.  One such time is here: the lexer sets the
176
`PREV_WHITE' flag of a token if it meets a new line when `parsing_args'
177
is set to 2.  It doesn't set it if it meets a new line when
178
`parsing_args' is 1, since then code like
179
 
180
     #define foo() bar
181
     foo
182
     baz
183
 
184
would be output with an erroneous space before `baz':
185
 
186
     foo
187
      baz
188
 
189
   This is a good example of the subtlety of getting token spacing
190
correct in the preprocessor; there are plenty of tests in the testsuite
191
for corner cases like this.
192
 
193
   The lexer is written to treat each of `\r', `\n', `\r\n' and `\n\r'
194
as a single new line indicator.  This allows it to transparently
195
preprocess MS-DOS, Macintosh and Unix files without their needing to
196
pass through a special filter beforehand.
197
 
198
   We also decided to treat a backslash, either `\' or the trigraph
199
`??/', separated from one of the above newline indicators by
200
non-comment whitespace only, as intending to escape the newline.  It
201
tends to be a typing mistake, and cannot reasonably be mistaken for
202
anything else in any of the C-family grammars.  Since handling it this
203
way is not strictly conforming to the ISO standard, the library issues a
204
warning wherever it encounters it.
205
 
206
   Handling newlines like this is made simpler by doing it in one place
207
only.  The function `handle_newline' takes care of all newline
208
characters, and `skip_escaped_newlines' takes care of arbitrarily long
209
sequences of escaped newlines, deferring to `handle_newline' to handle
210
the newlines themselves.
211
 
212
   The most painful aspect of lexing ISO-standard C and C++ is handling
213
trigraphs and backlash-escaped newlines.  Trigraphs are processed before
214
any interpretation of the meaning of a character is made, and
215
unfortunately there is a trigraph representation for a backslash, so it
216
is possible for the trigraph `??/' to introduce an escaped newline.
217
 
218
   Escaped newlines are tedious because theoretically they can occur
219
anywhere--between the `+' and `=' of the `+=' token, within the
220
characters of an identifier, and even between the `*' and `/' that
221
terminates a comment.  Moreover, you cannot be sure there is just
222
one--there might be an arbitrarily long sequence of them.
223
 
224
   So, for example, the routine that lexes a number, `parse_number',
225
cannot assume that it can scan forwards until the first non-number
226
character and be done with it, because this could be the `\'
227
introducing an escaped newline, or the `?' introducing the trigraph
228
sequence that represents the `\' of an escaped newline.  If it
229
encounters a `?' or `\', it calls `skip_escaped_newlines' to skip over
230
any potential escaped newlines before checking whether the number has
231
been finished.
232
 
233
   Similarly code in the main body of `_cpp_lex_direct' cannot simply
234
check for a `=' after a `+' character to determine whether it has a
235
`+=' token; it needs to be prepared for an escaped newline of some
236
sort.  Such cases use the function `get_effective_char', which returns
237
the first character after any intervening escaped newlines.
238
 
239
   The lexer needs to keep track of the correct column position,
240
including counting tabs as specified by the `-ftabstop=' option.  This
241
should be done even within C-style comments; they can appear in the
242
middle of a line, and we want to report diagnostics in the correct
243
position for text appearing after the end of the comment.
244
 
245
   Some identifiers, such as `__VA_ARGS__' and poisoned identifiers,
246
may be invalid and require a diagnostic.  However, if they appear in a
247
macro expansion we don't want to complain with each use of the macro.
248
It is therefore best to catch them during the lexing stage, in
249
`parse_identifier'.  In both cases, whether a diagnostic is needed or
250
not is dependent upon the lexer's state.  For example, we don't want to
251
issue a diagnostic for re-poisoning a poisoned identifier, or for using
252
`__VA_ARGS__' in the expansion of a variable-argument macro.  Therefore
253
`parse_identifier' makes use of state flags to determine whether a
254
diagnostic is appropriate.  Since we change state on a per-token basis,
255
and don't lex whole lines at a time, this is not a problem.
256
 
257
   Another place where state flags are used to change behavior is whilst
258
lexing header names.  Normally, a `<' would be lexed as a single token.
259
After a `#include' directive, though, it should be lexed as a single
260
token as far as the nearest `>' character.  Note that we don't allow
261
the terminators of header names to be escaped; the first `"' or `>'
262
terminates the header name.
263
 
264
   Interpretation of some character sequences depends upon whether we
265
are lexing C, C++ or Objective-C, and on the revision of the standard in
266
force.  For example, `::' is a single token in C++, but in C it is two
267
separate `:' tokens and almost certainly a syntax error.  Such cases
268
are handled by `_cpp_lex_direct' based upon command-line flags stored
269
in the `cpp_options' structure.
270
 
271
   Once a token has been lexed, it leads an independent existence.  The
272
spelling of numbers, identifiers and strings is copied to permanent
273
storage from the original input buffer, so a token remains valid and
274
correct even if its source buffer is freed with `_cpp_pop_buffer'.  The
275
storage holding the spellings of such tokens remains until the client
276
program calls cpp_destroy, probably at the end of the translation unit.
277
 
278
Lexing a line
279
=============
280
 
281
When the preprocessor was changed to return pointers to tokens, one
282
feature I wanted was some sort of guarantee regarding how long a
283
returned pointer remains valid.  This is important to the stand-alone
284
preprocessor, the future direction of the C family front ends, and even
285
to cpplib itself internally.
286
 
287
   Occasionally the preprocessor wants to be able to peek ahead in the
288
token stream.  For example, after the name of a function-like macro, it
289
wants to check the next token to see if it is an opening parenthesis.
290
Another example is that, after reading the first few tokens of a
291
`#pragma' directive and not recognizing it as a registered pragma, it
292
wants to backtrack and allow the user-defined handler for unknown
293
pragmas to access the full `#pragma' token stream.  The stand-alone
294
preprocessor wants to be able to test the current token with the
295
previous one to see if a space needs to be inserted to preserve their
296
separate tokenization upon re-lexing (paste avoidance), so it needs to
297
be sure the pointer to the previous token is still valid.  The
298
recursive-descent C++ parser wants to be able to perform tentative
299
parsing arbitrarily far ahead in the token stream, and then to be able
300
to jump back to a prior position in that stream if necessary.
301
 
302
   The rule I chose, which is fairly natural, is to arrange that the
303
preprocessor lex all tokens on a line consecutively into a token buffer,
304
which I call a "token run", and when meeting an unescaped new line
305
(newlines within comments do not count either), to start lexing back at
306
the beginning of the run.  Note that we do _not_ lex a line of tokens
307
at once; if we did that `parse_identifier' would not have state flags
308
available to warn about invalid identifiers (*note Invalid
309
identifiers::).
310
 
311
   In other words, accessing tokens that appeared earlier in the current
312
line is valid, but since each logical line overwrites the tokens of the
313
previous line, tokens from prior lines are unavailable.  In particular,
314
since a directive only occupies a single logical line, this means that
315
the directive handlers like the `#pragma' handler can jump around in
316
the directive's tokens if necessary.
317
 
318
   Two issues remain: what about tokens that arise from macro
319
expansions, and what happens when we have a long line that overflows
320
the token run?
321
 
322
   Since we promise clients that we preserve the validity of pointers
323
that we have already returned for tokens that appeared earlier in the
324
line, we cannot reallocate the run.  Instead, on overflow it is
325
expanded by chaining a new token run on to the end of the existing one.
326
 
327
   The tokens forming a macro's replacement list are collected by the
328
`#define' handler, and placed in storage that is only freed by
329
`cpp_destroy'.  So if a macro is expanded in the line of tokens, the
330
pointers to the tokens of its expansion that are returned will always
331
remain valid.  However, macros are a little trickier than that, since
332
they give rise to three sources of fresh tokens.  They are the built-in
333
macros like `__LINE__', and the `#' and `##' operators for
334
stringification and token pasting.  I handled this by allocating space
335
for these tokens from the lexer's token run chain.  This means they
336
automatically receive the same lifetime guarantees as lexed tokens, and
337
we don't need to concern ourselves with freeing them.
338
 
339
   Lexing into a line of tokens solves some of the token memory
340
management issues, but not all.  The opening parenthesis after a
341
function-like macro name might lie on a different line, and the front
342
ends definitely want the ability to look ahead past the end of the
343
current line.  So cpplib only moves back to the start of the token run
344
at the end of a line if the variable `keep_tokens' is zero.
345
Line-buffering is quite natural for the preprocessor, and as a result
346
the only time cpplib needs to increment this variable is whilst looking
347
for the opening parenthesis to, and reading the arguments of, a
348
function-like macro.  In the near future cpplib will export an
349
interface to increment and decrement this variable, so that clients can
350
share full control over the lifetime of token pointers too.
351
 
352
   The routine `_cpp_lex_token' handles moving to new token runs,
353
calling `_cpp_lex_direct' to lex new tokens, or returning
354
previously-lexed tokens if we stepped back in the token stream.  It also
355
checks each token for the `BOL' flag, which might indicate a directive
356
that needs to be handled, or require a start-of-line call-back to be
357
made.  `_cpp_lex_token' also handles skipping over tokens in failed
358
conditional blocks, and invalidates the control macro of the
359
multiple-include optimization if a token was successfully lexed outside
360
a directive.  In other words, its callers do not need to concern
361
themselves with such issues.
362
 
363

364
File: cppinternals.info,  Node: Hash Nodes,  Next: Macro Expansion,  Prev: Lexer,  Up: Top
365
 
366
Hash Nodes
367
**********
368
 
369
When cpplib encounters an "identifier", it generates a hash code for it
370
and stores it in the hash table.  By "identifier" we mean tokens with
371
type `CPP_NAME'; this includes identifiers in the usual C sense, as
372
well as keywords, directive names, macro names and so on.  For example,
373
all of `pragma', `int', `foo' and `__GNUC__' are identifiers and hashed
374
when lexed.
375
 
376
   Each node in the hash table contain various information about the
377
identifier it represents.  For example, its length and type.  At any one
378
time, each identifier falls into exactly one of three categories:
379
 
380
   * Macros
381
 
382
     These have been declared to be macros, either on the command line
383
     or with `#define'.  A few, such as `__TIME__' are built-ins
384
     entered in the hash table during initialization.  The hash node
385
     for a normal macro points to a structure with more information
386
     about the macro, such as whether it is function-like, how many
387
     arguments it takes, and its expansion.  Built-in macros are
388
     flagged as special, and instead contain an enum indicating which
389
     of the various built-in macros it is.
390
 
391
   * Assertions
392
 
393
     Assertions are in a separate namespace to macros.  To enforce
394
     this, cpp actually prepends a `#' character before hashing and
395
     entering it in the hash table.  An assertion's node points to a
396
     chain of answers to that assertion.
397
 
398
   * Void
399
 
400
     Everything else falls into this category--an identifier that is not
401
     currently a macro, or a macro that has since been undefined with
402
     `#undef'.
403
 
404
     When preprocessing C++, this category also includes the named
405
     operators, such as `xor'.  In expressions these behave like the
406
     operators they represent, but in contexts where the spelling of a
407
     token matters they are spelt differently.  This spelling
408
     distinction is relevant when they are operands of the stringizing
409
     and pasting macro operators `#' and `##'.  Named operator hash
410
     nodes are flagged, both to catch the spelling distinction and to
411
     prevent them from being defined as macros.
412
 
413
   The same identifiers share the same hash node.  Since each identifier
414
token, after lexing, contains a pointer to its hash node, this is used
415
to provide rapid lookup of various information.  For example, when
416
parsing a `#define' statement, CPP flags each argument's identifier
417
hash node with the index of that argument.  This makes duplicated
418
argument checking an O(1) operation for each argument.  Similarly, for
419
each identifier in the macro's expansion, lookup to see if it is an
420
argument, and which argument it is, is also an O(1) operation.  Further,
421
each directive name, such as `endif', has an associated directive enum
422
stored in its hash node, so that directive lookup is also O(1).
423
 
424

425
File: cppinternals.info,  Node: Macro Expansion,  Next: Token Spacing,  Prev: Hash Nodes,  Up: Top
426
 
427
Macro Expansion Algorithm
428
*************************
429
 
430
Macro expansion is a tricky operation, fraught with nasty corner cases
431
and situations that render what you thought was a nifty way to optimize
432
the preprocessor's expansion algorithm wrong in quite subtle ways.
433
 
434
   I strongly recommend you have a good grasp of how the C and C++
435
standards require macros to be expanded before diving into this
436
section, let alone the code!.  If you don't have a clear mental picture
437
of how things like nested macro expansion, stringification and token
438
pasting are supposed to work, damage to your sanity can quickly result.
439
 
440
Internal representation of macros
441
=================================
442
 
443
The preprocessor stores macro expansions in tokenized form.  This saves
444
repeated lexing passes during expansion, at the cost of a small
445
increase in memory consumption on average.  The tokens are stored
446
contiguously in memory, so a pointer to the first one and a token count
447
is all you need to get the replacement list of a macro.
448
 
449
   If the macro is a function-like macro the preprocessor also stores
450
its parameters, in the form of an ordered list of pointers to the hash
451
table entry of each parameter's identifier.  Further, in the macro's
452
stored expansion each occurrence of a parameter is replaced with a
453
special token of type `CPP_MACRO_ARG'.  Each such token holds the index
454
of the parameter it represents in the parameter list, which allows
455
rapid replacement of parameters with their arguments during expansion.
456
Despite this optimization it is still necessary to store the original
457
parameters to the macro, both for dumping with e.g., `-dD', and to warn
458
about non-trivial macro redefinitions when the parameter names have
459
changed.
460
 
461
Macro expansion overview
462
========================
463
 
464
The preprocessor maintains a "context stack", implemented as a linked
465
list of `cpp_context' structures, which together represent the macro
466
expansion state at any one time.  The `struct cpp_reader' member
467
variable `context' points to the current top of this stack.  The top
468
normally holds the unexpanded replacement list of the innermost macro
469
under expansion, except when cpplib is about to pre-expand an argument,
470
in which case it holds that argument's unexpanded tokens.
471
 
472
   When there are no macros under expansion, cpplib is in "base
473
context".  All contexts other than the base context contain a
474
contiguous list of tokens delimited by a starting and ending token.
475
When not in base context, cpplib obtains the next token from the list
476
of the top context.  If there are no tokens left in the list, it pops
477
that context off the stack, and subsequent ones if necessary, until an
478
unexhausted context is found or it returns to base context.  In base
479
context, cpplib reads tokens directly from the lexer.
480
 
481
   If it encounters an identifier that is both a macro and enabled for
482
expansion, cpplib prepares to push a new context for that macro on the
483
stack by calling the routine `enter_macro_context'.  When this routine
484
returns, the new context will contain the unexpanded tokens of the
485
replacement list of that macro.  In the case of function-like macros,
486
`enter_macro_context' also replaces any parameters in the replacement
487
list, stored as `CPP_MACRO_ARG' tokens, with the appropriate macro
488
argument.  If the standard requires that the parameter be replaced with
489
its expanded argument, the argument will have been fully macro expanded
490
first.
491
 
492
   `enter_macro_context' also handles special macros like `__LINE__'.
493
Although these macros expand to a single token which cannot contain any
494
further macros, for reasons of token spacing (*note Token Spacing::)
495
and simplicity of implementation, cpplib handles these special macros
496
by pushing a context containing just that one token.
497
 
498
   The final thing that `enter_macro_context' does before returning is
499
to mark the macro disabled for expansion (except for special macros
500
like `__TIME__').  The macro is re-enabled when its context is later
501
popped from the context stack, as described above.  This strict
502
ordering ensures that a macro is disabled whilst its expansion is being
503
scanned, but that it is _not_ disabled whilst any arguments to it are
504
being expanded.
505
 
506
Scanning the replacement list for macros to expand
507
==================================================
508
 
509
The C standard states that, after any parameters have been replaced
510
with their possibly-expanded arguments, the replacement list is scanned
511
for nested macros.  Further, any identifiers in the replacement list
512
that are not expanded during this scan are never again eligible for
513
expansion in the future, if the reason they were not expanded is that
514
the macro in question was disabled.
515
 
516
   Clearly this latter condition can only apply to tokens resulting from
517
argument pre-expansion.  Other tokens never have an opportunity to be
518
re-tested for expansion.  It is possible for identifiers that are
519
function-like macros to not expand initially but to expand during a
520
later scan.  This occurs when the identifier is the last token of an
521
argument (and therefore originally followed by a comma or a closing
522
parenthesis in its macro's argument list), and when it replaces its
523
parameter in the macro's replacement list, the subsequent token happens
524
to be an opening parenthesis (itself possibly the first token of an
525
argument).
526
 
527
   It is important to note that when cpplib reads the last token of a
528
given context, that context still remains on the stack.  Only when
529
looking for the _next_ token do we pop it off the stack and drop to a
530
lower context.  This makes backing up by one token easy, but more
531
importantly ensures that the macro corresponding to the current context
532
is still disabled when we are considering the last token of its
533
replacement list for expansion (or indeed expanding it).  As an
534
example, which illustrates many of the points above, consider
535
 
536
     #define foo(x) bar x
537
     foo(foo) (2)
538
 
539
which fully expands to `bar foo (2)'.  During pre-expansion of the
540
argument, `foo' does not expand even though the macro is enabled, since
541
it has no following parenthesis [pre-expansion of an argument only uses
542
tokens from that argument; it cannot take tokens from whatever follows
543
the macro invocation].  This still leaves the argument token `foo'
544
eligible for future expansion.  Then, when re-scanning after argument
545
replacement, the token `foo' is rejected for expansion, and marked
546
ineligible for future expansion, since the macro is now disabled.  It
547
is disabled because the replacement list `bar foo' of the macro is
548
still on the context stack.
549
 
550
   If instead the algorithm looked for an opening parenthesis first and
551
then tested whether the macro were disabled it would be subtly wrong.
552
In the example above, the replacement list of `foo' would be popped in
553
the process of finding the parenthesis, re-enabling `foo' and expanding
554
it a second time.
555
 
556
Looking for a function-like macro's opening parenthesis
557
=======================================================
558
 
559
Function-like macros only expand when immediately followed by a
560
parenthesis.  To do this cpplib needs to temporarily disable macros and
561
read the next token.  Unfortunately, because of spacing issues (*note
562
Token Spacing::), there can be fake padding tokens in-between, and if
563
the next real token is not a parenthesis cpplib needs to be able to
564
back up that one token as well as retain the information in any
565
intervening padding tokens.
566
 
567
   Backing up more than one token when macros are involved is not
568
permitted by cpplib, because in general it might involve issues like
569
restoring popped contexts onto the context stack, which are too hard.
570
Instead, searching for the parenthesis is handled by a special
571
function, `funlike_invocation_p', which remembers padding information
572
as it reads tokens.  If the next real token is not an opening
573
parenthesis, it backs up that one token, and then pushes an extra
574
context just containing the padding information if necessary.
575
 
576
Marking tokens ineligible for future expansion
577
==============================================
578
 
579
As discussed above, cpplib needs a way of marking tokens as
580
unexpandable.  Since the tokens cpplib handles are read-only once they
581
have been lexed, it instead makes a copy of the token and adds the flag
582
`NO_EXPAND' to the copy.
583
 
584
   For efficiency and to simplify memory management by avoiding having
585
to remember to free these tokens, they are allocated as temporary tokens
586
from the lexer's current token run (*note Lexing a line::) using the
587
function `_cpp_temp_token'.  The tokens are then re-used once the
588
current line of tokens has been read in.
589
 
590
   This might sound unsafe.  However, tokens runs are not re-used at the
591
end of a line if it happens to be in the middle of a macro argument
592
list, and cpplib only wants to back-up more than one lexer token in
593
situations where no macro expansion is involved, so the optimization is
594
safe.
595
 
596

597
File: cppinternals.info,  Node: Token Spacing,  Next: Line Numbering,  Prev: Macro Expansion,  Up: Top
598
 
599
Token Spacing
600
*************
601
 
602
First, consider an issue that only concerns the stand-alone
603
preprocessor: there needs to be a guarantee that re-reading its
604
preprocessed output results in an identical token stream.  Without
605
taking special measures, this might not be the case because of macro
606
substitution.  For example:
607
 
608
     #define PLUS +
609
     #define EMPTY
610
     #define f(x) =x=
611
     +PLUS -EMPTY- PLUS+ f(=)
612
             ==> + + - - + + = = =
613
     _not_
614
             ==> ++ -- ++ ===
615
 
616
   One solution would be to simply insert a space between all adjacent
617
tokens.  However, we would like to keep space insertion to a minimum,
618
both for aesthetic reasons and because it causes problems for people who
619
still try to abuse the preprocessor for things like Fortran source and
620
Makefiles.
621
 
622
   For now, just notice that when tokens are added (or removed, as
623
shown by the `EMPTY' example) from the original lexed token stream, we
624
need to check for accidental token pasting.  We call this "paste
625
avoidance".  Token addition and removal can only occur because of macro
626
expansion, but accidental pasting can occur in many places: both before
627
and after each macro replacement, each argument replacement, and
628
additionally each token created by the `#' and `##' operators.
629
 
630
   Look at how the preprocessor gets whitespace output correct
631
normally.  The `cpp_token' structure contains a flags byte, and one of
632
those flags is `PREV_WHITE'.  This is flagged by the lexer, and
633
indicates that the token was preceded by whitespace of some form other
634
than a new line.  The stand-alone preprocessor can use this flag to
635
decide whether to insert a space between tokens in the output.
636
 
637
   Now consider the result of the following macro expansion:
638
 
639
     #define add(x, y, z) x + y +z;
640
     sum = add (1,2, 3);
641
             ==> sum = 1 + 2 +3;
642
 
643
   The interesting thing here is that the tokens `1' and `2' are output
644
with a preceding space, and `3' is output without a preceding space,
645
but when lexed none of these tokens had that property.  Careful
646
consideration reveals that `1' gets its preceding whitespace from the
647
space preceding `add' in the macro invocation, _not_ replacement list.
648
`2' gets its whitespace from the space preceding the parameter `y' in
649
the macro replacement list, and `3' has no preceding space because
650
parameter `z' has none in the replacement list.
651
 
652
   Once lexed, tokens are effectively fixed and cannot be altered, since
653
pointers to them might be held in many places, in particular by
654
in-progress macro expansions.  So instead of modifying the two tokens
655
above, the preprocessor inserts a special token, which I call a
656
"padding token", into the token stream to indicate that spacing of the
657
subsequent token is special.  The preprocessor inserts padding tokens
658
in front of every macro expansion and expanded macro argument.  These
659
point to a "source token" from which the subsequent real token should
660
inherit its spacing.  In the above example, the source tokens are `add'
661
in the macro invocation, and `y' and `z' in the macro replacement list,
662
respectively.
663
 
664
   It is quite easy to get multiple padding tokens in a row, for
665
example if a macro's first replacement token expands straight into
666
another macro.
667
 
668
     #define foo bar
669
     #define bar baz
670
     [foo]
671
             ==> [baz]
672
 
673
   Here, two padding tokens are generated with sources the `foo' token
674
between the brackets, and the `bar' token from foo's replacement list,
675
respectively.  Clearly the first padding token is the one to use, so
676
the output code should contain a rule that the first padding token in a
677
sequence is the one that matters.
678
 
679
   But what if a macro expansion is left?  Adjusting the above example
680
slightly:
681
 
682
     #define foo bar
683
     #define bar EMPTY baz
684
     #define EMPTY
685
     [foo] EMPTY;
686
             ==> [ baz] ;
687
 
688
   As shown, now there should be a space before `baz' and the semicolon
689
in the output.
690
 
691
   The rules we decided above fail for `baz': we generate three padding
692
tokens, one per macro invocation, before the token `baz'.  We would
693
then have it take its spacing from the first of these, which carries
694
source token `foo' with no leading space.
695
 
696
   It is vital that cpplib get spacing correct in these examples since
697
any of these macro expansions could be stringified, where spacing
698
matters.
699
 
700
   So, this demonstrates that not just entering macro and argument
701
expansions, but leaving them requires special handling too.  I made
702
cpplib insert a padding token with a `NULL' source token when leaving
703
macro expansions, as well as after each replaced argument in a macro's
704
replacement list.  It also inserts appropriate padding tokens on either
705
side of tokens created by the `#' and `##' operators.  I expanded the
706
rule so that, if we see a padding token with a `NULL' source token,
707
_and_ that source token has no leading space, then we behave as if we
708
have seen no padding tokens at all.  A quick check shows this rule will
709
then get the above example correct as well.
710
 
711
   Now a relationship with paste avoidance is apparent: we have to be
712
careful about paste avoidance in exactly the same locations we have
713
padding tokens in order to get white space correct.  This makes
714
implementation of paste avoidance easy: wherever the stand-alone
715
preprocessor is fixing up spacing because of padding tokens, and it
716
turns out that no space is needed, it has to take the extra step to
717
check that a space is not needed after all to avoid an accidental paste.
718
The function `cpp_avoid_paste' advises whether a space is required
719
between two consecutive tokens.  To avoid excessive spacing, it tries
720
hard to only require a space if one is likely to be necessary, but for
721
reasons of efficiency it is slightly conservative and might recommend a
722
space where one is not strictly needed.
723
 
724

725
File: cppinternals.info,  Node: Line Numbering,  Next: Guard Macros,  Prev: Token Spacing,  Up: Top
726
 
727
Line numbering
728
**************
729
 
730
Just which line number anyway?
731
==============================
732
 
733
There are three reasonable requirements a cpplib client might have for
734
the line number of a token passed to it:
735
 
736
   * The source line it was lexed on.
737
 
738
   * The line it is output on.  This can be different to the line it was
739
     lexed on if, for example, there are intervening escaped newlines or
740
     C-style comments.  For example:
741
 
742
          foo /* A long
743
          comment */ bar \
744
          baz
745
          =>
746
          foo bar baz
747
 
748
   * If the token results from a macro expansion, the line of the macro
749
     name, or possibly the line of the closing parenthesis in the case
750
     of function-like macro expansion.
751
 
752
   The `cpp_token' structure contains `line' and `col' members.  The
753
lexer fills these in with the line and column of the first character of
754
the token.  Consequently, but maybe unexpectedly, a token from the
755
replacement list of a macro expansion carries the location of the token
756
within the `#define' directive, because cpplib expands a macro by
757
returning pointers to the tokens in its replacement list.  The current
758
implementation of cpplib assigns tokens created from built-in macros
759
and the `#' and `##' operators the location of the most recently lexed
760
token.  This is a because they are allocated from the lexer's token
761
runs, and because of the way the diagnostic routines infer the
762
appropriate location to report.
763
 
764
   The diagnostic routines in cpplib display the location of the most
765
recently _lexed_ token, unless they are passed a specific line and
766
column to report.  For diagnostics regarding tokens that arise from
767
macro expansions, it might also be helpful for the user to see the
768
original location in the macro definition that the token came from.
769
Since that is exactly the information each token carries, such an
770
enhancement could be made relatively easily in future.
771
 
772
   The stand-alone preprocessor faces a similar problem when determining
773
the correct line to output the token on: the position attached to a
774
token is fairly useless if the token came from a macro expansion.  All
775
tokens on a logical line should be output on its first physical line, so
776
the token's reported location is also wrong if it is part of a physical
777
line other than the first.
778
 
779
   To solve these issues, cpplib provides a callback that is generated
780
whenever it lexes a preprocessing token that starts a new logical line
781
other than a directive.  It passes this token (which may be a `CPP_EOF'
782
token indicating the end of the translation unit) to the callback
783
routine, which can then use the line and column of this token to
784
produce correct output.
785
 
786
Representation of line numbers
787
==============================
788
 
789
As mentioned above, cpplib stores with each token the line number that
790
it was lexed on.  In fact, this number is not the number of the line in
791
the source file, but instead bears more resemblance to the number of the
792
line in the translation unit.
793
 
794
   The preprocessor maintains a monotonic increasing line count, which
795
is incremented at every new line character (and also at the end of any
796
buffer that does not end in a new line).  Since a line number of zero is
797
useful to indicate certain special states and conditions, this variable
798
starts counting from one.
799
 
800
   This variable therefore uniquely enumerates each line in the
801
translation unit.  With some simple infrastructure, it is straight
802
forward to map from this to the original source file and line number
803
pair, saving space whenever line number information needs to be saved.
804
The code the implements this mapping lies in the files `line-map.c' and
805
`line-map.h'.
806
 
807
   Command-line macros and assertions are implemented by pushing a
808
buffer containing the right hand side of an equivalent `#define' or
809
`#assert' directive.  Some built-in macros are handled similarly.
810
Since these are all processed before the first line of the main input
811
file, it will typically have an assigned line closer to twenty than to
812
one.
813
 
814

815
File: cppinternals.info,  Node: Guard Macros,  Next: Files,  Prev: Line Numbering,  Up: Top
816
 
817
The Multiple-Include Optimization
818
*********************************
819
 
820
Header files are often of the form
821
 
822
     #ifndef FOO
823
     #define FOO
824
     ...
825
     #endif
826
 
827
to prevent the compiler from processing them more than once.  The
828
preprocessor notices such header files, so that if the header file
829
appears in a subsequent `#include' directive and `FOO' is defined, then
830
it is ignored and it doesn't preprocess or even re-open the file a
831
second time.  This is referred to as the "multiple include
832
optimization".
833
 
834
   Under what circumstances is such an optimization valid?  If the file
835
were included a second time, it can only be optimized away if that
836
inclusion would result in no tokens to return, and no relevant
837
directives to process.  Therefore the current implementation imposes
838
requirements and makes some allowances as follows:
839
 
840
  1. There must be no tokens outside the controlling `#if'-`#endif'
841
     pair, but whitespace and comments are permitted.
842
 
843
  2. There must be no directives outside the controlling directive
844
     pair, but the "null directive" (a line containing nothing other
845
     than a single `#' and possibly whitespace) is permitted.
846
 
847
  3. The opening directive must be of the form
848
 
849
          #ifndef FOO
850
 
851
     or
852
 
853
          #if !defined FOO     [equivalently, #if !defined(FOO)]
854
 
855
  4. In the second form above, the tokens forming the `#if' expression
856
     must have come directly from the source file--no macro expansion
857
     must have been involved.  This is because macro definitions can
858
     change, and tracking whether or not a relevant change has been
859
     made is not worth the implementation cost.
860
 
861
  5. There can be no `#else' or `#elif' directives at the outer
862
     conditional block level, because they would probably contain
863
     something of interest to a subsequent pass.
864
 
865
   First, when pushing a new file on the buffer stack,
866
`_stack_include_file' sets the controlling macro `mi_cmacro' to `NULL',
867
and sets `mi_valid' to `true'.  This indicates that the preprocessor
868
has not yet encountered anything that would invalidate the
869
multiple-include optimization.  As described in the next few
870
paragraphs, these two variables having these values effectively
871
indicates top-of-file.
872
 
873
   When about to return a token that is not part of a directive,
874
`_cpp_lex_token' sets `mi_valid' to `false'.  This enforces the
875
constraint that tokens outside the controlling conditional block
876
invalidate the optimization.
877
 
878
   The `do_if', when appropriate, and `do_ifndef' directive handlers
879
pass the controlling macro to the function `push_conditional'.  cpplib
880
maintains a stack of nested conditional blocks, and after processing
881
every opening conditional this function pushes an `if_stack' structure
882
onto the stack.  In this structure it records the controlling macro for
883
the block, provided there is one and we're at top-of-file (as described
884
above).  If an `#elif' or `#else' directive is encountered, the
885
controlling macro for that block is cleared to `NULL'.  Otherwise, it
886
survives until the `#endif' closing the block, upon which `do_endif'
887
sets `mi_valid' to true and stores the controlling macro in `mi_cmacro'.
888
 
889
   `_cpp_handle_directive' clears `mi_valid' when processing any
890
directive other than an opening conditional and the null directive.
891
With this, and requiring top-of-file to record a controlling macro, and
892
no `#else' or `#elif' for it to survive and be copied to `mi_cmacro' by
893
`do_endif', we have enforced the absence of directives outside the main
894
conditional block for the optimization to be on.
895
 
896
   Note that whilst we are inside the conditional block, `mi_valid' is
897
likely to be reset to `false', but this does not matter since the
898
closing `#endif' restores it to `true' if appropriate.
899
 
900
   Finally, since `_cpp_lex_direct' pops the file off the buffer stack
901
at `EOF' without returning a token, if the `#endif' directive was not
902
followed by any tokens, `mi_valid' is `true' and `_cpp_pop_file_buffer'
903
remembers the controlling macro associated with the file.  Subsequent
904
calls to `stack_include_file' result in no buffer being pushed if the
905
controlling macro is defined, effecting the optimization.
906
 
907
   A quick word on how we handle the
908
 
909
     #if !defined FOO
910
 
911
case.  `_cpp_parse_expr' and `parse_defined' take steps to see whether
912
the three stages `!', `defined-expression' and `end-of-directive' occur
913
in order in a `#if' expression.  If so, they return the guard macro to
914
`do_if' in the variable `mi_ind_cmacro', and otherwise set it to `NULL'.
915
`enter_macro_context' sets `mi_valid' to false, so if a macro was
916
expanded whilst parsing any part of the expression, then the
917
top-of-file test in `push_conditional' fails and the optimization is
918
turned off.
919
 
920

921
File: cppinternals.info,  Node: Files,  Next: Concept Index,  Prev: Guard Macros,  Up: Top
922
 
923
File Handling
924
*************
925
 
926
Fairly obviously, the file handling code of cpplib resides in the file
927
`files.c'.  It takes care of the details of file searching, opening,
928
reading and caching, for both the main source file and all the headers
929
it recursively includes.
930
 
931
   The basic strategy is to minimize the number of system calls.  On
932
many systems, the basic `open ()' and `fstat ()' system calls can be
933
quite expensive.  For every `#include'-d file, we need to try all the
934
directories in the search path until we find a match.  Some projects,
935
such as glibc, pass twenty or thirty include paths on the command line,
936
so this can rapidly become time consuming.
937
 
938
   For a header file we have not encountered before we have little
939
choice but to do this.  However, it is often the case that the same
940
headers are repeatedly included, and in these cases we try to avoid
941
repeating the filesystem queries whilst searching for the correct file.
942
 
943
   For each file we try to open, we store the constructed path in a
944
splay tree.  This path first undergoes simplification by the function
945
`_cpp_simplify_pathname'.  For example, `/usr/include/bits/../foo.h' is
946
simplified to `/usr/include/foo.h' before we enter it in the splay tree
947
and try to `open ()' the file.  CPP will then find subsequent uses of
948
`foo.h', even as `/usr/include/foo.h', in the splay tree and save
949
system calls.
950
 
951
   Further, it is likely the file contents have also been cached,
952
saving a `read ()' system call.  We don't bother caching the contents of
953
header files that are re-inclusion protected, and whose re-inclusion
954
macro is defined when we leave the header file for the first time.  If
955
the host supports it, we try to map suitably large files into memory,
956
rather than reading them in directly.
957
 
958
   The include paths are internally stored on a null-terminated
959
singly-linked list, starting with the `"header.h"' directory search
960
chain, which then links into the `' directory chain.
961
 
962
   Files included with the `' syntax start the lookup directly
963
in the second half of this chain.  However, files included with the
964
`"foo.h"' syntax start at the beginning of the chain, but with one
965
extra directory prepended.  This is the directory of the current file;
966
the one containing the `#include' directive.  Prepending this directory
967
on a per-file basis is handled by the function `search_from'.
968
 
969
   Note that a header included with a directory component, such as
970
`#include "mydir/foo.h"' and opened as
971
`/usr/local/include/mydir/foo.h', will have the complete path minus the
972
basename `foo.h' as the current directory.
973
 
974
   Enough information is stored in the splay tree that CPP can
975
immediately tell whether it can skip the header file because of the
976
multiple include optimization, whether the file didn't exist or
977
couldn't be opened for some reason, or whether the header was flagged
978
not to be re-used, as it is with the obsolete `#import' directive.
979
 
980
   For the benefit of MS-DOS filesystems with an 8.3 filename
981
limitation, CPP offers the ability to treat various include file names
982
as aliases for the real header files with shorter names.  The map from
983
one to the other is found in a special file called `header.gcc', stored
984
in the command line (or system) include directories to which the mapping
985
applies.  This may be higher up the directory tree than the full path to
986
the file minus the base name.
987
 
988

989
File: cppinternals.info,  Node: Concept Index,  Prev: Files,  Up: Top
990
 
991
Concept Index
992
*************
993
 
994
 
995
* Menu:
996
997
* assertions:                            Hash Nodes.          (line   6)
998
* controlling macros:                    Guard Macros.        (line   6)
999
* escaped newlines:                      Lexer.               (line   6)
1000
* files:                                 Files.               (line   6)
1001
* guard macros:                          Guard Macros.        (line   6)
1002
* hash table:                            Hash Nodes.          (line   6)
1003
* header files:                          Conventions.         (line   6)
1004
* identifiers:                           Hash Nodes.          (line   6)
1005
* interface:                             Conventions.         (line   6)
1006
* lexer:                                 Lexer.               (line   6)
1007
* line numbers:                          Line Numbering.      (line   6)
1008
* macro expansion:                       Macro Expansion.     (line   6)
1009
* macro representation (internal):       Macro Expansion.     (line  19)
1010
* macros:                                Hash Nodes.          (line   6)
1011
* multiple-include optimization:         Guard Macros.        (line   6)
1012
* named operators:                       Hash Nodes.          (line   6)
1013
* newlines:                              Lexer.               (line   6)
1014
* paste avoidance:                       Token Spacing.       (line   6)
1015
 
1016
 
1017
* token spacing:                         Token Spacing.       (line   6)
1018
1019
1020

1021
Tag Table:
1022
Node: Top986
1023
Node: Conventions2671
1024
Node: Lexer3613
1025
Ref: Invalid identifiers11526
1026
Ref: Lexing a line13475
1027
Node: Hash Nodes18248
1028
Node: Macro Expansion21127
1029
Node: Token Spacing30074
1030
Node: Line Numbering35934
1031
Node: Guard Macros40019
1032
Node: Files44810

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.