swift-mirror/lib/ClangImporter/ClangLookup.cpp

//===--- ClangLookup.cpp - Lookup in entities imported from Clang ---------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file contains facilities for name lookup in entites imported from Clang
//
//===----------------------------------------------------------------------===//

#include "ImporterImpl.h"
#include "SwiftDeclSynthesizer.h"
#include "SwiftLookupTable.h"
#include "swift/AST/ASTContext.h"
#include "swift/AST/Builtins.h"
#include "swift/AST/ClangModuleLoader.h"
#include "swift/AST/ConcreteDeclRef.h"
#include "swift/AST/Decl.h"
#include "swift/AST/DiagnosticEngine.h"
#include "swift/AST/Evaluator.h"
#include "swift/AST/ImportCache.h"
#include "swift/AST/Module.h"
#include "swift/AST/ModuleNameLookup.h"
#include "swift/AST/NameLookup.h"
#include "swift/AST/NameLookupRequests.h"
#include "swift/AST/PrettyStackTrace.h"
#include "swift/AST/SourceFile.h"
#include "swift/AST/Type.h"
#include "swift/AST/TypeCheckRequests.h"
#include "swift/AST/Types.h"
#include "swift/Basic/LLVM.h"
#include "swift/ClangImporter/ClangImporter.h"
#include "swift/ClangImporter/ClangImporterRequests.h"
#include "swift/ClangImporter/ClangModule.h"
#include "swift/Subsystems.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/CXXInheritance.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/DeclarationName.h"
#include "clang/AST/Mangle.h"
#include "clang/AST/Type.h"
#include "clang/Basic/Specifiers.h"
#include "clang/Index/IndexingAction.h"
#include "clang/Sema/Lookup.h"
#include "clang/Sema/Sema.h"
#include "clang/Serialization/ASTReader.h"
#include "clang/Serialization/ASTWriter.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include <utility>

using namespace swift;

namespace {
/// Collects name lookup results into the given tiny vector, for use in the
/// various ClangImporter lookup routines.
///
/// Validates that the name we looked up matches the resulting imported name.
class CollectLookupResults {
  /// Match by base name, since that is what MemberLookupTable is keyed on for
  /// laziness (i.e., see type of MemberLookupTable::isLazilyComplete).
  DeclBaseName name;
  TinyPtrVector<ValueDecl *> &result;
  ClangImporter::Implementation &impl;

public:
  CollectLookupResults(DeclBaseName name, TinyPtrVector<ValueDecl *> &result,
                       ClangImporter::Implementation &impl)
      : name(name), result(result), impl(impl) {}

  void add(ValueDecl *imported) {
    if (imported->getBaseName() == name)
      result.push_back(imported);

    // A Clang declaration can be imported under more than one name; the
    // '__<name>Unsafe' migration stub of an unsafe C++ method is one such
    // alternate, and only the alternate carries the name being looked up here.
    //
    // Only consider alternates declared alongside 'imported'. Other kinds of
    // alternate are re-parented elsewhere -- an anonymous enum constant, for
    // instance, is imported both at module scope and as a member of the
    // enclosing struct.
    for (auto *alternate : impl.getAlternateDecls(imported)) {
      if (alternate->getBaseName() == name &&
          alternate->getDeclContext() == imported->getDeclContext())
        result.push_back(alternate);
    }

    // Expand any macros introduced by the Clang importer.
    imported->visitAuxiliaryDecls([&](Decl *decl) {
      auto valueDecl = dyn_cast<ValueDecl>(decl);
      if (!valueDecl)
        return;

      // Bail out if the auxiliary decl was not produced by a macro.
      auto module = decl->getDeclContext()->getParentModule();
      auto *sf = module->getSourceFileContainingLocation(decl->getLoc());
      if (!sf || sf->Kind != SourceFileKind::MacroExpansion)
        return;

      // Only produce results that match the requested name.
      if (valueDecl->getBaseName() != name)
        return;

      result.push_back(valueDecl);
    });
  }
};
} // anonymous namespace

static SmallVector<const clang::NamedDecl *, 4>
directRecordMemberLookup(ClangImporter &Importer,
                         const clang::RecordDecl *whereDecl, DeclName name) {
  SmallVector<const clang::NamedDecl *, 4> result;

  // Class template instances aren't in the lookup table.
  // Import all member names to figure out which one(s) we're looking for.
  if (isa<clang::ClassTemplateSpecializationDecl>(whereDecl)) {
    // TODO: we could make this faster if we can cache class templates in the
    //       lookup table as well.

    for (auto *member : whereDecl->decls()) {
      auto *namedDecl = dyn_cast<clang::NamedDecl>(member);
      if (!namedDecl)
        continue;

      auto memberName = Importer.importName(namedDecl);
      if (!memberName)
        continue;

      // Use the base names here because *sometimes* our input name won't have
      // any arguments.
      if (name.getBaseName() == memberName.getBaseName())
        result.push_back(namedDecl);
    }

    return result;
  }

  auto *clangModule =
      importer::getClangOwningModule(whereDecl, whereDecl->getASTContext());

  auto *lookupTable = Importer.findLookupTable(clangModule);

  auto foundDecls = lookupTable->lookup(SerializedSwiftName(name.getBaseName()),
                                        EffectiveClangContext());

  // lookup() just gives us all decls in the module of the given name.
  // Make sure that `whereDecl` is the parent of all the members we found.
  auto *whereCanonical = whereDecl->getCanonicalDecl();

  // The same Clang decl can appear under multiple contexts, so dedup.
  llvm::SmallPtrSet<const clang::NamedDecl *, 4> seen;
  for (auto entry : foundDecls) {
    auto *found = entry.dyn_cast<clang::NamedDecl *>();
    if (!found)
      continue; // What we found wasn't a NamedDecl
    if (!seen.insert(found).second)
      continue; // Already saw this Clang decl via a different context entry

    auto *foundCtx = found->getNonTransparentDeclContext();
    if (auto *foundCtxDecl = dyn_cast<clang::RecordDecl>(foundCtx)) {
      // Context of found decl is also a decl; compare canonical decl of each
      if (foundCtxDecl->getCanonicalDecl() == whereCanonical)
        result.push_back(found);
    }
  }

  return result;
}

TinyPtrVector<ValueDecl *> CXXNamespaceMemberLookup::evaluate(
    Evaluator &evaluator, CXXNamespaceMemberLookupDescriptor desc) const {
  DeclName name = desc.name;
  auto &ctx = desc.namespaceDecl->getASTContext();

  auto *theNamespace =
      cast<clang::NamespaceDecl>(desc.namespaceDecl->getClangDecl())
          ->getCanonicalDecl();

  TinyPtrVector<ValueDecl *> result;

  auto &Importer = *static_cast<ClangImporter *>(ctx.getClangModuleLoader());
  auto *lookupTable = Importer.findLookupTable(nullptr);
  auto foundDecls = lookupTable->lookup(SerializedSwiftName(name.getBaseName()),
                                        EffectiveClangContext());

  CollectLookupResults collector(name.getBaseName(), result, Importer.Impl);
  llvm::SmallPtrSet<clang::NamedDecl *, 8> seenDecls;
  for (SwiftLookupTable::SingleEntry foundEntry : foundDecls) {
    auto *foundDecl = foundEntry.dyn_cast<clang::NamedDecl *>();
    if (!foundDecl)
      continue; // What we found wasn't a NamedDecl

    auto *foundCtx = foundDecl->getNonTransparentDeclContext();

    bool wasFound = false;
    while (auto *foundNamespace = dyn_cast<clang::NamespaceDecl>(foundCtx)) {
      // Compare theNamespace with the namespace enclosing the found decl,
      // as well as any outer namespaces if it is inline.
      if (foundNamespace->getCanonicalDecl() == theNamespace) {
        wasFound = true;
        break;
      }

      if (!foundNamespace->isInline())
        break;

      foundCtx = foundNamespace->getParent();
    }

    if (!wasFound)
      continue;

    if (!seenDecls.insert(foundDecl).second)
      continue; // We've already seen this; a re-declaration?
    if (auto *importedDecl =
            ctx.getClangModuleLoader()->importDeclDirectly(foundDecl))
      collector.add(cast<ValueDecl>(importedDecl));
  }
  return result;
}

void importer::forEachCXXNamespaceMember(
    EnumDecl *namespaceEnum, llvm::function_ref<void(ValueDecl *)> emit,
    bool includeSpecializations, bool includeOtherModules) {
  auto *namespaceDecl =
      cast<clang::NamespaceDecl>(namespaceEnum->getClangDecl());
  auto &ctx = namespaceEnum->getASTContext();
  auto *clangModuleLoader = ctx.getClangModuleLoader();

  // Keep track of which names we've seen and which decls we've imported.
  // When we lookup a member by name, we import all of them at once.
  llvm::SmallDenseSet<DeclName, 16> seenNames;
  llvm::SmallPtrSet<Decl *, 16> seenImports;

  auto importMember = [&](const clang::NamedDecl *nd) {
    DeclName importedName = clangModuleLoader->importName(nd);
    if (!importedName || !seenNames.insert(importedName).second)
      return;

    auto importedMembers = evaluateOrDefault(
        ctx.evaluator,
        CXXNamespaceMemberLookup({namespaceEnum, importedName}),
        {});

    for (auto *imported : importedMembers) {
      if (seenImports.insert(imported).second)
        emit(imported);
    }
  };

  // If this is non-null, we will only import members from that module
  const clang::Module *owningModule = nullptr;
  if (!includeOtherModules && namespaceDecl->getOwningModule())
    owningModule = namespaceDecl->getOwningModule()->getTopLevelModule();

  auto importSpecializations = [&](const clang::ClassTemplateDecl *tmpl) {
    if (!includeSpecializations)
      return;

    // Add all specializations to a worklist so we don't accidentally mutate
    // the list of decls we're iterating over.
    llvm::SmallPtrSet<const clang::ClassTemplateSpecializationDecl *, 16>
        specWorklist;
    specWorklist.insert_range(tmpl->specializations());

    for (auto *spec : specWorklist) {
      auto *imported = clangModuleLoader->importDeclDirectly(spec);
      if (imported && seenImports.insert(imported).second)
        emit(cast<ValueDecl>(imported));
    }
  };

  auto Redecls =
      llvm::SmallVector<clang::NamespaceDecl *, 32>(namespaceDecl->redecls());
  llvm::stable_sort(Redecls, [&](auto *LHS, auto *RHS) {
    // Sort according to module name, if any (a namespace redeclaration will not
    // have an owning Clang module if it is declared in a bridging header).
    if (!LHS->getOwningModule() || !RHS->getOwningModule())
      return (bool)LHS->getOwningModule() < (bool)RHS->getOwningModule();
    return LHS->getOwningModule()->Name < RHS->getOwningModule()->Name;
  });

  for (auto *redecl : Redecls) {
    // Skip namespace declarations that come from other top-level modules
    // if there's such a requirement (i.e., if owningModule is non-null)
    if (owningModule && redecl->getOwningModule() &&
        owningModule != redecl->getOwningModule()->getTopLevelModule())
      continue;

    for (auto *member : redecl->decls()) {
      if (auto *classTemplate = dyn_cast<clang::ClassTemplateDecl>(member)) {
        importSpecializations(classTemplate);
      }

      if (auto *nd = dyn_cast<clang::NamedDecl>(member)) {
        importMember(nd);
      }

      // Unscoped enums have their enumerators present in the parent namespace.
      if (auto *ed = dyn_cast<clang::EnumDecl>(member); ed && !ed->isScoped()) {
        for (const auto *ecd : ed->enumerators())
          importMember(ecd);
      }
    }
  }
}

TinyPtrVector<ValueDecl *> ClangRecordMemberLookup::evaluate(
    Evaluator &evaluator, ClangRecordMemberLookupDescriptor desc) const {
  NominalTypeDecl *recordDecl = desc.recordDecl;
  NominalTypeDecl *inheritingDecl = desc.inheritingDecl;
  DeclName name = desc.name;
  ClangInheritanceInfo inheritance = desc.inheritance;

  auto &ctx = recordDecl->getASTContext();
  auto &Importer = *static_cast<ClangImporter *>(ctx.getClangModuleLoader());
  auto *clangRecordDecl = cast<clang::RecordDecl>(recordDecl->getClangDecl());

  // Whether to skip non-public members. Feature::ImportNonPublicCxxMembers says
  // to import all non-public members by default; if that is disabled, we only
  // import non-public members annotated with SWIFT_PRIVATE_FILEID (since those
  // are the only classes that need non-public members.)
  auto *cxxRecordDecl =
      dyn_cast<clang::CXXRecordDecl>(inheritingDecl->getClangDecl());
  auto skipIfNonPublic =
      !ctx.LangOpts.hasFeature(Feature::ImportNonPublicCxxMembers) &&
      cxxRecordDecl && importer::getPrivateFileIDAttrs(cxxRecordDecl).empty();

  auto directResults =
      directRecordMemberLookup(Importer, clangRecordDecl, name);

  // It's possible that there are entries in the lookup table that end up
  // getting mangled as unsafe, but were not added to the look up table as
  // such. This can happen when, e.g., their unsafety depends on the
  // definition of a template class that was not yet instantiated when the
  // lookup table was being populated, but will get instantiated when that
  // decl is imported.
  //
  // If we are looking up "__{{name}}Unsafe", also look up "{{name}}" in
  // case we find members like this.
  if (cxxRecordDecl && !name.isSpecial()) {
    auto id = name.getBaseIdentifier().str();
    if (id.starts_with("__") && id.ends_with("Unsafe") && id != "__Unsafe") {
      auto unUnsafeId = id.drop_front(2).drop_back(6);
      DeclName unUnsafeName(ctx.getIdentifier(unUnsafeId));
      auto moreResults =
          directRecordMemberLookup(Importer, clangRecordDecl, unUnsafeName);
      directResults.append(moreResults.begin(), moreResults.end());
    }
  }

  // The set of declarations we found.
  TinyPtrVector<ValueDecl *> result;
  CollectLookupResults collector(name.getBaseName(), result, Importer.Impl);

  // Find the results that are actually a member of "recordDecl".
  ClangModuleLoader *clangModuleLoader = ctx.getClangModuleLoader();
  for (const clang::NamedDecl *found : directResults) {
    // We should not import 'found' if the following are all true:
    //
    // -  Feature::ImportNonPublicCxxMembers is not enabled
    // -  'found' is not a member of a SWIFT_PRIVATE_FILEID-annotated class
    // -  'found' is a non-public member.
    // -  'found' is not a non-inherited FieldDecl; we must import private
    //    fields because they may affect implicit conformances that iterate
    //    through all of a struct's fields, e.g., Sendable (#76892).
    //
    // Note that we can skip inherited FieldDecls because implicit conformances
    // handle those separately.
    //
    // The first two conditions are captured by skipIfNonPublic. The next two
    // are conveyed by the following:
    auto nonPublic = found->getAccess() == clang::AS_private ||
                     found->getAccess() == clang::AS_protected;
    auto noninheritedField = !inheritance && isa<clang::FieldDecl>(found);
    if (skipIfNonPublic && nonPublic && !noninheritedField)
      continue;

    // Don't import constructors on foreign reference types.
    if (isa<clang::CXXConstructorDecl>(found) && isa<ClassDecl>(recordDecl))
      continue;

    auto *imported =
        cast_or_null<ValueDecl>(clangModuleLoader->importDeclDirectly(found));
    if (!imported)
      continue;

    // If this member is found due to inheritance, clone it from the base class
    // by synthesizing getters and setters.
    if (inheritance) {
      // Alternate declarations are recorded against the base class's
      // declaration, so they have to be cloned separately.
      for (auto *alternate : Importer.Impl.getAlternateDecls(imported)) {
        if (alternate->getBaseName() != name.getBaseName() ||
            alternate->getDeclContext() != imported->getDeclContext())
          continue;
        if (auto *clonedAlternate = clangModuleLoader->importBaseMemberDecl(
                alternate, inheritingDecl, inheritance))
          result.push_back(clonedAlternate);
      }

      imported = clangModuleLoader->importBaseMemberDecl(
          imported, inheritingDecl, inheritance);
      if (!imported)
        continue;
    }

    collector.add(imported);
  }

  if (inheritance) {
    // For inherited members, add members that are synthesized eagerly, such as
    // operators. This is not necessary for non-inherited members because those
    // should already be in the lookup table.

    // If the derived class already has its own directly-synthesized
    // property with the looked-up name, don't clone a same-named
    // synthesized property from the base on top of it. This is the case
    // e.g. when SWIFT_REFCOUNTED_PTR is applied to both a base and a
    // derived smart pointer: each gets its own `asReference` and
    // surfacing the base's clone too would leave the derived with two
    // copies.
    bool derivedHasOwnSynthesizedVar = false;
    for (auto m : inheritingDecl->getCurrentMembersWithoutLoading()) {
      auto ownVD = dyn_cast<VarDecl>(m);
      if (ownVD && ownVD->hasName() && ownVD->getBaseName() == name &&
          !ownVD->hasClangNode() &&
          !clangModuleLoader->getOriginalForClonedMember(ownVD)) {
        derivedHasOwnSynthesizedVar = true;
        break;
      }
    }

    for (auto member :
         cast<NominalTypeDecl>(recordDecl)->getCurrentMembersWithoutLoading()) {
      auto namedMember = dyn_cast<ValueDecl>(member);
      if (!namedMember || !namedMember->hasName() ||
          namedMember->getBaseName() != name ||
          clangModuleLoader->isMemberSynthesizedPerType(namedMember) ||
          clangModuleLoader->getOriginalForClonedMember(namedMember))
        continue;

      if (derivedHasOwnSynthesizedVar && isa<VarDecl>(namedMember))
        continue;

      auto *imported = clangModuleLoader->importBaseMemberDecl(
          namedMember, inheritingDecl, inheritance);
      if (!imported)
        continue;

      collector.add(imported);
    }
  }

  // If this is a C++ record, look through any base classes.
  const clang::CXXRecordDecl *cxxRecord;
  if ((cxxRecord =
           dyn_cast<clang::CXXRecordDecl>(recordDecl->getClangDecl())) &&
      cxxRecord->isCompleteDefinition()) {
    // Capture the arity of already found members in the
    // current record, to avoid adding ambiguous members
    // from base classes.
    llvm::SmallSet<DeclName, 4> foundMethodNames;
    for (const auto *valueDecl : result)
      foundMethodNames.insert(valueDecl->getName());

    // If this FRT class has a single FRT superclass, skip looking up members
    // from that base: they are reachable via the Swift superclass chain
    // instead.
    const clang::RecordDecl *superclassClangDecl = nullptr;
    if (!inheritance) {
      auto derivedInfo = evaluateOrDefault(
          ctx.evaluator, ForeignReferenceTypeInfoRequest({cxxRecord}), {});
      if (auto primaryBase = derivedInfo.getPrimarySuperclass())
        superclassClangDecl = primaryBase;
    }

    for (auto base : cxxRecord->bases()) {
      if (skipIfNonPublic && base.getAccessSpecifier() != clang::AS_public)
        continue;

      clang::QualType baseType = base.getType();
      if (auto spectType =
              dyn_cast<clang::TemplateSpecializationType>(baseType))
        baseType = spectType->desugar();
      if (!isa<clang::RecordType>(baseType.getCanonicalType()))
        continue;

      auto *baseRecord = baseType->getAs<clang::RecordType>()->getDecl();

      if (superclassClangDecl && baseRecord->getCanonicalDecl() ==
                                     superclassClangDecl->getCanonicalDecl())
        continue;

      if (importer::isSymbolicCircularBase(cxxRecord, baseRecord))
        // Skip circular bases to avoid unbounded recursion
        continue;

      if (auto import = clangModuleLoader->importDeclDirectly(baseRecord)) {
        // If we are looking up the base class, go no further. We will have
        // already found it during the other lookup.
        if (cast<ValueDecl>(import)->getName() == name)
          continue;

        auto baseInheritance = ClangInheritanceInfo(inheritance, base);

        // Add Clang members that are imported lazily.
        auto baseResults = evaluateOrDefault(
            ctx.evaluator,
            ClangRecordMemberLookup({cast<NominalTypeDecl>(import), name,
                                     inheritingDecl, baseInheritance}),
            {});

        for (auto foundInBase : baseResults) {
          // Do not add duplicate entry with the same DeclName,
          // as that would cause an ambiguous lookup.
          if (foundMethodNames.count(foundInBase->getName()))
            continue;

          collector.add(foundInBase);
        }
      }
    }
  }

  if (result.empty() && !inheritance) {
    if (name.isSimpleName("pointee")) {
      if (auto *pointee = Importer.Impl.lookupAndImportPointee(inheritingDecl))
        result.push_back(pointee);
    } else if (name.getBaseName() == "successor" &&
               name.getArgumentNames().empty()) {
      if (auto *succ = Importer.Impl.lookupAndImportSuccessor(inheritingDecl))
        result.push_back(succ);
    } else if (name.getBaseName() == "__convertToBool" &&
               name.getArgumentNames().empty()) {
      if (auto *opBool =
              Importer.Impl.lookupAndImportOperatorBool(inheritingDecl))
        result.push_back(opBool);
    } else if (name.getBaseName().isSubscript()) {
      for (auto *sub : Importer.Impl.lookupAndImportSubscripts(inheritingDecl))
        result.push_back(sub);
    }
  }

  return result;
}

namespace {
/// Essentially a pair<CXXMethodDecl *, AccessSpecifier>, from qualified lookup.
///
/// The method is the result of the qualified lookup. The access is AS_none if
/// the method is not inherited, otherwise it denotes the effective access of
/// the method from the derived class where the qualified lookup originated.
struct CXXOverload {
  const clang::CXXMethodDecl *method = nullptr;
  clang::AccessSpecifier access = clang::AS_none;

  CXXOverload() = default;
  CXXOverload(const clang::CXXMethodDecl *m, clang::AccessSpecifier a)
      : method{m}, access{a} {}

  friend bool operator==(const CXXOverload &LHS, const CXXOverload &RHS) {
    return LHS.method == RHS.method && LHS.access == RHS.access;
  }

  operator bool() const { return static_cast<bool>(method); }

  /// If no overload has been picked yet, or candidate is const and the current
  /// pick isn't, take the candidate.
  void pickPreferringConst(CXXOverload candidate) {
    if (!candidate)
      return;
    if (!*this || (!this->method->isConst() && candidate.method->isConst()))
      *this = candidate;
  }
};

/// The argument types of a C++ method overload.
///
/// Note that this does not constitute the full signature of a C++ overload:
/// overloads with the same argument types but different constness (of 'this')
/// are still considered distinct overloads.
///
/// When looking up and importing certain members like operator[] -> subscript
/// or operator() -> callAsFunction that can have multiple overloads in Swift,
/// it is helpful to group overloads of the same argument types, so that if
/// there are both const and non-const overloads, we can decide which to use as
/// the getter and which to use as the setter (which is not decided by the
/// constnes of 'this', but by the constness of the return type). We define
/// CXXOverloadArgTypes to the key of a map, so that given a bunch of overloads,
/// we can sort them into these groups of the same argument types.
struct CXXOverloadArgTypes : llvm::SmallVector<clang::QualType, 4> {
  using ::CXXOverloadArgTypes::SmallVector::SmallVector;
  CXXOverloadArgTypes(CXXOverload overload) : SmallVector{} {
    for (auto p : overload.method->parameters())
      push_back(p->getType().getCanonicalType());
  }
};
} // namespace

template <>
struct llvm::DenseMapInfo<CXXOverloadArgTypes> {
  using Sig = CXXOverloadArgTypes;
  static inline Sig getEmptyKey() { return {{}}; }
  static inline Sig getTombstoneKey() { return {{}, {}}; }
  static unsigned getHashValue(const Sig &Val) {
    return static_cast<size_t>(llvm::hash_combine_range(llvm::map_range(
        Val, [](clang::QualType ty) { return ty.getAsOpaquePtr(); })));
  }
  static bool isEqual(const Sig &LHS, const Sig &RHS) { return LHS == RHS; }
};

namespace {
/// Perform a qualified lookup for \a name in \a Record, suppressing diagnostics
/// and returning std::nullopt if the lookup was unsuccessful.
static std::optional<clang::LookupResult>
lookupCXXMember(clang::Sema &Sema, clang::DeclarationName name,
                const clang::CXXRecordDecl *Record) {
  auto R = clang::LookupResult(Sema, name, clang::SourceLocation(),
                               clang::Sema::LookupMemberName);
  R.suppressDiagnostics();
  // NOTE: this will not find free-standing operator decl, i.e. not a member
  Sema.LookupQualifiedName(R, const_cast<clang::CXXRecordDecl *>(Record));

  switch (R.getResultKind()) {
  case clang::LookupResultKind::Found:
  case clang::LookupResultKind::FoundOverloaded:
    return R;
  default:
    return std::nullopt; // Lookup didn't yield any results
  }
}

/// Convenience wrapper around clang::LookupResult::iterator that yields
/// std::pair<NamedDecl *, AccessSpecifier> rather than just NamedDecl *.
struct ResultIterator
    : llvm::iterator_adaptor_base<
          ResultIterator, clang::LookupResult::iterator,
          clang::LookupResult::iterator::iterator_category,
          std::pair<const clang::NamedDecl *, clang::AccessSpecifier>> {
  explicit ResultIterator(const clang::LookupResult::iterator &it) { I = it; }
  value_type operator*() const {
    return std::make_pair(I.getDecl(), I.getAccess());
  }
};

/// Creates an iterable range of MethodOverloads for the results found
/// in \a R, originating from a qualified lookup in \a Origin.
///
/// This helper for the lookupAndImport* functions encapsulates downcasting the
/// decls to clang::CXXMethodDecl *s and "looking through" using decls. It also
/// ensures the access is set to clang::AS_none if the method is not inherited.
static auto filterMethodOverloads(clang::LookupResult &R,
                                  const clang::CXXRecordDecl *Origin,
                                  bool withTemplates) {
  return llvm::make_filter_range(
      llvm::map_range(
          llvm::make_range(ResultIterator{R.begin()}, ResultIterator{R.end()}),
          [=](std::pair<const clang::NamedDecl *, clang::AccessSpecifier> da) {
            auto [nd, access] = da;

            if (auto *usd = dyn_cast<clang::UsingShadowDecl>(nd))
              nd = usd->getTargetDecl();

            if (auto *ftd = dyn_cast<clang::FunctionTemplateDecl>(nd);
                ftd && withTemplates)
              nd = ftd->getTemplatedDecl();

            if (nd->getDeclContext() == Origin)
              access = clang::AS_none; // not inherited

            auto *md = dyn_cast<clang::CXXMethodDecl>(nd);
            return CXXOverload{md, access};
          }),
      [](CXXOverload o) { return o.method != nullptr; });
}

} // namespace

/// Imports a C++ \a method to a Swift \a struct as a non-inherited member when
/// \a access is AS_none, or an inherited member with effective \a access
/// otherwise.
///
/// Helper for the lookupAndImport* functions.
static FuncDecl *importUnderlyingFunction(ClangImporter::Implementation &Impl,
                                          CXXOverload overload,
                                          NominalTypeDecl *Struct) {
  Decl *imported;
  if (auto *ftd = overload.method->getDescribedFunctionTemplate())
    imported = Impl.importDecl(ftd, Impl.CurrentVersion);
  else
    imported = Impl.importDecl(overload.method, Impl.CurrentVersion);
  auto *func = dyn_cast_or_null<FuncDecl>(imported);
  if (!func)
    return nullptr;
  if (auto inheritance = ClangInheritanceInfo(overload.access))
    func = dyn_cast_or_null<FuncDecl>(
        Impl.importBaseMemberDecl(func, Struct, inheritance));
  if (!func)
    return nullptr;
  return func;
}

std::tuple<VarDecl *, FuncDecl *, FuncDecl *>
ClangImporter::Implementation::lookupAndImportPointeeAndOperatorStar(
    NominalTypeDecl *Struct) {
  const auto *CXXRecord =
      dyn_cast<clang::CXXRecordDecl>(Struct->getClangDecl());

  if (!CXXRecord)
    return {};

  if (auto [it, inserted] = importedPointeeCache.try_emplace(
          Struct, std::make_tuple(nullptr, nullptr, nullptr));
      !inserted)
    return it->second;

  // From this point onward, if we encounter some error and return, future calls
  // to this function will pick up the nullptr we cached using try_emplace. Note
  // that this may silently suppress unintentional cycles.

  auto &Ctx = getClangASTContext();
  auto &Sema = getClangSema();

  auto name = Ctx.DeclarationNames.getCXXOperatorName(
      clang::OverloadedOperatorKind::OO_Star);
  auto R = lookupCXXMember(Sema, name, CXXRecord);
  if (!R.has_value())
    return {};

  CXXOverload CXXGetter, CXXSetter;

  auto overloads =
      filterMethodOverloads(R.value(), CXXRecord, /*withTemplates=*/false);

  for (const auto &overload : overloads) {
    if (overload.method->isStatic() || overload.method->isVolatile() ||
        overload.method->getMinRequiredArguments() != 0 ||
        overload.method->getRefQualifier() == clang::RQ_RValue)
      continue;

    // A setter is anything that returns a mutable reference; anything else is
    // a getter.
    auto retTy = overload.method->getReturnType();
    bool isSetter =
        retTy->isReferenceType() && !retTy->getPointeeType().isConstQualified();

    if (isSetter)
      CXXSetter.pickPreferringConst(overload);

    // NOTE: a setter can also be used as a getter, so we don't check !isSetter
    CXXGetter.pickPreferringConst(overload);
  }

  if (!CXXGetter && !CXXSetter)
    return {};

  FuncDecl *getter = nullptr, *setter = nullptr;

  if (CXXSetter) {
    setter = importUnderlyingFunction(*this, CXXSetter, Struct);
    if (!setter)
      return {};
    markUnavailable(setter, "use .pointee property");
  }

  if (CXXGetter == CXXSetter) {
    getter = setter;
  } else if (CXXGetter) {
    getter = importUnderlyingFunction(*this, CXXGetter, Struct);
    if (!getter)
      return {};
    markUnavailable(getter, "use .pointee property");
  }

  SwiftDeclSynthesizer synth{*this};
  auto *pointee = synth.makeDereferencedPointeeProperty(getter, setter);
  if (!pointee)
    return {};

  importAttributes(CXXGetter ? CXXGetter.method : CXXSetter.method, pointee);

  Struct->addMember(pointee);
  auto pointeeAndOpStar =
      std::make_tuple(pointee, getter ? getter : setter, setter);
  importedPointeeCache[Struct] = pointeeAndOpStar;
  return pointeeAndOpStar;
}

VarDecl *
ClangImporter::Implementation::lookupAndImportPointee(NominalTypeDecl *Struct) {
  return std::get<0>(lookupAndImportPointeeAndOperatorStar(Struct));
}

FuncDecl *ClangImporter::Implementation::lookupAndImportSuccessor(
    NominalTypeDecl *Struct) {
  const auto *CXXRecord =
      dyn_cast<clang::CXXRecordDecl>(Struct->getClangDecl());

  if (!CXXRecord || !isa<StructDecl>(Struct))
    // Do not synthesize successor() if this is not a C++ record, or if it is
    // a foreign reference type (successor() needs to copy values of this type),
    // which would be a ClassDecl rather than a StructDecl.
    return nullptr;

  if (auto [it, inserted] = importedSuccessorCache.try_emplace(Struct, nullptr);
      !inserted)
    return it->second;

  // From this point onward, if we encounter some error and return, future calls
  // to this function will pick up the nullptr we cached using try_emplace. Note
  // that this may silently suppress unintentional cycles.

  auto &Ctx = getClangASTContext();
  auto &Sema = getClangSema();

  auto name = Ctx.DeclarationNames.getCXXOperatorName(
      clang::OverloadedOperatorKind::OO_PlusPlus);
  auto R = lookupCXXMember(Sema, name, CXXRecord);
  if (!R.has_value())
    return nullptr;

  auto overloads =
      filterMethodOverloads(R.value(), CXXRecord, /*withTemplates=*/false);

  CXXOverload CXXMethod;

  for (const auto &overload : overloads) {
    if (overload.method->isStatic() || overload.method->isVolatile() ||
        overload.method->getRefQualifier() == clang::RQ_RValue ||
        overload.method->getMinRequiredArguments() != 0)
      continue;

    // FIXME: we currently only support non-const overloads of operator++,
    // so skip const overloads for now. Synthesizing a nonmutating .successor()
    // from a const overload should be possible but currently causes a crash.

    if (overload.method->isConst())
      continue;

    CXXMethod = overload;
  }

  if (!CXXMethod)
    return nullptr;

  auto *incr = importUnderlyingFunction(*this, CXXMethod, Struct);
  if (!incr)
    return nullptr;
  markUnavailable(incr, "use .successor()");

  SwiftDeclSynthesizer synth{*this};
  auto *succ = synth.makeSuccessorFunc(incr);
  if (!succ)
    return nullptr;

  importAttributes(CXXMethod.method, succ);

  Struct->addMember(succ);
  importedSuccessorCache[Struct] = succ;
  return succ;
}

llvm::ArrayRef<SubscriptDecl *>
ClangImporter::Implementation::lookupAndImportSubscripts(
    NominalTypeDecl *Struct, bool noSynthesize) {
  const auto *CXXRecord =
      dyn_cast<clang::CXXRecordDecl>(Struct->getClangDecl());

  if (!CXXRecord)
    return {};

  auto [it, inserted] = importedSubscriptsCache.try_emplace(
      Struct, llvm::SmallVector<SubscriptDecl *, 1>{});
  auto &result = it->second;

  if (noSynthesize) {
    ASSERT(result.empty() && "should not have cached synthesized subscripts");
    return result;
  }

  if (!inserted)
    return result;

  // From this point onward, if we encounter some error and return, future calls
  // to this function will return (a reference to) the empty vector we cached.
  // Note that this may silently suppress unintentional cycles.

  auto &Ctx = getClangASTContext();
  auto &Sema = getClangSema();

  auto name = Ctx.DeclarationNames.getCXXOperatorName(
      clang::OverloadedOperatorKind::OO_Subscript);
  auto R = lookupCXXMember(Sema, name, CXXRecord);
  if (!R.has_value())
    return {};

  // If this FRT class has a single FRT superclass, inherited overloads whose
  // declaring class is that superclass (or a Clang base of it) are reachable
  // via the Swift superclass chain and should not be synthesized here again.
  const clang::CXXRecordDecl *superclassClangDecl = nullptr;
  auto frtInfo = evaluateOrDefault(
      SwiftContext.evaluator, ForeignReferenceTypeInfoRequest({CXXRecord}), {});
  superclassClangDecl = frtInfo.getPrimarySuperclass();

  llvm::SmallMapVector<CXXOverloadArgTypes,
                       std::pair<CXXOverload, CXXOverload>, 1>
      CXXSubscripts;

  auto overloads =
      filterMethodOverloads(R.value(), CXXRecord, /*withTemplates=*/true);
  for (const auto &overload : overloads) {
    if (overload.method->isVolatile() ||
        overload.method->getRefQualifier() == clang::RQ_RValue)
      continue;

    if (superclassClangDecl) {
      auto methodParent = overload.method->getParent();
      if (methodParent != CXXRecord &&
          (methodParent == superclassClangDecl ||
           superclassClangDecl->isDerivedFrom(methodParent)))
        continue;
    }

    auto retTy = overload.method->getReturnType();
    auto isSetter = (retTy->isAnyPointerType() || retTy->isReferenceType()) &&
                    !retTy->getPointeeType().isConstQualified();
    auto &[CXXGetter, CXXSetter] = CXXSubscripts[{overload}];
    if (isSetter)
      CXXSetter.pickPreferringConst(overload);
    else
      CXXGetter.pickPreferringConst(overload);
  }

  llvm::SmallVector<SubscriptDecl *, 1> subscripts;
  for (auto &[_, pair] : CXXSubscripts) {
    auto [CXXGetter, CXXSetter] = pair;
    ASSERT((CXXGetter || CXXSetter) &&
           "subscript should have at least getter or setter");

    if (CXXGetter && CXXSetter) {
      // The getter and setter have the same argument types, and neither of them
      // are volatile or r-value ref qualified (since we skip those overloads),
      // so they must differ by their const-ness (either const + non-const, or
      // const l-value ref + non-const l-value ref).
      //
      // If this subtle invariant is somehow broken, just skip importing this
      // getter/setter pair (asserting this invariant risks making ClangImporter
      // more fragile than necessary).
      if (!(CXXGetter.method->isConst() ^ CXXSetter.method->isConst()))
        continue;

      auto stripToUnderlying = [](clang::QualType ty) {
        if (ty->isPointerType())
          return ty->getPointeeType().getUnqualifiedType().getCanonicalType();
        else
          return ty.getNonReferenceType().getUnqualifiedType().getCanonicalType();
      };
      auto getRetTy = stripToUnderlying(CXXGetter.method->getReturnType()),
           setRetTy = stripToUnderlying(CXXSetter.method->getReturnType());
      if (getRetTy != setRetTy) {
        // Getter and setter return types differ; pick the const-overloaded one
        if (!CXXGetter.method->isConst())
          CXXGetter = {};
        if (!CXXSetter.method->isConst())
          CXXSetter = {};
      }
    }

    auto importSubscriptOverload = [&](CXXOverload overload) -> FuncDecl * {
      if (!overload)
        return nullptr;

      auto *swiftFunc = importUnderlyingFunction(*this, overload, Struct);
      if (!swiftFunc)
        return nullptr;
      markUnavailable(swiftFunc, "use subscript");

      auto name = swiftFunc->getBaseName();
      ASSERT(!name.isSpecial() &&
             "operator[] should not be imported with special name");
      ASSERT(name.getIdentifier().str().starts_with("__operatorSubscript") &&
             "operator[] should be imported as __operatorSubscript");

      for (auto *parameter : *(swiftFunc->getParameters())) {
        if (parameter->isInOut() || !parameter->getTypeInContext())
          // Subscripts with inout parameters are not allowed in Swift.
          return nullptr;
      }

      return swiftFunc;
    };

    FuncDecl *getter = importSubscriptOverload(CXXGetter),
             *setter = importSubscriptOverload(CXXSetter);

    // Mark subscript setter as mutating in Swift even if C++ operator is const.
    if (setter && !setter->getDeclContext()->isModuleScopeContext() &&
        !Struct->getDeclaredType()->isForeignReferenceType())
      setter->setSelfAccessKind(SelfAccessKind::Mutating);

    if (!getter && !setter)
      // Didn't end up with a usable getter or setter, so nothing to synthesize
      continue;

    SwiftDeclSynthesizer synth{*this};
    auto *subscript = synth.makeSubscript(getter, setter);
    if (!subscript)
      continue;

    // Import attributes from the Clang operator[] decl(s) onto the synthesized
    // accessor thunks (importAttributes is a no-op on SubscriptDecl itself).
    if (auto *getterAccessor = subscript->getAccessor(AccessorKind::Get);
        getterAccessor && CXXGetter)
      importAttributes(CXXGetter.method, getterAccessor);
    if (auto *setterAccessor = subscript->getAccessor(AccessorKind::Set);
        setterAccessor && CXXSetter)
      importAttributes(CXXSetter.method, setterAccessor);

    Struct->addMember(subscript);
    result.push_back(subscript);
  }

  return result;
}

FuncDecl *ClangImporter::Implementation::lookupAndImportOperatorBool(
    NominalTypeDecl *Struct) {
  auto *CXXRecord = const_cast<clang::CXXRecordDecl *>(
      dyn_cast<clang::CXXRecordDecl>(Struct->getClangDecl()));

  if (!CXXRecord)
    return nullptr;

  if (auto [it, inserted] =
          importedOperatorBoolCache.try_emplace(Struct, nullptr);
      !inserted)
    return it->second;

  // From this point onward, if we encounter some error and return, future calls
  // to this function will pick up the nullptr we cached using try_emplace. Note
  // that this may silently suppress unintentional cycles.

  auto &Ctx = getClangASTContext();
  auto &Sema = getClangSema();

  if (!Sema.hasReachableDefinition(CXXRecord))
    // Importing this operator requires reachable receiver object class
    return nullptr;

  // Look for operator bool() const
  clang::CXXConversionDecl *OpBool = nullptr;

  auto Conversions = CXXRecord->getVisibleConversionFunctions();
  for (auto it = Conversions.begin(); it != Conversions.end(); ++it) {
    auto *CD =
        dyn_cast<clang::CXXConversionDecl>(it.getDecl()->getUnderlyingDecl());
    if (!CD || CD->isDeleted() || it.getAccess() != clang::AS_public)
      // N.B. we need to check it.getAccess() and not CD->getAccess() because
      // the former gives the effective access via the derived class CXXRecord,
      // while the latter only gives the access of the decl as it is declared in
      // the base class.
      continue;

    if (CD->getConversionType()->isBooleanType() && CD->isConst() &&
        !CD->isVolatile() && CD->getRefQualifier() != clang::RQ_RValue &&
        Sema.isReachable(CD)) {
      if (OpBool && OpBool->getCanonicalDecl() != CD->getCanonicalDecl())
        return nullptr; // Ambiguous: multiple distinct operator bool() const
      OpBool = CD;
    }
  }

  if (!OpBool)
    return nullptr; // Did not find suitable operator bool() const

  // N.B. At this point it is still possible to have an ambiguous OpBool due to
  // non-virtual diamond inheritance. That scenario will be handled by Clang,
  // when we attempt to construct an ambiguous call with BuildCXXNamedCast(),
  // producing an invalid expr and causing us to bail out of this function.

  auto Loc = CXXRecord->getLocation();

  // Synthesize method:
  //
  //   bool __convertToBool() const { return static_cast<bool>(*this); }
  //

  clang::QualType MethodTy = OpBool->getType();
  clang::DeclarationName Name = &Ctx.Idents.get("__convertToBool");
  clang::DeclarationNameInfo NameInfo(Name, Loc);

  clang::CXXMethodDecl *Method = clang::CXXMethodDecl::Create(
      Ctx, CXXRecord, Loc, NameInfo, MethodTy,
      Ctx.getTrivialTypeSourceInfo(MethodTy, Loc),
      /*StorageClass=*/clang::SC_None,
      /*UsesFPIntrin=*/false,
      /*isInline=*/true, clang::ConstexprSpecKind::Unspecified,
      clang::SourceLocation());
  Method->setAccess(clang::AS_public);
  Method->setImplicit();

  {
    clang::Sema::SFINAETrap trap(Sema);
    clang::Sema::SynthesizedFunctionScope Scope(Sema, Method);

    auto This = Sema.ActOnCXXThis(Loc);
    if (This.isInvalid()) {
      Method->setInvalidDecl();
      return nullptr;
    }
    auto DerefThis =
        Sema.CreateBuiltinUnaryOp(Loc, clang::UO_Deref, This.get());
    if (DerefThis.isInvalid()) {
      Method->setInvalidDecl();
      return nullptr;
    }

    auto Cast = Sema.BuildCXXNamedCast(
        Loc, clang::tok::kw_static_cast,
        Ctx.getTrivialTypeSourceInfo(Ctx.BoolTy, Loc), DerefThis.get(),
        clang::SourceRange(Loc, Loc), clang::SourceRange(Loc, Loc));
    if (Cast.isInvalid()) {
      Method->setInvalidDecl();
      return nullptr;
    }

    auto Return = Sema.BuildReturnStmt(Loc, Cast.get());
    if (Return.isInvalid()) {
      Method->setInvalidDecl();
      return nullptr;
    }

    Method->setBody(clang::CompoundStmt::Create(
        Ctx, Return.get(), clang::FPOptionsOverride(), Loc, Loc));
    Method->markUsed(Ctx);
  }
  CXXRecord->addDecl(Method);

  auto *func =
      importUnderlyingFunction(*this, {Method, clang::AS_none}, Struct);
  if (!func)
    return nullptr;
  auto *depr = AvailableAttr::createUniversallyDeprecated(SwiftContext,
                                                          "use Bool(fromCxx:)");
  func->addAttribute(depr);
  markMemberSynthesizedPerType(func);
  importAttributes(OpBool, func);

  // The iterator from the try_emplace() at the beginning of this function may
  // have been invalidated during importUnavailableMethod(), so we must perform
  // the look up again:
  importedOperatorBoolCache[Struct] = func;
  return func;
}