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