• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
EqualKey(const internal_key_type & a,const internal_key_type & b)79   static bool EqualKey(const internal_key_type& a, const internal_key_type& b) {
80     return a == b;
81   }
82 
ComputeHash(const internal_key_type & a)83   static hash_value_type ComputeHash(const internal_key_type& a) {
84     return llvm::HashString(a);
85   }
86 
87   static std::pair<unsigned, unsigned>
ReadKeyDataLength(const unsigned char * & d)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&
GetInternalKey(const external_key_type & x)96   GetInternalKey(const external_key_type& x) { return x; }
97 
98   static const external_key_type&
GetExternalKey(const internal_key_type & x)99   GetExternalKey(const internal_key_type& x) { return x; }
100 
ReadKey(const unsigned char * d,unsigned n)101   static internal_key_type ReadKey(const unsigned char* d, unsigned n) {
102     return StringRef((const char *)d, n);
103   }
104 
ReadData(const internal_key_type & k,const unsigned char * d,unsigned DataLen)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 
GlobalModuleIndex(std::unique_ptr<llvm::MemoryBuffer> Buffer,llvm::BitstreamCursor Cursor)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 
~GlobalModuleIndex()231 GlobalModuleIndex::~GlobalModuleIndex() {
232   delete static_cast<IdentifierIndexTable *>(IdentifierIndex);
233 }
234 
235 std::pair<GlobalModuleIndex *, GlobalModuleIndex::ErrorCode>
readIndex(StringRef Path)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
getKnownModules(SmallVectorImpl<ModuleFile * > & ModuleFiles)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 
getModuleDependencies(ModuleFile * File,SmallVectorImpl<ModuleFile * > & Dependencies)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 
lookupIdentifier(StringRef Name,HitSet & Hits)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 
loadedModuleFile(ModuleFile * File)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 
printStats()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 
dump()357 LLVM_DUMP_METHOD 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.
getModuleFileInfo(const FileEntry * 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:
GlobalModuleIndexBuilder(FileManager & FileMgr,const PCHContainerReader & PCHContainerRdr)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 
emitBlockID(unsigned ID,const char * Name,llvm::BitstreamWriter & Stream,SmallVectorImpl<uint64_t> & Record)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 
emitRecordID(unsigned ID,const char * Name,llvm::BitstreamWriter & Stream,SmallVectorImpl<uint64_t> & Record)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
emitBlockInfoBlock(llvm::BitstreamWriter & Stream)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 
ReadData(const internal_key_type & k,const unsigned char * d,unsigned DataLen)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 
loadModuleFile(const FileEntry * File)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 
ComputeHash(key_type_ref Key)660   static hash_value_type ComputeHash(key_type_ref Key) {
661     return llvm::HashString(Key);
662   }
663 
664   std::pair<unsigned,unsigned>
EmitKeyDataLength(raw_ostream & Out,key_type_ref Key,data_type_ref Data)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 
EmitKey(raw_ostream & Out,key_type_ref Key,unsigned KeyLen)675   void EmitKey(raw_ostream& Out, key_type_ref Key, unsigned KeyLen) {
676     Out.write(Key.data(), KeyLen);
677   }
678 
EmitData(raw_ostream & Out,key_type_ref Key,data_type_ref Data,unsigned DataLen)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 
writeIndex(llvm::BitstreamWriter & Stream)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
writeIndex(FileManager & FileMgr,const PCHContainerReader & PCHContainerRdr,StringRef Path)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:
GlobalIndexIdentifierIterator(IdentifierIndexTable & Idx)869     explicit GlobalIndexIdentifierIterator(IdentifierIndexTable &Idx) {
870       Current = Idx.key_begin();
871       End = Idx.key_end();
872     }
873 
Next()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 
createIdentifierIterator() const885 IdentifierIterator *GlobalModuleIndex::createIdentifierIterator() const {
886   IdentifierIndexTable &Table =
887     *static_cast<IdentifierIndexTable *>(IdentifierIndex);
888   return new GlobalIndexIdentifierIterator(Table);
889 }
890