contrib/llvm-project/clang/lib/Lex/HeaderSearch.cpp

   1 //===- HeaderSearch.cpp - Resolve Header File Locations -------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements the DirectoryLookup and HeaderSearch interfaces.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/Lex/HeaderSearch.h"
  14 #include "clang/Basic/Diagnostic.h"
  15 #include "clang/Basic/FileManager.h"
  16 #include "clang/Basic/IdentifierTable.h"
  17 #include "clang/Basic/Module.h"
  18 #include "clang/Basic/SourceManager.h"
  19 #include "clang/Lex/DirectoryLookup.h"
  20 #include "clang/Lex/ExternalPreprocessorSource.h"
  21 #include "clang/Lex/HeaderMap.h"
  22 #include "clang/Lex/HeaderSearchOptions.h"
  23 #include "clang/Lex/LexDiagnostic.h"
  24 #include "clang/Lex/ModuleMap.h"
  25 #include "clang/Lex/Preprocessor.h"
  26 #include "llvm/ADT/APInt.h"
  27 #include "llvm/ADT/Hashing.h"
  28 #include "llvm/ADT/SmallString.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/ADT/StringRef.h"
  32 #include "llvm/Support/Allocator.h"
  33 #include "llvm/Support/Capacity.h"
  34 #include "llvm/Support/Errc.h"
  35 #include "llvm/Support/ErrorHandling.h"
  36 #include "llvm/Support/FileSystem.h"
  37 #include "llvm/Support/Path.h"
  38 #include "llvm/Support/VirtualFileSystem.h"
  39 #include <algorithm>
  40 #include <cassert>
  41 #include <cstddef>
  42 #include <cstdio>
  43 #include <cstring>
  44 #include <string>
  45 #include <system_error>
  46 #include <utility>
  47
  48 using namespace clang;
  49
  50 #define DEBUG_TYPE "file-search"
  51
  52 ALWAYS_ENABLED_STATISTIC(NumIncluded, "Number of attempted #includes.");
  53 ALWAYS_ENABLED_STATISTIC(
  54     NumMultiIncludeFileOptzn,
  55     "Number of #includes skipped due to the multi-include optimization.");
  56 ALWAYS_ENABLED_STATISTIC(NumFrameworkLookups, "Number of framework lookups.");
  57 ALWAYS_ENABLED_STATISTIC(NumSubFrameworkLookups,
  58                          "Number of subframework lookups.");
  59
  60 const IdentifierInfo *
  61 HeaderFileInfo::getControllingMacro(ExternalPreprocessorSource *External) {
  62   if (ControllingMacro) {
  63     if (ControllingMacro->isOutOfDate()) {
  64       assert(External && "We must have an external source if we have a "
  65                          "controlling macro that is out of date.");
  66       External->updateOutOfDateIdentifier(
  67           *const_cast<IdentifierInfo *>(ControllingMacro));
  68     }
  69     return ControllingMacro;
  70   }
  71
  72   if (!ControllingMacroID || !External)
  73     return nullptr;
  74
  75   ControllingMacro = External->GetIdentifier(ControllingMacroID);
  76   return ControllingMacro;
  77 }
  78
  79 ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() = default;
  80
  81 HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
  82                            SourceManager &SourceMgr, DiagnosticsEngine &Diags,
  83                            const LangOptions &LangOpts,
  84                            const TargetInfo *Target)
  85     : HSOpts(std::move(HSOpts)), Diags(Diags),
  86       FileMgr(SourceMgr.getFileManager()), FrameworkMap(64),
  87       ModMap(SourceMgr, Diags, LangOpts, Target, *this) {}
  88
  89 void HeaderSearch::PrintStats() {
  90   llvm::errs() << "\n*** HeaderSearch Stats:\n"
  91                << FileInfo.size() << " files tracked.\n";
  92   unsigned NumOnceOnlyFiles = 0, MaxNumIncludes = 0, NumSingleIncludedFiles = 0;
  93   for (unsigned i = 0, e = FileInfo.size(); i != e; ++i) {
  94     NumOnceOnlyFiles += FileInfo[i].isImport;
  95     if (MaxNumIncludes < FileInfo[i].NumIncludes)
  96       MaxNumIncludes = FileInfo[i].NumIncludes;
  97     NumSingleIncludedFiles += FileInfo[i].NumIncludes == 1;
  98   }
  99   llvm::errs() << "  " << NumOnceOnlyFiles << " #import/#pragma once files.\n"
 100                << "  " << NumSingleIncludedFiles << " included exactly once.\n"
 101                << "  " << MaxNumIncludes << " max times a file is included.\n";
 102
 103   llvm::errs() << "  " << NumIncluded << " #include/#include_next/#import.\n"
 104                << "    " << NumMultiIncludeFileOptzn
 105                << " #includes skipped due to the multi-include optimization.\n";
 106
 107   llvm::errs() << NumFrameworkLookups << " framework lookups.\n"
 108                << NumSubFrameworkLookups << " subframework lookups.\n";
 109 }
 110
 111 /// CreateHeaderMap - This method returns a HeaderMap for the specified
 112 /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
 113 const HeaderMap *HeaderSearch::CreateHeaderMap(const FileEntry *FE) {
 114   // We expect the number of headermaps to be small, and almost always empty.
 115   // If it ever grows, use of a linear search should be re-evaluated.
 116   if (!HeaderMaps.empty()) {
 117     for (unsigned i = 0, e = HeaderMaps.size(); i != e; ++i)
 118       // Pointer equality comparison of FileEntries works because they are
 119       // already uniqued by inode.
 120       if (HeaderMaps[i].first == FE)
 121         return HeaderMaps[i].second.get();
 122   }
 123
 124   if (std::unique_ptr<HeaderMap> HM = HeaderMap::Create(FE, FileMgr)) {
 125     HeaderMaps.emplace_back(FE, std::move(HM));
 126     return HeaderMaps.back().second.get();
 127   }
 128
 129   return nullptr;
 130 }
 131
 132 /// Get filenames for all registered header maps.
 133 void HeaderSearch::getHeaderMapFileNames(
 134     SmallVectorImpl<std::string> &Names) const {
 135   for (auto &HM : HeaderMaps)
 136     Names.push_back(HM.first->getName());
 137 }
 138
 139 std::string HeaderSearch::getCachedModuleFileName(Module *Module) {
 140   const FileEntry *ModuleMap =
 141       getModuleMap().getModuleMapFileForUniquing(Module);
 142   return getCachedModuleFileName(Module->Name, ModuleMap->getName());
 143 }
 144
 145 std::string HeaderSearch::getPrebuiltModuleFileName(StringRef ModuleName,
 146                                                     bool FileMapOnly) {
 147   // First check the module name to pcm file map.
 148   auto i (HSOpts->PrebuiltModuleFiles.find(ModuleName));
 149   if (i != HSOpts->PrebuiltModuleFiles.end())
 150     return i->second;
 151
 152   if (FileMapOnly || HSOpts->PrebuiltModulePaths.empty())
 153     return {};
 154
 155   // Then go through each prebuilt module directory and try to find the pcm
 156   // file.
 157   for (const std::string &Dir : HSOpts->PrebuiltModulePaths) {
 158     SmallString<256> Result(Dir);
 159     llvm::sys::fs::make_absolute(Result);
 160     llvm::sys::path::append(Result, ModuleName + ".pcm");
 161     if (getFileMgr().getFile(Result.str()))
 162       return Result.str().str();
 163   }
 164   return {};
 165 }
 166
 167 std::string HeaderSearch::getCachedModuleFileName(StringRef ModuleName,
 168                                                   StringRef ModuleMapPath) {
 169   // If we don't have a module cache path or aren't supposed to use one, we
 170   // can't do anything.
 171   if (getModuleCachePath().empty())
 172     return {};
 173
 174   SmallString<256> Result(getModuleCachePath());
 175   llvm::sys::fs::make_absolute(Result);
 176
 177   if (HSOpts->DisableModuleHash) {
 178     llvm::sys::path::append(Result, ModuleName + ".pcm");
 179   } else {
 180     // Construct the name <ModuleName>-<hash of ModuleMapPath>.pcm which should
 181     // ideally be globally unique to this particular module. Name collisions
 182     // in the hash are safe (because any translation unit can only import one
 183     // module with each name), but result in a loss of caching.
 184     //
 185     // To avoid false-negatives, we form as canonical a path as we can, and map
 186     // to lower-case in case we're on a case-insensitive file system.
 187     std::string Parent = llvm::sys::path::parent_path(ModuleMapPath);
 188     if (Parent.empty())
 189       Parent = ".";
 190     auto Dir = FileMgr.getDirectory(Parent);
 191     if (!Dir)
 192       return {};
 193     auto DirName = FileMgr.getCanonicalName(*Dir);
 194     auto FileName = llvm::sys::path::filename(ModuleMapPath);
 195
 196     llvm::hash_code Hash =
 197       llvm::hash_combine(DirName.lower(), FileName.lower());
 198
 199     SmallString<128> HashStr;
 200     llvm::APInt(64, size_t(Hash)).toStringUnsigned(HashStr, /*Radix*/36);
 201     llvm::sys::path::append(Result, ModuleName + "-" + HashStr + ".pcm");
 202   }
 203   return Result.str().str();
 204 }
 205
 206 Module *HeaderSearch::lookupModule(StringRef ModuleName, bool AllowSearch,
 207                                    bool AllowExtraModuleMapSearch) {
 208   // Look in the module map to determine if there is a module by this name.
 209   Module *Module = ModMap.findModule(ModuleName);
 210   if (Module || !AllowSearch || !HSOpts->ImplicitModuleMaps)
 211     return Module;
 212
 213   StringRef SearchName = ModuleName;
 214   Module = lookupModule(ModuleName, SearchName, AllowExtraModuleMapSearch);
 215
 216   // The facility for "private modules" -- adjacent, optional module maps named
 217   // module.private.modulemap that are supposed to define private submodules --
 218   // may have different flavors of names: FooPrivate, Foo_Private and Foo.Private.
 219   //
 220   // Foo.Private is now deprecated in favor of Foo_Private. Users of FooPrivate
 221   // should also rename to Foo_Private. Representing private as submodules
 222   // could force building unwanted dependencies into the parent module and cause
 223   // dependency cycles.
 224   if (!Module && SearchName.consume_back("_Private"))
 225     Module = lookupModule(ModuleName, SearchName, AllowExtraModuleMapSearch);
 226   if (!Module && SearchName.consume_back("Private"))
 227     Module = lookupModule(ModuleName, SearchName, AllowExtraModuleMapSearch);
 228   return Module;
 229 }
 230
 231 Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
 232                                    bool AllowExtraModuleMapSearch) {
 233   Module *Module = nullptr;
 234
 235   // Look through the various header search paths to load any available module
 236   // maps, searching for a module map that describes this module.
 237   for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
 238     if (SearchDirs[Idx].isFramework()) {
 239       // Search for or infer a module map for a framework. Here we use
 240       // SearchName rather than ModuleName, to permit finding private modules
 241       // named FooPrivate in buggy frameworks named Foo.
 242       SmallString<128> FrameworkDirName;
 243       FrameworkDirName += SearchDirs[Idx].getFrameworkDir()->getName();
 244       llvm::sys::path::append(FrameworkDirName, SearchName + ".framework");
 245       if (auto FrameworkDir = FileMgr.getDirectory(FrameworkDirName)) {
 246         bool IsSystem
 247           = SearchDirs[Idx].getDirCharacteristic() != SrcMgr::C_User;
 248         Module = loadFrameworkModule(ModuleName, *FrameworkDir, IsSystem);
 249         if (Module)
 250           break;
 251       }
 252     }
 253
 254     // FIXME: Figure out how header maps and module maps will work together.
 255
 256     // Only deal with normal search directories.
 257     if (!SearchDirs[Idx].isNormalDir())
 258       continue;
 259
 260     bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
 261     // Search for a module map file in this directory.
 262     if (loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
 263                           /*IsFramework*/false) == LMM_NewlyLoaded) {
 264       // We just loaded a module map file; check whether the module is
 265       // available now.
 266       Module = ModMap.findModule(ModuleName);
 267       if (Module)
 268         break;
 269     }
 270
 271     // Search for a module map in a subdirectory with the same name as the
 272     // module.
 273     SmallString<128> NestedModuleMapDirName;
 274     NestedModuleMapDirName = SearchDirs[Idx].getDir()->getName();
 275     llvm::sys::path::append(NestedModuleMapDirName, ModuleName);
 276     if (loadModuleMapFile(NestedModuleMapDirName, IsSystem,
 277                           /*IsFramework*/false) == LMM_NewlyLoaded){
 278       // If we just loaded a module map file, look for the module again.
 279       Module = ModMap.findModule(ModuleName);
 280       if (Module)
 281         break;
 282     }
 283
 284     // If we've already performed the exhaustive search for module maps in this
 285     // search directory, don't do it again.
 286     if (SearchDirs[Idx].haveSearchedAllModuleMaps())
 287       continue;
 288
 289     // Load all module maps in the immediate subdirectories of this search
 290     // directory if ModuleName was from @import.
 291     if (AllowExtraModuleMapSearch)
 292       loadSubdirectoryModuleMaps(SearchDirs[Idx]);
 293
 294     // Look again for the module.
 295     Module = ModMap.findModule(ModuleName);
 296     if (Module)
 297       break;
 298   }
 299
 300   return Module;
 301 }
 302
 303 //===----------------------------------------------------------------------===//
 304 // File lookup within a DirectoryLookup scope
 305 //===----------------------------------------------------------------------===//
 306
 307 /// getName - Return the directory or filename corresponding to this lookup
 308 /// object.
 309 StringRef DirectoryLookup::getName() const {
 310   // FIXME: Use the name from \c DirectoryEntryRef.
 311   if (isNormalDir())
 312     return getDir()->getName();
 313   if (isFramework())
 314     return getFrameworkDir()->getName();
 315   assert(isHeaderMap() && "Unknown DirectoryLookup");
 316   return getHeaderMap()->getFileName();
 317 }
 318
 319 Optional<FileEntryRef> HeaderSearch::getFileAndSuggestModule(
 320     StringRef FileName, SourceLocation IncludeLoc, const DirectoryEntry *Dir,
 321     bool IsSystemHeaderDir, Module *RequestingModule,
 322     ModuleMap::KnownHeader *SuggestedModule) {
 323   // If we have a module map that might map this header, load it and
 324   // check whether we'll have a suggestion for a module.
 325   auto File = getFileMgr().getFileRef(FileName, /*OpenFile=*/true);
 326   if (!File) {
 327     // For rare, surprising errors (e.g. "out of file handles"), diag the EC
 328     // message.
 329     std::error_code EC = llvm::errorToErrorCode(File.takeError());
 330     if (EC != llvm::errc::no_such_file_or_directory &&
 331         EC != llvm::errc::invalid_argument &&
 332         EC != llvm::errc::is_a_directory && EC != llvm::errc::not_a_directory) {
 333       Diags.Report(IncludeLoc, diag::err_cannot_open_file)
 334           << FileName << EC.message();
 335     }
 336     return None;
 337   }
 338
 339   // If there is a module that corresponds to this header, suggest it.
 340   if (!findUsableModuleForHeader(
 341           &File->getFileEntry(), Dir ? Dir : File->getFileEntry().getDir(),
 342           RequestingModule, SuggestedModule, IsSystemHeaderDir))
 343     return None;
 344
 345   return *File;
 346 }
 347
 348 /// LookupFile - Lookup the specified file in this search path, returning it
 349 /// if it exists or returning null if not.
 350 Optional<FileEntryRef> DirectoryLookup::LookupFile(
 351     StringRef &Filename, HeaderSearch &HS, SourceLocation IncludeLoc,
 352     SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,
 353     Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule,
 354     bool &InUserSpecifiedSystemFramework, bool &IsFrameworkFound,
 355     bool &IsInHeaderMap, SmallVectorImpl<char> &MappedName) const {
 356   InUserSpecifiedSystemFramework = false;
 357   IsInHeaderMap = false;
 358   MappedName.clear();
 359
 360   SmallString<1024> TmpDir;
 361   if (isNormalDir()) {
 362     // Concatenate the requested file onto the directory.
 363     TmpDir = getDir()->getName();
 364     llvm::sys::path::append(TmpDir, Filename);
 365     if (SearchPath) {
 366       StringRef SearchPathRef(getDir()->getName());
 367       SearchPath->clear();
 368       SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
 369     }
 370     if (RelativePath) {
 371       RelativePath->clear();
 372       RelativePath->append(Filename.begin(), Filename.end());
 373     }
 374
 375     return HS.getFileAndSuggestModule(TmpDir, IncludeLoc, getDir(),
 376                                       isSystemHeaderDirectory(),
 377                                       RequestingModule, SuggestedModule);
 378   }
 379
 380   if (isFramework())
 381     return DoFrameworkLookup(Filename, HS, SearchPath, RelativePath,
 382                              RequestingModule, SuggestedModule,
 383                              InUserSpecifiedSystemFramework, IsFrameworkFound);
 384
 385   assert(isHeaderMap() && "Unknown directory lookup");
 386   const HeaderMap *HM = getHeaderMap();
 387   SmallString<1024> Path;
 388   StringRef Dest = HM->lookupFilename(Filename, Path);
 389   if (Dest.empty())
 390     return None;
 391
 392   IsInHeaderMap = true;
 393
 394   auto FixupSearchPath = [&]() {
 395     if (SearchPath) {
 396       StringRef SearchPathRef(getName());
 397       SearchPath->clear();
 398       SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
 399     }
 400     if (RelativePath) {
 401       RelativePath->clear();
 402       RelativePath->append(Filename.begin(), Filename.end());
 403     }
 404   };
 405
 406   // Check if the headermap maps the filename to a framework include
 407   // ("Foo.h" -> "Foo/Foo.h"), in which case continue header lookup using the
 408   // framework include.
 409   if (llvm::sys::path::is_relative(Dest)) {
 410     MappedName.append(Dest.begin(), Dest.end());
 411     Filename = StringRef(MappedName.begin(), MappedName.size());
 412     Optional<FileEntryRef> Result = HM->LookupFile(Filename, HS.getFileMgr());
 413     if (Result) {
 414       FixupSearchPath();
 415       return *Result;
 416     }
 417   } else if (auto Res = HS.getFileMgr().getOptionalFileRef(Dest)) {
 418     FixupSearchPath();
 419     return *Res;
 420   }
 421
 422   return None;
 423 }
 424
 425 /// Given a framework directory, find the top-most framework directory.
 426 ///
 427 /// \param FileMgr The file manager to use for directory lookups.
 428 /// \param DirName The name of the framework directory.
 429 /// \param SubmodulePath Will be populated with the submodule path from the
 430 /// returned top-level module to the originally named framework.
 431 static const DirectoryEntry *
 432 getTopFrameworkDir(FileManager &FileMgr, StringRef DirName,
 433                    SmallVectorImpl<std::string> &SubmodulePath) {
 434   assert(llvm::sys::path::extension(DirName) == ".framework" &&
 435          "Not a framework directory");
 436
 437   // Note: as an egregious but useful hack we use the real path here, because
 438   // frameworks moving between top-level frameworks to embedded frameworks tend
 439   // to be symlinked, and we base the logical structure of modules on the
 440   // physical layout. In particular, we need to deal with crazy includes like
 441   //
 442   //   #include <Foo/Frameworks/Bar.framework/Headers/Wibble.h>
 443   //
 444   // where 'Bar' used to be embedded in 'Foo', is now a top-level framework
 445   // which one should access with, e.g.,
 446   //
 447   //   #include <Bar/Wibble.h>
 448   //
 449   // Similar issues occur when a top-level framework has moved into an
 450   // embedded framework.
 451   const DirectoryEntry *TopFrameworkDir = nullptr;
 452   if (auto TopFrameworkDirOrErr = FileMgr.getDirectory(DirName))
 453     TopFrameworkDir = *TopFrameworkDirOrErr;
 454
 455   if (TopFrameworkDir)
 456     DirName = FileMgr.getCanonicalName(TopFrameworkDir);
 457   do {
 458     // Get the parent directory name.
 459     DirName = llvm::sys::path::parent_path(DirName);
 460     if (DirName.empty())
 461       break;
 462
 463     // Determine whether this directory exists.
 464     auto Dir = FileMgr.getDirectory(DirName);
 465     if (!Dir)
 466       break;
 467
 468     // If this is a framework directory, then we're a subframework of this
 469     // framework.
 470     if (llvm::sys::path::extension(DirName) == ".framework") {
 471       SubmodulePath.push_back(llvm::sys::path::stem(DirName));
 472       TopFrameworkDir = *Dir;
 473     }
 474   } while (true);
 475
 476   return TopFrameworkDir;
 477 }
 478
 479 static bool needModuleLookup(Module *RequestingModule,
 480                              bool HasSuggestedModule) {
 481   return HasSuggestedModule ||
 482          (RequestingModule && RequestingModule->NoUndeclaredIncludes);
 483 }
 484
 485 /// DoFrameworkLookup - Do a lookup of the specified file in the current
 486 /// DirectoryLookup, which is a framework directory.
 487 Optional<FileEntryRef> DirectoryLookup::DoFrameworkLookup(
 488     StringRef Filename, HeaderSearch &HS, SmallVectorImpl<char> *SearchPath,
 489     SmallVectorImpl<char> *RelativePath, Module *RequestingModule,
 490     ModuleMap::KnownHeader *SuggestedModule,
 491     bool &InUserSpecifiedSystemFramework, bool &IsFrameworkFound) const {
 492   FileManager &FileMgr = HS.getFileMgr();
 493
 494   // Framework names must have a '/' in the filename.
 495   size_t SlashPos = Filename.find('/');
 496   if (SlashPos == StringRef::npos)
 497     return None;
 498
 499   // Find out if this is the home for the specified framework, by checking
 500   // HeaderSearch.  Possible answers are yes/no and unknown.
 501   FrameworkCacheEntry &CacheEntry =
 502     HS.LookupFrameworkCache(Filename.substr(0, SlashPos));
 503
 504   // If it is known and in some other directory, fail.
 505   if (CacheEntry.Directory && CacheEntry.Directory != getFrameworkDir())
 506     return None;
 507
 508   // Otherwise, construct the path to this framework dir.
 509
 510   // FrameworkName = "/System/Library/Frameworks/"
 511   SmallString<1024> FrameworkName;
 512   FrameworkName += getFrameworkDirRef()->getName();
 513   if (FrameworkName.empty() || FrameworkName.back() != '/')
 514     FrameworkName.push_back('/');
 515
 516   // FrameworkName = "/System/Library/Frameworks/Cocoa"
 517   StringRef ModuleName(Filename.begin(), SlashPos);
 518   FrameworkName += ModuleName;
 519
 520   // FrameworkName = "/System/Library/Frameworks/Cocoa.framework/"
 521   FrameworkName += ".framework/";
 522
 523   // If the cache entry was unresolved, populate it now.
 524   if (!CacheEntry.Directory) {
 525     ++NumFrameworkLookups;
 526
 527     // If the framework dir doesn't exist, we fail.
 528     auto Dir = FileMgr.getDirectory(FrameworkName);
 529     if (!Dir)
 530       return None;
 531
 532     // Otherwise, if it does, remember that this is the right direntry for this
 533     // framework.
 534     CacheEntry.Directory = getFrameworkDir();
 535
 536     // If this is a user search directory, check if the framework has been
 537     // user-specified as a system framework.
 538     if (getDirCharacteristic() == SrcMgr::C_User) {
 539       SmallString<1024> SystemFrameworkMarker(FrameworkName);
 540       SystemFrameworkMarker += ".system_framework";
 541       if (llvm::sys::fs::exists(SystemFrameworkMarker)) {
 542         CacheEntry.IsUserSpecifiedSystemFramework = true;
 543       }
 544     }
 545   }
 546
 547   // Set out flags.
 548   InUserSpecifiedSystemFramework = CacheEntry.IsUserSpecifiedSystemFramework;
 549   IsFrameworkFound = CacheEntry.Directory;
 550
 551   if (RelativePath) {
 552     RelativePath->clear();
 553     RelativePath->append(Filename.begin()+SlashPos+1, Filename.end());
 554   }
 555
 556   // Check "/System/Library/Frameworks/Cocoa.framework/Headers/file.h"
 557   unsigned OrigSize = FrameworkName.size();
 558
 559   FrameworkName += "Headers/";
 560
 561   if (SearchPath) {
 562     SearchPath->clear();
 563     // Without trailing '/'.
 564     SearchPath->append(FrameworkName.begin(), FrameworkName.end()-1);
 565   }
 566
 567   FrameworkName.append(Filename.begin()+SlashPos+1, Filename.end());
 568
 569   auto File =
 570       FileMgr.getOptionalFileRef(FrameworkName, /*OpenFile=*/!SuggestedModule);
 571   if (!File) {
 572     // Check "/System/Library/Frameworks/Cocoa.framework/PrivateHeaders/file.h"
 573     const char *Private = "Private";
 574     FrameworkName.insert(FrameworkName.begin()+OrigSize, Private,
 575                          Private+strlen(Private));
 576     if (SearchPath)
 577       SearchPath->insert(SearchPath->begin()+OrigSize, Private,
 578                          Private+strlen(Private));
 579
 580     File = FileMgr.getOptionalFileRef(FrameworkName,
 581                                       /*OpenFile=*/!SuggestedModule);
 582   }
 583
 584   // If we found the header and are allowed to suggest a module, do so now.
 585   if (File && needModuleLookup(RequestingModule, SuggestedModule)) {
 586     // Find the framework in which this header occurs.
 587     StringRef FrameworkPath = File->getFileEntry().getDir()->getName();
 588     bool FoundFramework = false;
 589     do {
 590       // Determine whether this directory exists.
 591       auto Dir = FileMgr.getDirectory(FrameworkPath);
 592       if (!Dir)
 593         break;
 594
 595       // If this is a framework directory, then we're a subframework of this
 596       // framework.
 597       if (llvm::sys::path::extension(FrameworkPath) == ".framework") {
 598         FoundFramework = true;
 599         break;
 600       }
 601
 602       // Get the parent directory name.
 603       FrameworkPath = llvm::sys::path::parent_path(FrameworkPath);
 604       if (FrameworkPath.empty())
 605         break;
 606     } while (true);
 607
 608     bool IsSystem = getDirCharacteristic() != SrcMgr::C_User;
 609     if (FoundFramework) {
 610       if (!HS.findUsableModuleForFrameworkHeader(
 611               &File->getFileEntry(), FrameworkPath, RequestingModule,
 612               SuggestedModule, IsSystem))
 613         return None;
 614     } else {
 615       if (!HS.findUsableModuleForHeader(&File->getFileEntry(), getDir(),
 616                                         RequestingModule, SuggestedModule,
 617                                         IsSystem))
 618         return None;
 619     }
 620   }
 621   if (File)
 622     return *File;
 623   return None;
 624 }
 625
 626 void HeaderSearch::setTarget(const TargetInfo &Target) {
 627   ModMap.setTarget(Target);
 628 }
 629
 630 //===----------------------------------------------------------------------===//
 631 // Header File Location.
 632 //===----------------------------------------------------------------------===//
 633
 634 /// Return true with a diagnostic if the file that MSVC would have found
 635 /// fails to match the one that Clang would have found with MSVC header search
 636 /// disabled.
 637 static bool checkMSVCHeaderSearch(DiagnosticsEngine &Diags,
 638                                   const FileEntry *MSFE, const FileEntry *FE,
 639                                   SourceLocation IncludeLoc) {
 640   if (MSFE && FE != MSFE) {
 641     Diags.Report(IncludeLoc, diag::ext_pp_include_search_ms) << MSFE->getName();
 642     return true;
 643   }
 644   return false;
 645 }
 646
 647 static const char *copyString(StringRef Str, llvm::BumpPtrAllocator &Alloc) {
 648   assert(!Str.empty());
 649   char *CopyStr = Alloc.Allocate<char>(Str.size()+1);
 650   std::copy(Str.begin(), Str.end(), CopyStr);
 651   CopyStr[Str.size()] = '\0';
 652   return CopyStr;
 653 }
 654
 655 static bool isFrameworkStylePath(StringRef Path, bool &IsPrivateHeader,
 656                                  SmallVectorImpl<char> &FrameworkName) {
 657   using namespace llvm::sys;
 658   path::const_iterator I = path::begin(Path);
 659   path::const_iterator E = path::end(Path);
 660   IsPrivateHeader = false;
 661
 662   // Detect different types of framework style paths:
 663   //
 664   //   ...Foo.framework/{Headers,PrivateHeaders}
 665   //   ...Foo.framework/Versions/{A,Current}/{Headers,PrivateHeaders}
 666   //   ...Foo.framework/Frameworks/Nested.framework/{Headers,PrivateHeaders}
 667   //   ...<other variations with 'Versions' like in the above path>
 668   //
 669   // and some other variations among these lines.
 670   int FoundComp = 0;
 671   while (I != E) {
 672     if (*I == "Headers")
 673       ++FoundComp;
 674     if (I->endswith(".framework")) {
 675       FrameworkName.append(I->begin(), I->end());
 676       ++FoundComp;
 677     }
 678     if (*I == "PrivateHeaders") {
 679       ++FoundComp;
 680       IsPrivateHeader = true;
 681     }
 682     ++I;
 683   }
 684
 685   return !FrameworkName.empty() && FoundComp >= 2;
 686 }
 687
 688 static void
 689 diagnoseFrameworkInclude(DiagnosticsEngine &Diags, SourceLocation IncludeLoc,
 690                          StringRef Includer, StringRef IncludeFilename,
 691                          const FileEntry *IncludeFE, bool isAngled = false,
 692                          bool FoundByHeaderMap = false) {
 693   bool IsIncluderPrivateHeader = false;
 694   SmallString<128> FromFramework, ToFramework;
 695   if (!isFrameworkStylePath(Includer, IsIncluderPrivateHeader, FromFramework))
 696     return;
 697   bool IsIncludeePrivateHeader = false;
 698   bool IsIncludeeInFramework = isFrameworkStylePath(
 699       IncludeFE->getName(), IsIncludeePrivateHeader, ToFramework);
 700
 701   if (!isAngled && !FoundByHeaderMap) {
 702     SmallString<128> NewInclude("<");
 703     if (IsIncludeeInFramework) {
 704       NewInclude += StringRef(ToFramework).drop_back(10); // drop .framework
 705       NewInclude += "/";
 706     }
 707     NewInclude += IncludeFilename;
 708     NewInclude += ">";
 709     Diags.Report(IncludeLoc, diag::warn_quoted_include_in_framework_header)
 710         << IncludeFilename
 711         << FixItHint::CreateReplacement(IncludeLoc, NewInclude);
 712   }
 713
 714   // Headers in Foo.framework/Headers should not include headers
 715   // from Foo.framework/PrivateHeaders, since this violates public/private
 716   // API boundaries and can cause modular dependency cycles.
 717   if (!IsIncluderPrivateHeader && IsIncludeeInFramework &&
 718       IsIncludeePrivateHeader && FromFramework == ToFramework)
 719     Diags.Report(IncludeLoc, diag::warn_framework_include_private_from_public)
 720         << IncludeFilename;
 721 }
 722
 723 /// LookupFile - Given a "foo" or \<foo> reference, look up the indicated file,
 724 /// return null on failure.  isAngled indicates whether the file reference is
 725 /// for system \#include's or not (i.e. using <> instead of ""). Includers, if
 726 /// non-empty, indicates where the \#including file(s) are, in case a relative
 727 /// search is needed. Microsoft mode will pass all \#including files.
 728 Optional<FileEntryRef> HeaderSearch::LookupFile(
 729     StringRef Filename, SourceLocation IncludeLoc, bool isAngled,
 730     const DirectoryLookup *FromDir, const DirectoryLookup *&CurDir,
 731     ArrayRef<std::pair<const FileEntry *, const DirectoryEntry *>> Includers,
 732     SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,
 733     Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule,
 734     bool *IsMapped, bool *IsFrameworkFound, bool SkipCache,
 735     bool BuildSystemModule) {
 736   if (IsMapped)
 737     *IsMapped = false;
 738
 739   if (IsFrameworkFound)
 740     *IsFrameworkFound = false;
 741
 742   if (SuggestedModule)
 743     *SuggestedModule = ModuleMap::KnownHeader();
 744
 745   // If 'Filename' is absolute, check to see if it exists and no searching.
 746   if (llvm::sys::path::is_absolute(Filename)) {
 747     CurDir = nullptr;
 748
 749     // If this was an #include_next "/absolute/file", fail.
 750     if (FromDir)
 751       return None;
 752
 753     if (SearchPath)
 754       SearchPath->clear();
 755     if (RelativePath) {
 756       RelativePath->clear();
 757       RelativePath->append(Filename.begin(), Filename.end());
 758     }
 759     // Otherwise, just return the file.
 760     return getFileAndSuggestModule(Filename, IncludeLoc, nullptr,
 761                                    /*IsSystemHeaderDir*/false,
 762                                    RequestingModule, SuggestedModule);
 763   }
 764
 765   // This is the header that MSVC's header search would have found.
 766   ModuleMap::KnownHeader MSSuggestedModule;
 767   const FileEntry *MSFE_FE = nullptr;
 768   StringRef MSFE_Name;
 769
 770   // Unless disabled, check to see if the file is in the #includer's
 771   // directory.  This cannot be based on CurDir, because each includer could be
 772   // a #include of a subdirectory (#include "foo/bar.h") and a subsequent
 773   // include of "baz.h" should resolve to "whatever/foo/baz.h".
 774   // This search is not done for <> headers.
 775   if (!Includers.empty() && !isAngled && !NoCurDirSearch) {
 776     SmallString<1024> TmpDir;
 777     bool First = true;
 778     for (const auto &IncluderAndDir : Includers) {
 779       const FileEntry *Includer = IncluderAndDir.first;
 780
 781       // Concatenate the requested file onto the directory.
 782       // FIXME: Portability.  Filename concatenation should be in sys::Path.
 783       TmpDir = IncluderAndDir.second->getName();
 784       TmpDir.push_back('/');
 785       TmpDir.append(Filename.begin(), Filename.end());
 786
 787       // FIXME: We don't cache the result of getFileInfo across the call to
 788       // getFileAndSuggestModule, because it's a reference to an element of
 789       // a container that could be reallocated across this call.
 790       //
 791       // If we have no includer, that means we're processing a #include
 792       // from a module build. We should treat this as a system header if we're
 793       // building a [system] module.
 794       bool IncluderIsSystemHeader =
 795           Includer ? getFileInfo(Includer).DirInfo != SrcMgr::C_User :
 796           BuildSystemModule;
 797       if (Optional<FileEntryRef> FE = getFileAndSuggestModule(
 798               TmpDir, IncludeLoc, IncluderAndDir.second, IncluderIsSystemHeader,
 799               RequestingModule, SuggestedModule)) {
 800         if (!Includer) {
 801           assert(First && "only first includer can have no file");
 802           return FE;
 803         }
 804
 805         // Leave CurDir unset.
 806         // This file is a system header or C++ unfriendly if the old file is.
 807         //
 808         // Note that we only use one of FromHFI/ToHFI at once, due to potential
 809         // reallocation of the underlying vector potentially making the first
 810         // reference binding dangling.
 811         HeaderFileInfo &FromHFI = getFileInfo(Includer);
 812         unsigned DirInfo = FromHFI.DirInfo;
 813         bool IndexHeaderMapHeader = FromHFI.IndexHeaderMapHeader;
 814         StringRef Framework = FromHFI.Framework;
 815
 816         HeaderFileInfo &ToHFI = getFileInfo(&FE->getFileEntry());
 817         ToHFI.DirInfo = DirInfo;
 818         ToHFI.IndexHeaderMapHeader = IndexHeaderMapHeader;
 819         ToHFI.Framework = Framework;
 820
 821         if (SearchPath) {
 822           StringRef SearchPathRef(IncluderAndDir.second->getName());
 823           SearchPath->clear();
 824           SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());
 825         }
 826         if (RelativePath) {
 827           RelativePath->clear();
 828           RelativePath->append(Filename.begin(), Filename.end());
 829         }
 830         if (First) {
 831           diagnoseFrameworkInclude(Diags, IncludeLoc,
 832                                    IncluderAndDir.second->getName(), Filename,
 833                                    &FE->getFileEntry());
 834           return FE;
 835         }
 836
 837         // Otherwise, we found the path via MSVC header search rules.  If
 838         // -Wmsvc-include is enabled, we have to keep searching to see if we
 839         // would've found this header in -I or -isystem directories.
 840         if (Diags.isIgnored(diag::ext_pp_include_search_ms, IncludeLoc)) {
 841           return FE;
 842         } else {
 843           MSFE_FE = &FE->getFileEntry();
 844           MSFE_Name = FE->getName();
 845           if (SuggestedModule) {
 846             MSSuggestedModule = *SuggestedModule;
 847             *SuggestedModule = ModuleMap::KnownHeader();
 848           }
 849           break;
 850         }
 851       }
 852       First = false;
 853     }
 854   }
 855
 856   Optional<FileEntryRef> MSFE(MSFE_FE ? FileEntryRef(MSFE_Name, *MSFE_FE)
 857                                       : Optional<FileEntryRef>());
 858
 859   CurDir = nullptr;
 860
 861   // If this is a system #include, ignore the user #include locs.
 862   unsigned i = isAngled ? AngledDirIdx : 0;
 863
 864   // If this is a #include_next request, start searching after the directory the
 865   // file was found in.
 866   if (FromDir)
 867     i = FromDir-&SearchDirs[0];
 868
 869   // Cache all of the lookups performed by this method.  Many headers are
 870   // multiply included, and the "pragma once" optimization prevents them from
 871   // being relex/pp'd, but they would still have to search through a
 872   // (potentially huge) series of SearchDirs to find it.
 873   LookupFileCacheInfo &CacheLookup = LookupFileCache[Filename];
 874
 875   // If the entry has been previously looked up, the first value will be
 876   // non-zero.  If the value is equal to i (the start point of our search), then
 877   // this is a matching hit.
 878   if (!SkipCache && CacheLookup.StartIdx == i+1) {
 879     // Skip querying potentially lots of directories for this lookup.
 880     i = CacheLookup.HitIdx;
 881     if (CacheLookup.MappedName) {
 882       Filename = CacheLookup.MappedName;
 883       if (IsMapped)
 884         *IsMapped = true;
 885     }
 886   } else {
 887     // Otherwise, this is the first query, or the previous query didn't match
 888     // our search start.  We will fill in our found location below, so prime the
 889     // start point value.
 890     CacheLookup.reset(/*StartIdx=*/i+1);
 891   }
 892
 893   SmallString<64> MappedName;
 894
 895   // Check each directory in sequence to see if it contains this file.
 896   for (; i != SearchDirs.size(); ++i) {
 897     bool InUserSpecifiedSystemFramework = false;
 898     bool IsInHeaderMap = false;
 899     bool IsFrameworkFoundInDir = false;
 900     Optional<FileEntryRef> File = SearchDirs[i].LookupFile(
 901         Filename, *this, IncludeLoc, SearchPath, RelativePath, RequestingModule,
 902         SuggestedModule, InUserSpecifiedSystemFramework, IsFrameworkFoundInDir,
 903         IsInHeaderMap, MappedName);
 904     if (!MappedName.empty()) {
 905       assert(IsInHeaderMap && "MappedName should come from a header map");
 906       CacheLookup.MappedName =
 907           copyString(MappedName, LookupFileCache.getAllocator());
 908     }
 909     if (IsMapped)
 910       // A filename is mapped when a header map remapped it to a relative path
 911       // used in subsequent header search or to an absolute path pointing to an
 912       // existing file.
 913       *IsMapped |= (!MappedName.empty() || (IsInHeaderMap && File));
 914     if (IsFrameworkFound)
 915       // Because we keep a filename remapped for subsequent search directory
 916       // lookups, ignore IsFrameworkFoundInDir after the first remapping and not
 917       // just for remapping in a current search directory.
 918       *IsFrameworkFound |= (IsFrameworkFoundInDir && !CacheLookup.MappedName);
 919     if (!File)
 920       continue;
 921
 922     CurDir = &SearchDirs[i];
 923
 924     // This file is a system header or C++ unfriendly if the dir is.
 925     HeaderFileInfo &HFI = getFileInfo(&File->getFileEntry());
 926     HFI.DirInfo = CurDir->getDirCharacteristic();
 927
 928     // If the directory characteristic is User but this framework was
 929     // user-specified to be treated as a system framework, promote the
 930     // characteristic.
 931     if (HFI.DirInfo == SrcMgr::C_User && InUserSpecifiedSystemFramework)
 932       HFI.DirInfo = SrcMgr::C_System;
 933
 934     // If the filename matches a known system header prefix, override
 935     // whether the file is a system header.
 936     for (unsigned j = SystemHeaderPrefixes.size(); j; --j) {
 937       if (Filename.startswith(SystemHeaderPrefixes[j-1].first)) {
 938         HFI.DirInfo = SystemHeaderPrefixes[j-1].second ? SrcMgr::C_System
 939                                                        : SrcMgr::C_User;
 940         break;
 941       }
 942     }
 943
 944     // If this file is found in a header map and uses the framework style of
 945     // includes, then this header is part of a framework we're building.
 946     if (CurDir->isIndexHeaderMap()) {
 947       size_t SlashPos = Filename.find('/');
 948       if (SlashPos != StringRef::npos) {
 949         HFI.IndexHeaderMapHeader = 1;
 950         HFI.Framework = getUniqueFrameworkName(StringRef(Filename.begin(),
 951                                                          SlashPos));
 952       }
 953     }
 954
 955     if (checkMSVCHeaderSearch(Diags, MSFE ? &MSFE->getFileEntry() : nullptr,
 956                               &File->getFileEntry(), IncludeLoc)) {
 957       if (SuggestedModule)
 958         *SuggestedModule = MSSuggestedModule;
 959       return MSFE;
 960     }
 961
 962     bool FoundByHeaderMap = !IsMapped ? false : *IsMapped;
 963     if (!Includers.empty())
 964       diagnoseFrameworkInclude(
 965           Diags, IncludeLoc, Includers.front().second->getName(), Filename,
 966           &File->getFileEntry(), isAngled, FoundByHeaderMap);
 967
 968     // Remember this location for the next lookup we do.
 969     CacheLookup.HitIdx = i;
 970     return File;
 971   }
 972
 973   // If we are including a file with a quoted include "foo.h" from inside
 974   // a header in a framework that is currently being built, and we couldn't
 975   // resolve "foo.h" any other way, change the include to <Foo/foo.h>, where
 976   // "Foo" is the name of the framework in which the including header was found.
 977   if (!Includers.empty() && Includers.front().first && !isAngled &&
 978       Filename.find('/') == StringRef::npos) {
 979     HeaderFileInfo &IncludingHFI = getFileInfo(Includers.front().first);
 980     if (IncludingHFI.IndexHeaderMapHeader) {
 981       SmallString<128> ScratchFilename;
 982       ScratchFilename += IncludingHFI.Framework;
 983       ScratchFilename += '/';
 984       ScratchFilename += Filename;
 985
 986       Optional<FileEntryRef> File = LookupFile(
 987           ScratchFilename, IncludeLoc, /*isAngled=*/true, FromDir, CurDir,
 988           Includers.front(), SearchPath, RelativePath, RequestingModule,
 989           SuggestedModule, IsMapped, /*IsFrameworkFound=*/nullptr);
 990
 991       if (checkMSVCHeaderSearch(Diags, MSFE ? &MSFE->getFileEntry() : nullptr,
 992                                 File ? &File->getFileEntry() : nullptr,
 993                                 IncludeLoc)) {
 994         if (SuggestedModule)
 995           *SuggestedModule = MSSuggestedModule;
 996         return MSFE;
 997       }
 998
 999       LookupFileCacheInfo &CacheLookup = LookupFileCache[Filename];
1000       CacheLookup.HitIdx = LookupFileCache[ScratchFilename].HitIdx;
1001       // FIXME: SuggestedModule.
1002       return File;
1003     }
1004   }
1005
1006   if (checkMSVCHeaderSearch(Diags, MSFE ? &MSFE->getFileEntry() : nullptr,
1007                             nullptr, IncludeLoc)) {
1008     if (SuggestedModule)
1009       *SuggestedModule = MSSuggestedModule;
1010     return MSFE;
1011   }
1012
1013   // Otherwise, didn't find it. Remember we didn't find this.
1014   CacheLookup.HitIdx = SearchDirs.size();
1015   return None;
1016 }
1017
1018 /// LookupSubframeworkHeader - Look up a subframework for the specified
1019 /// \#include file.  For example, if \#include'ing <HIToolbox/HIToolbox.h> from
1020 /// within ".../Carbon.framework/Headers/Carbon.h", check to see if HIToolbox
1021 /// is a subframework within Carbon.framework.  If so, return the FileEntry
1022 /// for the designated file, otherwise return null.
1023 Optional<FileEntryRef> HeaderSearch::LookupSubframeworkHeader(
1024     StringRef Filename, const FileEntry *ContextFileEnt,
1025     SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,
1026     Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule) {
1027   assert(ContextFileEnt && "No context file?");
1028
1029   // Framework names must have a '/' in the filename.  Find it.
1030   // FIXME: Should we permit '\' on Windows?
1031   size_t SlashPos = Filename.find('/');
1032   if (SlashPos == StringRef::npos)
1033     return None;
1034
1035   // Look up the base framework name of the ContextFileEnt.
1036   StringRef ContextName = ContextFileEnt->getName();
1037
1038   // If the context info wasn't a framework, couldn't be a subframework.
1039   const unsigned DotFrameworkLen = 10;
1040   auto FrameworkPos = ContextName.find(".framework");
1041   if (FrameworkPos == StringRef::npos ||
1042       (ContextName[FrameworkPos + DotFrameworkLen] != '/' &&
1043        ContextName[FrameworkPos + DotFrameworkLen] != '\\'))
1044     return None;
1045
1046   SmallString<1024> FrameworkName(ContextName.data(), ContextName.data() +
1047                                                           FrameworkPos +
1048                                                           DotFrameworkLen + 1);
1049
1050   // Append Frameworks/HIToolbox.framework/
1051   FrameworkName += "Frameworks/";
1052   FrameworkName.append(Filename.begin(), Filename.begin()+SlashPos);
1053   FrameworkName += ".framework/";
1054
1055   auto &CacheLookup =
1056       *FrameworkMap.insert(std::make_pair(Filename.substr(0, SlashPos),
1057                                           FrameworkCacheEntry())).first;
1058
1059   // Some other location?
1060   if (CacheLookup.second.Directory &&
1061       CacheLookup.first().size() == FrameworkName.size() &&
1062       memcmp(CacheLookup.first().data(), &FrameworkName[0],
1063              CacheLookup.first().size()) != 0)
1064     return None;
1065
1066   // Cache subframework.
1067   if (!CacheLookup.second.Directory) {
1068     ++NumSubFrameworkLookups;
1069
1070     // If the framework dir doesn't exist, we fail.
1071     auto Dir = FileMgr.getDirectory(FrameworkName);
1072     if (!Dir)
1073       return None;
1074
1075     // Otherwise, if it does, remember that this is the right direntry for this
1076     // framework.
1077     CacheLookup.second.Directory = *Dir;
1078   }
1079
1080
1081   if (RelativePath) {
1082     RelativePath->clear();
1083     RelativePath->append(Filename.begin()+SlashPos+1, Filename.end());
1084   }
1085
1086   // Check ".../Frameworks/HIToolbox.framework/Headers/HIToolbox.h"
1087   SmallString<1024> HeadersFilename(FrameworkName);
1088   HeadersFilename += "Headers/";
1089   if (SearchPath) {
1090     SearchPath->clear();
1091     // Without trailing '/'.
1092     SearchPath->append(HeadersFilename.begin(), HeadersFilename.end()-1);
1093   }
1094
1095   HeadersFilename.append(Filename.begin()+SlashPos+1, Filename.end());
1096   auto File = FileMgr.getOptionalFileRef(HeadersFilename, /*OpenFile=*/true);
1097   if (!File) {
1098     // Check ".../Frameworks/HIToolbox.framework/PrivateHeaders/HIToolbox.h"
1099     HeadersFilename = FrameworkName;
1100     HeadersFilename += "PrivateHeaders/";
1101     if (SearchPath) {
1102       SearchPath->clear();
1103       // Without trailing '/'.
1104       SearchPath->append(HeadersFilename.begin(), HeadersFilename.end()-1);
1105     }
1106
1107     HeadersFilename.append(Filename.begin()+SlashPos+1, Filename.end());
1108     File = FileMgr.getOptionalFileRef(HeadersFilename, /*OpenFile=*/true);
1109
1110     if (!File)
1111       return None;
1112   }
1113
1114   // This file is a system header or C++ unfriendly if the old file is.
1115   //
1116   // Note that the temporary 'DirInfo' is required here, as either call to
1117   // getFileInfo could resize the vector and we don't want to rely on order
1118   // of evaluation.
1119   unsigned DirInfo = getFileInfo(ContextFileEnt).DirInfo;
1120   getFileInfo(&File->getFileEntry()).DirInfo = DirInfo;
1121
1122   FrameworkName.pop_back(); // remove the trailing '/'
1123   if (!findUsableModuleForFrameworkHeader(&File->getFileEntry(), FrameworkName,
1124                                           RequestingModule, SuggestedModule,
1125                                           /*IsSystem*/ false))
1126     return None;
1127
1128   return *File;
1129 }
1130
1131 //===----------------------------------------------------------------------===//
1132 // File Info Management.
1133 //===----------------------------------------------------------------------===//
1134
1135 /// Merge the header file info provided by \p OtherHFI into the current
1136 /// header file info (\p HFI)
1137 static void mergeHeaderFileInfo(HeaderFileInfo &HFI,
1138                                 const HeaderFileInfo &OtherHFI) {
1139   assert(OtherHFI.External && "expected to merge external HFI");
1140
1141   HFI.isImport |= OtherHFI.isImport;
1142   HFI.isPragmaOnce |= OtherHFI.isPragmaOnce;
1143   HFI.isModuleHeader |= OtherHFI.isModuleHeader;
1144   HFI.NumIncludes += OtherHFI.NumIncludes;
1145
1146   if (!HFI.ControllingMacro && !HFI.ControllingMacroID) {
1147     HFI.ControllingMacro = OtherHFI.ControllingMacro;
1148     HFI.ControllingMacroID = OtherHFI.ControllingMacroID;
1149   }
1150
1151   HFI.DirInfo = OtherHFI.DirInfo;
1152   HFI.External = (!HFI.IsValid || HFI.External);
1153   HFI.IsValid = true;
1154   HFI.IndexHeaderMapHeader = OtherHFI.IndexHeaderMapHeader;
1155
1156   if (HFI.Framework.empty())
1157     HFI.Framework = OtherHFI.Framework;
1158 }
1159
1160 /// getFileInfo - Return the HeaderFileInfo structure for the specified
1161 /// FileEntry.
1162 HeaderFileInfo &HeaderSearch::getFileInfo(const FileEntry *FE) {
1163   if (FE->getUID() >= FileInfo.size())
1164     FileInfo.resize(FE->getUID() + 1);
1165
1166   HeaderFileInfo *HFI = &FileInfo[FE->getUID()];
1167   // FIXME: Use a generation count to check whether this is really up to date.
1168   if (ExternalSource && !HFI->Resolved) {
1169     HFI->Resolved = true;
1170     auto ExternalHFI = ExternalSource->GetHeaderFileInfo(FE);
1171
1172     HFI = &FileInfo[FE->getUID()];
1173     if (ExternalHFI.External)
1174       mergeHeaderFileInfo(*HFI, ExternalHFI);
1175   }
1176
1177   HFI->IsValid = true;
1178   // We have local information about this header file, so it's no longer
1179   // strictly external.
1180   HFI->External = false;
1181   return *HFI;
1182 }
1183
1184 const HeaderFileInfo *
1185 HeaderSearch::getExistingFileInfo(const FileEntry *FE,
1186                                   bool WantExternal) const {
1187   // If we have an external source, ensure we have the latest information.
1188   // FIXME: Use a generation count to check whether this is really up to date.
1189   HeaderFileInfo *HFI;
1190   if (ExternalSource) {
1191     if (FE->getUID() >= FileInfo.size()) {
1192       if (!WantExternal)
1193         return nullptr;
1194       FileInfo.resize(FE->getUID() + 1);
1195     }
1196
1197     HFI = &FileInfo[FE->getUID()];
1198     if (!WantExternal && (!HFI->IsValid || HFI->External))
1199       return nullptr;
1200     if (!HFI->Resolved) {
1201       HFI->Resolved = true;
1202       auto ExternalHFI = ExternalSource->GetHeaderFileInfo(FE);
1203
1204       HFI = &FileInfo[FE->getUID()];
1205       if (ExternalHFI.External)
1206         mergeHeaderFileInfo(*HFI, ExternalHFI);
1207     }
1208   } else if (FE->getUID() >= FileInfo.size()) {
1209     return nullptr;
1210   } else {
1211     HFI = &FileInfo[FE->getUID()];
1212   }
1213
1214   if (!HFI->IsValid || (HFI->External && !WantExternal))
1215     return nullptr;
1216
1217   return HFI;
1218 }
1219
1220 bool HeaderSearch::isFileMultipleIncludeGuarded(const FileEntry *File) {
1221   // Check if we've ever seen this file as a header.
1222   if (auto *HFI = getExistingFileInfo(File))
1223     return HFI->isPragmaOnce || HFI->isImport || HFI->ControllingMacro ||
1224            HFI->ControllingMacroID;
1225   return false;
1226 }
1227
1228 void HeaderSearch::MarkFileModuleHeader(const FileEntry *FE,
1229                                         ModuleMap::ModuleHeaderRole Role,
1230                                         bool isCompilingModuleHeader) {
1231   bool isModularHeader = !(Role & ModuleMap::TextualHeader);
1232
1233   // Don't mark the file info as non-external if there's nothing to change.
1234   if (!isCompilingModuleHeader) {
1235     if (!isModularHeader)
1236       return;
1237     auto *HFI = getExistingFileInfo(FE);
1238     if (HFI && HFI->isModuleHeader)
1239       return;
1240   }
1241
1242   auto &HFI = getFileInfo(FE);
1243   HFI.isModuleHeader |= isModularHeader;
1244   HFI.isCompilingModuleHeader |= isCompilingModuleHeader;
1245 }
1246
1247 bool HeaderSearch::ShouldEnterIncludeFile(Preprocessor &PP,
1248                                           const FileEntry *File, bool isImport,
1249                                           bool ModulesEnabled, Module *M) {
1250   ++NumIncluded; // Count # of attempted #includes.
1251
1252   // Get information about this file.
1253   HeaderFileInfo &FileInfo = getFileInfo(File);
1254
1255   // FIXME: this is a workaround for the lack of proper modules-aware support
1256   // for #import / #pragma once
1257   auto TryEnterImported = [&]() -> bool {
1258     if (!ModulesEnabled)
1259       return false;
1260     // Ensure FileInfo bits are up to date.
1261     ModMap.resolveHeaderDirectives(File);
1262     // Modules with builtins are special; multiple modules use builtins as
1263     // modular headers, example:
1264     //
1265     //    module stddef { header "stddef.h" export * }
1266     //
1267     // After module map parsing, this expands to:
1268     //
1269     //    module stddef {
1270     //      header "/path_to_builtin_dirs/stddef.h"
1271     //      textual "stddef.h"
1272     //    }
1273     //
1274     // It's common that libc++ and system modules will both define such
1275     // submodules. Make sure cached results for a builtin header won't
1276     // prevent other builtin modules to potentially enter the builtin header.
1277     // Note that builtins are header guarded and the decision to actually
1278     // enter them is postponed to the controlling macros logic below.
1279     bool TryEnterHdr = false;
1280     if (FileInfo.isCompilingModuleHeader && FileInfo.isModuleHeader)
1281       TryEnterHdr = File->getDir() == ModMap.getBuiltinDir() &&
1282                     ModuleMap::isBuiltinHeader(
1283                         llvm::sys::path::filename(File->getName()));
1284
1285     // Textual headers can be #imported from different modules. Since ObjC
1286     // headers find in the wild might rely only on #import and do not contain
1287     // controlling macros, be conservative and only try to enter textual headers
1288     // if such macro is present.
1289     if (!FileInfo.isModuleHeader &&
1290         FileInfo.getControllingMacro(ExternalLookup))
1291       TryEnterHdr = true;
1292     return TryEnterHdr;
1293   };
1294
1295   // If this is a #import directive, check that we have not already imported
1296   // this header.
1297   if (isImport) {
1298     // If this has already been imported, don't import it again.
1299     FileInfo.isImport = true;
1300
1301     // Has this already been #import'ed or #include'd?
1302     if (FileInfo.NumIncludes && !TryEnterImported())
1303       return false;
1304   } else {
1305     // Otherwise, if this is a #include of a file that was previously #import'd
1306     // or if this is the second #include of a #pragma once file, ignore it.
1307     if (FileInfo.isImport && !TryEnterImported())
1308       return false;
1309   }
1310
1311   // Next, check to see if the file is wrapped with #ifndef guards.  If so, and
1312   // if the macro that guards it is defined, we know the #include has no effect.
1313   if (const IdentifierInfo *ControllingMacro
1314       = FileInfo.getControllingMacro(ExternalLookup)) {
1315     // If the header corresponds to a module, check whether the macro is already
1316     // defined in that module rather than checking in the current set of visible
1317     // modules.
1318     if (M ? PP.isMacroDefinedInLocalModule(ControllingMacro, M)
1319           : PP.isMacroDefined(ControllingMacro)) {
1320       ++NumMultiIncludeFileOptzn;
1321       return false;
1322     }
1323   }
1324
1325   // Increment the number of times this file has been included.
1326   ++FileInfo.NumIncludes;
1327
1328   return true;
1329 }
1330
1331 size_t HeaderSearch::getTotalMemory() const {
1332   return SearchDirs.capacity()
1333     + llvm::capacity_in_bytes(FileInfo)
1334     + llvm::capacity_in_bytes(HeaderMaps)
1335     + LookupFileCache.getAllocator().getTotalMemory()
1336     + FrameworkMap.getAllocator().getTotalMemory();
1337 }
1338
1339 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
1340   return FrameworkNames.insert(Framework).first->first();
1341 }
1342
1343 bool HeaderSearch::hasModuleMap(StringRef FileName,
1344                                 const DirectoryEntry *Root,
1345                                 bool IsSystem) {
1346   if (!HSOpts->ImplicitModuleMaps)
1347     return false;
1348
1349   SmallVector<const DirectoryEntry *, 2> FixUpDirectories;
1350
1351   StringRef DirName = FileName;
1352   do {
1353     // Get the parent directory name.
1354     DirName = llvm::sys::path::parent_path(DirName);
1355     if (DirName.empty())
1356       return false;
1357
1358     // Determine whether this directory exists.
1359     auto Dir = FileMgr.getDirectory(DirName);
1360     if (!Dir)
1361       return false;
1362
1363     // Try to load the module map file in this directory.
1364     switch (loadModuleMapFile(*Dir, IsSystem,
1365                               llvm::sys::path::extension((*Dir)->getName()) ==
1366                                   ".framework")) {
1367     case LMM_NewlyLoaded:
1368     case LMM_AlreadyLoaded:
1369       // Success. All of the directories we stepped through inherit this module
1370       // map file.
1371       for (unsigned I = 0, N = FixUpDirectories.size(); I != N; ++I)
1372         DirectoryHasModuleMap[FixUpDirectories[I]] = true;
1373       return true;
1374
1375     case LMM_NoDirectory:
1376     case LMM_InvalidModuleMap:
1377       break;
1378     }
1379
1380     // If we hit the top of our search, we're done.
1381     if (*Dir == Root)
1382       return false;
1383
1384     // Keep track of all of the directories we checked, so we can mark them as
1385     // having module maps if we eventually do find a module map.
1386     FixUpDirectories.push_back(*Dir);
1387   } while (true);
1388 }
1389
1390 ModuleMap::KnownHeader
1391 HeaderSearch::findModuleForHeader(const FileEntry *File,
1392                                   bool AllowTextual) const {
1393   if (ExternalSource) {
1394     // Make sure the external source has handled header info about this file,
1395     // which includes whether the file is part of a module.
1396     (void)getExistingFileInfo(File);
1397   }
1398   return ModMap.findModuleForHeader(File, AllowTextual);
1399 }
1400
1401 static bool suggestModule(HeaderSearch &HS, const FileEntry *File,
1402                           Module *RequestingModule,
1403                           ModuleMap::KnownHeader *SuggestedModule) {
1404   ModuleMap::KnownHeader Module =
1405       HS.findModuleForHeader(File, /*AllowTextual*/true);
1406   if (SuggestedModule)
1407     *SuggestedModule = (Module.getRole() & ModuleMap::TextualHeader)
1408                            ? ModuleMap::KnownHeader()
1409                            : Module;
1410
1411   // If this module specifies [no_undeclared_includes], we cannot find any
1412   // file that's in a non-dependency module.
1413   if (RequestingModule && Module && RequestingModule->NoUndeclaredIncludes) {
1414     HS.getModuleMap().resolveUses(RequestingModule, /*Complain*/false);
1415     if (!RequestingModule->directlyUses(Module.getModule())) {
1416       return false;
1417     }
1418   }
1419
1420   return true;
1421 }
1422
1423 bool HeaderSearch::findUsableModuleForHeader(
1424     const FileEntry *File, const DirectoryEntry *Root, Module *RequestingModule,
1425     ModuleMap::KnownHeader *SuggestedModule, bool IsSystemHeaderDir) {
1426   if (File && needModuleLookup(RequestingModule, SuggestedModule)) {
1427     // If there is a module that corresponds to this header, suggest it.
1428     hasModuleMap(File->getName(), Root, IsSystemHeaderDir);
1429     return suggestModule(*this, File, RequestingModule, SuggestedModule);
1430   }
1431   return true;
1432 }
1433
1434 bool HeaderSearch::findUsableModuleForFrameworkHeader(
1435     const FileEntry *File, StringRef FrameworkName, Module *RequestingModule,
1436     ModuleMap::KnownHeader *SuggestedModule, bool IsSystemFramework) {
1437   // If we're supposed to suggest a module, look for one now.
1438   if (needModuleLookup(RequestingModule, SuggestedModule)) {
1439     // Find the top-level framework based on this framework.
1440     SmallVector<std::string, 4> SubmodulePath;
1441     const DirectoryEntry *TopFrameworkDir
1442       = ::getTopFrameworkDir(FileMgr, FrameworkName, SubmodulePath);
1443
1444     // Determine the name of the top-level framework.
1445     StringRef ModuleName = llvm::sys::path::stem(TopFrameworkDir->getName());
1446
1447     // Load this framework module. If that succeeds, find the suggested module
1448     // for this header, if any.
1449     loadFrameworkModule(ModuleName, TopFrameworkDir, IsSystemFramework);
1450
1451     // FIXME: This can find a module not part of ModuleName, which is
1452     // important so that we're consistent about whether this header
1453     // corresponds to a module. Possibly we should lock down framework modules
1454     // so that this is not possible.
1455     return suggestModule(*this, File, RequestingModule, SuggestedModule);
1456   }
1457   return true;
1458 }
1459
1460 static const FileEntry *getPrivateModuleMap(const FileEntry *File,
1461                                             FileManager &FileMgr) {
1462   StringRef Filename = llvm::sys::path::filename(File->getName());
1463   SmallString<128>  PrivateFilename(File->getDir()->getName());
1464   if (Filename == "module.map")
1465     llvm::sys::path::append(PrivateFilename, "module_private.map");
1466   else if (Filename == "module.modulemap")
1467     llvm::sys::path::append(PrivateFilename, "module.private.modulemap");
1468   else
1469     return nullptr;
1470   if (auto File = FileMgr.getFile(PrivateFilename))
1471     return *File;
1472   return nullptr;
1473 }
1474
1475 bool HeaderSearch::loadModuleMapFile(const FileEntry *File, bool IsSystem,
1476                                      FileID ID, unsigned *Offset,
1477                                      StringRef OriginalModuleMapFile) {
1478   // Find the directory for the module. For frameworks, that may require going
1479   // up from the 'Modules' directory.
1480   const DirectoryEntry *Dir = nullptr;
1481   if (getHeaderSearchOpts().ModuleMapFileHomeIsCwd) {
1482     if (auto DirOrErr = FileMgr.getDirectory("."))
1483       Dir = *DirOrErr;
1484   } else {
1485     if (!OriginalModuleMapFile.empty()) {
1486       // We're building a preprocessed module map. Find or invent the directory
1487       // that it originally occupied.
1488       auto DirOrErr = FileMgr.getDirectory(
1489           llvm::sys::path::parent_path(OriginalModuleMapFile));
1490       if (DirOrErr) {
1491         Dir = *DirOrErr;
1492       } else {
1493         auto *FakeFile = FileMgr.getVirtualFile(OriginalModuleMapFile, 0, 0);
1494         Dir = FakeFile->getDir();
1495       }
1496     } else {
1497       Dir = File->getDir();
1498     }
1499
1500     StringRef DirName(Dir->getName());
1501     if (llvm::sys::path::filename(DirName) == "Modules") {
1502       DirName = llvm::sys::path::parent_path(DirName);
1503       if (DirName.endswith(".framework"))
1504         if (auto DirOrErr = FileMgr.getDirectory(DirName))
1505           Dir = *DirOrErr;
1506       // FIXME: This assert can fail if there's a race between the above check
1507       // and the removal of the directory.
1508       assert(Dir && "parent must exist");
1509     }
1510   }
1511
1512   switch (loadModuleMapFileImpl(File, IsSystem, Dir, ID, Offset)) {
1513   case LMM_AlreadyLoaded:
1514   case LMM_NewlyLoaded:
1515     return false;
1516   case LMM_NoDirectory:
1517   case LMM_InvalidModuleMap:
1518     return true;
1519   }
1520   llvm_unreachable("Unknown load module map result");
1521 }
1522
1523 HeaderSearch::LoadModuleMapResult
1524 HeaderSearch::loadModuleMapFileImpl(const FileEntry *File, bool IsSystem,
1525                                     const DirectoryEntry *Dir, FileID ID,
1526                                     unsigned *Offset) {
1527   assert(File && "expected FileEntry");
1528
1529   // Check whether we've already loaded this module map, and mark it as being
1530   // loaded in case we recursively try to load it from itself.
1531   auto AddResult = LoadedModuleMaps.insert(std::make_pair(File, true));
1532   if (!AddResult.second)
1533     return AddResult.first->second ? LMM_AlreadyLoaded : LMM_InvalidModuleMap;
1534
1535   if (ModMap.parseModuleMapFile(File, IsSystem, Dir, ID, Offset)) {
1536     LoadedModuleMaps[File] = false;
1537     return LMM_InvalidModuleMap;
1538   }
1539
1540   // Try to load a corresponding private module map.
1541   if (const FileEntry *PMMFile = getPrivateModuleMap(File, FileMgr)) {
1542     if (ModMap.parseModuleMapFile(PMMFile, IsSystem, Dir)) {
1543       LoadedModuleMaps[File] = false;
1544       return LMM_InvalidModuleMap;
1545     }
1546   }
1547
1548   // This directory has a module map.
1549   return LMM_NewlyLoaded;
1550 }
1551
1552 const FileEntry *
1553 HeaderSearch::lookupModuleMapFile(const DirectoryEntry *Dir, bool IsFramework) {
1554   if (!HSOpts->ImplicitModuleMaps)
1555     return nullptr;
1556   // For frameworks, the preferred spelling is Modules/module.modulemap, but
1557   // module.map at the framework root is also accepted.
1558   SmallString<128> ModuleMapFileName(Dir->getName());
1559   if (IsFramework)
1560     llvm::sys::path::append(ModuleMapFileName, "Modules");
1561   llvm::sys::path::append(ModuleMapFileName, "module.modulemap");
1562   if (auto F = FileMgr.getFile(ModuleMapFileName))
1563     return *F;
1564
1565   // Continue to allow module.map
1566   ModuleMapFileName = Dir->getName();
1567   llvm::sys::path::append(ModuleMapFileName, "module.map");
1568   if (auto F = FileMgr.getFile(ModuleMapFileName))
1569     return *F;
1570   return nullptr;
1571 }
1572
1573 Module *HeaderSearch::loadFrameworkModule(StringRef Name,
1574                                           const DirectoryEntry *Dir,
1575                                           bool IsSystem) {
1576   if (Module *Module = ModMap.findModule(Name))
1577     return Module;
1578
1579   // Try to load a module map file.
1580   switch (loadModuleMapFile(Dir, IsSystem, /*IsFramework*/true)) {
1581   case LMM_InvalidModuleMap:
1582     // Try to infer a module map from the framework directory.
1583     if (HSOpts->ImplicitModuleMaps)
1584       ModMap.inferFrameworkModule(Dir, IsSystem, /*Parent=*/nullptr);
1585     break;
1586
1587   case LMM_AlreadyLoaded:
1588   case LMM_NoDirectory:
1589     return nullptr;
1590
1591   case LMM_NewlyLoaded:
1592     break;
1593   }
1594
1595   return ModMap.findModule(Name);
1596 }
1597
1598 HeaderSearch::LoadModuleMapResult
1599 HeaderSearch::loadModuleMapFile(StringRef DirName, bool IsSystem,
1600                                 bool IsFramework) {
1601   if (auto Dir = FileMgr.getDirectory(DirName))
1602     return loadModuleMapFile(*Dir, IsSystem, IsFramework);
1603
1604   return LMM_NoDirectory;
1605 }
1606
1607 HeaderSearch::LoadModuleMapResult
1608 HeaderSearch::loadModuleMapFile(const DirectoryEntry *Dir, bool IsSystem,
1609                                 bool IsFramework) {
1610   auto KnownDir = DirectoryHasModuleMap.find(Dir);
1611   if (KnownDir != DirectoryHasModuleMap.end())
1612     return KnownDir->second ? LMM_AlreadyLoaded : LMM_InvalidModuleMap;
1613
1614   if (const FileEntry *ModuleMapFile = lookupModuleMapFile(Dir, IsFramework)) {
1615     LoadModuleMapResult Result =
1616         loadModuleMapFileImpl(ModuleMapFile, IsSystem, Dir);
1617     // Add Dir explicitly in case ModuleMapFile is in a subdirectory.
1618     // E.g. Foo.framework/Modules/module.modulemap
1619     //      ^Dir                  ^ModuleMapFile
1620     if (Result == LMM_NewlyLoaded)
1621       DirectoryHasModuleMap[Dir] = true;
1622     else if (Result == LMM_InvalidModuleMap)
1623       DirectoryHasModuleMap[Dir] = false;
1624     return Result;
1625   }
1626   return LMM_InvalidModuleMap;
1627 }
1628
1629 void HeaderSearch::collectAllModules(SmallVectorImpl<Module *> &Modules) {
1630   Modules.clear();
1631
1632   if (HSOpts->ImplicitModuleMaps) {
1633     // Load module maps for each of the header search directories.
1634     for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
1635       bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
1636       if (SearchDirs[Idx].isFramework()) {
1637         std::error_code EC;
1638         SmallString<128> DirNative;
1639         llvm::sys::path::native(SearchDirs[Idx].getFrameworkDir()->getName(),
1640                                 DirNative);
1641
1642         // Search each of the ".framework" directories to load them as modules.
1643         llvm::vfs::FileSystem &FS = FileMgr.getVirtualFileSystem();
1644         for (llvm::vfs::directory_iterator Dir = FS.dir_begin(DirNative, EC),
1645                                            DirEnd;
1646              Dir != DirEnd && !EC; Dir.increment(EC)) {
1647           if (llvm::sys::path::extension(Dir->path()) != ".framework")
1648             continue;
1649
1650           auto FrameworkDir =
1651               FileMgr.getDirectory(Dir->path());
1652           if (!FrameworkDir)
1653             continue;
1654
1655           // Load this framework module.
1656           loadFrameworkModule(llvm::sys::path::stem(Dir->path()), *FrameworkDir,
1657                               IsSystem);
1658         }
1659         continue;
1660       }
1661
1662       // FIXME: Deal with header maps.
1663       if (SearchDirs[Idx].isHeaderMap())
1664         continue;
1665
1666       // Try to load a module map file for the search directory.
1667       loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
1668                         /*IsFramework*/ false);
1669
1670       // Try to load module map files for immediate subdirectories of this
1671       // search directory.
1672       loadSubdirectoryModuleMaps(SearchDirs[Idx]);
1673     }
1674   }
1675
1676   // Populate the list of modules.
1677   for (ModuleMap::module_iterator M = ModMap.module_begin(),
1678                                MEnd = ModMap.module_end();
1679        M != MEnd; ++M) {
1680     Modules.push_back(M->getValue());
1681   }
1682 }
1683
1684 void HeaderSearch::loadTopLevelSystemModules() {
1685   if (!HSOpts->ImplicitModuleMaps)
1686     return;
1687
1688   // Load module maps for each of the header search directories.
1689   for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
1690     // We only care about normal header directories.
1691     if (!SearchDirs[Idx].isNormalDir()) {
1692       continue;
1693     }
1694
1695     // Try to load a module map file for the search directory.
1696     loadModuleMapFile(SearchDirs[Idx].getDir(),
1697                       SearchDirs[Idx].isSystemHeaderDirectory(),
1698                       SearchDirs[Idx].isFramework());
1699   }
1700 }
1701
1702 void HeaderSearch::loadSubdirectoryModuleMaps(DirectoryLookup &SearchDir) {
1703   assert(HSOpts->ImplicitModuleMaps &&
1704          "Should not be loading subdirectory module maps");
1705
1706   if (SearchDir.haveSearchedAllModuleMaps())
1707     return;
1708
1709   std::error_code EC;
1710   SmallString<128> Dir = SearchDir.getDir()->getName();
1711   FileMgr.makeAbsolutePath(Dir);
1712   SmallString<128> DirNative;
1713   llvm::sys::path::native(Dir, DirNative);
1714   llvm::vfs::FileSystem &FS = FileMgr.getVirtualFileSystem();
1715   for (llvm::vfs::directory_iterator Dir = FS.dir_begin(DirNative, EC), DirEnd;
1716        Dir != DirEnd && !EC; Dir.increment(EC)) {
1717     bool IsFramework = llvm::sys::path::extension(Dir->path()) == ".framework";
1718     if (IsFramework == SearchDir.isFramework())
1719       loadModuleMapFile(Dir->path(), SearchDir.isSystemHeaderDirectory(),
1720                         SearchDir.isFramework());
1721   }
1722
1723   SearchDir.setSearchedAllModuleMaps(true);
1724 }
1725
1726 std::string HeaderSearch::suggestPathToFileForDiagnostics(
1727     const FileEntry *File, llvm::StringRef MainFile, bool *IsSystem) {
1728   // FIXME: We assume that the path name currently cached in the FileEntry is
1729   // the most appropriate one for this analysis (and that it's spelled the
1730   // same way as the corresponding header search path).
1731   return suggestPathToFileForDiagnostics(File->getName(), /*WorkingDir=*/"",
1732                                          MainFile, IsSystem);
1733 }
1734
1735 std::string HeaderSearch::suggestPathToFileForDiagnostics(
1736     llvm::StringRef File, llvm::StringRef WorkingDir, llvm::StringRef MainFile,
1737     bool *IsSystem) {
1738   using namespace llvm::sys;
1739
1740   unsigned BestPrefixLength = 0;
1741   // Checks whether Dir and File shares a common prefix, if they do and that's
1742   // the longest prefix we've seen so for it returns true and updates the
1743   // BestPrefixLength accordingly.
1744   auto CheckDir = [&](llvm::StringRef Dir) -> bool {
1745     llvm::SmallString<32> DirPath(Dir.begin(), Dir.end());
1746     if (!WorkingDir.empty() && !path::is_absolute(Dir))
1747       fs::make_absolute(WorkingDir, DirPath);
1748     path::remove_dots(DirPath, /*remove_dot_dot=*/true);
1749     Dir = DirPath;
1750     for (auto NI = path::begin(File), NE = path::end(File),
1751               DI = path::begin(Dir), DE = path::end(Dir);
1752          /*termination condition in loop*/; ++NI, ++DI) {
1753       // '.' components in File are ignored.
1754       while (NI != NE && *NI == ".")
1755         ++NI;
1756       if (NI == NE)
1757         break;
1758
1759       // '.' components in Dir are ignored.
1760       while (DI != DE && *DI == ".")
1761         ++DI;
1762       if (DI == DE) {
1763         // Dir is a prefix of File, up to '.' components and choice of path
1764         // separators.
1765         unsigned PrefixLength = NI - path::begin(File);
1766         if (PrefixLength > BestPrefixLength) {
1767           BestPrefixLength = PrefixLength;
1768           return true;
1769         }
1770         break;
1771       }
1772
1773       // Consider all path separators equal.
1774       if (NI->size() == 1 && DI->size() == 1 &&
1775           path::is_separator(NI->front()) && path::is_separator(DI->front()))
1776         continue;
1777
1778       if (*NI != *DI)
1779         break;
1780     }
1781     return false;
1782   };
1783
1784   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
1785     // FIXME: Support this search within frameworks and header maps.
1786     if (!SearchDirs[I].isNormalDir())
1787       continue;
1788
1789     StringRef Dir = SearchDirs[I].getDir()->getName();
1790     if (CheckDir(Dir) && IsSystem)
1791       *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
1792   }
1793
1794   // Try to shorten include path using TUs directory, if we couldn't find any
1795   // suitable prefix in include search paths.
1796   if (!BestPrefixLength && CheckDir(path::parent_path(MainFile)) && IsSystem)
1797     *IsSystem = false;
1798
1799
1800   return path::convert_to_slash(File.drop_front(BestPrefixLength));
1801 }