CacheTokens.cpp revision 84021556baceb76eedf7d44be8ba71d9b8cfacce 
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.Entry;
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