/src/WasmEdge/lib/validator/validator.cpp

Source
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright The WasmEdge Authors

#include "validator/validator.h"

#include "ast/section.h"
#include "common/errinfo.h"
#include "common/hash.h"

#include <map>
#include <numeric>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std::literals;

namespace WasmEdge {
namespace Validator {

namespace {

static constexpr uint32_t MaxSubtypeDepth = 63;
static constexpr uint32_t Unvisited = UINT32_MAX;
static constexpr uint32_t Visiting = UINT32_MAX - 1;

// TODO: make the super type depth table instead of recursively querying.
Expect<uint32_t>
checkSubtypeDepth(const uint32_t BaseIdx, uint32_t TestIdx, uint32_t Depth,
                  std::vector<uint32_t> &DepthMap,
                  const std::vector<const WasmEdge::AST::SubType *> &TypeVec) {
  if (TestIdx >= DepthMap.size()) {
    DepthMap.resize(TestIdx + 1, Unvisited);
  } else if (DepthMap[TestIdx] == Visiting) {
    spdlog::error(ErrCode::Value::InvalidSubType);
    spdlog::error("    Cycle detected in subtype hierarchy for type {}."sv,
                  BaseIdx);
    return Unexpect(ErrCode::Value::InvalidSubType);
  } else if (DepthMap[TestIdx] != Unvisited) {
    return DepthMap[TestIdx];
  }

  if (Depth >= MaxSubtypeDepth) {
    spdlog::error(ErrCode::Value::InvalidSubType);
    spdlog::error("    Subtype depth for type {} exceeded the limits of {}"sv,
                  BaseIdx, MaxSubtypeDepth);
    return Unexpect(ErrCode::Value::InvalidSubType);
  }

  DepthMap[TestIdx] = Visiting;
  uint32_t MaxDepth = 0;
  // A component core:type index may name a module type, which is not a sub
  // type and holds no place in the hierarchy.
  const auto *TestType = TypeVec[TestIdx];
  if (unlikely(TestType == nullptr)) {
    spdlog::error(ErrCode::Value::InvalidSubType);
    spdlog::error("    Type index {} does not refer to a sub type."sv, TestIdx);
    return Unexpect(ErrCode::Value::InvalidSubType);
  }
  for (const auto SuperIdx : TestType->getSuperTypeIndices()) {
    if (unlikely(SuperIdx >= TypeVec.size())) {
      spdlog::error(ErrCode::Value::InvalidSubType);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::DefinedType, SuperIdx,
          static_cast<uint32_t>(TypeVec.size())));
      return Unexpect(ErrCode::Value::InvalidSubType);
    }
    EXPECTED_TRY(
        auto RetDepth,
        checkSubtypeDepth(BaseIdx, SuperIdx, Depth + 1, DepthMap, TypeVec)
            .map_error([=](auto E) {
              spdlog::error(
                  "    When checking subtype hierarchy of super type {}."sv,
                  SuperIdx);
              return E;
            }));
    MaxDepth = std::max(MaxDepth, RetDepth + 1);
  }

  if (MaxDepth >= MaxSubtypeDepth) {
    spdlog::error(ErrCode::Value::InvalidSubType);
    spdlog::error("    Subtype depth for type {} exceeded the limits of {}"sv,
                  BaseIdx, MaxSubtypeDepth);
    return Unexpect(ErrCode::Value::InvalidSubType);
  }

  DepthMap[TestIdx] = MaxDepth;
  return MaxDepth;
}

// Set the canonical indices of a rec type from the first with the same key.
void setCanonicalIndices(Span<const AST::SubType> RecType, uint32_t BaseIdx,
                         const std::vector<const AST::SubType *> &TypeVec,
                         std::map<std::vector<uint32_t>, uint32_t> &RecTypes) {
  std::vector<uint32_t> Key;
  auto AddTypeIdx = [&](uint32_t Idx) {
    if (Idx >= BaseIdx && Idx - BaseIdx < RecType.size()) {
      Key.push_back(0U);
      Key.push_back(Idx - BaseIdx);
    } else {
      Key.push_back(1U);
      Key.push_back(TypeVec[Idx]->getCanonicalIndex().value_or(Idx));
    }
  };
  auto AddValType = [&](const ValType &VT) {
    Key.push_back(static_cast<uint32_t>(VT.getCode()));
    Key.push_back(static_cast<uint32_t>(VT.getHeapTypeCode()));
    if (VT.getHeapTypeCode() == TypeCode::TypeIndex) {
      AddTypeIdx(VT.getTypeIndex());
    }
  };

  Key.push_back(static_cast<uint32_t>(RecType.size()));
  for (const auto &Type : RecType) {
    const auto &CompType = Type.getCompositeType();
    Key.push_back(Type.isFinal() ? 1U : 0U);
    Key.push_back(static_cast<uint32_t>(Type.getSuperTypeIndices().size()));
    for (const auto Idx : Type.getSuperTypeIndices()) {
      AddTypeIdx(Idx);
    }
    Key.push_back(static_cast<uint32_t>(CompType.getContentTypeCode()));
    if (CompType.isFunc()) {
      const auto &FType = CompType.getFuncType();
      Key.push_back(static_cast<uint32_t>(FType.getParamTypes().size()));
      for (const auto &VT : FType.getParamTypes()) {
        AddValType(VT);
      }
      Key.push_back(static_cast<uint32_t>(FType.getReturnTypes().size()));
      for (const auto &VT : FType.getReturnTypes()) {
        AddValType(VT);
      }
    } else {
      const auto &FTypes = CompType.getFieldTypes();
      Key.push_back(static_cast<uint32_t>(FTypes.size()));
      for (const auto &FType : FTypes) {
        Key.push_back(static_cast<uint32_t>(FType.getValMut()));
        AddValType(FType.getStorageType());
      }
    }
  }
  const uint32_t CanonIdx =
      RecTypes.try_emplace(std::move(Key), BaseIdx).first->second;
  for (uint32_t I = 0; I < RecType.size(); I++) {
    const_cast<AST::SubType &>(RecType[I]).setCanonicalIndex(CanonIdx + I);
  }
}

} // namespace

// Validate Module. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::Module &Mod) {
  // https://webassembly.github.io/spec/core/valid/modules.html
  Checker.reset(true);

  // Validate and register type section.
  EXPECTED_TRY(validate(Mod.getTypeSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Type));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate and register the import section in FormChecker.
  EXPECTED_TRY(validate(Mod.getImportSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Import));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the function section and register functions in FormChecker.
  EXPECTED_TRY(validate(Mod.getFunctionSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Function));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the table section and register tables in FormChecker.
  EXPECTED_TRY(validate(Mod.getTableSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Table));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the memory section and register memories in FormChecker.
  EXPECTED_TRY(validate(Mod.getMemorySection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Memory));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the global section and register globals in FormChecker.
  EXPECTED_TRY(validate(Mod.getGlobalSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Global));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the tag section and register tags in FormChecker.
  EXPECTED_TRY(validate(Mod.getTagSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Tag));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate export section.
  EXPECTED_TRY(validate(Mod.getExportSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Export));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate start section.
  EXPECTED_TRY(validate(Mod.getStartSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Start));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the element section that initializes tables.
  EXPECTED_TRY(validate(Mod.getElementSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Element));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate the data section that initializes memories.
  EXPECTED_TRY(validate(Mod.getDataSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Data));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Validate code section and expressions.
  EXPECTED_TRY(validate(Mod.getCodeSection()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Sec_Code));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return E;
  }));

  // Multiple tables are for the ReferenceTypes proposal.
  if (Checker.getTables().size() > 1 &&
      !Conf.hasProposal(Proposal::ReferenceTypes)) {
    spdlog::error(ErrCode::Value::MultiTables);
    spdlog::error(ErrInfo::InfoProposal(Proposal::ReferenceTypes));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return Unexpect(ErrCode::Value::MultiTables);
  }

  // Multiple memories are for the MultiMemories proposal.
  if (Checker.getMemories().size() > 1 &&
      !Conf.hasProposal(Proposal::MultiMemories)) {
    spdlog::error(ErrCode::Value::MultiMemories);
    spdlog::error(ErrInfo::InfoProposal(Proposal::MultiMemories));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Module));
    return Unexpect(ErrCode::Value::MultiMemories);
  }

  // Set the validated flag.
  const_cast<AST::Module &>(Mod).setIsValidated();
  return {};
}

// Validate Sub type. See "include/validator/validator.h".
Expect<void>
Validator::validate(const AST::SubType &Type, uint32_t OwnTypeIdx,
                    std::vector<uint32_t> &SubTypeDepthMap,
                    const std::vector<const AST::SubType *> &TypeVec) {
  const auto &CompType = Type.getCompositeType();
  // A concrete heap type reference must name a defined type of this space.
  auto CheckValType = [&TypeVec](const ValType &VT) -> Expect<void> {
    if (VT.isRefType() && VT.getHeapTypeCode() == TypeCode::TypeIndex &&
        (VT.getTypeIndex() >= TypeVec.size() ||
         TypeVec[VT.getTypeIndex()] == nullptr)) {
      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::FunctionType, VT.getTypeIndex(),
          static_cast<uint32_t>(TypeVec.size())));
      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);
    }
    return {};
  };

  // Check the validation of the composite type.
  if (CompType.isFunc()) {
    const auto &FType = CompType.getFuncType();
    for (auto &PType : FType.getParamTypes()) {
      EXPECTED_TRY(CheckValType(PType).map_error([](auto E) {
        spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Function));
        return E;
      }));
    }
    if (unlikely(!Conf.hasProposal(Proposal::MultiValue)) &&
        FType.getReturnTypes().size() > 1) {
      spdlog::error(ErrCode::Value::InvalidResultArity);
      spdlog::error(ErrInfo::InfoProposal(Proposal::MultiValue));
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Function));
      return Unexpect(ErrCode::Value::InvalidResultArity);
    }
    for (auto &RType : FType.getReturnTypes()) {
      EXPECTED_TRY(CheckValType(RType).map_error([](auto E) {
        spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Function));
        return E;
      }));
    }
  } else {
    const auto &FTypes = CompType.getFieldTypes();
    for (auto &FieldType : FTypes) {
      EXPECTED_TRY(CheckValType(FieldType.getStorageType()));
    }
  }

  // In the current version, the length of the type index vector will be <= 1.
  if (Type.getSuperTypeIndices().size() > 1) {
    spdlog::error(ErrCode::Value::MultipleSuperTypes);
    return Unexpect(ErrCode::Value::MultipleSuperTypes);
  }

  for (const auto &Index : Type.getSuperTypeIndices()) {
    // A super type must be previously defined (smaller index than this sub
    // type), so OwnTypeIdx is the exclusive bound, subsuming the range check.
    if (unlikely(Index >= OwnTypeIdx)) {
      spdlog::error(ErrCode::Value::InvalidSubType);
      spdlog::error("    Super type index {} must be smaller than the sub type "
                    "index {}."sv,
                    Index, OwnTypeIdx);
      return Unexpect(ErrCode::Value::InvalidSubType);
    }

    EXPECTED_TRY(
        checkSubtypeDepth(Index, Index, 0, SubTypeDepthMap, TypeVec)
            .map_error([=](auto E) {
              spdlog::error(
                  "    When checking subtype hierarchy of super type {}."sv,
                  Index);
              return E;
            }));

    if (TypeVec[Index]->isFinal()) {
      spdlog::error(ErrCode::Value::InvalidSubType);
      spdlog::error("    Super type should not be final."sv);
      return Unexpect(ErrCode::Value::InvalidSubType);
    }
  }
  return {};
}

// Validate Rec type. See "include/validator/validator.h".
Expect<void>
Validator::validate(Span<const AST::SubType> RecType, uint32_t BaseIdx,
                    std::vector<uint32_t> &SubTypeDepthMap,
                    const std::vector<const AST::SubType *> &TypeVec) {
  // Check all the members before matching, which walks their super types.
  for (uint32_t I = 0; I < RecType.size(); I++) {
    EXPECTED_TRY(validate(RecType[I], BaseIdx + I, SubTypeDepthMap, TypeVec));
  }
  for (const auto &Type : RecType) {
    for (const auto &Index : Type.getSuperTypeIndices()) {
      if (!AST::TypeMatcher::matchType(TypeVec,
                                       TypeVec[Index]->getCompositeType(),
                                       Type.getCompositeType())) {
        spdlog::error(ErrCode::Value::InvalidSubType);
        spdlog::error("    Super type not matched."sv);
        return Unexpect(ErrCode::Value::InvalidSubType);
      }
    }
  }
  return {};
}

// Validate Limit type. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::Limit &Lim) {
  if (Lim.hasMax() && Lim.getMin() > Lim.getMax()) {
    spdlog::error(ErrCode::Value::InvalidLimit);
    spdlog::error(ErrInfo::InfoLimit(Lim.hasMax(), Lim.getMin(), Lim.getMax()));
    return Unexpect(ErrCode::Value::InvalidLimit);
  }
  if (Lim.isShared() && unlikely(!Lim.hasMax())) {
    spdlog::error(ErrCode::Value::SharedMemoryNoMax);
    return Unexpect(ErrCode::Value::SharedMemoryNoMax);
  }
  return {};
}

// Validate Table type. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::TableType &Tab) {
  // Validate value type.
  EXPECTED_TRY(Checker.validate(Tab.getRefType()));
  // Validate table limits.
  const auto &Lim = Tab.getLimit();
  EXPECTED_TRY(validate(Lim).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Limit));
    return E;
  }));
  uint64_t Range = getMaxAddress(Lim.getAddrType());
  if (Lim.getMin() > Range || (Lim.hasMax() && Lim.getMax() > Range)) {
    // Since spec test has no related error message, use this error instead.
    auto Code = Conf.hasProposal(Proposal::Memory64)
                    ? ErrCode::Value::InvalidTableSize64
                    : ErrCode::Value::InvalidLimit;
    spdlog::error(Code);
    spdlog::error(ErrInfo::InfoLimit(Lim.hasMax(), Lim.getMin(), Lim.getMax()));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Limit));
    return Unexpect(Code);
  }
  return {};
}

// Validate Memory type. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::MemoryType &Mem) {
  // Validate memory limits.
  const auto &Lim = Mem.getLimit();
  EXPECTED_TRY(validate(Lim).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Limit));
    return E;
  }));
  if (!Conf.hasProposal(Proposal::Memory64) && Lim.is64()) {
    spdlog::error(ErrCode::Value::InvalidLimit);
    spdlog::error(ErrInfo::InfoProposal(Proposal::Memory64));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Limit));
    return Unexpect(ErrCode::Value::InvalidLimit);
  }
  uint64_t Range = Lim.is32() ? (static_cast<uint64_t>(1) << 16)
                              : (static_cast<uint64_t>(1) << 48);
  if (Lim.getMin() > Range || (Lim.hasMax() && Lim.getMax() > Range)) {
    auto Code = Conf.hasProposal(Proposal::Memory64)
                    ? ErrCode::Value::InvalidMemPages64
                    : ErrCode::Value::InvalidMemPages;
    spdlog::error(Code);
    spdlog::error(ErrInfo::InfoLimit(Lim.hasMax(), Lim.getMin(), Lim.getMax()));
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Limit));
    return Unexpect(Code);
  }
  return {};
}

// Validate Global type. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::GlobalType &Glob) {
  // Validate value type.
  return Checker.validate(Glob.getValType());
}

// Validate Table segment. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::TableSegment &TabSeg) {
  if (TabSeg.getExpr().getInstrs().size() > 0) {
    // Check ref initialization is a const expression.
    EXPECTED_TRY(
        validateConstExpr(TabSeg.getExpr().getInstrs(),
                          {ValType(TabSeg.getTableType().getRefType())})
            .map_error([](auto E) {
              spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
              return E;
            }));
  } else {
    // No init expression. Check that the reference type is nullable.
    if (!TabSeg.getTableType().getRefType().isNullableRefType()) {
      spdlog::error(ErrCode::Value::TypeCheckFailed);
      spdlog::error(ErrInfo::InfoMismatch(
          ValType(TypeCode::RefNull,
                  TabSeg.getTableType().getRefType().getHeapTypeCode(),
                  TabSeg.getTableType().getRefType().getTypeIndex()),
          TabSeg.getTableType().getRefType()));
      return Unexpect(ErrCode::Value::TypeCheckFailed);
    }
  }
  // Validate table type.
  return validate(TabSeg.getTableType()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Table));
    return E;
  });
}

// Validate Global segment. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::GlobalSegment &GlobSeg) {
  // Check global initialization is a const expression.
  EXPECTED_TRY(validateConstExpr(GlobSeg.getExpr().getInstrs(),
                                 {GlobSeg.getGlobalType().getValType()})
                   .map_error([](auto E) {
                     spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
                     return E;
                   }));
  // Validate global type.
  return validate(GlobSeg.getGlobalType()).map_error([](auto E) {
    spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Global));
    return E;
  });
}

// Validate Element segment. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ElementSegment &ElemSeg) {
  // Check that initialization expressions are const expressions.
  for (auto &Expr : ElemSeg.getInitExprs()) {
    EXPECTED_TRY(
        validateConstExpr(Expr.getInstrs(), {ValType(ElemSeg.getRefType())})
            .map_error([](auto E) {
              spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
              return E;
            }));
  }

  // The reference type should be valid.
  EXPECTED_TRY(Checker.validate(ElemSeg.getRefType()));

  // Passive and declarative cases are valid with a valid reference type.
  if (ElemSeg.getMode() == AST::ElementSegment::ElemMode::Active) {
    // Check table index and reference type in context.
    const auto &TableVec = Checker.getTables();
    if (ElemSeg.getIdx() >= TableVec.size()) {
      spdlog::error(ErrCode::Value::InvalidTableIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Table, ElemSeg.getIdx(),
          static_cast<uint32_t>(TableVec.size())));
      return Unexpect(ErrCode::Value::InvalidTableIdx);
    }
    if (!AST::TypeMatcher::matchType(Checker.getTypes(),
                                     TableVec[ElemSeg.getIdx()].second,
                                     ElemSeg.getRefType())) {
      // Reference type does not match.
      spdlog::error(ErrCode::Value::TypeCheckFailed);
      spdlog::error(ErrInfo::InfoMismatch(TableVec[ElemSeg.getIdx()].second,
                                          ElemSeg.getRefType()));
      return Unexpect(ErrCode::Value::TypeCheckFailed);
    }
    // Check table initialization is a const expression.
    return validateConstExpr(ElemSeg.getExpr().getInstrs(),
                             {ValType(TableVec[ElemSeg.getIdx()].first)})
        .map_error([](auto E) {
          spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
          return E;
        });
  }
  return {};
}

// Validate Code segment. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::CodeSegment &CodeSeg,
                                 const uint32_t TypeIdx) {
  // Due to validation of the function section, the type at this index must
  // be a function type.
  const auto &FuncType =
      Checker.getTypes()[TypeIdx]->getCompositeType().getFuncType();
  // Reset stack in FormChecker.
  Checker.reset();
  // Add parameters to this frame.
  for (auto &Type : FuncType.getParamTypes()) {
    // Local passed by function parameters must have been initialized.
    Checker.addLocal(Type, true);
  }
  // Add locals to this frame.
  for (auto Val : CodeSeg.getLocals()) {
    for (uint32_t Cnt = 0; Cnt < Val.first; ++Cnt) {
      // The local value type should be valid.
      EXPECTED_TRY(Checker.validate(Val.second));
      Checker.addLocal(Val.second, false);
    }
  }
  // Validate function body expression.
  return Checker
      .validate(CodeSeg.getExpr().getInstrs(), FuncType.getReturnTypes())
      .map_error([](auto E) {
        spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
        return E;
      });
}

// Validate Data segment. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::DataSegment &DataSeg) {
  switch (DataSeg.getMode()) {
  case AST::DataSegment::DataMode::Active: {
    // Check memory index in context.
    const auto &MemVec = Checker.getMemories();
    if (DataSeg.getIdx() >= MemVec.size()) {
      spdlog::error(ErrCode::Value::InvalidMemoryIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Memory, DataSeg.getIdx(),
          static_cast<uint32_t>(MemVec.size())));
      return Unexpect(ErrCode::Value::InvalidMemoryIdx);
    }
    // Check memory initialization is a const expression.
    return validateConstExpr(DataSeg.getExpr().getInstrs(),
                             {ValType(MemVec[DataSeg.getIdx()])})
        .map_error([](auto E) {
          spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Expression));
          return E;
        });
  }
  case AST::DataSegment::DataMode::Passive:
    // Passive case is always valid.
    return {};
  default:
    return {};
  }
}

// Validate Import description. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ImportDesc &ImpDesc) {
  switch (ImpDesc.getExternalType()) {
  // External type and external content are ensured to match in the loader
  // phase.
  case ExternalType::Function: {
    const auto TId = ImpDesc.getExternalFuncTypeIdx();
    // Function type index must exist in context and be valid.
    if (TId >= Checker.getTypes().size()) {
      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::FunctionType, TId,
          static_cast<uint32_t>(Checker.getTypes().size())));
      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);
    }
    if (!Checker.getTypes()[TId]->getCompositeType().isFunc()) {
      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);
      spdlog::error("    Defined type index {} is not a function type."sv, TId);
      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);
    }
    Checker.addFunc(TId, true);
    return {};
  }
  case ExternalType::Table: {
    const auto &TabType = ImpDesc.getExternalTableType();
    // Table type must be valid.
    EXPECTED_TRY(validate(TabType).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Table));
      return E;
    }));
    Checker.addTable(TabType);
    return {};
  }
  case ExternalType::Memory: {
    const auto &MemType = ImpDesc.getExternalMemoryType();
    // Memory type must be valid.
    EXPECTED_TRY(validate(MemType).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Memory));
      return E;
    }));
    Checker.addMemory(MemType);
    return {};
  }
  case ExternalType::Tag: {
    const auto &T = ImpDesc.getExternalTagType();
    // Tag type index must exist in context.
    auto TagTypeIdx = T.getTypeIdx();
    if (TagTypeIdx >= Checker.getTypes().size()) {
      spdlog::error(ErrCode::Value::InvalidTagIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::TagType, TagTypeIdx,
          static_cast<uint32_t>(Checker.getTypes().size())));
      return Unexpect(ErrCode::Value::InvalidTagIdx);
    }
    // Tag type must be valid.
    auto &CompType = Checker.getTypes()[TagTypeIdx]->getCompositeType();
    if (!CompType.isFunc()) {
      spdlog::error(ErrCode::Value::InvalidTagIdx);
      spdlog::error("    Defined type index {} is not a function type."sv,
                    TagTypeIdx);
      return Unexpect(ErrCode::Value::InvalidTagIdx);
    }
    if (!CompType.getFuncType().getReturnTypes().empty()) {
      spdlog::error(ErrCode::Value::InvalidTagResultType);
      return Unexpect(ErrCode::Value::InvalidTagResultType);
    }
    Checker.addTag(TagTypeIdx);
    return {};
  }
  case ExternalType::Global: {
    const auto &GlobType = ImpDesc.getExternalGlobalType();
    // Global type must be valid.
    EXPECTED_TRY(validate(GlobType).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Global));
      return E;
    }));
    Checker.addGlobal(GlobType, true);
    return {};
  }
  default:
    return {};
  }
}

// Validate Export description. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ExportDesc &ExpDesc) {
  auto Id = ExpDesc.getExternalIndex();
  switch (ExpDesc.getExternalType()) {
  case ExternalType::Function:
    if (Id >= Checker.getFunctions().size()) {
      spdlog::error(ErrCode::Value::InvalidFuncIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Function, Id,
          static_cast<uint32_t>(Checker.getFunctions().size())));
      return Unexpect(ErrCode::Value::InvalidFuncIdx);
    }
    Checker.addRef(Id);
    return {};
  case ExternalType::Table:
    if (Id >= Checker.getTables().size()) {
      spdlog::error(ErrCode::Value::InvalidTableIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Table, Id,
          static_cast<uint32_t>(Checker.getTables().size())));
      return Unexpect(ErrCode::Value::InvalidTableIdx);
    }
    return {};
  case ExternalType::Memory:
    if (Id >= Checker.getMemories().size()) {
      spdlog::error(ErrCode::Value::InvalidMemoryIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Memory, Id,
          static_cast<uint32_t>(Checker.getMemories().size())));
      return Unexpect(ErrCode::Value::InvalidMemoryIdx);
    }
    return {};
  case ExternalType::Tag:
    if (Id >= Checker.getTags().size()) {
      spdlog::error(ErrCode::Value::InvalidTagIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Tag, Id,
          static_cast<uint32_t>(Checker.getTags().size())));
      return Unexpect(ErrCode::Value::InvalidTagIdx);
    }
    return {};
  case ExternalType::Global:
    if (Id >= Checker.getGlobals().size()) {
      spdlog::error(ErrCode::Value::InvalidGlobalIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Global, Id,
          static_cast<uint32_t>(Checker.getGlobals().size())));
      return Unexpect(ErrCode::Value::InvalidGlobalIdx);
    }
    return {};
  default:
    return {};
  }
}

Expect<void> Validator::validate(const AST::TypeSection &TypeSec) {
  const auto STypeList = TypeSec.getContent();
  std::vector<uint32_t> SubTypeDepthMap(STypeList.size(), Unvisited);
  std::map<std::vector<uint32_t>, uint32_t> RecTypes;
  uint32_t Idx = 0;
  while (Idx < STypeList.size()) {
    const auto &SType = STypeList[Idx];
    // The next type to add takes this index in the type index space.
    const uint32_t BaseIdx = static_cast<uint32_t>(Checker.getTypes().size());
    if (Conf.hasProposal(Proposal::GC)) {
      // With GC a type is (self-)recursive (a singleton is a rec group of 1):
      // add the whole group before validating so members can reference it.
      const uint32_t RecSize = SType.getRecursiveInfo().RecTypeSize;
      for (uint32_t I = Idx; I < Idx + RecSize; I++) {
        Checker.addType(STypeList[I]);
      }
      EXPECTED_TRY(validate(STypeList.subspan(Idx, RecSize), BaseIdx,
                            SubTypeDepthMap, Checker.getTypes())
                       .map_error([](auto E) {
                         spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Rec));
                         return E;
                       }));
      setCanonicalIndices(STypeList.subspan(Idx, RecSize), BaseIdx,
                          Checker.getTypes(), RecTypes);
      Idx += RecSize;
    } else {
      // Without GC there are no rec groups: a type may reference only earlier
      // ones, so validate it before registering.
      EXPECTED_TRY(
          validate(SType, BaseIdx, SubTypeDepthMap, Checker.getTypes()));
      Checker.addType(SType);
      setCanonicalIndices(STypeList.subspan(Idx, 1), BaseIdx,
                          Checker.getTypes(), RecTypes);
      Idx++;
    }
  }
  return {};
}

// Validate Import section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ImportSection &ImportSec) {
  for (auto &ImportDesc : ImportSec.getContent()) {
    EXPECTED_TRY(validate(ImportDesc).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Desc_Import));
      return E;
    }));
  }
  return {};
}

// Validate Function section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::FunctionSection &FuncSec) {
  const auto &FuncVec = FuncSec.getContent();
  const auto &TypeVec = Checker.getTypes();

  // Check whether the function type ID is valid in context.
  for (auto &TId : FuncVec) {
    if (TId >= TypeVec.size()) {
      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);
      spdlog::error(
          ErrInfo::InfoForbidIndex(ErrInfo::IndexCategory::FunctionType, TId,
                                   static_cast<uint32_t>(TypeVec.size())));
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Function));
      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);
    }
    if (!TypeVec[TId]->getCompositeType().isFunc()) {
      spdlog::error(ErrCode::Value::InvalidFuncTypeIdx);
      spdlog::error("    Defined type index {} is not a function type."sv, TId);
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Function));
      return Unexpect(ErrCode::Value::InvalidFuncTypeIdx);
    }
    Checker.addFunc(TId);
  }
  return {};
}

// Validate Table section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::TableSection &TabSec) {
  for (auto &Tab : TabSec.getContent()) {
    EXPECTED_TRY(validate(Tab).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Seg_Table));
      return E;
    }));
    Checker.addTable(Tab.getTableType());
  }
  return {};
}

// Validate Memory section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::MemorySection &MemSec) {
  for (auto &Mem : MemSec.getContent()) {
    EXPECTED_TRY(validate(Mem).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Type_Memory));
      return E;
    }));
    Checker.addMemory(Mem);
  }
  return {};
}

// Validate Global section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::GlobalSection &GlobSec) {
  for (auto &GlobSeg : GlobSec.getContent()) {
    EXPECTED_TRY(validate(GlobSeg).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Seg_Global));
      return E;
    }));
    Checker.addGlobal(GlobSeg.getGlobalType());
  }
  return {};
}

// Validate Element section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ElementSection &ElemSec) {
  for (auto &ElemSeg : ElemSec.getContent()) {
    EXPECTED_TRY(validate(ElemSeg).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Seg_Element));
      return E;
    }));
    Checker.addElem(ElemSeg);
  }
  return {};
}

// Validate Code section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::CodeSection &CodeSec) {
  const auto &CodeVec = CodeSec.getContent();
  const auto &FuncVec = Checker.getFunctions();

  // Validate function body.
  for (uint32_t Id = 0; Id < static_cast<uint32_t>(CodeVec.size()); ++Id) {
    // Added functions contain imported functions.
    uint32_t TId = Id + static_cast<uint32_t>(Checker.getNumImportFuncs());
    if (TId >= static_cast<uint32_t>(FuncVec.size())) {
      spdlog::error(ErrCode::Value::InvalidFuncIdx);
      spdlog::error(
          ErrInfo::InfoForbidIndex(ErrInfo::IndexCategory::Function, TId,
                                   static_cast<uint32_t>(FuncVec.size())));
      return Unexpect(ErrCode::Value::InvalidFuncIdx);
    }
    EXPECTED_TRY(validate(CodeVec[Id], FuncVec[TId]).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Seg_Code));
      return E;
    }));
  }
  return {};
}

// Validate Data section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::DataSection &DataSec) {
  for (auto &DataSeg : DataSec.getContent()) {
    EXPECTED_TRY(validate(DataSeg).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Seg_Data));
      return E;
    }));
    Checker.addData(DataSeg);
  }
  return {};
}

// Validate Start section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::StartSection &StartSec) {
  if (StartSec.getContent()) {
    auto FId = *StartSec.getContent();
    if (FId >= Checker.getFunctions().size()) {
      spdlog::error(ErrCode::Value::InvalidFuncIdx);
      spdlog::error(ErrInfo::InfoForbidIndex(
          ErrInfo::IndexCategory::Function, FId,
          static_cast<uint32_t>(Checker.getFunctions().size())));
      return Unexpect(ErrCode::Value::InvalidFuncIdx);
    }
    auto TId = Checker.getFunctions()[FId];
    assuming(TId < Checker.getTypes().size());
    if (!Checker.getTypes()[TId]->getCompositeType().isFunc()) {
      spdlog::error(ErrCode::Value::InvalidStartFunc);
      spdlog::error("    Defined type index {} is not a function type."sv, TId);
      return Unexpect(ErrCode::Value::InvalidStartFunc);
    }
    auto &Type = Checker.getTypes()[TId]->getCompositeType().getFuncType();
    if (Type.getParamTypes().size() != 0 || Type.getReturnTypes().size() != 0) {
      // Start function signature should be {}->{}
      spdlog::error(ErrCode::Value::InvalidStartFunc);
      spdlog::error(ErrInfo::InfoMismatch({}, {}, Type.getParamTypes(),
                                          Type.getReturnTypes()));
      return Unexpect(ErrCode::Value::InvalidStartFunc);
    }
  }
  return {};
}

// Validate Export section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::ExportSection &ExportSec) {
  std::unordered_set<std::string_view, Hash::Hash> ExportNames;
  for (auto &ExportDesc : ExportSec.getContent()) {
    auto Result = ExportNames.emplace(ExportDesc.getExternalName());
    if (!Result.second) {
      // Duplicated export name.
      spdlog::error(ErrCode::Value::DupExportName);
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Desc_Export));
      return Unexpect(ErrCode::Value::DupExportName);
    }
    EXPECTED_TRY(validate(ExportDesc).map_error([](auto E) {
      spdlog::error(ErrInfo::InfoAST(ASTNodeAttr::Desc_Export));
      return E;
    }));
  }
  return {};
}

// Validate Tag section. See "include/validator/validator.h".
Expect<void> Validator::validate(const AST::TagSection &TagSec) {
  const auto &TagVec = TagSec.getContent();
  const auto &TypeVec = Checker.getTypes();

  // Check whether the tag type ID is valid in context.
  for (auto &TagType : TagVec) {
    auto TagTypeIdx = TagType.getTypeIdx();
    if (TagTypeIdx >= TypeVec.size()) {
      spdlog::error(ErrCode::Value::InvalidTagIdx);
      spdlog::error(
          ErrInfo::InfoForbidIndex(ErrInfo::IndexCategory::TagType, TagTypeIdx,
                                   static_cast<uint32_t>(TypeVec.size())));
      return Unexpect(ErrCode::Value::InvalidTagIdx);
    }
    auto &CompType = TypeVec[TagTypeIdx]->getCompositeType();
    if (!CompType.isFunc()) {
      spdlog::error(ErrCode::Value::InvalidTagIdx);
      spdlog::error("    Defined type index {} is not a function type."sv,
                    TagTypeIdx);
      return Unexpect(ErrCode::Value::InvalidTagIdx);
    }
    if (!CompType.getFuncType().getReturnTypes().empty()) {
      spdlog::error(ErrCode::Value::InvalidTagResultType);
      return Unexpect(ErrCode::Value::InvalidTagResultType);
    }
    Checker.addTag(TagTypeIdx);
  }
  return {};
}

// Validate constant expression. See "include/validator/validator.h".
Expect<void> Validator::validateConstExpr(AST::InstrView Instrs,
                                          Span<const ValType> Returns) {
  for (auto &Instr : Instrs) {
    // Only these instructions are accepted.
    switch (Instr.getOpCode()) {
    case OpCode::Global__get: {
      // For the initialization case, global indices must be imported globals.
      auto GlobIdx = Instr.getTargetIndex();
      uint32_t ValidGlobalSize = Checker.getNumImportGlobals();
      if (Conf.hasProposal(Proposal::FunctionReferences)) {
        ValidGlobalSize = static_cast<uint32_t>(Checker.getGlobals().size());
      }
      if (GlobIdx >= ValidGlobalSize) {
        spdlog::error(ErrCode::Value::InvalidGlobalIdx);
        spdlog::error(ErrInfo::InfoForbidIndex(ErrInfo::IndexCategory::Global,
                                               GlobIdx, ValidGlobalSize));
        spdlog::error(
            ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));
        return Unexpect(ErrCode::Value::InvalidGlobalIdx);
      }
      if (Checker.getGlobals()[GlobIdx].second != ValMut::Const) {
        spdlog::error(ErrCode::Value::ConstExprRequired);
        spdlog::error(
            ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));
        return Unexpect(ErrCode::Value::ConstExprRequired);
      }
      break;
    }
    case OpCode::Ref__func: {
      // In a const expression, add the reference to the context.
      auto FuncIdx = Instr.getTargetIndex();
      if (FuncIdx >= Checker.getFunctions().size()) {
        // Function index out of range.
        spdlog::error(ErrCode::Value::InvalidFuncIdx);
        spdlog::error(ErrInfo::InfoForbidIndex(
            ErrInfo::IndexCategory::Function, FuncIdx,
            static_cast<uint32_t>(Checker.getFunctions().size())));
        spdlog::error(
            ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));
        return Unexpect(ErrCode::Value::InvalidFuncIdx);
      }
      Checker.addRef(Instr.getTargetIndex());
      break;
    }
    case OpCode::I32__const:
    case OpCode::I64__const:
    case OpCode::F32__const:
    case OpCode::F64__const:
    case OpCode::Ref__null:
    case OpCode::V128__const:
    case OpCode::End:
    case OpCode::Struct__new:
    case OpCode::Struct__new_default:
    case OpCode::Array__new:
    case OpCode::Array__new_default:
    case OpCode::Array__new_fixed:
    case OpCode::Any__convert_extern:
    case OpCode::Extern__convert_any:
    case OpCode::Ref__i31:
      break;

    // For the Extended-const proposal, these instructions are accepted.
    case OpCode::I32__add:
    case OpCode::I32__sub:
    case OpCode::I32__mul:
    case OpCode::I64__add:
    case OpCode::I64__sub:
    case OpCode::I64__mul:
      if (Conf.hasProposal(Proposal::ExtendedConst)) {
        break;
      }
      spdlog::error(ErrCode::Value::ConstExprRequired);
      spdlog::error(ErrInfo::InfoProposal(Proposal::ExtendedConst));
      spdlog::error(
          ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));
      return Unexpect(ErrCode::Value::ConstExprRequired);

    default:
      spdlog::error(ErrCode::Value::ConstExprRequired);
      spdlog::error(
          ErrInfo::InfoInstruction(Instr.getOpCode(), Instr.getOffset()));
      return Unexpect(ErrCode::Value::ConstExprRequired);
    }
  }
  // Validate expression with result types.
  Checker.reset();
  return Checker.validate(Instrs, Returns);
}

} // namespace Validator
} // namespace WasmEdge

Coverage Report

Created: 2026-11-12 06:35