Fix some subtle wrong partial ordering bugs particularly with C++1z auto-typed

non-type template parameters.

During partial ordering, when checking the substituted deduced template
arguments match the original, check the types of non-type template arguments
match even if they're dependent. The only way we get dependent types here is if
they really represent types of the other template (which are supposed to be
modeled as being substituted for unique, non-dependent types).

In order to make this work for auto-typed non-type template arguments, we need
to be able to perform auto deduction even when the initializer and
(potentially) the auto type are dependent, support for which is the bulk of
this patch. (Note that this requires the ability to deduce only a single level
of a multi-level dependent type.)

llvm-svn: 290511

7 files changed, 189 insertions, 93 deletions

diff --git a/clang/include/clang/AST/Type.h b/clang/include/clang/AST/Type.h
index d6b71075129..744a408e579 100644
--- a/clang/include/clang/AST/Type.h
+++ b/clang/include/clang/AST/Type.h
@@ -4092,18 +4092,22 @@ public:
 /// \brief Represents a C++11 auto or C++14 decltype(auto) type.
 ///
 /// These types are usually a placeholder for a deduced type. However, before
-/// the initializer is attached, or if the initializer is type-dependent, there
-/// is no deduced type and an auto type is canonical. In the latter case, it is
-/// also a dependent type.
+/// the initializer is attached, or (usually) if the initializer is
+/// type-dependent, there is no deduced type and an auto type is canonical. In
+/// the latter case, it is also a dependent type.
 class AutoType : public Type, public llvm::FoldingSetNode {
   AutoType(QualType DeducedType, AutoTypeKeyword Keyword, bool IsDependent)
     : Type(Auto, DeducedType.isNull() ? QualType(this, 0) : DeducedType,
            /*Dependent=*/IsDependent, /*InstantiationDependent=*/IsDependent,
-           /*VariablyModified=*/false,
-           /*ContainsParameterPack=*/DeducedType.isNull()
-               ? false : DeducedType->containsUnexpandedParameterPack()) {
-    assert((DeducedType.isNull() || !IsDependent) &&
-           "auto deduced to dependent type");
+           /*VariablyModified=*/false, /*ContainsParameterPack=*/false) {
+    if (!DeducedType.isNull()) {
+      if (DeducedType->isDependentType())
+        setDependent();
+      if (DeducedType->isInstantiationDependentType())
+        setInstantiationDependent();
+      if (DeducedType->containsUnexpandedParameterPack())
+        setContainsUnexpandedParameterPack();
+    }
     AutoTypeBits.Keyword = (unsigned)Keyword;
   }
 
diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h
index e0d75fcf731..d1f043e2d95 100644
--- a/clang/include/clang/Sema/Sema.h
+++ b/clang/include/clang/Sema/Sema.h
@@ -6655,10 +6655,12 @@ public:
     DAR_FailedAlreadyDiagnosed
   };
 
-  DeduceAutoResult DeduceAutoType(TypeSourceInfo *AutoType, Expr *&Initializer,
-                                  QualType &Result);
-  DeduceAutoResult DeduceAutoType(TypeLoc AutoTypeLoc, Expr *&Initializer,
-                                  QualType &Result);
+  DeduceAutoResult
+  DeduceAutoType(TypeSourceInfo *AutoType, Expr *&Initializer, QualType &Result,
+                 Optional<unsigned> DependentDeductionDepth = None);
+  DeduceAutoResult
+  DeduceAutoType(TypeLoc AutoTypeLoc, Expr *&Initializer, QualType &Result,
+                 Optional<unsigned> DependentDeductionDepth = None);
   void DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init);
   bool DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
                         bool Diagnose = true);
diff --git a/clang/include/clang/Sema/TemplateDeduction.h b/clang/include/clang/Sema/TemplateDeduction.h
index 8a64b8bb962..7344c92a5f8 100644
--- a/clang/include/clang/Sema/TemplateDeduction.h
+++ b/clang/include/clang/Sema/TemplateDeduction.h
@@ -40,6 +40,9 @@ class TemplateDeductionInfo {
   /// \brief Have we suppressed an error during deduction?
   bool HasSFINAEDiagnostic;
 
+  /// \brief The template parameter depth for which we're performing deduction.
+  unsigned DeducedDepth;
+
   /// \brief Warnings (and follow-on notes) that were suppressed due to
   /// SFINAE while performing template argument deduction.
   SmallVector<PartialDiagnosticAt, 4> SuppressedDiagnostics;
@@ -48,9 +51,9 @@ class TemplateDeductionInfo {
   void operator=(const TemplateDeductionInfo &) = delete;
 
 public:
-  TemplateDeductionInfo(SourceLocation Loc)
+  TemplateDeductionInfo(SourceLocation Loc, unsigned DeducedDepth = 0)
     : Deduced(nullptr), Loc(Loc), HasSFINAEDiagnostic(false),
-      Expression(nullptr) {}
+      DeducedDepth(DeducedDepth), Expression(nullptr) {}
 
   /// \brief Returns the location at which template argument is
   /// occurring.
@@ -58,6 +61,12 @@ public:
     return Loc;
   }
 
+  /// \brief The depth of template parameters for which deduction is being
+  /// performed.
+  unsigned getDeducedDepth() const {
+    return DeducedDepth;
+  }
+
   /// \brief Take ownership of the deduced template argument list.
   TemplateArgumentList *take() {
     TemplateArgumentList *Result = Deduced;
diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp
index bbf1965eef4..766ed944b13 100644
--- a/clang/lib/Sema/SemaTemplate.cpp
+++ b/clang/lib/Sema/SemaTemplate.cpp
@@ -5008,9 +5008,15 @@ ExprResult Sema::CheckTemplateArgument(NonTypeTemplateParmDecl *Param,
 
   // If the parameter type somehow involves auto, deduce the type now.
   if (getLangOpts().CPlusPlus1z && ParamType->isUndeducedType()) {
+    // When checking a deduced template argument, deduce from its type even if
+    // the type is dependent, in order to check the types of non-type template
+    // arguments line up properly in partial ordering.
+    Optional<unsigned> Depth;
+    if (CTAK != CTAK_Specified)
+      Depth = Param->getDepth() + 1;
     if (DeduceAutoType(
             Context.getTrivialTypeSourceInfo(ParamType, Param->getLocation()),
-                       Arg, ParamType) == DAR_Failed) {
+            Arg, ParamType, Depth) == DAR_Failed) {
       Diag(Arg->getExprLoc(),
            diag::err_non_type_template_parm_type_deduction_failure)
         << Param->getDeclName() << Param->getType() << Arg->getType()
@@ -5029,14 +5035,6 @@ ExprResult Sema::CheckTemplateArgument(NonTypeTemplateParmDecl *Param,
     }
   }
 
-  // If either the parameter has a dependent type or the argument is
-  // type-dependent, there's nothing we can check now.
-  if (ParamType->isDependentType() || Arg->isTypeDependent()) {
-    // FIXME: Produce a cloned, canonical expression?
-    Converted = TemplateArgument(Arg);
-    return Arg;
-  }
-
   // We should have already dropped all cv-qualifiers by now.
   assert(!ParamType.hasQualifiers() &&
          "non-type template parameter type cannot be qualified");
@@ -5058,6 +5056,14 @@ ExprResult Sema::CheckTemplateArgument(NonTypeTemplateParmDecl *Param,
     return ExprError();
   }
 
+  // If either the parameter has a dependent type or the argument is
+  // type-dependent, there's nothing we can check now.
+  if (ParamType->isDependentType() || Arg->isTypeDependent()) {
+    // FIXME: Produce a cloned, canonical expression?
+    Converted = TemplateArgument(Arg);
+    return Arg;
+  }
+
   if (getLangOpts().CPlusPlus1z) {
     // C++1z [temp.arg.nontype]p1:
     //   A template-argument for a non-type template parameter shall be
diff --git a/clang/lib/Sema/SemaTemplateDeduction.cpp b/clang/lib/Sema/SemaTemplateDeduction.cpp
index 3b02624e536..5c98ebf39ab 100644
--- a/clang/lib/Sema/SemaTemplateDeduction.cpp
+++ b/clang/lib/Sema/SemaTemplateDeduction.cpp
@@ -114,7 +114,8 @@ DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
 /// \brief 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 NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
+static NonTypeTemplateParmDecl *
+getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) {
   // If we are within an alias template, the expression may have undergone
   // any number of parameter substitutions already.
   while (1) {
@@ -128,7 +129,9 @@ static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
   }
 
   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
-    return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
+    if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
+      if (NTTP->getDepth() == Info.getDeducedDepth())
+        return NTTP;
 
   return nullptr;
 }
@@ -310,8 +313,8 @@ static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
     NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
     QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
     SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
-  assert(NTTP->getDepth() == 0 &&
-         "Cannot deduce non-type template argument with depth > 0");
+  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
+         "deducing non-type template argument with wrong depth");
 
   DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType,
                                      DeducedFromArrayBound);
@@ -377,8 +380,8 @@ DeduceNonTypeTemplateArgument(Sema &S,
                               Expr *Value,
                               TemplateDeductionInfo &Info,
                     SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
-  assert(NTTP->getDepth() == 0 &&
-         "Cannot deduce non-type template argument with depth > 0");
+  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
+         "deducing non-type template argument with wrong depth");
   assert((Value->isTypeDependent() || Value->isValueDependent()) &&
          "Expression template argument must be type- or value-dependent.");
 
@@ -413,8 +416,8 @@ DeduceNonTypeTemplateArgument(Sema &S,
                             ValueDecl *D, QualType T,
                             TemplateDeductionInfo &Info,
                             SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
-  assert(NTTP->getDepth() == 0 &&
-         "Cannot deduce non-type template argument with depth > 0");
+  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
+         "deducing non-type template argument with wrong depth");
 
   D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
   TemplateArgument New(D, T);
@@ -453,6 +456,10 @@ DeduceTemplateArguments(Sema &S,
 
   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()],
@@ -655,7 +662,7 @@ public:
       for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
         unsigned Depth, Index;
         std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
-        if (Depth == 0 && !SawIndices[Index]) {
+        if (Depth == Info.getDeducedDepth() && !SawIndices[Index]) {
           SawIndices[Index] = true;
 
           // Save the deduced template argument for the parameter pack expanded
@@ -686,7 +693,8 @@ public:
             S.CurrentInstantiationScope->getPartiallySubstitutedPack(
                 &ExplicitArgs, &NumExplicitArgs);
         if (PartiallySubstitutedPack &&
-            getDepthAndIndex(PartiallySubstitutedPack).second == Pack.Index)
+            getDepthAndIndex(PartiallySubstitutedPack) ==
+                std::make_pair(Info.getDeducedDepth(), Pack.Index))
           Pack.New.append(ExplicitArgs, ExplicitArgs + NumExplicitArgs);
       }
     }
@@ -1124,8 +1132,10 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
   //     cv-list T
   if (const TemplateTypeParmType *TemplateTypeParm
         = Param->getAs<TemplateTypeParmType>()) {
-    // Just skip any attempts to deduce from a placeholder type.
-    if (Arg->isPlaceholderType())
+    // Just skip any attempts to deduce from a placeholder type or a parameter
+    // at a different depth.
+    if (Arg->isPlaceholderType() ||
+        Info.getDeducedDepth() != TemplateTypeParm->getDepth())
       return Sema::TDK_Success;
 
     unsigned Index = TemplateTypeParm->getIndex();
@@ -1152,7 +1162,8 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
       return Sema::TDK_Underqualified;
     }
 
-    assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
+    assert(TemplateTypeParm->getDepth() == Info.getDeducedDepth() &&
+           "saw template type parameter with wrong depth");
     assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
     QualType DeducedType = Arg;
 
@@ -1404,14 +1415,14 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
 
       // Determine the array bound is something we can deduce.
       NonTypeTemplateParmDecl *NTTP
-        = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
+        = getDeducedParameterFromExpr(Info, DependentArrayParm->getSizeExpr());
       if (!NTTP)
         return Sema::TDK_Success;
 
       // We can perform template argument deduction for the given non-type
       // template parameter.
-      assert(NTTP->getDepth() == 0 &&
-             "Cannot deduce non-type template argument at depth > 0");
+      assert(NTTP->getDepth() == Info.getDeducedDepth() &&
+             "saw non-type template parameter with wrong depth");
       if (const ConstantArrayType *ConstantArrayArg
             = dyn_cast<ConstantArrayType>(ArrayArg)) {
         llvm::APSInt Size(ConstantArrayArg->getSize());
@@ -1689,14 +1700,17 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
 
         // Perform deduction on the vector size, if we can.
         NonTypeTemplateParmDecl *NTTP
-          = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
+          = getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
         if (!NTTP)
           return Sema::TDK_Success;
 
         llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
         ArgSize = VectorArg->getNumElements();
+        // Note that we use the "array bound" rules here; just like in that
+        // case, we don't have any particular type for the vector size, but
+        // we can provide one if necessary.
         return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
-                                             S.Context.IntTy, false, Info,
+                                             S.Context.IntTy, true, Info,
                                              Deduced);
       }
 
@@ -1712,7 +1726,7 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
 
         // Perform deduction on the vector size, if we can.
         NonTypeTemplateParmDecl *NTTP
-          = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
+          = getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
         if (!NTTP)
           return Sema::TDK_Success;
 
@@ -1820,7 +1834,7 @@ DeduceTemplateArguments(Sema &S,
 
   case TemplateArgument::Expression: {
     if (NonTypeTemplateParmDecl *NTTP
-          = getDeducedParameterFromExpr(Param.getAsExpr())) {
+          = getDeducedParameterFromExpr(Info, Param.getAsExpr())) {
       if (Arg.getKind() == TemplateArgument::Integral)
         return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
                                              Arg.getAsIntegral(),
@@ -2132,7 +2146,7 @@ ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
                                DeducedTemplateArgument Arg,
                                NamedDecl *Template,
                                TemplateDeductionInfo &Info,
-                               bool InFunctionTemplate,
+                               bool IsDeduced,
                                SmallVectorImpl<TemplateArgument> &Output) {
   auto ConvertArg = [&](DeducedTemplateArgument Arg,
                         unsigned ArgumentPackIndex) {
@@ -2146,7 +2160,7 @@ ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
     return S.CheckTemplateArgument(
         Param, ArgLoc, Template, Template->getLocation(),
         Template->getSourceRange().getEnd(), ArgumentPackIndex, Output,
-        InFunctionTemplate
+        IsDeduced
             ? (Arg.wasDeducedFromArrayBound() ? Sema::CTAK_DeducedFromArrayBound
                                               : Sema::CTAK_Deduced)
             : Sema::CTAK_Specified);
@@ -2210,7 +2224,7 @@ ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
 // TemplateDecl.
 template<typename TemplateDeclT>
 static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
-    Sema &S, TemplateDeclT *Template,
+    Sema &S, TemplateDeclT *Template, bool IsDeduced,
     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
     TemplateDeductionInfo &Info, SmallVectorImpl<TemplateArgument> &Builder,
     LocalInstantiationScope *CurrentInstantiationScope = nullptr,
@@ -2243,8 +2257,7 @@ static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
       // We have deduced this argument, so it still needs to be
       // checked and converted.
       if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
-                                         isa<FunctionTemplateDecl>(Template),
-                                         Builder)) {
+                                         IsDeduced, Builder)) {
         Info.Param = makeTemplateParameter(Param);
         // FIXME: These template arguments are temporary. Free them!
         Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
@@ -2277,9 +2290,8 @@ static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
         // Go through the motions of checking the empty argument pack against
         // the parameter pack.
         DeducedTemplateArgument DeducedPack(TemplateArgument::getEmptyPack());
-        if (ConvertDeducedTemplateArgument(
-                S, Param, DeducedPack, Template, Info,
-                isa<FunctionTemplateDecl>(Template), Builder)) {
+        if (ConvertDeducedTemplateArgument(S, Param, DeducedPack, Template,
+                                           Info, IsDeduced, Builder)) {
           Info.Param = makeTemplateParameter(Param);
           // FIXME: These template arguments are temporary. Free them!
           Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
@@ -2352,7 +2364,8 @@ template <typename T>
 static typename std::enable_if<IsPartialSpecialization<T>::value,
                                Sema::TemplateDeductionResult>::type
 FinishTemplateArgumentDeduction(
-    Sema &S, T *Partial, const TemplateArgumentList &TemplateArgs,
+    Sema &S, T *Partial, bool IsPartialOrdering,
+    const TemplateArgumentList &TemplateArgs,
     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
     TemplateDeductionInfo &Info) {
   // Unevaluated SFINAE context.
@@ -2365,8 +2378,8 @@ FinishTemplateArgumentDeduction(
   //   [...] or if any template argument remains neither deduced nor
   //   explicitly specified, template argument deduction fails.
   SmallVector<TemplateArgument, 4> Builder;
-  if (auto Result = ConvertDeducedTemplateArguments(S, Partial, Deduced,
-                                                    Info, Builder))
+  if (auto Result = ConvertDeducedTemplateArguments(
+          S, Partial, IsPartialOrdering, Deduced, Info, Builder))
     return Result;
 
   // Form the template argument list from the deduced template arguments.
@@ -2463,8 +2476,8 @@ Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
   if (Trap.hasErrorOccurred())
     return Sema::TDK_SubstitutionFailure;
 
-  return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
-                                           Deduced, Info);
+  return ::FinishTemplateArgumentDeduction(
+      *this, Partial, /*PartialOrdering=*/false, TemplateArgs, Deduced, Info);
 }
 
 /// \brief Perform template argument deduction to determine whether
@@ -2503,8 +2516,8 @@ Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
   if (Trap.hasErrorOccurred())
     return Sema::TDK_SubstitutionFailure;
 
-  return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
-                                           Deduced, Info);
+  return ::FinishTemplateArgumentDeduction(
+      *this, Partial, /*PartialOrdering=*/false, TemplateArgs, Deduced, Info);
 }
 
 /// \brief Determine whether the given type T is a simple-template-id type.
@@ -2856,7 +2869,7 @@ Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
   //   explicitly specified, template argument deduction fails.
   SmallVector<TemplateArgument, 4> Builder;
   if (auto Result = ConvertDeducedTemplateArguments(
-          *this, FunctionTemplate, Deduced, Info, Builder,
+          *this, FunctionTemplate, /*IsDeduced*/true, Deduced, Info, Builder,
           CurrentInstantiationScope, NumExplicitlySpecified,
           PartialOverloading))
     return Result;
@@ -3220,7 +3233,7 @@ DeduceFromInitializerList(Sema &S, TemplateParameterList *TemplateParams,
         S.Context.getAsDependentSizedArrayType(AdjustedParamType);
     // Determine the array bound is something we can deduce.
     if (NonTypeTemplateParmDecl *NTTP =
-            getDeducedParameterFromExpr(ArrTy->getSizeExpr())) {
+            getDeducedParameterFromExpr(Info, ArrTy->getSizeExpr())) {
       // We can perform template argument deduction for the given non-type
       // template parameter.
       assert(NTTP->getDepth() == 0 &&
@@ -3950,10 +3963,12 @@ namespace {
   class SubstituteAutoTransform :
     public TreeTransform<SubstituteAutoTransform> {
     QualType Replacement;
+    bool UseAutoSugar;
   public:
-    SubstituteAutoTransform(Sema &SemaRef, QualType Replacement)
+    SubstituteAutoTransform(Sema &SemaRef, QualType Replacement,
+                            bool UseAutoSugar = true)
         : TreeTransform<SubstituteAutoTransform>(SemaRef),
-          Replacement(Replacement) {}
+          Replacement(Replacement), UseAutoSugar(UseAutoSugar) {}
 
     QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
       // If we're building the type pattern to deduce against, don't wrap the
@@ -3963,19 +3978,17 @@ namespace {
       //   auto &&lref = lvalue;
       // must transform into "rvalue reference to T" not "rvalue reference to
       // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
-      if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
+      if (!UseAutoSugar) {
+        assert(isa<TemplateTypeParmType>(Replacement) &&
+               "unexpected unsugared replacement kind");
         QualType Result = Replacement;
         TemplateTypeParmTypeLoc NewTL =
           TLB.push<TemplateTypeParmTypeLoc>(Result);
         NewTL.setNameLoc(TL.getNameLoc());
         return Result;
       } else {
-        bool Dependent =
-          !Replacement.isNull() && Replacement->isDependentType();
-        QualType Result =
-          SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
-                                      TL.getTypePtr()->getKeyword(),
-                                      Dependent);
+        QualType Result = SemaRef.Context.getAutoType(
+            Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull());
         AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
         NewTL.setNameLoc(TL.getNameLoc());
         return Result;
@@ -3998,18 +4011,29 @@ namespace {
 }
 
 Sema::DeduceAutoResult
-Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
-  return DeduceAutoType(Type->getTypeLoc(), Init, Result);
+Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result,
+                     Optional<unsigned> DependentDeductionDepth) {
+  return DeduceAutoType(Type->getTypeLoc(), Init, Result,
+                        DependentDeductionDepth);
 }
 
 /// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
 ///
+/// Note that this is done even if the initializer is dependent. (This is
+/// necessary to support partial ordering of templates using 'auto'.)
+/// A dependent type will be produced when deducing from a dependent type.
+///
 /// \param Type the type pattern using the auto type-specifier.
 /// \param Init the initializer for the variable whose type is to be deduced.
 /// \param Result if type deduction was successful, this will be set to the
 ///        deduced type.
+/// \param DependentDeductionDepth Set if we should permit deduction in
+///        dependent cases. This is necessary for template partial ordering with
+///        'auto' template parameters. The value specified is the template
+///        parameter depth at which we should perform 'auto' deduction.
 Sema::DeduceAutoResult
-Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
+Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
+                     Optional<unsigned> DependentDeductionDepth) {
   if (Init->getType()->isNonOverloadPlaceholderType()) {
     ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
     if (NonPlaceholder.isInvalid())
@@ -4017,12 +4041,16 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
     Init = NonPlaceholder.get();
   }
 
-  if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
-    Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
+  if (!DependentDeductionDepth &&
+      (Type.getType()->isDependentType() || Init->isTypeDependent())) {
+    Result = SubstituteAutoTransform(*this, QualType()).Apply(Type);
     assert(!Result.isNull() && "substituting DependentTy can't fail");
     return DAR_Succeeded;
   }
 
+  // Find the depth of template parameter to synthesize.
+  unsigned Depth = DependentDeductionDepth.getValueOr(0);
+
   // If this is a 'decltype(auto)' specifier, do the decltype dance.
   // Since 'decltype(auto)' can only occur at the top of the type, we
   // don't need to go digging for it.
@@ -4055,15 +4083,16 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
   LocalInstantiationScope InstScope(*this);
 
   // Build template<class TemplParam> void Func(FuncParam);
-  TemplateTypeParmDecl *TemplParam =
-    TemplateTypeParmDecl::Create(Context, nullptr, SourceLocation(), Loc, 0, 0,
-                                 nullptr, false, false);
+  TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create(
+      Context, nullptr, SourceLocation(), Loc, Depth, 0, nullptr, false, false);
   QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
   NamedDecl *TemplParamPtr = TemplParam;
   FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt(
       Loc, Loc, TemplParamPtr, Loc, nullptr);
 
-  QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
+  QualType FuncParam =
+      SubstituteAutoTransform(*this, TemplArg, /*UseAutoSugar*/false)
+          .Apply(Type);
   assert(!FuncParam.isNull() &&
          "substituting template parameter for 'auto' failed");
 
@@ -4073,7 +4102,18 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
   QualType InitType = Init->getType();
   unsigned TDF = 0;
 
-  TemplateDeductionInfo Info(Loc);
+  TemplateDeductionInfo Info(Loc, Depth);
+
+  // If deduction failed, don't diagnose if the initializer is dependent; it
+  // might acquire a matching type in the instantiation.
+  auto DeductionFailed = [&]() -> DeduceAutoResult {
+    if (Init->isTypeDependent()) {
+      Result = SubstituteAutoTransform(*this, QualType()).Apply(Type);
+      assert(!Result.isNull() && "substituting DependentTy can't fail");
+      return DAR_Succeeded;
+    }
+    return DAR_Failed;
+  };
 
   InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
   if (InitList) {
@@ -4081,7 +4121,7 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
       if (DeduceTemplateArgumentByListElement(*this, TemplateParamsSt.get(),
                                               TemplArg, InitList->getInit(i),
                                               Info, Deduced, TDF))
-        return DAR_Failed;
+        return DeductionFailed();
     }
   } else {
     if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
@@ -4096,11 +4136,12 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
     if (DeduceTemplateArgumentsByTypeMatch(*this, TemplateParamsSt.get(),
                                            FuncParam, InitType, Info, Deduced,
                                            TDF))
-      return DAR_Failed;
+      return DeductionFailed();
   }
 
+  // Could be null if somehow 'auto' appears in a non-deduced context.
   if (Deduced[0].getKind() != TemplateArgument::Type)
-    return DAR_Failed;
+    return DeductionFailed();
 
   QualType DeducedType = Deduced[0].getAsType();
 
@@ -4112,7 +4153,7 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
 
   Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
   if (Result.isNull())
-   return DAR_FailedAlreadyDiagnosed;
+    return DAR_FailedAlreadyDiagnosed;
 
   // Check that the deduced argument type is compatible with the original
   // argument type per C++ [temp.deduct.call]p4.
@@ -4121,7 +4162,7 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
                                     Sema::OriginalCallArg(FuncParam,0,InitType),
                                     Result)) {
     Result = QualType();
-    return DAR_Failed;
+    return DeductionFailed();
   }
 
   return DAR_Succeeded;
@@ -4129,14 +4170,18 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
 
 QualType Sema::SubstAutoType(QualType TypeWithAuto,
                              QualType TypeToReplaceAuto) {
-  return SubstituteAutoTransform(*this, TypeToReplaceAuto).
-               TransformType(TypeWithAuto);
+  if (TypeToReplaceAuto->isDependentType())
+    TypeToReplaceAuto = QualType();
+  return SubstituteAutoTransform(*this, TypeToReplaceAuto)
+      .TransformType(TypeWithAuto);
 }
 
 TypeSourceInfo* Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
                              QualType TypeToReplaceAuto) {
-    return SubstituteAutoTransform(*this, TypeToReplaceAuto).
-               TransformType(TypeWithAuto);
+  if (TypeToReplaceAuto->isDependentType())
+    TypeToReplaceAuto = QualType();
+  return SubstituteAutoTransform(*this, TypeToReplaceAuto)
+      .TransformType(TypeWithAuto);
 }
 
 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
@@ -4575,8 +4620,9 @@ static bool isAtLeastAsSpecializedAs(Sema &S, QualType T1, QualType T2,
   Sema::InstantiatingTemplate Inst(S, Loc, P2, DeducedArgs, Info);
   auto *TST1 = T1->castAs<TemplateSpecializationType>();
   if (FinishTemplateArgumentDeduction(
-          S, P2, TemplateArgumentList(TemplateArgumentList::OnStack,
-                                      TST1->template_arguments()),
+          S, P2, /*PartialOrdering=*/true,
+          TemplateArgumentList(TemplateArgumentList::OnStack,
+                               TST1->template_arguments()),
           Deduced, Info))
     return false;
 
diff --git a/clang/test/SemaTemplate/temp_arg_nontype.cpp b/clang/test/SemaTemplate/temp_arg_nontype.cpp
index 91b0c6e7650..f581bcb4482 100644
--- a/clang/test/SemaTemplate/temp_arg_nontype.cpp
+++ b/clang/test/SemaTemplate/temp_arg_nontype.cpp
@@ -364,3 +364,13 @@ namespace PR17696 {
 
   b<&a::i> c; // okay
 }
+
+namespace partial_order_different_types {
+  // These are unordered because the type of the final argument doesn't match.
+  // FIXME: The second partial specialization should actually be rejected
+  // because it's not more specialized than the primary template.
+  template<int, int, typename T, typename, T> struct A;
+  template<int N, typename T, typename U, T V> struct A<0, N, T, U, V> {}; // expected-note {{matches}}
+  template<typename T, typename U, U V> struct A<0, 0, T, U, V> {}; // expected-note {{matches}}
+  A<0, 0, int, int, 0> a; // expected-error {{ambiguous partial specializations}}
+}
diff --git a/clang/test/SemaTemplate/temp_arg_nontype_cxx1z.cpp b/clang/test/SemaTemplate/temp_arg_nontype_cxx1z.cpp
index 3219258572a..265ea41c3fb 100644
--- a/clang/test/SemaTemplate/temp_arg_nontype_cxx1z.cpp
+++ b/clang/test/SemaTemplate/temp_arg_nontype_cxx1z.cpp
@@ -175,14 +175,33 @@ namespace Auto {
 
     // pointers
     template<auto v>    class B { };
-    template<auto* p>   class B<p> { };
+    template<auto* p>   class B<p> { }; // expected-note {{matches}}
     template<auto** pp> class B<pp> { };
-    template<auto* p0>   int &f(B<p0> b);
-    template<auto** pp0> float &f(B<pp0> b);
+    template<auto* p0>   int &f(B<p0> b); // expected-note {{candidate}}
+    template<auto** pp0> float &f(B<pp0> b); // expected-note {{candidate}}
 
     int a, *b = &a;
     int &r = f(B<&a>());
     float &s = f(B<&b>());
+
+    // pointers to members
+    template<typename T, auto *T::*p> struct B<p> {};
+    template<typename T, auto **T::*p> struct B<p> {};
+    template<typename T, auto *T::*p0>   char &f(B<p0> b); // expected-note {{candidate}}
+    template<typename T, auto **T::*pp0> short &f(B<pp0> b); // expected-note {{candidate}}
+
+    struct X { int n; int *p; int **pp; typedef int a, b; };
+    auto t = f(B<&X::n>()); // expected-error {{no match}}
+    char &u = f(B<&X::p>());
+    short &v = f(B<&X::pp>());
+
+    // A case where we need to do auto-deduction, and check whether the
+    // resulting dependent types match during partial ordering. These
+    // templates are not ordered due to the mismatching function parameter.
+    template<typename T, auto *(*f)(T, typename T::a)> struct B<f> {}; // expected-note {{matches}}
+    template<typename T, auto **(*f)(T, typename T::b)> struct B<f> {}; // expected-note {{matches}}
+    int **g(X, int);
+    B<&g> bg; // expected-error {{ambiguous}}
   }
 
   namespace Chained {