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