ExprConstant.cpp

//===--- ExprConstant.cpp - Expression Constant Evaluator -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the Expr constant evaluator.
//
// Constant expression evaluation produces four main results:
//
//  * A success/failure flag indicating whether constant folding was successful.
//    This is the 'bool' return value used by most of the code in this file. A
//    'false' return value indicates that constant folding has failed, and any
//    appropriate diagnostic has already been produced.
//
//  * An evaluated result, valid only if constant folding has not failed.
//
//  * A flag indicating if evaluation encountered (unevaluated) side-effects.
//    These arise in cases such as (sideEffect(), 0) and (sideEffect() || 1),
//    where it is possible to determine the evaluated result regardless.
//
//  * A set of notes indicating why the evaluation was not a constant expression
//    (under the C++11 / C++1y rules only, at the moment), or, if folding failed
//    too, why the expression could not be folded.
//
// If we are checking for a potential constant expression, failure to constant
// fold a potential constant sub-expression will be indicated by a 'false'
// return value (the expression could not be folded) and no diagnostic (the
// expression is not necessarily non-constant).
//
//===----------------------------------------------------------------------===//

#include "clang/AST/APValue.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTDiagnostic.h"
#include "clang/AST/ASTLambda.h"
#include "clang/AST/CharUnits.h"
#include "clang/AST/Expr.h"
#include "clang/AST/RecordLayout.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/AST/TypeLoc.h"
#include "clang/Basic/Builtins.h"
#include "clang/Basic/TargetInfo.h"
#include "llvm/Support/raw_ostream.h"
#include <cstring>
#include <functional>

using namespace clang;
using llvm::APSInt;
using llvm::APFloat;

static bool IsGlobalLValue(APValue::LValueBase B);

namespace {
  struct LValue;
  struct CallStackFrame;
  struct EvalInfo;

  static QualType getType(APValue::LValueBase B) {
    if (!B) return QualType();
    if (const ValueDecl *D = B.dyn_cast<const ValueDecl*>())
      return D->getType();

    const Expr *Base = B.get<const Expr*>();

    // For a materialized temporary, the type of the temporary we materialized
    // may not be the type of the expression.
    if (const MaterializeTemporaryExpr *MTE =
            dyn_cast<MaterializeTemporaryExpr>(Base)) {
      SmallVector<const Expr *, 2> CommaLHSs;
      SmallVector<SubobjectAdjustment, 2> Adjustments;
      const Expr *Temp = MTE->GetTemporaryExpr();
      const Expr *Inner = Temp->skipRValueSubobjectAdjustments(CommaLHSs,
                                                               Adjustments);
      // Keep any cv-qualifiers from the reference if we generated a temporary
      // for it directly. Otherwise use the type after adjustment.
      if (!Adjustments.empty())
        return Inner->getType();
    }

    return Base->getType();
  }

  /// Get an LValue path entry, which is known to not be an array index, as a
  /// field or base class.
  static
  APValue::BaseOrMemberType getAsBaseOrMember(APValue::LValuePathEntry E) {
    APValue::BaseOrMemberType Value;
    Value.setFromOpaqueValue(E.BaseOrMember);
    return Value;
  }

  /// Get an LValue path entry, which is known to not be an array index, as a
  /// field declaration.
  static const FieldDecl *getAsField(APValue::LValuePathEntry E) {
    return dyn_cast<FieldDecl>(getAsBaseOrMember(E).getPointer());
  }
  /// Get an LValue path entry, which is known to not be an array index, as a
  /// base class declaration.
  static const CXXRecordDecl *getAsBaseClass(APValue::LValuePathEntry E) {
    return dyn_cast<CXXRecordDecl>(getAsBaseOrMember(E).getPointer());
  }
  /// Determine whether this LValue path entry for a base class names a virtual
  /// base class.
  static bool isVirtualBaseClass(APValue::LValuePathEntry E) {
    return getAsBaseOrMember(E).getInt();
  }

  /// Given a CallExpr, try to get the alloc_size attribute. May return null.
  static const AllocSizeAttr *getAllocSizeAttr(const CallExpr *CE) {
    const FunctionDecl *Callee = CE->getDirectCallee();
    return Callee ? Callee->getAttr<AllocSizeAttr>() : nullptr;
  }

  /// Attempts to unwrap a CallExpr (with an alloc_size attribute) from an Expr.
  /// This will look through a single cast.
  ///
  /// Returns null if we couldn't unwrap a function with alloc_size.
  static const CallExpr *tryUnwrapAllocSizeCall(const Expr *E) {
    if (!E->getType()->isPointerType())
      return nullptr;

    E = E->IgnoreParens();
    // If we're doing a variable assignment from e.g. malloc(N), there will
    // probably be a cast of some kind. Ignore it.
    if (const auto *Cast = dyn_cast<CastExpr>(E))
      E = Cast->getSubExpr()->IgnoreParens();

    if (const auto *CE = dyn_cast<CallExpr>(E))
      return getAllocSizeAttr(CE) ? CE : nullptr;
    return nullptr;
  }

  /// Determines whether or not the given Base contains a call to a function
  /// with the alloc_size attribute.
  static bool isBaseAnAllocSizeCall(APValue::LValueBase Base) {
    const auto *E = Base.dyn_cast<const Expr *>();
    return E && E->getType()->isPointerType() && tryUnwrapAllocSizeCall(E);
  }

  /// Determines if an LValue with the given LValueBase will have an unsized
  /// array in its designator.
  /// Find the path length and type of the most-derived subobject in the given
  /// path, and find the size of the containing array, if any.
  static unsigned
  findMostDerivedSubobject(ASTContext &Ctx, APValue::LValueBase Base,
                           ArrayRef<APValue::LValuePathEntry> Path,
                           uint64_t &ArraySize, QualType &Type, bool &IsArray) {
    // This only accepts LValueBases from APValues, and APValues don't support
    // arrays that lack size info.
    assert(!isBaseAnAllocSizeCall(Base) &&
           "Unsized arrays shouldn't appear here");
    unsigned MostDerivedLength = 0;
    Type = getType(Base);

    for (unsigned I = 0, N = Path.size(); I != N; ++I) {
      if (Type->isArrayType()) {
        const ConstantArrayType *CAT =
            cast<ConstantArrayType>(Ctx.getAsArrayType(Type));
        Type = CAT->getElementType();
        ArraySize = CAT->getSize().getZExtValue();
        MostDerivedLength = I + 1;
        IsArray = true;
      } else if (Type->isAnyComplexType()) {
        const ComplexType *CT = Type->castAs<ComplexType>();
        Type = CT->getElementType();
        ArraySize = 2;
        MostDerivedLength = I + 1;
        IsArray = true;
      } else if (const FieldDecl *FD = getAsField(Path[I])) {
        Type = FD->getType();
        ArraySize = 0;
        MostDerivedLength = I + 1;
        IsArray = false;
      } else {
        // Path[I] describes a base class.
        ArraySize = 0;
        IsArray = false;
      }
    }
    return MostDerivedLength;
  }

  // The order of this enum is important for diagnostics.
  enum CheckSubobjectKind {
    CSK_Base, CSK_Derived, CSK_Field, CSK_ArrayToPointer, CSK_ArrayIndex,
    CSK_This, CSK_Real, CSK_Imag
  };

  /// A path from a glvalue to a subobject of that glvalue.
  struct SubobjectDesignator {
    /// True if the subobject was named in a manner not supported by C++11. Such
    /// lvalues can still be folded, but they are not core constant expressions
    /// and we cannot perform lvalue-to-rvalue conversions on them.
    unsigned Invalid : 1;

    /// Is this a pointer one past the end of an object?
    unsigned IsOnePastTheEnd : 1;

    /// Indicator of whether the first entry is an unsized array.
    unsigned FirstEntryIsAnUnsizedArray : 1;

    /// Indicator of whether the most-derived object is an array element.
    unsigned MostDerivedIsArrayElement : 1;

    /// The length of the path to the most-derived object of which this is a
    /// subobject.
    unsigned MostDerivedPathLength : 28;

    /// The size of the array of which the most-derived object is an element.
    /// This will always be 0 if the most-derived object is not an array
    /// element. 0 is not an indicator of whether or not the most-derived object
    /// is an array, however, because 0-length arrays are allowed.
    ///
    /// If the current array is an unsized array, the value of this is
    /// undefined.
    uint64_t MostDerivedArraySize;

    /// The type of the most derived object referred to by this address.
    QualType MostDerivedType;

    typedef APValue::LValuePathEntry PathEntry;

    /// The entries on the path from the glvalue to the designated subobject.
    SmallVector<PathEntry, 8> Entries;

    SubobjectDesignator() : Invalid(true) {}

    explicit SubobjectDesignator(QualType T)
        : Invalid(false), IsOnePastTheEnd(false),
          FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
          MostDerivedPathLength(0), MostDerivedArraySize(0),
          MostDerivedType(T) {}

    SubobjectDesignator(ASTContext &Ctx, const APValue &V)
        : Invalid(!V.isLValue() || !V.hasLValuePath()), IsOnePastTheEnd(false),
          FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
          MostDerivedPathLength(0), MostDerivedArraySize(0) {
      assert(V.isLValue() && "Non-LValue used to make an LValue designator?");
      if (!Invalid) {
        IsOnePastTheEnd = V.isLValueOnePastTheEnd();
        ArrayRef<PathEntry> VEntries = V.getLValuePath();
        Entries.insert(Entries.end(), VEntries.begin(), VEntries.end());
        if (V.getLValueBase()) {
          bool IsArray = false;
          MostDerivedPathLength = findMostDerivedSubobject(
              Ctx, V.getLValueBase(), V.getLValuePath(), MostDerivedArraySize,
              MostDerivedType, IsArray);
          MostDerivedIsArrayElement = IsArray;
        }
      }
    }

    void setInvalid() {
      Invalid = true;
      Entries.clear();
    }

    /// Determine whether the most derived subobject is an array without a
    /// known bound.
    bool isMostDerivedAnUnsizedArray() const {
      assert(!Invalid && "Calling this makes no sense on invalid designators");
      return Entries.size() == 1 && FirstEntryIsAnUnsizedArray;
    }

    /// Determine what the most derived array's size is. Results in an assertion
    /// failure if the most derived array lacks a size.
    uint64_t getMostDerivedArraySize() const {
      assert(!isMostDerivedAnUnsizedArray() && "Unsized array has no size");
      return MostDerivedArraySize;
    }

    /// Determine whether this is a one-past-the-end pointer.
    bool isOnePastTheEnd() const {
      assert(!Invalid);
      if (IsOnePastTheEnd)
        return true;
      if (!isMostDerivedAnUnsizedArray() && MostDerivedIsArrayElement &&
          Entries[MostDerivedPathLength - 1].ArrayIndex == MostDerivedArraySize)
        return true;
      return false;
    }

    /// Check that this refers to a valid subobject.
    bool isValidSubobject() const {
      if (Invalid)
        return false;
      return !isOnePastTheEnd();
    }
    /// Check that this refers to a valid subobject, and if not, produce a
    /// relevant diagnostic and set the designator as invalid.
    bool checkSubobject(EvalInfo &Info, const Expr *E, CheckSubobjectKind CSK);

    /// Update this designator to refer to the first element within this array.
    void addArrayUnchecked(const ConstantArrayType *CAT) {
      PathEntry Entry;
      Entry.ArrayIndex = 0;
      Entries.push_back(Entry);

      // This is a most-derived object.
      MostDerivedType = CAT->getElementType();
      MostDerivedIsArrayElement = true;
      MostDerivedArraySize = CAT->getSize().getZExtValue();
      MostDerivedPathLength = Entries.size();
    }
    /// Update this designator to refer to the first element within the array of
    /// elements of type T. This is an array of unknown size.
    void addUnsizedArrayUnchecked(QualType ElemTy) {
      PathEntry Entry;
      Entry.ArrayIndex = 0;
      Entries.push_back(Entry);

      MostDerivedType = ElemTy;
      MostDerivedIsArrayElement = true;
      // The value in MostDerivedArraySize is undefined in this case. So, set it
      // to an arbitrary value that's likely to loudly break things if it's
      // used.
      MostDerivedArraySize = std::numeric_limits<uint64_t>::max() / 2;
      MostDerivedPathLength = Entries.size();
    }
    /// Update this designator to refer to the given base or member of this
    /// object.
    void addDeclUnchecked(const Decl *D, bool Virtual = false) {
      PathEntry Entry;
      APValue::BaseOrMemberType Value(D, Virtual);
      Entry.BaseOrMember = Value.getOpaqueValue();
      Entries.push_back(Entry);

      // If this isn't a base class, it's a new most-derived object.
      if (const FieldDecl *FD = dyn_cast<FieldDecl>(D)) {
        MostDerivedType = FD->getType();
        MostDerivedIsArrayElement = false;
        MostDerivedArraySize = 0;
        MostDerivedPathLength = Entries.size();
      }
    }
    /// Update this designator to refer to the given complex component.
    void addComplexUnchecked(QualType EltTy, bool Imag) {
      PathEntry Entry;
      Entry.ArrayIndex = Imag;
      Entries.push_back(Entry);

      // This is technically a most-derived object, though in practice this
      // is unlikely to matter.
      MostDerivedType = EltTy;
      MostDerivedIsArrayElement = true;
      MostDerivedArraySize = 2;
      MostDerivedPathLength = Entries.size();
    }
    void diagnosePointerArithmetic(EvalInfo &Info, const Expr *E, uint64_t N);
    /// Add N to the address of this subobject.
    void adjustIndex(EvalInfo &Info, const Expr *E, uint64_t N) {
      if (Invalid) return;
      if (isMostDerivedAnUnsizedArray()) {
        // Can't verify -- trust that the user is doing the right thing (or if
        // not, trust that the caller will catch the bad behavior).
        Entries.back().ArrayIndex += N;
        return;
      }
      if (MostDerivedPathLength == Entries.size() &&
          MostDerivedIsArrayElement) {
        Entries.back().ArrayIndex += N;
        if (Entries.back().ArrayIndex > getMostDerivedArraySize()) {
          diagnosePointerArithmetic(Info, E, Entries.back().ArrayIndex);
          setInvalid();
        }
        return;
      }
      // [expr.add]p4: For the purposes of these operators, a pointer to a
      // nonarray object behaves the same as a pointer to the first element of
      // an array of length one with the type of the object as its element type.
      if (IsOnePastTheEnd && N == (uint64_t)-1)
        IsOnePastTheEnd = false;
      else if (!IsOnePastTheEnd && N == 1)
        IsOnePastTheEnd = true;
      else if (N != 0) {
        diagnosePointerArithmetic(Info, E, uint64_t(IsOnePastTheEnd) + N);
        setInvalid();
      }
    }
  };

  /// A stack frame in the constexpr call stack.
  struct CallStackFrame {
    EvalInfo &Info;

    /// Parent - The caller of this stack frame.
    CallStackFrame *Caller;

    /// Callee - The function which was called.
    const FunctionDecl *Callee;

    /// This - The binding for the this pointer in this call, if any.
    const LValue *This;

    /// Arguments - Parameter bindings for this function call, indexed by
    /// parameters' function scope indices.
    APValue *Arguments;

    // Note that we intentionally use std::map here so that references to
    // values are stable.
    typedef std::map<const void*, APValue> MapTy;
    typedef MapTy::const_iterator temp_iterator;
    /// Temporaries - Temporary lvalues materialized within this stack frame.
    MapTy Temporaries;

    /// CallLoc - The location of the call expression for this call.
    SourceLocation CallLoc;

    /// Index - The call index of this call.
    unsigned Index;

    CallStackFrame(EvalInfo &Info, SourceLocation CallLoc,
                   const FunctionDecl *Callee, const LValue *This,
                   APValue *Arguments);
    ~CallStackFrame();

    APValue *getTemporary(const void *Key) {
      MapTy::iterator I = Temporaries.find(Key);
      return I == Temporaries.end() ? nullptr : &I->second;
    }
    APValue &createTemporary(const void *Key, bool IsLifetimeExtended);
  };

  /// Temporarily override 'this'.
  class ThisOverrideRAII {
  public:
    ThisOverrideRAII(CallStackFrame &Frame, const LValue *NewThis, bool Enable)
        : Frame(Frame), OldThis(Frame.This) {
      if (Enable)
        Frame.This = NewThis;
    }
    ~ThisOverrideRAII() {
      Frame.This = OldThis;
    }
  private:
    CallStackFrame &Frame;
    const LValue *OldThis;
  };

  /// A partial diagnostic which we might know in advance that we are not going
  /// to emit.
  class OptionalDiagnostic {
    PartialDiagnostic *Diag;

  public:
    explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr)
      : Diag(Diag) {}

    template<typename T>
    OptionalDiagnostic &operator<<(const T &v) {
      if (Diag)
        *Diag << v;
      return *this;
    }

    OptionalDiagnostic &operator<<(const APSInt &I) {
      if (Diag) {
        SmallVector<char, 32> Buffer;
        I.toString(Buffer);
        *Diag << StringRef(Buffer.data(), Buffer.size());
      }
      return *this;
    }

    OptionalDiagnostic &operator<<(const APFloat &F) {
      if (Diag) {
        // FIXME: Force the precision of the source value down so we don't
        // print digits which are usually useless (we don't really care here if
        // we truncate a digit by accident in edge cases).  Ideally,
        // APFloat::toString would automatically print the shortest 
        // representation which rounds to the correct value, but it's a bit
        // tricky to implement.
        unsigned precision =
            llvm::APFloat::semanticsPrecision(F.getSemantics());
        precision = (precision * 59 + 195) / 196;
        SmallVector<char, 32> Buffer;
        F.toString(Buffer, precision);
        *Diag << StringRef(Buffer.data(), Buffer.size());
      }
      return *this;
    }
  };

  /// A cleanup, and a flag indicating whether it is lifetime-extended.
  class Cleanup {
    llvm::PointerIntPair<APValue*, 1, bool> Value;

  public:
    Cleanup(APValue *Val, bool IsLifetimeExtended)
        : Value(Val, IsLifetimeExtended) {}

    bool isLifetimeExtended() const { return Value.getInt(); }
    void endLifetime() {
      *Value.getPointer() = APValue();
    }
  };

  /// EvalInfo - This is a private struct used by the evaluator to capture
  /// information about a subexpression as it is folded.  It retains information
  /// about the AST context, but also maintains information about the folded
  /// expression.
  ///
  /// If an expression could be evaluated, it is still possible it is not a C
  /// "integer constant expression" or constant expression.  If not, this struct
  /// captures information about how and why not.
  ///
  /// One bit of information passed *into* the request for constant folding
  /// indicates whether the subexpression is "evaluated" or not according to C
  /// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
  /// evaluate the expression regardless of what the RHS is, but C only allows
  /// certain things in certain situations.
  struct LLVM_ALIGNAS(/*alignof(uint64_t)*/ 8) EvalInfo {
    ASTContext &Ctx;

    /// EvalStatus - Contains information about the evaluation.
    Expr::EvalStatus &EvalStatus;

    /// CurrentCall - The top of the constexpr call stack.
    CallStackFrame *CurrentCall;

    /// CallStackDepth - The number of calls in the call stack right now.
    unsigned CallStackDepth;

    /// NextCallIndex - The next call index to assign.
    unsigned NextCallIndex;

    /// StepsLeft - The remaining number of evaluation steps we're permitted
    /// to perform. This is essentially a limit for the number of statements
    /// we will evaluate.
    unsigned StepsLeft;

    /// BottomFrame - The frame in which evaluation started. This must be
    /// initialized after CurrentCall and CallStackDepth.
    CallStackFrame BottomFrame;

    /// A stack of values whose lifetimes end at the end of some surrounding
    /// evaluation frame.
    llvm::SmallVector<Cleanup, 16> CleanupStack;

    /// EvaluatingDecl - This is the declaration whose initializer is being
    /// evaluated, if any.
    APValue::LValueBase EvaluatingDecl;

    /// EvaluatingDeclValue - This is the value being constructed for the
    /// declaration whose initializer is being evaluated, if any.
    APValue *EvaluatingDeclValue;

    /// The current array initialization index, if we're performing array
    /// initialization.
    uint64_t ArrayInitIndex = -1;

    /// HasActiveDiagnostic - Was the previous diagnostic stored? If so, further
    /// notes attached to it will also be stored, otherwise they will not be.
    bool HasActiveDiagnostic;

    /// \brief Have we emitted a diagnostic explaining why we couldn't constant
    /// fold (not just why it's not strictly a constant expression)?
    bool HasFoldFailureDiagnostic;

    /// \brief Whether or not we're currently speculatively evaluating.
    bool IsSpeculativelyEvaluating;

    enum EvaluationMode {
      /// Evaluate as a constant expression. Stop if we find that the expression
      /// is not a constant expression.
      EM_ConstantExpression,

      /// Evaluate as a potential constant expression. Keep going if we hit a
      /// construct that we can't evaluate yet (because we don't yet know the
      /// value of something) but stop if we hit something that could never be
      /// a constant expression.
      EM_PotentialConstantExpression,

      /// Fold the expression to a constant. Stop if we hit a side-effect that
      /// we can't model.
      EM_ConstantFold,

      /// Evaluate the expression looking for integer overflow and similar
      /// issues. Don't worry about side-effects, and try to visit all
      /// subexpressions.
      EM_EvaluateForOverflow,

      /// Evaluate in any way we know how. Don't worry about side-effects that
      /// can't be modeled.
      EM_IgnoreSideEffects,

      /// Evaluate as a constant expression. Stop if we find that the expression
      /// is not a constant expression. Some expressions can be retried in the
      /// optimizer if we don't constant fold them here, but in an unevaluated
      /// context we try to fold them immediately since the optimizer never
      /// gets a chance to look at it.
      EM_ConstantExpressionUnevaluated,

      /// Evaluate as a potential constant expression. Keep going if we hit a
      /// construct that we can't evaluate yet (because we don't yet know the
      /// value of something) but stop if we hit something that could never be
      /// a constant expression. Some expressions can be retried in the
      /// optimizer if we don't constant fold them here, but in an unevaluated
      /// context we try to fold them immediately since the optimizer never
      /// gets a chance to look at it.
      EM_PotentialConstantExpressionUnevaluated,

      /// Evaluate as a constant expression. Continue evaluating if either:
      /// - We find a MemberExpr with a base that can't be evaluated.
      /// - We find a variable initialized with a call to a function that has
      ///   the alloc_size attribute on it.
      /// In either case, the LValue returned shall have an invalid base; in the
      /// former, the base will be the invalid MemberExpr, in the latter, the
      /// base will be either the alloc_size CallExpr or a CastExpr wrapping
      /// said CallExpr.
      EM_OffsetFold,
    } EvalMode;

    /// Are we checking whether the expression is a potential constant
    /// expression?
    bool checkingPotentialConstantExpression() const {
      return EvalMode == EM_PotentialConstantExpression ||
             EvalMode == EM_PotentialConstantExpressionUnevaluated;
    }

    /// Are we checking an expression for overflow?
    // FIXME: We should check for any kind of undefined or suspicious behavior
    // in such constructs, not just overflow.
    bool checkingForOverflow() { return EvalMode == EM_EvaluateForOverflow; }

    EvalInfo(const ASTContext &C, Expr::EvalStatus &S, EvaluationMode Mode)
      : Ctx(const_cast<ASTContext &>(C)), EvalStatus(S), CurrentCall(nullptr),
        CallStackDepth(0), NextCallIndex(1),
        StepsLeft(getLangOpts().ConstexprStepLimit),
        BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr),
        EvaluatingDecl((const ValueDecl *)nullptr),
        EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false),
        HasFoldFailureDiagnostic(false), IsSpeculativelyEvaluating(false),
        EvalMode(Mode) {}

    void setEvaluatingDecl(APValue::LValueBase Base, APValue &Value) {
      EvaluatingDecl = Base;
      EvaluatingDeclValue = &Value;
    }

    const LangOptions &getLangOpts() const { return Ctx.getLangOpts(); }

    bool CheckCallLimit(SourceLocation Loc) {
      // Don't perform any constexpr calls (other than the call we're checking)
      // when checking a potential constant expression.
      if (checkingPotentialConstantExpression() && CallStackDepth > 1)
        return false;
      if (NextCallIndex == 0) {
        // NextCallIndex has wrapped around.
        FFDiag(Loc, diag::note_constexpr_call_limit_exceeded);
        return false;
      }
      if (CallStackDepth <= getLangOpts().ConstexprCallDepth)
        return true;
      FFDiag(Loc, diag::note_constexpr_depth_limit_exceeded)
        << getLangOpts().ConstexprCallDepth;
      return false;
    }

    CallStackFrame *getCallFrame(unsigned CallIndex) {
      assert(CallIndex && "no call index in getCallFrame");
      // We will eventually hit BottomFrame, which has Index 1, so Frame can't
      // be null in this loop.
      CallStackFrame *Frame = CurrentCall;
      while (Frame->Index > CallIndex)
        Frame = Frame->Caller;
      return (Frame->Index == CallIndex) ? Frame : nullptr;
    }

    bool nextStep(const Stmt *S) {
      if (!StepsLeft) {
        FFDiag(S->getLocStart(), diag::note_constexpr_step_limit_exceeded);
        return false;
      }
      --StepsLeft;
      return true;
    }

  private:
    /// Add a diagnostic to the diagnostics list.
    PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId) {
      PartialDiagnostic PD(DiagId, Ctx.getDiagAllocator());
      EvalStatus.Diag->push_back(std::make_pair(Loc, PD));
      return EvalStatus.Diag->back().second;
    }

    /// Add notes containing a call stack to the current point of evaluation.
    void addCallStack(unsigned Limit);

  private:
    OptionalDiagnostic Diag(SourceLocation Loc, diag::kind DiagId,
                            unsigned ExtraNotes, bool IsCCEDiag) {
    
      if (EvalStatus.Diag) {
        // If we have a prior diagnostic, it will be noting that the expression
        // isn't a constant expression. This diagnostic is more important,
        // unless we require this evaluation to produce a constant expression.
        //
        // FIXME: We might want to show both diagnostics to the user in
        // EM_ConstantFold mode.
        if (!EvalStatus.Diag->empty()) {
          switch (EvalMode) {
          case EM_ConstantFold:
          case EM_IgnoreSideEffects:
          case EM_EvaluateForOverflow:
            if (!HasFoldFailureDiagnostic)
              break;
            // We've already failed to fold something. Keep that diagnostic.
          case EM_ConstantExpression:
          case EM_PotentialConstantExpression:
          case EM_ConstantExpressionUnevaluated:
          case EM_PotentialConstantExpressionUnevaluated:
          case EM_OffsetFold:
            HasActiveDiagnostic = false;
            return OptionalDiagnostic();
          }
        }

        unsigned CallStackNotes = CallStackDepth - 1;
        unsigned Limit = Ctx.getDiagnostics().getConstexprBacktraceLimit();
        if (Limit)
          CallStackNotes = std::min(CallStackNotes, Limit + 1);
        if (checkingPotentialConstantExpression())
          CallStackNotes = 0;

        HasActiveDiagnostic = true;
        HasFoldFailureDiagnostic = !IsCCEDiag;
        EvalStatus.Diag->clear();
        EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes);
        addDiag(Loc, DiagId);
        if (!checkingPotentialConstantExpression())
          addCallStack(Limit);
        return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second);
      }
      HasActiveDiagnostic = false;
      return OptionalDiagnostic();
    }
  public:
    // Diagnose that the evaluation could not be folded (FF => FoldFailure)
    OptionalDiagnostic
    FFDiag(SourceLocation Loc,
          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
          unsigned ExtraNotes = 0) {
      return Diag(Loc, DiagId, ExtraNotes, false);
    }
    
    OptionalDiagnostic FFDiag(const Expr *E, diag::kind DiagId
                              = diag::note_invalid_subexpr_in_const_expr,
                            unsigned ExtraNotes = 0) {
      if (EvalStatus.Diag)
        return Diag(E->getExprLoc(), DiagId, ExtraNotes, /*IsCCEDiag*/false);
      HasActiveDiagnostic = false;
      return OptionalDiagnostic();
    }

    /// Diagnose that the evaluation does not produce a C++11 core constant
    /// expression.
    ///
    /// FIXME: Stop evaluating if we're in EM_ConstantExpression or
    /// EM_PotentialConstantExpression mode and we produce one of these.
    OptionalDiagnostic CCEDiag(SourceLocation Loc, diag::kind DiagId
                                 = diag::note_invalid_subexpr_in_const_expr,
                               unsigned ExtraNotes = 0) {
      // Don't override a previous diagnostic. Don't bother collecting
      // diagnostics if we're evaluating for overflow.
      if (!EvalStatus.Diag || !EvalStatus.Diag->empty()) {
        HasActiveDiagnostic = false;
        return OptionalDiagnostic();
      }
      return Diag(Loc, DiagId, ExtraNotes, true);
    }
    OptionalDiagnostic CCEDiag(const Expr *E, diag::kind DiagId
                                 = diag::note_invalid_subexpr_in_const_expr,
                               unsigned ExtraNotes = 0) {
      return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes);
    }
    /// Add a note to a prior diagnostic.
    OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId) {
      if (!HasActiveDiagnostic)
        return OptionalDiagnostic();
      return OptionalDiagnostic(&addDiag(Loc, DiagId));
    }

    /// Add a stack of notes to a prior diagnostic.
    void addNotes(ArrayRef<PartialDiagnosticAt> Diags) {
      if (HasActiveDiagnostic) {
        EvalStatus.Diag->insert(EvalStatus.Diag->end(),
                                Diags.begin(), Diags.end());
      }
    }

    /// Should we continue evaluation after encountering a side-effect that we
    /// couldn't model?
    bool keepEvaluatingAfterSideEffect() {
      switch (EvalMode) {
      case EM_PotentialConstantExpression:
      case EM_PotentialConstantExpressionUnevaluated:
      case EM_EvaluateForOverflow:
      case EM_IgnoreSideEffects:
        return true;

      case EM_ConstantExpression:
      case EM_ConstantExpressionUnevaluated:
      case EM_ConstantFold:
      case EM_OffsetFold:
        return false;
      }
      llvm_unreachable("Missed EvalMode case");
    }

    /// Note that we have had a side-effect, and determine whether we should
    /// keep evaluating.
    bool noteSideEffect() {
      EvalStatus.HasSideEffects = true;
      return keepEvaluatingAfterSideEffect();
    }

    /// Should we continue evaluation after encountering undefined behavior?
    bool keepEvaluatingAfterUndefinedBehavior() {
      switch (EvalMode) {
      case EM_EvaluateForOverflow:
      case EM_IgnoreSideEffects:
      case EM_ConstantFold:
      case EM_OffsetFold:
        return true;

      case EM_PotentialConstantExpression:
      case EM_PotentialConstantExpressionUnevaluated:
      case EM_ConstantExpression:
      case EM_ConstantExpressionUnevaluated:
        return false;
      }
      llvm_unreachable("Missed EvalMode case");
    }

    /// Note that we hit something that was technically undefined behavior, but
    /// that we can evaluate past it (such as signed overflow or floating-point
    /// division by zero.)
    bool noteUndefinedBehavior() {
      EvalStatus.HasUndefinedBehavior = true;
      return keepEvaluatingAfterUndefinedBehavior();
    }

    /// Should we continue evaluation as much as possible after encountering a
    /// construct which can't be reduced to a value?
    bool keepEvaluatingAfterFailure() {
      if (!StepsLeft)
        return false;

      switch (EvalMode) {
      case EM_PotentialConstantExpression:
      case EM_PotentialConstantExpressionUnevaluated:
      case EM_EvaluateForOverflow:
        return true;

      case EM_ConstantExpression:
      case EM_ConstantExpressionUnevaluated:
      case EM_ConstantFold:
      case EM_IgnoreSideEffects:
      case EM_OffsetFold:
        return false;
      }
      llvm_unreachable("Missed EvalMode case");
    }

    /// Notes that we failed to evaluate an expression that other expressions
    /// directly depend on, and determine if we should keep evaluating. This
    /// should only be called if we actually intend to keep evaluating.
    ///
    /// Call noteSideEffect() instead if we may be able to ignore the value that
    /// we failed to evaluate, e.g. if we failed to evaluate Foo() in:
    ///
    /// (Foo(), 1)      // use noteSideEffect
    /// (Foo() || true) // use noteSideEffect
    /// Foo() + 1       // use noteFailure
    LLVM_NODISCARD bool noteFailure() {
      // Failure when evaluating some expression often means there is some
      // subexpression whose evaluation was skipped. Therefore, (because we
      // don't track whether we skipped an expression when unwinding after an
      // evaluation failure) every evaluation failure that bubbles up from a
      // subexpression implies that a side-effect has potentially happened. We
      // skip setting the HasSideEffects flag to true until we decide to
      // continue evaluating after that point, which happens here.
      bool KeepGoing = keepEvaluatingAfterFailure();
      EvalStatus.HasSideEffects |= KeepGoing;
      return KeepGoing;
    }

    bool allowInvalidBaseExpr() const {
      return EvalMode == EM_OffsetFold;
    }

    class ArrayInitLoopIndex {
      EvalInfo &Info;
      uint64_t OuterIndex;

    public:
      ArrayInitLoopIndex(EvalInfo &Info)
          : Info(Info), OuterIndex(Info.ArrayInitIndex) {
        Info.ArrayInitIndex = 0;
      }
      ~ArrayInitLoopIndex() { Info.ArrayInitIndex = OuterIndex; }

      operator uint64_t&() { return Info.ArrayInitIndex; }
    };
  };

  /// Object used to treat all foldable expressions as constant expressions.
  struct FoldConstant {
    EvalInfo &Info;
    bool Enabled;
    bool HadNoPriorDiags;
    EvalInfo::EvaluationMode OldMode;

    explicit FoldConstant(EvalInfo &Info, bool Enabled)
      : Info(Info),
        Enabled(Enabled),
        HadNoPriorDiags(Info.EvalStatus.Diag &&
                        Info.EvalStatus.Diag->empty() &&
                        !Info.EvalStatus.HasSideEffects),
        OldMode(Info.EvalMode) {
      if (Enabled &&
          (Info.EvalMode == EvalInfo::EM_ConstantExpression ||
           Info.EvalMode == EvalInfo::EM_ConstantExpressionUnevaluated))
        Info.EvalMode = EvalInfo::EM_ConstantFold;
    }
    void keepDiagnostics() { Enabled = false; }
    ~FoldConstant() {
      if (Enabled && HadNoPriorDiags && !Info.EvalStatus.Diag->empty() &&
          !Info.EvalStatus.HasSideEffects)
        Info.EvalStatus.Diag->clear();
      Info.EvalMode = OldMode;
    }
  };

  /// RAII object used to treat the current evaluation as the correct pointer
  /// offset fold for the current EvalMode
  struct FoldOffsetRAII {
    EvalInfo &Info;
    EvalInfo::EvaluationMode OldMode;
    explicit FoldOffsetRAII(EvalInfo &Info)
        : Info(Info), OldMode(Info.EvalMode) {
      if (!Info.checkingPotentialConstantExpression())
        Info.EvalMode = EvalInfo::EM_OffsetFold;
    }

    ~FoldOffsetRAII() { Info.EvalMode = OldMode; }
  };

  /// RAII object used to optionally suppress diagnostics and side-effects from
  /// a speculative evaluation.
  class SpeculativeEvaluationRAII {
    /// Pair of EvalInfo, and a bit that stores whether or not we were
    /// speculatively evaluating when we created this RAII.
    llvm::PointerIntPair<EvalInfo *, 1, bool> InfoAndOldSpecEval;
    Expr::EvalStatus Old;

    void moveFromAndCancel(SpeculativeEvaluationRAII &&Other) {
      InfoAndOldSpecEval = Other.InfoAndOldSpecEval;
      Old = Other.Old;
      Other.InfoAndOldSpecEval.setPointer(nullptr);
    }

    void maybeRestoreState() {
      EvalInfo *Info = InfoAndOldSpecEval.getPointer();
      if (!Info)
        return;

      Info->EvalStatus = Old;
      Info->IsSpeculativelyEvaluating = InfoAndOldSpecEval.getInt();
    }

  public:
    SpeculativeEvaluationRAII() = default;

    SpeculativeEvaluationRAII(
        EvalInfo &Info, SmallVectorImpl<PartialDiagnosticAt> *NewDiag = nullptr)
        : InfoAndOldSpecEval(&Info, Info.IsSpeculativelyEvaluating),
          Old(Info.EvalStatus) {
      Info.EvalStatus.Diag = NewDiag;
      Info.IsSpeculativelyEvaluating = true;
    }

    SpeculativeEvaluationRAII(const SpeculativeEvaluationRAII &Other) = delete;
    SpeculativeEvaluationRAII(SpeculativeEvaluationRAII &&Other) {
      moveFromAndCancel(std::move(Other));
    }

    SpeculativeEvaluationRAII &operator=(SpeculativeEvaluationRAII &&Other) {
      maybeRestoreState();
      moveFromAndCancel(std::move(Other));
      return *this;
    }

    ~SpeculativeEvaluationRAII() { maybeRestoreState(); }
  };