Implement the C++0x deduced 'auto' feature.

This fixes PR 8738, 9060 and 9132.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@126069 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 409 insertions, 123 deletions

diff --git a/lib/Sema/SemaCodeComplete.cpp b/lib/Sema/SemaCodeComplete.cpp
index aef5cab98a..bab665a38d 100644
--- a/lib/Sema/SemaCodeComplete.cpp
+++ b/lib/Sema/SemaCodeComplete.cpp
@@ -586,7 +586,6 @@ SimplifiedTypeClass clang::getSimplifiedTypeClass(CanQualType T) {
         
       case BuiltinType::Overload:
       case BuiltinType::Dependent:
-      case BuiltinType::UndeducedAuto:
         return STC_Other;
         
       case BuiltinType::ObjCId:
diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp
index 679b430a3c..dd30c1261e 100644
--- a/lib/Sema/SemaDecl.cpp
+++ b/lib/Sema/SemaDecl.cpp
@@ -1471,48 +1471,26 @@ bool Sema::MergeCompatibleFunctionDecls(FunctionDecl *New, FunctionDecl *Old) {
   return false;
 }
 
-/// MergeVarDecl - We just parsed a variable 'New' which has the same name
-/// and scope as a previous declaration 'Old'.  Figure out how to resolve this
-/// situation, merging decls or emitting diagnostics as appropriate.
+/// MergeVarDecl - We parsed a variable 'New' which has the same name and scope
+/// as a previous declaration 'Old'.  Figure out how to merge their types,
+/// emitting diagnostics as appropriate.
 ///
-/// Tentative definition rules (C99 6.9.2p2) are checked by
-/// FinalizeDeclaratorGroup. Unfortunately, we can't analyze tentative
-/// definitions here, since the initializer hasn't been attached.
+/// Declarations using the auto type specifier (C++ [decl.spec.auto]) call back
+/// to here in AddInitializerToDecl and AddCXXDirectInitializerToDecl. We can't
+/// check them before the initializer is attached.
 ///
-void Sema::MergeVarDecl(VarDecl *New, LookupResult &Previous) {
-  // If the new decl is already invalid, don't do any other checking.
-  if (New->isInvalidDecl())
+void Sema::MergeVarDeclTypes(VarDecl *New, VarDecl *Old) {
+  if (New->isInvalidDecl() || Old->isInvalidDecl())
     return;
 
-  // Verify the old decl was also a variable.
-  VarDecl *Old = 0;
-  if (!Previous.isSingleResult() ||
-      !(Old = dyn_cast<VarDecl>(Previous.getFoundDecl()))) {
-    Diag(New->getLocation(), diag::err_redefinition_different_kind)
-      << New->getDeclName();
-    Diag(Previous.getRepresentativeDecl()->getLocation(),
-         diag::note_previous_definition);
-    return New->setInvalidDecl();
-  }
-
-  // C++ [class.mem]p1:
-  //   A member shall not be declared twice in the member-specification [...]
-  // 
-  // Here, we need only consider static data members.
-  if (Old->isStaticDataMember() && !New->isOutOfLine()) {
-    Diag(New->getLocation(), diag::err_duplicate_member) 
-      << New->getIdentifier();
-    Diag(Old->getLocation(), diag::note_previous_declaration);
-    New->setInvalidDecl();
-  }
-  
-  MergeDeclAttributes(New, Old, Context);
-
-  // Merge the types
   QualType MergedT;
   if (getLangOptions().CPlusPlus) {
-    if (Context.hasSameType(New->getType(), Old->getType()))
-      MergedT = New->getType();
+    AutoType *AT = New->getType()->getContainedAutoType();
+    if (AT && !AT->isDeduced()) {
+      // We don't know what the new type is until the initializer is attached.
+      return;
+    } else if (Context.hasSameType(New->getType(), Old->getType()))
+      return;
     // C++ [basic.link]p10:
     //   [...] the types specified by all declarations referring to a given
     //   object or function shall be identical, except that declarations for an
@@ -1536,7 +1514,8 @@ void Sema::MergeVarDecl(VarDecl *New, LookupResult &Previous) {
         MergedT = Old->getType();
     } else if (New->getType()->isObjCObjectPointerType()
                && Old->getType()->isObjCObjectPointerType()) {
-        MergedT = Context.mergeObjCGCQualifiers(New->getType(), Old->getType());
+        MergedT = Context.mergeObjCGCQualifiers(New->getType(),
+                                                        Old->getType());
     }
   } else {
     MergedT = Context.mergeTypes(New->getType(), Old->getType());
@@ -1548,6 +1527,49 @@ void Sema::MergeVarDecl(VarDecl *New, LookupResult &Previous) {
     return New->setInvalidDecl();
   }
   New->setType(MergedT);
+}
+
+/// MergeVarDecl - We just parsed a variable 'New' which has the same name
+/// and scope as a previous declaration 'Old'.  Figure out how to resolve this
+/// situation, merging decls or emitting diagnostics as appropriate.
+///
+/// Tentative definition rules (C99 6.9.2p2) are checked by
+/// FinalizeDeclaratorGroup. Unfortunately, we can't analyze tentative
+/// definitions here, since the initializer hasn't been attached.
+///
+void Sema::MergeVarDecl(VarDecl *New, LookupResult &Previous) {
+  // If the new decl is already invalid, don't do any other checking.
+  if (New->isInvalidDecl())
+    return;
+
+  // Verify the old decl was also a variable.
+  VarDecl *Old = 0;
+  if (!Previous.isSingleResult() ||
+      !(Old = dyn_cast<VarDecl>(Previous.getFoundDecl()))) {
+    Diag(New->getLocation(), diag::err_redefinition_different_kind)
+      << New->getDeclName();
+    Diag(Previous.getRepresentativeDecl()->getLocation(),
+         diag::note_previous_definition);
+    return New->setInvalidDecl();
+  }
+
+  // C++ [class.mem]p1:
+  //   A member shall not be declared twice in the member-specification [...]
+  // 
+  // Here, we need only consider static data members.
+  if (Old->isStaticDataMember() && !New->isOutOfLine()) {
+    Diag(New->getLocation(), diag::err_duplicate_member) 
+      << New->getIdentifier();
+    Diag(Old->getLocation(), diag::note_previous_declaration);
+    New->setInvalidDecl();
+  }
+  
+  MergeDeclAttributes(New, Old, Context);
+
+  // Merge the types.
+  MergeVarDeclTypes(New, Old);
+  if (New->isInvalidDecl())
+    return;
 
   // C99 6.2.2p4: Check if we have a static decl followed by a non-static.
   if (New->getStorageClass() == SC_Static &&
@@ -3004,6 +3026,12 @@ Sema::ActOnVariableDeclarator(Scope *S, Declarator &D, DeclContext *DC,
     NewVD = VarDecl::Create(Context, DC, D.getIdentifierLoc(),
                             II, R, TInfo, SC, SCAsWritten);
 
+    // If this decl has an auto type in need of deduction, mark the VarDecl so
+    // we can diagnose uses of it in its own initializer.
+    if (D.getDeclSpec().getTypeSpecType() == DeclSpec::TST_auto) {
+      NewVD->setParsingAutoInit(R->getContainedAutoType());
+    }
+
     if (D.isInvalidType() || Invalid)
       NewVD->setInvalidDecl();
 
@@ -4466,17 +4494,14 @@ bool Sema::CheckForConstantInitializer(Expr *Init, QualType DclT) {
   return true;
 }
 
-void Sema::AddInitializerToDecl(Decl *dcl, Expr *init) {
-  AddInitializerToDecl(dcl, init, /*DirectInit=*/false);
-}
-
 /// AddInitializerToDecl - Adds the initializer Init to the
 /// declaration dcl. If DirectInit is true, this is C++ direct
 /// initialization rather than copy initialization.
-void Sema::AddInitializerToDecl(Decl *RealDecl, Expr *Init, bool DirectInit) {
+void Sema::AddInitializerToDecl(Decl *RealDecl, Expr *Init,
+                                bool DirectInit, bool TypeMayContainAuto) {
   // If there is no declaration, there was an error parsing it.  Just ignore
   // the initializer.
-  if (RealDecl == 0)
+  if (RealDecl == 0 || RealDecl->isInvalidDecl())
     return;
 
   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(RealDecl)) {
@@ -4507,6 +4532,25 @@ void Sema::AddInitializerToDecl(Decl *RealDecl, Expr *Init, bool DirectInit) {
     return;
   }
 
+  // C++0x [decl.spec.auto]p6. Deduce the type which 'auto' stands in for.
+  if (TypeMayContainAuto && VDecl->getType()->getContainedAutoType()) {
+    VDecl->setParsingAutoInit(false);
+
+    QualType DeducedType;
+    if (!DeduceAutoType(VDecl->getType(), Init, DeducedType)) {
+      Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure)
+        << VDecl->getDeclName() << VDecl->getType() << Init->getType()
+        << Init->getSourceRange();
+      RealDecl->setInvalidDecl();
+      return;
+    }
+    VDecl->setType(DeducedType);
+
+    // If this is a redeclaration, check that the type we just deduced matches
+    // the previously declared type.
+    if (VarDecl *Old = VDecl->getPreviousDeclaration())
+      MergeVarDeclTypes(VDecl, Old);
+  }
   
 
   // A definition must end up with a complete type, which means it must be
@@ -4755,6 +4799,13 @@ void Sema::ActOnInitializerError(Decl *D) {
   VarDecl *VD = dyn_cast<VarDecl>(D);
   if (!VD) return;
 
+  // Auto types are meaningless if we can't make sense of the initializer.
+  if (VD->isParsingAutoInit()) {
+    VD->setParsingAutoInit(false);
+    VD->setInvalidDecl();
+    return;
+  }
+
   QualType Ty = VD->getType();
   if (Ty->isDependentType()) return;
 
@@ -4779,7 +4830,7 @@ void Sema::ActOnInitializerError(Decl *D) {
 }
 
 void Sema::ActOnUninitializedDecl(Decl *RealDecl,
-                                  bool TypeContainsUndeducedAuto) {
+                                  bool TypeMayContainAuto) {
   // If there is no declaration, there was an error parsing it. Just ignore it.
   if (RealDecl == 0)
     return;
@@ -4788,7 +4839,9 @@ void Sema::ActOnUninitializedDecl(Decl *RealDecl,
     QualType Type = Var->getType();
 
     // C++0x [dcl.spec.auto]p3
-    if (TypeContainsUndeducedAuto) {
+    if (TypeMayContainAuto && Type->getContainedAutoType()) {
+      Var->setParsingAutoInit(false);
+
       Diag(Var->getLocation(), diag::err_auto_var_requires_init)
         << Var->getDeclName() << Type;
       Var->setInvalidDecl();
@@ -4999,6 +5052,41 @@ Sema::FinalizeDeclaratorGroup(Scope *S, const DeclSpec &DS,
   if (DS.isTypeSpecOwned())
     Decls.push_back(DS.getRepAsDecl());
 
+  // C++0x [dcl.spec.auto]p7:
+  //   If the type deduced for the template parameter U is not the same in each
+  //   deduction, the program is ill-formed.
+  // FIXME: When initializer-list support is added, a distinction is needed
+  // between the deduced type U and the deduced type which 'auto' stands for.
+  //   auto a = 0, b = { 1, 2, 3 };
+  // is legal because the deduced type U is 'int' in both cases.
+  bool TypeContainsAuto = DS.getTypeSpecType() == DeclSpec::TST_auto;
+  if (TypeContainsAuto && NumDecls > 1) {
+    QualType Deduced;
+    CanQualType DeducedCanon;
+    VarDecl *DeducedDecl = 0;
+    for (unsigned i = 0; i != NumDecls; ++i) {
+      if (VarDecl *D = dyn_cast<VarDecl>(Group[i])) {
+        AutoType *AT = D->getType()->getContainedAutoType();
+        if (AT && AT->isDeduced()) {
+          QualType U = AT->getDeducedType();
+          CanQualType UCanon = Context.getCanonicalType(U);
+          if (Deduced.isNull()) {
+            Deduced = U;
+            DeducedCanon = UCanon;
+            DeducedDecl = D;
+          } else if (DeducedCanon != UCanon) {
+            Diag(DS.getTypeSpecTypeLoc(), diag::err_auto_different_deductions)
+              << Deduced << DeducedDecl->getDeclName()
+              << U << D->getDeclName()
+              << DeducedDecl->getInit()->getSourceRange()
+              << D->getInit()->getSourceRange();
+            break;
+          }
+        }
+      }
+    }
+  }
+
   for (unsigned i = 0; i != NumDecls; ++i)
     if (Decl *D = Group[i])
       Decls.push_back(D);
diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp
index 2e6c4c8ace..e8abab8476 100644
--- a/lib/Sema/SemaDeclCXX.cpp
+++ b/lib/Sema/SemaDeclCXX.cpp
@@ -1073,7 +1073,8 @@ Sema::ActOnCXXMemberDeclarator(Scope *S, AccessSpecifier AS, Declarator &D,
   assert((Name || isInstField) && "No identifier for non-field ?");
 
   if (Init)
-    AddInitializerToDecl(Member, Init, false);
+    AddInitializerToDecl(Member, Init, false,
+                         DS.getTypeSpecType() == DeclSpec::TST_auto);
   if (Deleted) // FIXME: Source location is not very good.
     SetDeclDeleted(Member, D.getSourceRange().getBegin());
 
@@ -5953,7 +5954,8 @@ void Sema::FinalizeVarWithDestructor(VarDecl *VD, const RecordType *Record) {
 void Sema::AddCXXDirectInitializerToDecl(Decl *RealDecl,
                                          SourceLocation LParenLoc,
                                          MultiExprArg Exprs,
-                                         SourceLocation RParenLoc) {
+                                         SourceLocation RParenLoc,
+                                         bool TypeMayContainAuto) {
   assert(Exprs.size() != 0 && Exprs.get() && "missing expressions");
 
   // If there is no declaration, there was an error parsing it.  Just ignore
@@ -5968,6 +5970,37 @@ void Sema::AddCXXDirectInitializerToDecl(Decl *RealDecl,
     return;
   }
 
+  // C++0x [decl.spec.auto]p6. Deduce the type which 'auto' stands in for.
+  if (TypeMayContainAuto && VDecl->getType()->getContainedAutoType()) {
+    VDecl->setParsingAutoInit(false);
+
+    // FIXME: n3225 doesn't actually seem to indicate this is ill-formed
+    if (Exprs.size() > 1) {
+      Diag(Exprs.get()[1]->getSourceRange().getBegin(),
+           diag::err_auto_var_init_multiple_expressions)
+        << VDecl->getDeclName() << VDecl->getType()
+        << VDecl->getSourceRange();
+      RealDecl->setInvalidDecl();
+      return;
+    }
+
+    Expr *Init = Exprs.get()[0];
+    QualType DeducedType;
+    if (!DeduceAutoType(VDecl->getType(), Init, DeducedType)) {
+      Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure)
+        << VDecl->getDeclName() << VDecl->getType() << Init->getType()
+        << Init->getSourceRange();
+      RealDecl->setInvalidDecl();
+      return;
+    }
+    VDecl->setType(DeducedType);
+
+    // If this is a redeclaration, check that the type we just deduced matches
+    // the previously declared type.
+    if (VarDecl *Old = VDecl->getPreviousDeclaration())
+      MergeVarDeclTypes(VDecl, Old);
+  }
+
   // We will represent direct-initialization similarly to copy-initialization:
   //    int x(1);  -as-> int x = 1;
   //    ClassType x(a,b,c); -as-> ClassType x = ClassType(a,b,c);
diff --git a/lib/Sema/SemaExpr.cpp b/lib/Sema/SemaExpr.cpp
index df49ad5c9a..65b57c30cd 100644
--- a/lib/Sema/SemaExpr.cpp
+++ b/lib/Sema/SemaExpr.cpp
@@ -75,6 +75,15 @@ bool Sema::DiagnoseUseOfDecl(NamedDecl *D, SourceLocation Loc,
     }
   }
 
+  // See if this is an auto-typed variable whose initializer we are parsing.
+  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
+    if (VD->isParsingAutoInit()) {
+      Diag(Loc, diag::err_auto_variable_cannot_appear_in_own_initializer)
+        << D->getDeclName();
+      return true;
+    }
+  }
+
   // See if the decl is deprecated.
   if (const DeprecatedAttr *DA = D->getAttr<DeprecatedAttr>())
     EmitDeprecationWarning(D, DA->getMessage(), Loc, UnknownObjCClass);
@@ -964,13 +973,6 @@ ExprResult
 Sema::BuildDeclRefExpr(ValueDecl *D, QualType Ty, ExprValueKind VK,
                        const DeclarationNameInfo &NameInfo,
                        const CXXScopeSpec *SS) {
-  if (Ty == Context.UndeducedAutoTy) {
-    Diag(NameInfo.getLoc(),
-         diag::err_auto_variable_cannot_appear_in_own_initializer)
-      << D->getDeclName();
-    return ExprError();
-  }
-
   MarkDeclarationReferenced(NameInfo.getLoc(), D);
 
   Expr *E = DeclRefExpr::Create(Context,
@@ -9650,26 +9652,18 @@ ExprResult Sema::CheckPlaceholderExpr(Expr *E, SourceLocation Loc) {
   if (!BT || !BT->isPlaceholderType()) return Owned(E);
 
   // If this is overload, check for a single overload.
-  if (BT->getKind() == BuiltinType::Overload) {
-    if (FunctionDecl *Specialization
-          = ResolveSingleFunctionTemplateSpecialization(E)) {
-      // The access doesn't really matter in this case.
-      DeclAccessPair Found = DeclAccessPair::make(Specialization,
-                                                  Specialization->getAccess());
-      E = FixOverloadedFunctionReference(E, Found, Specialization);
-      if (!E) return ExprError();
-      return Owned(E);
-    }
-
-    Diag(Loc, diag::err_ovl_unresolvable) << E->getSourceRange();
-    return ExprError();
-  }
+  assert(BT->getKind() == BuiltinType::Overload);
 
-  // Otherwise it's a use of undeduced auto.
-  assert(BT->getKind() == BuiltinType::UndeducedAuto);
+  if (FunctionDecl *Specialization
+        = ResolveSingleFunctionTemplateSpecialization(E)) {
+    // The access doesn't really matter in this case.
+    DeclAccessPair Found = DeclAccessPair::make(Specialization,
+                                                Specialization->getAccess());
+    E = FixOverloadedFunctionReference(E, Found, Specialization);
+    if (!E) return ExprError();
+    return Owned(E);
+  }
 
-  DeclRefExpr *DRE = cast<DeclRefExpr>(E->IgnoreParens());
-  Diag(Loc, diag::err_auto_variable_cannot_appear_in_own_initializer)
-    << DRE->getDecl() << E->getSourceRange();
+  Diag(Loc, diag::err_ovl_unresolvable) << E->getSourceRange();
   return ExprError();
 }
diff --git a/lib/Sema/SemaExprCXX.cpp b/lib/Sema/SemaExprCXX.cpp
index 0d48741387..f9c2c9a62e 100644
--- a/lib/Sema/SemaExprCXX.cpp
+++ b/lib/Sema/SemaExprCXX.cpp
@@ -759,11 +759,16 @@ Sema::ActOnCXXNew(SourceLocation StartLoc, bool UseGlobal,
                   Declarator &D, SourceLocation ConstructorLParen,
                   MultiExprArg ConstructorArgs,
                   SourceLocation ConstructorRParen) {
+  bool TypeContainsAuto = D.getDeclSpec().getTypeSpecType() == DeclSpec::TST_auto;
+
   Expr *ArraySize = 0;
   // If the specified type is an array, unwrap it and save the expression.
   if (D.getNumTypeObjects() > 0 &&
       D.getTypeObject(0).Kind == DeclaratorChunk::Array) {
     DeclaratorChunk &Chunk = D.getTypeObject(0);
+    if (TypeContainsAuto)
+      return ExprError(Diag(Chunk.Loc, diag::err_new_array_of_auto)
+        << D.getSourceRange());
     if (Chunk.Arr.hasStatic)
       return ExprError(Diag(Chunk.Loc, diag::err_static_illegal_in_new)
         << D.getSourceRange());
@@ -793,14 +798,12 @@ Sema::ActOnCXXNew(SourceLocation StartLoc, bool UseGlobal,
     }
   }
 
-  TypeSourceInfo *TInfo = GetTypeForDeclarator(D, /*Scope=*/0);
+  TypeSourceInfo *TInfo = GetTypeForDeclarator(D, /*Scope=*/0, /*OwnedDecl=*/0,
+                                               /*AllowAuto=*/true);
   QualType AllocType = TInfo->getType();
   if (D.isInvalidType())
     return ExprError();
 
-  if (!TInfo)
-    TInfo = Context.getTrivialTypeSourceInfo(AllocType);
-
   return BuildCXXNew(StartLoc, UseGlobal,
                      PlacementLParen,
                      move(PlacementArgs),
@@ -811,7 +814,8 @@ Sema::ActOnCXXNew(SourceLocation StartLoc, bool UseGlobal,
                      ArraySize,
                      ConstructorLParen,
                      move(ConstructorArgs),
-                     ConstructorRParen);
+                     ConstructorRParen,
+                     TypeContainsAuto);
 }
 
 ExprResult
@@ -825,9 +829,33 @@ Sema::BuildCXXNew(SourceLocation StartLoc, bool UseGlobal,
                   Expr *ArraySize,
                   SourceLocation ConstructorLParen,
                   MultiExprArg ConstructorArgs,
-                  SourceLocation ConstructorRParen) {
+                  SourceLocation ConstructorRParen,
+                  bool TypeMayContainAuto) {
   SourceRange TypeRange = AllocTypeInfo->getTypeLoc().getSourceRange();
 
+  // C++0x [decl.spec.auto]p6. Deduce the type which 'auto' stands in for.
+  if (TypeMayContainAuto && AllocType->getContainedAutoType()) {
+    if (ConstructorArgs.size() == 0)
+      return ExprError(Diag(StartLoc, diag::err_auto_new_requires_ctor_arg)
+                       << AllocType << TypeRange);
+    if (ConstructorArgs.size() != 1) {
+      Expr *FirstBad = ConstructorArgs.get()[1];
+      return ExprError(Diag(FirstBad->getSourceRange().getBegin(),
+                            diag::err_auto_new_ctor_multiple_expressions)
+                       << AllocType << TypeRange);
+    }
+    QualType DeducedType;
+    if (!DeduceAutoType(AllocType, ConstructorArgs.get()[0], DeducedType))
+      return ExprError(Diag(StartLoc, diag::err_auto_new_deduction_failure)
+                       << AllocType
+                       << ConstructorArgs.get()[0]->getType()
+                       << TypeRange
+                       << ConstructorArgs.get()[0]->getSourceRange());
+
+    AllocType = DeducedType;
+    AllocTypeInfo = Context.getTrivialTypeSourceInfo(AllocType, StartLoc);
+  }
+  
   // Per C++0x [expr.new]p5, the type being constructed may be a
   // typedef of an array type.
   if (!ArraySize) {
diff --git a/lib/Sema/SemaTemplate.cpp b/lib/Sema/SemaTemplate.cpp
index 9a11c68e05..f0a0103205 100644
--- a/lib/Sema/SemaTemplate.cpp
+++ b/lib/Sema/SemaTemplate.cpp
@@ -2783,6 +2783,10 @@ bool UnnamedLocalNoLinkageFinder::VisitDecltypeType(const DecltypeType*) {
   return false;
 }
 
+bool UnnamedLocalNoLinkageFinder::VisitAutoType(const AutoType *T) {
+  return Visit(T->getDeducedType());
+}
+
 bool UnnamedLocalNoLinkageFinder::VisitRecordType(const RecordType* T) {
   return VisitTagDecl(T->getDecl());
 }
diff --git a/lib/Sema/SemaTemplateDeduction.cpp b/lib/Sema/SemaTemplateDeduction.cpp
index fceeaa7fdd..bd0a618283 100644
--- a/lib/Sema/SemaTemplateDeduction.cpp
+++ b/lib/Sema/SemaTemplateDeduction.cpp
@@ -22,6 +22,7 @@
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "llvm/ADT/BitVector.h"
+#include "TreeTransform.h"
 #include <algorithm>
 
 namespace clang {
@@ -2445,21 +2446,22 @@ static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
     ParamType = ParamType.getLocalUnqualifiedType();
   const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
   if (ParamRefType) {
+    QualType PointeeType = ParamRefType->getPointeeType();
+
     //   [C++0x] 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 (const RValueReferenceType *RValueRef
-                                   = dyn_cast<RValueReferenceType>(ParamType)) {
-      if (!RValueRef->getPointeeType().getQualifiers() &&
-          isa<TemplateTypeParmType>(RValueRef->getPointeeType()) &&
+    if (isa<RValueReferenceType>(ParamType)) {
+      if (!PointeeType.getQualifiers() &&
+          isa<TemplateTypeParmType>(PointeeType) &&
           Arg->Classify(S.Context).isLValue())
         ArgType = S.Context.getLValueReferenceType(ArgType);
     }
 
     //   [...] If P is a reference type, the type referred to by P is used
     //   for type deduction.
-    ParamType = ParamRefType->getPointeeType();
+    ParamType = PointeeType;
   }
 
   // Overload sets usually make this parameter an undeduced
@@ -2946,6 +2948,95 @@ Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
                                  QualType(), Specialization, Info);
 }
 
+namespace {
+  /// Substitute the 'auto' type specifier within a type for a given replacement
+  /// type.
+  class SubstituteAutoTransform :
+    public TreeTransform<SubstituteAutoTransform> {
+    QualType Replacement;
+  public:
+    SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) :
+      TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) {
+    }
+    QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
+      // If we're building the type pattern to deduce against, don't wrap the
+      // substituted type in an AutoType. Certain template deduction rules
+      // apply only when a template type parameter appears directly (and not if
+      // the parameter is found through desugaring). For instance:
+      //   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 (isa<TemplateTypeParmType>(Replacement)) {
+        QualType Result = Replacement;
+        TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
+        NewTL.setNameLoc(TL.getNameLoc());
+        return Result;
+      } else {
+        QualType Result = RebuildAutoType(Replacement);
+        AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
+        NewTL.setNameLoc(TL.getNameLoc());
+        return Result;
+      }
+    }
+  };
+}
+
+/// \brief Deduce the type for an auto type-specifier (C++0x [dcl.spec.auto]p6)
+///
+/// \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. This may still contain undeduced autos if the type is
+/// dependent.
+///
+/// \returns true if deduction succeeded, false if it failed.
+bool
+Sema::DeduceAutoType(QualType Type, Expr *Init, QualType &Result) {
+  if (Init->isTypeDependent()) {
+    Result = Type;
+    return true;
+  }
+
+  SourceLocation Loc = Init->getExprLoc();
+
+  LocalInstantiationScope InstScope(*this);
+
+  // Build template<class TemplParam> void Func(FuncParam);
+  NamedDecl *TemplParam
+    = TemplateTypeParmDecl::Create(Context, 0, Loc, 0, 0, 0, false, false);
+  TemplateParameterList *TemplateParams
+    = TemplateParameterList::Create(Context, Loc, Loc, &TemplParam, 1, Loc);
+
+  QualType TemplArg = Context.getTemplateTypeParmType(0, 0, false);
+  QualType FuncParam =
+    SubstituteAutoTransform(*this, TemplArg).TransformType(Type);
+
+  // Deduce type of TemplParam in Func(Init)
+  llvm::SmallVector<DeducedTemplateArgument, 1> Deduced;
+  Deduced.resize(1);
+  QualType InitType = Init->getType();
+  unsigned TDF = 0;
+  if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
+                                                FuncParam, InitType, Init,
+                                                TDF))
+    return false;
+
+  TemplateDeductionInfo Info(Context, Loc);
+  if (::DeduceTemplateArguments(*this, TemplateParams,
+                                FuncParam, InitType, Info, Deduced,
+                                TDF))
+    return false;
+
+  QualType DeducedType = Deduced[0].getAsType();
+  if (DeducedType.isNull())
+    return false;
+
+  Result = SubstituteAutoTransform(*this, DeducedType).TransformType(Type);
+  return true;
+}
+
 static void
 MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
                            bool OnlyDeduced,
@@ -3740,6 +3831,11 @@ MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
                                OnlyDeduced, Depth, Used);
     break;
 
+  case Type::Auto:
+    MarkUsedTemplateParameters(SemaRef,
+                               cast<AutoType>(T)->getDeducedType(),
+                               OnlyDeduced, Depth, Used);
+
   // None of these types have any template parameters in them.
   case Type::Builtin:
   case Type::VariableArray:
diff --git a/lib/Sema/SemaTemplateInstantiateDecl.cpp b/lib/Sema/SemaTemplateInstantiateDecl.cpp
index ecb9019136..c0150c07bb 100644
--- a/lib/Sema/SemaTemplateInstantiateDecl.cpp
+++ b/lib/Sema/SemaTemplateInstantiateDecl.cpp
@@ -324,19 +324,21 @@ Decl *TemplateDeclInstantiator::VisitVarDecl(VarDecl *D) {
     ASTOwningVector<Expr*> InitArgs(SemaRef);
     if (!InstantiateInitializer(SemaRef, D->getInit(), TemplateArgs, LParenLoc,
                                 InitArgs, RParenLoc)) {
+      bool TypeMayContainAuto = true;
       // Attach the initializer to the declaration, if we have one.
       if (InitArgs.size() == 0)
-        SemaRef.ActOnUninitializedDecl(Var, false);    
+        SemaRef.ActOnUninitializedDecl(Var, TypeMayContainAuto);
       else if (D->hasCXXDirectInitializer()) {
         // Add the direct initializer to the declaration.
         SemaRef.AddCXXDirectInitializerToDecl(Var,
                                               LParenLoc,
                                               move_arg(InitArgs),
-                                              RParenLoc);
+                                              RParenLoc,
+                                              TypeMayContainAuto);
       } else {
         assert(InitArgs.size() == 1);
         Expr *Init = InitArgs.take()[0];
-        SemaRef.AddInitializerToDecl(Var, Init, false);
+        SemaRef.AddInitializerToDecl(Var, Init, false, TypeMayContainAuto);
       }
     } else {
       // FIXME: Not too happy about invalidating the declaration
diff --git a/lib/Sema/SemaType.cpp b/lib/Sema/SemaType.cpp
index e69f9dd176..c88baa540f 100644
--- a/lib/Sema/SemaType.cpp
+++ b/lib/Sema/SemaType.cpp
@@ -791,7 +791,7 @@ static QualType ConvertDeclSpecToType(Sema &S, TypeProcessingState &state) {
   }
   case DeclSpec::TST_auto: {
     // TypeQuals handled by caller.
-    Result = Context.UndeducedAutoTy;
+    Result = Context.getAutoType(QualType());
     break;
   }
 
@@ -1091,9 +1091,9 @@ QualType Sema::BuildArrayType(QualType T, ArrayType::ArraySizeModifier ASM,
     return QualType();
   }
 
-  if (Context.getCanonicalType(T) == Context.UndeducedAutoTy) {
-    Diag(Loc,  diag::err_illegal_decl_array_of_auto)
-      << getPrintableNameForEntity(Entity);
+  if (T->getContainedAutoType()) {
+    Diag(Loc, diag::err_illegal_decl_array_of_auto)
+      << getPrintableNameForEntity(Entity) << T;
     return QualType();
   }
 
@@ -1405,7 +1405,8 @@ QualType Sema::GetTypeFromParser(ParsedType Ty, TypeSourceInfo **TInfo) {
 /// The result of this call will never be null, but the associated
 /// type may be a null type if there's an unrecoverable error.
 TypeSourceInfo *Sema::GetTypeForDeclarator(Declarator &D, Scope *S,
-                                           TagDecl **OwnedDecl) {
+                                           TagDecl **OwnedDecl,
+                                           bool AutoAllowedInTypeName) {
   // Determine the type of the declarator. Not all forms of declarator
   // have a type.
   QualType T;
@@ -1449,33 +1450,8 @@ TypeSourceInfo *Sema::GetTypeForDeclarator(Declarator &D, Scope *S,
   if (D.getAttributes())
     distributeTypeAttrsFromDeclarator(state, T);
 
-  // Check for auto functions and trailing return type and adjust the
-  // return type accordingly.
-  if (getLangOptions().CPlusPlus0x && D.isFunctionDeclarator()) {
-    const DeclaratorChunk::FunctionTypeInfo &FTI = D.getFunctionTypeInfo();
-    if (T == Context.UndeducedAutoTy) {
-      if (FTI.TrailingReturnType) {
-          T = GetTypeFromParser(ParsedType::getFromOpaquePtr(FTI.TrailingReturnType),
-                                &ReturnTypeInfo);
-      }
-      else {
-          Diag(D.getDeclSpec().getTypeSpecTypeLoc(),
-               diag::err_auto_missing_trailing_return);
-          T = Context.IntTy;
-          D.setInvalidType(true);
-      }
-    }
-    else if (FTI.TrailingReturnType) {
-      Diag(D.getDeclSpec().getTypeSpecTypeLoc(),
-           diag::err_trailing_return_without_auto);
-      D.setInvalidType(true);
-    }
-  }
-
-  if (T.isNull())
-    return Context.getNullTypeSourceInfo();
-
-  if (T == Context.UndeducedAutoTy) {
+  if (D.getDeclSpec().getTypeSpecType() == DeclSpec::TST_auto &&
+      !D.isFunctionDeclarator()) {
     int Error = -1;
 
     switch (D.getContext()) {
@@ -1500,14 +1476,19 @@ TypeSourceInfo *Sema::GetTypeForDeclarator(Declarator &D, Scope *S,
       Error = 5; // Template parameter
       break;
     case Declarator::BlockLiteralContext:
-      Error = 6;  // Block literal
+      Error = 6; // Block literal
+      break;
+    case Declarator::TemplateTypeArgContext:
+      Error = 7; // Template type argument
+      break;
+    case Declarator::TypeNameContext:
+      if (!AutoAllowedInTypeName)
+        Error = 8; // Generic
       break;
     case Declarator::FileContext:
     case Declarator::BlockContext:
     case Declarator::ForContext:
     case Declarator::ConditionContext:
-    case Declarator::TypeNameContext:
-    case Declarator::TemplateTypeArgContext:
       break;
     }
 
@@ -1519,6 +1500,9 @@ TypeSourceInfo *Sema::GetTypeForDeclarator(Declarator &D, Scope *S,
     }
   }
 
+  if (T.isNull())
+    return Context.getNullTypeSourceInfo();
+
   // The name we're declaring, if any.
   DeclarationName Name;
   if (D.getIdentifier())
@@ -1631,6 +1615,32 @@ TypeSourceInfo *Sema::GetTypeForDeclarator(Declarator &D, Scope *S,
         D.setInvalidType(true);
       }
 
+      // Check for auto functions and trailing return type and adjust the
+      // return type accordingly.
+      if (!D.isInvalidType()) {
+        // trailing-return-type is only required if we're declaring a function,
+        // and not, for instance, a pointer to a function.
+        if (D.getDeclSpec().getTypeSpecType() == DeclSpec::TST_auto &&
+            !FTI.TrailingReturnType && chunkIndex == 0) {
+          Diag(D.getDeclSpec().getTypeSpecTypeLoc(),
+               diag::err_auto_missing_trailing_return);
+          T = Context.IntTy;
+          D.setInvalidType(true);
+        } else if (FTI.TrailingReturnType) {
+          if (T.hasQualifiers() || !isa<AutoType>(T)) {
+            // T must be exactly 'auto' at this point. See CWG issue 681.
+            Diag(D.getDeclSpec().getTypeSpecTypeLoc(),
+                 diag::err_trailing_return_without_auto)
+              << T << D.getDeclSpec().getSourceRange();
+            D.setInvalidType(true);
+          }
+
+          T = GetTypeFromParser(
+            ParsedType::getFromOpaquePtr(FTI.TrailingReturnType),
+            &ReturnTypeInfo);
+        }
+      }
+
       // cv-qualifiers on return types are pointless except when the type is a
       // class type in C++.
       if (T.getCVRQualifiers() && D.getDeclSpec().getTypeQualifiers() &&
diff --git a/lib/Sema/TreeTransform.h b/lib/Sema/TreeTr