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/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 }
    886