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
|
<html>
<head>
<title>"clang" CFE Internals Manual</title>
<link type="text/css" rel="stylesheet" href="../menu.css" />
<link type="text/css" rel="stylesheet" href="../content.css" />
</head>
<body>
<!--#include virtual="../menu.html.incl"-->
<div id="content">
<h1>"clang" CFE Internals Manual</h1>
<ul>
<li><a href="#intro">Introduction</a></li>
<li><a href="#libsystem">LLVM System and Support Libraries</a></li>
<li><a href="#libbasic">The clang 'Basic' Library</a>
<ul>
<li><a href="#SourceLocation">The SourceLocation and SourceManager
classes</a></li>
</ul>
</li>
<li><a href="#liblex">The Lexer and Preprocessor Library</a>
<ul>
<li><a href="#Token">The Token class</a></li>
<li><a href="#Lexer">The Lexer class</a></li>
<li><a href="#TokenLexer">The TokenLexer class</a></li>
<li><a href="#MultipleIncludeOpt">The MultipleIncludeOpt class</a></li>
</ul>
</li>
<li><a href="#libparse">The Parser Library</a>
<ul>
</ul>
</li>
<li><a href="#libast">The AST Library</a>
<ul>
<li><a href="#Type">The Type class and its subclasses</a></li>
<li><a href="#QualType">The QualType class</a></li>
<li><a href="#CFG">The CFG class</a></li>
</ul>
</li>
</ul>
<!-- ======================================================================= -->
<h2 id="intro">Introduction</h2>
<!-- ======================================================================= -->
<p>This document describes some of the more important APIs and internal design
decisions made in the clang C front-end. The purpose of this document is to
both capture some of this high level information and also describe some of the
design decisions behind it. This is meant for people interested in hacking on
clang, not for end-users. The description below is categorized by
libraries, and does not describe any of the clients of the libraries.</p>
<!-- ======================================================================= -->
<h2 id="libsystem">LLVM System and Support Libraries</h2>
<!-- ======================================================================= -->
<p>The LLVM libsystem library provides the basic clang system abstraction layer,
which is used for file system access. The LLVM libsupport library provides many
underlying libraries and <a
href="http://llvm.org/docs/ProgrammersManual.html">data-structures</a>,
including command line option
processing and various containers.</p>
<!-- ======================================================================= -->
<h2 id="libbasic">The clang 'Basic' Library</h2>
<!-- ======================================================================= -->
<p>This library certainly needs a better name. The 'basic' library contains a
number of low-level utilities for tracking and manipulating source buffers,
locations within the source buffers, diagnostics, tokens, target abstraction,
and information about the subset of the language being compiled for.</p>
<p>Part of this infrastructure is specific to C (such as the TargetInfo class),
other parts could be reused for other non-C-based languages (SourceLocation,
SourceManager, Diagnostics, FileManager). When and if there is future demand
we can figure out if it makes sense to introduce a new library, move the general
classes somewhere else, or introduce some other solution.</p>
<p>We describe the roles of these classes in order of their dependencies.</p>
<!-- ======================================================================= -->
<h3 id="SourceLocation">The SourceLocation and SourceManager classes</h3>
<!-- ======================================================================= -->
<p>Strangely enough, the SourceLocation class represents a location within the
source code of the program. Important design points include:</p>
<ol>
<li>sizeof(SourceLocation) must be extremely small, as these are embedded into
many AST nodes and are passed around often. Currently it is 32 bits.</li>
<li>SourceLocation must be a simple value object that can be efficiently
copied.</li>
<li>We should be able to represent a source location for any byte of any input
file. This includes in the middle of tokens, in whitespace, in trigraphs,
etc.</li>
<li>A SourceLocation must encode the current #include stack that was active when
the location was processed. For example, if the location corresponds to a
token, it should contain the set of #includes active when the token was
lexed. This allows us to print the #include stack for a diagnostic.</li>
<li>SourceLocation must be able to describe macro expansions, capturing both
the ultimate instantiation point and the source of the original character
data.</li>
</ol>
<p>In practice, the SourceLocation works together with the SourceManager class
to encode two pieces of information about a location: it's physical location
and it's virtual location. For most tokens, these will be the same. However,
for a macro expansion (or tokens that came from a _Pragma directive) these will
describe the location of the characters corresponding to the token and the
location where the token was used (i.e. the macro instantiation point or the
location of the _Pragma itself).</p>
<p>For efficiency, we only track one level of macro instantions: if a token was
produced by multiple instantiations, we only track the source and ultimate
destination. Though we could track the intermediate instantiation points, this
would require extra bookkeeping and no known client would benefit substantially
from this.</p>
<p>The clang front-end inherently depends on the location of a token being
tracked correctly. If it is ever incorrect, the front-end may get confused and
die. The reason for this is that the notion of the 'spelling' of a Token in
clang depends on being able to find the original input characters for the token.
This concept maps directly to the "physical" location for the token.</p>
<!-- ======================================================================= -->
<h2 id="liblex">The Lexer and Preprocessor Library</h2>
<!-- ======================================================================= -->
<p>The Lexer library contains several tightly-connected classes that are involved
with the nasty process of lexing and preprocessing C source code. The main
interface to this library for outside clients is the large <a
href="#Preprocessor">Preprocessor</a> class.
It contains the various pieces of state that are required to coherently read
tokens out of a translation unit.</p>
<p>The core interface to the Preprocessor object (once it is set up) is the
Preprocessor::Lex method, which returns the next <a href="#Token">Token</a> from
the preprocessor stream. There are two types of token providers that the
preprocessor is capable of reading from: a buffer lexer (provided by the <a
href="#Lexer">Lexer</a> class) and a buffered token stream (provided by the <a
href="#TokenLexer">TokenLexer</a> class).
<!-- ======================================================================= -->
<h3 id="Token">The Token class</h3>
<!-- ======================================================================= -->
<p>The Token class is used to represent a single lexed token. Tokens are
intended to be used by the lexer/preprocess and parser libraries, but are not
intended to live beyond them (for example, they should not live in the ASTs).<p>
<p>Tokens most often live on the stack (or some other location that is efficient
to access) as the parser is running, but occasionally do get buffered up. For
example, macro definitions are stored as a series of tokens, and the C++
front-end will eventually need to buffer tokens up for tentative parsing and
various pieces of look-ahead. As such, the size of a Token matter. On a 32-bit
system, sizeof(Token) is currently 16 bytes.</p>
<p>Tokens contain the following information:</p>
<ul>
<li><b>A SourceLocation</b> - This indicates the location of the start of the
token.</li>
<li><b>A length</b> - This stores the length of the token as stored in the
SourceBuffer. For tokens that include them, this length includes trigraphs and
escaped newlines which are ignored by later phases of the compiler. By pointing
into the original source buffer, it is always possible to get the original
spelling of a token completely accurately.</li>
<li><b>IdentifierInfo</b> - If a token takes the form of an identifier, and if
identifier lookup was enabled when the token was lexed (e.g. the lexer was not
reading in 'raw' mode) this contains a pointer to the unique hash value for the
identifier. Because the lookup happens before keyword identification, this
field is set even for language keywords like 'for'.</li>
<li><b>TokenKind</b> - This indicates the kind of token as classified by the
lexer. This includes things like <tt>tok::starequal</tt> (for the "*="
operator), <tt>tok::ampamp</tt> for the "&&" token, and keyword values
(e.g. <tt>tok::kw_for</tt>) for identifiers that correspond to keywords. Note
that some tokens can be spelled multiple ways. For example, C++ supports
"operator keywords", where things like "and" are treated exactly like the
"&&" operator. In these cases, the kind value is set to
<tt>tok::ampamp</tt>, which is good for the parser, which doesn't have to
consider both forms. For something that cares about which form is used (e.g.
the preprocessor 'stringize' operator) the spelling indicates the original
form.</li>
<li><b>Flags</b> - There are currently four flags tracked by the
lexer/preprocessor system on a per-token basis:
<ol>
<li><b>StartOfLine</b> - This was the first token that occurred on its input
source line.</li>
<li><b>LeadingSpace</b> - There was a space character either immediately
before the token or transitively before the token as it was expanded
through a macro. The definition of this flag is very closely defined by
the stringizing requirements of the preprocessor.</li>
<li><b>DisableExpand</b> - This flag is used internally to the preprocessor to
represent identifier tokens which have macro expansion disabled. This
prevents them from being considered as candidates for macro expansion ever
in the future.</li>
<li><b>NeedsCleaning</b> - This flag is set if the original spelling for the
token includes a trigraph or escaped newline. Since this is uncommon,
many pieces of code can fast-path on tokens that did not need cleaning.
</p>
</ol>
</li>
</ul>
<p>One interesting (and somewhat unusual) aspect of tokens is that they don't
contain any semantic information about the lexed value. For example, if the
token was a pp-number token, we do not represent the value of the number that
was lexed (this is left for later pieces of code to decide). Additionally, the
lexer library has no notion of typedef names vs variable names: both are
returned as identifiers, and the parser is left to decide whether a specific
identifier is a typedef or a variable (tracking this requires scope information
among other things).</p>
<!-- ======================================================================= -->
<h3 id="Lexer">The Lexer class</h3>
<!-- ======================================================================= -->
<p>The Lexer class provides the mechanics of lexing tokens out of a source
buffer and deciding what they mean. The Lexer is complicated by the fact that
it operates on raw buffers that have not had spelling eliminated (this is a
necessity to get decent performance), but this is countered with careful coding
as well as standard performance techniques (for example, the comment handling
code is vectorized on X86 and PowerPC hosts).</p>
<p>The lexer has a couple of interesting modal features:</p>
<ul>
<li>The lexer can operate in 'raw' mode. This mode has several features that
make it possible to quickly lex the file (e.g. it stops identifier lookup,
doesn't specially handle preprocessor tokens, handles EOF differently, etc).
This mode is used for lexing within an "<tt>#if 0</tt>" block, for
example.</li>
<li>The lexer can capture and return comments as tokens. This is required to
support the -C preprocessor mode, which passes comments through, and is
used by the diagnostic checker to identifier expect-error annotations.</li>
<li>The lexer can be in ParsingFilename mode, which happens when preprocessing
after reading a #include directive. This mode changes the parsing of '<'
to return an "angled string" instead of a bunch of tokens for each thing
within the filename.</li>
<li>When parsing a preprocessor directive (after "<tt>#</tt>") the
ParsingPreprocessorDirective mode is entered. This changes the parser to
return EOM at a newline.</li>
<li>The Lexer uses a LangOptions object to know whether trigraphs are enabled,
whether C++ or ObjC keywords are recognized, etc.</li>
</ul>
<p>In addition to these modes, the lexer keeps track of a couple of other
features that are local to a lexed buffer, which change as the buffer is
lexed:</p>
<ul>
<li>The Lexer uses BufferPtr to keep track of the current character being
lexed.</li>
<li>The Lexer uses IsAtStartOfLine to keep track of whether the next lexed token
will start with its "start of line" bit set.</li>
<li>The Lexer keeps track of the current #if directives that are active (which
can be nested).</li>
<li>The Lexer keeps track of an <a href="#MultipleIncludeOpt">
MultipleIncludeOpt</a> object, which is used to
detect whether the buffer uses the standard "<tt>#ifndef XX</tt> /
<tt>#define XX</tt>" idiom to prevent multiple inclusion. If a buffer does,
subsequent includes can be ignored if the XX macro is defined.</li>
</ul>
<!-- ======================================================================= -->
<h3 id="TokenLexer">The TokenLexer class</h3>
<!-- ======================================================================= -->
<p>The TokenLexer class is a token provider that returns tokens from a list
of tokens that came from somewhere else. It typically used for two things: 1)
returning tokens from a macro definition as it is being expanded 2) returning
tokens from an arbitrary buffer of tokens. The later use is used by _Pragma and
will most likely be used to handle unbounded look-ahead for the C++ parser.</p>
<!-- ======================================================================= -->
<h3 id="MultipleIncludeOpt">The MultipleIncludeOpt class</h3>
<!-- ======================================================================= -->
<p>The MultipleIncludeOpt class implements a really simple little state machine
that is used to detect the standard "<tt>#ifndef XX</tt> / <tt>#define XX</tt>"
idiom that people typically use to prevent multiple inclusion of headers. If a
buffer uses this idiom and is subsequentl
|
