text: //===--- Module.cpp - Swift Language Module Implementation ----------------===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
  // Licensed under Apache License v2.0 with Runtime Library Exception
  //
  // See http://swift.org/LICENSE.txt for license information
  // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
  //
  //===----------------------------------------------------------------------===//
  //
  //  This file implements the Module class and subclasses.
  //
  //===----------------------------------------------------------------------===//
  
  #include "swift/AST/Module.h"
  #include "swift/AST/AST.h"
  #include "swift/AST/ASTPrinter.h"
  #include "swift/AST/ASTWalker.h"
  #include "swift/AST/DiagnosticsSema.h"
  #include "swift/AST/LazyResolver.h"
  #include "swift/AST/LinkLibrary.h"
  #include "swift/AST/ModuleLoader.h"
  #include "swift/AST/NameLookup.h"
  #include "swift/AST/ReferencedNameTracker.h"
  #include "swift/AST/PrettyStackTrace.h"
  #include "swift/AST/PrintOptions.h"
  #include "swift/Basic/SourceManager.h"
  #include "clang/Basic/Module.h"
  #include "llvm/ADT/DenseMap.h"
  #include "llvm/ADT/DenseSet.h"
  #include "llvm/ADT/TinyPtrVector.h"
  #include "llvm/ADT/SmallPtrSet.h"
  #include "llvm/ADT/StringExtras.h"
  #include "llvm/ADT/STLExtras.h"
  #include "llvm/Support/MD5.h"
  #include "llvm/Support/MemoryBuffer.h"
  #include "llvm/Support/Path.h"
  #include "llvm/Support/raw_ostream.h"
  #include "llvm/Support/SaveAndRestore.h"
  
  using namespace swift;
  
  //===----------------------------------------------------------------------===//
  // Builtin Module Name lookup
  //===----------------------------------------------------------------------===//
  
  class BuiltinUnit::LookupCache {
    /// The cache of identifiers we've already looked up.  We use a
    /// single hashtable for both types and values as a minor
    /// optimization; this prevents us from having both a builtin type
    /// and a builtin value with the same name, but that's okay.
    llvm::DenseMap<Identifier, ValueDecl*> Cache;
  
  public:
    void lookupValue(Identifier Name, NLKind LookupKind, const BuiltinUnit &M,
                     SmallVectorImpl<ValueDecl*> &Result);
  };
  
  BuiltinUnit::LookupCache &BuiltinUnit::getCache() const {
    // FIXME: This leaks. Sticking this into ASTContext isn't enough because then
    // the DenseMap will leak.
    if (!Cache)
      const_cast<BuiltinUnit *>(this)->Cache = llvm::make_unique<LookupCache>();
    return *Cache;
  }
  
  void BuiltinUnit::LookupCache::lookupValue(
         Identifier Name, NLKind LookupKind, const BuiltinUnit &M,
         SmallVectorImpl<ValueDecl*> &Result) {
    // Only qualified lookup ever finds anything in the builtin module.
    if (LookupKind != NLKind::QualifiedLookup) return;
    
    ValueDecl *&Entry = Cache[Name];
    ASTContext &Ctx = M.getParentModule()->getASTContext();
    if (!Entry) {
      if (Type Ty = getBuiltinType(Ctx, Name.str())) {
        TypeAliasDecl *TAD = new (Ctx) TypeAliasDecl(SourceLoc(), Name,
                                                     SourceLoc(),
                                                     TypeLoc::withoutLoc(Ty),
                                                     const_cast<BuiltinUnit*>(&M));
        TAD->computeType();
        TAD->setAccessibility(Accessibility::Public);
        Entry = TAD;
      }
    }
  
    if (!Entry)
      Entry = getBuiltinValueDecl(Ctx, Name);
  
    if (Entry)
      Result.push_back(Entry);
  }
  
  // Out-of-line because std::unique_ptr wants LookupCache to be complete.
  BuiltinUnit::BuiltinUnit(ModuleDecl &M)
     : FileUnit(FileUnitKind::Builtin, M) {
    M.getASTContext().addDestructorCleanup(*this);
  }
  
  //===----------------------------------------------------------------------===//
  // Normal Module Name Lookup
  //===----------------------------------------------------------------------===//
  
  class SourceFile::LookupCache {
    /// A lookup map for value decls. When declarations are added they are added
    /// under all variants of the name they can be found under.
    class DeclMap {
      llvm::DenseMap<DeclName, TinyPtrVector<ValueDecl*>> Members;
  
    public:
      void add(ValueDecl *VD) {
        if (!VD->hasName()) return;
        VD->getFullName().addToLookupTable(Members, VD);
      }
  
      void clear() {
        Members.shrink_and_clear();
      }
  
      decltype(Members)::const_iterator begin() const { return Members.begin(); }
      decltype(Members)::const_iterator end() const { return Members.end(); }
      decltype(Members)::const_iterator find(DeclName Name) const {
        return Members.find(Name);
      }
    };
  
    DeclMap TopLevelValues;
    DeclMap ClassMembers;
    bool MemberCachePopulated = false;
  
    template<typename Range>
    void doPopulateCache(Range decls, bool onlyOperators);
    void addToMemberCache(DeclRange decls);
    void populateMemberCache(const SourceFile &SF);
  public:
    typedef ModuleDecl::AccessPathTy AccessPathTy;
    
    LookupCache(const SourceFile &SF);
  
    /// Throw away as much memory as possible.
    void invalidate();
    
    void lookupValue(AccessPathTy AccessPath, DeclName Name,
                     NLKind LookupKind, SmallVectorImpl<ValueDecl*> &Result);
    
    void lookupVisibleDecls(AccessPathTy AccessPath,
                            VisibleDeclConsumer &Consumer,
                            NLKind LookupKind);
    
    void lookupClassMembers(AccessPathTy AccessPath,
                            VisibleDeclConsumer &consumer,
                            const SourceFile &SF);
                            
    void lookupClassMember(AccessPathTy accessPath,
                           DeclName name,
                           SmallVectorImpl<ValueDecl*> &results,
                           const SourceFile &SF);
  
    SmallVector<ValueDecl *, 0> AllVisibleValues;
  };
  using SourceLookupCache = SourceFile::LookupCache;
  
  SourceLookupCache &SourceFile::getCache() const {
    if (!Cache) {
      const_cast<SourceFile *>(this)->Cache =
          llvm::make_unique<SourceLookupCache>(*this);
    }
    return *Cache;
  }
  
  template<typename Range>
  void SourceLookupCache::doPopulateCache(Range decls,
                                          bool onlyOperators) {
    for (Decl *D : decls) {
      if (ValueDecl *VD = dyn_cast<ValueDecl>(D))
        if (onlyOperators ? VD->getName().isOperator() : VD->hasName()) {
          // Cache the value under both its compound name and its full name.
          TopLevelValues.add(VD);
        }
      if (NominalTypeDecl *NTD = dyn_cast<NominalTypeDecl>(D))
        doPopulateCache(NTD->getMembers(), true);
      if (ExtensionDecl *ED = dyn_cast<ExtensionDecl>(D))
        doPopulateCache(ED->getMembers(), true);
    }
  }
  
  void SourceLookupCache::populateMemberCache(const SourceFile &SF) {
    for (const Decl *D : SF.Decls) {
      if (const NominalTypeDecl *NTD = dyn_cast<NominalTypeDecl>(D)) {
        addToMemberCache(NTD->getMembers());
      } else if (const ExtensionDecl *ED = dyn_cast<ExtensionDecl>(D)) {
        addToMemberCache(ED->getMembers());
      }
    }
  
    MemberCachePopulated = true;
  }
  
  void SourceLookupCache::addToMemberCache(DeclRange decls) {
    for (Decl *D : decls) {
      auto VD = dyn_cast<ValueDecl>(D);
      if (!VD)
        continue;
  
      if (auto NTD = dyn_cast<NominalTypeDecl>(VD)) {
        assert(!VD->canBeAccessedByDynamicLookup() &&
               "inner types cannot be accessed by dynamic lookup");
        addToMemberCache(NTD->getMembers());
      } else if (VD->canBeAccessedByDynamicLookup()) {
        ClassMembers.add(VD);
      }
    }
  }
  
  /// Populate our cache on the first name lookup.
  SourceLookupCache::LookupCache(const SourceFile &SF) {
    doPopulateCache(llvm::makeArrayRef(SF.Decls), false);
  }
  
  void SourceLookupCache::lookupValue(AccessPathTy AccessPath, DeclName Name,
                                      NLKind LookupKind,
                                      SmallVectorImpl<ValueDecl*> &Result) {
    // If this import is specific to some named type or decl ("import Swift.int")
    // then filter out any lookups that don't match.
    if (!ModuleDecl::matchesAccessPath(AccessPath, Name))
      return;
    
    auto I = TopLevelValues.find(Name);
    if (I == TopLevelValues.end()) return;
    
    Result.reserve(I->second.size());
    for (ValueDecl *Elt : I->second)
      Result.push_back(Elt);
  }
  
  void SourceLookupCache::lookupVisibleDecls(AccessPathTy AccessPath,
                                             VisibleDeclConsumer &Consumer,
                                             NLKind LookupKind) {
    assert(AccessPath.size() <= 1 && "can only refer to top-level decls");
  
    if (!AccessPath.empty()) {
      auto I = TopLevelValues.find(AccessPath.front().first);
      if (I == TopLevelValues.end()) return;
  
      for (auto vd : I->second)
        Consumer.foundDecl(vd, DeclVisibilityKind::VisibleAtTopLevel);
      return;
    }
  
    for (auto &tlv : TopLevelValues) {
      for (ValueDecl *vd : tlv.second) {
        // Declarations are added under their full and simple names.  Skip the
        // entry for the simple name so that we report each declaration once.
        if (tlv.first.isSimpleName() && !vd->getFullName().isSimpleName())
          continue;
        Consumer.foundDecl(vd, DeclVisibilityKind::VisibleAtTopLevel);
      }
    }
  }
  
  void SourceLookupCache::lookupClassMembers(AccessPathTy accessPath,
                                             VisibleDeclConsumer &consumer,
                                             const SourceFile &SF) {
    if (!MemberCachePopulated)
      populateMemberCache(SF);
    
    assert(accessPath.size() <= 1 && "can only refer to top-level decls");
    
    if (!accessPath.empty()) {
      for (auto &member : ClassMembers) {
        // Non-simple names are also stored under their simple name, so make
        // sure to only report them once.
        if (!member.first.isSimpleName())
          continue;
  
        for (ValueDecl *vd : member.second) {
          Type ty = vd->getDeclContext()->getDeclaredTypeOfContext();
          if (auto nominal = ty->getAnyNominal())
            if (nominal->getName() == accessPath.front().first)
              consumer.foundDecl(vd, DeclVisibilityKind::DynamicLookup);
        }
      }
      return;
    }
  
    for (auto &member : ClassMembers) {
      // Non-simple names are also stored under their simple name, so make sure to
      // only report them once.
      if (!member.first.isSimpleName())
        continue;
  
      for (ValueDecl *vd : member.second)
        consumer.foundDecl(vd, DeclVisibilityKind::DynamicLookup);
    }
  }
  
  void SourceLookupCache::lookupClassMember(AccessPathTy accessPath,
                                            DeclName name,
                                            SmallVectorImpl<ValueDecl*> &results,
                                            const SourceFile &SF) {
    if (!MemberCachePopulated)
      populateMemberCache(SF);
    
    assert(accessPath.size() <= 1 && "can only refer to top-level decls");
    
    auto iter = ClassMembers.find(name);
    if (iter == ClassMembers.end())
      return;
    
    if (!accessPath.empty()) {
      for (ValueDecl *vd : iter->second) {
        Type ty = vd->getDeclContext()->getDeclaredTypeOfContext();
        if (auto nominal = ty->getAnyNominal())
          if (nominal->getName() == accessPath.front().first)
            results.push_back(vd);
      }
      return;
    }
  
    results.append(iter->second.begin(), iter->second.end());
  }
  
  void SourceLookupCache::invalidate() {
    TopLevelValues.clear();
    ClassMembers.clear();
    MemberCachePopulated = false;
  
    // std::move AllVisibleValues into a temporary to destroy its contents.
    using SameSizeSmallVector = decltype(AllVisibleValues);
    (void)SameSizeSmallVector{std::move(AllVisibleValues)};
  }
  
  //===----------------------------------------------------------------------===//
  // Module Implementation
  //===----------------------------------------------------------------------===//
  
  ModuleDecl::ModuleDecl(Identifier name, ASTContext &ctx)
    : TypeDecl(DeclKind::Module, &ctx, name, SourceLoc(), { }),
      DeclContext(DeclContextKind::Module, nullptr),
      Flags({0, 0, 0}), DSOHandle(nullptr) {
    ctx.addDestructorCleanup(*this);
    setImplicit();
    setType(ModuleType::get(this));
    setAccessibility(Accessibility::Public);
  }
  
  void Module::addFile(FileUnit &newFile) {
    assert(!isa<DerivedFileUnit>(newFile) &&
           "DerivedFileUnits are added automatically");
  
    // Require Main and REPL files to be the first file added.
    assert(Files.empty() ||
           !isa<SourceFile>(newFile) ||
           cast<SourceFile>(newFile).Kind == SourceFileKind::Library ||
           cast<SourceFile>(newFile).Kind == SourceFileKind::SIL);
    Files.push_back(&newFile);
  
    switch (newFile.getKind()) {
    case FileUnitKind::Source:
    case FileUnitKind::ClangModule: {
      for (auto File : Files) {
        if (isa<DerivedFileUnit>(File))
          return;
      }
      auto DFU = new (getASTContext()) DerivedFileUnit(*this);
      Files.push_back(DFU);
      break;
    }
  
    case FileUnitKind::Builtin:
    case FileUnitKind::SerializedAST:
      break;
  
    case FileUnitKind::Derived:
      llvm_unreachable("DerivedFileUnits are added automatically");
    }
  }
  
  void Module::removeFile(FileUnit &existingFile) {
    // Do a reverse search; usually the file to be deleted will be at the end.
    std::reverse_iterator<decltype(Files)::iterator> I(Files.end()),
    E(Files.begin());
    I = std::find(I, E, &existingFile);
    assert(I != E);
  
    // Adjust for the std::reverse_iterator offset.
    ++I;
    Files.erase(I.base());
  }
  
  DerivedFileUnit &Module::getDerivedFileUnit() const {
    for (auto File : Files) {
      if (auto DFU = dyn_cast<DerivedFileUnit>(File))
        return *DFU;
    }
    llvm_unreachable("the client should not be calling this function if "
                     "there is no DerivedFileUnit");
  }
  
  VarDecl *Module::getDSOHandle() {
    if (DSOHandle)
      return DSOHandle;
  
    auto unsafeMutablePtr = getASTContext().getUnsafeMutablePointerDecl();
    if (!unsafeMutablePtr)
      return nullptr;
  
    Type arg;
    auto &ctx = getASTContext();
    if (auto voidDecl = ctx.getVoidDecl()) {
      arg = voidDecl->getDeclaredInterfaceType();
    } else {
      arg = TupleType::getEmpty(ctx);
    }
    
    Type type = BoundGenericType::get(unsafeMutablePtr, Type(), { arg });
    auto handleVar = new (ctx) VarDecl(/*IsStatic=*/false, /*IsLet=*/false,
                                       SourceLoc(),
                                       ctx.getIdentifier("__dso_handle"),
                                       type, Files[0]);
    handleVar->setImplicit(true);
    handleVar->getAttrs().add(
      new (ctx) SILGenNameAttr("__dso_handle", /*Implicit=*/true));
    handleVar->setAccessibility(Accessibility::Internal);
    DSOHandle = handleVar;
    return handleVar;
  }
  
  #define FORWARD(name, args) \
    for (const FileUnit *file : getFiles()) \
      file->name args;
  
  void Module::lookupValue(AccessPathTy AccessPath, DeclName Name,
                           NLKind LookupKind, 
                           SmallVectorImpl<ValueDecl*> &Result) const {
    FORWARD(lookupValue, (AccessPath, Name, LookupKind, Result));
  }
  
  TypeDecl * Module::lookupLocalType(StringRef MangledName) const {
    for (auto file : getFiles()) {
      auto TD = file->lookupLocalType(MangledName);
      if (TD)
        return TD;
    }
    return nullptr;
  }
  
  void Module::lookupMember(SmallVectorImpl<ValueDecl*> &results,
                            DeclContext *container, DeclName name,
                            Identifier privateDiscriminator) const {
    size_t oldSize = results.size();
    bool alreadyInPrivateContext = false;
  
    switch (container->getContextKind()) {
    case DeclContextKind::SerializedLocal:
    case DeclContextKind::AbstractClosureExpr:
    case DeclContextKind::Initializer:
    case DeclContextKind::TopLevelCodeDecl:
    case DeclContextKind::AbstractFunctionDecl:
    case DeclContextKind::SubscriptDecl:
      llvm_unreachable("This context does not support lookup.");
  
    case DeclContextKind::FileUnit:
      llvm_unreachable("Use FileUnit::lookupValue instead.");
  
    case DeclContextKind::ExtensionDecl:
      llvm_unreachable("Use ExtensionDecl::lookupDirect instead.");
  
    case DeclContextKind::Module: {
      assert(container == this);
      this->lookupValue({}, name, NLKind::QualifiedLookup, results);
      break;
    }
  
    case DeclContextKind::NominalTypeDecl: {
      auto nominal = cast<NominalTypeDecl>(container);
      auto lookupResults = nominal->lookupDirect(name);
  
      // Filter out declarations from other modules.
      std::copy_if(lookupResults.begin(), lookupResults.end(),
                   std::back_inserter(results),
                   [this](const ValueDecl *VD) -> bool {
        return VD->getModuleContext() == this;
      });
  
      alreadyInPrivateContext =
        (nominal->getFormalAccess() == Accessibility::Private);
  
      break;
    }
    }
  
    // Filter by private-discriminator, or filter out private decls if there isn't
    // one...unless we're already in a private context, in which case everything
    // is private and a discriminator is unnecessary.
    if (alreadyInPrivateContext) {
      assert(privateDiscriminator.empty() && "unnecessary private-discriminator");
      // Don't remove anything; everything here is private anyway.
  
    } else if (privateDiscriminator.empty()) {
      auto newEnd = std::remove_if(results.begin()+oldSize, results.end(),
                                   [](const ValueDecl *VD) -> bool {
        return VD->getFormalAccess() <= Accessibility::Private;
      });
      results.erase(newEnd, results.end());
  
    } else {
      auto newEnd = std::remove_if(results.begin()+oldSize, results.end(),
                                   [=](const ValueDecl *VD) -> bool {
        if (VD->getFormalAccess() > Accessibility::Private)
          return true;
        auto enclosingFile =
          cast<FileUnit>(VD->getDeclContext()->getModuleScopeContext());
        auto discriminator = enclosingFile->getDiscriminatorForPrivateValue(VD);
        return discriminator != privateDiscriminator;
      });
      results.erase(newEnd, results.end());
    }
  }
  
  void Module::lookupObjCMethods(
         ObjCSelector selector,
         SmallVectorImpl<AbstractFunctionDecl *> &results) const {
    FORWARD(lookupObjCMethods, (selector, results));
  }
  
  void BuiltinUnit::lookupValue(Module::AccessPathTy accessPath, DeclName name,
                                NLKind lookupKind,
                                SmallVectorImpl<ValueDecl*> &result) const {
    getCache().lookupValue(name.getBaseName(), lookupKind, *this, result);
  }
  
  void BuiltinUnit::lookupObjCMethods(
         ObjCSelector selector,
         SmallVectorImpl<AbstractFunctionDecl *> &results) const {
    // No @objc methods in the Builtin module.
  }
  
  DerivedFileUnit::DerivedFileUnit(Module &M)
      : FileUnit(FileUnitKind::Derived, M) {
    M.getASTContext().addDestructorCleanup(*this);
  }
  
  void DerivedFileUnit::lookupValue(Module::AccessPathTy accessPath,
                                    DeclName name,
                                    NLKind lookupKind,
                                    SmallVectorImpl<ValueDecl*> &result) const {
    // If this import is specific to some named type or decl ("import Swift.int")
    // then filter out any lookups that don't match.
    if (!Module::matchesAccessPath(accessPath, name))
      return;
    
    for (auto D : DerivedDecls) {
      if (D->getFullName().matchesRef(name))
        result.push_back(D);
    }
  }
  
  void DerivedFileUnit::lookupVisibleDecls(Module::AccessPathTy accessPath,
                                           VisibleDeclConsumer &consumer,
                                           NLKind lookupKind) const {
    assert(accessPath.size() <= 1 && "can only refer to top-level decls");
    
    Identifier Id;
    if (!accessPath.empty()) {
      Id = accessPath.front().first;
    }
  
    for (auto D : DerivedDecls) {
      if (Id.empty() || D->getName() == Id)
        consumer.foundDecl(D, DeclVisibilityKind::VisibleAtTopLevel);
    }
  }
  
  void DerivedFileUnit::lookupObjCMethods(
         ObjCSelector selector,
         SmallVectorImpl<AbstractFunctionDecl *> &results) const {
    for (auto D : DerivedDecls) {
      if (auto func = dyn_cast<AbstractFunctionDecl>(D)) {
        if (func->isObjC() && func->getObjCSelector() == selector)
          results.push_back(func);
      }
    }
  }
  
  void DerivedFileUnit::getTopLevelDecls(SmallVectorImpl<swift::Decl *> &results)
  const {
    results.append(DerivedDecls.begin(), DerivedDecls.end());
  }
  
  void SourceFile::lookupValue(Module::AccessPathTy accessPath, DeclName name,
                               NLKind lookupKind,
                               SmallVectorImpl<ValueDecl*> &result) const {
    getCache().lookupValue(accessPath, name, lookupKind, result);
  }
  
  void Module::lookupVisibleDecls(AccessPathTy AccessPath,
                                  VisibleDeclConsumer &Consumer,
                                  NLKind LookupKind) const {
    FORWARD(lookupVisibleDecls, (AccessPath, Consumer, LookupKind));
  }
  
  void SourceFile::lookupVisibleDecls(Module::AccessPathTy AccessPath,
                                      VisibleDeclConsumer &Consumer,
                                      NLKind LookupKind) const {
    getCache().lookupVisibleDecls(AccessPath, Consumer, LookupKind);
  }
  
  void Module::lookupClassMembers(AccessPathTy accessPath,
                                  VisibleDeclConsumer &consumer) const {
    FORWARD(lookupClassMembers, (accessPath, consumer));
  }
  
  void SourceFile::lookupClassMembers(Module::AccessPathTy accessPath,
                                      VisibleDeclConsumer &consumer) const {
    getCache().lookupClassMembers(accessPath, consumer, *this);
  }
  
  void Module::lookupClassMember(AccessPathTy accessPath,
                                 DeclName name,
                                 SmallVectorImpl<ValueDecl*> &results) const {
    FORWARD(lookupClassMember, (accessPath, name, results));
  }
  
  void SourceFile::lookupClassMember(Module::AccessPathTy accessPath,
                                     DeclName name,
                                     SmallVectorImpl<ValueDecl*> &results) const {
    getCache().lookupClassMember(accessPath, name, results, *this);
  }
  
  void SourceFile::lookupObjCMethods(
         ObjCSelector selector,
         SmallVectorImpl<AbstractFunctionDecl *> &results) const {
    // FIXME: Make sure this table is complete, somehow.
    auto known = ObjCMethods.find(selector);
    if (known == ObjCMethods.end()) return;
    results.append(known->second.begin(), known->second.end());
  }
  
  void Module::getLocalTypeDecls(SmallVectorImpl<TypeDecl*> &Results) const {
    FORWARD(getLocalTypeDecls, (Results));
  }
  
  void Module::getTopLevelDecls(SmallVectorImpl<Decl*> &Results) const {
    FORWARD(getTopLevelDecls, (Results));
  }
  
  void SourceFile::getTopLevelDecls(SmallVectorImpl<Decl*> &Results) const {
    Results.append(Decls.begin(), Decls.end());
  }
  
  void SourceFile::getLocalTypeDecls(SmallVectorImpl<TypeDecl*> &Results) const {
    Results.append(LocalTypeDecls.begin(), LocalTypeDecls.end());
  }
  
  void Module::getDisplayDecls(SmallVectorImpl<Decl*> &Results) const {
    // FIXME: Should this do extra access control filtering?
    FORWARD(getDisplayDecls, (Results));
  }
  
  DeclContext *BoundGenericType::getGenericParamContext(
                 DeclContext *gpContext) const {
    // If no context was provided, use the declaration itself.
    if (!gpContext)
      return getDecl();
  
    assert(gpContext->isNominalTypeOrNominalTypeExtensionContext() == getDecl() &&
           "not a valid context");
    return gpContext;
  }
  
  ArrayRef<Substitution> BoundGenericType::getSubstitutions(
                                             Module *module,
                                             LazyResolver *resolver,
                                             DeclContext *gpContext) {
    // FIXME: If there is no module, infer one. This is a hack for callers that
    // don't have access to the module. It will have to go away once we're
    // properly differentiating bound generic types based on the protocol
    // conformances visible from a given module.
    if (!module) {
      module = getDecl()->getParentModule();
    }
  
    // Check the context, introducing the default if needed.
    gpContext = getGenericParamContext(gpContext);
  
    // If we already have a cached copy of the substitutions, return them.
    auto *canon = getCanonicalType()->castTo<BoundGenericType>();
    const ASTContext &ctx = canon->getASTContext();
    if (auto known = ctx.getSubstitutions(canon, gpContext))
      return *known;
  
    // Compute the set of substitutions.
    TypeSubstitutionMap substitutions;
    auto genericParams = gpContext->getGenericParamsOfContext();
    unsigned index = 0;
    for (Type arg : canon->getGenericArgs()) {
      auto gp = genericParams->getParams()[index++];
      auto archetype = gp->getArchetype();
      substitutions[archetype] = arg;
    }
  
    // Collect all of the archetypes.
    SmallVector<ArchetypeType *, 2> allArchetypesList;
    ArrayRef<ArchetypeType *> allArchetypes = genericParams->getAllArchetypes();
    if (genericParams->getOuterParameters()) {
      SmallVector<const GenericParamList *, 2> allGenericParams;
      unsigned numArchetypes = 0;
      for (; genericParams; genericParams = genericParams->getOuterParameters()) {
        allGenericParams.push_back(genericParams);
        numArchetypes += genericParams->getAllArchetypes().size();
      }
      allArchetypesList.reserve(numArchetypes);
      for (auto gp = allGenericParams.rbegin(), gpEnd = allGenericParams.rend();
           gp != gpEnd; ++gp) {
        allArchetypesList.append((*gp)->getAllArchetypes().begin(),
                                 (*gp)->getAllArchetypes().end());
      }
      allArchetypes = allArchetypesList;
    }
  
    // For each of the archetypes, compute the substitution.
    bool hasTypeVariables = canon->hasTypeVariable();
    SmallVector<Substitution, 4> resultSubstitutions;
    resultSubstitutions.resize(allArchetypes.size());
    index = 0;
    for (auto archetype : allArchetypes) {
      // Substitute into the type.
      SubstOptions options;
      if (hasTypeVariables)
        options |= SubstFlags::IgnoreMissing;
      auto type = Type(archetype).subst(module, substitutions, options);
      if (!type)
        type = ErrorType::get(module->getASTContext());
  
      SmallVector<ProtocolConformanceRef, 4> conformances;
      for (auto proto : archetype->getConformsTo()) {
        // If the type is a type variable or is dependent, just fill in null
        // conformances.
        if (type->is<TypeVariableType>() || type->isTypeParameter()) {
          conformances.push_back(ProtocolConformanceRef(proto));
  
        // Otherwise, find the conformances.
        } else {
          auto conforms = module->lookupConformance(type, proto, resolver);
          switch (conforms.getInt()) {
          case ConformanceKind::Conforms:
            conformances.push_back(
                           ProtocolConformanceRef(proto, conforms.getPointer()));
            break;
          case ConformanceKind::UncheckedConforms:
          case ConformanceKind::DoesNotConform:
            conformances.push_back(ProtocolConformanceRef(proto));
            break;
          }
        }
      }
  
      // Record this substitution.
      resultSubstitutions[index] = {type, ctx.AllocateCopy(conformances)};
      ++index;
    }
  
    // Before recording substitutions, make sure we didn't end up doing it
    // recursively.
    if (auto known = ctx.getSubstitutions(canon, gpContext))
      return *known;
  
    // Copy and record the substitutions.
    auto permanentSubs = ctx.AllocateCopy(resultSubstitutions,
                                          hasTypeVariables
                                            ? AllocationArena::ConstraintSolver
                                            : AllocationArena::Permanent);
    ctx.setSubstitutions(canon, gpContext, permanentSubs);
    return permanentSubs;
  }
  
  LookupConformanceResult Module::lookupConformance(Type type,
                                                    ProtocolDecl *protocol,
                                                    LazyResolver *resolver) {
    ASTContext &ctx = getASTContext();
  
    // An archetype conforms to a protocol if the protocol is listed in the
    // archetype's list of conformances.
    if (auto archetype = type->getAs<ArchetypeType>()) {
      if (protocol->isSpecificProtocol(KnownProtocolKind::AnyObject)) {
        if (archetype->requiresClass())
          return { nullptr, ConformanceKind::Conforms };
        return { nullptr, ConformanceKind::DoesNotConform };
      }
  
      for (auto ap : archetype->getConformsTo()) {
        if (ap == protocol || ap->inheritsFrom(protocol))
          return { nullptr, ConformanceKind::Conforms };
      }
  
      if (!archetype->getSuperclass()) {
        return { nullptr, ConformanceKind::DoesNotConform };
      }
    }
  
    // An existential conforms to a protocol if the protocol is listed in the
    // existential's list of conformances and the existential conforms to
    // itself.
    if (type->isExistentialType()) {
      SmallVector<ProtocolDecl *, 4> protocols;
      type->getAnyExistentialTypeProtocols(protocols);
  
      // Due to an IRGen limitation, witness tables cannot be passed from an
      // existential to an archetype parameter, so for now we restrict this to
      // @objc protocols.
      for (auto proto : protocols) {
        if (!proto->isObjC() &&
            !proto->isSpecificProtocol(KnownProtocolKind::AnyObject))
          return { nullptr, ConformanceKind::DoesNotConform };
      }
  
      // If the existential type cannot be represented or the protocol does not
      // conform to itself, there's no point in looking further.
      if (!protocol->existentialConformsToSelf() ||
          !protocol->existentialTypeSupported(resolver))
        return { nullptr, ConformanceKind::DoesNotConform };
  
      // Special-case AnyObject, which may not be in the list of conformances.
      if (protocol->isSpecificProtocol(KnownProtocolKind::AnyObject)) {
        return { nullptr, type->isClassExistentialType()
                            ? ConformanceKind::Conforms
                            : ConformanceKind::DoesNotConform };
      }
  
      // Look for this protocol within the existential's list of conformances.
      for (auto proto : protocols) {
        if (proto == protocol || proto->inheritsFrom(protocol)) {
          return { nullptr, ConformanceKind::Conforms };
        }
      }
  
      // We didn't find our protocol in the existential's list; it doesn't
      // conform.
      return { nullptr, ConformanceKind::DoesNotConform };
    }
  
    // Check for protocol conformance of archetype via superclass requirement.
    if (auto archetype = type->getAs<ArchetypeType>()) {
      if (auto super = archetype->getSuperclass()) {
        auto inheritedConformance = lookupConformance(super, protocol, resolver);
        switch (inheritedConformance.getInt()) {
        case ConformanceKind::DoesNotConform:
          return { nullptr, ConformanceKind::DoesNotConform };
        case ConformanceKind::UncheckedConforms:
          return inheritedConformance;
        case ConformanceKind::Conforms:
          auto result =
            ctx.getInheritedConformance(type, inheritedConformance.getPointer());
          return { result, ConformanceKind::Conforms };
        }
      }
    }
  
    // UnresolvedType is a placeholder for an unknown type used when generating
    // diagnostics.  We consider it to conform to all protocols, since the
    // intended type might have.
    if (type->is<UnresolvedType>()) {
      return {
        ctx.getConformance(type, protocol, protocol->getLoc(), this,
                           ProtocolConformanceState::Complete),
        ConformanceKind::Conforms
      };
    }
    
    
    auto nominal = type->getAnyNominal();
  
    // If we don't have a nominal type, there are no conformances.
    // FIXME: We may have implicit conformances for some cases. Handle those
    // here.
    if (!nominal) {
      return { nullptr, ConformanceKind::DoesNotConform };
    }
  
    // Find the (unspecialized) conformance.
    SmallVector<ProtocolConformance *, 2> conformances;
    if (!nominal->lookupConformance(this, protocol, conformances))
      return { nullptr, ConformanceKind::DoesNotConform };
  
    // FIXME: Ambiguity resolution.
    auto conformance = conformances.front();
  
    // Rebuild inherited conformances based on the root normal conformance.
    // FIXME: This is a hack to work around our inability to handle multiple
    // levels of substitution through inherited conformances elsewhere in the
    // compiler.
    if (auto inherited = dyn_cast<InheritedProtocolConformance>(conformance)) {
      // Dig out the conforming nominal type.
      auto rootConformance = inherited->getRootNormalConformance();
      auto conformingNominal
        = rootConformance->getType()->getClassOrBoundGenericClass();
  
      // Map up to our superclass's type.
      Type superclassTy = type->getSuperclass(resolver);
      while (superclassTy->getAnyNominal() != conformingNominal)
        superclassTy = superclassTy->getSuperclass(resolver);
  
      // Compute the conformance for the inherited type.
      auto inheritedConformance = lookupConformance(superclassTy, protocol,
                                                    resolver);
      switch (inheritedConformance.getInt()) {
      case ConformanceKind::DoesNotConform:
        llvm_unreachable("We already found the inherited conformance");
  
      case ConformanceKind::UncheckedConforms:
        return inheritedConformance;
  
      case ConformanceKind::Conforms:
        // Create inherited conformance below.
        break;
      }
  
      // Create the inherited conformance entry.
      conformance
        = ctx.getInheritedConformance(type, inheritedConformance.getPointer());
      return { conformance, ConformanceKind::Conforms };
    }
  
    // If the type is specialized, find the conformance for the generic type.
    if (type->isSpecialized()) {
      // Figure out the type that's explicitly conforming to this protocol.
      Type explicitConformanceType = conformance->getType();
      DeclContext *explicitConformanceDC = conformance->getDeclContext();
  
      // If the explicit conformance is associated with a type that is different
      // from the type we're checking, retrieve generic conformance.
      if (!explicitConformanceType->isEqual(type)) {
        // Gather the substitutions we need to map the generic conformance to
        // the specialized conformance.
        SmallVector<Substitution, 4> substitutionsVec;
        auto substitutions = type->gatherAllSubstitutions(this, substitutionsVec,
                                                          resolver,
                                                          explicitConformanceDC);
        
        for (auto sub : substitutions) {
          if (sub.getReplacement()->is<ErrorType>())
            return { nullptr, ConformanceKind::DoesNotConform };
        }
  
        // Create the specialized conformance entry.
        auto result = ctx.getSpecializedConformance(type, conformance,
                                                    substitutions);
        return { result, ConformanceKind::Conforms };
      }
    }
  
    // Record and return the simple conformance.
    return { conformance, ConformanceKind::Conforms };
  }
  
  namespace {
    template <typename T>
    using OperatorMap = SourceFile::OperatorMap<T>;
  
    template <typename T>
    struct OperatorKind {
      static_assert(static_cast<T*>(nullptr), "Only usable with operators");
    };
  
    template <>
    struct OperatorKind<PrefixOperatorDecl> {
      static const auto value = DeclKind::PrefixOperator;
    };
  
    template <>
    struct OperatorKind<InfixOperatorDecl> {
      static const auto value = DeclKind::InfixOperator;
    };
  
    template <>
    struct OperatorKind<PostfixOperatorDecl> {
      static const auto value = DeclKind::PostfixOperator;
    };
  }
  
  template <typename Op, typename T>
  static Op *lookupOperator(T &container, Identifier name) {
    return cast_or_null<Op>(container.lookupOperator(name,
                                                     OperatorKind<Op>::value));
  }
  
  /// A helper class to sneak around C++ access control rules.
  class SourceFile::Impl {
  public:
    /// Only intended for use by lookupOperatorDeclForName.
    static ArrayRef<std::pair<Module::ImportedModule, SourceFile::ImportOptions>>
    getImportsForSourceFile(const SourceFile &SF) {
      return SF.Imports;
    }
  };
  
  
  template<typename OP_DECL>
  static Optional<OP_DECL *>
  lookupOperatorDeclForName(Module *M, SourceLoc Loc, Identifier Name,
                            OperatorMap<OP_DECL *> SourceFile::*OP_MAP);
  
  // Returns None on error, Optional(nullptr) if no operator decl found, or
  // Optional(decl) if decl was found.
  template<typename OP_DECL>
  static Optional<OP_DECL *>
  lookupOperatorDeclForName(const FileUnit &File, SourceLoc Loc, Identifier Name,
                            bool includePrivate,
                            OperatorMap<OP_DECL *> SourceFile::*OP_MAP)
  {
    switch (File.getKind()) {
    case FileUnitKind::Builtin:
    case FileUnitKind::Derived:
      // The Builtin module declares no operators, nor do derived units.
      return nullptr;
    case FileUnitKind::Source:
      break;
    case FileUnitKind::SerializedAST:
    case FileUnitKind::ClangModule:
      return lookupOperator<OP_DECL>(cast<LoadedFile>(File), Name);
    }
  
    auto &SF = cast<SourceFile>(File);
    assert(SF.ASTStage >= SourceFile::NameBound);
  
    // Look for an operator declaration in the current module.
    auto found = (SF.*OP_MAP).find(Name);
    if (found != (SF.*OP_MAP).end() && (includePrivate || found->second.getInt()))
      return found->second.getPointer();
  
    // Look for imported operator decls.
    // Record whether they come from re-exported modules.
    // FIXME: We ought to prefer operators elsewhere in this module before we
    // check imports.
    llvm::SmallDenseMap<OP_DECL*, bool, 16> importedOperators;
    for (auto &imported : SourceFile::Impl::getImportsForSourceFile(SF)) {
      bool isExported =
          imported.second.contains(SourceFile::ImportFlags::Exported);
      if (!includePrivate && !isExported)
        continue;
  
      Optional<OP_DECL *> maybeOp
        = lookupOperatorDeclForName(imported.first.second, Loc, Name, OP_MAP);
      if (!maybeOp)
        return None;
      
      if (OP_DECL *op = *maybeOp)
        importedOperators[op] |= isExported;
    }
  
    typename OperatorMap<OP_DECL *>::mapped_type result = { nullptr, true };
    
    if (!importedOperators.empty()) {
      // Check for conflicts.
      auto i = importedOperators.begin(), end = importedOperators.end();
      auto start = i;
      for (++i; i != end; ++i) {
        if (i->first->conflictsWith(start->first)) {
          if (Loc.isValid()) {
            ASTContext &C = SF.getASTContext();
            C.Diags.diagnose(Loc, diag::ambiguous_operator_decls);
            C.Diags.diagnose(start->first->getLoc(),
                             diag::found_this_operator_decl);
            C.Diags.diagnose(i->first->getLoc(), diag::found_this_operator_decl);
          }
          return None;
        }
      }
      result = { start->first, start->second };
    }
  
    if (includePrivate) {
      // Cache the mapping so we don't need to troll imports next time.
      // It's not safe to cache the non-private results because we didn't search
      // private imports there, but in most non-private cases the result will
      // be cached in the final lookup.
      auto &mutableOpMap = const_cast<OperatorMap<OP_DECL *> &>(SF.*OP_MAP);
      mutableOpMap[Name] = result;
    }
  
    if (includePrivate || result.getInt())
      return result.getPointer();
    return nullptr;
  }
  
  template<typename OP_DECL>
  static Optional<OP_DECL *>
  lookupOperatorDeclForName(Module *M, SourceLoc Loc, Identifier Name,
                            OperatorMap<OP_DECL *> SourceFile::*OP_MAP)
  {
    OP_DECL *result = nullptr;
    for (const FileUnit *File : M->getFiles()) {
      auto next = lookupOperatorDeclForName(*File, Loc, Name, false, OP_MAP);
      if (!next.hasValue())
        return next;
  
      // FIXME: Diagnose ambiguity.
      if (*next && result)
        return None;
      if (*next)
        result = *next;
    }
    return result;
  }
  
  #define LOOKUP_OPERATOR(Kind) \
  Kind##OperatorDecl * \
  Module::lookup##Kind##Operator(Identifier name, SourceLoc loc) { \
    auto result = lookupOperatorDeclForName(this, loc, name, \
                                            &SourceFile::Kind##Operators); \
    return result ? *result : nullptr; \
  } \
  Kind##OperatorDecl * \
  SourceFile::lookup##Kind##Operator(Identifier name, bool isCascading, \
                                     SourceLoc loc) { \
    auto result = lookupOperatorDeclForName(*this, loc, name, true, \
                                            &SourceFile::Kind##Operators); \
    if (!result.hasValue()) \
      return nullptr; \
    if (ReferencedNames) {\
      if (!result.getValue() || \
          result.getValue()->getDeclContext()->getModuleScopeContext() != this) {\
        ReferencedNames->addTopLevelName(name, isCascading); \
      } \
    } \
    if (!result.getValue()) { \
      result = lookupOperatorDeclForName(getParentModule(), loc, name, \
                                         &SourceFile::Kind##Operators); \
    } \
    return result.hasValue() ? result.getValue() : nullptr; \
  }
  
  LOOKUP_OPERATOR(Prefix)
  LOOKUP_OPERATOR(Infix)
  LOOKUP_OPERATOR(Postfix)
  #undef LOOKUP_OPERATOR
  
  void Module::getImportedModules(SmallVectorImpl<ImportedModule> &modules,
                                  Module::ImportFilter filter) const {
    FORWARD(getImportedModules, (modules, filter));
  }
  
  void
  SourceFile::getImportedModules(SmallVectorImpl<Module::ImportedModule> &modules,
                                 Module::ImportFilter filter) const {
    assert(ASTStage >= Parsed || Kind == SourceFileKind::SIL);
    for (auto importPair : Imports) {
      switch (filter) {
      case Module::ImportFilter::All:
        break;
      case Module::ImportFilter::Public:
        if (!importPair.second.contains(ImportFlags::Exported))
          continue;
        break;
      case Module::ImportFilter::Private:
        if (importPair.second.contains(ImportFlags::Exported))
          continue;
        break;
      }
  
      modules.push_back(importPair.first);
    }
  }
  
  void Module::getImportedModulesForLookup(
      SmallVectorImpl<ImportedModule> &modules) const {
    FORWARD(getImportedModulesForLookup, (modules));
  }
  
  bool Module::isSameAccessPath(AccessPathTy lhs, AccessPathTy rhs) {
    using AccessPathElem = std::pair<Identifier, SourceLoc>;
    if (lhs.size() != rhs.size())
      return false;
    return std::equal(lhs.begin(), lhs.end(), rhs.begin(),
                      [](const AccessPathElem &lElem,
                         const AccessPathElem &rElem) {
      return lElem.first == rElem.first;
    });
  }
  
  StringRef Module::getModuleFilename() const {
    // FIXME: Audit uses of this function and figure out how to migrate them to
    // per-file names. Modules can consist of more than one file.
    StringRef Result;
    for (auto F : getFiles()) {
      if (auto SF = dyn_cast<SourceFile>(F)) {
        if (!Result.empty())
          return StringRef();
        Result = SF->getFilename();
        continue;
      }
      if (auto LF = dyn_cast<LoadedFile>(F)) {
        if (!Result.empty())
          return StringRef();
        Result = LF->getFilename();
        continue;
      }
      if (isa<DerivedFileUnit>(F))
        continue;
      return StringRef();
    }
    return Result;
  }
  
  bool Module::isStdlibModule() const {
    return !getParent() && getName() == getASTContext().StdlibModuleName;
  }
  
  bool Module::isSwiftShimsModule() const {
    return !getParent() && getName() == getASTContext().SwiftShimsModuleName;
  }
  
  bool Module::isBuiltinModule() const {
    return this == getASTContext().TheBuiltinModule;
  }
  
  bool SourceFile::registerMainClass(ClassDecl *mainClass, SourceLoc diagLoc) {
    if (mainClass == MainClass)
      return false;
  
    ArtificialMainKind kind = mainClass->getArtificialMainKind();
    if (getParentModule()->registerEntryPointFile(this, diagLoc, kind))
      return true;
  
    MainClass = mainClass;
    MainClassDiagLoc = diagLoc;
    return false;
  }
  
  bool Module::registerEntryPointFile(FileUnit *file, SourceLoc diagLoc,
                                      Optional<ArtificialMainKind> kind) {
    if (!EntryPointInfo.hasEntryPoint()) {
      EntryPointInfo.setEntryPointFile(file);
      return false;
    }
  
    if (diagLoc.isInvalid())
      return true;
  
    assert(kind.hasValue() && "multiple entry points without attributes");
  
    // %select indices for UI/NSApplication-related diagnostics.
    enum : unsigned {
      UIApplicationMainClass = 0,
      NSApplicationMainClass = 1,
    } mainClassDiagKind;
  
    switch (kind.getValue()) {
    case ArtificialMainKind::UIApplicationMain:
      mainClassDiagKind = UIApplicationMainClass;
      break;
    case ArtificialMainKind::NSApplicationMain:
      mainClassDiagKind = NSApplicationMainClass;
      break;
    }
  
    FileUnit *existingFile = EntryPointInfo.getEntryPointFile();
    const ClassDecl *existingClass = existingFile->getMainClass();
    SourceLoc existingDiagLoc;
  
    if (auto *sourceFile = dyn_cast<SourceFile>(existingFile)) {
      if (existingClass) {
        existingDiagLoc = sourceFile->getMainClassDiagLoc();
      } else {
        if (auto bufID = sourceFile->getBufferID())
          existingDiagLoc = getASTContext().SourceMgr.getLocForBufferStart(*bufID);
      }
    }
  
    if (existingClass) {
      if (EntryPointInfo.markDiagnosedMultipleMainClasses()) {
        // If we already have a main class, and we haven't diagnosed it,
        // do so now.
        if (existingDiagLoc.isValid()) {
          getASTContext().Diags.diagnose(existingDiagLoc, diag::attr_ApplicationMain_multiple,
                             mainClassDiagKind);
        } else {
          getASTContext().Diags.diagnose(existingClass, diag::attr_ApplicationMain_multiple,
                             mainClassDiagKind);
        }
      }
  
      // Always diagnose the new class.
      getASTContext().Diags.diagnose(diagLoc, diag::attr_ApplicationMain_multiple,
                         mainClassDiagKind);
  
    } else {
      // We don't have an existing class, but we /do/ have a file in script mode.
      // Diagnose that.
      if (EntryPointInfo.markDiagnosedMainClassWithScript()) {
        getASTContext().Diags.diagnose(diagLoc, diag::attr_ApplicationMain_with_script,
                           mainClassDiagKind);
  
        if (existingDiagLoc.isValid()) {
          getASTContext().Diags.diagnose(existingDiagLoc,
                             diag::attr_ApplicationMain_script_here);
        }
      }
    }
  
    return true;
  }
  
  bool Module::isSystemModule() const {
    if (isStdlibModule())
      return true;
    for (auto F : getFiles()) {
      if (auto LF = dyn_cast<LoadedFile>(F))
        return LF->isSystemModule();
    }
    return false;
  }
  
  template<bool respectVisibility, typename Callback>
  static bool forAllImportedModules(Module *topLevel,
                                    Module::AccessPathTy thisPath,
                                    bool includePrivateTopLevelImports,
                                    const Callback &fn) {
    using ImportedModule = Module::ImportedModule;
    using AccessPathTy = Module::AccessPathTy;
    
    llvm::SmallSet<ImportedModule, 32, Module::OrderImportedModules> visited;
    SmallVector<ImportedModule, 32> stack;
  
    // Even if we're processing the top-level module like any other, we may
    // still want to include non-exported modules.
    Module::ImportFilter filter = respectVisibility ? Module::ImportFilter::Public
                                                    : Module::ImportFilter::All;
    Module::ImportFilter topLevelFilter =
      includePrivateTopLevelImports ? Module::ImportFilter::All : filter;
    topLevel->getImportedModules(stack, topLevelFilter);
  
    // Make sure the top-level module is first; we want pre-order-ish traversal.
    AccessPathTy overridingPath;
    if (respectVisibility)
      overridingPath = thisPath;
    stack.push_back(ImportedModule(overridingPath, topLevel));
  
    while (!stack.empty()) {
      auto next = stack.pop_back_val();
  
      // Filter any whole-module imports, and skip specific-decl imports if the
      // import path doesn't match exactly.
      if (next.first.empty() || !respectVisibility)
        next.first = overridingPath;
      else if (!overridingPath.empty() &&
               !Module::isSameAccessPath(next.first, overridingPath)) {
        // If we ever allow importing non-top-level decls, it's possible the rule
        // above isn't what we want.
        assert(next.first.size() == 1 && "import of non-top-level decl");
        continue;
      }
  
      if (!visited.insert(next).second)
        continue;
  
      if (!fn(next))
        return false;
  
      if (respectVisibility)
        next.second->getImportedModulesForLookup(stack);
      else
        next.second->getImportedModules(stack, filter);
    }
  
    return true;
  }
  
  bool Module::forAllVisibleModules(AccessPathTy thisPath,
                                    bool includePrivateTopLevelImports,
                                    llvm::function_ref<bool(ImportedModule)> fn) {
    return forAllImportedModules<true>(this, thisPath,
                                       includePrivateTopLevelImports, fn);
  }
  
  bool FileUnit::forAllVisibleModules(
      llvm::function_ref<bool(Module::ImportedModule)> fn) {
    if (!getParentModule()->forAllVisibleModules(Module::AccessPathTy(), fn))
      return false;
  
    if (auto SF = dyn_cast<SourceFile>(this)) {
      // Handle privately visible modules as well.
      // FIXME: Should this apply to all FileUnits?
      SmallVector<Module::ImportedModule, 4> imports;
      SF->getImportedModules(imports, Module::ImportFilter::Private);
      for (auto importPair : imports)
        if (!importPair.second->forAllVisibleModules(importPair.first, fn))
          return false;
    }
  
    return true;
  }
  
  void Module::collectLinkLibraries(LinkLibraryCallback callback) {
    // FIXME: The proper way to do this depends on the decls used.
    FORWARD(collectLinkLibraries, (callback));
  }
  
  void
  SourceFile::collectLinkLibraries(Module::LinkLibraryCallback callback) const {
    for (auto importPair : Imports)
      importPair.first.second->collectLinkLibraries(callback);
  }
  
  bool Module::walk(ASTWalker &Walker) {
    llvm::SaveAndRestore<ASTWalker::ParentTy> SAR(Walker.Parent, this);
    for (auto SF : getFiles())
      if (SF->walk(Walker))
        return true;
    return false;
  }
  
  const clang::Module *Module::findUnderlyingClangModule() {
    for (auto *FU : getFiles()) {
      if (auto *Mod = FU->getUnderlyingClangModule())
        return Mod;
    }
    return nullptr;
  }
  
  //===----------------------------------------------------------------------===//
  // SourceFile Implementation
  //===----------------------------------------------------------------------===//
  
  void SourceFile::print(raw_ostream &OS, const PrintOptions &PO) {
    StreamPrinter Printer(OS);
    print(Printer, PO);
  }
  
  void SourceFile::print(ASTPrinter &Printer, const PrintOptions &PO) {
    std::set<DeclKind> MajorDeclKinds = {DeclKind::Class, DeclKind::Enum,
      DeclKind::Extension, DeclKind::Protocol, DeclKind::Struct};
    for (auto decl : Decls) {
      if (!decl->shouldPrintInContext(PO))
        continue;
      // For a major decl, we print an empty line before it.
      if (MajorDeclKinds.find(decl->getKind()) != MajorDeclKinds.end())
        Printer << "\n";
      if(decl->print(Printer, PO))
        Printer << "\n";
    }
  }
  
  void SourceFile::addImports(
      ArrayRef<std::pair<Module::ImportedModule, ImportOptions>> IM) {
    using ImportPair = std::pair<Module::ImportedModule, ImportOptions>;
    if (IM.empty())
      return;
    ASTContext &ctx = getASTContext();
    auto newBuf =
       ctx.AllocateUninitialized<ImportPair>(Imports.size() + IM.size());
  
    auto iter = newBuf.begin();
    iter = std::uninitialized_copy(Imports.begin(), Imports.end(), iter);
    iter = std::uninitialized_copy(IM.begin(), IM.end(), iter);
    assert(iter == newBuf.end());
  
    Imports = newBuf;
  }
  
  bool SourceFile::hasTestableImport(const swift::Module *module) const {
    using ImportPair = std::pair<Module::ImportedModule, ImportOptions>;
    return std::any_of(Imports.begin(), Imports.end(),
                       [module](ImportPair importPair) -> bool {
      return importPair.first.second == module &&
          importPair.second.contains(ImportFlags::Testable);
    });
  }
  
  void SourceFile::clearLookupCache() {
    if (!Cache)
      return;
  
    // Abandon any current cache. We'll rebuild it on demand.
    Cache->invalidate();
    Cache.reset();
  }
  
  void
  SourceFile::cacheVisibleDecls(SmallVectorImpl<ValueDecl*> &&globals) const {
    SmallVectorImpl<ValueDecl*> &cached = getCache().AllVisibleValues;
    cached = std::move(globals);
  }
  
  const SmallVectorImpl<ValueDecl *> &
  SourceFile::getCachedVisibleDecls() const {
    return getCache().AllVisibleValues;
  }
  
  static void performAutoImport(SourceFile &SF,
                                SourceFile::ImplicitModuleImportKind modImpKind) {
    if (SF.Kind == SourceFileKind::SIL)
      assert(modImpKind == SourceFile::ImplicitModuleImportKind::None);
  
    ASTContext &Ctx = SF.getASTContext();
    Module *M = nullptr;
  
    switch (modImpKind) {
    case SourceFile::ImplicitModuleImportKind::None:
      return;
    case SourceFile::ImplicitModuleImportKind::Builtin:
      M = Ctx.TheBuiltinModule;
      break;
    case SourceFile::ImplicitModuleImportKind::Stdlib:
      M = Ctx.getStdlibModule(true);
      break;
    }
  
    assert(M && "unable to auto-import module");
  
    // FIXME: These will be the same for most source files, but we copy them
    // over and over again.
    auto Imports =
      std::make_pair(Module::ImportedModule({}, M), SourceFile::ImportOptions());
    SF.addImports(Imports);
  }
  
  SourceFile::SourceFile(Module &M, SourceFileKind K,
                         Optional<unsigned> bufferID,
                         ImplicitModuleImportKind ModImpKind)
    : FileUnit(FileUnitKind::Source, M),
      BufferID(bufferID ? *bufferID : -1), Kind(K) {
    M.getASTContext().addDestructorCleanup(*this);
    performAutoImport(*this, ModImpKind);
  
    if (isScriptMode()) {
      bool problem = M.registerEntryPointFile(this, SourceLoc(), None);
      assert(!problem && "multiple main files?");
      (void)problem;
    }
  }
  
  SourceFile::~SourceFile() {}
  
  bool FileUnit::walk(ASTWalker &walker) {
    SmallVector<Decl *, 64> Decls;
    getTopLevelDecls(Decls);
    llvm::SaveAndRestore<ASTWalker::ParentTy> SAR(walker.Parent,
                                                  getParentModule());
    for (Decl *D : Decls) {
  #ifndef NDEBUG
      PrettyStackTraceDecl debugStack("walking into decl", D);
  #endif
      
      if (D->walk(walker))
        return true;
    }
    return false;
  }
  
  bool SourceFile::walk(ASTWalker &walker) {
    llvm::SaveAndRestore<ASTWalker::ParentTy> SAR(walker.Parent,
                                                  getParentModule());
    for (Decl *D : Decls) {
  #ifndef NDEBUG
      PrettyStackTraceDecl debugStack("walking into decl", D);
  #endif
  
      if (D->walk(walker))
        return true;
    }
    return false;
  }
  
  StringRef SourceFile::getFilename() const {
    if (BufferID == -1)
      return "";
    SourceManager &SM = getASTContext().SourceMgr;
    return SM.getIdentifierForBuffer(BufferID);
  }
  
  Identifier
  SourceFile::getDiscriminatorForPrivateValue(const ValueDecl *D) const {
    assert(D->getDeclContext()->getModuleScopeContext() == this);
  
    if (!PrivateDiscriminator.empty())
      return PrivateDiscriminator;
  
    StringRef name = getFilename();
    if (name.empty()) {
      assert(1 == std::count_if(getParentModule()->getFiles().begin(),
                                getParentModule()->getFiles().end(),
                                [](const FileUnit *FU) -> bool {
        return isa<SourceFile>(FU) && cast<SourceFile>(FU)->getFilename().empty();
      }) && "can't promise uniqueness if multiple source files are nameless");
  
      // We still need a discriminator, so keep going.
    }
  
    // Use a hash of the basename of the source file as our discriminator.
    // This keeps us from leaking information about the original filename
    // while still providing uniqueness. Using the basename makes the
    // discriminator invariant across source checkout locations.
    // FIXME: Use a faster hash here? We don't need security, just uniqueness.
    llvm::MD5 hash;
    hash.update(getParentModule()->getName().str());
    hash.update(llvm::sys::path::filename(name));
    llvm::MD5::MD5Result result;
    hash.final(result);
  
    // Make sure the whole thing is a valid identifier.
    SmallString<33> buffer{"_"};
  
    // Write the hash as a hex string.
    // FIXME: This should go into llvm/ADT/StringExtras.h.
    // FIXME: And there are more compact ways to encode a 16-byte value.
    buffer.reserve(buffer.size() + 2*llvm::array_lengthof(result));
    for (uint8_t byte : result) {
      buffer.push_back(llvm::hexdigit(byte >> 4, /*lowercase=*/false));
      buffer.push_back(llvm::hexdigit(byte & 0xF, /*lowercase=*/false));
    }
  
    PrivateDiscriminator = getASTContext().getIdentifier(buffer);
    return PrivateDiscriminator;
  }
  
  TypeRefinementContext *SourceFile::getTypeRefinementContext() {
    return TRC;
  }
  
  void SourceFile::setTypeRefinementContext(TypeRefinementContext *Root) {
    TRC = Root;
  }
  
  //===----------------------------------------------------------------------===//
  // Miscellaneous
  //===----------------------------------------------------------------------===//
  
  void FileUnit::anchor() {}
  void *FileUnit::operator new(size_t Bytes, ASTContext &C, unsigned Alignment) {
    return C.Allocate(Bytes, Alignment);
  }
  
  StringRef LoadedFile::getFilename() const {
    return "";
  }
  
  static const clang::Module *
  getClangModule(llvm::PointerUnion<const Module *, const void *> Union) {
    return static_cast<const clang::Module *>(Union.get<const void *>());
  }
  
  StringRef ModuleEntity::getName() const {
    assert(!Mod.isNull());
    if (auto SwiftMod = Mod.dyn_cast<const Module*>())
      return SwiftMod->getName().str();
    return getClangModule(Mod)->Name;
  }
  
  std::string ModuleEntity::getFullName() const {
    assert(!Mod.isNull());
    if (auto SwiftMod = Mod.dyn_cast<const Module*>())
      return SwiftMod->getName().str();
    return getClangModule(Mod)->getFullModuleName();
  }
  
  bool ModuleEntity::isSystemModule() const {
    assert(!Mod.isNull());
    if (auto SwiftMod = Mod.dyn_cast<const Module*>())
      return SwiftMod->isSystemModule();
    return getClangModule(Mod)->IsSystem;
  }
  
  bool ModuleEntity::isBuiltinModule() const {
    assert(!Mod.isNull());
    if (auto SwiftMod = Mod.dyn_cast<const Module*>())
      return SwiftMod->isBuiltinModule();
    return false;
  }
  