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