// SPDX-License-Identifier: Apache-2.0

// SPDX-FileCopyrightText: Copyright The WasmEdge Authors

#include "validator/formchecker.h"

#include "common/errinfo.h"

#include <array>

#include <cstdint>

#include <tuple>

using namespace std::literals;

namespace WasmEdge {

namespace Validator {

namespace {

// Helper function for printing an error log for an index out of range.

auto logOutOfRange(ErrCode Code, ErrInfo::IndexCategory Cate, uint32_t Idx,

                   uint32_t Bound) {

  spdlog::error(Code);

  spdlog::error(ErrInfo::InfoForbidIndex(Cate, Idx, Bound));

  return Unexpect(Code);

}

// Helper function for extracting address type to TypeCode.

TypeCode convAddrTypeToTypeCode(const AddressType AT) noexcept {

  switch (AT) {

  case AddressType::I32:

    return TypeCode::I32;

  case AddressType::I64:

    return TypeCode::I64;

  default:

    assumingUnreachable();

  }

};

// Helper function for packing TypeCode to address type.

AddressType convTypeCodeToAddrType(const TypeCode TC) noexcept {

  switch (TC) {

  case TypeCode::I32:

    return AddressType::I32;

  case TypeCode::I64:

    return AddressType::I64;

  default:

    assumingUnreachable();

  }

};

} // namespace

void FormChecker::reset(bool CleanGlobal) {

  ValStack.clear();

  CtrlStack.clear();

  Locals.clear();

  Returns.clear();

  if (CleanGlobal) {

    Types.clear();

    Funcs.clear();

    Tables.clear();

    Mems.clear();

    Globals.clear();

    Datas.clear();

    Elems.clear();

    Refs.clear();

    Tags.clear();

    NumImportFuncs = 0;

    NumImportGlobals = 0;

  }

}

Expect<void> FormChecker::validate(AST::InstrView Instrs,

                                   Span<const ValType> RetVals) {

  for (const ValType &Val : RetVals) {

    Returns.push_back(Val);

  }

  return checkExpr(Instrs);

}

Expect<void> FormChecker::validate(const ValType &VT) const noexcept {

  // The value type should be validated for the type index case.

  if (VT.isRefType() && VT.getHeapTypeCode() == TypeCode::TypeIndex) {

    if (VT.getTypeIndex() >= Types.size()) {

      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);

      spdlog::error(ErrInfo::InfoForbidIndex(

          ErrInfo::IndexCategory::FunctionType, VT.getTypeIndex(),

          static_cast<uint32_t>(Types.size())));

      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);

    }

  }

  return {};

}

void FormChecker::addType(const AST::SubType &Type) { Types.push_back(&Type); }

void FormChecker::addFunc(const uint32_t TypeIdx, const bool IsImport) {

  if (Types.size() > TypeIdx) {

    Funcs.emplace_back(TypeIdx);

  }

  if (IsImport) {

    NumImportFuncs++;

  }

}

void FormChecker::addTable(const AST::TableType &Tab) {

  Tables.emplace_back(convAddrTypeToTypeCode(Tab.getLimit().getAddrType()),

                      Tab.getRefType());

}

void FormChecker::addMemory(const AST::MemoryType &Mem) {

  Mems.push_back(convAddrTypeToTypeCode(Mem.getLimit().getAddrType()));

}

void FormChecker::addGlobal(const AST::GlobalType &Glob, const bool IsImport) {

  // The global type is confirmed in the loading phase.

  Globals.emplace_back(Glob.getValType(), Glob.getValMut());

  if (IsImport) {

    NumImportGlobals++;

  }

}

void FormChecker::addData(const AST::DataSegment &) {

  Datas.emplace_back(static_cast<uint32_t>(Datas.size()));

}

void FormChecker::addElem(const AST::ElementSegment &Elem) {

  Elems.emplace_back(Elem.getRefType());

}

void FormChecker::addRef(const uint32_t FuncIdx) { Refs.emplace(FuncIdx); }

void FormChecker::addLocal(const ValType &V, bool Initialized) {

  Locals.emplace_back(V);

  if (Initialized || V.isDefaultable()) {

    LocalInits.push_back(static_cast<uint32_t>(Locals.size() - 1));

    Locals.back().IsInit = true;

  }

}

void FormChecker::addTag(const uint32_t TypeIdx) { Tags.push_back(TypeIdx); }

ValType FormChecker::VTypeToAST(const VType &V) {

  if (!V) {

    return TypeCode::I32;

  }

  return *V;

}

Expect<void> FormChecker::checkExpr(AST::InstrView Instrs) {

  if (Instrs.size() > 0) {

    // Push ctrl frame ([] -> [Returns])

    pushCtrl({}, Returns, &*Instrs.rbegin());

    return checkInstrs(Instrs);

  }

  return {};

}

Expect<void> FormChecker::checkInstrs(AST::InstrView Instrs) {

  // Validate instructions

  for (auto &Instr : Instrs) {

    EXPECTED_TRY(checkInstr(Instr).map_error([&Instr](auto E) {

      spdlog::error(

          ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));

      return E;

    }));

  }

  return {};

}

Expect<void> FormChecker::checkInstr(const AST::Instruction &Instr) {

  // Note: The instructions and their immediates have passed proposal

  // configuration checking in the loader phase.

  // Helper lambda for checking whether the table index is valid.

  auto checkTableIdx = [this](const uint32_t Idx) -> Expect<void> {

    if (unlikely(Idx >= Tables.size())) {

      return logOutOfRange(ErrCode::Value::InvalidTableIdx,

                           ErrInfo::IndexCategory::Table, Idx,

                           static_cast<uint32_t>(Tables.size()));

    }

    return {};

  };

  // Helper lambda for checking whether the memory index is valid.

  auto checkMemIdx = [this](const uint32_t Idx) -> Expect<void> {

    if (unlikely(Idx >= Mems.size())) {

      return logOutOfRange(ErrCode::Value::InvalidMemoryIdx,

                           ErrInfo::IndexCategory::Memory, Idx,

                           static_cast<uint32_t>(Mems.size()));

    }

    return {};

  };

  // Helper lambda for checking whether the data index is valid.

  auto checkDataIdx = [this](const uint32_t Idx) -> Expect<void> {

    if (unlikely(Idx >= Datas.size())) {

      return logOutOfRange(ErrCode::Value::InvalidDataIdx,

                           ErrInfo::IndexCategory::Data, Idx,

                           static_cast<uint32_t>(Datas.size()));

    }

    return {};

  };

  // Helper lambda for checking whether the element index is valid.

  auto checkElemIdx = [this](const uint32_t Idx) -> Expect<void> {

    if (unlikely(Idx >= Elems.size())) {

      return logOutOfRange(ErrCode::Value::InvalidElemIdx,

                           ErrInfo::IndexCategory::Element, Idx,

                           static_cast<uint32_t>(Elems.size()));

    }

    return {};

  };

  // Helper lambda for checking whether the tag index is valid.

  auto checkTagIdx = [this](const uint32_t Idx) -> Expect<void> {

    if (unlikely(Idx >= Tags.size())) {

      return logOutOfRange(ErrCode::Value::InvalidTagIdx,

                           ErrInfo::IndexCategory::Tag, Idx,

                           static_cast<uint32_t>(Tags.size()));

    }

    return {};

  };

  // Helper lambda for checking the defined type.

  auto checkDefinedType =

      [this](uint32_t TIdx, TypeCode TC) -> Expect<const AST::CompositeType *> {

    if (TIdx >= Types.size()) {

      return logOutOfRange(ErrCode::Value::InvalidFuncTypeIdx,

                           ErrInfo::IndexCategory::FunctionType, TIdx,

                           static_cast<uint32_t>(Types.size()));

    }

    const auto &CType = Types[TIdx]->getCompositeType();

    if (CType.getContentTypeCode() == TC) {

      return &CType;

    } else {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

  };

  // Helper lambda for checking and resolving the block type.

  auto checkBlockType = [this, checkDefinedType](std::vector<ValType> &Buffer,

                                                 const BlockType &BType)

      -> Expect<std::pair<Span<const ValType>, Span<const ValType>>> {

    using ReturnType = std::pair<Span<const ValType>, Span<const ValType>>;

    if (BType.isEmpty()) {

      // Empty case. t2* = none

      return ReturnType{{}, {}};

    } else if (BType.isValType()) {

      // ValType case. t2* = valtype

      EXPECTED_TRY(validate(BType.getValType()));

      Buffer[0] = BType.getValType();

      return ReturnType{{}, Buffer};

    } else {

      // Type index case. t2* = functype.returns.

      EXPECTED_TRY(auto CompType,

                   checkDefinedType(BType.getTypeIndex(), TypeCode::Func));

      const auto &FType = CompType->getFuncType();

      return ReturnType{FType.getParamTypes(), FType.getReturnTypes()};

    }

  };

  // Helper lambda for checking control stack depth and return index.

  auto checkCtrlStackDepth = [this](uint32_t N) -> Expect<uint32_t> {

    // Check the control stack for at least N + 1 frames.

    if (N >= CtrlStack.size()) {

      // Branch out of the stack.

      return logOutOfRange(ErrCode::Value::InvalidLabelIdx,

                           ErrInfo::IndexCategory::Label, N,

                           static_cast<uint32_t>(CtrlStack.size()));

    }

    // Return the index of the N-th element from the end.

    return static_cast<uint32_t>(CtrlStack.size()) - UINT32_C(1) - N;

  };

  // Helper lambda for checking lane index and performing transformation.

  auto checkLaneAndTrans = [this,

                            &Instr](uint32_t N, Span<const ValType> Take,

                                    Span<const ValType> Put) -> Expect<void> {

    if (Instr.getMemoryLane() >= N) {

      return logOutOfRange(ErrCode::Value::InvalidLaneIdx,

                           ErrInfo::IndexCategory::Lane, Instr.getMemoryLane(),

                           N);

    }

    return StackTrans(Take, Put);

  };

  // Helper lambda for checking memory alignment and performing transformation.

  auto checkMemArgAndTrans = [this, checkMemIdx,

                              &Instr](uint32_t N, Span<const ValType> Take,

                                      Span<const ValType> Put,

                                      bool CheckLane = false) -> Expect<void> {

    // The first arg is always `addr_type`, representing the memory offset.

    // This helper will automatically add the first arg, therefore the caller

    // should set the input type list without the memory offset arg.

    // Check the memory index and get the address type.

    EXPECTED_TRY(checkMemIdx(Instr.getTargetIndex()));

    // Check the alignment.

    auto IsAtomic = Instr.getOpCode() >= OpCode::Memory__atomic__notify &&

                    Instr.getOpCode() <= OpCode::I64__atomic__rmw32__cmpxchg_u;

    if (Instr.getMemoryAlign() > 31 ||

        (!IsAtomic && (1UL << Instr.getMemoryAlign()) > (N >> 3UL))) {

      // 2 ^ align must be <= N / 8.

      spdlog::error(ErrCode::Value::AlignmentTooLarge);

      spdlog::error(ErrInfo::InfoMismatch(static_cast<uint8_t>(N >> 3),

                                          Instr.getMemoryAlign()));

      return Unexpect(ErrCode::Value::AlignmentTooLarge);

    }

    if (IsAtomic && (1UL << Instr.getMemoryAlign()) != (N >> 3UL)) {

      // 2 ^ align must be == N / 8.

      spdlog::error(ErrCode::Value::InvalidAlignment);

      spdlog::error(ErrInfo::InfoMismatch(static_cast<uint8_t>(N >> 3),

                                          Instr.getMemoryAlign()));

      return Unexpect(ErrCode::Value::InvalidAlignment);

    }

    // Check the memory offset validation.

    auto ATCode = Mems[Instr.getTargetIndex()];

    if (Instr.getMemoryOffset() >

        getMaxAddress(convTypeCodeToAddrType(ATCode))) {

      spdlog::error(ErrCode::Value::InvalidOffset);

      return Unexpect(ErrCode::Value::InvalidOffset);

    }

    // Check the memory lane if needed.

    if (CheckLane && Instr.getMemoryLane() >= 128 / N) {

      return logOutOfRange(ErrCode::Value::InvalidLaneIdx,

                           ErrInfo::IndexCategory::Lane, Instr.getMemoryLane(),

                           128 / N);

    }

    // Perform the stack change. Additionally pop the first arg (address type).

    EXPECTED_TRY(popTypes(Take));

    EXPECTED_TRY(popType(ATCode));

    pushTypes(Put);

    return {};

  };

  // Helper lambda for checking value type matching.

  auto checkTypesMatching = [this](Span<const ValType> Exp,

                                   Span<const ValType> Got) -> Expect<void> {

    if (!AST::TypeMatcher::matchTypes(Types, Exp, Got)) {

      std::vector<ValType> ExpV(Exp.begin(), Exp.end()),

          GotV(Got.begin(), Got.end());

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(ExpV, GotV));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    return {};

  };

  // Helper lambda for recording jump data.

  auto recordJump = [this, &Instr](AST::Instruction::JumpDescriptor &Jump,

                                   uint32_t Arity, uint32_t D) -> void {

    const uint32_t Remain =

        static_cast<uint32_t>(ValStack.size() - CtrlStack[D].Height);

    Jump.StackEraseBegin = Remain + Arity;

    Jump.StackEraseEnd = Arity;

    Jump.PCOffset = static_cast<int32_t>(CtrlStack[D].Jump - &Instr);

  };

  // Helper lambda for unpacking a value type.

  auto unpackType = [](const ValType &T) -> ValType {

    if (T.isPackType()) {

      return ValType(TypeCode::I32);

    }

    return T;

  };

  // Helper lambda for downcasting into the top heap type.

  auto toTopHeapType = [this](const ValType &T) -> ValType {

    assuming(T.isRefType());

    if (T.isAbsHeapType()) {

      switch (T.getHeapTypeCode()) {

      case TypeCode::NullFuncRef:

      case TypeCode::FuncRef:

        return TypeCode::FuncRef;

      case TypeCode::NullExternRef:

      case TypeCode::ExternRef:

        return TypeCode::ExternRef;

      case TypeCode::NullExnRef:

      case TypeCode::ExnRef:

        return TypeCode::ExnRef;

      case TypeCode::NullRef:

      case TypeCode::AnyRef:

      case TypeCode::EqRef:

      case TypeCode::I31Ref:

      case TypeCode::StructRef:

      case TypeCode::ArrayRef:

        return TypeCode::AnyRef;

      default:

        assumingUnreachable();

      }

    } else {

      const auto &CompType = Types[T.getTypeIndex()]->getCompositeType();

      if (CompType.isFunc()) {

        return TypeCode::FuncRef;

      } else {

        return TypeCode::AnyRef;

      }

    }

  };

  switch (Instr.getOpCode()) {

  // Control instructions.

  case OpCode::Unreachable:

    return unreachable();

  case OpCode::Nop:

    return {};

  case OpCode::Block:

  case OpCode::Loop:

  case OpCode::If:

  case OpCode::Try_table: {

    // Get blocktype [t1*] -> [t2*] and check valtype first.

    std::vector<ValType> Buffer(1);

    const auto &BType = (Instr.getOpCode() == OpCode::Try_table)

                            ? Instr.getTryCatch().ResType

                            : Instr.getBlockType();

    EXPECTED_TRY(auto T1T2, checkBlockType(Buffer, BType));

    auto [T1, T2] = T1T2;

    // For the if instruction, pop I32 first.

    if (Instr.getOpCode() == OpCode::If) {

      EXPECTED_TRY(popType(TypeCode::I32));

    }

    // Pop and check [t1*]

    EXPECTED_TRY(popTypes(T1));

    // For the try_table instruction, validate the handlers.

    if (Instr.getOpCode() == OpCode::Try_table) {

      const auto &TryDesc = Instr.getTryCatch();

      const_cast<AST::Instruction::TryDescriptor &>(TryDesc).BlockParamNum =

          static_cast<uint32_t>(T1.size());

      // Validate catch clause.

      for (const auto &C : TryDesc.Catch) {

        if (!C.IsAll) {

          // Check tag index.

          EXPECTED_TRY(checkTagIdx(C.TagIndex));

          // Result types of tag indices are checked in the tag section.

        }

        EXPECTED_TRY(auto D, checkCtrlStackDepth(C.LabelIndex));

        pushCtrl({}, getLabelTypes(CtrlStack[D]), &Instr + TryDesc.JumpEnd,

                 Instr.getOpCode());

        std::vector<ValType> NTypes;

        if (!C.IsAll) {

          // The type is checked as a function type.

          NTypes = Types[Tags[C.TagIndex]]

                       ->getCompositeType()

                       .getFuncType()

                       .getParamTypes();

        }

        if (C.IsRef) {

          NTypes.emplace_back(ValType(TypeCode::Ref, TypeCode::ExnRef));

        }

        pushTypes(NTypes);

        EXPECTED_TRY(popCtrl());

        recordJump(const_cast<AST::Instruction::JumpDescriptor &>(C.Jump),

                   static_cast<uint32_t>(NTypes.size()), D);

      }

    }

    // Push ctrl frame ([t1*], [t2*])

    const AST::Instruction *From = nullptr;

    if (Instr.getOpCode() == OpCode::Loop) {

      From = &Instr;

    } else if (Instr.getOpCode() == OpCode::Try_table) {

      From = &Instr + Instr.getTryCatch().JumpEnd;

    } else {

      From = &Instr + Instr.getJumpEnd();

    }

    pushCtrl(T1, T2, From, Instr.getOpCode());

    if (Instr.getOpCode() == OpCode::If &&

        Instr.getJumpElse() == Instr.getJumpEnd()) {

      // No else case in if-else statement.

      EXPECTED_TRY(checkTypesMatching(T2, T1));

    }

    return {};

  }

  case OpCode::Else: {

    EXPECTED_TRY(auto Ctrl, popCtrl());

    pushCtrl(Ctrl.StartTypes, Ctrl.EndTypes, Ctrl.Jump, Instr.getOpCode());

    return {};

  }

  case OpCode::Throw: {

    EXPECTED_TRY(checkTagIdx(Instr.getTargetIndex()));

    EXPECTED_TRY(auto CompType, checkDefinedType(Tags[Instr.getTargetIndex()],

                                                 TypeCode::Func));

    std::vector<ValType> Input = CompType->getFuncType().getParamTypes();

    EXPECTED_TRY(popTypes(Input));

    return unreachable();

  }

  case OpCode::Throw_ref:

    EXPECTED_TRY(popType(TypeCode::ExnRef));

    return unreachable();

  case OpCode::End: {

    EXPECTED_TRY(auto Ctrl, popCtrl());

    pushTypes(Ctrl.EndTypes);

    return {};

  }

  case OpCode::Br: {

    EXPECTED_TRY(auto D, checkCtrlStackDepth(Instr.getJump().TargetIndex));

    // D is the last D element of control stack.

    const auto NTypes = getLabelTypes(CtrlStack[D]);

    EXPECTED_TRY(popTypes(NTypes));

    recordJump(const_cast<AST::Instruction &>(Instr).getJump(),

               static_cast<uint32_t>(NTypes.size()), D);

    return unreachable();

  }

  case OpCode::Br_if: {

    EXPECTED_TRY(auto D, checkCtrlStackDepth(Instr.getJump().TargetIndex));

    // D is the last D element of control stack.

    EXPECTED_TRY(popType(TypeCode::I32));

    const auto NTypes = getLabelTypes(CtrlStack[D]);

    EXPECTED_TRY(popTypes(NTypes));

    recordJump(const_cast<AST::Instruction &>(Instr).getJump(),

               static_cast<uint32_t>(NTypes.size()), D);

    pushTypes(NTypes);

    return {};

  }

  case OpCode::Br_table: {

    EXPECTED_TRY(popType(TypeCode::I32));

    auto LabelTable = const_cast<AST::Instruction &>(Instr).getLabelList();

    const auto LabelTableSize = static_cast<uint32_t>(LabelTable.size() - 1);

    EXPECTED_TRY(auto M,

                 checkCtrlStackDepth(LabelTable[LabelTableSize].TargetIndex));

    // M is the M-th element from the end of the control stack.

    auto MTypes = getLabelTypes(CtrlStack[M]);

    for (uint32_t LabelIdx = 0; LabelIdx < LabelTableSize; ++LabelIdx) {

      const uint32_t L = LabelTable[LabelIdx].TargetIndex;

      EXPECTED_TRY(auto N, checkCtrlStackDepth(L));

      // N is the N-th element from the end of the control stack.

      const auto NTypes = getLabelTypes(CtrlStack[N]);

      if (MTypes.size() != NTypes.size()) {

        return checkTypesMatching(MTypes, NTypes);

      }

      // Push the popped types.

      std::vector<VType> TypeBuf(NTypes.size());

      for (uint32_t IdxN = static_cast<uint32_t>(NTypes.size()); IdxN >= 1;

           --IdxN) {

        const uint32_t Idx = IdxN - 1;

        // Cannot use popTypes() here because we need the popped value.

        EXPECTED_TRY(auto Type, popType(NTypes[Idx]));

        // Check whether `unreachableVType` occurred when an `unreachable`

        // instruction appeared before the `br_table` instruction.

        if (CtrlStack.back().IsUnreachable) {

          TypeBuf[Idx] = unreachableVType();

        } else {

          TypeBuf[Idx] = Type;

        }

      }

      recordJump(LabelTable[LabelIdx], static_cast<uint32_t>(NTypes.size()), N);

      pushTypes(TypeBuf);

    }

    const auto NTypes = getLabelTypes(CtrlStack[M]);

    EXPECTED_TRY(popTypes(NTypes));

    recordJump(LabelTable[LabelTableSize], static_cast<uint32_t>(NTypes.size()),

               M);

    return unreachable();

  }

  case OpCode::Br_on_null: {

    // D is the last D element of control stack.

    EXPECTED_TRY(auto D, checkCtrlStackDepth(Instr.getJump().TargetIndex));

    const auto NTypes = getLabelTypes(CtrlStack[D]);

    EXPECTED_TRY(auto ResT, popType());

    if (ResT.has_value() && !ResT->isRefType()) {

      spdlog::error(ErrCode::Value::InvalidBrRefType);

      return Unexpect(ErrCode::ErrCode::Value::InvalidBrRefType);

    }

    EXPECTED_TRY(popTypes(NTypes));

    recordJump(const_cast<AST::Instruction &>(Instr).getJump(),

               static_cast<uint32_t>(NTypes.size()), D);

    pushTypes(NTypes);

    if (ResT.has_value()) {

      pushType(ResT->toNonNullableRef());

    } else {

      pushType(unreachableVType());

    }

    return {};

  }

  case OpCode::Br_on_non_null: {

    EXPECTED_TRY(auto D, checkCtrlStackDepth(Instr.getJump().TargetIndex));

    // Get the result type of the label. (Should be [t* rt].)

    auto LabelTypes = getLabelTypes(CtrlStack[D]);

    std::vector<ValType> NTypes(LabelTypes.begin(), LabelTypes.end());

    if (unlikely(NTypes.empty())) {

      spdlog::error(ErrCode::Value::InvalidBrRefType);

      return Unexpect(ErrCode::Value::InvalidBrRefType);

    }

    // Pop types [t* (ref.null rt)].

    ValType &RT = NTypes.back();

    if (!RT.isRefType()) {

      spdlog::error(ErrCode::Value::InvalidBrRefType);

      return Unexpect(ErrCode::Value::InvalidBrRefType);

    }

    RT.toNullableRef();

    EXPECTED_TRY(popTypes(NTypes));

    recordJump(const_cast<AST::Instruction &>(Instr).getJump(),

               static_cast<uint32_t>(NTypes.size()), D);

    // Push types [t*].

    NTypes.pop_back();

    pushTypes(NTypes);

    return {};

  }

  case OpCode::Return:

    EXPECTED_TRY(popTypes(Returns));

    return unreachable();

  case OpCode::Call: {

    auto N = Instr.getTargetIndex();

    if (unlikely(N >= Funcs.size())) {

      return logOutOfRange(ErrCode::Value::InvalidFuncIdx,

                           ErrInfo::IndexCategory::Function, N,

                           static_cast<uint32_t>(Funcs.size()));

    }

    // Because functions were validated when added, Type[Funcs[N]] must be a

    // function type.

    auto &FuncType = Types[Funcs[N]]->getCompositeType().getFuncType();

    return StackTrans(FuncType.getParamTypes(), FuncType.getReturnTypes());

  }

  case OpCode::Call_indirect: {

    auto N = Instr.getTargetIndex();

    auto T = Instr.getSourceIndex();

    // Check source table index.

    EXPECTED_TRY(checkTableIdx(T));

    if (!AST::TypeMatcher::matchType(Types, TypeCode::FuncRef,

                                     Tables[T].second)) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(TypeCode::FuncRef, Tables[T].second));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    // Check target function type index.

    EXPECTED_TRY(auto CompType, checkDefinedType(N, TypeCode::Func));

    EXPECTED_TRY(popType(Tables[T].first));

    const auto &FType = CompType->getFuncType();

    return StackTrans(FType.getParamTypes(), FType.getReturnTypes());

  }

  case OpCode::Return_call: {

    auto N = Instr.getTargetIndex();

    if (unlikely(N >= Funcs.size())) {

      // Call function index out of range

      spdlog::error(ErrCode::Value::InvalidFuncIdx);

      spdlog::error(

          ErrInfo::InfoForbidIndex(ErrInfo::IndexCategory::Function, N,

                                   static_cast<uint32_t>(Funcs.size())));

      return Unexpect(ErrCode::Value::InvalidFuncIdx);

    }

    // Because functions were validated when added, Type[Funcs[N]] must be a

    // function type.

    auto &FType = Types[Funcs[N]]->getCompositeType().getFuncType();

    EXPECTED_TRY(checkTypesMatching(Returns, FType.getReturnTypes()));

    EXPECTED_TRY(popTypes(FType.getParamTypes()));

    return unreachable();

  }

  case OpCode::Return_call_indirect: {

    auto N = Instr.getTargetIndex();

    auto T = Instr.getSourceIndex();

    // Check source table index.

    EXPECTED_TRY(checkTableIdx(T));

    if (!AST::TypeMatcher::matchType(Types, TypeCode::FuncRef,

                                     Tables[T].second)) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(TypeCode::FuncRef, Tables[T].second));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    // Check target function type index.

    EXPECTED_TRY(auto CompType, checkDefinedType(N, TypeCode::Func));

    const auto &FType = CompType->getFuncType();

    EXPECTED_TRY(checkTypesMatching(Returns, FType.getReturnTypes()));

    EXPECTED_TRY(popType(Tables[T].first));

    EXPECTED_TRY(popTypes(FType.getParamTypes()));

    return unreachable();

  }

  case OpCode::Call_ref: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Func));

    const auto &FType = CompType->getFuncType();

    std::vector<ValType> Input = FType.getParamTypes();

    Input.push_back(ValType(TypeCode::RefNull, Instr.getTargetIndex()));

    return StackTrans(Input, FType.getReturnTypes());

  }

  case OpCode::Return_call_ref: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Func));

    const auto &FType = CompType->getFuncType();

    EXPECTED_TRY(checkTypesMatching(Returns, FType.getReturnTypes()));

    EXPECTED_TRY(popType(ValType(TypeCode::RefNull, Instr.getTargetIndex())));

    EXPECTED_TRY(popTypes(FType.getParamTypes()));

    return unreachable();

  }

  // Reference Instructions.

  case OpCode::Ref__null: {

    EXPECTED_TRY(validate(Instr.getValType()));

    return StackTrans({}, {Instr.getValType()});

  }

  case OpCode::Ref__is_null: {

    EXPECTED_TRY(auto Type, popType());

    if (Type.has_value() && !Type->isRefType()) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(TypeCode::FuncRef, VTypeToAST(Type)));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    return StackTrans({}, {ValType(TypeCode::I32)});

  }

  case OpCode::Ref__func: {

    auto FuncIdx = Instr.getTargetIndex();

    if (Refs.find(FuncIdx) == Refs.cend()) {

      // Undeclared function reference.

      spdlog::error(ErrCode::Value::InvalidRefIdx);

      return Unexpect(ErrCode::Value::InvalidRefIdx);

    }

    assuming(FuncIdx < Funcs.size());

    auto TypeIdx = Funcs[FuncIdx];

    assuming(TypeIdx < Types.size());

    return StackTrans({}, {ValType(TypeCode::Ref, TypeIdx)});

  }

  case OpCode::Ref__eq:

    return StackTrans({ValType(TypeCode::RefNull, TypeCode::EqRef),

                       ValType(TypeCode::RefNull, TypeCode::EqRef)},

                      {ValType(TypeCode::I32)});

  case OpCode::Ref__as_non_null: {

    EXPECTED_TRY(auto Type, popType());

    if (Type == unreachableVType()) {

      pushType(unreachableVType());

      return {};

    }

    if (!Type->isRefType()) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(

          ValType(TypeCode::RefNull, TypeCode::FuncRef), VTypeToAST(Type)));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    return StackTrans({}, {Type->toNonNullableRef()});

  }

  case OpCode::Struct__new:

  case OpCode::Struct__new_default: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Struct));

    std::vector<ValType> Fields;

    if (Instr.getOpCode() == OpCode::Struct__new) {

      Fields.reserve(CompType->getFieldTypes().size());

    }

    for (auto &FType : CompType->getFieldTypes()) {

      if (Instr.getOpCode() == OpCode::Struct__new) {

        Fields.emplace_back(unpackType(FType.getStorageType()));

      } else if (!FType.getStorageType().isDefaultable()) {

        spdlog::error(ErrCode::Value::TypeCheckFailed);

        spdlog::error("    Value type should be defaultable."sv);

        return Unexpect(ErrCode::Value::TypeCheckFailed);

      }

    }

    return StackTrans(Fields, {ValType(TypeCode::Ref, Instr.getTargetIndex())});

  }

  case OpCode::Struct__get:

  case OpCode::Struct__get_s:

  case OpCode::Struct__get_u: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Struct));

    if (Instr.getSourceIndex() >= CompType->getFieldTypes().size()) {

      return logOutOfRange(

          ErrCode::Value::InvalidFieldIdx, ErrInfo::IndexCategory::Field,

          Instr.getSourceIndex(),

          static_cast<uint32_t>(CompType->getFieldTypes().size()));

    }

    const auto &FType = CompType->getFieldTypes()[Instr.getSourceIndex()];

    if (unlikely(Instr.getOpCode() == OpCode::Struct__get &&

                 FType.getStorageType().isPackType())) {

      // For a packed type, the `_s` or `_u` in the instruction is required.

      spdlog::error(ErrCode::Value::InvalidPackedField);

      return Unexpect(ErrCode::Value::InvalidPackedField);

    } else if (unlikely(Instr.getOpCode() != OpCode::Struct__get &&

                        !FType.getStorageType().isPackType())) {

      // The `_s` or `_u` in instruction only accepts packed field.

      spdlog::error(ErrCode::Value::InvalidUnpackedField);

      return Unexpect(ErrCode::Value::InvalidUnpackedField);

    }

    return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex())},

                      {unpackType(FType.getStorageType())});

  }

  case OpCode::Struct__set: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Struct));

    if (Instr.getSourceIndex() >= CompType->getFieldTypes().size()) {

      return logOutOfRange(

          ErrCode::Value::InvalidFieldIdx, ErrInfo::IndexCategory::Field,

          Instr.getSourceIndex(),

          static_cast<uint32_t>(CompType->getFieldTypes().size()));

    }

    const auto &FType = CompType->getFieldTypes()[Instr.getSourceIndex()];

    if (FType.getValMut() != ValMut::Var) {

      spdlog::error(ErrCode::Value::ImmutableField);

      return Unexpect(ErrCode::Value::ImmutableField);

    }

    return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex()),

                       unpackType(FType.getStorageType())},

                      {});

  }

  case OpCode::Array__new:

  case OpCode::Array__new_default:

  case OpCode::Array__new_fixed: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &SType = CompType->getFieldTypes()[0].getStorageType();

    if (Instr.getOpCode() == OpCode::Array__new) {

      return StackTrans({unpackType(SType), ValType(TypeCode::I32)},

                        {ValType(TypeCode::Ref, Instr.getTargetIndex())});

    } else if (Instr.getOpCode() == OpCode::Array__new_default) {

      if (!SType.isDefaultable()) {

        spdlog::error(ErrCode::Value::TypeCheckFailed);

        spdlog::error("    Value type should be defaultable."sv);

        return Unexpect(ErrCode::Value::TypeCheckFailed);

      }

      return StackTrans({ValType(TypeCode::I32)},

                        {ValType(TypeCode::Ref, Instr.getTargetIndex())});

    } else {

      std::vector<ValType> Fields(Instr.getSourceIndex(), unpackType(SType));

      return StackTrans(Fields,

                        {ValType(TypeCode::Ref, Instr.getTargetIndex())});

    }

  }

  case OpCode::Array__new_data:

  case OpCode::Array__init_data: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &FType = CompType->getFieldTypes()[0];

    if (Instr.getOpCode() == OpCode::Array__init_data &&

        FType.getValMut() != ValMut::Var) {

      spdlog::error(ErrCode::Value::ImmutableArray);

      return Unexpect(ErrCode::Value::ImmutableArray);

    }

    if (!unpackType(FType.getStorageType()).isNumType()) {

      spdlog::error(ErrCode::Value::ArrayTypesNumtypeRequired);

      return Unexpect(ErrCode::Value::ArrayTypesNumtypeRequired);

    }

    EXPECTED_TRY(checkDataIdx(Instr.getSourceIndex()));

    if (Instr.getOpCode() == OpCode::Array__new_data) {

      return StackTrans({ValType(TypeCode::I32), ValType(TypeCode::I32)},

                        {ValType(TypeCode::Ref, Instr.getTargetIndex())});

    } else {

      return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex()),

                         ValType(TypeCode::I32), ValType(TypeCode::I32),

                         ValType(TypeCode::I32)},

                        {});

    }

  }

  case OpCode::Array__new_elem:

  case OpCode::Array__init_elem: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &FType = CompType->getFieldTypes()[0];

    if (Instr.getOpCode() == OpCode::Array__init_elem &&

        FType.getValMut() != ValMut::Var) {

      spdlog::error(ErrCode::Value::ImmutableArray);

      return Unexpect(ErrCode::Value::ImmutableArray);

    }

    if (!FType.getStorageType().isRefType()) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    EXPECTED_TRY(checkElemIdx(Instr.getSourceIndex()));

    if (!AST::TypeMatcher::matchType(Types, FType.getStorageType(),

                                     Elems[Instr.getSourceIndex()])) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(FType.getStorageType(),

                                          Elems[Instr.getSourceIndex()]));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    if (Instr.getOpCode() == OpCode::Array__new_elem) {

      return StackTrans({ValType(TypeCode::I32), ValType(TypeCode::I32)},

                        {ValType(TypeCode::Ref, Instr.getTargetIndex())});

    } else {

      return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex()),

                         ValType(TypeCode::I32), ValType(TypeCode::I32),

                         ValType(TypeCode::I32)},

                        {});

    }

  }

  case OpCode::Array__get:

  case OpCode::Array__get_s:

  case OpCode::Array__get_u: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &FType = CompType->getFieldTypes()[0];

    if (unlikely(Instr.getOpCode() == OpCode::Array__get &&

                 FType.getStorageType().isPackType())) {

      // For a packed type, the `_s` or `_u` in the instruction is required.

      spdlog::error(ErrCode::Value::InvalidPackedArray);

      return Unexpect(ErrCode::Value::InvalidPackedArray);

    } else if (unlikely(Instr.getOpCode() != OpCode::Array__get &&

                        !FType.getStorageType().isPackType())) {

      // The `_s` or `_u` in instruction only accepts packed array.

      spdlog::error(ErrCode::Value::InvalidUnpackedArray);

      return Unexpect(ErrCode::Value::InvalidUnpackedArray);

    }

    return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex()),

                       ValType(TypeCode::I32)},

                      {unpackType(FType.getStorageType())});

  }

  case OpCode::Array__set:

  case OpCode::Array__fill: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &FType = CompType->getFieldTypes()[0];

    if (FType.getValMut() != ValMut::Var) {

      spdlog::error(ErrCode::Value::ImmutableArray);

      return Unexpect(ErrCode::Value::ImmutableArray);

    }

    std::vector<ValType> Fields = {

        ValType(TypeCode::RefNull, Instr.getTargetIndex()),

        ValType(TypeCode::I32), unpackType(FType.getStorageType())};

    if (Instr.getOpCode() == OpCode::Array__fill) {

      Fields.emplace_back(ValType(TypeCode::I32));

    }

    return StackTrans(Fields, {});

  }

  case OpCode::Array__len:

    return StackTrans({ValType(TypeCode::ArrayRef)}, {ValType(TypeCode::I32)});

  case OpCode::Array__copy: {

    EXPECTED_TRY(auto CompType,

                 checkDefinedType(Instr.getTargetIndex(), TypeCode::Array));

    const auto &DstFType = CompType->getFieldTypes()[0];

    if (DstFType.getValMut() != ValMut::Var) {

      spdlog::error(ErrCode::Value::ImmutableArray);

      return Unexpect(ErrCode::Value::ImmutableArray);

    }

    EXPECTED_TRY(auto Src,

                 checkDefinedType(Instr.getSourceIndex(), TypeCode::Array));

    const auto &SrcFType = Src->getFieldTypes()[0];

    if (!AST::TypeMatcher::matchType(Types, DstFType.getStorageType(),

                                     SrcFType.getStorageType())) {

      spdlog::error(ErrCode::Value::ArrayTypesMismatch);

      spdlog::error(ErrInfo::InfoMismatch(DstFType.getStorageType(),

                                          SrcFType.getStorageType()));

      return Unexpect(ErrCode::Value::ArrayTypesMismatch);

    }

    return StackTrans({ValType(TypeCode::RefNull, Instr.getTargetIndex()),

                       ValType(TypeCode::I32),

                       ValType(TypeCode::RefNull, Instr.getSourceIndex()),

                       ValType(TypeCode::I32), ValType(TypeCode::I32)},

                      {});

  }

  case OpCode::Ref__test:

  case OpCode::Ref__test_null:

  case OpCode::Ref__cast:

  case OpCode::Ref__cast_null: {

    EXPECTED_TRY(validate(Instr.getValType()));

    EXPECTED_TRY(auto Type, popType());

    if (Type.has_value() && !Type->isRefType()) {

      // The trap occurs when the actual type is not a reference type.

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(

          ErrInfo::InfoMismatch(Instr.getValType(), VTypeToAST(Type)));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    // When Type is nullopt (unreachable/bottom type), the bottom type matches

    // any target type, so skip the type matching check.

    if (Type.has_value() &&

        !AST::TypeMatcher::matchType(Types, toTopHeapType(*Type),

                                     Instr.getValType())) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(*Type, Instr.getValType()));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    if (Instr.getOpCode() == OpCode::Ref__test ||

        Instr.getOpCode() == OpCode::Ref__test_null) {

      return StackTrans({}, {ValType(TypeCode::I32)});

    } else {

      return StackTrans({}, {Instr.getValType()});

    }

  }

  case OpCode::Br_on_cast:

  case OpCode::Br_on_cast_fail: {

    // The reference types should be valid.

    auto &RT1 = Instr.getBrCast().RType1;

    auto &RT2 = Instr.getBrCast().RType2;

    EXPECTED_TRY(validate(RT1));

    EXPECTED_TRY(validate(RT2));

    // The reference type RT2 should match RT1.

    if (unlikely(!AST::TypeMatcher::matchType(Types, RT1, RT2))) {

      spdlog::error(ErrCode::Value::TypeCheckFailed);

      spdlog::error(ErrInfo::InfoMismatch(RT1, RT2));

      return Unexpect(ErrCode::Value::TypeCheckFailed);

    }

    EXPECTED_TRY(auto D,

                 checkCtrlStackDepth(Instr.getBrCast().Jump.TargetIndex));

    // Get the result type of the label. (Should be [t* rt'].)

    auto LabelTypes = getLabelTypes(CtrlStack[D]);

    std::vector<ValType> NTypes(LabelTypes.begin(), LabelTypes.end());

    if (unlikely(NTypes.empty())) {

      spdlog::error(ErrCode::Value::InvalidBrRefType);

      return Unexpect(ErrCode::Value::InvalidBrRefType);

    }

    // Get the type difference between rt1 \ rt2. (rt1' = rt1 \ rt2)

    ValType RT1P = RT2.isNullableRefType() ? RT1.getNonNullableRef() : RT1;

    // For br_on_cast, rt2 must match rt'.

    // For Br_on_cast_fail, rt1' must match rt'.

    ValType &RTP = NTypes.back();

    const ValType &RTRHS = Instr.getOpCode() == OpCode::Br_on_cast ? RT2 : RT1P;

    if (unlikely(!AST::TypeMatcher::matchType(Types, RTP, RTRHS))) {