From 439c4f64af3e618537d3acd2321269862e5efe8f Mon Sep 17 00:00:00 2001 From: Emma Turner Date: Tue, 6 Sep 2022 13:46:26 +0100 Subject: [PATCH] SCORU: Wasm PVM: implement store_has --- src/lib_scoru_wasm/durable.ml | 10 +- src/lib_scoru_wasm/durable.mli | 6 + src/lib_scoru_wasm/host_funcs.ml | 48 +++++ src/lib_scoru_wasm/host_funcs.mli | 12 ++ .../test/test_durable_storage.ml | 199 ++++++++++++++++++ src/lib_scoru_wasm/test/test_wasm_pvm.ml | 54 +++++ .../test/wasm_kernels/README.md | 12 ++ .../test/wasm_kernels/test-store-has.wasm | Bin 0 -> 18984 bytes src/lib_tree_encoding/tree.ml | 7 + src/lib_tree_encoding/tree.mli | 4 + src/lib_tree_encoding/tree_encoding.mli | 2 + 11 files changed, 352 insertions(+), 2 deletions(-) create mode 100755 src/lib_scoru_wasm/test/wasm_kernels/test-store-has.wasm diff --git a/src/lib_scoru_wasm/durable.ml b/src/lib_scoru_wasm/durable.ml index 66f39e44d15a..16cf02a5e511 100644 --- a/src/lib_scoru_wasm/durable.ml +++ b/src/lib_scoru_wasm/durable.ml @@ -49,10 +49,10 @@ type key = string list (* A key is bounded to 250 bytes, including the implicit '/durable' prefix. Additionally, values are implicitly appended with '_'. **) -let max_prefix_key_length = 250 - String.length "/durable" - String.length "/_" +let max_key_length = 250 - String.length "/durable" - String.length "/_" let key_of_string_exn s = - if String.length s > max_prefix_key_length then raise (Invalid_key s) ; + if String.length s > max_key_length then raise (Invalid_key s) ; let key = match String.split '/' s with | "" :: tl -> tl (* Must start with '/' *) @@ -96,3 +96,9 @@ let find_value_exn tree key = match opt with | None -> raise Not_found | Some subtree -> Runner.decode E.chunked_byte_vector subtree + +let count_subtrees tree key = + let open Lwt.Syntax in + let* opt = T.find_tree tree @@ to_value_key key in + let+ len = T.length tree key in + if Option.is_none opt then len else len - 1 diff --git a/src/lib_scoru_wasm/durable.mli b/src/lib_scoru_wasm/durable.mli index 8a8400b8bd8d..4aad6ca565d6 100644 --- a/src/lib_scoru_wasm/durable.mli +++ b/src/lib_scoru_wasm/durable.mli @@ -54,6 +54,9 @@ val to_storage : t -> Tezos_webassembly_interpreter.Durable_storage.t - a step only contains alphanumeric ascii, or dots ('.') *) type key +(** [max_key_length] is the maximum length of a key in bytes. *) +val max_key_length : int + (** raise @Invalid_key *) val key_of_string_exn : string -> key @@ -63,3 +66,6 @@ val find_value : t -> key -> Lazy_containers.Chunked_byte_vector.t option Lwt.t (** raise @Not_found *) val find_value_exn : t -> key -> Lazy_containers.Chunked_byte_vector.t Lwt.t + +(** [count_subtrees durable key] returns the number of subtrees under [key]. *) +val count_subtrees : t -> key -> int Lwt.t diff --git a/src/lib_scoru_wasm/host_funcs.ml b/src/lib_scoru_wasm/host_funcs.ml index 7416b6ff3142..375da506b874 100644 --- a/src/lib_scoru_wasm/host_funcs.ml +++ b/src/lib_scoru_wasm/host_funcs.ml @@ -28,6 +28,8 @@ open Instance exception Bad_input +exception Key_too_large of int + let retrieve_memory memories = match Vector.num_elements memories with | 1l -> Vector.get 0l memories @@ -203,6 +205,48 @@ let _alternate_write_debug = Lwt.return (durable, []) | _ -> raise Bad_input) +let store_has_name = "tezos_store_has" + +let store_has_type = + let input_types = + Types.[NumType I32Type; NumType I32Type] |> Vector.of_list + in + let output_types = Types.[NumType I32Type] |> Vector.of_list in + Types.FuncType (input_types, output_types) + +let store_has_unknown_key = 0 + +let store_has_value_only = 1 + +let store_has_subtrees_only = 2 + +let store_has_value_and_subtrees = 3 + +let store_has = + Host_funcs.Host_func + (fun _input_buffer _output_buffer durable memories inputs -> + let open Lwt.Syntax in + match inputs with + | [Values.(Num (I32 key_offset)); Values.(Num (I32 key_length))] -> + let key_length = Int32.to_int key_length in + if key_length > Durable.max_key_length then + raise (Key_too_large key_length) ; + let* memory = retrieve_memory memories in + let* key = Memory.load_bytes memory key_offset key_length in + let tree = Durable.of_storage_exn durable in + let key = Durable.key_of_string_exn key in + let* value_opt = Durable.find_value tree key in + let+ num_subtrees = Durable.count_subtrees tree key in + let r = + match (value_opt, num_subtrees) with + | None, 0 -> store_has_unknown_key + | Some _, 0 -> store_has_value_only + | None, _ -> store_has_subtrees_only + | _ -> store_has_value_and_subtrees + in + (durable, [Values.(Num (I32 (I32.of_int_s r)))]) + | _ -> raise Bad_input) + let lookup_opt name = match name with | "read_input" -> @@ -211,6 +255,7 @@ let lookup_opt name = Some (ExternFunc (HostFunc (write_output_type, write_output_name))) | "write_debug" -> Some (ExternFunc (HostFunc (write_debug_type, write_debug_name))) + | "store_has" -> Some (ExternFunc (HostFunc (store_has_type, store_has_name))) | _ -> None let lookup name = @@ -225,6 +270,7 @@ let register_host_funcs registry = (read_input_name, read_input); (write_output_name, write_output); (write_debug_name, write_debug); + (store_has_name, store_has); ] module Internal_for_tests = struct @@ -235,4 +281,6 @@ module Internal_for_tests = struct let aux_write_input_in_memory = aux_write_input_in_memory let read_input = Func.HostFunc (read_input_type, read_input_name) + + let store_has = Func.HostFunc (store_has_type, store_has_name) end diff --git a/src/lib_scoru_wasm/host_funcs.mli b/src/lib_scoru_wasm/host_funcs.mli index 123a27118de0..1b6fdee5f133 100644 --- a/src/lib_scoru_wasm/host_funcs.mli +++ b/src/lib_scoru_wasm/host_funcs.mli @@ -56,6 +56,9 @@ val register_host_funcs : exception Bad_input +(** A durable key was given by the kernel with a longer-than-allowed length. *) +exception Key_too_large of int + module Internal_for_tests : sig (** [aux_write_output ~input_buffer ~output_buffer ~module_inst ~src ~num_bytes] reads num_bytes from the memory of module_inst starting at @@ -92,4 +95,13 @@ module Internal_for_tests : sig int Lwt.t val read_input : Tezos_webassembly_interpreter.Instance.func_inst + + (** [store_has] returns whether a key corresponds to a value and/or subtrees. + Namely, it returns the following enum: + - [0]: There is no value at [key], nor subtrees under [key]. + - [1]: There is a value at [key], but no subtrees under [key]. + - [2]: There is no value at [key], but there are subtrees under [key]. + - [3]: There is a value at [key], and subtrees under [key]. + *) + val store_has : Tezos_webassembly_interpreter.Instance.func_inst end diff --git a/src/lib_scoru_wasm/test/test_durable_storage.ml b/src/lib_scoru_wasm/test/test_durable_storage.ml index 24e85b22eb4e..f9f898802ef5 100644 --- a/src/lib_scoru_wasm/test/test_durable_storage.ml +++ b/src/lib_scoru_wasm/test/test_durable_storage.ml @@ -33,6 +33,7 @@ open Tztest open Lazy_containers +open Tezos_webassembly_interpreter open Tezos_scoru_wasm include Test_encodings_util module Wasm = Wasm_pvm.Make (Tree) @@ -54,6 +55,40 @@ let wrap_as_durable_storage tree = Tezos_webassembly_interpreter.Durable_storage.of_tree @@ Tree_encoding.Wrapped.wrap tree +(* Test checking that if [key] is missing, [store_has key] returns [false] *) +let test_store_has_missing_key () = + let open Lwt.Syntax in + let* tree = empty_tree () in + let* durable = wrap_as_durable_storage tree in + let module_inst = Tezos_webassembly_interpreter.Instance.empty_module_inst in + let memory = Memory.alloc (MemoryType Types.{min = 20l; max = Some 3600l}) in + let src = 10l in + let key = "/test/path" in + let _ = Memory.store_bytes memory src key in + let memories = Lazy_vector.Int32Vector.cons memory module_inst.memories in + let module_inst = {module_inst with memories} in + let values = + Values.[Num (I32 src); Num (I32 (Int32.of_int @@ String.length key))] + in + let host_funcs_registry = Tezos_webassembly_interpreter.Host_funcs.empty () in + Host_funcs.register_host_funcs host_funcs_registry ; + + let module_reg = Instance.ModuleMap.create () in + let module_key = Instance.Module_key "test" in + Instance.update_module_ref module_reg module_key module_inst ; + + let* _, result = + Eval.invoke + ~module_reg + ~caller:module_key + ~durable + host_funcs_registry + Host_funcs.Internal_for_tests.store_has + values + in + assert (result = Values.[Num (I32 (I32.of_int_s 0))]) ; + Lwt.return @@ Result.return_unit + let assert_invalid_key run = let open Lwt_syntax in Lwt.catch @@ -63,8 +98,140 @@ let assert_invalid_key run = (fun caught_exn -> match caught_exn with | Durable.Invalid_key _ -> Lwt.return_ok () + | Host_funcs.Key_too_large _ -> Lwt.return_ok () | x -> raise x) +(* Test checking that if [key] is too large, [store_has key] traps. *) +let test_store_has_key_too_long () = + let open Lwt_syntax in + let* tree = empty_tree () in + let* durable = wrap_as_durable_storage tree in + let module_inst = Tezos_webassembly_interpreter.Instance.empty_module_inst in + let memory = Memory.alloc (MemoryType Types.{min = 20l; max = Some 3600l}) in + let src = 10l in + (* Together with the '/durable' prefix, and '/_' this key is too long *) + let key = List.repeat 240 "a" |> String.concat "" |> ( ^ ) "/" in + let _ = Memory.store_bytes memory src key in + let memories = Lazy_vector.Int32Vector.cons memory module_inst.memories in + let module_inst = {module_inst with memories} in + let host_funcs_registry = Tezos_webassembly_interpreter.Host_funcs.empty () in + Host_funcs.register_host_funcs host_funcs_registry ; + + let module_reg = Instance.ModuleMap.create () in + let module_key = Instance.Module_key "test" in + Instance.update_module_ref module_reg module_key module_inst ; + + let values = + Values.[Num (I32 src); Num (I32 (Int32.of_int @@ String.length key))] + in + let* _ = + assert_invalid_key (fun () -> + Eval.invoke + ~module_reg + ~caller:module_key + ~durable + host_funcs_registry + Host_funcs.Internal_for_tests.store_has + values) + in + (* We can tell [store_has] that [key] is one byte less long, which makes it valid *) + let values = + Values.[Num (I32 src); Num (I32 (Int32.of_int @@ (String.length key - 1)))] + in + let* _, result = + Eval.invoke + ~module_reg + ~caller:module_key + ~durable + host_funcs_registry + Host_funcs.Internal_for_tests.store_has + values + in + assert (result = Values.[Num (I32 (I32.of_int_s 0))]) ; + Lwt.return_ok () + +(* Test checking that if [key] has value/subtree, [store_has key] returns + the correct enum value. *) +let test_store_has_existing_key () = + let open Lwt_syntax in + let* tree = empty_tree () in + let value () = Chunked_byte_vector.of_string "a very long value" in + let key_steps = + [ + "thequickbrownfoxjumpedoverthelazydog"; + "THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG"; + "0123456789"; + "key.containing.all.valid.chars"; + ] + in + let* tree = + Tree_encoding_runner.encode + (Tree_encoding.scope + ("durable" :: List.append key_steps ["_"]) + Tree_encoding.chunked_byte_vector) + (value ()) + tree + in + let* tree = + Tree_encoding_runner.encode + (Tree_encoding.scope + ("durable" :: List.append key_steps ["one"; "_"]) + Tree_encoding.chunked_byte_vector) + (value ()) + tree + in + let* tree = + Tree_encoding_runner.encode + (Tree_encoding.scope + ("durable" :: List.append key_steps ["two"; "three"; "_"]) + Tree_encoding.chunked_byte_vector) + (value ()) + tree + in + let* durable = wrap_as_durable_storage tree in + let module_inst = Tezos_webassembly_interpreter.Instance.empty_module_inst in + let memory = Memory.alloc (MemoryType Types.{min = 20l; max = Some 3600l}) in + let src = 20l in + let key = "/" ^ String.concat "/" key_steps in + let _ = Memory.store_bytes memory src key in + let src_one = 1000l in + let key_one = key ^ "/one" in + let _ = Memory.store_bytes memory src_one key_one in + let src_two = 2000l in + let key_two = key ^ "/two" in + let _ = Memory.store_bytes memory src_two key_two in + let memories = Lazy_vector.Int32Vector.cons memory module_inst.memories in + let module_inst = {module_inst with memories} in + let host_funcs_registry = Tezos_webassembly_interpreter.Host_funcs.empty () in + Host_funcs.register_host_funcs host_funcs_registry ; + + let module_reg = Instance.ModuleMap.create () in + let module_key = Instance.Module_key "test" in + Instance.update_module_ref module_reg module_key module_inst ; + + let check src key expected = + let values = + Values.[Num (I32 src); Num (I32 (Int32.of_int @@ String.length key))] + in + let+ _, result = + Eval.invoke + ~module_reg + ~caller:module_key + ~durable + host_funcs_registry + Host_funcs.Internal_for_tests.store_has + values + in + assert (result = Values.[Num (I32 (I32.of_int_s expected))]) + in + (* key has a value, and subtrees at 'one' & 'two' *) + let* _ = check src key 3 in + (* key/one has a value, and no subtrees. *) + let* _ = check src_one key_one 1 in + (* key/two has no value, and a subtree at key/two/three. *) + let* _ = check src_two key_two 2 in + Lwt.return_ok () + (* Test that find_value/find_value_exn correctly decode the chunked_byte_vector *) let test_durable_find_value () = @@ -102,6 +269,34 @@ let test_durable_find_value () = assert (Option.is_none r) ; Lwt.return_ok () +let test_durable_count_subtrees () = + let open Lwt_syntax in + let* tree = empty_tree () in + let assert_subtree_count t count under = + let* t = wrap_as_durable_storage t in + let dbl = Durable.of_storage_exn t in + let+ n = Durable.count_subtrees dbl @@ Durable.key_of_string_exn under in + assert (n = count) + in + let add_value t at = + let value = Chunked_byte_vector.of_string "a very long value" in + Tree_encoding_runner.encode + (Tree_encoding.scope at Tree_encoding.chunked_byte_vector) + value + t + in + let* () = assert_subtree_count tree 0 "/hello" in + let* tree = add_value tree ["durable"; "hello"; "world"; "_"] in + let* () = assert_subtree_count tree 1 "/hello" in + let* tree = add_value tree ["durable"; "hello"; "you"; "_"] in + let* () = assert_subtree_count tree 2 "/hello" in + let* tree = add_value tree ["durable"; "hello"; "you"; "too"; "_"] in + let* () = assert_subtree_count tree 2 "/hello" in + let* () = assert_subtree_count tree 1 "/hello/you" in + let* () = assert_subtree_count tree 0 "/hello/you/too" in + let* () = assert_subtree_count tree 0 "/bye" in + Lwt.return_ok () + (* Test invalid key encodings are rejected. *) let test_durable_invalid_keys () = let open Lwt.Syntax in @@ -129,6 +324,10 @@ let test_durable_invalid_keys () = let tests = [ + tztest "store_has missing key" `Quick test_store_has_missing_key; + tztest "store_has existing key" `Quick test_store_has_existing_key; + tztest "store_has key too long key" `Quick test_store_has_key_too_long; tztest "Durable: find value" `Quick test_durable_find_value; + tztest "Durable: count subtrees" `Quick test_durable_count_subtrees; tztest "Durable: invalid keys" `Quick test_durable_invalid_keys; ] diff --git a/src/lib_scoru_wasm/test/test_wasm_pvm.ml b/src/lib_scoru_wasm/test/test_wasm_pvm.ml index d4dd49da9aa4..90b87dc85792 100644 --- a/src/lib_scoru_wasm/test/test_wasm_pvm.ml +++ b/src/lib_scoru_wasm/test/test_wasm_pvm.ml @@ -2,6 +2,7 @@ (* *) (* Open Source License *) (* Copyright (c) 2022 Nomadic Labs *) +(* Copyright (c) 2022 TriliTech *) (* *) (* Permission is hereby granted, free of charge, to any person obtaining a *) (* copy of this software and associated documentation files (the "Software"),*) @@ -41,6 +42,16 @@ let unreachable_kernel = "unreachable" (* Kernel writing `"hello"` to debug output. *) let test_write_debug_kernel = "test-write-debug" +(* Kernel checking the return of the store_has host func. + + This kernel expects a collection of values to exist: + - `/durable/hi/bye` + - `/durable/hello` + - `/durable/hello/universe` + and asserts that `store_has` returns the correct type for each. +*) +let test_store_has_kernel = "test-store-has" + (** [check_error kind reason error] checks a Wasm PVM error [error] is of a given [kind] with a possible [reason]. @@ -170,6 +181,45 @@ let should_run_debug_kernel kernel = (* The kernel should not fail. *) assert (not @@ is_stuck state_after_first_message) +let should_run_store_has_kernel kernel = + let open Lwt_syntax in + let* tree = initial_boot_sector_from_kernel kernel in + let add_value tree key_steps = + let open Lazy_containers in + let open Test_encodings_util in + let value = Chunked_byte_vector.of_string "a very long value" in + Tree_encoding_runner.encode + (Tree_encoding.scope + ("durable" :: List.append key_steps ["_"]) + Tree_encoding.chunked_byte_vector) + value + tree + in + let* tree = add_value tree ["hi"; "bye"] in + let* tree = add_value tree ["hello"] in + let* tree = add_value tree ["hello"; "universe"] in + (* Make the first ticks of the WASM PVM (parsing of origination + message, parsing and init of the kernel), to switch it to + “Input_requested” mode. *) + let* tree = eval_until_input_requested tree in + let* state_before_first_message = + Wasm.Internal_for_tests.get_tick_state tree + in + (* The kernel is not expected to fail, the PVM should not be in stuck state. *) + assert (not @@ is_stuck state_before_first_message) ; + (* We now delete the path ["hello"; "universe"] - this will cause the kernel + assertion on this path to fail, and the PVM should become stuck. *) + let* tree = set_input_step "test" 0 tree in + let* tree = + Test_encodings_util.Tree.remove tree ["durable"; "hello"; "universe"; "_"] + in + let* tree = eval_until_input_requested tree in + let+ state_after_first_message = + Wasm.Internal_for_tests.get_tick_state tree + in + (* The kernel is now expected to fail, the PVM should be in stuck state. *) + assert (is_stuck state_after_first_message) + let test_with_kernel kernel test () = let open Lwt_result_syntax in let open Tezt.Base in @@ -210,4 +260,8 @@ let tests = "Test write_debug kernel" `Quick (test_with_kernel test_write_debug_kernel should_run_debug_kernel); + tztest + "Test store-has kernel" + `Quick + (test_with_kernel test_store_has_kernel should_run_store_has_kernel); ] diff --git a/src/lib_scoru_wasm/test/wasm_kernels/README.md b/src/lib_scoru_wasm/test/wasm_kernels/README.md index 57950461c5ca..403e7288af9f 100644 --- a/src/lib_scoru_wasm/test/wasm_kernels/README.md +++ b/src/lib_scoru_wasm/test/wasm_kernels/README.md @@ -51,3 +51,15 @@ git checkout 0c98b17c4599d6f656312b16f17798406d491d77 ./scripts/build-unit-kernel.sh "test-write-debug" ``` + +## [test-store-has.wasm](./test-store-has.wasm) +This kernel is designed to test the `store_has` host function behaviour, on different keys in *durable storage*. + +It may be originated directly within a boot sector. + +To build the `test-store-has.wasm` kernel, run the following from the checked-out `trili/kernel` repo: +```shell +git checkout 4788b8a882efbc9c19621ab43d617b2bdd5b1baf + +./scripts/build-unit-kernel.sh "test-store-has" +``` diff --git a/src/lib_scoru_wasm/test/wasm_kernels/test-store-has.wasm b/src/lib_scoru_wasm/test/wasm_kernels/test-store-has.wasm new file mode 100755 index 0000000000000000000000000000000000000000..51e8068e6c65b21c6f9af7153f99ab8fab48714c GIT binary patch literal 18984 zcmZQbEY4+QU|?X3;7eetuV+YLuCK3WtOv0f>k}C384_6QL4YBF0V2nczyjhk)5Jn_~iVeRLQW3j-q)6DJcVCnpyt zCnqx}CrBY16BC%r$;rvd#L33P&d9{c#0v5fD+2=)Gb0-VBR5D3FB20JBO@aVD`Nqp zm>4TFBZDBDBy&BZV?)CM2JU(W$15EW`T>Y$H)dhWP0h_Os$^o|&Q2}LOU;STORXqj zVBw07Pf09Ej8Dx=VP@oxkIzU=EQn7^EKX%+;*@4&aAf2bWnz@$66ciQR#8<`*V5LB zN=r6v0k|W#B)^0R$^5FGZk1Bn9P`1 z6j&7)&6pSzSRFaC90jrzm>mVOG?^I8nV~`)AR!L8kODJUl0yL`-OzBL0YtN8fqV#N za%3s62s{N@#lU@%iIE9ruR*pF1H@i|OCVVV1_cI3jV#9rAR`=^1ulaGl|U|Ga)3Yu zMn@)hUIv)L6JUkx2!$*PjE;=%yo@jfPrwS;5DGXH7#*42d6{4e8X6BYFgWrc6!0i8 zy7DqBFgP-pF$p+=9K@65*aK3fz~Cs5eE>0$lo@0}!i-y(k+EI@6sHS7u2E!CVB+TnMYIB=0+YZ( zkQhI=I8==SlLE8AB9NFOivkNjH#iI#1#W^w_(91*i;=OO$w7g^ktIumi9w0c6{G^h zVgR#1;VRGuQq9c`Q>wwl0#)b80oDXo%BaBL$OuzbJ(u$0r$X8$iIRumvL5UKSC={3#Sj?D26qvzj z+l)zohml)>860uk3d|rEgA=YmFUZ+U4hqZ~Okfu>Bb>_!5@bQqS$kpvcI>#;w4}%K(;T;QD z9wu%DRt08IC<(NKB$SwW8DXX3mgFn3v33F zN*oFxn-w?|n6i~P6qx;a85B4anH3lmSrj;U8Ngw|pvc0*49fW;VADAi*cCtpADg3W znIlUfsJH~@8h2@sgtQ{N0-Gaai6WZ<11|$NlY;^~C>66SGJxWdg_j8w=PZtl3aljp z>p?DXWPk=op%MeQ91_?763)Qz5;Hfmg93vBDD5J9fL(#fUx6Lue0Bw9&q5_OX+;(V zb_HeyHffMQ1P+5tQv$gKl%JTmnH)eiPU$$%z@Wqc@jSBvC^Y?fnYa~LAb|st5!eUP zsmQLtBG3Iw*aVOm$m`6G%wcCfU8jgMJFhBmDs^?3i3KAmKk8$cp13yMjdLju_~}bEKp0 zg1ij&mJ*9AFN*>T$k!Z5@x}&HFb9-=6j?w_aLg#NIx;G7lqhi&f=WF$Q1o%|FmrM~**;6}13a&RlKf$Cij1r87eiWN4H zkt_-vP$St9MlwT<#FG<&=#0;~k27VJb&9R?BwbHG^$T-YFmA}2U`LXrU}mw=KnShXVqCl4nnB&WmzsT{ne&6vOf zkgx?gdI3lt)I?bWVkm-&7-j_qfm5IWaRb%Q8cZCZ8iI$J8yp}9K*~Uc7&EA)<;e@m zR0<3N$3f~rtv7)aAeI6vxLppnK;R@ul$V(s;wY#g3ScupjsgpS>ZL427DuQ{AZ`Q| zd7!=uiyNpN4|5C?H>mW+u+)tgR4ZsOfjxz65~Okmn*(Y+K>eq{;ti_T7@($tYF|(* z9^!c=c0|Ha;>>o;%u)nbu&|g^;((7KS=mb5W{@nRz^}mV$XH~?!~(UM2WFBYFOtoCNHzBykT1c@|31ujs=V$fvT0#ahm#Gt^XAZX6S;K-oBYR0q! zBBOIJ%IS^G61Ela{2DLZXxxrl#a81e#ZgqqBEDCI( zuvCD>EWDrsHO-*0%?6Jnu+a((*;z`=u&P6m1=Qe&Rwy9fvw@QzlLB*AHmHdL&vXh5 zZjiDPQlv1r@qz+jJ1AgySwXo=fdSHtP-2G$5(A_)#{(*a6&M_Oz|}Ats4NAuI6&1N z2PpP<6xhH8JUCQ97J|dgu}*>Ak+}@1=3`f2$^vzu6xgBB$-o0{pR>SIE=V)DELUIx z7hMoG3#dI0O0=+G0$1Lk4mh|JhNf*uVFJ$Vpqc<;g%ZqcP#FqI`B=+PaAn49#sn^U zz-@S>*a5i;Y%YiaaS~gWz(i2c@qh|3ctH(u0=W2wdH})(g*3Ryi{t@jZcxWZfdQU2 zpcU-i!&{pmSt!oC6Xz zV_E^C5Q@Q~jtq`VK*DBB8$c97F<8`*!Ep^p*o2A2(+^bc7bq7@n=v)Cfd;P_9HHDlP+2f- z#?%3og>qY{1LcBgGo~3(?i3Jh#DR|5QR{@1j=0lqRp6gfGC7wuqY_XK*DBB2S5}kenGSu(-sf~iZT#w z#&iNiAr$X{a*u#$Go}k53ZWP*3W`CHuo=@05Cw`~5N*bE21GeBI9>tKW=s!26hbjr z)RDpQ4oKLH=>>>FCd4^u1te_7 z)BqZ^Kqv-_Ix;x^fyj11Wx>K`Okhz*2FDhVuo=??5QR_-7DdSRfMlWV0Ty^&gVf+r zXQZ9vj7#y z0>?ngLG5ygMkQuQw;R-aV1|vffEp2u+zOxpNYJpmv?3F;g8~zHRE$N5*%4+u3#d=* zC;+NxnKhUMK*Jy`pym-Ps2>6zW&(}hLMnU>CK<%wkrE52MGR^sfc)nu0_s8tC@{E5 zXMy@83<}JU0Y-2~8^mLPgduo<&an;@05YJu9?a(l^(`6Am?S`fp}`~o8Xy2QU|GzV z1VA;h8IuI4-31vYgAU$`WPvIqP^+5Rj7fr@oBJ*(U>zAitr!JHNSnk_UJ=y4gN^$! zI@Ej=cpmPJv3XBTOxaJ0!K=U&kS&rbj0dUJl1eB9Bm_SoG zpb-crQ1%c2WiLiYMg@>^_}l;}*Mf!`nULoOm^7F`tvcA;0Ei1pSB@-@k#tb;1`2v6 zEOP@_SRnz=2nh&K`UWLI1qOkwpke^jZ`NR9fQ))7FbM2`3NkA&W+{SZub2h)gM^g8 zBTV4dJZM%6WIqM0T>?<^95Ttn3hENDf>If%UC9b5u^`0+tV;kI z+yxaAU_QubCV?#w>p^{H(Cif0sXUN08tHLGk{VTxSN3zvLM5uLsbwa*h+qG1tv)LRDwhd zI0|9m#Dv^+VuE&^SU__W;If|y>={@%fg0Z6raH)3;BWzr7@~Ha;64FmZVkw=oI9un zfk!kqIHI8CBsiOaI}!Y#+KRbM3AyJ0o->16ro;?N@UWf(BdC81?KvMo2pnlJa1!SVT31b4C)>jDb&9 zf@dTd6&OJiJ>W@4XyM}uGhPYa;8kQq7_Nvk5)2x|1r_O_`~@yolpqxyBWT(ZhU@FL$+2GO@>VA;x!3oV5ROC9= zL&rS9Wh-bt8dNJYLI!O>=~DwbW>OCx!vc?=fTnmM221gCgZ0s)Om1UlH^g4Au!ji#DZ+PV@(#snV_k11_fqVl@Icq0;6L+Xz>ns-W#-J1>9q0 z&H`oS>_VtYCZs3^^~J#JD-^(GKB!Ti4Qj?`DS--1CCJhZq*gGa0<*wQP#A&Q9Z0On zATdy!fY!1pf*QS`WiFs7Q(($6V`AV|V1%}$85I~I2~i1YDT)G1mM<@;;D^mLfL0o@ zK+OlO2xG}sVnA>O;MOsLGBYH(gKUM^A*H~;&BNgI?a_~opB}D%&dSZp;B;}_j3YCf zH+^rZ=l;%w=-mh)^=?1`2wMN-*Z}U|fV(6-psufgKQDOglcRm1V*_K66$3A5jgKQ+ znd1QvkH-a z(Fw%v1{P1yngs<$xNZDk+l0y-KY(om^VrJZ(tKb69)tj|BMW4$5vZ>Yb241j1FVMd zIx;JQT0*d19eA1nR1PsHF=s0zsr1`rqpdcb}G7fGO{HlQksIZFZ5##Ueycny-2 z0(UGyK4jnq_v9eGM@I&33FuNsa7753$q|?h(!jvIAGBNxvFZuB7EOV{5j;YH7$$(Z zj*p3f5j23$%jCEKwCE4iPX@0-QDA{gOfo2e>`-I@1v-NwXz>`RwGW!B0r$w69rrYW zmO?TLJOViY6o3LxKrDe3AQGe=)Z#%>zXHE{8PKFO11|%_IgZ*2i~@I|CV?g~nH)eB z5KPkX2guDx3YZwURiTRkK~>#{7SNI(CdX!w2?|Wog5dR^3=E(|4X#Y5fh4%OK-KsZ zF!K%vBOAPcQ(yuYZ=jl60IX7p2~=(J!wNBQRinTN8o7Z?xD!!`F=8#m7`>$xm_c>2 zfC4jU6vImsMVfmjG(kg&dZIH|dA>m~OsHw&R%6#CZEZ{~7 zXc`>M19t=6c$pR0AU#-Kb_F(Q!NRV(dli99cls8d#rWV*`gLFB_~q25zA-D6wUO2AaTqcXkC9NBJyBtt@Z> z6cvyV1&v_|oB{DcBX4ZrVOS+bkhW|kX2*goCD2M<0q{&JsMLZ@CW88PETE>IV@Vby zY{01yRExsK1z5pVIWu%{03rjPG*e^0p1dHdVdXEI0;2+~{AE*Mg%-Ua7NqE90k{4kZ9+(3`{L8Dz>=-R0%9KbQ5gftKhDvKClPI6=bFB)V8RXrdVgXf!-SQXeH;it%s z#WARDBmgcZ6qrGyCZM4)Q0@mM2Z#zO1qO%$ZqPDi zm^o4kjF5VjI})Y3gf2-{U=Vl=3PZ;i;KFPUhz*)thLorRbHRMjm>_6)1=J1zEg4{h z3}rJ4%mPU>aBpN{VnM8THGtQ}3XF~{;B|+fJ`rd{9kduo5i)?|$dRQ48BAATa$+=R z=1^c#01XX-mK!rUN`UgE0t;eMJXi>{%H0vZD4t1y1-vL;LV?LqB+KyvxM&Bd6Sxm@ zmXrc$6|w@W254{+ROvBkGIN-NnlK}EBOpfrCLIpLI5L6?4N$&q0L{ySR+wa&F@f2j633B2m*E6x)*ZAGi$R0w0*LL%n576= z$LGjs1(607A8ck2X^=hzc1H#eUIqm=M<&pi0jmOw6@vt5x&f3l!MisEKz4osSMThO z^*-QvF?L7BEG2d`Ca^H1v-k(B0<`WBr2YqprwFRa7(l@#0BsH^uqv=>GBbcO06Ta$ zhys%alL%B2qz`PMB0I>H?2h$WP#ZvNol05^rA!6GJqFD@T z8-WTu@Sr0HIHw7$1*w-}VBn5mWCHI@08ImcS^(hIAUM5&L>RKc3j{$^F$zq`4M$M> z3Z#@F3p_XuZ#6PN`U;K=+(OWnBBQ`euw9M}+$9LtA*Lii{S|ONg_aEhS)j=?c)A5G ze*&$oN6!0@qzv*2Xv+sE5kWi!&ijg>ECbt4puot@0%~;$fJRdpvmEQ8-6-%*4$y`O z@K{QA5jPivp}q3bQxG2nF<{l z%it1>g&|WlVP*2yfr5UvPgGJyaDDi@NsE+?Z3C)oeN#qAugdIub1z1D?A_Cg@ z!vpF^GYNp3|6mU(FbZ4+8OZ?Sb)fKWKzM#AIR(0nOM$^r23k)sI4%LX&x}bzfdN!k z@hC7j?tqAZ0)->X@c@V?a1UY}XhKYZQQ!&+Z$5&j!NefNT+hS64RZ1gcJMR=XyzN- zdINI0)LQ{H+!Q%L+YuNvm?S{O z1lR)_Obi-KJc5m2+ZCC?twxAaW(NgO&zsea7rY!>fmw%vL5Txg$SQ#P+lrvZ8n{80 z0BS%oJ2GVSL~$VO<JA$0Ww_y)C9vF5B#9D1mNX~pw$rI zc@zPVcR;g=FF-K`a}yKXfuQyDg^KK8XET8cR?vPPM+T6y6hW&y6_^}r3PF`LLU+)Fl;K&GeI+VkN%wdLe6gj}XQblG3Hpd!REP(d-pqd6&1|C8L)sjl=pvVIE z1UbO#Ruq{PSQR+3mDpk3RM5PqE`x#+hXRKqvzxRdb0Hry69Xe?y`CbQ0z1U{?2e3O zip&b2x*fy^5f);~7Emy!W z7Hla*5#9)9<_(iAlEdI3~wfL53=gGv?9;0YsW=?62YTPpz`HI)Dj z1%d}Apk<2>ilNYT1`14|CYA)G^7i`sn z0enZJ0<)tEq@Dt8@~~piP+)cfm8cCYpr#YpaSEU4z#~e0n~g04RkYW zFsUHL8fYgVs5!(8>I6WC4xup*-tNi)TI>$$At*8`uz|*R*?2+2g`mMTaIRAVB@hJ$ zN7fQWQ27mUi+v#|&RIb2X8_Irpt%XGg;|3M>Lvz|`;grP>TZI@E3%Y8^@c73132Ko z<8PWw3{DE2pul5rlmI7YPLM4Eid>EiilEhB;A{=5o*^N|$IQsU#K^6{>BwB7$OGEp zr@*DalcmH1YE*zH$wBKUc)&$FgCZv=m9vA^FL8pJ&EPF$py6==uuTY~!9Ir>%?>h} zQ-Mo?GfRmR#aK?LvFspYxk1LVL((KSsQTjqWj_W-=8`PXcp)eab7X;pSYW{q8bRd% zE&Je5U~^Q+Qetxl6%URKpvf7Kr&&Bf+ib!6NEJYQ2GB075^y_FS_#x?1w}avTHw0! zGJ;$KY6Zjlb&wJ3#vQ9BfBpRQjR>eW!w7N-qyZyv2b99$4I@xH3)WE5Wf0)L$&AQG z9~iQg*dZgXpt2m)bY}-GQUGm+1aHY@2lc@b>6-ymr|>Z|FoHU`?2a!Xd04`c39=88 z-SIiH2qU)wyW<0x2s>zGl^vA5Wk4mS1``7>X!n;z7N}bdUY`x>&ayimVaRes;@)5Y zD**Qg*_~L-nPL>!9nXMzIc7`|3ha)PK%O;YvQc1HV0X00GGodBvjnotm^{ENjx00K zc1;C#M^J%cp}_8VgCR?S4c1^$V0Tmi4+F3wh5^7r99iIw61Xo5%7?6AmI6dS$j#vG zxa^Ks7_uC}!(0&O6Yvkr2P+8rKq1SFDFEyPqWuCJG6yFH7Eqx9sS>zLP637B?R|oqR)WHXj34llVVL}QFU>2xVz>M4-0;z^~hZwjQb1-s( z$C(uv9GSBmYYLT^KnqV{O>jpRP|uQ4ff+Q|2cE`Yabzw8ZHxj}<&2<>TcDY1W{@a2 zD}(xPj`hV^j?ns_QGr1bwE9JX8C3ssfOcJjM3@~wEkICf1zhDbIU?2nOpZwPKa(R; z{SWHPv49q0a)9c84p7bo@9{-74ID^}AZ3X9A2ddm1*(-5SV8Uu0<>~ zoy=KEED%Pa5-5I^7(s~y+=l=)7Qq|*AVI+B_y@EAwGdpZffnJyf`A?B6?QB^fL#s} z1X$%jL4ZvHIS4>w_n@Q&TC>3oOWZ7upx#MMmLhn02X13PgQcKRPSE^seHLhJkQ-E^ z;|n~<5;IUE8r-L3E(9%f0nZxN!*dX*o1?%8$~~ZY9#DGYP+)+jTTn58lyex6a}Fp& z!<2!W5iFp%VT5}Rd~^c1vR40(B!md*B%qK)rQFP}2pp9TD6L0kyV3Lvi3vof5MGt0&l6 zR?vQ$Y$bM3nZyAeItGP{0!x+>rz3MAC=+uyGJ;Ng0JTDt*c>Ga6`2$`L8`exk-!L= zipU0uvM6wY#v<9k3x(Mfn94vUDT5N50!v8|s5$^O>J%9jSRGkFQ%s=MJUpQNk6_ao z6ga`L&I;CpT{SnT1_i~O0w*XtfV)?qkv>qXI7^Wg)D2Kzg!+^b)Pw^S5saWkw@{xl zaPxtOTNIcCUV$n~Ztia^jGzID0}R}6SU`u|fCjBVn2CXbK|dpt0YsOi7MH|B4z1BI zE=txf&C7)Gi}i|%86+447~~lk7$g}O7+4|t^ph%689?U24=2H;nJj#J~V@ zC&>Ri3=9k)8sr}~1_lNWD4!k57J%|O85kJ27#J9k)o?Q~Fo5)f#6V_%FfRiG10Mqe z13v=;Lm0?~;h7~F!KFzhMX9M!3M>rr1I+P>IXU^sVCNSlmdBT+ChHXyCnpvpCTEsZ zD&&`?7NzCnmoqRhEMXL25M*Fr=wO8Si;W2q4 key -> value option Lwt.t val find_tree : tree -> key -> tree option Lwt.t + + val length : tree -> key -> int Lwt.t end type 'tree backend = (module S with type tree = 'tree) @@ -71,6 +73,9 @@ let find : type tree. tree backend -> tree -> key -> value option Lwt.t = let find_tree : type tree. tree backend -> tree -> key -> tree option Lwt.t = fun (module T) tree key -> T.find_tree tree key +let length : type tree. tree backend -> tree -> key -> int Lwt.t = + fun (module T) tree key -> T.length tree key + type wrapped_tree = Wrapped_tree : 'tree * 'tree backend -> wrapped_tree type Lazy_containers.Lazy_map.tree += Wrapped of wrapped_tree @@ -99,6 +104,8 @@ module Wrapped : S with type tree = wrapped_tree = struct let+ t' = find_tree b t key in match t' with Some t' -> Some (Wrapped_tree (t', b)) | None -> None + let length (Wrapped_tree (t, b)) key = length b t key + let find (Wrapped_tree (t, b)) key = find b t key let select = function diff --git a/src/lib_tree_encoding/tree.mli b/src/lib_tree_encoding/tree.mli index f53180336461..b9e109731eb2 100644 --- a/src/lib_tree_encoding/tree.mli +++ b/src/lib_tree_encoding/tree.mli @@ -50,6 +50,8 @@ module type S = sig val find : tree -> key -> value option Lwt.t val find_tree : tree -> key -> tree option Lwt.t + + val length : tree -> key -> int Lwt.t end type 'tree backend = (module S with type tree = 'tree) @@ -68,6 +70,8 @@ val find : 'tree backend -> 'tree -> key -> value option Lwt.t val find_tree : 'tree backend -> 'tree -> key -> 'tree option Lwt.t +val length : 'tree backend -> 'tree -> key -> int Lwt.t + (** A [wrapped_tree] allows modifications to the underlying tree, without affecting the tree that it was decoded from. *) type wrapped_tree = Wrapped_tree : 'tree * 'tree backend -> wrapped_tree diff --git a/src/lib_tree_encoding/tree_encoding.mli b/src/lib_tree_encoding/tree_encoding.mli index 1d0fc0932ac4..97ffe0cfd0e6 100644 --- a/src/lib_tree_encoding/tree_encoding.mli +++ b/src/lib_tree_encoding/tree_encoding.mli @@ -266,6 +266,8 @@ module type TREE = sig val find : tree -> key -> value option Lwt.t val find_tree : tree -> key -> tree option Lwt.t + + val length : tree -> key -> int Lwt.t end type wrapped_tree -- GitLab