//===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file implements C++ template argument deduction.

//

//===----------------------------------------------------------------------===//

#include "TreeTransform.h"

#include "TypeLocBuilder.h"

#include "clang/AST/ASTContext.h"

#include "clang/AST/ASTLambda.h"

#include "clang/AST/Decl.h"

#include "clang/AST/DeclAccessPair.h"

#include "clang/AST/DeclBase.h"

#include "clang/AST/DeclCXX.h"

#include "clang/AST/DeclTemplate.h"

#include "clang/AST/DeclarationName.h"

#include "clang/AST/Expr.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/NestedNameSpecifier.h"

#include "clang/AST/RecursiveASTVisitor.h"

#include "clang/AST/TemplateBase.h"

#include "clang/AST/TemplateName.h"

#include "clang/AST/Type.h"

#include "clang/AST/TypeLoc.h"

#include "clang/AST/UnresolvedSet.h"

#include "clang/Basic/AddressSpaces.h"

#include "clang/Basic/ExceptionSpecificationType.h"

#include "clang/Basic/LLVM.h"

#include "clang/Basic/LangOptions.h"

#include "clang/Basic/PartialDiagnostic.h"

#include "clang/Basic/SourceLocation.h"

#include "clang/Basic/Specifiers.h"

#include "clang/Sema/EnterExpressionEvaluationContext.h"

#include "clang/Sema/Ownership.h"

#include "clang/Sema/Sema.h"

#include "clang/Sema/Template.h"

#include "clang/Sema/TemplateDeduction.h"

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/APSInt.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/FoldingSet.h"

#include "llvm/ADT/SmallBitVector.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/ErrorHandling.h"

#include <algorithm>

#include <cassert>

#include <optional>

#include <tuple>

#include <type_traits>

#include <utility>

namespace clang {

  /// Various flags that control template argument deduction.

  ///

  /// These flags can be bitwise-OR'd together.

  enum TemplateDeductionFlags {

    /// No template argument deduction flags, which indicates the

    /// strictest results for template argument deduction (as used for, e.g.,

    /// matching class template partial specializations).

    TDF_None = 0,

    /// Within template argument deduction from a function call, we are

    /// matching with a parameter type for which the original parameter was

    /// a reference.

    TDF_ParamWithReferenceType = 0x1,

    /// Within template argument deduction from a function call, we

    /// are matching in a case where we ignore cv-qualifiers.

    TDF_IgnoreQualifiers = 0x02,

    /// Within template argument deduction from a function call,

    /// we are matching in a case where we can perform template argument

    /// deduction from a template-id of a derived class of the argument type.

    TDF_DerivedClass = 0x04,

    /// Allow non-dependent types to differ, e.g., when performing

    /// template argument deduction from a function call where conversions

    /// may apply.

    TDF_SkipNonDependent = 0x08,

    /// Whether we are performing template argument deduction for

    /// parameters and arguments in a top-level template argument

    TDF_TopLevelParameterTypeList = 0x10,

    /// Within template argument deduction from overload resolution per

    /// C++ [over.over] allow matching function types that are compatible in

    /// terms of noreturn and default calling convention adjustments, or

    /// similarly matching a declared template specialization against a

    /// possible template, per C++ [temp.deduct.decl]. In either case, permit

    /// deduction where the parameter is a function type that can be converted

    /// to the argument type.

    TDF_AllowCompatibleFunctionType = 0x20,

    /// Within template argument deduction for a conversion function, we are

    /// matching with an argument type for which the original argument was

    /// a reference.

    TDF_ArgWithReferenceType = 0x40,

  };

}

using namespace clang;

using namespace sema;

/// Compare two APSInts, extending and switching the sign as

/// necessary to compare their values regardless of underlying type.

static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {

  if (Y.getBitWidth() > X.getBitWidth())

    X = X.extend(Y.getBitWidth());

  else if (Y.getBitWidth() < X.getBitWidth())

    Y = Y.extend(X.getBitWidth());

  // If there is a signedness mismatch, correct it.

  if (X.isSigned() != Y.isSigned()) {

    // If the signed value is negative, then the values cannot be the same.

    if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))

      return false;

    Y.setIsSigned(true);

    X.setIsSigned(true);

  }

  return X == Y;

}

static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch(

    Sema &S, TemplateParameterList *TemplateParams, QualType Param,

    QualType Arg, TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,

    bool PartialOrdering = false, bool DeducedFromArrayBound = false);

static Sema::TemplateDeductionResult

DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,

                        ArrayRef<TemplateArgument> Ps,

                        ArrayRef<TemplateArgument> As,

                        TemplateDeductionInfo &Info,

                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,

                        bool NumberOfArgumentsMustMatch);

static void MarkUsedTemplateParameters(ASTContext &Ctx,

                                       const TemplateArgument &TemplateArg,

                                       bool OnlyDeduced, unsigned Depth,

                                       llvm::SmallBitVector &Used);

static void MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,

                                       bool OnlyDeduced, unsigned Level,

                                       llvm::SmallBitVector &Deduced);

/// If the given expression is of a form that permits the deduction

/// of a non-type template parameter, return the declaration of that

/// non-type template parameter.

static const NonTypeTemplateParmDecl *

getDeducedParameterFromExpr(const Expr *E, unsigned Depth) {

  // If we are within an alias template, the expression may have undergone

  // any number of parameter substitutions already.

  while (true) {

    if (const auto *IC = dyn_cast<ImplicitCastExpr>(E))

      E = IC->getSubExpr();

    else if (const auto *CE = dyn_cast<ConstantExpr>(E))

      E = CE->getSubExpr();

    else if (const auto *Subst = dyn_cast<SubstNonTypeTemplateParmExpr>(E))

      E = Subst->getReplacement();

    else if (const auto *CCE = dyn_cast<CXXConstructExpr>(E)) {

      // Look through implicit copy construction from an lvalue of the same type.

      if (CCE->getParenOrBraceRange().isValid())

        break;

      // Note, there could be default arguments.

      assert(CCE->getNumArgs() >= 1 && "implicit construct expr should have 1 arg");

      E = CCE->getArg(0);

    } else

      break;

  }

  if (const auto *DRE = dyn_cast<DeclRefExpr>(E))

    if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))

      if (NTTP->getDepth() == Depth)

        return NTTP;

  return nullptr;

}

static const NonTypeTemplateParmDecl *

getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) {

  return getDeducedParameterFromExpr(E, Info.getDeducedDepth());

}

/// Determine whether two declaration pointers refer to the same

/// declaration.

static bool isSameDeclaration(Decl *X, Decl *Y) {

  if (NamedDecl *NX = dyn_cast<NamedDecl>(X))

    X = NX->getUnderlyingDecl();

  if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))

    Y = NY->getUnderlyingDecl();

  return X->getCanonicalDecl() == Y->getCanonicalDecl();

}

/// Verify that the given, deduced template arguments are compatible.

///

/// \returns The deduced template argument, or a NULL template argument if

/// the deduced template arguments were incompatible.

static DeducedTemplateArgument

checkDeducedTemplateArguments(ASTContext &Context,

                              const DeducedTemplateArgument &X,

                              const DeducedTemplateArgument &Y,

                              bool AggregateCandidateDeduction = false) {

  // We have no deduction for one or both of the arguments; they're compatible.

  if (X.isNull())

    return Y;

  if (Y.isNull())

    return X;

  // If we have two non-type template argument values deduced for the same

  // parameter, they must both match the type of the parameter, and thus must

  // match each other's type. As we're only keeping one of them, we must check

  // for that now. The exception is that if either was deduced from an array

  // bound, the type is permitted to differ.

  if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) {

    QualType XType = X.getNonTypeTemplateArgumentType();

    if (!XType.isNull()) {

      QualType YType = Y.getNonTypeTemplateArgumentType();

      if (YType.isNull() || !Context.hasSameType(XType, YType))

        return DeducedTemplateArgument();

    }

  }

  switch (X.getKind()) {

  case TemplateArgument::Null:

    llvm_unreachable("Non-deduced template arguments handled above");

  case TemplateArgument::Type: {

    // If two template type arguments have the same type, they're compatible.

    QualType TX = X.getAsType(), TY = Y.getAsType();

    if (Y.getKind() == TemplateArgument::Type && Context.hasSameType(TX, TY))

      return DeducedTemplateArgument(Context.getCommonSugaredType(TX, TY),

                                     X.wasDeducedFromArrayBound() ||

                                         Y.wasDeducedFromArrayBound());

    // If one of the two arguments was deduced from an array bound, the other

    // supersedes it.

    if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())

      return X.wasDeducedFromArrayBound() ? Y : X;

    // The arguments are not compatible.

    return DeducedTemplateArgument();

  }

  case TemplateArgument::Integral:

    // If we deduced a constant in one case and either a dependent expression or

    // declaration in another case, keep the integral constant.

    // If both are integral constants with the same value, keep that value.

    if (Y.getKind() == TemplateArgument::Expression ||

        Y.getKind() == TemplateArgument::Declaration ||

        (Y.getKind() == TemplateArgument::Integral &&

         hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))

      return X.wasDeducedFromArrayBound() ? Y : X;

    // All other combinations are incompatible.

    return DeducedTemplateArgument();

  case TemplateArgument::Template:

    if (Y.getKind() == TemplateArgument::Template &&

        Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))

      return X;

    // All other combinations are incompatible.

    return DeducedTemplateArgument();

  case TemplateArgument::TemplateExpansion:

    if (Y.getKind() == TemplateArgument::TemplateExpansion &&

        Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),

                                    Y.getAsTemplateOrTemplatePattern()))

      return X;

    // All other combinations are incompatible.

    return DeducedTemplateArgument();

  case TemplateArgument::Expression: {

    if (Y.getKind() != TemplateArgument::Expression)

      return checkDeducedTemplateArguments(Context, Y, X);

    // Compare the expressions for equality

    llvm::FoldingSetNodeID ID1, ID2;

    X.getAsExpr()->Profile(ID1, Context, true);

    Y.getAsExpr()->Profile(ID2, Context, true);

    if (ID1 == ID2)

      return X.wasDeducedFromArrayBound() ? Y : X;

    // Differing dependent expressions are incompatible.

    return DeducedTemplateArgument();

  }

  case TemplateArgument::Declaration:

    assert(!X.wasDeducedFromArrayBound());

    // If we deduced a declaration and a dependent expression, keep the

    // declaration.

    if (Y.getKind() == TemplateArgument::Expression)

      return X;

    // If we deduced a declaration and an integral constant, keep the

    // integral constant and whichever type did not come from an array

    // bound.

    if (Y.getKind() == TemplateArgument::Integral) {

      if (Y.wasDeducedFromArrayBound())

        return TemplateArgument(Context, Y.getAsIntegral(),

                                X.getParamTypeForDecl());

      return Y;

    }

    // If we deduced two declarations, make sure that they refer to the

    // same declaration.

    if (Y.getKind() == TemplateArgument::Declaration &&

        isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))

      return X;

    // All other combinations are incompatible.

    return DeducedTemplateArgument();

  case TemplateArgument::NullPtr:

    // If we deduced a null pointer and a dependent expression, keep the

    // null pointer.

    if (Y.getKind() == TemplateArgument::Expression)

      return TemplateArgument(Context.getCommonSugaredType(

                                  X.getNullPtrType(), Y.getAsExpr()->getType()),

                              true);

    // If we deduced a null pointer and an integral constant, keep the

    // integral constant.

    if (Y.getKind() == TemplateArgument::Integral)

      return Y;

    // If we deduced two null pointers, they are the same.

    if (Y.getKind() == TemplateArgument::NullPtr)

      return TemplateArgument(

          Context.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()),

          true);

    // All other combinations are incompatible.

    return DeducedTemplateArgument();

  case TemplateArgument::Pack: {

    if (Y.getKind() != TemplateArgument::Pack ||

        (!AggregateCandidateDeduction && X.pack_size() != Y.pack_size()))

      return DeducedTemplateArgument();

    llvm::SmallVector<TemplateArgument, 8> NewPack;

    for (TemplateArgument::pack_iterator

             XA = X.pack_begin(),

             XAEnd = X.pack_end(), YA = Y.pack_begin(), YAEnd = Y.pack_end();

         XA != XAEnd; ++XA, ++YA) {

      if (YA != YAEnd) {

        TemplateArgument Merged = checkDeducedTemplateArguments(

            Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),

            DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()));

        if (Merged.isNull() && !(XA->isNull() && YA->isNull()))

          return DeducedTemplateArgument();

        NewPack.push_back(Merged);

      } else {

        NewPack.push_back(*XA);

      }

    }

    return DeducedTemplateArgument(

        TemplateArgument::CreatePackCopy(Context, NewPack),

        X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());

  }

  }

  llvm_unreachable("Invalid TemplateArgument Kind!");

}

/// Deduce the value of the given non-type template parameter

/// as the given deduced template argument. All non-type template parameter

/// deduction is funneled through here.

static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(

    Sema &S, TemplateParameterList *TemplateParams,

    const NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,

    QualType ValueType, TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  assert(NTTP->getDepth() == Info.getDeducedDepth() &&

         "deducing non-type template argument with wrong depth");

  DeducedTemplateArgument Result = checkDeducedTemplateArguments(

      S.Context, Deduced[NTTP->getIndex()], NewDeduced);

  if (Result.isNull()) {

    Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP);

    Info.FirstArg = Deduced[NTTP->getIndex()];

    Info.SecondArg = NewDeduced;

    return Sema::TDK_Inconsistent;

  }

  Deduced[NTTP->getIndex()] = Result;

  if (!S.getLangOpts().CPlusPlus17)

    return Sema::TDK_Success;

  if (NTTP->isExpandedParameterPack())

    // FIXME: We may still need to deduce parts of the type here! But we

    // don't have any way to find which slice of the type to use, and the

    // type stored on the NTTP itself is nonsense. Perhaps the type of an

    // expanded NTTP should be a pack expansion type?

    return Sema::TDK_Success;

  // Get the type of the parameter for deduction. If it's a (dependent) array

  // or function type, we will not have decayed it yet, so do that now.

  QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());

  if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))

    ParamType = Expansion->getPattern();

  // FIXME: It's not clear how deduction of a parameter of reference

  // type from an argument (of non-reference type) should be performed.

  // For now, we just remove reference types from both sides and let

  // the final check for matching types sort out the mess.

  ValueType = ValueType.getNonReferenceType();

  if (ParamType->isReferenceType())

    ParamType = ParamType.getNonReferenceType();

  else

    // Top-level cv-qualifiers are irrelevant for a non-reference type.

    ValueType = ValueType.getUnqualifiedType();

  return DeduceTemplateArgumentsByTypeMatch(

      S, TemplateParams, ParamType, ValueType, Info, Deduced,

      TDF_SkipNonDependent, /*PartialOrdering=*/false,

      /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());

}

/// Deduce the value of the given non-type template parameter

/// from the given integral constant.

static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(

    Sema &S, TemplateParameterList *TemplateParams,

    const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,

    QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  return DeduceNonTypeTemplateArgument(

      S, TemplateParams, NTTP,

      DeducedTemplateArgument(S.Context, Value, ValueType,

                              DeducedFromArrayBound),

      ValueType, Info, Deduced);

}

/// Deduce the value of the given non-type template parameter

/// from the given null pointer template argument type.

static Sema::TemplateDeductionResult DeduceNullPtrTemplateArgument(

    Sema &S, TemplateParameterList *TemplateParams,

    const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,

    TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  Expr *Value = S.ImpCastExprToType(

                     new (S.Context) CXXNullPtrLiteralExpr(S.Context.NullPtrTy,

                                                           NTTP->getLocation()),

                     NullPtrType,

                     NullPtrType->isMemberPointerType() ? CK_NullToMemberPointer

                                                        : CK_NullToPointer)

                    .get();

  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,

                                       DeducedTemplateArgument(Value),

                                       Value->getType(), Info, Deduced);

}

/// Deduce the value of the given non-type template parameter

/// from the given type- or value-dependent expression.

///

/// \returns true if deduction succeeded, false otherwise.

static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(

    Sema &S, TemplateParameterList *TemplateParams,

    const NonTypeTemplateParmDecl *NTTP, Expr *Value, TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,

                                       DeducedTemplateArgument(Value),

                                       Value->getType(), Info, Deduced);

}

/// Deduce the value of the given non-type template parameter

/// from the given declaration.

///

/// \returns true if deduction succeeded, false otherwise.

static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(

    Sema &S, TemplateParameterList *TemplateParams,

    const NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T,

    TemplateDeductionInfo &Info,

    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;

  TemplateArgument New(D, T);

  return DeduceNonTypeTemplateArgument(

      S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);

}

static Sema::TemplateDeductionResult

DeduceTemplateArguments(Sema &S,

                        TemplateParameterList *TemplateParams,

                        TemplateName Param,

                        TemplateName Arg,

                        TemplateDeductionInfo &Info,

                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  TemplateDecl *ParamDecl = Param.getAsTemplateDecl();

  if (!ParamDecl) {

    // The parameter type is dependent and is not a template template parameter,

    // so there is nothing that we can deduce.

    return Sema::TDK_Success;

  }

  if (TemplateTemplateParmDecl *TempParam

        = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {

    // If we're not deducing at this depth, there's nothing to deduce.

    if (TempParam->getDepth() != Info.getDeducedDepth())

      return Sema::TDK_Success;

    DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));

    DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,

                                                 Deduced[TempParam->getIndex()],

                                                                   NewDeduced);

    if (Result.isNull()) {

      Info.Param = TempParam;

      Info.FirstArg = Deduced[TempParam->getIndex()];

      Info.SecondArg = NewDeduced;

      return Sema::TDK_Inconsistent;

    }

    Deduced[TempParam->getIndex()] = Result;

    return Sema::TDK_Success;

  }

  // Verify that the two template names are equivalent.

  if (S.Context.hasSameTemplateName(Param, Arg))

    return Sema::TDK_Success;

  // Mismatch of non-dependent template parameter to argument.

  Info.FirstArg = TemplateArgument(Param);

  Info.SecondArg = TemplateArgument(Arg);

  return Sema::TDK_NonDeducedMismatch;

}

/// Deduce the template arguments by comparing the template parameter

/// type (which is a template-id) with the template argument type.

///

/// \param S the Sema

///

/// \param TemplateParams the template parameters that we are deducing

///

/// \param P the parameter type

///

/// \param A the argument type

///

/// \param Info information about the template argument deduction itself

///

/// \param Deduced the deduced template arguments

///

/// \returns the result of template argument deduction so far. Note that a

/// "success" result means that template argument deduction has not yet failed,

/// but it may still fail, later, for other reasons.

static Sema::TemplateDeductionResult

DeduceTemplateSpecArguments(Sema &S, TemplateParameterList *TemplateParams,

                            const QualType P, QualType A,

                            TemplateDeductionInfo &Info,

                            SmallVectorImpl<DeducedTemplateArgument> &Deduced) {

  QualType UP = P;

  if (const auto *IP = P->getAs<InjectedClassNameType>())

    UP = IP->getInjectedSpecializationType();

  // FIXME: Try to preserve type sugar here, which is hard

  // because of the unresolved template arguments.

  const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>();

  TemplateName TNP = TP->getTemplateName();

  // If the parameter is an alias template, there is nothing to deduce.

  if (const auto *TD = TNP.getAsTemplateDecl(); TD && TD->isTypeAlias())

    return Sema::TDK_Success;

  ArrayRef<TemplateArgument> PResolved = TP->template_arguments();

  QualType UA = A;

  // Treat an injected-class-name as its underlying template-id.

  if (const auto *Injected = A->getAs<InjectedClassNameType>())

    UA = Injected->getInjectedSpecializationType();

  // Check whether the template argument is a dependent template-id.

  // FIXME: Should not lose sugar here.

  if (const auto *SA =

          dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) {

    TemplateName TNA = SA->getTemplateName();

    // If the argument is an alias template, there is nothing to deduce.

    if (const auto *TD = TNA.getAsTemplateDecl(); TD && TD->isTypeAlias())

      return Sema::TDK_Success;

    // Perform template argument deduction for the template name.

    if (auto Result =

            DeduceTemplateArguments(S, TemplateParams, TNP, TNA, Info, Deduced))

      return Result;

    // Perform template argument deduction on each template

    // argument. Ignore any missing/extra arguments, since they could be

    // filled in by default arguments.

    return DeduceTemplateArguments(S, TemplateParams, PResolved,

                                   SA->template_arguments(), Info, Deduced,

                                   /*NumberOfArgumentsMustMatch=*/false);

  }

  // If the argument type is a class template specialization, we

  // perform template argument deduction using its template

  // arguments.

  const auto *RA = UA->getAs<RecordType>();

  const auto *SA =

      RA ? dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl()) : nullptr;

  if (!SA) {

    Info.FirstArg = TemplateArgument(P);

    Info.SecondArg = TemplateArgument(A);

    return Sema::TDK_NonDeducedMismatch;

  }

  // Perform template argument deduction for the template name.

  if (auto Result = DeduceTemplateArguments(

          S, TemplateParams, TP->getTemplateName(),

          TemplateName(SA->getSpecializedTemplate()), Info, Deduced))

    return Result;

  // Perform template argument deduction for the template arguments.

  return DeduceTemplateArguments(S, TemplateParams, PResolved,

                                 SA->getTemplateArgs().asArray(), Info, Deduced,

                                 /*NumberOfArgumentsMustMatch=*/true);

}

static bool IsPossiblyOpaquelyQualifiedTypeInternal(const Type *T) {

  assert(T->isCanonicalUnqualified());

  switch (T->getTypeClass()) {

  case Type::TypeOfExpr:

  case Type::TypeOf:

  case Type::DependentName:

  case Type::Decltype:

  case Type::UnresolvedUsing:

  case Type::TemplateTypeParm:

    return true;

  case Type::ConstantArray:

  case Type::IncompleteArray:

  case Type::VariableArray:

  case Type::DependentSizedArray:

    return IsPossiblyOpaquelyQualifiedTypeInternal(

        cast<ArrayType>(T)->getElementType().getTypePtr());

  default:

    return false;

  }

}

/// Determines whether the given type is an opaque type that

/// might be more qualified when instantiated.

static bool IsPossiblyOpaquelyQualifiedType(QualType T) {

  return IsPossiblyOpaquelyQualifiedTypeInternal(

      T->getCanonicalTypeInternal().getTypePtr());

}

/// Helper function to build a TemplateParameter when we don't

/// know its type statically.

static TemplateParameter makeTemplateParameter(Decl *D) {

  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))

    return TemplateParameter(TTP);

  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))

    return TemplateParameter(NTTP);

  return TemplateParameter(cast<TemplateTemplateParmDecl>(D));

}

/// A pack that we're currently deducing.

struct clang::DeducedPack {

  // The index of the pack.

  unsigned Index;

  // The old value of the pack before we started deducing it.

  DeducedTemplateArgument Saved;

  // A deferred value of this pack from an inner deduction, that couldn't be

  // deduced because this deduction hadn't happened yet.

  DeducedTemplateArgument DeferredDeduction;

  // The new value of the pack.

  SmallVector<DeducedTemplateArgument, 4> New;

  // The outer deduction for this pack, if any.

  DeducedPack *Outer = nullptr;

  DeducedPack(unsigned Index) : Index(Index) {}

};

namespace {

/// A scope in which we're performing pack deduction.

class PackDeductionScope {

public:

  /// Prepare to deduce the packs named within Pattern.

  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,

                     SmallVectorImpl<DeducedTemplateArgument> &Deduced,

                     TemplateDeductionInfo &Info, TemplateArgument Pattern,

                     bool DeducePackIfNotAlreadyDeduced = false)

      : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info),

        DeducePackIfNotAlreadyDeduced(DeducePackIfNotAlreadyDeduced){

    unsigned NumNamedPacks = addPacks(Pattern);

    finishConstruction(NumNamedPacks);

  }

  /// Prepare to directly deduce arguments of the parameter with index \p Index.

  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,

                     SmallVectorImpl<DeducedTemplateArgument> &Deduced,

                     TemplateDeductionInfo &Info, unsigned Index)

      : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {

    addPack(Index);

    finishConstruction(1);

  }

private:

  void addPack(unsigned Index) {

    // Save the deduced template argument for the parameter pack expanded

    // by this pack expansion, then clear out the deduction.

    DeducedPack Pack(Index);

    Pack.Saved = Deduced[Index];

    Deduced[Index] = TemplateArgument();

    // FIXME: What if we encounter multiple packs with different numbers of

    // pre-expanded expansions? (This should already have been diagnosed

    // during substitution.)

    if (std::optional<unsigned> ExpandedPackExpansions =

            getExpandedPackSize(TemplateParams->getParam(Index)))

      FixedNumExpansions = ExpandedPackExpansions;

    Packs.push_back(Pack);

  }

  unsigned addPacks(TemplateArgument Pattern) {

    // Compute the set of template parameter indices that correspond to

    // parameter packs expanded by the pack expansion.

    llvm::SmallBitVector SawIndices(TemplateParams->size());

    llvm::SmallVector<TemplateArgument, 4> ExtraDeductions;

    auto AddPack = [&](unsigned Index) {

      if (SawIndices[Index])

        return;

      SawIndices[Index] = true;

      addPack(Index);

      // Deducing a parameter pack that is a pack expansion also constrains the

      // packs appearing in that parameter to have the same deduced arity. Also,

      // in C++17 onwards, deducing a non-type template parameter deduces its

      // type, so we need to collect the pending deduced values for those packs.

      if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(

              TemplateParams->getParam(Index))) {

        if (!NTTP->isExpandedParameterPack())

          if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType()))

            ExtraDeductions.push_back(Expansion->getPattern());

      }

      // FIXME: Also collect the unexpanded packs in any type and template

      // parameter packs that are pack expansions.

    };

    auto Collect = [&](TemplateArgument Pattern) {

      SmallVector<UnexpandedParameterPack, 2> Unexpanded;

      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);

      for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {

        unsigned Depth, Index;

        std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);

        if (Depth == Info.getDeducedDepth())

          AddPack(Index);

      }

    };

    // Look for unexpanded packs in the pattern.

    Collect(Pattern);

    assert(!Packs.empty() && "Pack expansion without unexpanded packs?");

    unsigned NumNamedPacks = Packs.size();

    // Also look for unexpanded packs that are indirectly deduced by deducing

    // the sizes of the packs in this pattern.

    while (!ExtraDeductions.empty())

      Collect(ExtraDeductions.pop_back_val());

    return NumNamedPacks;

  }

  void finishConstruction(unsigned NumNamedPacks) {

    // Dig out the partially-substituted pack, if there is one.

    const TemplateArgument *PartialPackArgs = nullptr;

    unsigned NumPartialPackArgs = 0;

    std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);

    if (auto *Scope = S.CurrentInstantiationScope)

      if (auto *Partial = Scope->getPartiallySubstitutedPack(

              &PartialPackArgs, &NumPartialPackArgs))

        PartialPackDepthIndex = getDepthAndIndex(Partial);

    // This pack expansion will have been partially or fully expanded if

    // it only names explicitly-specified parameter packs (including the

    // partially-substituted one, if any).

    bool IsExpanded = true;

    for (unsigned I = 0; I != NumNamedPacks; ++I) {

      if (Packs[I].Index >= Info.getNumExplicitArgs()) {

        IsExpanded = false;

        IsPartiallyExpanded = false;

        break;

      }

      if (PartialPackDepthIndex ==

            std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {

        IsPartiallyExpanded = true;

      }

    }

    // Skip over the pack elements that were expanded into separate arguments.

    // If we partially expanded, this is the number of partial arguments.

    if (IsPartiallyExpanded)

      PackElements += NumPartialPackArgs;

    else if (IsExpanded)

      PackElements += *FixedNumExpansions;

    for (auto &Pack : Packs) {

      if (Info.PendingDeducedPacks.size() > Pack.Index)

        Pack.Outer = Info.PendingDeducedPacks[Pack.Index];

      else

        Info.PendingDeducedPacks.resize(Pack.Index + 1);

      Info.PendingDeducedPacks[Pack.Index] = &Pack;

      if (PartialPackDepthIndex ==

            std::make_pair(Info.getDeducedDepth(), Pack.Index)) {

        Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);

        // We pre-populate the deduced value of the partially-substituted

        // pack with the specified value. This is not entirely correct: the

        // value is supposed to have been substituted, not deduced, but the

        // cases where this is observable require an exact type match anyway.

        //

        // FIXME: If we could represent a "depth i, index j, pack elem k"

        // parameter, we could substitute the partially-substituted pack

        // everywhere and avoid this.

        if (!IsPartiallyExpanded)

          Deduced[Pack.Index] = Pack.New[PackElements];

      }

    }

  }

public:

  ~PackDeductionScope() {

    for (auto &Pack : Packs)

      Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;

  }

  /// Determine whether this pack has already been partially expanded into a

  /// sequence of (prior) function parameters / template arguments.

  bool isPartiallyExpanded() { return IsPartiallyExpanded; }

  /// Determine whether this pack expansion scope has a known, fixed arity.

  /// This happens if it involves a pack from an outer template that has

  /// (notionally) already been expanded.

  bool hasFixedArity() { return FixedNumExpansions.has_value(); }

  /// Determine whether the next element of the argument is still part of this

  /// pack. This is the case unless the pack is already expanded to a fixed

  /// length.

  bool hasNextElement() {

    return !FixedNumExpansions || *FixedNumExpansions > PackElements;

  }

  /// Move to deducing the next element in each pack that is being deduced.

  void nextPackElement() {

    // Capture the deduced template arguments for each parameter pack expanded

    // by this pack expansion, add them to the list of arguments we've deduced

    // for that pack, then clear out the deduced argument.

    for (auto &Pack : Packs) {

      DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];

      if (!Pack.New.empty() || !DeducedArg.isNull()) {

        while (Pack.New.size() < PackElements)

          Pack.New.push_back(DeducedTemplateArgument());

        if (Pack.New.size() == PackElements)

          Pack.New.push_back(DeducedArg);

        else

          Pack.New[PackElements] = DeducedArg;

        DeducedArg = Pack.New.size() > PackElements + 1

                         ? Pack.New[PackElements + 1]

                         : DeducedTemplateArgument();

      }

    }

    ++PackElements;

  }

  /// Finish template argument deduction for a set of argument packs,

  /// producing the argument packs and checking for consistency with prior

  /// deductions.

  Sema::TemplateDeductionResult finish() {

    // Build argument packs for each of the parameter packs expanded by this

    // pack expansion.

    for (auto &Pack : Packs) {

      // Put back the old value for this pack.

      Deduced[Pack.Index] = Pack.Saved;

      // Always make sure the size of this pack is correct, even if we didn't

      // deduce any values for it.

      //

      // FIXME: This isn't required by the normative wording, but substitution

      // and post-substitution checking will always fail if the arity of any

      // pack is not equal to the number of elements we processed. (Either that

      // or something else has gone *very* wrong.) We're permitted to skip any

      // hard errors from those follow-on steps by the intent (but not the

      // wording) of C++ [temp.inst]p8:

      //

      //   If the function selected by overload resolution can be determined

      //   without instantiating a class template definition, it is unspecified

      //   whether that instantiation actually takes place

      Pack.New.resize(PackElements);

      // Build or find a new value for this pack.

      DeducedTemplateArgument NewPack;

      if (Pack.New.empty()) {

        // If we deduced an empty argument pack, create it now.

        NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());

      } else {

        TemplateArgument *ArgumentPack =

            new (S.Context) TemplateArgument[Pack.New.size()];

        std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);

        NewPack = DeducedTemplateArgument(

            TemplateArgument(llvm::ArrayRef(ArgumentPack, Pack.New.size())),

            // FIXME: This is wrong, it's possible that some pack elements are

            // deduced from an array bound and others are not:

            //   template<typename ...T, T ...V> void g(const T (&...p)[V]);

            //   g({1, 2, 3}, {{}, {}});

            // ... should deduce T = {int, size_t (from array bound)}.

            Pack.New[0].wasDeducedFromArrayBound());

      }

      // Pick where we're going to put the merged pack.

      DeducedTemplateArgument *Loc;

      if (Pack.Outer) {

        if (Pack.Outer->DeferredDeduction.isNull()) {

          // Defer checking this pack until we have a complete pack to compare

          // it against.

          Pack.Outer->DeferredDeduction = NewPack;

          continue;

        }