PTHLexer.cpp revision 28396608ec20d44e9d1470e1ea51689bb504d0de 
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      if (i == min)
404        break;
405
406      min = i;
407      continue;
408    }
409
410    uint32_t SpellingPTHOffset =
411        ((uint32_t) ((uint8_t) p[4]))
412        | (((uint32_t) ((uint8_t) p[5])) << 8)
413        | (((uint32_t) ((uint8_t) p[6])) << 16)
414        | (((uint32_t) ((uint8_t) p[7])) << 24);
415
416    return PTHMgr.getSpellingAtPTHOffset(SpellingPTHOffset, Buffer);
417  }
418  while (min != max);
419
420  return 0;
421}
422
423unsigned PTHLexer::getSpelling(SourceLocation sloc, const char *&Buffer) {
424  SourceManager& SM = PP->getSourceManager();
425  sloc = SM.getPhysicalLoc(sloc);
426  unsigned fid = SM.getCanonicalFileID(sloc);
427  unsigned fpos = SM.getFullFilePos(sloc);
428
429  return (fid == FileID ) ? MySpellingSrch.getSpellingLinearSearch(fpos, Buffer)
430                          : PTHMgr.getSpelling(fid, fpos, Buffer);
431}
432
433//===----------------------------------------------------------------------===//
434// Internal Data Structures for PTH file lookup and resolving identifiers.
435//===----------------------------------------------------------------------===//
436
437
438/// PTHFileLookup - This internal data structure is used by the PTHManager
439///  to map from FileEntry objects managed by FileManager to offsets within
440///  the PTH file.
441namespace {
442class VISIBILITY_HIDDEN PTHFileLookup {
443public:
444  class Val {
445    uint32_t TokenOff;
446    uint32_t PPCondOff;
447    uint32_t SpellingOff;
448
449  public:
450    Val() : TokenOff(~0) {}
451    Val(uint32_t toff, uint32_t poff, uint32_t soff)
452      : TokenOff(toff), PPCondOff(poff), SpellingOff(soff) {}
453
454    uint32_t getTokenOffset() const {
455      assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized.");
456      return TokenOff;
457    }
458
459    uint32_t getPPCondOffset() const {
460      assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized.");
461      return PPCondOff;
462    }
463
464    uint32_t getSpellingOffset() const {
465      assert(TokenOff != ~((uint32_t)0) && "PTHFileLookup entry initialized.");
466      return SpellingOff;
467    }
468
469    bool isValid() const { return TokenOff != ~((uint32_t)0); }
470  };
471
472private:
473  llvm::StringMap<Val> FileMap;
474
475public:
476  PTHFileLookup() {};
477
478  Val Lookup(const FileEntry* FE) {
479    const char* s = FE->getName();
480    unsigned size = strlen(s);
481    return FileMap.GetOrCreateValue(s, s+size).getValue();
482  }
483
484  void ReadTable(const char* D) {
485    uint32_t N = Read32(D);     // Read the length of the table.
486
487    for ( ; N > 0; --N) {       // The rest of the data is the table itself.
488      uint32_t len = Read32(D);
489      const char* s = D;
490      D += len;
491
492      uint32_t TokenOff = Read32(D);
493      uint32_t PPCondOff = Read32(D);
494      uint32_t SpellingOff = Read32(D);
495
496      FileMap.GetOrCreateValue(s, s+len).getValue() =
497        Val(TokenOff, PPCondOff, SpellingOff);
498    }
499  }
500};
501} // end anonymous namespace
502
503//===----------------------------------------------------------------------===//
504// PTHManager methods.
505//===----------------------------------------------------------------------===//
506
507PTHManager::PTHManager(const llvm::MemoryBuffer* buf, void* fileLookup,
508                       const char* idDataTable, IdentifierInfo** perIDCache,
509                       Preprocessor& pp)
510: Buf(buf), PerIDCache(perIDCache), FileLookup(fileLookup),
511  IdDataTable(idDataTable), ITable(pp.getIdentifierTable()), PP(pp) {}
512
513PTHManager::~PTHManager() {
514  delete Buf;
515  delete (PTHFileLookup*) FileLookup;
516  free(PerIDCache);
517}
518
519PTHManager* PTHManager::Create(const std::string& file, Preprocessor& PP) {
520
521  // Memory map the PTH file.
522  llvm::OwningPtr<llvm::MemoryBuffer>
523  File(llvm::MemoryBuffer::getFile(file.c_str()));
524
525  if (!File)
526    return 0;
527
528  // Get the buffer ranges and check if there are at least three 32-bit
529  // words at the end of the file.
530  const char* BufBeg = File->getBufferStart();
531  const char* BufEnd = File->getBufferEnd();
532
533  if(!(BufEnd > BufBeg + sizeof(uint32_t)*3)) {
534    assert(false && "Invalid PTH file.");
535    return 0; // FIXME: Proper error diagnostic?
536  }
537
538  // Compute the address of the index table at the end of the PTH file.
539  // This table contains the offset of the file lookup table, the
540  // persistent ID -> identifer data table.
541  const char* EndTable = BufEnd - sizeof(uint32_t)*3;
542
543  // Construct the file lookup table.  This will be used for mapping from
544  // FileEntry*'s to cached tokens.
545  const char* FileTableOffset = EndTable + sizeof(uint32_t)*2;
546  const char* FileTable = BufBeg + Read32(FileTableOffset);
547
548  if (!(FileTable > BufBeg && FileTable < BufEnd)) {
549    assert(false && "Invalid PTH file.");
550    return 0; // FIXME: Proper error diagnostic?
551  }
552
553  llvm::OwningPtr<PTHFileLookup> FL(new PTHFileLookup());
554  FL->ReadTable(FileTable);
555
556  // Get the location of the table mapping from persistent ids to the
557  // data needed to reconstruct identifiers.
558  const char* IDTableOffset = EndTable + sizeof(uint32_t)*1;
559  const char* IData = BufBeg + Read32(IDTableOffset);
560  if (!(IData > BufBeg && IData < BufEnd)) {
561    assert(false && "Invalid PTH file.");
562    return 0; // FIXME: Proper error diagnostic?
563  }
564
565  // Get the number of IdentifierInfos and pre-allocate the identifier cache.
566  uint32_t NumIds = Read32(IData);
567
568  // Pre-allocate the peristent ID -> IdentifierInfo* cache.  We use calloc()
569  // so that we in the best case only zero out memory once when the OS returns
570  // us new pages.
571  IdentifierInfo** PerIDCache =
572    (IdentifierInfo**) calloc(NumIds, sizeof(*PerIDCache));
573
574  if (!PerIDCache) {
575    assert(false && "Could not allocate Persistent ID cache.");
576    return 0;
577  }
578
579  // Create the new lexer.
580  return new PTHManager(File.take(), FL.take(), IData, PerIDCache, PP);
581}
582
583IdentifierInfo* PTHManager::GetIdentifierInfo(unsigned persistentID) {
584
585  // Check if the IdentifierInfo has already been resolved.
586  IdentifierInfo*& II = PerIDCache[persistentID];
587  if (II) return II;
588
589  // Look in the PTH file for the string data for the IdentifierInfo object.
590  const char* TableEntry = IdDataTable + sizeof(uint32_t) * persistentID;
591  const char* IDData = Buf->getBufferStart() + Read32(TableEntry);
592  assert(IDData < Buf->getBufferEnd());
593
594  // Read the length of the string.
595  uint32_t len = Read32(IDData);
596
597  // Get the IdentifierInfo* with the specified string.
598  II = &ITable.get(IDData, IDData+len);
599  return II;
600}
601
602PTHLexer* PTHManager::CreateLexer(unsigned FileID, const FileEntry* FE) {
603
604  if (!FE)
605    return 0;
606
607  // Lookup the FileEntry object in our file lookup data structure.  It will
608  // return a variant that indicates whether or not there is an offset within
609  // the PTH file that contains cached tokens.
610  PTHFileLookup::Val FileData = ((PTHFileLookup*) FileLookup)->Lookup(FE);
611
612  if (!FileData.isValid()) // No tokens available.
613    return 0;
614
615  // Compute the offset of the token data within the buffer.
616  const char* data = Buf->getBufferStart() + FileData.getTokenOffset();
617
618  // Get the location of pp-conditional table.
619  const char* ppcond = Buf->getBufferStart() + FileData.getPPCondOffset();
620  uint32_t len = Read32(ppcond);
621  if (len == 0) ppcond = 0;
622
623  // Get the location of the spelling table.
624  const char* spellingTable = Buf->getBufferStart() +
625                              FileData.getSpellingOffset();
626
627  len = Read32(spellingTable);
628  if (len == 0) spellingTable = 0;
629
630  assert(data < Buf->getBufferEnd());
631
632  // Create the SpellingSearch object for this FileID.
633  PTHSpellingSearch* ss = new PTHSpellingSearch(*this, len, spellingTable);
634  SpellingMap[FileID] = ss;
635
636  return new PTHLexer(PP, SourceLocation::getFileLoc(FileID, 0), data, ppcond,
637                      *ss, *this);
638}
639