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