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 (auto 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 Module *Module::findOrInferSubmodule(StringRef Name) {
325   llvm::StringMap<unsigned>::const_iterator Pos = SubModuleIndex.find(Name);
326   if (Pos != SubModuleIndex.end())
327     return SubModules[Pos->getValue()];
328   if (!InferSubmodules)
329     return nullptr;
330   Module *Result = new Module(Name, SourceLocation(), this, false, InferExplicitSubmodules, 0);
331   Result->InferExplicitSubmodules = InferExplicitSubmodules;
332   Result->InferSubmodules = InferSubmodules;
333   Result->InferExportWildcard = InferExportWildcard;
334   if (Result->InferExportWildcard)
335     Result->Exports.push_back(Module::ExportDecl(nullptr, true));
336   return Result;
337 }
338 
339 void Module::getExportedModules(SmallVectorImpl<Module *> &Exported) const {
340   // All non-explicit submodules are exported.
341   for (std::vector<Module *>::const_iterator I = SubModules.begin(),
342                                              E = SubModules.end();
343        I != E; ++I) {
344     Module *Mod = *I;
345     if (!Mod->IsExplicit)
346       Exported.push_back(Mod);
347   }
348 
349   // Find re-exported modules by filtering the list of imported modules.
350   bool AnyWildcard = false;
351   bool UnrestrictedWildcard = false;
352   SmallVector<Module *, 4> WildcardRestrictions;
353   for (unsigned I = 0, N = Exports.size(); I != N; ++I) {
354     Module *Mod = Exports[I].getPointer();
355     if (!Exports[I].getInt()) {
356       // Export a named module directly; no wildcards involved.
357       Exported.push_back(Mod);
358 
359       continue;
360     }
361 
362     // Wildcard export: export all of the imported modules that match
363     // the given pattern.
364     AnyWildcard = true;
365     if (UnrestrictedWildcard)
366       continue;
367 
368     if (Module *Restriction = Exports[I].getPointer())
369       WildcardRestrictions.push_back(Restriction);
370     else {
371       WildcardRestrictions.clear();
372       UnrestrictedWildcard = true;
373     }
374   }
375 
376   // If there were any wildcards, push any imported modules that were
377   // re-exported by the wildcard restriction.
378   if (!AnyWildcard)
379     return;
380 
381   for (unsigned I = 0, N = Imports.size(); I != N; ++I) {
382     Module *Mod = Imports[I];
383     bool Acceptable = UnrestrictedWildcard;
384     if (!Acceptable) {
385       // Check whether this module meets one of the restrictions.
386       for (unsigned R = 0, NR = WildcardRestrictions.size(); R != NR; ++R) {
387         Module *Restriction = WildcardRestrictions[R];
388         if (Mod == Restriction || Mod->isSubModuleOf(Restriction)) {
389           Acceptable = true;
390           break;
391         }
392       }
393     }
394 
395     if (!Acceptable)
396       continue;
397 
398     Exported.push_back(Mod);
399   }
400 }
401 
402 void Module::buildVisibleModulesCache() const {
403   assert(VisibleModulesCache.empty() && "cache does not need building");
404 
405   // This module is visible to itself.
406   VisibleModulesCache.insert(this);
407 
408   // Every imported module is visible.
409   SmallVector<Module *, 16> Stack(Imports.begin(), Imports.end());
410   while (!Stack.empty()) {
411     Module *CurrModule = Stack.pop_back_val();
412 
413     // Every module transitively exported by an imported module is visible.
414     if (VisibleModulesCache.insert(CurrModule).second)
415       CurrModule->getExportedModules(Stack);
416   }
417 }
418 
419 void Module::print(raw_ostream &OS, unsigned Indent) const {
420   OS.indent(Indent);
421   if (IsFramework)
422     OS << "framework ";
423   if (IsExplicit)
424     OS << "explicit ";
425   OS << "module ";
426   printModuleId(OS, &Name, &Name + 1);
427 
428   if (IsSystem || IsExternC) {
429     OS.indent(Indent + 2);
430     if (IsSystem)
431       OS << " [system]";
432     if (IsExternC)
433       OS << " [extern_c]";
434   }
435 
436   OS << " {\n";
437 
438   if (!Requirements.empty()) {
439     OS.indent(Indent + 2);
440     OS << "requires ";
441     for (unsigned I = 0, N = Requirements.size(); I != N; ++I) {
442       if (I)
443         OS << ", ";
444       if (!Requirements[I].second)
445         OS << "!";
446       OS << Requirements[I].first;
447     }
448     OS << "\n";
449   }
450 
451   if (Header H = getUmbrellaHeader()) {
452     OS.indent(Indent + 2);
453     OS << "umbrella header \"";
454     OS.write_escaped(H.NameAsWritten);
455     OS << "\"\n";
456   } else if (DirectoryName D = getUmbrellaDir()) {
457     OS.indent(Indent + 2);
458     OS << "umbrella \"";
459     OS.write_escaped(D.NameAsWritten);
460     OS << "\"\n";
461   }
462 
463   if (!ConfigMacros.empty() || ConfigMacrosExhaustive) {
464     OS.indent(Indent + 2);
465     OS << "config_macros ";
466     if (ConfigMacrosExhaustive)
467       OS << "[exhaustive]";
468     for (unsigned I = 0, N = ConfigMacros.size(); I != N; ++I) {
469       if (I)
470         OS << ", ";
471       OS << ConfigMacros[I];
472     }
473     OS << "\n";
474   }
475 
476   struct {
477     StringRef Prefix;
478     HeaderKind Kind;
479   } Kinds[] = {{"", HK_Normal},
480                {"textual ", HK_Textual},
481                {"private ", HK_Private},
482                {"private textual ", HK_PrivateTextual},
483                {"exclude ", HK_Excluded}};
484 
485   for (auto &K : Kinds) {
486     assert(&K == &Kinds[K.Kind] && "kinds in wrong order");
487     for (auto &H : Headers[K.Kind]) {
488       OS.indent(Indent + 2);
489       OS << K.Prefix << "header \"";
490       OS.write_escaped(H.NameAsWritten);
491       OS << "\" { size " << H.Entry->getSize()
492          << " mtime " << H.Entry->getModificationTime() << " }\n";
493     }
494   }
495   for (auto *Unresolved : {&UnresolvedHeaders, &MissingHeaders}) {
496     for (auto &U : *Unresolved) {
497       OS.indent(Indent + 2);
498       OS << Kinds[U.Kind].Prefix << "header \"";
499       OS.write_escaped(U.FileName);
500       OS << "\"";
501       if (U.Size || U.ModTime) {
502         OS << " {";
503         if (U.Size)
504           OS << " size " << *U.Size;
505         if (U.ModTime)
506           OS << " mtime " << *U.ModTime;
507         OS << " }";
508       }
509       OS << "\n";
510     }
511   }
512 
513   if (!ExportAsModule.empty()) {
514     OS.indent(Indent + 2);
515     OS << "export_as" << ExportAsModule << "\n";
516   }
517 
518   for (submodule_const_iterator MI = submodule_begin(), MIEnd = submodule_end();
519        MI != MIEnd; ++MI)
520     // Print inferred subframework modules so that we don't need to re-infer
521     // them (requires expensive directory iteration + stat calls) when we build
522     // the module. Regular inferred submodules are OK, as we need to look at all
523     // those header files anyway.
524     if (!(*MI)->IsInferred || (*MI)->IsFramework)
525       (*MI)->print(OS, Indent + 2);
526 
527   for (unsigned I = 0, N = Exports.size(); I != N; ++I) {
528     OS.indent(Indent + 2);
529     OS << "export ";
530     if (Module *Restriction = Exports[I].getPointer()) {
531       OS << Restriction->getFullModuleName(true);
532       if (Exports[I].getInt())
533         OS << ".*";
534     } else {
535       OS << "*";
536     }
537     OS << "\n";
538   }
539 
540   for (unsigned I = 0, N = UnresolvedExports.size(); I != N; ++I) {
541     OS.indent(Indent + 2);
542     OS << "export ";
543     printModuleId(OS, UnresolvedExports[I].Id);
544     if (UnresolvedExports[I].Wildcard)
545       OS << (UnresolvedExports[I].Id.empty() ? "*" : ".*");
546     OS << "\n";
547   }
548 
549   for (unsigned I = 0, N = DirectUses.size(); I != N; ++I) {
550     OS.indent(Indent + 2);
551     OS << "use ";
552     OS << DirectUses[I]->getFullModuleName(true);
553     OS << "\n";
554   }
555 
556   for (unsigned I = 0, N = UnresolvedDirectUses.size(); I != N; ++I) {
557     OS.indent(Indent + 2);
558     OS << "use ";
559     printModuleId(OS, UnresolvedDirectUses[I]);
560     OS << "\n";
561   }
562 
563   for (unsigned I = 0, N = LinkLibraries.size(); I != N; ++I) {
564     OS.indent(Indent + 2);
565     OS << "link ";
566     if (LinkLibraries[I].IsFramework)
567       OS << "framework ";
568     OS << "\"";
569     OS.write_escaped(LinkLibraries[I].Library);
570     OS << "\"";
571   }
572 
573   for (unsigned I = 0, N = UnresolvedConflicts.size(); I != N; ++I) {
574     OS.indent(Indent + 2);
575     OS << "conflict ";
576     printModuleId(OS, UnresolvedConflicts[I].Id);
577     OS << ", \"";
578     OS.write_escaped(UnresolvedConflicts[I].Message);
579     OS << "\"\n";
580   }
581 
582   for (unsigned I = 0, N = Conflicts.size(); I != N; ++I) {
583     OS.indent(Indent + 2);
584     OS << "conflict ";
585     OS << Conflicts[I].Other->getFullModuleName(true);
586     OS << ", \"";
587     OS.write_escaped(Conflicts[I].Message);
588     OS << "\"\n";
589   }
590 
591   if (InferSubmodules) {
592     OS.indent(Indent + 2);
593     if (InferExplicitSubmodules)
594       OS << "explicit ";
595     OS << "module * {\n";
596     if (InferExportWildcard) {
597       OS.indent(Indent + 4);
598       OS << "export *\n";
599     }
600     OS.indent(Indent + 2);
601     OS << "}\n";
602   }
603 
604   OS.indent(Indent);
605   OS << "}\n";
606 }
607 
608 LLVM_DUMP_METHOD void Module::dump() const {
609   print(llvm::errs());
610 }
611 
612 void VisibleModuleSet::setVisible(Module *M, SourceLocation Loc,
613                                   VisibleCallback Vis, ConflictCallback Cb) {
614   assert(Loc.isValid() && "setVisible expects a valid import location");
615   if (isVisible(M))
616     return;
617 
618   ++Generation;
619 
620   struct Visiting {
621     Module *M;
622     Visiting *ExportedBy;
623   };
624 
625   std::function<void(Visiting)> VisitModule = [&](Visiting V) {
626     // Nothing to do for a module that's already visible.
627     unsigned ID = V.M->getVisibilityID();
628     if (ImportLocs.size() <= ID)
629       ImportLocs.resize(ID + 1);
630     else if (ImportLocs[ID].isValid())
631       return;
632 
633     ImportLocs[ID] = Loc;
634     Vis(M);
635 
636     // Make any exported modules visible.
637     SmallVector<Module *, 16> Exports;
638     V.M->getExportedModules(Exports);
639     for (Module *E : Exports) {
640       // Don't recurse to unavailable submodules.
641       if (E->isAvailable())
642         VisitModule({E, &V});
643     }
644 
645     for (auto &C : V.M->Conflicts) {
646       if (isVisible(C.Other)) {
647         llvm::SmallVector<Module*, 8> Path;
648         for (Visiting *I = &V; I; I = I->ExportedBy)
649           Path.push_back(I->M);
650         Cb(Path, C.Other, C.Message);
651       }
652     }
653   };
654   VisitModule({M, nullptr});
655 }
656