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