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