contrib/llvm/tools/clang/lib/Serialization/GlobalModuleIndex.cpp

   1 //===--- GlobalModuleIndex.cpp - Global Module Index ------------*- C++ -*-===//
   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 file implements the GlobalModuleIndex class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "ASTReaderInternals.h"
  15 #include "clang/Frontend/PCHContainerOperations.h"
  16 #include "clang/Basic/FileManager.h"
  17 #include "clang/Lex/HeaderSearch.h"
  18 #include "clang/Serialization/ASTBitCodes.h"
  19 #include "clang/Serialization/GlobalModuleIndex.h"
  20 #include "clang/Serialization/Module.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/MapVector.h"
  23 #include "llvm/ADT/SmallString.h"
  24 #include "llvm/ADT/StringExtras.h"
  25 #include "llvm/Bitcode/BitstreamReader.h"
  26 #include "llvm/Bitcode/BitstreamWriter.h"
  27 #include "llvm/Support/FileSystem.h"
  28 #include "llvm/Support/LockFileManager.h"
  29 #include "llvm/Support/MemoryBuffer.h"
  30 #include "llvm/Support/OnDiskHashTable.h"
  31 #include "llvm/Support/Path.h"
  32 #include <cstdio>
  33 using namespace clang;
  34 using namespace serialization;
  35
  36 //----------------------------------------------------------------------------//
  37 // Shared constants
  38 //----------------------------------------------------------------------------//
  39 namespace {
  40   enum {
  41     /// \brief The block containing the index.
  42     GLOBAL_INDEX_BLOCK_ID = llvm::bitc::FIRST_APPLICATION_BLOCKID
  43   };
  44
  45   /// \brief Describes the record types in the index.
  46   enum IndexRecordTypes {
  47     /// \brief Contains version information and potentially other metadata,
  48     /// used to determine if we can read this global index file.
  49     INDEX_METADATA,
  50     /// \brief Describes a module, including its file name and dependencies.
  51     MODULE,
  52     /// \brief The index for identifiers.
  53     IDENTIFIER_INDEX
  54   };
  55 }
  56
  57 /// \brief The name of the global index file.
  58 static const char * const IndexFileName = "modules.idx";
  59
  60 /// \brief The global index file version.
  61 static const unsigned CurrentVersion = 1;
  62
  63 //----------------------------------------------------------------------------//
  64 // Global module index reader.
  65 //----------------------------------------------------------------------------//
  66
  67 namespace {
  68
  69 /// \brief Trait used to read the identifier index from the on-disk hash
  70 /// table.
  71 class IdentifierIndexReaderTrait {
  72 public:
  73   typedef StringRef external_key_type;
  74   typedef StringRef internal_key_type;
  75   typedef SmallVector<unsigned, 2> data_type;
  76   typedef unsigned hash_value_type;
  77   typedef unsigned offset_type;
  78
  79   static bool EqualKey(const internal_key_type& a, const internal_key_type& b) {
  80     return a == b;
  81   }
  82
  83   static hash_value_type ComputeHash(const internal_key_type& a) {
  84     return llvm::HashString(a);
  85   }
  86
  87   static std::pair<unsigned, unsigned>
  88   ReadKeyDataLength(const unsigned char*& d) {
  89     using namespace llvm::support;
  90     unsigned KeyLen = endian::readNext<uint16_t, little, unaligned>(d);
  91     unsigned DataLen = endian::readNext<uint16_t, little, unaligned>(d);
  92     return std::make_pair(KeyLen, DataLen);
  93   }
  94
  95   static const internal_key_type&
  96   GetInternalKey(const external_key_type& x) { return x; }
  97
  98   static const external_key_type&
  99   GetExternalKey(const internal_key_type& x) { return x; }
 100
 101   static internal_key_type ReadKey(const unsigned char* d, unsigned n) {
 102     return StringRef((const char *)d, n);
 103   }
 104
 105   static data_type ReadData(const internal_key_type& k,
 106                             const unsigned char* d,
 107                             unsigned DataLen) {
 108     using namespace llvm::support;
 109
 110     data_type Result;
 111     while (DataLen > 0) {
 112       unsigned ID = endian::readNext<uint32_t, little, unaligned>(d);
 113       Result.push_back(ID);
 114       DataLen -= 4;
 115     }
 116
 117     return Result;
 118   }
 119 };
 120
 121 typedef llvm::OnDiskIterableChainedHashTable<IdentifierIndexReaderTrait>
 122     IdentifierIndexTable;
 123
 124 }
 125
 126 GlobalModuleIndex::GlobalModuleIndex(std::unique_ptr<llvm::MemoryBuffer> Buffer,
 127                                      llvm::BitstreamCursor Cursor)
 128     : Buffer(std::move(Buffer)), IdentifierIndex(), NumIdentifierLookups(),
 129       NumIdentifierLookupHits() {
 130   // Read the global index.
 131   bool InGlobalIndexBlock = false;
 132   bool Done = false;
 133   while (!Done) {
 134     llvm::BitstreamEntry Entry = Cursor.advance();
 135
 136     switch (Entry.Kind) {
 137     case llvm::BitstreamEntry::Error:
 138       return;
 139
 140     case llvm::BitstreamEntry::EndBlock:
 141       if (InGlobalIndexBlock) {
 142         InGlobalIndexBlock = false;
 143         Done = true;
 144         continue;
 145       }
 146       return;
 147
 148
 149     case llvm::BitstreamEntry::Record:
 150       // Entries in the global index block are handled below.
 151       if (InGlobalIndexBlock)
 152         break;
 153
 154       return;
 155
 156     case llvm::BitstreamEntry::SubBlock:
 157       if (!InGlobalIndexBlock && Entry.ID == GLOBAL_INDEX_BLOCK_ID) {
 158         if (Cursor.EnterSubBlock(GLOBAL_INDEX_BLOCK_ID))
 159           return;
 160
 161         InGlobalIndexBlock = true;
 162       } else if (Cursor.SkipBlock()) {
 163         return;
 164       }
 165       continue;
 166     }
 167
 168     SmallVector<uint64_t, 64> Record;
 169     StringRef Blob;
 170     switch ((IndexRecordTypes)Cursor.readRecord(Entry.ID, Record, &Blob)) {
 171     case INDEX_METADATA:
 172       // Make sure that the version matches.
 173       if (Record.size() < 1 || Record[0] != CurrentVersion)
 174         return;
 175       break;
 176
 177     case MODULE: {
 178       unsigned Idx = 0;
 179       unsigned ID = Record[Idx++];
 180
 181       // Make room for this module's information.
 182       if (ID == Modules.size())
 183         Modules.push_back(ModuleInfo());
 184       else
 185         Modules.resize(ID + 1);
 186
 187       // Size/modification time for this module file at the time the
 188       // global index was built.
 189       Modules[ID].Size = Record[Idx++];
 190       Modules[ID].ModTime = Record[Idx++];
 191
 192       // File name.
 193       unsigned NameLen = Record[Idx++];
 194       Modules[ID].FileName.assign(Record.begin() + Idx,
 195                                   Record.begin() + Idx + NameLen);
 196       Idx += NameLen;
 197
 198       // Dependencies
 199       unsigned NumDeps = Record[Idx++];
 200       Modules[ID].Dependencies.insert(Modules[ID].Dependencies.end(),
 201                                       Record.begin() + Idx,
 202                                       Record.begin() + Idx + NumDeps);
 203       Idx += NumDeps;
 204
 205       // Make sure we're at the end of the record.
 206       assert(Idx == Record.size() && "More module info?");
 207
 208       // Record this module as an unresolved module.
 209       // FIXME: this doesn't work correctly for module names containing path
 210       // separators.
 211       StringRef ModuleName = llvm::sys::path::stem(Modules[ID].FileName);
 212       // Remove the -<hash of ModuleMapPath>
 213       ModuleName = ModuleName.rsplit('-').first;
 214       UnresolvedModules[ModuleName] = ID;
 215       break;
 216     }
 217
 218     case IDENTIFIER_INDEX:
 219       // Wire up the identifier index.
 220       if (Record[0]) {
 221         IdentifierIndex = IdentifierIndexTable::Create(
 222             (const unsigned char *)Blob.data() + Record[0],
 223             (const unsigned char *)Blob.data() + sizeof(uint32_t),
 224             (const unsigned char *)Blob.data(), IdentifierIndexReaderTrait());
 225       }
 226       break;
 227     }
 228   }
 229 }
 230
 231 GlobalModuleIndex::~GlobalModuleIndex() {
 232   delete static_cast<IdentifierIndexTable *>(IdentifierIndex);
 233 }
 234
 235 std::pair<GlobalModuleIndex *, GlobalModuleIndex::ErrorCode>
 236 GlobalModuleIndex::readIndex(StringRef Path) {
 237   // Load the index file, if it's there.
 238   llvm::SmallString<128> IndexPath;
 239   IndexPath += Path;
 240   llvm::sys::path::append(IndexPath, IndexFileName);
 241
 242   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> BufferOrErr =
 243       llvm::MemoryBuffer::getFile(IndexPath.c_str());
 244   if (!BufferOrErr)
 245     return std::make_pair(nullptr, EC_NotFound);
 246   std::unique_ptr<llvm::MemoryBuffer> Buffer = std::move(BufferOrErr.get());
 247
 248   /// \brief The bitstream reader from which we'll read the AST file.
 249   llvm::BitstreamReader Reader((const unsigned char *)Buffer->getBufferStart(),
 250                                (const unsigned char *)Buffer->getBufferEnd());
 251
 252   /// \brief The main bitstream cursor for the main block.
 253   llvm::BitstreamCursor Cursor(Reader);
 254
 255   // Sniff for the signature.
 256   if (Cursor.Read(8) != 'B' ||
 257       Cursor.Read(8) != 'C' ||
 258       Cursor.Read(8) != 'G' ||
 259       Cursor.Read(8) != 'I') {
 260     return std::make_pair(nullptr, EC_IOError);
 261   }
 262
 263   return std::make_pair(new GlobalModuleIndex(std::move(Buffer), Cursor),
 264                         EC_None);
 265 }
 266
 267 void
 268 GlobalModuleIndex::getKnownModules(SmallVectorImpl<ModuleFile *> &ModuleFiles) {
 269   ModuleFiles.clear();
 270   for (unsigned I = 0, N = Modules.size(); I != N; ++I) {
 271     if (ModuleFile *MF = Modules[I].File)
 272       ModuleFiles.push_back(MF);
 273   }
 274 }
 275
 276 void GlobalModuleIndex::getModuleDependencies(
 277        ModuleFile *File,
 278        SmallVectorImpl<ModuleFile *> &Dependencies) {
 279   // Look for information about this module file.
 280   llvm::DenseMap<ModuleFile *, unsigned>::iterator Known
 281     = ModulesByFile.find(File);
 282   if (Known == ModulesByFile.end())
 283     return;
 284
 285   // Record dependencies.
 286   Dependencies.clear();
 287   ArrayRef<unsigned> StoredDependencies = Modules[Known->second].Dependencies;
 288   for (unsigned I = 0, N = StoredDependencies.size(); I != N; ++I) {
 289     if (ModuleFile *MF = Modules[I].File)
 290       Dependencies.push_back(MF);
 291   }
 292 }
 293
 294 bool GlobalModuleIndex::lookupIdentifier(StringRef Name, HitSet &Hits) {
 295   Hits.clear();
 296
 297   // If there's no identifier index, there is nothing we can do.
 298   if (!IdentifierIndex)
 299     return false;
 300
 301   // Look into the identifier index.
 302   ++NumIdentifierLookups;
 303   IdentifierIndexTable &Table
 304     = *static_cast<IdentifierIndexTable *>(IdentifierIndex);
 305   IdentifierIndexTable::iterator Known = Table.find(Name);
 306   if (Known == Table.end()) {
 307     return true;
 308   }
 309
 310   SmallVector<unsigned, 2> ModuleIDs = *Known;
 311   for (unsigned I = 0, N = ModuleIDs.size(); I != N; ++I) {
 312     if (ModuleFile *MF = Modules[ModuleIDs[I]].File)
 313       Hits.insert(MF);
 314   }
 315
 316   ++NumIdentifierLookupHits;
 317   return true;
 318 }
 319
 320 bool GlobalModuleIndex::loadedModuleFile(ModuleFile *File) {
 321   // Look for the module in the global module index based on the module name.
 322   StringRef Name = File->ModuleName;
 323   llvm::StringMap<unsigned>::iterator Known = UnresolvedModules.find(Name);
 324   if (Known == UnresolvedModules.end()) {
 325     return true;
 326   }
 327
 328   // Rectify this module with the global module index.
 329   ModuleInfo &Info = Modules[Known->second];
 330
 331   //  If the size and modification time match what we expected, record this
 332   // module file.
 333   bool Failed = true;
 334   if (File->File->getSize() == Info.Size &&
 335       File->File->getModificationTime() == Info.ModTime) {
 336     Info.File = File;
 337     ModulesByFile[File] = Known->second;
 338
 339     Failed = false;
 340   }
 341
 342   // One way or another, we have resolved this module file.
 343   UnresolvedModules.erase(Known);
 344   return Failed;
 345 }
 346
 347 void GlobalModuleIndex::printStats() {
 348   std::fprintf(stderr, "*** Global Module Index Statistics:\n");
 349   if (NumIdentifierLookups) {
 350     fprintf(stderr, "  %u / %u identifier lookups succeeded (%f%%)\n",
 351             NumIdentifierLookupHits, NumIdentifierLookups,
 352             (double)NumIdentifierLookupHits*100.0/NumIdentifierLookups);
 353   }
 354   std::fprintf(stderr, "\n");
 355 }
 356
 357 void GlobalModuleIndex::dump() {
 358   llvm::errs() << "*** Global Module Index Dump:\n";
 359   llvm::errs() << "Module files:\n";
 360   for (auto &MI : Modules) {
 361     llvm::errs() << "** " << MI.FileName << "\n";
 362     if (MI.File)
 363       MI.File->dump();
 364     else
 365       llvm::errs() << "\n";
 366   }
 367   llvm::errs() << "\n";
 368 }
 369
 370 //----------------------------------------------------------------------------//
 371 // Global module index writer.
 372 //----------------------------------------------------------------------------//
 373
 374 namespace {
 375   /// \brief Provides information about a specific module file.
 376   struct ModuleFileInfo {
 377     /// \brief The numberic ID for this module file.
 378     unsigned ID;
 379
 380     /// \brief The set of modules on which this module depends. Each entry is
 381     /// a module ID.
 382     SmallVector<unsigned, 4> Dependencies;
 383   };
 384
 385   /// \brief Builder that generates the global module index file.
 386   class GlobalModuleIndexBuilder {
 387     FileManager &FileMgr;
 388     const PCHContainerReader &PCHContainerRdr;
 389
 390     /// \brief Mapping from files to module file information.
 391     typedef llvm::MapVector<const FileEntry *, ModuleFileInfo> ModuleFilesMap;
 392
 393     /// \brief Information about each of the known module files.
 394     ModuleFilesMap ModuleFiles;
 395
 396     /// \brief Mapping from identifiers to the list of module file IDs that
 397     /// consider this identifier to be interesting.
 398     typedef llvm::StringMap<SmallVector<unsigned, 2> > InterestingIdentifierMap;
 399
 400     /// \brief A mapping from all interesting identifiers to the set of module
 401     /// files in which those identifiers are considered interesting.
 402     InterestingIdentifierMap InterestingIdentifiers;
 403
 404     /// \brief Write the block-info block for the global module index file.
 405     void emitBlockInfoBlock(llvm::BitstreamWriter &Stream);
 406
 407     /// \brief Retrieve the module file information for the given file.
 408     ModuleFileInfo &getModuleFileInfo(const FileEntry *File) {
 409       llvm::MapVector<const FileEntry *, ModuleFileInfo>::iterator Known
 410         = ModuleFiles.find(File);
 411       if (Known != ModuleFiles.end())
 412         return Known->second;
 413
 414       unsigned NewID = ModuleFiles.size();
 415       ModuleFileInfo &Info = ModuleFiles[File];
 416       Info.ID = NewID;
 417       return Info;
 418     }
 419
 420   public:
 421     explicit GlobalModuleIndexBuilder(
 422         FileManager &FileMgr, const PCHContainerReader &PCHContainerRdr)
 423         : FileMgr(FileMgr), PCHContainerRdr(PCHContainerRdr) {}
 424
 425     /// \brief Load the contents of the given module file into the builder.
 426     ///
 427     /// \returns true if an error occurred, false otherwise.
 428     bool loadModuleFile(const FileEntry *File);
 429
 430     /// \brief Write the index to the given bitstream.
 431     void writeIndex(llvm::BitstreamWriter &Stream);
 432   };
 433 }
 434
 435 static void emitBlockID(unsigned ID, const char *Name,
 436                         llvm::BitstreamWriter &Stream,
 437                         SmallVectorImpl<uint64_t> &Record) {
 438   Record.clear();
 439   Record.push_back(ID);
 440   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_SETBID, Record);
 441
 442   // Emit the block name if present.
 443   if (!Name || Name[0] == 0) return;
 444   Record.clear();
 445   while (*Name)
 446     Record.push_back(*Name++);
 447   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_BLOCKNAME, Record);
 448 }
 449
 450 static void emitRecordID(unsigned ID, const char *Name,
 451                          llvm::BitstreamWriter &Stream,
 452                          SmallVectorImpl<uint64_t> &Record) {
 453   Record.clear();
 454   Record.push_back(ID);
 455   while (*Name)
 456     Record.push_back(*Name++);
 457   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_SETRECORDNAME, Record);
 458 }
 459
 460 void
 461 GlobalModuleIndexBuilder::emitBlockInfoBlock(llvm::BitstreamWriter &Stream) {
 462   SmallVector<uint64_t, 64> Record;
 463   Stream.EnterSubblock(llvm::bitc::BLOCKINFO_BLOCK_ID, 3);
 464
 465 #define BLOCK(X) emitBlockID(X ## _ID, #X, Stream, Record)
 466 #define RECORD(X) emitRecordID(X, #X, Stream, Record)
 467   BLOCK(GLOBAL_INDEX_BLOCK);
 468   RECORD(INDEX_METADATA);
 469   RECORD(MODULE);
 470   RECORD(IDENTIFIER_INDEX);
 471 #undef RECORD
 472 #undef BLOCK
 473
 474   Stream.ExitBlock();
 475 }
 476
 477 namespace {
 478   class InterestingASTIdentifierLookupTrait
 479     : public serialization::reader::ASTIdentifierLookupTraitBase {
 480
 481   public:
 482     /// \brief The identifier and whether it is "interesting".
 483     typedef std::pair<StringRef, bool> data_type;
 484
 485     data_type ReadData(const internal_key_type& k,
 486                        const unsigned char* d,
 487                        unsigned DataLen) {
 488       // The first bit indicates whether this identifier is interesting.
 489       // That's all we care about.
 490       using namespace llvm::support;
 491       unsigned RawID = endian::readNext<uint32_t, little, unaligned>(d);
 492       bool IsInteresting = RawID & 0x01;
 493       return std::make_pair(k, IsInteresting);
 494     }
 495   };
 496 }
 497
 498 bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) {
 499   // Open the module file.
 500
 501   auto Buffer = FileMgr.getBufferForFile(File, /*isVolatile=*/true);
 502   if (!Buffer) {
 503     return true;
 504   }
 505
 506   // Initialize the input stream
 507   llvm::BitstreamReader InStreamFile;
 508   PCHContainerRdr.ExtractPCH((*Buffer)->getMemBufferRef(), InStreamFile);
 509   llvm::BitstreamCursor InStream(InStreamFile);
 510
 511   // Sniff for the signature.
 512   if (InStream.Read(8) != 'C' ||
 513       InStream.Read(8) != 'P' ||
 514       InStream.Read(8) != 'C' ||
 515       InStream.Read(8) != 'H') {
 516     return true;
 517   }
 518
 519   // Record this module file and assign it a unique ID (if it doesn't have
 520   // one already).
 521   unsigned ID = getModuleFileInfo(File).ID;
 522
 523   // Search for the blocks and records we care about.
 524   enum { Other, ControlBlock, ASTBlock } State = Other;
 525   bool Done = false;
 526   while (!Done) {
 527     llvm::BitstreamEntry Entry = InStream.advance();
 528     switch (Entry.Kind) {
 529     case llvm::BitstreamEntry::Error:
 530       Done = true;
 531       continue;
 532
 533     case llvm::BitstreamEntry::Record:
 534       // In the 'other' state, just skip the record. We don't care.
 535       if (State == Other) {
 536         InStream.skipRecord(Entry.ID);
 537         continue;
 538       }
 539
 540       // Handle potentially-interesting records below.
 541       break;
 542
 543     case llvm::BitstreamEntry::SubBlock:
 544       if (Entry.ID == CONTROL_BLOCK_ID) {
 545         if (InStream.EnterSubBlock(CONTROL_BLOCK_ID))
 546           return true;
 547
 548         // Found the control block.
 549         State = ControlBlock;
 550         continue;
 551       }
 552
 553       if (Entry.ID == AST_BLOCK_ID) {
 554         if (InStream.EnterSubBlock(AST_BLOCK_ID))
 555           return true;
 556
 557         // Found the AST block.
 558         State = ASTBlock;
 559         continue;
 560       }
 561
 562       if (InStream.SkipBlock())
 563         return true;
 564
 565       continue;
 566
 567     case llvm::BitstreamEntry::EndBlock:
 568       State = Other;
 569       continue;
 570     }
 571
 572     // Read the given record.
 573     SmallVector<uint64_t, 64> Record;
 574     StringRef Blob;
 575     unsigned Code = InStream.readRecord(Entry.ID, Record, &Blob);
 576
 577     // Handle module dependencies.
 578     if (State == ControlBlock && Code == IMPORTS) {
 579       // Load each of the imported PCH files.
 580       unsigned Idx = 0, N = Record.size();
 581       while (Idx < N) {
 582         // Read information about the AST file.
 583
 584         // Skip the imported kind
 585         ++Idx;
 586
 587         // Skip the import location
 588         ++Idx;
 589
 590         // Load stored size/modification time.
 591         off_t StoredSize = (off_t)Record[Idx++];
 592         time_t StoredModTime = (time_t)Record[Idx++];
 593
 594         // Skip the stored signature.
 595         // FIXME: we could read the signature out of the import and validate it.
 596         Idx++;
 597
 598         // Retrieve the imported file name.
 599         unsigned Length = Record[Idx++];
 600         SmallString<128> ImportedFile(Record.begin() + Idx,
 601                                       Record.begin() + Idx + Length);
 602         Idx += Length;
 603
 604         // Find the imported module file.
 605         const FileEntry *DependsOnFile
 606           = FileMgr.getFile(ImportedFile, /*openFile=*/false,
 607                             /*cacheFailure=*/false);
 608         if (!DependsOnFile ||
 609             (StoredSize != DependsOnFile->getSize()) ||
 610             (StoredModTime != DependsOnFile->getModificationTime()))
 611           return true;
 612
 613         // Record the dependency.
 614         unsigned DependsOnID = getModuleFileInfo(DependsOnFile).ID;
 615         getModuleFileInfo(File).Dependencies.push_back(DependsOnID);
 616       }
 617
 618       continue;
 619     }
 620
 621     // Handle the identifier table
 622     if (State == ASTBlock && Code == IDENTIFIER_TABLE && Record[0] > 0) {
 623       typedef llvm::OnDiskIterableChainedHashTable<
 624           InterestingASTIdentifierLookupTrait> InterestingIdentifierTable;
 625       std::unique_ptr<InterestingIdentifierTable> Table(
 626           InterestingIdentifierTable::Create(
 627               (const unsigned char *)Blob.data() + Record[0],
 628               (const unsigned char *)Blob.data() + sizeof(uint32_t),
 629               (const unsigned char *)Blob.data()));
 630       for (InterestingIdentifierTable::data_iterator D = Table->data_begin(),
 631                                                      DEnd = Table->data_end();
 632            D != DEnd; ++D) {
 633         std::pair<StringRef, bool> Ident = *D;
 634         if (Ident.second)
 635           InterestingIdentifiers[Ident.first].push_back(ID);
 636         else
 637           (void)InterestingIdentifiers[Ident.first];
 638       }
 639     }
 640
 641     // We don't care about this record.
 642   }
 643
 644   return false;
 645 }
 646
 647 namespace {
 648
 649 /// \brief Trait used to generate the identifier index as an on-disk hash
 650 /// table.
 651 class IdentifierIndexWriterTrait {
 652 public:
 653   typedef StringRef key_type;
 654   typedef StringRef key_type_ref;
 655   typedef SmallVector<unsigned, 2> data_type;
 656   typedef const SmallVector<unsigned, 2> &data_type_ref;
 657   typedef unsigned hash_value_type;
 658   typedef unsigned offset_type;
 659
 660   static hash_value_type ComputeHash(key_type_ref Key) {
 661     return llvm::HashString(Key);
 662   }
 663
 664   std::pair<unsigned,unsigned>
 665   EmitKeyDataLength(raw_ostream& Out, key_type_ref Key, data_type_ref Data) {
 666     using namespace llvm::support;
 667     endian::Writer<little> LE(Out);
 668     unsigned KeyLen = Key.size();
 669     unsigned DataLen = Data.size() * 4;
 670     LE.write<uint16_t>(KeyLen);
 671     LE.write<uint16_t>(DataLen);
 672     return std::make_pair(KeyLen, DataLen);
 673   }
 674
 675   void EmitKey(raw_ostream& Out, key_type_ref Key, unsigned KeyLen) {
 676     Out.write(Key.data(), KeyLen);
 677   }
 678
 679   void EmitData(raw_ostream& Out, key_type_ref Key, data_type_ref Data,
 680                 unsigned DataLen) {
 681     using namespace llvm::support;
 682     for (unsigned I = 0, N = Data.size(); I != N; ++I)
 683       endian::Writer<little>(Out).write<uint32_t>(Data[I]);
 684   }
 685 };
 686
 687 }
 688
 689 void GlobalModuleIndexBuilder::writeIndex(llvm::BitstreamWriter &Stream) {
 690   using namespace llvm;
 691
 692   // Emit the file header.
 693   Stream.Emit((unsigned)'B', 8);
 694   Stream.Emit((unsigned)'C', 8);
 695   Stream.Emit((unsigned)'G', 8);
 696   Stream.Emit((unsigned)'I', 8);
 697
 698   // Write the block-info block, which describes the records in this bitcode
 699   // file.
 700   emitBlockInfoBlock(Stream);
 701
 702   Stream.EnterSubblock(GLOBAL_INDEX_BLOCK_ID, 3);
 703
 704   // Write the metadata.
 705   SmallVector<uint64_t, 2> Record;
 706   Record.push_back(CurrentVersion);
 707   Stream.EmitRecord(INDEX_METADATA, Record);
 708
 709   // Write the set of known module files.
 710   for (ModuleFilesMap::iterator M = ModuleFiles.begin(),
 711                                 MEnd = ModuleFiles.end();
 712        M != MEnd; ++M) {
 713     Record.clear();
 714     Record.push_back(M->second.ID);
 715     Record.push_back(M->first->getSize());
 716     Record.push_back(M->first->getModificationTime());
 717
 718     // File name
 719     StringRef Name(M->first->getName());
 720     Record.push_back(Name.size());
 721     Record.append(Name.begin(), Name.end());
 722
 723     // Dependencies
 724     Record.push_back(M->second.Dependencies.size());
 725     Record.append(M->second.Dependencies.begin(), M->second.Dependencies.end());
 726     Stream.EmitRecord(MODULE, Record);
 727   }
 728
 729   // Write the identifier -> module file mapping.
 730   {
 731     llvm::OnDiskChainedHashTableGenerator<IdentifierIndexWriterTrait> Generator;
 732     IdentifierIndexWriterTrait Trait;
 733
 734     // Populate the hash table.
 735     for (InterestingIdentifierMap::iterator I = InterestingIdentifiers.begin(),
 736                                             IEnd = InterestingIdentifiers.end();
 737          I != IEnd; ++I) {
 738       Generator.insert(I->first(), I->second, Trait);
 739     }
 740
 741     // Create the on-disk hash table in a buffer.
 742     SmallString<4096> IdentifierTable;
 743     uint32_t BucketOffset;
 744     {
 745       using namespace llvm::support;
 746       llvm::raw_svector_ostream Out(IdentifierTable);
 747       // Make sure that no bucket is at offset 0
 748       endian::Writer<little>(Out).write<uint32_t>(0);
 749       BucketOffset = Generator.Emit(Out, Trait);
 750     }
 751
 752     // Create a blob abbreviation
 753     BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
 754     Abbrev->Add(BitCodeAbbrevOp(IDENTIFIER_INDEX));
 755     Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
 756     Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
 757     unsigned IDTableAbbrev = Stream.EmitAbbrev(Abbrev);
 758
 759     // Write the identifier table
 760     uint64_t Record[] = {IDENTIFIER_INDEX, BucketOffset};
 761     Stream.EmitRecordWithBlob(IDTableAbbrev, Record, IdentifierTable);
 762   }
 763
 764   Stream.ExitBlock();
 765 }
 766
 767 GlobalModuleIndex::ErrorCode
 768 GlobalModuleIndex::writeIndex(FileManager &FileMgr,
 769                               const PCHContainerReader &PCHContainerRdr,
 770                               StringRef Path) {
 771   llvm::SmallString<128> IndexPath;
 772   IndexPath += Path;
 773   llvm::sys::path::append(IndexPath, IndexFileName);
 774
 775   // Coordinate building the global index file with other processes that might
 776   // try to do the same.
 777   llvm::LockFileManager Locked(IndexPath);
 778   switch (Locked) {
 779   case llvm::LockFileManager::LFS_Error:
 780     return EC_IOError;
 781
 782   case llvm::LockFileManager::LFS_Owned:
 783     // We're responsible for building the index ourselves. Do so below.
 784     break;
 785
 786   case llvm::LockFileManager::LFS_Shared:
 787     // Someone else is responsible for building the index. We don't care
 788     // when they finish, so we're done.
 789     return EC_Building;
 790   }
 791
 792   // The module index builder.
 793   GlobalModuleIndexBuilder Builder(FileMgr, PCHContainerRdr);
 794
 795   // Load each of the module files.
 796   std::error_code EC;
 797   for (llvm::sys::fs::directory_iterator D(Path, EC), DEnd;
 798        D != DEnd && !EC;
 799        D.increment(EC)) {
 800     // If this isn't a module file, we don't care.
 801     if (llvm::sys::path::extension(D->path()) != ".pcm") {
 802       // ... unless it's a .pcm.lock file, which indicates that someone is
 803       // in the process of rebuilding a module. They'll rebuild the index
 804       // at the end of that translation unit, so we don't have to.
 805       if (llvm::sys::path::extension(D->path()) == ".pcm.lock")
 806         return EC_Building;
 807
 808       continue;
 809     }
 810
 811     // If we can't find the module file, skip it.
 812     const FileEntry *ModuleFile = FileMgr.getFile(D->path());
 813     if (!ModuleFile)
 814       continue;
 815
 816     // Load this module file.
 817     if (Builder.loadModuleFile(ModuleFile))
 818       return EC_IOError;
 819   }
 820
 821   // The output buffer, into which the global index will be written.
 822   SmallVector<char, 16> OutputBuffer;
 823   {
 824     llvm::BitstreamWriter OutputStream(OutputBuffer);
 825     Builder.writeIndex(OutputStream);
 826   }
 827
 828   // Write the global index file to a temporary file.
 829   llvm::SmallString<128> IndexTmpPath;
 830   int TmpFD;
 831   if (llvm::sys::fs::createUniqueFile(IndexPath + "-%%%%%%%%", TmpFD,
 832                                       IndexTmpPath))
 833     return EC_IOError;
 834
 835   // Open the temporary global index file for output.
 836   llvm::raw_fd_ostream Out(TmpFD, true);
 837   if (Out.has_error())
 838     return EC_IOError;
 839
 840   // Write the index.
 841   Out.write(OutputBuffer.data(), OutputBuffer.size());
 842   Out.close();
 843   if (Out.has_error())
 844     return EC_IOError;
 845
 846   // Remove the old index file. It isn't relevant any more.
 847   llvm::sys::fs::remove(IndexPath);
 848
 849   // Rename the newly-written index file to the proper name.
 850   if (llvm::sys::fs::rename(IndexTmpPath, IndexPath)) {
 851     // Rename failed; just remove the
 852     llvm::sys::fs::remove(IndexTmpPath);
 853     return EC_IOError;
 854   }
 855
 856   // We're done.
 857   return EC_None;
 858 }
 859
 860 namespace {
 861   class GlobalIndexIdentifierIterator : public IdentifierIterator {
 862     /// \brief The current position within the identifier lookup table.
 863     IdentifierIndexTable::key_iterator Current;
 864
 865     /// \brief The end position within the identifier lookup table.
 866     IdentifierIndexTable::key_iterator End;
 867
 868   public:
 869     explicit GlobalIndexIdentifierIterator(IdentifierIndexTable &Idx) {
 870       Current = Idx.key_begin();
 871       End = Idx.key_end();
 872     }
 873
 874     StringRef Next() override {
 875       if (Current == End)
 876         return StringRef();
 877
 878       StringRef Result = *Current;
 879       ++Current;
 880       return Result;
 881     }
 882   };
 883 }
 884
 885 IdentifierIterator *GlobalModuleIndex::createIdentifierIterator() const {
 886   IdentifierIndexTable &Table =
 887     *static_cast<IdentifierIndexTable *>(IdentifierIndex);
 888   return new GlobalIndexIdentifierIterator(Table);
 889 }