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