PTHLexer.cpp revision f02f6f0ee3e05b958bcf67f00f4503671d67eccd
1//===--- PTHLexer.cpp - Lex from a token stream ---------------------------===// 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 file implements the PTHLexer interface. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Basic/TokenKinds.h" 15#include "clang/Basic/FileManager.h" 16#include "clang/Basic/IdentifierTable.h" 17#include "clang/Lex/PTHLexer.h" 18#include "clang/Lex/Preprocessor.h" 19#include "clang/Lex/PTHManager.h" 20#include "clang/Lex/Token.h" 21#include "clang/Lex/Preprocessor.h" 22#include "llvm/Support/Compiler.h" 23#include "llvm/Support/MemoryBuffer.h" 24#include "llvm/ADT/StringMap.h" 25#include "llvm/ADT/OwningPtr.h" 26 27using namespace clang; 28 29#define DISK_TOKEN_SIZE (1+1+3+4+2) 30 31//===----------------------------------------------------------------------===// 32// Utility methods for reading from the mmap'ed PTH file. 33//===----------------------------------------------------------------------===// 34 35static inline uint8_t Read8(const char*& data) { 36 return (uint8_t) *(data++); 37} 38 39static inline uint32_t Read32(const char*& data) { 40 uint32_t V = (uint32_t) Read8(data); 41 V |= (((uint32_t) Read8(data)) << 8); 42 V |= (((uint32_t) Read8(data)) << 16); 43 V |= (((uint32_t) Read8(data)) << 24); 44 return V; 45} 46 47//===----------------------------------------------------------------------===// 48// PTHLexer methods. 49//===----------------------------------------------------------------------===// 50 51PTHLexer::PTHLexer(Preprocessor& pp, SourceLocation fileloc, const char* D, 52 const char* ppcond, 53 PTHSpellingSearch& mySpellingSrch, 54 PTHManager& PM) 55 : PreprocessorLexer(&pp, fileloc), TokBuf(D), CurPtr(D), LastHashTokPtr(0), 56 PPCond(ppcond), CurPPCondPtr(ppcond), MySpellingSrch(mySpellingSrch), 57 PTHMgr(PM) 58{ 59 FileID = fileloc.getFileID(); 60} 61 62void PTHLexer::Lex(Token& Tok) { 63LexNextToken: 64 65 //===--------------------------------------==// 66 // Read the raw token data. 67 //===--------------------------------------==// 68 69 // Shadow CurPtr into an automatic variable. 70 const unsigned char *CurPtrShadow = (const unsigned char*) CurPtr; 71 72 // Read in the data for the token. 14 bytes in total. 73 tok::TokenKind k = (tok::TokenKind) CurPtrShadow[0]; 74 Token::TokenFlags flags = (Token::TokenFlags) CurPtrShadow[1]; 75 76 uint32_t perID = ((uint32_t) CurPtrShadow[2]) 77 | (((uint32_t) CurPtrShadow[3]) << 8) 78 | (((uint32_t) CurPtrShadow[4]) << 16); 79 80 uint32_t FileOffset = ((uint32_t) CurPtrShadow[5]) 81 | (((uint32_t) CurPtrShadow[6]) << 8) 82 | (((uint32_t) CurPtrShadow[7]) << 16) 83 | (((uint32_t) CurPtrShadow[8]) << 24); 84 85 uint32_t Len = ((uint32_t) CurPtrShadow[9]) 86 | (((uint32_t) CurPtrShadow[10]) << 8); 87 88 CurPtr = (const char*) (CurPtrShadow + DISK_TOKEN_SIZE); 89 90 //===--------------------------------------==// 91 // Construct the token itself. 92 //===--------------------------------------==// 93 94 Tok.startToken(); 95 Tok.setKind(k); 96 Tok.setFlag(flags); 97 assert(!LexingRawMode); 98 Tok.setIdentifierInfo(perID ? PTHMgr.GetIdentifierInfo(perID-1) : 0); 99 Tok.setLocation(SourceLocation::getFileLoc(FileID, FileOffset)); 100 Tok.setLength(Len); 101 102 //===--------------------------------------==// 103 // Process the token. 104 //===--------------------------------------==// 105#if 0 106 SourceManager& SM = PP->getSourceManager(); 107 llvm::cerr << SM.getFileEntryForID(FileID)->getName() 108 << ':' << SM.getLogicalLineNumber(Tok.getLocation()) 109 << ':' << SM.getLogicalColumnNumber(Tok.getLocation()) 110 << '\n'; 111#endif 112 113 if (k == tok::identifier) { 114 MIOpt.ReadToken(); 115 return PP->HandleIdentifier(Tok); 116 } 117 118 if (k == tok::eof) { 119 // Save the end-of-file token. 120 EofToken = Tok; 121 122 Preprocessor *PPCache = PP; 123 124 assert(!ParsingPreprocessorDirective); 125 assert(!LexingRawMode); 126 127 // FIXME: Issue diagnostics similar to Lexer. 128 if (PP->HandleEndOfFile(Tok, false)) 129 return; 130 131 assert(PPCache && "Raw buffer::LexEndOfFile should return a token"); 132 return PPCache->Lex(Tok); 133 } 134 135 if (k == tok::hash && Tok.isAtStartOfLine()) { 136 LastHashTokPtr = CurPtr - DISK_TOKEN_SIZE; 137 assert(!LexingRawMode); 138 PP->HandleDirective(Tok); 139 140 if (PP->isCurrentLexer(this)) 141 goto LexNextToken; 142 143 return PP->Lex(Tok); 144 } 145 146 if (k == tok::eom) { 147 assert(ParsingPreprocessorDirective); 148 ParsingPreprocessorDirective = false; 149 return; 150 } 151 152 MIOpt.ReadToken(); 153} 154 155// FIXME: We can just grab the last token instead of storing a copy 156// into EofToken. 157void PTHLexer::getEOF(Token& Tok) { 158 assert(EofToken.is(tok::eof)); 159 Tok = EofToken; 160} 161 162void PTHLexer::DiscardToEndOfLine() { 163 assert(ParsingPreprocessorDirective && ParsingFilename == false && 164 "Must be in a preprocessing directive!"); 165 166 // We assume that if the preprocessor wishes to discard to the end of 167 // the line that it also means to end the current preprocessor directive. 168 ParsingPreprocessorDirective = false; 169 170 // Skip tokens by only peeking at their token kind and the flags. 171 // We don't need to actually reconstruct full tokens from the token buffer. 172 // This saves some copies and it also reduces IdentifierInfo* lookup. 173 const char* p = CurPtr; 174 while (1) { 175 // Read the token kind. Are we at the end of the file? 176 tok::TokenKind x = (tok::TokenKind) (uint8_t) *p; 177 if (x == tok::eof) break; 178 179 // Read the token flags. Are we at the start of the next line? 180 Token::TokenFlags y = (Token::TokenFlags) (uint8_t) p[1]; 181 if (y & Token::StartOfLine) break; 182 183 // Skip to the next token. 184 p += DISK_TOKEN_SIZE; 185 } 186 187 CurPtr = p; 188} 189 190/// SkipBlock - Used by Preprocessor to skip the current conditional block. 191bool PTHLexer::SkipBlock() { 192 assert(CurPPCondPtr && "No cached PP conditional information."); 193 assert(LastHashTokPtr && "No known '#' token."); 194 195 const char* HashEntryI = 0; 196 uint32_t Offset; 197 uint32_t TableIdx; 198 199 do { 200 // Read the token offset from the side-table. 201 Offset = Read32(CurPPCondPtr); 202 203 // Read the target table index from the side-table. 204 TableIdx = Read32(CurPPCondPtr); 205 206 // Compute the actual memory address of the '#' token data for this entry. 207 HashEntryI = TokBuf + Offset; 208 209 // Optmization: "Sibling jumping". #if...#else...#endif blocks can 210 // contain nested blocks. In the side-table we can jump over these 211 // nested blocks instead of doing a linear search if the next "sibling" 212 // entry is not at a location greater than LastHashTokPtr. 213 if (HashEntryI < LastHashTokPtr && TableIdx) { 214 // In the side-table we are still at an entry for a '#' token that 215 // is earlier than the last one we saw. Check if the location we would 216 // stride gets us closer. 217 const char* NextPPCondPtr = PPCond + TableIdx*(sizeof(uint32_t)*2); 218 assert(NextPPCondPtr >= CurPPCondPtr); 219 // Read where we should jump to. 220 uint32_t TmpOffset = Read32(NextPPCondPtr); 221 const char* HashEntryJ = TokBuf + TmpOffset; 222 223 if (HashEntryJ <= LastHashTokPtr) { 224 // Jump directly to the next entry in the side table. 225 HashEntryI = HashEntryJ; 226 Offset = TmpOffset; 227 TableIdx = Read32(NextPPCondPtr); 228 CurPPCondPtr = NextPPCondPtr; 229 } 230 } 231 } 232 while (HashEntryI < LastHashTokPtr); 233 assert(HashEntryI == LastHashTokPtr && "No PP-cond entry found for '#'"); 234 assert(TableIdx && "No jumping from #endifs."); 235 236 // Update our side-table iterator. 237 const char* NextPPCondPtr = PPCond + TableIdx*(sizeof(uint32_t)*2); 238 assert(NextPPCondPtr >= CurPPCondPtr); 239 CurPPCondPtr = NextPPCondPtr; 240 241 // Read where we should jump to. 242 HashEntryI = TokBuf + Read32(NextPPCondPtr); 243 uint32_t NextIdx = Read32(NextPPCondPtr); 244 245 // By construction NextIdx will be zero if this is a #endif. This is useful 246 // to know to obviate lexing another token. 247 bool isEndif = NextIdx == 0; 248 249 // This case can occur when we see something like this: 250 // 251 // #if ... 252 // /* a comment or nothing */ 253 // #elif 254 // 255 // If we are skipping the first #if block it will be the case that CurPtr 256 // already points 'elif'. Just return. 257 258 if (CurPtr > HashEntryI) { 259 assert(CurPtr == HashEntryI + DISK_TOKEN_SIZE); 260 // Did we reach a #endif? If so, go ahead and consume that token as well. 261 if (isEndif) 262 CurPtr += DISK_TOKEN_SIZE*2; 263 else 264 LastHashTokPtr = HashEntryI; 265 266 return isEndif; 267 } 268 269 // Otherwise, we need to advance. Update CurPtr to point to the '#' token. 270 CurPtr = HashEntryI; 271 272 // Update the location of the last observed '#'. This is useful if we 273 // are skipping multiple blocks. 274 LastHashTokPtr = CurPtr; 275 276 // Skip the '#' token. 277 assert(((tok::TokenKind) (unsigned char) *CurPtr) == tok::hash); 278 CurPtr += DISK_TOKEN_SIZE; 279 280 // Did we reach a #endif? If so, go ahead and consume that token as well. 281 if (isEndif) { CurPtr += DISK_TOKEN_SIZE*2; } 282 283 return isEndif; 284} 285 286SourceLocation PTHLexer::getSourceLocation() { 287 // getLocation is not on the hot path. It is used to get the location of 288 // the next token when transitioning back to this lexer when done 289 // handling a #included file. Just read the necessary data from the token 290 // data buffer to construct the SourceLocation object. 291 // NOTE: This is a virtual function; hence it is defined out-of-line. 292 const char* p = CurPtr + (1 + 1 + 3); 293 uint32_t offset = 294 ((uint32_t) ((uint8_t) p[0])) 295 | (((uint32_t) ((uint8_t) p[1])) << 8) 296 | (((uint32_t) ((uint8_t) p[2])) << 16) 297 | (((uint32_t) ((uint8_t) p[3])) << 24); 298 return SourceLocation::getFileLoc(FileID, offset); 299} 300 301//===----------------------------------------------------------------------===// 302// getSpelling() - Use cached data in PTH files for getSpelling(). 303//===----------------------------------------------------------------------===// 304 305unsigned PTHManager::getSpelling(unsigned FileID, unsigned fpos, 306 const char *& Buffer) { 307 308 llvm::DenseMap<unsigned,PTHSpellingSearch*>::iterator I = 309 SpellingMap.find(FileID); 310 311 if (I == SpellingMap.end()) 312 return 0; 313 314 return I->second->getSpellingBinarySearch(fpos, Buffer); 315} 316 317unsigned PTHManager::getSpellingAtPTHOffset(unsigned PTHOffset, 318 const char *& Buffer) { 319 320 const char* p = Buf->getBufferStart() + PTHOffset; 321 assert(p < Buf->getBufferEnd()); 322 323 // The string is prefixed by 16 bits for its length, followed by the string 324 // itself. 325 unsigned len = ((unsigned) ((uint8_t) p[0])) 326 | (((unsigned) ((uint8_t) p[1])) << 8); 327 328 Buffer = p + 2; 329 return len; 330} 331 332unsigned PTHSpellingSearch::getSpellingLinearSearch(unsigned fpos, 333 const char *&Buffer) { 334 const char* p = LinearItr; 335 unsigned len = 0; 336 337 if (p == TableEnd) 338 return getSpellingBinarySearch(fpos, Buffer); 339 340 do { 341 uint32_t TokOffset = 342 ((uint32_t) ((uint8_t) p[0])) 343 | (((uint32_t) ((uint8_t) p[1])) << 8) 344 | (((uint32_t) ((uint8_t) p[2])) << 16) 345 | (((uint32_t) ((uint8_t) p[3])) << 24); 346 347 if (TokOffset > fpos) 348 return getSpellingBinarySearch(fpos, Buffer); 349 350 // Did we find a matching token offset for this spelling? 351 if (TokOffset == fpos) { 352 uint32_t SpellingPTHOffset = 353 ((uint32_t) ((uint8_t) p[4])) 354 | (((uint32_t) ((uint8_t) p[5])) << 8) 355 | (((uint32_t) ((uint8_t) p[6])) << 16) 356 | (((uint32_t) ((uint8_t) p[7])) << 24); 357 358 p += SpellingEntrySize; 359 len = PTHMgr.getSpellingAtPTHOffset(SpellingPTHOffset, Buffer); 360 break; 361 } 362 363 // No match. Keep on looking. 364 p += SpellingEntrySize; 365 } 366 while (p != TableEnd); 367 368 LinearItr = p; 369 return len; 370} 371 372unsigned PTHSpellingSearch::getSpellingBinarySearch(unsigned fpos, 373 const char *& Buffer) { 374 375 assert((TableEnd - TableBeg) % SpellingEntrySize == 0); 376 377 if (TableEnd == TableBeg) 378 return 0; 379 380 assert(TableEnd > TableBeg); 381 382 unsigned min = 0; 383 const char* tb = TableBeg; 384 unsigned max = NumSpellings; 385 386 do { 387 unsigned i = (max - min) / 2 + min; 388 const char* p = tb + (i * SpellingEntrySize); 389 390 uint32_t TokOffset = 391 ((uint32_t) ((uint8_t) p[0])) 392 | (((uint32_t) ((uint8_t) p[1])) << 8) 393 | (((uint32_t) ((uint8_t) p[2])) << 16) 394 | (((uint32_t) ((uint8_t) p[3])) << 24); 395 396 if (TokOffset > fpos) { 397 max = i; 398 assert(!(max == min) || (min == i)); 399 continue; 400 } 401 402 if (TokOffset < fpos) { 403 min = i; 404 continue; 405 } 406 407 uint32_t SpellingPTHOffset = 408 ((uint32_t) ((uint8_t) p[4])) 409 | (((uint32_t) ((uint8_t) p[5])) << 8) 410 | (((uint32_t) ((uint8_t) p[6])) << 16) 411 | (((uint32_t) ((uint8_t) p[7])) << 24); 412 413 return PTHMgr.getSpellingAtPTHOffset(SpellingPTHOffset, Buffer); 414 } 415 while (min != max); 416 417 return 0; 418} 419 420unsigned PTHLexer::getSpelling(SourceLocation sloc, const char *&Buffer) { 421 SourceManager& SM = PP->getSourceManager(); 422 sloc = SM.getPhysicalLoc(sloc); 423 unsigned fid = sloc.getFileID(); 424 unsigned fpos = SM.getFullFilePos(sloc); 425 426 return (fid == FileID ) ? MySpellingSrch.getSpellingLinearSearch(fpos, Buffer) 427 : PTHMgr.getSpelling(fid, fpos, Buffer); 428} 429 430//===----------------------------------------------------------------------===// 431// Internal Data Structures for PTH file lookup and resolving identifiers. 432//===----------------------------------------------------------------------===// 433 434 435/// PTHFileLookup - This internal data structure is used by the PTHManager 436/// to map from FileEntry objects managed by FileManager to offsets within 437/// the PTH file. 438namespace { 439class VISIBILITY_HIDDEN PTHFileLookup { 440public: 441 class Val { 442 uint32_t TokenOff; 443 uint32_t PPCondOff; 444 uint32_t SpellingOff; 445 446 public: 447 Val() : TokenOff(~0) {} 448 Val(uint32_t toff, uint32_t poff, uint32_t soff) 449 : TokenOff(toff), PPCondOff(poff), SpellingOff(soff) {} 450 451 uint32_t getTokenOffset() const { 452 assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized."); 453 return TokenOff; 454 } 455 456 uint32_t getPPCondOffset() const { 457 assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized."); 458 return PPCondOff; 459 } 460 461 uint32_t getSpellingOffset() const { 462 assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized."); 463 return SpellingOff; 464 } 465 466 bool isValid() const { return TokenOff != ~((uint32_t)0); } 467 }; 468 469private: 470 llvm::StringMap<Val> FileMap; 471 472public: 473 PTHFileLookup() {}; 474 475 Val Lookup(const FileEntry* FE) { 476 const char* s = FE->getName(); 477 unsigned size = strlen(s); 478 return FileMap.GetOrCreateValue(s, s+size).getValue(); 479 } 480 481 void ReadTable(const char* D) { 482 uint32_t N = Read32(D); // Read the length of the table. 483 484 for ( ; N > 0; --N) { // The rest of the data is the table itself. 485 uint32_t len = Read32(D); 486 const char* s = D; 487 D += len; 488 489 uint32_t TokenOff = Read32(D); 490 uint32_t PPCondOff = Read32(D); 491 uint32_t SpellingOff = Read32(D); 492 493 FileMap.GetOrCreateValue(s, s+len).getValue() = 494 Val(TokenOff, PPCondOff, SpellingOff); 495 } 496 } 497}; 498} // end anonymous namespace 499 500//===----------------------------------------------------------------------===// 501// PTHManager methods. 502//===----------------------------------------------------------------------===// 503 504PTHManager::PTHManager(const llvm::MemoryBuffer* buf, void* fileLookup, 505 const char* idDataTable, IdentifierInfo** perIDCache, 506 Preprocessor& pp) 507: Buf(buf), PerIDCache(perIDCache), FileLookup(fileLookup), 508 IdDataTable(idDataTable), ITable(pp.getIdentifierTable()), PP(pp) {} 509 510PTHManager::~PTHManager() { 511 delete Buf; 512 delete (PTHFileLookup*) FileLookup; 513 free(PerIDCache); 514} 515 516PTHManager* PTHManager::Create(const std::string& file, Preprocessor& PP) { 517 518 // Memory map the PTH file. 519 llvm::OwningPtr<llvm::MemoryBuffer> 520 File(llvm::MemoryBuffer::getFile(file.c_str())); 521 522 if (!File) 523 return 0; 524 525 // Get the buffer ranges and check if there are at least three 32-bit 526 // words at the end of the file. 527 const char* BufBeg = File->getBufferStart(); 528 const char* BufEnd = File->getBufferEnd(); 529 530 if(!(BufEnd > BufBeg + sizeof(uint32_t)*3)) { 531 assert(false && "Invalid PTH file."); 532 return 0; // FIXME: Proper error diagnostic? 533 } 534 535 // Compute the address of the index table at the end of the PTH file. 536 // This table contains the offset of the file lookup table, the 537 // persistent ID -> identifer data table. 538 const char* EndTable = BufEnd - sizeof(uint32_t)*3; 539 540 // Construct the file lookup table. This will be used for mapping from 541 // FileEntry*'s to cached tokens. 542 const char* FileTableOffset = EndTable + sizeof(uint32_t)*2; 543 const char* FileTable = BufBeg + Read32(FileTableOffset); 544 545 if (!(FileTable > BufBeg && FileTable < BufEnd)) { 546 assert(false && "Invalid PTH file."); 547 return 0; // FIXME: Proper error diagnostic? 548 } 549 550 llvm::OwningPtr<PTHFileLookup> FL(new PTHFileLookup()); 551 FL->ReadTable(FileTable); 552 553 // Get the location of the table mapping from persistent ids to the 554 // data needed to reconstruct identifiers. 555 const char* IDTableOffset = EndTable + sizeof(uint32_t)*1; 556 const char* IData = BufBeg + Read32(IDTableOffset); 557 if (!(IData > BufBeg && IData < BufEnd)) { 558 assert(false && "Invalid PTH file."); 559 return 0; // FIXME: Proper error diagnostic? 560 } 561 562 // Get the number of IdentifierInfos and pre-allocate the identifier cache. 563 uint32_t NumIds = Read32(IData); 564 565 // Pre-allocate the peristent ID -> IdentifierInfo* cache. We use calloc() 566 // so that we in the best case only zero out memory once when the OS returns 567 // us new pages. 568 IdentifierInfo** PerIDCache = 569 (IdentifierInfo**) calloc(NumIds, sizeof(*PerIDCache)); 570 571 if (!PerIDCache) { 572 assert(false && "Could not allocate Persistent ID cache."); 573 return 0; 574 } 575 576 // Create the new lexer. 577 return new PTHManager(File.take(), FL.take(), IData, PerIDCache, PP); 578} 579 580IdentifierInfo* PTHManager::GetIdentifierInfo(unsigned persistentID) { 581 582 // Check if the IdentifierInfo has already been resolved. 583 IdentifierInfo*& II = PerIDCache[persistentID]; 584 if (II) return II; 585 586 // Look in the PTH file for the string data for the IdentifierInfo object. 587 const char* TableEntry = IdDataTable + sizeof(uint32_t) * persistentID; 588 const char* IDData = Buf->getBufferStart() + Read32(TableEntry); 589 assert(IDData < Buf->getBufferEnd()); 590 591 // Read the length of the string. 592 uint32_t len = Read32(IDData); 593 594 // Get the IdentifierInfo* with the specified string. 595 II = &ITable.get(IDData, IDData+len); 596 return II; 597} 598 599PTHLexer* PTHManager::CreateLexer(unsigned FileID, const FileEntry* FE) { 600 601 if (!FE) 602 return 0; 603 604 // Lookup the FileEntry object in our file lookup data structure. It will 605 // return a variant that indicates whether or not there is an offset within 606 // the PTH file that contains cached tokens. 607 PTHFileLookup::Val FileData = ((PTHFileLookup*) FileLookup)->Lookup(FE); 608 609 if (!FileData.isValid()) // No tokens available. 610 return 0; 611 612 // Compute the offset of the token data within the buffer. 613 const char* data = Buf->getBufferStart() + FileData.getTokenOffset(); 614 615 // Get the location of pp-conditional table. 616 const char* ppcond = Buf->getBufferStart() + FileData.getPPCondOffset(); 617 uint32_t len = Read32(ppcond); 618 if (len == 0) ppcond = 0; 619 620 // Get the location of the spelling table. 621 const char* spellingTable = Buf->getBufferStart() + 622 FileData.getSpellingOffset(); 623 624 len = Read32(spellingTable); 625 if (len == 0) spellingTable = 0; 626 627 assert(data < Buf->getBufferEnd()); 628 629 // Create the SpellingSearch object for this FileID. 630 PTHSpellingSearch* ss = new PTHSpellingSearch(*this, len, spellingTable); 631 SpellingMap[FileID] = ss; 632 633 return new PTHLexer(PP, SourceLocation::getFileLoc(FileID, 0), data, ppcond, 634 *ss, *this); 635} 636