This file is indexed.

/usr/share/doc/gcc-4.4-base/cppinternals.html is in cpp-4.4-doc 4.4.7-1ubuntu2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
<html lang="en">
<head>
<title>The GNU C Preprocessor Internals</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="The GNU C Preprocessor Internals">
<meta name="generator" content="makeinfo 4.13">
<link title="Top" rel="top" href="#Top">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
  pre.display { font-family:inherit }
  pre.format  { font-family:inherit }
  pre.smalldisplay { font-family:inherit; font-size:smaller }
  pre.smallformat  { font-family:inherit; font-size:smaller }
  pre.smallexample { font-size:smaller }
  pre.smalllisp    { font-size:smaller }
  span.sc    { font-variant:small-caps }
  span.roman { font-family:serif; font-weight:normal; } 
  span.sansserif { font-family:sans-serif; font-weight:normal; } 
--></style>
</head>
<body>
<h1 class="settitle">The GNU C Preprocessor Internals</h1>
<div class="contents">
<h2>Table of Contents</h2>
<ul>
<li><a name="toc_Top" href="#Top">The GNU C Preprocessor Internals</a>
<li><a name="toc_Top" href="#Top">1 Cpplib&mdash;the GNU C Preprocessor</a>
<li><a name="toc_Conventions" href="#Conventions">Conventions</a>
<li><a name="toc_Lexer" href="#Lexer">The Lexer</a>
<ul>
<li><a href="#Lexer">Overview</a>
<li><a href="#Lexer">Lexing a token</a>
<li><a href="#Lexer">Lexing a line</a>
</li></ul>
<li><a name="toc_Hash-Nodes" href="#Hash-Nodes">Hash Nodes</a>
<li><a name="toc_Macro-Expansion" href="#Macro-Expansion">Macro Expansion Algorithm</a>
<ul>
<li><a href="#Macro-Expansion">Internal representation of macros</a>
<li><a href="#Macro-Expansion">Macro expansion overview</a>
<li><a href="#Macro-Expansion">Scanning the replacement list for macros to expand</a>
<li><a href="#Macro-Expansion">Looking for a function-like macro's opening parenthesis</a>
<li><a href="#Macro-Expansion">Marking tokens ineligible for future expansion</a>
</li></ul>
<li><a name="toc_Token-Spacing" href="#Token-Spacing">Token Spacing</a>
<li><a name="toc_Line-Numbering" href="#Line-Numbering">Line numbering</a>
<ul>
<li><a href="#Line-Numbering">Just which line number anyway?</a>
<li><a href="#Line-Numbering">Representation of line numbers</a>
</li></ul>
<li><a name="toc_Guard-Macros" href="#Guard-Macros">The Multiple-Include Optimization</a>
<li><a name="toc_Files" href="#Files">File Handling</a>
<li><a name="toc_Concept-Index" href="#Concept-Index">Concept Index</a>
</li></ul>
</div>



<div class="node">
<a name="Top"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Conventions">Conventions</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#dir">(dir)</a>

</div>

<h2 class="unnumbered">The GNU C Preprocessor Internals</h2>

<h2 class="chapter">1 Cpplib&mdash;the GNU C Preprocessor</h2>

<p>The GNU C preprocessor is
implemented as a library, <dfn>cpplib</dfn>, so it can be easily shared between
a stand-alone preprocessor, and a preprocessor integrated with the C,
C++ and Objective-C front ends.  It is also available for use by other
programs, though this is not recommended as its exposed interface has
not yet reached a point of reasonable stability.

   <p>The library has been written to be re-entrant, so that it can be used
to preprocess many files simultaneously if necessary.  It has also been
written with the preprocessing token as the fundamental unit; the
preprocessor in previous versions of GCC would operate on text strings
as the fundamental unit.

   <p>This brief manual documents the internals of cpplib, and explains some
of the tricky issues.  It is intended that, along with the comments in
the source code, a reasonably competent C programmer should be able to
figure out what the code is doing, and why things have been implemented
the way they have.

<ul class="menu">
<li><a accesskey="1" href="#Conventions">Conventions</a>:          Conventions used in the code. 
<li><a accesskey="2" href="#Lexer">Lexer</a>:                The combined C, C++ and Objective-C Lexer. 
<li><a accesskey="3" href="#Hash-Nodes">Hash Nodes</a>:           All identifiers are entered into a hash table. 
<li><a accesskey="4" href="#Macro-Expansion">Macro Expansion</a>:      Macro expansion algorithm. 
<li><a accesskey="5" href="#Token-Spacing">Token Spacing</a>:        Spacing and paste avoidance issues. 
<li><a accesskey="6" href="#Line-Numbering">Line Numbering</a>:       Tracking location within files. 
<li><a accesskey="7" href="#Guard-Macros">Guard Macros</a>:         Optimizing header files with guard macros. 
<li><a accesskey="8" href="#Files">Files</a>:                File handling. 
<li><a accesskey="9" href="#Concept-Index">Concept Index</a>:        Index. 
</ul>

<div class="node">
<a name="Conventions"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Lexer">Lexer</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Top">Top</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Conventions</h2>

<p><a name="index-interface-1"></a><a name="index-header-files-2"></a>
cpplib has two interfaces&mdash;one is exposed internally only, and the
other is for both internal and external use.

   <p>The convention is that functions and types that are exposed to multiple
files internally are prefixed with &lsquo;<samp><span class="samp">_cpp_</span></samp>&rsquo;, and are to be found in
the file <samp><span class="file">internal.h</span></samp>.  Functions and types exposed to external
clients are in <samp><span class="file">cpplib.h</span></samp>, and prefixed with &lsquo;<samp><span class="samp">cpp_</span></samp>&rsquo;.  For
historical reasons this is no longer quite true, but we should strive to
stick to it.

   <p>We are striving to reduce the information exposed in <samp><span class="file">cpplib.h</span></samp> to the
bare minimum necessary, and then to keep it there.  This makes clear
exactly what external clients are entitled to assume, and allows us to
change internals in the future without worrying whether library clients
are perhaps relying on some kind of undocumented implementation-specific
behavior.

<div class="node">
<a name="Lexer"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Hash-Nodes">Hash Nodes</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Conventions">Conventions</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">The Lexer</h2>

<p><a name="index-lexer-3"></a><a name="index-newlines-4"></a><a name="index-escaped-newlines-5"></a>

<h3 class="section">Overview</h3>

<p>The lexer is contained in the file <samp><span class="file">lex.c</span></samp>.  It is a hand-coded
lexer, and not implemented as a state machine.  It can understand C, C++
and Objective-C source code, and has been extended to allow reasonably
successful preprocessing of assembly language.  The lexer does not make
an initial pass to strip out trigraphs and escaped newlines, but handles
them as they are encountered in a single pass of the input file.  It
returns preprocessing tokens individually, not a line at a time.

   <p>It is mostly transparent to users of the library, since the library's
interface for obtaining the next token, <code>cpp_get_token</code>, takes care
of lexing new tokens, handling directives, and expanding macros as
necessary.  However, the lexer does expose some functionality so that
clients of the library can easily spell a given token, such as
<code>cpp_spell_token</code> and <code>cpp_token_len</code>.  These functions are
useful when generating diagnostics, and for emitting the preprocessed
output.

<h3 class="section">Lexing a token</h3>

<p>Lexing of an individual token is handled by <code>_cpp_lex_direct</code> and
its subroutines.  In its current form the code is quite complicated,
with read ahead characters and such-like, since it strives to not step
back in the character stream in preparation for handling non-ASCII file
encodings.  The current plan is to convert any such files to UTF-8
before processing them.  This complexity is therefore unnecessary and
will be removed, so I'll not discuss it further here.

   <p>The job of <code>_cpp_lex_direct</code> is simply to lex a token.  It is not
responsible for issues like directive handling, returning lookahead
tokens directly, multiple-include optimization, or conditional block
skipping.  It necessarily has a minor r&ocirc;le to play in memory
management of lexed lines.  I discuss these issues in a separate section
(see <a href="#Lexing-a-line">Lexing a line</a>).

   <p>The lexer places the token it lexes into storage pointed to by the
variable <code>cur_token</code>, and then increments it.  This variable is
important for correct diagnostic positioning.  Unless a specific line
and column are passed to the diagnostic routines, they will examine the
<code>line</code> and <code>col</code> values of the token just before the location
that <code>cur_token</code> points to, and use that location to report the
diagnostic.

   <p>The lexer does not consider whitespace to be a token in its own right. 
If whitespace (other than a new line) precedes a token, it sets the
<code>PREV_WHITE</code> bit in the token's flags.  Each token has its
<code>line</code> and <code>col</code> variables set to the line and column of the
first character of the token.  This line number is the line number in
the translation unit, and can be converted to a source (file, line) pair
using the line map code.

   <p>The first token on a logical, i.e. unescaped, line has the flag
<code>BOL</code> set for beginning-of-line.  This flag is intended for
internal use, both to distinguish a &lsquo;<samp><span class="samp">#</span></samp>&rsquo; that begins a directive
from one that doesn't, and to generate a call-back to clients that want
to be notified about the start of every non-directive line with tokens
on it.  Clients cannot reliably determine this for themselves: the first
token might be a macro, and the tokens of a macro expansion do not have
the <code>BOL</code> flag set.  The macro expansion may even be empty, and the
next token on the line certainly won't have the <code>BOL</code> flag set.

   <p>New lines are treated specially; exactly how the lexer handles them is
context-dependent.  The C standard mandates that directives are
terminated by the first unescaped newline character, even if it appears
in the middle of a macro expansion.  Therefore, if the state variable
<code>in_directive</code> is set, the lexer returns a <code>CPP_EOF</code> token,
which is normally used to indicate end-of-file, to indicate
end-of-directive.  In a directive a <code>CPP_EOF</code> token never means
end-of-file.  Conveniently, if the caller was <code>collect_args</code>, it
already handles <code>CPP_EOF</code> as if it were end-of-file, and reports an
error about an unterminated macro argument list.

   <p>The C standard also specifies that a new line in the middle of the
arguments to a macro is treated as whitespace.  This white space is
important in case the macro argument is stringified.  The state variable
<code>parsing_args</code> is nonzero when the preprocessor is collecting the
arguments to a macro call.  It is set to 1 when looking for the opening
parenthesis to a function-like macro, and 2 when collecting the actual
arguments up to the closing parenthesis, since these two cases need to
be distinguished sometimes.  One such time is here: the lexer sets the
<code>PREV_WHITE</code> flag of a token if it meets a new line when
<code>parsing_args</code> is set to 2.  It doesn't set it if it meets a new
line when <code>parsing_args</code> is 1, since then code like

<pre class="smallexample">     #define foo() bar
     foo
     baz
</pre>
   <p class="noindent">would be output with an erroneous space before &lsquo;<samp><span class="samp">baz</span></samp>&rsquo;:

<pre class="smallexample">     foo
      baz
</pre>
   <p>This is a good example of the subtlety of getting token spacing correct
in the preprocessor; there are plenty of tests in the testsuite for
corner cases like this.

   <p>The lexer is written to treat each of &lsquo;<samp><span class="samp">\r</span></samp>&rsquo;, &lsquo;<samp><span class="samp">\n</span></samp>&rsquo;, &lsquo;<samp><span class="samp">\r\n</span></samp>&rsquo;
and &lsquo;<samp><span class="samp">\n\r</span></samp>&rsquo; as a single new line indicator.  This allows it to
transparently preprocess MS-DOS, Macintosh and Unix files without their
needing to pass through a special filter beforehand.

   <p>We also decided to treat a backslash, either &lsquo;<samp><span class="samp">\</span></samp>&rsquo; or the trigraph
&lsquo;<samp><span class="samp">??/</span></samp>&rsquo;, separated from one of the above newline indicators by
non-comment whitespace only, as intending to escape the newline.  It
tends to be a typing mistake, and cannot reasonably be mistaken for
anything else in any of the C-family grammars.  Since handling it this
way is not strictly conforming to the ISO standard, the library issues a
warning wherever it encounters it.

   <p>Handling newlines like this is made simpler by doing it in one place
only.  The function <code>handle_newline</code> takes care of all newline
characters, and <code>skip_escaped_newlines</code> takes care of arbitrarily
long sequences of escaped newlines, deferring to <code>handle_newline</code>
to handle the newlines themselves.

   <p>The most painful aspect of lexing ISO-standard C and C++ is handling
trigraphs and backlash-escaped newlines.  Trigraphs are processed before
any interpretation of the meaning of a character is made, and unfortunately
there is a trigraph representation for a backslash, so it is possible for
the trigraph &lsquo;<samp><span class="samp">??/</span></samp>&rsquo; to introduce an escaped newline.

   <p>Escaped newlines are tedious because theoretically they can occur
anywhere&mdash;between the &lsquo;<samp><span class="samp">+</span></samp>&rsquo; and &lsquo;<samp><span class="samp">=</span></samp>&rsquo; of the &lsquo;<samp><span class="samp">+=</span></samp>&rsquo; token,
within the characters of an identifier, and even between the &lsquo;<samp><span class="samp">*</span></samp>&rsquo;
and &lsquo;<samp><span class="samp">/</span></samp>&rsquo; that terminates a comment.  Moreover, you cannot be sure
there is just one&mdash;there might be an arbitrarily long sequence of them.

   <p>So, for example, the routine that lexes a number, <code>parse_number</code>,
cannot assume that it can scan forwards until the first non-number
character and be done with it, because this could be the &lsquo;<samp><span class="samp">\</span></samp>&rsquo;
introducing an escaped newline, or the &lsquo;<samp><span class="samp">?</span></samp>&rsquo; introducing the trigraph
sequence that represents the &lsquo;<samp><span class="samp">\</span></samp>&rsquo; of an escaped newline.  If it
encounters a &lsquo;<samp><span class="samp">?</span></samp>&rsquo; or &lsquo;<samp><span class="samp">\</span></samp>&rsquo;, it calls <code>skip_escaped_newlines</code>
to skip over any potential escaped newlines before checking whether the
number has been finished.

   <p>Similarly code in the main body of <code>_cpp_lex_direct</code> cannot simply
check for a &lsquo;<samp><span class="samp">=</span></samp>&rsquo; after a &lsquo;<samp><span class="samp">+</span></samp>&rsquo; character to determine whether it
has a &lsquo;<samp><span class="samp">+=</span></samp>&rsquo; token; it needs to be prepared for an escaped newline of
some sort.  Such cases use the function <code>get_effective_char</code>, which
returns the first character after any intervening escaped newlines.

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

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

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

   <p>Interpretation of some character sequences depends upon whether we are
lexing C, C++ or Objective-C, and on the revision of the standard in
force.  For example, &lsquo;<samp><span class="samp">::</span></samp>&rsquo; is a single token in C++, but in C it is
two separate &lsquo;<samp><span class="samp">:</span></samp>&rsquo; tokens and almost certainly a syntax error.  Such
cases are handled by <code>_cpp_lex_direct</code> based upon command-line
flags stored in the <code>cpp_options</code> structure.

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

   <p><a name="Lexing-a-line"></a>

<h3 class="section">Lexing a line</h3>

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

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

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

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

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

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

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

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

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

<div class="node">
<a name="Hash-Nodes"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Macro-Expansion">Macro Expansion</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Lexer">Lexer</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Hash Nodes</h2>

<p><a name="index-hash-table-7"></a><a name="index-identifiers-8"></a><a name="index-macros-9"></a><a name="index-assertions-10"></a><a name="index-named-operators-11"></a>
When cpplib encounters an &ldquo;identifier&rdquo;, it generates a hash code for
it and stores it in the hash table.  By &ldquo;identifier&rdquo; we mean tokens
with type <code>CPP_NAME</code>; this includes identifiers in the usual C
sense, as well as keywords, directive names, macro names and so on.  For
example, all of <code>pragma</code>, <code>int</code>, <code>foo</code> and
<code>__GNUC__</code> are identifiers and hashed when lexed.

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

     <ul>
<li>Macros

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

     <li>Assertions

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

     <li>Void

     <p>Everything else falls into this category&mdash;an identifier that is not
currently a macro, or a macro that has since been undefined with
<code>#undef</code>.

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

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

<div class="node">
<a name="Macro-Expansion"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Token-Spacing">Token Spacing</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Hash-Nodes">Hash Nodes</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Macro Expansion Algorithm</h2>

<p><a name="index-macro-expansion-12"></a>
Macro expansion is a tricky operation, fraught with nasty corner cases
and situations that render what you thought was a nifty way to
optimize the preprocessor's expansion algorithm wrong in quite subtle
ways.

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

<h3 class="section">Internal representation of macros</h3>

<p><a name="index-macro-representation-_0028internal_0029-13"></a>
The preprocessor stores macro expansions in tokenized form.  This
saves repeated lexing passes during expansion, at the cost of a small
increase in memory consumption on average.  The tokens are stored
contiguously in memory, so a pointer to the first one and a token
count is all you need to get the replacement list of a macro.

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

<h3 class="section">Macro expansion overview</h3>

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

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

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

   <p><code>enter_macro_context</code> also handles special macros like
<code>__LINE__</code>.  Although these macros expand to a single token which
cannot contain any further macros, for reasons of token spacing
(see <a href="#Token-Spacing">Token Spacing</a>) and simplicity of implementation, cpplib
handles these special macros by pushing a context containing just that
one token.

   <p>The final thing that <code>enter_macro_context</code> does before returning
is to mark the macro disabled for expansion (except for special macros
like <code>__TIME__</code>).  The macro is re-enabled when its context is
later popped from the context stack, as described above.  This strict
ordering ensures that a macro is disabled whilst its expansion is
being scanned, but that it is <em>not</em> disabled whilst any arguments
to it are being expanded.

<h3 class="section">Scanning the replacement list for macros to expand</h3>

<p>The C standard states that, after any parameters have been replaced
with their possibly-expanded arguments, the replacement list is
scanned for nested macros.  Further, any identifiers in the
replacement list that are not expanded during this scan are never
again eligible for expansion in the future, if the reason they were
not expanded is that the macro in question was disabled.

   <p>Clearly this latter condition can only apply to tokens resulting from
argument pre-expansion.  Other tokens never have an opportunity to be
re-tested for expansion.  It is possible for identifiers that are
function-like macros to not expand initially but to expand during a
later scan.  This occurs when the identifier is the last token of an
argument (and therefore originally followed by a comma or a closing
parenthesis in its macro's argument list), and when it replaces its
parameter in the macro's replacement list, the subsequent token
happens to be an opening parenthesis (itself possibly the first token
of an argument).

   <p>It is important to note that when cpplib reads the last token of a
given context, that context still remains on the stack.  Only when
looking for the <em>next</em> token do we pop it off the stack and drop
to a lower context.  This makes backing up by one token easy, but more
importantly ensures that the macro corresponding to the current
context is still disabled when we are considering the last token of
its replacement list for expansion (or indeed expanding it).  As an
example, which illustrates many of the points above, consider

<pre class="smallexample">     #define foo(x) bar x
     foo(foo) (2)
</pre>
   <p class="noindent">which fully expands to &lsquo;<samp><span class="samp">bar foo (2)</span></samp>&rsquo;.  During pre-expansion
of the argument, &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; does not expand even though the macro is
enabled, since it has no following parenthesis [pre-expansion of an
argument only uses tokens from that argument; it cannot take tokens
from whatever follows the macro invocation].  This still leaves the
argument token &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; eligible for future expansion.  Then, when
re-scanning after argument replacement, the token &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; is
rejected for expansion, and marked ineligible for future expansion,
since the macro is now disabled.  It is disabled because the
replacement list &lsquo;<samp><span class="samp">bar foo</span></samp>&rsquo; of the macro is still on the context
stack.

   <p>If instead the algorithm looked for an opening parenthesis first and
then tested whether the macro were disabled it would be subtly wrong. 
In the example above, the replacement list of &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; would be
popped in the process of finding the parenthesis, re-enabling
&lsquo;<samp><span class="samp">foo</span></samp>&rsquo; and expanding it a second time.

<h3 class="section">Looking for a function-like macro's opening parenthesis</h3>

<p>Function-like macros only expand when immediately followed by a
parenthesis.  To do this cpplib needs to temporarily disable macros
and read the next token.  Unfortunately, because of spacing issues
(see <a href="#Token-Spacing">Token Spacing</a>), there can be fake padding tokens in-between,
and if the next real token is not a parenthesis cpplib needs to be
able to back up that one token as well as retain the information in
any intervening padding tokens.

   <p>Backing up more than one token when macros are involved is not
permitted by cpplib, because in general it might involve issues like
restoring popped contexts onto the context stack, which are too hard. 
Instead, searching for the parenthesis is handled by a special
function, <code>funlike_invocation_p</code>, which remembers padding
information as it reads tokens.  If the next real token is not an
opening parenthesis, it backs up that one token, and then pushes an
extra context just containing the padding information if necessary.

<h3 class="section">Marking tokens ineligible for future expansion</h3>

<p>As discussed above, cpplib needs a way of marking tokens as
unexpandable.  Since the tokens cpplib handles are read-only once they
have been lexed, it instead makes a copy of the token and adds the
flag <code>NO_EXPAND</code> to the copy.

   <p>For efficiency and to simplify memory management by avoiding having to
remember to free these tokens, they are allocated as temporary tokens
from the lexer's current token run (see <a href="#Lexing-a-line">Lexing a line</a>) using the
function <code>_cpp_temp_token</code>.  The tokens are then re-used once the
current line of tokens has been read in.

   <p>This might sound unsafe.  However, tokens runs are not re-used at the
end of a line if it happens to be in the middle of a macro argument
list, and cpplib only wants to back-up more than one lexer token in
situations where no macro expansion is involved, so the optimization
is safe.

<div class="node">
<a name="Token-Spacing"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Line-Numbering">Line Numbering</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Macro-Expansion">Macro Expansion</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Token Spacing</h2>

<p><a name="index-paste-avoidance-14"></a><a name="index-spacing-15"></a><a name="index-token-spacing-16"></a>
First, consider an issue that only concerns the stand-alone
preprocessor: there needs to be a guarantee that re-reading its preprocessed
output results in an identical token stream.  Without taking special
measures, this might not be the case because of macro substitution. 
For example:

<pre class="smallexample">     #define PLUS +
     #define EMPTY
     #define f(x) =x=
     +PLUS -EMPTY- PLUS+ f(=)
             ==&gt; + + - - + + = = =
     <em>not</em>
             ==&gt; ++ -- ++ ===
</pre>
   <p>One solution would be to simply insert a space between all adjacent
tokens.  However, we would like to keep space insertion to a minimum,
both for aesthetic reasons and because it causes problems for people who
still try to abuse the preprocessor for things like Fortran source and
Makefiles.

   <p>For now, just notice that when tokens are added (or removed, as shown by
the <code>EMPTY</code> example) from the original lexed token stream, we need
to check for accidental token pasting.  We call this <dfn>paste
avoidance</dfn>.  Token addition and removal can only occur because of macro
expansion, but accidental pasting can occur in many places: both before
and after each macro replacement, each argument replacement, and
additionally each token created by the &lsquo;<samp><span class="samp">#</span></samp>&rsquo; and &lsquo;<samp><span class="samp">##</span></samp>&rsquo; operators.

   <p>Look at how the preprocessor gets whitespace output correct
normally.  The <code>cpp_token</code> structure contains a flags byte, and one
of those flags is <code>PREV_WHITE</code>.  This is flagged by the lexer, and
indicates that the token was preceded by whitespace of some form other
than a new line.  The stand-alone preprocessor can use this flag to
decide whether to insert a space between tokens in the output.

   <p>Now consider the result of the following macro expansion:

<pre class="smallexample">     #define add(x, y, z) x + y +z;
     sum = add (1,2, 3);
             ==&gt; sum = 1 + 2 +3;
</pre>
   <p>The interesting thing here is that the tokens &lsquo;<samp><span class="samp">1</span></samp>&rsquo; and &lsquo;<samp><span class="samp">2</span></samp>&rsquo; are
output with a preceding space, and &lsquo;<samp><span class="samp">3</span></samp>&rsquo; is output without a
preceding space, but when lexed none of these tokens had that property. 
Careful consideration reveals that &lsquo;<samp><span class="samp">1</span></samp>&rsquo; gets its preceding
whitespace from the space preceding &lsquo;<samp><span class="samp">add</span></samp>&rsquo; in the macro invocation,
<em>not</em> replacement list.  &lsquo;<samp><span class="samp">2</span></samp>&rsquo; gets its whitespace from the
space preceding the parameter &lsquo;<samp><span class="samp">y</span></samp>&rsquo; in the macro replacement list,
and &lsquo;<samp><span class="samp">3</span></samp>&rsquo; has no preceding space because parameter &lsquo;<samp><span class="samp">z</span></samp>&rsquo; has none
in the replacement list.

   <p>Once lexed, tokens are effectively fixed and cannot be altered, since
pointers to them might be held in many places, in particular by
in-progress macro expansions.  So instead of modifying the two tokens
above, the preprocessor inserts a special token, which I call a
<dfn>padding token</dfn>, into the token stream to indicate that spacing of
the subsequent token is special.  The preprocessor inserts padding
tokens in front of every macro expansion and expanded macro argument. 
These point to a <dfn>source token</dfn> from which the subsequent real token
should inherit its spacing.  In the above example, the source tokens are
&lsquo;<samp><span class="samp">add</span></samp>&rsquo; in the macro invocation, and &lsquo;<samp><span class="samp">y</span></samp>&rsquo; and &lsquo;<samp><span class="samp">z</span></samp>&rsquo; in the
macro replacement list, respectively.

   <p>It is quite easy to get multiple padding tokens in a row, for example if
a macro's first replacement token expands straight into another macro.

<pre class="smallexample">     #define foo bar
     #define bar baz
     [foo]
             ==&gt; [baz]
</pre>
   <p>Here, two padding tokens are generated with sources the &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; token
between the brackets, and the &lsquo;<samp><span class="samp">bar</span></samp>&rsquo; token from foo's replacement
list, respectively.  Clearly the first padding token is the one to
use, so the output code should contain a rule that the first
padding token in a sequence is the one that matters.

   <p>But what if a macro expansion is left?  Adjusting the above
example slightly:

<pre class="smallexample">     #define foo bar
     #define bar EMPTY baz
     #define EMPTY
     [foo] EMPTY;
             ==&gt; [ baz] ;
</pre>
   <p>As shown, now there should be a space before &lsquo;<samp><span class="samp">baz</span></samp>&rsquo; and the
semicolon in the output.

   <p>The rules we decided above fail for &lsquo;<samp><span class="samp">baz</span></samp>&rsquo;: we generate three
padding tokens, one per macro invocation, before the token &lsquo;<samp><span class="samp">baz</span></samp>&rsquo;. 
We would then have it take its spacing from the first of these, which
carries source token &lsquo;<samp><span class="samp">foo</span></samp>&rsquo; with no leading space.

   <p>It is vital that cpplib get spacing correct in these examples since any
of these macro expansions could be stringified, where spacing matters.

   <p>So, this demonstrates that not just entering macro and argument
expansions, but leaving them requires special handling too.  I made
cpplib insert a padding token with a <code>NULL</code> source token when
leaving macro expansions, as well as after each replaced argument in a
macro's replacement list.  It also inserts appropriate padding tokens on
either side of tokens created by the &lsquo;<samp><span class="samp">#</span></samp>&rsquo; and &lsquo;<samp><span class="samp">##</span></samp>&rsquo; operators. 
I expanded the rule so that, if we see a padding token with a
<code>NULL</code> source token, <em>and</em> that source token has no leading
space, then we behave as if we have seen no padding tokens at all.  A
quick check shows this rule will then get the above example correct as
well.

   <p>Now a relationship with paste avoidance is apparent: we have to be
careful about paste avoidance in exactly the same locations we have
padding tokens in order to get white space correct.  This makes
implementation of paste avoidance easy: wherever the stand-alone
preprocessor is fixing up spacing because of padding tokens, and it
turns out that no space is needed, it has to take the extra step to
check that a space is not needed after all to avoid an accidental paste. 
The function <code>cpp_avoid_paste</code> advises whether a space is required
between two consecutive tokens.  To avoid excessive spacing, it tries
hard to only require a space if one is likely to be necessary, but for
reasons of efficiency it is slightly conservative and might recommend a
space where one is not strictly needed.

<div class="node">
<a name="Line-Numbering"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Guard-Macros">Guard Macros</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Token-Spacing">Token Spacing</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Line numbering</h2>

<p><a name="index-line-numbers-17"></a>

<h3 class="section">Just which line number anyway?</h3>

<p>There are three reasonable requirements a cpplib client might have for
the line number of a token passed to it:

     <ul>
<li>The source line it was lexed on. 
<li>The line it is output on.  This can be different to the line it was
lexed on if, for example, there are intervening escaped newlines or
C-style comments.  For example:

     <pre class="smallexample">          foo /* <span class="roman">A long
          comment</span> */ bar \
          baz
          &rArr;
          foo bar baz
</pre>
     <li>If the token results from a macro expansion, the line of the macro name,
or possibly the line of the closing parenthesis in the case of
function-like macro expansion. 
</ul>

   <p>The <code>cpp_token</code> structure contains <code>line</code> and <code>col</code>
members.  The lexer fills these in with the line and column of the first
character of the token.  Consequently, but maybe unexpectedly, a token
from the replacement list of a macro expansion carries the location of
the token within the <code>#define</code> directive, because cpplib expands a
macro by returning pointers to the tokens in its replacement list.  The
current implementation of cpplib assigns tokens created from built-in
macros and the &lsquo;<samp><span class="samp">#</span></samp>&rsquo; and &lsquo;<samp><span class="samp">##</span></samp>&rsquo; operators the location of the most
recently lexed token.  This is a because they are allocated from the
lexer's token runs, and because of the way the diagnostic routines infer
the appropriate location to report.

   <p>The diagnostic routines in cpplib display the location of the most
recently <em>lexed</em> token, unless they are passed a specific line and
column to report.  For diagnostics regarding tokens that arise from
macro expansions, it might also be helpful for the user to see the
original location in the macro definition that the token came from. 
Since that is exactly the information each token carries, such an
enhancement could be made relatively easily in future.

   <p>The stand-alone preprocessor faces a similar problem when determining
the correct line to output the token on: the position attached to a
token is fairly useless if the token came from a macro expansion.  All
tokens on a logical line should be output on its first physical line, so
the token's reported location is also wrong if it is part of a physical
line other than the first.

   <p>To solve these issues, cpplib provides a callback that is generated
whenever it lexes a preprocessing token that starts a new logical line
other than a directive.  It passes this token (which may be a
<code>CPP_EOF</code> token indicating the end of the translation unit) to the
callback routine, which can then use the line and column of this token
to produce correct output.

<h3 class="section">Representation of line numbers</h3>

<p>As mentioned above, cpplib stores with each token the line number that
it was lexed on.  In fact, this number is not the number of the line in
the source file, but instead bears more resemblance to the number of the
line in the translation unit.

   <p>The preprocessor maintains a monotonic increasing line count, which is
incremented at every new line character (and also at the end of any
buffer that does not end in a new line).  Since a line number of zero is
useful to indicate certain special states and conditions, this variable
starts counting from one.

   <p>This variable therefore uniquely enumerates each line in the translation
unit.  With some simple infrastructure, it is straight forward to map
from this to the original source file and line number pair, saving space
whenever line number information needs to be saved.  The code the
implements this mapping lies in the files <samp><span class="file">line-map.c</span></samp> and
<samp><span class="file">line-map.h</span></samp>.

   <p>Command-line macros and assertions are implemented by pushing a buffer
containing the right hand side of an equivalent <code>#define</code> or
<code>#assert</code> directive.  Some built-in macros are handled similarly. 
Since these are all processed before the first line of the main input
file, it will typically have an assigned line closer to twenty than to
one.

<div class="node">
<a name="Guard-Macros"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Files">Files</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Line-Numbering">Line Numbering</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">The Multiple-Include Optimization</h2>

<p><a name="index-guard-macros-18"></a><a name="index-controlling-macros-19"></a><a name="index-multiple_002dinclude-optimization-20"></a>
Header files are often of the form

<pre class="smallexample">     #ifndef FOO
     #define FOO
     ...
     #endif
</pre>
   <p class="noindent">to prevent the compiler from processing them more than once.  The
preprocessor notices such header files, so that if the header file
appears in a subsequent <code>#include</code> directive and <code>FOO</code> is
defined, then it is ignored and it doesn't preprocess or even re-open
the file a second time.  This is referred to as the <dfn>multiple
include optimization</dfn>.

   <p>Under what circumstances is such an optimization valid?  If the file
were included a second time, it can only be optimized away if that
inclusion would result in no tokens to return, and no relevant
directives to process.  Therefore the current implementation imposes
requirements and makes some allowances as follows:

     <ol type=1 start=1>
<li>There must be no tokens outside the controlling <code>#if</code>-<code>#endif</code>
pair, but whitespace and comments are permitted.

     <li>There must be no directives outside the controlling directive pair, but
the <dfn>null directive</dfn> (a line containing nothing other than a single
&lsquo;<samp><span class="samp">#</span></samp>&rsquo; and possibly whitespace) is permitted.

     <li>The opening directive must be of the form

     <pre class="smallexample">          #ifndef FOO
</pre>
     <p>or

     <pre class="smallexample">          #if !defined FOO     [equivalently, #if !defined(FOO)]
</pre>
     <li>In the second form above, the tokens forming the <code>#if</code> expression
must have come directly from the source file&mdash;no macro expansion must
have been involved.  This is because macro definitions can change, and
tracking whether or not a relevant change has been made is not worth the
implementation cost.

     <li>There can be no <code>#else</code> or <code>#elif</code> directives at the outer
conditional block level, because they would probably contain something
of interest to a subsequent pass.
        </ol>

   <p>First, when pushing a new file on the buffer stack,
<code>_stack_include_file</code> sets the controlling macro <code>mi_cmacro</code> to
<code>NULL</code>, and sets <code>mi_valid</code> to <code>true</code>.  This indicates
that the preprocessor has not yet encountered anything that would
invalidate the multiple-include optimization.  As described in the next
few paragraphs, these two variables having these values effectively
indicates top-of-file.

   <p>When about to return a token that is not part of a directive,
<code>_cpp_lex_token</code> sets <code>mi_valid</code> to <code>false</code>.  This
enforces the constraint that tokens outside the controlling conditional
block invalidate the optimization.

   <p>The <code>do_if</code>, when appropriate, and <code>do_ifndef</code> directive
handlers pass the controlling macro to the function
<code>push_conditional</code>.  cpplib maintains a stack of nested conditional
blocks, and after processing every opening conditional this function
pushes an <code>if_stack</code> structure onto the stack.  In this structure
it records the controlling macro for the block, provided there is one
and we're at top-of-file (as described above).  If an <code>#elif</code> or
<code>#else</code> directive is encountered, the controlling macro for that
block is cleared to <code>NULL</code>.  Otherwise, it survives until the
<code>#endif</code> closing the block, upon which <code>do_endif</code> sets
<code>mi_valid</code> to true and stores the controlling macro in
<code>mi_cmacro</code>.

   <p><code>_cpp_handle_directive</code> clears <code>mi_valid</code> when processing any
directive other than an opening conditional and the null directive. 
With this, and requiring top-of-file to record a controlling macro, and
no <code>#else</code> or <code>#elif</code> for it to survive and be copied to
<code>mi_cmacro</code> by <code>do_endif</code>, we have enforced the absence of
directives outside the main conditional block for the optimization to be
on.

   <p>Note that whilst we are inside the conditional block, <code>mi_valid</code> is
likely to be reset to <code>false</code>, but this does not matter since
the closing <code>#endif</code> restores it to <code>true</code> if appropriate.

   <p>Finally, since <code>_cpp_lex_direct</code> pops the file off the buffer stack
at <code>EOF</code> without returning a token, if the <code>#endif</code> directive
was not followed by any tokens, <code>mi_valid</code> is <code>true</code> and
<code>_cpp_pop_file_buffer</code> remembers the controlling macro associated
with the file.  Subsequent calls to <code>stack_include_file</code> result in
no buffer being pushed if the controlling macro is defined, effecting
the optimization.

   <p>A quick word on how we handle the

<pre class="smallexample">     #if !defined FOO
</pre>
   <p class="noindent">case.  <code>_cpp_parse_expr</code> and <code>parse_defined</code> take steps to see
whether the three stages &lsquo;<samp><span class="samp">!</span></samp>&rsquo;, &lsquo;<samp><span class="samp">defined-expression</span></samp>&rsquo; and
&lsquo;<samp><span class="samp">end-of-directive</span></samp>&rsquo; occur in order in a <code>#if</code> expression.  If
so, they return the guard macro to <code>do_if</code> in the variable
<code>mi_ind_cmacro</code>, and otherwise set it to <code>NULL</code>. 
<code>enter_macro_context</code> sets <code>mi_valid</code> to false, so if a macro
was expanded whilst parsing any part of the expression, then the
top-of-file test in <code>push_conditional</code> fails and the optimization
is turned off.

<div class="node">
<a name="Files"></a>
<p><hr>
Next:&nbsp;<a rel="next" accesskey="n" href="#Concept-Index">Concept Index</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Guard-Macros">Guard Macros</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">File Handling</h2>

<p><a name="index-files-21"></a>
Fairly obviously, the file handling code of cpplib resides in the file
<samp><span class="file">files.c</span></samp>.  It takes care of the details of file searching,
opening, reading and caching, for both the main source file and all the
headers it recursively includes.

   <p>The basic strategy is to minimize the number of system calls.  On many
systems, the basic <code>open ()</code> and <code>fstat ()</code> system calls can
be quite expensive.  For every <code>#include</code>-d file, we need to try
all the directories in the search path until we find a match.  Some
projects, such as glibc, pass twenty or thirty include paths on the
command line, so this can rapidly become time consuming.

   <p>For a header file we have not encountered before we have little choice
but to do this.  However, it is often the case that the same headers are
repeatedly included, and in these cases we try to avoid repeating the
filesystem queries whilst searching for the correct file.

   <p>For each file we try to open, we store the constructed path in a splay
tree.  This path first undergoes simplification by the function
<code>_cpp_simplify_pathname</code>.  For example,
<samp><span class="file">/usr/include/bits/../foo.h</span></samp> is simplified to
<samp><span class="file">/usr/include/foo.h</span></samp> before we enter it in the splay tree and try
to <code>open ()</code> the file.  CPP will then find subsequent uses of
<samp><span class="file">foo.h</span></samp>, even as <samp><span class="file">/usr/include/foo.h</span></samp>, in the splay tree and
save system calls.

   <p>Further, it is likely the file contents have also been cached, saving a
<code>read ()</code> system call.  We don't bother caching the contents of
header files that are re-inclusion protected, and whose re-inclusion
macro is defined when we leave the header file for the first time.  If
the host supports it, we try to map suitably large files into memory,
rather than reading them in directly.

   <p>The include paths are internally stored on a null-terminated
singly-linked list, starting with the <code>"header.h"</code> directory search
chain, which then links into the <code>&lt;header.h&gt;</code> directory chain.

   <p>Files included with the <code>&lt;foo.h&gt;</code> syntax start the lookup directly
in the second half of this chain.  However, files included with the
<code>"foo.h"</code> syntax start at the beginning of the chain, but with one
extra directory prepended.  This is the directory of the current file;
the one containing the <code>#include</code> directive.  Prepending this
directory on a per-file basis is handled by the function
<code>search_from</code>.

   <p>Note that a header included with a directory component, such as
<code>#include "mydir/foo.h"</code> and opened as
<samp><span class="file">/usr/local/include/mydir/foo.h</span></samp>, will have the complete path minus
the basename &lsquo;<samp><span class="samp">foo.h</span></samp>&rsquo; as the current directory.

   <p>Enough information is stored in the splay tree that CPP can immediately
tell whether it can skip the header file because of the multiple include
optimization, whether the file didn't exist or couldn't be opened for
some reason, or whether the header was flagged not to be re-used, as it
is with the obsolete <code>#import</code> directive.

   <p>For the benefit of MS-DOS filesystems with an 8.3 filename limitation,
CPP offers the ability to treat various include file names as aliases
for the real header files with shorter names.  The map from one to the
other is found in a special file called &lsquo;<samp><span class="samp">header.gcc</span></samp>&rsquo;, stored in the
command line (or system) include directories to which the mapping
applies.  This may be higher up the directory tree than the full path to
the file minus the base name.

<div class="node">
<a name="Concept-Index"></a>
<p><hr>
Previous:&nbsp;<a rel="previous" accesskey="p" href="#Files">Files</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="#Top">Top</a>

</div>

<h2 class="unnumbered">Concept Index</h2>

<ul class="index-cp" compact>
<li><a href="#index-assertions-10">assertions</a>: <a href="#Hash-Nodes">Hash Nodes</a></li>
<li><a href="#index-controlling-macros-19">controlling macros</a>: <a href="#Guard-Macros">Guard Macros</a></li>
<li><a href="#index-escaped-newlines-5">escaped newlines</a>: <a href="#Lexer">Lexer</a></li>
<li><a href="#index-files-21">files</a>: <a href="#Files">Files</a></li>
<li><a href="#index-guard-macros-18">guard macros</a>: <a href="#Guard-Macros">Guard Macros</a></li>
<li><a href="#index-hash-table-7">hash table</a>: <a href="#Hash-Nodes">Hash Nodes</a></li>
<li><a href="#index-header-files-2">header files</a>: <a href="#Conventions">Conventions</a></li>
<li><a href="#index-identifiers-8">identifiers</a>: <a href="#Hash-Nodes">Hash Nodes</a></li>
<li><a href="#index-interface-1">interface</a>: <a href="#Conventions">Conventions</a></li>
<li><a href="#index-lexer-3">lexer</a>: <a href="#Lexer">Lexer</a></li>
<li><a href="#index-line-numbers-17">line numbers</a>: <a href="#Line-Numbering">Line Numbering</a></li>
<li><a href="#index-macro-expansion-12">macro expansion</a>: <a href="#Macro-Expansion">Macro Expansion</a></li>
<li><a href="#index-macro-representation-_0028internal_0029-13">macro representation (internal)</a>: <a href="#Macro-Expansion">Macro Expansion</a></li>
<li><a href="#index-macros-9">macros</a>: <a href="#Hash-Nodes">Hash Nodes</a></li>
<li><a href="#index-multiple_002dinclude-optimization-20">multiple-include optimization</a>: <a href="#Guard-Macros">Guard Macros</a></li>
<li><a href="#index-named-operators-11">named operators</a>: <a href="#Hash-Nodes">Hash Nodes</a></li>
<li><a href="#index-newlines-4">newlines</a>: <a href="#Lexer">Lexer</a></li>
<li><a href="#index-paste-avoidance-14">paste avoidance</a>: <a href="#Token-Spacing">Token Spacing</a></li>
<li><a href="#index-spacing-15">spacing</a>: <a href="#Token-Spacing">Token Spacing</a></li>
<li><a href="#index-token-run-6">token run</a>: <a href="#Lexer">Lexer</a></li>
<li><a href="#index-token-spacing-16">token spacing</a>: <a href="#Token-Spacing">Token Spacing</a></li>
   </ul></body></html>