diff --git a/src/lib_lazy_containers/lazy_vector.ml b/src/lib_lazy_containers/lazy_vector.ml index 47d31fc55140886006c20877cfcc9a8719c50d50..6bcff95a25c6aa62bf4e85ef8480c6b22dc3ed44 100644 --- a/src/lib_lazy_containers/lazy_vector.ml +++ b/src/lib_lazy_containers/lazy_vector.ml @@ -86,6 +86,8 @@ module type S = sig val grow : ?default:(unit -> 'a) -> key -> 'a t -> 'a t + val pop : 'a t -> ('a * 'a t) Lwt.t + val append : 'a -> 'a t -> 'a t * key val concat : 'a t -> 'a t -> 'a t Lwt.t @@ -182,6 +184,18 @@ module Make (Key : KeyS) : S with type key = Key.t = struct in (map, num_elements) + let pop map = + let open Lwt.Syntax in + if Key.(unsigned_compare zero map.num_elements < 0) then + let+ x = get Key.zero map in + ( x, + { + map with + first = Key.succ map.first; + num_elements = Key.pred map.num_elements; + } ) + else raise Bounds + let append elt map = append_opt (Some elt) map let rec grow ?default delta map = diff --git a/src/lib_lazy_containers/lazy_vector.mli b/src/lib_lazy_containers/lazy_vector.mli index 05e1a5c46ec66f49585456b670b0cf2e05a4551d..46cf1a1e3d0089d888942c04cfee3374c587954f 100644 --- a/src/lib_lazy_containers/lazy_vector.mli +++ b/src/lib_lazy_containers/lazy_vector.mli @@ -147,6 +147,11 @@ module type S = sig large. *) val grow : ?default:(unit -> 'a) -> key -> 'a t -> 'a t + (** [pop vector] removes the head from [vector], and returns it. + + @raise Bounds when applied on an empty vector. *) + val pop : 'a t -> ('a * 'a t) Lwt.t + (** [append elt vector] creates a new lazy vector that has one more item than [vector] whose value is [elt]. This is a shortcut for [vector |> grow Key.(succ zero) |> set (num_elements vector) elt]. diff --git a/src/lib_scoru_wasm/init_encodings.ml b/src/lib_scoru_wasm/init_encodings.ml index f1a5a2d5f69282604d993274cdecb4f77e93aac0..9ac907ca14ba4b9c5e65966b3611c4e47bf8e6a4 100644 --- a/src/lib_scoru_wasm/init_encodings.ml +++ b/src/lib_scoru_wasm/init_encodings.ml @@ -126,6 +126,48 @@ let aggregate_cases : (function m, t -> IK_Aggregate_concat (m, sec, t)); ] +let join_kont_encoding enc_b = + tagged_union + tag_encoding + [ + case + "J_Init" + (lazy_vec_encoding (lazy_vec_encoding enc_b)) + (function J_Init v -> Some v | _ -> None) + (fun v -> J_Init v); + case + "J_Next" + (tup2 + ~flatten:true + (scope ["kont"] (concat_kont_encoding (lazy_vec_encoding enc_b))) + (scope ["acc"] (lazy_vec_encoding (lazy_vec_encoding enc_b)))) + (function J_Next (kont, acc) -> Some (kont, acc) | _ -> None) + (function kont, acc -> J_Next (kont, acc)); + case + "J_Stop" + (lazy_vec_encoding enc_b) + (function J_Stop res -> Some res | _ -> None) + (fun res -> J_Stop res); + ] + +let map_concat_kont_encoding enc_a enc_b = + tagged_union + tag_encoding + [ + case + "MC_Map" + (map_kont_encoding + (lazy_vec_encoding enc_a) + (lazy_vec_encoding (lazy_vec_encoding enc_b))) + (function MC_Map m -> Some m | _ -> None) + (fun m -> MC_Map m); + case + "MC_Join" + (join_kont_encoding enc_b) + (function MC_Join j -> Some j | _ -> None) + (fun j -> MC_Join j); + ] + let init_kont_encoding = tagged_union tag_encoding @@ [ @@ -218,11 +260,28 @@ let init_kont_encoding = (lazy_vec_encoding Wasm_encoding.data_label_ref_encoding)))) (function IK_Datas (inst, map) -> Some (inst, map) | _ -> None) (function inst, map -> IK_Datas (inst, map)); + case + "IK_Es_elem" + (tup2 + ~flatten:true + (scope ["module"] Wasm_encoding.module_instance_encoding) + (scope + ["kont"] + (map_concat_kont_encoding + Parser.(no_region_encoding Elem.elem_encoding) + Wasm_encoding.admin_instr_encoding))) + (function IK_Es_elems (inst, map) -> Some (inst, map) | _ -> None) + (function inst, map -> IK_Es_elems (inst, map)); case "IK_Remaining" - Wasm_encoding.module_instance_encoding - (function IK_Remaining m -> Some m | _ -> None) - (function m -> IK_Remaining m); + (tup2 + ~flatten:true + (scope ["module"] Wasm_encoding.module_instance_encoding) + (scope + ["es_elem"] + (lazy_vec_encoding Wasm_encoding.admin_instr_encoding))) + (function IK_Remaining (m, admin) -> Some (m, admin) | _ -> None) + (function m, admin -> IK_Remaining (m, admin)); case "IK_Stop" Wasm_encoding.module_instance_encoding diff --git a/src/lib_webassembly/exec/eval.ml b/src/lib_webassembly/exec/eval.ml index 9ef1021e36ad5b5e4e8e68671814ed6dedbcff45..9ec30a7c5c10e744b1b2f488b9863d314a10a819 100644 --- a/src/lib_webassembly/exec/eval.ml +++ b/src/lib_webassembly/exec/eval.ml @@ -1057,6 +1057,12 @@ let map_step {origin; destination; offset} f = let destination = Vector.set offset (f x) destination in {origin; destination; offset = Int32.succ offset} +let map_i_step {origin; destination; offset} f = + let open Lwt.Syntax in + let+ x = Vector.get offset origin in + let destination = Vector.set offset (f offset x) destination in + {origin; destination; offset = Int32.succ offset} + let map_s_step {origin; destination; offset} f = let open Lwt.Syntax in let* x = Vector.get offset origin in @@ -1129,6 +1135,66 @@ let section_set_vec : | Table, tables -> {inst with tables} | Memory, memories -> {inst with memories} +type 'b join_kont = + | J_Init of 'b Vector.t Vector.t + | J_Next of 'b concat_kont * 'b Vector.t Vector.t + | J_Stop of 'b Vector.t + +let join_kont vec = J_Init vec + +let join_completed = function + | J_Init v when Vector.num_elements v = 0l -> Some (Vector.create 0l) + | J_Stop v -> Some v + | _ -> None + +let join_step = + let open Lwt.Syntax in + function + | J_Init v when 1l < Vector.num_elements v -> + let* x, v = Vector.pop v in + let+ y, v = Vector.pop v in + J_Next (concat_kont x y, v) + | J_Init v when Vector.num_elements v = 1l -> + let+ v = Vector.get 0l v in + J_Stop v + | J_Next (tick, acc) + when concat_completed tick && Vector.num_elements acc = 0l -> + Lwt.return (J_Stop tick.res) + | J_Next (tick, acc) when concat_completed tick -> + let+ x, acc = Vector.pop acc in + J_Next (concat_kont tick.res x, acc) + | J_Next (tick, acc) -> + let+ tick = concat_step tick in + J_Next (tick, acc) + | J_Init _ -> + (* [num_elements = 0l], so [join_completed] returns [Some], should not be called in this state *) + assert false + | J_Stop _ -> assert false + +type ('a, 'b) map_concat_kont = + | MC_Map of ('a, 'b Vector.t) map_kont + | MC_Join of 'b join_kont + +let map_concat_kont v = MC_Map (map_kont v) + +let map_concat_completed = function MC_Join v -> join_completed v | _ -> None + +let map_concat_step f = function + | MC_Map map when map_completed map -> + Lwt.return (MC_Join (join_kont map.destination)) + | MC_Map map -> + let+ map = f map in + MC_Map map + | MC_Join tick -> ( + match join_completed tick with + | Some _ -> + (* [map_concat_completed] would have returned [Some], so + illegal state to call this function *) + assert false + | None -> + let+ tick = join_step tick in + MC_Join tick) + type init_kont = | IK_Start | IK_Add_import of (extern, import, module_inst) fold_right2_kont @@ -1142,7 +1208,8 @@ type init_kont = | IK_Exports of module_inst * (export, extern NameMap.t) fold_left_kont | IK_Elems of module_inst * (elem_segment, elem_inst) map_kont | IK_Datas of module_inst * (data_segment, data_inst) map_kont - | IK_Remaining of module_inst + | IK_Es_elems of module_inst * (elem_segment, admin_instr) map_concat_kont + | IK_Remaining of module_inst * admin_instr Vector.t | IK_Stop of module_inst let section_next_init_kont : @@ -1236,20 +1303,32 @@ let init_step ~module_reg ~self host_funcs (m : module_) (exts : extern list) = | IK_Datas (inst0, tick) when map_completed tick -> let inst = {inst0 with datas = tick.destination} in update_module_ref module_reg self inst ; - Lwt.return (IK_Remaining inst) + Lwt.return (IK_Es_elems (inst, map_concat_kont m.it.elems)) | IK_Datas (inst0, tick) -> let+ tick = map_step tick create_data in IK_Datas (inst0, tick) - | IK_Remaining inst -> + | IK_Es_elems (inst0, tick) -> ( + match map_concat_completed tick with + | Some es_elem -> Lwt.return (IK_Remaining (inst0, es_elem)) + | None -> + let+ tick = + map_concat_step + (fun tick -> + map_i_step tick (fun i x -> run_elem i x |> Vector.of_list)) + tick + in + IK_Es_elems (inst0, tick)) + | IK_Remaining (inst, es_elem) -> (* TODO: https://gitlab.com/tezos/tezos/-/issues/3076 These transformations should be refactored and abadoned during the tickification, to avoid the roundtrip vector -> list -> vector. *) + let* es_elem = Vector.to_list es_elem in + let* datas = Vector.to_list m.it.datas in - let* elems = Vector.to_list m.it.elems in - let es_elem = List.concat (Lib.List32.mapi run_elem elems) in let* datas = Lib.List32.mapi_s (run_data inst) datas in let es_data = TzStdLib.List.concat datas in let es_start = Lib.Option.get (Lib.Option.map run_start m.it.start) [] in + let+ (_ : Values.value stack) = eval module_reg diff --git a/src/lib_webassembly/exec/eval.mli b/src/lib_webassembly/exec/eval.mli index 07b86f2c0bd376016c9578225cc88a3700698b47..04f4a0a1f83d0faaaadb60d41d4b9e3e537b51c2 100644 --- a/src/lib_webassembly/exec/eval.mli +++ b/src/lib_webassembly/exec/eval.mli @@ -9,6 +9,23 @@ exception Crash of Source.region * string exception Exhaustion of Source.region * string +type frame = {inst : module_key; locals : value ref list} + +type code = value list * admin_instr list + +and admin_instr = admin_instr' Source.phrase + +and admin_instr' = + | From_block of Ast.block_label * int32 + | Plain of Ast.instr' + | Refer of ref_ + | Invoke of func_inst + | Trapping of string + | Returning of value list + | Breaking of int32 * value list + | Label of int32 * Ast.instr list * code + | Frame of int32 * frame * code + type ('a, 'b, 'acc) fold_right2_kont = { acc : 'acc; lv : 'a Vector.t; @@ -37,6 +54,15 @@ type (_, _) init_section = | Table : (Ast.table, table_inst) init_section | Memory : (Ast.memory, memory_inst) init_section +type 'b join_kont = + | J_Init of 'b Vector.t Vector.t + | J_Next of 'b concat_kont * 'b Vector.t Vector.t + | J_Stop of 'b Vector.t + +type ('a, 'b) map_concat_kont = + | MC_Map of ('a, 'b Vector.t) map_kont + | MC_Join of 'b join_kont + type init_kont = | IK_Start (** Very first tick of the [init] function *) | IK_Add_import of (extern, Ast.import, module_inst) fold_right2_kont @@ -50,7 +76,8 @@ type init_kont = | IK_Exports of module_inst * (Ast.export, extern NameMap.t) fold_left_kont | IK_Elems of module_inst * (Ast.elem_segment, elem_inst) map_kont | IK_Datas of module_inst * (Ast.data_segment, data_inst) map_kont - | IK_Remaining of module_inst + | IK_Es_elems of module_inst * (Ast.elem_segment, admin_instr) map_concat_kont + | IK_Remaining of module_inst * admin_instr Vector.t | IK_Stop of module_inst (** Witness that there is no more tick to execute to complete the [init] process. *) @@ -85,23 +112,6 @@ val invoke : value list -> value list Lwt.t (* raises Trap *) -type frame = {inst : module_key; locals : value ref list} - -type code = value list * admin_instr list - -and admin_instr = admin_instr' Source.phrase - -and admin_instr' = - | From_block of Ast.block_label * int32 - | Plain of Ast.instr' - | Refer of ref_ - | Invoke of func_inst - | Trapping of string - | Returning of value list - | Breaking of int32 * value list - | Label of int32 * Ast.instr list * code - | Frame of int32 * frame * code - type config = { frame : frame; input : input_inst;