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