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