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

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