contrib/llvm-project/clang/lib/Serialization/GlobalModuleIndex.cpp

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