clang/lib/AST/ByteCode/Pointer.cpp

//===--- Pointer.cpp - Types for the constexpr VM ---------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "Pointer.h"
#include "Boolean.h"
#include "Char.h"
#include "Context.h"
#include "Floating.h"
#include "Function.h"
#include "InitMap.h"
#include "Integral.h"
#include "MemberPointer.h"
#include "PrimType.h"
#include "Record.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/RecordLayout.h"

using namespace clang;
using namespace clang::interp;

// Helper to check if a Type can be passed to
// ASTContext::getTypeSize().
static bool validType(QualType T) {
  if (const RecordDecl *RD = T->getAsRecordDecl())
    return ASTContext::hasLayout(RD);
  return !T->isDependentType() && !T->isUndeducedAutoType() &&
         !T->isSpecificBuiltinType(BuiltinType::UnknownAny) &&
         !T->isIncompleteType();
}

Pointer::Pointer(Block *Pointee)
    : Pointer(Pointee, Pointee->getMetadataSize(), Pointee->getMetadataSize()) {
}

Pointer::Pointer(Block *Pointee, uint64_t BaseAndOffset)
    : Pointer(Pointee, BaseAndOffset, BaseAndOffset) {}

Pointer::Pointer(Block *Pointee, unsigned Base, uint64_t Offset)
    : Offset(Offset), StorageKind(Storage::Block) {
  assert(Pointee);
  assert(Base % alignof(void *) == 0 && "wrong base");
  assert(Base >= Pointee->getMetadataSize());

  BS = {Pointee, Base, nullptr, nullptr};
  Pointee->addPointer(this);
}

Pointer::Pointer(const Pointer &P)
    : Offset(P.Offset), StorageKind(P.StorageKind) {
  switch (StorageKind) {
  case Storage::Int:
    Int = P.Int;
    break;
  case Storage::Block:
    BS = P.BS;
    if (BS.Pointee)
      BS.Pointee->addPointer(this);
    break;
  case Storage::Fn:
    Fn = P.Fn;
    break;
  case Storage::Typeid:
    Typeid = P.Typeid;
    break;
  case Storage::String:
    Str = P.Str;
    break;
  case Storage::Opaque:
    Opaque = P.Opaque;
    break;
  }
}

Pointer::Pointer(Pointer &&P) : Offset(P.Offset), StorageKind(P.StorageKind) {
  switch (StorageKind) {
  case Storage::Int:
    Int = P.Int;
    break;
  case Storage::Block:
    BS = P.BS;
    if (BS.Pointee)
      BS.Pointee->replacePointer(&P, this);
    break;
  case Storage::Fn:
    Fn = P.Fn;
    break;
  case Storage::Typeid:
    Typeid = P.Typeid;
    break;
  case Storage::String:
    Str = P.Str;
    break;
  case Storage::Opaque:
    Opaque = P.Opaque;
    break;
  }
}

Pointer::~Pointer() {
  if (!isBlockPointer())
    return;

  if (Block *Pointee = BS.Pointee) {
    Pointee->removePointer(this);
    BS.Pointee = nullptr;
    Pointee->cleanup();
  }
}

Pointer &Pointer::operator=(const Pointer &P) {
  // If the current storage type is Block, we need to remove
  // this pointer from the block.
  if (isBlockPointer()) {
    if (P.isBlockPointer() && this->block() == P.block()) {
      Offset = P.Offset;
      BS.Base = P.BS.Base;
      return *this;
    }

    if (Block *Pointee = BS.Pointee) {
      Pointee->removePointer(this);
      BS.Pointee = nullptr;
      Pointee->cleanup();
    }
  }

  StorageKind = P.StorageKind;
  Offset = P.Offset;

  switch (StorageKind) {
  case Storage::Int:
    Int = P.Int;
    break;
  case Storage::Block:
    BS = P.BS;

    if (BS.Pointee)
      BS.Pointee->addPointer(this);
    break;
  case Storage::Fn:
    Fn = P.Fn;
    break;
  case Storage::Typeid:
    Typeid = P.Typeid;
    break;
  case Storage::String:
    Str = P.Str;
    break;
  case Storage::Opaque:
    Opaque = P.Opaque;
    break;
  }
  return *this;
}

Pointer &Pointer::operator=(Pointer &&P) {
  // If the current storage type is Block, we need to remove
  // this pointer from the block.
  if (isBlockPointer()) {
    if (P.isBlockPointer() && this->block() == P.block()) {
      Offset = P.Offset;
      BS.Base = P.BS.Base;
      return *this;
    }

    if (Block *Pointee = BS.Pointee) {
      Pointee->removePointer(this);
      BS.Pointee = nullptr;
      Pointee->cleanup();
    }
  }

  StorageKind = P.StorageKind;
  Offset = P.Offset;

  switch (StorageKind) {
  case Storage::Int:
    Int = P.Int;
    break;
  case Storage::Block:
    BS = P.BS;

    if (BS.Pointee)
      BS.Pointee->addPointer(this);
    break;
  case Storage::Fn:
    Fn = P.Fn;
    break;
  case Storage::Typeid:
    Typeid = P.Typeid;
    break;
  case Storage::String:
    Str = P.Str;
    break;
  case Storage::Opaque:
    Opaque = P.Opaque;
    break;
  }
  return *this;
}

bool Pointer::operator==(const Pointer &P) const {
  if (StorageKind != P.StorageKind)
    return false;

  switch (StorageKind) {
  case Storage::Int:
    return P.Int.Value == Int.Value && P.Int.getType() == Int.getType() &&
           P.Offset == Offset;
  case Storage::Block:
    return P.view() == view();
  case Storage::Fn:
    return P.Fn.Func == Fn.Func && P.Offset == Offset;
  case Storage::Typeid:
    llvm_unreachable("typeid in operator==?");
  case Storage::String:
    return Str.Base == P.Str.Base && Offset == P.Offset;
  case Storage::Opaque:
    if (P.Opaque.Base != Opaque.Base ||
        P.Opaque.PathLength != Opaque.PathLength || P.Offset != Offset)
      return false;

    for (unsigned I = 0; I != Opaque.PathLength; ++I) {
      if (Opaque.Path[I].Kind != P.Opaque.Path[I].Kind)
        return false;
      switch (Opaque.Path[I].Kind) {
      case PointerPathEntry::Base:
        if (Opaque.Path[I].RD != P.Opaque.Path[I].RD)
          return false;
        break;
      case PointerPathEntry::Array:
      case PointerPathEntry::NegativeArray:
        if (Opaque.Path[I].Index != P.Opaque.Path[I].Index)
          return false;
        break;
      case PointerPathEntry::Field:
        if (Opaque.Path[I].FD != P.Opaque.Path[I].FD)
          return false;
        break;
      }
    }
  }
  return true;
}

APValue Pointer::toAPValue(const ASTContext &ASTCtx) const {

  if (isZero())
    return APValue(APValue::LValueBase(), CharUnits::Zero(), {},
                   /*IsOnePastEnd=*/false, /*IsNullPtr=*/true);

  switch (StorageKind) {
  case Storage::Int:
    return APValue(static_cast<const Expr *>(nullptr),
                   CharUnits::fromQuantity(asIntPointer().Value + this->Offset),
                   {},
                   /*IsOnePastEnd=*/false, /*IsNullPtr=*/false);
  case Storage::Block:
    // See below.
    break;
  case Storage::Fn: {
    const FunctionPointer &FP = asFunctionPointer();
    if (const FunctionDecl *FD = FP.Func->getDecl())
      return APValue(FD, CharUnits::fromQuantity(Offset), {},
                     /*OnePastTheEnd=*/false, /*IsNull=*/false);
    return APValue(FP.Func->getExpr(), CharUnits::fromQuantity(Offset), {},
                   /*OnePastTheEnd=*/false, /*IsNull=*/false);
  } break;
  case Storage::Typeid: {
    TypeInfoLValue TypeInfo(Typeid.TypePtr);
    return APValue(APValue::LValueBase::getTypeInfo(
                       TypeInfo, QualType(Typeid.TypeInfoType, 0)),
                   CharUnits::Zero(), {},
                   /*OnePastTheEnd=*/false, /*IsNull=*/false);
  } break;
  case Storage::String: {
    llvm::SmallVector<APValue::LValuePathEntry, 1> Path;
    if (Offset != 0 || Str.Decayed)
      Path.push_back(APValue::LValuePathEntry::ArrayIndex(Offset));

    return APValue(APValue::LValueBase(Str.Base),
                   CharUnits::fromQuantity(Offset * elemSize()), Path,
                   /*OnePastTheEnd=*/false, /*IsNull=*/false);
  }
  case Storage::Opaque: {
    bool ValidBase = Opaque.hasValidBase() || this->Offset <= 1;

    size_t LayoutOffset = Opaque.computeLayoutOffset(ASTCtx).value_or(0);
    size_t ElemSize = 0;
    if (validType(Opaque.getFieldType()))
      ElemSize = ASTCtx.getTypeSizeInChars(Opaque.getFieldType()).getQuantity();

    auto LValueOffset =
        CharUnits::fromQuantity(LayoutOffset + (this->Offset * ElemSize));
    APValue::LValueBase Base;
    if (const Expr *E = Opaque.Base.asExpr())
      Base = E;
    else
      Base = Opaque.Base.asValueDecl();

    // For valid bases, assemble the LValuePath.
    APValue Result;
    if (ValidBase) {
      llvm::SmallVector<APValue::LValuePathEntry, 5> Path;
      for (const PointerPathEntry &Entry : Opaque.path()) {
        switch (Entry.Kind) {
        case PointerPathEntry::Field:
          Path.push_back(APValue::LValuePathEntry({Entry.FD, false}));
          break;
        case PointerPathEntry::Base:
          Path.push_back(APValue::LValuePathEntry(
              {Entry.RD.getPointer(), Entry.RD.getInt()}));
          break;
        case PointerPathEntry::Array:
          Path.push_back(APValue::LValuePathEntry::ArrayIndex(Entry.Index));
          break;
        case PointerPathEntry::NegativeArray:
          Path.push_back(APValue::LValuePathEntry::ArrayIndex(-Entry.Index));
          break;
        }
      }

      Result = APValue(Base, LValueOffset, Path, Opaque.isOnePastEnd(),
                       /*IsNullPtr=*/false);

    } else {
      Result = APValue(Base, LValueOffset, APValue::NoLValuePath{});
    }
    Result.setConstexprUnknown(Opaque.isConstexprUnknown());
    return Result;
  }
  }

  assert(isBlockPointer());
  // Build the lvalue base from the block.
  const Descriptor *Desc = getDeclDesc();
  APValue::LValueBase Base;
  if (const auto *VD = Desc->asValueDecl())
    Base = VD;
  else if (const auto *E = Desc->asExpr()) {
    if (block()->isDynamic()) {
      DynamicAllocLValue DA(*block()->DynAllocId, Desc->getDynAllocKind());
      Base =
          APValue::LValueBase::getDynamicAlloc(DA, Desc->getDataType(ASTCtx));
    } else {
      Base = E;
    }
  } else
    llvm_unreachable("Invalid allocation type");

  CharUnits Offset = CharUnits::Zero();

  auto getFieldOffset = [&](const FieldDecl *FD) -> std::optional<CharUnits> {
    if (!ASTContext::hasLayout(FD->getParent()))
      return std::nullopt;
    // This shouldn't happen, but if it does, don't crash inside
    // getASTRecordLayout.
    const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(FD->getParent());
    unsigned FieldIndex = FD->getFieldIndex();
    return ASTCtx.toCharUnitsFromBits(Layout.getFieldOffset(FieldIndex));
  };

  // Build the path into the object.
  bool OnePastEnd = isOnePastEnd() && !isZeroSizeArray();

  llvm::SmallVector<APValue::LValuePathEntry, 5> Path;
  PtrView Ptr = view();
  while (Ptr.isField() || Ptr.isArrayElement()) {

    if (Ptr.isArrayRoot()) {
      // An array root may still be an array element itself.
      if (Ptr.isArrayElement()) {
        Ptr = Ptr.expand();
        const Descriptor *Desc = Ptr.getFieldDesc();
        unsigned Index = Ptr.getIndex();
        QualType ElemType = Desc->getElemQualType();
        Offset += (Index * ASTCtx.getTypeSizeInChars(ElemType));
        if (Ptr.getArray().getFieldDesc()->IsArray)
          Path.push_back(APValue::LValuePathEntry::ArrayIndex(Index));
        Ptr = Ptr.getArray();
      } else {
        const Descriptor *Desc = Ptr.getFieldDesc();
        const auto *Dcl = Desc->asDecl();
        Path.push_back(APValue::LValuePathEntry({Dcl, /*IsVirtual=*/false}));

        if (const auto *FD = dyn_cast_if_present<FieldDecl>(Dcl)) {
          if (std::optional<CharUnits> FieldOffset = getFieldOffset(FD))
            Offset += *FieldOffset;
          else
            return APValue();
        }

        Ptr = Ptr.getBase();
      }
    } else if (Ptr.isArrayElement()) {
      Ptr = Ptr.expand();
      const Descriptor *Desc = Ptr.getFieldDesc();
      unsigned Index;
      if (Ptr.isOnePastEnd()) {
        Index = Ptr.getArray().getNumElems();
        OnePastEnd = false;
      } else
        Index = Ptr.getIndex();

      QualType ElemType = Desc->getElemQualType();
      if (const auto *RD = ElemType->getAsRecordDecl();
          RD && !RD->getDefinition()) {
        // Ignore this for the offset.
      } else {
        Offset += (Index * ASTCtx.getTypeSizeInChars(ElemType));
      }
      if (Ptr.getArray().getFieldDesc()->IsArray)
        Path.push_back(APValue::LValuePathEntry::ArrayIndex(Index));
      Ptr = Ptr.getArray();
    } else {
      const Descriptor *Desc = Ptr.getFieldDesc();

      // Create a path entry for the field.
      if (const auto *BaseOrMember = Desc->asDecl()) {
        bool IsVirtual = false;
        if (const auto *FD = dyn_cast<FieldDecl>(BaseOrMember)) {
          Ptr = Ptr.getBase();
          if (std::optional<CharUnits> FieldOffset = getFieldOffset(FD))
            Offset += *FieldOffset;
          else
            return APValue();
        } else if (const auto *RD = dyn_cast<CXXRecordDecl>(BaseOrMember)) {
          IsVirtual = Ptr.isVirtualBaseClass();
          Ptr = Ptr.getBase();
          const Record *BaseRecord = Ptr.getRecord();

          if (!ASTContext::hasLayout(BaseRecord->getDecl()))
            return APValue();

          const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(
              cast<CXXRecordDecl>(BaseRecord->getDecl()));
          if (IsVirtual)
            Offset += Layout.getVBaseClassOffset(RD);
          else
            Offset += Layout.getBaseClassOffset(RD);

        } else {
          Ptr = Ptr.getBase();
        }
        Path.push_back(APValue::LValuePathEntry({BaseOrMember, IsVirtual}));
        continue;
      }
      llvm_unreachable("Invalid field type");
    }
  }

  // We assemble the LValuePath starting from the innermost pointer to the
  // outermost one. SO in a.b.c, the first element in Path will refer to
  // the field 'c', while later code expects it to refer to 'a'.
  // Just invert the order of the elements.
  std::reverse(Path.begin(), Path.end());

  auto Result = APValue(Base, Offset, Path, OnePastEnd);
  Result.setConstexprUnknown(isConstexprUnknown());
  return Result;
}

void Pointer::print(llvm::raw_ostream &OS) const {
  switch (StorageKind) {
  case Storage::Block: {
    const Block *B = BS.Pointee;
    OS << "(Block) " << B << " {";

    if (isRoot())
      OS << "rootptr(" << BS.Base << "), ";
    else
      OS << BS.Base << ", ";

    if (isElementPastEnd())
      OS << "pastend, ";
    else
      OS << Offset << ", ";

    if (B)
      OS << B->getSize();
    else
      OS << "nullptr";
    OS << "}";
  } break;
  case Storage::Int:
    OS << "(Int) {" << Int.Value << " + " << Offset << ", " << Int.getType()
       << ", " << (Int.isNull() ? "null" : "nonnull") << '}';
    break;
  case Storage::Fn:
    OS << "(Fn) { " << Fn.Func << " + " << Offset << " }";
    break;
  case Storage::Typeid:
    OS << "(Typeid) { " << (const void *)asTypeidPointer().TypePtr << ", "
       << (const void *)asTypeidPointer().TypeInfoType << " + " << Offset
       << "}";
    break;
  case Storage::String:
    OS << "(String) { " << (const void *)Str.getLiteral() << ' ';
    Str.getLiteral()->outputString(OS);
    OS << ". ID: " << Str.ID << " + " << Offset << "}";
    break;
  case Storage::Opaque:
    OS << "(Opaque) { Base: " << Opaque.Base << ", "
       << Opaque.FieldType.getPointer() << " Length: " << Opaque.PathLength
       << ". PastEnd: " << Opaque.isOnePastEnd();
    OS << "} + " << Offset;
    break;
  }
}

/// Compute an offset that can be used to compare the pointer to another one
/// with the same base. To get accurate results, we basically _have to_ compute
/// the lvalue offset using the ASTRecordLayout.
///
/// This function will fail if we're trying to get the type size of a forward
/// declaration.
///
// FIXME: We're still mixing values from the record layout with our internal
// offsets, which will inevitably lead to cryptic errors.
std::optional<size_t>
Pointer::computeOffsetForComparison(const ASTContext &ASTCtx) const {
  switch (StorageKind) {
  case Storage::Int:
    return Int.Value + Offset;
  case Storage::Block:
    // See below.
    break;
  case Storage::Fn:
    return getIntegerRepresentation();
  case Storage::Typeid:
    return reinterpret_cast<uintptr_t>(asTypeidPointer().TypePtr) + Offset;
  case Storage::String:
    return reinterpret_cast<uintptr_t>(Str.getLiteral()) + Offset;
  case Storage::Opaque:
    return computeLayoutOffset(ASTCtx);
  }

  auto getTypeSize = [&](QualType T) -> std::optional<size_t> {
    if (!validType(T))
      return std::nullopt;
    return ASTCtx.getTypeSizeInChars(T).getQuantity();
  };

  size_t Result = 0;
  PtrView P = view();
  while (true) {
    if (P.isVirtualBaseClass()) {
      Result += getInlineDesc()->Offset;
      P = P.getBase();
      continue;
    }

    if (P.isBaseClass()) {
      Result += P.getInlineDesc()->Offset - sizeof(InlineDescriptor);
      P = P.getBase();
      continue;
    }
    if (P.isArrayElement()) {
      P = P.expand();
      Result += (P.getIndex() * P.elemSize());
      P = P.getArray();
      continue;
    }

    if (P.isRoot()) {
      if (P.isOnePastEnd()) {
        if (auto Size = getTypeSize(P.getDeclDesc()->getType()))
          Result += *Size;
        else
          return std::nullopt;
      }
      break;
    }

    assert(P.getField());
    const Record *R = P.getBase().getRecord();
    assert(R);

    if (!ASTContext::hasLayout(R->getDecl()))
      return std::nullopt;
    const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(R->getDecl());
    Result += ASTCtx
                  .toCharUnitsFromBits(
                      Layout.getFieldOffset(P.getField()->getFieldIndex()))
                  .getQuantity();

    if (P.isOnePastEnd()) {
      if (auto Size = getTypeSize(P.getField()->getType()))
        Result += *Size;
      else
        return std::nullopt;
    }

    P = P.getBase();
    if (P.isRoot())
      break;
  }
  return Result;
}

std::optional<size_t>
Pointer::computeLayoutOffset(const ASTContext &ASTCtx) const {
  switch (StorageKind) {
  case Storage::Int:
    return Int.Value + Offset;
  case Storage::Block:
    // See below.
    break;
  case Storage::Fn:
    return getIntegerRepresentation();
  case Storage::Typeid:
    return reinterpret_cast<uintptr_t>(asTypeidPointer().TypePtr) + Offset;
  case Storage::String:
    return Offset * Str.getLiteral()->getCharByteWidth();
  case Storage::Opaque:
    if (auto O = Opaque.computeLayoutOffset(ASTCtx)) {
      size_t TypeSize = 0;
      if (QualType FT = Opaque.getFieldType(); validType(FT))
        TypeSize = ASTCtx.getTypeSizeInChars(FT).getQuantity();
      return *O + (Offset * TypeSize);
    }
    return std::nullopt;
  }

  auto getTypeSize = [&](QualType T) -> std::optional<size_t> {
    if (!validType(T))
      return std::nullopt;
    return ASTCtx.getTypeSizeInChars(T).getQuantity();
  };

  auto getRecordDecl = [&](PtrView P) -> const CXXRecordDecl * {
    if (const Record *R = P.getRecord())
      return cast<CXXRecordDecl>(R->getDecl());
    return cast<CXXRecordDecl>(P.getFieldDesc()->asDecl());
  };

  auto getRecordSize = [&](const RecordDecl *RD) -> unsigned {
    CanQualType RecordTy = ASTCtx.getCanonicalTagType(RD);
    return ASTCtx.getTypeSizeInChars(RecordTy).getQuantity();
  };

  size_t Result = 0;
  PtrView P = view();
  while (true) {
    if (P.isBaseClass()) {
      const CXXRecordDecl *BaseRD = getRecordDecl(P.getBase());
      if (!ASTContext::hasLayout(BaseRD))
        return std::nullopt;
      const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(BaseRD);
      const CXXRecordDecl *RD = getRecordDecl(P);
      if (P.isVirtualBaseClass())
        Result += Layout.getVBaseClassOffset(RD).getQuantity();
      else
        Result += Layout.getBaseClassOffset(RD).getQuantity();

      if (P.isOnePastEnd())
        Result += getRecordSize(RD);

      P = P.getBase();
      continue;
    }

    if (P.isArrayElement()) {
      P = P.expand();
      assert(P.getFieldDesc()->isArray());
      if (std::optional<size_t> ElemSize =
              getTypeSize(P.getFieldDesc()->getElemQualType()))
        Result += *ElemSize * P.getIndex();
      else
        return std::nullopt;

      P = P.getArray();
      continue;
    }

    if (P.isRoot()) {
      if (P.isPastEnd() || P.isOnePastEnd()) {
        if (std::optional<size_t> Size =
                getTypeSize(P.getDeclDesc()->getType()))
          Result += *Size * P.getIndex();
        else
          return std::nullopt;
      }
      break;
    }

    assert(P.getField());
    const FieldDecl *F = P.getField();
    if (!ASTContext::hasLayout(F->getParent()))
      return std::nullopt;
    const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(F->getParent());
    Result +=
        ASTCtx.toCharUnitsFromBits(Layout.getFieldOffset(F->getFieldIndex()))
            .getQuantity();

    if (P.isPastEnd() || P.isOnePastEnd()) {
      if (std::optional<size_t> Size = getTypeSize(F->getType()))
        Result += *Size * P.getIndex();
      else
        return std::nullopt;
    }

    P = P.getBase();
    if (P.isRoot())
      break;
  }
  return Result;
}

std::string Pointer::toDiagnosticString(const ASTContext &Ctx) const {
  if (isZero())
    return "nullptr";

  if (isIntegralPointer())
    return (Twine("&(") + Twine(asIntPointer().Value + Offset) + ")").str();

  QualType Ty = getType();
  if (Ty->isLValueReferenceType())
    Ty = Ty->getPointeeType();
  return toAPValue(Ctx).getAsString(Ctx, Ty);
}

bool PtrView::isElementInitialized(unsigned Index) const {
  const Descriptor *Desc = getFieldDesc();
  assert(Desc);

  if (Pointee->isStatic() && Base == 0)
    return true;

  if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
    const auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
    return GD.InitState == GlobalInitState::Initialized;
  }

  if (Desc->isPrimitiveArray()) {
    InitMapPtr IM = getInitMap();

    if (IM.allInitialized())
      return true;

    if (!IM.hasInitMap())
      return false;
    return IM->isElementInitialized(Index);
  }
  return isInitialized();
}

bool Pointer::isElementAlive(unsigned Index) const {
  assert(getFieldDesc()->isPrimitiveArray());

  InitMapPtr &IM = getInitMap();
  if (!IM.hasInitMap())
    return true;

  if (IM.allInitialized())
    return true;

  return IM->isElementAlive(Index);
}

Lifetime PtrView::getLifetime() const {
  if (Base < sizeof(InlineDescriptor))
    return Lifetime::Started;

  if (inArray() && !isArrayRoot()) {
    InitMapPtr &IM = getInitMap();

    if (!IM.hasInitMap()) {
      if (IM.allInitialized())
        return Lifetime::Started;
      return getArray().getLifetime();
    }

    return IM->isElementAlive(getIndex()) ? Lifetime::Started : Lifetime::Ended;
  }

  return getInlineDesc()->LifeState;
}

void PtrView::setLifeState(Lifetime L) const {
  if (Base < sizeof(InlineDescriptor))
    return;

  if (inArray() && !isArrayRoot()) {
    assert(L == Lifetime::Started || L == Lifetime::Ended);
    const Descriptor *Desc = getFieldDesc();
    InitMapPtr &IM = getInitMap();
    if (!IM.hasInitMap())
      IM.setInitMap(new InitMap(Desc->getNumElems(), IM.allInitialized()));

    if (L == Lifetime::Ended)
      IM->endElementLifetime(getIndex());
    else if (L == Lifetime::Started)
      IM->startElementLifetime(getIndex());
    assert(isArrayRoot() || (this->getLifetime() == L));
    return;
  }

  getInlineDesc()->LifeState = L;
}

void PtrView::initialize() const {
  // FIXME: This happens when the control flow jumps right into a scope, e.g. in
  // switch_into_init_stmt in constant-expression-cxx2a.cpp. I.e. we have never
  // initialized the scope via an InitScope op.
  if (LLVM_UNLIKELY(!Pointee->isInitialized()))
    Pointee->invokeCtor();

  if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
    auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
    GD.InitState = GlobalInitState::Initialized;
    return;
  }

  const Descriptor *Desc = getFieldDesc();
  assert(Desc);
  if (Desc->isPrimitiveArray()) {
    if (Desc->getNumElems() != 0)
      initializeElement(getIndex());
    return;
  }

  // Field has its bit in an inline descriptor.
  assert(Base != 0 && "Only composite fields can be initialised");
  getInlineDesc()->IsInitialized = true;
  getInlineDesc()->LifeState = Lifetime::Started;
}

void PtrView::initializeElement(unsigned Index) const {
  // Primitive global arrays don't have an initmap.
  if (Pointee->isStatic() && Base == 0)
    return;

  assert(Index < getFieldDesc()->getNumElems());

  // FIXME: This happens when the control flow jumps right into a scope, e.g. in
  // switch_into_init_stmt in constant-expression-cxx2a.cpp. I.e. we have never
  // initialized the scope via an InitScope op.
  if (LLVM_UNLIKELY(!Pointee->isInitialized()))
    Pointee->invokeCtor();

  InitMapPtr &IM = getInitMap();
  if (IM.allInitialized())
    return;

  if (!IM.hasInitMap()) {
    const Descriptor *Desc = getFieldDesc();
    IM.setInitMap(new InitMap(Desc->getNumElems()));
  }
  assert(IM.hasInitMap());

  if (IM->initializeElement(Index))
    IM.noteAllInitialized();
}

void Pointer::initializeAllElements() const {
  assert(getFieldDesc()->isPrimitiveArray());
  assert(isArrayRoot());

  getInitMap().noteAllInitialized();
}

bool PtrView::allElementsInitialized() const {
  assert(getFieldDesc()->isPrimitiveArray());
  assert(isArrayRoot());

  if (Pointee->isStatic() && Base == 0)
    return true;

  if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
    const auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
    return GD.InitState == GlobalInitState::Initialized;
  }

  InitMapPtr IM = getInitMap();
  return IM.allInitialized();
}

bool Pointer::allElementsAlive() const {
  assert(getFieldDesc()->isPrimitiveArray());
  assert(isArrayRoot());

  if (isStatic() && BS.Base == 0)
    return true;

  if (isRoot() && BS.Base == sizeof(GlobalInlineDescriptor) &&
      Offset == BS.Base) {
    const auto &GD = block()->getBlockDesc<GlobalInlineDescriptor>();
    return GD.InitState == GlobalInitState::Initialized;
  }

  InitMapPtr &IM = getInitMap();
  return IM.allInitialized() || (IM.hasInitMap() && IM->allElementsAlive());
}

void PtrView::activate() const {
  // Field has its bit in an inline descriptor.
  assert(Base != 0 && "Only composite fields can be activated");

  if (isRoot() && Base == sizeof(GlobalInlineDescriptor))
    return;
  if (!getInlineDesc()->InUnion)
    return;

  std::function<void(PtrView P)> activate;
  activate = [&activate](PtrView P) -> void {
    P.getInlineDesc()->IsActive = true;
    P.startLifetime();
    if (const Record *R = P.getRecord(); R && !R->isUnion()) {
      for (const Record::Field &F : R->fields()) {
        PtrView FieldPtr = P.atField(F.Offset);
        if (!FieldPtr.getInlineDesc()->IsActive)
          activate(FieldPtr);
      }
      // FIXME: Bases?
    }
  };

  std::function<void(PtrView &)> deactivate;
  deactivate = [&deactivate](PtrView &P) -> void {
    P.getInlineDesc()->IsActive = false;

    if (const Record *R = P.getRecord()) {
      for (const Record::Field &F : R->fields()) {
        PtrView FieldPtr = P.atField(F.Offset);
        if (FieldPtr.getInlineDesc()->IsActive)
          deactivate(FieldPtr);
      }
      // FIXME: Bases?
    }
  };

  PtrView B = *this;
  // Primitive array elements can't be activated individually, so
  // look at the array root instead.
  if (B.getFieldDesc()->isPrimitiveArray() && B.isArrayElement())
    B = B.getArray();

  while (!B.isRoot() && B.inUnion()) {
    activate(B);

    // When walking up the pointer chain, deactivate
    // all union child pointers that aren't on our path.
    PtrView Cur = B;
    B = B.getBase();
    if (const Record *BR = B.getRecord(); BR && BR->isUnion()) {
      for (const Record::Field &F : BR->fields()) {
        PtrView FieldPtr = B.atField(F.Offset);
        if (FieldPtr != Cur)
          deactivate(FieldPtr);
      }
    }
  }
}

bool Pointer::hasSameBase(const Pointer &A, const Pointer &B) {
  // Two null pointers always have the same base.
  if (A.isZero() && B.isZero())
    return true;

  // We allow comparisons between opaque pointers and block pointers, provided
  // they have the same declaration as base.
  if (A.StorageKind != B.StorageKind) {
    if (A.isOpaquePointer() && A.Opaque.Base.isVarDecl() &&
        B.isBlockPointer()) {
      if (const VarDecl *BDecl = B.block()->getDescriptor()->asVarDecl())
        return BDecl == A.Opaque.Base.asVarDecl()->getMostRecentDecl();
      return false;
    }
    if (B.isOpaquePointer() && B.Opaque.Base.isVarDecl() &&
        A.isBlockPointer()) {
      if (const VarDecl *ADecl = A.block()->getDescriptor()->asVarDecl())
        return ADecl == B.Opaque.Base.asVarDecl()->getMostRecentDecl();
      return false;
    }
    return false;
  }

  switch (A.StorageKind) {
  case Storage::Int:
    return true;
  case Storage::Block:
    return A.BS.Pointee == B.BS.Pointee;
  case Storage::Fn:
    return true;
  case Storage::Typeid:
    return A.asTypeidPointer().TypePtr == B.asTypeidPointer().TypePtr;
  case Storage::String:
    return A.Str.ID == B.Str.ID && A.Str.getLiteral() == B.Str.getLiteral();
  case Storage::Opaque:
    if (A.Opaque.Base.isExpr())
      return B.Opaque.Base.isExpr() && A.Opaque.Base == B.Opaque.Base;
    if (A.Opaque.Base.isVarDecl())
      return B.Opaque.Base.isVarDecl() &&
             A.Opaque.Base.asVarDecl()->getMostRecentDecl() ==
                 B.Opaque.Base.asVarDecl()->getMostRecentDecl();
    return false;
  }
  llvm_unreachable("should have been handled by the fully covered switch");
}

bool Pointer::pointToSameBlock(const Pointer &A, const Pointer &B) {
  if (!A.isBlockPointer() || !B.isBlockPointer())
    return false;
  return A.block() == B.block();
}

bool Pointer::elemsOfSameArray(const Pointer &A, const Pointer &B) {
  assert(hasSameBase(A, B));
  assert(A.isBlockPointer());
  assert(B.isBlockPointer());

  if (A.BS.Base == B.BS.Base)
    return true;

  if (A.isBaseClass() || B.isBaseClass())
    return false;

  if (A.getField() || B.getField())
    return false;

  auto closestArray = [](const Pointer &P) -> PtrView {
    if (P.isArrayRoot())
      return P.view();

    PtrView V = P.view();
    if (V.isArrayElement() || V.isOnePastEnd())
      V = V.expand().getArray();

    if (P.isRoot())
      return P.view();

    while (!V.isRoot() && !V.getFieldDesc()->IsArray) {
      if (V.isArrayElement()) {
        V = V.expand().getArray();
        break;
      }
      V = V.getBase();
    }
    return V;
  };

  if (closestArray(A) != closestArray(B))
    return false;

  return true;
}

// FIXME: This should return true for string pointers.
bool Pointer::pointsToLiteral() const {
  if (isZero())
    return false;

  if (isDynamic())
    return false;

  const Expr *E = getRootExpr();
  return E && !isa<MaterializeTemporaryExpr, StringLiteral>(E);
}

bool Pointer::pointsToLabel() const {
  if (isZero())
    return false;

  if (isOpaquePointer())
    return isa_and_nonnull<AddrLabelExpr>(Opaque.Base.asExpr());
  return false;
}

std::optional<std::pair<PtrView, PtrView>>
Pointer::computeSplitPoint(const Pointer &A, const Pointer &B) {
  if (!A.isBlockPointer() || !B.isBlockPointer())
    return std::nullopt;

  if (A.asBlockPointer().Pointee != B.asBlockPointer().Pointee)
    return std::nullopt;
  if (A.isRoot() && B.isRoot())
    return std::nullopt;

  if (A == B)
    return std::make_pair(A.view(), B.view());

  auto getBase = [](PtrView P) -> PtrView {
    if (P.isArrayElement())
      return P.expand().getArray();
    return P.getBase();
  };

  PtrView IterA = A.view();
  PtrView IterB = B.view();
  PtrView CurA = IterA;
  PtrView CurB = IterB;
  for (;;) {
    if (IterA.Base > IterB.Base) {
      CurA = IterA;
      IterA = getBase(IterA);
    } else {
      CurB = IterB;
      IterB = getBase(IterB);
    }

    if (IterA == IterB) {
      // If the Iter is an array, CurA and CurB are both elements of the same
      // array. That is fine, so return nullopt.
      if (IterA.getFieldDesc()->isArray())
        return std::nullopt;
      return std::make_pair(CurA, CurB);
    }

    if (IterA.isRoot() && IterB.isRoot())
      return std::nullopt;
  }

  llvm_unreachable("The loop above should've returned.");
}

/// Convert a pointer to a composite value to an rvalue.
static bool toRValue(const Context &Ctx, QualType Ty, PtrView Ptr, APValue &R) {
  const ASTContext &ASTCtx = Ctx.getASTContext();
  if (const auto *AT = Ty->getAs<AtomicType>())
    Ty = AT->getValueType();

  // Invalid pointers.
  if (!Ptr.isLive() || Ptr.isPastEnd())
    return false;

  // Primitives should never end up here.
  assert(!Ctx.canClassify(Ty));
  const Descriptor *FieldDesc = Ptr.getFieldDesc();
  assert(FieldDesc);

  if (const auto *RT = Ty->getAsCanonical<RecordType>()) {
    if (!FieldDesc->isRecord())
      return false;
    const auto *Record = Ptr.getRecord();
    assert(Record && "Missing record descriptor");

    bool Ok = true;
    if (RT->getDecl()->isUnion()) {
      const FieldDecl *ActiveField = nullptr;
      APValue Value;
      for (const auto &F : Record->fields()) {
        PtrView FP = Ptr.atField(F.Offset);
        if (FP.isActive()) {
          const Descriptor *Desc = F.Desc;
          if (Desc->isPrimitive()) {
            TYPE_SWITCH(Desc->getPrimType(),
                        Value = FP.deref<T>().toAPValue(ASTCtx));
          } else {
            QualType FieldTy = F.Decl->getType();
            Ok &= toRValue(Ctx, FieldTy, FP, Value);
          }
          ActiveField = FP.getFieldDesc()->asFieldDecl();
          break;
        }
      }
      R = APValue(ActiveField, Value);
    } else {
      unsigned NF = Record->getNumFields();
      unsigned NB = Record->getNumBases();
      unsigned NV = Ptr.isBaseClass() ? 0 : Record->getNumVirtualBases();

      R = APValue(APValue::UninitStruct(), NB, NF, NV);

      for (unsigned I = 0; I != NF; ++I) {
        const Record::Field *FD = Record->getField(I);
        const Descriptor *Desc = FD->Desc;
        PtrView FP = Ptr.atField(FD->Offset);
        APValue &Value = R.getStructField(I);
        if (Desc->isPrimitive()) {
          TYPE_SWITCH(Desc->getPrimType(),
                      Value = FP.deref<T>().toAPValue(ASTCtx));
        } else {
          QualType FieldTy = FD->Decl->getType();
          Ok &= toRValue(Ctx, FieldTy, FP, Value);
        }
      }

      for (unsigned I = 0; I != NB; ++I) {
        const Record::Base *BD = Record->getBase(I);
        QualType BaseTy = Ctx.getASTContext().getCanonicalTagType(BD->Decl);
        PtrView BP = Ptr.atField(BD->Offset);
        Ok &= toRValue(Ctx, BaseTy, BP, R.getStructBase(I));
      }

      for (unsigned I = 0; I != NV; ++I) {
        const Record::Base *VD = Record->getVirtualBase(I);
        assert(VD);
        QualType VirtBaseTy = Ctx.getASTContext().getCanonicalTagType(VD->Decl);
        PtrView VP = Ptr.atField(VD->Offset);
        Ok &= toRValue(Ctx, VirtBaseTy, VP, R.getStructVirtualBase(I));
      }
    }
    return Ok;
  }

  if (Ty->isIncompleteArrayType()) {
    R = APValue(APValue::UninitArray(), 0, 0);
    return true;
  }

  if (const auto *AT = Ty->getAsArrayTypeUnsafe()) {
    if (!FieldDesc->isArray())
      return false;
    const size_t NumElems = Ptr.getNumElems();
    QualType ElemTy = AT->getElementType();
    R = APValue(APValue::UninitArray{}, NumElems, NumElems);

    bool Ok = true;
    OptPrimType ElemT = Ctx.classify(ElemTy);
    for (unsigned I = 0; I != NumElems; ++I) {
      APValue &Slot = R.getArrayInitializedElt(I);
      if (ElemT) {
        TYPE_SWITCH(*ElemT, Slot = Ptr.elem<T>(I).toAPValue(ASTCtx));
      } else {
        Ok &= toRValue(Ctx, ElemTy, Ptr.atIndex(I).narrow(), Slot);
      }
    }
    return Ok;
  }

  // Complex types.
  if (Ty->isAnyComplexType()) {
    // Can happen via C casts.
    if (!FieldDesc->getType()->isAnyComplexType())
      return false;

    PrimType ElemT = FieldDesc->getPrimType();
    if (isIntegerOrBoolType(ElemT)) {
      INT_TYPE_SWITCH(ElemT, {
        auto V1 = Ptr.elem<T>(0);
        auto V2 = Ptr.elem<T>(1);
        R = APValue(V1.toAPSInt(), V2.toAPSInt());
        return true;
      });
    } else if (ElemT == PT_Float) {
      R = APValue(Ptr.elem<Floating>(0).getAPFloat(),
                  Ptr.elem<Floating>(1).getAPFloat());
      return true;
    }
    return false;
  }

  // Vector types.
  if (const auto *VT = Ty->getAs<VectorType>()) {
    if (!FieldDesc->isPrimitiveArray())
      return false;

    PrimType ElemT = FieldDesc->getPrimType();
    SmallVector<APValue> Values;
    Values.reserve(VT->getNumElements());
    for (unsigned I = 0; I != VT->getNumElements(); ++I) {
      TYPE_SWITCH(ElemT,
                  { Values.push_back(Ptr.elem<T>(I).toAPValue(ASTCtx)); });
    }

    assert(Values.size() == VT->getNumElements());
    R = APValue(Values.data(), Values.size());
    return true;
  }

  // Constant Matrix types.
  if (const auto *MT = Ty->getAs<ConstantMatrixType>()) {
    if (!FieldDesc->isPrimitiveArray())
      return false;
    PrimType ElemT = FieldDesc->getPrimType();
    unsigned NumElems = MT->getNumElementsFlattened();

    SmallVector<APValue> Values;
    Values.reserve(NumElems);
    for (unsigned I = 0; I != NumElems; ++I) {
      TYPE_SWITCH(ElemT,
                  { Values.push_back(Ptr.elem<T>(I).toAPValue(ASTCtx)); });
    }

    R = APValue(Values.data(), MT->getNumRows(), MT->getNumColumns());
    return true;
  }

  llvm_unreachable("invalid value to return");
}

std::optional<APValue> Pointer::toRValue(const Context &Ctx,
                                         QualType ResultType) const {
  const ASTContext &ASTCtx = Ctx.getASTContext();
  assert(!ResultType.isNull());

  // Can't return functions as rvalues.
  if (ResultType->isFunctionType())
    return std::nullopt;

  // Invalid to read from.
  if (isDummy() || !isLive() || isPastEnd() ||
      (isOnePastEnd() && !isZeroSizeArray()))
    return std::nullopt;

  // We can return these as rvalues, but we can't deref() them.
  if (isZero() || isIntegralPointer())
    return toAPValue(ASTCtx);

  // Just load primitive types.
  if (OptPrimType T = Ctx.classify(ResultType)) {
    if (!canDeref(*T))
      return std::nullopt;
    TYPE_SWITCH(*T, return this->load<T>().toAPValue(ASTCtx));
  }

  if (!isBlockPointer())
    return std::nullopt;

  // Return the composite type.
  APValue Result;
  if (!::toRValue(Ctx, ResultType, view(), Result))
    return std::nullopt;
  return Result;
}

const VarDecl *Pointer::getRootVarDecl() const {
  return dyn_cast_if_present<VarDecl>(getRootValueDecl());
}

const ValueDecl *Pointer::getRootValueDecl() const {
  if (isBlockPointer())
    return getDeclDesc()->asValueDecl();
  if (isOpaquePointer())
    return Opaque.getBaseDecl();
  return nullptr;
}

const Expr *Pointer::getRootExpr() const {
  if (isBlockPointer())
    return getDeclDesc()->asExpr();
  if (isStringPointer())
    return Str.getLiteral();
  if (isOpaquePointer())
    return Opaque.getBaseExpr();
  return nullptr;
}

std::optional<IntPointer> IntPointer::atOffset(const interp::Context &Ctx,
                                               unsigned Offset) const {
  QualType CurType = getPointeeType();
  if (CurType.isNull() || !CurType->isRecordType())
    return std::nullopt;

  const Record *R = Ctx.getRecord(CurType->getAsRecordDecl());
  if (!R)
    return *this;

  const Record::Field *F = R->findField(Offset);
  if (!F)
    return *this;

  const FieldDecl *FD = F->Decl;
  if (FD->getParent()->isInvalidDecl())
    return std::nullopt;

  const ASTContext &ASTCtx = Ctx.getASTContext();
  const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(FD->getParent());
  unsigned FieldIndex = FD->getFieldIndex();
  uint64_t FieldOffset =
      ASTCtx.toCharUnitsFromBits(Layout.getFieldOffset(FieldIndex))
          .getQuantity();

  uint64_t NewValue = this->Value + FieldOffset;
  return IntPointer{{FD->getType().getTypePtr(), NewValue == 0}, NewValue};
}

IntPointer IntPointer::baseCast(const interp::Context &Ctx,
                                unsigned BaseOffset) const {
  if (!getType())
    return *this;

  QualType CurType = getPointeeType();
  if (CurType.isNull() || !CurType->isRecordType())
    return *this;

  // null pointers stay null during a cast, per conv.ptr
  if (Value == 0)
    return *this;

  const Record *R = Ctx.getRecord(CurType->getAsRecordDecl());

  // This iterates over bases and checks for the proper offset. That's
  // potentially slow but this case really shouldn't happen a lot.
  const Record::Base *B = R->findBase(BaseOffset);
  if (!B)
    return *this;

  const Descriptor *BaseDesc = B->Desc;
  // Adjust the offset value based on the information from the record layout.
  const ASTContext &ASTCtx = Ctx.getASTContext();
  const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(R->getDecl());
  CharUnits BaseLayoutOffset =
      Layout.getBaseClassOffset(cast<CXXRecordDecl>(BaseDesc->asDecl()));

  const RecordDecl *RD = BaseDesc->ElemRecord->getDecl();
  QualType T = RD->getASTContext().getTagType(ElaboratedTypeKeyword::None,
                                              std::nullopt, RD, false);
  uint64_t NewValue = Value + BaseLayoutOffset.getQuantity();
  return {{T.getTypePtr(), NewValue == 0}, NewValue};
}

std::optional<size_t>
OpaquePointer::computeLayoutOffset(const ASTContext &ASTCtx) const {
  size_t Offset = 0;
  QualType CurType = getObjectType();
  for (const PointerPathEntry &Entry : path()) {
    switch (Entry.Kind) {
    case PointerPathEntry::Base: {
      const CXXRecordDecl *RD = CurType->getAsCXXRecordDecl();
      if (!ASTContext::hasLayout(RD))
        return std::nullopt;

      const CXXRecordDecl *BaseDecl = Entry.RD.getPointer();
      if (!RD->isDerivedFrom(BaseDecl))
        return std::nullopt;

      const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(RD);
      if (Entry.RD.getInt())
        Offset += Layout.getVBaseClassOffset(BaseDecl).getQuantity();
      else
        Offset += Layout.getBaseClassOffset(BaseDecl).getQuantity();

      CurType = ASTCtx.getCanonicalTagType(BaseDecl);
    } break;

    case PointerPathEntry::Field: {
      const FieldDecl *FD = Entry.FD;
      const RecordDecl *RD = FD->getParent();
      if (!ASTContext::hasLayout(RD))
        return std::nullopt;

      const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(RD);
      Offset +=
          ASTCtx.toCharUnitsFromBits(Layout.getFieldOffset(FD->getFieldIndex()))
              .getQuantity();

      CurType = FD->getType();
    } break;
    case PointerPathEntry::Array:
    case PointerPathEntry::NegativeArray: {
      bool Add = (Entry.Kind == PointerPathEntry::Array);
      uint64_t Index = Entry.Index;
      if (!CurType->isArrayType()) {
        if (Add)
          Offset += Index * ASTCtx.getTypeSizeInChars(CurType).getQuantity();
        else
          Offset -= Index * ASTCtx.getTypeSizeInChars(CurType).getQuantity();
        continue;
      }
      const ArrayType *AT = CurType->getAsArrayTypeUnsafe();
      assert(AT);
      QualType ElemTy = AT->getElementType();
      if (!validType(ElemTy) || isa<VariableArrayType>(AT))
        return std::nullopt;
      if (Add)
        Offset += Index * ASTCtx.getTypeSizeInChars(ElemTy).getQuantity();
      else
        Offset -= Index * ASTCtx.getTypeSizeInChars(ElemTy).getQuantity();
      CurType = AT->getElementType();
    } break;
    }
  }

  return Offset;
}

QualType OpaquePointer::getSurroundingArray() const {
  if (PathLength == 0)
    return getObjectType();
  if (Path[PathLength - 1].Kind != PointerPathEntry::Array)
    return getFieldType();

  assert(Path[PathLength - 1].Kind == PointerPathEntry::Array);
  assert(isArrayElement());

  QualType CurType = getObjectType();
  for (const PointerPathEntry &Entry : path().drop_back(1)) {
    switch (Entry.Kind) {
    case PointerPathEntry::Base:
      CurType = Entry.RD.getPointer()->getASTContext().getCanonicalTagType(
          Entry.RD.getPointer());
      break;
    case PointerPathEntry::Field:
      CurType = Entry.FD->getType();
      break;
    case PointerPathEntry::Array:
    case PointerPathEntry::NegativeArray:
      if (!CurType->isArrayType())
        break;
      CurType = CurType->getAsArrayTypeUnsafe()->getElementType();
    }
  }
  return CurType;
}

/// Check if the pointer has offset 0.
// As an optimization, don't actually compute the offset.
bool OpaquePointer::isRoot() const {
  QualType CurType = getObjectType();
  for (const PointerPathEntry &Entry : path()) {
    switch (Entry.Kind) {
    case PointerPathEntry::Base:
      if (Entry.RD.getInt())
        return false;
      CurType = Entry.RD.getPointer()->getASTContext().getCanonicalTagType(
          Entry.RD.getPointer());
      break;
    case PointerPathEntry::Field:
      if (!Entry.FD->getParent()->isUnion() && Entry.FD->getFieldIndex() != 0)
        return false;
      CurType = Entry.FD->getType();
      break;
    case PointerPathEntry::Array:
      if (Entry.Index != 0)
        return false;
      if (!CurType->isArrayType())
        continue;
      CurType = CurType->getAsArrayTypeUnsafe()->getElementType();
      break;
    case PointerPathEntry::NegativeArray:
      return false;
    }
  }
  return true;
}

bool OpaquePointer::isUnknownSizeArray() const {
  QualType FieldType = getFieldType();

  if (isArrayElement())
    FieldType = getSurroundingArray();

  bool Result = false;
  // If the field type is an IncompleteArrayType, we still need to check the
  // base to see if this array is a flexible array member _and_ has actually
  // been initialized by data we know the size of.
  if (isa<IncompleteArrayType>(FieldType)) {
    const VarDecl *Base = this->Base.asVarDecl();
    if (!Base || !Base->getType()->isRecordType() || !Base->hasInit())
      Result = true;
    else
      Result = !Base->hasFlexibleArrayInit(Base->getASTContext());
  } else if (isa<VariableArrayType>(FieldType))
    Result = true;

  return Result;
}

/// This is used in Pointer::isOnePastEnd(). We cannot read from such pointers.
/// We can of course never read from opaque pointers anyway but we diagnose
/// one-past-the-end pointers differently.
///
/// In contrast, OpaquePointer::isOnePastEnd() only uses the past-end bit. That
/// is used for the APValue conversion.
bool OpaquePointer::isOnePastEndOrElementPastEnd() const {
  if (isOnePastEnd())
    return true;

  if (PathLength == 0)
    return false;

  if (Path[PathLength - 1].Kind != PointerPathEntry::Array)
    return false;

  QualType ArrTy = getSurroundingArray();
  if (!ArrTy->isArrayType())
    return false;
  // FIXME: Flexible array members?
  if (const auto *CAT =
          dyn_cast<ConstantArrayType>(ArrTy->getAsArrayTypeUnsafe())) {
    if (Path[PathLength - 1].Index >= CAT->getZExtSize())
      return true;
  }

  return false;
}

bool OpaquePointer::hasValidBase() const {
  if (const VarDecl *VD = Base.asVarDecl())
    return !VD->hasExternalStorage();

  return !Base.getType()->isPointerType();
}