CacheTokens.cpp revision b1c86492f9a9bef01a4567408c22f961bbd604fe
1//===--- CacheTokens.cpp - Caching of lexer tokens for PTH support --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This provides a possible implementation of PTH support for Clang that is 11// based on caching lexed tokens and identifiers. 12// 13//===----------------------------------------------------------------------===// 14 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" 30 31// FIXME: put this somewhere else? 32#ifndef S_ISDIR 33#define S_ISDIR(x) (((x)&_S_IFDIR)!=0) 34#endif 35 36using namespace clang; 37using namespace clang::io; 38 39//===----------------------------------------------------------------------===// 40// PTH-specific stuff. 41//===----------------------------------------------------------------------===// 42 43namespace { 44class PTHEntry { 45 Offset TokenData, PPCondData; 46 47public: 48 PTHEntry() {} 49 50 PTHEntry(Offset td, Offset ppcd) 51 : TokenData(td), PPCondData(ppcd) {} 52 53 Offset getTokenOffset() const { return TokenData; } 54 Offset getPPCondTableOffset() const { return PPCondData; } 55}; 56 57 58class PTHEntryKeyVariant { 59 union { const FileEntry* FE; const char* Path; }; 60 enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind; 61 struct stat *StatBuf; 62public: 63 PTHEntryKeyVariant(const FileEntry *fe) 64 : FE(fe), Kind(IsFE), StatBuf(0) {} 65 66 PTHEntryKeyVariant(struct stat* statbuf, const char* path) 67 : Path(path), Kind(IsDE), StatBuf(new struct stat(*statbuf)) {} 68 69 explicit PTHEntryKeyVariant(const char* path) 70 : Path(path), Kind(IsNoExist), StatBuf(0) {} 71 72 bool isFile() const { return Kind == IsFE; } 73 74 llvm::StringRef getString() const { 75 return Kind == IsFE ? FE->getName() : Path; 76 } 77 78 unsigned getKind() const { return (unsigned) Kind; } 79 80 void EmitData(llvm::raw_ostream& Out) { 81 switch (Kind) { 82 case IsFE: 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()); 89 break; 90 case IsDE: 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); 97 delete StatBuf; 98 break; 99 default: 100 break; 101 } 102 } 103 104 unsigned getRepresentationLength() const { 105 return Kind == IsNoExist ? 0 : 4 + 4 + 2 + 8 + 8; 106 } 107}; 108 109class FileEntryPTHEntryInfo { 110public: 111 typedef PTHEntryKeyVariant key_type; 112 typedef key_type key_type_ref; 113 114 typedef PTHEntry data_type; 115 typedef const PTHEntry& data_type_ref; 116 117 static unsigned ComputeHash(PTHEntryKeyVariant V) { 118 return llvm::HashString(V.getString()); 119 } 120 121 static std::pair<unsigned,unsigned> 122 EmitKeyDataLength(llvm::raw_ostream& Out, PTHEntryKeyVariant V, 123 const PTHEntry& E) { 124 125 unsigned n = V.getString().size() + 1 + 1; 126 ::Emit16(Out, n); 127 128 unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0); 129 ::Emit8(Out, m); 130 131 return std::make_pair(n, m); 132 } 133 134 static void EmitKey(llvm::raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){ 135 // Emit the entry kind. 136 ::Emit8(Out, (unsigned) V.getKind()); 137 // Emit the string. 138 Out.write(V.getString().data(), n - 1); 139 } 140 141 static void EmitData(llvm::raw_ostream& Out, PTHEntryKeyVariant V, 142 const PTHEntry& E, unsigned) { 143 144 145 // For file entries emit the offsets into the PTH file for token data 146 // and the preprocessor blocks table. 147 if (V.isFile()) { 148 ::Emit32(Out, E.getTokenOffset()); 149 ::Emit32(Out, E.getPPCondTableOffset()); 150 } 151 152 // Emit any other data associated with the key (i.e., stat information). 153 V.EmitData(Out); 154 } 155}; 156 157class OffsetOpt { 158 bool valid; 159 Offset off; 160public: 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; } 165}; 166} // end anonymous namespace 167 168typedef OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap; 169 170namespace { 171class PTHWriter { 172 typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap; 173 typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy; 174 175 IDMap IM; 176 llvm::raw_fd_ostream& Out; 177 Preprocessor& PP; 178 uint32_t idcount; 179 PTHMap PM; 180 CachedStrsTy CachedStrs; 181 Offset CurStrOffset; 182 std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries; 183 184 //// Get the persistent id for the given IdentifierInfo*. 185 uint32_t ResolveID(const IdentifierInfo* II); 186 187 /// Emit a token to the PTH file. 188 void EmitToken(const Token& T); 189 190 void Emit8(uint32_t V) { ::Emit8(Out, V); } 191 192 void Emit16(uint32_t V) { ::Emit16(Out, V); } 193 194 void Emit32(uint32_t V) { ::Emit32(Out, V); } 195 196 void EmitBuf(const char *Ptr, unsigned NumBytes) { 197 Out.write(Ptr, NumBytes); 198 } 199 200 void EmitString(llvm::StringRef V) { 201 ::Emit16(Out, V.size()); 202 EmitBuf(V.data(), V.size()); 203 } 204 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(); 210 211 /// EmitFileTable - Emit a table mapping from file name strings to PTH 212 /// token data. 213 Offset EmitFileTable() { return PM.Emit(Out); } 214 215 PTHEntry LexTokens(Lexer& L); 216 Offset EmitCachedSpellings(); 217 218public: 219 PTHWriter(llvm::raw_fd_ostream& out, Preprocessor& pp) 220 : Out(out), PP(pp), idcount(0), CurStrOffset(0) {} 221 222 PTHMap &getPM() { return PM; } 223 void GeneratePTH(const std::string &MainFile); 224}; 225} // end anonymous namespace 226 227uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) { 228 // Null IdentifierInfo's map to the persistent ID 0. 229 if (!II) 230 return 0; 231 232 IDMap::iterator I = IM.find(II); 233 if (I != IM.end()) 234 return I->second; // We've already added 1. 235 236 IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL. 237 return idcount; 238} 239 240void 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)); 244 245 if (!T.isLiteral()) { 246 Emit32(ResolveID(T.getIdentifierInfo())); 247 } else { 248 // We cache *un-cleaned* spellings. This gives us 100% fidelity with the 249 // source code. 250 const char* s = T.getLiteralData(); 251 unsigned len = T.getLength(); 252 253 // Get the string entry. 254 llvm::StringMapEntry<OffsetOpt> *E = &CachedStrs.GetOrCreateValue(s, s+len); 255 256 // If this is a new string entry, bump the PTH offset. 257 if (!E->getValue().hasOffset()) { 258 E->getValue().setOffset(CurStrOffset); 259 StrEntries.push_back(E); 260 CurStrOffset += len + 1; 261 } 262 263 // Emit the relative offset into the PTH file for the spelling string. 264 Emit32(E->getValue().getOffset()); 265 } 266 267 // Emit the offset into the original source file of this token so that we 268 // can reconstruct its SourceLocation. 269 Emit32(PP.getSourceManager().getFileOffset(T.getLocation())); 270} 271 272PTHEntry PTHWriter::LexTokens(Lexer& L) { 273 // Pad 0's so that we emit tokens to a 4-byte alignment. 274 // This speed up reading them back in. 275 Pad(Out, 4); 276 Offset TokenOff = (Offset) Out.tell(); 277 278 // Keep track of matching '#if' ... '#endif'. 279 typedef std::vector<std::pair<Offset, unsigned> > PPCondTable; 280 PPCondTable PPCond; 281 std::vector<unsigned> PPStartCond; 282 bool ParsingPreprocessorDirective = false; 283 Token Tok; 284 285 do { 286 L.LexFromRawLexer(Tok); 287 NextToken: 288 289 if ((Tok.isAtStartOfLine() || Tok.is(tok::eof)) && 290 ParsingPreprocessorDirective) { 291 // Insert an eod token into the token cache. It has the same 292 // position as the next token that is not on the same line as the 293 // preprocessor directive. Observe that we continue processing 294 // 'Tok' when we exit this branch. 295 Token Tmp = Tok; 296 Tmp.setKind(tok::eod); 297 Tmp.clearFlag(Token::StartOfLine); 298 Tmp.setIdentifierInfo(0); 299 EmitToken(Tmp); 300 ParsingPreprocessorDirective = false; 301 } 302 303 if (Tok.is(tok::raw_identifier)) { 304 PP.LookUpIdentifierInfo(Tok); 305 EmitToken(Tok); 306 continue; 307 } 308 309 if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) { 310 // Special processing for #include. Store the '#' token and lex 311 // the next token. 312 assert(!ParsingPreprocessorDirective); 313 Offset HashOff = (Offset) Out.tell(); 314 315 // Get the next token. 316 Token NextTok; 317 L.LexFromRawLexer(NextTok); 318 319 // If we see the start of line, then we had a null directive "#". In 320 // this case, discard both tokens. 321 if (NextTok.isAtStartOfLine()) 322 goto NextToken; 323 324 // The token is the start of a directive. Emit it. 325 EmitToken(Tok); 326 Tok = NextTok; 327 328 // Did we see 'include'/'import'/'include_next'? 329 if (Tok.isNot(tok::raw_identifier)) { 330 EmitToken(Tok); 331 continue; 332 } 333 334 IdentifierInfo* II = PP.LookUpIdentifierInfo(Tok); 335 tok::PPKeywordKind K = II->getPPKeywordID(); 336 337 ParsingPreprocessorDirective = true; 338 339 switch (K) { 340 case tok::pp_not_keyword: 341 // Invalid directives "#foo" can occur in #if 0 blocks etc, just pass 342 // them through. 343 default: 344 break; 345 346 case tok::pp_include: 347 case tok::pp_import: 348 case tok::pp_include_next: { 349 // Save the 'include' token. 350 EmitToken(Tok); 351 // Lex the next token as an include string. 352 L.setParsingPreprocessorDirective(true); 353 L.LexIncludeFilename(Tok); 354 L.setParsingPreprocessorDirective(false); 355 assert(!Tok.isAtStartOfLine()); 356 if (Tok.is(tok::raw_identifier)) 357 PP.LookUpIdentifierInfo(Tok); 358 359 break; 360 } 361 case tok::pp_if: 362 case tok::pp_ifdef: 363 case tok::pp_ifndef: { 364 // Add an entry for '#if' and friends. We initially set the target 365 // index to 0. This will get backpatched when we hit #endif. 366 PPStartCond.push_back(PPCond.size()); 367 PPCond.push_back(std::make_pair(HashOff, 0U)); 368 break; 369 } 370 case tok::pp_endif: { 371 // Add an entry for '#endif'. We set the target table index to itself. 372 // This will later be set to zero when emitting to the PTH file. We 373 // use 0 for uninitialized indices because that is easier to debug. 374 unsigned index = PPCond.size(); 375 // Backpatch the opening '#if' entry. 376 assert(!PPStartCond.empty()); 377 assert(PPCond.size() > PPStartCond.back()); 378 assert(PPCond[PPStartCond.back()].second == 0); 379 PPCond[PPStartCond.back()].second = index; 380 PPStartCond.pop_back(); 381 // Add the new entry to PPCond. 382 PPCond.push_back(std::make_pair(HashOff, index)); 383 EmitToken(Tok); 384 385 // Some files have gibberish on the same line as '#endif'. 386 // Discard these tokens. 387 do 388 L.LexFromRawLexer(Tok); 389 while (Tok.isNot(tok::eof) && !Tok.isAtStartOfLine()); 390 // We have the next token in hand. 391 // Don't immediately lex the next one. 392 goto NextToken; 393 } 394 case tok::pp_elif: 395 case tok::pp_else: { 396 // Add an entry for #elif or #else. 397 // This serves as both a closing and opening of a conditional block. 398 // This means that its entry will get backpatched later. 399 unsigned index = PPCond.size(); 400 // Backpatch the previous '#if' entry. 401 assert(!PPStartCond.empty()); 402 assert(PPCond.size() > PPStartCond.back()); 403 assert(PPCond[PPStartCond.back()].second == 0); 404 PPCond[PPStartCond.back()].second = index; 405 PPStartCond.pop_back(); 406 // Now add '#elif' as a new block opening. 407 PPCond.push_back(std::make_pair(HashOff, 0U)); 408 PPStartCond.push_back(index); 409 break; 410 } 411 } 412 } 413 414 EmitToken(Tok); 415 } 416 while (Tok.isNot(tok::eof)); 417 418 assert(PPStartCond.empty() && "Error: imblanced preprocessor conditionals."); 419 420 // Next write out PPCond. 421 Offset PPCondOff = (Offset) Out.tell(); 422 423 // Write out the size of PPCond so that clients can identifer empty tables. 424 Emit32(PPCond.size()); 425 426 for (unsigned i = 0, e = PPCond.size(); i!=e; ++i) { 427 Emit32(PPCond[i].first - TokenOff); 428 uint32_t x = PPCond[i].second; 429 assert(x != 0 && "PPCond entry not backpatched."); 430 // Emit zero for #endifs. This allows us to do checking when 431 // we read the PTH file back in. 432 Emit32(x == i ? 0 : x); 433 } 434 435 return PTHEntry(TokenOff, PPCondOff); 436} 437 438Offset PTHWriter::EmitCachedSpellings() { 439 // Write each cached strings to the PTH file. 440 Offset SpellingsOff = Out.tell(); 441 442 for (std::vector<llvm::StringMapEntry<OffsetOpt>*>::iterator 443 I = StrEntries.begin(), E = StrEntries.end(); I!=E; ++I) 444 EmitBuf((*I)->getKeyData(), (*I)->getKeyLength()+1 /*nul included*/); 445 446 return SpellingsOff; 447} 448 449void PTHWriter::GeneratePTH(const std::string &MainFile) { 450 // Generate the prologue. 451 Out << "cfe-pth"; 452 Emit32(PTHManager::Version); 453 454 // Leave 4 words for the prologue. 455 Offset PrologueOffset = Out.tell(); 456 for (unsigned i = 0; i < 4; ++i) 457 Emit32(0); 458 459 // Write the name of the MainFile. 460 if (!MainFile.empty()) { 461 EmitString(MainFile); 462 } else { 463 // String with 0 bytes. 464 Emit16(0); 465 } 466 Emit8(0); 467 468 // Iterate over all the files in SourceManager. Create a lexer 469 // for each file and cache the tokens. 470 SourceManager &SM = PP.getSourceManager(); 471 const LangOptions &LOpts = PP.getLangOptions(); 472 473 for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(), 474 E = SM.fileinfo_end(); I != E; ++I) { 475 const SrcMgr::ContentCache &C = *I->second; 476 const FileEntry *FE = C.OrigEntry; 477 478 // FIXME: Handle files with non-absolute paths. 479 if (llvm::sys::path::is_relative(FE->getName())) 480 continue; 481 482 const llvm::MemoryBuffer *B = C.getBuffer(PP.getDiagnostics(), SM); 483 if (!B) continue; 484 485 FileID FID = SM.createFileID(FE, SourceLocation(), SrcMgr::C_User); 486 const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID); 487 Lexer L(FID, FromFile, SM, LOpts); 488 PM.insert(FE, LexTokens(L)); 489 } 490 491 // Write out the identifier table. 492 const std::pair<Offset,Offset> &IdTableOff = EmitIdentifierTable(); 493 494 // Write out the cached strings table. 495 Offset SpellingOff = EmitCachedSpellings(); 496 497 // Write out the file table. 498 Offset FileTableOff = EmitFileTable(); 499 500 // Finally, write the prologue. 501 Out.seek(PrologueOffset); 502 Emit32(IdTableOff.first); 503 Emit32(IdTableOff.second); 504 Emit32(FileTableOff); 505 Emit32(SpellingOff); 506} 507 508namespace { 509/// StatListener - A simple "interpose" object used to monitor stat calls 510/// invoked by FileManager while processing the original sources used 511/// as input to PTH generation. StatListener populates the PTHWriter's 512/// file map with stat information for directories as well as negative stats. 513/// Stat information for files are populated elsewhere. 514class StatListener : public FileSystemStatCache { 515 PTHMap &PM; 516public: 517 StatListener(PTHMap &pm) : PM(pm) {} 518 ~StatListener() {} 519 520 LookupResult getStat(const char *Path, struct stat &StatBuf, 521 int *FileDescriptor) { 522 LookupResult Result = statChained(Path, StatBuf, FileDescriptor); 523 524 if (Result == CacheMissing) // Failed 'stat'. 525 PM.insert(PTHEntryKeyVariant(Path), PTHEntry()); 526 else if (S_ISDIR(StatBuf.st_mode)) { 527 // Only cache directories with absolute paths. 528 if (llvm::sys::path::is_relative(Path)) 529 return Result; 530 531 PM.insert(PTHEntryKeyVariant(&StatBuf, Path), PTHEntry()); 532 } 533 534 return Result; 535 } 536}; 537} // end anonymous namespace 538 539 540void clang::CacheTokens(Preprocessor &PP, llvm::raw_fd_ostream* OS) { 541 // Get the name of the main file. 542 const SourceManager &SrcMgr = PP.getSourceManager(); 543 const FileEntry *MainFile = SrcMgr.getFileEntryForID(SrcMgr.getMainFileID()); 544 llvm::SmallString<128> MainFilePath(MainFile->getName()); 545 546 llvm::sys::fs::make_absolute(MainFilePath); 547 548 // Create the PTHWriter. 549 PTHWriter PW(*OS, PP); 550 551 // Install the 'stat' system call listener in the FileManager. 552 StatListener *StatCache = new StatListener(PW.getPM()); 553 PP.getFileManager().addStatCache(StatCache, /*AtBeginning=*/true); 554 555 // Lex through the entire file. This will populate SourceManager with 556 // all of the header information. 557 Token Tok; 558 PP.EnterMainSourceFile(); 559 do { PP.Lex(Tok); } while (Tok.isNot(tok::eof)); 560 561 // Generate the PTH file. 562 PP.getFileManager().removeStatCache(StatCache); 563 PW.GeneratePTH(MainFilePath.str()); 564} 565 566//===----------------------------------------------------------------------===// 567 568namespace { 569class PTHIdKey { 570public: 571 const IdentifierInfo* II; 572 uint32_t FileOffset; 573}; 574 575class PTHIdentifierTableTrait { 576public: 577 typedef PTHIdKey* key_type; 578 typedef key_type key_type_ref; 579 580 typedef uint32_t data_type; 581 typedef data_type data_type_ref; 582 583 static unsigned ComputeHash(PTHIdKey* key) { 584 return llvm::HashString(key->II->getName()); 585 } 586 587 static std::pair<unsigned,unsigned> 588 EmitKeyDataLength(llvm::raw_ostream& Out, const PTHIdKey* key, uint32_t) { 589 unsigned n = key->II->getLength() + 1; 590 ::Emit16(Out, n); 591 return std::make_pair(n, sizeof(uint32_t)); 592 } 593 594 static void EmitKey(llvm::raw_ostream& Out, PTHIdKey* key, unsigned n) { 595 // Record the location of the key data. This is used when generating 596 // the mapping from persistent IDs to strings. 597 key->FileOffset = Out.tell(); 598 Out.write(key->II->getNameStart(), n); 599 } 600 601 static void EmitData(llvm::raw_ostream& Out, PTHIdKey*, uint32_t pID, 602 unsigned) { 603 ::Emit32(Out, pID); 604 } 605}; 606} // end anonymous namespace 607 608/// EmitIdentifierTable - Emits two tables to the PTH file. The first is 609/// a hashtable mapping from identifier strings to persistent IDs. The second 610/// is a straight table mapping from persistent IDs to string data (the 611/// keys of the first table). 612/// 613std::pair<Offset,Offset> PTHWriter::EmitIdentifierTable() { 614 // Build two maps: 615 // (1) an inverse map from persistent IDs -> (IdentifierInfo*,Offset) 616 // (2) a map from (IdentifierInfo*, Offset)* -> persistent IDs 617 618 // Note that we use 'calloc', so all the bytes are 0. 619 PTHIdKey *IIDMap = (PTHIdKey*)calloc(idcount, sizeof(PTHIdKey)); 620 621 // Create the hashtable. 622 OnDiskChainedHashTableGenerator<PTHIdentifierTableTrait> IIOffMap; 623 624 // Generate mapping from persistent IDs -> IdentifierInfo*. 625 for (IDMap::iterator I = IM.begin(), E = IM.end(); I != E; ++I) { 626 // Decrement by 1 because we are using a vector for the lookup and 627 // 0 is reserved for NULL. 628 assert(I->second > 0); 629 assert(I->second-1 < idcount); 630 unsigned idx = I->second-1; 631 632 // Store the mapping from persistent ID to IdentifierInfo* 633 IIDMap[idx].II = I->first; 634 635 // Store the reverse mapping in a hashtable. 636 IIOffMap.insert(&IIDMap[idx], I->second); 637 } 638 639 // Write out the inverse map first. This causes the PCIDKey entries to 640 // record PTH file offsets for the string data. This is used to write 641 // the second table. 642 Offset StringTableOffset = IIOffMap.Emit(Out); 643 644 // Now emit the table mapping from persistent IDs to PTH file offsets. 645 Offset IDOff = Out.tell(); 646 Emit32(idcount); // Emit the number of identifiers. 647 for (unsigned i = 0 ; i < idcount; ++i) 648 Emit32(IIDMap[i].FileOffset); 649 650 // Finally, release the inverse map. 651 free(IIDMap); 652 653 return std::make_pair(IDOff, StringTableOffset); 654} 655