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