contrib/llvm/tools/clang/lib/Frontend/CacheTokens.cpp

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