CacheTokens.cpp revision 66392d4260cdd1a98f9ce908d99e3cf9a31432e2 
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/FileManager.h"
17#include "clang/Basic/SourceManager.h"
18#include "clang/Basic/IdentifierTable.h"
19#include "clang/Basic/Diagnostic.h"
20#include "clang/Basic/OnDiskHashTable.h"
21#include "clang/Lex/Lexer.h"
22#include "clang/Lex/Preprocessor.h"
23#include "llvm/ADT/StringExtras.h"
24#include "llvm/ADT/StringMap.h"
25#include "llvm/Support/MemoryBuffer.h"
26#include "llvm/Support/raw_ostream.h"
27#include "llvm/System/Path.h"
28
29// FIXME: put this somewhere else?
30#ifndef S_ISDIR
31#define S_ISDIR(x) (((x)&_S_IFDIR)!=0)
32#endif
33
34using namespace clang;
35using namespace clang::io;
36
37//===----------------------------------------------------------------------===//
38// PTH-specific stuff.
39//===----------------------------------------------------------------------===//
40
41namespace {
42class PTHEntry {
43  Offset TokenData, PPCondData;
44
45public:
46  PTHEntry() {}
47
48  PTHEntry(Offset td, Offset ppcd)
49    : TokenData(td), PPCondData(ppcd) {}
50
51  Offset getTokenOffset() const { return TokenData; }
52  Offset getPPCondTableOffset() const { return PPCondData; }
53};
54
55
56class PTHEntryKeyVariant {
57  union { const FileEntry* FE; const char* Path; };
58  enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind;
59  struct stat *StatBuf;
60public:
61  PTHEntryKeyVariant(const FileEntry *fe)
62    : FE(fe), Kind(IsFE), StatBuf(0) {}
63
64  PTHEntryKeyVariant(struct stat* statbuf, const char* path)
65    : Path(path), Kind(IsDE), StatBuf(new struct stat(*statbuf)) {}
66
67  explicit PTHEntryKeyVariant(const char* path)
68    : Path(path), Kind(IsNoExist), StatBuf(0) {}
69
70  bool isFile() const { return Kind == IsFE; }
71
72  llvm::StringRef getString() const {
73    return Kind == IsFE ? FE->getName() : Path;
74  }
75
76  unsigned getKind() const { return (unsigned) Kind; }
77
78  void EmitData(llvm::raw_ostream& Out) {
79    switch (Kind) {
80    case IsFE:
81      // Emit stat information.
82      ::Emit32(Out, FE->getInode());
83      ::Emit32(Out, FE->getDevice());
84      ::Emit16(Out, FE->getFileMode());
85      ::Emit64(Out, FE->getModificationTime());
86      ::Emit64(Out, FE->getSize());
87      break;
88    case IsDE:
89      // Emit stat information.
90      ::Emit32(Out, (uint32_t) StatBuf->st_ino);
91      ::Emit32(Out, (uint32_t) StatBuf->st_dev);
92      ::Emit16(Out, (uint16_t) StatBuf->st_mode);
93      ::Emit64(Out, (uint64_t) StatBuf->st_mtime);
94      ::Emit64(Out, (uint64_t) StatBuf->st_size);
95      delete StatBuf;
96      break;
97    default:
98      break;
99    }
100  }
101
102  unsigned getRepresentationLength() const {
103    return Kind == IsNoExist ? 0 : 4 + 4 + 2 + 8 + 8;
104  }
105};
106
107class FileEntryPTHEntryInfo {
108public:
109  typedef PTHEntryKeyVariant key_type;
110  typedef key_type key_type_ref;
111
112  typedef PTHEntry data_type;
113  typedef const PTHEntry& data_type_ref;
114
115  static unsigned ComputeHash(PTHEntryKeyVariant V) {
116    return llvm::HashString(V.getString());
117  }
118
119  static std::pair<unsigned,unsigned>
120  EmitKeyDataLength(llvm::raw_ostream& Out, PTHEntryKeyVariant V,
121                    const PTHEntry& E) {
122
123    unsigned n = V.getString().size() + 1 + 1;
124    ::Emit16(Out, n);
125
126    unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0);
127    ::Emit8(Out, m);
128
129    return std::make_pair(n, m);
130  }
131
132  static void EmitKey(llvm::raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){
133    // Emit the entry kind.
134    ::Emit8(Out, (unsigned) V.getKind());
135    // Emit the string.
136    Out.write(V.getString().data(), n - 1);
137  }
138
139  static void EmitData(llvm::raw_ostream& Out, PTHEntryKeyVariant V,
140                       const PTHEntry& E, unsigned) {
141
142
143    // For file entries emit the offsets into the PTH file for token data
144    // and the preprocessor blocks table.
145    if (V.isFile()) {
146      ::Emit32(Out, E.getTokenOffset());
147      ::Emit32(Out, E.getPPCondTableOffset());
148    }
149
150    // Emit any other data associated with the key (i.e., stat information).
151    V.EmitData(Out);
152  }
153};
154
155class OffsetOpt {
156  bool valid;
157  Offset off;
158public:
159  OffsetOpt() : valid(false) {}
160  bool hasOffset() const { return valid; }
161  Offset getOffset() const { assert(valid); return off; }
162  void setOffset(Offset o) { off = o; valid = true; }
163};
164} // end anonymous namespace
165
166typedef OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap;
167
168namespace {
169class PTHWriter {
170  typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap;
171  typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy;
172
173  IDMap IM;
174  llvm::raw_fd_ostream& Out;
175  Preprocessor& PP;
176  uint32_t idcount;
177  PTHMap PM;
178  CachedStrsTy CachedStrs;
179  Offset CurStrOffset;
180  std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries;
181
182  //// Get the persistent id for the given IdentifierInfo*.
183  uint32_t ResolveID(const IdentifierInfo* II);
184
185  /// Emit a token to the PTH file.
186  void EmitToken(const Token& T);
187
188  void Emit8(uint32_t V) { ::Emit8(Out, V); }
189
190  void Emit16(uint32_t V) { ::Emit16(Out, V); }
191
192  void Emit32(uint32_t V) { ::Emit32(Out, V); }
193
194  void EmitBuf(const char *Ptr, unsigned NumBytes) {
195    Out.write(Ptr, NumBytes);
196  }
197
198  void EmitString(llvm::StringRef V) {
199    ::Emit16(Out, V.size());
200    EmitBuf(V.data(), V.size());
201  }
202
203  /// EmitIdentifierTable - Emits two tables to the PTH file.  The first is
204  ///  a hashtable mapping from identifier strings to persistent IDs.
205  ///  The second is a straight table mapping from persistent IDs to string data
206  ///  (the keys of the first table).
207  std::pair<Offset, Offset> EmitIdentifierTable();
208
209  /// EmitFileTable - Emit a table mapping from file name strings to PTH
210  /// token data.
211  Offset EmitFileTable() { return PM.Emit(Out); }
212
213  PTHEntry LexTokens(Lexer& L);
214  Offset EmitCachedSpellings();
215
216public:
217  PTHWriter(llvm::raw_fd_ostream& out, Preprocessor& pp)
218    : Out(out), PP(pp), idcount(0), CurStrOffset(0) {}
219
220  PTHMap &getPM() { return PM; }
221  void GeneratePTH(const std::string &MainFile);
222};
223} // end anonymous namespace
224
225uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) {
226  // Null IdentifierInfo's map to the persistent ID 0.
227  if (!II)
228    return 0;
229
230  IDMap::iterator I = IM.find(II);
231  if (I != IM.end())
232    return I->second; // We've already added 1.
233
234  IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL.
235  return idcount;
236}
237
238void PTHWriter::EmitToken(const Token& T) {
239  // Emit the token kind, flags, and length.
240  Emit32(((uint32_t) T.getKind()) | ((((uint32_t) T.getFlags())) << 8)|
241         (((uint32_t) T.getLength()) << 16));
242
243  if (!T.isLiteral()) {
244    Emit32(ResolveID(T.getIdentifierInfo()));
245  } else {
246    // We cache *un-cleaned* spellings. This gives us 100% fidelity with the
247    // source code.
248    const char* s = T.getLiteralData();
249    unsigned len = T.getLength();
250
251    // Get the string entry.
252    llvm::StringMapEntry<OffsetOpt> *E = &CachedStrs.GetOrCreateValue(s, s+len);
253
254    // If this is a new string entry, bump the PTH offset.
255    if (!E->getValue().hasOffset()) {
256      E->getValue().setOffset(CurStrOffset);
257      StrEntries.push_back(E);
258      CurStrOffset += len + 1;
259    }
260
261    // Emit the relative offset into the PTH file for the spelling string.
262    Emit32(E->getValue().getOffset());
263  }
264
265  // Emit the offset into the original source file of this token so that we
266  // can reconstruct its SourceLocation.
267  Emit32(PP.getSourceManager().getFileOffset(T.getLocation()));
268}
269
270PTHEntry PTHWriter::LexTokens(Lexer& L) {
271  // Pad 0's so that we emit tokens to a 4-byte alignment.
272  // This speed up reading them back in.
273  Pad(Out, 4);
274  Offset TokenOff = (Offset) Out.tell();
275
276  // Keep track of matching '#if' ... '#endif'.
277  typedef std::vector<std::pair<Offset, unsigned> > PPCondTable;
278  PPCondTable PPCond;
279  std::vector<unsigned> PPStartCond;
280  bool ParsingPreprocessorDirective = false;
281  Token Tok;
282
283  do {
284    L.LexFromRawLexer(Tok);
285  NextToken:
286
287    if ((Tok.isAtStartOfLine() || Tok.is(tok::eof)) &&
288        ParsingPreprocessorDirective) {
289      // Insert an eom token into the token cache.  It has the same
290      // position as the next token that is not on the same line as the
291      // preprocessor directive.  Observe that we continue processing
292      // 'Tok' when we exit this branch.
293      Token Tmp = Tok;
294      Tmp.setKind(tok::eom);
295      Tmp.clearFlag(Token::StartOfLine);
296      Tmp.setIdentifierInfo(0);
297      EmitToken(Tmp);
298      ParsingPreprocessorDirective = false;
299    }
300
301    if (Tok.is(tok::identifier)) {
302      PP.LookUpIdentifierInfo(Tok);
303      EmitToken(Tok);
304      continue;
305    }
306
307    if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
308      // Special processing for #include.  Store the '#' token and lex
309      // the next token.
310      assert(!ParsingPreprocessorDirective);
311      Offset HashOff = (Offset) Out.tell();
312
313      // Get the next token.
314      Token NextTok;
315      L.LexFromRawLexer(NextTok);
316
317      // If we see the start of line, then we had a null directive "#".  In
318      // this case, discard both tokens.
319      if (NextTok.isAtStartOfLine())
320        goto NextToken;
321
322      // The token is the start of a directive.  Emit it.
323      EmitToken(Tok);
324      Tok = NextTok;
325
326      // Did we see 'include'/'import'/'include_next'?
327      if (Tok.isNot(tok::identifier)) {
328        EmitToken(Tok);
329        continue;
330      }
331
332      IdentifierInfo* II = PP.LookUpIdentifierInfo(Tok);
333      tok::PPKeywordKind K = II->getPPKeywordID();
334
335      ParsingPreprocessorDirective = true;
336
337      switch (K) {
338      case tok::pp_not_keyword:
339        // Invalid directives "#foo" can occur in #if 0 blocks etc, just pass
340        // them through.
341      default:
342        break;
343
344      case tok::pp_include:
345      case tok::pp_import:
346      case tok::pp_include_next: {
347        // Save the 'include' token.
348        EmitToken(Tok);
349        // Lex the next token as an include string.
350        L.setParsingPreprocessorDirective(true);
351        L.LexIncludeFilename(Tok);
352        L.setParsingPreprocessorDirective(false);
353        assert(!Tok.isAtStartOfLine());
354        if (Tok.is(tok::identifier))
355          PP.LookUpIdentifierInfo(Tok);
356
357        break;
358      }
359      case tok::pp_if:
360      case tok::pp_ifdef:
361      case tok::pp_ifndef: {
362        // Add an entry for '#if' and friends.  We initially set the target
363        // index to 0.  This will get backpatched when we hit #endif.
364        PPStartCond.push_back(PPCond.size());
365        PPCond.push_back(std::make_pair(HashOff, 0U));
366        break;
367      }
368      case tok::pp_endif: {
369        // Add an entry for '#endif'.  We set the target table index to itself.
370        // This will later be set to zero when emitting to the PTH file.  We
371        // use 0 for uninitialized indices because that is easier to debug.
372        unsigned index = PPCond.size();
373        // Backpatch the opening '#if' entry.
374        assert(!PPStartCond.empty());
375        assert(PPCond.size() > PPStartCond.back());
376        assert(PPCond[PPStartCond.back()].second == 0);
377        PPCond[PPStartCond.back()].second = index;
378        PPStartCond.pop_back();
379        // Add the new entry to PPCond.
380        PPCond.push_back(std::make_pair(HashOff, index));
381        EmitToken(Tok);
382
383        // Some files have gibberish on the same line as '#endif'.
384        // Discard these tokens.
385        do
386          L.LexFromRawLexer(Tok);
387        while (Tok.isNot(tok::eof) && !Tok.isAtStartOfLine());
388        // We have the next token in hand.
389        // Don't immediately lex the next one.
390        goto NextToken;
391      }
392      case tok::pp_elif:
393      case tok::pp_else: {
394        // Add an entry for #elif or #else.
395        // This serves as both a closing and opening of a conditional block.
396        // This means that its entry will get backpatched later.
397        unsigned index = PPCond.size();
398        // Backpatch the previous '#if' entry.
399        assert(!PPStartCond.empty());
400        assert(PPCond.size() > PPStartCond.back());
401        assert(PPCond[PPStartCond.back()].second == 0);
402        PPCond[PPStartCond.back()].second = index;
403        PPStartCond.pop_back();
404        // Now add '#elif' as a new block opening.
405        PPCond.push_back(std::make_pair(HashOff, 0U));
406        PPStartCond.push_back(index);
407        break;
408      }
409      }
410    }
411
412    EmitToken(Tok);
413  }
414  while (Tok.isNot(tok::eof));
415
416  assert(PPStartCond.empty() && "Error: imblanced preprocessor conditionals.");
417
418  // Next write out PPCond.
419  Offset PPCondOff = (Offset) Out.tell();
420
421  // Write out the size of PPCond so that clients can identifer empty tables.
422  Emit32(PPCond.size());
423
424  for (unsigned i = 0, e = PPCond.size(); i!=e; ++i) {
425    Emit32(PPCond[i].first - TokenOff);
426    uint32_t x = PPCond[i].second;
427    assert(x != 0 && "PPCond entry not backpatched.");
428    // Emit zero for #endifs.  This allows us to do checking when
429    // we read the PTH file back in.
430    Emit32(x == i ? 0 : x);
431  }
432
433  return PTHEntry(TokenOff, PPCondOff);
434}
435
436Offset PTHWriter::EmitCachedSpellings() {
437  // Write each cached strings to the PTH file.
438  Offset SpellingsOff = Out.tell();
439
440  for (std::vector<llvm::StringMapEntry<OffsetOpt>*>::iterator
441       I = StrEntries.begin(), E = StrEntries.end(); I!=E; ++I)
442    EmitBuf((*I)->getKeyData(), (*I)->getKeyLength()+1 /*nul included*/);
443
444  return SpellingsOff;
445}
446
447void PTHWriter::GeneratePTH(const std::string &MainFile) {
448  // Generate the prologue.
449  Out << "cfe-pth";
450  Emit32(PTHManager::Version);
451
452  // Leave 4 words for the prologue.
453  Offset PrologueOffset = Out.tell();
454  for (unsigned i = 0; i < 4; ++i)
455    Emit32(0);
456
457  // Write the name of the MainFile.
458  if (!MainFile.empty()) {
459    EmitString(MainFile);
460  } else {
461    // String with 0 bytes.
462    Emit16(0);
463  }
464  Emit8(0);
465
466  // Iterate over all the files in SourceManager.  Create a lexer
467  // for each file and cache the tokens.
468  SourceManager &SM = PP.getSourceManager();
469  const LangOptions &LOpts = PP.getLangOptions();
470
471  for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(),
472       E = SM.fileinfo_end(); I != E; ++I) {
473    const SrcMgr::ContentCache &C = *I->second;
474    const FileEntry *FE = C.Entry;
475
476    // FIXME: Handle files with non-absolute paths.
477    llvm::sys::Path P(FE->getName());
478    if (!P.isAbsolute())
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 StatSysCallCache {
514  PTHMap &PM;
515public:
516  StatListener(PTHMap &pm) : PM(pm) {}
517  ~StatListener() {}
518
519  int stat(const char *path, struct stat *buf) {
520    int result = StatSysCallCache::stat(path, buf);
521
522    if (result != 0) // Failed 'stat'.
523      PM.insert(PTHEntryKeyVariant(path), PTHEntry());
524    else if (S_ISDIR(buf->st_mode)) {
525      // Only cache directories with absolute paths.
526      if (!llvm::sys::Path(path).isAbsolute())
527        return result;
528
529      PM.insert(PTHEntryKeyVariant(buf, path), PTHEntry());
530    }
531
532    return result;
533  }
534};
535} // end anonymous namespace
536
537
538void clang::CacheTokens(Preprocessor &PP, llvm::raw_fd_ostream* OS) {
539  // Get the name of the main file.
540  const SourceManager &SrcMgr = PP.getSourceManager();
541  const FileEntry *MainFile = SrcMgr.getFileEntryForID(SrcMgr.getMainFileID());
542  llvm::sys::Path MainFilePath(MainFile->getName());
543
544  MainFilePath.makeAbsolute();
545
546  // Create the PTHWriter.
547  PTHWriter PW(*OS, PP);
548
549  // Install the 'stat' system call listener in the FileManager.
550  StatListener *StatCache = new StatListener(PW.getPM());
551  PP.getFileManager().addStatCache(StatCache, /*AtBeginning=*/true);
552
553  // Lex through the entire file.  This will populate SourceManager with
554  // all of the header information.
555  Token Tok;
556  PP.EnterMainSourceFile();
557  do { PP.Lex(Tok); } while (Tok.isNot(tok::eof));
558
559  // Generate the PTH file.
560  PP.getFileManager().removeStatCache(StatCache);
561  PW.GeneratePTH(MainFilePath.str());
562}
563
564//===----------------------------------------------------------------------===//
565
566namespace {
567class PTHIdKey {
568public:
569  const IdentifierInfo* II;
570  uint32_t FileOffset;
571};
572
573class PTHIdentifierTableTrait {
574public:
575  typedef PTHIdKey* key_type;
576  typedef key_type  key_type_ref;
577
578  typedef uint32_t  data_type;
579  typedef data_type data_type_ref;
580
581  static unsigned ComputeHash(PTHIdKey* key) {
582    return llvm::HashString(key->II->getName());
583  }
584
585  static std::pair<unsigned,unsigned>
586  EmitKeyDataLength(llvm::raw_ostream& Out, const PTHIdKey* key, uint32_t) {
587    unsigned n = key->II->getLength() + 1;
588    ::Emit16(Out, n);
589    return std::make_pair(n, sizeof(uint32_t));
590  }
591
592  static void EmitKey(llvm::raw_ostream& Out, PTHIdKey* key, unsigned n) {
593    // Record the location of the key data.  This is used when generating
594    // the mapping from persistent IDs to strings.
595    key->FileOffset = Out.tell();
596    Out.write(key->II->getNameStart(), n);
597  }
598
599  static void EmitData(llvm::raw_ostream& Out, PTHIdKey*, uint32_t pID,
600                       unsigned) {
601    ::Emit32(Out, pID);
602  }
603};
604} // end anonymous namespace
605
606/// EmitIdentifierTable - Emits two tables to the PTH file.  The first is
607///  a hashtable mapping from identifier strings to persistent IDs.  The second
608///  is a straight table mapping from persistent IDs to string data (the
609///  keys of the first table).
610///
611std::pair<Offset,Offset> PTHWriter::EmitIdentifierTable() {
612  // Build two maps:
613  //  (1) an inverse map from persistent IDs -> (IdentifierInfo*,Offset)
614  //  (2) a map from (IdentifierInfo*, Offset)* -> persistent IDs
615
616  // Note that we use 'calloc', so all the bytes are 0.
617  PTHIdKey *IIDMap = (PTHIdKey*)calloc(idcount, sizeof(PTHIdKey));
618
619  // Create the hashtable.
620  OnDiskChainedHashTableGenerator<PTHIdentifierTableTrait> IIOffMap;
621
622  // Generate mapping from persistent IDs -> IdentifierInfo*.
623  for (IDMap::iterator I = IM.begin(), E = IM.end(); I != E; ++I) {
624    // Decrement by 1 because we are using a vector for the lookup and
625    // 0 is reserved for NULL.
626    assert(I->second > 0);
627    assert(I->second-1 < idcount);
628    unsigned idx = I->second-1;
629
630    // Store the mapping from persistent ID to IdentifierInfo*
631    IIDMap[idx].II = I->first;
632
633    // Store the reverse mapping in a hashtable.
634    IIOffMap.insert(&IIDMap[idx], I->second);
635  }
636
637  // Write out the inverse map first.  This causes the PCIDKey entries to
638  // record PTH file offsets for the string data.  This is used to write
639  // the second table.
640  Offset StringTableOffset = IIOffMap.Emit(Out);
641
642  // Now emit the table mapping from persistent IDs to PTH file offsets.
643  Offset IDOff = Out.tell();
644  Emit32(idcount);  // Emit the number of identifiers.
645  for (unsigned i = 0 ; i < idcount; ++i)
646    Emit32(IIDMap[i].FileOffset);
647
648  // Finally, release the inverse map.
649  free(IIDMap);
650
651  return std::make_pair(IDOff, StringTableOffset);
652}
653