diff --git a/src/lib_scoru_wasm/binary_parser_encodings.ml b/src/lib_scoru_wasm/binary_parser_encodings.ml
new file mode 100644
index 0000000000000000000000000000000000000000..059a9c7ebd38078bb292e03a7bc8579da02e4c39
--- /dev/null
+++ b/src/lib_scoru_wasm/binary_parser_encodings.ml
@@ -0,0 +1,1524 @@
+(*****************************************************************************)
+(*                                                                           *)
+(* Open Source License                                                       *)
+(* Copyright (c) 2022 Nomadic Labs <contact@nomadic-labs.com>                *)
+(*                                                                           *)
+(* Permission is hereby granted, free of charge, to any person obtaining a   *)
+(* copy of this software and associated documentation files (the "Software"),*)
+(* to deal in the Software without restriction, including without limitation *)
+(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
+(* and/or sell copies of the Software, and to permit persons to whom the     *)
+(* Software is furnished to do so, subject to the following conditions:      *)
+(*                                                                           *)
+(* The above copyright notice and this permission notice shall be included   *)
+(* in all copies or substantial portions of the Software.                    *)
+(*                                                                           *)
+(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
+(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
+(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
+(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
+(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
+(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
+(* DEALINGS IN THE SOFTWARE.                                                 *)
+(*                                                                           *)
+(*****************************************************************************)
+
+open Tezos_webassembly_interpreter
+open Lazy_containers
+
+module Make (Tree_encoding : Tree_encoding.S) = struct
+  module V = Instance.Vector
+  module M = Instance.NameMap
+  module C = Chunked_byte_vector.Lwt
+  module Wasm_encoding = Wasm_encoding.Make (Tree_encoding)
+  include Tree_encoding
+
+  (* TODO: keep region? *)
+  let no_region_encoding enc =
+    conv (fun s -> Source.(s @@ no_region)) (fun {it; _} -> it) enc
+
+  let vector_encoding value_enc =
+    Lazy_vector_encoding.Int32.lazy_vector
+      (value [] Data_encoding.int32)
+      value_enc
+
+  module Lazy_vec = struct
+    let raw_encoding vector_encoding =
+      let offset = value ["offset"] Data_encoding.int32 in
+      let vector = scope ["vector"] vector_encoding in
+      conv
+        (fun (offset, vector) -> Decode.LazyVec {offset; vector})
+        (fun (LazyVec {offset; vector}) -> (offset, vector))
+        (tup2 ~flatten:true offset vector)
+
+    let encoding value_encoding = raw_encoding (vector_encoding value_encoding)
+  end
+
+  module Lazy_stack = struct
+    let encoding value_enc =
+      (* TODO: The stack can be probably encoded in a unique key in the tree,
+         since it is never used concurrently. *)
+      let offset = value ["length"] Data_encoding.int32 in
+      let vector = scope ["vector"] (vector_encoding value_enc) in
+      conv
+        (fun (length, vector) -> Decode.LazyStack {length; vector})
+        (fun (LazyStack {length; vector}) -> (length, vector))
+        (tup2 ~flatten:true offset vector)
+  end
+
+  module Byte_vector = struct
+    type t' = Decode.byte_vector_kont
+
+    let vkstart_case =
+      case
+        "VKStart"
+        (value [] Data_encoding.unit)
+        (function Decode.VKStart -> Some () | _ -> None)
+        (fun () -> Decode.VKStart)
+
+    let vkread_case =
+      let value_enc =
+        let pos = value ["pos"] Data_encoding.int64 in
+        let length = value ["length"] Data_encoding.int64 in
+        let data_label =
+          value ["data_label"] Interpreter_encodings.Ast.data_label_encoding
+        in
+        tup3 ~flatten:true data_label pos length
+      in
+      case
+        "VKRead"
+        value_enc
+        (function Decode.VKRead (b, p, l) -> Some (b, p, l) | _ -> None)
+        (fun (b, p, l) -> Decode.VKRead (b, p, l))
+
+    let vkstop_case =
+      case
+        "VKStop"
+        (value ["data_label"] Interpreter_encodings.Ast.data_label_encoding)
+        (function Decode.VKStop b -> Some b | _ -> None)
+        (fun b -> Decode.VKStop b)
+
+    let tag_encoding = value [] Data_encoding.string
+
+    let encoding =
+      tagged_union tag_encoding [vkstart_case; vkread_case; vkstop_case]
+  end
+
+  module Name = struct
+    let utf8 = value [] Data_encoding.int31
+
+    let nkstart_case =
+      case
+        "NKStart"
+        (value [] Data_encoding.unit)
+        (function Decode.NKStart -> Some () | _ -> None)
+        (fun () -> Decode.NKStart)
+
+    let nkparse_case =
+      let value_enc =
+        let pos = value ["pos"] Data_encoding.int31 in
+        let buffer = scope ["lazy_kont"] (Lazy_vec.encoding utf8) in
+        let length = value ["length"] Data_encoding.int31 in
+        tup3 ~flatten:true pos buffer length
+      in
+      case
+        "NKParse"
+        value_enc
+        (function Decode.NKParse (p, v, l) -> Some (p, v, l) | _ -> None)
+        (fun (p, v, l) -> Decode.NKParse (p, v, l))
+
+    let nkstop_case =
+      case
+        "NKStop"
+        (vector_encoding utf8)
+        (function Decode.NKStop v -> Some v | _ -> None)
+        (fun v -> Decode.NKStop v)
+
+    let tag_encoding = value [] Data_encoding.string
+
+    let encoding =
+      tagged_union tag_encoding [nkstart_case; nkparse_case; nkstop_case]
+  end
+
+  let name_encoding = vector_encoding Name.utf8
+
+  module Func_type = struct
+    type tags = FKStart | FKIns | FKOut | FKStop
+
+    let value_type_encoding =
+      value [] Interpreter_encodings.Types.value_type_encoding
+
+    let fkstart_case =
+      case
+        "FKStart"
+        (value [] Data_encoding.unit)
+        (function Decode.FKStart -> Some () | _ -> None)
+        (fun () -> FKStart)
+
+    let fkins_case =
+      let lazy_vec =
+        scope ["ins_kont"] (Lazy_vec.encoding value_type_encoding)
+      in
+      case
+        "FKIns"
+        lazy_vec
+        (function Decode.FKIns vec -> Some vec | _ -> None)
+        (fun vec -> FKIns vec)
+
+    let fkout_case =
+      let params = scope ["params"] (vector_encoding value_type_encoding) in
+      let lazy_vec =
+        scope ["lazy_kont"] (Lazy_vec.encoding value_type_encoding)
+      in
+      case
+        "FKOut"
+        (tup2 ~flatten:true params lazy_vec)
+        (function Decode.FKOut (p, vec) -> Some (p, vec) | _ -> None)
+        (fun (p, vec) -> FKOut (p, vec))
+
+    let func_type_encoding =
+      let params = scope ["params"] (vector_encoding value_type_encoding) in
+      let result = scope ["result"] (vector_encoding value_type_encoding) in
+      conv
+        (fun (params, result) -> Types.FuncType (params, result))
+        (fun (Types.FuncType (params, result)) -> (params, result))
+        (tup2 ~flatten:true params result)
+
+    let fkstop_case =
+      case
+        "FKStop"
+        func_type_encoding
+        (function Decode.FKStop ft -> Some ft | _ -> None)
+        (fun ft -> FKStop ft)
+
+    let tag_encoding = Data_encoding.string |> value []
+
+    let encoding =
+      tagged_union
+        tag_encoding
+        [fkstart_case; fkins_case; fkout_case; fkstop_case]
+  end
+
+  module Import = struct
+    let impkstart_case =
+      let tag = "ImpKStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant tag))
+        (function Decode.ImpKStart -> Some () | _ -> None)
+        (fun () -> ImpKStart)
+
+    let impkmodulename_case =
+      case
+        "ImpKModuleName"
+        Name.encoding
+        (function Decode.ImpKModuleName n -> Some n | _ -> None)
+        (fun n -> ImpKModuleName n)
+
+    let impkitemname_case =
+      case
+        "ImpKItemName"
+        (tup2 ~flatten:true name_encoding Name.encoding)
+        (function Decode.ImpKItemName (m, i) -> Some (m, i) | _ -> None)
+        (fun (m, i) -> ImpKItemName (m, i))
+
+    let import_encoding =
+      conv
+        (fun (module_name, item_name, idesc) ->
+          Ast.{module_name; item_name; idesc})
+        (fun {module_name; item_name; idesc} -> (module_name, item_name, idesc))
+        (tup3
+           ~flatten:true
+           (scope ["module_name"] name_encoding)
+           (scope ["item_name"] name_encoding)
+           (value ["idesc"] Interpreter_encodings.Ast.import_desc_encoding))
+
+    let impkstop_case =
+      case
+        "ImpKStop"
+        import_encoding
+        (function Decode.ImpKStop i -> Some i | _ -> None)
+        (fun i -> ImpKStop i)
+
+    let tag_encoding = value [] Data_encoding.string
+
+    let encoding =
+      tagged_union
+        tag_encoding
+        [impkstart_case; impkmodulename_case; impkitemname_case; impkstop_case]
+  end
+
+  module Export = struct
+    let expkstart_case =
+      let tag = "ExpKStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant tag))
+        (function Decode.ExpKStart -> Some () | _ -> None)
+        (fun () -> ExpKStart)
+
+    let expkname_case =
+      case
+        "ExpKName"
+        Name.encoding
+        (function Decode.ExpKName n -> Some n | _ -> None)
+        (fun n -> ExpKName n)
+
+    let export_encoding =
+      conv
+        (fun (name, edesc) -> Ast.{name; edesc})
+        (fun {name; edesc} -> (name, edesc))
+        (tup2
+           ~flatten:true
+           (scope ["name"] name_encoding)
+           (value ["edesc"] Interpreter_encodings.Ast.export_desc_encoding))
+
+    let expkstop_case =
+      case
+        "ExpKStop"
+        export_encoding
+        (function Decode.ExpKStop e -> Some e | _ -> None)
+        (fun e -> ExpKStop e)
+
+    let tags_encoding = value [] Data_encoding.string
+
+    let encoding =
+      tagged_union tags_encoding [expkstart_case; expkname_case; expkstop_case]
+  end
+
+  module Size = struct
+    let encoding =
+      conv
+        (fun (size, start) -> Decode.{size; start})
+        (fun {size; start} -> (size, start))
+        (tup2
+           ~flatten:true
+           (value ["size"] Data_encoding.int31)
+           (value ["start"] Data_encoding.int31))
+  end
+
+  module Instr_block = struct
+    let stop_case =
+      case
+        "IKStop"
+        (value [] Interpreter_encodings.Ast.block_label_encoding)
+        (function Decode.IKStop lbl -> Some lbl | _ -> None)
+        (fun lbl -> IKStop lbl)
+
+    let next_case =
+      case
+        "IKNext"
+        (value [] Interpreter_encodings.Ast.block_label_encoding)
+        (function Decode.IKNext lbl -> Some lbl | _ -> None)
+        (fun lbl -> IKNext lbl)
+
+    let block_case =
+      let encoding =
+        tup2
+          ~flatten:true
+          (value ["type"] Interpreter_encodings.Ast.block_type_encoding)
+          (value ["pos"] Data_encoding.int31)
+      in
+      case
+        "IKBlock"
+        encoding
+        (function Decode.IKBlock (ty, i) -> Some (ty, i) | _ -> None)
+        (fun (ty, i) -> IKBlock (ty, i))
+
+    let loop_case =
+      let encoding =
+        tup2
+          ~flatten:true
+          (value ["type"] Interpreter_encodings.Ast.block_type_encoding)
+          (value ["pos"] Data_encoding.int31)
+      in
+      case
+        "IKLoop"
+        encoding
+        (function Decode.IKLoop (ty, i) -> Some (ty, i) | _ -> None)
+        (fun (ty, i) -> IKLoop (ty, i))
+
+    let if1_case =
+      let encoding =
+        tup2
+          ~flatten:true
+          (value ["type"] Interpreter_encodings.Ast.block_type_encoding)
+          (value ["pos"] Data_encoding.int31)
+      in
+      case
+        "IKIf1"
+        encoding
+        (function Decode.IKIf1 (ty, i) -> Some (ty, i) | _ -> None)
+        (fun (ty, i) -> IKIf1 (ty, i))
+
+    let if2_case =
+      let encoding =
+        tup3
+          ~flatten:true
+          (value ["type"] Interpreter_encodings.Ast.block_type_encoding)
+          (value ["pos"] Data_encoding.int31)
+          (value ["else"] Interpreter_encodings.Ast.block_label_encoding)
+      in
+      case
+        "IKIf2"
+        encoding
+        (function
+          | Decode.IKIf2 (ty, i, else_lbl) -> Some (ty, i, else_lbl) | _ -> None)
+        (fun (ty, i, else_lbl) -> IKIf2 (ty, i, else_lbl))
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [stop_case; next_case; block_case; loop_case; if1_case; if2_case]
+  end
+
+  module Block = struct
+    let start_case =
+      let tag = "BlockStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant tag))
+        (function Decode.BlockStart -> Some () | _ -> None)
+        (fun _ -> BlockStart)
+
+    let parse_case =
+      case
+        "BlockParse"
+        (scope [] (Lazy_stack.encoding Instr_block.encoding))
+        (function Decode.BlockParse ik -> Some ik | _ -> None)
+        (fun ik -> BlockParse ik)
+
+    let stop_case =
+      case
+        "BlockStop"
+        (value [] Interpreter_encodings.Ast.block_label_encoding)
+        (function Decode.BlockStop lbl -> Some lbl | _ -> None)
+        (fun lbl -> BlockStop lbl)
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [start_case; parse_case; stop_case]
+  end
+
+  module Code = struct
+    let value_type_acc_enc =
+      let occurences = value ["occurences"] Data_encoding.int32 in
+      let value_type =
+        value ["type"] Interpreter_encodings.Types.value_type_encoding
+      in
+      tup2 ~flatten:true occurences value_type
+
+    let ckstart_case =
+      let tag = "CKStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant tag))
+        (function Decode.CKStart -> Some () | _ -> None)
+        (fun () -> CKStart)
+
+    let cklocalsparse_case =
+      let left = value ["left"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let vec_kont =
+        scope ["vec_kont"] (Lazy_vec.encoding value_type_acc_enc)
+      in
+      let locals_size = value ["locals_size"] Data_encoding.int64 in
+      case
+        "CKLocalsParse"
+        (tup5 ~flatten:true left size pos vec_kont locals_size)
+        (function
+          | Decode.CKLocalsParse {left; size; pos; vec_kont; locals_size} ->
+              Some (left, size, pos, vec_kont, locals_size)
+          | _ -> None)
+        (fun (left, size, pos, vec_kont, locals_size) ->
+          Decode.CKLocalsParse {left; size; pos; vec_kont; locals_size})
+
+    let cklocalsaccumulate_case =
+      let left = value ["left"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let type_vec =
+        scope ["type_vec"] (Lazy_vec.encoding value_type_acc_enc)
+      in
+      let curr_type = scope ["curr_type"] (option value_type_acc_enc) in
+      let vec_kont =
+        scope ["vec_kont"] (Lazy_vec.encoding Func_type.value_type_encoding)
+      in
+
+      case
+        "CKLocalsAccumulate"
+        (tup6 ~flatten:true left size pos type_vec curr_type vec_kont)
+        (function
+          | Decode.CKLocalsAccumulate
+              {left; size; pos; type_vec; curr_type; vec_kont} ->
+              Some (left, size, pos, type_vec, curr_type, vec_kont)
+          | _ -> None)
+        (fun (left, size, pos, type_vec, curr_type, vec_kont) ->
+          Decode.CKLocalsAccumulate
+            {left; size; pos; type_vec; curr_type; vec_kont})
+
+    let ckbody_case =
+      let left = value ["left"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let locals =
+        scope ["locals"] (vector_encoding Func_type.value_type_encoding)
+      in
+      let const_kont = scope ["const_kont"] Block.encoding in
+      case
+        "CKBody"
+        (tup4 ~flatten:true left size locals const_kont)
+        (function
+          | Decode.CKBody {left; size; locals; const_kont} ->
+              Some (left, size, locals, const_kont)
+          | _ -> None)
+        (fun (left, size, locals, const_kont) ->
+          CKBody {left; size; locals; const_kont})
+
+    let func_encoding =
+      let ftype = value ["ftype"] Interpreter_encodings.Ast.var_encoding in
+      let locals =
+        scope ["locals"] (vector_encoding Func_type.value_type_encoding)
+      in
+      let body =
+        value ["body"] Interpreter_encodings.Ast.block_label_encoding
+      in
+      conv
+        (fun (ftype, locals, body) ->
+          Source.(Ast.{ftype; locals; body} @@ no_region))
+        (fun {it = {ftype; locals; body}; _} -> (ftype, locals, body))
+        (tup3 ~flatten:true ftype locals body)
+
+    let ckstop_case =
+      case
+        "CKStop"
+        func_encoding
+        (function Decode.CKStop func -> Some func | _ -> None)
+        (fun func -> CKStop func)
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [
+          ckstart_case;
+          cklocalsparse_case;
+          cklocalsaccumulate_case;
+          ckbody_case;
+          ckstop_case;
+        ]
+  end
+
+  module Elem = struct
+    let region enc =
+      Data_encoding.conv
+        (fun p -> p.Source.it)
+        (fun v -> Source.(v @@ no_region))
+        enc
+
+    let index_kind_encoding =
+      Data_encoding.string_enum
+        [("Indexed", Decode.Indexed); ("Const", Decode.Const)]
+
+    let ekstart_case =
+      let tag = "EKStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant "tag"))
+        (function Decode.EKStart -> Some () | _ -> None)
+        (fun () -> EKStart)
+
+    let ekmode_case =
+      let left = value ["left"] Data_encoding.int31 in
+      let index =
+        value
+          ["index"]
+          (Interpreter_encodings.Source.phrase_encoding Data_encoding.int32)
+      in
+      let index_kind = value ["index_kind"] index_kind_encoding in
+      let early_ref_type =
+        value_option
+          ["early_ref_type"]
+          Interpreter_encodings.Types.ref_type_encoding
+      in
+      let offset_kont = value ["offset_kont"] Data_encoding.int31 in
+      let offset_kont_code = scope ["offset_kont_code"] Block.encoding in
+      case
+        "EKMode"
+        (tup6
+           ~flatten:true
+           left
+           index
+           index_kind
+           early_ref_type
+           offset_kont
+           offset_kont_code)
+        (function
+          | Decode.EKMode
+              {
+                left;
+                index;
+                index_kind;
+                early_ref_type;
+                offset_kont = offset_kont, offset_kont_code;
+              } ->
+              Some
+                ( left,
+                  index,
+                  index_kind,
+                  early_ref_type,
+                  offset_kont,
+                  offset_kont_code )
+          | _ -> None)
+        (fun ( left,
+               index,
+               index_kind,
+               early_ref_type,
+               offset_kont,
+               offset_kont_code ) ->
+          EKMode
+            {
+              left;
+              index;
+              index_kind;
+              early_ref_type;
+              offset_kont = (offset_kont, offset_kont_code);
+            })
+
+    let ekinitindexed_case =
+      let mode =
+        value ["mode"] Interpreter_encodings.Ast.segment_mode_encoding
+      in
+      let ref_type =
+        value ["ref_type"] Interpreter_encodings.Types.ref_type_encoding
+      in
+      let einit_vec =
+        scope
+          ["einit_vec"]
+          (Lazy_vec.encoding
+             (value
+                []
+                (Interpreter_encodings.Source.phrase_encoding
+                   Interpreter_encodings.Ast.block_label_encoding)))
+      in
+      case
+        "EKInitIndexed"
+        (tup3 ~flatten:true mode ref_type einit_vec)
+        (function
+          | Decode.EKInitIndexed {mode; ref_type; einit_vec} ->
+              Some (mode, ref_type, einit_vec)
+          | _ -> None)
+        (fun (mode, ref_type, einit_vec) ->
+          EKInitIndexed {mode; ref_type; einit_vec})
+
+    let ekinitconst_case =
+      let mode =
+        value ["mode"] Interpreter_encodings.Ast.segment_mode_encoding
+      in
+      let ref_type =
+        value ["ref_type"] Interpreter_encodings.Types.ref_type_encoding
+      in
+      let einit_vec =
+        scope
+          ["einit_vec"]
+          (Lazy_vec.encoding
+             (value
+                []
+                (Interpreter_encodings.Source.phrase_encoding
+                   Interpreter_encodings.Ast.block_label_encoding)))
+      in
+      let einit_kont_pos = value ["einit_kont_pos"] Data_encoding.int31 in
+      let einit_kont_block = scope ["einit_kont_block"] Block.encoding in
+      case
+        "EKInitConst"
+        (tup5
+           ~flatten:true
+           mode
+           ref_type
+           einit_vec
+           einit_kont_pos
+           einit_kont_block)
+        (function
+          | Decode.EKInitConst
+              {mode; ref_type; einit_vec; einit_kont = pos, block} ->
+              Some (mode, ref_type, einit_vec, pos, block)
+          | _ -> None)
+        (fun (mode, ref_type, einit_vec, pos, block) ->
+          EKInitConst {mode; ref_type; einit_vec; einit_kont = (pos, block)})
+
+    let elem_encoding =
+      let etype =
+        value ["ref_type"] Interpreter_encodings.Types.ref_type_encoding
+      in
+      let einit =
+        scope
+          ["einit"]
+          (vector_encoding (value [] Interpreter_encodings.Ast.const_encoding))
+      in
+      let emode =
+        value ["mode"] Interpreter_encodings.Ast.segment_mode_encoding
+      in
+      conv
+        (fun (etype, einit, emode) -> Ast.{etype; einit; emode})
+        (fun Ast.{etype; einit; emode} -> (etype, einit, emode))
+        (tup3 ~flatten:true etype einit emode)
+
+    let ekstop_case =
+      case
+        "EKStop"
+        elem_encoding
+        (function Decode.EKStop elem -> Some elem | _ -> None)
+        (fun elem -> EKStop elem)
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [
+          ekstart_case;
+          ekmode_case;
+          ekinitindexed_case;
+          ekinitconst_case;
+          ekstop_case;
+        ]
+  end
+
+  module Data = struct
+    let dkstart_case =
+      let tag = "DKStart" in
+      case
+        tag
+        (value [] (Data_encoding.constant tag))
+        (function Decode.DKStart -> Some () | _ -> None)
+        (fun () -> DKStart)
+
+    let dkmode_case =
+      let left = value ["left"] Data_encoding.int31 in
+      let index =
+        value
+          ["index"]
+          (Interpreter_encodings.Source.phrase_encoding Data_encoding.int32)
+      in
+      let offset_kont = value ["offset_kont"] Data_encoding.int31 in
+      let offset_kont_code = scope ["offset_kont_code"] Block.encoding in
+      case
+        "DKMode"
+        (tup4 ~flatten:true left index offset_kont offset_kont_code)
+        (function
+          | Decode.DKMode {left; index; offset_kont = pos, block} ->
+              Some (left, index, pos, block)
+          | _ -> None)
+        (fun (left, index, pos, block) ->
+          DKMode {left; index; offset_kont = (pos, block)})
+
+    let dkinit_case =
+      let dmode =
+        value ["dmode"] Interpreter_encodings.Ast.segment_mode_encoding
+      in
+      let init_kont = scope ["init_kont"] Byte_vector.encoding in
+      case
+        "DKInit"
+        (tup2 ~flatten:true dmode init_kont)
+        (function
+          | Decode.DKInit {dmode; init_kont} -> Some (dmode, init_kont)
+          | _ -> None)
+        (fun (dmode, init_kont) -> DKInit {dmode; init_kont})
+
+    let data_segment_encoding =
+      let dmode =
+        value ["dmode"] Interpreter_encodings.Ast.segment_mode_encoding
+      in
+      let dinit =
+        value ["dinit"] Interpreter_encodings.Ast.data_label_encoding
+      in
+      conv
+        (fun (dinit, dmode) -> Ast.{dinit; dmode})
+        (fun {dinit; dmode} -> (dinit, dmode))
+        (tup2 ~flatten:true dinit dmode)
+
+    let dkstop_case =
+      case
+        "DKStop"
+        data_segment_encoding
+        (function Decode.DKStop data_segment -> Some data_segment | _ -> None)
+        (fun data_segment -> DKStop data_segment)
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [dkstart_case; dkmode_case; dkinit_case; dkstop_case]
+  end
+
+  module Field = struct
+    let type_field_encoding =
+      scope
+        ["module"; "types"]
+        (vector_encoding (no_region_encoding Func_type.func_type_encoding))
+
+    let import_field_encoding =
+      scope
+        ["module"; "imports"]
+        (vector_encoding (no_region_encoding Import.import_encoding))
+
+    let func_field_encoding =
+      scope
+        ["module"; "funcs"]
+        (vector_encoding (value [] Interpreter_encodings.Ast.var_encoding))
+
+    let table_field_encoding =
+      scope
+        ["module"; "tables"]
+        (vector_encoding (value [] Interpreter_encodings.Ast.table_encoding))
+
+    let memory_field_encoding =
+      scope
+        ["module"; "memories"]
+        (vector_encoding (value [] Interpreter_encodings.Ast.memory_encoding))
+
+    let global_field_encoding =
+      scope
+        ["module"; "globals"]
+        (vector_encoding (value [] Interpreter_encodings.Ast.global_encoding))
+
+    let export_field_encoding =
+      scope
+        ["module"; "exports"]
+        (vector_encoding (no_region_encoding Export.export_encoding))
+
+    let start_field_encoding =
+      value_option ["module"; "start"] Interpreter_encodings.Ast.start_encoding
+
+    let elem_field_encoding =
+      scope
+        ["module"; "elem_segments"]
+        (vector_encoding (no_region_encoding Elem.elem_encoding))
+
+    let data_count_field_encoding =
+      value_option ["module"; "data_count"] Data_encoding.int32
+
+    let code_field_encoding =
+      scope ["module"; "code"] (vector_encoding Code.func_encoding)
+
+    let data_field_encoding =
+      scope
+        ["module"; "data_segments"]
+        (vector_encoding (no_region_encoding Data.data_segment_encoding))
+
+    let building_state_encoding =
+      conv
+        (fun ( types,
+               imports,
+               vars,
+               tables,
+               memories,
+               globals,
+               exports,
+               start,
+               (elems, data_count, code, datas) ) ->
+          Decode.
+            {
+              types;
+              imports;
+              vars;
+              tables;
+              memories;
+              globals;
+              exports;
+              start;
+              elems;
+              data_count;
+              code;
+              datas;
+            })
+        (fun Decode.
+               {
+                 types;
+                 imports;
+                 vars;
+                 tables;
+                 memories;
+                 globals;
+                 exports;
+                 start;
+                 elems;
+                 data_count;
+                 code;
+                 datas;
+               } ->
+          ( types,
+            imports,
+            vars,
+            tables,
+            memories,
+            globals,
+            exports,
+            start,
+            (elems, data_count, code, datas) ))
+        (tup9
+           ~flatten:true
+           type_field_encoding
+           import_field_encoding
+           func_field_encoding
+           table_field_encoding
+           memory_field_encoding
+           global_field_encoding
+           export_field_encoding
+           start_field_encoding
+           (tup4
+              ~flatten:true
+              elem_field_encoding
+              data_count_field_encoding
+              code_field_encoding
+              data_field_encoding))
+
+    (* Only used to encode field_type. *)
+    type packed_field_type =
+      | FieldType : ('a, 'repr) Decode.field_type -> packed_field_type
+
+    let packed_field_type_encoding =
+      let open Decode in
+      let type_field_encoding =
+        let tag = "TypeField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType TypeField -> Some () | _ -> None)
+          (fun () -> FieldType TypeField)
+      in
+      let import_field_encoding =
+        let tag = "ImportField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType ImportField -> Some () | _ -> None)
+          (fun () -> FieldType ImportField)
+      in
+      let func_field_encoding =
+        let tag = "FuncField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType FuncField -> Some () | _ -> None)
+          (fun () -> FieldType FuncField)
+      in
+      let table_field_encoding =
+        let tag = "TableField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType TableField -> Some () | _ -> None)
+          (fun () -> FieldType TableField)
+      in
+      let memory_field_encoding =
+        let tag = "MemoryField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType MemoryField -> Some () | _ -> None)
+          (fun () -> FieldType MemoryField)
+      in
+      let global_field_encoding =
+        let tag = "GlobalField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType GlobalField -> Some () | _ -> None)
+          (fun () -> FieldType GlobalField)
+      in
+      let export_field_encoding =
+        let tag = "ExportField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType ExportField -> Some () | _ -> None)
+          (fun () -> FieldType ExportField)
+      in
+      let start_field_encoding =
+        let tag = "StartField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType StartField -> Some () | _ -> None)
+          (fun () -> FieldType StartField)
+      in
+      let elem_field_encoding =
+        let tag = "ElemField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType ElemField -> Some () | _ -> None)
+          (fun () -> FieldType ElemField)
+      in
+      let data_count_field_encoding =
+        let tag = "DataCountField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType DataCountField -> Some () | _ -> None)
+          (fun () -> FieldType DataCountField)
+      in
+      let code_field_encoding =
+        let tag = "CodeField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType CodeField -> Some () | _ -> None)
+          (fun () -> FieldType CodeField)
+      in
+      let data_field_encoding =
+        let tag = "DataField" in
+        case
+          tag
+          (value [] (Data_encoding.constant tag))
+          (function FieldType DataField -> Some () | _ -> None)
+          (fun () -> FieldType DataField)
+      in
+      tagged_union
+        (value [] Data_encoding.string)
+        [
+          type_field_encoding;
+          import_field_encoding;
+          func_field_encoding;
+          table_field_encoding;
+          memory_field_encoding;
+          global_field_encoding;
+          export_field_encoding;
+          start_field_encoding;
+          elem_field_encoding;
+          data_count_field_encoding;
+          code_field_encoding;
+          data_field_encoding;
+        ]
+
+    (* Only used to encode lazy vector parameterized by the field type in the
+       continuation. *)
+    type packed_typed_lazy_vec =
+      | TypedLazyVec :
+          ('a, Decode.vec_repr) Decode.field_type * 'a Decode.lazy_vec_kont
+          -> packed_typed_lazy_vec
+
+    let packed_typed_lazy_vec_encoding =
+      let open Decode in
+      let type_field_encoding =
+        let tag = "TypeField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding type_field_encoding)
+          (function TypedLazyVec (TypeField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (TypeField, vec))
+      in
+      let import_field_encoding =
+        let tag = "ImportField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding import_field_encoding)
+          (function TypedLazyVec (ImportField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (ImportField, vec))
+      in
+      let func_field_encoding =
+        let tag = "FuncField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding func_field_encoding)
+          (function TypedLazyVec (FuncField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (FuncField, vec))
+      in
+      let table_field_encoding =
+        let tag = "TableField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding table_field_encoding)
+          (function TypedLazyVec (TableField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (TableField, vec))
+      in
+      let memory_field_encoding =
+        let tag = "MemoryField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding memory_field_encoding)
+          (function TypedLazyVec (MemoryField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (MemoryField, vec))
+      in
+      let global_field_encoding =
+        let tag = "GlobalField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding global_field_encoding)
+          (function TypedLazyVec (GlobalField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (GlobalField, vec))
+      in
+      let export_field_encoding =
+        let tag = "ExportField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding export_field_encoding)
+          (function TypedLazyVec (ExportField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (ExportField, vec))
+      in
+      let elem_field_encoding =
+        let tag = "ElemField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding elem_field_encoding)
+          (function TypedLazyVec (ElemField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (ElemField, vec))
+      in
+      let code_field_encoding =
+        let tag = "CodeField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding code_field_encoding)
+          (function TypedLazyVec (CodeField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (CodeField, vec))
+      in
+      let data_field_encoding =
+        let tag = "DataField" in
+        case
+          tag
+          (Lazy_vec.raw_encoding data_field_encoding)
+          (function TypedLazyVec (DataField, vec) -> Some vec | _ -> None)
+          (fun vec -> TypedLazyVec (DataField, vec))
+      in
+      tagged_union
+        (value [] Data_encoding.string)
+        [
+          type_field_encoding;
+          import_field_encoding;
+          func_field_encoding;
+          table_field_encoding;
+          memory_field_encoding;
+          global_field_encoding;
+          export_field_encoding;
+          elem_field_encoding;
+          code_field_encoding;
+          data_field_encoding;
+        ]
+  end
+
+  module Module = struct
+    let mkstart_case =
+      case
+        "MKStart"
+        (value [] Data_encoding.unit)
+        (function Decode.MKStart -> Some () | _ -> None)
+        (fun () -> Decode.MKStart)
+
+    let mkskipcustom_case =
+      case
+        "MKSkipCustom"
+        (option Field.packed_field_type_encoding)
+        (function
+          | Decode.MKSkipCustom (Some field_type) ->
+              Some (Some (Field.FieldType field_type))
+          | Decode.MKSkipCustom None -> Some None
+          | _ -> None)
+        (function
+          | None -> MKSkipCustom None
+          | Some (FieldType ft) -> MKSkipCustom (Some ft))
+
+    let mkfieldstart_case =
+      case
+        "MKFieldStart"
+        Field.packed_field_type_encoding
+        (function
+          | Decode.MKFieldStart field_type -> Some (Field.FieldType field_type)
+          | _ -> None)
+        (fun (FieldType ft) -> MKFieldStart ft)
+
+    let mkfield_case =
+      case
+        "MKField"
+        (tup2 ~flatten:true Field.packed_typed_lazy_vec_encoding Size.encoding)
+        (function
+          | Decode.MKField (field_type, size, vec) ->
+              Some (Field.TypedLazyVec (field_type, vec), size)
+          | _ -> None)
+        (fun (TypedLazyVec (ft, vec), size) -> MKField (ft, size, vec))
+
+    let mkelaboratefunc_case =
+      let func_types = Field.func_field_encoding in
+      let func_bodies = Field.code_field_encoding in
+      let func_kont =
+        scope ["func_kont"] (Lazy_vec.encoding Code.func_encoding)
+      in
+      let no_datas_in_func = value ["no-datas-in-funcs"] Data_encoding.bool in
+      case
+        "MKElaborateFunc"
+        (tup4 ~flatten:true func_types func_bodies func_kont no_datas_in_func)
+        (function
+          | Decode.MKElaborateFunc
+              (func_types, func_bodies, func_kont, no_datas_in_func) ->
+              Some (func_types, func_bodies, func_kont, no_datas_in_func)
+          | _ -> None)
+        (fun (func_types, func_bodies, func_kont, no_datas_in_func) ->
+          MKElaborateFunc (func_types, func_bodies, func_kont, no_datas_in_func))
+
+    let module_funcs_encoding =
+      scope ["module"; "funcs"] (vector_encoding Code.func_encoding)
+
+    let mkbuild_case =
+      let no_datas_in_func = value ["no-datas-in-funcs"] Data_encoding.bool in
+      case
+        "MKBuild"
+        (tup2 ~flatten:true (option module_funcs_encoding) no_datas_in_func)
+        (function
+          | Decode.MKBuild (funcs, no_datas_in_func) ->
+              Some (funcs, no_datas_in_func)
+          | _ -> None)
+        (fun (funcs, no_datas_in_func) -> MKBuild (funcs, no_datas_in_func))
+
+    let mktypes_case =
+      let func_type_kont = scope ["func_type_kont"] Func_type.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let type_accumulator = Lazy_vec.raw_encoding Field.type_field_encoding in
+      case
+        "MKTypes"
+        (tup4 ~flatten:true func_type_kont pos size type_accumulator)
+        (function
+          | Decode.MKTypes (func_type_kont, pos, size, types_acc) ->
+              Some (func_type_kont, pos, size, types_acc)
+          | _ -> None)
+        (fun (func_type_kont, pos, size, types_acc) ->
+          MKTypes (func_type_kont, pos, size, types_acc))
+
+    let mkimport_case =
+      let import_kont = scope ["import_kont"] Import.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let import_accumulator =
+        Lazy_vec.raw_encoding Field.import_field_encoding
+      in
+      case
+        "MKImport"
+        (tup4 ~flatten:true import_kont pos size import_accumulator)
+        (function
+          | Decode.MKImport (import_kont, pos, size, import_acc) ->
+              Some (import_kont, pos, size, import_acc)
+          | _ -> None)
+        (fun (import_kont, pos, size, import_acc) ->
+          MKImport (import_kont, pos, size, import_acc))
+
+    let mkexport_case =
+      let export_kont = scope ["export_kont"] Export.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let export_accumulator =
+        Lazy_vec.raw_encoding Field.export_field_encoding
+      in
+      case
+        "MKExport"
+        (tup4 ~flatten:true export_kont pos size export_accumulator)
+        (function
+          | Decode.MKExport (export_kont, pos, size, export_acc) ->
+              Some (export_kont, pos, size, export_acc)
+          | _ -> None)
+        (fun (export_kont, pos, size, export_acc) ->
+          MKExport (export_kont, pos, size, export_acc))
+
+    let mkglobal_case =
+      let global_type =
+        value ["global_type"] Interpreter_encodings.Types.global_type_encoding
+      in
+      let block_kont = scope ["block_kont"] Block.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let global_accumulator =
+        Lazy_vec.raw_encoding Field.global_field_encoding
+      in
+      case
+        "MKGlobal"
+        (tup5 ~flatten:true global_type pos block_kont size global_accumulator)
+        (function
+          | Decode.MKGlobal (global_type, pos, block_kont, size, global_acc) ->
+              Some (global_type, pos, block_kont, size, global_acc)
+          | _ -> None)
+        (fun (global_type, pos, block_kont, size, global_acc) ->
+          MKGlobal (global_type, pos, block_kont, size, global_acc))
+
+    let mkdata_case =
+      let data_kont = scope ["data_kont"] Data.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let data_accumulator = Lazy_vec.raw_encoding Field.data_field_encoding in
+      case
+        "MKData"
+        (tup4 ~flatten:true data_kont pos size data_accumulator)
+        (function
+          | Decode.MKData (data_kont, pos, size, data_acc) ->
+              Some (data_kont, pos, size, data_acc)
+          | _ -> None)
+        (fun (data_kont, pos, size, data_acc) ->
+          MKData (data_kont, pos, size, data_acc))
+
+    let mkelem_case =
+      let elem_kont = scope ["elem_kont"] Elem.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let elem_accumulator = Lazy_vec.raw_encoding Field.elem_field_encoding in
+      case
+        "MKElem"
+        (tup4 ~flatten:true elem_kont pos size elem_accumulator)
+        (function
+          | Decode.MKElem (elem_kont, pos, size, elem_acc) ->
+              Some (elem_kont, pos, size, elem_acc)
+          | _ -> None)
+        (fun (elem_kont, pos, size, elem_acc) ->
+          MKElem (elem_kont, pos, size, elem_acc))
+
+    let mkcode_case =
+      let code_kont = scope ["code_kont"] Code.encoding in
+      let pos = value ["pos"] Data_encoding.int31 in
+      let size = scope ["size"] Size.encoding in
+      let code_accumulator = Lazy_vec.raw_encoding Field.code_field_encoding in
+      case
+        "MKCode"
+        (tup4 ~flatten:true code_kont pos size code_accumulator)
+        (function
+          | Decode.MKCode (code_kont, pos, size, code_acc) ->
+              Some (code_kont, pos, size, code_acc)
+          | _ -> None)
+        (fun (code_kont, pos, size, code_acc) ->
+          MKCode (code_kont, pos, size, code_acc))
+
+    let module_encoding =
+      let open Field in
+      conv
+        (fun ( types,
+               globals,
+               tables,
+               memories,
+               funcs,
+               start,
+               elems,
+               datas,
+               (imports, exports, allocations) ) ->
+          Ast.
+            {
+              types;
+              tables;
+              memories;
+              globals;
+              funcs;
+              imports;
+              exports;
+              elems;
+              datas;
+              start;
+              allocations;
+            })
+        (fun {
+               types;
+               tables;
+               memories;
+               globals;
+               funcs;
+               imports;
+               exports;
+               elems;
+               datas;
+               start;
+               allocations;
+             } ->
+          ( types,
+            globals,
+            tables,
+            memories,
+            funcs,
+            start,
+            elems,
+            datas,
+            (imports, exports, allocations) ))
+        (tup9
+           ~flatten:true
+           type_field_encoding
+           global_field_encoding
+           table_field_encoding
+           memory_field_encoding
+           module_funcs_encoding
+           start_field_encoding
+           elem_field_encoding
+           data_field_encoding
+           (tup3
+              ~flatten:true
+              import_field_encoding
+              export_field_encoding
+              Wasm_encoding.allocations_encoding))
+
+    let mkstop_case =
+      case
+        "MKStop"
+        (no_region_encoding module_encoding)
+        (function Decode.MKStop m -> Some m | _ -> None)
+        (fun m -> MKStop m)
+
+    let encoding =
+      tagged_union
+        (value [] Data_encoding.string)
+        [
+          mkstart_case;
+          mkskipcustom_case;
+          mkfieldstart_case;
+          mkfield_case;
+          mkelaboratefunc_case;
+          mkbuild_case;
+          mkstop_case;
+          mktypes_case;
+          mkimport_case;
+          mkexport_case;
+          mkglobal_case;
+          mkelem_case;
+          mkdata_case;
+          mkelem_case;
+          mkcode_case;
+        ]
+  end
+
+  module Building_state = struct
+    let types_encoding =
+      vector_encoding (no_region_encoding Wasm_encoding.func_type_encoding)
+
+    let imports_encoding =
+      vector_encoding (no_region_encoding Import.import_encoding)
+
+    let vars_encoding =
+      vector_encoding (value [] Interpreter_encodings.Ast.var_encoding)
+
+    let tables_encoding =
+      vector_encoding (value [] Interpreter_encodings.Ast.table_encoding)
+
+    let memories_encoding =
+      vector_encoding (value [] Interpreter_encodings.Ast.memory_encoding)
+
+    let globals_encoding =
+      vector_encoding (value [] Interpreter_encodings.Ast.global_encoding)
+
+    let exports_encoding =
+      vector_encoding (no_region_encoding Export.export_encoding)
+
+    let start_encoding =
+      value_option [] Interpreter_encodings.Ast.start_encoding
+
+    let elems_encoding = vector_encoding (no_region_encoding Elem.elem_encoding)
+
+    let func_encoding' =
+      conv
+        (fun (ftype, locals, body) -> Ast.{ftype; locals; body})
+        (fun {ftype; locals; body} -> (ftype, locals, body))
+      @@ tup3
+           ~flatten:false
+           (value ["ftype"] Interpreter_encodings.Ast.var_encoding)
+           (scope
+              ["locals"]
+              (vector_encoding
+                 (value [] Interpreter_encodings.Types.value_type_encoding)))
+           (value ["body"] Interpreter_encodings.Ast.block_label_encoding)
+
+    let code_encoding = vector_encoding (no_region_encoding func_encoding')
+
+    let datas_encoding =
+      vector_encoding (no_region_encoding Data.data_segment_encoding)
+
+    let encoding =
+      conv
+        (fun ( types,
+               imports,
+               vars,
+               tables,
+               memories,
+               globals,
+               exports,
+               start,
+               (elems, data_count, code, datas) ) ->
+          Decode.
+            {
+              types;
+              imports;
+              vars;
+              tables;
+              memories;
+              globals;
+              exports;
+              start;
+              elems;
+              data_count;
+              code;
+              datas;
+            })
+        (fun {
+               types;
+               imports;
+               vars;
+               tables;
+               memories;
+               globals;
+               exports;
+               start;
+               elems;
+               data_count;
+               code;
+               datas;
+             } ->
+          ( types,
+            imports,
+            vars,
+            tables,
+            memories,
+            globals,
+            exports,
+            start,
+            (elems, data_count, code, datas) ))
+        (tup9
+           ~flatten:true
+           (scope ["types"] types_encoding)
+           (scope ["imports"] imports_encoding)
+           (scope ["vars"] vars_encoding)
+           (scope ["tables"] tables_encoding)
+           (scope ["memories"] memories_encoding)
+           (scope ["globals"] globals_encoding)
+           (scope ["exports"] exports_encoding)
+           (scope ["start"] start_encoding)
+           (tup4
+              ~flatten:true
+              (scope ["elems"] elems_encoding)
+              (scope ["data_count"] (value_option [] Data_encoding.int32))
+              (scope ["code"] code_encoding)
+              (scope ["datas"] datas_encoding)))
+  end
+
+  module Decode = struct
+    let encoding =
+      conv
+        (fun ( building_state,
+               module_kont,
+               allocation_state,
+               stream_pos,
+               stream_name ) ->
+          Decode.
+            {
+              building_state;
+              module_kont;
+              allocation_state;
+              stream_pos;
+              stream_name;
+            })
+        (fun {
+               building_state;
+               module_kont;
+               allocation_state;
+               stream_pos;
+               stream_name;
+             } ->
+          ( building_state,
+            module_kont,
+            allocation_state,
+            stream_pos,
+            stream_name ))
+      @@ tup5
+           ~flatten:true
+           (scope ["building_state"] Building_state.encoding)
+           (scope ["module_kont"] Module.encoding)
+           (scope ["allocation_state"] Wasm_encoding.allocations_encoding)
+           (value ["stream_pos"] Data_encoding.int31)
+           (value ["stream_name"] Data_encoding.string)
+  end
+end
diff --git a/src/lib_scoru_wasm/interpreter_encodings.ml b/src/lib_scoru_wasm/interpreter_encodings.ml
index 45c81578cf5ea392e7e6a56229da50aeb473f1da..7a38bf0c205ed34626a876a74f01ecebc2bbc009 100644
--- a/src/lib_scoru_wasm/interpreter_encodings.ml
+++ b/src/lib_scoru_wasm/interpreter_encodings.ml
@@ -32,6 +32,14 @@ let string_enum cases =
   | [(title, value)] -> conv (fun _ -> ()) (fun () -> value) (constant title)
   | cases -> string_enum cases
 
+module Source = struct
+  open Source
+
+  let phrase_encoding encoding =
+    let open Data_encoding in
+    conv (fun x -> x.it) (fun v -> v @@ no_region) encoding
+end
+
 module Types = struct
   open Types
 
@@ -108,6 +116,34 @@ module Types = struct
         unit_case_incr "ExtSplat" ExtSplat;
         unit_case_incr "ExtZero" ExtZero;
       ]
+
+  let global_type_encoding =
+    let open Data_encoding in
+    conv
+      (fun (Types.GlobalType (v, m)) -> (v, m))
+      (fun (v, m) -> Types.GlobalType (v, m))
+      (tup2 value_type_encoding mutability_encoding)
+
+  let limits_encoding value_encoding =
+    let open Data_encoding in
+    conv
+      (fun {min; max} -> (min, max))
+      (fun (min, max) -> {min; max})
+      (tup2 value_encoding (option value_encoding))
+
+  let table_type_encoding =
+    let open Data_encoding in
+    conv
+      (fun (TableType (l, r)) -> (l, r))
+      (fun (l, r) -> TableType (l, r))
+      (tup2 (limits_encoding int32) ref_type_encoding)
+
+  let memory_type_encoding =
+    let open Data_encoding in
+    conv
+      (fun (MemoryType l) -> l)
+      (fun l -> MemoryType l)
+      (limits_encoding int32)
 end
 
 module Values = struct
@@ -530,20 +566,11 @@ module Ast = struct
             (memop_encoding Types.vec_type_encoding Types.pack_size_encoding))
          (req "lane" int31))
 
-  let var_encoding =
-    let open Data_encoding in
-    let open Source in
-    conv (fun x -> x.it) (fun var -> var @@ no_region) Data_encoding.int32
+  let var_encoding = Source.phrase_encoding Data_encoding.int32
 
-  let num_encoding =
-    let open Data_encoding in
-    let open Source in
-    conv (fun x -> x.it) (fun x -> x @@ no_region) Values.num_encoding
+  let num_encoding = Source.phrase_encoding Values.num_encoding
 
-  let vec_encoding =
-    let open Data_encoding in
-    let open Source in
-    conv (fun x -> x.it) (fun vec -> vec @@ no_region) Values.vec_encoding
+  let vec_encoding = Source.phrase_encoding Values.vec_encoding
 
   let block_type_encoding =
     let open Data_encoding in
@@ -571,4 +598,128 @@ module Ast = struct
     let open Data_encoding in
     let open Ast in
     conv (fun (Data_label l) -> l) (fun l -> Data_label l) int32
+
+  let import_desc_encoding =
+    let open Ast in
+    let unannotated_encoding =
+      union_incr
+        [
+          case_incr
+            "FuncImport"
+            var_encoding
+            (function FuncImport v -> Some v | _ -> None)
+            (fun v -> FuncImport v);
+          case_incr
+            "TableImport"
+            Types.table_type_encoding
+            (function TableImport t -> Some t | _ -> None)
+            (fun t -> TableImport t);
+          case_incr
+            "MemoryImport"
+            Types.memory_type_encoding
+            (function MemoryImport m -> Some m | _ -> None)
+            (fun m -> MemoryImport m);
+          case_incr
+            "GlobalImport"
+            Types.global_type_encoding
+            (function GlobalImport g -> Some g | _ -> None)
+            (fun g -> GlobalImport g);
+        ]
+    in
+    Source.phrase_encoding unannotated_encoding
+
+  let export_desc_encoding =
+    let open Ast in
+    let unannotated_encoding =
+      union_incr
+        [
+          case_incr
+            "FuncExport"
+            var_encoding
+            (function FuncExport v -> Some v | _ -> None)
+            (fun v -> FuncExport v);
+          case_incr
+            "TableExport"
+            var_encoding
+            (function TableExport t -> Some t | _ -> None)
+            (fun t -> TableExport t);
+          case_incr
+            "MemoryExport"
+            var_encoding
+            (function MemoryExport m -> Some m | _ -> None)
+            (fun m -> MemoryExport m);
+          case_incr
+            "GlobalExport"
+            var_encoding
+            (function GlobalExport g -> Some g | _ -> None)
+            (fun g -> GlobalExport g);
+        ]
+    in
+    Source.phrase_encoding unannotated_encoding
+
+  let const_encoding = Source.phrase_encoding block_label_encoding
+
+  let segment_mode_encoding =
+    let open Data_encoding in
+    let unannotated_encoding =
+      union_incr
+        [
+          case_incr
+            "Passive"
+            (constant "Passive")
+            (function Ast.Passive -> Some () | _ -> None)
+            (fun () -> Passive);
+          case_incr
+            "Active"
+            (tup2 var_encoding const_encoding)
+            (function
+              | Ast.Active {index; offset} -> Some (index, offset) | _ -> None)
+            (fun (index, offset) -> Active {index; offset});
+          case_incr
+            "Declarative"
+            (constant "Declarative")
+            (function Ast.Declarative -> Some () | _ -> None)
+            (fun () -> Declarative);
+        ]
+    in
+    Source.phrase_encoding unannotated_encoding
+
+  let table_encoding =
+    let open Data_encoding in
+    let unannoted_encoding =
+      conv
+        (fun {ttype} -> ttype)
+        (fun ttype -> {ttype})
+        Types.table_type_encoding
+    in
+    Source.phrase_encoding unannoted_encoding
+
+  let memory_encoding =
+    let open Data_encoding in
+    let unannoted_encoding =
+      conv
+        (fun {mtype} -> mtype)
+        (fun mtype -> {mtype})
+        Types.memory_type_encoding
+    in
+    Source.phrase_encoding unannoted_encoding
+
+  let global_encoding =
+    let open Data_encoding in
+    let unannoted_encoding =
+      conv
+        (fun {gtype; ginit} -> (gtype, ginit))
+        (fun (gtype, ginit) -> {gtype; ginit})
+        (tup2
+           Types.global_type_encoding
+           (Source.phrase_encoding block_label_encoding))
+    in
+    Source.phrase_encoding unannoted_encoding
+
+  let start_encoding =
+    let open Data_encoding in
+    let unannoted_encoding =
+      conv (fun {sfunc} -> sfunc) (fun sfunc -> {sfunc}) var_encoding
+    in
+    Source.phrase_encoding unannoted_encoding
 end
diff --git a/src/lib_scoru_wasm/interpreter_encodings.mli b/src/lib_scoru_wasm/interpreter_encodings.mli
index 32c232b537c1e38995062a4f9312de41bfcf982a..2f07a4e07ea4d677ecbfaba52ea054cad9ee5d5f 100644
--- a/src/lib_scoru_wasm/interpreter_encodings.mli
+++ b/src/lib_scoru_wasm/interpreter_encodings.mli
@@ -23,6 +23,12 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+module Source : sig
+  open Tezos_webassembly_interpreter.Source
+
+  val phrase_encoding : 'a Data_encoding.t -> 'a phrase Data_encoding.t
+end
+
 module Types : sig
   open Tezos_webassembly_interpreter.Types
 
@@ -50,6 +56,8 @@ module Types : sig
   val extension_encoding : extension Data_encoding.t
 
   val vec_extension_encoding : vec_extension Data_encoding.t
+
+  val global_type_encoding : global_type Data_encoding.t
 end
 
 module Values : sig
@@ -215,4 +223,20 @@ module Ast : sig
   val block_label_encoding : Ast.block_label Data_encoding.t
 
   val data_label_encoding : Ast.data_label Data_encoding.t
+
+  val import_desc_encoding : Ast.import_desc Data_encoding.t
+
+  val export_desc_encoding : Ast.export_desc Data_encoding.t
+
+  val const_encoding : Ast.const Data_encoding.t
+
+  val segment_mode_encoding : Ast.segment_mode Data_encoding.t
+
+  val table_encoding : Ast.table Data_encoding.t
+
+  val memory_encoding : Ast.memory Data_encoding.t
+
+  val global_encoding : Ast.global Data_encoding.t
+
+  val start_encoding : Ast.start Data_encoding.t
 end
diff --git a/src/lib_scoru_wasm/test/ast_generators.ml b/src/lib_scoru_wasm/test/ast_generators.ml
index 87c7171fc274730cdf88ee325bb7889237259106..092af5c5430cfedbcbc4c2d73e8b8c259ca3f188 100644
--- a/src/lib_scoru_wasm/test/ast_generators.ml
+++ b/src/lib_scoru_wasm/test/ast_generators.ml
@@ -412,6 +412,66 @@ let allocations_gen =
   let+ datas = datas_table_gen in
   Ast.{blocks; datas}
 
+let limit_gen gen =
+  let* min = gen in
+  let* max = opt gen in
+  return {Types.min; Types.max}
+
+let table_type_gen =
+  let* limit = limit_gen int32 in
+  let* ref_type = ref_type_gen in
+  return @@ Types.TableType (limit, ref_type)
+
+let memory_type_gen =
+  let+ limit = limit_gen int32 in
+  Types.MemoryType limit
+
+let global_type_gen =
+  let* vt = value_type_gen in
+  let* mt = oneofl [Types.Immutable; Types.Mutable] in
+  return @@ Types.GlobalType (vt, mt)
+
+let import_desc_gen =
+  let+ idesc =
+    oneof
+      [
+        map (fun v -> Ast.FuncImport v) var_gen;
+        map (fun tt -> Ast.TableImport tt) table_type_gen;
+        map (fun mt -> Ast.MemoryImport mt) memory_type_gen;
+        map (fun gt -> Ast.GlobalImport gt) global_type_gen;
+      ]
+  in
+  no_region idesc
+
+let export_desc_gen =
+  let+ edesc =
+    oneof
+      [
+        map (fun v -> Ast.FuncExport v) var_gen;
+        map (fun v -> Ast.TableExport v) var_gen;
+        map (fun v -> Ast.MemoryExport v) var_gen;
+        map (fun v -> Ast.GlobalExport v) var_gen;
+      ]
+  in
+  no_region edesc
+
+let const_gen = map no_region block_label_gen
+
+let segment_mode_gen =
+  let passive = return Ast.Passive in
+  let active =
+    let* index = var_gen in
+    let+ offset = block_label_gen in
+    Ast.Active {index; offset = no_region offset}
+  in
+  let declarative = return Ast.Declarative in
+  let+ mode = oneof [passive; active; declarative] in
+  no_region mode
+
+let start_gen =
+  let+ sfunc = var_gen in
+  no_region Ast.{sfunc}
+
 let module_key_and_instance_gen ?module_reg () =
   let module_reg =
     match module_reg with
diff --git a/src/lib_scoru_wasm/test/test_ast_generators.ml b/src/lib_scoru_wasm/test/test_ast_generators.ml
index a406cf4a4d932db00c539601ea6ca2d21b46b8eb..c9ac97a6be00d0ba22ecf58c29b23df0a7eee72c 100644
--- a/src/lib_scoru_wasm/test/test_ast_generators.ml
+++ b/src/lib_scoru_wasm/test/test_ast_generators.ml
@@ -27,7 +27,7 @@
     -------
     Component:    Tree_encoding
     Invocation:   dune exec  src/lib_scoru_wasm/test/test_scoru_wasm.exe \
-                    -- test "AST Generators"
+                    -- test "^AST Generators$"
     Subject:      Encoding tests for the tezos-scoru-wasm library
 *)
 
diff --git a/src/lib_scoru_wasm/test/test_input.ml b/src/lib_scoru_wasm/test/test_input.ml
index d25e9cbe07c9f2721418623a9e8f1ced109c8702..3f468a5202ba6cf1c575785d9d49adc3045919fa 100644
--- a/src/lib_scoru_wasm/test/test_input.ml
+++ b/src/lib_scoru_wasm/test/test_input.ml
@@ -27,7 +27,7 @@
     -------
     Component:    Lib_scoru_wasm input
     Invocation:   dune exec  src/lib_scoru_wasm/test/test_scoru_wasm.exe \
-                    -- test "$Encodings^"
+                    -- test "^Input$"
     Subject:      Input tests for the tezos-scoru-wasm library
 *)
 
diff --git a/src/lib_scoru_wasm/test/test_parser_encoding.ml b/src/lib_scoru_wasm/test/test_parser_encoding.ml
new file mode 100644
index 0000000000000000000000000000000000000000..a98b820d1c6745a06bc7298bc969461265fe7ca1
--- /dev/null
+++ b/src/lib_scoru_wasm/test/test_parser_encoding.ml
@@ -0,0 +1,1422 @@
+(*****************************************************************************)
+(*                                                                           *)
+(* Open Source License                                                       *)
+(* Copyright (c) 2022 Nomadic Labs <contact@nomadic-labs.com>                *)
+(*                                                                           *)
+(* Permission is hereby granted, free of charge, to any person obtaining a   *)
+(* copy of this software and associated documentation files (the "Software"),*)
+(* to deal in the Software without restriction, including without limitation *)
+(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
+(* and/or sell copies of the Software, and to permit persons to whom the     *)
+(* Software is furnished to do so, subject to the following conditions:      *)
+(*                                                                           *)
+(* The above copyright notice and this permission notice shall be included   *)
+(* in all copies or substantial portions of the Software.                    *)
+(*                                                                           *)
+(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
+(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
+(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
+(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
+(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
+(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
+(* DEALINGS IN THE SOFTWARE.                                                 *)
+(*                                                                           *)
+(*****************************************************************************)
+
+(** Testing
+    -------
+    Component:    Tree_encoding_decoding
+    Invocation:   dune exec  src/lib_scoru_wasm/test/test_scoru_wasm.exe \
+                    -- test "^Parser Encodings$"
+    Subject:      Parser encoding tests for the tezos-scoru-wasm library
+*)
+
+open Tztest
+open Lazy_containers
+open Tezos_webassembly_interpreter
+open Tezos_scoru_wasm
+
+(* Use context-binary for testing. *)
+module Context = Tezos_context_memory.Context_binary
+
+module Tree :
+  Tezos_context_sigs.Context.TREE
+    with type t = Context.t
+     and type tree = Context.tree
+     and type key = string list
+     and type value = bytes = struct
+  type t = Context.t
+
+  type tree = Context.tree
+
+  type key = Context.key
+
+  type value = Context.value
+
+  include Context.Tree
+end
+
+type Lazy_containers.Lazy_map.tree += Tree of Tree.tree
+
+module Tree_encoding = struct
+  include Tree_encoding.Make (struct
+    include Tree
+
+    let select = function
+      | Tree t -> t
+      | _ -> raise Tree_encoding.Incorrect_tree_type
+
+    let wrap t = Tree t
+  end)
+
+  include Lazy_map_encoding.Make (Instance.NameMap)
+end
+
+module Parser = Binary_parser_encodings.Make (Tree_encoding)
+
+module Utils = struct
+  include Tree_encoding
+  module V = Lazy_vector.LwtInt32Vector
+  module C = Chunked_byte_vector.Lwt
+
+  let empty_tree () =
+    let open Lwt_syntax in
+    let* index = Context.init "/tmp" in
+    let empty_store = Context.empty index in
+    return @@ Context.Tree.empty empty_store
+
+  let test_encode_decode enc value f =
+    let open Lwt_result_syntax in
+    let*! empty_tree = empty_tree () in
+    let*! tree = Tree_encoding.encode enc value empty_tree in
+    let*! value' = Tree_encoding.decode enc tree in
+    f value'
+
+  let encode_decode enc value = test_encode_decode enc value Lwt.return
+
+  let make_test encoding gen check () =
+    Test_wasm_encoding.qcheck gen (fun value ->
+        let open Lwt_result_syntax in
+        let*! value' = encode_decode encoding value in
+        let* res = check value value' in
+        (* TODO: a better error reporting could be useful. *)
+        if res then return_unit else fail ())
+end
+
+module Byte_vector = struct
+  open Utils
+
+  let gen_chunked_byte_vector =
+    let open QCheck2.Gen in
+    let+ values = string in
+    C.of_string values
+
+  let gen_buffer =
+    let open QCheck2.Gen in
+    let* buffer = Ast_generators.data_label_gen in
+    let* length = int64 in
+    let+ offset = int64 in
+    (buffer, offset, length)
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.VKStart in
+    let read =
+      let+ buffer, offset, length = gen_buffer in
+      Decode.VKRead (buffer, offset, length)
+    in
+    let stop =
+      let+ vec = Ast_generators.data_label_gen in
+      Decode.VKStop vec
+    in
+    oneof [start; read; stop]
+
+  let check_buffer (buffer, offset, length) (buffer', offset', length') =
+    let open Lwt_result_syntax in
+    return
+      (buffer = buffer' && Int64.equal offset offset'
+     && Int64.equal length length')
+
+  let check_vector vector vector' =
+    let open Lwt_result_syntax in
+    assert (C.length vector = C.length vector') ;
+    let*! str = C.to_string vector in
+    let*! str' = C.to_string vector' in
+    return (String.equal str str')
+
+  let check bv bv' =
+    match (bv, bv') with
+    | Decode.VKStart, Decode.VKStart -> Lwt.return_ok true
+    | VKRead (buffer, offset, length), VKRead (buffer', offset', length') ->
+        check_buffer (buffer, offset, length) (buffer', offset', length')
+    | VKStop label, VKStop label' -> Lwt.return_ok (label = label')
+    | _, _ -> Lwt.return_ok false
+
+  let tests =
+    [
+      tztest
+        "Byte_vector"
+        `Quick
+        (make_test Parser.Byte_vector.encoding gen check);
+    ]
+end
+
+(* Lazy_vector generators *)
+module Vec = struct
+  open Utils
+
+  let gen gen_values =
+    let open QCheck2.Gen in
+    let* length = int_range 1 100 in
+    let* values = list_repeat length gen_values in
+    let vec =
+      List.fold_left_i
+        (fun index vec value -> V.set (Int32.of_int index) value vec)
+        (V.create (Int32.of_int length))
+        values
+    in
+    return vec
+
+  (* Vectors will always be of same type, but some GADTs usage can
+     make them virtually of different type. See
+     {!Module.check_field_type_value} and it's usage when checking
+     equality of two [MKField] states. *)
+  let check_possibly_different (eq_value : 'a -> 'b -> (bool, _) result Lwt.t)
+      (vector : 'a V.t) (vector' : 'b V.t) =
+    let open Lwt_result_syntax in
+    assert (V.num_elements vector = V.num_elements vector') ;
+    let*! eq_s =
+      List.init_es
+        ~when_negative_length:()
+        (Int32.to_int (V.num_elements vector) - 1)
+        (fun index ->
+          let*! v = V.get (Int32.of_int index) vector in
+          let*! v' = V.get (Int32.of_int index) vector' in
+          eq_value v v')
+    in
+    match eq_s with
+    | Ok b -> return (List.for_all Stdlib.(( = ) true) b)
+    | Error () -> return false
+
+  (* Checks two vectors are equivalent. *)
+  let check (eq_value : 'a -> 'a -> (bool, _) result Lwt.t) (vector : 'a V.t)
+      (vector' : 'a V.t) =
+    check_possibly_different eq_value vector vector'
+
+  let tests =
+    let eq x y = Lwt.return_ok (Int32.equal x y) in
+    [
+      tztest
+        "Vec"
+        `Quick
+        (make_test
+           Parser.(vector_encoding (value [] Data_encoding.int32))
+           (gen QCheck2.Gen.int32)
+           (check eq));
+    ]
+end
+
+(* Generators for Lazy_vec, similar to {!Vec}. *)
+module LazyVec = struct
+  open Utils
+
+  let gen_with_vec gen_vec =
+    let open QCheck2.Gen in
+    let* vector = gen_vec in
+    let* offset =
+      Lib_test.Qcheck2_helpers.int32_range_gen 0l (V.num_elements vector)
+    in
+    return (Decode.LazyVec {vector; offset})
+
+  let gen gen_values = gen_with_vec (Vec.gen gen_values)
+
+  let check eq_value (Decode.LazyVec {vector; offset})
+      (Decode.LazyVec {vector = vector'; offset = offset'}) =
+    let open Lwt_result_syntax in
+    let* eq_lzvecs = Vec.check eq_value vector vector' in
+    return (eq_lzvecs && offset = offset')
+
+  let check_possibly_different eq_value (Decode.LazyVec {vector; offset})
+      (Decode.LazyVec {vector = vector'; offset = offset'}) =
+    let open Lwt_result_syntax in
+    let* eq_lzvecs = Vec.check_possibly_different eq_value vector vector' in
+    return (eq_lzvecs && offset = offset')
+
+  let tests =
+    let eq x y = Lwt.return_ok (Int32.equal x y) in
+    [
+      tztest
+        "LazyVec"
+        `Quick
+        (make_test
+           Parser.Lazy_vec.(encoding (value [] Data_encoding.int32))
+           (gen QCheck2.Gen.int32)
+           (check eq));
+    ]
+end
+
+module Names = struct
+  open Utils
+
+  let gen_utf8 = QCheck2.Gen.small_nat
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.NKStart in
+    let parse =
+      let* (Decode.LazyVec {vector; _} as buffer) = LazyVec.gen gen_utf8 in
+      let vector_length = Int32.to_int (V.num_elements vector) in
+      let* offset = int_range 0 vector_length in
+      let+ length = int_range vector_length (vector_length * 2) in
+      Decode.NKParse (offset, buffer, length)
+    in
+    let stop =
+      let+ buffer = Vec.gen small_nat in
+      Decode.NKStop buffer
+    in
+    oneof [start; parse; stop]
+
+  let check ns ns' =
+    let open Lwt_result_syntax in
+    let eq_value x y = return (x = y) in
+    match (ns, ns') with
+    | Decode.NKStart, Decode.NKStart -> return true
+    | NKParse (offset, buffer, length), NKParse (offset', buffer', length') ->
+        let+ eq_bs = LazyVec.check eq_value buffer buffer' in
+        eq_bs && offset = offset' && length = length'
+    | NKStop vec, NKStop vec' -> Vec.check eq_value vec vec'
+    | _, _ -> return false
+
+  let tests = [tztest "Names" `Quick (make_test Parser.Name.encoding gen check)]
+end
+
+module Func_type = struct
+  open Utils
+
+  let func_type_gen =
+    let open QCheck2.Gen in
+    let* ins = Vec.gen Ast_generators.value_type_gen in
+    let+ out = Vec.gen Ast_generators.value_type_gen in
+    Types.FuncType (ins, out)
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.FKStart in
+    let ins =
+      let+ ins = LazyVec.gen Ast_generators.value_type_gen in
+      Decode.FKIns ins
+    in
+    let out =
+      let* ins = Vec.gen Ast_generators.value_type_gen in
+      let+ out = LazyVec.gen Ast_generators.value_type_gen in
+      Decode.FKOut (ins, out)
+    in
+    let stop =
+      let+ ft = func_type_gen in
+      Decode.FKStop ft
+    in
+    oneof [start; ins; out; stop]
+
+  let func_type_check (Types.FuncType (ins, out)) (Types.FuncType (ins', out'))
+      =
+    let open Lwt_result_syntax in
+    let eq_value_types t t' = return Stdlib.(t = t') in
+    let* eq_ins = Vec.check eq_value_types ins ins' in
+    let+ eq_out = Vec.check eq_value_types out out' in
+    eq_ins && eq_out
+
+  let check fk fk' =
+    let open Lwt_result_syntax in
+    let eq_value_types t t' = return Stdlib.(t = t') in
+    match (fk, fk') with
+    | Decode.FKStart, Decode.FKStart -> return true
+    | FKIns ins, FKIns ins' -> LazyVec.check eq_value_types ins ins'
+    | FKOut (ins, out), FKOut (ins', out') ->
+        let* eq_ins = Vec.check eq_value_types ins ins' in
+        let+ eq_out = LazyVec.check eq_value_types out out' in
+        eq_ins && eq_out
+    | FKStop ft, FKStop ft' -> func_type_check ft ft'
+    | _, _ -> return false
+
+  let tests =
+    [tztest "Func_type" `Quick (make_test Parser.Func_type.encoding gen check)]
+end
+
+module Imports = struct
+  open Utils
+
+  let import_gen =
+    let open QCheck2.Gen in
+    let* modl = Vec.gen Names.gen_utf8 in
+    let* item = Vec.gen Names.gen_utf8 in
+    let+ idesc = Ast_generators.import_desc_gen in
+    Ast.{module_name = modl; item_name = item; idesc}
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.ImpKStart in
+    let module_name =
+      let+ modl = Names.gen in
+      Decode.ImpKModuleName modl
+    in
+    let item_name =
+      let* modl = Vec.gen Names.gen_utf8 in
+      let+ item = Names.gen in
+      Decode.ImpKItemName (modl, item)
+    in
+    let stop =
+      let+ import = import_gen in
+      Decode.ImpKStop import
+    in
+    oneof [start; module_name; item_name; stop]
+
+  let import_check import import' =
+    let open Lwt_result_syntax in
+    let eq_value x y = return (x = y) in
+    let* eq_m =
+      Vec.check eq_value import.Ast.module_name import'.Ast.module_name
+    in
+    let+ eq_i = Vec.check eq_value import.item_name import'.item_name in
+    eq_m && eq_i && import.idesc = import'.idesc
+
+  let check import import' =
+    let open Lwt_result_syntax in
+    match (import, import') with
+    | Decode.ImpKStart, Decode.ImpKStart -> return true
+    | ImpKModuleName m, ImpKModuleName m' -> Names.check m m'
+    | ImpKItemName (m, i), ImpKItemName (m', i') ->
+        let eq_value x y = return (x = y) in
+        let* eq_m = Vec.check eq_value m m' in
+        let+ eq_i = Names.check i i' in
+        eq_m && eq_i
+    | ImpKStop imp, ImpKStop imp' -> import_check imp imp'
+    | _, _ -> return false
+
+  let tests =
+    [tztest "Imports" `Quick (make_test Parser.Import.encoding gen check)]
+end
+
+module LazyStack = struct
+  open Utils
+
+  let gen gen_values =
+    let open QCheck2.Gen in
+    let* vector = Vec.gen gen_values in
+    let* length =
+      Lib_test.Qcheck2_helpers.int32_range_gen 0l (V.num_elements vector)
+    in
+    return (Decode.LazyStack {vector; length})
+
+  let check eq_value (Decode.LazyStack {vector; length})
+      (Decode.LazyStack {vector = vector'; length = length'}) =
+    let open Lwt_result_syntax in
+    let* eq_lzs = Vec.check eq_value vector vector' in
+    return (eq_lzs && length = length')
+
+  let tests =
+    let eq x y = Lwt.return_ok (Int32.equal x y) in
+    [
+      tztest
+        "LazyStack"
+        `Quick
+        (make_test
+           Parser.Lazy_stack.(encoding (value [] Data_encoding.int32))
+           (gen QCheck2.Gen.int32)
+           (check eq));
+    ]
+end
+
+module Exports = struct
+  open Utils
+
+  let export_gen =
+    let open QCheck2.Gen in
+    let* name = Vec.gen Names.gen_utf8 in
+    let+ edesc = Ast_generators.export_desc_gen in
+    Ast.{name; edesc}
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.ExpKStart in
+    let name =
+      let+ name = Names.gen in
+      Decode.ExpKName name
+    in
+    let stop =
+      let+ export = export_gen in
+      Decode.ExpKStop export
+    in
+    oneof [start; name; stop]
+
+  let export_check exp exp' =
+    let open Lwt_result_syntax in
+    let eq_value x y = return (x = y) in
+    let+ eq_n = Vec.check eq_value exp.Ast.name exp'.Ast.name in
+    eq_n && exp.edesc = exp'.edesc
+
+  let check export export' =
+    let open Lwt_result_syntax in
+    match (export, export') with
+    | Decode.ExpKStart, Decode.ExpKStart -> return true
+    | ExpKName n, ExpKName n' -> Names.check n n'
+    | ExpKStop exp, ExpKStop exp' -> export_check exp exp'
+    | _, _ -> return false
+
+  let tests =
+    [tztest "Exports" `Quick (make_test Parser.Export.encoding gen check)]
+end
+
+module Size = struct
+  open Utils
+
+  let gen =
+    let open QCheck2.Gen in
+    let* size = small_nat in
+    let+ start = small_nat in
+    Decode.{size; start}
+
+  let check s s' =
+    let open Lwt_result_syntax in
+    return (s.Decode.size = s'.Decode.size && s.start = s'.start)
+
+  let tests = [tztest "Size" `Quick (make_test Parser.Size.encoding gen check)]
+end
+
+module Instr_block = struct
+  open Utils
+
+  let gen =
+    let open QCheck2.Gen in
+    let stop =
+      let+ lbl = Ast_generators.block_label_gen in
+      Decode.IKStop lbl
+    in
+    let next =
+      let+ lbl = Ast_generators.block_label_gen in
+      Decode.IKNext lbl
+    in
+    let block =
+      let* ty = Ast_generators.block_type_gen in
+      let+ pos = small_nat in
+      Decode.IKBlock (ty, pos)
+    in
+    let loop =
+      let* ty = Ast_generators.block_type_gen in
+      let+ pos = small_nat in
+      Decode.IKLoop (ty, pos)
+    in
+    let if1 =
+      let* ty = Ast_generators.block_type_gen in
+      let+ pos = small_nat in
+      Decode.IKIf1 (ty, pos)
+    in
+    let if2 =
+      let* ty = Ast_generators.block_type_gen in
+      let* pos = small_nat in
+      let+ lbl = Ast_generators.block_label_gen in
+      Decode.IKIf2 (ty, pos, lbl)
+    in
+    oneof [stop; next; block; loop; if1; if2]
+
+  let check ik ik' =
+    let open Lwt_result_syntax in
+    match (ik, ik') with
+    | Decode.IKStop l, Decode.IKStop l' | IKNext l, IKNext l' -> return (l = l')
+    | IKBlock (ty, pos), IKBlock (ty', pos')
+    | IKLoop (ty, pos), IKLoop (ty', pos')
+    | IKIf1 (ty, pos), IKIf1 (ty', pos') ->
+        return (ty = ty' && pos = pos')
+    | IKIf2 (ty, pos, l), IKIf2 (ty', pos', l') ->
+        return (ty = ty' && pos = pos' && l = l')
+    | _, _ -> return_false
+
+  let tests =
+    [
+      tztest
+        "Instr_block"
+        `Quick
+        (make_test Parser.Instr_block.encoding gen check);
+    ]
+end
+
+module Block = struct
+  open Utils
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.BlockStart in
+    let parse =
+      let+ instr_stack = LazyStack.gen Instr_block.gen in
+      Decode.BlockParse instr_stack
+    in
+    let stop =
+      let+ lbl = Ast_generators.block_label_gen in
+      Decode.BlockStop lbl
+    in
+    oneof [start; parse; stop]
+
+  let check bl bl' =
+    let open Lwt_result_syntax in
+    match (bl, bl') with
+    | Decode.BlockStart, Decode.BlockStart -> return_true
+    | BlockParse is, BlockParse is' -> LazyStack.check Instr_block.check is is'
+    | BlockStop l, BlockStop l' -> return (l = l')
+    | _, _ -> return_false
+
+  let tests =
+    [tztest "Block" `Quick (make_test Parser.Block.encoding gen check)]
+end
+
+module Code = struct
+  open Utils
+
+  let func_gen =
+    let open QCheck2.Gen in
+    let* ftype = Ast_generators.var_gen in
+    let* locals = Vec.gen Ast_generators.value_type_gen in
+    let+ body = Ast_generators.block_label_gen in
+    Source.(Ast.{ftype; locals; body} @@ no_region)
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.CKStart in
+    let locals_parse =
+      let* left = small_nat in
+      let* size = Size.gen in
+      let* pos = small_nat in
+      let* vec_kont = LazyVec.gen (pair int32 Ast_generators.value_type_gen) in
+      let+ locals_size = int64 in
+      Decode.CKLocalsParse {left; size; pos; vec_kont; locals_size}
+    in
+    let locals_accumulate =
+      let* left = small_nat in
+      let* size = Size.gen in
+      let* pos = small_nat in
+      let* type_vec = LazyVec.gen (pair int32 Ast_generators.value_type_gen) in
+      let* curr_type = opt (pair int32 Ast_generators.value_type_gen) in
+      let+ vec_kont = LazyVec.gen Ast_generators.value_type_gen in
+      Decode.CKLocalsAccumulate {left; size; pos; type_vec; curr_type; vec_kont}
+    in
+    let body =
+      let* left = small_nat in
+      let* size = Size.gen in
+      let* locals = Vec.gen Ast_generators.value_type_gen in
+      let+ const_kont = Block.gen in
+      Decode.CKBody {left; size; locals; const_kont}
+    in
+    let stop =
+      let+ func = func_gen in
+      Decode.CKStop func
+    in
+    oneof [start; locals_parse; locals_accumulate; body; stop]
+
+  let check_func Ast.{ftype; locals; body}
+      Ast.{ftype = ftype'; locals = locals'; body = body'} =
+    let open Lwt_result_syntax in
+    let eq_value_type t t' = return (t = t') in
+    let+ eq_locals = Vec.check eq_value_type locals locals' in
+    ftype = ftype' && body = body' && eq_locals
+
+  let check code code' =
+    let open Lwt_result_syntax in
+    let eq_value_type t t' = return (t = t') in
+    match (code, code') with
+    | Decode.CKStart, Decode.CKStart -> return_true
+    | ( Decode.CKLocalsParse {left; size; pos; vec_kont; locals_size},
+        Decode.CKLocalsParse
+          {
+            left = left';
+            size = size';
+            pos = pos';
+            vec_kont = vec_kont';
+            locals_size = locals_size';
+          } ) ->
+        let+ eq_vec_kont = LazyVec.check eq_value_type vec_kont vec_kont' in
+        eq_vec_kont && left = left' && size = size' && pos = pos'
+        && locals_size = locals_size'
+    | ( Decode.CKLocalsAccumulate
+          {left; size; pos; type_vec; curr_type; vec_kont},
+        Decode.CKLocalsAccumulate
+          {
+            left = left';
+            size = size';
+            pos = pos';
+            type_vec = type_vec';
+            curr_type = curr_type';
+            vec_kont = vec_kont';
+          } ) ->
+        let* eq_type_vec = LazyVec.check eq_value_type type_vec type_vec' in
+        let+ eq_vec_kont = LazyVec.check eq_value_type vec_kont vec_kont' in
+        eq_type_vec && eq_vec_kont && left = left' && size = size' && pos = pos'
+        && curr_type = curr_type'
+    | ( Decode.CKBody {left; size; locals; const_kont},
+        Decode.CKBody
+          {
+            left = left';
+            size = size';
+            locals = locals';
+            const_kont = const_kont';
+          } ) ->
+        let* eq_locals = Vec.check eq_value_type locals locals' in
+        let+ eq_const_kont = Block.check const_kont const_kont' in
+        eq_locals && eq_const_kont && left = left' && size = size'
+    | Decode.CKStop Source.{it = func; _}, Decode.CKStop Source.{it = func'; _}
+      ->
+        check_func func func'
+    | _, _ -> return false
+
+  let tests = [tztest "Code" `Quick (make_test Parser.Code.encoding gen check)]
+end
+
+module Elem = struct
+  open Utils
+
+  let elem_gen =
+    let open QCheck2.Gen in
+    let open Ast_generators in
+    let* etype = ref_type_gen in
+    let* emode = segment_mode_gen in
+    let+ einit = Vec.gen const_gen in
+    Ast.{etype; emode; einit}
+
+  let gen =
+    let open QCheck2.Gen in
+    let open Ast_generators in
+    let start = return Decode.EKStart in
+    let mode =
+      let* left = small_nat in
+      let* index = int32 in
+      let* index_kind = oneofl [Decode.Indexed; Decode.Const] in
+      let* early_ref_type = opt ref_type_gen in
+      let* offset_kont = small_nat in
+      let+ offset_kont_code = Block.gen in
+      Decode.EKMode
+        {
+          left;
+          index = Source.(index @@ no_region);
+          index_kind;
+          early_ref_type;
+          offset_kont = (offset_kont, offset_kont_code);
+        }
+    in
+    let initindexed =
+      let* mode = segment_mode_gen in
+      let* ref_type = ref_type_gen in
+      let+ einit_vec = LazyVec.gen const_gen in
+      Decode.EKInitIndexed {mode; ref_type; einit_vec}
+    in
+    let initconst =
+      let* mode = segment_mode_gen in
+      let* ref_type = ref_type_gen in
+      let* einit_vec = LazyVec.gen const_gen in
+      let* pos = small_int in
+      let+ block = Block.gen in
+      Decode.EKInitConst {mode; ref_type; einit_vec; einit_kont = (pos, block)}
+    in
+    let stop =
+      let+ elem = elem_gen in
+      Decode.EKStop elem
+    in
+    oneof [start; mode; initindexed; initconst; stop]
+
+  let elem_check Ast.{emode; einit; etype}
+      Ast.{emode = emode'; einit = einit'; etype = etype'} =
+    let open Lwt_result_syntax in
+    let eq_const c c' = return (c = c') in
+    let* eq_init = Vec.check eq_const einit einit' in
+    return (emode = emode' && eq_init && etype = etype')
+
+  let check ek ek' =
+    let open Lwt_result_syntax in
+    match (ek, ek') with
+    | Decode.EKStart, Decode.EKStart -> return_true
+    | ( EKMode
+          {
+            left;
+            index;
+            index_kind;
+            early_ref_type;
+            offset_kont = offset_kont_pos, offset_kont_code;
+          },
+        EKMode
+          {
+            left = left';
+            index = index';
+            index_kind = index_kind';
+            early_ref_type = early_ref_type';
+            offset_kont = offset_kont_pos', offset_kont_code';
+          } ) ->
+        let+ eq_code = Block.check offset_kont_code offset_kont_code' in
+        left = left' && index = index' && index_kind = index_kind'
+        && early_ref_type = early_ref_type'
+        && offset_kont_pos = offset_kont_pos'
+        && eq_code
+    | ( EKInitIndexed {mode; ref_type; einit_vec},
+        EKInitIndexed
+          {mode = mode'; ref_type = ref_type'; einit_vec = einit_vec'} ) ->
+        let eq_const c c' = return (c = c') in
+        let+ eq_init = LazyVec.check eq_const einit_vec einit_vec' in
+        mode = mode' && ref_type = ref_type' && eq_init
+    | ( EKInitConst {mode; ref_type; einit_vec; einit_kont = pos, block},
+        EKInitConst
+          {
+            mode = mode';
+            ref_type = ref_type';
+            einit_vec = einit_vec';
+            einit_kont = pos', block';
+          } ) ->
+        let eq_const c c' = return (c = c') in
+        let* eq_init = LazyVec.check eq_const einit_vec einit_vec' in
+        let+ eq_block = Block.check block block' in
+        mode = mode' && ref_type = ref_type' && pos = pos' && eq_init
+        && eq_block
+    | EKStop elem, EKStop elem' -> elem_check elem elem'
+    | _, _ -> return_false
+
+  let tests = [tztest "Elem" `Quick (make_test Parser.Elem.encoding gen check)]
+end
+
+module Data = struct
+  open Utils
+
+  let data_gen =
+    let open QCheck2.Gen in
+    let* dmode = Ast_generators.segment_mode_gen in
+    let+ dinit = Ast_generators.data_label_gen in
+    Ast.{dmode; dinit}
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.DKStart in
+    let mode =
+      let* left = small_nat in
+      let* index = int32 in
+      let* offset_kont = small_nat in
+      let+ offset_kont_code = Block.gen in
+      Decode.DKMode
+        {
+          left;
+          index = Source.(index @@ no_region);
+          offset_kont = (offset_kont, offset_kont_code);
+        }
+    in
+    let init =
+      let* dmode = Ast_generators.segment_mode_gen in
+      let+ init_kont = Byte_vector.gen in
+      Decode.DKInit {dmode; init_kont}
+    in
+    let stop =
+      let+ data = data_gen in
+      Decode.DKStop data
+    in
+    oneof [start; mode; init; stop]
+
+  let data_check Ast.{dmode; dinit} Ast.{dmode = dmode'; dinit = dinit'} =
+    let open Lwt_result_syntax in
+    return (dmode = dmode' && dinit = dinit')
+
+  let check dk dk' =
+    let open Lwt_result_syntax in
+    match (dk, dk') with
+    | Decode.DKStart, Decode.DKStart -> return_true
+    | ( DKMode {left; index; offset_kont = offset_kont_pos, offset_kont_code},
+        DKMode
+          {
+            left = left';
+            index = index';
+            offset_kont = offset_kont_pos', offset_kont_code';
+          } ) ->
+        let+ eq_code = Block.check offset_kont_code offset_kont_code' in
+        left = left' && index = index'
+        && offset_kont_pos = offset_kont_pos'
+        && eq_code
+    | DKInit {dmode; init_kont}, DKInit {dmode = dmode'; init_kont = init_kont'}
+      ->
+        let+ eq_init = Byte_vector.check init_kont init_kont' in
+        dmode = dmode' && eq_init
+    | DKStop data, DKStop data' -> data_check data data'
+    | _, _ -> return false
+
+  let tests = [tztest "Data" `Quick (make_test Parser.Data.encoding gen check)]
+end
+
+module Field = struct
+  open Utils
+
+  let no_region gen = QCheck2.Gen.map (fun v -> Source.(v @@ no_region)) gen
+
+  let type_field_gen = Vec.gen (no_region Func_type.func_type_gen)
+
+  let import_field_gen = Vec.gen (no_region Imports.import_gen)
+
+  let func_field_gen = Vec.gen Ast_generators.var_gen
+
+  let table_field_gen =
+    let open QCheck2.Gen in
+    let table_gen =
+      let+ ttype = Ast_generators.table_type_gen in
+      Ast.{ttype}
+    in
+    Vec.gen (no_region table_gen)
+
+  let memory_field_gen =
+    let open QCheck2.Gen in
+    let memory_gen =
+      let+ mtype = Ast_generators.memory_type_gen in
+      Ast.{mtype}
+    in
+    Vec.gen (no_region memory_gen)
+
+  let global_field_gen =
+    let open QCheck2.Gen in
+    let global_gen =
+      let* ginit = no_region Ast_generators.block_label_gen in
+      let+ gtype = Ast_generators.global_type_gen in
+      Ast.{gtype; ginit}
+    in
+    Vec.gen (no_region global_gen)
+
+  let export_field_gen = Vec.gen (no_region Exports.export_gen)
+
+  let start_field_gen = QCheck2.Gen.opt Ast_generators.start_gen
+
+  let elem_field_gen = Vec.gen (no_region Elem.elem_gen)
+
+  let data_count_field_gen = QCheck2.Gen.(opt int32)
+
+  let code_field_gen = Vec.gen Code.func_gen
+
+  let data_field_gen = Vec.gen (no_region Data.data_gen)
+
+  let field_type_gen =
+    let open QCheck2.Gen in
+    let pack f = Parser.Field.FieldType f in
+    oneofl
+      [
+        pack Decode.TypeField;
+        pack ImportField;
+        pack FuncField;
+        pack TableField;
+        pack MemoryField;
+        pack GlobalField;
+        pack ExportField;
+        pack StartField;
+        pack ElemField;
+        pack DataCountField;
+        pack CodeField;
+        pack DataField;
+      ]
+
+  let typed_lazy_vec_gen =
+    let open QCheck2.Gen in
+    let pack f gen_vec =
+      let+ vec = LazyVec.gen_with_vec gen_vec in
+      Parser.Field.TypedLazyVec (f, vec)
+    in
+    oneof
+      [
+        pack Decode.TypeField type_field_gen;
+        pack ImportField import_field_gen;
+        pack FuncField func_field_gen;
+        pack TableField table_field_gen;
+        pack MemoryField memory_field_gen;
+        pack GlobalField global_field_gen;
+        pack ExportField export_field_gen;
+        pack ElemField elem_field_gen;
+        pack CodeField code_field_gen;
+        pack DataField data_field_gen;
+      ]
+
+  let check_field_type :
+      type a a' repr repr'.
+      (a, repr) Decode.field_type -> (a', repr') Decode.field_type -> bool =
+   fun ft ft' ->
+    match (ft, ft') with
+    | Decode.DataCountField, Decode.DataCountField -> true
+    | StartField, StartField -> true
+    | TypeField, TypeField -> true
+    | ImportField, ImportField -> true
+    | FuncField, FuncField -> true
+    | TableField, TableField -> true
+    | MemoryField, MemoryField -> true
+    | GlobalField, GlobalField -> true
+    | ExportField, ExportField -> true
+    | ElemField, ElemField -> true
+    | CodeField, CodeField -> true
+    | DataField, DataField -> true
+    | _, _ -> false
+
+  let check_packed_field_type (Parser.Field.FieldType ft)
+      (Parser.Field.FieldType ft') =
+    Lwt.return_ok (check_field_type ft ft')
+
+  let check_field_type_value :
+      type a a' repr repr'.
+      (a, repr) Decode.field_type ->
+      (a', repr') Decode.field_type ->
+      a ->
+      a' ->
+      (bool, _) result Lwt.t =
+   fun ft ft' x y ->
+    let open Lwt_result_syntax in
+    match (ft, ft') with
+    | Decode.DataCountField, Decode.DataCountField -> return (x = y)
+    | StartField, StartField -> return (x = y)
+    | TypeField, TypeField -> Func_type.func_type_check x.Source.it y.Source.it
+    | ImportField, ImportField -> Imports.import_check x.Source.it y.Source.it
+    | FuncField, FuncField -> return (x = y)
+    | TableField, TableField -> return (x = y)
+    | MemoryField, MemoryField -> return (x = y)
+    | GlobalField, GlobalField -> return (x = y)
+    | ExportField, ExportField -> Exports.export_check x.Source.it y.Source.it
+    | ElemField, ElemField -> Elem.elem_check x.Source.it y.Source.it
+    | CodeField, CodeField -> Code.check_func x.Source.it y.Source.it
+    | DataField, DataField -> Data.data_check x.Source.it y.Source.it
+    | _, _ -> return_false
+
+  let building_state_gen =
+    let open QCheck2.Gen in
+    let* types = type_field_gen in
+    let* imports = import_field_gen in
+    let* vars = func_field_gen in
+    let* tables = table_field_gen in
+    let* memories = memory_field_gen in
+    let* globals = global_field_gen in
+    let* exports = export_field_gen in
+    let* start = start_field_gen in
+    let* elems = elem_field_gen in
+    let* data_count = data_count_field_gen in
+    let* code = code_field_gen in
+    let+ datas = data_field_gen in
+    Decode.
+      {
+        types;
+        imports;
+        vars;
+        tables;
+        memories;
+        globals;
+        exports;
+        start;
+        elems;
+        data_count;
+        code;
+        datas;
+      }
+
+  let building_state_check
+      Decode.
+        {
+          types;
+          imports;
+          vars;
+          tables;
+          memories;
+          globals;
+          exports;
+          start;
+          elems;
+          data_count;
+          code;
+          datas;
+        }
+      Decode.
+        {
+          types = types';
+          imports = imports';
+          vars = vars';
+          tables = tables';
+          memories = memories';
+          globals = globals';
+          exports = exports';
+          start = start';
+          elems = elems';
+          data_count = data_count';
+          code = code';
+          datas = datas';
+        } =
+    let open Lwt_result_syntax in
+    let check_no_region check v v' = check v.Source.it v'.Source.it in
+    let eq v v' = return (v = v') in
+    let* eq_types =
+      Vec.check (check_no_region Func_type.func_type_check) types types'
+    in
+    let* eq_imports =
+      Vec.check (check_no_region Imports.import_check) imports imports'
+    in
+    let* eq_vars = Vec.check (check_no_region eq) vars vars' in
+    let* eq_tables = Vec.check (check_no_region eq) tables tables' in
+    let* eq_memories = Vec.check (check_no_region eq) memories memories' in
+    let* eq_globals = Vec.check (check_no_region eq) globals globals' in
+    let* eq_exports =
+      Vec.check (check_no_region Exports.export_check) exports exports'
+    in
+    let* eq_start = return (start = start') in
+    let* eq_elems = Vec.check (check_no_region Elem.elem_check) elems elems' in
+    let* eq_data_count = return (data_count = data_count') in
+    let* eq_code = Vec.check (check_no_region Code.check_func) code code' in
+    let+ eq_datas = Vec.check (check_no_region Data.data_check) datas datas' in
+    eq_types && eq_imports && eq_vars && eq_tables && eq_memories && eq_globals
+    && eq_exports && eq_start && eq_elems && eq_data_count && eq_code
+    && eq_datas
+
+  let tests =
+    [
+      tztest
+        "Field"
+        `Quick
+        (make_test
+           Parser.Field.building_state_encoding
+           building_state_gen
+           building_state_check);
+      tztest
+        "Field.Packed"
+        `Quick
+        (make_test
+           Parser.Field.packed_field_type_encoding
+           field_type_gen
+           check_packed_field_type);
+    ]
+end
+
+module Module = struct
+  open Utils
+
+  (* Different version from Ast_generators.allocations_gen: the vector
+     is never created lazily. *)
+  let allocations_gen =
+    let open QCheck2.Gen in
+    let* blocks = Vec.gen (Vec.gen Ast_generators.instr_gen) in
+    let+ datas = Vec.gen Byte_vector.gen_chunked_byte_vector in
+    Ast.{blocks; datas}
+
+  let module_gen =
+    let open QCheck2.Gen in
+    let open Field in
+    let* types = type_field_gen in
+    let* globals = global_field_gen in
+    let* tables = table_field_gen in
+    let* memories = memory_field_gen in
+    let* funcs = code_field_gen in
+    let* start = start_field_gen in
+    let* elems = elem_field_gen in
+    let* datas = data_field_gen in
+    let* imports = import_field_gen in
+    let* exports = export_field_gen in
+    let+ allocations = allocations_gen in
+    Ast.
+      {
+        types;
+        globals;
+        tables;
+        memories;
+        funcs;
+        start;
+        elems;
+        datas;
+        imports;
+        exports;
+        allocations;
+      }
+
+  let gen =
+    let open QCheck2.Gen in
+    let start = return Decode.MKStart in
+    let skip_custom =
+      let+ packed_ft_opt = opt Field.field_type_gen in
+      match packed_ft_opt with
+      | Some (Parser.Field.FieldType ft) -> Decode.MKSkipCustom (Some ft)
+      | None -> MKSkipCustom None
+    in
+    let field_start =
+      let+ (Parser.Field.FieldType ft) = Field.field_type_gen in
+      Decode.MKFieldStart ft
+    in
+    let field =
+      let* size = Size.gen in
+      let+ (Parser.Field.TypedLazyVec (ft, vec)) = Field.typed_lazy_vec_gen in
+      Decode.MKField (ft, size, vec)
+    in
+    let elaborate_func =
+      let* func_types = Vec.gen Ast_generators.var_gen in
+      let* func_bodies = Field.code_field_gen in
+      let* func_kont = LazyVec.gen Code.func_gen in
+      let+ datas_in_func = bool in
+      Decode.MKElaborateFunc (func_types, func_bodies, func_kont, datas_in_func)
+    in
+    let build =
+      let* funcs = opt (Vec.gen Code.func_gen) in
+      let+ datas_in_func = bool in
+      Decode.MKBuild (funcs, datas_in_func)
+    in
+    let stop =
+      let+ modl = module_gen in
+      Decode.MKStop Source.(modl @@ no_region)
+    in
+    let types =
+      let* func_type_kont = Func_type.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.type_field_gen in
+      Decode.MKTypes (func_type_kont, pos, size, vec_kont)
+    in
+    let imports =
+      let* import_kont = Imports.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.import_field_gen in
+      Decode.MKImport (import_kont, pos, size, vec_kont)
+    in
+    let exports =
+      let* export_kont = Exports.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.export_field_gen in
+      Decode.MKExport (export_kont, pos, size, vec_kont)
+    in
+    let global =
+      let* global_type = Ast_generators.global_type_gen in
+      let* pos = small_nat in
+      let* block_kont = Block.gen in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.global_field_gen in
+      Decode.MKGlobal (global_type, pos, block_kont, size, vec_kont)
+    in
+    let elem =
+      let* elem_kont = Elem.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.elem_field_gen in
+      Decode.MKElem (elem_kont, pos, size, vec_kont)
+    in
+    let data =
+      let* data_kont = Data.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.data_field_gen in
+      Decode.MKData (data_kont, pos, size, vec_kont)
+    in
+    let code =
+      let* code_kont = Code.gen in
+      let* pos = small_nat in
+      let* size = Size.gen in
+      let+ vec_kont = LazyVec.gen_with_vec Field.code_field_gen in
+      Decode.MKCode (code_kont, pos, size, vec_kont)
+    in
+    oneof
+      [
+        start;
+        skip_custom;
+        field_start;
+        field;
+        elaborate_func;
+        build;
+        stop;
+        types;
+        imports;
+        exports;
+        global;
+        elem;
+        data;
+        code;
+      ]
+
+  let check_allocations allocations allocations' =
+    let open Lwt_result_syntax in
+    let eq_instr i i' = return (i = i') in
+    let* eq_blocks =
+      Vec.check
+        (Vec.check eq_instr)
+        allocations.Ast.blocks
+        allocations'.Ast.blocks
+    in
+    let+ eq_datas =
+      Vec.check Byte_vector.check_vector allocations.datas allocations'.datas
+    in
+    eq_blocks && eq_datas
+
+  let check_module
+      Source.
+        {
+          it =
+            Ast.
+              {
+                types;
+                globals;
+                tables;
+                memories;
+                funcs;
+                start;
+                elems;
+                datas;
+                imports;
+                exports;
+                allocations;
+              };
+          _;
+        }
+      Source.
+        {
+          it =
+            Ast.
+              {
+                types = types';
+                globals = globals';
+                tables = tables';
+                memories = memories';
+                funcs = funcs';
+                start = start';
+                elems = elems';
+                datas = datas';
+                imports = imports';
+                exports = exports';
+                allocations = allocations';
+              };
+          _;
+        } =
+    let open Lwt_result_syntax in
+    let check_no_region check v v' = check v.Source.it v'.Source.it in
+    let eq v v' = return (v = v') in
+    let* eq_types =
+      Vec.check (check_no_region Func_type.func_type_check) types types'
+    in
+    let* eq_globals = Vec.check (check_no_region eq) globals globals' in
+    let* eq_tables = Vec.check (check_no_region eq) tables tables' in
+    let* eq_memories = Vec.check (check_no_region eq) memories memories' in
+    let* eq_funcs = Vec.check (check_no_region Code.check_func) funcs funcs' in
+    let* eq_start = return (start = start') in
+    let* eq_elems = Vec.check (check_no_region Elem.elem_check) elems elems' in
+    let* eq_datas = Vec.check (check_no_region Data.data_check) datas datas' in
+    let* eq_imports =
+      Vec.check (check_no_region Imports.import_check) imports imports'
+    in
+    let* eq_exports =
+      Vec.check (check_no_region Exports.export_check) exports exports'
+    in
+    let+ eq_allocations = check_allocations allocations allocations' in
+    eq_types && eq_globals && eq_funcs && eq_tables && eq_memories && eq_start
+    && eq_elems && eq_datas && eq_imports && eq_exports && eq_allocations
+
+  let check_without_region check x y = check x.Source.it y.Source.it
+
+  let check mk mk' =
+    let open Lwt_result_syntax in
+    match (mk, mk') with
+    | Decode.MKStart, Decode.MKStart -> return_true
+    | MKSkipCustom None, MKSkipCustom None -> return_true
+    | MKSkipCustom (Some ft), MKSkipCustom (Some ft') ->
+        return @@ Field.check_field_type ft ft'
+    | MKFieldStart ft, MKFieldStart ft' ->
+        return @@ Field.check_field_type ft ft'
+    | MKField (ft, size, kont), MKField (ft', size', kont') ->
+        let* eq_kont =
+          LazyVec.check_possibly_different
+            (Field.check_field_type_value ft ft')
+            kont
+            kont'
+        in
+        let+ eq_size = Size.check size size' in
+        eq_kont && eq_size && Field.check_field_type ft ft'
+    | ( MKElaborateFunc (fts, fbs, kont, datas),
+        MKElaborateFunc (fts', fbs', kont', datas') ) ->
+        let eq_vars v v' = return (v = v') in
+        let* eq_fts = Vec.check eq_vars fts fts' in
+        let* eq_fbs =
+          Vec.check (check_without_region Code.check_func) fbs fbs'
+        in
+        let+ eq_kont =
+          LazyVec.check (check_without_region Code.check_func) kont kont'
+        in
+        eq_fts && eq_fbs && eq_kont && datas = datas'
+    | MKBuild (Some funcs, datas), MKBuild (Some funcs', datas') ->
+        let+ eq_funcs =
+          Vec.check (check_without_region Code.check_func) funcs funcs'
+        in
+        eq_funcs && datas = datas'
+    | MKBuild (None, datas), MKBuild (None, datas') -> return (datas = datas')
+    | MKStop m, MKStop m' -> check_module m m'
+    | ( MKTypes (func_type_kont, pos, size, vec_kont),
+        MKTypes (func_type_kont', pos', size', vec_kont') ) ->
+        let* eq_func_type_kont =
+          Func_type.check func_type_kont func_type_kont'
+        in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check
+            (check_without_region Func_type.func_type_check)
+            vec_kont
+            vec_kont'
+        in
+        eq_func_type_kont && eq_size && eq_vec_kont && pos = pos'
+    | ( MKImport (import_kont, pos, size, vec_kont),
+        MKImport (import_kont', pos', size', vec_kont') ) ->
+        let* eq_import_kont = Imports.check import_kont import_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check
+            (check_without_region Imports.import_check)
+            vec_kont
+            vec_kont'
+        in
+        eq_import_kont && eq_size && eq_vec_kont && pos = pos'
+    | ( MKExport (export_kont, pos, size, vec_kont),
+        MKExport (export_kont', pos', size', vec_kont') ) ->
+        let* eq_export_kont = Exports.check export_kont export_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check
+            (check_without_region Exports.export_check)
+            vec_kont
+            vec_kont'
+        in
+        eq_export_kont && eq_size && eq_vec_kont && pos = pos'
+    | ( MKGlobal (global_type, pos, block_kont, size, vec_kont),
+        MKGlobal (global_type', pos', block_kont', size', vec_kont') ) ->
+        let* eq_block_kont = Block.check block_kont block_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check (fun g g' -> return (g = g')) vec_kont vec_kont'
+        in
+        eq_block_kont && eq_size && eq_vec_kont && pos = pos'
+        && global_type = global_type'
+    | ( MKElem (elem_kont, pos, size, vec_kont),
+        MKElem (elem_kont', pos', size', vec_kont') ) ->
+        let* eq_elem_kont = Elem.check elem_kont elem_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check
+            (check_without_region Elem.elem_check)
+            vec_kont
+            vec_kont'
+        in
+        eq_elem_kont && eq_size && eq_vec_kont && pos = pos'
+    | ( MKData (data_kont, pos, size, vec_kont),
+        MKData (data_kont', pos', size', vec_kont') ) ->
+        let* eq_data_kont = Data.check data_kont data_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check (fun d d' -> return (d = d')) vec_kont vec_kont'
+        in
+        eq_data_kont && eq_size && eq_vec_kont && pos = pos'
+    | ( MKCode (code_kont, pos, size, vec_kont),
+        MKCode (code_kont', pos', size', vec_kont') ) ->
+        let* eq_code_kont = Code.check code_kont code_kont' in
+        let* eq_size = Size.check size size' in
+        let+ eq_vec_kont =
+          LazyVec.check
+            (check_without_region Code.check_func)
+            vec_kont
+            vec_kont'
+        in
+        eq_code_kont && eq_size && eq_vec_kont && pos = pos'
+    | _, _ -> return_false
+
+  let tests =
+    [tztest "Module" `Quick (make_test Parser.Module.encoding gen check)]
+end
+
+let tests =
+  Byte_vector.tests @ Vec.tests @ LazyVec.tests @ Names.tests @ Func_type.tests
+  @ Imports.tests @ LazyStack.tests @ Exports.tests @ Instr_block.tests
+  @ Block.tests @ Size.tests @ Code.tests @ Elem.tests @ Data.tests
+  @ Field.tests @ Module.tests
diff --git a/src/lib_scoru_wasm/test/test_parser_encoding.mli b/src/lib_scoru_wasm/test/test_parser_encoding.mli
new file mode 100644
index 0000000000000000000000000000000000000000..d57a8ef1a4230218e645669ffae1302cd64ccf1b
--- /dev/null
+++ b/src/lib_scoru_wasm/test/test_parser_encoding.mli
@@ -0,0 +1,26 @@
+(*****************************************************************************)
+(*                                                                           *)
+(* Open Source License                                                       *)
+(* Copyright (c) 2022 Nomadic Labs <contact@nomadic-labs.com>                *)
+(*                                                                           *)
+(* Permission is hereby granted, free of charge, to any person obtaining a   *)
+(* copy of this software and associated documentation files (the "Software"),*)
+(* to deal in the Software without restriction, including without limitation *)
+(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
+(* and/or sell copies of the Software, and to permit persons to whom the     *)
+(* Software is furnished to do so, subject to the following conditions:      *)
+(*                                                                           *)
+(* The above copyright notice and this permission notice shall be included   *)
+(* in all copies or substantial portions of the Software.                    *)
+(*                                                                           *)
+(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
+(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
+(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
+(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
+(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
+(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
+(* DEALINGS IN THE SOFTWARE.                                                 *)
+(*                                                                           *)
+(*****************************************************************************)
+
+val tests : unit Alcotest_lwt.test_case list
diff --git a/src/lib_scoru_wasm/test/test_scoru_wasm.ml b/src/lib_scoru_wasm/test/test_scoru_wasm.ml
index a480daedef663ac2723f8e18d87a83bb5edaa643..f4697d6eb4f82b7c6eb6ccb0010470b70a98a24d 100644
--- a/src/lib_scoru_wasm/test/test_scoru_wasm.ml
+++ b/src/lib_scoru_wasm/test/test_scoru_wasm.ml
@@ -37,5 +37,6 @@ let () =
       ("Input", Test_input.tests);
       ("AST Generators", Test_ast_generators.tests);
       ("WASM Encodings", Test_wasm_encoding.tests);
+      ("Parser Encodings", Test_parser_encoding.tests);
     ]
   |> Lwt_main.run
diff --git a/src/lib_scoru_wasm/test/test_wasm_encoding.ml b/src/lib_scoru_wasm/test/test_wasm_encoding.ml
index 003459980d01e19288115c38465b08cb48fcb4f8..98b7acc55c37fc3a1cfb8a6ce4d608cabe5b2b32 100644
--- a/src/lib_scoru_wasm/test/test_wasm_encoding.ml
+++ b/src/lib_scoru_wasm/test/test_wasm_encoding.ml
@@ -27,7 +27,7 @@
     -------
     Component:    Tree_encoding
     Invocation:   dune exec  src/lib_scoru_wasm/test/test_scoru_wasm.exe \
-                    -- test "WASM Encodings"
+                    -- test "^WASM Encodings$"
     Subject:      Encoding tests for the tezos-scoru-wasm library
 *)
 
diff --git a/src/lib_scoru_wasm/wasm_encoding.mli b/src/lib_scoru_wasm/wasm_encoding.mli
index 9155161f6f40abca1b3ac3632329b67995d3dfd7..603b522c59194a7a2cd0ad663185e02ef575417c 100644
--- a/src/lib_scoru_wasm/wasm_encoding.mli
+++ b/src/lib_scoru_wasm/wasm_encoding.mli
@@ -60,6 +60,8 @@ module Make (M : Tree_encoding.S) : sig
 
   val function_vector_encoding : Instance.func_inst Instance.Vector.t t
 
+  val func_type_encoding : Types.func_type t
+
   val function_type_vector_encoding : Types.func_type Instance.Vector.t t
 
   val value_ref_vector_encoding : Values.ref_ Instance.Vector.t t
diff --git a/src/lib_scoru_wasm/wasm_pvm.ml b/src/lib_scoru_wasm/wasm_pvm.ml
index ebf0c4195e986b835d1206ed51eedee44e4a7412..08049ca21185ab1396b944448ffe438425f188ee 100644
--- a/src/lib_scoru_wasm/wasm_pvm.ml
+++ b/src/lib_scoru_wasm/wasm_pvm.ml
@@ -23,9 +23,19 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* The name by which the module is registered. This can be anything as long
+   as we use the same name to lookup from the registry. *)
+let wasm_main_module_name = "main"
+
+(* This is the name of the main function of the module. We require the
+   kernel to expose a function named [kernel_next]. *)
+let wasm_entrypoint = "kernel_next"
+
 module Wasm = Tezos_webassembly_interpreter
 
-type tick_state = Decode | Eval of Wasm.Eval.config
+type tick_state =
+  | Decode of Tezos_webassembly_interpreter.Decode.decode_kont
+  | Eval of Wasm.Eval.config
 
 type pvm_state = {
   kernel : Lazy_containers.Chunked_byte_vector.Lwt.t;
@@ -41,7 +51,16 @@ module Make (T : Tree_encoding.TREE) :
     type tree = T.tree
 
     module Tree_encoding = Tree_encoding.Make (T)
+
+    (* TODO: https://gitlab.com/tezos/tezos/-/issues/3568
+       The [Wasm_encoding] functor is already used in
+       [Binary_parser_encodings].
+       Ideally, we would make [Binary_parser_encodings.Make] reexpose
+       the [Wasm_encoding] module it computes. However, since we have
+       a short-term solution to remove the functor layer of
+       [Tree_encoding], we leave the code as-is. *)
     module Wasm_encoding = Wasm_encoding.Make (Tree_encoding)
+    module Parsing = Binary_parser_encodings.Make (Tree_encoding)
 
     let host_funcs =
       let registry = Wasm.Host_funcs.empty () in
@@ -51,14 +70,17 @@ module Make (T : Tree_encoding.TREE) :
     let tick_state_encoding =
       let open Tree_encoding in
       tagged_union
-        ~default:Decode
+        ~default:
+          (Decode
+             (Tezos_webassembly_interpreter.Decode.initial_decode_kont
+                ~name:wasm_main_module_name))
         (value [] Data_encoding.string)
         [
           case
             "decode"
-            (value [] Data_encoding.unit)
-            (function Decode -> Some () | _ -> None)
-            (fun () -> Decode);
+            Parsing.Decode.encoding
+            (function Decode m -> Some m | _ -> None)
+            (fun m -> Decode m);
           case
             "eval"
             (Wasm_encoding.config_encoding ~host_funcs)
@@ -84,21 +106,10 @@ module Make (T : Tree_encoding.TREE) :
     let status_encoding =
       Tree_encoding.value ["input"; "consuming"] Data_encoding.bool
 
-    (* The name by which the module is registered. This can be anything as long
-       as we use the same name to lookup from the registry. *)
-    let wasm_main_module_name = "main"
-
-    (* This is the name of the main function of the module. We require the
-       kernel to expose a function named [kernel_next]. *)
-    let wasm_entrypoint = "kernel_next"
-
     let next_state state =
       let open Lwt_syntax in
       match state.tick with
-      | Decode ->
-          let* ast_module =
-            Wasm.Decode.decode ~name:wasm_main_module_name ~bytes:state.kernel
-          in
+      | Decode {module_kont = MKStop ast_module; _} ->
           let self = Wasm.Instance.Module_key wasm_main_module_name in
           (* The module instance is registered in [self] that contains the
              module registry, why we can ignore the result here. *)
@@ -112,6 +123,11 @@ module Make (T : Tree_encoding.TREE) :
           in
           let eval_config = Wasm.Eval.config host_funcs self [] [] in
           Lwt.return {state with tick = Eval eval_config}
+      | Decode m ->
+          let+ m =
+            Tezos_webassembly_interpreter.Decode.module_step state.kernel m
+          in
+          {state with tick = Decode m}
       | Eval ({Wasm.Eval.frame; code; _} as eval_config) -> (
           match code with
           | _values, [] ->
diff --git a/src/lib_tree_encoding/test/test_encoding.ml b/src/lib_tree_encoding/test/test_encoding.ml
index b74490907ccba3091fea458f3f7e10e61bc53bb4..2878a7d5bdc4391312669371ef927b641617d56c 100644
--- a/src/lib_tree_encoding/test/test_encoding.ml
+++ b/src/lib_tree_encoding/test/test_encoding.ml
@@ -410,6 +410,35 @@ let test_return () =
   assert (v = "K") ;
   return_unit
 
+let test_swap_maps () =
+  let open Tree_encoding in
+  let open Lwt_result_syntax in
+  let int_map_enc = lazy_map (value [] Data_encoding.int31) in
+  let enc = tup2 ~flatten:false int_map_enc int_map_enc in
+  let*! tree = empty_tree () in
+  let assert_value_at_index ~key vec expected =
+    let*! value = Map.get key vec in
+    assert (value = expected) ;
+    return_unit
+  in
+  (* Create a pair of maps. *)
+  let map1 = Map.(create () |> set "foo" 1) in
+  let map2 = Map.(create () |> set "bar" 2) in
+  let pair = (map1, map2) in
+  (* Encode the lazy maps to the tree. *)
+  let*! tree = encode enc pair tree in
+  (* Decode the maps. *)
+  let*! pair = decode enc tree in
+  (* Encode a new pair where the elements have been swapped. *)
+  let swapped_pair = (snd pair, fst pair) in
+  let*! tree = encode enc swapped_pair tree in
+  (* Decode the swapped version. *)
+  let*! swapped_pair = decode enc tree in
+  (* Check that it's possible to access the elements of both maps. *)
+  let* () = assert_value_at_index ~key:"foo" (snd swapped_pair) 1 in
+  let* () = assert_value_at_index ~key:"bar" (fst swapped_pair) 2 in
+  return_unit
+
 let test_swap_vectors () =
   let open Tree_encoding in
   let open Lwt_result_syntax in
@@ -471,5 +500,6 @@ let tests =
     tztest "Value-option" `Quick test_value_option;
     tztest "Delayed" `Quick test_delayed;
     tztest "Return" `Quick test_return;
+    tztest "Swap maps" `Quick test_swap_maps;
     tztest "Swap vectors" `Quick test_swap_vectors;
   ]
diff --git a/src/lib_tree_encoding/tree_encoding.ml b/src/lib_tree_encoding/tree_encoding.ml
index 52f8ad619489141c384451c2cd5de67603956fa3..608990c78f695ba9a442271a41db4e8e5c0d3e02 100644
--- a/src/lib_tree_encoding/tree_encoding.ml
+++ b/src/lib_tree_encoding/tree_encoding.ml
@@ -349,8 +349,12 @@ module Make (T : Tree.S) : S with type tree = T.tree = struct
         in
         let decode =
           D.map
-            (fun produce_value -> Map.create ~produce_value ())
-            (D.lazy_mapping to_key value.decode)
+            (fun (origin, produce_value) ->
+              Map.create ?origin ~produce_value ())
+            (let open D.Syntax in
+            let+ origin = D.subtree
+            and+ produce_value = D.lazy_mapping to_key value.decode in
+            (origin, produce_value))
         in
         {encode; decode}
     end
diff --git a/src/lib_webassembly/binary/decode.ml b/src/lib_webassembly/binary/decode.ml
index c9a6f60d73903491282bd63f16e77235fcc4426a..4a081f2eafb42c91a6fc45eada0f65f003b92930 100644
--- a/src/lib_webassembly/binary/decode.ml
+++ b/src/lib_webassembly/binary/decode.ml
@@ -1931,7 +1931,7 @@ type module_kont =
   | MKBuild of func Vector.t option * bool
       (** Accumulating the parsed sections vectors into a module and checking
       invariants. *)
-  | MKStop of module_'  (** Final step of the parsing, cannot reduce. *)
+  | MKStop of module_  (** Final step of the parsing, cannot reduce. *)
     (* TODO (https://gitlab.com/tezos/tezos/-/issues/3120): actually, should be module_ *)
   | MKTypes of func_type_kont * pos * size * type_ lazy_vec_kont
       (** Function types section parsing. *)
@@ -2294,50 +2294,47 @@ let module_step bytes state =
         s
         (len s)
         "data count section required" ;
-      {
-        state with
-        module_kont =
-          MKStop
-            {
-              types;
-              tables;
-              memories;
-              globals;
-              funcs;
-              imports;
-              exports;
-              elems;
-              datas;
-              start;
-              allocations = state.allocation_state;
-            };
-      }
-      |> Lwt.return
+      let m =
+        Source.(
+          {
+            types;
+            tables;
+            memories;
+            globals;
+            funcs;
+            imports;
+            exports;
+            elems;
+            datas;
+            start;
+            allocations = state.allocation_state;
+          }
+          @@ region_ state.stream_name 0 state.stream_pos)
+      in
+      {state with module_kont = MKStop m} |> Lwt.return
   | MKStop _ (* Stop cannot reduce. *) -> assert false
 
+let initial_decode_kont ~name =
+  let allocation_state = Ast.empty_allocations () in
+  {
+    building_state = empty_building_state;
+    module_kont = MKStart;
+    allocation_state;
+    stream_pos = 0;
+    stream_name = name;
+  }
+
 let module_ name bytes =
   let open Lwt.Syntax in
   let rec loop = function
-    | {module_kont = MKStop m; stream_pos; _} -> Lwt.return (m, stream_pos)
+    | {module_kont = MKStop m; stream_pos; _} -> Lwt.return m
     | k ->
         let* next_state = module_step bytes k in
         loop next_state
   in
-  let allocation_state = Ast.empty_allocations () in
-  loop
-    {
-      building_state = empty_building_state;
-      module_kont = MKStart;
-      allocation_state;
-      stream_pos = 0;
-      stream_name = name;
-    }
+  loop @@ initial_decode_kont ~name
 
-let decode ~name ~bytes =
-  let open Lwt.Syntax in
-  let left = 0 in
-  let+ m, right = module_ name bytes in
-  Source.(m @@ region_ name left right)
+let decode ~name ~bytes = module_ name bytes
 
 let all_custom tag s =
   let open Lwt.Syntax in
diff --git a/src/lib_webassembly/binary/decode.mli b/src/lib_webassembly/binary/decode.mli
index 1dbb6ce9e44f2f9398bd48808b82156516cc7bba..73212cfa8a79c818961e4d3708c61201d7d2afec 100644
--- a/src/lib_webassembly/binary/decode.mli
+++ b/src/lib_webassembly/binary/decode.mli
@@ -54,7 +54,7 @@ type block_kont =
 type 'a lazy_vec_kont = LazyVec of {offset : int32; vector : 'a Vector.t}
 
 (** Position of a value on the stream. *)
-type pos = private int
+type pos = int
 
 (** Size checking version of {!sized} for CPS-style parsing. *)
 type size = {size : int; start : pos}
@@ -213,8 +213,7 @@ type module_kont =
   | MKBuild of Ast.func Vector.t option * bool
       (** Accumulating the parsed sections vectors into a module and checking
       invariants. *)
-  | MKStop of Ast.module_' (* TODO (#3120): actually, should be module_ *)
-      (** Final step of the parsing, cannot reduce. *)
+  | MKStop of Ast.module_  (** Final step of the parsing, cannot reduce. *)
   | MKTypes of func_type_kont * pos * size * Ast.type_ lazy_vec_kont
       (** Function types section parsing. *)
   | MKImport of import_kont * pos * size * Ast.import lazy_vec_kont
@@ -275,6 +274,11 @@ type decode_kont = {
 (** [make_stream filename bytes] returns a new stream to decode. *)
 val make_stream : name:string -> bytes:Chunked_byte_vector.Lwt.t -> stream
 
+(** [initial_decode_kont ~name] returns the initial tick state to be
+    fed to [module_step], such that [name] is the name of the input
+    (generally the name of the file that contains said input). *)
+val initial_decode_kont : name:string -> decode_kont
+
 (** [module_step stream kont] takes one step of parsing from a
    continuation and returns a new continuation. Fails when the
    continuation of the module is [MKStop] since it cannot reduce. *)
diff --git a/src/lib_webassembly/runtime/partial_table.ml b/src/lib_webassembly/runtime/partial_table.ml
index 09370e27df70058e7406d68f46ed05fc28d59392..f21e6ebb13ac5c59594f9952471f6ae5ea279470 100644
--- a/src/lib_webassembly/runtime/partial_table.ml
+++ b/src/lib_webassembly/runtime/partial_table.ml
@@ -21,7 +21,10 @@ let valid_limits {min; max} =
   match max with None -> true | Some m -> I32.le_u min m
 
 let create size r =
-  try Vector.create ~produce_value:(fun _ -> Lwt.return r) size
+  try
+    let vec = Vector.create 0l in
+    Vector.grow size ~default:(fun _ -> r) vec ;
+    vec
   with Out_of_memory | Invalid_argument _ -> raise OutOfMemory
 
 let create_shallow size =
diff --git a/src/proto_alpha/lib_protocol/test/integration/test_sc_rollup_wasm.ml b/src/proto_alpha/lib_protocol/test/integration/test_sc_rollup_wasm.ml
index 0b2174edee14531a211bb081ec754724a84ab642..0200361d180c475139d404f0f1792bfaffae35a3 100644
--- a/src/proto_alpha/lib_protocol/test/integration/test_sc_rollup_wasm.ml
+++ b/src/proto_alpha/lib_protocol/test/integration/test_sc_rollup_wasm.ml
@@ -417,9 +417,10 @@ let should_boot_computation_kernel () =
   let*! s = Prover.install_boot_sector s boot_sector in
   (* installing the boot kernel *)
   let* s = checked_eval ~loc:__LOC__ context s in
-  (* make the first tick of the WASM PVM, to switch it to “waiting for
-     input” mode *)
-  let* s = checked_eval ~loc:__LOC__ context s in
+  (* Make the first ticks of the WASM PVM (parsing of origination
+     message, parsing and init of the kernel), to switch it to
+     “waiting for input” mode. *)
+  let* s = eval_until_set_input context s in
   (* Feeding it with one input *)
   let* s =
     checked_set_input ~loc:__LOC__ context (arbitrary_input 0 "test") s