1 //===- Module.cpp - Describe a module -------------------------------------===//
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 Module class, which describes a module in the source
11 // code.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/Basic/Module.h"
16 #include "clang/Basic/CharInfo.h"
17 #include "clang/Basic/FileManager.h"
18 #include "clang/Basic/LangOptions.h"
19 #include "clang/Basic/SourceLocation.h"
20 #include "clang/Basic/TargetInfo.h"
21 #include "llvm/ADT/ArrayRef.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/ADT/StringSwitch.h"
26 #include "llvm/Support/Compiler.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <algorithm>
30 #include <cassert>
31 #include <functional>
32 #include <string>
33 #include <utility>
34 #include <vector>
35 
36 using namespace clang;
37 
38 Module::Module(StringRef Name, SourceLocation DefinitionLoc, Module *Parent,
39                bool IsFramework, bool IsExplicit, unsigned VisibilityID)
40     : Name(Name), DefinitionLoc(DefinitionLoc), Parent(Parent),
41       VisibilityID(VisibilityID), IsMissingRequirement(false),
42       HasIncompatibleModuleFile(false), IsAvailable(true),
43       IsFromModuleFile(false), IsFramework(IsFramework), IsExplicit(IsExplicit),
44       IsSystem(false), IsExternC(false), IsInferred(false),
45       InferSubmodules(false), InferExplicitSubmodules(false),
46       InferExportWildcard(false), ConfigMacrosExhaustive(false),
47       NoUndeclaredIncludes(false), NameVisibility(Hidden) {
48   if (Parent) {
49     if (!Parent->isAvailable())
50       IsAvailable = false;
51     if (Parent->IsSystem)
52       IsSystem = true;
53     if (Parent->IsExternC)
54       IsExternC = true;
55     if (Parent->NoUndeclaredIncludes)
56       NoUndeclaredIncludes = true;
57     IsMissingRequirement = Parent->IsMissingRequirement;
58 
59     Parent->SubModuleIndex[Name] = Parent->SubModules.size();
60     Parent->SubModules.push_back(this);
61   }
62 }
63 
64 Module::~Module() {
65   for (submodule_iterator I = submodule_begin(), IEnd = submodule_end();
66        I != IEnd; ++I) {
67     delete *I;
68   }
69 }
70 
71 /// \brief Determine whether a translation unit built using the current
72 /// language options has the given feature.
73 static bool hasFeature(StringRef Feature, const LangOptions &LangOpts,
74                        const TargetInfo &Target) {
75   bool HasFeature = llvm::StringSwitch<bool>(Feature)
76                         .Case("altivec", LangOpts.AltiVec)
77                         .Case("blocks", LangOpts.Blocks)
78                         .Case("coroutines", LangOpts.CoroutinesTS)
79                         .Case("cplusplus", LangOpts.CPlusPlus)
80                         .Case("cplusplus11", LangOpts.CPlusPlus11)
81                         .Case("freestanding", LangOpts.Freestanding)
82                         .Case("gnuinlineasm", LangOpts.GNUAsm)
83                         .Case("objc", LangOpts.ObjC1)
84                         .Case("objc_arc", LangOpts.ObjCAutoRefCount)
85                         .Case("opencl", LangOpts.OpenCL)
86                         .Case("tls", Target.isTLSSupported())
87                         .Case("zvector", LangOpts.ZVector)
88                         .Default(Target.hasFeature(Feature));
89   if (!HasFeature)
90     HasFeature = std::find(LangOpts.ModuleFeatures.begin(),
91                            LangOpts.ModuleFeatures.end(),
92                            Feature) != LangOpts.ModuleFeatures.end();
93   return HasFeature;
94 }
95 
96 bool Module::isAvailable(const LangOptions &LangOpts, const TargetInfo &Target,
97                          Requirement &Req,
98                          UnresolvedHeaderDirective &MissingHeader) const {
99   if (IsAvailable)
100     return true;
101 
102   for (const Module *Current = this; Current; Current = Current->Parent) {
103     for (unsigned I = 0, N = Current->Requirements.size(); I != N; ++I) {
104       if (hasFeature(Current->Requirements[I].first, LangOpts, Target) !=
105               Current->Requirements[I].second) {
106         Req = Current->Requirements[I];
107         return false;
108       }
109     }
110     if (!Current->MissingHeaders.empty()) {
111       MissingHeader = Current->MissingHeaders.front();
112       return false;
113     }
114   }
115 
116   llvm_unreachable("could not find a reason why module is unavailable");
117 }
118 
119 bool Module::isSubModuleOf(const Module *Other) const {
120   const Module *This = this;
121   do {
122     if (This == Other)
123       return true;
124 
125     This = This->Parent;
126   } while (This);
127 
128   return false;
129 }
130 
131 const Module *Module::getTopLevelModule() const {
132   const Module *Result = this;
133   while (Result->Parent)
134     Result = Result->Parent;
135 
136   return Result;
137 }
138 
139 static StringRef getModuleNameFromComponent(
140     const std::pair<std::string, SourceLocation> &IdComponent) {
141   return IdComponent.first;
142 }
143 
144 static StringRef getModuleNameFromComponent(StringRef R) { return R; }
145 
146 template<typename InputIter>
147 static void printModuleId(raw_ostream &OS, InputIter Begin, InputIter End,
148                           bool AllowStringLiterals = true) {
149   for (InputIter It = Begin; It != End; ++It) {
150     if (It != Begin)
151       OS << ".";
152 
153     StringRef Name = getModuleNameFromComponent(*It);
154     if (!AllowStringLiterals || isValidIdentifier(Name))
155       OS << Name;
156     else {
157       OS << '"';
158       OS.write_escaped(Name);
159       OS << '"';
160     }
161   }
162 }
163 
164 template<typename Container>
165 static void printModuleId(raw_ostream &OS, const Container &C) {
166   return printModuleId(OS, C.begin(), C.end());
167 }
168 
169 std::string Module::getFullModuleName(bool AllowStringLiterals) const {
170   SmallVector<StringRef, 2> Names;
171 
172   // Build up the set of module names (from innermost to outermost).
173   for (const Module *M = this; M; M = M->Parent)
174     Names.push_back(M->Name);
175 
176   std::string Result;
177 
178   llvm::raw_string_ostream Out(Result);
179   printModuleId(Out, Names.rbegin(), Names.rend(), AllowStringLiterals);
180   Out.flush();
181 
182   return Result;
183 }
184 
185 bool Module::fullModuleNameIs(ArrayRef<StringRef> nameParts) const {
186   for (const Module *M = this; M; M = M->Parent) {
187     if (nameParts.empty() || M->Name != nameParts.back())
188       return false;
189     nameParts = nameParts.drop_back();
190   }
191   return nameParts.empty();
192 }
193 
194 Module::DirectoryName Module::getUmbrellaDir() const {
195   if (Header U = getUmbrellaHeader())
196     return {"", U.Entry->getDir()};
197 
198   return {UmbrellaAsWritten, Umbrella.dyn_cast<const DirectoryEntry *>()};
199 }
200 
201 ArrayRef<const FileEntry *> Module::getTopHeaders(FileManager &FileMgr) {
202   if (!TopHeaderNames.empty()) {
203     for (std::vector<std::string>::iterator
204            I = TopHeaderNames.begin(), E = TopHeaderNames.end(); I != E; ++I) {
205       if (const FileEntry *FE = FileMgr.getFile(*I))
206         TopHeaders.insert(FE);
207     }
208     TopHeaderNames.clear();
209   }
210 
211   return llvm::makeArrayRef(TopHeaders.begin(), TopHeaders.end());
212 }
213 
214 bool Module::directlyUses(const Module *Requested) const {
215   auto *Top = getTopLevelModule();
216 
217   // A top-level module implicitly uses itself.
218   if (Requested->isSubModuleOf(Top))
219     return true;
220 
221   for (auto *Use : Top->DirectUses)
222     if (Requested->isSubModuleOf(Use))
223       return true;
224 
225   // Anyone is allowed to use our builtin stddef.h and its accompanying module.
226   if (!Requested->Parent && Requested->Name == "_Builtin_stddef_max_align_t")
227     return true;
228 
229   return false;
230 }
231 
232 void Module::addRequirement(StringRef Feature, bool RequiredState,
233                             const LangOptions &LangOpts,
234                             const TargetInfo &Target) {
235   Requirements.push_back(Requirement(Feature, RequiredState));
236 
237   // If this feature is currently available, we're done.
238   if (hasFeature(Feature, LangOpts, Target) == RequiredState)
239     return;
240 
241   markUnavailable(/*MissingRequirement*/true);
242 }
243 
244 void Module::markUnavailable(bool MissingRequirement) {
245   auto needUpdate = [MissingRequirement](Module *M) {
246     return M->IsAvailable || (!M->IsMissingRequirement && MissingRequirement);
247   };
248 
249   if (!needUpdate(this))
250     return;
251 
252   SmallVector<Module *, 2> Stack;
253   Stack.push_back(this);
254   while (!Stack.empty()) {
255     Module *Current = Stack.back();
256     Stack.pop_back();
257 
258     if (!needUpdate(Current))
259       continue;
260 
261     Current->IsAvailable = false;
262     Current->IsMissingRequirement |= MissingRequirement;
263     for (submodule_iterator Sub = Current->submodule_begin(),
264                          SubEnd = Current->submodule_end();
265          Sub != SubEnd; ++Sub) {
266       if (needUpdate(*Sub))
267         Stack.push_back(*Sub);
268     }
269   }
270 }
271 
272 Module *Module::findSubmodule(StringRef Name) const {
273   llvm::StringMap<unsigned>::const_iterator Pos = SubModuleIndex.find(Name);
274   if (Pos == SubModuleIndex.end())
275     return nullptr;
276 
277   return SubModules[Pos->getValue()];
278 }
279 
280 void Module::getExportedModules(SmallVectorImpl<Module *> &Exported) const {
281   // All non-explicit submodules are exported.
282   for (std::vector<Module *>::const_iterator I = SubModules.begin(),
283                                              E = SubModules.end();
284        I != E; ++I) {
285     Module *Mod = *I;
286     if (!Mod->IsExplicit)
287       Exported.push_back(Mod);
288   }
289 
290   // Find re-exported modules by filtering the list of imported modules.
291   bool AnyWildcard = false;
292   bool UnrestrictedWildcard = false;
293   SmallVector<Module *, 4> WildcardRestrictions;
294   for (unsigned I = 0, N = Exports.size(); I != N; ++I) {
295     Module *Mod = Exports[I].getPointer();
296     if (!Exports[I].getInt()) {
297       // Export a named module directly; no wildcards involved.
298       Exported.push_back(Mod);
299 
300       continue;
301     }
302 
303     // Wildcard export: export all of the imported modules that match
304     // the given pattern.
305     AnyWildcard = true;
306     if (UnrestrictedWildcard)
307       continue;
308 
309     if (Module *Restriction = Exports[I].getPointer())
310       WildcardRestrictions.push_back(Restriction);
311     else {
312       WildcardRestrictions.clear();
313       UnrestrictedWildcard = true;
314     }
315   }
316 
317   // If there were any wildcards, push any imported modules that were
318   // re-exported by the wildcard restriction.
319   if (!AnyWildcard)
320     return;
321 
322   for (unsigned I = 0, N = Imports.size(); I != N; ++I) {
323     Module *Mod = Imports[I];
324     bool Acceptable = UnrestrictedWildcard;
325     if (!Acceptable) {
326       // Check whether this module meets one of the restrictions.
327       for (unsigned R = 0, NR = WildcardRestrictions.size(); R != NR; ++R) {
328         Module *Restriction = WildcardRestrictions[R];
329         if (Mod == Restriction || Mod->isSubModuleOf(Restriction)) {
330           Acceptable = true;
331           break;
332         }
333       }
334     }
335 
336     if (!Acceptable)
337       continue;
338 
339     Exported.push_back(Mod);
340   }
341 }
342 
343 void Module::buildVisibleModulesCache() const {
344   assert(VisibleModulesCache.empty() && "cache does not need building");
345 
346   // This module is visible to itself.
347   VisibleModulesCache.insert(this);
348 
349   // Every imported module is visible.
350   SmallVector<Module *, 16> Stack(Imports.begin(), Imports.end());
351   while (!Stack.empty()) {
352     Module *CurrModule = Stack.pop_back_val();
353 
354     // Every module transitively exported by an imported module is visible.
355     if (VisibleModulesCache.insert(CurrModule).second)
356       CurrModule->getExportedModules(Stack);
357   }
358 }
359 
360 void Module::print(raw_ostream &OS, unsigned Indent) const {
361   OS.indent(Indent);
362   if (IsFramework)
363     OS << "framework ";
364   if (IsExplicit)
365     OS << "explicit ";
366   OS << "module ";
367   printModuleId(OS, &Name, &Name + 1);
368 
369   if (IsSystem || IsExternC) {
370     OS.indent(Indent + 2);
371     if (IsSystem)
372       OS << " [system]";
373     if (IsExternC)
374       OS << " [extern_c]";
375   }
376 
377   OS << " {\n";
378 
379   if (!Requirements.empty()) {
380     OS.indent(Indent + 2);
381     OS << "requires ";
382     for (unsigned I = 0, N = Requirements.size(); I != N; ++I) {
383       if (I)
384         OS << ", ";
385       if (!Requirements[I].second)
386         OS << "!";
387       OS << Requirements[I].first;
388     }
389     OS << "\n";
390   }
391 
392   if (Header H = getUmbrellaHeader()) {
393     OS.indent(Indent + 2);
394     OS << "umbrella header \"";
395     OS.write_escaped(H.NameAsWritten);
396     OS << "\"\n";
397   } else if (DirectoryName D = getUmbrellaDir()) {
398     OS.indent(Indent + 2);
399     OS << "umbrella \"";
400     OS.write_escaped(D.NameAsWritten);
401     OS << "\"\n";
402   }
403 
404   if (!ConfigMacros.empty() || ConfigMacrosExhaustive) {
405     OS.indent(Indent + 2);
406     OS << "config_macros ";
407     if (ConfigMacrosExhaustive)
408       OS << "[exhaustive]";
409     for (unsigned I = 0, N = ConfigMacros.size(); I != N; ++I) {
410       if (I)
411         OS << ", ";
412       OS << ConfigMacros[I];
413     }
414     OS << "\n";
415   }
416 
417   struct {
418     StringRef Prefix;
419     HeaderKind Kind;
420   } Kinds[] = {{"", HK_Normal},
421                {"textual ", HK_Textual},
422                {"private ", HK_Private},
423                {"private textual ", HK_PrivateTextual},
424                {"exclude ", HK_Excluded}};
425 
426   for (auto &K : Kinds) {
427     assert(&K == &Kinds[K.Kind] && "kinds in wrong order");
428     for (auto &H : Headers[K.Kind]) {
429       OS.indent(Indent + 2);
430       OS << K.Prefix << "header \"";
431       OS.write_escaped(H.NameAsWritten);
432       OS << "\" { size " << H.Entry->getSize()
433          << " mtime " << H.Entry->getModificationTime() << " }\n";
434     }
435   }
436   for (auto *Unresolved : {&UnresolvedHeaders, &MissingHeaders}) {
437     for (auto &U : *Unresolved) {
438       OS.indent(Indent + 2);
439       OS << Kinds[U.Kind].Prefix << "header \"";
440       OS.write_escaped(U.FileName);
441       OS << "\"";
442       if (U.Size || U.ModTime) {
443         OS << " {";
444         if (U.Size)
445           OS << " size " << *U.Size;
446         if (U.ModTime)
447           OS << " mtime " << *U.ModTime;
448         OS << " }";
449       }
450       OS << "\n";
451     }
452   }
453 
454   if (!ExportAsModule.empty()) {
455     OS.indent(Indent + 2);
456     OS << "export_as" << ExportAsModule << "\n";
457   }
458 
459   for (submodule_const_iterator MI = submodule_begin(), MIEnd = submodule_end();
460        MI != MIEnd; ++MI)
461     // Print inferred subframework modules so that we don't need to re-infer
462     // them (requires expensive directory iteration + stat calls) when we build
463     // the module. Regular inferred submodules are OK, as we need to look at all
464     // those header files anyway.
465     if (!(*MI)->IsInferred || (*MI)->IsFramework)
466       (*MI)->print(OS, Indent + 2);
467 
468   for (unsigned I = 0, N = Exports.size(); I != N; ++I) {
469     OS.indent(Indent + 2);
470     OS << "export ";
471     if (Module *Restriction = Exports[I].getPointer()) {
472       OS << Restriction->getFullModuleName(true);
473       if (Exports[I].getInt())
474         OS << ".*";
475     } else {
476       OS << "*";
477     }
478     OS << "\n";
479   }
480 
481   for (unsigned I = 0, N = UnresolvedExports.size(); I != N; ++I) {
482     OS.indent(Indent + 2);
483     OS << "export ";
484     printModuleId(OS, UnresolvedExports[I].Id);
485     if (UnresolvedExports[I].Wildcard)
486       OS << (UnresolvedExports[I].Id.empty() ? "*" : ".*");
487     OS << "\n";
488   }
489 
490   for (unsigned I = 0, N = DirectUses.size(); I != N; ++I) {
491     OS.indent(Indent + 2);
492     OS << "use ";
493     OS << DirectUses[I]->getFullModuleName(true);
494     OS << "\n";
495   }
496 
497   for (unsigned I = 0, N = UnresolvedDirectUses.size(); I != N; ++I) {
498     OS.indent(Indent + 2);
499     OS << "use ";
500     printModuleId(OS, UnresolvedDirectUses[I]);
501     OS << "\n";
502   }
503 
504   for (unsigned I = 0, N = LinkLibraries.size(); I != N; ++I) {
505     OS.indent(Indent + 2);
506     OS << "link ";
507     if (LinkLibraries[I].IsFramework)
508       OS << "framework ";
509     OS << "\"";
510     OS.write_escaped(LinkLibraries[I].Library);
511     OS << "\"";
512   }
513 
514   for (unsigned I = 0, N = UnresolvedConflicts.size(); I != N; ++I) {
515     OS.indent(Indent + 2);
516     OS << "conflict ";
517     printModuleId(OS, UnresolvedConflicts[I].Id);
518     OS << ", \"";
519     OS.write_escaped(UnresolvedConflicts[I].Message);
520     OS << "\"\n";
521   }
522 
523   for (unsigned I = 0, N = Conflicts.size(); I != N; ++I) {
524     OS.indent(Indent + 2);
525     OS << "conflict ";
526     OS << Conflicts[I].Other->getFullModuleName(true);
527     OS << ", \"";
528     OS.write_escaped(Conflicts[I].Message);
529     OS << "\"\n";
530   }
531 
532   if (InferSubmodules) {
533     OS.indent(Indent + 2);
534     if (InferExplicitSubmodules)
535       OS << "explicit ";
536     OS << "module * {\n";
537     if (InferExportWildcard) {
538       OS.indent(Indent + 4);
539       OS << "export *\n";
540     }
541     OS.indent(Indent + 2);
542     OS << "}\n";
543   }
544 
545   OS.indent(Indent);
546   OS << "}\n";
547 }
548 
549 LLVM_DUMP_METHOD void Module::dump() const {
550   print(llvm::errs());
551 }
552 
553 void VisibleModuleSet::setVisible(Module *M, SourceLocation Loc,
554                                   VisibleCallback Vis, ConflictCallback Cb) {
555   assert(Loc.isValid() && "setVisible expects a valid import location");
556   if (isVisible(M))
557     return;
558 
559   ++Generation;
560 
561   struct Visiting {
562     Module *M;
563     Visiting *ExportedBy;
564   };
565 
566   std::function<void(Visiting)> VisitModule = [&](Visiting V) {
567     // Modules that aren't available cannot be made visible.
568     if (!V.M->isAvailable())
569       return;
570 
571     // Nothing to do for a module that's already visible.
572     unsigned ID = V.M->getVisibilityID();
573     if (ImportLocs.size() <= ID)
574       ImportLocs.resize(ID + 1);
575     else if (ImportLocs[ID].isValid())
576       return;
577 
578     ImportLocs[ID] = Loc;
579     Vis(M);
580 
581     // Make any exported modules visible.
582     SmallVector<Module *, 16> Exports;
583     V.M->getExportedModules(Exports);
584     for (Module *E : Exports)
585       VisitModule({E, &V});
586 
587     for (auto &C : V.M->Conflicts) {
588       if (isVisible(C.Other)) {
589         llvm::SmallVector<Module*, 8> Path;
590         for (Visiting *I = &V; I; I = I->ExportedBy)
591           Path.push_back(I->M);
592         Cb(Path, C.Other, C.Message);
593       }
594     }
595   };
596   VisitModule({M, nullptr});
597 }
598