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