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 main bitstream cursor for the main block.
 249   llvm::BitstreamCursor Cursor(*Buffer);
 250
 251   // Sniff for the signature.
 252   if (Cursor.Read(8) != 'B' ||
 253       Cursor.Read(8) != 'C' ||
 254       Cursor.Read(8) != 'G' ||
 255       Cursor.Read(8) != 'I') {
 256     return std::make_pair(nullptr, EC_IOError);
 257   }
 258
 259   return std::make_pair(new GlobalModuleIndex(std::move(Buffer), Cursor),
 260                         EC_None);
 261 }
 262
 263 void
 264 GlobalModuleIndex::getKnownModules(SmallVectorImpl<ModuleFile *> &ModuleFiles) {
 265   ModuleFiles.clear();
 266   for (unsigned I = 0, N = Modules.size(); I != N; ++I) {
 267     if (ModuleFile *MF = Modules[I].File)
 268       ModuleFiles.push_back(MF);
 269   }
 270 }
 271
 272 void GlobalModuleIndex::getModuleDependencies(
 273        ModuleFile *File,
 274        SmallVectorImpl<ModuleFile *> &Dependencies) {
 275   // Look for information about this module file.
 276   llvm::DenseMap<ModuleFile *, unsigned>::iterator Known
 277     = ModulesByFile.find(File);
 278   if (Known == ModulesByFile.end())
 279     return;
 280
 281   // Record dependencies.
 282   Dependencies.clear();
 283   ArrayRef<unsigned> StoredDependencies = Modules[Known->second].Dependencies;
 284   for (unsigned I = 0, N = StoredDependencies.size(); I != N; ++I) {
 285     if (ModuleFile *MF = Modules[I].File)
 286       Dependencies.push_back(MF);
 287   }
 288 }
 289
 290 bool GlobalModuleIndex::lookupIdentifier(StringRef Name, HitSet &Hits) {
 291   Hits.clear();
 292
 293   // If there's no identifier index, there is nothing we can do.
 294   if (!IdentifierIndex)
 295     return false;
 296
 297   // Look into the identifier index.
 298   ++NumIdentifierLookups;
 299   IdentifierIndexTable &Table
 300     = *static_cast<IdentifierIndexTable *>(IdentifierIndex);
 301   IdentifierIndexTable::iterator Known = Table.find(Name);
 302   if (Known == Table.end()) {
 303     return true;
 304   }
 305
 306   SmallVector<unsigned, 2> ModuleIDs = *Known;
 307   for (unsigned I = 0, N = ModuleIDs.size(); I != N; ++I) {
 308     if (ModuleFile *MF = Modules[ModuleIDs[I]].File)
 309       Hits.insert(MF);
 310   }
 311
 312   ++NumIdentifierLookupHits;
 313   return true;
 314 }
 315
 316 bool GlobalModuleIndex::loadedModuleFile(ModuleFile *File) {
 317   // Look for the module in the global module index based on the module name.
 318   StringRef Name = File->ModuleName;
 319   llvm::StringMap<unsigned>::iterator Known = UnresolvedModules.find(Name);
 320   if (Known == UnresolvedModules.end()) {
 321     return true;
 322   }
 323
 324   // Rectify this module with the global module index.
 325   ModuleInfo &Info = Modules[Known->second];
 326
 327   //  If the size and modification time match what we expected, record this
 328   // module file.
 329   bool Failed = true;
 330   if (File->File->getSize() == Info.Size &&
 331       File->File->getModificationTime() == Info.ModTime) {
 332     Info.File = File;
 333     ModulesByFile[File] = Known->second;
 334
 335     Failed = false;
 336   }
 337
 338   // One way or another, we have resolved this module file.
 339   UnresolvedModules.erase(Known);
 340   return Failed;
 341 }
 342
 343 void GlobalModuleIndex::printStats() {
 344   std::fprintf(stderr, "*** Global Module Index Statistics:\n");
 345   if (NumIdentifierLookups) {
 346     fprintf(stderr, "  %u / %u identifier lookups succeeded (%f%%)\n",
 347             NumIdentifierLookupHits, NumIdentifierLookups,
 348             (double)NumIdentifierLookupHits*100.0/NumIdentifierLookups);
 349   }
 350   std::fprintf(stderr, "\n");
 351 }
 352
 353 LLVM_DUMP_METHOD void GlobalModuleIndex::dump() {
 354   llvm::errs() << "*** Global Module Index Dump:\n";
 355   llvm::errs() << "Module files:\n";
 356   for (auto &MI : Modules) {
 357     llvm::errs() << "** " << MI.FileName << "\n";
 358     if (MI.File)
 359       MI.File->dump();
 360     else
 361       llvm::errs() << "\n";
 362   }
 363   llvm::errs() << "\n";
 364 }
 365
 366 //----------------------------------------------------------------------------//
 367 // Global module index writer.
 368 //----------------------------------------------------------------------------//
 369
 370 namespace {
 371   /// \brief Provides information about a specific module file.
 372   struct ModuleFileInfo {
 373     /// \brief The numberic ID for this module file.
 374     unsigned ID;
 375
 376     /// \brief The set of modules on which this module depends. Each entry is
 377     /// a module ID.
 378     SmallVector<unsigned, 4> Dependencies;
 379   };
 380
 381   /// \brief Builder that generates the global module index file.
 382   class GlobalModuleIndexBuilder {
 383     FileManager &FileMgr;
 384     const PCHContainerReader &PCHContainerRdr;
 385
 386     /// \brief Mapping from files to module file information.
 387     typedef llvm::MapVector<const FileEntry *, ModuleFileInfo> ModuleFilesMap;
 388
 389     /// \brief Information about each of the known module files.
 390     ModuleFilesMap ModuleFiles;
 391
 392     /// \brief Mapping from identifiers to the list of module file IDs that
 393     /// consider this identifier to be interesting.
 394     typedef llvm::StringMap<SmallVector<unsigned, 2> > InterestingIdentifierMap;
 395
 396     /// \brief A mapping from all interesting identifiers to the set of module
 397     /// files in which those identifiers are considered interesting.
 398     InterestingIdentifierMap InterestingIdentifiers;
 399
 400     /// \brief Write the block-info block for the global module index file.
 401     void emitBlockInfoBlock(llvm::BitstreamWriter &Stream);
 402
 403     /// \brief Retrieve the module file information for the given file.
 404     ModuleFileInfo &getModuleFileInfo(const FileEntry *File) {
 405       llvm::MapVector<const FileEntry *, ModuleFileInfo>::iterator Known
 406         = ModuleFiles.find(File);
 407       if (Known != ModuleFiles.end())
 408         return Known->second;
 409
 410       unsigned NewID = ModuleFiles.size();
 411       ModuleFileInfo &Info = ModuleFiles[File];
 412       Info.ID = NewID;
 413       return Info;
 414     }
 415
 416   public:
 417     explicit GlobalModuleIndexBuilder(
 418         FileManager &FileMgr, const PCHContainerReader &PCHContainerRdr)
 419         : FileMgr(FileMgr), PCHContainerRdr(PCHContainerRdr) {}
 420
 421     /// \brief Load the contents of the given module file into the builder.
 422     ///
 423     /// \returns true if an error occurred, false otherwise.
 424     bool loadModuleFile(const FileEntry *File);
 425
 426     /// \brief Write the index to the given bitstream.
 427     void writeIndex(llvm::BitstreamWriter &Stream);
 428   };
 429 }
 430
 431 static void emitBlockID(unsigned ID, const char *Name,
 432                         llvm::BitstreamWriter &Stream,
 433                         SmallVectorImpl<uint64_t> &Record) {
 434   Record.clear();
 435   Record.push_back(ID);
 436   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_SETBID, Record);
 437
 438   // Emit the block name if present.
 439   if (!Name || Name[0] == 0) return;
 440   Record.clear();
 441   while (*Name)
 442     Record.push_back(*Name++);
 443   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_BLOCKNAME, Record);
 444 }
 445
 446 static void emitRecordID(unsigned ID, const char *Name,
 447                          llvm::BitstreamWriter &Stream,
 448                          SmallVectorImpl<uint64_t> &Record) {
 449   Record.clear();
 450   Record.push_back(ID);
 451   while (*Name)
 452     Record.push_back(*Name++);
 453   Stream.EmitRecord(llvm::bitc::BLOCKINFO_CODE_SETRECORDNAME, Record);
 454 }
 455
 456 void
 457 GlobalModuleIndexBuilder::emitBlockInfoBlock(llvm::BitstreamWriter &Stream) {
 458   SmallVector<uint64_t, 64> Record;
 459   Stream.EnterBlockInfoBlock();
 460
 461 #define BLOCK(X) emitBlockID(X ## _ID, #X, Stream, Record)
 462 #define RECORD(X) emitRecordID(X, #X, Stream, Record)
 463   BLOCK(GLOBAL_INDEX_BLOCK);
 464   RECORD(INDEX_METADATA);
 465   RECORD(MODULE);
 466   RECORD(IDENTIFIER_INDEX);
 467 #undef RECORD
 468 #undef BLOCK
 469
 470   Stream.ExitBlock();
 471 }
 472
 473 namespace {
 474   class InterestingASTIdentifierLookupTrait
 475     : public serialization::reader::ASTIdentifierLookupTraitBase {
 476
 477   public:
 478     /// \brief The identifier and whether it is "interesting".
 479     typedef std::pair<StringRef, bool> data_type;
 480
 481     data_type ReadData(const internal_key_type& k,
 482                        const unsigned char* d,
 483                        unsigned DataLen) {
 484       // The first bit indicates whether this identifier is interesting.
 485       // That's all we care about.
 486       using namespace llvm::support;
 487       unsigned RawID = endian::readNext<uint32_t, little, unaligned>(d);
 488       bool IsInteresting = RawID & 0x01;
 489       return std::make_pair(k, IsInteresting);
 490     }
 491   };
 492 }
 493
 494 bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) {
 495   // Open the module file.
 496
 497   auto Buffer = FileMgr.getBufferForFile(File, /*isVolatile=*/true);
 498   if (!Buffer) {
 499     return true;
 500   }
 501
 502   // Initialize the input stream
 503   llvm::BitstreamCursor InStream(PCHContainerRdr.ExtractPCH(**Buffer));
 504
 505   // Sniff for the signature.
 506   if (InStream.Read(8) != 'C' ||
 507       InStream.Read(8) != 'P' ||
 508       InStream.Read(8) != 'C' ||
 509       InStream.Read(8) != 'H') {
 510     return true;
 511   }
 512
 513   // Record this module file and assign it a unique ID (if it doesn't have
 514   // one already).
 515   unsigned ID = getModuleFileInfo(File).ID;
 516
 517   // Search for the blocks and records we care about.
 518   enum { Other, ControlBlock, ASTBlock } State = Other;
 519   bool Done = false;
 520   while (!Done) {
 521     llvm::BitstreamEntry Entry = InStream.advance();
 522     switch (Entry.Kind) {
 523     case llvm::BitstreamEntry::Error:
 524       Done = true;
 525       continue;
 526
 527     case llvm::BitstreamEntry::Record:
 528       // In the 'other' state, just skip the record. We don't care.
 529       if (State == Other) {
 530         InStream.skipRecord(Entry.ID);
 531         continue;
 532       }
 533
 534       // Handle potentially-interesting records below.
 535       break;
 536
 537     case llvm::BitstreamEntry::SubBlock:
 538       if (Entry.ID == CONTROL_BLOCK_ID) {
 539         if (InStream.EnterSubBlock(CONTROL_BLOCK_ID))
 540           return true;
 541
 542         // Found the control block.
 543         State = ControlBlock;
 544         continue;
 545       }
 546
 547       if (Entry.ID == AST_BLOCK_ID) {
 548         if (InStream.EnterSubBlock(AST_BLOCK_ID))
 549           return true;
 550
 551         // Found the AST block.
 552         State = ASTBlock;
 553         continue;
 554       }
 555
 556       if (InStream.SkipBlock())
 557         return true;
 558
 559       continue;
 560
 561     case llvm::BitstreamEntry::EndBlock:
 562       State = Other;
 563       continue;
 564     }
 565
 566     // Read the given record.
 567     SmallVector<uint64_t, 64> Record;
 568     StringRef Blob;
 569     unsigned Code = InStream.readRecord(Entry.ID, Record, &Blob);
 570
 571     // Handle module dependencies.
 572     if (State == ControlBlock && Code == IMPORTS) {
 573       // Load each of the imported PCH files.
 574       unsigned Idx = 0, N = Record.size();
 575       while (Idx < N) {
 576         // Read information about the AST file.
 577
 578         // Skip the imported kind
 579         ++Idx;
 580
 581         // Skip the import location
 582         ++Idx;
 583
 584         // Load stored size/modification time.
 585         off_t StoredSize = (off_t)Record[Idx++];
 586         time_t StoredModTime = (time_t)Record[Idx++];
 587
 588         // Skip the stored signature.
 589         // FIXME: we could read the signature out of the import and validate it.
 590         Idx++;
 591
 592         // Retrieve the imported file name.
 593         unsigned Length = Record[Idx++];
 594         SmallString<128> ImportedFile(Record.begin() + Idx,
 595                                       Record.begin() + Idx + Length);
 596         Idx += Length;
 597
 598         // Find the imported module file.
 599         const FileEntry *DependsOnFile
 600           = FileMgr.getFile(ImportedFile, /*openFile=*/false,
 601                             /*cacheFailure=*/false);
 602         if (!DependsOnFile ||
 603             (StoredSize != DependsOnFile->getSize()) ||
 604             (StoredModTime != DependsOnFile->getModificationTime()))
 605           return true;
 606
 607         // Record the dependency.
 608         unsigned DependsOnID = getModuleFileInfo(DependsOnFile).ID;
 609         getModuleFileInfo(File).Dependencies.push_back(DependsOnID);
 610       }
 611
 612       continue;
 613     }
 614
 615     // Handle the identifier table
 616     if (State == ASTBlock && Code == IDENTIFIER_TABLE && Record[0] > 0) {
 617       typedef llvm::OnDiskIterableChainedHashTable<
 618           InterestingASTIdentifierLookupTrait> InterestingIdentifierTable;
 619       std::unique_ptr<InterestingIdentifierTable> Table(
 620           InterestingIdentifierTable::Create(
 621               (const unsigned char *)Blob.data() + Record[0],
 622               (const unsigned char *)Blob.data() + sizeof(uint32_t),
 623               (const unsigned char *)Blob.data()));
 624       for (InterestingIdentifierTable::data_iterator D = Table->data_begin(),
 625                                                      DEnd = Table->data_end();
 626            D != DEnd; ++D) {
 627         std::pair<StringRef, bool> Ident = *D;
 628         if (Ident.second)
 629           InterestingIdentifiers[Ident.first].push_back(ID);
 630         else
 631           (void)InterestingIdentifiers[Ident.first];
 632       }
 633     }
 634
 635     // We don't care about this record.
 636   }
 637
 638   return false;
 639 }
 640
 641 namespace {
 642
 643 /// \brief Trait used to generate the identifier index as an on-disk hash
 644 /// table.
 645 class IdentifierIndexWriterTrait {
 646 public:
 647   typedef StringRef key_type;
 648   typedef StringRef key_type_ref;
 649   typedef SmallVector<unsigned, 2> data_type;
 650   typedef const SmallVector<unsigned, 2> &data_type_ref;
 651   typedef unsigned hash_value_type;
 652   typedef unsigned offset_type;
 653
 654   static hash_value_type ComputeHash(key_type_ref Key) {
 655     return llvm::HashString(Key);
 656   }
 657
 658   std::pair<unsigned,unsigned>
 659   EmitKeyDataLength(raw_ostream& Out, key_type_ref Key, data_type_ref Data) {
 660     using namespace llvm::support;
 661     endian::Writer<little> LE(Out);
 662     unsigned KeyLen = Key.size();
 663     unsigned DataLen = Data.size() * 4;
 664     LE.write<uint16_t>(KeyLen);
 665     LE.write<uint16_t>(DataLen);
 666     return std::make_pair(KeyLen, DataLen);
 667   }
 668
 669   void EmitKey(raw_ostream& Out, key_type_ref Key, unsigned KeyLen) {
 670     Out.write(Key.data(), KeyLen);
 671   }
 672
 673   void EmitData(raw_ostream& Out, key_type_ref Key, data_type_ref Data,
 674                 unsigned DataLen) {
 675     using namespace llvm::support;
 676     for (unsigned I = 0, N = Data.size(); I != N; ++I)
 677       endian::Writer<little>(Out).write<uint32_t>(Data[I]);
 678   }
 679 };
 680
 681 }
 682
 683 void GlobalModuleIndexBuilder::writeIndex(llvm::BitstreamWriter &Stream) {
 684   using namespace llvm;
 685
 686   // Emit the file header.
 687   Stream.Emit((unsigned)'B', 8);
 688   Stream.Emit((unsigned)'C', 8);
 689   Stream.Emit((unsigned)'G', 8);
 690   Stream.Emit((unsigned)'I', 8);
 691
 692   // Write the block-info block, which describes the records in this bitcode
 693   // file.
 694   emitBlockInfoBlock(Stream);
 695
 696   Stream.EnterSubblock(GLOBAL_INDEX_BLOCK_ID, 3);
 697
 698   // Write the metadata.
 699   SmallVector<uint64_t, 2> Record;
 700   Record.push_back(CurrentVersion);
 701   Stream.EmitRecord(INDEX_METADATA, Record);
 702
 703   // Write the set of known module files.
 704   for (ModuleFilesMap::iterator M = ModuleFiles.begin(),
 705                                 MEnd = ModuleFiles.end();
 706        M != MEnd; ++M) {
 707     Record.clear();
 708     Record.push_back(M->second.ID);
 709     Record.push_back(M->first->getSize());
 710     Record.push_back(M->first->getModificationTime());
 711
 712     // File name
 713     StringRef Name(M->first->getName());
 714     Record.push_back(Name.size());
 715     Record.append(Name.begin(), Name.end());
 716
 717     // Dependencies
 718     Record.push_back(M->second.Dependencies.size());
 719     Record.append(M->second.Dependencies.begin(), M->second.Dependencies.end());
 720     Stream.EmitRecord(MODULE, Record);
 721   }
 722
 723   // Write the identifier -> module file mapping.
 724   {
 725     llvm::OnDiskChainedHashTableGenerator<IdentifierIndexWriterTrait> Generator;
 726     IdentifierIndexWriterTrait Trait;
 727
 728     // Populate the hash table.
 729     for (InterestingIdentifierMap::iterator I = InterestingIdentifiers.begin(),
 730                                             IEnd = InterestingIdentifiers.end();
 731          I != IEnd; ++I) {
 732       Generator.insert(I->first(), I->second, Trait);
 733     }
 734
 735     // Create the on-disk hash table in a buffer.
 736     SmallString<4096> IdentifierTable;
 737     uint32_t BucketOffset;
 738     {
 739       using namespace llvm::support;
 740       llvm::raw_svector_ostream Out(IdentifierTable);
 741       // Make sure that no bucket is at offset 0
 742       endian::Writer<little>(Out).write<uint32_t>(0);
 743       BucketOffset = Generator.Emit(Out, Trait);
 744     }
 745
 746     // Create a blob abbreviation
 747     auto Abbrev = std::make_shared<BitCodeAbbrev>();
 748     Abbrev->Add(BitCodeAbbrevOp(IDENTIFIER_INDEX));
 749     Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
 750     Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
 751     unsigned IDTableAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
 752
 753     // Write the identifier table
 754     uint64_t Record[] = {IDENTIFIER_INDEX, BucketOffset};
 755     Stream.EmitRecordWithBlob(IDTableAbbrev, Record, IdentifierTable);
 756   }
 757
 758   Stream.ExitBlock();
 759 }
 760
 761 GlobalModuleIndex::ErrorCode
 762 GlobalModuleIndex::writeIndex(FileManager &FileMgr,
 763                               const PCHContainerReader &PCHContainerRdr,
 764                               StringRef Path) {
 765   llvm::SmallString<128> IndexPath;
 766   IndexPath += Path;
 767   llvm::sys::path::append(IndexPath, IndexFileName);
 768
 769   // Coordinate building the global index file with other processes that might
 770   // try to do the same.
 771   llvm::LockFileManager Locked(IndexPath);
 772   switch (Locked) {
 773   case llvm::LockFileManager::LFS_Error:
 774     return EC_IOError;
 775
 776   case llvm::LockFileManager::LFS_Owned:
 777     // We're responsible for building the index ourselves. Do so below.
 778     break;
 779
 780   case llvm::LockFileManager::LFS_Shared:
 781     // Someone else is responsible for building the index. We don't care
 782     // when they finish, so we're done.
 783     return EC_Building;
 784   }
 785
 786   // The module index builder.
 787   GlobalModuleIndexBuilder Builder(FileMgr, PCHContainerRdr);
 788
 789   // Load each of the module files.
 790   std::error_code EC;
 791   for (llvm::sys::fs::directory_iterator D(Path, EC), DEnd;
 792        D != DEnd && !EC;
 793        D.increment(EC)) {
 794     // If this isn't a module file, we don't care.
 795     if (llvm::sys::path::extension(D->path()) != ".pcm") {
 796       // ... unless it's a .pcm.lock file, which indicates that someone is
 797       // in the process of rebuilding a module. They'll rebuild the index
 798       // at the end of that translation unit, so we don't have to.
 799       if (llvm::sys::path::extension(D->path()) == ".pcm.lock")
 800         return EC_Building;
 801
 802       continue;
 803     }
 804
 805     // If we can't find the module file, skip it.
 806     const FileEntry *ModuleFile = FileMgr.getFile(D->path());
 807     if (!ModuleFile)
 808       continue;
 809
 810     // Load this module file.
 811     if (Builder.loadModuleFile(ModuleFile))
 812       return EC_IOError;
 813   }
 814
 815   // The output buffer, into which the global index will be written.
 816   SmallVector<char, 16> OutputBuffer;
 817   {
 818     llvm::BitstreamWriter OutputStream(OutputBuffer);
 819     Builder.writeIndex(OutputStream);
 820   }
 821
 822   // Write the global index file to a temporary file.
 823   llvm::SmallString<128> IndexTmpPath;
 824   int TmpFD;
 825   if (llvm::sys::fs::createUniqueFile(IndexPath + "-%%%%%%%%", TmpFD,
 826                                       IndexTmpPath))
 827     return EC_IOError;
 828
 829   // Open the temporary global index file for output.
 830   llvm::raw_fd_ostream Out(TmpFD, true);
 831   if (Out.has_error())
 832     return EC_IOError;
 833
 834   // Write the index.
 835   Out.write(OutputBuffer.data(), OutputBuffer.size());
 836   Out.close();
 837   if (Out.has_error())
 838     return EC_IOError;
 839
 840   // Remove the old index file. It isn't relevant any more.
 841   llvm::sys::fs::remove(IndexPath);
 842
 843   // Rename the newly-written index file to the proper name.
 844   if (llvm::sys::fs::rename(IndexTmpPath, IndexPath)) {
 845     // Rename failed; just remove the
 846     llvm::sys::fs::remove(IndexTmpPath);
 847     return EC_IOError;
 848   }
 849
 850   // We're done.
 851   return EC_None;
 852 }
 853
 854 namespace {
 855   class GlobalIndexIdentifierIterator : public IdentifierIterator {
 856     /// \brief The current position within the identifier lookup table.
 857     IdentifierIndexTable::key_iterator Current;
 858
 859     /// \brief The end position within the identifier lookup table.
 860     IdentifierIndexTable::key_iterator End;
 861
 862   public:
 863     explicit GlobalIndexIdentifierIterator(IdentifierIndexTable &Idx) {
 864       Current = Idx.key_begin();
 865       End = Idx.key_end();
 866     }
 867
 868     StringRef Next() override {
 869       if (Current == End)
 870         return StringRef();
 871
 872       StringRef Result = *Current;
 873       ++Current;
 874       return Result;
 875     }
 876   };
 877 }
 878
 879 IdentifierIterator *GlobalModuleIndex::createIdentifierIterator() const {
 880   IdentifierIndexTable &Table =
 881     *static_cast<IdentifierIndexTable *>(IdentifierIndex);
 882   return new GlobalIndexIdentifierIterator(Table);
 883 }