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