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