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/LexDiagnostic.h"
23#include "clang/Lex/Lexer.h"
24#include "clang/Lex/LiteralSupport.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/ADT/StringSwitch.h"
27#include "llvm/Support/Allocator.h"
28#include "llvm/Support/FileSystem.h"
29#include "llvm/Support/Host.h"
30#include "llvm/Support/PathV2.h"
31#include "llvm/Support/raw_ostream.h"
32#include <stdlib.h>
33#if defined(LLVM_ON_UNIX)
34#include <limits.h>
35#endif
36using namespace clang;
37
38Module::ExportDecl
39ModuleMap::resolveExport(Module *Mod,
40                         const Module::UnresolvedExportDecl &Unresolved,
41                         bool Complain) const {
42  // We may have just a wildcard.
43  if (Unresolved.Id.empty()) {
44    assert(Unresolved.Wildcard && "Invalid unresolved export");
45    return Module::ExportDecl(0, true);
46  }
47
48  // Find the starting module.
49  Module *Context = lookupModuleUnqualified(Unresolved.Id[0].first, Mod);
50  if (!Context) {
51    if (Complain)
52      Diags->Report(Unresolved.Id[0].second,
53                    diag::err_mmap_missing_module_unqualified)
54        << Unresolved.Id[0].first << Mod->getFullModuleName();
55
56    return Module::ExportDecl();
57  }
58
59  // Dig into the module path.
60  for (unsigned I = 1, N = Unresolved.Id.size(); I != N; ++I) {
61    Module *Sub = lookupModuleQualified(Unresolved.Id[I].first,
62                                        Context);
63    if (!Sub) {
64      if (Complain)
65        Diags->Report(Unresolved.Id[I].second,
66                      diag::err_mmap_missing_module_qualified)
67          << Unresolved.Id[I].first << Context->getFullModuleName()
68          << SourceRange(Unresolved.Id[0].second, Unresolved.Id[I-1].second);
69
70      return Module::ExportDecl();
71    }
72
73    Context = Sub;
74  }
75
76  return Module::ExportDecl(Context, Unresolved.Wildcard);
77}
78
79ModuleMap::ModuleMap(FileManager &FileMgr, const DiagnosticConsumer &DC,
80                     const LangOptions &LangOpts, const TargetInfo *Target,
81                     HeaderSearch &HeaderInfo)
82  : LangOpts(LangOpts), Target(Target), HeaderInfo(HeaderInfo),
83    BuiltinIncludeDir(0)
84{
85  IntrusiveRefCntPtr<DiagnosticIDs> DiagIDs(new DiagnosticIDs);
86  Diags = IntrusiveRefCntPtr<DiagnosticsEngine>(
87            new DiagnosticsEngine(DiagIDs, new DiagnosticOptions));
88  Diags->setClient(DC.clone(*Diags), /*ShouldOwnClient=*/true);
89  SourceMgr = new SourceManager(*Diags, FileMgr);
90}
91
92ModuleMap::~ModuleMap() {
93  for (llvm::StringMap<Module *>::iterator I = Modules.begin(),
94                                        IEnd = Modules.end();
95       I != IEnd; ++I) {
96    delete I->getValue();
97  }
98
99  delete SourceMgr;
100}
101
102void ModuleMap::setTarget(const TargetInfo &Target) {
103  assert((!this->Target || this->Target == &Target) &&
104         "Improper target override");
105  this->Target = &Target;
106}
107
108/// \brief "Sanitize" a filename so that it can be used as an identifier.
109static StringRef sanitizeFilenameAsIdentifier(StringRef Name,
110                                              SmallVectorImpl<char> &Buffer) {
111  if (Name.empty())
112    return Name;
113
114  if (!isValidIdentifier(Name)) {
115    // If we don't already have something with the form of an identifier,
116    // create a buffer with the sanitized name.
117    Buffer.clear();
118    if (isDigit(Name[0]))
119      Buffer.push_back('_');
120    Buffer.reserve(Buffer.size() + Name.size());
121    for (unsigned I = 0, N = Name.size(); I != N; ++I) {
122      if (isIdentifierBody(Name[I]))
123        Buffer.push_back(Name[I]);
124      else
125        Buffer.push_back('_');
126    }
127
128    Name = StringRef(Buffer.data(), Buffer.size());
129  }
130
131  while (llvm::StringSwitch<bool>(Name)
132#define KEYWORD(Keyword,Conditions) .Case(#Keyword, true)
133#define ALIAS(Keyword, AliasOf, Conditions) .Case(Keyword, true)
134#include "clang/Basic/TokenKinds.def"
135           .Default(false)) {
136    if (Name.data() != Buffer.data())
137      Buffer.append(Name.begin(), Name.end());
138    Buffer.push_back('_');
139    Name = StringRef(Buffer.data(), Buffer.size());
140  }
141
142  return Name;
143}
144
145Module *ModuleMap::findModuleForHeader(const FileEntry *File) {
146  HeadersMap::iterator Known = Headers.find(File);
147  if (Known != Headers.end()) {
148    // If a header is not available, don't report that it maps to anything.
149    if (!Known->second.isAvailable())
150      return 0;
151
152    return Known->second.getModule();
153  }
154
155  const DirectoryEntry *Dir = File->getDir();
156  SmallVector<const DirectoryEntry *, 2> SkippedDirs;
157
158  // Note: as an egregious but useful hack we use the real path here, because
159  // frameworks moving from top-level frameworks to embedded frameworks tend
160  // to be symlinked from the top-level location to the embedded location,
161  // and we need to resolve lookups as if we had found the embedded location.
162  StringRef DirName = SourceMgr->getFileManager().getCanonicalName(Dir);
163
164  // Keep walking up the directory hierarchy, looking for a directory with
165  // an umbrella header.
166  do {
167    llvm::DenseMap<const DirectoryEntry *, Module *>::iterator KnownDir
168      = UmbrellaDirs.find(Dir);
169    if (KnownDir != UmbrellaDirs.end()) {
170      Module *Result = KnownDir->second;
171
172      // Search up the module stack until we find a module with an umbrella
173      // directory.
174      Module *UmbrellaModule = Result;
175      while (!UmbrellaModule->getUmbrellaDir() && UmbrellaModule->Parent)
176        UmbrellaModule = UmbrellaModule->Parent;
177
178      if (UmbrellaModule->InferSubmodules) {
179        // Infer submodules for each of the directories we found between
180        // the directory of the umbrella header and the directory where
181        // the actual header is located.
182        bool Explicit = UmbrellaModule->InferExplicitSubmodules;
183
184        for (unsigned I = SkippedDirs.size(); I != 0; --I) {
185          // Find or create the module that corresponds to this directory name.
186          SmallString<32> NameBuf;
187          StringRef Name = sanitizeFilenameAsIdentifier(
188                             llvm::sys::path::stem(SkippedDirs[I-1]->getName()),
189                             NameBuf);
190          Result = findOrCreateModule(Name, Result, /*IsFramework=*/false,
191                                      Explicit).first;
192
193          // Associate the module and the directory.
194          UmbrellaDirs[SkippedDirs[I-1]] = Result;
195
196          // If inferred submodules export everything they import, add a
197          // wildcard to the set of exports.
198          if (UmbrellaModule->InferExportWildcard && Result->Exports.empty())
199            Result->Exports.push_back(Module::ExportDecl(0, true));
200        }
201
202        // Infer a submodule with the same name as this header file.
203        SmallString<32> NameBuf;
204        StringRef Name = sanitizeFilenameAsIdentifier(
205                           llvm::sys::path::stem(File->getName()), NameBuf);
206        Result = findOrCreateModule(Name, Result, /*IsFramework=*/false,
207                                    Explicit).first;
208        Result->addTopHeader(File);
209
210        // If inferred submodules export everything they import, add a
211        // wildcard to the set of exports.
212        if (UmbrellaModule->InferExportWildcard && Result->Exports.empty())
213          Result->Exports.push_back(Module::ExportDecl(0, true));
214      } else {
215        // Record each of the directories we stepped through as being part of
216        // the module we found, since the umbrella header covers them all.
217        for (unsigned I = 0, N = SkippedDirs.size(); I != N; ++I)
218          UmbrellaDirs[SkippedDirs[I]] = Result;
219      }
220
221      Headers[File] = KnownHeader(Result, /*Excluded=*/false);
222
223      // If a header corresponds to an unavailable module, don't report
224      // that it maps to anything.
225      if (!Result->isAvailable())
226        return 0;
227
228      return Result;
229    }
230
231    SkippedDirs.push_back(Dir);
232
233    // Retrieve our parent path.
234    DirName = llvm::sys::path::parent_path(DirName);
235    if (DirName.empty())
236      break;
237
238    // Resolve the parent path to a directory entry.
239    Dir = SourceMgr->getFileManager().getDirectory(DirName);
240  } while (Dir);
241
242  return 0;
243}
244
245bool ModuleMap::isHeaderInUnavailableModule(const FileEntry *Header) const {
246  HeadersMap::const_iterator Known = Headers.find(Header);
247  if (Known != Headers.end())
248    return !Known->second.isAvailable();
249
250  const DirectoryEntry *Dir = Header->getDir();
251  SmallVector<const DirectoryEntry *, 2> SkippedDirs;
252  StringRef DirName = Dir->getName();
253
254  // Keep walking up the directory hierarchy, looking for a directory with
255  // an umbrella header.
256  do {
257    llvm::DenseMap<const DirectoryEntry *, Module *>::const_iterator KnownDir
258      = UmbrellaDirs.find(Dir);
259    if (KnownDir != UmbrellaDirs.end()) {
260      Module *Found = KnownDir->second;
261      if (!Found->isAvailable())
262        return true;
263
264      // Search up the module stack until we find a module with an umbrella
265      // directory.
266      Module *UmbrellaModule = Found;
267      while (!UmbrellaModule->getUmbrellaDir() && UmbrellaModule->Parent)
268        UmbrellaModule = UmbrellaModule->Parent;
269
270      if (UmbrellaModule->InferSubmodules) {
271        for (unsigned I = SkippedDirs.size(); I != 0; --I) {
272          // Find or create the module that corresponds to this directory name.
273          SmallString<32> NameBuf;
274          StringRef Name = sanitizeFilenameAsIdentifier(
275                             llvm::sys::path::stem(SkippedDirs[I-1]->getName()),
276                             NameBuf);
277          Found = lookupModuleQualified(Name, Found);
278          if (!Found)
279            return false;
280          if (!Found->isAvailable())
281            return true;
282        }
283
284        // Infer a submodule with the same name as this header file.
285        SmallString<32> NameBuf;
286        StringRef Name = sanitizeFilenameAsIdentifier(
287                           llvm::sys::path::stem(Header->getName()),
288                           NameBuf);
289        Found = lookupModuleQualified(Name, Found);
290        if (!Found)
291          return false;
292      }
293
294      return !Found->isAvailable();
295    }
296
297    SkippedDirs.push_back(Dir);
298
299    // Retrieve our parent path.
300    DirName = llvm::sys::path::parent_path(DirName);
301    if (DirName.empty())
302      break;
303
304    // Resolve the parent path to a directory entry.
305    Dir = SourceMgr->getFileManager().getDirectory(DirName);
306  } while (Dir);
307
308  return false;
309}
310
311Module *ModuleMap::findModule(StringRef Name) const {
312  llvm::StringMap<Module *>::const_iterator Known = Modules.find(Name);
313  if (Known != Modules.end())
314    return Known->getValue();
315
316  return 0;
317}
318
319Module *ModuleMap::lookupModuleUnqualified(StringRef Name,
320                                           Module *Context) const {
321  for(; Context; Context = Context->Parent) {
322    if (Module *Sub = lookupModuleQualified(Name, Context))
323      return Sub;
324  }
325
326  return findModule(Name);
327}
328
329Module *ModuleMap::lookupModuleQualified(StringRef Name, Module *Context) const{
330  if (!Context)
331    return findModule(Name);
332
333  return Context->findSubmodule(Name);
334}
335
336std::pair<Module *, bool>
337ModuleMap::findOrCreateModule(StringRef Name, Module *Parent, bool IsFramework,
338                              bool IsExplicit) {
339  // Try to find an existing module with this name.
340  if (Module *Sub = lookupModuleQualified(Name, Parent))
341    return std::make_pair(Sub, false);
342
343  // Create a new module with this name.
344  Module *Result = new Module(Name, SourceLocation(), Parent, IsFramework,
345                              IsExplicit);
346  if (!Parent)
347    Modules[Name] = Result;
348  return std::make_pair(Result, true);
349}
350
351bool ModuleMap::canInferFrameworkModule(const DirectoryEntry *ParentDir,
352                                        StringRef Name, bool &IsSystem) const {
353  // Check whether we have already looked into the parent directory
354  // for a module map.
355  llvm::DenseMap<const DirectoryEntry *, InferredDirectory>::const_iterator
356    inferred = InferredDirectories.find(ParentDir);
357  if (inferred == InferredDirectories.end())
358    return false;
359
360  if (!inferred->second.InferModules)
361    return false;
362
363  // We're allowed to infer for this directory, but make sure it's okay
364  // to infer this particular module.
365  bool canInfer = std::find(inferred->second.ExcludedModules.begin(),
366                            inferred->second.ExcludedModules.end(),
367                            Name) == inferred->second.ExcludedModules.end();
368
369  if (canInfer && inferred->second.InferSystemModules)
370    IsSystem = true;
371
372  return canInfer;
373}
374
375/// \brief For a framework module, infer the framework against which we
376/// should link.
377static void inferFrameworkLink(Module *Mod, const DirectoryEntry *FrameworkDir,
378                               FileManager &FileMgr) {
379  assert(Mod->IsFramework && "Can only infer linking for framework modules");
380  assert(!Mod->isSubFramework() &&
381         "Can only infer linking for top-level frameworks");
382
383  SmallString<128> LibName;
384  LibName += FrameworkDir->getName();
385  llvm::sys::path::append(LibName, Mod->Name);
386  if (FileMgr.getFile(LibName)) {
387    Mod->LinkLibraries.push_back(Module::LinkLibrary(Mod->Name,
388                                                     /*IsFramework=*/true));
389  }
390}
391
392Module *
393ModuleMap::inferFrameworkModule(StringRef ModuleName,
394                                const DirectoryEntry *FrameworkDir,
395                                bool IsSystem,
396                                Module *Parent) {
397  // Check whether we've already found this module.
398  if (Module *Mod = lookupModuleQualified(ModuleName, Parent))
399    return Mod;
400
401  FileManager &FileMgr = SourceMgr->getFileManager();
402
403  // If the framework has a parent path from which we're allowed to infer
404  // a framework module, do so.
405  if (!Parent) {
406    // Determine whether we're allowed to infer a module map.
407
408    // Note: as an egregious but useful hack we use the real path here, because
409    // we might be looking at an embedded framework that symlinks out to a
410    // top-level framework, and we need to infer as if we were naming the
411    // top-level framework.
412    StringRef FrameworkDirName
413      = SourceMgr->getFileManager().getCanonicalName(FrameworkDir);
414
415    bool canInfer = false;
416    if (llvm::sys::path::has_parent_path(FrameworkDirName)) {
417      // Figure out the parent path.
418      StringRef Parent = llvm::sys::path::parent_path(FrameworkDirName);
419      if (const DirectoryEntry *ParentDir = FileMgr.getDirectory(Parent)) {
420        // Check whether we have already looked into the parent directory
421        // for a module map.
422        llvm::DenseMap<const DirectoryEntry *, InferredDirectory>::const_iterator
423          inferred = InferredDirectories.find(ParentDir);
424        if (inferred == InferredDirectories.end()) {
425          // We haven't looked here before. Load a module map, if there is
426          // one.
427          SmallString<128> ModMapPath = Parent;
428          llvm::sys::path::append(ModMapPath, "module.map");
429          if (const FileEntry *ModMapFile = FileMgr.getFile(ModMapPath)) {
430            parseModuleMapFile(ModMapFile);
431            inferred = InferredDirectories.find(ParentDir);
432          }
433
434          if (inferred == InferredDirectories.end())
435            inferred = InferredDirectories.insert(
436                         std::make_pair(ParentDir, InferredDirectory())).first;
437        }
438
439        if (inferred->second.InferModules) {
440          // We're allowed to infer for this directory, but make sure it's okay
441          // to infer this particular module.
442          StringRef Name = llvm::sys::path::stem(FrameworkDirName);
443          canInfer = std::find(inferred->second.ExcludedModules.begin(),
444                               inferred->second.ExcludedModules.end(),
445                               Name) == inferred->second.ExcludedModules.end();
446
447          if (inferred->second.InferSystemModules)
448            IsSystem = true;
449        }
450      }
451    }
452
453    // If we're not allowed to infer a framework module, don't.
454    if (!canInfer)
455      return 0;
456  }
457
458
459  // Look for an umbrella header.
460  SmallString<128> UmbrellaName = StringRef(FrameworkDir->getName());
461  llvm::sys::path::append(UmbrellaName, "Headers");
462  llvm::sys::path::append(UmbrellaName, ModuleName + ".h");
463  const FileEntry *UmbrellaHeader = FileMgr.getFile(UmbrellaName);
464
465  // FIXME: If there's no umbrella header, we could probably scan the
466  // framework to load *everything*. But, it's not clear that this is a good
467  // idea.
468  if (!UmbrellaHeader)
469    return 0;
470
471  Module *Result = new Module(ModuleName, SourceLocation(), Parent,
472                              /*IsFramework=*/true, /*IsExplicit=*/false);
473  if (IsSystem)
474    Result->IsSystem = IsSystem;
475
476  if (!Parent)
477    Modules[ModuleName] = Result;
478
479  // umbrella header "umbrella-header-name"
480  Result->Umbrella = UmbrellaHeader;
481  Headers[UmbrellaHeader] = KnownHeader(Result, /*Excluded=*/false);
482  UmbrellaDirs[UmbrellaHeader->getDir()] = Result;
483
484  // export *
485  Result->Exports.push_back(Module::ExportDecl(0, true));
486
487  // module * { export * }
488  Result->InferSubmodules = true;
489  Result->InferExportWildcard = true;
490
491  // Look for subframeworks.
492  llvm::error_code EC;
493  SmallString<128> SubframeworksDirName
494    = StringRef(FrameworkDir->getName());
495  llvm::sys::path::append(SubframeworksDirName, "Frameworks");
496  SmallString<128> SubframeworksDirNameNative;
497  llvm::sys::path::native(SubframeworksDirName.str(),
498                          SubframeworksDirNameNative);
499  for (llvm::sys::fs::directory_iterator
500         Dir(SubframeworksDirNameNative.str(), EC), DirEnd;
501       Dir != DirEnd && !EC; Dir.increment(EC)) {
502    if (!StringRef(Dir->path()).endswith(".framework"))
503      continue;
504
505    if (const DirectoryEntry *SubframeworkDir
506          = FileMgr.getDirectory(Dir->path())) {
507      // Note: as an egregious but useful hack, we use the real path here and
508      // check whether it is actually a subdirectory of the parent directory.
509      // This will not be the case if the 'subframework' is actually a symlink
510      // out to a top-level framework.
511      StringRef SubframeworkDirName = FileMgr.getCanonicalName(SubframeworkDir);
512      bool FoundParent = false;
513      do {
514        // Get the parent directory name.
515        SubframeworkDirName
516          = llvm::sys::path::parent_path(SubframeworkDirName);
517        if (SubframeworkDirName.empty())
518          break;
519
520        if (FileMgr.getDirectory(SubframeworkDirName) == FrameworkDir) {
521          FoundParent = true;
522          break;
523        }
524      } while (true);
525
526      if (!FoundParent)
527        continue;
528
529      // FIXME: Do we want to warn about subframeworks without umbrella headers?
530      SmallString<32> NameBuf;
531      inferFrameworkModule(sanitizeFilenameAsIdentifier(
532                             llvm::sys::path::stem(Dir->path()), NameBuf),
533                           SubframeworkDir, IsSystem, Result);
534    }
535  }
536
537  // If the module is a top-level framework, automatically link against the
538  // framework.
539  if (!Result->isSubFramework()) {
540    inferFrameworkLink(Result, FrameworkDir, FileMgr);
541  }
542
543  return Result;
544}
545
546void ModuleMap::setUmbrellaHeader(Module *Mod, const FileEntry *UmbrellaHeader){
547  Headers[UmbrellaHeader] = KnownHeader(Mod, /*Excluded=*/false);
548  Mod->Umbrella = UmbrellaHeader;
549  UmbrellaDirs[UmbrellaHeader->getDir()] = Mod;
550}
551
552void ModuleMap::setUmbrellaDir(Module *Mod, const DirectoryEntry *UmbrellaDir) {
553  Mod->Umbrella = UmbrellaDir;
554  UmbrellaDirs[UmbrellaDir] = Mod;
555}
556
557void ModuleMap::addHeader(Module *Mod, const FileEntry *Header,
558                          bool Excluded) {
559  if (Excluded) {
560    Mod->ExcludedHeaders.push_back(Header);
561  } else {
562    Mod->Headers.push_back(Header);
563    HeaderInfo.MarkFileModuleHeader(Header);
564  }
565  Headers[Header] = KnownHeader(Mod, Excluded);
566}
567
568const FileEntry *
569ModuleMap::getContainingModuleMapFile(Module *Module) const {
570  if (Module->DefinitionLoc.isInvalid() || !SourceMgr)
571    return 0;
572
573  return SourceMgr->getFileEntryForID(
574           SourceMgr->getFileID(Module->DefinitionLoc));
575}
576
577void ModuleMap::dump() {
578  llvm::errs() << "Modules:";
579  for (llvm::StringMap<Module *>::iterator M = Modules.begin(),
580                                        MEnd = Modules.end();
581       M != MEnd; ++M)
582    M->getValue()->print(llvm::errs(), 2);
583
584  llvm::errs() << "Headers:";
585  for (HeadersMap::iterator H = Headers.begin(), HEnd = Headers.end();
586       H != HEnd; ++H) {
587    llvm::errs() << "  \"" << H->first->getName() << "\" -> "
588                 << H->second.getModule()->getFullModuleName() << "\n";
589  }
590}
591
592bool ModuleMap::resolveExports(Module *Mod, bool Complain) {
593  bool HadError = false;
594  for (unsigned I = 0, N = Mod->UnresolvedExports.size(); I != N; ++I) {
595    Module::ExportDecl Export = resolveExport(Mod, Mod->UnresolvedExports[I],
596                                              Complain);
597    if (Export.getPointer() || Export.getInt())
598      Mod->Exports.push_back(Export);
599    else
600      HadError = true;
601  }
602  Mod->UnresolvedExports.clear();
603  return HadError;
604}
605
606Module *ModuleMap::inferModuleFromLocation(FullSourceLoc Loc) {
607  if (Loc.isInvalid())
608    return 0;
609
610  // Use the expansion location to determine which module we're in.
611  FullSourceLoc ExpansionLoc = Loc.getExpansionLoc();
612  if (!ExpansionLoc.isFileID())
613    return 0;
614
615
616  const SourceManager &SrcMgr = Loc.getManager();
617  FileID ExpansionFileID = ExpansionLoc.getFileID();
618
619  while (const FileEntry *ExpansionFile
620           = SrcMgr.getFileEntryForID(ExpansionFileID)) {
621    // Find the module that owns this header (if any).
622    if (Module *Mod = findModuleForHeader(ExpansionFile))
623      return Mod;
624
625    // No module owns this header, so look up the inclusion chain to see if
626    // any included header has an associated module.
627    SourceLocation IncludeLoc = SrcMgr.getIncludeLoc(ExpansionFileID);
628    if (IncludeLoc.isInvalid())
629      return 0;
630
631    ExpansionFileID = SrcMgr.getFileID(IncludeLoc);
632  }
633
634  return 0;
635}
636
637//----------------------------------------------------------------------------//
638// Module map file parser
639//----------------------------------------------------------------------------//
640
641namespace clang {
642  /// \brief A token in a module map file.
643  struct MMToken {
644    enum TokenKind {
645      Comma,
646      EndOfFile,
647      HeaderKeyword,
648      Identifier,
649      ExcludeKeyword,
650      ExplicitKeyword,
651      ExportKeyword,
652      FrameworkKeyword,
653      LinkKeyword,
654      ModuleKeyword,
655      Period,
656      UmbrellaKeyword,
657      RequiresKeyword,
658      Star,
659      StringLiteral,
660      LBrace,
661      RBrace,
662      LSquare,
663      RSquare
664    } Kind;
665
666    unsigned Location;
667    unsigned StringLength;
668    const char *StringData;
669
670    void clear() {
671      Kind = EndOfFile;
672      Location = 0;
673      StringLength = 0;
674      StringData = 0;
675    }
676
677    bool is(TokenKind K) const { return Kind == K; }
678
679    SourceLocation getLocation() const {
680      return SourceLocation::getFromRawEncoding(Location);
681    }
682
683    StringRef getString() const {
684      return StringRef(StringData, StringLength);
685    }
686  };
687
688  /// \brief The set of attributes that can be attached to a module.
689  struct Attributes {
690    Attributes() : IsSystem() { }
691
692    /// \brief Whether this is a system module.
693    unsigned IsSystem : 1;
694  };
695
696
697  class ModuleMapParser {
698    Lexer &L;
699    SourceManager &SourceMgr;
700
701    /// \brief Default target information, used only for string literal
702    /// parsing.
703    const TargetInfo *Target;
704
705    DiagnosticsEngine &Diags;
706    ModuleMap &Map;
707
708    /// \brief The directory that this module map resides in.
709    const DirectoryEntry *Directory;
710
711    /// \brief The directory containing Clang-supplied headers.
712    const DirectoryEntry *BuiltinIncludeDir;
713
714    /// \brief Whether an error occurred.
715    bool HadError;
716
717    /// \brief Stores string data for the various string literals referenced
718    /// during parsing.
719    llvm::BumpPtrAllocator StringData;
720
721    /// \brief The current token.
722    MMToken Tok;
723
724    /// \brief The active module.
725    Module *ActiveModule;
726
727    /// \brief Consume the current token and return its location.
728    SourceLocation consumeToken();
729
730    /// \brief Skip tokens until we reach the a token with the given kind
731    /// (or the end of the file).
732    void skipUntil(MMToken::TokenKind K);
733
734    typedef SmallVector<std::pair<std::string, SourceLocation>, 2> ModuleId;
735    bool parseModuleId(ModuleId &Id);
736    void parseModuleDecl();
737    void parseRequiresDecl();
738    void parseHeaderDecl(SourceLocation UmbrellaLoc, SourceLocation ExcludeLoc);
739    void parseUmbrellaDirDecl(SourceLocation UmbrellaLoc);
740    void parseExportDecl();
741    void parseLinkDecl();
742    void parseInferredModuleDecl(bool Framework, bool Explicit);
743    bool parseOptionalAttributes(Attributes &Attrs);
744
745    const DirectoryEntry *getOverriddenHeaderSearchDir();
746
747  public:
748    explicit ModuleMapParser(Lexer &L, SourceManager &SourceMgr,
749                             const TargetInfo *Target,
750                             DiagnosticsEngine &Diags,
751                             ModuleMap &Map,
752                             const DirectoryEntry *Directory,
753                             const DirectoryEntry *BuiltinIncludeDir)
754      : L(L), SourceMgr(SourceMgr), Target(Target), Diags(Diags), Map(Map),
755        Directory(Directory), BuiltinIncludeDir(BuiltinIncludeDir),
756        HadError(false), ActiveModule(0)
757    {
758      Tok.clear();
759      consumeToken();
760    }
761
762    bool parseModuleMapFile();
763  };
764}
765
766SourceLocation ModuleMapParser::consumeToken() {
767retry:
768  SourceLocation Result = Tok.getLocation();
769  Tok.clear();
770
771  Token LToken;
772  L.LexFromRawLexer(LToken);
773  Tok.Location = LToken.getLocation().getRawEncoding();
774  switch (LToken.getKind()) {
775  case tok::raw_identifier:
776    Tok.StringData = LToken.getRawIdentifierData();
777    Tok.StringLength = LToken.getLength();
778    Tok.Kind = llvm::StringSwitch<MMToken::TokenKind>(Tok.getString())
779                 .Case("header", MMToken::HeaderKeyword)
780                 .Case("exclude", MMToken::ExcludeKeyword)
781                 .Case("explicit", MMToken::ExplicitKeyword)
782                 .Case("export", MMToken::ExportKeyword)
783                 .Case("framework", MMToken::FrameworkKeyword)
784                 .Case("link", MMToken::LinkKeyword)
785                 .Case("module", MMToken::ModuleKeyword)
786                 .Case("requires", MMToken::RequiresKeyword)
787                 .Case("umbrella", MMToken::UmbrellaKeyword)
788                 .Default(MMToken::Identifier);
789    break;
790
791  case tok::comma:
792    Tok.Kind = MMToken::Comma;
793    break;
794
795  case tok::eof:
796    Tok.Kind = MMToken::EndOfFile;
797    break;
798
799  case tok::l_brace:
800    Tok.Kind = MMToken::LBrace;
801    break;
802
803  case tok::l_square:
804    Tok.Kind = MMToken::LSquare;
805    break;
806
807  case tok::period:
808    Tok.Kind = MMToken::Period;
809    break;
810
811  case tok::r_brace:
812    Tok.Kind = MMToken::RBrace;
813    break;
814
815  case tok::r_square:
816    Tok.Kind = MMToken::RSquare;
817    break;
818
819  case tok::star:
820    Tok.Kind = MMToken::Star;
821    break;
822
823  case tok::string_literal: {
824    if (LToken.hasUDSuffix()) {
825      Diags.Report(LToken.getLocation(), diag::err_invalid_string_udl);
826      HadError = true;
827      goto retry;
828    }
829
830    // Parse the string literal.
831    LangOptions LangOpts;
832    StringLiteralParser StringLiteral(&LToken, 1, SourceMgr, LangOpts, *Target);
833    if (StringLiteral.hadError)
834      goto retry;
835
836    // Copy the string literal into our string data allocator.
837    unsigned Length = StringLiteral.GetStringLength();
838    char *Saved = StringData.Allocate<char>(Length + 1);
839    memcpy(Saved, StringLiteral.GetString().data(), Length);
840    Saved[Length] = 0;
841
842    // Form the token.
843    Tok.Kind = MMToken::StringLiteral;
844    Tok.StringData = Saved;
845    Tok.StringLength = Length;
846    break;
847  }
848
849  case tok::comment:
850    goto retry;
851
852  default:
853    Diags.Report(LToken.getLocation(), diag::err_mmap_unknown_token);
854    HadError = true;
855    goto retry;
856  }
857
858  return Result;
859}
860
861void ModuleMapParser::skipUntil(MMToken::TokenKind K) {
862  unsigned braceDepth = 0;
863  unsigned squareDepth = 0;
864  do {
865    switch (Tok.Kind) {
866    case MMToken::EndOfFile:
867      return;
868
869    case MMToken::LBrace:
870      if (Tok.is(K) && braceDepth == 0 && squareDepth == 0)
871        return;
872
873      ++braceDepth;
874      break;
875
876    case MMToken::LSquare:
877      if (Tok.is(K) && braceDepth == 0 && squareDepth == 0)
878        return;
879
880      ++squareDepth;
881      break;
882
883    case MMToken::RBrace:
884      if (braceDepth > 0)
885        --braceDepth;
886      else if (Tok.is(K))
887        return;
888      break;
889
890    case MMToken::RSquare:
891      if (squareDepth > 0)
892        --squareDepth;
893      else if (Tok.is(K))
894        return;
895      break;
896
897    default:
898      if (braceDepth == 0 && squareDepth == 0 && Tok.is(K))
899        return;
900      break;
901    }
902
903   consumeToken();
904  } while (true);
905}
906
907/// \brief Parse a module-id.
908///
909///   module-id:
910///     identifier
911///     identifier '.' module-id
912///
913/// \returns true if an error occurred, false otherwise.
914bool ModuleMapParser::parseModuleId(ModuleId &Id) {
915  Id.clear();
916  do {
917    if (Tok.is(MMToken::Identifier)) {
918      Id.push_back(std::make_pair(Tok.getString(), Tok.getLocation()));
919      consumeToken();
920    } else {
921      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module_name);
922      return true;
923    }
924
925    if (!Tok.is(MMToken::Period))
926      break;
927
928    consumeToken();
929  } while (true);
930
931  return false;
932}
933
934namespace {
935  /// \brief Enumerates the known attributes.
936  enum AttributeKind {
937    /// \brief An unknown attribute.
938    AT_unknown,
939    /// \brief The 'system' attribute.
940    AT_system
941  };
942}
943
944/// \brief Parse a module declaration.
945///
946///   module-declaration:
947///     'explicit'[opt] 'framework'[opt] 'module' module-id attributes[opt]
948///       { module-member* }
949///
950///   module-member:
951///     requires-declaration
952///     header-declaration
953///     submodule-declaration
954///     export-declaration
955///     link-declaration
956///
957///   submodule-declaration:
958///     module-declaration
959///     inferred-submodule-declaration
960void ModuleMapParser::parseModuleDecl() {
961  assert(Tok.is(MMToken::ExplicitKeyword) || Tok.is(MMToken::ModuleKeyword) ||
962         Tok.is(MMToken::FrameworkKeyword));
963  // Parse 'explicit' or 'framework' keyword, if present.
964  SourceLocation ExplicitLoc;
965  bool Explicit = false;
966  bool Framework = false;
967
968  // Parse 'explicit' keyword, if present.
969  if (Tok.is(MMToken::ExplicitKeyword)) {
970    ExplicitLoc = consumeToken();
971    Explicit = true;
972  }
973
974  // Parse 'framework' keyword, if present.
975  if (Tok.is(MMToken::FrameworkKeyword)) {
976    consumeToken();
977    Framework = true;
978  }
979
980  // Parse 'module' keyword.
981  if (!Tok.is(MMToken::ModuleKeyword)) {
982    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
983    consumeToken();
984    HadError = true;
985    return;
986  }
987  consumeToken(); // 'module' keyword
988
989  // If we have a wildcard for the module name, this is an inferred submodule.
990  // Parse it.
991  if (Tok.is(MMToken::Star))
992    return parseInferredModuleDecl(Framework, Explicit);
993
994  // Parse the module name.
995  ModuleId Id;
996  if (parseModuleId(Id)) {
997    HadError = true;
998    return;
999  }
1000
1001  if (ActiveModule) {
1002    if (Id.size() > 1) {
1003      Diags.Report(Id.front().second, diag::err_mmap_nested_submodule_id)
1004        << SourceRange(Id.front().second, Id.back().second);
1005
1006      HadError = true;
1007      return;
1008    }
1009  } else if (Id.size() == 1 && Explicit) {
1010    // Top-level modules can't be explicit.
1011    Diags.Report(ExplicitLoc, diag::err_mmap_explicit_top_level);
1012    Explicit = false;
1013    ExplicitLoc = SourceLocation();
1014    HadError = true;
1015  }
1016
1017  Module *PreviousActiveModule = ActiveModule;
1018  if (Id.size() > 1) {
1019    // This module map defines a submodule. Go find the module of which it
1020    // is a submodule.
1021    ActiveModule = 0;
1022    for (unsigned I = 0, N = Id.size() - 1; I != N; ++I) {
1023      if (Module *Next = Map.lookupModuleQualified(Id[I].first, ActiveModule)) {
1024        ActiveModule = Next;
1025        continue;
1026      }
1027
1028      if (ActiveModule) {
1029        Diags.Report(Id[I].second, diag::err_mmap_missing_module_qualified)
1030          << Id[I].first << ActiveModule->getTopLevelModule();
1031      } else {
1032        Diags.Report(Id[I].second, diag::err_mmap_expected_module_name);
1033      }
1034      HadError = true;
1035      return;
1036    }
1037  }
1038
1039  StringRef ModuleName = Id.back().first;
1040  SourceLocation ModuleNameLoc = Id.back().second;
1041
1042  // Parse the optional attribute list.
1043  Attributes Attrs;
1044  parseOptionalAttributes(Attrs);
1045
1046  // Parse the opening brace.
1047  if (!Tok.is(MMToken::LBrace)) {
1048    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_lbrace)
1049      << ModuleName;
1050    HadError = true;
1051    return;
1052  }
1053  SourceLocation LBraceLoc = consumeToken();
1054
1055  // Determine whether this (sub)module has already been defined.
1056  if (Module *Existing = Map.lookupModuleQualified(ModuleName, ActiveModule)) {
1057    if (Existing->DefinitionLoc.isInvalid() && !ActiveModule) {
1058      // Skip the module definition.
1059      skipUntil(MMToken::RBrace);
1060      if (Tok.is(MMToken::RBrace))
1061        consumeToken();
1062      else {
1063        Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
1064        Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
1065        HadError = true;
1066      }
1067      return;
1068    }
1069
1070    Diags.Report(ModuleNameLoc, diag::err_mmap_module_redefinition)
1071      << ModuleName;
1072    Diags.Report(Existing->DefinitionLoc, diag::note_mmap_prev_definition);
1073
1074    // Skip the module definition.
1075    skipUntil(MMToken::RBrace);
1076    if (Tok.is(MMToken::RBrace))
1077      consumeToken();
1078
1079    HadError = true;
1080    return;
1081  }
1082
1083  // Start defining this module.
1084  ActiveModule = Map.findOrCreateModule(ModuleName, ActiveModule, Framework,
1085                                        Explicit).first;
1086  ActiveModule->DefinitionLoc = ModuleNameLoc;
1087  if (Attrs.IsSystem)
1088    ActiveModule->IsSystem = true;
1089
1090  bool Done = false;
1091  do {
1092    switch (Tok.Kind) {
1093    case MMToken::EndOfFile:
1094    case MMToken::RBrace:
1095      Done = true;
1096      break;
1097
1098    case MMToken::ExplicitKeyword:
1099    case MMToken::FrameworkKeyword:
1100    case MMToken::ModuleKeyword:
1101      parseModuleDecl();
1102      break;
1103
1104    case MMToken::ExportKeyword:
1105      parseExportDecl();
1106      break;
1107
1108    case MMToken::RequiresKeyword:
1109      parseRequiresDecl();
1110      break;
1111
1112    case MMToken::UmbrellaKeyword: {
1113      SourceLocation UmbrellaLoc = consumeToken();
1114      if (Tok.is(MMToken::HeaderKeyword))
1115        parseHeaderDecl(UmbrellaLoc, SourceLocation());
1116      else
1117        parseUmbrellaDirDecl(UmbrellaLoc);
1118      break;
1119    }
1120
1121    case MMToken::ExcludeKeyword: {
1122      SourceLocation ExcludeLoc = consumeToken();
1123      if (Tok.is(MMToken::HeaderKeyword)) {
1124        parseHeaderDecl(SourceLocation(), ExcludeLoc);
1125      } else {
1126        Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1127          << "exclude";
1128      }
1129      break;
1130    }
1131
1132    case MMToken::HeaderKeyword:
1133      parseHeaderDecl(SourceLocation(), SourceLocation());
1134      break;
1135
1136    case MMToken::LinkKeyword:
1137      parseLinkDecl();
1138      break;
1139
1140    default:
1141      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_member);
1142      consumeToken();
1143      break;
1144    }
1145  } while (!Done);
1146
1147  if (Tok.is(MMToken::RBrace))
1148    consumeToken();
1149  else {
1150    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
1151    Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
1152    HadError = true;
1153  }
1154
1155  // If the active module is a top-level framework, and there are no link
1156  // libraries, automatically link against the framework.
1157  if (ActiveModule->IsFramework && !ActiveModule->isSubFramework() &&
1158      ActiveModule->LinkLibraries.empty()) {
1159    inferFrameworkLink(ActiveModule, Directory, SourceMgr.getFileManager());
1160  }
1161
1162  // We're done parsing this module. Pop back to the previous module.
1163  ActiveModule = PreviousActiveModule;
1164}
1165
1166/// \brief Parse a requires declaration.
1167///
1168///   requires-declaration:
1169///     'requires' feature-list
1170///
1171///   feature-list:
1172///     identifier ',' feature-list
1173///     identifier
1174void ModuleMapParser::parseRequiresDecl() {
1175  assert(Tok.is(MMToken::RequiresKeyword));
1176
1177  // Parse 'requires' keyword.
1178  consumeToken();
1179
1180  // Parse the feature-list.
1181  do {
1182    if (!Tok.is(MMToken::Identifier)) {
1183      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_feature);
1184      HadError = true;
1185      return;
1186    }
1187
1188    // Consume the feature name.
1189    std::string Feature = Tok.getString();
1190    consumeToken();
1191
1192    // Add this feature.
1193    ActiveModule->addRequirement(Feature, Map.LangOpts, *Map.Target);
1194
1195    if (!Tok.is(MMToken::Comma))
1196      break;
1197
1198    // Consume the comma.
1199    consumeToken();
1200  } while (true);
1201}
1202
1203/// \brief Append to \p Paths the set of paths needed to get to the
1204/// subframework in which the given module lives.
1205static void appendSubframeworkPaths(Module *Mod,
1206                                    SmallVectorImpl<char> &Path) {
1207  // Collect the framework names from the given module to the top-level module.
1208  SmallVector<StringRef, 2> Paths;
1209  for (; Mod; Mod = Mod->Parent) {
1210    if (Mod->IsFramework)
1211      Paths.push_back(Mod->Name);
1212  }
1213
1214  if (Paths.empty())
1215    return;
1216
1217  // Add Frameworks/Name.framework for each subframework.
1218  for (unsigned I = Paths.size() - 1; I != 0; --I) {
1219    llvm::sys::path::append(Path, "Frameworks");
1220    llvm::sys::path::append(Path, Paths[I-1] + ".framework");
1221  }
1222}
1223
1224/// \brief Determine whether the given file name is the name of a builtin
1225/// header, supplied by Clang to replace, override, or augment existing system
1226/// headers.
1227static bool isBuiltinHeader(StringRef FileName) {
1228  return llvm::StringSwitch<bool>(FileName)
1229      .Case("float.h", true)
1230      .Case("iso646.h", true)
1231      .Case("limits.h", true)
1232      .Case("stdalign.h", true)
1233      .Case("stdarg.h", true)
1234      .Case("stdbool.h", true)
1235      .Case("stddef.h", true)
1236      .Case("stdint.h", true)
1237      .Case("tgmath.h", true)
1238      .Case("unwind.h", true)
1239      .Default(false);
1240}
1241
1242/// \brief Parse a header declaration.
1243///
1244///   header-declaration:
1245///     'umbrella'[opt] 'header' string-literal
1246///     'exclude'[opt] 'header' string-literal
1247void ModuleMapParser::parseHeaderDecl(SourceLocation UmbrellaLoc,
1248                                      SourceLocation ExcludeLoc) {
1249  assert(Tok.is(MMToken::HeaderKeyword));
1250  consumeToken();
1251
1252  bool Umbrella = UmbrellaLoc.isValid();
1253  bool Exclude = ExcludeLoc.isValid();
1254  assert(!(Umbrella && Exclude) && "Cannot have both 'umbrella' and 'exclude'");
1255  // Parse the header name.
1256  if (!Tok.is(MMToken::StringLiteral)) {
1257    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1258      << "header";
1259    HadError = true;
1260    return;
1261  }
1262  std::string FileName = Tok.getString();
1263  SourceLocation FileNameLoc = consumeToken();
1264
1265  // Check whether we already have an umbrella.
1266  if (Umbrella && ActiveModule->Umbrella) {
1267    Diags.Report(FileNameLoc, diag::err_mmap_umbrella_clash)
1268      << ActiveModule->getFullModuleName();
1269    HadError = true;
1270    return;
1271  }
1272
1273  // Look for this file.
1274  const FileEntry *File = 0;
1275  const FileEntry *BuiltinFile = 0;
1276  SmallString<128> PathName;
1277  if (llvm::sys::path::is_absolute(FileName)) {
1278    PathName = FileName;
1279    File = SourceMgr.getFileManager().getFile(PathName);
1280  } else if (const DirectoryEntry *Dir = getOverriddenHeaderSearchDir()) {
1281    PathName = Dir->getName();
1282    llvm::sys::path::append(PathName, FileName);
1283    File = SourceMgr.getFileManager().getFile(PathName);
1284  } else {
1285    // Search for the header file within the search directory.
1286    PathName = Directory->getName();
1287    unsigned PathLength = PathName.size();
1288
1289    if (ActiveModule->isPartOfFramework()) {
1290      appendSubframeworkPaths(ActiveModule, PathName);
1291
1292      // Check whether this file is in the public headers.
1293      llvm::sys::path::append(PathName, "Headers");
1294      llvm::sys::path::append(PathName, FileName);
1295      File = SourceMgr.getFileManager().getFile(PathName);
1296
1297      if (!File) {
1298        // Check whether this file is in the private headers.
1299        PathName.resize(PathLength);
1300        llvm::sys::path::append(PathName, "PrivateHeaders");
1301        llvm::sys::path::append(PathName, FileName);
1302        File = SourceMgr.getFileManager().getFile(PathName);
1303      }
1304    } else {
1305      // Lookup for normal headers.
1306      llvm::sys::path::append(PathName, FileName);
1307      File = SourceMgr.getFileManager().getFile(PathName);
1308
1309      // If this is a system module with a top-level header, this header
1310      // may have a counterpart (or replacement) in the set of headers
1311      // supplied by Clang. Find that builtin header.
1312      if (ActiveModule->IsSystem && !Umbrella && BuiltinIncludeDir &&
1313          BuiltinIncludeDir != Directory && isBuiltinHeader(FileName)) {
1314        SmallString<128> BuiltinPathName(BuiltinIncludeDir->getName());
1315        llvm::sys::path::append(BuiltinPathName, FileName);
1316        BuiltinFile = SourceMgr.getFileManager().getFile(BuiltinPathName);
1317
1318        // If Clang supplies this header but the underlying system does not,
1319        // just silently swap in our builtin version. Otherwise, we'll end
1320        // up adding both (later).
1321        if (!File && BuiltinFile) {
1322          File = BuiltinFile;
1323          BuiltinFile = 0;
1324        }
1325      }
1326    }
1327  }
1328
1329  // FIXME: We shouldn't be eagerly stat'ing every file named in a module map.
1330  // Come up with a lazy way to do this.
1331  if (File) {
1332    if (ModuleMap::KnownHeader OwningModule = Map.Headers[File]) {
1333      Diags.Report(FileNameLoc, diag::err_mmap_header_conflict)
1334        << FileName << OwningModule.getModule()->getFullModuleName();
1335      HadError = true;
1336    } else if (Umbrella) {
1337      const DirectoryEntry *UmbrellaDir = File->getDir();
1338      if (Module *UmbrellaModule = Map.UmbrellaDirs[UmbrellaDir]) {
1339        Diags.Report(UmbrellaLoc, diag::err_mmap_umbrella_clash)
1340          << UmbrellaModule->getFullModuleName();
1341        HadError = true;
1342      } else {
1343        // Record this umbrella header.
1344        Map.setUmbrellaHeader(ActiveModule, File);
1345      }
1346    } else {
1347      // Record this header.
1348      Map.addHeader(ActiveModule, File, Exclude);
1349
1350      // If there is a builtin counterpart to this file, add it now.
1351      if (BuiltinFile)
1352        Map.addHeader(ActiveModule, BuiltinFile, Exclude);
1353    }
1354  } else if (!Exclude) {
1355    // Ignore excluded header files. They're optional anyway.
1356
1357    Diags.Report(FileNameLoc, diag::err_mmap_header_not_found)
1358      << Umbrella << FileName;
1359    HadError = true;
1360  }
1361}
1362
1363/// \brief Parse an umbrella directory declaration.
1364///
1365///   umbrella-dir-declaration:
1366///     umbrella string-literal
1367void ModuleMapParser::parseUmbrellaDirDecl(SourceLocation UmbrellaLoc) {
1368  // Parse the directory name.
1369  if (!Tok.is(MMToken::StringLiteral)) {
1370    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
1371      << "umbrella";
1372    HadError = true;
1373    return;
1374  }
1375
1376  std::string DirName = Tok.getString();
1377  SourceLocation DirNameLoc = consumeToken();
1378
1379  // Check whether we already have an umbrella.
1380  if (ActiveModule->Umbrella) {
1381    Diags.Report(DirNameLoc, diag::err_mmap_umbrella_clash)
1382      << ActiveModule->getFullModuleName();
1383    HadError = true;
1384    return;
1385  }
1386
1387  // Look for this file.
1388  const DirectoryEntry *Dir = 0;
1389  if (llvm::sys::path::is_absolute(DirName))
1390    Dir = SourceMgr.getFileManager().getDirectory(DirName);
1391  else {
1392    SmallString<128> PathName;
1393    PathName = Directory->getName();
1394    llvm::sys::path::append(PathName, DirName);
1395    Dir = SourceMgr.getFileManager().getDirectory(PathName);
1396  }
1397
1398  if (!Dir) {
1399    Diags.Report(DirNameLoc, diag::err_mmap_umbrella_dir_not_found)
1400      << DirName;
1401    HadError = true;
1402    return;
1403  }
1404
1405  if (Module *OwningModule = Map.UmbrellaDirs[Dir]) {
1406    Diags.Report(UmbrellaLoc, diag::err_mmap_umbrella_clash)
1407      << OwningModule->getFullModuleName();
1408    HadError = true;
1409    return;
1410  }
1411
1412  // Record this umbrella directory.
1413  Map.setUmbrellaDir(ActiveModule, Dir);
1414}
1415
1416/// \brief Parse a module export declaration.
1417///
1418///   export-declaration:
1419///     'export' wildcard-module-id
1420///
1421///   wildcard-module-id:
1422///     identifier
1423///     '*'
1424///     identifier '.' wildcard-module-id
1425void ModuleMapParser::parseExportDecl() {
1426  assert(Tok.is(MMToken::ExportKeyword));
1427  SourceLocation ExportLoc = consumeToken();
1428
1429  // Parse the module-id with an optional wildcard at the end.
1430  ModuleId ParsedModuleId;
1431  bool Wildcard = false;
1432  do {
1433    if (Tok.is(MMToken::Identifier)) {
1434      ParsedModuleId.push_back(std::make_pair(Tok.getString(),
1435                                              Tok.getLocation()));
1436      consumeToken();
1437
1438      if (Tok.is(MMToken::Period)) {
1439        consumeToken();
1440        continue;
1441      }
1442
1443      break;
1444    }
1445
1446    if(Tok.is(MMToken::Star)) {
1447      Wildcard = true;
1448      consumeToken();
1449      break;
1450    }
1451
1452    Diags.Report(Tok.getLocation(), diag::err_mmap_export_module_id);
1453    HadError = true;
1454    return;
1455  } while (true);
1456
1457  Module::UnresolvedExportDecl Unresolved = {
1458    ExportLoc, ParsedModuleId, Wildcard
1459  };
1460  ActiveModule->UnresolvedExports.push_back(Unresolved);
1461}
1462
1463/// \brief Parse a link declaration.
1464///
1465///   module-declaration:
1466///     'link' 'framework'[opt] string-literal
1467void ModuleMapParser::parseLinkDecl() {
1468  assert(Tok.is(MMToken::LinkKeyword));
1469  SourceLocation LinkLoc = consumeToken();
1470
1471  // Parse the optional 'framework' keyword.
1472  bool IsFramework = false;
1473  if (Tok.is(MMToken::FrameworkKeyword)) {
1474    consumeToken();
1475    IsFramework = true;
1476  }
1477
1478  // Parse the library name
1479  if (!Tok.is(MMToken::StringLiteral)) {
1480    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_library_name)
1481      << IsFramework << SourceRange(LinkLoc);
1482    HadError = true;
1483    return;
1484  }
1485
1486  std::string LibraryName = Tok.getString();
1487  consumeToken();
1488  ActiveModule->LinkLibraries.push_back(Module::LinkLibrary(LibraryName,
1489                                                            IsFramework));
1490}
1491
1492/// \brief Parse an inferred module declaration (wildcard modules).
1493///
1494///   module-declaration:
1495///     'explicit'[opt] 'framework'[opt] 'module' * attributes[opt]
1496///       { inferred-module-member* }
1497///
1498///   inferred-module-member:
1499///     'export' '*'
1500///     'exclude' identifier
1501void ModuleMapParser::parseInferredModuleDecl(bool Framework, bool Explicit) {
1502  assert(Tok.is(MMToken::Star));
1503  SourceLocation StarLoc = consumeToken();
1504  bool Failed = false;
1505
1506  // Inferred modules must be submodules.
1507  if (!ActiveModule && !Framework) {
1508    Diags.Report(StarLoc, diag::err_mmap_top_level_inferred_submodule);
1509    Failed = true;
1510  }
1511
1512  if (ActiveModule) {
1513    // Inferred modules must have umbrella directories.
1514    if (!Failed && !ActiveModule->getUmbrellaDir()) {
1515      Diags.Report(StarLoc, diag::err_mmap_inferred_no_umbrella);
1516      Failed = true;
1517    }
1518
1519    // Check for redefinition of an inferred module.
1520    if (!Failed && ActiveModule->InferSubmodules) {
1521      Diags.Report(StarLoc, diag::err_mmap_inferred_redef);
1522      if (ActiveModule->InferredSubmoduleLoc.isValid())
1523        Diags.Report(ActiveModule->InferredSubmoduleLoc,
1524                     diag::note_mmap_prev_definition);
1525      Failed = true;
1526    }
1527
1528    // Check for the 'framework' keyword, which is not permitted here.
1529    if (Framework) {
1530      Diags.Report(StarLoc, diag::err_mmap_inferred_framework_submodule);
1531      Framework = false;
1532    }
1533  } else if (Explicit) {
1534    Diags.Report(StarLoc, diag::err_mmap_explicit_inferred_framework);
1535    Explicit = false;
1536  }
1537
1538  // If there were any problems with this inferred submodule, skip its body.
1539  if (Failed) {
1540    if (Tok.is(MMToken::LBrace)) {
1541      consumeToken();
1542      skipUntil(MMToken::RBrace);
1543      if (Tok.is(MMToken::RBrace))
1544        consumeToken();
1545    }
1546    HadError = true;
1547    return;
1548  }
1549
1550  // Parse optional attributes.
1551  Attributes Attrs;
1552  parseOptionalAttributes(Attrs);
1553
1554  if (ActiveModule) {
1555    // Note that we have an inferred submodule.
1556    ActiveModule->InferSubmodules = true;
1557    ActiveModule->InferredSubmoduleLoc = StarLoc;
1558    ActiveModule->InferExplicitSubmodules = Explicit;
1559  } else {
1560    // We'll be inferring framework modules for this directory.
1561    Map.InferredDirectories[Directory].InferModules = true;
1562    Map.InferredDirectories[Directory].InferSystemModules = Attrs.IsSystem;
1563  }
1564
1565  // Parse the opening brace.
1566  if (!Tok.is(MMToken::LBrace)) {
1567    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_lbrace_wildcard);
1568    HadError = true;
1569    return;
1570  }
1571  SourceLocation LBraceLoc = consumeToken();
1572
1573  // Parse the body of the inferred submodule.
1574  bool Done = false;
1575  do {
1576    switch (Tok.Kind) {
1577    case MMToken::EndOfFile:
1578    case MMToken::RBrace:
1579      Done = true;
1580      break;
1581
1582    case MMToken::ExcludeKeyword: {
1583      if (ActiveModule) {
1584        Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
1585          << (ActiveModule != 0);
1586        consumeToken();
1587        break;
1588      }
1589
1590      consumeToken();
1591      if (!Tok.is(MMToken::Identifier)) {
1592        Diags.Report(Tok.getLocation(), diag::err_mmap_missing_exclude_name);
1593        break;
1594      }
1595
1596      Map.InferredDirectories[Directory].ExcludedModules
1597        .push_back(Tok.getString());
1598      consumeToken();
1599      break;
1600    }
1601
1602    case MMToken::ExportKeyword:
1603      if (!ActiveModule) {
1604        Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
1605          << (ActiveModule != 0);
1606        consumeToken();
1607        break;
1608      }
1609
1610      consumeToken();
1611      if (Tok.is(MMToken::Star))
1612        ActiveModule->InferExportWildcard = true;
1613      else
1614        Diags.Report(Tok.getLocation(),
1615                     diag::err_mmap_expected_export_wildcard);
1616      consumeToken();
1617      break;
1618
1619    case MMToken::ExplicitKeyword:
1620    case MMToken::ModuleKeyword:
1621    case MMToken::HeaderKeyword:
1622    case MMToken::UmbrellaKeyword:
1623    default:
1624      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_inferred_member)
1625          << (ActiveModule != 0);
1626      consumeToken();
1627      break;
1628    }
1629  } while (!Done);
1630
1631  if (Tok.is(MMToken::RBrace))
1632    consumeToken();
1633  else {
1634    Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
1635    Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
1636    HadError = true;
1637  }
1638}
1639
1640/// \brief Parse optional attributes.
1641///
1642///   attributes:
1643///     attribute attributes
1644///     attribute
1645///
1646///   attribute:
1647///     [ identifier ]
1648///
1649/// \param Attrs Will be filled in with the parsed attributes.
1650///
1651/// \returns true if an error occurred, false otherwise.
1652bool ModuleMapParser::parseOptionalAttributes(Attributes &Attrs) {
1653  bool HadError = false;
1654
1655  while (Tok.is(MMToken::LSquare)) {
1656    // Consume the '['.
1657    SourceLocation LSquareLoc = consumeToken();
1658
1659    // Check whether we have an attribute name here.
1660    if (!Tok.is(MMToken::Identifier)) {
1661      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_attribute);
1662      skipUntil(MMToken::RSquare);
1663      if (Tok.is(MMToken::RSquare))
1664        consumeToken();
1665      HadError = true;
1666    }
1667
1668    // Decode the attribute name.
1669    AttributeKind Attribute
1670      = llvm::StringSwitch<AttributeKind>(Tok.getString())
1671          .Case("system", AT_system)
1672          .Default(AT_unknown);
1673    switch (Attribute) {
1674    case AT_unknown:
1675      Diags.Report(Tok.getLocation(), diag::warn_mmap_unknown_attribute)
1676        << Tok.getString();
1677      break;
1678
1679    case AT_system:
1680      Attrs.IsSystem = true;
1681      break;
1682    }
1683    consumeToken();
1684
1685    // Consume the ']'.
1686    if (!Tok.is(MMToken::RSquare)) {
1687      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rsquare);
1688      Diags.Report(LSquareLoc, diag::note_mmap_lsquare_match);
1689      skipUntil(MMToken::RSquare);
1690      HadError = true;
1691    }
1692
1693    if (Tok.is(MMToken::RSquare))
1694      consumeToken();
1695  }
1696
1697  return HadError;
1698}
1699
1700/// \brief If there is a specific header search directory due the presence
1701/// of an umbrella directory, retrieve that directory. Otherwise, returns null.
1702const DirectoryEntry *ModuleMapParser::getOverriddenHeaderSearchDir() {
1703  for (Module *Mod = ActiveModule; Mod; Mod = Mod->Parent) {
1704    // If we have an umbrella directory, use that.
1705    if (Mod->hasUmbrellaDir())
1706      return Mod->getUmbrellaDir();
1707
1708    // If we have a framework directory, stop looking.
1709    if (Mod->IsFramework)
1710      return 0;
1711  }
1712
1713  return 0;
1714}
1715
1716/// \brief Parse a module map file.
1717///
1718///   module-map-file:
1719///     module-declaration*
1720bool ModuleMapParser::parseModuleMapFile() {
1721  do {
1722    switch (Tok.Kind) {
1723    case MMToken::EndOfFile:
1724      return HadError;
1725
1726    case MMToken::ExplicitKeyword:
1727    case MMToken::ModuleKeyword:
1728    case MMToken::FrameworkKeyword:
1729      parseModuleDecl();
1730      break;
1731
1732    case MMToken::Comma:
1733    case MMToken::ExcludeKeyword:
1734    case MMToken::ExportKeyword:
1735    case MMToken::HeaderKeyword:
1736    case MMToken::Identifier:
1737    case MMToken::LBrace:
1738    case MMToken::LinkKeyword:
1739    case MMToken::LSquare:
1740    case MMToken::Period:
1741    case MMToken::RBrace:
1742    case MMToken::RSquare:
1743    case MMToken::RequiresKeyword:
1744    case MMToken::Star:
1745    case MMToken::StringLiteral:
1746    case MMToken::UmbrellaKeyword:
1747      Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
1748      HadError = true;
1749      consumeToken();
1750      break;
1751    }
1752  } while (true);
1753}
1754
1755bool ModuleMap::parseModuleMapFile(const FileEntry *File) {
1756  llvm::DenseMap<const FileEntry *, bool>::iterator Known
1757    = ParsedModuleMap.find(File);
1758  if (Known != ParsedModuleMap.end())
1759    return Known->second;
1760
1761  assert(Target != 0 && "Missing target information");
1762  FileID ID = SourceMgr->createFileID(File, SourceLocation(), SrcMgr::C_User);
1763  const llvm::MemoryBuffer *Buffer = SourceMgr->getBuffer(ID);
1764  if (!Buffer)
1765    return ParsedModuleMap[File] = true;
1766
1767  // Parse this module map file.
1768  Lexer L(ID, SourceMgr->getBuffer(ID), *SourceMgr, MMapLangOpts);
1769  Diags->getClient()->BeginSourceFile(MMapLangOpts);
1770  ModuleMapParser Parser(L, *SourceMgr, Target, *Diags, *this, File->getDir(),
1771                         BuiltinIncludeDir);
1772  bool Result = Parser.parseModuleMapFile();
1773  Diags->getClient()->EndSourceFile();
1774  ParsedModuleMap[File] = Result;
1775  return Result;
1776}
1777