feat: implement validation phaseHEADmain

11 files changed, 1726 insertions, 5 deletions

diff --git a/TODO b/TODO
index 37a5ced..5e21bb4 100644
--- a/TODO
+++ b/TODO
@@ -1,5 +1,4 @@
 * Support text format (.wat)
-* Implement validation
 * Provide sane bindings to PHP
 * Write PHPDoc for public APIs
 * Provide high-level APIs
diff --git a/src/WebAssembly/BinaryFormat/Decoder.php b/src/WebAssembly/BinaryFormat/Decoder.php
index 90b1706..87e5640 100644
--- a/src/WebAssembly/BinaryFormat/Decoder.php
+++ b/src/WebAssembly/BinaryFormat/Decoder.php
@@ -38,7 +38,6 @@ use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
 use function array_reduce;
 use function assert;
 use function count;
-use function get_class;
 use function in_array;
 use function is_int;
 use function ord;
@@ -980,7 +979,7 @@ final class Decoder
         $result = [];
         while (true) {
             $instr = $this->decodeInstr();
-            if (in_array(get_class($instr), $delimiters, true)) {
+            if (in_array($instr::class, $delimiters, true)) {
                 return [$result, $instr];
             }
             $result[] = $instr;
diff --git a/src/WebAssembly/Structure/Types/ValType.php b/src/WebAssembly/Structure/Types/ValType.php
index ace4604..02e1113 100644
--- a/src/WebAssembly/Structure/Types/ValType.php
+++ b/src/WebAssembly/Structure/Types/ValType.php
@@ -13,4 +13,28 @@ enum ValType
     case V128;
     case FuncRef;
     case ExternRef;
+
+    public function isNum(): bool
+    {
+        return match ($this) {
+            ValType::I32 , ValType::I64 , ValType::F32 , ValType::F64 => true,
+            default => false,
+        };
+    }
+
+    public function isVec(): bool
+    {
+        return match ($this) {
+            ValType::V128 => true,
+            default => false,
+        };
+    }
+
+    public function isRef(): bool
+    {
+        return match ($this) {
+            ValType::FuncRef , ValType::ExternRef => true,
+            default => false,
+        };
+    }
 }
diff --git a/src/WebAssembly/Validation/Context.php b/src/WebAssembly/Validation/Context.php
new file mode 100644
index 0000000..e63fb0d
--- /dev/null
+++ b/src/WebAssembly/Validation/Context.php
@@ -0,0 +1,42 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\FuncType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\GlobalType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\MemType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\TableType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+
+final readonly class Context
+{
+    /**
+     * @param list<FuncType> $types
+     * @param list<FuncType> $funcs
+     * @param list<TableType> $tables
+     * @param list<MemType> $mems
+     * @param list<GlobalType> $globals
+     * @param list<ValType> $elems
+     * @param list<bool> $datas
+     * @param list<ValType> $locals
+     * @param list<list<ValType>> $labels
+     * @param list<ValType> $return
+     * @param list<int> $refs
+     */
+    public function __construct(
+        public array $types,
+        public array $funcs,
+        public array $tables,
+        public array $mems,
+        public array $globals,
+        public array $elems,
+        public array $datas,
+        public array $locals,
+        public array $labels,
+        public array $return,
+        public array $refs,
+    ) {
+    }
+}
diff --git a/src/WebAssembly/Validation/ControlFrame.php b/src/WebAssembly/Validation/ControlFrame.php
new file mode 100644
index 0000000..e956b4c
--- /dev/null
+++ b/src/WebAssembly/Validation/ControlFrame.php
@@ -0,0 +1,24 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+
+final readonly class ControlFrame
+{
+    /**
+     * @param class-string $opcode
+     * @param list<ValType> $startTypes
+     * @param list<ValType> $endTypes
+     */
+    public function __construct(
+        public string $opcode,
+        public array $startTypes,
+        public array $endTypes,
+        public int $height,
+        public bool $unreachable,
+    ) {
+    }
+}
diff --git a/src/WebAssembly/Validation/FunctionValidator.php b/src/WebAssembly/Validation/FunctionValidator.php
new file mode 100644
index 0000000..2b94f02
--- /dev/null
+++ b/src/WebAssembly/Validation/FunctionValidator.php
@@ -0,0 +1,1015 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instr;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instrs;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instrs\Control\BlockType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instrs\Control\BlockTypes;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\FuncType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\Mut;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+use function count;
+use function in_array;
+
+final class FunctionValidator
+{
+    /**
+     * @var list<string>
+     */
+    private array $errors = [];
+
+    public function __construct(
+        private readonly Context $context,
+        private readonly ValidationStack $validationStack,
+    ) {
+    }
+
+    /**
+     * @param list<Instr> $body
+     * @return list<string>
+     */
+    public function validate(array $body): array
+    {
+        $this->validateInstrs($body);
+        $this->validateEnd();
+
+        return $this->errors;
+    }
+
+    /**
+     * @param list<Instr> $instrs
+     */
+    private function validateInstrs(array $instrs): void
+    {
+        foreach ($instrs as $instr) {
+            $this->validateInstr($instr);
+        }
+    }
+
+    private function validateInstr(Instr $instr): void
+    {
+        switch ($instr::class) {
+            case Instrs\Numeric\I32Const::class:
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I64Const::class:
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\F32Const::class:
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F64Const::class:
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\I32Eqz::class:
+            case Instrs\Numeric\I32Clz::class:
+            case Instrs\Numeric\I32Ctz::class:
+            case Instrs\Numeric\I32Popcnt::class:
+            case Instrs\Numeric\I32Extend8S::class:
+            case Instrs\Numeric\I32Extend16S::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I32Add::class:
+            case Instrs\Numeric\I32Sub::class:
+            case Instrs\Numeric\I32Mul::class:
+            case Instrs\Numeric\I32DivS::class:
+            case Instrs\Numeric\I32DivU::class:
+            case Instrs\Numeric\I32RemS::class:
+            case Instrs\Numeric\I32RemU::class:
+            case Instrs\Numeric\I32And::class:
+            case Instrs\Numeric\I32Or::class:
+            case Instrs\Numeric\I32Xor::class:
+            case Instrs\Numeric\I32Shl::class:
+            case Instrs\Numeric\I32ShrS::class:
+            case Instrs\Numeric\I32ShrU::class:
+            case Instrs\Numeric\I32RotL::class:
+            case Instrs\Numeric\I32RotR::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I32Eq::class:
+            case Instrs\Numeric\I32Ne::class:
+            case Instrs\Numeric\I32LtS::class:
+            case Instrs\Numeric\I32LtU::class:
+            case Instrs\Numeric\I32GtS::class:
+            case Instrs\Numeric\I32GtU::class:
+            case Instrs\Numeric\I32LeS::class:
+            case Instrs\Numeric\I32LeU::class:
+            case Instrs\Numeric\I32GeS::class:
+            case Instrs\Numeric\I32GeU::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I64Eqz::class:
+            case Instrs\Numeric\I64Clz::class:
+            case Instrs\Numeric\I64Ctz::class:
+            case Instrs\Numeric\I64Popcnt::class:
+            case Instrs\Numeric\I64Extend8S::class:
+            case Instrs\Numeric\I64Extend16S::class:
+            case Instrs\Numeric\I64Extend32S::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\I64Add::class:
+            case Instrs\Numeric\I64Sub::class:
+            case Instrs\Numeric\I64Mul::class:
+            case Instrs\Numeric\I64DivS::class:
+            case Instrs\Numeric\I64DivU::class:
+            case Instrs\Numeric\I64RemS::class:
+            case Instrs\Numeric\I64RemU::class:
+            case Instrs\Numeric\I64And::class:
+            case Instrs\Numeric\I64Or::class:
+            case Instrs\Numeric\I64Xor::class:
+            case Instrs\Numeric\I64Shl::class:
+            case Instrs\Numeric\I64ShrS::class:
+            case Instrs\Numeric\I64ShrU::class:
+            case Instrs\Numeric\I64RotL::class:
+            case Instrs\Numeric\I64RotR::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\I64Eq::class:
+            case Instrs\Numeric\I64Ne::class:
+            case Instrs\Numeric\I64LtS::class:
+            case Instrs\Numeric\I64LtU::class:
+            case Instrs\Numeric\I64GtS::class:
+            case Instrs\Numeric\I64GtU::class:
+            case Instrs\Numeric\I64LeS::class:
+            case Instrs\Numeric\I64LeU::class:
+            case Instrs\Numeric\I64GeS::class:
+            case Instrs\Numeric\I64GeU::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\F32Abs::class:
+            case Instrs\Numeric\F32Neg::class:
+            case Instrs\Numeric\F32Ceil::class:
+            case Instrs\Numeric\F32Floor::class:
+            case Instrs\Numeric\F32Trunc::class:
+            case Instrs\Numeric\F32Nearest::class:
+            case Instrs\Numeric\F32Sqrt::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F32Add::class:
+            case Instrs\Numeric\F32Sub::class:
+            case Instrs\Numeric\F32Mul::class:
+            case Instrs\Numeric\F32Div::class:
+            case Instrs\Numeric\F32Min::class:
+            case Instrs\Numeric\F32Max::class:
+            case Instrs\Numeric\F32CopySign::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F32Eq::class:
+            case Instrs\Numeric\F32Ne::class:
+            case Instrs\Numeric\F32Lt::class:
+            case Instrs\Numeric\F32Gt::class:
+            case Instrs\Numeric\F32Le::class:
+            case Instrs\Numeric\F32Ge::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\F64Abs::class:
+            case Instrs\Numeric\F64Neg::class:
+            case Instrs\Numeric\F64Ceil::class:
+            case Instrs\Numeric\F64Floor::class:
+            case Instrs\Numeric\F64Trunc::class:
+            case Instrs\Numeric\F64Nearest::class:
+            case Instrs\Numeric\F64Sqrt::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\F64Add::class:
+            case Instrs\Numeric\F64Sub::class:
+            case Instrs\Numeric\F64Mul::class:
+            case Instrs\Numeric\F64Div::class:
+            case Instrs\Numeric\F64Min::class:
+            case Instrs\Numeric\F64Max::class:
+            case Instrs\Numeric\F64CopySign::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\F64Eq::class:
+            case Instrs\Numeric\F64Ne::class:
+            case Instrs\Numeric\F64Lt::class:
+            case Instrs\Numeric\F64Gt::class:
+            case Instrs\Numeric\F64Le::class:
+            case Instrs\Numeric\F64Ge::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I32WrapI64::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I32TruncF32S::class:
+            case Instrs\Numeric\I32TruncF32U::class:
+            case Instrs\Numeric\I32TruncSatF32S::class:
+            case Instrs\Numeric\I32TruncSatF32U::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I32TruncF64S::class:
+            case Instrs\Numeric\I32TruncF64U::class:
+            case Instrs\Numeric\I32TruncSatF64S::class:
+            case Instrs\Numeric\I32TruncSatF64U::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I64ExtendI32S::class:
+            case Instrs\Numeric\I64ExtendI32U::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\I64TruncF32S::class:
+            case Instrs\Numeric\I64TruncF32U::class:
+            case Instrs\Numeric\I64TruncSatF32S::class:
+            case Instrs\Numeric\I64TruncSatF32U::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\I64TruncF64S::class:
+            case Instrs\Numeric\I64TruncF64U::class:
+            case Instrs\Numeric\I64TruncSatF64S::class:
+            case Instrs\Numeric\I64TruncSatF64U::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\F32ConvertI32S::class:
+            case Instrs\Numeric\F32ConvertI32U::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F32ConvertI64S::class:
+            case Instrs\Numeric\F32ConvertI64U::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F32DemoteF64::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F64ConvertI32S::class:
+            case Instrs\Numeric\F64ConvertI32U::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\F64ConvertI64S::class:
+            case Instrs\Numeric\F64ConvertI64U::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\F64PromoteF32::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\I32ReinterpretF32::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I64ReinterpretF64::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\F32ReinterpretI32::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F64ReinterpretI64::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Numeric\I32ReinterpretF64::class:
+                $this->validationStack->popValOf(ValType::F64);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Numeric\I64ReinterpretF32::class:
+                $this->validationStack->popValOf(ValType::F32);
+                $this->validationStack->pushVal(ValType::I64);
+                break;
+
+            case Instrs\Numeric\F32ReinterpretI64::class:
+                $this->validationStack->popValOf(ValType::I64);
+                $this->validationStack->pushVal(ValType::F32);
+                break;
+
+            case Instrs\Numeric\F64ReinterpretI32::class:
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::F64);
+                break;
+
+            case Instrs\Parametric\Drop::class:
+                $this->validationStack->popVal();
+                break;
+
+            case Instrs\Parametric\Select::class:
+                $this->validateSelect();
+                break;
+
+            case Instrs\Control\Nop::class:
+                break;
+
+            case Instrs\Control\Unreachable::class:
+                $this->validationStack->unreachable();
+                break;
+
+            case Instrs\Control\Block::class:
+                $this->validateBlock($instr);
+                break;
+
+            case Instrs\Control\Loop::class:
+                $this->validateLoop($instr);
+                break;
+
+            case Instrs\Control\If_::class:
+                $this->validateIf($instr);
+                break;
+
+            case Instrs\Control\End::class:
+                $this->validateEnd();
+                break;
+
+            case Instrs\Control\Else_::class:
+                $this->validateElse($instr);
+                break;
+
+            case Instrs\Control\Br::class:
+                $this->validateBr($instr);
+                break;
+
+            case Instrs\Control\BrIf::class:
+                $this->validateBrIf($instr);
+                break;
+
+            case Instrs\Control\BrTable::class:
+                $this->validateBrTable($instr);
+                break;
+
+            case Instrs\Control\Call::class:
+                $this->validateCall($instr);
+                break;
+
+            case Instrs\Control\CallIndirect::class:
+                $this->validateCallIndirect($instr);
+                break;
+
+            case Instrs\Control\Return_::class:
+                $this->validateReturn();
+                break;
+
+            case Instrs\Variable\LocalGet::class:
+                $this->validateLocalGet($instr);
+                break;
+
+            case Instrs\Variable\LocalSet::class:
+                $this->validateLocalSet($instr);
+                break;
+
+            case Instrs\Variable\LocalTee::class:
+                $this->validateLocalTee($instr);
+                break;
+
+            case Instrs\Variable\GlobalGet::class:
+                $this->validateGlobalGet($instr);
+                break;
+
+            case Instrs\Variable\GlobalSet::class:
+                $this->validateGlobalSet($instr);
+                break;
+
+            case Instrs\Reference\RefNull::class:
+                $this->validateRefNull($instr);
+                break;
+
+            case Instrs\Reference\RefIsNull::class:
+                $this->validateRefIsNull();
+                break;
+
+            case Instrs\Reference\RefFunc::class:
+                $this->validateRefFunc($instr);
+                break;
+
+            case Instrs\Table\TableGet::class:
+                $this->validateTableGet($instr);
+                break;
+
+            case Instrs\Table\TableSet::class:
+                $this->validateTableSet($instr);
+                break;
+
+            case Instrs\Table\TableSize::class:
+                $this->validateTableSize($instr);
+                break;
+
+            case Instrs\Table\TableGrow::class:
+                $this->validateTableGrow($instr);
+                break;
+
+            case Instrs\Table\TableFill::class:
+                $this->validateTableFill($instr);
+                break;
+
+            case Instrs\Table\TableCopy::class:
+                $this->validateTableCopy($instr);
+                break;
+
+            case Instrs\Table\TableInit::class:
+                $this->validateTableInit($instr);
+                break;
+
+            case Instrs\Table\ElemDrop::class:
+                $this->validateElemDrop($instr);
+                break;
+
+            case Instrs\Memory\I32Load::class:
+                $this->validateMemLoad($instr->align, 4, ValType::I32);
+                break;
+
+            case Instrs\Memory\I32Load8S::class:
+            case Instrs\Memory\I32Load8U::class:
+                $this->validateMemLoad($instr->align, 1, ValType::I32);
+                break;
+
+            case Instrs\Memory\I32Load16S::class:
+            case Instrs\Memory\I32Load16U::class:
+                $this->validateMemLoad($instr->align, 2, ValType::I32);
+                break;
+
+            case Instrs\Memory\I64Load::class:
+                $this->validateMemLoad($instr->align, 8, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Load8S::class:
+            case Instrs\Memory\I64Load8U::class:
+                $this->validateMemLoad($instr->align, 1, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Load16S::class:
+            case Instrs\Memory\I64Load16U::class:
+                $this->validateMemLoad($instr->align, 2, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Load32S::class:
+            case Instrs\Memory\I64Load32U::class:
+                $this->validateMemLoad($instr->align, 4, ValType::I64);
+                break;
+
+            case Instrs\Memory\F32Load::class:
+                $this->validateMemLoad($instr->align, 4, ValType::F32);
+                break;
+
+            case Instrs\Memory\F64Load::class:
+                $this->validateMemLoad($instr->align, 8, ValType::F64);
+                break;
+
+            case Instrs\Memory\I32Store::class:
+                $this->validateMemStore($instr->align, 4, ValType::I32);
+                break;
+
+            case Instrs\Memory\I32Store8::class:
+                $this->validateMemStore($instr->align, 1, ValType::I32);
+                break;
+
+            case Instrs\Memory\I32Store16::class:
+                $this->validateMemStore($instr->align, 2, ValType::I32);
+                break;
+
+            case Instrs\Memory\I64Store::class:
+                $this->validateMemStore($instr->align, 8, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Store8::class:
+                $this->validateMemStore($instr->align, 1, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Store16::class:
+                $this->validateMemStore($instr->align, 2, ValType::I64);
+                break;
+
+            case Instrs\Memory\I64Store32::class:
+                $this->validateMemStore($instr->align, 4, ValType::I64);
+                break;
+
+            case Instrs\Memory\F32Store::class:
+                $this->validateMemStore($instr->align, 4, ValType::F32);
+                break;
+
+            case Instrs\Memory\F64Store::class:
+                $this->validateMemStore($instr->align, 8, ValType::F64);
+                break;
+
+            case Instrs\Memory\MemorySize::class:
+                $this->validateMemoryExists();
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Memory\MemoryGrow::class:
+                $this->validateMemoryExists();
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->pushVal(ValType::I32);
+                break;
+
+            case Instrs\Memory\MemoryFill::class:
+                $this->validateMemoryExists();
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                break;
+
+            case Instrs\Memory\MemoryCopy::class:
+                $this->validateMemoryExists();
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                $this->validationStack->popValOf(ValType::I32);
+                break;
+
+            case Instrs\Memory\MemoryInit::class:
+                $this->validateMemoryInit($instr);
+                break;
+
+            case Instrs\Memory\DataDrop::class:
+                $this->validateDataDrop($instr);
+                break;
+
+            default:
+                $this->addError('Unsupported instruction: ' . $instr::class);
+        }
+    }
+
+    private function validateSelect(): void
+    {
+        $this->validationStack->popValOf(ValType::I32);
+        $t1 = $this->validationStack->popVal();
+        $t2 = $this->validationStack->popVal();
+        if (! (($t1 === null || $t1->isNum()) && ($t2 === null || $t2->isNum()) ||
+               ($t1 === null || $t1->isVec()) && ($t2 === null || $t2->isVec()))) {
+            $this->addError('Invalid select operand types');
+            return;
+        }
+        if ($t1 !== $t2 && $t1 !== null && $t2 !== null) {
+            $this->addError('Type mismatch in select');
+        }
+        $this->validationStack->pushVal($t1 ?? $t2);
+    }
+
+    private function validateBlock(Instrs\Control\Block $instr): void
+    {
+        [$t1, $t2] = $this->extractBlockTypes($instr->type);
+        $this->validationStack->popVals($t1);
+        $this->validationStack->pushCtrl($instr::class, $t1, $t2);
+        $this->validateInstrs($instr->body);
+        $ctrl = $this->validationStack->popCtrl();
+        $this->validationStack->pushVals($ctrl->endTypes);
+    }
+
+    private function validateLoop(Instrs\Control\Loop $instr): void
+    {
+        [$t1, $t2] = $this->extractBlockTypes($instr->type);
+        $this->validationStack->popVals($t1);
+        $this->validationStack->pushCtrl($instr::class, $t1, $t2);
+        $this->validateInstrs($instr->body);
+        $ctrl = $this->validationStack->popCtrl();
+        $this->validationStack->pushVals($ctrl->endTypes);
+    }
+
+    private function validateIf(Instrs\Control\If_ $instr): void
+    {
+        [$t1, $t2] = $this->extractBlockTypes($instr->type);
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popVals($t1);
+        $this->validationStack->pushCtrl($instr::class, $t1, $t2);
+        $this->validateInstrs($instr->thenBody);
+        $ctrl = $this->validationStack->popCtrl();
+        $this->validationStack->pushCtrl(Instrs\Control\Else_::class, $ctrl->startTypes, $ctrl->endTypes);
+        $this->validateInstrs($instr->elseBody);
+        $ctrl = $this->validationStack->popCtrl();
+        $this->validationStack->pushVals($ctrl->endTypes);
+    }
+
+    private function validateEnd(): void
+    {
+        $ctrl = $this->validationStack->popCtrl();
+        $this->validationStack->pushVals($ctrl->endTypes);
+    }
+
+    private function validateElse(Instrs\Control\Else_ $instr): void
+    {
+        $ctrl = $this->validationStack->popCtrl();
+        if ($ctrl->opcode !== Instrs\Control\If_::class) {
+            $this->addError('else without matching if');
+            return;
+        }
+        $this->validationStack->pushCtrl($instr::class, $ctrl->startTypes, $ctrl->endTypes);
+    }
+
+    private function validateBr(Instrs\Control\Br $instr): void
+    {
+        $ctrl = $this->validationStack->getControl($instr->label);
+        if ($ctrl === null) {
+            $this->addError('Invalid label index');
+            return;
+        }
+        $this->validationStack->popVals($this->validationStack->labelTypes($ctrl));
+        $this->validationStack->unreachable();
+    }
+
+    private function validateBrIf(Instrs\Control\BrIf $instr): void
+    {
+        $ctrl = $this->validationStack->getControl($instr->label);
+        if ($ctrl === null) {
+            $this->addError('Invalid label index');
+            return;
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $labelType = $this->validationStack->labelTypes($ctrl);
+        $this->validationStack->popVals($labelType);
+        $this->validationStack->pushVals($labelType);
+    }
+
+    private function validateBrTable(Instrs\Control\BrTable $instr): void
+    {
+        $this->validationStack->popValOf(ValType::I32);
+
+        $defaultCtrl = $this->validationStack->getControl($instr->defaultLabel);
+        if ($defaultCtrl === null) {
+            $this->addError('Invalid default label');
+            return;
+        }
+        $arity = count($this->validationStack->labelTypes($defaultCtrl));
+
+        foreach ($instr->labelTable as $labelIdx) {
+            $labelCtrl = $this->validationStack->getControl($labelIdx);
+            if ($labelCtrl === null) {
+                $this->addError('Invalid label index');
+                return;
+            }
+            if (count($this->validationStack->labelTypes($labelCtrl)) !== $arity) {
+                $this->addError('Inconsistent label arity');
+                return;
+            }
+            $types = $this->validationStack->labelTypes($labelCtrl);
+            $this->validationStack->pushVals($this->validationStack->popVals($types));
+        }
+
+        $this->validationStack->popVals($this->validationStack->labelTypes($defaultCtrl));
+        $this->validationStack->unreachable();
+    }
+
+    private function validateCall(Instrs\Control\Call $instr): void
+    {
+        $funcIdx = $instr->func;
+        if (! isset($this->context->funcs[$funcIdx])) {
+            $this->addError("Invalid function index: {$funcIdx}");
+            return;
+        }
+        $funcType = $this->context->funcs[$funcIdx];
+        $this->validationStack->popVals($funcType->params);
+        $this->validationStack->pushVals($funcType->results);
+    }
+
+    private function validateCallIndirect(Instrs\Control\CallIndirect $instr): void
+    {
+        $tableIdx = $instr->funcTable;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $tableType = $this->context->tables[$tableIdx];
+        if ($tableType->refType !== ValType::FuncRef) {
+            $this->addError('call_indirect requires a table with funcref element type');
+        }
+        $typeIdx = $instr->type;
+        if (! isset($this->context->types[$typeIdx])) {
+            $this->addError("Invalid type index: {$typeIdx}");
+            return;
+        }
+        $funcType = $this->context->types[$typeIdx];
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popVals($funcType->params);
+        $this->validationStack->pushVals($funcType->results);
+    }
+
+    private function validateReturn(): void
+    {
+        $this->validationStack->popVals($this->context->return);
+        $this->validationStack->unreachable();
+    }
+
+    private function validateLocalGet(Instrs\Variable\LocalGet $instr): void
+    {
+        $localIdx = $instr->var;
+        if (! isset($this->context->locals[$localIdx])) {
+            $this->addError("Invalid local index: {$localIdx}");
+            return;
+        }
+        $localType = $this->context->locals[$localIdx];
+        $this->validationStack->pushVal($localType);
+    }
+
+    private function validateLocalSet(Instrs\Variable\LocalSet $instr): void
+    {
+        $localIdx = $instr->var;
+        if (! isset($this->context->locals[$localIdx])) {
+            $this->addError("Invalid local index: {$localIdx}");
+            return;
+        }
+        $localType = $this->context->locals[$localIdx];
+        $this->validationStack->popValOf($localType);
+    }
+
+    private function validateLocalTee(Instrs\Variable\LocalTee $instr): void
+    {
+        $localIdx = $instr->var;
+        if (! isset($this->context->locals[$localIdx])) {
+            $this->addError("Invalid local index: {$localIdx}");
+            return;
+        }
+        $type = $this->context->locals[$localIdx];
+        $this->validationStack->popValOf($type);
+        $this->validationStack->pushVal($type);
+    }
+
+    private function validateGlobalGet(Instrs\Variable\GlobalGet $instr): void
+    {
+        $globalIdx = $instr->var;
+        if (! isset($this->context->globals[$globalIdx])) {
+            $this->addError("Invalid global index: {$globalIdx}");
+            return;
+        }
+        $this->validationStack->pushVal($this->context->globals[$globalIdx]->valType);
+    }
+
+    private function validateGlobalSet(Instrs\Variable\GlobalSet $instr): void
+    {
+        $globalIdx = $instr->var;
+        if (! isset($this->context->globals[$globalIdx])) {
+            $this->addError("Invalid global index: {$globalIdx}");
+            return;
+        }
+        $globalType = $this->context->globals[$globalIdx];
+        if ($globalType->mut !== Mut::Var) {
+            $this->addError('Cannot set immutable global');
+        }
+        $this->validationStack->popValOf($globalType->valType);
+    }
+
+    private function validateRefNull(Instrs\Reference\RefNull $instr): void
+    {
+        $this->validationStack->pushVal($instr->type);
+    }
+
+    private function validateRefIsNull(): void
+    {
+        $val = $this->validationStack->popVal();
+        if ($val !== null && ! $val->isRef()) {
+            $this->addError('ref.is_null expects a reference type');
+        }
+        $this->validationStack->pushVal(ValType::I32);
+    }
+
+    private function validateRefFunc(Instrs\Reference\RefFunc $instr): void
+    {
+        $funcIdx = $instr->func;
+        if (! isset($this->context->funcs[$funcIdx])) {
+            $this->addError("unknown function {$funcIdx}");
+            return;
+        }
+        if (! in_array($funcIdx, $this->context->refs, true)) {
+            $this->addError('undeclared function reference');
+            return;
+        }
+        $this->validationStack->pushVal(ValType::FuncRef);
+    }
+
+    private function validateTableGet(Instrs\Table\TableGet $instr): void
+    {
+        $tableIdx = $instr->table;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->pushVal($this->context->tables[$tableIdx]->refType);
+    }
+
+    private function validateTableSet(Instrs\Table\TableSet $instr): void
+    {
+        $tableIdx = $instr->table;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $this->validationStack->popValOf($this->context->tables[$tableIdx]->refType);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateTableSize(Instrs\Table\TableSize $instr): void
+    {
+        $tableIdx = $instr->table;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $this->validationStack->pushVal(ValType::I32);
+    }
+
+    private function validateTableGrow(Instrs\Table\TableGrow $instr): void
+    {
+        $tableIdx = $instr->table;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf($this->context->tables[$tableIdx]->refType);
+        $this->validationStack->pushVal(ValType::I32);
+    }
+
+    private function validateTableFill(Instrs\Table\TableFill $instr): void
+    {
+        $tableIdx = $instr->table;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf($this->context->tables[$tableIdx]->refType);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateTableCopy(Instrs\Table\TableCopy $instr): void
+    {
+        $toIdx = $instr->to;
+        $fromIdx = $instr->from;
+        if (! isset($this->context->tables[$toIdx])) {
+            $this->addError("Invalid destination table index: {$toIdx}");
+            return;
+        }
+        if (! isset($this->context->tables[$fromIdx])) {
+            $this->addError("Invalid source table index: {$fromIdx}");
+            return;
+        }
+        if ($this->context->tables[$toIdx]->refType !== $this->context->tables[$fromIdx]->refType) {
+            $this->addError('table.copy requires tables with the same reference type');
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateTableInit(Instrs\Table\TableInit $instr): void
+    {
+        $tableIdx = $instr->to;
+        $elemIdx = $instr->from;
+        if (! isset($this->context->tables[$tableIdx])) {
+            $this->addError("Invalid table index: {$tableIdx}");
+            return;
+        }
+        if (! isset($this->context->elems[$elemIdx])) {
+            $this->addError("Invalid element segment index: {$elemIdx}");
+            return;
+        }
+        if ($this->context->tables[$tableIdx]->refType !== $this->context->elems[$elemIdx]) {
+            $this->addError('table.init requires matching reference types');
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateElemDrop(Instrs\Table\ElemDrop $instr): void
+    {
+        $elemIdx = $instr->elem;
+        if (! isset($this->context->elems[$elemIdx])) {
+            $this->addError("Invalid element segment index: {$elemIdx}");
+        }
+    }
+
+    private function validateMemoryExists(): void
+    {
+        if (! isset($this->context->mems[0])) {
+            $this->addError('Memory 0 is not defined');
+        }
+    }
+
+    private function validateMemLoad(int $align, int $maxAlign, ValType $resultType): void
+    {
+        $this->validateMemoryExists();
+        if ((1 << $align) > $maxAlign) {
+            $this->addError("alignment must not be larger than natural alignment ({$maxAlign})");
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->pushVal($resultType);
+    }
+
+    private function validateMemStore(int $align, int $maxAlign, ValType $valueType): void
+    {
+        $this->validateMemoryExists();
+        if ((1 << $align) > $maxAlign) {
+            $this->addError("alignment must not be larger than natural alignment ({$maxAlign})");
+        }
+        $this->validationStack->popValOf($valueType);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateMemoryInit(Instrs\Memory\MemoryInit $instr): void
+    {
+        if (! isset($this->context->mems[0])) {
+            $this->addError('Memory 0 is not defined');
+        }
+        $dataIdx = $instr->data;
+        if (! isset($this->context->datas[$dataIdx])) {
+            $this->addError("Invalid data segment index: {$dataIdx}");
+        }
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+        $this->validationStack->popValOf(ValType::I32);
+    }
+
+    private function validateDataDrop(Instrs\Memory\DataDrop $instr): void
+    {
+        $dataIdx = $instr->data;
+        if (! isset($this->context->datas[$dataIdx])) {
+            $this->addError("Invalid data segment index: {$dataIdx}");
+        }
+    }
+
+    /**
+     * @return array{list<ValType>, list<ValType>}
+     */
+    private function extractBlockTypes(BlockType $blockType): array
+    {
+        $funcType = $this->expandBlockType($blockType);
+        return [$funcType->params, $funcType->results];
+    }
+
+    private function expandBlockType(BlockType $blockType): FuncType
+    {
+        if ($blockType instanceof BlockTypes\TypeIdx) {
+            if (! isset($this->context->types[$blockType->inner])) {
+                $this->addError("Invalid type index: {$blockType->inner}");
+                return new FuncType([], []);
+            }
+            return $this->context->types[$blockType->inner];
+        } elseif ($blockType instanceof BlockTypes\ValType) {
+            $t = $blockType->inner;
+            return new FuncType(
+                [],
+                $t === null ? [] : [$t],
+            );
+        }
+        $this->addError('Unknown block type: ' . $blockType::class);
+        return new FuncType([], []);
+    }
+
+    private function addError(string $message): void
+    {
+        $this->errors[] = $message;
+    }
+}
diff --git a/src/WebAssembly/Validation/ValidationFailureException.php b/src/WebAssembly/Validation/ValidationFailureException.php
new file mode 100644
index 0000000..9650e80
--- /dev/null
+++ b/src/WebAssembly/Validation/ValidationFailureException.php
@@ -0,0 +1,11 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use RuntimeException;
+
+final class ValidationFailureException extends RuntimeException
+{
+}
diff --git a/src/WebAssembly/Validation/ValidationResult.php b/src/WebAssembly/Validation/ValidationResult.php
new file mode 100644
index 0000000..0a9395a
--- /dev/null
+++ b/src/WebAssembly/Validation/ValidationResult.php
@@ -0,0 +1,16 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+final readonly class ValidationResult
+{
+    /**
+     * @param list<string> $errors
+     */
+    public function __construct(
+        public array $errors,
+    ) {
+    }
+}
diff --git a/src/WebAssembly/Validation/ValidationStack.php b/src/WebAssembly/Validation/ValidationStack.php
new file mode 100644
index 0000000..53b47a7
--- /dev/null
+++ b/src/WebAssembly/Validation/ValidationStack.php
@@ -0,0 +1,154 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instrs;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+use function array_pop;
+use function array_reverse;
+use function array_slice;
+use function assert;
+use function count;
+
+final class ValidationStack
+{
+    /**
+     * @var list<?ValType>
+     */
+    private array $values = [];
+
+    /**
+     * @var list<ControlFrame>
+     */
+    private array $controls = [];
+
+    public function __construct(
+    ) {
+    }
+
+    public function pushVal(?ValType $type): void
+    {
+        $this->values[] = $type;
+    }
+
+    /**
+     * @param list<?ValType> $types
+     */
+    public function pushVals(array $types): void
+    {
+        foreach ($types as $type) {
+            $this->pushVal($type);
+        }
+    }
+
+    public function popVal(): ?ValType
+    {
+        // Check stack underflow.
+        $currentCtrl = $this->getCurrentControl();
+        if (count($this->values) === $currentCtrl->height) {
+            // If the current control frame is marked as unreachable, the stack behaves polymorphically.
+            if ($currentCtrl->unreachable) {
+                return null;
+            }
+            throw new ValidationFailureException('Value stack underflow');
+        }
+
+        return array_pop($this->values);
+    }
+
+    public function popValOf(?ValType $expect): ?ValType
+    {
+        $actual = $this->popVal();
+        if ($actual !== $expect && $actual !== null && $expect !== null) {
+            throw new ValidationFailureException('Type mismatch');
+        }
+        return $actual;
+    }
+
+    /**
+     * @param list<ValType> $types
+     * @return list<?ValType>
+     */
+    public function popVals(array $types): array
+    {
+        $popped = [];
+        foreach (array_reverse($types) as $type) {
+            $popped[] = $this->popValOf($type);
+        }
+        return array_reverse($popped);
+    }
+
+    /**
+     * @param class-string $opcode
+     * @param list<ValType> $in
+     * @param list<ValType> $out
+     */
+    public function pushCtrl(string $opcode, array $in, array $out): void
+    {
+        $ctrl = new ControlFrame($opcode, $in, $out, count($this->values), false);
+        $this->controls[] = $ctrl;
+        $this->pushVals($in);
+    }
+
+    public function popCtrl(): ControlFrame
+    {
+        if ($this->controlDepth() === 0) {
+            throw new ValidationFailureException('Control stack underflow');
+        }
+        $ctrl = $this->getCurrentControl();
+        $this->popVals($ctrl->endTypes);
+        if (count($this->values) !== $ctrl->height) {
+            throw new ValidationFailureException('Invalid stack height');
+        }
+        array_pop($this->controls);
+        return $ctrl;
+    }
+
+    /**
+     * @return list<ValType>
+     */
+    public function labelTypes(ControlFrame $ctrl): array
+    {
+        return $ctrl->opcode === Instrs\Control\Loop::class ? $ctrl->startTypes : $ctrl->endTypes;
+    }
+
+    public function unreachable(): void
+    {
+        $currentCtrl = $this->getCurrentControl();
+        $this->values = array_slice($this->values, 0, $currentCtrl->height);
+        assert(count($this->controls) !== 0);
+        array_pop($this->controls);
+        $this->controls[] = new ControlFrame(
+            $currentCtrl->opcode,
+            $currentCtrl->startTypes,
+            $currentCtrl->endTypes,
+            $currentCtrl->height,
+            true,
+        );
+    }
+
+    public function controlDepth(): int
+    {
+        return count($this->controls);
+    }
+
+    public function getControl(int $index): ?ControlFrame
+    {
+        $absIndex = count($this->controls) - 1 - $index;
+        if ($absIndex < 0) {
+            return null;
+        }
+        return $this->controls[$absIndex] ?? null;
+    }
+
+    public function getCurrentControl(): ControlFrame
+    {
+        if ($this->controlDepth() === 0) {
+            throw new ValidationFailureException('No control frame available');
+        }
+        assert(count($this->controls) !== 0);
+        return $this->controls[array_key_last($this->controls)];
+    }
+}
diff --git a/src/WebAssembly/Validation/Validator.php b/src/WebAssembly/Validation/Validator.php
new file mode 100644
index 0000000..60685e4
--- /dev/null
+++ b/src/WebAssembly/Validation/Validator.php
@@ -0,0 +1,426 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Nsfisis\Waddiwasi\WebAssembly\Validation;
+
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instr;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Instructions\Instrs;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\DataModes;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\ElemModes;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\ExportDescs;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\Func;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\ImportDescs;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Modules\Module;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\FuncType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\Limits;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\MemType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\Mut;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\TableType;
+use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+use function array_fill;
+use function array_map;
+use function array_merge;
+use function count;
+use function in_array;
+
+final class Validator
+{
+    /**
+     * @var list<string>
+     */
+    private array $errors = [];
+
+    public function __construct(
+        private readonly Module $module,
+    ) {
+    }
+
+    public function validate(): ValidationResult
+    {
+        try {
+            $this->validateModule();
+            return new ValidationResult($this->errors);
+        } catch (ValidationFailureException $e) {
+            return new ValidationResult([...$this->errors, $e->getMessage()]);
+        }
+    }
+
+    private function validateModule(): void
+    {
+        $importFuncTypes = [];
+        $importTableTypes = [];
+        $importMemTypes = [];
+        $importGlobalTypes = [];
+        foreach ($this->module->imports as $import) {
+            $desc = $import->desc;
+            if ($desc instanceof ImportDescs\Func) {
+                if (isset($this->module->types[$desc->func])) {
+                    $importFuncTypes[] = $this->module->types[$desc->func];
+                } else {
+                    $this->addError("Invalid import function type index: {$desc->func}");
+                    $importFuncTypes[] = new FuncType([], []);
+                }
+            } elseif ($desc instanceof ImportDescs\Table) {
+                $importTableTypes[] = $desc->table;
+            } elseif ($desc instanceof ImportDescs\Mem) {
+                $importMemTypes[] = $desc->mem;
+            } elseif ($desc instanceof ImportDescs\Global_) {
+                $importGlobalTypes[] = $desc->global;
+            }
+        }
+
+        $c = new Context(
+            types: $this->module->types,
+            funcs: array_merge(
+                $importFuncTypes,
+                array_map(
+                    fn (Func $f) => $this->module->types[$f->type] ?? new FuncType([], []),
+                    $this->module->funcs,
+                ),
+            ),
+            tables: array_merge(
+                $importTableTypes,
+                array_map(fn ($t) => $t->type, $this->module->tables),
+            ),
+            mems: array_merge(
+                $importMemTypes,
+                array_map(fn ($m) => $m->type, $this->module->mems),
+            ),
+            globals: array_merge(
+                $importGlobalTypes,
+                array_map(fn ($g) => $g->type, $this->module->globals),
+            ),
+            elems: array_map(fn ($e) => $e->type, $this->module->elems),
+            datas: array_fill(0, count($this->module->datas), true),
+            locals: [],
+            labels: [],
+            return: [],
+            refs: $this->collectRefs(),
+        );
+
+        $c_ = new Context(
+            types: $c->types,
+            funcs: $c->funcs,
+            tables: $c->tables,
+            mems: $c->mems,
+            globals: $importGlobalTypes,
+            elems: $c->elems,
+            datas: $c->datas,
+            locals: $c->locals,
+            labels: $c->labels,
+            return: $c->return,
+            refs: $c->refs,
+        );
+
+        $this->validateTypes();
+
+        $this->validateFuncs($c);
+        $this->validateTables($c);
+        $this->validateMems($c);
+        $this->validateGlobals($c_);
+        $this->validateElems($c_);
+        $this->validateDatas($c_);
+
+        $this->validateStart($c);
+        $this->validateImports($c);
+        $this->validateExports($c);
+
+        $this->validateMemsCount($c);
+        $this->validateExportsHaveDifferentNames();
+    }
+
+    private function validateTypes(): void
+    {
+        // Do nothing because function types are always valid.
+    }
+
+    private function validateFuncs(Context $c): void
+    {
+        foreach ($this->module->funcs as $func) {
+            $this->validateFunc($c, $func);
+        }
+    }
+
+    private function validateTables(Context $c): void
+    {
+        foreach ($this->module->tables as $table) {
+            $this->validateTableType($table->type);
+        }
+    }
+
+    private function validateTableType(TableType $tableType): void
+    {
+        $this->validateLimits($tableType->limits, 2 ** 32 - 1);
+    }
+
+    private function validateLimits(Limits $limits, int $k): void
+    {
+        $n = $limits->min;
+        $m = $limits->max;
+        $this->addErrorUnless($n <= $k, 'invalid limits');
+        if ($m !== null) {
+            $this->addErrorUnless($m <= $k, 'invalid limits');
+            $this->addErrorUnless($n <= $m, 'invalid limits');
+        }
+    }
+
+    private function validateMems(Context $c): void
+    {
+        foreach ($this->module->mems as $mem) {
+            $this->validateMemType($mem->type);
+        }
+    }
+
+    private function validateMemType(MemType $memType): void
+    {
+        $this->validateLimits($memType->limits, 2 ** 16);
+    }
+
+    private function validateGlobals(Context $c): void
+    {
+        foreach ($this->module->globals as $global) {
+            $this->validateConstantExpr($global->init, $global->type->valType, $c);
+        }
+    }
+
+    /**
+     * @param list<Instr> $instrs
+     */
+    private function validateConstantExpr(array $instrs, ValType $expectedType, Context $c): void
+    {
+        if (count($instrs) !== 1) {
+            $this->addError('constant expression required');
+            return;
+        }
+        $instr = $instrs[0];
+        $actualType = match ($instr::class) {
+            Instrs\Numeric\F32Const::class => ValType::F32,
+            Instrs\Numeric\F64Const::class => ValType::F64,
+            Instrs\Numeric\I32Const::class => ValType::I32,
+            Instrs\Numeric\I64Const::class => ValType::I64,
+            Instrs\Reference\RefFunc::class => $this->validateConstRefFunc($instr, $c),
+            Instrs\Reference\RefNull::class => $instr->type,
+            Instrs\Variable\GlobalGet::class => $this->validateConstGlobalGet($instr, $c),
+            default => null,
+        };
+        if ($actualType === null) {
+            $this->addError('constant expression required');
+            return;
+        }
+        if ($actualType !== $expectedType) {
+            $this->addError('type mismatch');
+        }
+    }
+
+    private function validateConstRefFunc(Instrs\Reference\RefFunc $instr, Context $c): ?ValType
+    {
+        if (! isset($c->funcs[$instr->func])) {
+            $this->addError("unknown function {$instr->func}");
+            return null;
+        }
+        return ValType::FuncRef;
+    }
+
+    private function validateConstGlobalGet(Instrs\Variable\GlobalGet $instr, Context $c): ?ValType
+    {
+        if (! isset($c->globals[$instr->var])) {
+            $this->addError("unknown global {$instr->var}");
+            return null;
+        }
+        $global = $c->globals[$instr->var];
+        if ($global->mut !== Mut::Const) {
+            $this->addError('constant expression required');
+            return null;
+        }
+        return $global->valType;
+    }
+
+    private function validateElems(Context $c): void
+    {
+        foreach ($this->module->elems as $elem) {
+            foreach ($elem->init as $initExpr) {
+                $this->validateConstantExpr($initExpr, $elem->type, $c);
+            }
+            if ($elem->mode instanceof ElemModes\Active) {
+                if (! isset($c->tables[$elem->mode->table])) {
+                    $this->addError("unknown table {$elem->mode->table}");
+                    continue;
+                }
+                if ($c->tables[$elem->mode->table]->refType !== $elem->type) {
+                    $this->addError('type mismatch');
+                }
+                $this->validateConstantExpr($elem->mode->offset, ValType::I32, $c);
+            }
+        }
+    }
+
+    private function validateDatas(Context $c): void
+    {
+        foreach ($this->module->datas as $data) {
+            if ($data->mode instanceof DataModes\Active) {
+                if (! isset($c->mems[$data->mode->memory])) {
+                    $this->addError("unknown memory {$data->mode->memory}");
+                    continue;
+                }
+                $this->validateConstantExpr($data->mode->offset, ValType::I32, $c);
+            }
+        }
+    }
+
+    private function validateStart(Context $c): void
+    {
+        $start = $this->module->start;
+        if ($start === null) {
+            return;
+        }
+        $funcIdx = $start->func;
+        if (! isset($c->funcs[$funcIdx])) {
+            $this->addError("Invalid start function index: {$funcIdx}");
+            return;
+        }
+        $funcType = $c->funcs[$funcIdx];
+        $this->addErrorUnless(
+            count($funcType->params) === 0 && count($funcType->results) === 0,
+            'start function must have type [] -> []',
+        );
+    }
+
+    private function validateImports(Context $c): void
+    {
+        foreach ($this->module->imports as $import) {
+            $desc = $import->desc;
+            if ($desc instanceof ImportDescs\Func) {
+                $this->addErrorUnless(
+                    isset($this->module->types[$desc->func]),
+                    "Invalid import function type index: {$desc->func}",
+                );
+            } elseif ($desc instanceof ImportDescs\Table) {
+                $this->validateTableType($desc->table);
+            } elseif ($desc instanceof ImportDescs\Mem) {
+                $this->validateMemType($desc->mem);
+            } elseif ($desc instanceof ImportDescs\Global_) {
+                // Global import types are always valid
+            }
+        }
+    }
+
+    private function validateExports(Context $c): void
+    {
+        foreach ($this->module->exports as $export) {
+            $desc = $export->desc;
+            if ($desc instanceof ExportDescs\Func) {
+                $this->addErrorUnless(
+                    isset($c->funcs[$desc->func]),
+                    "Invalid export function index: {$desc->func}",
+                );
+            } elseif ($desc instanceof ExportDescs\Table) {
+                $this->addErrorUnless(
+                    isset($c->tables[$desc->table]),
+                    "Invalid export table index: {$desc->table}",
+                );
+            } elseif ($desc instanceof ExportDescs\Mem) {
+                $this->addErrorUnless(
+                    isset($c->mems[$desc->mem]),
+                    "Invalid export memory index: {$desc->mem}",
+                );
+            } elseif ($desc instanceof ExportDescs\Global_) {
+                $this->addErrorUnless(
+                    isset($c->globals[$desc->global]),
+                    "Invalid export global index: {$desc->global}",
+                );
+            }
+        }
+    }
+
+    private function validateMemsCount(Context $c): void
+    {
+        $this->addErrorUnless(
+            count($c->mems) <= 1,
+            'multiple memories are not allowed',
+        );
+    }
+
+    private function validateExportsHaveDifferentNames(): void
+    {
+        $names = [];
+        foreach ($this->module->exports as $export) {
+            if (in_array($export->name, $names, true)) {
+                $this->addError("Duplicate export name: {$export->name}");
+            }
+            $names[] = $export->name;
+        }
+    }
+
+    private function validateFunc(Context $c, Func $func): void
+    {
+        $funcType = $this->module->types[$func->type] ?? null;
+        if ($funcType === null) {
+            $this->addError("Invalid function type index: {$func->type}");
+            return;
+        }
+
+        $localTypes = array_merge(
+            $funcType->params,
+            array_map(fn ($l) => $l->type, $func->locals),
+        );
+
+        $funcContext = new Context(
+            types: $c->types,
+            funcs: $c->funcs,
+            tables: $c->tables,
+            mems: $c->mems,
+            globals: $c->globals,
+            elems: $c->elems,
+            datas: $c->datas,
+            locals: $localTypes,
+            labels: [$funcType->results],
+            return: $funcType->results,
+            refs: $c->refs,
+        );
+
+        $validationStack = new ValidationStack();
+        $validationStack->pushCtrl(Instrs\Control\Block::class, [], $funcType->results);
+
+        $functionValidator = new FunctionValidator($funcContext, $validationStack);
+        $errors = $functionValidator->validate($func->body);
+        array_push($this->errors, ...$errors);
+    }
+
+    /**
+     * Collect the set of function indices that are "declared" (appear in elem segment inits or exports).
+     *
+     * @return list<int>
+     */
+    private function collectRefs(): array
+    {
+        $refs = [];
+        foreach ($this->module->elems as $elem) {
+            foreach ($elem->init as $initExpr) {
+                foreach ($initExpr as $instr) {
+                    if ($instr instanceof Instrs\Reference\RefFunc) {
+                        $refs[] = $instr->func;
+                    }
+                }
+            }
+        }
+        foreach ($this->module->exports as $export) {
+            if ($export->desc instanceof ExportDescs\Func) {
+                $refs[] = $export->desc->func;
+            }
+        }
+        return array_values(array_unique($refs));
+    }
+
+    private function addErrorUnless(bool $x, string $message): void
+    {
+        if (! $x) {
+            $this->addError($message);
+        }
+    }
+
+    private function addError(string $message): void
+    {
+        $this->errors[] = $message;
+    }
+}
diff --git a/tests/src/SpecTestsuites/SpecTestsuiteBase.php b/tests/src/SpecTestsuites/SpecTestsuiteBase.php
index 7106407..bcf7fa0 100644
--- a/tests/src/SpecTestsuites/SpecTestsuiteBase.php
+++ b/tests/src/SpecTestsuites/SpecTestsuiteBase.php
@@ -31,6 +31,7 @@ use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\MemType;
 use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\Mut;
 use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\TableType;
 use Nsfisis\Waddiwasi\WebAssembly\Structure\Types\ValType;
+use Nsfisis\Waddiwasi\WebAssembly\Validation\Validator;
 use PHPUnit\Framework\TestCase;
 use RuntimeException;
 use function count;
@@ -157,8 +158,18 @@ abstract class SpecTestsuiteBase extends TestCase
         string $text,
         int $line,
     ): void {
-        // @todo Our implementation does not support "validation" step.
-        $this->assertTrue(true);
+        $filePath = __DIR__ . "/../../fixtures/spec_testsuites/core/{$filename}";
+        $wasmBinaryStream = new FileStream($filePath);
+        try {
+            $module = (new Decoder($wasmBinaryStream))->decode();
+        } catch (InvalidBinaryFormatException) {
+            // Malformed binary is also a form of invalid module.
+            $this->assertTrue(true);
+            return;
+        }
+        $result = (new Validator($module))->validate();
+        // @todo Check error message.
+        $this->assertNotEmpty($result->errors, "validating {$filename} is expected to fail (at {$line})");
     }
 
     protected function runAssertExhaustionCommand(