contrib/llvm/tools/clang/lib/Lex/ModuleMap.cpp

   1 //===--- ModuleMap.cpp - Describe the layout of modules ---------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the ModuleMap implementation, which describes the layout
  11 // of a module as it relates to headers.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #include "clang/Lex/ModuleMap.h"
  15 #include "clang/Basic/CharInfo.h"
  16 #include "clang/Basic/Diagnostic.h"
  17 #include "clang/Basic/DiagnosticOptions.h"
  18 #include "clang/Basic/FileManager.h"
  19 #include "clang/Basic/TargetInfo.h"
  20 #include "clang/Basic/TargetOptions.h"
  21 #include "clang/Lex/HeaderSearch.h"
  22 #include "clang/Lex/HeaderSearchOptions.h"
  23 #include "clang/Lex/LexDiagnostic.h"
  24 #include "clang/Lex/Lexer.h"
  25 #include "clang/Lex/LiteralSupport.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/StringSwitch.h"
  28 #include "llvm/Support/Allocator.h"
  29 #include "llvm/Support/FileSystem.h"
  30 #include "llvm/Support/Host.h"
  31 #include "llvm/Support/Path.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include <stdlib.h>
  34 #if defined(LLVM_ON_UNIX)
  35 #include <limits.h>
  36 #endif
  37 using namespace clang;
  38
  39 Module::ExportDecl
  40 ModuleMap::resolveExport(Module *Mod,
  41                          const Module::UnresolvedExportDecl &Unresolved,
  42                          bool Complain) const {
  43   // We may have just a wildcard.
  44   if (Unresolved.Id.empty()) {
  45     assert(Unresolved.Wildcard && "Invalid unresolved export");
  46     return Module::ExportDecl(nullptr, true);
  47   }
  48
  49   // Resolve the module-id.
  50   Module *Context = resolveModuleId(Unresolved.Id, Mod, Complain);
  51   if (!Context)
  52     return Module::ExportDecl();
  53
  54   return Module::ExportDecl(Context, Unresolved.Wildcard);
  55 }
  56
  57 Module *ModuleMap::resolveModuleId(const ModuleId &Id, Module *Mod,
  58                                    bool Complain) const {
  59   // Find the starting module.
  60   Module *Context = lookupModuleUnqualified(Id[0].first, Mod);
  61   if (!Context) {
  62     if (Complain)
  63       Diags.Report(Id[0].second, diag::err_mmap_missing_module_unqualified)
  64       << Id[0].first << Mod->getFullModuleName();
  65
  66     return nullptr;
  67   }
  68
  69   // Dig into the module path.
  70   for (unsigned I = 1, N = Id.size(); I != N; ++I) {
  71     Module *Sub = lookupModuleQualified(Id[I].first, Context);
  72     if (!Sub) {
  73       if (Complain)
  74         Diags.Report(Id[I].second, diag::err_mmap_missing_module_qualified)
  75         << Id[I].first << Context->getFullModuleName()
  76         << SourceRange(Id[0].second, Id[I-1].second);
  77
  78       return nullptr;
  79     }
  80
  81     Context = Sub;
  82   }
  83
  84   return Context;
  85 }
  86
  87 ModuleMap::ModuleMap(SourceManager &SourceMgr, DiagnosticsEngine &Diags,
  88                      const LangOptions &LangOpts, const TargetInfo *Target,
  89                      HeaderSearch &HeaderInfo)
  90     : SourceMgr(SourceMgr), Diags(Diags), LangOpts(LangOpts), Target(Target),
  91       HeaderInfo(HeaderInfo), BuiltinIncludeDir(nullptr),
  92       CompilingModule(nullptr), SourceModule(nullptr), NumCreatedModules(0) {
  93   MMapLangOpts.LineComment = true;
  94 }
  95
  96 ModuleMap::~ModuleMap() {
  97   for (llvm::StringMap<Module *>::iterator I = Modules.begin(),
  98                                         IEnd = Modules.end();
  99        I != IEnd; ++I) {
 100     delete I->getValue();
 101   }
 102 }
 103
 104 void ModuleMap::setTarget(const TargetInfo &Target) {
 105   assert((!this->Target || this->Target == &Target) &&
 106          "Improper target override");
 107   this->Target = &Target;
 108 }
 109
 110 /// \brief "Sanitize" a filename so that it can be used as an identifier.
 111 static StringRef sanitizeFilenameAsIdentifier(StringRef Name,
 112                                               SmallVectorImpl<char> &Buffer) {
 113   if (Name.empty())
 114     return Name;
 115
 116   if (!isValidIdentifier(Name)) {
 117     // If we don't already have something with the form of an identifier,
 118     // create a buffer with the sanitized name.
 119     Buffer.clear();
 120     if (isDigit(Name[0]))
 121       Buffer.push_back('_');
 122     Buffer.reserve(Buffer.size() + Name.size());
 123     for (unsigned I = 0, N = Name.size(); I != N; ++I) {
 124       if (isIdentifierBody(Name[I]))
 125         Buffer.push_back(Name[I]);
 126       else
 127         Buffer.push_back('_');
 128     }
 129
 130     Name = StringRef(Buffer.data(), Buffer.size());
 131   }
 132
 133   while (llvm::StringSwitch<bool>(Name)
 134 #define KEYWORD(Keyword,Conditions) .Case(#Keyword, true)
 135 #define ALIAS(Keyword, AliasOf, Conditions) .Case(Keyword, true)
 136 #include "clang/Basic/TokenKinds.def"
 137            .Default(false)) {
 138     if (Name.data() != Buffer.data())
 139       Buffer.append(Name.begin(), Name.end());
 140     Buffer.push_back('_');
 141     Name = StringRef(Buffer.data(), Buffer.size());
 142   }
 143
 144   return Name;
 145 }
 146
 147 /// \brief Determine whether the given file name is the name of a builtin
 148 /// header, supplied by Clang to replace, override, or augment existing system
 149 /// headers.
 150 static bool isBuiltinHeader(StringRef FileName) {
 151   return llvm::StringSwitch<bool>(FileName)
 152            .Case("float.h", true)
 153            .Case("iso646.h", true)
 154            .Case("limits.h", true)
 155            .Case("stdalign.h", true)
 156            .Case("stdarg.h", true)
 157            .Case("stdbool.h", true)
 158            .Case("stddef.h", true)
 159            .Case("stdint.h", true)
 160            .Case("tgmath.h", true)
 161            .Case("unwind.h", true)
 162            .Default(false);
 163 }
 164
 165 ModuleMap::HeadersMap::iterator
 166 ModuleMap::findKnownHeader(const FileEntry *File) {
 167   HeadersMap::iterator Known = Headers.find(File);
 168   if (HeaderInfo.getHeaderSearchOpts().ImplicitModuleMaps &&
 169       Known == Headers.end() && File->getDir() == BuiltinIncludeDir &&
 170       isBuiltinHeader(llvm::sys::path::filename(File->getName()))) {
 171     HeaderInfo.loadTopLevelSystemModules();
 172     return Headers.find(File);
 173   }
 174   return Known;
 175 }
 176
 177 ModuleMap::KnownHeader
 178 ModuleMap::findHeaderInUmbrellaDirs(const FileEntry *File,
 179                     SmallVectorImpl<const DirectoryEntry *> &IntermediateDirs) {
 180   if (UmbrellaDirs.empty())
 181     return KnownHeader();
 182
 183   const DirectoryEntry *Dir = File->getDir();
 184   assert(Dir && "file in no directory");
 185
 186   // Note: as an egregious but useful hack we use the real path here, because
 187   // frameworks moving from top-level frameworks to embedded frameworks tend
 188   // to be symlinked from the top-level location to the embedded location,
 189   // and we need to resolve lookups as if we had found the embedded location.
 190   StringRef DirName = SourceMgr.getFileManager().getCanonicalName(Dir);
 191
 192   // Keep walking up the directory hierarchy, looking for a directory with
 193   // an umbrella header.
 194   do {
 195     auto KnownDir = UmbrellaDirs.find(Dir);
 196     if (KnownDir != UmbrellaDirs.end())
 197       return KnownHeader(KnownDir->second, NormalHeader);
 198
 199     IntermediateDirs.push_back(Dir);
 200
 201     // Retrieve our parent path.
 202     DirName = llvm::sys::path::parent_path(DirName);
 203     if (DirName.empty())
 204       break;
 205
 206     // Resolve the parent path to a directory entry.
 207     Dir = SourceMgr.getFileManager().getDirectory(DirName);
 208   } while (Dir);
 209   return KnownHeader();
 210 }
 211
 212 static bool violatesPrivateInclude(Module *RequestingModule,
 213                                    const FileEntry *IncFileEnt,
 214                                    ModuleMap::ModuleHeaderRole Role,
 215                                    Module *RequestedModule) {
 216   bool IsPrivateRole = Role & ModuleMap::PrivateHeader;
 217 #ifndef NDEBUG
 218   if (IsPrivateRole) {
 219     // Check for consistency between the module header role
 220     // as obtained from the lookup and as obtained from the module.
 221     // This check is not cheap, so enable it only for debugging.
 222     bool IsPrivate = false;
 223     SmallVectorImpl<Module::Header> *HeaderList[] = {
 224         &RequestedModule->Headers[Module::HK_Private],
 225         &RequestedModule->Headers[Module::HK_PrivateTextual]};
 226     for (auto *Hs : HeaderList)
 227       IsPrivate |=
 228           std::find_if(Hs->begin(), Hs->end(), [&](const Module::Header &H) {
 229             return H.Entry == IncFileEnt;
 230           }) != Hs->end();
 231     assert((!IsPrivateRole || IsPrivate) && "inconsistent headers and roles");
 232   }
 233 #endif
 234   return IsPrivateRole && (!RequestingModule ||
 235                            RequestedModule->getTopLevelModule() !=
 236                                RequestingModule->getTopLevelModule());
 237 }
 238
 239 static Module *getTopLevelOrNull(Module *M) {
 240   return M ? M->getTopLevelModule() : nullptr;
 241 }
 242
 243 void ModuleMap::diagnoseHeaderInclusion(Module *RequestingModule,
 244                                         SourceLocation FilenameLoc,
 245                                         StringRef Filename,
 246                                         const FileEntry *File) {
 247   // No errors for indirect modules. This may be a bit of a problem for modules
 248   // with no source files.
 249   if (getTopLevelOrNull(RequestingModule) != getTopLevelOrNull(SourceModule))
 250     return;
 251
 252   if (RequestingModule)
 253     resolveUses(RequestingModule, /*Complain=*/false);
 254
 255   bool Excluded = false;
 256   Module *Private = nullptr;
 257   Module *NotUsed = nullptr;
 258
 259   HeadersMap::iterator Known = findKnownHeader(File);
 260   if (Known != Headers.end()) {
 261     for (const KnownHeader &Header : Known->second) {
 262       // Remember private headers for later printing of a diagnostic.
 263       if (violatesPrivateInclude(RequestingModule, File, Header.getRole(),
 264                                  Header.getModule())) {
 265         Private = Header.getModule();
 266         continue;
 267       }
 268
 269       // If uses need to be specified explicitly, we are only allowed to return
 270       // modules that are explicitly used by the requesting module.
 271       if (RequestingModule && LangOpts.ModulesDeclUse &&
 272           !RequestingModule->directlyUses(Header.getModule())) {
 273         NotUsed = Header.getModule();
 274         continue;
 275       }
 276
 277       // We have found a module that we can happily use.
 278       return;
 279     }
 280
 281     Excluded = true;
 282   }
 283
 284   // We have found a header, but it is private.
 285   if (Private) {
 286     Diags.Report(FilenameLoc, diag::warn_use_of_private_header_outside_module)
 287         << Filename;
 288     return;
 289   }
 290
 291   // We have found a module, but we don't use it.
 292   if (NotUsed) {
 293     Diags.Report(FilenameLoc, diag::err_undeclared_use_of_module)
 294         << RequestingModule->getFullModuleName() << Filename;
 295     return;
 296   }
 297
 298   if (Excluded || isHeaderInUmbrellaDirs(File))
 299     return;
 300
 301   // At this point, only non-modular includes remain.
 302
 303   if (LangOpts.ModulesStrictDeclUse) {
 304     Diags.Report(FilenameLoc, diag::err_undeclared_use_of_module)
 305         << RequestingModule->getFullModuleName() << Filename;
 306   } else if (RequestingModule) {
 307     diag::kind DiagID = RequestingModule->getTopLevelModule()->IsFramework ?
 308         diag::warn_non_modular_include_in_framework_module :
 309         diag::warn_non_modular_include_in_module;
 310     Diags.Report(FilenameLoc, DiagID) << RequestingModule->getFullModuleName();
 311   }
 312 }
 313
 314 static bool isBetterKnownHeader(const ModuleMap::KnownHeader &New,
 315                                 const ModuleMap::KnownHeader &Old) {
 316   // Prefer available modules.
 317   if (New.getModule()->isAvailable() && !Old.getModule()->isAvailable())
 318     return true;
 319
 320   // Prefer a public header over a private header.
 321   if ((New.getRole() & ModuleMap::PrivateHeader) !=
 322       (Old.getRole() & ModuleMap::PrivateHeader))
 323     return !(New.getRole() & ModuleMap::PrivateHeader);
 324
 325   // Prefer a non-textual header over a textual header.
 326   if ((New.getRole() & ModuleMap::TextualHeader) !=
 327       (Old.getRole() & ModuleMap::TextualHeader))
 328     return !(New.getRole() & ModuleMap::TextualHeader);
 329
 330   // Don't have a reason to choose between these. Just keep the first one.
 331   return false;
 332 }
 333
 334 ModuleMap::KnownHeader ModuleMap::findModuleForHeader(const FileEntry *File) {
 335   auto MakeResult = [&](ModuleMap::KnownHeader R) -> ModuleMap::KnownHeader {
 336     if (R.getRole() & ModuleMap::TextualHeader)
 337       return ModuleMap::KnownHeader();
 338     return R;
 339   };
 340
 341   HeadersMap::iterator Known = findKnownHeader(File);
 342   if (Known != Headers.end()) {
 343     ModuleMap::KnownHeader Result;
 344     // Iterate over all modules that 'File' is part of to find the best fit.
 345     for (KnownHeader &H : Known->second) {
 346       // Prefer a header from the current module over all others.
 347       if (H.getModule()->getTopLevelModule() == CompilingModule)
 348         return MakeResult(H);
 349       if (!Result || isBetterKnownHeader(H, Result))
 350         Result = H;
 351     }
 352     return MakeResult(Result);
 353   }
 354
 355   return MakeResult(findOrCreateModuleForHeaderInUmbrellaDir(File));
 356 }
 357
 358 ModuleMap::KnownHeader
 359 ModuleMap::findOrCreateModuleForHeaderInUmbrellaDir(const FileEntry *File) {
 360   assert(!Headers.count(File) && "already have a module for this header");
 361
 362   SmallVector<const DirectoryEntry *, 2> SkippedDirs;
 363   KnownHeader H = findHeaderInUmbrellaDirs(File, SkippedDirs);
 364   if (H) {
 365     Module *Result = H.getModule();
 366
 367     // Search up the module stack until we find a module with an umbrella
 368     // directory.
 369     Module *UmbrellaModule = Result;
 370     while (!UmbrellaModule->getUmbrellaDir() && UmbrellaModule->Parent)
 371       UmbrellaModule = UmbrellaModule->Parent;
 372
 373     if (UmbrellaModule->InferSubmodules) {
 374       const FileEntry *UmbrellaModuleMap =
 375           getModuleMapFileForUniquing(UmbrellaModule);
 376
 377       // Infer submodules for each of the directories we found between
 378       // the directory of the umbrella header and the directory where
 379       // the actual header is located.
 380       bool Explicit = UmbrellaModule->InferExplicitSubmodules;
 381
 382       for (unsigned I = SkippedDirs.size(); I != 0; --I) {
 383         // Find or create the module that corresponds to this directory name.
 384         SmallString<32> NameBuf;
 385         StringRef Name = sanitizeFilenameAsIdentifier(
 386             llvm::sys::path::stem(SkippedDirs[I-1]->getName()), NameBuf);
 387         Result = findOrCreateModule(Name, Result, /*IsFramework=*/false,
 388                                     Explicit).first;
 389         InferredModuleAllowedBy[Result] = UmbrellaModuleMap;
 390         Result->IsInferred = true;
 391
 392         // Associate the module and the directory.
 393         UmbrellaDirs[SkippedDirs[I-1]] = Result;
 394
 395         // If inferred submodules export everything they import, add a
 396         // wildcard to the set of exports.
 397         if (UmbrellaModule->InferExportWildcard && Result->Exports.empty())
 398           Result->Exports.push_back(Module::ExportDecl(nullptr, true));
 399       }
 400
 401       // Infer a submodule with the same name as this header file.
 402       SmallString<32> NameBuf;
 403       StringRef Name = sanitizeFilenameAsIdentifier(
 404                          llvm::sys::path::stem(File->getName()), NameBuf);
 405       Result = findOrCreateModule(Name, Result, /*IsFramework=*/false,
 406                                   Explicit).first;
 407       InferredModuleAllowedBy[Result] = UmbrellaModuleMap;
 408       Result->IsInferred = true;
 409       Result->addTopHeader(File);
 410
 411       // If inferred submodules export everything they import, add a
 412       // wildcard to the set of exports.
 413       if (UmbrellaModule->InferExportWildcard && Result->Exports.empty())
 414         Result->Exports.push_back(Module::ExportDecl(nullptr, true));
 415     } else {
 416       // Record each of the directories we stepped through as being part of
 417       // the module we found, since the umbrella header covers them all.
 418       for (unsigned I = 0, N = SkippedDirs.size(); I != N; ++I)
 419         UmbrellaDirs[SkippedDirs[I]] = Result;
 420     }
 421
 422     KnownHeader Header(Result, NormalHeader);
 423     Headers[File].push_back(Header);
 424     return Header;
 425   }
 426
 427   return KnownHeader();
 428 }
 429
 430 ArrayRef<ModuleMap::KnownHeader>
 431 ModuleMap::findAllModulesForHeader(const FileEntry *File) const {
 432   auto It = Headers.find(File);
 433   if (It == Headers.end())
 434     return None;
 435   return It->second;
 436 }
 437
 438 bool ModuleMap::isHeaderInUnavailableModule(const FileEntry *Header) const {
 439   return isHeaderUnavailableInModule(Header, nullptr);
 440 }
 441
 442 bool
 443 ModuleMap::isHeaderUnavailableInModule(const FileEntry *Header,
 444                                        const Module *RequestingModule) const {
 445   HeadersMap::const_iterator Known = Headers.find(Header);
 446   if (Known != Headers.end()) {
 447     for (SmallVectorImpl<KnownHeader>::const_iterator
 448              I = Known->second.begin(),
 449              E = Known->second.end();
 450          I != E; ++I) {
 451       if (I->isAvailable() && (!RequestingModule ||
 452                                I->getModule()->isSubModuleOf(RequestingModule)))
 453         return false;
 454     }
 455     return true;
 456   }
 457
 458   const DirectoryEntry *Dir = Header->getDir();
 459   SmallVector<const DirectoryEntry *, 2> SkippedDirs;
 460   StringRef DirName = Dir->getName();
 461
 462   auto IsUnavailable = [&](const Module *M) {
 463     return !M->isAvailable() && (!RequestingModule ||
 464                                  M->isSubModuleOf(RequestingModule));
 465   };
 466
 467   // Keep walking up the directory hierarchy, looking for a directory with
 468   // an umbrella header.
 469   do {
 470     llvm::DenseMap<const DirectoryEntry *, Module *>::const_iterator KnownDir
 471       = UmbrellaDirs.find(Dir);
 472     if (KnownDir != UmbrellaDirs.end()) {
 473       Module *Found = KnownDir->second;
 474       if (IsUnavailable(Found))
 475         return true;
 476
 477       // Search up the module stack until we find a module with an umbrella
 478       // directory.
 479       Module *UmbrellaModule = Found;
 480       while (!UmbrellaModule->getUmbrellaDir() && UmbrellaModule->Parent)
 481         UmbrellaModule = UmbrellaModule->Parent;
 482
 483       if (UmbrellaModule->InferSubmodules) {
 484         for (unsigned I = SkippedDirs.size(); I != 0; --I) {
 485           // Find or create the module that corresponds to this directory name.
 486           SmallString<32> NameBuf;
 487           StringRef Name = sanitizeFilenameAsIdentifier(
 488                              llvm::sys::path::stem(SkippedDirs[I-1]->getName()),
 489                              NameBuf);
 490           Found = lookupModuleQualified(Name, Found);
 491           if (!Found)
 492             return false;
 493           if (IsUnavailable(Found))
 494             return true;
 495         }
 496
 497         // Infer a submodule with the same name as this header file.
 498         SmallString<32> NameBuf;
 499         StringRef Name = sanitizeFilenameAsIdentifier(
 500                            llvm::sys::path::stem(Header->getName()),
 501                            NameBuf);
 502         Found = lookupModuleQualified(Name, Found);
 503         if (!Found)
 504           return false;
 505       }
 506
 507       return IsUnavailable(Found);
 508     }
 509
 510     SkippedDirs.push_back(Dir);
 511
 512     // Retrieve our parent path.
 513     DirName = llvm::sys::path::parent_path(DirName);
 514     if (DirName.empty())
 515       break;
 516
 517     // Resolve the parent path to a directory entry.
 518     Dir = SourceMgr.getFileManager().getDirectory(DirName);
 519   } while (Dir);
 520
 521   return false;
 522 }
 523
 524 Module *ModuleMap::findModule(StringRef Name) const {
 525   llvm::StringMap<Module *>::const_iterator Known = Modules.find(Name);
 526   if (Known != Modules.end())
 527     return Known->getValue();
 528
 529   return nullptr;
 530 }
 531
 532 Module *ModuleMap::lookupModuleUnqualified(StringRef Name,
 533                                            Module *Context) const {
 534   for(; Context; Context = Context->Parent) {
 535     if (Module *Sub = lookupModuleQualified(Name, Context))
 536       return Sub;
 537   }
 538
 539   return findModule(Name);
 540 }
 541
 542 Module *ModuleMap::lookupModuleQualified(StringRef Name, Module *Context) const{
 543   if (!Context)
 544     return findModule(Name);
 545
 546   return Context->findSubmodule(Name);
 547 }
 548
 549 std::pair<Module *, bool>
 550 ModuleMap::findOrCreateModule(StringRef Name, Module *Parent, bool IsFramework,
 551                               bool IsExplicit) {
 552   // Try to find an existing module with this name.
 553   if (Module *Sub = lookupModuleQualified(Name, Parent))
 554     return std::make_pair(Sub, false);
 555
 556   // Create a new module with this name.
 557   Module *Result = new Module(Name, SourceLocation(), Parent,
 558                               IsFramework, IsExplicit, NumCreatedModules++);
 559   if (LangOpts.CurrentModule == Name) {
 560     SourceModule = Result;
 561     SourceModuleName = Name;
 562   }
 563   if (!Parent) {
 564     Modules[Name] = Result;
 565     if (!LangOpts.CurrentModule.empty() && !CompilingModule &&
 566         Name == LangOpts.CurrentModule) {
 567       CompilingModule = Result;
 568     }
 569   }
 570   return std::make_pair(Result, true);
 571 }
 572
 573 /// \brief For a framework module, infer the framework against which we
 574 /// should link.
 575 static void inferFrameworkLink(Module *Mod, const DirectoryEntry *FrameworkDir,
 576                                FileManager &FileMgr) {
 577   assert(Mod->IsFramework && "Can only infer linking for framework modules");
 578   assert(!Mod->isSubFramework() &&
 579          "Can only infer linking for top-level frameworks");
 580
 581   SmallString<128> LibName;
 582   LibName += FrameworkDir->getName();
 583   llvm::sys::path::append(LibName, Mod->Name);
 584
 585   // The library name of a framework has more than one possible extension since
 586   // the introduction of the text-based dynamic library format. We need to check
 587   // for both before we give up.
 588   static const char *frameworkExtensions[] = {"", ".tbd"};
 589   for (const auto *extension : frameworkExtensions) {
 590     llvm::sys::path::replace_extension(LibName, extension);
 591     if (FileMgr.getFile(LibName)) {
 592       Mod->LinkLibraries.push_back(Module::LinkLibrary(Mod->Name,
 593                                                        /*IsFramework=*/true));
 594       return;
 595     }
 596   }
 597 }
 598
 599 Module *ModuleMap::inferFrameworkModule(const DirectoryEntry *FrameworkDir,
 600                                         bool IsSystem, Module *Parent) {
 601   Attributes Attrs;
 602   Attrs.IsSystem = IsSystem;
 603   return inferFrameworkModule(FrameworkDir, Attrs, Parent);
 604 }
 605
 606 Module *ModuleMap::inferFrameworkModule(const DirectoryEntry *FrameworkDir,
 607                                         Attributes Attrs, Module *Parent) {
 608   // Note: as an egregious but useful hack we use the real path here, because
 609   // we might be looking at an embedded framework that symlinks out to a
 610   // top-level framework, and we need to infer as if we were naming the
 611   // top-level framework.
 612   StringRef FrameworkDirName =
 613       SourceMgr.getFileManager().getCanonicalName(FrameworkDir);
 614
 615   // In case this is a case-insensitive filesystem, use the canonical
 616   // directory name as the ModuleName, since modules are case-sensitive.
 617   // FIXME: we should be able to give a fix-it hint for the correct spelling.
 618   SmallString<32> ModuleNameStorage;
 619   StringRef ModuleName = sanitizeFilenameAsIdentifier(
 620       llvm::sys::path::stem(FrameworkDirName), ModuleNameStorage);
 621
 622   // Check whether we've already found this module.
 623   if (Module *Mod = lookupModuleQualified(ModuleName, Parent))
 624     return Mod;
 625
 626   FileManager &FileMgr = SourceMgr.getFileManager();
 627
 628   // If the framework has a parent path from which we're allowed to infer
 629   // a framework module, do so.
 630   const FileEntry *ModuleMapFile = nullptr;
 631   if (!Parent) {
 632     // Determine whether we're allowed to infer a module map.
 633     bool canInfer = false;
 634     if (llvm::sys::path::has_parent_path(FrameworkDirName)) {
 635       // Figure out the parent path.
 636       StringRef Parent = llvm::sys::path::parent_path(FrameworkDirName);
 637       if (const DirectoryEntry *ParentDir = FileMgr.getDirectory(Parent)) {
 638         // Check whether we have already looked into the parent directory
 639         // for a module map.
 640         llvm::DenseMap<const DirectoryEntry *, InferredDirectory>::const_iterator
 641           inferred = InferredDirectories.find(ParentDir);
 642         if (inferred == InferredDirectories.end()) {
 643           // We haven't looked here before. Load a module map, if there is
 644           // one.
 645           bool IsFrameworkDir = Parent.endswith(".framework");
 646           if (const FileEntry *ModMapFile =
 647                 HeaderInfo.lookupModuleMapFile(ParentDir, IsFrameworkDir)) {
 648             parseModuleMapFile(ModMapFile, Attrs.IsSystem, ParentDir);
 649             inferred = InferredDirectories.find(ParentDir);
 650           }
 651
 652           if (inferred == InferredDirectories.end())
 653             inferred = InferredDirectories.insert(
 654                          std::make_pair(ParentDir, InferredDirectory())).first;
 655         }
 656
 657         if (inferred->second.InferModules) {
 658           // We're allowed to infer for this directory, but make sure it's okay
 659           // to infer this particular module.
 660           StringRef Name = llvm::sys::path::stem(FrameworkDirName);
 661           canInfer = std::find(inferred->second.ExcludedModules.begin(),
 662                                inferred->second.ExcludedModules.end(),
 663                                Name) == inferred->second.ExcludedModules.end();
 664
 665           Attrs.IsSystem |= inferred->second.Attrs.IsSystem;
 666           Attrs.IsExternC |= inferred->second.Attrs.IsExternC;
 667           Attrs.IsExhaustive |= inferred->second.Attrs.IsExhaustive;
 668           ModuleMapFile = inferred->second.ModuleMapFile;
 669         }
 670       }
 671     }
 672
 673     // If we're not allowed to infer a framework module, don't.
 674     if (!canInfer)
 675       return nullptr;
 676   } else
 677     ModuleMapFile = getModuleMapFileForUniquing(Parent);
 678
 679
 680   // Look for an umbrella header.
 681   SmallString<128> UmbrellaName = StringRef(FrameworkDir->getName());
 682   llvm::sys::path::append(UmbrellaName, "Headers", ModuleName + ".h");
 683   const FileEntry *UmbrellaHeader = FileMgr.getFile(UmbrellaName);
 684
 685   // FIXME: If there's no umbrella header, we could probably scan the
 686   // framework to load *everything*. But, it's not clear that this is a good
 687   // idea.
 688   if (!UmbrellaHeader)
 689     return nullptr;
 690
 691   Module *Result = new Module(ModuleName, SourceLocation(), Parent,
 692                               /*IsFramework=*/true, /*IsExplicit=*/false,
 693                               NumCreatedModules++);
 694   InferredModuleAllowedBy[Result] = ModuleMapFile;
 695   Result->IsInferred = true;
 696   if (LangOpts.CurrentModule == ModuleName) {
 697     SourceModule = Result;
 698     SourceModuleName = ModuleName;
 699   }
 700
 701   Result->IsSystem |= Attrs.IsSystem;
 702   Result->IsExternC |= Attrs.IsExternC;
 703   Result->ConfigMacrosExhaustive |= Attrs.IsExhaustive;
 704   Result->Directory = FrameworkDir;
 705
 706   if (!Parent)
 707     Modules[ModuleName] = Result;
 708
 709   // umbrella header "umbrella-header-name"
 710   //
 711   // The "Headers/" component of the name is implied because this is
 712   // a framework module.
 713   setUmbrellaHeader(Result, UmbrellaHeader, ModuleName + ".h");
 714
 715   // export *
 716   Result->Exports.push_back(Module::ExportDecl(nullptr, true));
 717
 718   // module * { export * }
 719   Result->InferSubmodules = true;
 720   Result->InferExportWildcard = true;
 721
 722   // Look for subframeworks.
 723   std::error_code EC;
 724   SmallString<128> SubframeworksDirName
 725     = StringRef(FrameworkDir->getName());
 726   llvm::sys::path::append(SubframeworksDirName, "Frameworks");
 727   llvm::sys::path::native(SubframeworksDirName);
 728   for (llvm::sys::fs::directory_iterator Dir(SubframeworksDirName, EC), DirEnd;
 729        Dir != DirEnd && !EC; Dir.increment(EC)) {
 730     if (!StringRef(Dir->path()).endswith(".framework"))
 731       continue;
 732
 733     if (const DirectoryEntry *SubframeworkDir
 734           = FileMgr.getDirectory(Dir->path())) {
 735       // Note: as an egregious but useful hack, we use the real path here and
 736       // check whether it is actually a subdirectory of the parent directory.
 737       // This will not be the case if the 'subframework' is actually a symlink
 738       // out to a top-level framework.
 739       StringRef SubframeworkDirName = FileMgr.getCanonicalName(SubframeworkDir);
 740       bool FoundParent = false;
 741       do {
 742         // Get the parent directory name.
 743         SubframeworkDirName
 744           = llvm::sys::path::parent_path(SubframeworkDirName);
 745         if (SubframeworkDirName.empty())
 746           break;
 747
 748         if (FileMgr.getDirectory(SubframeworkDirName) == FrameworkDir) {
 749           FoundParent = true;
 750           break;
 751         }
 752       } while (true);
 753
 754       if (!FoundParent)
 755         continue;
 756
 757       // FIXME: Do we want to warn about subframeworks without umbrella headers?
 758       inferFrameworkModule(SubframeworkDir, Attrs, Result);
 759     }
 760   }
 761
 762   // If the module is a top-level framework, automatically link against the
 763   // framework.
 764   if (!Result->isSubFramework()) {
 765     inferFrameworkLink(Result, FrameworkDir, FileMgr);
 766   }
 767
 768   return Result;
 769 }
 770
 771 void ModuleMap::setUmbrellaHeader(Module *Mod, const FileEntry *UmbrellaHeader,
 772                                   Twine NameAsWritten) {
 773   Headers[UmbrellaHeader].push_back(KnownHeader(Mod, NormalHeader));
 774   Mod->Umbrella = UmbrellaHeader;
 775   Mod->UmbrellaAsWritten = NameAsWritten.str();
 776   UmbrellaDirs[UmbrellaHeader->getDir()] = Mod;
 777 }
 778
 779 void ModuleMap::setUmbrellaDir(Module *Mod, const DirectoryEntry *UmbrellaDir,
 780                                Twine NameAsWritten) {
 781   Mod->Umbrella = UmbrellaDir;
 782   Mod->UmbrellaAsWritten = NameAsWritten.str();
 783   UmbrellaDirs[UmbrellaDir] = Mod;
 784 }
 785
 786 static Module::HeaderKind headerRoleToKind(ModuleMap::ModuleHeaderRole Role) {
 787   switch ((int)Role) {
 788   default: llvm_unreachable("unknown header role");
 789   case ModuleMap::NormalHeader:
 790     return Module::HK_Normal;
 791   case ModuleMap::PrivateHeader:
 792     return Module::HK_Private;
 793   case ModuleMap::TextualHeader:
 794     return Module::HK_Textual;
 795   case ModuleMap::PrivateHeader | ModuleMap::TextualHeader:
 796     return Module::HK_PrivateTextual;
 797   }
 798 }
 799
 800 void ModuleMap::addHeader(Module *Mod, Module::Header Header,
 801                           ModuleHeaderRole Role, bool Imported) {
 802   KnownHeader KH(Mod, Role);
 803
 804   // Only add each header to the headers list once.
 805   // FIXME: Should we diagnose if a header is listed twice in the
 806   // same module definition?
 807   auto &HeaderList = Headers[Header.Entry];
 808   for (auto H : HeaderList)
 809     if (H == KH)
 810       return;
 811
 812   HeaderList.push_back(KH);
 813   Mod->Headers[headerRoleToKind(Role)].push_back(std::move(Header));
 814
 815   bool isCompilingModuleHeader = Mod->getTopLevelModule() == CompilingModule;
 816   if (!Imported || isCompilingModuleHeader) {
 817     // When we import HeaderFileInfo, the external source is expected to
 818     // set the isModuleHeader flag itself.
 819     HeaderInfo.MarkFileModuleHeader(Header.Entry, Role,
 820                                     isCompilingModuleHeader);
 821   }
 822 }
 823
 824 void ModuleMap::excludeHeader(Module *Mod, Module::Header Header) {
 825   // Add this as a known header so we won't implicitly add it to any
 826   // umbrella directory module.
 827   // FIXME: Should we only exclude it from umbrella modules within the
 828   // specified module?
 829   (void) Headers[Header.Entry];
 830
 831   Mod->Headers[Module::HK_Excluded].push_back(std::move(Header));
 832 }
 833
 834 const FileEntry *
 835 ModuleMap::getContainingModuleMapFile(const Module *Module) const {
 836   if (Module->DefinitionLoc.isInvalid())
 837     return nullptr;
 838
 839   return SourceMgr.getFileEntryForID(
 840            SourceMgr.getFileID(Module->DefinitionLoc));
 841 }
 842
 843 const FileEntry *ModuleMap::getModuleMapFileForUniquing(const Module *M) const {
 844   if (M->IsInferred) {
 845     assert(InferredModuleAllowedBy.count(M) && "missing inferred module map");
 846     return InferredModuleAllowedBy.find(M)->second;
 847   }
 848   return getContainingModuleMapFile(M);
 849 }
 850
 851 void ModuleMap::setInferredModuleAllowedBy(Module *M, const FileEntry *ModMap) {
 852   assert(M->IsInferred && "module not inferred");
 853   InferredModuleAllowedBy[M] = ModMap;
 854 }
 855
 856 void ModuleMap::dump() {
 857   llvm::errs() << "Modules:";
 858   for (llvm::StringMap<Module *>::iterator M = Modules.begin(),
 859                                         MEnd = Modules.end();
 860        M != MEnd; ++M)
 861     M->getValue()->print(llvm::errs(), 2);
 862
 863   llvm::errs() << "Headers:";
 864   for (HeadersMap::iterator H = Headers.begin(), HEnd = Headers.end();
 865        H != HEnd; ++H) {
 866     llvm::errs() << "  \"" << H->first->getName() << "\" -> ";
 867     for (SmallVectorImpl<KnownHeader>::const_iterator I = H->second.begin(),
 868                                                       E = H->second.end();
 869          I != E; ++I) {
 870       if (I != H->second.begin())
 871         llvm::errs() << ",";
 872       llvm::errs() << I->getModule()->getFullModuleName();
 873     }
 874     llvm::errs() << "\n";
 875   }
 876 }
 877
 878 bool ModuleMap::resolveExports(Module *Mod, bool Complain) {
 879   auto Unresolved = std::move(Mod->UnresolvedExports);
 880   Mod->UnresolvedExports.clear();
 881   for (auto &UE : Unresolved) {
 882     Module::ExportDecl Export = resolveExport(Mod, UE, Complain);
 883     if (Export.getPointer() || Export.getInt())
 884       Mod->Exports.push_back(Export);
 885     else
 886       Mod->UnresolvedExports.push_back(UE);
 887   }
 888   return !Mod->UnresolvedExports.empty();
 889 }
 890
 891 bool ModuleMap::resolveUses(Module *Mod, bool Complain) {
 892   auto Unresolved = std::move(Mod->UnresolvedDirectUses);
 893   Mod->UnresolvedDirectUses.clear();
 894   for (auto &UDU : Unresolved) {
 895     Module *DirectUse = resolveModuleId(UDU, Mod, Complain);
 896     if (DirectUse)
 897       Mod->DirectUses.push_back(DirectUse);
 898     else
 899       Mod->UnresolvedDirectUses.push_back(UDU);
 900   }
 901   return !Mod->UnresolvedDirectUses.empty();
 902 }
 903
 904 bool ModuleMap::resolveConflicts(Module *Mod, bool Complain) {
 905   auto Unresolved = std::move(Mod->UnresolvedConflicts);
 906   Mod->UnresolvedConflicts.clear();
 907   for (auto &UC : Unresolved) {
 908     if (Module *OtherMod = resolveModuleId(UC.Id, Mod, Complain)) {
 909       Module::Conflict Conflict;
 910       Conflict.Other = OtherMod;
 911       Conflict.Message = UC.Message;
 912       Mod->Conflicts.push_back(Conflict);
 913     } else
 914       Mod->UnresolvedConflicts.push_back(UC);
 915   }
 916   return !Mod->UnresolvedConflicts.empty();
 917 }
 918
 919 Module *ModuleMap::inferModuleFromLocation(FullSourceLoc Loc) {
 920   if (Loc.isInvalid())
 921     return nullptr;
 922
 923   // Use the expansion location to determine which module we're in.
 924   FullSourceLoc ExpansionLoc = Loc.getExpansionLoc();
 925   if (!ExpansionLoc.isFileID())
 926     return nullptr;
 927
 928   const SourceManager &SrcMgr = Loc.getManager();
 929   FileID ExpansionFileID = ExpansionLoc.getFileID();
 930
 931   while (const FileEntry *ExpansionFile
 932            = SrcMgr.getFileEntryForID(ExpansionFileID)) {
 933     // Find the module that owns this header (if any).
 934     if (Module *Mod = findModuleForHeader(ExpansionFile).getModule())
 935       return Mod;
 936
 937     // No module owns this header, so look up the inclusion chain to see if
 938     // any included header has an associated module.
 939     SourceLocation IncludeLoc = SrcMgr.getIncludeLoc(ExpansionFileID);
 940     if (IncludeLoc.isInvalid())
 941       return nullptr;
 942
 943     ExpansionFileID = SrcMgr.getFileID(IncludeLoc);
 944   }
 945
 946   return nullptr;
 947 }
 948
 949 //----------------------------------------------------------------------------//
 950 // Module map file parser
 951 //----------------------------------------------------------------------------//
 952
 953 namespace clang {
 954   /// \brief A token in a module map file.
 955   struct MMToken {
 956     enum TokenKind {
 957       Comma,
 958       ConfigMacros,
 959       Conflict,
 960       EndOfFile,
 961       HeaderKeyword,
 962       Identifier,
 963       Exclaim,
 964       ExcludeKeyword,
 965       ExplicitKeyword,
 966       ExportKeyword,
 967       ExternKeyword,
 968       FrameworkKeyword,
 969       LinkKeyword,
 970       ModuleKeyword,
 971       Period,
 972       PrivateKeyword,
 973       UmbrellaKeyword,
 974       UseKeyword,
 975       RequiresKeyword,
 976       Star,
 977       StringLiteral,
 978       TextualKeyword,
 979       LBrace,
 980       RBrace,
 981       LSquare,
 982       RSquare
 983     } Kind;
 984
 985     unsigned Location;
 986     unsigned StringLength;
 987     const char *StringData;
 988
 989     void clear() {
 990       Kind = EndOfFile;
 991       Location = 0;
 992       StringLength = 0;
 993       StringData = nullptr;
 994     }
 995
 996     bool is(TokenKind K) const { return Kind == K; }
 997
 998     SourceLocation getLocation() const {
 999       return SourceLocation::getFromRawEncoding(Location);
1000     }
1001
1002     StringRef getString() const {
1003       return StringRef(StringData, StringLength);
1004     }
1005   };
1006
1007   class ModuleMapParser {
1008     Lexer &L;
1009     SourceManager &SourceMgr;
1010
1011     /// \brief Default target information, used only for string literal
1012     /// parsing.
1013     const TargetInfo *Target;
1014
1015     DiagnosticsEngine &Diags;
1016     ModuleMap &Map;
1017
1018     /// \brief The current module map file.
1019     const FileEntry *ModuleMapFile;
1020
1021     /// \brief The directory that file names in this module map file should
1022     /// be resolved relative to.
1023     const DirectoryEntry *Directory;
1024
1025     /// \brief The directory containing Clang-supplied headers.
1026     const DirectoryEntry *BuiltinIncludeDir;
1027
1028     /// \brief Whether this module map is in a system header directory.
1029     bool IsSystem;
1030
1031     /// \brief Whether an error occurred.
1032     bool HadError;
1033
1034     /// \brief Stores string data for the various string literals referenced
1035     /// during parsing.
1036     llvm::BumpPtrAllocator StringData;
1037
1038     /// \brief The current token.
1039     MMToken Tok;
1040
1041     /// \brief The active module.
1042     Module *ActiveModule;
1043
1044     /// \brief Whether a module uses the 'requires excluded' hack to mark its
1045     /// contents as 'textual'.
1046     ///
1047     /// On older Darwin SDK versions, 'requires excluded' is used to mark the
1048     /// contents of the Darwin.C.excluded (assert.h) and Tcl.Private modules as
1049     /// non-modular headers.  For backwards compatibility, we continue to
1050     /// support this idiom for just these modules, and map the headers to
1051     /// 'textual' to match the original intent.
1052     llvm::SmallPtrSet<Module *, 2> UsesRequiresExcludedHack;
1053
1054     /// \brief Consume the current token and return its location.
1055     SourceLocation consumeToken();
1056
1057     /// \brief Skip tokens until we reach the a token with the given kind
1058     /// (or the end of the file).
1059     void skipUntil(MMToken::TokenKind K);
1060
1061     typedef SmallVector<std::pair<std::string, SourceLocation>, 2> ModuleId;
1062     bool parseModuleId(ModuleId &Id);
1063     void parseModuleDecl();
1064     void parseExternModuleDecl();
1065     void parseRequiresDecl();
1066     void parseHeaderDecl(clang::MMToken::TokenKind,
1067                          SourceLocation LeadingLoc);
1068     void parseUmbrellaDirDecl(SourceLocation UmbrellaLoc);
1069     void parseExportDecl();
1070     void parseUseDecl();
1071     void parseLinkDecl();
1072     void parseConfigMacros();
1073     void parseConflict();
1074     void parseInferredModuleDecl(bool Framework, bool Explicit);
1075
1076     typedef ModuleMap::Attributes Attributes;
1077     bool parseOptionalAttributes(Attributes &Attrs);
1078
1079   public:
1080     explicit ModuleMapParser(Lexer &L, SourceManager &SourceMgr,
1081                              const TargetInfo *Target,
1082                              DiagnosticsEngine &Diags,
1083                              ModuleMap &Map,
1084                              const FileEntry *ModuleMapFile,
1085                              const DirectoryEntry *Directory,
1086                              const DirectoryEntry *BuiltinIncludeDir,
1087                              bool IsSystem)
1088       : L(L), SourceMgr(SourceMgr), Target(Target), Diags(Diags), Map(Map),
1089         ModuleMapFile(ModuleMapFile), Directory(Directory),
1090         BuiltinIncludeDir(BuiltinIncludeDir), IsSystem(IsSystem),
1091         HadError(false), ActiveModule(nullptr)
1092     {
1093       Tok.clear();
1094       consumeToken();
1095     }
1096
1097     bool parseModuleMapFile();
1098   };
1099 }
1100
1101 SourceLocation ModuleMapParser::consumeToken() {
1102 retry:
1103   SourceLocation Result = Tok.getLocation();
1104   Tok.clear();
1105
1106   Token LToken;
1107   L.LexFromRawLexer(LToken);
1108   Tok.Location = LToken.getLocation().getRawEncoding();
1109   switch (LToken.getKind()) {
1110   case tok::raw_identifier: {
1111     StringRef RI = LToken.getRawIdentifier();
1112     Tok.StringData = RI.data();
1113     Tok.StringLength = RI.size();
1114     Tok.Kind = llvm::StringSwitch<MMToken::TokenKind>(RI)
1115                  .Case("config_macros", MMToken::ConfigMacros)
1116                  .Case("conflict", MMToken::Conflict)
1117                  .Case("exclude", MMToken::ExcludeKeyword)
1118                  .Case("explicit", MMToken::ExplicitKeyword)
1119                  .Case("export", MMToken::ExportKeyword)
1120                  .Case("extern", MMToken::ExternKeyword)
1121                  .Case("framework", MMToken::FrameworkKeyword)
1122                  .Case("header", MMToken::HeaderKeyword)
1123                  .Case("link", MMToken::LinkKeyword)
1124                  .Case("module", MMToken::ModuleKeyword)
1125                  .Case("private", MMToken::PrivateKeyword)
1126                  .Case("requires", MMToken::RequiresKeyword)
1127                  .Case("textual", MMToken::TextualKeyword)
1128                  .Case("umbrella", MMToken::UmbrellaKeyword)
1129                  .Case("use", MMToken::UseKeyword)
1130                  .Default(MMToken::Identifier);
1131     break;
1132   }
1133
1134   case tok::comma:
1135     Tok.Kind = MMToken::Comma;
1136     break;
1137
1138   case tok::eof:
1139     Tok.Kind = MMToken::EndOfFile;
1140     break;
1141
1142   case tok::l_brace:
1143     Tok.Kind = MMToken::LBrace;
1144     break;
1145
1146   case tok::l_square:
1147     Tok.Kind = MMToken::LSquare;
1148     break;
1149
1150   case tok::period:
1151     Tok.Kind = MMToken::Period;
1152     break;
1153
1154   case tok::r_brace:
1155     Tok.Kind = MMToken::RBrace;
1156     break;
1157
1158   case tok::r_square:
1159     Tok.Kind = MMToken::RSquare;
1160     break;
1161
1162   case tok::star:
1163     Tok.Kind = MMToken::Star;
1164     break;
1165
1166   case tok::exclaim:
1167     Tok.Kind = MMToken::Exclaim;
1168     break;
1169
1170   case tok::string_literal: {
1171     if (LToken.hasUDSuffix()) {
1172       Diags.Report(LToken.getLocation(), diag::err_invalid_string_udl);
1173       HadError = true;
1174       goto retry;
1175     }
1176
1177     // Parse the string literal.
1178     LangOptions LangOpts;
1179     StringLiteralParser StringLiteral(LToken, SourceMgr, LangOpts, *Target);
1180     if (StringLiteral.hadError)
1181       goto retry;
1182
1183     // Copy the string literal into our string data allocator.
1184     unsigned Length = StringLiteral.GetStringLength();
1185     char *Saved = StringData.Allocate<char>(Length + 1);
1186     memcpy(Saved, StringLiteral.GetString().data(), Length);
1187     Saved[Length] = 0;
1188
1189     // Form the token.
1190     Tok.Kind = MMToken::StringLiteral;
1191     Tok.StringData = Saved;
1192     Tok.StringLength = Length;
1193     break;
1194   }
1195
1196   case tok::comment:
1197     goto retry;
1198
1199   default:
1200     Diags.Report(LToken.getLocation(), diag::err_mmap_unknown_token);
1201     HadError = true;
1202     goto retry;
1203   }
1204
1205   return Result;
1206 }
1207
1208 void ModuleMapParser::skipUntil(MMToken::TokenKind K) {
1209   unsigned braceDepth = 0;
1210   unsigned squareDepth = 0;
1211   do {
1212     switch (Tok.Kind) {
1213     case MMToken::EndOfFile:
1214       return;
1215
1216     case MMToken::LBrace:
1217       if (Tok.is(K) && braceDepth == 0 && squareDepth == 0)
1218         return;
1219
1220       ++braceDepth;
1221       break;
1222
1223     case MMToken::LSquare:
1224       if (Tok.is(K) && braceDepth == 0 && squareDepth == 0)
1225         return;
1226
1227       ++squareDepth;
1228       break;
1229
1230     case MMToken::RBrace:
1231       if (braceDepth > 0)
1232         --braceDepth;
1233       else if (Tok.is(K))
1234         return;
1235       break;
1236
1237     case MMToken::RSquare:
1238       if (squareDepth > 0)
1239         --squareDepth;
1240       else if (Tok.is(K))
1241         return;
1242       break;
1243
1244     default:
1245       if (braceDepth == 0 && squareDepth == 0 && Tok.is(K))
1246         return;
1247       break;
1248     }
1249
1250    consumeToken();
1251   } while (true);
1252 }
1253
1254 /// \brief Parse a module-id.
1255 ///
1256 ///   module-id:
1257 ///     identifier
1258 ///     identifier '.' module-id
1259 ///
1260 /// \returns true if an error occurred, false otherwise.
1261 bool ModuleMapParser::parseModuleId(ModuleId &Id) {
1262   Id.clear();
1263   do {
1264     if (Tok.is(MMToken::Identifier) || Tok.is(MMToken::StringLiteral)) {
1265       Id.push_back(std::make_pair(Tok.getString(), Tok.getLocation()));
1266       consumeToken();
1267     } else {
1268       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module_name);
1269       return true;
1270     }
1271
1272     if (!Tok.is(MMToken::Period))
1273       break;
1274
1275     consumeToken();
1276   } while (true);
1277
1278   return false;
1279 }
1280
1281 namespace {
1282   /// \brief Enumerates the known attributes.
1283   enum AttributeKind {
1284     /// \brief An unknown attribute.
1285     AT_unknown,
1286     /// \brief The 'system' attribute.
1287     AT_system,
1288     /// \brief The 'extern_c' attribute.
1289     AT_extern_c,
1290     /// \brief The 'exhaustive' attribute.
1291     AT_exhaustive
1292   };
1293 }
1294
1295 /// \brief Parse a module declaration.
1296 ///
1297 ///   module-declaration:
1298 ///     'extern' 'module' module-id string-literal
1299 ///     'explicit'[opt] 'framework'[opt] 'module' module-id attributes[opt]
1300 ///       { module-member* }
1301 ///
1302 ///   module-member:
1303 ///     requires-declaration
1304 ///     header-declaration
1305 ///     submodule-declaration
1306 ///     export-declaration
1307 ///     link-declaration
1308 ///
1309 ///   submodule-declaration:
1310 ///     module-declaration
1311 ///     inferred-submodule-declaration
1312 void ModuleMapParser::parseModuleDecl() {
1313   assert(Tok.is(MMToken::ExplicitKeyword) || Tok.is(MMToken::ModuleKeyword) ||
1314          Tok.is(MMToken::FrameworkKeyword) || Tok.is(MMToken::ExternKeyword));
1315   if (Tok.is(MMToken::ExternKeyword)) {
1316     parseExternModuleDecl();
1317     return;
1318   }
1319
1320   // Parse 'explicit' or 'framework' keyword, if present.
1321   SourceLocation ExplicitLoc;
1322   bool Explicit = false;
1323   bool Framework = false;
1324
1325   // Parse 'explicit' keyword, if present.
1326   if (Tok.is(MMToken::ExplicitKeyword)) {
1327     ExplicitLoc = consumeToken();
1328     Explicit = true;
1329   }
1330
1331   // Parse 'framework' keyword, if present.
1332   if (Tok.is(MMToken::FrameworkKeyword)) {
1333     consumeToken();
1334     Framework = true;
1335   }
1336
1337   // Parse 'module' keyword.
1338   if (!Tok.is(MMToken::ModuleKeyword)) {
1339     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
1340     consumeToken();
1341     HadError = true;
1342     return;
1343   }
1344   consumeToken(); // 'module' keyword
1345
1346   // If we have a wildcard for the module name, this is an inferred submodule.
1347   // Parse it.
1348   if (Tok.is(MMToken::Star))
1349     return parseInferredModuleDecl(Framework, Explicit);
1350
1351   // Parse the module name.
1352   ModuleId Id;
1353   if (parseModuleId(Id)) {
1354     HadError = true;
1355     return;
1356   }
1357
1358   if (ActiveModule) {
1359     if (Id.size() > 1) {
1360       Diags.Report(Id.front().second, diag::err_mmap_nested_submodule_id)
1361         << SourceRange(Id.front().second, Id.back().second);
1362
1363       HadError = true;
1364       return;
1365     }
1366   } else if (Id.size() == 1 && Explicit) {
1367     // Top-level modules can't be explicit.
1368     Diags.Report(ExplicitLoc, diag::err_mmap_explicit_top_level);
1369     Explicit = false;
1370     ExplicitLoc = SourceLocation();
1371     HadError = true;
1372   }
1373
1374   Module *PreviousActiveModule = ActiveModule;
1375   if (Id.size() > 1) {
1376     // This module map defines a submodule. Go find the module of which it
1377     // is a submodule.
1378     ActiveModule = nullptr;
1379     const Module *TopLevelModule = nullptr;
1380     for (unsigned I = 0, N = Id.size() - 1; I != N; ++I) {
1381       if (Module *Next = Map.lookupModuleQualified(Id[I].first, ActiveModule)) {
1382         if (I == 0)
1383           TopLevelModule = Next;
1384         ActiveModule = Next;
1385         continue;
1386       }
1387
1388       if (ActiveModule) {
1389         Diags.Report(Id[I].second, diag::err_mmap_missing_module_qualified)
1390           << Id[I].first
1391           << ActiveModule->getTopLevelModule()->getFullModuleName();
1392       } else {
1393         Diags.Report(Id[I].second, diag::err_mmap_expected_module_name);
1394       }
1395       HadError = true;
1396       return;
1397     }
1398
1399     if (ModuleMapFile != Map.getContainingModuleMapFile(TopLevelModule)) {
1400       assert(ModuleMapFile != Map.getModuleMapFileForUniquing(TopLevelModule) &&
1401              "submodule defined in same file as 'module *' that allowed its "
1402              "top-level module");
1403       Map.addAdditionalModuleMapFile(TopLevelModule, ModuleMapFile);
1404     }
1405   }
1406
1407   StringRef ModuleName = Id.back().first;
1408   SourceLocation ModuleNameLoc = Id.back().second;
1409
1410   // Parse the optional attribute list.
1411   Attributes Attrs;
1412   parseOptionalAttributes(Attrs);
1413
1414   // Parse the opening brace.
1415   if (!Tok.is(MMToken::LBrace)) {
1416     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_lbrace)
1417       << ModuleName;
1418     HadError = true;
1419     return;
1420   }
1421   SourceLocation LBraceLoc = consumeToken();
1422
1423   // Determine whether this (sub)module has already been defined.
1424   if (Module *Existing = Map.lookupModuleQualified(ModuleName, ActiveModule)) {
1425     if (Existing->DefinitionLoc.isInvalid() && !ActiveModule) {
1426       // Skip the module definition.
1427       skipUntil(MMToken::RBrace);
1428       if (Tok.is(MMToken::RBrace))
1429         consumeToken();
1430       else {
1431         Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
1432         Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
1433         HadError = true;
1434       }
1435       return;
1436     }
1437
1438     Diags.Report(ModuleNameLoc, diag::err_mmap_module_redefinition)
1439       << ModuleName;
1440     Diags.Report(Existing->DefinitionLoc, diag::note_mmap_prev_definition);
1441
1442     // Skip the module definition.
1443     skipUntil(MMToken::RBrace);
1444     if (Tok.is(MMToken::RBrace))
1445       consumeToken();
1446
1447     HadError = true;
1448     return;
1449   }
1450
1451   // Start defining this module.
1452   ActiveModule = Map.findOrCreateModule(ModuleName, ActiveModule, Framework,
1453                                         Explicit).first;
1454   ActiveModule->DefinitionLoc = ModuleNameLoc;
1455   if (Attrs.IsSystem || IsSystem)
1456     ActiveModule->IsSystem = true;
1457   if (Attrs.IsExternC)
1458     ActiveModule->IsExternC = true;
1459   ActiveModule->Directory = Directory;
1460
1461   bool Done = false;
1462   do {
1463     switch (Tok.Kind) {
1464     case MMToken::EndOfFile:
1465     case MMToken::RBrace:
1466       Done = true;
1467       break;
1468
1469     case MMToken::ConfigMacros:
1470       parseConfigMacros();
1471       break;
1472
1473     case MMToken::Conflict:
1474       parseConflict();
1475       break;
1476
1477     case MMToken::ExplicitKeyword:
1478     case MMToken::ExternKeyword:
1479     case MMToken::FrameworkKeyword:
1480     case MMToken::ModuleKeyword:
1481       parseModuleDecl();
1482       break;
1483
1484     case MMToken::ExportKeyword:
1485       parseExportDecl();
1486       break;
1487
1488     case MMToken::UseKeyword:
1489       parseUseDecl();
1490       break;
1491
1492     case MMToken::RequiresKeyword:
1493       parseRequiresDecl();
1494       break;
1495
1496     case MMToken::TextualKeyword:
1497       parseHeaderDecl(MMToken::TextualKeyword, consumeToken());
1498       break;
1499
1500     case MMToken::UmbrellaKeyword: {
1501       SourceLocation UmbrellaLoc = consumeToken();
1502       if (Tok.is(MMToken::HeaderKeyword))
1503         parseHeaderDecl(MMToken::UmbrellaKeyword, UmbrellaLoc);
1504       else
1505         parseUmbrellaDirDecl(UmbrellaLoc);
1506       break;
1507     }
1508
1509     case MMToken::ExcludeKeyword:
1510       parseHeaderDecl(MMToken::ExcludeKeyword, consumeToken());
1511       break;
1512
1513     case MMToken::PrivateKeyword:
1514       parseHeaderDecl(MMToken::PrivateKeyword, consumeToken());
1515       break;
1516
1517     case MMToken::HeaderKeyword:
1518       parseHeaderDecl(MMToken::HeaderKeyword, consumeToken());
1519       break;
1520
1521     case MMToken::LinkKeyword:
1522       parseLinkDecl();
1523       break;
1524
1525     default:
1526       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_member);
1527       consumeToken();
1528       break;
1529     }
1530   } while (!Done);
1531
1532   if (Tok.is(MMToken::RBrace))
1533     consumeToken();
1534   else {
1535     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
1536     Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
1537     HadError = true;
1538   }
1539
1540   // If the active module is a top-level framework, and there are no link
1541   // libraries, automatically link against the framework.
1542   if (ActiveModule->IsFramework && !ActiveModule->isSubFramework() &&
1543       ActiveModule->LinkLibraries.empty()) {
1544     inferFrameworkLink(ActiveModule, Directory, SourceMgr.getFileManager());
1545   }
1546
1547   // If the module meets all requirements but is still unavailable, mark the
1548   // whole tree as unavailable to prevent it from building.
1549   if (!ActiveModule->IsAvailable && !ActiveModule->IsMissingRequirement &&
1550       ActiveModule->Parent) {
1551     ActiveModule->getTopLevelModule()->markUnavailable();
1552     ActiveModule->getTopLevelModule()->MissingHeaders.append(
1553       ActiveModule->MissingHeaders.begin(), ActiveModule->MissingHeaders.end());
1554   }
1555
1556   // We're done parsing this module. Pop back to the previous module.
1557   ActiveModule = PreviousActiveModule;
1558 }
1559
1560 /// \brief Parse an extern module declaration.
1561 ///
1562 ///   extern module-declaration:
1563 ///     'extern' 'module' module-id string-literal
1564 void ModuleMapParser::parseExternModuleDecl() {
1565   assert(Tok.is(MMToken::ExternKeyword));
1566   SourceLocation ExternLoc = consumeToken(); // 'extern' keyword
1567
1568   // Parse 'module' keyword.
1569   if (!Tok.is(MMToken::ModuleKeyword)) {
1570     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
1571     consumeToken();
1572     HadError = true;
1573     return;
1574   }
1575   consumeToken(); // 'module' keyword
1576
1577   // Parse the module name.
1578   ModuleId Id;
1579   if (parseModuleId(Id)) {
1580     HadError = true;
1581     return;
1582   }
1583
1584   // Parse the referenced module map file name.
1585   if (!Tok.is(MMToken::StringLiteral)) {
1586     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_mmap_file);
1587     HadError = true;
1588     return;
1589   }
1590   std::string FileName = Tok.getString();
1591   consumeToken(); // filename
1592
1593   StringRef FileNameRef = FileName;
1594   SmallString<128> ModuleMapFileName;
1595   if (llvm::sys::path::is_relative(FileNameRef)) {
1596     ModuleMapFileName += Directory->getName();
1597     llvm::sys::path::append(ModuleMapFileName, FileName);
1598     FileNameRef = ModuleMapFileName;
1599   }
1600   if (const FileEntry *File = SourceMgr.getFileManager().getFile(FileNameRef))
1601     Map.parseModuleMapFile(
1602         File, /*IsSystem=*/false,
1603         Map.HeaderInfo.getHeaderSearchOpts().ModuleMapFileHomeIsCwd
1604             ? Directory
1605             : File->getDir(), ExternLoc);
1606 }
1607
1608 /// Whether to add the requirement \p Feature to the module \p M.
1609 ///
1610 /// This preserves backwards compatibility for two hacks in the Darwin system
1611 /// module map files:
1612 ///
1613 /// 1. The use of 'requires excluded' to make headers non-modular, which
1614 ///    should really be mapped to 'textual' now that we have this feature.  We
1615 ///    drop the 'excluded' requirement, and set \p IsRequiresExcludedHack to
1616 ///    true.  Later, this bit will be used to map all the headers inside this
1617 ///    module to 'textual'.
1618 ///
1619 ///    This affects Darwin.C.excluded (for assert.h) and Tcl.Private.
1620 ///
1621 /// 2. Removes a bogus cplusplus requirement from IOKit.avc.  This requirement
1622 ///    was never correct and causes issues now that we check it, so drop it.
1623 static bool shouldAddRequirement(Module *M, StringRef Feature,
1624                                  bool &IsRequiresExcludedHack) {
1625   static const StringRef DarwinCExcluded[] = {"Darwin", "C", "excluded"};
1626   static const StringRef TclPrivate[] = {"Tcl", "Private"};
1627   static const StringRef IOKitAVC[] = {"IOKit", "avc"};
1628
1629   if (Feature == "excluded" && (M->fullModuleNameIs(DarwinCExcluded) ||
1630                                 M->fullModuleNameIs(TclPrivate))) {
1631     IsRequiresExcludedHack = true;
1632     return false;
1633   } else if (Feature == "cplusplus" && M->fullModuleNameIs(IOKitAVC)) {
1634     return false;
1635   }
1636
1637   return true;
1638 }
1639
1640 /// \brief Parse a requires declaration.
1641 ///
1642 ///   requires-declaration:
1643 ///     'requires' feature-list
1644 ///
1645 ///   feature-list:
1646 ///     feature ',' feature-list
1647 ///     feature
1648 ///
1649 ///   feature:
1650 ///     '!'[opt] identifier
1651 void ModuleMapParser::parseRequiresDecl() {
1652   assert(Tok.is(MMToken::RequiresKeyword));
1653
1654   // Parse 'requires' keyword.
1655   consumeToken();
1656
1657   // Parse the feature-list.
1658   do {
1659     bool RequiredState = true;
1660     if (Tok.is(MMToken::Exclaim)) {
1661       RequiredState = false;
1662       consumeToken();
1663     }
1664
1665     if (!Tok.is(MMToken::Identifier)) {
1666       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_feature);
1667       HadError = true;
1668       return;
1669     }
1670
1671     // Consume the feature name.
1672     std::string Feature = Tok.getString();
1673     consumeToken();
1674
1675     bool IsRequiresExcludedHack = false;
1676     bool ShouldAddRequirement =
1677         shouldAddRequirement(ActiveModule, Feature, IsRequiresExcludedHack);
1678
1679     if (IsRequiresExcludedHack)
1680       UsesRequiresExcludedHack.insert(ActiveModule);
1681
1682     if (ShouldAddRequirement) {
1683       // Add this feature.
1684       ActiveModule->addRequirement(Feature, RequiredState, Map.LangOpts,
1685                                    *Map.Target);
1686     }
1687
1688     if (!Tok.is(MMToken::Comma))
1689       break;
1690
1691     // Consume the comma.
1692     consumeToken();
1693   } while (true);
1694 }
1695
1696 /// \brief Append to \p Paths the set of paths needed to get to the
1697 /// subframework in which the given module lives.
1698 static void appendSubframeworkPaths(Module *Mod,
1699                                     SmallVectorImpl<char> &Path) {
1700   // Collect the framework names from the given module to the top-level module.
1701   SmallVector<StringRef, 2> Paths;
1702   for (; Mod; Mod = Mod->Parent) {
1703     if (Mod->IsFramework)
1704       Paths.push_back(Mod->Name);
1705   }
1706
1707   if (Paths.empty())
1708     return;
1709
1710   // Add Frameworks/Name.framework for each subframework.
1711   for (unsigned I = Paths.size() - 1; I != 0; --I)
1712     llvm::sys::path::append(Path, "Frameworks", Paths[I-1] + ".framework");
1713 }
1714
1715 /// \brief Parse a header declaration.
1716 ///
1717 ///   header-declaration:
1718 ///     'textual'[opt] 'header' string-literal
1719 ///     'private' 'textual'[opt] 'header' string-literal
1720 ///     'exclude' 'header' string-literal
1721 ///     'umbrella' 'header' string-literal
1722 ///
1723 /// FIXME: Support 'private textual header'.
1724 void ModuleMapParser::parseHeaderDecl(MMToken::TokenKind LeadingToken,
1725                                       SourceLocation LeadingLoc) {
1726   // We've already consumed the first token.
1727   ModuleMap::ModuleHeaderRole Role = ModuleMap::NormalHeader;
1728   if (LeadingToken == MMToken::PrivateKeyword) {
1729     Role = ModuleMap::PrivateHeader;
1730     // 'private' may optionally be followed by 'textual'.
1731     if (Tok.is(MMToken::TextualKeyword)) {
1732       LeadingToken = Tok.Kind;
1733       consumeToken();
1734     }
1735   }
1736
1737   if (LeadingToken == MMToken::TextualKeyword)
1738     Role = ModuleMap::ModuleHeaderRole(Role | ModuleMap::TextualHeader);
1739
1740   if (UsesRequiresExcludedHack.count(ActiveModule)) {
1741     // Mark this header 'textual' (see doc comment for
1742     // Module::UsesRequiresExcludedHack).
1743     Role = ModuleMap::ModuleHeaderRole(Role | ModuleMap::TextualHeader);
1744   }
1745
1746   if (LeadingToken != MMToken::HeaderKeyword) {
1747     if (!Tok.is(MMToken::HeaderKeyword)) {
1748       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1749           << (LeadingToken == MMToken::PrivateKeyword ? "private" :
1750               LeadingToken == MMToken::ExcludeKeyword ? "exclude" :
1751               LeadingToken == MMToken::TextualKeyword ? "textual" : "umbrella");
1752       return;
1753     }
1754     consumeToken();
1755   }
1756
1757   // Parse the header name.
1758   if (!Tok.is(MMToken::StringLiteral)) {
1759     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1760       << "header";
1761     HadError = true;
1762     return;
1763   }
1764   Module::UnresolvedHeaderDirective Header;
1765   Header.FileName = Tok.getString();
1766   Header.FileNameLoc = consumeToken();
1767
1768   // Check whether we already have an umbrella.
1769   if (LeadingToken == MMToken::UmbrellaKeyword && ActiveModule->Umbrella) {
1770     Diags.Report(Header.FileNameLoc, diag::err_mmap_umbrella_clash)
1771       << ActiveModule->getFullModuleName();
1772     HadError = true;
1773     return;
1774   }
1775
1776   // Look for this file.
1777   const FileEntry *File = nullptr;
1778   const FileEntry *BuiltinFile = nullptr;
1779   SmallString<128> RelativePathName;
1780   if (llvm::sys::path::is_absolute(Header.FileName)) {
1781     RelativePathName = Header.FileName;
1782     File = SourceMgr.getFileManager().getFile(RelativePathName);
1783   } else {
1784     // Search for the header file within the search directory.
1785     SmallString<128> FullPathName(Directory->getName());
1786     unsigned FullPathLength = FullPathName.size();
1787
1788     if (ActiveModule->isPartOfFramework()) {
1789       appendSubframeworkPaths(ActiveModule, RelativePathName);
1790
1791       // Check whether this file is in the public headers.
1792       llvm::sys::path::append(RelativePathName, "Headers", Header.FileName);
1793       llvm::sys::path::append(FullPathName, RelativePathName);
1794       File = SourceMgr.getFileManager().getFile(FullPathName);
1795
1796       if (!File) {
1797         // Check whether this file is in the private headers.
1798         // FIXME: Should we retain the subframework paths here?
1799         RelativePathName.clear();
1800         FullPathName.resize(FullPathLength);
1801         llvm::sys::path::append(RelativePathName, "PrivateHeaders",
1802                                 Header.FileName);
1803         llvm::sys::path::append(FullPathName, RelativePathName);
1804         File = SourceMgr.getFileManager().getFile(FullPathName);
1805       }
1806     } else {
1807       // Lookup for normal headers.
1808       llvm::sys::path::append(RelativePathName, Header.FileName);
1809       llvm::sys::path::append(FullPathName, RelativePathName);
1810       File = SourceMgr.getFileManager().getFile(FullPathName);
1811
1812       // If this is a system module with a top-level header, this header
1813       // may have a counterpart (or replacement) in the set of headers
1814       // supplied by Clang. Find that builtin header.
1815       if (ActiveModule->IsSystem && LeadingToken != MMToken::UmbrellaKeyword &&
1816           BuiltinIncludeDir && BuiltinIncludeDir != Directory &&
1817           isBuiltinHeader(Header.FileName)) {
1818         SmallString<128> BuiltinPathName(BuiltinIncludeDir->getName());
1819         llvm::sys::path::append(BuiltinPathName, Header.FileName);
1820         BuiltinFile = SourceMgr.getFileManager().getFile(BuiltinPathName);
1821
1822         // If Clang supplies this header but the underlying system does not,
1823         // just silently swap in our builtin version. Otherwise, we'll end
1824         // up adding both (later).
1825         //
1826         // For local visibility, entirely replace the system file with our
1827         // one and textually include the system one. We need to pass macros
1828         // from our header to the system one if we #include_next it.
1829         //
1830         // FIXME: Can we do this in all cases?
1831         if (BuiltinFile && (!File || Map.LangOpts.ModulesLocalVisibility)) {
1832           File = BuiltinFile;
1833           RelativePathName = BuiltinPathName;
1834           BuiltinFile = nullptr;
1835         }
1836       }
1837     }
1838   }
1839
1840   // FIXME: We shouldn't be eagerly stat'ing every file named in a module map.
1841   // Come up with a lazy way to do this.
1842   if (File) {
1843     if (LeadingToken == MMToken::UmbrellaKeyword) {
1844       const DirectoryEntry *UmbrellaDir = File->getDir();
1845       if (Module *UmbrellaModule = Map.UmbrellaDirs[UmbrellaDir]) {
1846         Diags.Report(LeadingLoc, diag::err_mmap_umbrella_clash)
1847           << UmbrellaModule->getFullModuleName();
1848         HadError = true;
1849       } else {
1850         // Record this umbrella header.
1851         Map.setUmbrellaHeader(ActiveModule, File, RelativePathName.str());
1852       }
1853     } else if (LeadingToken == MMToken::ExcludeKeyword) {
1854       Module::Header H = {RelativePathName.str(), File};
1855       Map.excludeHeader(ActiveModule, H);
1856     } else {
1857       // If there is a builtin counterpart to this file, add it now, before
1858       // the "real" header, so we build the built-in one first when building
1859       // the module.
1860       if (BuiltinFile) {
1861         // FIXME: Taking the name from the FileEntry is unstable and can give
1862         // different results depending on how we've previously named that file
1863         // in this build.
1864         Module::Header H = { BuiltinFile->getName(), BuiltinFile };
1865         Map.addHeader(ActiveModule, H, Role);
1866       }
1867
1868       // Record this header.
1869       Module::Header H = { RelativePathName.str(), File };
1870       Map.addHeader(ActiveModule, H, Role);
1871     }
1872   } else if (LeadingToken != MMToken::ExcludeKeyword) {
1873     // Ignore excluded header files. They're optional anyway.
1874
1875     // If we find a module that has a missing header, we mark this module as
1876     // unavailable and store the header directive for displaying diagnostics.
1877     Header.IsUmbrella = LeadingToken == MMToken::UmbrellaKeyword;
1878     ActiveModule->markUnavailable();
1879     ActiveModule->MissingHeaders.push_back(Header);
1880   }
1881 }
1882
1883 static int compareModuleHeaders(const Module::Header *A,
1884                                 const Module::Header *B) {
1885   return A->NameAsWritten.compare(B->NameAsWritten);
1886 }
1887
1888 /// \brief Parse an umbrella directory declaration.
1889 ///
1890 ///   umbrella-dir-declaration:
1891 ///     umbrella string-literal
1892 void ModuleMapParser::parseUmbrellaDirDecl(SourceLocation UmbrellaLoc) {
1893   // Parse the directory name.
1894   if (!Tok.is(MMToken::StringLiteral)) {
1895     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1896       << "umbrella";
1897     HadError = true;
1898     return;
1899   }
1900
1901   std::string DirName = Tok.getString();
1902   SourceLocation DirNameLoc = consumeToken();
1903
1904   // Check whether we already have an umbrella.
1905   if (ActiveModule->Umbrella) {
1906     Diags.Report(DirNameLoc, diag::err_mmap_umbrella_clash)
1907       << ActiveModule->getFullModuleName();
1908     HadError = true;
1909     return;
1910   }
1911
1912   // Look for this file.
1913   const DirectoryEntry *Dir = nullptr;
1914   if (llvm::sys::path::is_absolute(DirName))
1915     Dir = SourceMgr.getFileManager().getDirectory(DirName);
1916   else {
1917     SmallString<128> PathName;
1918     PathName = Directory->getName();
1919     llvm::sys::path::append(PathName, DirName);
1920     Dir = SourceMgr.getFileManager().getDirectory(PathName);
1921   }
1922
1923   if (!Dir) {
1924     Diags.Report(DirNameLoc, diag::err_mmap_umbrella_dir_not_found)
1925       << DirName;
1926     HadError = true;
1927     return;
1928   }
1929
1930   if (UsesRequiresExcludedHack.count(ActiveModule)) {
1931     // Mark this header 'textual' (see doc comment for
1932     // ModuleMapParser::UsesRequiresExcludedHack). Although iterating over the
1933     // directory is relatively expensive, in practice this only applies to the
1934     // uncommonly used Tcl module on Darwin platforms.
1935     std::error_code EC;
1936     SmallVector<Module::Header, 6> Headers;
1937     for (llvm::sys::fs::recursive_directory_iterator I(Dir->getName(), EC), E;
1938          I != E && !EC; I.increment(EC)) {
1939       if (const FileEntry *FE = SourceMgr.getFileManager().getFile(I->path())) {
1940
1941         Module::Header Header = {I->path(), FE};
1942         Headers.push_back(std::move(Header));
1943       }
1944     }
1945
1946     // Sort header paths so that the pcm doesn't depend on iteration order.
1947     llvm::array_pod_sort(Headers.begin(), Headers.end(), compareModuleHeaders);
1948
1949     for (auto &Header : Headers)
1950       Map.addHeader(ActiveModule, std::move(Header), ModuleMap::TextualHeader);
1951     return;
1952   }
1953
1954   if (Module *OwningModule = Map.UmbrellaDirs[Dir]) {
1955     Diags.Report(UmbrellaLoc, diag::err_mmap_umbrella_clash)
1956       << OwningModule->getFullModuleName();
1957     HadError = true;
1958     return;
1959   }
1960
1961   // Record this umbrella directory.
1962   Map.setUmbrellaDir(ActiveModule, Dir, DirName);
1963 }
1964
1965 /// \brief Parse a module export declaration.
1966 ///
1967 ///   export-declaration:
1968 ///     'export' wildcard-module-id
1969 ///
1970 ///   wildcard-module-id:
1971 ///     identifier
1972 ///     '*'
1973 ///     identifier '.' wildcard-module-id
1974 void ModuleMapParser::parseExportDecl() {
1975   assert(Tok.is(MMToken::ExportKeyword));
1976   SourceLocation ExportLoc = consumeToken();
1977
1978   // Parse the module-id with an optional wildcard at the end.
1979   ModuleId ParsedModuleId;
1980   bool Wildcard = false;
1981   do {
1982     // FIXME: Support string-literal module names here.
1983     if (Tok.is(MMToken::Identifier)) {
1984       ParsedModuleId.push_back(std::make_pair(Tok.getString(),
1985                                               Tok.getLocation()));
1986       consumeToken();
1987
1988       if (Tok.is(MMToken::Period)) {
1989         consumeToken();
1990         continue;
1991       }
1992
1993       break;
1994     }
1995
1996     if(Tok.is(MMToken::Star)) {
1997       Wildcard = true;
1998       consumeToken();
1999       break;
2000     }
2001
2002     Diags.Report(Tok.getLocation(), diag::err_mmap_module_id);
2003     HadError = true;
2004     return;
2005   } while (true);
2006
2007   Module::UnresolvedExportDecl Unresolved = {
2008     ExportLoc, ParsedModuleId, Wildcard
2009   };
2010   ActiveModule->UnresolvedExports.push_back(Unresolved);
2011 }
2012
2013 /// \brief Parse a module use declaration.
2014 ///
2015 ///   use-declaration:
2016 ///     'use' wildcard-module-id
2017 void ModuleMapParser::parseUseDecl() {
2018   assert(Tok.is(MMToken::UseKeyword));
2019   auto KWLoc = consumeToken();
2020   // Parse the module-id.
2021   ModuleId ParsedModuleId;
2022   parseModuleId(ParsedModuleId);
2023
2024   if (ActiveModule->Parent)
2025     Diags.Report(KWLoc, diag::err_mmap_use_decl_submodule);
2026   else
2027     ActiveModule->UnresolvedDirectUses.push_back(ParsedModuleId);
2028 }
2029
2030 /// \brief Parse a link declaration.
2031 ///
2032 ///   module-declaration:
2033 ///     'link' 'framework'[opt] string-literal
2034 void ModuleMapParser::parseLinkDecl() {
2035   assert(Tok.is(MMToken::LinkKeyword));
2036   SourceLocation LinkLoc = consumeToken();
2037
2038   // Parse the optional 'framework' keyword.
2039   bool IsFramework = false;
2040   if (Tok.is(MMToken::FrameworkKeyword)) {
2041     consumeToken();
2042     IsFramework = true;
2043   }
2044
2045   // Parse the library name
2046   if (!Tok.is(MMToken::StringLiteral)) {
2047     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_library_name)
2048       << IsFramework << SourceRange(LinkLoc);
2049     HadError = true;
2050     return;
2051   }
2052
2053   std::string LibraryName = Tok.getString();
2054   consumeToken();
2055   ActiveModule->LinkLibraries.push_back(Module::LinkLibrary(LibraryName,
2056                                                             IsFramework));
2057 }
2058
2059 /// \brief Parse a configuration macro declaration.
2060 ///
2061 ///   module-declaration:
2062 ///     'config_macros' attributes[opt] config-macro-list?
2063 ///
2064 ///   config-macro-list:
2065 ///     identifier (',' identifier)?
2066 void ModuleMapParser::parseConfigMacros() {
2067   assert(Tok.is(MMToken::ConfigMacros));
2068   SourceLocation ConfigMacrosLoc = consumeToken();
2069
2070   // Only top-level modules can have configuration macros.
2071   if (ActiveModule->Parent) {
2072     Diags.Report(ConfigMacrosLoc, diag::err_mmap_config_macro_submodule);
2073   }
2074
2075   // Parse the optional attributes.
2076   Attributes Attrs;
2077   parseOptionalAttributes(Attrs);
2078   if (Attrs.IsExhaustive && !ActiveModule->Parent) {
2079     ActiveModule->ConfigMacrosExhaustive = true;
2080   }
2081
2082   // If we don't have an identifier, we're done.
2083   // FIXME: Support macros with the same name as a keyword here.
2084   if (!Tok.is(MMToken::Identifier))
2085     return;
2086
2087   // Consume the first identifier.
2088   if (!ActiveModule->Parent) {
2089     ActiveModule->ConfigMacros.push_back(Tok.getString().str());
2090   }
2091   consumeToken();
2092
2093   do {
2094     // If there's a comma, consume it.
2095     if (!Tok.is(MMToken::Comma))
2096       break;
2097     consumeToken();
2098
2099     // We expect to see a macro name here.
2100     // FIXME: Support macros with the same name as a keyword here.
2101     if (!Tok.is(MMToken::Identifier)) {
2102       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_config_macro);
2103       break;
2104     }
2105
2106     // Consume the macro name.
2107     if (!ActiveModule->Parent) {
2108       ActiveModule->ConfigMacros.push_back(Tok.getString().str());
2109     }
2110     consumeToken();
2111   } while (true);
2112 }
2113
2114 /// \brief Format a module-id into a string.
2115 static std::string formatModuleId(const ModuleId &Id) {
2116   std::string result;
2117   {
2118     llvm::raw_string_ostream OS(result);
2119
2120     for (unsigned I = 0, N = Id.size(); I != N; ++I) {
2121       if (I)
2122         OS << ".";
2123       OS << Id[I].first;
2124     }
2125   }
2126
2127   return result;
2128 }
2129
2130 /// \brief Parse a conflict declaration.
2131 ///
2132 ///   module-declaration:
2133 ///     'conflict' module-id ',' string-literal
2134 void ModuleMapParser::parseConflict() {
2135   assert(Tok.is(MMToken::Conflict));
2136   SourceLocation ConflictLoc = consumeToken();
2137   Module::UnresolvedConflict Conflict;
2138
2139   // Parse the module-id.
2140   if (parseModuleId(Conflict.Id))
2141     return;
2142
2143   // Parse the ','.
2144   if (!Tok.is(MMToken::Comma)) {
2145     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_conflicts_comma)
2146       << SourceRange(ConflictLoc);
2147     return;
2148   }
2149   consumeToken();
2150
2151   // Parse the message.
2152   if (!Tok.is(MMToken::StringLiteral)) {
2153     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_conflicts_message)
2154       << formatModuleId(Conflict.Id);
2155     return;
2156   }
2157   Conflict.Message = Tok.getString().str();
2158   consumeToken();
2159
2160   // Add this unresolved conflict.
2161   ActiveModule->UnresolvedConflicts.push_back(Conflict);
2162 }
2163
2164 /// \brief Parse an inferred module declaration (wildcard modules).
2165 ///
2166 ///   module-declaration:
2167 ///     'explicit'[opt] 'framework'[opt] 'module' * attributes[opt]
2168 ///       { inferred-module-member* }
2169 ///
2170 ///   inferred-module-member:
2171 ///     'export' '*'
2172 ///     'exclude' identifier
2173 void ModuleMapParser::parseInferredModuleDecl(bool Framework, bool Explicit) {
2174   assert(Tok.is(MMToken::Star));
2175   SourceLocation StarLoc = consumeToken();
2176   bool Failed = false;
2177
2178   // Inferred modules must be submodules.
2179   if (!ActiveModule && !Framework) {
2180     Diags.Report(StarLoc, diag::err_mmap_top_level_inferred_submodule);
2181     Failed = true;
2182   }
2183
2184   if (ActiveModule) {
2185     // Inferred modules must have umbrella directories.
2186     if (!Failed && ActiveModule->IsAvailable &&
2187         !ActiveModule->getUmbrellaDir()) {
2188       Diags.Report(StarLoc, diag::err_mmap_inferred_no_umbrella);
2189       Failed = true;
2190     }
2191
2192     // Check for redefinition of an inferred module.
2193     if (!Failed && ActiveModule->InferSubmodules) {
2194       Diags.Report(StarLoc, diag::err_mmap_inferred_redef);
2195       if (ActiveModule->InferredSubmoduleLoc.isValid())
2196         Diags.Report(ActiveModule->InferredSubmoduleLoc,
2197                      diag::note_mmap_prev_definition);
2198       Failed = true;
2199     }
2200
2201     // Check for the 'framework' keyword, which is not permitted here.
2202     if (Framework) {
2203       Diags.Report(StarLoc, diag::err_mmap_inferred_framework_submodule);
2204       Framework = false;
2205     }
2206   } else if (Explicit) {
2207     Diags.Report(StarLoc, diag::err_mmap_explicit_inferred_framework);
2208     Explicit = false;
2209   }
2210
2211   // If there were any problems with this inferred submodule, skip its body.
2212   if (Failed) {
2213     if (Tok.is(MMToken::LBrace)) {
2214       consumeToken();
2215       skipUntil(MMToken::RBrace);
2216       if (Tok.is(MMToken::RBrace))
2217         consumeToken();
2218     }
2219     HadError = true;
2220     return;
2221   }
2222
2223   // Parse optional attributes.
2224   Attributes Attrs;
2225   parseOptionalAttributes(Attrs);
2226
2227   if (ActiveModule) {
2228     // Note that we have an inferred submodule.
2229     ActiveModule->InferSubmodules = true;
2230     ActiveModule->InferredSubmoduleLoc = StarLoc;
2231     ActiveModule->InferExplicitSubmodules = Explicit;
2232   } else {
2233     // We'll be inferring framework modules for this directory.
2234     Map.InferredDirectories[Directory].InferModules = true;
2235     Map.InferredDirectories[Directory].Attrs = Attrs;
2236     Map.InferredDirectories[Directory].ModuleMapFile = ModuleMapFile;
2237     // FIXME: Handle the 'framework' keyword.
2238   }
2239
2240   // Parse the opening brace.
2241   if (!Tok.is(MMToken::LBrace)) {
2242     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_lbrace_wildcard);
2243     HadError = true;
2244     return;
2245   }
2246   SourceLocation LBraceLoc = consumeToken();
2247
2248   // Parse the body of the inferred submodule.
2249   bool Done = false;
2250   do {
2251     switch (Tok.Kind) {
2252     case MMToken::EndOfFile:
2253     case MMToken::RBrace:
2254       Done = true;
2255       break;
2256
2257     case MMToken::ExcludeKeyword: {
2258       if (ActiveModule) {
2259         Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
2260           << (ActiveModule != nullptr);
2261         consumeToken();
2262         break;
2263       }
2264
2265       consumeToken();
2266       // FIXME: Support string-literal module names here.
2267       if (!Tok.is(MMToken::Identifier)) {
2268         Diags.Report(Tok.getLocation(), diag::err_mmap_missing_exclude_name);
2269         break;
2270       }
2271
2272       Map.InferredDirectories[Directory].ExcludedModules
2273         .push_back(Tok.getString());
2274       consumeToken();
2275       break;
2276     }
2277
2278     case MMToken::ExportKeyword:
2279       if (!ActiveModule) {
2280         Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
2281           << (ActiveModule != nullptr);
2282         consumeToken();
2283         break;
2284       }
2285
2286       consumeToken();
2287       if (Tok.is(MMToken::Star))
2288         ActiveModule->InferExportWildcard = true;
2289       else
2290         Diags.Report(Tok.getLocation(),
2291                      diag::err_mmap_expected_export_wildcard);
2292       consumeToken();
2293       break;
2294
2295     case MMToken::ExplicitKeyword:
2296     case MMToken::ModuleKeyword:
2297     case MMToken::HeaderKeyword:
2298     case MMToken::PrivateKeyword:
2299     case MMToken::UmbrellaKeyword:
2300     default:
2301       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
2302           << (ActiveModule != nullptr);
2303       consumeToken();
2304       break;
2305     }
2306   } while (!Done);
2307
2308   if (Tok.is(MMToken::RBrace))
2309     consumeToken();
2310   else {
2311     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
2312     Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
2313     HadError = true;
2314   }
2315 }
2316
2317 /// \brief Parse optional attributes.
2318 ///
2319 ///   attributes:
2320 ///     attribute attributes
2321 ///     attribute
2322 ///
2323 ///   attribute:
2324 ///     [ identifier ]
2325 ///
2326 /// \param Attrs Will be filled in with the parsed attributes.
2327 ///
2328 /// \returns true if an error occurred, false otherwise.
2329 bool ModuleMapParser::parseOptionalAttributes(Attributes &Attrs) {
2330   bool HadError = false;
2331
2332   while (Tok.is(MMToken::LSquare)) {
2333     // Consume the '['.
2334     SourceLocation LSquareLoc = consumeToken();
2335
2336     // Check whether we have an attribute name here.
2337     if (!Tok.is(MMToken::Identifier)) {
2338       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_attribute);
2339       skipUntil(MMToken::RSquare);
2340       if (Tok.is(MMToken::RSquare))
2341         consumeToken();
2342       HadError = true;
2343     }
2344
2345     // Decode the attribute name.
2346     AttributeKind Attribute
2347       = llvm::StringSwitch<AttributeKind>(Tok.getString())
2348           .Case("exhaustive", AT_exhaustive)
2349           .Case("extern_c", AT_extern_c)
2350           .Case("system", AT_system)
2351           .Default(AT_unknown);
2352     switch (Attribute) {
2353     case AT_unknown:
2354       Diags.Report(Tok.getLocation(), diag::warn_mmap_unknown_attribute)
2355         << Tok.getString();
2356       break;
2357
2358     case AT_system:
2359       Attrs.IsSystem = true;
2360       break;
2361
2362     case AT_extern_c:
2363       Attrs.IsExternC = true;
2364       break;
2365
2366     case AT_exhaustive:
2367       Attrs.IsExhaustive = true;
2368       break;
2369     }
2370     consumeToken();
2371
2372     // Consume the ']'.
2373     if (!Tok.is(MMToken::RSquare)) {
2374       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rsquare);
2375       Diags.Report(LSquareLoc, diag::note_mmap_lsquare_match);
2376       skipUntil(MMToken::RSquare);
2377       HadError = true;
2378     }
2379
2380     if (Tok.is(MMToken::RSquare))
2381       consumeToken();
2382   }
2383
2384   return HadError;
2385 }
2386
2387 /// \brief Parse a module map file.
2388 ///
2389 ///   module-map-file:
2390 ///     module-declaration*
2391 bool ModuleMapParser::parseModuleMapFile() {
2392   do {
2393     switch (Tok.Kind) {
2394     case MMToken::EndOfFile:
2395       return HadError;
2396
2397     case MMToken::ExplicitKeyword:
2398     case MMToken::ExternKeyword:
2399     case MMToken::ModuleKeyword:
2400     case MMToken::FrameworkKeyword:
2401       parseModuleDecl();
2402       break;
2403
2404     case MMToken::Comma:
2405     case MMToken::ConfigMacros:
2406     case MMToken::Conflict:
2407     case MMToken::Exclaim:
2408     case MMToken::ExcludeKeyword:
2409     case MMToken::ExportKeyword:
2410     case MMToken::HeaderKeyword:
2411     case MMToken::Identifier:
2412     case MMToken::LBrace:
2413     case MMToken::LinkKeyword:
2414     case MMToken::LSquare:
2415     case MMToken::Period:
2416     case MMToken::PrivateKeyword:
2417     case MMToken::RBrace:
2418     case MMToken::RSquare:
2419     case MMToken::RequiresKeyword:
2420     case MMToken::Star:
2421     case MMToken::StringLiteral:
2422     case MMToken::TextualKeyword:
2423     case MMToken::UmbrellaKeyword:
2424     case MMToken::UseKeyword:
2425       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
2426       HadError = true;
2427       consumeToken();
2428       break;
2429     }
2430   } while (true);
2431 }
2432
2433 bool ModuleMap::parseModuleMapFile(const FileEntry *File, bool IsSystem,
2434                                    const DirectoryEntry *Dir,
2435                                    SourceLocation ExternModuleLoc) {
2436   llvm::DenseMap<const FileEntry *, bool>::iterator Known
2437     = ParsedModuleMap.find(File);
2438   if (Known != ParsedModuleMap.end())
2439     return Known->second;
2440
2441   assert(Target && "Missing target information");
2442   auto FileCharacter = IsSystem ? SrcMgr::C_System : SrcMgr::C_User;
2443   FileID ID = SourceMgr.createFileID(File, ExternModuleLoc, FileCharacter);
2444   const llvm::MemoryBuffer *Buffer = SourceMgr.getBuffer(ID);
2445   if (!Buffer)
2446     return ParsedModuleMap[File] = true;
2447
2448   // Parse this module map file.
2449   Lexer L(ID, SourceMgr.getBuffer(ID), SourceMgr, MMapLangOpts);
2450   SourceLocation Start = L.getSourceLocation();
2451   ModuleMapParser Parser(L, SourceMgr, Target, Diags, *this, File, Dir,
2452                          BuiltinIncludeDir, IsSystem);
2453   bool Result = Parser.parseModuleMapFile();
2454   ParsedModuleMap[File] = Result;
2455
2456   // Notify callbacks that we parsed it.
2457   for (const auto &Cb : Callbacks)
2458     Cb->moduleMapFileRead(Start, *File, IsSystem);
2459   return Result;
2460 }