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/OnDiskHashTable.h"
  21 #include "clang/Basic/SourceManager.h"
  22 #include "clang/Lex/Lexer.h"
  23 #include "clang/Lex/Preprocessor.h"
  24 #include "llvm/ADT/StringExtras.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/Support/FileSystem.h"
  27 #include "llvm/Support/MemoryBuffer.h"
  28 #include "llvm/Support/Path.h"
  29 #include "llvm/Support/raw_ostream.h"
  30
  31 // FIXME: put this somewhere else?
  32 #ifndef S_ISDIR
  33 #define S_ISDIR(x) (((x)&_S_IFDIR)!=0)
  34 #endif
  35
  36 using namespace clang;
  37 using namespace clang::io;
  38
  39 //===----------------------------------------------------------------------===//
  40 // PTH-specific stuff.
  41 //===----------------------------------------------------------------------===//
  42
  43 namespace {
  44 class PTHEntry {
  45   Offset TokenData, PPCondData;
  46
  47 public:
  48   PTHEntry() {}
  49
  50   PTHEntry(Offset td, Offset ppcd)
  51     : TokenData(td), PPCondData(ppcd) {}
  52
  53   Offset getTokenOffset() const { return TokenData; }
  54   Offset getPPCondTableOffset() const { return PPCondData; }
  55 };
  56
  57
  58 class PTHEntryKeyVariant {
  59   union { const FileEntry* FE; const char* Path; };
  60   enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind;
  61   struct stat *StatBuf;
  62 public:
  63   PTHEntryKeyVariant(const FileEntry *fe)
  64     : FE(fe), Kind(IsFE), StatBuf(0) {}
  65
  66   PTHEntryKeyVariant(struct stat* statbuf, const char* path)
  67     : Path(path), Kind(IsDE), StatBuf(new struct stat(*statbuf)) {}
  68
  69   explicit PTHEntryKeyVariant(const char* path)
  70     : Path(path), Kind(IsNoExist), StatBuf(0) {}
  71
  72   bool isFile() const { return Kind == IsFE; }
  73
  74   StringRef getString() const {
  75     return Kind == IsFE ? FE->getName() : Path;
  76   }
  77
  78   unsigned getKind() const { return (unsigned) Kind; }
  79
  80   void EmitData(raw_ostream& Out) {
  81     switch (Kind) {
  82     case IsFE:
  83       // Emit stat information.
  84       ::Emit32(Out, FE->getInode());
  85       ::Emit32(Out, FE->getDevice());
  86       ::Emit16(Out, FE->getFileMode());
  87       ::Emit64(Out, FE->getModificationTime());
  88       ::Emit64(Out, FE->getSize());
  89       break;
  90     case IsDE:
  91       // Emit stat information.
  92       ::Emit32(Out, (uint32_t) StatBuf->st_ino);
  93       ::Emit32(Out, (uint32_t) StatBuf->st_dev);
  94       ::Emit16(Out, (uint16_t) StatBuf->st_mode);
  95       ::Emit64(Out, (uint64_t) StatBuf->st_mtime);
  96       ::Emit64(Out, (uint64_t) StatBuf->st_size);
  97       delete StatBuf;
  98       break;
  99     default:
 100       break;
 101     }
 102   }
 103
 104   unsigned getRepresentationLength() const {
 105     return Kind == IsNoExist ? 0 : 4 + 4 + 2 + 8 + 8;
 106   }
 107 };
 108
 109 class FileEntryPTHEntryInfo {
 110 public:
 111   typedef PTHEntryKeyVariant key_type;
 112   typedef key_type key_type_ref;
 113
 114   typedef PTHEntry data_type;
 115   typedef const PTHEntry& data_type_ref;
 116
 117   static unsigned ComputeHash(PTHEntryKeyVariant V) {
 118     return llvm::HashString(V.getString());
 119   }
 120
 121   static std::pair<unsigned,unsigned>
 122   EmitKeyDataLength(raw_ostream& Out, PTHEntryKeyVariant V,
 123                     const PTHEntry& E) {
 124
 125     unsigned n = V.getString().size() + 1 + 1;
 126     ::Emit16(Out, n);
 127
 128     unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0);
 129     ::Emit8(Out, m);
 130
 131     return std::make_pair(n, m);
 132   }
 133
 134   static void EmitKey(raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){
 135     // Emit the entry kind.
 136     ::Emit8(Out, (unsigned) V.getKind());
 137     // Emit the string.
 138     Out.write(V.getString().data(), n - 1);
 139   }
 140
 141   static void EmitData(raw_ostream& Out, PTHEntryKeyVariant V,
 142                        const PTHEntry& E, unsigned) {
 143
 144
 145     // For file entries emit the offsets into the PTH file for token data
 146     // and the preprocessor blocks table.
 147     if (V.isFile()) {
 148       ::Emit32(Out, E.getTokenOffset());
 149       ::Emit32(Out, E.getPPCondTableOffset());
 150     }
 151
 152     // Emit any other data associated with the key (i.e., stat information).
 153     V.EmitData(Out);
 154   }
 155 };
 156
 157 class OffsetOpt {
 158   bool valid;
 159   Offset off;
 160 public:
 161   OffsetOpt() : valid(false) {}
 162   bool hasOffset() const { return valid; }
 163   Offset getOffset() const { assert(valid); return off; }
 164   void setOffset(Offset o) { off = o; valid = true; }
 165 };
 166 } // end anonymous namespace
 167
 168 typedef OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap;
 169
 170 namespace {
 171 class PTHWriter {
 172   typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap;
 173   typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy;
 174
 175   IDMap IM;
 176   llvm::raw_fd_ostream& Out;
 177   Preprocessor& PP;
 178   uint32_t idcount;
 179   PTHMap PM;
 180   CachedStrsTy CachedStrs;
 181   Offset CurStrOffset;
 182   std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries;
 183
 184   //// Get the persistent id for the given IdentifierInfo*.
 185   uint32_t ResolveID(const IdentifierInfo* II);
 186
 187   /// Emit a token to the PTH file.
 188   void EmitToken(const Token& T);
 189
 190   void Emit8(uint32_t V) { ::Emit8(Out, V); }
 191
 192   void Emit16(uint32_t V) { ::Emit16(Out, V); }
 193
 194   void Emit32(uint32_t V) { ::Emit32(Out, V); }
 195
 196   void EmitBuf(const char *Ptr, unsigned NumBytes) {
 197     Out.write(Ptr, NumBytes);
 198   }
 199
 200   void EmitString(StringRef V) {
 201     ::Emit16(Out, V.size());
 202     EmitBuf(V.data(), V.size());
 203   }
 204
 205   /// EmitIdentifierTable - Emits two tables to the PTH file.  The first is
 206   ///  a hashtable mapping from identifier strings to persistent IDs.
 207   ///  The second is a straight table mapping from persistent IDs to string data
 208   ///  (the keys of the first table).
 209   std::pair<Offset, Offset> EmitIdentifierTable();
 210
 211   /// EmitFileTable - Emit a table mapping from file name strings to PTH
 212   /// token data.
 213   Offset EmitFileTable() { return PM.Emit(Out); }
 214
 215   PTHEntry LexTokens(Lexer& L);
 216   Offset EmitCachedSpellings();
 217
 218 public:
 219   PTHWriter(llvm::raw_fd_ostream& out, Preprocessor& pp)
 220     : Out(out), PP(pp), idcount(0), CurStrOffset(0) {}
 221
 222   PTHMap &getPM() { return PM; }
 223   void GeneratePTH(const std::string &MainFile);
 224 };
 225 } // end anonymous namespace
 226
 227 uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) {
 228   // Null IdentifierInfo's map to the persistent ID 0.
 229   if (!II)
 230     return 0;
 231
 232   IDMap::iterator I = IM.find(II);
 233   if (I != IM.end())
 234     return I->second; // We've already added 1.
 235
 236   IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL.
 237   return idcount;
 238 }
 239
 240 void PTHWriter::EmitToken(const Token& T) {
 241   // Emit the token kind, flags, and length.
 242   Emit32(((uint32_t) T.getKind()) | ((((uint32_t) T.getFlags())) << 8)|
 243          (((uint32_t) T.getLength()) << 16));
 244
 245   if (!T.isLiteral()) {
 246     Emit32(ResolveID(T.getIdentifierInfo()));
 247   } else {
 248     // We cache *un-cleaned* spellings. This gives us 100% fidelity with the
 249     // source code.
 250     StringRef s(T.getLiteralData(), T.getLength());
 251
 252     // Get the string entry.
 253     llvm::StringMapEntry<OffsetOpt> *E = &CachedStrs.GetOrCreateValue(s);
 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 += s.size() + 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
 271 PTHEntry 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 eod 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::eod);
 296       Tmp.clearFlag(Token::StartOfLine);
 297       Tmp.setIdentifierInfo(0);
 298       EmitToken(Tmp);
 299       ParsingPreprocessorDirective = false;
 300     }
 301
 302     if (Tok.is(tok::raw_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::raw_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::raw_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
 437 Offset 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
 448 void PTHWriter::GeneratePTH(const std::string &MainFile) {
 449   // Generate the prologue.
 450   Out << "cfe-pth" << '\0';
 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.getLangOpts();
 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.OrigEntry;
 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
 507 namespace {
 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.
 513 class StatListener : public FileSystemStatCache {
 514   PTHMap &PM;
 515 public:
 516   StatListener(PTHMap &pm) : PM(pm) {}
 517   ~StatListener() {}
 518
 519   LookupResult getStat(const char *Path, struct stat &StatBuf,
 520                        bool isFile, int *FileDescriptor) {
 521     LookupResult Result = statChained(Path, StatBuf, isFile, 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
 539 void 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   SmallString<128> MainFilePath(MainFile->getName());
 544
 545   llvm::sys::fs::make_absolute(MainFilePath);
 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
 567 namespace {
 568 class PTHIdKey {
 569 public:
 570   const IdentifierInfo* II;
 571   uint32_t FileOffset;
 572 };
 573
 574 class PTHIdentifierTableTrait {
 575 public:
 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(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(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(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 ///
 612 std::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 }