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/Lex/Lexer.h"
16 #include "clang/Lex/LiteralSupport.h"
17 #include "clang/Lex/LexDiagnostic.h"
18 #include "clang/Basic/Diagnostic.h"
19 #include "clang/Basic/FileManager.h"
20 #include "clang/Basic/TargetInfo.h"
21 #include "clang/Basic/TargetOptions.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/Host.h"
24 #include "llvm/Support/PathV2.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/ADT/StringSwitch.h"
28 using namespace clang;
29 
30 //----------------------------------------------------------------------------//
31 // Module
32 //----------------------------------------------------------------------------//
33 
34 std::string ModuleMap::Module::getFullModuleName() const {
35   llvm::SmallVector<StringRef, 2> Names;
36 
37   // Build up the set of module names (from innermost to outermost).
38   for (const Module *M = this; M; M = M->Parent)
39     Names.push_back(M->Name);
40 
41   std::string Result;
42   for (llvm::SmallVector<StringRef, 2>::reverse_iterator I = Names.rbegin(),
43                                                       IEnd = Names.rend();
44        I != IEnd; ++I) {
45     if (!Result.empty())
46       Result += '.';
47 
48     Result += *I;
49   }
50 
51   return Result;
52 }
53 
54 StringRef ModuleMap::Module::getTopLevelModuleName() const {
55   const Module *Top = this;
56   while (Top->Parent)
57     Top = Top->Parent;
58 
59   return Top->Name;
60 }
61 
62 //----------------------------------------------------------------------------//
63 // Module map
64 //----------------------------------------------------------------------------//
65 
66 ModuleMap::ModuleMap(FileManager &FileMgr, const DiagnosticConsumer &DC) {
67   llvm::IntrusiveRefCntPtr<DiagnosticIDs> DiagIDs(new DiagnosticIDs);
68   Diags = llvm::IntrusiveRefCntPtr<DiagnosticsEngine>(
69             new DiagnosticsEngine(DiagIDs));
70   Diags->setClient(DC.clone(*Diags), /*ShouldOwnClient=*/true);
71   SourceMgr = new SourceManager(*Diags, FileMgr);
72 }
73 
74 ModuleMap::~ModuleMap() {
75   delete SourceMgr;
76 }
77 
78 ModuleMap::Module *ModuleMap::findModuleForHeader(const FileEntry *File) {
79   llvm::DenseMap<const FileEntry *, Module *>::iterator Known
80     = Headers.find(File);
81   if (Known != Headers.end())
82     return Known->second;
83 
84   const DirectoryEntry *Dir = File->getDir();
85   llvm::DenseMap<const DirectoryEntry *, Module *>::iterator KnownDir
86     = UmbrellaDirs.find(Dir);
87   if (KnownDir != UmbrellaDirs.end())
88     return KnownDir->second;
89 
90   // Walk up the directory hierarchy looking for umbrella headers.
91   llvm::SmallVector<const DirectoryEntry *, 2> SkippedDirs;
92   StringRef DirName = Dir->getName();
93   do {
94     // Retrieve our parent path.
95     DirName = llvm::sys::path::parent_path(DirName);
96     if (DirName.empty())
97       break;
98 
99     // Resolve the parent path to a directory entry.
100     Dir = SourceMgr->getFileManager().getDirectory(DirName);
101     if (!Dir)
102       break;
103 
104     KnownDir = UmbrellaDirs.find(Dir);
105     if (KnownDir != UmbrellaDirs.end()) {
106       Module *Result = KnownDir->second;
107 
108       // Record each of the directories we stepped through as being part of
109       // the module we found, since the umbrella header covers them all.
110       for (unsigned I = 0, N = SkippedDirs.size(); I != N; ++I)
111         UmbrellaDirs[SkippedDirs[I]] = Result;
112 
113       return Result;
114     }
115 
116     SkippedDirs.push_back(Dir);
117   } while (true);
118 
119   return 0;
120 }
121 
122 ModuleMap::Module *ModuleMap::findModule(StringRef Name) {
123   llvm::StringMap<Module *>::iterator Known = Modules.find(Name);
124   if (Known != Modules.end())
125     return Known->getValue();
126 
127   return 0;
128 }
129 
130 static void indent(llvm::raw_ostream &OS, unsigned Spaces) {
131   OS << std::string(' ', Spaces);
132 }
133 
134 static void dumpModule(llvm::raw_ostream &OS, ModuleMap::Module *M,
135                        unsigned Indent) {
136   indent(OS, Indent);
137   if (M->IsExplicit)
138     OS << "explicit ";
139   OS << M->Name << " {\n";
140 
141   if (M->UmbrellaHeader) {
142     indent(OS, Indent + 2);
143     OS << "umbrella \"" << M->UmbrellaHeader->getName() << "\"\n";
144   }
145 
146   for (unsigned I = 0, N = M->Headers.size(); I != N; ++I) {
147     indent(OS, Indent + 2);
148     OS << "header \"" << M->Headers[I]->getName() << "\"\n";
149   }
150 
151   for (llvm::StringMap<ModuleMap::Module *>::iterator
152             MI = M->SubModules.begin(),
153          MIEnd = M->SubModules.end();
154        MI != MIEnd; ++MI)
155     dumpModule(llvm::errs(), MI->getValue(), Indent + 2);
156 
157   indent(OS, Indent);
158   OS << "}\n";
159 }
160 
161 void ModuleMap::dump() {
162   llvm::errs() << "Modules:";
163   for (llvm::StringMap<Module *>::iterator M = Modules.begin(),
164                                         MEnd = Modules.end();
165        M != MEnd; ++M)
166     dumpModule(llvm::errs(), M->getValue(), 2);
167 
168   llvm::errs() << "Headers:";
169   for (llvm::DenseMap<const FileEntry *, Module *>::iterator
170             H = Headers.begin(),
171          HEnd = Headers.end();
172        H != HEnd; ++H) {
173     llvm::errs() << "  \"" << H->first->getName() << "\" -> "
174                  << H->second->getFullModuleName() << "\n";
175   }
176 }
177 
178 //----------------------------------------------------------------------------//
179 // Module map file parser
180 //----------------------------------------------------------------------------//
181 
182 namespace clang {
183   /// \brief A token in a module map file.
184   struct MMToken {
185     enum TokenKind {
186       EndOfFile,
187       HeaderKeyword,
188       Identifier,
189       ExplicitKeyword,
190       ModuleKeyword,
191       UmbrellaKeyword,
192       StringLiteral,
193       LBrace,
194       RBrace
195     } Kind;
196 
197     unsigned Location;
198     unsigned StringLength;
199     const char *StringData;
200 
201     void clear() {
202       Kind = EndOfFile;
203       Location = 0;
204       StringLength = 0;
205       StringData = 0;
206     }
207 
208     bool is(TokenKind K) const { return Kind == K; }
209 
210     SourceLocation getLocation() const {
211       return SourceLocation::getFromRawEncoding(Location);
212     }
213 
214     StringRef getString() const {
215       return StringRef(StringData, StringLength);
216     }
217   };
218 
219   class ModuleMapParser {
220     Lexer &L;
221     SourceManager &SourceMgr;
222     DiagnosticsEngine &Diags;
223     ModuleMap &Map;
224 
225     /// \brief The directory that this module map resides in.
226     const DirectoryEntry *Directory;
227 
228     /// \brief Whether an error occurred.
229     bool HadError;
230 
231     /// \brief Default target information, used only for string literal
232     /// parsing.
233     TargetInfo *Target;
234 
235     /// \brief Stores string data for the various string literals referenced
236     /// during parsing.
237     llvm::BumpPtrAllocator StringData;
238 
239     /// \brief The current token.
240     MMToken Tok;
241 
242     /// \brief The active module.
243     ModuleMap::Module *ActiveModule;
244 
245     /// \brief Consume the current token and return its location.
246     SourceLocation consumeToken();
247 
248     /// \brief Skip tokens until we reach the a token with the given kind
249     /// (or the end of the file).
250     void skipUntil(MMToken::TokenKind K);
251 
252     void parseModuleDecl();
253     void parseUmbrellaDecl();
254     void parseHeaderDecl();
255 
256   public:
257     typedef ModuleMap::Module Module;
258 
259     explicit ModuleMapParser(Lexer &L, SourceManager &SourceMgr,
260                              DiagnosticsEngine &Diags,
261                              ModuleMap &Map,
262                              const DirectoryEntry *Directory)
263       : L(L), SourceMgr(SourceMgr), Diags(Diags), Map(Map),
264         Directory(Directory), HadError(false), ActiveModule(0)
265     {
266       TargetOptions TargetOpts;
267       TargetOpts.Triple = llvm::sys::getDefaultTargetTriple();
268       Target = TargetInfo::CreateTargetInfo(Diags, TargetOpts);
269 
270       Tok.clear();
271       consumeToken();
272     }
273 
274     bool parseModuleMapFile();
275   };
276 }
277 
278 SourceLocation ModuleMapParser::consumeToken() {
279 retry:
280   SourceLocation Result = Tok.getLocation();
281   Tok.clear();
282 
283   Token LToken;
284   L.LexFromRawLexer(LToken);
285   Tok.Location = LToken.getLocation().getRawEncoding();
286   switch (LToken.getKind()) {
287   case tok::raw_identifier:
288     Tok.StringData = LToken.getRawIdentifierData();
289     Tok.StringLength = LToken.getLength();
290     Tok.Kind = llvm::StringSwitch<MMToken::TokenKind>(Tok.getString())
291                  .Case("header", MMToken::HeaderKeyword)
292                  .Case("explicit", MMToken::ExplicitKeyword)
293                  .Case("module", MMToken::ModuleKeyword)
294                  .Case("umbrella", MMToken::UmbrellaKeyword)
295                  .Default(MMToken::Identifier);
296     break;
297 
298   case tok::eof:
299     Tok.Kind = MMToken::EndOfFile;
300     break;
301 
302   case tok::l_brace:
303     Tok.Kind = MMToken::LBrace;
304     break;
305 
306   case tok::r_brace:
307     Tok.Kind = MMToken::RBrace;
308     break;
309 
310   case tok::string_literal: {
311     // Parse the string literal.
312     LangOptions LangOpts;
313     StringLiteralParser StringLiteral(&LToken, 1, SourceMgr, LangOpts, *Target);
314     if (StringLiteral.hadError)
315       goto retry;
316 
317     // Copy the string literal into our string data allocator.
318     unsigned Length = StringLiteral.GetStringLength();
319     char *Saved = StringData.Allocate<char>(Length + 1);
320     memcpy(Saved, StringLiteral.GetString().data(), Length);
321     Saved[Length] = 0;
322 
323     // Form the token.
324     Tok.Kind = MMToken::StringLiteral;
325     Tok.StringData = Saved;
326     Tok.StringLength = Length;
327     break;
328   }
329 
330   case tok::comment:
331     goto retry;
332 
333   default:
334     Diags.Report(LToken.getLocation(), diag::err_mmap_unknown_token);
335     HadError = true;
336     goto retry;
337   }
338 
339   return Result;
340 }
341 
342 void ModuleMapParser::skipUntil(MMToken::TokenKind K) {
343   unsigned braceDepth = 0;
344   do {
345     switch (Tok.Kind) {
346     case MMToken::EndOfFile:
347       return;
348 
349     case MMToken::LBrace:
350       if (Tok.is(K) && braceDepth == 0)
351         return;
352 
353       ++braceDepth;
354       break;
355 
356     case MMToken::RBrace:
357       if (braceDepth > 0)
358         --braceDepth;
359       else if (Tok.is(K))
360         return;
361       break;
362 
363     default:
364       if (braceDepth == 0 && Tok.is(K))
365         return;
366       break;
367     }
368 
369    consumeToken();
370   } while (true);
371 }
372 
373 /// \brief Parse a module declaration.
374 ///
375 ///   module-declaration:
376 ///     'module' identifier { module-member* }
377 ///
378 ///   module-member:
379 ///     umbrella-declaration
380 ///     header-declaration
381 ///     'explicit'[opt] module-declaration
382 void ModuleMapParser::parseModuleDecl() {
383   assert(Tok.is(MMToken::ExplicitKeyword) || Tok.is(MMToken::ModuleKeyword));
384 
385   // Parse 'explicit' keyword, if present.
386   bool Explicit = false;
387   if (Tok.is(MMToken::ExplicitKeyword)) {
388     consumeToken();
389     Explicit = true;
390   }
391 
392   // Parse 'module' keyword.
393   if (!Tok.is(MMToken::ModuleKeyword)) {
394     Diags.Report(Tok.getLocation(),
395                  diag::err_mmap_expected_module_after_explicit);
396     consumeToken();
397     HadError = true;
398     return;
399   }
400   consumeToken(); // 'module' keyword
401 
402   // Parse the module name.
403   if (!Tok.is(MMToken::Identifier)) {
404     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module_name);
405     HadError = true;
406     return;
407   }
408   StringRef ModuleName = Tok.getString();
409   SourceLocation ModuleNameLoc = consumeToken();
410 
411   // Parse the opening brace.
412   if (!Tok.is(MMToken::LBrace)) {
413     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_lbrace)
414       << ModuleName;
415     HadError = true;
416     return;
417   }
418   SourceLocation LBraceLoc = consumeToken();
419 
420   // Determine whether this (sub)module has already been defined.
421   llvm::StringMap<Module *> &ModuleSpace
422     = ActiveModule? ActiveModule->SubModules : Map.Modules;
423   llvm::StringMap<Module *>::iterator ExistingModule
424     = ModuleSpace.find(ModuleName);
425   if (ExistingModule != ModuleSpace.end()) {
426     Diags.Report(ModuleNameLoc, diag::err_mmap_module_redefinition)
427       << ModuleName;
428     Diags.Report(ExistingModule->getValue()->DefinitionLoc,
429                  diag::note_mmap_prev_definition);
430 
431     // Skip the module definition.
432     skipUntil(MMToken::RBrace);
433     if (Tok.is(MMToken::RBrace))
434       consumeToken();
435 
436     HadError = true;
437     return;
438   }
439 
440   // Start defining this module.
441   ActiveModule = new Module(ModuleName, ModuleNameLoc, ActiveModule, Explicit);
442   ModuleSpace[ModuleName] = ActiveModule;
443 
444   bool Done = false;
445   do {
446     switch (Tok.Kind) {
447     case MMToken::EndOfFile:
448     case MMToken::RBrace:
449       Done = true;
450       break;
451 
452     case MMToken::ExplicitKeyword:
453     case MMToken::ModuleKeyword:
454       parseModuleDecl();
455       break;
456 
457     case MMToken::HeaderKeyword:
458       parseHeaderDecl();
459       break;
460 
461     case MMToken::UmbrellaKeyword:
462       parseUmbrellaDecl();
463       break;
464 
465     default:
466       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_member);
467       consumeToken();
468       break;
469     }
470   } while (!Done);
471 
472   if (Tok.is(MMToken::RBrace))
473     consumeToken();
474   else {
475     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_rbrace);
476     Diags.Report(LBraceLoc, diag::note_mmap_lbrace_match);
477     HadError = true;
478   }
479 
480   // We're done parsing this module. Pop back to our parent scope.
481   ActiveModule = ActiveModule->Parent;
482 }
483 
484 /// \brief Parse an umbrella header declaration.
485 ///
486 ///   umbrella-declaration:
487 ///     'umbrella' string-literal
488 void ModuleMapParser::parseUmbrellaDecl() {
489   assert(Tok.is(MMToken::UmbrellaKeyword));
490   SourceLocation UmbrellaLoc = consumeToken();
491 
492   // Parse the header name.
493   if (!Tok.is(MMToken::StringLiteral)) {
494     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
495       << "umbrella";
496     HadError = true;
497     return;
498   }
499   StringRef FileName = Tok.getString();
500   SourceLocation FileNameLoc = consumeToken();
501 
502   // Check whether we already have an umbrella header.
503   if (ActiveModule->UmbrellaHeader) {
504     Diags.Report(FileNameLoc, diag::err_mmap_umbrella_header_conflict)
505       << ActiveModule->getFullModuleName()
506       << ActiveModule->UmbrellaHeader->getName();
507     HadError = true;
508     return;
509   }
510 
511   // Only top-level modules can have umbrella headers.
512   if (ActiveModule->Parent) {
513     Diags.Report(UmbrellaLoc, diag::err_mmap_umbrella_header_submodule)
514       << ActiveModule->getFullModuleName();
515     HadError = true;
516     return;
517   }
518 
519   // Look for this file.
520   llvm::SmallString<128> PathName;
521   PathName += Directory->getName();
522   llvm::sys::path::append(PathName, FileName);
523 
524   // FIXME: We shouldn't be eagerly stat'ing every file named in a module map.
525   // Come up with a lazy way to do this.
526   if (const FileEntry *File = SourceMgr.getFileManager().getFile(PathName)) {
527     if (const Module *OwningModule = Map.Headers[File]) {
528       Diags.Report(FileNameLoc, diag::err_mmap_header_conflict)
529         << FileName << OwningModule->getFullModuleName();
530       HadError = true;
531     } else if ((OwningModule = Map.UmbrellaDirs[Directory])) {
532       Diags.Report(UmbrellaLoc, diag::err_mmap_umbrella_clash)
533         << OwningModule->getFullModuleName();
534       HadError = true;
535     } else {
536       // Record this umbrella header.
537       ActiveModule->UmbrellaHeader = File;
538       Map.Headers[File] = ActiveModule;
539       Map.UmbrellaDirs[Directory] = ActiveModule;
540     }
541   } else {
542     Diags.Report(FileNameLoc, diag::err_mmap_header_not_found)
543       << true << FileName;
544     HadError = true;
545   }
546 }
547 
548 /// \brief Parse a header declaration.
549 ///
550 ///   header-declaration:
551 ///     'header' string-literal
552 void ModuleMapParser::parseHeaderDecl() {
553   assert(Tok.is(MMToken::HeaderKeyword));
554   consumeToken();
555 
556   // Parse the header name.
557   if (!Tok.is(MMToken::StringLiteral)) {
558     Diags.Report(Tok.getLocation(), diag::err_mmap_expected_header)
559       << "header";
560     HadError = true;
561     return;
562   }
563   StringRef FileName = Tok.getString();
564   SourceLocation FileNameLoc = consumeToken();
565 
566   // Look for this file.
567   llvm::SmallString<128> PathName;
568   PathName += Directory->getName();
569   llvm::sys::path::append(PathName, FileName);
570 
571   // FIXME: We shouldn't be eagerly stat'ing every file named in a module map.
572   // Come up with a lazy way to do this.
573   if (const FileEntry *File = SourceMgr.getFileManager().getFile(PathName)) {
574     if (const Module *OwningModule = Map.Headers[File]) {
575       Diags.Report(FileNameLoc, diag::err_mmap_header_conflict)
576         << FileName << OwningModule->getFullModuleName();
577       HadError = true;
578     } else {
579       // Record this file.
580       ActiveModule->Headers.push_back(File);
581       Map.Headers[File] = ActiveModule;
582     }
583   } else {
584     Diags.Report(FileNameLoc, diag::err_mmap_header_not_found)
585       << false << FileName;
586     HadError = true;
587   }
588 }
589 
590 /// \brief Parse a module map file.
591 ///
592 ///   module-map-file:
593 ///     module-declaration*
594 bool ModuleMapParser::parseModuleMapFile() {
595   do {
596     switch (Tok.Kind) {
597     case MMToken::EndOfFile:
598       return HadError;
599 
600     case MMToken::ModuleKeyword:
601       parseModuleDecl();
602       break;
603 
604     case MMToken::ExplicitKeyword:
605     case MMToken::HeaderKeyword:
606     case MMToken::Identifier:
607     case MMToken::LBrace:
608     case MMToken::RBrace:
609     case MMToken::StringLiteral:
610     case MMToken::UmbrellaKeyword:
611       Diags.Report(Tok.getLocation(), diag::err_mmap_expected_module);
612       HadError = true;
613       consumeToken();
614       break;
615     }
616   } while (true);
617 
618   return HadError;
619 }
620 
621 bool ModuleMap::parseModuleMapFile(const FileEntry *File) {
622   FileID ID = SourceMgr->createFileID(File, SourceLocation(), SrcMgr::C_User);
623   const llvm::MemoryBuffer *Buffer = SourceMgr->getBuffer(ID);
624   if (!Buffer)
625     return true;
626 
627   // Parse this module map file.
628   Lexer L(ID, SourceMgr->getBuffer(ID), *SourceMgr, LangOpts);
629   Diags->getClient()->BeginSourceFile(LangOpts);
630   ModuleMapParser Parser(L, *SourceMgr, *Diags, *this, File->getDir());
631   bool Result = Parser.parseModuleMapFile();
632   Diags->getClient()->EndSourceFile();
633 
634   return Result;
635 }
636