[c++1z] Synthesize implicit deduction guides from constructors on demand. Rank

such guides below explicit ones, and ensure that references to the class's
template parameters are not treated as forwarding references.

We make a few tweaks to the wording in the current standard:
1) The constructor parameter list is copied faithfully to the deduction guide,
   without losing default arguments or a varargs ellipsis (which the standard
   wording loses by omission).
2) If the class template declares no constructors, we add a T() -> T<...> guide
   (which will only ever work if T has default arguments for all non-pack
   template parameters).
3) If the class template declares nothing that looks like a copy or move
   constructor, we add a T(T<...>) -> T<...> guide.
#2 and #3 follow from the "pretend we had a class type with these constructors"
philosophy for deduction guides.

llvm-svn: 295007

6 files changed, 462 insertions, 69 deletions

diff --git a/clang/lib/Sema/SemaInit.cpp b/clang/lib/Sema/SemaInit.cpp
index 32e7ae0d8d8..a455717c4d6 100644
--- a/clang/lib/Sema/SemaInit.cpp
+++ b/clang/lib/Sema/SemaInit.cpp
@@ -8242,45 +8242,27 @@ QualType Sema::DeduceTemplateSpecializationFromInitializer(
     return QualType();
   }
 
+  // Can't deduce from dependent arguments.
+  if (Expr::hasAnyTypeDependentArguments(Inits))
+    return Context.DependentTy;
+
   // FIXME: Perform "exact type" matching first, per CWG discussion?
   //        Or implement this via an implied 'T(T) -> T' deduction guide?
 
   // FIXME: Do we need/want a std::initializer_list<T> special case?
 
+  // Look up deduction guides, including those synthesized from constructors.
+  //
   // C++1z [over.match.class.deduct]p1:
   //   A set of functions and function templates is formed comprising:
-  bool HasDefaultConstructor = false;
-  SmallVector<DeclAccessPair, 16> CtorsAndGuides;
-  CXXRecordDecl *Primary = Template->getTemplatedDecl();
-  bool Complete = isCompleteType(TSInfo->getTypeLoc().getEndLoc(),
-                                 Context.getTypeDeclType(Primary));
-  if (Complete) {
-    for (NamedDecl *D : LookupConstructors(Template->getTemplatedDecl())) {
-      //   - For each constructor of the class template designated by the
-      //     template-name, a function template [...]
-      auto Info = getConstructorInfo(D);
-      if (!Info.Constructor || Info.Constructor->isInvalidDecl())
-        continue;
-
-      // FIXME: Synthesize a deduction guide.
-
-      if (Info.Constructor->isDefaultConstructor())
-        HasDefaultConstructor = true;
-    }
-  }
-
+  //   - For each constructor of the class template designated by the
+  //     template-name, a function template [...]
   //  - For each deduction-guide, a function or function template [...]
   DeclarationNameInfo NameInfo(
       Context.DeclarationNames.getCXXDeductionGuideName(Template),
       TSInfo->getTypeLoc().getEndLoc());
   LookupResult Guides(*this, NameInfo, LookupOrdinaryName);
   LookupQualifiedName(Guides, Template->getDeclContext());
-  for (auto I = Guides.begin(), E = Guides.end(); I != E; ++I) {
-    auto *FD = dyn_cast<FunctionDecl>(*I);
-    if (FD && FD->getMinRequiredArguments() == 0)
-      HasDefaultConstructor = true;
-    CtorsAndGuides.push_back(I.getPair());
-  }
 
   // FIXME: Do not diagnose inaccessible deduction guides. The standard isn't
   // clear on this, but they're not found by name so access does not apply.
@@ -8307,8 +8289,8 @@ QualType Sema::DeduceTemplateSpecializationFromInitializer(
   auto tryToResolveOverload =
       [&](bool OnlyListConstructors) -> OverloadingResult {
     Candidates.clear();
-    for (DeclAccessPair Pair : CtorsAndGuides) {
-      NamedDecl *D = Pair.getDecl()->getUnderlyingDecl();
+    for (auto I = Guides.begin(), E = Guides.end(); I != E; ++I) {
+      NamedDecl *D = (*I)->getUnderlyingDecl();
       if (D->isInvalidDecl())
         continue;
 
@@ -8357,10 +8339,11 @@ QualType Sema::DeduceTemplateSpecializationFromInitializer(
       bool SuppressUserConversions = Kind.isCopyInit();
 
       if (TD)
-        AddTemplateOverloadCandidate(TD, Pair, /*ExplicitArgs*/ nullptr, Inits,
-                                     Candidates, SuppressUserConversions);
+        AddTemplateOverloadCandidate(TD, I.getPair(), /*ExplicitArgs*/ nullptr,
+                                     Inits, Candidates,
+                                     SuppressUserConversions);
       else
-        AddOverloadCandidate(FD, Pair, Inits, Candidates,
+        AddOverloadCandidate(FD, I.getPair(), Inits, Candidates,
                              SuppressUserConversions);
     }
     return Candidates.BestViableFunction(*this, Kind.getLocation(), Best);
@@ -8371,7 +8354,21 @@ QualType Sema::DeduceTemplateSpecializationFromInitializer(
   // C++11 [over.match.list]p1, per DR1467: for list-initialization, first
   // try initializer-list constructors.
   if (ListInit) {
-    if (ListInit->getNumInits() || !HasDefaultConstructor)
+    bool TryListConstructors = true;
+
+    // Try list constructors unless the list is empty and the class has one or
+    // more default constructors, in which case those constructors win.
+    if (!ListInit->getNumInits()) {
+      for (NamedDecl *D : Guides) {
+        auto *FD = dyn_cast<FunctionDecl>(D->getUnderlyingDecl());
+        if (FD && FD->getMinRequiredArguments() == 0) {
+          TryListConstructors = false;
+          break;
+        }
+      }
+    }
+
+    if (TryListConstructors)
       Result = tryToResolveOverload(/*OnlyListConstructor*/true);
     // Then unwrap the initializer list and try again considering all
     // constructors.
@@ -8393,13 +8390,18 @@ QualType Sema::DeduceTemplateSpecializationFromInitializer(
     Candidates.NoteCandidates(*this, OCD_ViableCandidates, Inits);
     return QualType();
 
-  case OR_No_Viable_Function:
+  case OR_No_Viable_Function: {
+    CXXRecordDecl *Primary =
+        cast<ClassTemplateDecl>(Template)->getTemplatedDecl();
+    bool Complete =
+        isCompleteType(Kind.getLocation(), Context.getTypeDeclType(Primary));
     Diag(Kind.getLocation(),
          Complete ? diag::err_deduced_class_template_ctor_no_viable
                   : diag::err_deduced_class_template_incomplete)
-      << TemplateName << !CtorsAndGuides.empty();
+      << TemplateName << !Guides.empty();
     Candidates.NoteCandidates(*this, OCD_AllCandidates, Inits);
     return QualType();
+  }
 
   case OR_Deleted: {
     Diag(Kind.getLocation(), diag::err_deduced_class_template_deleted)
diff --git a/clang/lib/Sema/SemaLookup.cpp b/clang/lib/Sema/SemaLookup.cpp
index 7066215b2b0..9ea433ffe5c 100644
--- a/clang/lib/Sema/SemaLookup.cpp
+++ b/clang/lib/Sema/SemaLookup.cpp
@@ -774,6 +774,7 @@ static bool isImplicitlyDeclaredMemberFunctionName(DeclarationName Name) {
 /// that need to be declared in the given declaration context, do so.
 static void DeclareImplicitMemberFunctionsWithName(Sema &S,
                                                    DeclarationName Name,
+                                                   SourceLocation Loc,
                                                    const DeclContext *DC) {
   if (!DC)
     return;
@@ -816,6 +817,10 @@ static void DeclareImplicitMemberFunctionsWithName(Sema &S,
     }
     break;
 
+  case DeclarationName::CXXDeductionGuideName:
+    S.DeclareImplicitDeductionGuides(Name.getCXXDeductionGuideTemplate(), Loc);
+    break;
+
   default:
     break;
   }
@@ -828,7 +833,8 @@ static bool LookupDirect(Sema &S, LookupResult &R, const DeclContext *DC) {
 
   // Lazily declare C++ special member functions.
   if (S.getLangOpts().CPlusPlus)
-    DeclareImplicitMemberFunctionsWithName(S, R.getLookupName(), DC);
+    DeclareImplicitMemberFunctionsWithName(S, R.getLookupName(), R.getNameLoc(),
+                                           DC);
 
   // Perform lookup into this declaration context.
   DeclContext::lookup_result DR = DC->lookup(R.getLookupName());
@@ -1041,7 +1047,7 @@ bool Sema::CppLookupName(LookupResult &R, Scope *S) {
   if (isImplicitlyDeclaredMemberFunctionName(Name)) {
     for (Scope *PreS = S; PreS; PreS = PreS->getParent())
       if (DeclContext *DC = PreS->getEntity())
-        DeclareImplicitMemberFunctionsWithName(*this, Name, DC);
+        DeclareImplicitMemberFunctionsWithName(*this, Name, R.getNameLoc(), DC);
   }
 
   // Implicitly declare member functions with the name we're looking for, if in
diff --git a/clang/lib/Sema/SemaOverload.cpp b/clang/lib/Sema/SemaOverload.cpp
index 05caf923d0c..659d6226f3b 100644
--- a/clang/lib/Sema/SemaOverload.cpp
+++ b/clang/lib/Sema/SemaOverload.cpp
@@ -8991,6 +8991,14 @@ bool clang::isBetterOverloadCandidate(Sema &S, const OverloadCandidate &Cand1,
     // C++14 [over.match.best]p1 section 2 bullet 3.
   }
 
+  //    -- F1 is generated from a deduction-guide and F2 is not
+  if (Cand1.Function && Cand2.Function && Cand1.Function->isDeductionGuide() &&
+      Cand1.Function->isImplicit() != Cand2.Function->isImplicit()) {
+    assert(Cand2.Function->isDeductionGuide() &&
+           "comparing deduction guide with non-deduction-guide");
+    return Cand2.Function->isImplicit();
+  }
+
   //    -- F1 is a non-template function and F2 is a function template
   //       specialization, or, if not that,
   bool Cand1IsSpecialization = Cand1.Function &&
diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp
index dd2dfe4235a..e86f287e0c5 100644
--- a/clang/lib/Sema/SemaTemplate.cpp
+++ b/clang/lib/Sema/SemaTemplate.cpp
@@ -1415,6 +1415,350 @@ Sema::CheckClassTemplate(Scope *S, unsigned TagSpec, TagUseKind TUK,
   return NewTemplate;
 }
 
+namespace {
+/// Transform to convert portions of a constructor declaration into the
+/// corresponding deduction guide, per C++1z [over.match.class.deduct]p1.
+struct ConvertConstructorToDeductionGuideTransform {
+  ConvertConstructorToDeductionGuideTransform(Sema &S,
+                                              ClassTemplateDecl *Template)
+      : SemaRef(S), Template(Template) {}
+
+  Sema &SemaRef;
+  ClassTemplateDecl *Template;
+
+  DeclContext *DC = Template->getDeclContext();
+  CXXRecordDecl *Primary = Template->getTemplatedDecl();
+  DeclarationName DeductionGuideName =
+      SemaRef.Context.DeclarationNames.getCXXDeductionGuideName(Template);
+
+  QualType DeducedType = SemaRef.Context.getTypeDeclType(Primary);
+
+  // Index adjustment to apply to convert depth-1 template parameters into
+  // depth-0 template parameters.
+  unsigned Depth1IndexAdjustment = Template->getTemplateParameters()->size();
+
+  /// Transform a constructor declaration into a deduction guide.
+  NamedDecl *transformConstructor(FunctionTemplateDecl *FTD, FunctionDecl *FD) {
+    SmallVector<TemplateArgument, 16> SubstArgs;
+
+    // C++ [over.match.class.deduct]p1:
+    // -- For each constructor of the class template designated by the
+    //    template-name, a function template with the following properties:
+
+    //    -- The template parameters are the template parameters of the class
+    //       template followed by the template parameters (including default
+    //       template arguments) of the constructor, if any.
+    TemplateParameterList *TemplateParams = Template->getTemplateParameters();
+    if (FTD) {
+      TemplateParameterList *InnerParams = FTD->getTemplateParameters();
+      SmallVector<NamedDecl *, 16> AllParams;
+      AllParams.reserve(TemplateParams->size() + InnerParams->size());
+      AllParams.insert(AllParams.begin(),
+                       TemplateParams->begin(), TemplateParams->end());
+      SubstArgs.reserve(InnerParams->size());
+
+      // Later template parameters could refer to earlier ones, so build up
+      // a list of substituted template arguments as we go.
+      for (NamedDecl *Param : *InnerParams) {
+        MultiLevelTemplateArgumentList Args;
+        Args.addOuterTemplateArguments(SubstArgs);
+        Args.addOuterTemplateArguments(None);
+        NamedDecl *NewParam = transformTemplateParameter(Param, Args);
+        if (!NewParam)
+          return nullptr;
+        AllParams.push_back(NewParam);
+        SubstArgs.push_back(SemaRef.Context.getCanonicalTemplateArgument(
+            SemaRef.Context.getInjectedTemplateArg(NewParam)));
+      }
+      TemplateParams = TemplateParameterList::Create(
+          SemaRef.Context, InnerParams->getTemplateLoc(),
+          InnerParams->getLAngleLoc(), AllParams, InnerParams->getRAngleLoc(),
+          /*FIXME: RequiresClause*/ nullptr);
+    }
+
+    // If we built a new template-parameter-list, track that we need to
+    // substitute references to the old parameters into references to the
+    // new ones.
+    MultiLevelTemplateArgumentList Args;
+    if (FTD) {
+      Args.addOuterTemplateArguments(SubstArgs);
+      Args.addOuterTemplateArguments(None);
+    }
+
+    FunctionProtoTypeLoc FPTL = FD->getTypeSourceInfo()->getTypeLoc()
+                                   .getAsAdjusted<FunctionProtoTypeLoc>();
+    assert(FPTL && "no prototype for constructor declaration");
+
+    // Transform the type of the function, adjusting the return type and
+    // replacing references to the old parameters with references to the
+    // new ones.
+    TypeLocBuilder TLB;
+    SmallVector<ParmVarDecl*, 8> Params;
+    QualType NewType = transformFunctionProtoType(TLB, FPTL, Params, Args);
+    if (NewType.isNull())
+      return nullptr;
+    TypeSourceInfo *NewTInfo = TLB.getTypeSourceInfo(SemaRef.Context, NewType);
+
+    return buildDeductionGuide(TemplateParams, FD->isExplicit(), NewTInfo,
+                               FD->getLocStart(), FD->getLocation(),
+                               FD->getLocEnd());
+  }
+
+  /// Build a deduction guide with the specified parameter types.
+  NamedDecl *buildSimpleDeductionGuide(MutableArrayRef<QualType> ParamTypes) {
+    SourceLocation Loc = Template->getLocation();
+
+    // Build the requested type.
+    FunctionProtoType::ExtProtoInfo EPI;
+    EPI.HasTrailingReturn = true;
+    QualType Result = SemaRef.BuildFunctionType(DeducedType, ParamTypes, Loc,
+                                                DeductionGuideName, EPI);
+    TypeSourceInfo *TSI = SemaRef.Context.getTrivialTypeSourceInfo(Result, Loc);
+
+    FunctionProtoTypeLoc FPTL =
+        TSI->getTypeLoc().castAs<FunctionProtoTypeLoc>();
+
+    // Build the parameters, needed during deduction / substitution.
+    SmallVector<ParmVarDecl*, 4> Params;
+    for (auto T : ParamTypes) {
+      ParmVarDecl *NewParam = ParmVarDecl::Create(
+          SemaRef.Context, DC, Loc, Loc, nullptr, T,
+          SemaRef.Context.getTrivialTypeSourceInfo(T, Loc), SC_None, nullptr);
+      NewParam->setScopeInfo(0, Params.size());
+      FPTL.setParam(Params.size(), NewParam);
+      Params.push_back(NewParam);
+    }
+
+    return buildDeductionGuide(Template->getTemplateParameters(), false, TSI,
+                               Loc, Loc, Loc);
+  }
+
+private:
+  /// Transform a constructor template parameter into a deduction guide template
+  /// parameter, rebuilding any internal references to earlier parameters and
+  /// renumbering as we go.
+  NamedDecl *transformTemplateParameter(NamedDecl *TemplateParam,
+                                        MultiLevelTemplateArgumentList &Args) {
+    if (auto *TTP = dyn_cast<TemplateTypeParmDecl>(TemplateParam)) {
+      // TemplateTypeParmDecl's index cannot be changed after creation, so
+      // substitute it directly.
+      auto *NewTTP = TemplateTypeParmDecl::Create(
+          SemaRef.Context, DC, TTP->getLocStart(), TTP->getLocation(),
+          /*Depth*/0, Depth1IndexAdjustment + TTP->getIndex(),
+          TTP->getIdentifier(), TTP->wasDeclaredWithTypename(),
+          TTP->isParameterPack());
+      if (TTP->hasDefaultArgument()) {
+        TypeSourceInfo *InstantiatedDefaultArg =
+            SemaRef.SubstType(TTP->getDefaultArgumentInfo(), Args,
+                              TTP->getDefaultArgumentLoc(), TTP->getDeclName());
+        if (InstantiatedDefaultArg)
+          NewTTP->setDefaultArgument(InstantiatedDefaultArg);
+      }
+      return NewTTP;
+    }
+
+    if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(TemplateParam))
+      return transformTemplateParameterImpl(TTP, Args);
+
+    return transformTemplateParameterImpl(
+        cast<NonTypeTemplateParmDecl>(TemplateParam), Args);
+  }
+  template<typename TemplateParmDecl>
+  TemplateParmDecl *
+  transformTemplateParameterImpl(TemplateParmDecl *OldParam,
+                                 MultiLevelTemplateArgumentList &Args) {
+    // Ask the template instantiator to do the heavy lifting for us, then adjust
+    // the index of the parameter once it's done.
+    auto *NewParam =
+        cast_or_null<TemplateParmDecl>(SemaRef.SubstDecl(OldParam, DC, Args));
+    assert(NewParam->getDepth() == 0 && "unexpected template param depth");
+    NewParam->setPosition(NewParam->getPosition() + Depth1IndexAdjustment);
+    return NewParam;
+  }
+
+  QualType transformFunctionProtoType(TypeLocBuilder &TLB,
+                                      FunctionProtoTypeLoc TL,
+                                      SmallVectorImpl<ParmVarDecl*> &Params,
+                                      MultiLevelTemplateArgumentList &Args) {
+    SmallVector<QualType, 4> ParamTypes;
+    const FunctionProtoType *T = TL.getTypePtr();
+
+    //    -- The types of the function parameters are those of the constructor.
+    for (auto *OldParam : TL.getParams()) {
+      // If we're transforming a non-template constructor, just reuse its
+      // parameters as the parameters of the deduction guide. Otherwise, we
+      // need to transform their references to constructor template parameters.
+      ParmVarDecl *NewParam = Args.getNumLevels()
+                                  ? transformFunctionTypeParam(OldParam, Args)
+                                  : OldParam;
+      if (!NewParam)
+        return QualType();
+      ParamTypes.push_back(NewParam->getType());
+      Params.push_back(NewParam);
+    }
+
+    //    -- The return type is the class template specialization designated by
+    //       the template-name and template arguments corresponding to the
+    //       template parameters obtained from the class template.
+    //
+    // We use the injected-class-name type of the primary template instead.
+    // This has the convenient property that it is different from any type that
+    // the user can write in a deduction-guide (because they cannot enter the
+    // context of the template), so implicit deduction guides can never collide
+    // with explicit ones.
+    QualType ReturnType = DeducedType;
+    TLB.pushTypeSpec(ReturnType).setNameLoc(Primary->getLocation());
+
+    // Resolving a wording defect, we also inherit the variadicness of the
+    // constructor.
+    FunctionProtoType::ExtProtoInfo EPI;
+    EPI.Variadic = T->isVariadic();
+    EPI.HasTrailingReturn = true;
+
+    QualType Result = SemaRef.BuildFunctionType(
+        ReturnType, ParamTypes, TL.getLocStart(), DeductionGuideName, EPI);
+    if (Result.isNull())
+      return QualType();
+
+    FunctionProtoTypeLoc NewTL = TLB.push<FunctionProtoTypeLoc>(Result);
+    NewTL.setLocalRangeBegin(TL.getLocalRangeBegin());
+    NewTL.setLParenLoc(TL.getLParenLoc());
+    NewTL.setRParenLoc(TL.getRParenLoc());
+    NewTL.setExceptionSpecRange(SourceRange());
+    NewTL.setLocalRangeEnd(TL.getLocalRangeEnd());
+    for (unsigned I = 0, E = NewTL.getNumParams(); I != E; ++I)
+      NewTL.setParam(I, Params[I]);
+
+    return Result;
+  }
+
+  ParmVarDecl *
+  transformFunctionTypeParam(ParmVarDecl *OldParam,
+                             MultiLevelTemplateArgumentList &Args) {
+    TypeSourceInfo *OldDI = OldParam->getTypeSourceInfo();
+    TypeSourceInfo *NewDI = SemaRef.SubstType(
+        OldDI, Args, OldParam->getLocation(), OldParam->getDeclName());
+    if (!NewDI)
+      return nullptr;
+
+    // Resolving a wording defect, we also inherit default arguments from the
+    // constructor.
+    ExprResult NewDefArg;
+    if (OldParam->hasDefaultArg()) {
+      NewDefArg = SemaRef.SubstExpr(OldParam->getDefaultArg(), Args);
+      if (NewDefArg.isInvalid())
+        return nullptr;
+    }
+
+    ParmVarDecl *NewParam = ParmVarDecl::Create(SemaRef.Context, DC,
+                                                OldParam->getInnerLocStart(),
+                                                OldParam->getLocation(),
+                                                OldParam->getIdentifier(),
+                                                NewDI->getType(),
+                                                NewDI,
+                                                OldParam->getStorageClass(),
+                                                NewDefArg.get());
+    NewParam->setScopeInfo(OldParam->getFunctionScopeDepth(),
+                           OldParam->getFunctionScopeIndex());
+    return NewParam;
+  }
+
+  NamedDecl *buildDeductionGuide(TemplateParameterList *TemplateParams,
+                                 bool Explicit, TypeSourceInfo *TInfo,
+                                 SourceLocation LocStart, SourceLocation Loc,
+                                 SourceLocation LocEnd) {
+    // Build the implicit deduction guide template.
+    auto *Guide = FunctionDecl::Create(SemaRef.Context, DC, LocStart, Loc,
+                                       DeductionGuideName, TInfo->getType(),
+                                       TInfo, SC_None);
+    Guide->setImplicit();
+    if (Explicit)
+      Guide->setExplicitSpecified();
+    Guide->setRangeEnd(LocEnd);
+    Guide->setParams(
+        TInfo->getTypeLoc().castAs<FunctionProtoTypeLoc>().getParams());
+
+    auto *GuideTemplate = FunctionTemplateDecl::Create(
+        SemaRef.Context, DC, Loc, DeductionGuideName, TemplateParams, Guide);
+    GuideTemplate->setImplicit();
+    Guide->setDescribedFunctionTemplate(GuideTemplate);
+
+    if (isa<CXXRecordDecl>(DC)) {
+      Guide->setAccess(AS_public);
+      GuideTemplate->setAccess(AS_public);
+    }
+
+    DC->addDecl(GuideTemplate);
+    return GuideTemplate;
+  }
+};
+}
+
+void Sema::DeclareImplicitDeductionGuides(TemplateDecl *Template,
+                                          SourceLocation Loc) {
+  DeclContext *DC = Template->getDeclContext();
+  if (DC->isDependentContext())
+    return;
+
+  ConvertConstructorToDeductionGuideTransform Transform(
+      *this, cast<ClassTemplateDecl>(Template));
+  if (!isCompleteType(Loc, Transform.DeducedType))
+    return;
+
+  // Check whether we've already declared deduction guides for this template.
+  // FIXME: Consider storing a flag on the template to indicate this.
+  auto Existing = DC->lookup(Transform.DeductionGuideName);
+  for (auto *D : Existing)
+    if (D->isImplicit())
+      return;
+
+  // In case we were expanding a pack when we attempted to declare deduction
+  // guides, turn off pack expansion for everything we're about to do.
+  ArgumentPackSubstitutionIndexRAII SubstIndex(*this, -1);
+  // Create a template instantiation record to track the "instantiation" of
+  // constructors into deduction guides.
+  // FIXME: Add a kind for this to give more meaningful diagnostics. But can
+  // this substitution process actually fail?
+  InstantiatingTemplate BuildingDeductionGuides(*this, Loc, Template);
+
+  // Convert declared constructors into deduction guide templates.
+  // FIXME: Skip constructors for which deduction must necessarily fail (those
+  // for which some class template parameter without a default argument never
+  // appears in a deduced context).
+  bool AddedAny = false;
+  bool AddedCopyOrMove = false;
+  for (NamedDecl *D : LookupConstructors(Transform.Primary)) {
+    D = D->getUnderlyingDecl();
+    if (D->isInvalidDecl() || D->isImplicit())
+      continue;
+    D = cast<NamedDecl>(D->getCanonicalDecl());
+
+    auto *FTD = dyn_cast<FunctionTemplateDecl>(D);
+    auto *FD = FTD ? FTD->getTemplatedDecl() : dyn_cast<FunctionDecl>(D);
+    // Class-scope explicit specializations (MS extension) do not result in
+    // deduction guides.
+    if (!FD || (!FTD && FD->isFunctionTemplateSpecialization()))
+      continue;
+
+    Transform.transformConstructor(FTD, FD);
+    AddedAny = true;
+
+    CXXConstructorDecl *CD = cast<CXXConstructorDecl>(FD);
+    AddedCopyOrMove |= CD->isCopyOrMoveConstructor();
+  }
+
+  // Synthesize an X() -> X<...> guide if there were no declared constructors.
+  // FIXME: The standard doesn't say (how) to do this.
+  if (!AddedAny)
+    Transform.buildSimpleDeductionGuide(None);
+
+  // Synthesize an X(X<...>) -> X<...> guide if there was no declared constructor
+  // resembling a copy or move constructor.
+  // FIXME: The standard doesn't say (how) to do this.
+  if (!AddedCopyOrMove)
+    Transform.buildSimpleDeductionGuide(Transform.DeducedType);
+}
+
 /// \brief Diagnose the presence of a default template argument on a
 /// template parameter, which is ill-formed in certain contexts.
 ///
diff --git a/clang/lib/Sema/SemaTemplateDeduction.cpp b/clang/lib/Sema/SemaTemplateDeduction.cpp
index 48c8c2b64eb..5d78fd437e2 100644
--- a/clang/lib/Sema/SemaTemplateDeduction.cpp
+++ b/clang/lib/Sema/SemaTemplateDeduction.cpp
@@ -963,6 +963,32 @@ bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
   return Param == Arg;
 }
 
+/// Get the index of the first template parameter that was originally from the
+/// innermost template-parameter-list. This is 0 except when we concatenate
+/// the template parameter lists of a class template and a constructor template
+/// when forming an implicit deduction guide.
+static unsigned getFirstInnerIndex(FunctionTemplateDecl *FTD) {
+  if (!FTD->isImplicit() || !FTD->getTemplatedDecl()->isDeductionGuide())
+    return 0;
+  return FTD->getDeclName().getCXXDeductionGuideTemplate()
+            ->getTemplateParameters()->size();
+}
+
+/// Determine whether a type denotes a forwarding reference.
+static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
+  // C++1z [temp.deduct.call]p3:
+  //   A forwarding reference is an rvalue reference to a cv-unqualified
+  //   template parameter that does not represent a template parameter of a
+  //   class template.
+  if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
+    if (ParamRef->getPointeeType().getQualifiers())
+      return false;
+    auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
+    return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
+  }
+  return false;
+}
+
 /// \brief Deduce the template arguments by comparing the parameter type and
 /// the argument type (C++ [temp.deduct.type]).
 ///
@@ -1083,21 +1109,15 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
       //   taking the address of a function template (14.8.2.2) or when deducing
       //   template arguments from a function declaration (14.8.2.6) and Pi and
       //   Ai are parameters of the top-level parameter-type-list of P and A,
-      //   respectively, Pi is adjusted if it is an rvalue reference to a
-      //   cv-unqualified template parameter and Ai is an lvalue reference, in
+      //   respectively, Pi is adjusted if it is a forwarding reference and Ai
+      //   is an lvalue reference, in
       //   which case the type of Pi is changed to be the template parameter
       //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
       //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
       //   deduced as X&. - end note ]
       TDF &= ~TDF_TopLevelParameterTypeList;
-
-      if (const RValueReferenceType *ParamRef
-                                        = Param->getAs<RValueReferenceType>()) {
-        if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
-            !ParamRef->getPointeeType().getQualifiers())
-          if (Arg->isLValueReferenceType())
-            Param = ParamRef->getPointeeType();
-      }
+      if (isForwardingReference(Param, 0) && Arg->isLValueReferenceType())
+        Param = Param->getPointeeType();
     }
   }
 
@@ -3185,12 +3205,9 @@ ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
 /// \returns true if the caller should not attempt to perform any template
 /// argument deduction based on this P/A pair because the argument is an
 /// overloaded function set that could not be resolved.
-static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
-                                          TemplateParameterList *TemplateParams,
-                                                      QualType &ParamType,
-                                                      QualType &ArgType,
-                                                      Expr *Arg,
-                                                      unsigned &TDF) {
+static bool AdjustFunctionParmAndArgTypesForDeduction(
+    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
+    QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF) {
   // C++0x [temp.deduct.call]p3:
   //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
   //   are ignored for type deduction.
@@ -3221,13 +3238,10 @@ static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
       ArgType = Arg->getType();
     }
 
-    // C++0x [temp.deduct.call]p3:
-    //   If P is an rvalue reference to a cv-unqualified template
-    //   parameter and the argument is an lvalue, the type "lvalue
-    //   reference to A" is used in place of A for type deduction.
-    if (ParamRefType->isRValueReferenceType() &&
-        !ParamType.getQualifiers() &&
-        isa<TemplateTypeParmType>(ParamType) &&
+    // C++1z [temp.deduct.call]p3:
+    //   If P is a forwarding reference and the argument is an lvalue, the type
+    //   "lvalue reference to A" is used in place of A for type deduction.
+    if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
         Arg->isLValue())
       ArgType = S.Context.getLValueReferenceType(ArgType);
   } else {
@@ -3286,8 +3300,8 @@ hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
                                QualType T);
 
 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
-    Sema &S, TemplateParameterList *TemplateParams, QualType ParamType,
-    Expr *Arg, TemplateDeductionInfo &Info,
+    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
+    QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
     SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
     bool DecomposedParam, unsigned ArgIdx, unsigned TDF);
@@ -3325,7 +3339,7 @@ static Sema::TemplateDeductionResult DeduceFromInitializerList(
   if (ElTy->isDependentType()) {
     for (Expr *E : ILE->inits()) {
       if (auto Result = DeduceTemplateArgumentsFromCallArgument(
-              S, TemplateParams, ElTy, E, Info, Deduced, OriginalCallArgs, true,
+              S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
               ArgIdx, TDF))
         return Result;
     }
@@ -3354,8 +3368,8 @@ static Sema::TemplateDeductionResult DeduceFromInitializerList(
 /// \brief Perform template argument deduction per [temp.deduct.call] for a
 ///        single parameter / argument pair.
 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
-    Sema &S, TemplateParameterList *TemplateParams, QualType ParamType,
-    Expr *Arg, TemplateDeductionInfo &Info,
+    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
+    QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
     SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
     bool DecomposedParam, unsigned ArgIdx, unsigned TDF) {
@@ -3364,8 +3378,8 @@ static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
 
   //   If P is a reference type [...]
   //   If P is a cv-qualified type [...]
-  if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
-                                                ArgType, Arg, TDF))
+  if (AdjustFunctionParmAndArgTypesForDeduction(
+          S, TemplateParams, FirstInnerIndex, ParamType, ArgType, Arg, TDF))
     return Sema::TDK_Success;
 
   //   If [...] the argument is a non-empty initializer list [...]
@@ -3421,6 +3435,8 @@ Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
   unsigned NumParams = Function->getNumParams();
 
+  unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
+
   // C++ [temp.deduct.call]p1:
   //   Template argument deduction is done by comparing each function template
   //   parameter type (call it P) with the type of the corresponding argument
@@ -3475,7 +3491,7 @@ Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
 
     //   ... with the type of the corresponding argument
     return DeduceTemplateArgumentsFromCallArgument(
-        *this, TemplateParams, ParamType, Args[ArgIdx], Info, Deduced,
+        *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
         OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0);
   };
 
@@ -4203,7 +4219,7 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
 
     for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
       if (DeduceTemplateArgumentsFromCallArgument(
-              *this, TemplateParamsSt.get(), TemplArg, InitList->getInit(i),
+              *this, TemplateParamsSt.get(), 0, TemplArg, InitList->getInit(i),
               Info, Deduced, OriginalCallArgs, /*Decomposed*/ true,
               /*ArgIdx*/ 0, /*TDF*/ 0))
         return DeductionFailed();
@@ -4215,7 +4231,7 @@ Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
     }
 
     if (DeduceTemplateArgumentsFromCallArgument(
-            *this, TemplateParamsSt.get(), FuncParam, Init, Info, Deduced,
+            *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
             OriginalCallArgs, /*Decomposed*/ false, /*ArgIdx*/ 0, /*TDF*/ 0))
       return DeductionFailed();
   }
diff --git a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
index a69d54c5dc5..a0e4d2999d9 100644
--- a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
+++ b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
@@ -3553,6 +3553,8 @@ TemplateDeclInstantiator::InitFunctionInstantiation(FunctionDecl *New,
   if (Tmpl->isDeleted())
     New->setDeletedAsWritten();
 
+  New->setImplicit(Tmpl->isImplicit());
+
   // Forward the mangling number from the template to the instantiated decl.
   SemaRef.Context.setManglingNumber(New,
                                     SemaRef.Context.getManglingNumber(Tmpl));
@@ -4952,6 +4954,21 @@ NamedDecl *Sema::FindInstantiatedDecl(SourceLocation Loc, NamedDecl *D,
           DC = FD->getLexicalDeclContext();
           continue;
         }
+        // An implicit deduction guide acts as if it's within the class template
+        // specialization described by its name and first N template params.
+        if (FD->isDeductionGuide() && FD->isImplicit()) {
+          TemplateDecl *TD = FD->getDeclName().getCXXDeductionGuideTemplate();
+          TemplateArgumentListInfo Args(Loc, Loc);
+          for (auto Arg : TemplateArgs.getInnermost().take_front(
+                                      TD->getTemplateParameters()->size()))
+            Args.addArgument(
+                getTrivialTemplateArgumentLoc(Arg, QualType(), Loc));
+          QualType T = CheckTemplateIdType(TemplateName(TD), Loc, Args);
+          if (T.isNull())
+            return nullptr;
+          DC = T->getAsCXXRecordDecl();
+          continue;
+        }
       }
 
       DC = DC->getParent();