1 //===--- CacheTokens.cpp - Caching of lexer tokens for PTH support --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This provides a possible implementation of PTH support for Clang that is
11 // based on caching lexed tokens and identifiers.
13 //===----------------------------------------------------------------------===//
15 #include "clang/Frontend/Utils.h"
16 #include "clang/Basic/Diagnostic.h"
17 #include "clang/Basic/FileManager.h"
18 #include "clang/Basic/FileSystemStatCache.h"
19 #include "clang/Basic/IdentifierTable.h"
20 #include "clang/Basic/OnDiskHashTable.h"
21 #include "clang/Basic/SourceManager.h"
22 #include "clang/Lex/Lexer.h"
23 #include "clang/Lex/Preprocessor.h"
24 #include "llvm/ADT/StringExtras.h"
25 #include "llvm/ADT/StringMap.h"
26 #include "llvm/Support/FileSystem.h"
27 #include "llvm/Support/MemoryBuffer.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Support/Path.h"
31 // FIXME: put this somewhere else?
33 #define S_ISDIR(x) (((x)&_S_IFDIR)!=0)
36 using namespace clang;
37 using namespace clang::io;
39 //===----------------------------------------------------------------------===//
40 // PTH-specific stuff.
41 //===----------------------------------------------------------------------===//
45 Offset TokenData, PPCondData;
50 PTHEntry(Offset td, Offset ppcd)
51 : TokenData(td), PPCondData(ppcd) {}
53 Offset getTokenOffset() const { return TokenData; }
54 Offset getPPCondTableOffset() const { return PPCondData; }
58 class PTHEntryKeyVariant {
59 union { const FileEntry* FE; const char* Path; };
60 enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind;
63 PTHEntryKeyVariant(const FileEntry *fe)
64 : FE(fe), Kind(IsFE), StatBuf(0) {}
66 PTHEntryKeyVariant(struct stat* statbuf, const char* path)
67 : Path(path), Kind(IsDE), StatBuf(new struct stat(*statbuf)) {}
69 explicit PTHEntryKeyVariant(const char* path)
70 : Path(path), Kind(IsNoExist), StatBuf(0) {}
72 bool isFile() const { return Kind == IsFE; }
74 StringRef getString() const {
75 return Kind == IsFE ? FE->getName() : Path;
78 unsigned getKind() const { return (unsigned) Kind; }
80 void EmitData(raw_ostream& Out) {
83 // Emit stat information.
84 ::Emit32(Out, FE->getInode());
85 ::Emit32(Out, FE->getDevice());
86 ::Emit16(Out, FE->getFileMode());
87 ::Emit64(Out, FE->getModificationTime());
88 ::Emit64(Out, FE->getSize());
91 // Emit stat information.
92 ::Emit32(Out, (uint32_t) StatBuf->st_ino);
93 ::Emit32(Out, (uint32_t) StatBuf->st_dev);
94 ::Emit16(Out, (uint16_t) StatBuf->st_mode);
95 ::Emit64(Out, (uint64_t) StatBuf->st_mtime);
96 ::Emit64(Out, (uint64_t) StatBuf->st_size);
104 unsigned getRepresentationLength() const {
105 return Kind == IsNoExist ? 0 : 4 + 4 + 2 + 8 + 8;
109 class FileEntryPTHEntryInfo {
111 typedef PTHEntryKeyVariant key_type;
112 typedef key_type key_type_ref;
114 typedef PTHEntry data_type;
115 typedef const PTHEntry& data_type_ref;
117 static unsigned ComputeHash(PTHEntryKeyVariant V) {
118 return llvm::HashString(V.getString());
121 static std::pair<unsigned,unsigned>
122 EmitKeyDataLength(raw_ostream& Out, PTHEntryKeyVariant V,
125 unsigned n = V.getString().size() + 1 + 1;
128 unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0);
131 return std::make_pair(n, m);
134 static void EmitKey(raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){
135 // Emit the entry kind.
136 ::Emit8(Out, (unsigned) V.getKind());
138 Out.write(V.getString().data(), n - 1);
141 static void EmitData(raw_ostream& Out, PTHEntryKeyVariant V,
142 const PTHEntry& E, unsigned) {
145 // For file entries emit the offsets into the PTH file for token data
146 // and the preprocessor blocks table.
148 ::Emit32(Out, E.getTokenOffset());
149 ::Emit32(Out, E.getPPCondTableOffset());
152 // Emit any other data associated with the key (i.e., stat information).
161 OffsetOpt() : valid(false) {}
162 bool hasOffset() const { return valid; }
163 Offset getOffset() const { assert(valid); return off; }
164 void setOffset(Offset o) { off = o; valid = true; }
166 } // end anonymous namespace
168 typedef OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap;
172 typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap;
173 typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy;
176 llvm::raw_fd_ostream& Out;
180 CachedStrsTy CachedStrs;
182 std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries;
184 //// Get the persistent id for the given IdentifierInfo*.
185 uint32_t ResolveID(const IdentifierInfo* II);
187 /// Emit a token to the PTH file.
188 void EmitToken(const Token& T);
190 void Emit8(uint32_t V) { ::Emit8(Out, V); }
192 void Emit16(uint32_t V) { ::Emit16(Out, V); }
194 void Emit32(uint32_t V) { ::Emit32(Out, V); }
196 void EmitBuf(const char *Ptr, unsigned NumBytes) {
197 Out.write(Ptr, NumBytes);
200 void EmitString(StringRef V) {
201 ::Emit16(Out, V.size());
202 EmitBuf(V.data(), V.size());
205 /// EmitIdentifierTable - Emits two tables to the PTH file. The first is
206 /// a hashtable mapping from identifier strings to persistent IDs.
207 /// The second is a straight table mapping from persistent IDs to string data
208 /// (the keys of the first table).
209 std::pair<Offset, Offset> EmitIdentifierTable();
211 /// EmitFileTable - Emit a table mapping from file name strings to PTH
213 Offset EmitFileTable() { return PM.Emit(Out); }
215 PTHEntry LexTokens(Lexer& L);
216 Offset EmitCachedSpellings();
219 PTHWriter(llvm::raw_fd_ostream& out, Preprocessor& pp)
220 : Out(out), PP(pp), idcount(0), CurStrOffset(0) {}
222 PTHMap &getPM() { return PM; }
223 void GeneratePTH(const std::string &MainFile);
225 } // end anonymous namespace
227 uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) {
228 // Null IdentifierInfo's map to the persistent ID 0.
232 IDMap::iterator I = IM.find(II);
234 return I->second; // We've already added 1.
236 IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL.
240 void PTHWriter::EmitToken(const Token& T) {
241 // Emit the token kind, flags, and length.
242 Emit32(((uint32_t) T.getKind()) | ((((uint32_t) T.getFlags())) << 8)|
243 (((uint32_t) T.getLength()) << 16));
245 if (!T.isLiteral()) {
246 Emit32(ResolveID(T.getIdentifierInfo()));
248 // We cache *un-cleaned* spellings. This gives us 100% fidelity with the
250 StringRef s(T.getLiteralData(), T.getLength());
252 // Get the string entry.
253 llvm::StringMapEntry<OffsetOpt> *E = &CachedStrs.GetOrCreateValue(s);
255 // If this is a new string entry, bump the PTH offset.
256 if (!E->getValue().hasOffset()) {
257 E->getValue().setOffset(CurStrOffset);
258 StrEntries.push_back(E);
259 CurStrOffset += s.size() + 1;
262 // Emit the relative offset into the PTH file for the spelling string.
263 Emit32(E->getValue().getOffset());
266 // Emit the offset into the original source file of this token so that we
267 // can reconstruct its SourceLocation.
268 Emit32(PP.getSourceManager().getFileOffset(T.getLocation()));
271 PTHEntry PTHWriter::LexTokens(Lexer& L) {
272 // Pad 0's so that we emit tokens to a 4-byte alignment.
273 // This speed up reading them back in.
275 Offset TokenOff = (Offset) Out.tell();
277 // Keep track of matching '#if' ... '#endif'.
278 typedef std::vector<std::pair<Offset, unsigned> > PPCondTable;
280 std::vector<unsigned> PPStartCond;
281 bool ParsingPreprocessorDirective = false;
285 L.LexFromRawLexer(Tok);
288 if ((Tok.isAtStartOfLine() || Tok.is(tok::eof)) &&
289 ParsingPreprocessorDirective) {
290 // Insert an eod token into the token cache. It has the same
291 // position as the next token that is not on the same line as the
292 // preprocessor directive. Observe that we continue processing
293 // 'Tok' when we exit this branch.
295 Tmp.setKind(tok::eod);
296 Tmp.clearFlag(Token::StartOfLine);
297 Tmp.setIdentifierInfo(0);
299 ParsingPreprocessorDirective = false;
302 if (Tok.is(tok::raw_identifier)) {
303 PP.LookUpIdentifierInfo(Tok);
308 if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
309 // Special processing for #include. Store the '#' token and lex
311 assert(!ParsingPreprocessorDirective);
312 Offset HashOff = (Offset) Out.tell();
314 // Get the next token.
316 L.LexFromRawLexer(NextTok);
318 // If we see the start of line, then we had a null directive "#". In
319 // this case, discard both tokens.
320 if (NextTok.isAtStartOfLine())
323 // The token is the start of a directive. Emit it.
327 // Did we see 'include'/'import'/'include_next'?
328 if (Tok.isNot(tok::raw_identifier)) {
333 IdentifierInfo* II = PP.LookUpIdentifierInfo(Tok);
334 tok::PPKeywordKind K = II->getPPKeywordID();
336 ParsingPreprocessorDirective = true;
339 case tok::pp_not_keyword:
340 // Invalid directives "#foo" can occur in #if 0 blocks etc, just pass
345 case tok::pp_include:
347 case tok::pp_include_next: {
348 // Save the 'include' token.
350 // Lex the next token as an include string.
351 L.setParsingPreprocessorDirective(true);
352 L.LexIncludeFilename(Tok);
353 L.setParsingPreprocessorDirective(false);
354 assert(!Tok.isAtStartOfLine());
355 if (Tok.is(tok::raw_identifier))
356 PP.LookUpIdentifierInfo(Tok);
362 case tok::pp_ifndef: {
363 // Add an entry for '#if' and friends. We initially set the target
364 // index to 0. This will get backpatched when we hit #endif.
365 PPStartCond.push_back(PPCond.size());
366 PPCond.push_back(std::make_pair(HashOff, 0U));
369 case tok::pp_endif: {
370 // Add an entry for '#endif'. We set the target table index to itself.
371 // This will later be set to zero when emitting to the PTH file. We
372 // use 0 for uninitialized indices because that is easier to debug.
373 unsigned index = PPCond.size();
374 // Backpatch the opening '#if' entry.
375 assert(!PPStartCond.empty());
376 assert(PPCond.size() > PPStartCond.back());
377 assert(PPCond[PPStartCond.back()].second == 0);
378 PPCond[PPStartCond.back()].second = index;
379 PPStartCond.pop_back();
380 // Add the new entry to PPCond.
381 PPCond.push_back(std::make_pair(HashOff, index));
384 // Some files have gibberish on the same line as '#endif'.
385 // Discard these tokens.
387 L.LexFromRawLexer(Tok);
388 while (Tok.isNot(tok::eof) && !Tok.isAtStartOfLine());
389 // We have the next token in hand.
390 // Don't immediately lex the next one.
395 // Add an entry for #elif or #else.
396 // This serves as both a closing and opening of a conditional block.
397 // This means that its entry will get backpatched later.
398 unsigned index = PPCond.size();
399 // Backpatch the previous '#if' entry.
400 assert(!PPStartCond.empty());
401 assert(PPCond.size() > PPStartCond.back());
402 assert(PPCond[PPStartCond.back()].second == 0);
403 PPCond[PPStartCond.back()].second = index;
404 PPStartCond.pop_back();
405 // Now add '#elif' as a new block opening.
406 PPCond.push_back(std::make_pair(HashOff, 0U));
407 PPStartCond.push_back(index);
415 while (Tok.isNot(tok::eof));
417 assert(PPStartCond.empty() && "Error: imblanced preprocessor conditionals.");
419 // Next write out PPCond.
420 Offset PPCondOff = (Offset) Out.tell();
422 // Write out the size of PPCond so that clients can identifer empty tables.
423 Emit32(PPCond.size());
425 for (unsigned i = 0, e = PPCond.size(); i!=e; ++i) {
426 Emit32(PPCond[i].first - TokenOff);
427 uint32_t x = PPCond[i].second;
428 assert(x != 0 && "PPCond entry not backpatched.");
429 // Emit zero for #endifs. This allows us to do checking when
430 // we read the PTH file back in.
431 Emit32(x == i ? 0 : x);
434 return PTHEntry(TokenOff, PPCondOff);
437 Offset PTHWriter::EmitCachedSpellings() {
438 // Write each cached strings to the PTH file.
439 Offset SpellingsOff = Out.tell();
441 for (std::vector<llvm::StringMapEntry<OffsetOpt>*>::iterator
442 I = StrEntries.begin(), E = StrEntries.end(); I!=E; ++I)
443 EmitBuf((*I)->getKeyData(), (*I)->getKeyLength()+1 /*nul included*/);
448 void PTHWriter::GeneratePTH(const std::string &MainFile) {
449 // Generate the prologue.
450 Out << "cfe-pth" << '\0';
451 Emit32(PTHManager::Version);
453 // Leave 4 words for the prologue.
454 Offset PrologueOffset = Out.tell();
455 for (unsigned i = 0; i < 4; ++i)
458 // Write the name of the MainFile.
459 if (!MainFile.empty()) {
460 EmitString(MainFile);
462 // String with 0 bytes.
467 // Iterate over all the files in SourceManager. Create a lexer
468 // for each file and cache the tokens.
469 SourceManager &SM = PP.getSourceManager();
470 const LangOptions &LOpts = PP.getLangOpts();
472 for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(),
473 E = SM.fileinfo_end(); I != E; ++I) {
474 const SrcMgr::ContentCache &C = *I->second;
475 const FileEntry *FE = C.OrigEntry;
477 // FIXME: Handle files with non-absolute paths.
478 if (llvm::sys::path::is_relative(FE->getName()))
481 const llvm::MemoryBuffer *B = C.getBuffer(PP.getDiagnostics(), SM);
484 FileID FID = SM.createFileID(FE, SourceLocation(), SrcMgr::C_User);
485 const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID);
486 Lexer L(FID, FromFile, SM, LOpts);
487 PM.insert(FE, LexTokens(L));
490 // Write out the identifier table.
491 const std::pair<Offset,Offset> &IdTableOff = EmitIdentifierTable();
493 // Write out the cached strings table.
494 Offset SpellingOff = EmitCachedSpellings();
496 // Write out the file table.
497 Offset FileTableOff = EmitFileTable();
499 // Finally, write the prologue.
500 Out.seek(PrologueOffset);
501 Emit32(IdTableOff.first);
502 Emit32(IdTableOff.second);
503 Emit32(FileTableOff);
508 /// StatListener - A simple "interpose" object used to monitor stat calls
509 /// invoked by FileManager while processing the original sources used
510 /// as input to PTH generation. StatListener populates the PTHWriter's
511 /// file map with stat information for directories as well as negative stats.
512 /// Stat information for files are populated elsewhere.
513 class StatListener : public FileSystemStatCache {
516 StatListener(PTHMap &pm) : PM(pm) {}
519 LookupResult getStat(const char *Path, struct stat &StatBuf,
520 int *FileDescriptor) {
521 LookupResult Result = statChained(Path, StatBuf, FileDescriptor);
523 if (Result == CacheMissing) // Failed 'stat'.
524 PM.insert(PTHEntryKeyVariant(Path), PTHEntry());
525 else if (S_ISDIR(StatBuf.st_mode)) {
526 // Only cache directories with absolute paths.
527 if (llvm::sys::path::is_relative(Path))
530 PM.insert(PTHEntryKeyVariant(&StatBuf, Path), PTHEntry());
536 } // end anonymous namespace
539 void clang::CacheTokens(Preprocessor &PP, llvm::raw_fd_ostream* OS) {
540 // Get the name of the main file.
541 const SourceManager &SrcMgr = PP.getSourceManager();
542 const FileEntry *MainFile = SrcMgr.getFileEntryForID(SrcMgr.getMainFileID());
543 SmallString<128> MainFilePath(MainFile->getName());
545 llvm::sys::fs::make_absolute(MainFilePath);
547 // Create the PTHWriter.
548 PTHWriter PW(*OS, PP);
550 // Install the 'stat' system call listener in the FileManager.
551 StatListener *StatCache = new StatListener(PW.getPM());
552 PP.getFileManager().addStatCache(StatCache, /*AtBeginning=*/true);
554 // Lex through the entire file. This will populate SourceManager with
555 // all of the header information.
557 PP.EnterMainSourceFile();
558 do { PP.Lex(Tok); } while (Tok.isNot(tok::eof));
560 // Generate the PTH file.
561 PP.getFileManager().removeStatCache(StatCache);
562 PW.GeneratePTH(MainFilePath.str());
565 //===----------------------------------------------------------------------===//
570 const IdentifierInfo* II;
574 class PTHIdentifierTableTrait {
576 typedef PTHIdKey* key_type;
577 typedef key_type key_type_ref;
579 typedef uint32_t data_type;
580 typedef data_type data_type_ref;
582 static unsigned ComputeHash(PTHIdKey* key) {
583 return llvm::HashString(key->II->getName());
586 static std::pair<unsigned,unsigned>
587 EmitKeyDataLength(raw_ostream& Out, const PTHIdKey* key, uint32_t) {
588 unsigned n = key->II->getLength() + 1;
590 return std::make_pair(n, sizeof(uint32_t));
593 static void EmitKey(raw_ostream& Out, PTHIdKey* key, unsigned n) {
594 // Record the location of the key data. This is used when generating
595 // the mapping from persistent IDs to strings.
596 key->FileOffset = Out.tell();
597 Out.write(key->II->getNameStart(), n);
600 static void EmitData(raw_ostream& Out, PTHIdKey*, uint32_t pID,
605 } // end anonymous namespace
607 /// EmitIdentifierTable - Emits two tables to the PTH file. The first is
608 /// a hashtable mapping from identifier strings to persistent IDs. The second
609 /// is a straight table mapping from persistent IDs to string data (the
610 /// keys of the first table).
612 std::pair<Offset,Offset> PTHWriter::EmitIdentifierTable() {
614 // (1) an inverse map from persistent IDs -> (IdentifierInfo*,Offset)
615 // (2) a map from (IdentifierInfo*, Offset)* -> persistent IDs
617 // Note that we use 'calloc', so all the bytes are 0.
618 PTHIdKey *IIDMap = (PTHIdKey*)calloc(idcount, sizeof(PTHIdKey));
620 // Create the hashtable.
621 OnDiskChainedHashTableGenerator<PTHIdentifierTableTrait> IIOffMap;
623 // Generate mapping from persistent IDs -> IdentifierInfo*.
624 for (IDMap::iterator I = IM.begin(), E = IM.end(); I != E; ++I) {
625 // Decrement by 1 because we are using a vector for the lookup and
626 // 0 is reserved for NULL.
627 assert(I->second > 0);
628 assert(I->second-1 < idcount);
629 unsigned idx = I->second-1;
631 // Store the mapping from persistent ID to IdentifierInfo*
632 IIDMap[idx].II = I->first;
634 // Store the reverse mapping in a hashtable.
635 IIOffMap.insert(&IIDMap[idx], I->second);
638 // Write out the inverse map first. This causes the PCIDKey entries to
639 // record PTH file offsets for the string data. This is used to write
641 Offset StringTableOffset = IIOffMap.Emit(Out);
643 // Now emit the table mapping from persistent IDs to PTH file offsets.
644 Offset IDOff = Out.tell();
645 Emit32(idcount); // Emit the number of identifiers.
646 for (unsigned i = 0 ; i < idcount; ++i)
647 Emit32(IIDMap[i].FileOffset);
649 // Finally, release the inverse map.
652 return std::make_pair(IDOff, StringTableOffset);