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