1//===--- HeaderSearch.cpp - Resolve Header File Locations ---===//
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 DirectoryLookup and HeaderSearch interfaces.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Lex/HeaderSearch.h"
15#include "clang/Basic/FileManager.h"
16#include "clang/Basic/IdentifierTable.h"
17#include "clang/Lex/HeaderMap.h"
18#include "clang/Lex/HeaderSearchOptions.h"
19#include "clang/Lex/LexDiagnostic.h"
20#include "clang/Lex/Lexer.h"
21#include "llvm/ADT/APInt.h"
22#include "llvm/ADT/Hashing.h"
23#include "llvm/ADT/SmallString.h"
24#include "llvm/Support/Capacity.h"
25#include "llvm/Support/FileSystem.h"
26#include "llvm/Support/Path.h"
27#include "llvm/Support/raw_ostream.h"
28#include <cstdio>
29#if defined(LLVM_ON_UNIX)
30#include <limits.h>
31#endif
32using namespace clang;
33
34const IdentifierInfo *
35HeaderFileInfo::getControllingMacro(ExternalIdentifierLookup *External) {
36  if (ControllingMacro)
37    return ControllingMacro;
38
39  if (!ControllingMacroID || !External)
40    return nullptr;
41
42  ControllingMacro = External->GetIdentifier(ControllingMacroID);
43  return ControllingMacro;
44}
45
46ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() {}
47
48HeaderSearch::HeaderSearch(IntrusiveRefCntPtr<HeaderSearchOptions> HSOpts,
49                           SourceManager &SourceMgr, DiagnosticsEngine &Diags,
50                           const LangOptions &LangOpts,
51                           const TargetInfo *Target)
52    : HSOpts(HSOpts), Diags(Diags), FileMgr(SourceMgr.getFileManager()),
53      FrameworkMap(64), ModMap(SourceMgr, Diags, LangOpts, Target, *this) {
54  AngledDirIdx = 0;
55  SystemDirIdx = 0;
56  NoCurDirSearch = false;
57
58  ExternalLookup = nullptr;
59  ExternalSource = nullptr;
60  NumIncluded = 0;
61  NumMultiIncludeFileOptzn = 0;
62  NumFrameworkLookups = NumSubFrameworkLookups = 0;
63
64  EnabledModules = LangOpts.Modules;
65}
66
67HeaderSearch::~HeaderSearch() {
68  // Delete headermaps.
69  for (unsigned i = 0, e = HeaderMaps.size(); i != e; ++i)
70    delete HeaderMaps[i].second;
71}
72
73void HeaderSearch::PrintStats() {
74  fprintf(stderr, "\n*** HeaderSearch Stats:\n");
75  fprintf(stderr, "%d files tracked.\n", (int)FileInfo.size());
76  unsigned NumOnceOnlyFiles = 0, MaxNumIncludes = 0, NumSingleIncludedFiles = 0;
77  for (unsigned i = 0, e = FileInfo.size(); i != e; ++i) {
78    NumOnceOnlyFiles += FileInfo[i].isImport;
79    if (MaxNumIncludes < FileInfo[i].NumIncludes)
80      MaxNumIncludes = FileInfo[i].NumIncludes;
81    NumSingleIncludedFiles += FileInfo[i].NumIncludes == 1;
82  }
83  fprintf(stderr, "  %d #import/#pragma once files.\n", NumOnceOnlyFiles);
84  fprintf(stderr, "  %d included exactly once.\n", NumSingleIncludedFiles);
85  fprintf(stderr, "  %d max times a file is included.\n", MaxNumIncludes);
86
87  fprintf(stderr, "  %d #include/#include_next/#import.\n", NumIncluded);
88  fprintf(stderr, "    %d #includes skipped due to"
89          " the multi-include optimization.\n", NumMultiIncludeFileOptzn);
90
91  fprintf(stderr, "%d framework lookups.\n", NumFrameworkLookups);
92  fprintf(stderr, "%d subframework lookups.\n", NumSubFrameworkLookups);
93}
94
95/// CreateHeaderMap - This method returns a HeaderMap for the specified
96/// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
97const HeaderMap *HeaderSearch::CreateHeaderMap(const FileEntry *FE) {
98  // We expect the number of headermaps to be small, and almost always empty.
99  // If it ever grows, use of a linear search should be re-evaluated.
100  if (!HeaderMaps.empty()) {
101    for (unsigned i = 0, e = HeaderMaps.size(); i != e; ++i)
102      // Pointer equality comparison of FileEntries works because they are
103      // already uniqued by inode.
104      if (HeaderMaps[i].first == FE)
105        return HeaderMaps[i].second;
106  }
107
108  if (const HeaderMap *HM = HeaderMap::Create(FE, FileMgr)) {
109    HeaderMaps.push_back(std::make_pair(FE, HM));
110    return HM;
111  }
112
113  return nullptr;
114}
115
116std::string HeaderSearch::getModuleFileName(Module *Module) {
117  return getModuleFileName(Module->Name, Module->ModuleMap->getName());
118}
119
120std::string HeaderSearch::getModuleFileName(StringRef ModuleName,
121                                            StringRef ModuleMapPath) {
122  // If we don't have a module cache path, we can't do anything.
123  if (ModuleCachePath.empty())
124    return std::string();
125
126  SmallString<256> Result(ModuleCachePath);
127  llvm::sys::fs::make_absolute(Result);
128
129  if (HSOpts->DisableModuleHash) {
130    llvm::sys::path::append(Result, ModuleName + ".pcm");
131  } else {
132    // Construct the name <ModuleName>-<hash of ModuleMapPath>.pcm which should
133    // be globally unique to this particular module. To avoid false-negatives
134    // on case-insensitive filesystems, we use lower-case, which is safe because
135    // to cause a collision the modules must have the same name, which is an
136    // error if they are imported in the same translation.
137    SmallString<256> AbsModuleMapPath(ModuleMapPath);
138    llvm::sys::fs::make_absolute(AbsModuleMapPath);
139    llvm::APInt Code(64, llvm::hash_value(AbsModuleMapPath.str().lower()));
140    SmallString<128> HashStr;
141    Code.toStringUnsigned(HashStr, /*Radix*/36);
142    llvm::sys::path::append(Result, ModuleName + "-" + HashStr.str() + ".pcm");
143  }
144  return Result.str().str();
145}
146
147Module *HeaderSearch::lookupModule(StringRef ModuleName, bool AllowSearch) {
148  // Look in the module map to determine if there is a module by this name.
149  Module *Module = ModMap.findModule(ModuleName);
150  if (Module || !AllowSearch)
151    return Module;
152
153  // Look through the various header search paths to load any available module
154  // maps, searching for a module map that describes this module.
155  for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
156    if (SearchDirs[Idx].isFramework()) {
157      // Search for or infer a module map for a framework.
158      SmallString<128> FrameworkDirName;
159      FrameworkDirName += SearchDirs[Idx].getFrameworkDir()->getName();
160      llvm::sys::path::append(FrameworkDirName, ModuleName + ".framework");
161      if (const DirectoryEntry *FrameworkDir
162            = FileMgr.getDirectory(FrameworkDirName)) {
163        bool IsSystem
164          = SearchDirs[Idx].getDirCharacteristic() != SrcMgr::C_User;
165        Module = loadFrameworkModule(ModuleName, FrameworkDir, IsSystem);
166        if (Module)
167          break;
168      }
169    }
170
171    // FIXME: Figure out how header maps and module maps will work together.
172
173    // Only deal with normal search directories.
174    if (!SearchDirs[Idx].isNormalDir())
175      continue;
176
177    bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
178    // Search for a module map file in this directory.
179    if (loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
180                          /*IsFramework*/false) == LMM_NewlyLoaded) {
181      // We just loaded a module map file; check whether the module is
182      // available now.
183      Module = ModMap.findModule(ModuleName);
184      if (Module)
185        break;
186    }
187
188    // Search for a module map in a subdirectory with the same name as the
189    // module.
190    SmallString<128> NestedModuleMapDirName;
191    NestedModuleMapDirName = SearchDirs[Idx].getDir()->getName();
192    llvm::sys::path::append(NestedModuleMapDirName, ModuleName);
193    if (loadModuleMapFile(NestedModuleMapDirName, IsSystem,
194                          /*IsFramework*/false) == LMM_NewlyLoaded){
195      // If we just loaded a module map file, look for the module again.
196      Module = ModMap.findModule(ModuleName);
197      if (Module)
198        break;
199    }
200
201    // If we've already performed the exhaustive search for module maps in this
202    // search directory, don't do it again.
203    if (SearchDirs[Idx].haveSearchedAllModuleMaps())
204      continue;
205
206    // Load all module maps in the immediate subdirectories of this search
207    // directory.
208    loadSubdirectoryModuleMaps(SearchDirs[Idx]);
209
210    // Look again for the module.
211    Module = ModMap.findModule(ModuleName);
212    if (Module)
213      break;
214  }
215
216  return Module;
217}
218
219//===----------------------------------------------------------------------===//
220// File lookup within a DirectoryLookup scope
221//===----------------------------------------------------------------------===//
222
223/// getName - Return the directory or filename corresponding to this lookup
224/// object.
225const char *DirectoryLookup::getName() const {
226  if (isNormalDir())
227    return getDir()->getName();
228  if (isFramework())
229    return getFrameworkDir()->getName();
230  assert(isHeaderMap() && "Unknown DirectoryLookup");
231  return getHeaderMap()->getFileName();
232}
233
234static const FileEntry *
235getFileAndSuggestModule(HeaderSearch &HS, StringRef FileName,
236                        const DirectoryEntry *Dir, bool IsSystemHeaderDir,
237                        ModuleMap::KnownHeader *SuggestedModule) {
238  // If we have a module map that might map this header, load it and
239  // check whether we'll have a suggestion for a module.
240  HS.hasModuleMap(FileName, Dir, IsSystemHeaderDir);
241  if (SuggestedModule) {
242    const FileEntry *File = HS.getFileMgr().getFile(FileName,
243                                                    /*OpenFile=*/false);
244    if (File) {
245      // If there is a module that corresponds to this header, suggest it.
246      *SuggestedModule = HS.findModuleForHeader(File);
247
248      // FIXME: This appears to be a no-op. We loaded the module map for this
249      // directory at the start of this function.
250      if (!SuggestedModule->getModule() &&
251          HS.hasModuleMap(FileName, Dir, IsSystemHeaderDir))
252        *SuggestedModule = HS.findModuleForHeader(File);
253    }
254
255    return File;
256  }
257
258  return HS.getFileMgr().getFile(FileName, /*openFile=*/true);
259}
260
261/// LookupFile - Lookup the specified file in this search path, returning it
262/// if it exists or returning null if not.
263const FileEntry *DirectoryLookup::LookupFile(
264    StringRef &Filename,
265    HeaderSearch &HS,
266    SmallVectorImpl<char> *SearchPath,
267    SmallVectorImpl<char> *RelativePath,
268    ModuleMap::KnownHeader *SuggestedModule,
269    bool &InUserSpecifiedSystemFramework,
270    bool &HasBeenMapped,
271    SmallVectorImpl<char> &MappedName) const {
272  InUserSpecifiedSystemFramework = false;
273  HasBeenMapped = false;
274
275  SmallString<1024> TmpDir;
276  if (isNormalDir()) {
277    // Concatenate the requested file onto the directory.
278    TmpDir = getDir()->getName();
279    llvm::sys::path::append(TmpDir, Filename);
280    if (SearchPath) {
281      StringRef SearchPathRef(getDir()->getName());
282      SearchPath->clear();
283      SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
284    }
285    if (RelativePath) {
286      RelativePath->clear();
287      RelativePath->append(Filename.begin(), Filename.end());
288    }
289
290    return getFileAndSuggestModule(HS, TmpDir.str(), getDir(),
291                                   isSystemHeaderDirectory(),
292                                   SuggestedModule);
293  }
294
295  if (isFramework())
296    return DoFrameworkLookup(Filename, HS, SearchPath, RelativePath,
297                             SuggestedModule, InUserSpecifiedSystemFramework);
298
299  assert(isHeaderMap() && "Unknown directory lookup");
300  const HeaderMap *HM = getHeaderMap();
301  SmallString<1024> Path;
302  StringRef Dest = HM->lookupFilename(Filename, Path);
303  if (Dest.empty())
304    return nullptr;
305
306  const FileEntry *Result;
307
308  // Check if the headermap maps the filename to a framework include
309  // ("Foo.h" -> "Foo/Foo.h"), in which case continue header lookup using the
310  // framework include.
311  if (llvm::sys::path::is_relative(Dest)) {
312    MappedName.clear();
313    MappedName.append(Dest.begin(), Dest.end());
314    Filename = StringRef(MappedName.begin(), MappedName.size());
315    HasBeenMapped = true;
316    Result = HM->LookupFile(Filename, HS.getFileMgr());
317
318  } else {
319    Result = HS.getFileMgr().getFile(Dest);
320  }
321
322  if (Result) {
323    if (SearchPath) {
324      StringRef SearchPathRef(getName());
325      SearchPath->clear();
326      SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
327    }
328    if (RelativePath) {
329      RelativePath->clear();
330      RelativePath->append(Filename.begin(), Filename.end());
331    }
332  }
333  return Result;
334}
335
336/// \brief Given a framework directory, find the top-most framework directory.
337///
338/// \param FileMgr The file manager to use for directory lookups.
339/// \param DirName The name of the framework directory.
340/// \param SubmodulePath Will be populated with the submodule path from the
341/// returned top-level module to the originally named framework.
342static const DirectoryEntry *
343getTopFrameworkDir(FileManager &FileMgr, StringRef DirName,
344                   SmallVectorImpl<std::string> &SubmodulePath) {
345  assert(llvm::sys::path::extension(DirName) == ".framework" &&
346         "Not a framework directory");
347
348  // Note: as an egregious but useful hack we use the real path here, because
349  // frameworks moving between top-level frameworks to embedded frameworks tend
350  // to be symlinked, and we base the logical structure of modules on the
351  // physical layout. In particular, we need to deal with crazy includes like
352  //
353  //   #include <Foo/Frameworks/Bar.framework/Headers/Wibble.h>
354  //
355  // where 'Bar' used to be embedded in 'Foo', is now a top-level framework
356  // which one should access with, e.g.,
357  //
358  //   #include <Bar/Wibble.h>
359  //
360  // Similar issues occur when a top-level framework has moved into an
361  // embedded framework.
362  const DirectoryEntry *TopFrameworkDir = FileMgr.getDirectory(DirName);
363  DirName = FileMgr.getCanonicalName(TopFrameworkDir);
364  do {
365    // Get the parent directory name.
366    DirName = llvm::sys::path::parent_path(DirName);
367    if (DirName.empty())
368      break;
369
370    // Determine whether this directory exists.
371    const DirectoryEntry *Dir = FileMgr.getDirectory(DirName);
372    if (!Dir)
373      break;
374
375    // If this is a framework directory, then we're a subframework of this
376    // framework.
377    if (llvm::sys::path::extension(DirName) == ".framework") {
378      SubmodulePath.push_back(llvm::sys::path::stem(DirName));
379      TopFrameworkDir = Dir;
380    }
381  } while (true);
382
383  return TopFrameworkDir;
384}
385
386/// DoFrameworkLookup - Do a lookup of the specified file in the current
387/// DirectoryLookup, which is a framework directory.
388const FileEntry *DirectoryLookup::DoFrameworkLookup(
389    StringRef Filename,
390    HeaderSearch &HS,
391    SmallVectorImpl<char> *SearchPath,
392    SmallVectorImpl<char> *RelativePath,
393    ModuleMap::KnownHeader *SuggestedModule,
394    bool &InUserSpecifiedSystemFramework) const
395{
396  FileManager &FileMgr = HS.getFileMgr();
397
398  // Framework names must have a '/' in the filename.
399  size_t SlashPos = Filename.find('/');
400  if (SlashPos == StringRef::npos) return nullptr;
401
402  // Find out if this is the home for the specified framework, by checking
403  // HeaderSearch.  Possible answers are yes/no and unknown.
404  HeaderSearch::FrameworkCacheEntry &CacheEntry =
405    HS.LookupFrameworkCache(Filename.substr(0, SlashPos));
406
407  // If it is known and in some other directory, fail.
408  if (CacheEntry.Directory && CacheEntry.Directory != getFrameworkDir())
409    return nullptr;
410
411  // Otherwise, construct the path to this framework dir.
412
413  // FrameworkName = "/System/Library/Frameworks/"
414  SmallString<1024> FrameworkName;
415  FrameworkName += getFrameworkDir()->getName();
416  if (FrameworkName.empty() || FrameworkName.back() != '/')
417    FrameworkName.push_back('/');
418
419  // FrameworkName = "/System/Library/Frameworks/Cocoa"
420  StringRef ModuleName(Filename.begin(), SlashPos);
421  FrameworkName += ModuleName;
422
423  // FrameworkName = "/System/Library/Frameworks/Cocoa.framework/"
424  FrameworkName += ".framework/";
425
426  // If the cache entry was unresolved, populate it now.
427  if (!CacheEntry.Directory) {
428    HS.IncrementFrameworkLookupCount();
429
430    // If the framework dir doesn't exist, we fail.
431    const DirectoryEntry *Dir = FileMgr.getDirectory(FrameworkName.str());
432    if (!Dir) return nullptr;
433
434    // Otherwise, if it does, remember that this is the right direntry for this
435    // framework.
436    CacheEntry.Directory = getFrameworkDir();
437
438    // If this is a user search directory, check if the framework has been
439    // user-specified as a system framework.
440    if (getDirCharacteristic() == SrcMgr::C_User) {
441      SmallString<1024> SystemFrameworkMarker(FrameworkName);
442      SystemFrameworkMarker += ".system_framework";
443      if (llvm::sys::fs::exists(SystemFrameworkMarker.str())) {
444        CacheEntry.IsUserSpecifiedSystemFramework = true;
445      }
446    }
447  }
448
449  // Set the 'user-specified system framework' flag.
450  InUserSpecifiedSystemFramework = CacheEntry.IsUserSpecifiedSystemFramework;
451
452  if (RelativePath) {
453    RelativePath->clear();
454    RelativePath->append(Filename.begin()+SlashPos+1, Filename.end());
455  }
456
457  // Check "/System/Library/Frameworks/Cocoa.framework/Headers/file.h"
458  unsigned OrigSize = FrameworkName.size();
459
460  FrameworkName += "Headers/";
461
462  if (SearchPath) {
463    SearchPath->clear();
464    // Without trailing '/'.
465    SearchPath->append(FrameworkName.begin(), FrameworkName.end()-1);
466  }
467
468  FrameworkName.append(Filename.begin()+SlashPos+1, Filename.end());
469  const FileEntry *FE = FileMgr.getFile(FrameworkName.str(),
470                                        /*openFile=*/!SuggestedModule);
471  if (!FE) {
472    // Check "/System/Library/Frameworks/Cocoa.framework/PrivateHeaders/file.h"
473    const char *Private = "Private";
474    FrameworkName.insert(FrameworkName.begin()+OrigSize, Private,
475                         Private+strlen(Private));
476    if (SearchPath)
477      SearchPath->insert(SearchPath->begin()+OrigSize, Private,
478                         Private+strlen(Private));
479
480    FE = FileMgr.getFile(FrameworkName.str(), /*openFile=*/!SuggestedModule);
481  }
482
483  // If we found the header and are allowed to suggest a module, do so now.
484  if (FE && SuggestedModule) {
485    // Find the framework in which this header occurs.
486    StringRef FrameworkPath = FE->getDir()->getName();
487    bool FoundFramework = false;
488    do {
489      // Determine whether this directory exists.
490      const DirectoryEntry *Dir = FileMgr.getDirectory(FrameworkPath);
491      if (!Dir)
492        break;
493
494      // If this is a framework directory, then we're a subframework of this
495      // framework.
496      if (llvm::sys::path::extension(FrameworkPath) == ".framework") {
497        FoundFramework = true;
498        break;
499      }
500
501      // Get the parent directory name.
502      FrameworkPath = llvm::sys::path::parent_path(FrameworkPath);
503      if (FrameworkPath.empty())
504        break;
505    } while (true);
506
507    if (FoundFramework) {
508      // Find the top-level framework based on this framework.
509      SmallVector<std::string, 4> SubmodulePath;
510      const DirectoryEntry *TopFrameworkDir
511        = ::getTopFrameworkDir(FileMgr, FrameworkPath, SubmodulePath);
512
513      // Determine the name of the top-level framework.
514      StringRef ModuleName = llvm::sys::path::stem(TopFrameworkDir->getName());
515
516      // Load this framework module. If that succeeds, find the suggested module
517      // for this header, if any.
518      bool IsSystem = getDirCharacteristic() != SrcMgr::C_User;
519      if (HS.loadFrameworkModule(ModuleName, TopFrameworkDir, IsSystem)) {
520        *SuggestedModule = HS.findModuleForHeader(FE);
521      }
522    } else {
523      *SuggestedModule = HS.findModuleForHeader(FE);
524    }
525  }
526  return FE;
527}
528
529void HeaderSearch::setTarget(const TargetInfo &Target) {
530  ModMap.setTarget(Target);
531}
532
533
534//===----------------------------------------------------------------------===//
535// Header File Location.
536//===----------------------------------------------------------------------===//
537
538/// \brief Return true with a diagnostic if the file that MSVC would have found
539/// fails to match the one that Clang would have found with MSVC header search
540/// disabled.
541static bool checkMSVCHeaderSearch(DiagnosticsEngine &Diags,
542                                  const FileEntry *MSFE, const FileEntry *FE,
543                                  SourceLocation IncludeLoc) {
544  if (MSFE && FE != MSFE) {
545    Diags.Report(IncludeLoc, diag::ext_pp_include_search_ms) << MSFE->getName();
546    return true;
547  }
548  return false;
549}
550
551static const char *copyString(StringRef Str, llvm::BumpPtrAllocator &Alloc) {
552  assert(!Str.empty());
553  char *CopyStr = Alloc.Allocate<char>(Str.size()+1);
554  std::copy(Str.begin(), Str.end(), CopyStr);
555  CopyStr[Str.size()] = '\0';
556  return CopyStr;
557}
558
559/// LookupFile - Given a "foo" or \<foo> reference, look up the indicated file,
560/// return null on failure.  isAngled indicates whether the file reference is
561/// for system \#include's or not (i.e. using <> instead of ""). Includers, if
562/// non-empty, indicates where the \#including file(s) are, in case a relative
563/// search is needed. Microsoft mode will pass all \#including files.
564const FileEntry *HeaderSearch::LookupFile(
565    StringRef Filename, SourceLocation IncludeLoc, bool isAngled,
566    const DirectoryLookup *FromDir, const DirectoryLookup *&CurDir,
567    ArrayRef<const FileEntry *> Includers, SmallVectorImpl<char> *SearchPath,
568    SmallVectorImpl<char> *RelativePath,
569    ModuleMap::KnownHeader *SuggestedModule, bool SkipCache) {
570  if (!HSOpts->ModuleMapFiles.empty()) {
571    // Preload all explicitly specified module map files. This enables modules
572    // map files lying in a directory structure separate from the header files
573    // that they describe. These cannot be loaded lazily upon encountering a
574    // header file, as there is no other known mapping from a header file to its
575    // module map file.
576    for (llvm::SetVector<std::string>::iterator
577             I = HSOpts->ModuleMapFiles.begin(),
578             E = HSOpts->ModuleMapFiles.end();
579         I != E; ++I) {
580      const FileEntry *File = FileMgr.getFile(*I);
581      if (!File)
582        continue;
583      loadModuleMapFile(File, /*IsSystem=*/false);
584    }
585    HSOpts->ModuleMapFiles.clear();
586  }
587
588  if (SuggestedModule)
589    *SuggestedModule = ModuleMap::KnownHeader();
590
591  // If 'Filename' is absolute, check to see if it exists and no searching.
592  if (llvm::sys::path::is_absolute(Filename)) {
593    CurDir = nullptr;
594
595    // If this was an #include_next "/absolute/file", fail.
596    if (FromDir) return nullptr;
597
598    if (SearchPath)
599      SearchPath->clear();
600    if (RelativePath) {
601      RelativePath->clear();
602      RelativePath->append(Filename.begin(), Filename.end());
603    }
604    // Otherwise, just return the file.
605    return FileMgr.getFile(Filename, /*openFile=*/true);
606  }
607
608  // This is the header that MSVC's header search would have found.
609  const FileEntry *MSFE = nullptr;
610  ModuleMap::KnownHeader MSSuggestedModule;
611
612  // Unless disabled, check to see if the file is in the #includer's
613  // directory.  This cannot be based on CurDir, because each includer could be
614  // a #include of a subdirectory (#include "foo/bar.h") and a subsequent
615  // include of "baz.h" should resolve to "whatever/foo/baz.h".
616  // This search is not done for <> headers.
617  if (!Includers.empty() && !isAngled && !NoCurDirSearch) {
618    SmallString<1024> TmpDir;
619    for (ArrayRef<const FileEntry *>::iterator I = Includers.begin(),
620                                               E = Includers.end();
621         I != E; ++I) {
622      const FileEntry *Includer = *I;
623      // Concatenate the requested file onto the directory.
624      // FIXME: Portability.  Filename concatenation should be in sys::Path.
625      TmpDir = Includer->getDir()->getName();
626      TmpDir.push_back('/');
627      TmpDir.append(Filename.begin(), Filename.end());
628
629      // FIXME: We don't cache the result of getFileInfo across the call to
630      // getFileAndSuggestModule, because it's a reference to an element of
631      // a container that could be reallocated across this call.
632      bool IncluderIsSystemHeader =
633          getFileInfo(Includer).DirInfo != SrcMgr::C_User;
634      if (const FileEntry *FE =
635              getFileAndSuggestModule(*this, TmpDir.str(), Includer->getDir(),
636                                      IncluderIsSystemHeader,
637                                      SuggestedModule)) {
638        // Leave CurDir unset.
639        // This file is a system header or C++ unfriendly if the old file is.
640        //
641        // Note that we only use one of FromHFI/ToHFI at once, due to potential
642        // reallocation of the underlying vector potentially making the first
643        // reference binding dangling.
644        HeaderFileInfo &FromHFI = getFileInfo(Includer);
645        unsigned DirInfo = FromHFI.DirInfo;
646        bool IndexHeaderMapHeader = FromHFI.IndexHeaderMapHeader;
647        StringRef Framework = FromHFI.Framework;
648
649        HeaderFileInfo &ToHFI = getFileInfo(FE);
650        ToHFI.DirInfo = DirInfo;
651        ToHFI.IndexHeaderMapHeader = IndexHeaderMapHeader;
652        ToHFI.Framework = Framework;
653
654        if (SearchPath) {
655          StringRef SearchPathRef(Includer->getDir()->getName());
656          SearchPath->clear();
657          SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
658        }
659        if (RelativePath) {
660          RelativePath->clear();
661          RelativePath->append(Filename.begin(), Filename.end());
662        }
663        if (I == Includers.begin())
664          return FE;
665
666        // Otherwise, we found the path via MSVC header search rules.  If
667        // -Wmsvc-include is enabled, we have to keep searching to see if we
668        // would've found this header in -I or -isystem directories.
669        if (Diags.isIgnored(diag::ext_pp_include_search_ms, IncludeLoc)) {
670          return FE;
671        } else {
672          MSFE = FE;
673          if (SuggestedModule) {
674            MSSuggestedModule = *SuggestedModule;
675            *SuggestedModule = ModuleMap::KnownHeader();
676          }
677          break;
678        }
679      }
680    }
681  }
682
683  CurDir = nullptr;
684
685  // If this is a system #include, ignore the user #include locs.
686  unsigned i = isAngled ? AngledDirIdx : 0;
687
688  // If this is a #include_next request, start searching after the directory the
689  // file was found in.
690  if (FromDir)
691    i = FromDir-&SearchDirs[0];
692
693  // Cache all of the lookups performed by this method.  Many headers are
694  // multiply included, and the "pragma once" optimization prevents them from
695  // being relex/pp'd, but they would still have to search through a
696  // (potentially huge) series of SearchDirs to find it.
697  LookupFileCacheInfo &CacheLookup =
698    LookupFileCache.GetOrCreateValue(Filename).getValue();
699
700  // If the entry has been previously looked up, the first value will be
701  // non-zero.  If the value is equal to i (the start point of our search), then
702  // this is a matching hit.
703  if (!SkipCache && CacheLookup.StartIdx == i+1) {
704    // Skip querying potentially lots of directories for this lookup.
705    i = CacheLookup.HitIdx;
706    if (CacheLookup.MappedName)
707      Filename = CacheLookup.MappedName;
708  } else {
709    // Otherwise, this is the first query, or the previous query didn't match
710    // our search start.  We will fill in our found location below, so prime the
711    // start point value.
712    CacheLookup.reset(/*StartIdx=*/i+1);
713  }
714
715  SmallString<64> MappedName;
716
717  // Check each directory in sequence to see if it contains this file.
718  for (; i != SearchDirs.size(); ++i) {
719    bool InUserSpecifiedSystemFramework = false;
720    bool HasBeenMapped = false;
721    const FileEntry *FE =
722      SearchDirs[i].LookupFile(Filename, *this, SearchPath, RelativePath,
723                               SuggestedModule, InUserSpecifiedSystemFramework,
724                               HasBeenMapped, MappedName);
725    if (HasBeenMapped) {
726      CacheLookup.MappedName =
727          copyString(Filename, LookupFileCache.getAllocator());
728    }
729    if (!FE) continue;
730
731    CurDir = &SearchDirs[i];
732
733    // This file is a system header or C++ unfriendly if the dir is.
734    HeaderFileInfo &HFI = getFileInfo(FE);
735    HFI.DirInfo = CurDir->getDirCharacteristic();
736
737    // If the directory characteristic is User but this framework was
738    // user-specified to be treated as a system framework, promote the
739    // characteristic.
740    if (HFI.DirInfo == SrcMgr::C_User && InUserSpecifiedSystemFramework)
741      HFI.DirInfo = SrcMgr::C_System;
742
743    // If the filename matches a known system header prefix, override
744    // whether the file is a system header.
745    for (unsigned j = SystemHeaderPrefixes.size(); j; --j) {
746      if (Filename.startswith(SystemHeaderPrefixes[j-1].first)) {
747        HFI.DirInfo = SystemHeaderPrefixes[j-1].second ? SrcMgr::C_System
748                                                       : SrcMgr::C_User;
749        break;
750      }
751    }
752
753    // If this file is found in a header map and uses the framework style of
754    // includes, then this header is part of a framework we're building.
755    if (CurDir->isIndexHeaderMap()) {
756      size_t SlashPos = Filename.find('/');
757      if (SlashPos != StringRef::npos) {
758        HFI.IndexHeaderMapHeader = 1;
759        HFI.Framework = getUniqueFrameworkName(StringRef(Filename.begin(),
760                                                         SlashPos));
761      }
762    }
763
764    if (checkMSVCHeaderSearch(Diags, MSFE, FE, IncludeLoc)) {
765      if (SuggestedModule)
766        *SuggestedModule = MSSuggestedModule;
767      return MSFE;
768    }
769
770    // Remember this location for the next lookup we do.
771    CacheLookup.HitIdx = i;
772    return FE;
773  }
774
775  // If we are including a file with a quoted include "foo.h" from inside
776  // a header in a framework that is currently being built, and we couldn't
777  // resolve "foo.h" any other way, change the include to <Foo/foo.h>, where
778  // "Foo" is the name of the framework in which the including header was found.
779  if (!Includers.empty() && !isAngled &&
780      Filename.find('/') == StringRef::npos) {
781    HeaderFileInfo &IncludingHFI = getFileInfo(Includers.front());
782    if (IncludingHFI.IndexHeaderMapHeader) {
783      SmallString<128> ScratchFilename;
784      ScratchFilename += IncludingHFI.Framework;
785      ScratchFilename += '/';
786      ScratchFilename += Filename;
787
788      const FileEntry *FE = LookupFile(
789          ScratchFilename, IncludeLoc, /*isAngled=*/true, FromDir, CurDir,
790          Includers.front(), SearchPath, RelativePath, SuggestedModule);
791
792      if (checkMSVCHeaderSearch(Diags, MSFE, FE, IncludeLoc)) {
793        if (SuggestedModule)
794          *SuggestedModule = MSSuggestedModule;
795        return MSFE;
796      }
797
798      LookupFileCacheInfo &CacheLookup
799        = LookupFileCache.GetOrCreateValue(Filename).getValue();
800      CacheLookup.HitIdx
801        = LookupFileCache.GetOrCreateValue(ScratchFilename).getValue().HitIdx;
802      // FIXME: SuggestedModule.
803      return FE;
804    }
805  }
806
807  if (checkMSVCHeaderSearch(Diags, MSFE, nullptr, IncludeLoc)) {
808    if (SuggestedModule)
809      *SuggestedModule = MSSuggestedModule;
810    return MSFE;
811  }
812
813  // Otherwise, didn't find it. Remember we didn't find this.
814  CacheLookup.HitIdx = SearchDirs.size();
815  return nullptr;
816}
817
818/// LookupSubframeworkHeader - Look up a subframework for the specified
819/// \#include file.  For example, if \#include'ing <HIToolbox/HIToolbox.h> from
820/// within ".../Carbon.framework/Headers/Carbon.h", check to see if HIToolbox
821/// is a subframework within Carbon.framework.  If so, return the FileEntry
822/// for the designated file, otherwise return null.
823const FileEntry *HeaderSearch::
824LookupSubframeworkHeader(StringRef Filename,
825                         const FileEntry *ContextFileEnt,
826                         SmallVectorImpl<char> *SearchPath,
827                         SmallVectorImpl<char> *RelativePath,
828                         ModuleMap::KnownHeader *SuggestedModule) {
829  assert(ContextFileEnt && "No context file?");
830
831  // Framework names must have a '/' in the filename.  Find it.
832  // FIXME: Should we permit '\' on Windows?
833  size_t SlashPos = Filename.find('/');
834  if (SlashPos == StringRef::npos) return nullptr;
835
836  // Look up the base framework name of the ContextFileEnt.
837  const char *ContextName = ContextFileEnt->getName();
838
839  // If the context info wasn't a framework, couldn't be a subframework.
840  const unsigned DotFrameworkLen = 10;
841  const char *FrameworkPos = strstr(ContextName, ".framework");
842  if (FrameworkPos == nullptr ||
843      (FrameworkPos[DotFrameworkLen] != '/' &&
844       FrameworkPos[DotFrameworkLen] != '\\'))
845    return nullptr;
846
847  SmallString<1024> FrameworkName(ContextName, FrameworkPos+DotFrameworkLen+1);
848
849  // Append Frameworks/HIToolbox.framework/
850  FrameworkName += "Frameworks/";
851  FrameworkName.append(Filename.begin(), Filename.begin()+SlashPos);
852  FrameworkName += ".framework/";
853
854  llvm::StringMapEntry<FrameworkCacheEntry> &CacheLookup =
855    FrameworkMap.GetOrCreateValue(Filename.substr(0, SlashPos));
856
857  // Some other location?
858  if (CacheLookup.getValue().Directory &&
859      CacheLookup.getKeyLength() == FrameworkName.size() &&
860      memcmp(CacheLookup.getKeyData(), &FrameworkName[0],
861             CacheLookup.getKeyLength()) != 0)
862    return nullptr;
863
864  // Cache subframework.
865  if (!CacheLookup.getValue().Directory) {
866    ++NumSubFrameworkLookups;
867
868    // If the framework dir doesn't exist, we fail.
869    const DirectoryEntry *Dir = FileMgr.getDirectory(FrameworkName.str());
870    if (!Dir) return nullptr;
871
872    // Otherwise, if it does, remember that this is the right direntry for this
873    // framework.
874    CacheLookup.getValue().Directory = Dir;
875  }
876
877  const FileEntry *FE = nullptr;
878
879  if (RelativePath) {
880    RelativePath->clear();
881    RelativePath->append(Filename.begin()+SlashPos+1, Filename.end());
882  }
883
884  // Check ".../Frameworks/HIToolbox.framework/Headers/HIToolbox.h"
885  SmallString<1024> HeadersFilename(FrameworkName);
886  HeadersFilename += "Headers/";
887  if (SearchPath) {
888    SearchPath->clear();
889    // Without trailing '/'.
890    SearchPath->append(HeadersFilename.begin(), HeadersFilename.end()-1);
891  }
892
893  HeadersFilename.append(Filename.begin()+SlashPos+1, Filename.end());
894  if (!(FE = FileMgr.getFile(HeadersFilename.str(), /*openFile=*/true))) {
895
896    // Check ".../Frameworks/HIToolbox.framework/PrivateHeaders/HIToolbox.h"
897    HeadersFilename = FrameworkName;
898    HeadersFilename += "PrivateHeaders/";
899    if (SearchPath) {
900      SearchPath->clear();
901      // Without trailing '/'.
902      SearchPath->append(HeadersFilename.begin(), HeadersFilename.end()-1);
903    }
904
905    HeadersFilename.append(Filename.begin()+SlashPos+1, Filename.end());
906    if (!(FE = FileMgr.getFile(HeadersFilename.str(), /*openFile=*/true)))
907      return nullptr;
908  }
909
910  // This file is a system header or C++ unfriendly if the old file is.
911  //
912  // Note that the temporary 'DirInfo' is required here, as either call to
913  // getFileInfo could resize the vector and we don't want to rely on order
914  // of evaluation.
915  unsigned DirInfo = getFileInfo(ContextFileEnt).DirInfo;
916  getFileInfo(FE).DirInfo = DirInfo;
917
918  // If we're supposed to suggest a module, look for one now.
919  if (SuggestedModule) {
920    // Find the top-level framework based on this framework.
921    FrameworkName.pop_back(); // remove the trailing '/'
922    SmallVector<std::string, 4> SubmodulePath;
923    const DirectoryEntry *TopFrameworkDir
924      = ::getTopFrameworkDir(FileMgr, FrameworkName, SubmodulePath);
925
926    // Determine the name of the top-level framework.
927    StringRef ModuleName = llvm::sys::path::stem(TopFrameworkDir->getName());
928
929    // Load this framework module. If that succeeds, find the suggested module
930    // for this header, if any.
931    bool IsSystem = false;
932    if (loadFrameworkModule(ModuleName, TopFrameworkDir, IsSystem)) {
933      *SuggestedModule = findModuleForHeader(FE);
934    }
935  }
936
937  return FE;
938}
939
940/// \brief Helper static function to normalize a path for injection into
941/// a synthetic header.
942/*static*/ std::string
943HeaderSearch::NormalizeDashIncludePath(StringRef File, FileManager &FileMgr) {
944  // Implicit include paths should be resolved relative to the current
945  // working directory first, and then use the regular header search
946  // mechanism. The proper way to handle this is to have the
947  // predefines buffer located at the current working directory, but
948  // it has no file entry. For now, workaround this by using an
949  // absolute path if we find the file here, and otherwise letting
950  // header search handle it.
951  SmallString<128> Path(File);
952  llvm::sys::fs::make_absolute(Path);
953  bool exists;
954  if (llvm::sys::fs::exists(Path.str(), exists) || !exists)
955    Path = File;
956  else if (exists)
957    FileMgr.getFile(File);
958
959  return Lexer::Stringify(Path.str());
960}
961
962//===----------------------------------------------------------------------===//
963// File Info Management.
964//===----------------------------------------------------------------------===//
965
966/// \brief Merge the header file info provided by \p OtherHFI into the current
967/// header file info (\p HFI)
968static void mergeHeaderFileInfo(HeaderFileInfo &HFI,
969                                const HeaderFileInfo &OtherHFI) {
970  HFI.isImport |= OtherHFI.isImport;
971  HFI.isPragmaOnce |= OtherHFI.isPragmaOnce;
972  HFI.isModuleHeader |= OtherHFI.isModuleHeader;
973  HFI.NumIncludes += OtherHFI.NumIncludes;
974
975  if (!HFI.ControllingMacro && !HFI.ControllingMacroID) {
976    HFI.ControllingMacro = OtherHFI.ControllingMacro;
977    HFI.ControllingMacroID = OtherHFI.ControllingMacroID;
978  }
979
980  if (OtherHFI.External) {
981    HFI.DirInfo = OtherHFI.DirInfo;
982    HFI.External = OtherHFI.External;
983    HFI.IndexHeaderMapHeader = OtherHFI.IndexHeaderMapHeader;
984  }
985
986  if (HFI.Framework.empty())
987    HFI.Framework = OtherHFI.Framework;
988
989  HFI.Resolved = true;
990}
991
992/// getFileInfo - Return the HeaderFileInfo structure for the specified
993/// FileEntry.
994HeaderFileInfo &HeaderSearch::getFileInfo(const FileEntry *FE) {
995  if (FE->getUID() >= FileInfo.size())
996    FileInfo.resize(FE->getUID()+1);
997
998  HeaderFileInfo &HFI = FileInfo[FE->getUID()];
999  if (ExternalSource && !HFI.Resolved)
1000    mergeHeaderFileInfo(HFI, ExternalSource->GetHeaderFileInfo(FE));
1001  HFI.IsValid = 1;
1002  return HFI;
1003}
1004
1005bool HeaderSearch::tryGetFileInfo(const FileEntry *FE, HeaderFileInfo &Result) const {
1006  if (FE->getUID() >= FileInfo.size())
1007    return false;
1008  const HeaderFileInfo &HFI = FileInfo[FE->getUID()];
1009  if (HFI.IsValid) {
1010    Result = HFI;
1011    return true;
1012  }
1013  return false;
1014}
1015
1016bool HeaderSearch::isFileMultipleIncludeGuarded(const FileEntry *File) {
1017  // Check if we've ever seen this file as a header.
1018  if (File->getUID() >= FileInfo.size())
1019    return false;
1020
1021  // Resolve header file info from the external source, if needed.
1022  HeaderFileInfo &HFI = FileInfo[File->getUID()];
1023  if (ExternalSource && !HFI.Resolved)
1024    mergeHeaderFileInfo(HFI, ExternalSource->GetHeaderFileInfo(File));
1025
1026  return HFI.isPragmaOnce || HFI.isImport ||
1027      HFI.ControllingMacro || HFI.ControllingMacroID;
1028}
1029
1030void HeaderSearch::MarkFileModuleHeader(const FileEntry *FE,
1031                                        ModuleMap::ModuleHeaderRole Role,
1032                                        bool isCompilingModuleHeader) {
1033  if (FE->getUID() >= FileInfo.size())
1034    FileInfo.resize(FE->getUID()+1);
1035
1036  HeaderFileInfo &HFI = FileInfo[FE->getUID()];
1037  HFI.isModuleHeader = true;
1038  HFI.isCompilingModuleHeader = isCompilingModuleHeader;
1039  HFI.setHeaderRole(Role);
1040}
1041
1042bool HeaderSearch::ShouldEnterIncludeFile(const FileEntry *File, bool isImport){
1043  ++NumIncluded; // Count # of attempted #includes.
1044
1045  // Get information about this file.
1046  HeaderFileInfo &FileInfo = getFileInfo(File);
1047
1048  // If this is a #import directive, check that we have not already imported
1049  // this header.
1050  if (isImport) {
1051    // If this has already been imported, don't import it again.
1052    FileInfo.isImport = true;
1053
1054    // Has this already been #import'ed or #include'd?
1055    if (FileInfo.NumIncludes) return false;
1056  } else {
1057    // Otherwise, if this is a #include of a file that was previously #import'd
1058    // or if this is the second #include of a #pragma once file, ignore it.
1059    if (FileInfo.isImport)
1060      return false;
1061  }
1062
1063  // Next, check to see if the file is wrapped with #ifndef guards.  If so, and
1064  // if the macro that guards it is defined, we know the #include has no effect.
1065  if (const IdentifierInfo *ControllingMacro
1066      = FileInfo.getControllingMacro(ExternalLookup))
1067    if (ControllingMacro->hasMacroDefinition()) {
1068      ++NumMultiIncludeFileOptzn;
1069      return false;
1070    }
1071
1072  // Increment the number of times this file has been included.
1073  ++FileInfo.NumIncludes;
1074
1075  return true;
1076}
1077
1078size_t HeaderSearch::getTotalMemory() const {
1079  return SearchDirs.capacity()
1080    + llvm::capacity_in_bytes(FileInfo)
1081    + llvm::capacity_in_bytes(HeaderMaps)
1082    + LookupFileCache.getAllocator().getTotalMemory()
1083    + FrameworkMap.getAllocator().getTotalMemory();
1084}
1085
1086StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
1087  return FrameworkNames.GetOrCreateValue(Framework).getKey();
1088}
1089
1090bool HeaderSearch::hasModuleMap(StringRef FileName,
1091                                const DirectoryEntry *Root,
1092                                bool IsSystem) {
1093  if (!enabledModules())
1094    return false;
1095
1096  SmallVector<const DirectoryEntry *, 2> FixUpDirectories;
1097
1098  StringRef DirName = FileName;
1099  do {
1100    // Get the parent directory name.
1101    DirName = llvm::sys::path::parent_path(DirName);
1102    if (DirName.empty())
1103      return false;
1104
1105    // Determine whether this directory exists.
1106    const DirectoryEntry *Dir = FileMgr.getDirectory(DirName);
1107    if (!Dir)
1108      return false;
1109
1110    // Try to load the module map file in this directory.
1111    switch (loadModuleMapFile(Dir, IsSystem, /*IsFramework*/false)) {
1112    case LMM_NewlyLoaded:
1113    case LMM_AlreadyLoaded:
1114      // Success. All of the directories we stepped through inherit this module
1115      // map file.
1116      for (unsigned I = 0, N = FixUpDirectories.size(); I != N; ++I)
1117        DirectoryHasModuleMap[FixUpDirectories[I]] = true;
1118      return true;
1119
1120    case LMM_NoDirectory:
1121    case LMM_InvalidModuleMap:
1122      break;
1123    }
1124
1125    // If we hit the top of our search, we're done.
1126    if (Dir == Root)
1127      return false;
1128
1129    // Keep track of all of the directories we checked, so we can mark them as
1130    // having module maps if we eventually do find a module map.
1131    FixUpDirectories.push_back(Dir);
1132  } while (true);
1133}
1134
1135ModuleMap::KnownHeader
1136HeaderSearch::findModuleForHeader(const FileEntry *File) const {
1137  if (ExternalSource) {
1138    // Make sure the external source has handled header info about this file,
1139    // which includes whether the file is part of a module.
1140    (void)getFileInfo(File);
1141  }
1142  return ModMap.findModuleForHeader(File);
1143}
1144
1145static const FileEntry *getPrivateModuleMap(StringRef ModuleMapPath,
1146                                            const DirectoryEntry *Directory,
1147                                            FileManager &FileMgr) {
1148  StringRef Filename = llvm::sys::path::filename(ModuleMapPath);
1149  SmallString<128>  PrivateFilename(Directory->getName());
1150  if (Filename == "module.map")
1151    llvm::sys::path::append(PrivateFilename, "module_private.map");
1152  else if (Filename == "module.modulemap")
1153    llvm::sys::path::append(PrivateFilename, "module.private.modulemap");
1154  else
1155    return nullptr;
1156  return FileMgr.getFile(PrivateFilename);
1157}
1158
1159bool HeaderSearch::loadModuleMapFile(const FileEntry *File, bool IsSystem) {
1160  switch (loadModuleMapFileImpl(File, IsSystem)) {
1161  case LMM_AlreadyLoaded:
1162  case LMM_NewlyLoaded:
1163    return false;
1164  case LMM_NoDirectory:
1165  case LMM_InvalidModuleMap:
1166    return true;
1167  }
1168  llvm_unreachable("Unknown load module map result");
1169}
1170
1171HeaderSearch::LoadModuleMapResult
1172HeaderSearch::loadModuleMapFileImpl(const FileEntry *File, bool IsSystem) {
1173  assert(File && "expected FileEntry");
1174
1175  const DirectoryEntry *Dir = File->getDir();
1176  auto KnownDir = DirectoryHasModuleMap.find(Dir);
1177  if (KnownDir != DirectoryHasModuleMap.end())
1178    return KnownDir->second ? LMM_AlreadyLoaded : LMM_InvalidModuleMap;
1179
1180  if (ModMap.parseModuleMapFile(File, IsSystem)) {
1181    DirectoryHasModuleMap[Dir] = false;
1182    return LMM_InvalidModuleMap;
1183  }
1184
1185  // Try to load a corresponding private module map.
1186  if (const FileEntry *PMMFile =
1187        getPrivateModuleMap(File->getName(), Dir, FileMgr)) {
1188    if (ModMap.parseModuleMapFile(PMMFile, IsSystem)) {
1189      DirectoryHasModuleMap[Dir] = false;
1190      return LMM_InvalidModuleMap;
1191    }
1192  }
1193
1194  // This directory has a module map.
1195  DirectoryHasModuleMap[Dir] = true;
1196  return LMM_NewlyLoaded;
1197}
1198
1199const FileEntry *
1200HeaderSearch::lookupModuleMapFile(const DirectoryEntry *Dir, bool IsFramework) {
1201  // For frameworks, the preferred spelling is Modules/module.modulemap, but
1202  // module.map at the framework root is also accepted.
1203  SmallString<128> ModuleMapFileName(Dir->getName());
1204  if (IsFramework)
1205    llvm::sys::path::append(ModuleMapFileName, "Modules");
1206  llvm::sys::path::append(ModuleMapFileName, "module.modulemap");
1207  if (const FileEntry *F = FileMgr.getFile(ModuleMapFileName))
1208    return F;
1209
1210  // Continue to allow module.map
1211  ModuleMapFileName = Dir->getName();
1212  llvm::sys::path::append(ModuleMapFileName, "module.map");
1213  return FileMgr.getFile(ModuleMapFileName);
1214}
1215
1216Module *HeaderSearch::loadFrameworkModule(StringRef Name,
1217                                          const DirectoryEntry *Dir,
1218                                          bool IsSystem) {
1219  if (Module *Module = ModMap.findModule(Name))
1220    return Module;
1221
1222  // Try to load a module map file.
1223  switch (loadModuleMapFile(Dir, IsSystem, /*IsFramework*/true)) {
1224  case LMM_InvalidModuleMap:
1225    break;
1226
1227  case LMM_AlreadyLoaded:
1228  case LMM_NoDirectory:
1229    return nullptr;
1230
1231  case LMM_NewlyLoaded:
1232    return ModMap.findModule(Name);
1233  }
1234
1235
1236  // Try to infer a module map from the framework directory.
1237  return ModMap.inferFrameworkModule(Name, Dir, IsSystem, /*Parent=*/nullptr);
1238}
1239
1240
1241HeaderSearch::LoadModuleMapResult
1242HeaderSearch::loadModuleMapFile(StringRef DirName, bool IsSystem,
1243                                bool IsFramework) {
1244  if (const DirectoryEntry *Dir = FileMgr.getDirectory(DirName))
1245    return loadModuleMapFile(Dir, IsSystem, IsFramework);
1246
1247  return LMM_NoDirectory;
1248}
1249
1250HeaderSearch::LoadModuleMapResult
1251HeaderSearch::loadModuleMapFile(const DirectoryEntry *Dir, bool IsSystem,
1252                                bool IsFramework) {
1253  auto KnownDir = DirectoryHasModuleMap.find(Dir);
1254  if (KnownDir != DirectoryHasModuleMap.end())
1255    return KnownDir->second? LMM_AlreadyLoaded : LMM_InvalidModuleMap;
1256
1257  if (const FileEntry *ModuleMapFile = lookupModuleMapFile(Dir, IsFramework)) {
1258    LoadModuleMapResult Result = loadModuleMapFileImpl(ModuleMapFile, IsSystem);
1259    // Add Dir explicitly in case ModuleMapFile is in a subdirectory.
1260    // E.g. Foo.framework/Modules/module.modulemap
1261    //      ^Dir                  ^ModuleMapFile
1262    if (Result == LMM_NewlyLoaded)
1263      DirectoryHasModuleMap[Dir] = true;
1264    return Result;
1265  }
1266  return LMM_InvalidModuleMap;
1267}
1268
1269void HeaderSearch::collectAllModules(SmallVectorImpl<Module *> &Modules) {
1270  Modules.clear();
1271
1272  // Load module maps for each of the header search directories.
1273  for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
1274    bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
1275    if (SearchDirs[Idx].isFramework()) {
1276      std::error_code EC;
1277      SmallString<128> DirNative;
1278      llvm::sys::path::native(SearchDirs[Idx].getFrameworkDir()->getName(),
1279                              DirNative);
1280
1281      // Search each of the ".framework" directories to load them as modules.
1282      for (llvm::sys::fs::directory_iterator Dir(DirNative.str(), EC), DirEnd;
1283           Dir != DirEnd && !EC; Dir.increment(EC)) {
1284        if (llvm::sys::path::extension(Dir->path()) != ".framework")
1285          continue;
1286
1287        const DirectoryEntry *FrameworkDir = FileMgr.getDirectory(Dir->path());
1288        if (!FrameworkDir)
1289          continue;
1290
1291        // Load this framework module.
1292        loadFrameworkModule(llvm::sys::path::stem(Dir->path()), FrameworkDir,
1293                            IsSystem);
1294      }
1295      continue;
1296    }
1297
1298    // FIXME: Deal with header maps.
1299    if (SearchDirs[Idx].isHeaderMap())
1300      continue;
1301
1302    // Try to load a module map file for the search directory.
1303    loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem, /*IsFramework*/false);
1304
1305    // Try to load module map files for immediate subdirectories of this search
1306    // directory.
1307    loadSubdirectoryModuleMaps(SearchDirs[Idx]);
1308  }
1309
1310  // Populate the list of modules.
1311  for (ModuleMap::module_iterator M = ModMap.module_begin(),
1312                               MEnd = ModMap.module_end();
1313       M != MEnd; ++M) {
1314    Modules.push_back(M->getValue());
1315  }
1316}
1317
1318void HeaderSearch::loadTopLevelSystemModules() {
1319  // Load module maps for each of the header search directories.
1320  for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
1321    // We only care about normal header directories.
1322    if (!SearchDirs[Idx].isNormalDir()) {
1323      continue;
1324    }
1325
1326    // Try to load a module map file for the search directory.
1327    loadModuleMapFile(SearchDirs[Idx].getDir(),
1328                      SearchDirs[Idx].isSystemHeaderDirectory(),
1329                      SearchDirs[Idx].isFramework());
1330  }
1331}
1332
1333void HeaderSearch::loadSubdirectoryModuleMaps(DirectoryLookup &SearchDir) {
1334  if (SearchDir.haveSearchedAllModuleMaps())
1335    return;
1336
1337  std::error_code EC;
1338  SmallString<128> DirNative;
1339  llvm::sys::path::native(SearchDir.getDir()->getName(), DirNative);
1340  for (llvm::sys::fs::directory_iterator Dir(DirNative.str(), EC), DirEnd;
1341       Dir != DirEnd && !EC; Dir.increment(EC)) {
1342    loadModuleMapFile(Dir->path(), SearchDir.isSystemHeaderDirectory(),
1343                      SearchDir.isFramework());
1344  }
1345
1346  SearchDir.setSearchedAllModuleMaps(true);
1347}
1348