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