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/SourceManager.h"
21 #include "clang/Lex/Lexer.h"
22 #include "clang/Lex/Preprocessor.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/Support/EndianStream.h"
26 #include "llvm/Support/FileSystem.h"
27 #include "llvm/Support/MemoryBuffer.h"
28 #include "llvm/Support/OnDiskHashTable.h"
29 #include "llvm/Support/Path.h"
30 #include "llvm/Support/raw_ostream.h"
32 // FIXME: put this somewhere else?
34 #define S_ISDIR(x) (((x)&_S_IFDIR)!=0)
37 using namespace clang;
39 //===----------------------------------------------------------------------===//
40 // PTH-specific stuff.
41 //===----------------------------------------------------------------------===//
43 typedef uint32_t Offset;
47 Offset TokenData, PPCondData;
52 PTHEntry(Offset td, Offset ppcd)
53 : TokenData(td), PPCondData(ppcd) {}
55 Offset getTokenOffset() const { return TokenData; }
56 Offset getPPCondTableOffset() const { return PPCondData; }
60 class PTHEntryKeyVariant {
61 union { const FileEntry* FE; const char* Path; };
62 enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind;
66 PTHEntryKeyVariant(const FileEntry *fe) : FE(fe), Kind(IsFE), Data(nullptr) {}
68 PTHEntryKeyVariant(FileData *Data, const char *path)
69 : Path(path), Kind(IsDE), Data(new FileData(*Data)) {}
71 explicit PTHEntryKeyVariant(const char *path)
72 : Path(path), Kind(IsNoExist), Data(nullptr) {}
74 bool isFile() const { return Kind == IsFE; }
76 StringRef getString() const {
77 return Kind == IsFE ? FE->getName() : Path;
80 unsigned getKind() const { return (unsigned) Kind; }
82 void EmitData(raw_ostream& Out) {
83 using namespace llvm::support;
84 endian::Writer<little> LE(Out);
87 // Emit stat information.
88 llvm::sys::fs::UniqueID UID = FE->getUniqueID();
89 LE.write<uint64_t>(UID.getFile());
90 LE.write<uint64_t>(UID.getDevice());
91 LE.write<uint64_t>(FE->getModificationTime());
92 LE.write<uint64_t>(FE->getSize());
95 // Emit stat information.
96 LE.write<uint64_t>(Data->UniqueID.getFile());
97 LE.write<uint64_t>(Data->UniqueID.getDevice());
98 LE.write<uint64_t>(Data->ModTime);
99 LE.write<uint64_t>(Data->Size);
107 unsigned getRepresentationLength() const {
108 return Kind == IsNoExist ? 0 : 4 + 4 + 2 + 8 + 8;
112 class FileEntryPTHEntryInfo {
114 typedef PTHEntryKeyVariant key_type;
115 typedef key_type key_type_ref;
117 typedef PTHEntry data_type;
118 typedef const PTHEntry& data_type_ref;
120 typedef unsigned hash_value_type;
121 typedef unsigned offset_type;
123 static hash_value_type ComputeHash(PTHEntryKeyVariant V) {
124 return llvm::HashString(V.getString());
127 static std::pair<unsigned,unsigned>
128 EmitKeyDataLength(raw_ostream& Out, PTHEntryKeyVariant V,
130 using namespace llvm::support;
131 endian::Writer<little> LE(Out);
133 unsigned n = V.getString().size() + 1 + 1;
134 LE.write<uint16_t>(n);
136 unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0);
137 LE.write<uint8_t>(m);
139 return std::make_pair(n, m);
142 static void EmitKey(raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){
143 using namespace llvm::support;
144 // Emit the entry kind.
145 endian::Writer<little>(Out).write<uint8_t>((unsigned)V.getKind());
147 Out.write(V.getString().data(), n - 1);
150 static void EmitData(raw_ostream& Out, PTHEntryKeyVariant V,
151 const PTHEntry& E, unsigned) {
152 using namespace llvm::support;
153 endian::Writer<little> LE(Out);
155 // For file entries emit the offsets into the PTH file for token data
156 // and the preprocessor blocks table.
158 LE.write<uint32_t>(E.getTokenOffset());
159 LE.write<uint32_t>(E.getPPCondTableOffset());
162 // Emit any other data associated with the key (i.e., stat information).
171 OffsetOpt() : valid(false) {}
172 bool hasOffset() const { return valid; }
173 Offset getOffset() const { assert(valid); return off; }
174 void setOffset(Offset o) { off = o; valid = true; }
176 } // end anonymous namespace
178 typedef llvm::OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap;
182 typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap;
183 typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy;
186 raw_pwrite_stream &Out;
190 CachedStrsTy CachedStrs;
192 std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries;
194 //// Get the persistent id for the given IdentifierInfo*.
195 uint32_t ResolveID(const IdentifierInfo* II);
197 /// Emit a token to the PTH file.
198 void EmitToken(const Token& T);
200 void Emit8(uint32_t V) {
201 using namespace llvm::support;
202 endian::Writer<little>(Out).write<uint8_t>(V);
205 void Emit16(uint32_t V) {
206 using namespace llvm::support;
207 endian::Writer<little>(Out).write<uint16_t>(V);
210 void Emit32(uint32_t V) {
211 using namespace llvm::support;
212 endian::Writer<little>(Out).write<uint32_t>(V);
215 void EmitBuf(const char *Ptr, unsigned NumBytes) {
216 Out.write(Ptr, NumBytes);
219 void EmitString(StringRef V) {
220 using namespace llvm::support;
221 endian::Writer<little>(Out).write<uint16_t>(V.size());
222 EmitBuf(V.data(), V.size());
225 /// EmitIdentifierTable - Emits two tables to the PTH file. The first is
226 /// a hashtable mapping from identifier strings to persistent IDs.
227 /// The second is a straight table mapping from persistent IDs to string data
228 /// (the keys of the first table).
229 std::pair<Offset, Offset> EmitIdentifierTable();
231 /// EmitFileTable - Emit a table mapping from file name strings to PTH
233 Offset EmitFileTable() { return PM.Emit(Out); }
235 PTHEntry LexTokens(Lexer& L);
236 Offset EmitCachedSpellings();
239 PTHWriter(raw_pwrite_stream &out, Preprocessor &pp)
240 : Out(out), PP(pp), idcount(0), CurStrOffset(0) {}
242 PTHMap &getPM() { return PM; }
243 void GeneratePTH(const std::string &MainFile);
245 } // end anonymous namespace
247 uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) {
248 // Null IdentifierInfo's map to the persistent ID 0.
252 IDMap::iterator I = IM.find(II);
254 return I->second; // We've already added 1.
256 IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL.
260 void PTHWriter::EmitToken(const Token& T) {
261 // Emit the token kind, flags, and length.
262 Emit32(((uint32_t) T.getKind()) | ((((uint32_t) T.getFlags())) << 8)|
263 (((uint32_t) T.getLength()) << 16));
265 if (!T.isLiteral()) {
266 Emit32(ResolveID(T.getIdentifierInfo()));
268 // We cache *un-cleaned* spellings. This gives us 100% fidelity with the
270 StringRef s(T.getLiteralData(), T.getLength());
272 // Get the string entry.
273 auto &E = *CachedStrs.insert(std::make_pair(s, OffsetOpt())).first;
275 // If this is a new string entry, bump the PTH offset.
276 if (!E.second.hasOffset()) {
277 E.second.setOffset(CurStrOffset);
278 StrEntries.push_back(&E);
279 CurStrOffset += s.size() + 1;
282 // Emit the relative offset into the PTH file for the spelling string.
283 Emit32(E.second.getOffset());
286 // Emit the offset into the original source file of this token so that we
287 // can reconstruct its SourceLocation.
288 Emit32(PP.getSourceManager().getFileOffset(T.getLocation()));
291 PTHEntry PTHWriter::LexTokens(Lexer& L) {
292 // Pad 0's so that we emit tokens to a 4-byte alignment.
293 // This speed up reading them back in.
294 using namespace llvm::support;
295 endian::Writer<little> LE(Out);
296 uint32_t TokenOff = Out.tell();
297 for (uint64_t N = llvm::OffsetToAlignment(TokenOff, 4); N; --N, ++TokenOff)
298 LE.write<uint8_t>(0);
300 // Keep track of matching '#if' ... '#endif'.
301 typedef std::vector<std::pair<Offset, unsigned> > PPCondTable;
303 std::vector<unsigned> PPStartCond;
304 bool ParsingPreprocessorDirective = false;
308 L.LexFromRawLexer(Tok);
311 if ((Tok.isAtStartOfLine() || Tok.is(tok::eof)) &&
312 ParsingPreprocessorDirective) {
313 // Insert an eod token into the token cache. It has the same
314 // position as the next token that is not on the same line as the
315 // preprocessor directive. Observe that we continue processing
316 // 'Tok' when we exit this branch.
318 Tmp.setKind(tok::eod);
319 Tmp.clearFlag(Token::StartOfLine);
320 Tmp.setIdentifierInfo(nullptr);
322 ParsingPreprocessorDirective = false;
325 if (Tok.is(tok::raw_identifier)) {
326 PP.LookUpIdentifierInfo(Tok);
331 if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
332 // Special processing for #include. Store the '#' token and lex
334 assert(!ParsingPreprocessorDirective);
335 Offset HashOff = (Offset) Out.tell();
337 // Get the next token.
339 L.LexFromRawLexer(NextTok);
341 // If we see the start of line, then we had a null directive "#". In
342 // this case, discard both tokens.
343 if (NextTok.isAtStartOfLine())
346 // The token is the start of a directive. Emit it.
350 // Did we see 'include'/'import'/'include_next'?
351 if (Tok.isNot(tok::raw_identifier)) {
356 IdentifierInfo* II = PP.LookUpIdentifierInfo(Tok);
357 tok::PPKeywordKind K = II->getPPKeywordID();
359 ParsingPreprocessorDirective = true;
362 case tok::pp_not_keyword:
363 // Invalid directives "#foo" can occur in #if 0 blocks etc, just pass
368 case tok::pp_include:
370 case tok::pp_include_next: {
371 // Save the 'include' token.
373 // Lex the next token as an include string.
374 L.setParsingPreprocessorDirective(true);
375 L.LexIncludeFilename(Tok);
376 L.setParsingPreprocessorDirective(false);
377 assert(!Tok.isAtStartOfLine());
378 if (Tok.is(tok::raw_identifier))
379 PP.LookUpIdentifierInfo(Tok);
385 case tok::pp_ifndef: {
386 // Add an entry for '#if' and friends. We initially set the target
387 // index to 0. This will get backpatched when we hit #endif.
388 PPStartCond.push_back(PPCond.size());
389 PPCond.push_back(std::make_pair(HashOff, 0U));
392 case tok::pp_endif: {
393 // Add an entry for '#endif'. We set the target table index to itself.
394 // This will later be set to zero when emitting to the PTH file. We
395 // use 0 for uninitialized indices because that is easier to debug.
396 unsigned index = PPCond.size();
397 // Backpatch the opening '#if' entry.
398 assert(!PPStartCond.empty());
399 assert(PPCond.size() > PPStartCond.back());
400 assert(PPCond[PPStartCond.back()].second == 0);
401 PPCond[PPStartCond.back()].second = index;
402 PPStartCond.pop_back();
403 // Add the new entry to PPCond.
404 PPCond.push_back(std::make_pair(HashOff, index));
407 // Some files have gibberish on the same line as '#endif'.
408 // Discard these tokens.
410 L.LexFromRawLexer(Tok);
411 while (Tok.isNot(tok::eof) && !Tok.isAtStartOfLine());
412 // We have the next token in hand.
413 // Don't immediately lex the next one.
418 // Add an entry for #elif or #else.
419 // This serves as both a closing and opening of a conditional block.
420 // This means that its entry will get backpatched later.
421 unsigned index = PPCond.size();
422 // Backpatch the previous '#if' entry.
423 assert(!PPStartCond.empty());
424 assert(PPCond.size() > PPStartCond.back());
425 assert(PPCond[PPStartCond.back()].second == 0);
426 PPCond[PPStartCond.back()].second = index;
427 PPStartCond.pop_back();
428 // Now add '#elif' as a new block opening.
429 PPCond.push_back(std::make_pair(HashOff, 0U));
430 PPStartCond.push_back(index);
438 while (Tok.isNot(tok::eof));
440 assert(PPStartCond.empty() && "Error: imblanced preprocessor conditionals.");
442 // Next write out PPCond.
443 Offset PPCondOff = (Offset) Out.tell();
445 // Write out the size of PPCond so that clients can identifer empty tables.
446 Emit32(PPCond.size());
448 for (unsigned i = 0, e = PPCond.size(); i!=e; ++i) {
449 Emit32(PPCond[i].first - TokenOff);
450 uint32_t x = PPCond[i].second;
451 assert(x != 0 && "PPCond entry not backpatched.");
452 // Emit zero for #endifs. This allows us to do checking when
453 // we read the PTH file back in.
454 Emit32(x == i ? 0 : x);
457 return PTHEntry(TokenOff, PPCondOff);
460 Offset PTHWriter::EmitCachedSpellings() {
461 // Write each cached strings to the PTH file.
462 Offset SpellingsOff = Out.tell();
464 for (std::vector<llvm::StringMapEntry<OffsetOpt>*>::iterator
465 I = StrEntries.begin(), E = StrEntries.end(); I!=E; ++I)
466 EmitBuf((*I)->getKeyData(), (*I)->getKeyLength()+1 /*nul included*/);
471 static uint32_t swap32le(uint32_t X) {
472 return llvm::support::endian::byte_swap<uint32_t, llvm::support::little>(X);
475 static void pwrite32le(raw_pwrite_stream &OS, uint32_t Val, uint64_t &Off) {
476 uint32_t LEVal = swap32le(Val);
477 OS.pwrite(reinterpret_cast<const char *>(&LEVal), 4, Off);
481 void PTHWriter::GeneratePTH(const std::string &MainFile) {
482 // Generate the prologue.
483 Out << "cfe-pth" << '\0';
484 Emit32(PTHManager::Version);
486 // Leave 4 words for the prologue.
487 Offset PrologueOffset = Out.tell();
488 for (unsigned i = 0; i < 4; ++i)
491 // Write the name of the MainFile.
492 if (!MainFile.empty()) {
493 EmitString(MainFile);
495 // String with 0 bytes.
500 // Iterate over all the files in SourceManager. Create a lexer
501 // for each file and cache the tokens.
502 SourceManager &SM = PP.getSourceManager();
503 const LangOptions &LOpts = PP.getLangOpts();
505 for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(),
506 E = SM.fileinfo_end(); I != E; ++I) {
507 const SrcMgr::ContentCache &C = *I->second;
508 const FileEntry *FE = C.OrigEntry;
510 // FIXME: Handle files with non-absolute paths.
511 if (llvm::sys::path::is_relative(FE->getName()))
514 const llvm::MemoryBuffer *B = C.getBuffer(PP.getDiagnostics(), SM);
517 FileID FID = SM.createFileID(FE, SourceLocation(), SrcMgr::C_User);
518 const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID);
519 Lexer L(FID, FromFile, SM, LOpts);
520 PM.insert(FE, LexTokens(L));
523 // Write out the identifier table.
524 const std::pair<Offset,Offset> &IdTableOff = EmitIdentifierTable();
526 // Write out the cached strings table.
527 Offset SpellingOff = EmitCachedSpellings();
529 // Write out the file table.
530 Offset FileTableOff = EmitFileTable();
532 // Finally, write the prologue.
533 uint64_t Off = PrologueOffset;
534 pwrite32le(Out, IdTableOff.first, Off);
535 pwrite32le(Out, IdTableOff.second, Off);
536 pwrite32le(Out, FileTableOff, Off);
537 pwrite32le(Out, SpellingOff, Off);
541 /// StatListener - A simple "interpose" object used to monitor stat calls
542 /// invoked by FileManager while processing the original sources used
543 /// as input to PTH generation. StatListener populates the PTHWriter's
544 /// file map with stat information for directories as well as negative stats.
545 /// Stat information for files are populated elsewhere.
546 class StatListener : public FileSystemStatCache {
549 StatListener(PTHMap &pm) : PM(pm) {}
550 ~StatListener() override {}
552 LookupResult getStat(const char *Path, FileData &Data, bool isFile,
553 std::unique_ptr<vfs::File> *F,
554 vfs::FileSystem &FS) override {
555 LookupResult Result = statChained(Path, Data, isFile, F, FS);
557 if (Result == CacheMissing) // Failed 'stat'.
558 PM.insert(PTHEntryKeyVariant(Path), PTHEntry());
559 else if (Data.IsDirectory) {
560 // Only cache directories with absolute paths.
561 if (llvm::sys::path::is_relative(Path))
564 PM.insert(PTHEntryKeyVariant(&Data, Path), PTHEntry());
570 } // end anonymous namespace
572 void clang::CacheTokens(Preprocessor &PP, raw_pwrite_stream *OS) {
573 // Get the name of the main file.
574 const SourceManager &SrcMgr = PP.getSourceManager();
575 const FileEntry *MainFile = SrcMgr.getFileEntryForID(SrcMgr.getMainFileID());
576 SmallString<128> MainFilePath(MainFile->getName());
578 llvm::sys::fs::make_absolute(MainFilePath);
580 // Create the PTHWriter.
581 PTHWriter PW(*OS, PP);
583 // Install the 'stat' system call listener in the FileManager.
584 auto StatCacheOwner = llvm::make_unique<StatListener>(PW.getPM());
585 StatListener *StatCache = StatCacheOwner.get();
586 PP.getFileManager().addStatCache(std::move(StatCacheOwner),
587 /*AtBeginning=*/true);
589 // Lex through the entire file. This will populate SourceManager with
590 // all of the header information.
592 PP.EnterMainSourceFile();
593 do { PP.Lex(Tok); } while (Tok.isNot(tok::eof));
595 // Generate the PTH file.
596 PP.getFileManager().removeStatCache(StatCache);
597 PW.GeneratePTH(MainFilePath.str());
600 //===----------------------------------------------------------------------===//
605 const IdentifierInfo* II;
609 class PTHIdentifierTableTrait {
611 typedef PTHIdKey* key_type;
612 typedef key_type key_type_ref;
614 typedef uint32_t data_type;
615 typedef data_type data_type_ref;
617 typedef unsigned hash_value_type;
618 typedef unsigned offset_type;
620 static hash_value_type ComputeHash(PTHIdKey* key) {
621 return llvm::HashString(key->II->getName());
624 static std::pair<unsigned,unsigned>
625 EmitKeyDataLength(raw_ostream& Out, const PTHIdKey* key, uint32_t) {
626 using namespace llvm::support;
627 unsigned n = key->II->getLength() + 1;
628 endian::Writer<little>(Out).write<uint16_t>(n);
629 return std::make_pair(n, sizeof(uint32_t));
632 static void EmitKey(raw_ostream& Out, PTHIdKey* key, unsigned n) {
633 // Record the location of the key data. This is used when generating
634 // the mapping from persistent IDs to strings.
635 key->FileOffset = Out.tell();
636 Out.write(key->II->getNameStart(), n);
639 static void EmitData(raw_ostream& Out, PTHIdKey*, uint32_t pID,
641 using namespace llvm::support;
642 endian::Writer<little>(Out).write<uint32_t>(pID);
645 } // end anonymous namespace
647 /// EmitIdentifierTable - Emits two tables to the PTH file. The first is
648 /// a hashtable mapping from identifier strings to persistent IDs. The second
649 /// is a straight table mapping from persistent IDs to string data (the
650 /// keys of the first table).
652 std::pair<Offset,Offset> PTHWriter::EmitIdentifierTable() {
654 // (1) an inverse map from persistent IDs -> (IdentifierInfo*,Offset)
655 // (2) a map from (IdentifierInfo*, Offset)* -> persistent IDs
657 // Note that we use 'calloc', so all the bytes are 0.
658 PTHIdKey *IIDMap = (PTHIdKey*)calloc(idcount, sizeof(PTHIdKey));
660 // Create the hashtable.
661 llvm::OnDiskChainedHashTableGenerator<PTHIdentifierTableTrait> IIOffMap;
663 // Generate mapping from persistent IDs -> IdentifierInfo*.
664 for (IDMap::iterator I = IM.begin(), E = IM.end(); I != E; ++I) {
665 // Decrement by 1 because we are using a vector for the lookup and
666 // 0 is reserved for NULL.
667 assert(I->second > 0);
668 assert(I->second-1 < idcount);
669 unsigned idx = I->second-1;
671 // Store the mapping from persistent ID to IdentifierInfo*
672 IIDMap[idx].II = I->first;
674 // Store the reverse mapping in a hashtable.
675 IIOffMap.insert(&IIDMap[idx], I->second);
678 // Write out the inverse map first. This causes the PCIDKey entries to
679 // record PTH file offsets for the string data. This is used to write
681 Offset StringTableOffset = IIOffMap.Emit(Out);
683 // Now emit the table mapping from persistent IDs to PTH file offsets.
684 Offset IDOff = Out.tell();
685 Emit32(idcount); // Emit the number of identifiers.
686 for (unsigned i = 0 ; i < idcount; ++i)
687 Emit32(IIDMap[i].FileOffset);
689 // Finally, release the inverse map.
692 return std::make_pair(IDOff, StringTableOffset);