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