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