[c++20] P1064R0: Allow virtual function calls in constant expression

evaluation.

This reinstates r360559, reverted in r360580, with a fix to avoid
crashing if evaluation-for-overflow mode encounters a virtual call on an
object of a class with a virtual base class, and to generally not try to
resolve virtual function calls to objects whose (notional) vptrs are not
readable. (The standard rules are unclear here, but this seems like a
reasonable approach.)

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

4 files changed, 265 insertions, 40 deletions

diff --git a/lib/AST/DeclCXX.cpp b/lib/AST/DeclCXX.cpp
index b9ecdc6572..f9f70ecb59 100644
--- a/lib/AST/DeclCXX.cpp
+++ b/lib/AST/DeclCXX.cpp
@@ -1946,8 +1946,8 @@ static bool recursivelyOverrides(const CXXMethodDecl *DerivedMD,
 }
 
 CXXMethodDecl *
-CXXMethodDecl::getCorrespondingMethodInClass(const CXXRecordDecl *RD,
-                                             bool MayBeBase) {
+CXXMethodDecl::getCorrespondingMethodDeclaredInClass(const CXXRecordDecl *RD,
+                                                     bool MayBeBase) {
   if (this->getParent()->getCanonicalDecl() == RD->getCanonicalDecl())
     return this;
 
@@ -1973,6 +1973,15 @@ CXXMethodDecl::getCorrespondingMethodInClass(const CXXRecordDecl *RD,
       return MD;
   }
 
+  return nullptr;
+}
+
+CXXMethodDecl *
+CXXMethodDecl::getCorrespondingMethodInClass(const CXXRecordDecl *RD,
+                                             bool MayBeBase) {
+  if (auto *MD = getCorrespondingMethodDeclaredInClass(RD, MayBeBase))
+    return MD;
+
   for (const auto &I : RD->bases()) {
     const RecordType *RT = I.getType()->getAs<RecordType>();
     if (!RT)
diff --git a/lib/AST/ExprConstant.cpp b/lib/AST/ExprConstant.cpp
index ea36072bd9..2c4cad1fff 100644
--- a/lib/AST/ExprConstant.cpp
+++ b/lib/AST/ExprConstant.cpp
@@ -37,6 +37,7 @@
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/ASTLambda.h"
 #include "clang/AST/CharUnits.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/OSLog.h"
 #include "clang/AST/RecordLayout.h"
@@ -2485,6 +2486,21 @@ static bool HandleLValueBasePath(EvalInfo &Info, const CastExpr *E,
   return true;
 }
 
+/// Cast an lvalue referring to a derived class to a known base subobject.
+static bool CastToBaseClass(EvalInfo &Info, const Expr *E, LValue &Result,
+                            const CXXRecordDecl *DerivedRD,
+                            const CXXRecordDecl *BaseRD) {
+  CXXBasePaths Paths(/*FindAmbiguities=*/false,
+                     /*RecordPaths=*/true, /*DetectVirtual=*/false);
+  if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
+    llvm_unreachable("Class must be derived from the passed in base class!");
+
+  for (CXXBasePathElement &Elem : Paths.front())
+    if (!HandleLValueBase(Info, E, Result, Elem.Class, Elem.Base))
+      return false;
+  return true;
+}
+
 /// Update LVal to refer to the given field, which must be a member of the type
 /// currently described by LVal.
 static bool HandleLValueMember(EvalInfo &Info, const Expr *E, LValue &LVal,
@@ -4461,16 +4477,19 @@ static bool CheckConstexprFunction(EvalInfo &Info, SourceLocation CallLoc,
   }
 
   // DR1872: An instantiated virtual constexpr function can't be called in a
-  // constant expression.
-  if (isa<CXXMethodDecl>(Declaration) &&
-      cast<CXXMethodDecl>(Declaration)->isVirtual()) {
-    Info.FFDiag(CallLoc, diag::note_constexpr_virtual_call);
+  // constant expression (prior to C++20). We can still constant-fold such a
+  // call.
+  if (!Info.Ctx.getLangOpts().CPlusPlus2a && isa<CXXMethodDecl>(Declaration) &&
+      cast<CXXMethodDecl>(Declaration)->isVirtual())
+    Info.CCEDiag(CallLoc, diag::note_constexpr_virtual_call);
+
+  if (Definition && Definition->isInvalidDecl()) {
+    Info.FFDiag(CallLoc, diag::note_invalid_subexpr_in_const_expr);
     return false;
   }
 
   // Can we evaluate this function call?
-  if (Definition && Definition->isConstexpr() &&
-      !Definition->isInvalidDecl() && Body)
+  if (Definition && Definition->isConstexpr() && Body)
     return true;
 
   if (Info.getLangOpts().CPlusPlus11) {
@@ -4517,7 +4536,7 @@ const AccessKinds CheckMemberCallThisPointerHandler::AccessKind;
 /// Check that the pointee of the 'this' pointer in a member function call is
 /// either within its lifetime or in its period of construction or destruction.
 static bool checkMemberCallThisPointer(EvalInfo &Info, const Expr *E,
-                                       const LValue &This) {
+                                       const LValue &This, bool IsVirtual) {
   if (This.Designator.Invalid)
     return false;
 
@@ -4538,6 +4557,16 @@ static bool checkMemberCallThisPointer(EvalInfo &Info, const Expr *E,
                          : diag::note_constexpr_access_unsized_array)
           << AK_MemberCall;
       return false;
+    } else if (IsVirtual) {
+      // Conservatively refuse to perform a virtual function call if we would
+      // not be able to read a notional 'vptr' value.
+      APValue Val;
+      This.moveInto(Val);
+      QualType StarThisType =
+          Info.Ctx.getLValueReferenceType(This.Designator.getType(Info.Ctx));
+      Info.FFDiag(E, diag::note_constexpr_virtual_out_of_lifetime)
+          << Val.getAsString(Info.Ctx, StarThisType);
+      return false;
     }
     return true;
   }
@@ -4546,6 +4575,155 @@ static bool checkMemberCallThisPointer(EvalInfo &Info, const Expr *E,
   return Obj && findSubobject(Info, E, Obj, This.Designator, Handler);
 }
 
+struct DynamicType {
+  /// The dynamic class type of the object.
+  const CXXRecordDecl *Type;
+  /// The corresponding path length in the lvalue.
+  unsigned PathLength;
+};
+
+static const CXXRecordDecl *getBaseClassType(SubobjectDesignator &Designator,
+                                             unsigned PathLength) {
+  assert(PathLength >= Designator.MostDerivedPathLength && PathLength <=
+      Designator.Entries.size() && "invalid path length");
+  return (PathLength == Designator.MostDerivedPathLength)
+             ? Designator.MostDerivedType->getAsCXXRecordDecl()
+             : getAsBaseClass(Designator.Entries[PathLength - 1]);
+}
+
+/// Determine the dynamic type of an object.
+static Optional<DynamicType> ComputeDynamicType(EvalInfo &Info, LValue &This) {
+  // If we don't have an lvalue denoting an object of class type, there is no
+  // meaningful dynamic type. (We consider objects of non-class type to have no
+  // dynamic type.)
+  if (This.Designator.IsOnePastTheEnd || This.Designator.Invalid ||
+      !This.Designator.MostDerivedType->getAsCXXRecordDecl())
+    return None;
+
+  // FIXME: For very deep class hierarchies, it might be beneficial to use a
+  // binary search here instead. But the overwhelmingly common case is that
+  // we're not in the middle of a constructor, so it probably doesn't matter
+  // in practice.
+  ArrayRef<APValue::LValuePathEntry> Path = This.Designator.Entries;
+  for (unsigned PathLength = This.Designator.MostDerivedPathLength;
+       PathLength <= Path.size(); ++PathLength) {
+    switch (Info.isEvaluatingConstructor(This.getLValueBase(),
+                                         Path.slice(0, PathLength))) {
+    case ConstructionPhase::Bases:
+      // We're constructing a base class. This is not the dynamic type.
+      break;
+
+    case ConstructionPhase::None:
+    case ConstructionPhase::AfterBases:
+      // We've finished constructing the base classes, so this is the dynamic
+      // type.
+      return DynamicType{getBaseClassType(This.Designator, PathLength),
+                         PathLength};
+    }
+  }
+
+  // CWG issue 1517: we're constructing a base class of the object described by
+  // 'This', so that object has not yet begun its period of construction and
+  // any polymorphic operation on it results in undefined behavior.
+  return None;
+}
+
+/// Perform virtual dispatch.
+static const CXXMethodDecl *HandleVirtualDispatch(
+    EvalInfo &Info, const Expr *E, LValue &This, const CXXMethodDecl *Found,
+    llvm::SmallVectorImpl<QualType> &CovariantAdjustmentPath) {
+  Optional<DynamicType> DynType = ComputeDynamicType(Info, This);
+  if (!DynType) {
+    Info.FFDiag(E);
+    return nullptr;
+  }
+
+  // Find the final overrider. It must be declared in one of the classes on the
+  // path from the dynamic type to the static type.
+  // FIXME: If we ever allow literal types to have virtual base classes, that
+  // won't be true.
+  const CXXMethodDecl *Callee = Found;
+  unsigned PathLength = DynType->PathLength;
+  for (/**/; PathLength <= This.Designator.Entries.size(); ++PathLength) {
+    const CXXRecordDecl *Class = getBaseClassType(This.Designator, PathLength);
+    if (Class->getNumVBases()) {
+      Info.FFDiag(E);
+      return nullptr;
+    }
+
+    const CXXMethodDecl *Overrider =
+        Found->getCorrespondingMethodDeclaredInClass(Class, false);
+    if (Overrider) {
+      Callee = Overrider;
+      break;
+    }
+  }
+
+  // C++2a [class.abstract]p6:
+  //   the effect of making a virtual call to a pure virtual function [...] is
+  //   undefined
+  if (Callee->isPure()) {
+    Info.FFDiag(E, diag::note_constexpr_pure_virtual_call, 1) << Callee;
+    Info.Note(Callee->getLocation(), diag::note_declared_at);
+    return nullptr;
+  }
+
+  // If necessary, walk the rest of the path to determine the sequence of
+  // covariant adjustment steps to apply.
+  if (!Info.Ctx.hasSameUnqualifiedType(Callee->getReturnType(),
+                                       Found->getReturnType())) {
+    CovariantAdjustmentPath.push_back(Callee->getReturnType());
+    for (unsigned CovariantPathLength = PathLength + 1;
+         CovariantPathLength != This.Designator.Entries.size();
+         ++CovariantPathLength) {
+      const CXXRecordDecl *NextClass =
+          getBaseClassType(This.Designator, CovariantPathLength);
+      const CXXMethodDecl *Next =
+          Found->getCorrespondingMethodDeclaredInClass(NextClass, false);
+      if (Next && !Info.Ctx.hasSameUnqualifiedType(
+                      Next->getReturnType(), CovariantAdjustmentPath.back()))
+        CovariantAdjustmentPath.push_back(Next->getReturnType());
+    }
+    if (!Info.Ctx.hasSameUnqualifiedType(Found->getReturnType(),
+                                         CovariantAdjustmentPath.back()))
+      CovariantAdjustmentPath.push_back(Found->getReturnType());
+  }
+
+  // Perform 'this' adjustment.
+  if (!CastToDerivedClass(Info, E, This, Callee->getParent(), PathLength))
+    return nullptr;
+
+  return Callee;
+}
+
+/// Perform the adjustment from a value returned by a virtual function to
+/// a value of the statically expected type, which may be a pointer or
+/// reference to a base class of the returned type.
+static bool HandleCovariantReturnAdjustment(EvalInfo &Info, const Expr *E,
+                                            APValue &Result,
+                                            ArrayRef<QualType> Path) {
+  assert(Result.isLValue() &&
+         "unexpected kind of APValue for covariant return");
+  if (Result.isNullPointer())
+    return true;
+
+  LValue LVal;
+  LVal.setFrom(Info.Ctx, Result);
+
+  const CXXRecordDecl *OldClass = Path[0]->getPointeeCXXRecordDecl();
+  for (unsigned I = 1; I != Path.size(); ++I) {
+    const CXXRecordDecl *NewClass = Path[I]->getPointeeCXXRecordDecl();
+    assert(OldClass && NewClass && "unexpected kind of covariant return");
+    if (OldClass != NewClass &&
+        !CastToBaseClass(Info, E, LVal, OldClass, NewClass))
+      return false;
+    OldClass = NewClass;
+  }
+
+  LVal.moveInto(Result);
+  return true;
+}
+
 /// Determine if a class has any fields that might need to be copied by a
 /// trivial copy or move operation.
 static bool hasFields(const CXXRecordDecl *RD) {
@@ -4735,11 +4913,6 @@ static bool HandleConstructorCall(const Expr *E, const LValue &This,
                                   BaseType->getAsCXXRecordDecl(), &Layout))
         return false;
       Value = &Result.getStructBase(BasesSeen++);
-
-      // This is the point at which the dynamic type of the object becomes this
-      // class type.
-      if (BasesSeen == RD->getNumBases())
-        EvalObj.finishedConstructingBases();
     } else if ((FD = I->getMember())) {
       if (!HandleLValueMember(Info, I->getInit(), Subobject, FD, &Layout))
         return false;
@@ -4800,6 +4973,11 @@ static bool HandleConstructorCall(const Expr *E, const LValue &This,
         return false;
       Success = false;
     }
+
+    // This is the point at which the dynamic type of the object becomes this
+    // class type.
+    if (I->isBaseInitializer() && BasesSeen == RD->getNumBases())
+      EvalObj.finishedConstructingBases();
   }
 
   return Success &&
@@ -5040,27 +5218,30 @@ public:
     const FunctionDecl *FD = nullptr;
     LValue *This = nullptr, ThisVal;
     auto Args = llvm::makeArrayRef(E->getArgs(), E->getNumArgs());
+    bool HasQualifier = false;
 
     // Extract function decl and 'this' pointer from the callee.
     if (CalleeType->isSpecificBuiltinType(BuiltinType::BoundMember)) {
-      const ValueDecl *Member = nullptr;
+      const CXXMethodDecl *Member = nullptr;
       if (const MemberExpr *ME = dyn_cast<MemberExpr>(Callee)) {
         // Explicit bound member calls, such as x.f() or p->g();
         if (!EvaluateObjectArgument(Info, ME->getBase(), ThisVal))
           return false;
-        Member = ME->getMemberDecl();
+        Member = dyn_cast<CXXMethodDecl>(ME->getMemberDecl());
+        if (!Member)
+          return Error(Callee);
         This = &ThisVal;
+        HasQualifier = ME->hasQualifier();
       } else if (const BinaryOperator *BE = dyn_cast<BinaryOperator>(Callee)) {
         // Indirect bound member calls ('.*' or '->*').
-        Member = HandleMemberPointerAccess(Info, BE, ThisVal, false);
-        if (!Member) return false;
+        Member = dyn_cast_or_null<CXXMethodDecl>(
+            HandleMemberPointerAccess(Info, BE, ThisVal, false));
+        if (!Member)
+          return Error(Callee);
         This = &ThisVal;
       } else
         return Error(Callee);
-
-      FD = dyn_cast<FunctionDecl>(Member);
-      if (!FD)
-        return Error(Callee);
+      FD = Member;
     } else if (CalleeType->isFunctionPointerType()) {
       LValue Call;
       if (!EvaluatePointer(Callee, Call, Info))
@@ -5130,8 +5311,20 @@ public:
     } else
       return Error(E);
 
-    if (This && !checkMemberCallThisPointer(Info, E, *This))
-      return false;
+    SmallVector<QualType, 4> CovariantAdjustmentPath;
+    if (This) {
+      auto *NamedMember = dyn_cast<CXXMethodDecl>(FD);
+      bool IsVirtual = NamedMember && NamedMember->isVirtual() && !HasQualifier;
+
+      // Check that the 'this' pointer points to an object of the right type.
+      if (!checkMemberCallThisPointer(Info, E, *This, IsVirtual))
+        return false;
+
+      // Perform virtual dispatch, if necessary.
+      if (IsVirtual && !(FD = HandleVirtualDispatch(Info, E, *This, NamedMember,
+                                                    CovariantAdjustmentPath)))
+        return true;
+    }
 
     const FunctionDecl *Definition = nullptr;
     Stmt *Body = FD->getBody(Definition);
@@ -5141,6 +5334,11 @@ public:
                             Result, ResultSlot))
       return false;
 
+    if (!CovariantAdjustmentPath.empty() &&
+        !HandleCovariantReturnAdjustment(Info, E, Result,
+                                         CovariantAdjustmentPath))
+      return false;
+
     return true;
   }
 
diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp
index afd50f1438..1da2ca8ca5 100644
--- a/lib/Sema/SemaDeclCXX.cpp
+++ b/lib/Sema/SemaDeclCXX.cpp
@@ -1596,6 +1596,9 @@ bool Sema::CheckConstexprFunctionDecl(const FunctionDecl *NewFD) {
     //  The definition of a constexpr constructor shall satisfy the following
     //  constraints:
     //  - the class shall not have any virtual base classes;
+    //
+    // FIXME: This only applies to constructors, not arbitrary member
+    // functions.
     const CXXRecordDecl *RD = MD->getParent();
     if (RD->getNumVBases()) {
       Diag(NewFD->getLocation(), diag::err_constexpr_virtual_base)
@@ -1612,21 +1615,25 @@ bool Sema::CheckConstexprFunctionDecl(const FunctionDecl *NewFD) {
     // C++11 [dcl.constexpr]p3:
     //  The definition of a constexpr function shall satisfy the following
     //  constraints:
-    // - it shall not be virtual;
+    // - it shall not be virtual; (removed in C++20)
     const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(NewFD);
     if (Method && Method->isVirtual()) {
-      Method = Method->getCanonicalDecl();
-      Diag(Method->getLocation(), diag::err_constexpr_virtual);
-
-      // If it's not obvious why this function is virtual, find an overridden
-      // function which uses the 'virtual' keyword.
-      const CXXMethodDecl *WrittenVirtual = Method;
-      while (!WrittenVirtual->isVirtualAsWritten())
-        WrittenVirtual = *WrittenVirtual->begin_overridden_methods();
-      if (WrittenVirtual != Method)
-        Diag(WrittenVirtual->getLocation(),
-             diag::note_overridden_virtual_function);
-      return false;
+      if (getLangOpts().CPlusPlus2a) {
+        Diag(Method->getLocation(), diag::warn_cxx17_compat_constexpr_virtual);
+      } else {
+        Method = Method->getCanonicalDecl();
+        Diag(Method->getLocation(), diag::err_constexpr_virtual);
+
+        // If it's not obvious why this function is virtual, find an overridden
+        // function which uses the 'virtual' keyword.
+        const CXXMethodDecl *WrittenVirtual = Method;
+        while (!WrittenVirtual->isVirtualAsWritten())
+          WrittenVirtual = *WrittenVirtual->begin_overridden_methods();
+        if (WrittenVirtual != Method)
+          Diag(WrittenVirtual->getLocation(),
+               diag::note_overridden_virtual_function);
+        return false;
+      }
     }
 
     // - its return type shall be a literal type;
@@ -15197,7 +15204,8 @@ void Sema::MarkVirtualMemberExceptionSpecsNeeded(SourceLocation Loc,
 }
 
 void Sema::MarkVirtualMembersReferenced(SourceLocation Loc,
-                                        const CXXRecordDecl *RD) {
+                                        const CXXRecordDecl *RD,
+                                        bool ConstexprOnly) {
   // Mark all functions which will appear in RD's vtable as used.
   CXXFinalOverriderMap FinalOverriders;
   RD->getFinalOverriders(FinalOverriders);
@@ -15212,7 +15220,7 @@ void Sema::MarkVirtualMembersReferenced(SourceLocation Loc,
 
       // C++ [basic.def.odr]p2:
       //   [...] A virtual member function is used if it is not pure. [...]
-      if (!Overrider->isPure())
+      if (!Overrider->isPure() && (!ConstexprOnly || Overrider->isConstexpr()))
         MarkFunctionReferenced(Loc, Overrider);
     }
   }
diff --git a/lib/Sema/SemaTemplateInstantiate.cpp b/lib/Sema/SemaTemplateInstantiate.cpp
index edc281cad6..55d1d94bd8 100644
--- a/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/lib/Sema/SemaTemplateInstantiate.cpp
@@ -2082,6 +2082,7 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
   LateInstantiatedAttrVec LateAttrs;
   Instantiator.enableLateAttributeInstantiation(&LateAttrs);
 
+  bool MightHaveConstexprVirtualFunctions = false;
   for (auto *Member : Pattern->decls()) {
     // Don't instantiate members not belonging in this semantic context.
     // e.g. for:
@@ -2128,6 +2129,10 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
           Instantiation->setInvalidDecl();
           break;
         }
+      } else if (CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(NewMember)) {
+        if (MD->isConstexpr() && !MD->getFriendObjectKind() &&
+            (MD->isVirtualAsWritten() || Instantiation->getNumBases()))
+          MightHaveConstexprVirtualFunctions = true;
       }
 
       if (NewMember->isInvalidDecl())
@@ -2220,9 +2225,14 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
     Consumer.HandleTagDeclDefinition(Instantiation);
 
     // Always emit the vtable for an explicit instantiation definition
-    // of a polymorphic class template specialization.
+    // of a polymorphic class template specialization. Otherwise, eagerly
+    // instantiate only constexpr virtual functions in preparation for their use
+    // in constant evaluation.
     if (TSK == TSK_ExplicitInstantiationDefinition)
       MarkVTableUsed(PointOfInstantiation, Instantiation, true);
+    else if (MightHaveConstexprVirtualFunctions)
+      MarkVirtualMembersReferenced(PointOfInstantiation, Instantiation,
+                                   /*ConstexprOnly*/ true);
   }
 
   return Instantiation->isInvalidDecl();