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