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