From 87d6f6c7c90bf7b427397d6bd2e2c70d610678e3 Mon Sep 17 00:00:00 2001 From: Son Ho Date: Tue, 4 Jul 2023 14:57:51 +0200 Subject: Reorganize the Lean tests --- compiler/Config.ml | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'compiler/Config.ml') diff --git a/compiler/Config.ml b/compiler/Config.ml index ce9b0e0c..bfb9d161 100644 --- a/compiler/Config.ml +++ b/compiler/Config.ml @@ -162,6 +162,11 @@ let backward_no_state_update = ref false *) let split_files = ref true +(** For Lean, controls whether we generate a lakefile or not. + + *) +let lean_gen_lakefile = ref false + (** If true, treat the unit functions (function taking no inputs and returning no outputs) as unit tests: evaluate them with the interpreter and check that they don't panic. -- cgit v1.3.1 From 0a0445c72e005c328b4764f5fb0f8f38e7a55d60 Mon Sep 17 00:00:00 2001 From: Son Ho Date: Wed, 5 Jul 2023 14:52:23 +0200 Subject: Start using namespaces in the Lean backend --- compiler/Config.ml | 7 + compiler/Extract.ml | 28 +- compiler/ExtractBase.ml | 4 +- compiler/Pure.ml | 10 +- compiler/Translate.ml | 80 ++-- tests/coq/betree/BetreeMain_Opaque.v | 2 +- tests/coq/hashmap_on_disk/HashmapMain_Opaque.v | 2 +- tests/coq/misc/External_Opaque.v | 2 +- tests/fstar/betree/BetreeMain.Opaque.fsti | 2 +- .../betree_back_stateful/BetreeMain.Opaque.fsti | 2 +- .../fstar/hashmap_on_disk/HashmapMain.Opaque.fsti | 2 +- tests/fstar/misc/External.Opaque.fsti | 2 +- tests/hol4/betree/betreeMain_OpaqueScript.sml | 2 +- .../hashmap_on_disk/hashmapMain_OpaqueScript.sml | 2 +- tests/hol4/misc-external/external_OpaqueScript.sml | 2 +- tests/lean/BetreeMain/ExternalFuns.lean | 9 - tests/lean/BetreeMain/Funs.lean | 498 ++++++++++----------- tests/lean/BetreeMain/FunsExternal.lean | 35 ++ tests/lean/BetreeMain/FunsExternal_Template.lean | 31 ++ tests/lean/BetreeMain/Opaque.lean | 35 -- tests/lean/BetreeMain/Types.lean | 5 +- tests/lean/Constants.lean | 9 +- tests/lean/External/ExternalFuns.lean | 9 - tests/lean/External/Funs.lean | 36 +- tests/lean/External/FunsExternal.lean | 33 ++ tests/lean/External/FunsExternal_Template.lean | 29 ++ tests/lean/External/Opaque.lean | 14 +- tests/lean/External/Types.lean | 5 +- tests/lean/Hashmap/Funs.lean | 192 ++++---- tests/lean/Hashmap/Types.lean | 5 +- tests/lean/HashmapMain/ExternalFuns.lean | 9 - tests/lean/HashmapMain/Funs.lean | 221 +++++---- tests/lean/HashmapMain/FunsExternal.lean | 17 + tests/lean/HashmapMain/FunsExternal_Template.lean | 16 + tests/lean/HashmapMain/Opaque.lean | 8 +- tests/lean/HashmapMain/Types.lean | 5 +- tests/lean/Loops/Funs.lean | 5 +- tests/lean/Loops/Types.lean | 5 +- tests/lean/NoNestedBorrows.lean | 5 +- tests/lean/Paper.lean | 5 +- tests/lean/PoloniusList.lean | 5 +- tests/lean/Tests.lean | 9 - tests/lean/lakefile.lean | 21 +- 43 files changed, 766 insertions(+), 659 deletions(-) delete mode 100644 tests/lean/BetreeMain/ExternalFuns.lean create mode 100644 tests/lean/BetreeMain/FunsExternal.lean create mode 100644 tests/lean/BetreeMain/FunsExternal_Template.lean delete mode 100644 tests/lean/BetreeMain/Opaque.lean delete mode 100644 tests/lean/External/ExternalFuns.lean create mode 100644 tests/lean/External/FunsExternal.lean create mode 100644 tests/lean/External/FunsExternal_Template.lean delete mode 100644 tests/lean/HashmapMain/ExternalFuns.lean create mode 100644 tests/lean/HashmapMain/FunsExternal.lean create mode 100644 tests/lean/HashmapMain/FunsExternal_Template.lean delete mode 100644 tests/lean/Tests.lean (limited to 'compiler/Config.ml') diff --git a/compiler/Config.ml b/compiler/Config.ml index bfb9d161..f58ba89b 100644 --- a/compiler/Config.ml +++ b/compiler/Config.ml @@ -297,3 +297,10 @@ let filter_useless_monadic_calls = ref true dynamically check for that). *) let filter_useless_functions = ref true + +(** Obsolete. TODO: remove. + + For Lean we used to parameterize the entire development by a section variable + called opaque_defs, of type OpaqueDefs. + *) +let wrap_opaque_in_sig = ref false diff --git a/compiler/Extract.ml b/compiler/Extract.ml index 7d00dd73..50215dac 100644 --- a/compiler/Extract.ml +++ b/compiler/Extract.ml @@ -625,13 +625,12 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) in prefix ^ tname ^ suffix in - let get_fun_name = get_name in - let fun_name_to_snake_case (fname : fun_name) : string = - let fname = get_fun_name fname in - (* Converting to snake case should be a no-op, but it doesn't cost much *) - let fname = List.map to_snake_case fname in - (* Concatenate the elements *) - String.concat "_" fname + let get_fun_name fname = + let fname = get_name fname in + (* TODO: don't convert to snake case for Coq, HOL4, F* *) + match !backend with + | FStar | Coq | HOL4 -> String.concat "_" (List.map to_snake_case fname) + | Lean -> String.concat "." fname in let global_name (name : global_name) : string = (* Converting to snake case also lowercases the letters (in Rust, global @@ -642,7 +641,7 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) let fun_name (fname : fun_name) (num_loops : int) (loop_id : LoopId.id option) (num_rgs : int) (rg : region_group_info option) (filter_info : bool * int) : string = - let fname = fun_name_to_snake_case fname in + let fname = get_fun_name fname in (* Compute the suffix *) let suffix = default_fun_suffix num_loops loop_id num_rgs rg filter_info in (* Concatenate *) @@ -651,7 +650,7 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) let termination_measure_name (_fid : A.FunDeclId.id) (fname : fun_name) (num_loops : int) (loop_id : LoopId.id option) : string = - let fname = fun_name_to_snake_case fname in + let fname = get_fun_name fname in let lp_suffix = default_fun_loop_suffix num_loops loop_id in (* Compute the suffix *) let suffix = @@ -666,7 +665,7 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) let decreases_proof_name (_fid : A.FunDeclId.id) (fname : fun_name) (num_loops : int) (loop_id : LoopId.id option) : string = - let fname = fun_name_to_snake_case fname in + let fname = get_fun_name fname in let lp_suffix = default_fun_loop_suffix num_loops loop_id in (* Compute the suffix *) let suffix = @@ -681,7 +680,7 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) let opaque_pre () = match !Config.backend with | FStar | Coq | HOL4 -> "" - | Lean -> "opaque_defs." + | Lean -> if !Config.wrap_opaque_in_sig then "opaque_defs." else "" in let var_basename (_varset : StringSet.t) (basename : string option) (ty : ty) @@ -2981,8 +2980,11 @@ let extract_fun_decl_gen (ctx : extraction_ctx) (fmt : F.formatter) let use_forall = is_opaque_coq && def.signature.type_params <> [] in (* Print the qualifier ("assume", etc.). - For Lean: we generate a record of assumed functions *) - (if not (!backend = Lean && (kind = Assumed || kind = Declared)) then + if `wrap_opaque_in_sig`: we generate a record of assumed funcions. + TODO: this is obsolete. + *) + (if not (!Config.wrap_opaque_in_sig && (kind = Assumed || kind = Declared)) + then let qualif = ctx.fmt.fun_decl_kind_to_qualif kind in match qualif with | Some qualif -> diff --git a/compiler/ExtractBase.ml b/compiler/ExtractBase.ml index 14ce4119..feab7706 100644 --- a/compiler/ExtractBase.ml +++ b/compiler/ExtractBase.ml @@ -240,7 +240,9 @@ type formatter = { - loop identifier, if this is for a loop *) opaque_pre : unit -> string; - (** The prefix to use for opaque definitions. + (** TODO: obsolete, remove. + + The prefix to use for opaque definitions. We need this because for some backends like Lean and Coq, we group opaque definitions in module signatures, meaning that using those diff --git a/compiler/Pure.ml b/compiler/Pure.ml index 4a00dfb2..b251a005 100644 --- a/compiler/Pure.ml +++ b/compiler/Pure.ml @@ -18,16 +18,19 @@ module GlobalDeclId = A.GlobalDeclId (they monotonically increase across functions) while in {!module:Pure} we want the indices to start at 0 for every function. *) -module LoopId = IdGen () +module LoopId = +IdGen () type loop_id = LoopId.id [@@deriving show, ord] (** We give an identifier to every phase of the synthesis (forward, backward for group of regions 0, etc.) *) -module SynthPhaseId = IdGen () +module SynthPhaseId = +IdGen () (** Pay attention to the fact that we also define a {!E.VarId} module in Values *) -module VarId = IdGen () +module VarId = +IdGen () type integer_type = T.integer_type [@@deriving show, ord] @@ -723,6 +726,7 @@ type fun_sig_info = { *) type fun_sig = { type_params : type_var list; + (** TODO: we should analyse the signature to make the type parameters implicit whenever possible *) inputs : ty list; (** The input types. diff --git a/compiler/Translate.ml b/compiler/Translate.ml index 5827b4a8..795674b4 100644 --- a/compiler/Translate.ml +++ b/compiler/Translate.ml @@ -750,18 +750,17 @@ let extract_definitions (fmt : Format.formatter) (config : gen_config) if config.extract_state_type && config.extract_fun_decls then export_state_type (); - (* For Lean, we parameterize the entire development by a section variable - called opaque_defs, of type OpaqueDefs. The code below emits the type - definition for OpaqueDefs, which is a structure, in which each field is one - of the functions marked as Opaque. We emit the `structure ...` bit here, - then rely on `extract_fun_decl` to be aware of this, and skip the keyword - (e.g. "axiom" or "val") so as to generate valid syntax for records. - - We also generate such a structure only if there actually are opaque - definitions. - *) + (* Obsolete: (TODO: remove) For Lean we parameterize the entire development by a section + variable called opaque_defs, of type OpaqueDefs. The code below emits the type + definition for OpaqueDefs, which is a structure, in which each field is one of the + functions marked as Opaque. We emit the `structure ...` bit here, then rely on + `extract_fun_decl` to be aware of this, and skip the keyword (e.g. "axiom" or "val") + so as to generate valid syntax for records. + + We also generate such a structure only if there actually are opaque definitions. *) let wrap_in_sig = - config.extract_opaque && config.extract_fun_decls && !Config.backend = Lean + config.extract_opaque && config.extract_fun_decls + && !Config.wrap_opaque_in_sig && let _, opaque_funs = module_has_opaque_decls ctx in opaque_funs @@ -785,6 +784,8 @@ let extract_definitions (fmt : Format.formatter) (config : gen_config) type extract_file_info = { filename : string; + namespace : string; + in_namespace : bool; crate_name : string; rust_module_name : string; module_name : string; @@ -852,9 +853,10 @@ let extract_file (config : gen_config) (ctx : gen_ctx) (fi : extract_file_info) (* Add the custom includes *) List.iter (fun m -> Printf.fprintf out "import %s\n" m) fi.custom_includes; (* Always open the Primitives namespace *) - Printf.fprintf out "open Primitives\n\n"; - (* Open the namespace *) - Printf.fprintf out "namespace %s\n" fi.crate_name + Printf.fprintf out "open Primitives\n"; + (* If we are inside the namespace: declare it, otherwise: open it *) + if fi.in_namespace then Printf.fprintf out "namespace %s\n" fi.namespace + else Printf.fprintf out "open %s\n" fi.namespace | HOL4 -> Printf.fprintf out "open primitivesLib divDefLib\n"; (* Add the custom imports and includes *) @@ -884,7 +886,7 @@ let extract_file (config : gen_config) (ctx : gen_ctx) (fi : extract_file_info) (* Close the module *) (match !Config.backend with | FStar -> () - | Lean -> Printf.fprintf out "end %s\n" fi.crate_name + | Lean -> if fi.in_namespace then Printf.fprintf out "end %s\n" fi.namespace | HOL4 -> Printf.fprintf out "val _ = export_theory ()\n" | Coq -> Printf.fprintf out "End %s .\n" fi.module_name); @@ -986,7 +988,7 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : (* Open the output file *) (* First compute the filename by replacing the extension and converting the * case (rust module names are snake case) *) - let crate_name, extract_filebasename = + let namespace, crate_name, extract_filebasename = match Filename.chop_suffix_opt ~suffix:".llbc" filename with | None -> (* Note that we already checked the suffix upon opening the file *) @@ -1001,8 +1003,14 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : StringUtils.lowercase_first_letter crate_name else crate_name in + (* We use the raw crate name for the namespaces *) + let namespace = + match !Config.backend with + | FStar | Coq | HOL4 -> crate.name + | Lean -> crate.name + in (* Concatenate *) - (crate_name, Filename.concat dest_dir crate_name) + (namespace, crate_name, Filename.concat dest_dir crate_name) in (* Put the translated definitions in maps *) @@ -1134,6 +1142,7 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : (* Extract the types *) (* If there are opaque types, we extract in an interface *) + (* TODO: for Lean and Coq: generate a template file *) let types_filename_ext = match !Config.backend with | FStar -> if has_opaque_types then ".fsti" else ".fst" @@ -1157,6 +1166,8 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : let file_info = { filename = types_filename; + namespace; + in_namespace = true; crate_name; rust_module_name = crate.A.name; module_name = types_module; @@ -1183,6 +1194,8 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : let file_info = { filename = template_clauses_filename; + namespace; + in_namespace = true; crate_name; rust_module_name = crate.A.name; module_name = template_clauses_module; @@ -1196,20 +1209,25 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : (* Extract the opaque functions, if needed *) let opaque_funs_module = if has_opaque_funs then ( + (* In the case of Lean we generate a template file *) + let module_suffix, opaque_imported_suffix, custom_msg = + match !Config.backend with + | FStar | Coq | HOL4 -> + ("Opaque", "Opaque", ": external function declarations") + | Lean -> + ( "FunsExternal_Template", + "FunsExternal", + ": external functions.\n\ + -- This is a template file: rename it to \ + \"FunsExternal.lean\" and fill the holes." ) + in let opaque_filename = - extract_filebasename ^ file_delimiter ^ "Opaque" ^ opaque_ext + extract_filebasename ^ file_delimiter ^ module_suffix ^ opaque_ext in - let opaque_module = crate_name ^ module_delimiter ^ "Opaque" in + let opaque_module = crate_name ^ module_delimiter ^ module_suffix in let opaque_imported_module = - (* In the case of Lean, we declare an interface (a record) containing - the opaque definitions, and we leave it to the user to provide an - instance of this module. - - TODO: do the same for Coq. - TODO: do the same for the type definitions. - *) if !Config.backend = Lean then - crate_name ^ module_delimiter ^ "ExternalFuns" + crate_name ^ module_delimiter ^ opaque_imported_suffix else opaque_module in let opaque_config = @@ -1230,10 +1248,12 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : let file_info = { filename = opaque_filename; + namespace; + in_namespace = false; crate_name; rust_module_name = crate.A.name; module_name = opaque_module; - custom_msg = ": opaque function definitions"; + custom_msg; custom_imports = []; custom_includes = [ types_module ]; } @@ -1266,6 +1286,8 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : let file_info = { filename = fun_filename; + namespace; + in_namespace = true; crate_name; rust_module_name = crate.A.name; module_name = fun_module; @@ -1295,6 +1317,8 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : let file_info = { filename = extract_filebasename ^ ext; + namespace; + in_namespace = true; crate_name; rust_module_name = crate.A.name; module_name = crate_name; diff --git a/tests/coq/betree/BetreeMain_Opaque.v b/tests/coq/betree/BetreeMain_Opaque.v index 08ab530a..51321f56 100644 --- a/tests/coq/betree/BetreeMain_Opaque.v +++ b/tests/coq/betree/BetreeMain_Opaque.v @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [betree_main]: opaque function definitions *) +(** [betree_main]: external function declarations *) Require Import Primitives. Import Primitives. Require Import Coq.ZArith.ZArith. diff --git a/tests/coq/hashmap_on_disk/HashmapMain_Opaque.v b/tests/coq/hashmap_on_disk/HashmapMain_Opaque.v index 6152b94b..e1e7fe2b 100644 --- a/tests/coq/hashmap_on_disk/HashmapMain_Opaque.v +++ b/tests/coq/hashmap_on_disk/HashmapMain_Opaque.v @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [hashmap_main]: opaque function definitions *) +(** [hashmap_main]: external function declarations *) Require Import Primitives. Import Primitives. Require Import Coq.ZArith.ZArith. diff --git a/tests/coq/misc/External_Opaque.v b/tests/coq/misc/External_Opaque.v index d60251e0..5ee65277 100644 --- a/tests/coq/misc/External_Opaque.v +++ b/tests/coq/misc/External_Opaque.v @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [external]: opaque function definitions *) +(** [external]: external function declarations *) Require Import Primitives. Import Primitives. Require Import Coq.ZArith.ZArith. diff --git a/tests/fstar/betree/BetreeMain.Opaque.fsti b/tests/fstar/betree/BetreeMain.Opaque.fsti index dc49601a..dfbd73d6 100644 --- a/tests/fstar/betree/BetreeMain.Opaque.fsti +++ b/tests/fstar/betree/BetreeMain.Opaque.fsti @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [betree_main]: opaque function definitions *) +(** [betree_main]: external function declarations *) module BetreeMain.Opaque open Primitives include BetreeMain.Types diff --git a/tests/fstar/betree_back_stateful/BetreeMain.Opaque.fsti b/tests/fstar/betree_back_stateful/BetreeMain.Opaque.fsti index dc49601a..dfbd73d6 100644 --- a/tests/fstar/betree_back_stateful/BetreeMain.Opaque.fsti +++ b/tests/fstar/betree_back_stateful/BetreeMain.Opaque.fsti @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [betree_main]: opaque function definitions *) +(** [betree_main]: external function declarations *) module BetreeMain.Opaque open Primitives include BetreeMain.Types diff --git a/tests/fstar/hashmap_on_disk/HashmapMain.Opaque.fsti b/tests/fstar/hashmap_on_disk/HashmapMain.Opaque.fsti index 6e54ea10..6e6a0e2b 100644 --- a/tests/fstar/hashmap_on_disk/HashmapMain.Opaque.fsti +++ b/tests/fstar/hashmap_on_disk/HashmapMain.Opaque.fsti @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [hashmap_main]: opaque function definitions *) +(** [hashmap_main]: external function declarations *) module HashmapMain.Opaque open Primitives include HashmapMain.Types diff --git a/tests/fstar/misc/External.Opaque.fsti b/tests/fstar/misc/External.Opaque.fsti index 7d86405a..356d5fc4 100644 --- a/tests/fstar/misc/External.Opaque.fsti +++ b/tests/fstar/misc/External.Opaque.fsti @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [external]: opaque function definitions *) +(** [external]: external function declarations *) module External.Opaque open Primitives include External.Types diff --git a/tests/hol4/betree/betreeMain_OpaqueScript.sml b/tests/hol4/betree/betreeMain_OpaqueScript.sml index a6f0cf15..10d67cca 100644 --- a/tests/hol4/betree/betreeMain_OpaqueScript.sml +++ b/tests/hol4/betree/betreeMain_OpaqueScript.sml @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [betree_main]: opaque function definitions *) +(** [betree_main]: external function declarations *) open primitivesLib divDefLib open betreeMain_TypesTheory diff --git a/tests/hol4/hashmap_on_disk/hashmapMain_OpaqueScript.sml b/tests/hol4/hashmap_on_disk/hashmapMain_OpaqueScript.sml index 5f6bcbb4..c38eca01 100644 --- a/tests/hol4/hashmap_on_disk/hashmapMain_OpaqueScript.sml +++ b/tests/hol4/hashmap_on_disk/hashmapMain_OpaqueScript.sml @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [hashmap_main]: opaque function definitions *) +(** [hashmap_main]: external function declarations *) open primitivesLib divDefLib open hashmapMain_TypesTheory diff --git a/tests/hol4/misc-external/external_OpaqueScript.sml b/tests/hol4/misc-external/external_OpaqueScript.sml index e2fd281d..02efc2be 100644 --- a/tests/hol4/misc-external/external_OpaqueScript.sml +++ b/tests/hol4/misc-external/external_OpaqueScript.sml @@ -1,5 +1,5 @@ (** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *) -(** [external]: opaque function definitions *) +(** [external]: external function declarations *) open primitivesLib divDefLib open external_TypesTheory diff --git a/tests/lean/BetreeMain/ExternalFuns.lean b/tests/lean/BetreeMain/ExternalFuns.lean deleted file mode 100644 index 59beb514..00000000 --- a/tests/lean/BetreeMain/ExternalFuns.lean +++ /dev/null @@ -1,9 +0,0 @@ -import Base -import BetreeMain.Types -import BetreeMain.Opaque - -namespace BetreeMain - -def opaque_defs : OpaqueDefs := by sorry - -end BetreeMain diff --git a/tests/lean/BetreeMain/Funs.lean b/tests/lean/BetreeMain/Funs.lean index 2eb7fa1f..78e14146 100644 --- a/tests/lean/BetreeMain/Funs.lean +++ b/tests/lean/BetreeMain/Funs.lean @@ -2,59 +2,57 @@ -- [betree_main]: function definitions import Base import BetreeMain.Types -import BetreeMain.ExternalFuns +import BetreeMain.FunsExternal open Primitives - -namespace BetreeMain +namespace betree_main /- [betree_main::betree::load_internal_node] -/ -def betree_load_internal_node_fwd +def betree.load_internal_node_fwd (id : U64) (st : State) : Result (State × (betree_list_t (U64 × betree_message_t))) := - opaque_defs.betree_utils_load_internal_node_fwd id st + betree_utils.load_internal_node_fwd id st /- [betree_main::betree::store_internal_node] -/ -def betree_store_internal_node_fwd +def betree.store_internal_node_fwd (id : U64) (content : betree_list_t (U64 × betree_message_t)) (st : State) : Result (State × Unit) := do - let (st0, _) ← - opaque_defs.betree_utils_store_internal_node_fwd id content st + let (st0, _) ← betree_utils.store_internal_node_fwd id content st Result.ret (st0, ()) /- [betree_main::betree::load_leaf_node] -/ -def betree_load_leaf_node_fwd +def betree.load_leaf_node_fwd (id : U64) (st : State) : Result (State × (betree_list_t (U64 × U64))) := - opaque_defs.betree_utils_load_leaf_node_fwd id st + betree_utils.load_leaf_node_fwd id st /- [betree_main::betree::store_leaf_node] -/ -def betree_store_leaf_node_fwd +def betree.store_leaf_node_fwd (id : U64) (content : betree_list_t (U64 × U64)) (st : State) : Result (State × Unit) := do - let (st0, _) ← opaque_defs.betree_utils_store_leaf_node_fwd id content st + let (st0, _) ← betree_utils.store_leaf_node_fwd id content st Result.ret (st0, ()) /- [betree_main::betree::fresh_node_id] -/ -def betree_fresh_node_id_fwd (counter : U64) : Result U64 := +def betree.fresh_node_id_fwd (counter : U64) : Result U64 := do let _ ← counter + (U64.ofInt 1 (by intlit)) Result.ret counter /- [betree_main::betree::fresh_node_id] -/ -def betree_fresh_node_id_back (counter : U64) : Result U64 := +def betree.fresh_node_id_back (counter : U64) : Result U64 := counter + (U64.ofInt 1 (by intlit)) /- [betree_main::betree::NodeIdCounter::{0}::new] -/ -def betree_node_id_counter_new_fwd : Result betree_node_id_counter_t := +def betree.NodeIdCounter.new_fwd : Result betree_node_id_counter_t := Result.ret { betree_node_id_counter_next_node_id := (U64.ofInt 0 (by intlit)) } /- [betree_main::betree::NodeIdCounter::{0}::fresh_id] -/ -def betree_node_id_counter_fresh_id_fwd +def betree.NodeIdCounter.fresh_id_fwd (self : betree_node_id_counter_t) : Result U64 := do let _ ← self.betree_node_id_counter_next_node_id + @@ -62,7 +60,7 @@ def betree_node_id_counter_fresh_id_fwd Result.ret self.betree_node_id_counter_next_node_id /- [betree_main::betree::NodeIdCounter::{0}::fresh_id] -/ -def betree_node_id_counter_fresh_id_back +def betree.NodeIdCounter.fresh_id_back (self : betree_node_id_counter_t) : Result betree_node_id_counter_t := do let i ← self.betree_node_id_counter_next_node_id + @@ -75,7 +73,7 @@ def core_num_u64_max_body : Result U64 := def core_num_u64_max_c : U64 := eval_global core_num_u64_max_body (by simp) /- [betree_main::betree::upsert_update] -/ -def betree_upsert_update_fwd +def betree.upsert_update_fwd (prev : Option U64) (st : betree_upsert_fun_state_t) : Result U64 := match prev with | Option.none => @@ -96,17 +94,17 @@ def betree_upsert_update_fwd else Result.ret (U64.ofInt 0 (by intlit)) /- [betree_main::betree::List::{1}::len] -/ -divergent def betree_list_len_fwd +divergent def betree.List.len_fwd (T : Type) (self : betree_list_t T) : Result U64 := match self with | betree_list_t.Cons t tl => do - let i ← betree_list_len_fwd T tl + let i ← betree.List.len_fwd T tl (U64.ofInt 1 (by intlit)) + i | betree_list_t.Nil => Result.ret (U64.ofInt 0 (by intlit)) /- [betree_main::betree::List::{1}::split_at] -/ -divergent def betree_list_split_at_fwd +divergent def betree.List.split_at_fwd (T : Type) (self : betree_list_t T) (n : U64) : Result ((betree_list_t T) × (betree_list_t T)) := @@ -117,28 +115,28 @@ divergent def betree_list_split_at_fwd | betree_list_t.Cons hd tl => do let i ← n - (U64.ofInt 1 (by intlit)) - let p ← betree_list_split_at_fwd T tl i + let p ← betree.List.split_at_fwd T tl i let (ls0, ls1) := p let l := ls0 Result.ret (betree_list_t.Cons hd l, ls1) | betree_list_t.Nil => Result.fail Error.panic /- [betree_main::betree::List::{1}::push_front] -/ -def betree_list_push_front_fwd_back +def betree.List.push_front_fwd_back (T : Type) (self : betree_list_t T) (x : T) : Result (betree_list_t T) := let tl := mem_replace_fwd (betree_list_t T) self betree_list_t.Nil let l := tl Result.ret (betree_list_t.Cons x l) /- [betree_main::betree::List::{1}::pop_front] -/ -def betree_list_pop_front_fwd (T : Type) (self : betree_list_t T) : Result T := +def betree.List.pop_front_fwd (T : Type) (self : betree_list_t T) : Result T := let ls := mem_replace_fwd (betree_list_t T) self betree_list_t.Nil match ls with | betree_list_t.Cons x tl => Result.ret x | betree_list_t.Nil => Result.fail Error.panic /- [betree_main::betree::List::{1}::pop_front] -/ -def betree_list_pop_front_back +def betree.List.pop_front_back (T : Type) (self : betree_list_t T) : Result (betree_list_t T) := let ls := mem_replace_fwd (betree_list_t T) self betree_list_t.Nil match ls with @@ -146,13 +144,13 @@ def betree_list_pop_front_back | betree_list_t.Nil => Result.fail Error.panic /- [betree_main::betree::List::{1}::hd] -/ -def betree_list_hd_fwd (T : Type) (self : betree_list_t T) : Result T := +def betree.List.hd_fwd (T : Type) (self : betree_list_t T) : Result T := match self with | betree_list_t.Cons hd l => Result.ret hd | betree_list_t.Nil => Result.fail Error.panic /- [betree_main::betree::List::{2}::head_has_key] -/ -def betree_list_head_has_key_fwd +def betree.List.head_has_key_fwd (T : Type) (self : betree_list_t (U64 × T)) (key : U64) : Result Bool := match self with | betree_list_t.Cons hd l => let (i, _) := hd @@ -160,7 +158,7 @@ def betree_list_head_has_key_fwd | betree_list_t.Nil => Result.ret false /- [betree_main::betree::List::{2}::partition_at_pivot] -/ -divergent def betree_list_partition_at_pivot_fwd +divergent def betree.List.partition_at_pivot_fwd (T : Type) (self : betree_list_t (U64 × T)) (pivot : U64) : Result ((betree_list_t (U64 × T)) × (betree_list_t (U64 × T))) := @@ -171,14 +169,14 @@ divergent def betree_list_partition_at_pivot_fwd then Result.ret (betree_list_t.Nil, betree_list_t.Cons (i, t) tl) else do - let p ← betree_list_partition_at_pivot_fwd T tl pivot + let p ← betree.List.partition_at_pivot_fwd T tl pivot let (ls0, ls1) := p let l := ls0 Result.ret (betree_list_t.Cons (i, t) l, ls1) | betree_list_t.Nil => Result.ret (betree_list_t.Nil, betree_list_t.Nil) /- [betree_main::betree::Leaf::{3}::split] -/ -def betree_leaf_split_fwd +def betree.Leaf.split_fwd (self : betree_leaf_t) (content : betree_list_t (U64 × U64)) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (st : State) : @@ -186,16 +184,16 @@ def betree_leaf_split_fwd := do let p ← - betree_list_split_at_fwd (U64 × U64) content + betree.List.split_at_fwd (U64 × U64) content params.betree_params_split_size let (content0, content1) := p - let p0 ← betree_list_hd_fwd (U64 × U64) content1 + let p0 ← betree.List.hd_fwd (U64 × U64) content1 let (pivot, _) := p0 - let id0 ← betree_node_id_counter_fresh_id_fwd node_id_cnt - let node_id_cnt0 ← betree_node_id_counter_fresh_id_back node_id_cnt - let id1 ← betree_node_id_counter_fresh_id_fwd node_id_cnt0 - let (st0, _) ← betree_store_leaf_node_fwd id0 content0 st - let (st1, _) ← betree_store_leaf_node_fwd id1 content1 st0 + let id0 ← betree.NodeIdCounter.fresh_id_fwd node_id_cnt + let node_id_cnt0 ← betree.NodeIdCounter.fresh_id_back node_id_cnt + let id1 ← betree.NodeIdCounter.fresh_id_fwd node_id_cnt0 + let (st0, _) ← betree.store_leaf_node_fwd id0 content0 st + let (st1, _) ← betree.store_leaf_node_fwd id1 content1 st0 let n := betree_node_t.Leaf { betree_leaf_id := id0, @@ -209,7 +207,7 @@ def betree_leaf_split_fwd Result.ret (st1, betree_internal_t.mk self.betree_leaf_id pivot n n0) /- [betree_main::betree::Leaf::{3}::split] -/ -def betree_leaf_split_back +def betree.Leaf.split_back (self : betree_leaf_t) (content : betree_list_t (U64 × U64)) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (st : State) : @@ -217,19 +215,19 @@ def betree_leaf_split_back := do let p ← - betree_list_split_at_fwd (U64 × U64) content + betree.List.split_at_fwd (U64 × U64) content params.betree_params_split_size let (content0, content1) := p - let _ ← betree_list_hd_fwd (U64 × U64) content1 - let id0 ← betree_node_id_counter_fresh_id_fwd node_id_cnt - let node_id_cnt0 ← betree_node_id_counter_fresh_id_back node_id_cnt - let id1 ← betree_node_id_counter_fresh_id_fwd node_id_cnt0 - let (st0, _) ← betree_store_leaf_node_fwd id0 content0 st - let _ ← betree_store_leaf_node_fwd id1 content1 st0 - betree_node_id_counter_fresh_id_back node_id_cnt0 + let _ ← betree.List.hd_fwd (U64 × U64) content1 + let id0 ← betree.NodeIdCounter.fresh_id_fwd node_id_cnt + let node_id_cnt0 ← betree.NodeIdCounter.fresh_id_back node_id_cnt + let id1 ← betree.NodeIdCounter.fresh_id_fwd node_id_cnt0 + let (st0, _) ← betree.store_leaf_node_fwd id0 content0 st + let _ ← betree.store_leaf_node_fwd id1 content1 st0 + betree.NodeIdCounter.fresh_id_back node_id_cnt0 /- [betree_main::betree::Node::{5}::lookup_in_bindings] -/ -divergent def betree_node_lookup_in_bindings_fwd +divergent def betree.Node.lookup_in_bindings_fwd (key : U64) (bindings : betree_list_t (U64 × U64)) : Result (Option U64) := match bindings with | betree_list_t.Cons hd tl => @@ -239,11 +237,11 @@ divergent def betree_node_lookup_in_bindings_fwd else if i > key then Result.ret Option.none - else betree_node_lookup_in_bindings_fwd key tl + else betree.Node.lookup_in_bindings_fwd key tl | betree_list_t.Nil => Result.ret Option.none /- [betree_main::betree::Node::{5}::lookup_first_message_for_key] -/ -divergent def betree_node_lookup_first_message_for_key_fwd +divergent def betree.Node.lookup_first_message_for_key_fwd (key : U64) (msgs : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) := @@ -252,11 +250,11 @@ divergent def betree_node_lookup_first_message_for_key_fwd let (i, m) := x if i >= key then Result.ret (betree_list_t.Cons (i, m) next_msgs) - else betree_node_lookup_first_message_for_key_fwd key next_msgs + else betree.Node.lookup_first_message_for_key_fwd key next_msgs | betree_list_t.Nil => Result.ret betree_list_t.Nil /- [betree_main::betree::Node::{5}::lookup_first_message_for_key] -/ -divergent def betree_node_lookup_first_message_for_key_back +divergent def betree.Node.lookup_first_message_for_key_back (key : U64) (msgs : betree_list_t (U64 × betree_message_t)) (ret0 : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) @@ -269,70 +267,70 @@ divergent def betree_node_lookup_first_message_for_key_back else do let next_msgs0 ← - betree_node_lookup_first_message_for_key_back key next_msgs ret0 + betree.Node.lookup_first_message_for_key_back key next_msgs ret0 Result.ret (betree_list_t.Cons (i, m) next_msgs0) | betree_list_t.Nil => Result.ret ret0 /- [betree_main::betree::Node::{5}::apply_upserts] -/ -divergent def betree_node_apply_upserts_fwd +divergent def betree.Node.apply_upserts_fwd (msgs : betree_list_t (U64 × betree_message_t)) (prev : Option U64) (key : U64) (st : State) : Result (State × U64) := do - let b ← betree_list_head_has_key_fwd betree_message_t msgs key + let b ← betree.List.head_has_key_fwd betree_message_t msgs key if b then do - let msg ← betree_list_pop_front_fwd (U64 × betree_message_t) msgs + let msg ← betree.List.pop_front_fwd (U64 × betree_message_t) msgs let (_, m) := msg match m with | betree_message_t.Insert i => Result.fail Error.panic | betree_message_t.Delete => Result.fail Error.panic | betree_message_t.Upsert s => do - let v ← betree_upsert_update_fwd prev s + let v ← betree.upsert_update_fwd prev s let msgs0 ← - betree_list_pop_front_back (U64 × betree_message_t) msgs - betree_node_apply_upserts_fwd msgs0 (Option.some v) key st + betree.List.pop_front_back (U64 × betree_message_t) msgs + betree.Node.apply_upserts_fwd msgs0 (Option.some v) key st else do - let (st0, v) ← opaque_defs.core_option_option_unwrap_fwd U64 prev st + let (st0, v) ← core.option.Option.unwrap_fwd U64 prev st let _ ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs (key, + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs (key, betree_message_t.Insert v) Result.ret (st0, v) /- [betree_main::betree::Node::{5}::apply_upserts] -/ -divergent def betree_node_apply_upserts_back +divergent def betree.Node.apply_upserts_back (msgs : betree_list_t (U64 × betree_message_t)) (prev : Option U64) (key : U64) (st : State) : Result (betree_list_t (U64 × betree_message_t)) := do - let b ← betree_list_head_has_key_fwd betree_message_t msgs key + let b ← betree.List.head_has_key_fwd betree_message_t msgs key if b then do - let msg ← betree_list_pop_front_fwd (U64 × betree_message_t) msgs + let msg ← betree.List.pop_front_fwd (U64 × betree_message_t) msgs let (_, m) := msg match m with | betree_message_t.Insert i => Result.fail Error.panic | betree_message_t.Delete => Result.fail Error.panic | betree_message_t.Upsert s => do - let v ← betree_upsert_update_fwd prev s + let v ← betree.upsert_update_fwd prev s let msgs0 ← - betree_list_pop_front_back (U64 × betree_message_t) msgs - betree_node_apply_upserts_back msgs0 (Option.some v) key st + betree.List.pop_front_back (U64 × betree_message_t) msgs + betree.Node.apply_upserts_back msgs0 (Option.some v) key st else do - let (_, v) ← opaque_defs.core_option_option_unwrap_fwd U64 prev st - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs (key, + let (_, v) ← core.option.Option.unwrap_fwd U64 prev st + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs (key, betree_message_t.Insert v) /- [betree_main::betree::Node::{5}::lookup] -/ -mutual divergent def betree_node_lookup_fwd +mutual divergent def betree.Node.lookup_fwd (self : betree_node_t) (key : U64) (st : State) : Result (State × (Option U64)) := @@ -340,8 +338,8 @@ mutual divergent def betree_node_lookup_fwd | betree_node_t.Internal node => do let ⟨ i, i0, n, n0 ⟩ := node - let (st0, msgs) ← betree_load_internal_node_fwd i st - let pending ← betree_node_lookup_first_message_for_key_fwd key msgs + let (st0, msgs) ← betree.load_internal_node_fwd i st + let pending ← betree.Node.lookup_first_message_for_key_fwd key msgs match pending with | betree_list_t.Cons p l => let (k, msg) := p @@ -349,10 +347,10 @@ mutual divergent def betree_node_lookup_fwd then do let (st1, opt) ← - betree_internal_lookup_in_children_fwd (betree_internal_t.mk i i0 + betree.Internal.lookup_in_children_fwd (betree_internal_t.mk i i0 n n0) key st0 let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, msg) l) Result.ret (st1, opt) else @@ -360,58 +358,58 @@ mutual divergent def betree_node_lookup_fwd | betree_message_t.Insert v => do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, betree_message_t.Insert v) l) Result.ret (st0, Option.some v) | betree_message_t.Delete => do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, betree_message_t.Delete) l) Result.ret (st0, Option.none) | betree_message_t.Upsert ufs => do let (st1, v) ← - betree_internal_lookup_in_children_fwd (betree_internal_t.mk i + betree.Internal.lookup_in_children_fwd (betree_internal_t.mk i i0 n n0) key st0 let (st2, v0) ← - betree_node_apply_upserts_fwd (betree_list_t.Cons (k, + betree.Node.apply_upserts_fwd (betree_list_t.Cons (k, betree_message_t.Upsert ufs) l) v key st1 let node0 ← - betree_internal_lookup_in_children_back (betree_internal_t.mk i + betree.Internal.lookup_in_children_back (betree_internal_t.mk i i0 n n0) key st0 let ⟨ i1, _, _, _ ⟩ := node0 let pending0 ← - betree_node_apply_upserts_back (betree_list_t.Cons (k, + betree.Node.apply_upserts_back (betree_list_t.Cons (k, betree_message_t.Upsert ufs) l) v key st1 let msgs0 ← - betree_node_lookup_first_message_for_key_back key msgs pending0 - let (st3, _) ← betree_store_internal_node_fwd i1 msgs0 st2 + betree.Node.lookup_first_message_for_key_back key msgs pending0 + let (st3, _) ← betree.store_internal_node_fwd i1 msgs0 st2 Result.ret (st3, Option.some v0) | betree_list_t.Nil => do let (st1, opt) ← - betree_internal_lookup_in_children_fwd (betree_internal_t.mk i i0 n + betree.Internal.lookup_in_children_fwd (betree_internal_t.mk i i0 n n0) key st0 let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs betree_list_t.Nil Result.ret (st1, opt) | betree_node_t.Leaf node => do - let (st0, bindings) ← betree_load_leaf_node_fwd node.betree_leaf_id st - let opt ← betree_node_lookup_in_bindings_fwd key bindings + let (st0, bindings) ← betree.load_leaf_node_fwd node.betree_leaf_id st + let opt ← betree.Node.lookup_in_bindings_fwd key bindings Result.ret (st0, opt) /- [betree_main::betree::Node::{5}::lookup] -/ -divergent def betree_node_lookup_back +divergent def betree.Node.lookup_back (self : betree_node_t) (key : U64) (st : State) : Result betree_node_t := match self with | betree_node_t.Internal node => do let ⟨ i, i0, n, n0 ⟩ := node - let (st0, msgs) ← betree_load_internal_node_fwd i st - let pending ← betree_node_lookup_first_message_for_key_fwd key msgs + let (st0, msgs) ← betree.load_internal_node_fwd i st + let pending ← betree.Node.lookup_first_message_for_key_fwd key msgs match pending with | betree_list_t.Cons p l => let (k, msg) := p @@ -419,10 +417,10 @@ divergent def betree_node_lookup_back then do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, msg) l) let node0 ← - betree_internal_lookup_in_children_back (betree_internal_t.mk i + betree.Internal.lookup_in_children_back (betree_internal_t.mk i i0 n n0) key st0 Result.ret (betree_node_t.Internal node0) else @@ -430,64 +428,64 @@ divergent def betree_node_lookup_back | betree_message_t.Insert v => do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, betree_message_t.Insert v) l) Result.ret (betree_node_t.Internal (betree_internal_t.mk i i0 n n0)) | betree_message_t.Delete => do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs (betree_list_t.Cons (k, betree_message_t.Delete) l) Result.ret (betree_node_t.Internal (betree_internal_t.mk i i0 n n0)) | betree_message_t.Upsert ufs => do let (st1, v) ← - betree_internal_lookup_in_children_fwd (betree_internal_t.mk i + betree.Internal.lookup_in_children_fwd (betree_internal_t.mk i i0 n n0) key st0 let (st2, _) ← - betree_node_apply_upserts_fwd (betree_list_t.Cons (k, + betree.Node.apply_upserts_fwd (betree_list_t.Cons (k, betree_message_t.Upsert ufs) l) v key st1 let node0 ← - betree_internal_lookup_in_children_back (betree_internal_t.mk i + betree.Internal.lookup_in_children_back (betree_internal_t.mk i i0 n n0) key st0 let ⟨ i1, i2, n1, n2 ⟩ := node0 let pending0 ← - betree_node_apply_upserts_back (betree_list_t.Cons (k, + betree.Node.apply_upserts_back (betree_list_t.Cons (k, betree_message_t.Upsert ufs) l) v key st1 let msgs0 ← - betree_node_lookup_first_message_for_key_back key msgs pending0 - let _ ← betree_store_internal_node_fwd i1 msgs0 st2 + betree.Node.lookup_first_message_for_key_back key msgs pending0 + let _ ← betree.store_internal_node_fwd i1 msgs0 st2 Result.ret (betree_node_t.Internal (betree_internal_t.mk i1 i2 n1 n2)) | betree_list_t.Nil => do let _ ← - betree_node_lookup_first_message_for_key_back key msgs + betree.Node.lookup_first_message_for_key_back key msgs betree_list_t.Nil let node0 ← - betree_internal_lookup_in_children_back (betree_internal_t.mk i i0 + betree.Internal.lookup_in_children_back (betree_internal_t.mk i i0 n n0) key st0 Result.ret (betree_node_t.Internal node0) | betree_node_t.Leaf node => do - let (_, bindings) ← betree_load_leaf_node_fwd node.betree_leaf_id st - let _ ← betree_node_lookup_in_bindings_fwd key bindings + let (_, bindings) ← betree.load_leaf_node_fwd node.betree_leaf_id st + let _ ← betree.Node.lookup_in_bindings_fwd key bindings Result.ret (betree_node_t.Leaf node) /- [betree_main::betree::Internal::{4}::lookup_in_children] -/ -divergent def betree_internal_lookup_in_children_fwd +divergent def betree.Internal.lookup_in_children_fwd (self : betree_internal_t) (key : U64) (st : State) : Result (State × (Option U64)) := let ⟨ _, i, n, n0 ⟩ := self if key < i - then betree_node_lookup_fwd n key st - else betree_node_lookup_fwd n0 key st + then betree.Node.lookup_fwd n key st + else betree.Node.lookup_fwd n0 key st /- [betree_main::betree::Internal::{4}::lookup_in_children] -/ -divergent def betree_internal_lookup_in_children_back +divergent def betree.Internal.lookup_in_children_back (self : betree_internal_t) (key : U64) (st : State) : Result betree_internal_t := @@ -495,17 +493,17 @@ divergent def betree_internal_lookup_in_children_back if key < i0 then do - let n1 ← betree_node_lookup_back n key st + let n1 ← betree.Node.lookup_back n key st Result.ret (betree_internal_t.mk i i0 n1 n0) else do - let n1 ← betree_node_lookup_back n0 key st + let n1 ← betree.Node.lookup_back n0 key st Result.ret (betree_internal_t.mk i i0 n n1) end /- [betree_main::betree::Node::{5}::lookup_mut_in_bindings] -/ -divergent def betree_node_lookup_mut_in_bindings_fwd +divergent def betree.Node.lookup_mut_in_bindings_fwd (key : U64) (bindings : betree_list_t (U64 × U64)) : Result (betree_list_t (U64 × U64)) := @@ -514,11 +512,11 @@ divergent def betree_node_lookup_mut_in_bindings_fwd let (i, i0) := hd if i >= key then Result.ret (betree_list_t.Cons (i, i0) tl) - else betree_node_lookup_mut_in_bindings_fwd key tl + else betree.Node.lookup_mut_in_bindings_fwd key tl | betree_list_t.Nil => Result.ret betree_list_t.Nil /- [betree_main::betree::Node::{5}::lookup_mut_in_bindings] -/ -divergent def betree_node_lookup_mut_in_bindings_back +divergent def betree.Node.lookup_mut_in_bindings_back (key : U64) (bindings : betree_list_t (U64 × U64)) (ret0 : betree_list_t (U64 × U64)) : Result (betree_list_t (U64 × U64)) @@ -530,60 +528,60 @@ divergent def betree_node_lookup_mut_in_bindings_back then Result.ret ret0 else do - let tl0 ← betree_node_lookup_mut_in_bindings_back key tl ret0 + let tl0 ← betree.Node.lookup_mut_in_bindings_back key tl ret0 Result.ret (betree_list_t.Cons (i, i0) tl0) | betree_list_t.Nil => Result.ret ret0 /- [betree_main::betree::Node::{5}::apply_to_leaf] -/ -def betree_node_apply_to_leaf_fwd_back +def betree.Node.apply_to_leaf_fwd_back (bindings : betree_list_t (U64 × U64)) (key : U64) (new_msg : betree_message_t) : Result (betree_list_t (U64 × U64)) := do - let bindings0 ← betree_node_lookup_mut_in_bindings_fwd key bindings - let b ← betree_list_head_has_key_fwd U64 bindings0 key + let bindings0 ← betree.Node.lookup_mut_in_bindings_fwd key bindings + let b ← betree.List.head_has_key_fwd U64 bindings0 key if b then do - let hd ← betree_list_pop_front_fwd (U64 × U64) bindings0 + let hd ← betree.List.pop_front_fwd (U64 × U64) bindings0 match new_msg with | betree_message_t.Insert v => do - let bindings1 ← betree_list_pop_front_back (U64 × U64) bindings0 + let bindings1 ← betree.List.pop_front_back (U64 × U64) bindings0 let bindings2 ← - betree_list_push_front_fwd_back (U64 × U64) bindings1 (key, v) - betree_node_lookup_mut_in_bindings_back key bindings bindings2 + betree.List.push_front_fwd_back (U64 × U64) bindings1 (key, v) + betree.Node.lookup_mut_in_bindings_back key bindings bindings2 | betree_message_t.Delete => do - let bindings1 ← betree_list_pop_front_back (U64 × U64) bindings0 - betree_node_lookup_mut_in_bindings_back key bindings bindings1 + let bindings1 ← betree.List.pop_front_back (U64 × U64) bindings0 + betree.Node.lookup_mut_in_bindings_back key bindings bindings1 | betree_message_t.Upsert s => do let (_, i) := hd - let v ← betree_upsert_update_fwd (Option.some i) s - let bindings1 ← betree_list_pop_front_back (U64 × U64) bindings0 + let v ← betree.upsert_update_fwd (Option.some i) s + let bindings1 ← betree.List.pop_front_back (U64 × U64) bindings0 let bindings2 ← - betree_list_push_front_fwd_back (U64 × U64) bindings1 (key, v) - betree_node_lookup_mut_in_bindings_back key bindings bindings2 + betree.List.push_front_fwd_back (U64 × U64) bindings1 (key, v) + betree.Node.lookup_mut_in_bindings_back key bindings bindings2 else match new_msg with | betree_message_t.Insert v => do let bindings1 ← - betree_list_push_front_fwd_back (U64 × U64) bindings0 (key, v) - betree_node_lookup_mut_in_bindings_back key bindings bindings1 + betree.List.push_front_fwd_back (U64 × U64) bindings0 (key, v) + betree.Node.lookup_mut_in_bindings_back key bindings bindings1 | betree_message_t.Delete => - betree_node_lookup_mut_in_bindings_back key bindings bindings0 + betree.Node.lookup_mut_in_bindings_back key bindings bindings0 | betree_message_t.Upsert s => do - let v ← betree_upsert_update_fwd Option.none s + let v ← betree.upsert_update_fwd Option.none s let bindings1 ← - betree_list_push_front_fwd_back (U64 × U64) bindings0 (key, v) - betree_node_lookup_mut_in_bindings_back key bindings bindings1 + betree.List.push_front_fwd_back (U64 × U64) bindings0 (key, v) + betree.Node.lookup_mut_in_bindings_back key bindings bindings1 /- [betree_main::betree::Node::{5}::apply_messages_to_leaf] -/ -divergent def betree_node_apply_messages_to_leaf_fwd_back +divergent def betree.Node.apply_messages_to_leaf_fwd_back (bindings : betree_list_t (U64 × U64)) (new_msgs : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × U64)) @@ -592,12 +590,12 @@ divergent def betree_node_apply_messages_to_leaf_fwd_back | betree_list_t.Cons new_msg new_msgs_tl => do let (i, m) := new_msg - let bindings0 ← betree_node_apply_to_leaf_fwd_back bindings i m - betree_node_apply_messages_to_leaf_fwd_back bindings0 new_msgs_tl + let bindings0 ← betree.Node.apply_to_leaf_fwd_back bindings i m + betree.Node.apply_messages_to_leaf_fwd_back bindings0 new_msgs_tl | betree_list_t.Nil => Result.ret bindings /- [betree_main::betree::Node::{5}::filter_messages_for_key] -/ -divergent def betree_node_filter_messages_for_key_fwd_back +divergent def betree.Node.filter_messages_for_key_fwd_back (key : U64) (msgs : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) := @@ -608,14 +606,14 @@ divergent def betree_node_filter_messages_for_key_fwd_back then do let msgs0 ← - betree_list_pop_front_back (U64 × betree_message_t) + betree.List.pop_front_back (U64 × betree_message_t) (betree_list_t.Cons (k, m) l) - betree_node_filter_messages_for_key_fwd_back key msgs0 + betree.Node.filter_messages_for_key_fwd_back key msgs0 else Result.ret (betree_list_t.Cons (k, m) l) | betree_list_t.Nil => Result.ret betree_list_t.Nil /- [betree_main::betree::Node::{5}::lookup_first_message_after_key] -/ -divergent def betree_node_lookup_first_message_after_key_fwd +divergent def betree.Node.lookup_first_message_after_key_fwd (key : U64) (msgs : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) := @@ -623,12 +621,12 @@ divergent def betree_node_lookup_first_message_after_key_fwd | betree_list_t.Cons p next_msgs => let (k, m) := p if k = key - then betree_node_lookup_first_message_after_key_fwd key next_msgs + then betree.Node.lookup_first_message_after_key_fwd key next_msgs else Result.ret (betree_list_t.Cons (k, m) next_msgs) | betree_list_t.Nil => Result.ret betree_list_t.Nil /- [betree_main::betree::Node::{5}::lookup_first_message_after_key] -/ -divergent def betree_node_lookup_first_message_after_key_back +divergent def betree.Node.lookup_first_message_after_key_back (key : U64) (msgs : betree_list_t (U64 × betree_message_t)) (ret0 : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) @@ -640,79 +638,79 @@ divergent def betree_node_lookup_first_message_after_key_back then do let next_msgs0 ← - betree_node_lookup_first_message_after_key_back key next_msgs ret0 + betree.Node.lookup_first_message_after_key_back key next_msgs ret0 Result.ret (betree_list_t.Cons (k, m) next_msgs0) else Result.ret ret0 | betree_list_t.Nil => Result.ret ret0 /- [betree_main::betree::Node::{5}::apply_to_internal] -/ -def betree_node_apply_to_internal_fwd_back +def betree.Node.apply_to_internal_fwd_back (msgs : betree_list_t (U64 × betree_message_t)) (key : U64) (new_msg : betree_message_t) : Result (betree_list_t (U64 × betree_message_t)) := do - let msgs0 ← betree_node_lookup_first_message_for_key_fwd key msgs - let b ← betree_list_head_has_key_fwd betree_message_t msgs0 key + let msgs0 ← betree.Node.lookup_first_message_for_key_fwd key msgs + let b ← betree.List.head_has_key_fwd betree_message_t msgs0 key if b then match new_msg with | betree_message_t.Insert i => do - let msgs1 ← betree_node_filter_messages_for_key_fwd_back key msgs0 + let msgs1 ← betree.Node.filter_messages_for_key_fwd_back key msgs0 let msgs2 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs1 + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs1 (key, betree_message_t.Insert i) - betree_node_lookup_first_message_for_key_back key msgs msgs2 + betree.Node.lookup_first_message_for_key_back key msgs msgs2 | betree_message_t.Delete => do - let msgs1 ← betree_node_filter_messages_for_key_fwd_back key msgs0 + let msgs1 ← betree.Node.filter_messages_for_key_fwd_back key msgs0 let msgs2 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs1 + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs1 (key, betree_message_t.Delete) - betree_node_lookup_first_message_for_key_back key msgs msgs2 + betree.Node.lookup_first_message_for_key_back key msgs msgs2 | betree_message_t.Upsert s => do - let p ← betree_list_hd_fwd (U64 × betree_message_t) msgs0 + let p ← betree.List.hd_fwd (U64 × betree_message_t) msgs0 let (_, m) := p match m with | betree_message_t.Insert prev => do - let v ← betree_upsert_update_fwd (Option.some prev) s + let v ← betree.upsert_update_fwd (Option.some prev) s let msgs1 ← - betree_list_pop_front_back (U64 × betree_message_t) msgs0 + betree.List.pop_front_back (U64 × betree_message_t) msgs0 let msgs2 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs1 + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs1 (key, betree_message_t.Insert v) - betree_node_lookup_first_message_for_key_back key msgs msgs2 + betree.Node.lookup_first_message_for_key_back key msgs msgs2 | betree_message_t.Delete => do - let v ← betree_upsert_update_fwd Option.none s + let v ← betree.upsert_update_fwd Option.none s let msgs1 ← - betree_list_pop_front_back (U64 × betree_message_t) msgs0 + betree.List.pop_front_back (U64 × betree_message_t) msgs0 let msgs2 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs1 + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs1 (key, betree_message_t.Insert v) - betree_node_lookup_first_message_for_key_back key msgs msgs2 + betree.Node.lookup_first_message_for_key_back key msgs msgs2 | betree_message_t.Upsert ufs => do let msgs1 ← - betree_node_lookup_first_message_after_key_fwd key msgs0 + betree.Node.lookup_first_message_after_key_fwd key msgs0 let msgs2 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs1 + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs1 (key, betree_message_t.Upsert s) let msgs3 ← - betree_node_lookup_first_message_after_key_back key msgs0 msgs2 - betree_node_lookup_first_message_for_key_back key msgs msgs3 + betree.Node.lookup_first_message_after_key_back key msgs0 msgs2 + betree.Node.lookup_first_message_for_key_back key msgs msgs3 else do let msgs1 ← - betree_list_push_front_fwd_back (U64 × betree_message_t) msgs0 (key, + betree.List.push_front_fwd_back (U64 × betree_message_t) msgs0 (key, new_msg) - betree_node_lookup_first_message_for_key_back key msgs msgs1 + betree.Node.lookup_first_message_for_key_back key msgs msgs1 /- [betree_main::betree::Node::{5}::apply_messages_to_internal] -/ -divergent def betree_node_apply_messages_to_internal_fwd_back +divergent def betree.Node.apply_messages_to_internal_fwd_back (msgs : betree_list_t (U64 × betree_message_t)) (new_msgs : betree_list_t (U64 × betree_message_t)) : Result (betree_list_t (U64 × betree_message_t)) @@ -721,12 +719,12 @@ divergent def betree_node_apply_messages_to_internal_fwd_back | betree_list_t.Cons new_msg new_msgs_tl => do let (i, m) := new_msg - let msgs0 ← betree_node_apply_to_internal_fwd_back msgs i m - betree_node_apply_messages_to_internal_fwd_back msgs0 new_msgs_tl + let msgs0 ← betree.Node.apply_to_internal_fwd_back msgs i m + betree.Node.apply_messages_to_internal_fwd_back msgs0 new_msgs_tl | betree_list_t.Nil => Result.ret msgs /- [betree_main::betree::Node::{5}::apply_messages] -/ -mutual divergent def betree_node_apply_messages_fwd +mutual divergent def betree.Node.apply_messages_fwd (self : betree_node_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (msgs : betree_list_t (U64 × betree_message_t)) (st : State) : @@ -736,49 +734,49 @@ mutual divergent def betree_node_apply_messages_fwd | betree_node_t.Internal node => do let ⟨ i, i0, n, n0 ⟩ := node - let (st0, content) ← betree_load_internal_node_fwd i st + let (st0, content) ← betree.load_internal_node_fwd i st let content0 ← - betree_node_apply_messages_to_internal_fwd_back content msgs - let num_msgs ← betree_list_len_fwd (U64 × betree_message_t) content0 + betree.Node.apply_messages_to_internal_fwd_back content msgs + let num_msgs ← betree.List.len_fwd (U64 × betree_message_t) content0 if num_msgs >= params.betree_params_min_flush_size then do let (st1, content1) ← - betree_internal_flush_fwd (betree_internal_t.mk i i0 n n0) params + betree.Internal.flush_fwd (betree_internal_t.mk i i0 n n0) params node_id_cnt content0 st0 let (node0, _) ← - betree_internal_flush_back (betree_internal_t.mk i i0 n n0) params + betree.Internal.flush_back (betree_internal_t.mk i i0 n n0) params node_id_cnt content0 st0 let ⟨ i1, _, _, _ ⟩ := node0 - let (st2, _) ← betree_store_internal_node_fwd i1 content1 st1 + let (st2, _) ← betree.store_internal_node_fwd i1 content1 st1 Result.ret (st2, ()) else do - let (st1, _) ← betree_store_internal_node_fwd i content0 st0 + let (st1, _) ← betree.store_internal_node_fwd i content0 st0 Result.ret (st1, ()) | betree_node_t.Leaf node => do - let (st0, content) ← betree_load_leaf_node_fwd node.betree_leaf_id st - let content0 ← betree_node_apply_messages_to_leaf_fwd_back content msgs - let len ← betree_list_len_fwd (U64 × U64) content0 + let (st0, content) ← betree.load_leaf_node_fwd node.betree_leaf_id st + let content0 ← betree.Node.apply_messages_to_leaf_fwd_back content msgs + let len ← betree.List.len_fwd (U64 × U64) content0 let i ← (U64.ofInt 2 (by intlit)) * params.betree_params_split_size if len >= i then do let (st1, _) ← - betree_leaf_split_fwd node content0 params node_id_cnt st0 + betree.Leaf.split_fwd node content0 params node_id_cnt st0 let (st2, _) ← - betree_store_leaf_node_fwd node.betree_leaf_id betree_list_t.Nil + betree.store_leaf_node_fwd node.betree_leaf_id betree_list_t.Nil st1 Result.ret (st2, ()) else do let (st1, _) ← - betree_store_leaf_node_fwd node.betree_leaf_id content0 st0 + betree.store_leaf_node_fwd node.betree_leaf_id content0 st0 Result.ret (st1, ()) /- [betree_main::betree::Node::{5}::apply_messages] -/ -divergent def betree_node_apply_messages_back +divergent def betree.Node.apply_messages_back (self : betree_node_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (msgs : betree_list_t (U64 × betree_message_t)) (st : State) : @@ -788,53 +786,53 @@ divergent def betree_node_apply_messages_back | betree_node_t.Internal node => do let ⟨ i, i0, n, n0 ⟩ := node - let (st0, content) ← betree_load_internal_node_fwd i st + let (st0, content) ← betree.load_internal_node_fwd i st let content0 ← - betree_node_apply_messages_to_internal_fwd_back content msgs - let num_msgs ← betree_list_len_fwd (U64 × betree_message_t) content0 + betree.Node.apply_messages_to_internal_fwd_back content msgs + let num_msgs ← betree.List.len_fwd (U64 × betree_message_t) content0 if num_msgs >= params.betree_params_min_flush_size then do let (st1, content1) ← - betree_internal_flush_fwd (betree_internal_t.mk i i0 n n0) params + betree.Internal.flush_fwd (betree_internal_t.mk i i0 n n0) params node_id_cnt content0 st0 let (node0, node_id_cnt0) ← - betree_internal_flush_back (betree_internal_t.mk i i0 n n0) params + betree.Internal.flush_back (betree_internal_t.mk i i0 n n0) params node_id_cnt content0 st0 let ⟨ i1, i2, n1, n2 ⟩ := node0 - let _ ← betree_store_internal_node_fwd i1 content1 st1 + let _ ← betree.store_internal_node_fwd i1 content1 st1 Result.ret (betree_node_t.Internal (betree_internal_t.mk i1 i2 n1 n2), node_id_cnt0) else do - let _ ← betree_store_internal_node_fwd i content0 st0 + let _ ← betree.store_internal_node_fwd i content0 st0 Result.ret (betree_node_t.Internal (betree_internal_t.mk i i0 n n0), node_id_cnt) | betree_node_t.Leaf node => do - let (st0, content) ← betree_load_leaf_node_fwd node.betree_leaf_id st - let content0 ← betree_node_apply_messages_to_leaf_fwd_back content msgs - let len ← betree_list_len_fwd (U64 × U64) content0 + let (st0, content) ← betree.load_leaf_node_fwd node.betree_leaf_id st + let content0 ← betree.Node.apply_messages_to_leaf_fwd_back content msgs + let len ← betree.List.len_fwd (U64 × U64) content0 let i ← (U64.ofInt 2 (by intlit)) * params.betree_params_split_size if len >= i then do let (st1, new_node) ← - betree_leaf_split_fwd node content0 params node_id_cnt st0 + betree.Leaf.split_fwd node content0 params node_id_cnt st0 let _ ← - betree_store_leaf_node_fwd node.betree_leaf_id betree_list_t.Nil + betree.store_leaf_node_fwd node.betree_leaf_id betree_list_t.Nil st1 let node_id_cnt0 ← - betree_leaf_split_back node content0 params node_id_cnt st0 + betree.Leaf.split_back node content0 params node_id_cnt st0 Result.ret (betree_node_t.Internal new_node, node_id_cnt0) else do - let _ ← betree_store_leaf_node_fwd node.betree_leaf_id content0 st0 + let _ ← betree.store_leaf_node_fwd node.betree_leaf_id content0 st0 Result.ret (betree_node_t.Leaf { node with betree_leaf_size := len }, node_id_cnt) /- [betree_main::betree::Internal::{4}::flush] -/ -divergent def betree_internal_flush_fwd +divergent def betree.Internal.flush_fwd (self : betree_internal_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (content : betree_list_t (U64 × betree_message_t)) (st : State) : @@ -842,39 +840,39 @@ divergent def betree_internal_flush_fwd := do let ⟨ _, i, n, n0 ⟩ := self - let p ← betree_list_partition_at_pivot_fwd betree_message_t content i + let p ← betree.List.partition_at_pivot_fwd betree_message_t content i let (msgs_left, msgs_right) := p - let len_left ← betree_list_len_fwd (U64 × betree_message_t) msgs_left + let len_left ← betree.List.len_fwd (U64 × betree_message_t) msgs_left if len_left >= params.betree_params_min_flush_size then do let (st0, _) ← - betree_node_apply_messages_fwd n params node_id_cnt msgs_left st + betree.Node.apply_messages_fwd n params node_id_cnt msgs_left st let (_, node_id_cnt0) ← - betree_node_apply_messages_back n params node_id_cnt msgs_left st + betree.Node.apply_messages_back n params node_id_cnt msgs_left st let len_right ← - betree_list_len_fwd (U64 × betree_message_t) msgs_right + betree.List.len_fwd (U64 × betree_message_t) msgs_right if len_right >= params.betree_params_min_flush_size then do let (st1, _) ← - betree_node_apply_messages_fwd n0 params node_id_cnt0 msgs_right + betree.Node.apply_messages_fwd n0 params node_id_cnt0 msgs_right st0 let _ ← - betree_node_apply_messages_back n0 params node_id_cnt0 msgs_right + betree.Node.apply_messages_back n0 params node_id_cnt0 msgs_right st0 Result.ret (st1, betree_list_t.Nil) else Result.ret (st0, msgs_right) else do let (st0, _) ← - betree_node_apply_messages_fwd n0 params node_id_cnt msgs_right st + betree.Node.apply_messages_fwd n0 params node_id_cnt msgs_right st let _ ← - betree_node_apply_messages_back n0 params node_id_cnt msgs_right st + betree.Node.apply_messages_back n0 params node_id_cnt msgs_right st Result.ret (st0, msgs_left) /- [betree_main::betree::Internal::{4}::flush] -/ -divergent def betree_internal_flush_back +divergent def betree.Internal.flush_back (self : betree_internal_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (content : betree_list_t (U64 × betree_message_t)) (st : State) : @@ -882,36 +880,36 @@ divergent def betree_internal_flush_back := do let ⟨ i, i0, n, n0 ⟩ := self - let p ← betree_list_partition_at_pivot_fwd betree_message_t content i0 + let p ← betree.List.partition_at_pivot_fwd betree_message_t content i0 let (msgs_left, msgs_right) := p - let len_left ← betree_list_len_fwd (U64 × betree_message_t) msgs_left + let len_left ← betree.List.len_fwd (U64 × betree_message_t) msgs_left if len_left >= params.betree_params_min_flush_size then do let (st0, _) ← - betree_node_apply_messages_fwd n params node_id_cnt msgs_left st + betree.Node.apply_messages_fwd n params node_id_cnt msgs_left st let (n1, node_id_cnt0) ← - betree_node_apply_messages_back n params node_id_cnt msgs_left st + betree.Node.apply_messages_back n params node_id_cnt msgs_left st let len_right ← - betree_list_len_fwd (U64 × betree_message_t) msgs_right + betree.List.len_fwd (U64 × betree_message_t) msgs_right if len_right >= params.betree_params_min_flush_size then do let (n2, node_id_cnt1) ← - betree_node_apply_messages_back n0 params node_id_cnt0 msgs_right + betree.Node.apply_messages_back n0 params node_id_cnt0 msgs_right st0 Result.ret (betree_internal_t.mk i i0 n1 n2, node_id_cnt1) else Result.ret (betree_internal_t.mk i i0 n1 n0, node_id_cnt0) else do let (n1, node_id_cnt0) ← - betree_node_apply_messages_back n0 params node_id_cnt msgs_right st + betree.Node.apply_messages_back n0 params node_id_cnt msgs_right st Result.ret (betree_internal_t.mk i i0 n n1, node_id_cnt0) end /- [betree_main::betree::Node::{5}::apply] -/ -def betree_node_apply_fwd +def betree.Node.apply_fwd (self : betree_node_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (key : U64) (new_msg : betree_message_t) (st : State) : @@ -920,34 +918,34 @@ def betree_node_apply_fwd do let l := betree_list_t.Nil let (st0, _) ← - betree_node_apply_messages_fwd self params node_id_cnt + betree.Node.apply_messages_fwd self params node_id_cnt (betree_list_t.Cons (key, new_msg) l) st let _ ← - betree_node_apply_messages_back self params node_id_cnt + betree.Node.apply_messages_back self params node_id_cnt (betree_list_t.Cons (key, new_msg) l) st Result.ret (st0, ()) /- [betree_main::betree::Node::{5}::apply] -/ -def betree_node_apply_back +def betree.Node.apply_back (self : betree_node_t) (params : betree_params_t) (node_id_cnt : betree_node_id_counter_t) (key : U64) (new_msg : betree_message_t) (st : State) : Result (betree_node_t × betree_node_id_counter_t) := let l := betree_list_t.Nil - betree_node_apply_messages_back self params node_id_cnt (betree_list_t.Cons + betree.Node.apply_messages_back self params node_id_cnt (betree_list_t.Cons (key, new_msg) l) st /- [betree_main::betree::BeTree::{6}::new] -/ -def betree_be_tree_new_fwd +def betree.BeTree.new_fwd (min_flush_size : U64) (split_size : U64) (st : State) : Result (State × betree_be_tree_t) := do - let node_id_cnt ← betree_node_id_counter_new_fwd - let id ← betree_node_id_counter_fresh_id_fwd node_id_cnt - let (st0, _) ← betree_store_leaf_node_fwd id betree_list_t.Nil st - let node_id_cnt0 ← betree_node_id_counter_fresh_id_back node_id_cnt + let node_id_cnt ← betree.NodeIdCounter.new_fwd + let id ← betree.NodeIdCounter.fresh_id_fwd node_id_cnt + let (st0, _) ← betree.store_leaf_node_fwd id betree_list_t.Nil st + let node_id_cnt0 ← betree.NodeIdCounter.fresh_id_back node_id_cnt Result.ret (st0, { betree_be_tree_params := @@ -965,103 +963,103 @@ def betree_be_tree_new_fwd }) /- [betree_main::betree::BeTree::{6}::apply] -/ -def betree_be_tree_apply_fwd +def betree.BeTree.apply_fwd (self : betree_be_tree_t) (key : U64) (msg : betree_message_t) (st : State) : Result (State × Unit) := do let (st0, _) ← - betree_node_apply_fwd self.betree_be_tree_root self.betree_be_tree_params + betree.Node.apply_fwd self.betree_be_tree_root self.betree_be_tree_params self.betree_be_tree_node_id_cnt key msg st let _ ← - betree_node_apply_back self.betree_be_tree_root + betree.Node.apply_back self.betree_be_tree_root self.betree_be_tree_params self.betree_be_tree_node_id_cnt key msg st Result.ret (st0, ()) /- [betree_main::betree::BeTree::{6}::apply] -/ -def betree_be_tree_apply_back +def betree.BeTree.apply_back (self : betree_be_tree_t) (key : U64) (msg : betree_message_t) (st : State) : Result betree_be_tree_t := do let (n, nic) ← - betree_node_apply_back self.betree_be_tree_root + betree.Node.apply_back self.betree_be_tree_root self.betree_be_tree_params self.betree_be_tree_node_id_cnt key msg st Result.ret { self with betree_be_tree_node_id_cnt := nic, betree_be_tree_root := n } /- [betree_main::betree::BeTree::{6}::insert] -/ -def betree_be_tree_insert_fwd +def betree.BeTree.insert_fwd (self : betree_be_tree_t) (key : U64) (value : U64) (st : State) : Result (State × Unit) := do let (st0, _) ← - betree_be_tree_apply_fwd self key (betree_message_t.Insert value) st + betree.BeTree.apply_fwd self key (betree_message_t.Insert value) st let _ ← - betree_be_tree_apply_back self key (betree_message_t.Insert value) st + betree.BeTree.apply_back self key (betree_message_t.Insert value) st Result.ret (st0, ()) /- [betree_main::betree::BeTree::{6}::insert] -/ -def betree_be_tree_insert_back +def betree.BeTree.insert_back (self : betree_be_tree_t) (key : U64) (value : U64) (st : State) : Result betree_be_tree_t := - betree_be_tree_apply_back self key (betree_message_t.Insert value) st + betree.BeTree.apply_back self key (betree_message_t.Insert value) st /- [betree_main::betree::BeTree::{6}::delete] -/ -def betree_be_tree_delete_fwd +def betree.BeTree.delete_fwd (self : betree_be_tree_t) (key : U64) (st : State) : Result (State × Unit) := do let (st0, _) ← - betree_be_tree_apply_fwd self key betree_message_t.Delete st - let _ ← betree_be_tree_apply_back self key betree_message_t.Delete st + betree.BeTree.apply_fwd self key betree_message_t.Delete st + let _ ← betree.BeTree.apply_back self key betree_message_t.Delete st Result.ret (st0, ()) /- [betree_main::betree::BeTree::{6}::delete] -/ -def betree_be_tree_delete_back +def betree.BeTree.delete_back (self : betree_be_tree_t) (key : U64) (st : State) : Result betree_be_tree_t := - betree_be_tree_apply_back self key betree_message_t.Delete st + betree.BeTree.apply_back self key betree_message_t.Delete st /- [betree_main::betree::BeTree::{6}::upsert] -/ -def betree_be_tree_upsert_fwd +def betree.BeTree.upsert_fwd (self : betree_be_tree_t) (key : U64) (upd : betree_upsert_fun_state_t) (st : State) : Result (State × Unit) := do let (st0, _) ← - betree_be_tree_apply_fwd self key (betree_message_t.Upsert upd) st + betree.BeTree.apply_fwd self key (betree_message_t.Upsert upd) st let _ ← - betree_be_tree_apply_back self key (betree_message_t.Upsert upd) st + betree.BeTree.apply_back self key (betree_message_t.Upsert upd) st Result.ret (st0, ()) /- [betree_main::betree::BeTree::{6}::upsert] -/ -def betree_be_tree_upsert_back +def betree.BeTree.upsert_back (self : betree_be_tree_t) (key : U64) (upd : betree_upsert_fun_state_t) (st : State) : Result betree_be_tree_t := - betree_be_tree_apply_back self key (betree_message_t.Upsert upd) st + betree.BeTree.apply_back self key (betree_message_t.Upsert upd) st /- [betree_main::betree::BeTree::{6}::lookup] -/ -def betree_be_tree_lookup_fwd +def betree.BeTree.lookup_fwd (self : betree_be_tree_t) (key : U64) (st : State) : Result (State × (Option U64)) := - betree_node_lookup_fwd self.betree_be_tree_root key st + betree.Node.lookup_fwd self.betree_be_tree_root key st /- [betree_main::betree::BeTree::{6}::lookup] -/ -def betree_be_tree_lookup_back +def betree.BeTree.lookup_back (self : betree_be_tree_t) (key : U64) (st : State) : Result betree_be_tree_t := do - let n ← betree_node_lookup_back self.betree_be_tree_root key st + let n ← betree.Node.lookup_back self.betree_be_tree_root key st Result.ret { self with betree_be_tree_root := n } /- [betree_main::main] -/ @@ -1071,4 +1069,4 @@ def main_fwd : Result Unit := /- Unit test for [betree_main::main] -/ #assert (main_fwd == .ret ()) -end BetreeMain +end betree_main diff --git a/tests/lean/BetreeMain/FunsExternal.lean b/tests/lean/BetreeMain/FunsExternal.lean new file mode 100644 index 00000000..0c715ef9 --- /dev/null +++ b/tests/lean/BetreeMain/FunsExternal.lean @@ -0,0 +1,35 @@ +-- [betree_main]: external functions. +import Base +import BetreeMain.Types +open Primitives +open betree_main + +-- TODO: fill those bodies + +/- [betree_main::betree_utils::load_internal_node] -/ +def betree_utils.load_internal_node_fwd + : + U64 → State → Result (State × (betree_list_t (U64 × betree_message_t))) := + fun _ _ => .fail .panic + +/- [betree_main::betree_utils::store_internal_node] -/ +def betree_utils.store_internal_node_fwd + : + U64 → betree_list_t (U64 × betree_message_t) → State → Result (State + × Unit) := + fun _ _ _ => .fail .panic + +/- [betree_main::betree_utils::load_leaf_node] -/ +def betree_utils.load_leaf_node_fwd + : U64 → State → Result (State × (betree_list_t (U64 × U64))) := + fun _ _ => .fail .panic + +/- [betree_main::betree_utils::store_leaf_node] -/ +def betree_utils.store_leaf_node_fwd + : U64 → betree_list_t (U64 × U64) → State → Result (State × Unit) := + fun _ _ _ => .fail .panic + +/- [core::option::Option::{0}::unwrap] -/ +def core.option.Option.unwrap_fwd + (T : Type) : Option T → State → Result (State × T) := + fun _ _ => .fail .panic diff --git a/tests/lean/BetreeMain/FunsExternal_Template.lean b/tests/lean/BetreeMain/FunsExternal_Template.lean new file mode 100644 index 00000000..9b5a54e5 --- /dev/null +++ b/tests/lean/BetreeMain/FunsExternal_Template.lean @@ -0,0 +1,31 @@ +-- THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS +-- [betree_main]: external functions. +-- This is a template file: rename it to "FunsExternal.lean" and fill the holes. +import Base +import BetreeMain.Types +open Primitives +open betree_main + +/- [betree_main::betree_utils::load_internal_node] -/ +axiom betree_utils.load_internal_node_fwd + : + U64 → State → Result (State × (betree_list_t (U64 × betree_message_t))) + +/- [betree_main::betree_utils::store_internal_node] -/ +axiom betree_utils.store_internal_node_fwd + : + U64 → betree_list_t (U64 × betree_message_t) → State → Result (State + × Unit) + +/- [betree_main::betree_utils::load_leaf_node] -/ +axiom betree_utils.load_leaf_node_fwd + : U64 → State → Result (State × (betree_list_t (U64 × U64))) + +/- [betree_main::betree_utils::store_leaf_node] -/ +axiom betree_utils.store_leaf_node_fwd + : U64 → betree_list_t (U64 × U64) → State → Result (State × Unit) + +/- [core::option::Option::{0}::unwrap] -/ +axiom core.option.Option.unwrap_fwd + (T : Type) : Option T → State → Result (State × T) + diff --git a/tests/lean/BetreeMain/Opaque.lean b/tests/lean/BetreeMain/Opaque.lean deleted file mode 100644 index d043186b..00000000 --- a/tests/lean/BetreeMain/Opaque.lean +++ /dev/null @@ -1,35 +0,0 @@ --- THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS --- [betree_main]: opaque function definitions -import Base -import BetreeMain.Types -open Primitives - -namespace BetreeMain - -structure OpaqueDefs where - - /- [betree_main::betree_utils::load_internal_node] -/ - betree_utils_load_internal_node_fwd - : - U64 → State → Result (State × (betree_list_t (U64 × - betree_message_t))) - - /- [betree_main::betree_utils::store_internal_node] -/ - betree_utils_store_internal_node_fwd - : - U64 → betree_list_t (U64 × betree_message_t) → State → Result (State - × Unit) - - /- [betree_main::betree_utils::load_leaf_node] -/ - betree_utils_load_leaf_node_fwd - : U64 → State → Result (State × (betree_list_t (U64 × U64))) - - /- [betree_main::betree_utils::store_leaf_node] -/ - betree_utils_store_leaf_node_fwd - : U64 → betree_list_t (U64 × U64) → State → Result (State × Unit) - - /- [core::option::Option::{0}::unwrap] -/ - core_option_option_unwrap_fwd - (T : Type) : Option T → State → Result (State × T) - -end BetreeMain diff --git a/tests/lean/BetreeMain/Types.lean b/tests/lean/BetreeMain/Types.lean index cfed6a28..3ecbd668 100644 --- a/tests/lean/BetreeMain/Types.lean +++ b/tests/lean/BetreeMain/Types.lean @@ -2,8 +2,7 @@ -- [betree_main]: type definitions import Base open Primitives - -namespace BetreeMain +namespace betree_main /- [betree_main::betree::List] -/ inductive betree_list_t (T : Type) := @@ -57,4 +56,4 @@ structure betree_be_tree_t where /- The state type used in the state-error monad -/ axiom State : Type -end BetreeMain +end betree_main diff --git a/tests/lean/Constants.lean b/tests/lean/Constants.lean index 9f6a47de..39c270be 100644 --- a/tests/lean/Constants.lean +++ b/tests/lean/Constants.lean @@ -2,8 +2,7 @@ -- [constants] import Base open Primitives - -namespace Constants +namespace constants /- [constants::X0] -/ def x0_body : Result U32 := Result.ret (U32.ofInt 0 (by intlit)) @@ -69,11 +68,11 @@ structure wrap_t (T : Type) where wrap_val : T /- [constants::Wrap::{0}::new] -/ -def wrap_new_fwd (T : Type) (val : T) : Result (wrap_t T) := +def Wrap.new_fwd (T : Type) (val : T) : Result (wrap_t T) := Result.ret { wrap_val := val } /- [constants::Y] -/ -def y_body : Result (wrap_t I32) := wrap_new_fwd I32 (I32.ofInt 2 (by intlit)) +def y_body : Result (wrap_t I32) := Wrap.new_fwd I32 (I32.ofInt 2 (by intlit)) def y_c : wrap_t I32 := eval_global y_body (by simp) /- [constants::unwrap_y] -/ @@ -132,4 +131,4 @@ def s4_body : Result (pair_t U32 U32) := mk_pair1_fwd (U32.ofInt 7 (by intlit)) (U32.ofInt 8 (by intlit)) def s4_c : pair_t U32 U32 := eval_global s4_body (by simp) -end Constants +end constants diff --git a/tests/lean/External/ExternalFuns.lean b/tests/lean/External/ExternalFuns.lean deleted file mode 100644 index d63db2ac..00000000 --- a/tests/lean/External/ExternalFuns.lean +++ /dev/null @@ -1,9 +0,0 @@ -import Base -import External.Types -import External.Opaque - -namespace External - -def opaque_defs : OpaqueDefs := sorry - -end External diff --git a/tests/lean/External/Funs.lean b/tests/lean/External/Funs.lean index e36987e0..6bfffc33 100644 --- a/tests/lean/External/Funs.lean +++ b/tests/lean/External/Funs.lean @@ -2,18 +2,17 @@ -- [external]: function definitions import Base import External.Types -import External.ExternalFuns +import External.FunsExternal open Primitives - -namespace External +namespace external /- [external::swap] -/ def swap_fwd (T : Type) (x : T) (y : T) (st : State) : Result (State × Unit) := do - let (st0, _) ← opaque_defs.core_mem_swap_fwd T x y st - let (st1, _) ← opaque_defs.core_mem_swap_back0 T x y st st0 - let (st2, _) ← opaque_defs.core_mem_swap_back1 T x y st st1 + let (st0, _) ← core.mem.swap_fwd T x y st + let (st1, _) ← core.mem.swap_back0 T x y st st0 + let (st2, _) ← core.mem.swap_back1 T x y st st1 Result.ret (st2, ()) /- [external::swap] -/ @@ -22,18 +21,17 @@ def swap_back Result (State × (T × T)) := do - let (st1, _) ← opaque_defs.core_mem_swap_fwd T x y st - let (st2, x0) ← opaque_defs.core_mem_swap_back0 T x y st st1 - let (_, y0) ← opaque_defs.core_mem_swap_back1 T x y st st2 + let (st1, _) ← core.mem.swap_fwd T x y st + let (st2, x0) ← core.mem.swap_back0 T x y st st1 + let (_, y0) ← core.mem.swap_back1 T x y st st2 Result.ret (st0, (x0, y0)) /- [external::test_new_non_zero_u32] -/ def test_new_non_zero_u32_fwd (x : U32) (st : State) : Result (State × core_num_nonzero_non_zero_u32_t) := do - let (st0, opt) ← opaque_defs.core_num_nonzero_non_zero_u32_new_fwd x st - opaque_defs.core_option_option_unwrap_fwd core_num_nonzero_non_zero_u32_t - opt st0 + let (st0, opt) ← core.num.nonzero.NonZeroU32.new_fwd x st + core.option.Option.unwrap_fwd core_num_nonzero_non_zero_u32_t opt st0 /- [external::test_vec] -/ def test_vec_fwd : Result Unit := @@ -49,9 +47,9 @@ def test_vec_fwd : Result Unit := def custom_swap_fwd (T : Type) (x : T) (y : T) (st : State) : Result (State × T) := do - let (st0, _) ← opaque_defs.core_mem_swap_fwd T x y st - let (st1, x0) ← opaque_defs.core_mem_swap_back0 T x y st st0 - let (st2, _) ← opaque_defs.core_mem_swap_back1 T x y st st1 + let (st0, _) ← core.mem.swap_fwd T x y st + let (st1, x0) ← core.mem.swap_back0 T x y st st0 + let (st2, _) ← core.mem.swap_back1 T x y st st1 Result.ret (st2, x0) /- [external::custom_swap] -/ @@ -60,9 +58,9 @@ def custom_swap_back Result (State × (T × T)) := do - let (st1, _) ← opaque_defs.core_mem_swap_fwd T x y st - let (st2, _) ← opaque_defs.core_mem_swap_back0 T x y st st1 - let (_, y0) ← opaque_defs.core_mem_swap_back1 T x y st st2 + let (st1, _) ← core.mem.swap_fwd T x y st + let (st2, _) ← core.mem.swap_back0 T x y st st1 + let (_, y0) ← core.mem.swap_back1 T x y st st2 Result.ret (st0, (ret0, y0)) /- [external::test_custom_swap] -/ @@ -88,4 +86,4 @@ def test_swap_non_zero_fwd (x : U32) (st : State) : Result (State × U32) := then Result.fail Error.panic else Result.ret (st1, x0) -end External +end external diff --git a/tests/lean/External/FunsExternal.lean b/tests/lean/External/FunsExternal.lean new file mode 100644 index 00000000..5326dd77 --- /dev/null +++ b/tests/lean/External/FunsExternal.lean @@ -0,0 +1,33 @@ +-- [external]: templates for the external functions. +import Base +import External.Types +open Primitives +open external + +-- TODO: fill those bodies + +/- [core::mem::swap] -/ +def core.mem.swap_fwd + (T : Type) : T → T → State → Result (State × Unit) := + fun _x _y s => .ret (s, ()) + +/- [core::mem::swap] -/ +def core.mem.swap_back0 + (T : Type) : T → T → State → State → Result (State × T) := + fun _x y _s0 s1 => .ret (s1, y) + +/- [core::mem::swap] -/ +def core.mem.swap_back1 + (T : Type) : T → T → State → State → Result (State × T) := + fun x _y _s0 s1 => .ret (s1, x) + +/- [core::num::nonzero::NonZeroU32::{14}::new] -/ +def core.num.nonzero.NonZeroU32.new_fwd + : + U32 → State → Result (State × (Option core_num_nonzero_non_zero_u32_t)) := + fun _ _ => .fail .panic + +/- [core::option::Option::{0}::unwrap] -/ +def core.option.Option.unwrap_fwd + (T : Type) : Option T → State → Result (State × T) := + fun _ _ => .fail .panic diff --git a/tests/lean/External/FunsExternal_Template.lean b/tests/lean/External/FunsExternal_Template.lean new file mode 100644 index 00000000..d6c0eb1d --- /dev/null +++ b/tests/lean/External/FunsExternal_Template.lean @@ -0,0 +1,29 @@ +-- THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS +-- [external]: external functions. +-- This is a template file: rename it to "FunsExternal.lean" and fill the holes. +import Base +import External.Types +open Primitives +open external + +/- [core::mem::swap] -/ +axiom core.mem.swap_fwd + (T : Type) : T → T → State → Result (State × Unit) + +/- [core::mem::swap] -/ +axiom core.mem.swap_back0 + (T : Type) : T → T → State → State → Result (State × T) + +/- [core::mem::swap] -/ +axiom core.mem.swap_back1 + (T : Type) : T → T → State → State → Result (State × T) + +/- [core::num::nonzero::NonZeroU32::{14}::new] -/ +axiom core.num.nonzero.NonZeroU32.new_fwd + : + U32 → State → Result (State × (Option core_num_nonzero_non_zero_u32_t)) + +/- [core::option::Option::{0}::unwrap] -/ +axiom core.option.Option.unwrap_fwd + (T : Type) : Option T → State → Result (State × T) + diff --git a/tests/lean/External/Opaque.lean b/tests/lean/External/Opaque.lean index 1c0db095..d0297523 100644 --- a/tests/lean/External/Opaque.lean +++ b/tests/lean/External/Opaque.lean @@ -4,29 +4,29 @@ import Base import External.Types open Primitives -namespace External +namespace external structure OpaqueDefs where /- [core::mem::swap] -/ - core_mem_swap_fwd (T : Type) : T → T → State → Result (State × Unit) + core.mem.swap_fwd (T : Type) : T → T → State → Result (State × Unit) /- [core::mem::swap] -/ - core_mem_swap_back0 + core.mem.swap_back0 (T : Type) : T → T → State → State → Result (State × T) /- [core::mem::swap] -/ - core_mem_swap_back1 + core.mem.swap_back1 (T : Type) : T → T → State → State → Result (State × T) /- [core::num::nonzero::NonZeroU32::{14}::new] -/ - core_num_nonzero_non_zero_u32_new_fwd + core.num.nonzero.NonZeroU32.new_fwd : U32 → State → Result (State × (Option core_num_nonzero_non_zero_u32_t)) /- [core::option::Option::{0}::unwrap] -/ - core_option_option_unwrap_fwd + core.option.Option.unwrap_fwd (T : Type) : Option T → State → Result (State × T) -end External +end external diff --git a/tests/lean/External/Types.lean b/tests/lean/External/Types.lean index fda0670e..316f6474 100644 --- a/tests/lean/External/Types.lean +++ b/tests/lean/External/Types.lean @@ -2,8 +2,7 @@ -- [external]: type definitions import Base open Primitives - -namespace External +namespace external /- [core::num::nonzero::NonZeroU32] -/ axiom core_num_nonzero_non_zero_u32_t : Type @@ -11,4 +10,4 @@ axiom core_num_nonzero_non_zero_u32_t : Type /- The state type used in the state-error monad -/ axiom State : Type -end External +end external diff --git a/tests/lean/Hashmap/Funs.lean b/tests/lean/Hashmap/Funs.lean index b4254726..8f54eca8 100644 --- a/tests/lean/Hashmap/Funs.lean +++ b/tests/lean/Hashmap/Funs.lean @@ -3,38 +3,37 @@ import Base import Hashmap.Types open Primitives - -namespace Hashmap +namespace hashmap /- [hashmap::hash_key] -/ def hash_key_fwd (k : Usize) : Result Usize := Result.ret k /- [hashmap::HashMap::{0}::allocate_slots] -/ -divergent def hash_map_allocate_slots_loop_fwd +divergent def HashMap.allocate_slots_loop_fwd (T : Type) (slots : Vec (list_t T)) (n : Usize) : Result (Vec (list_t T)) := if n > (Usize.ofInt 0 (by intlit)) then do let slots0 ← vec_push_back (list_t T) slots list_t.Nil let n0 ← n - (Usize.ofInt 1 (by intlit)) - hash_map_allocate_slots_loop_fwd T slots0 n0 + HashMap.allocate_slots_loop_fwd T slots0 n0 else Result.ret slots /- [hashmap::HashMap::{0}::allocate_slots] -/ -def hash_map_allocate_slots_fwd +def HashMap.allocate_slots_fwd (T : Type) (slots : Vec (list_t T)) (n : Usize) : Result (Vec (list_t T)) := - hash_map_allocate_slots_loop_fwd T slots n + HashMap.allocate_slots_loop_fwd T slots n /- [hashmap::HashMap::{0}::new_with_capacity] -/ -def hash_map_new_with_capacity_fwd +def HashMap.new_with_capacity_fwd (T : Type) (capacity : Usize) (max_load_dividend : Usize) (max_load_divisor : Usize) : Result (hash_map_t T) := do let v := vec_new (list_t T) - let slots ← hash_map_allocate_slots_fwd T v capacity + let slots ← HashMap.allocate_slots_fwd T v capacity let i ← capacity * max_load_dividend let i0 ← i / max_load_divisor Result.ret @@ -46,12 +45,12 @@ def hash_map_new_with_capacity_fwd } /- [hashmap::HashMap::{0}::new] -/ -def hash_map_new_fwd (T : Type) : Result (hash_map_t T) := - hash_map_new_with_capacity_fwd T (Usize.ofInt 32 (by intlit)) +def HashMap.new_fwd (T : Type) : Result (hash_map_t T) := + HashMap.new_with_capacity_fwd T (Usize.ofInt 32 (by intlit)) (Usize.ofInt 4 (by intlit)) (Usize.ofInt 5 (by intlit)) /- [hashmap::HashMap::{0}::clear] -/ -divergent def hash_map_clear_loop_fwd_back +divergent def HashMap.clear_loop_fwd_back (T : Type) (slots : Vec (list_t T)) (i : Usize) : Result (Vec (list_t T)) := let i0 := vec_len (list_t T) slots if i < i0 @@ -59,15 +58,15 @@ divergent def hash_map_clear_loop_fwd_back do let i1 ← i + (Usize.ofInt 1 (by intlit)) let slots0 ← vec_index_mut_back (list_t T) slots i list_t.Nil - hash_map_clear_loop_fwd_back T slots0 i1 + HashMap.clear_loop_fwd_back T slots0 i1 else Result.ret slots /- [hashmap::HashMap::{0}::clear] -/ -def hash_map_clear_fwd_back +def HashMap.clear_fwd_back (T : Type) (self : hash_map_t T) : Result (hash_map_t T) := do let v ← - hash_map_clear_loop_fwd_back T self.hash_map_slots + HashMap.clear_loop_fwd_back T self.hash_map_slots (Usize.ofInt 0 (by intlit)) Result.ret { @@ -78,26 +77,26 @@ def hash_map_clear_fwd_back } /- [hashmap::HashMap::{0}::len] -/ -def hash_map_len_fwd (T : Type) (self : hash_map_t T) : Result Usize := +def HashMap.len_fwd (T : Type) (self : hash_map_t T) : Result Usize := Result.ret self.hash_map_num_entries /- [hashmap::HashMap::{0}::insert_in_list] -/ -divergent def hash_map_insert_in_list_loop_fwd +divergent def HashMap.insert_in_list_loop_fwd (T : Type) (key : Usize) (value : T) (ls : list_t T) : Result Bool := match ls with | list_t.Cons ckey cvalue tl => if ckey = key then Result.ret false - else hash_map_insert_in_list_loop_fwd T key value tl + else HashMap.insert_in_list_loop_fwd T key value tl | list_t.Nil => Result.ret true /- [hashmap::HashMap::{0}::insert_in_list] -/ -def hash_map_insert_in_list_fwd +def HashMap.insert_in_list_fwd (T : Type) (key : Usize) (value : T) (ls : list_t T) : Result Bool := - hash_map_insert_in_list_loop_fwd T key value ls + HashMap.insert_in_list_loop_fwd T key value ls /- [hashmap::HashMap::{0}::insert_in_list] -/ -divergent def hash_map_insert_in_list_loop_back +divergent def HashMap.insert_in_list_loop_back (T : Type) (key : Usize) (value : T) (ls : list_t T) : Result (list_t T) := match ls with | list_t.Cons ckey cvalue tl => @@ -105,18 +104,18 @@ divergent def hash_map_insert_in_list_loop_back then Result.ret (list_t.Cons ckey value tl) else do - let tl0 ← hash_map_insert_in_list_loop_back T key value tl + let tl0 ← HashMap.insert_in_list_loop_back T key value tl Result.ret (list_t.Cons ckey cvalue tl0) | list_t.Nil => let l := list_t.Nil Result.ret (list_t.Cons key value l) /- [hashmap::HashMap::{0}::insert_in_list] -/ -def hash_map_insert_in_list_back +def HashMap.insert_in_list_back (T : Type) (key : Usize) (value : T) (ls : list_t T) : Result (list_t T) := - hash_map_insert_in_list_loop_back T key value ls + HashMap.insert_in_list_loop_back T key value ls /- [hashmap::HashMap::{0}::insert_no_resize] -/ -def hash_map_insert_no_resize_fwd_back +def HashMap.insert_no_resize_fwd_back (T : Type) (self : hash_map_t T) (key : Usize) (value : T) : Result (hash_map_t T) := @@ -125,18 +124,18 @@ def hash_map_insert_no_resize_fwd_back let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (list_t T) self.hash_map_slots hash_mod - let inserted ← hash_map_insert_in_list_fwd T key value l + let inserted ← HashMap.insert_in_list_fwd T key value l if inserted then do let i0 ← self.hash_map_num_entries + (Usize.ofInt 1 (by intlit)) - let l0 ← hash_map_insert_in_list_back T key value l + let l0 ← HashMap.insert_in_list_back T key value l let v ← vec_index_mut_back (list_t T) self.hash_map_slots hash_mod l0 Result.ret { self with hash_map_num_entries := i0, hash_map_slots := v } else do - let l0 ← hash_map_insert_in_list_back T key value l + let l0 ← HashMap.insert_in_list_back T key value l let v ← vec_index_mut_back (list_t T) self.hash_map_slots hash_mod l0 Result.ret { self with hash_map_slots := v } @@ -146,22 +145,22 @@ def core_num_u32_max_body : Result U32 := def core_num_u32_max_c : U32 := eval_global core_num_u32_max_body (by simp) /- [hashmap::HashMap::{0}::move_elements_from_list] -/ -divergent def hash_map_move_elements_from_list_loop_fwd_back +divergent def HashMap.move_elements_from_list_loop_fwd_back (T : Type) (ntable : hash_map_t T) (ls : list_t T) : Result (hash_map_t T) := match ls with | list_t.Cons k v tl => do - let ntable0 ← hash_map_insert_no_resize_fwd_back T ntable k v - hash_map_move_elements_from_list_loop_fwd_back T ntable0 tl + let ntable0 ← HashMap.insert_no_resize_fwd_back T ntable k v + HashMap.move_elements_from_list_loop_fwd_back T ntable0 tl | list_t.Nil => Result.ret ntable /- [hashmap::HashMap::{0}::move_elements_from_list] -/ -def hash_map_move_elements_from_list_fwd_back +def HashMap.move_elements_from_list_fwd_back (T : Type) (ntable : hash_map_t T) (ls : list_t T) : Result (hash_map_t T) := - hash_map_move_elements_from_list_loop_fwd_back T ntable ls + HashMap.move_elements_from_list_loop_fwd_back T ntable ls /- [hashmap::HashMap::{0}::move_elements] -/ -divergent def hash_map_move_elements_loop_fwd_back +divergent def HashMap.move_elements_loop_fwd_back (T : Type) (ntable : hash_map_t T) (slots : Vec (list_t T)) (i : Usize) : Result ((hash_map_t T) × (Vec (list_t T))) := @@ -171,22 +170,22 @@ divergent def hash_map_move_elements_loop_fwd_back do let l ← vec_index_mut_fwd (list_t T) slots i let ls := mem_replace_fwd (list_t T) l list_t.Nil - let ntable0 ← hash_map_move_elements_from_list_fwd_back T ntable ls + let ntable0 ← HashMap.move_elements_from_list_fwd_back T ntable ls let i1 ← i + (Usize.ofInt 1 (by intlit)) let l0 := mem_replace_back (list_t T) l list_t.Nil let slots0 ← vec_index_mut_back (list_t T) slots i l0 - hash_map_move_elements_loop_fwd_back T ntable0 slots0 i1 + HashMap.move_elements_loop_fwd_back T ntable0 slots0 i1 else Result.ret (ntable, slots) /- [hashmap::HashMap::{0}::move_elements] -/ -def hash_map_move_elements_fwd_back +def HashMap.move_elements_fwd_back (T : Type) (ntable : hash_map_t T) (slots : Vec (list_t T)) (i : Usize) : Result ((hash_map_t T) × (Vec (list_t T))) := - hash_map_move_elements_loop_fwd_back T ntable slots i + HashMap.move_elements_loop_fwd_back T ntable slots i /- [hashmap::HashMap::{0}::try_resize] -/ -def hash_map_try_resize_fwd_back +def HashMap.try_resize_fwd_back (T : Type) (self : hash_map_t T) : Result (hash_map_t T) := do let max_usize ← Scalar.cast .Usize core_num_u32_max_c @@ -198,9 +197,9 @@ def hash_map_try_resize_fwd_back then do let i2 ← capacity * (Usize.ofInt 2 (by intlit)) - let ntable ← hash_map_new_with_capacity_fwd T i2 i i0 + let ntable ← HashMap.new_with_capacity_fwd T i2 i i0 let (ntable0, _) ← - hash_map_move_elements_fwd_back T ntable self.hash_map_slots + HashMap.move_elements_fwd_back T ntable self.hash_map_slots (Usize.ofInt 0 (by intlit)) Result.ret { @@ -212,84 +211,84 @@ def hash_map_try_resize_fwd_back else Result.ret { self with hash_map_max_load_factor := (i, i0) } /- [hashmap::HashMap::{0}::insert] -/ -def hash_map_insert_fwd_back +def HashMap.insert_fwd_back (T : Type) (self : hash_map_t T) (key : Usize) (value : T) : Result (hash_map_t T) := do - let self0 ← hash_map_insert_no_resize_fwd_back T self key value - let i ← hash_map_len_fwd T self0 + let self0 ← HashMap.insert_no_resize_fwd_back T self key value + let i ← HashMap.len_fwd T self0 if i > self0.hash_map_max_load - then hash_map_try_resize_fwd_back T self0 + then HashMap.try_resize_fwd_back T self0 else Result.ret self0 /- [hashmap::HashMap::{0}::contains_key_in_list] -/ -divergent def hash_map_contains_key_in_list_loop_fwd +divergent def HashMap.contains_key_in_list_loop_fwd (T : Type) (key : Usize) (ls : list_t T) : Result Bool := match ls with | list_t.Cons ckey t tl => if ckey = key then Result.ret true - else hash_map_contains_key_in_list_loop_fwd T key tl + else HashMap.contains_key_in_list_loop_fwd T key tl | list_t.Nil => Result.ret false /- [hashmap::HashMap::{0}::contains_key_in_list] -/ -def hash_map_contains_key_in_list_fwd +def HashMap.contains_key_in_list_fwd (T : Type) (key : Usize) (ls : list_t T) : Result Bool := - hash_map_contains_key_in_list_loop_fwd T key ls + HashMap.contains_key_in_list_loop_fwd T key ls /- [hashmap::HashMap::{0}::contains_key] -/ -def hash_map_contains_key_fwd +def HashMap.contains_key_fwd (T : Type) (self : hash_map_t T) (key : Usize) : Result Bool := do let hash ← hash_key_fwd key let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_fwd (list_t T) self.hash_map_slots hash_mod - hash_map_contains_key_in_list_fwd T key l + HashMap.contains_key_in_list_fwd T key l /- [hashmap::HashMap::{0}::get_in_list] -/ -divergent def hash_map_get_in_list_loop_fwd +divergent def HashMap.get_in_list_loop_fwd (T : Type) (key : Usize) (ls : list_t T) : Result T := match ls with | list_t.Cons ckey cvalue tl => if ckey = key then Result.ret cvalue - else hash_map_get_in_list_loop_fwd T key tl + else HashMap.get_in_list_loop_fwd T key tl | list_t.Nil => Result.fail Error.panic /- [hashmap::HashMap::{0}::get_in_list] -/ -def hash_map_get_in_list_fwd +def HashMap.get_in_list_fwd (T : Type) (key : Usize) (ls : list_t T) : Result T := - hash_map_get_in_list_loop_fwd T key ls + HashMap.get_in_list_loop_fwd T key ls /- [hashmap::HashMap::{0}::get] -/ -def hash_map_get_fwd +def HashMap.get_fwd (T : Type) (self : hash_map_t T) (key : Usize) : Result T := do let hash ← hash_key_fwd key let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_fwd (list_t T) self.hash_map_slots hash_mod - hash_map_get_in_list_fwd T key l + HashMap.get_in_list_fwd T key l /- [hashmap::HashMap::{0}::get_mut_in_list] -/ -divergent def hash_map_get_mut_in_list_loop_fwd +divergent def HashMap.get_mut_in_list_loop_fwd (T : Type) (ls : list_t T) (key : Usize) : Result T := match ls with | list_t.Cons ckey cvalue tl => if ckey = key then Result.ret cvalue - else hash_map_get_mut_in_list_loop_fwd T tl key + else HashMap.get_mut_in_list_loop_fwd T tl key | list_t.Nil => Result.fail Error.panic /- [hashmap::HashMap::{0}::get_mut_in_list] -/ -def hash_map_get_mut_in_list_fwd +def HashMap.get_mut_in_list_fwd (T : Type) (ls : list_t T) (key : Usize) : Result T := - hash_map_get_mut_in_list_loop_fwd T ls key + HashMap.get_mut_in_list_loop_fwd T ls key /- [hashmap::HashMap::{0}::get_mut_in_list] -/ -divergent def hash_map_get_mut_in_list_loop_back +divergent def HashMap.get_mut_in_list_loop_back (T : Type) (ls : list_t T) (key : Usize) (ret0 : T) : Result (list_t T) := match ls with | list_t.Cons ckey cvalue tl => @@ -297,27 +296,27 @@ divergent def hash_map_get_mut_in_list_loop_back then Result.ret (list_t.Cons ckey ret0 tl) else do - let tl0 ← hash_map_get_mut_in_list_loop_back T tl key ret0 + let tl0 ← HashMap.get_mut_in_list_loop_back T tl key ret0 Result.ret (list_t.Cons ckey cvalue tl0) | list_t.Nil => Result.fail Error.panic /- [hashmap::HashMap::{0}::get_mut_in_list] -/ -def hash_map_get_mut_in_list_back +def HashMap.get_mut_in_list_back (T : Type) (ls : list_t T) (key : Usize) (ret0 : T) : Result (list_t T) := - hash_map_get_mut_in_list_loop_back T ls key ret0 + HashMap.get_mut_in_list_loop_back T ls key ret0 /- [hashmap::HashMap::{0}::get_mut] -/ -def hash_map_get_mut_fwd +def HashMap.get_mut_fwd (T : Type) (self : hash_map_t T) (key : Usize) : Result T := do let hash ← hash_key_fwd key let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (list_t T) self.hash_map_slots hash_mod - hash_map_get_mut_in_list_fwd T l key + HashMap.get_mut_in_list_fwd T l key /- [hashmap::HashMap::{0}::get_mut] -/ -def hash_map_get_mut_back +def HashMap.get_mut_back (T : Type) (self : hash_map_t T) (key : Usize) (ret0 : T) : Result (hash_map_t T) := @@ -326,12 +325,12 @@ def hash_map_get_mut_back let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (list_t T) self.hash_map_slots hash_mod - let l0 ← hash_map_get_mut_in_list_back T l key ret0 + let l0 ← HashMap.get_mut_in_list_back T l key ret0 let v ← vec_index_mut_back (list_t T) self.hash_map_slots hash_mod l0 Result.ret { self with hash_map_slots := v } /- [hashmap::HashMap::{0}::remove_from_list] -/ -divergent def hash_map_remove_from_list_loop_fwd +divergent def HashMap.remove_from_list_loop_fwd (T : Type) (key : Usize) (ls : list_t T) : Result (Option T) := match ls with | list_t.Cons ckey t tl => @@ -342,16 +341,16 @@ divergent def hash_map_remove_from_list_loop_fwd match mv_ls with | list_t.Cons i cvalue tl0 => Result.ret (Option.some cvalue) | list_t.Nil => Result.fail Error.panic - else hash_map_remove_from_list_loop_fwd T key tl + else HashMap.remove_from_list_loop_fwd T key tl | list_t.Nil => Result.ret Option.none /- [hashmap::HashMap::{0}::remove_from_list] -/ -def hash_map_remove_from_list_fwd +def HashMap.remove_from_list_fwd (T : Type) (key : Usize) (ls : list_t T) : Result (Option T) := - hash_map_remove_from_list_loop_fwd T key ls + HashMap.remove_from_list_loop_fwd T key ls /- [hashmap::HashMap::{0}::remove_from_list] -/ -divergent def hash_map_remove_from_list_loop_back +divergent def HashMap.remove_from_list_loop_back (T : Type) (key : Usize) (ls : list_t T) : Result (list_t T) := match ls with | list_t.Cons ckey t tl => @@ -364,24 +363,24 @@ divergent def hash_map_remove_from_list_loop_back | list_t.Nil => Result.fail Error.panic else do - let tl0 ← hash_map_remove_from_list_loop_back T key tl + let tl0 ← HashMap.remove_from_list_loop_back T key tl Result.ret (list_t.Cons ckey t tl0) | list_t.Nil => Result.ret list_t.Nil /- [hashmap::HashMap::{0}::remove_from_list] -/ -def hash_map_remove_from_list_back +def HashMap.remove_from_list_back (T : Type) (key : Usize) (ls : list_t T) : Result (list_t T) := - hash_map_remove_from_list_loop_back T key ls + HashMap.remove_from_list_loop_back T key ls /- [hashmap::HashMap::{0}::remove] -/ -def hash_map_remove_fwd +def HashMap.remove_fwd (T : Type) (self : hash_map_t T) (key : Usize) : Result (Option T) := do let hash ← hash_key_fwd key let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (list_t T) self.hash_map_slots hash_mod - let x ← hash_map_remove_from_list_fwd T key l + let x ← HashMap.remove_from_list_fwd T key l match x with | Option.none => Result.ret Option.none | Option.some x0 => @@ -390,24 +389,24 @@ def hash_map_remove_fwd Result.ret (Option.some x0) /- [hashmap::HashMap::{0}::remove] -/ -def hash_map_remove_back +def HashMap.remove_back (T : Type) (self : hash_map_t T) (key : Usize) : Result (hash_map_t T) := do let hash ← hash_key_fwd key let i := vec_len (list_t T) self.hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (list_t T) self.hash_map_slots hash_mod - let x ← hash_map_remove_from_list_fwd T key l + let x ← HashMap.remove_from_list_fwd T key l match x with | Option.none => do - let l0 ← hash_map_remove_from_list_back T key l + let l0 ← HashMap.remove_from_list_back T key l let v ← vec_index_mut_back (list_t T) self.hash_map_slots hash_mod l0 Result.ret { self with hash_map_slots := v } | Option.some x0 => do let i0 ← self.hash_map_num_entries - (Usize.ofInt 1 (by intlit)) - let l0 ← hash_map_remove_from_list_back T key l + let l0 ← HashMap.remove_from_list_back T key l let v ← vec_index_mut_back (list_t T) self.hash_map_slots hash_mod l0 Result.ret { self with hash_map_num_entries := i0, hash_map_slots := v } @@ -415,34 +414,33 @@ def hash_map_remove_back /- [hashmap::test1] -/ def test1_fwd : Result Unit := do - let hm ← hash_map_new_fwd U64 + let hm ← HashMap.new_fwd U64 let hm0 ← - hash_map_insert_fwd_back U64 hm (Usize.ofInt 0 (by intlit)) + HashMap.insert_fwd_back U64 hm (Usize.ofInt 0 (by intlit)) (U64.ofInt 42 (by intlit)) let hm1 ← - hash_map_insert_fwd_back U64 hm0 (Usize.ofInt 128 (by intlit)) + HashMap.insert_fwd_back U64 hm0 (Usize.ofInt 128 (by intlit)) (U64.ofInt 18 (by intlit)) let hm2 ← - hash_map_insert_fwd_back U64 hm1 (Usize.ofInt 1024 (by intlit)) + HashMap.insert_fwd_back U64 hm1 (Usize.ofInt 1024 (by intlit)) (U64.ofInt 138 (by intlit)) let hm3 ← - hash_map_insert_fwd_back U64 hm2 (Usize.ofInt 1056 (by intlit)) + HashMap.insert_fwd_back U64 hm2 (Usize.ofInt 1056 (by intlit)) (U64.ofInt 256 (by intlit)) - let i ← hash_map_get_fwd U64 hm3 (Usize.ofInt 128 (by intlit)) + let i ← HashMap.get_fwd U64 hm3 (Usize.ofInt 128 (by intlit)) if not (i = (U64.ofInt 18 (by intlit))) then Result.fail Error.panic else do let hm4 ← - hash_map_get_mut_back U64 hm3 (Usize.ofInt 1024 (by intlit)) + HashMap.get_mut_back U64 hm3 (Usize.ofInt 1024 (by intlit)) (U64.ofInt 56 (by intlit)) - let i0 ← hash_map_get_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) + let i0 ← HashMap.get_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) if not (i0 = (U64.ofInt 56 (by intlit))) then Result.fail Error.panic else do - let x ← - hash_map_remove_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) + let x ← HashMap.remove_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) match x with | Option.none => Result.fail Error.panic | Option.some x0 => @@ -451,21 +449,21 @@ def test1_fwd : Result Unit := else do let hm5 ← - hash_map_remove_back U64 hm4 (Usize.ofInt 1024 (by intlit)) + HashMap.remove_back U64 hm4 (Usize.ofInt 1024 (by intlit)) let i1 ← - hash_map_get_fwd U64 hm5 (Usize.ofInt 0 (by intlit)) + HashMap.get_fwd U64 hm5 (Usize.ofInt 0 (by intlit)) if not (i1 = (U64.ofInt 42 (by intlit))) then Result.fail Error.panic else do let i2 ← - hash_map_get_fwd U64 hm5 (Usize.ofInt 128 (by intlit)) + HashMap.get_fwd U64 hm5 (Usize.ofInt 128 (by intlit)) if not (i2 = (U64.ofInt 18 (by intlit))) then Result.fail Error.panic else do let i3 ← - hash_map_get_fwd U64 hm5 + HashMap.get_fwd U64 hm5 (Usize.ofInt 1056 (by intlit)) if not (i3 = (U64.ofInt 256 (by intlit))) then Result.fail Error.panic @@ -474,4 +472,4 @@ def test1_fwd : Result Unit := /- Unit test for [hashmap::test1] -/ #assert (test1_fwd == .ret ()) -end Hashmap +end hashmap diff --git a/tests/lean/Hashmap/Types.lean b/tests/lean/Hashmap/Types.lean index 0aec6acf..75a6500f 100644 --- a/tests/lean/Hashmap/Types.lean +++ b/tests/lean/Hashmap/Types.lean @@ -2,8 +2,7 @@ -- [hashmap]: type definitions import Base open Primitives - -namespace Hashmap +namespace hashmap /- [hashmap::List] -/ inductive list_t (T : Type) := @@ -17,4 +16,4 @@ structure hash_map_t (T : Type) where hash_map_max_load : Usize hash_map_slots : Vec (list_t T) -end Hashmap +end hashmap diff --git a/tests/lean/HashmapMain/ExternalFuns.lean b/tests/lean/HashmapMain/ExternalFuns.lean deleted file mode 100644 index bc831158..00000000 --- a/tests/lean/HashmapMain/ExternalFuns.lean +++ /dev/null @@ -1,9 +0,0 @@ -import Base -import HashmapMain.Types -import HashmapMain.Opaque - -namespace HashmapMain - -def opaque_defs : OpaqueDefs := by sorry - -end HashmapMain diff --git a/tests/lean/HashmapMain/Funs.lean b/tests/lean/HashmapMain/Funs.lean index 34a0eca1..06929431 100644 --- a/tests/lean/HashmapMain/Funs.lean +++ b/tests/lean/HashmapMain/Funs.lean @@ -2,17 +2,16 @@ -- [hashmap_main]: function definitions import Base import HashmapMain.Types -import HashmapMain.ExternalFuns +import HashmapMain.FunsExternal open Primitives - -namespace HashmapMain +namespace hashmap_main /- [hashmap_main::hashmap::hash_key] -/ -def hashmap_hash_key_fwd (k : Usize) : Result Usize := +def hashmap.hash_key_fwd (k : Usize) : Result Usize := Result.ret k /- [hashmap_main::hashmap::HashMap::{0}::allocate_slots] -/ -divergent def hashmap_hash_map_allocate_slots_loop_fwd +divergent def hashmap.HashMap.allocate_slots_loop_fwd (T : Type) (slots : Vec (hashmap_list_t T)) (n : Usize) : Result (Vec (hashmap_list_t T)) := @@ -21,25 +20,25 @@ divergent def hashmap_hash_map_allocate_slots_loop_fwd do let slots0 ← vec_push_back (hashmap_list_t T) slots hashmap_list_t.Nil let n0 ← n - (Usize.ofInt 1 (by intlit)) - hashmap_hash_map_allocate_slots_loop_fwd T slots0 n0 + hashmap.HashMap.allocate_slots_loop_fwd T slots0 n0 else Result.ret slots /- [hashmap_main::hashmap::HashMap::{0}::allocate_slots] -/ -def hashmap_hash_map_allocate_slots_fwd +def hashmap.HashMap.allocate_slots_fwd (T : Type) (slots : Vec (hashmap_list_t T)) (n : Usize) : Result (Vec (hashmap_list_t T)) := - hashmap_hash_map_allocate_slots_loop_fwd T slots n + hashmap.HashMap.allocate_slots_loop_fwd T slots n /- [hashmap_main::hashmap::HashMap::{0}::new_with_capacity] -/ -def hashmap_hash_map_new_with_capacity_fwd +def hashmap.HashMap.new_with_capacity_fwd (T : Type) (capacity : Usize) (max_load_dividend : Usize) (max_load_divisor : Usize) : Result (hashmap_hash_map_t T) := do let v := vec_new (hashmap_list_t T) - let slots ← hashmap_hash_map_allocate_slots_fwd T v capacity + let slots ← hashmap.HashMap.allocate_slots_fwd T v capacity let i ← capacity * max_load_dividend let i0 ← i / max_load_divisor Result.ret @@ -52,12 +51,12 @@ def hashmap_hash_map_new_with_capacity_fwd } /- [hashmap_main::hashmap::HashMap::{0}::new] -/ -def hashmap_hash_map_new_fwd (T : Type) : Result (hashmap_hash_map_t T) := - hashmap_hash_map_new_with_capacity_fwd T (Usize.ofInt 32 (by intlit)) +def hashmap.HashMap.new_fwd (T : Type) : Result (hashmap_hash_map_t T) := + hashmap.HashMap.new_with_capacity_fwd T (Usize.ofInt 32 (by intlit)) (Usize.ofInt 4 (by intlit)) (Usize.ofInt 5 (by intlit)) /- [hashmap_main::hashmap::HashMap::{0}::clear] -/ -divergent def hashmap_hash_map_clear_loop_fwd_back +divergent def hashmap.HashMap.clear_loop_fwd_back (T : Type) (slots : Vec (hashmap_list_t T)) (i : Usize) : Result (Vec (hashmap_list_t T)) := @@ -68,15 +67,15 @@ divergent def hashmap_hash_map_clear_loop_fwd_back let i1 ← i + (Usize.ofInt 1 (by intlit)) let slots0 ← vec_index_mut_back (hashmap_list_t T) slots i hashmap_list_t.Nil - hashmap_hash_map_clear_loop_fwd_back T slots0 i1 + hashmap.HashMap.clear_loop_fwd_back T slots0 i1 else Result.ret slots /- [hashmap_main::hashmap::HashMap::{0}::clear] -/ -def hashmap_hash_map_clear_fwd_back +def hashmap.HashMap.clear_fwd_back (T : Type) (self : hashmap_hash_map_t T) : Result (hashmap_hash_map_t T) := do let v ← - hashmap_hash_map_clear_loop_fwd_back T self.hashmap_hash_map_slots + hashmap.HashMap.clear_loop_fwd_back T self.hashmap_hash_map_slots (Usize.ofInt 0 (by intlit)) Result.ret { @@ -87,27 +86,27 @@ def hashmap_hash_map_clear_fwd_back } /- [hashmap_main::hashmap::HashMap::{0}::len] -/ -def hashmap_hash_map_len_fwd +def hashmap.HashMap.len_fwd (T : Type) (self : hashmap_hash_map_t T) : Result Usize := Result.ret self.hashmap_hash_map_num_entries /- [hashmap_main::hashmap::HashMap::{0}::insert_in_list] -/ -divergent def hashmap_hash_map_insert_in_list_loop_fwd +divergent def hashmap.HashMap.insert_in_list_loop_fwd (T : Type) (key : Usize) (value : T) (ls : hashmap_list_t T) : Result Bool := match ls with | hashmap_list_t.Cons ckey cvalue tl => if ckey = key then Result.ret false - else hashmap_hash_map_insert_in_list_loop_fwd T key value tl + else hashmap.HashMap.insert_in_list_loop_fwd T key value tl | hashmap_list_t.Nil => Result.ret true /- [hashmap_main::hashmap::HashMap::{0}::insert_in_list] -/ -def hashmap_hash_map_insert_in_list_fwd +def hashmap.HashMap.insert_in_list_fwd (T : Type) (key : Usize) (value : T) (ls : hashmap_list_t T) : Result Bool := - hashmap_hash_map_insert_in_list_loop_fwd T key value ls + hashmap.HashMap.insert_in_list_loop_fwd T key value ls /- [hashmap_main::hashmap::HashMap::{0}::insert_in_list] -/ -divergent def hashmap_hash_map_insert_in_list_loop_back +divergent def hashmap.HashMap.insert_in_list_loop_back (T : Type) (key : Usize) (value : T) (ls : hashmap_list_t T) : Result (hashmap_list_t T) := @@ -117,37 +116,37 @@ divergent def hashmap_hash_map_insert_in_list_loop_back then Result.ret (hashmap_list_t.Cons ckey value tl) else do - let tl0 ← hashmap_hash_map_insert_in_list_loop_back T key value tl + let tl0 ← hashmap.HashMap.insert_in_list_loop_back T key value tl Result.ret (hashmap_list_t.Cons ckey cvalue tl0) | hashmap_list_t.Nil => let l := hashmap_list_t.Nil Result.ret (hashmap_list_t.Cons key value l) /- [hashmap_main::hashmap::HashMap::{0}::insert_in_list] -/ -def hashmap_hash_map_insert_in_list_back +def hashmap.HashMap.insert_in_list_back (T : Type) (key : Usize) (value : T) (ls : hashmap_list_t T) : Result (hashmap_list_t T) := - hashmap_hash_map_insert_in_list_loop_back T key value ls + hashmap.HashMap.insert_in_list_loop_back T key value ls /- [hashmap_main::hashmap::HashMap::{0}::insert_no_resize] -/ -def hashmap_hash_map_insert_no_resize_fwd_back +def hashmap.HashMap.insert_no_resize_fwd_back (T : Type) (self : hashmap_hash_map_t T) (key : Usize) (value : T) : Result (hashmap_hash_map_t T) := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - let inserted ← hashmap_hash_map_insert_in_list_fwd T key value l + let inserted ← hashmap.HashMap.insert_in_list_fwd T key value l if inserted then do let i0 ← self.hashmap_hash_map_num_entries + (Usize.ofInt 1 (by intlit)) - let l0 ← hashmap_hash_map_insert_in_list_back T key value l + let l0 ← hashmap.HashMap.insert_in_list_back T key value l let v ← vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod l0 @@ -159,7 +158,7 @@ def hashmap_hash_map_insert_no_resize_fwd_back } else do - let l0 ← hashmap_hash_map_insert_in_list_back T key value l + let l0 ← hashmap.HashMap.insert_in_list_back T key value l let v ← vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod l0 @@ -171,26 +170,26 @@ def core_num_u32_max_body : Result U32 := def core_num_u32_max_c : U32 := eval_global core_num_u32_max_body (by simp) /- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/ -divergent def hashmap_hash_map_move_elements_from_list_loop_fwd_back +divergent def hashmap.HashMap.move_elements_from_list_loop_fwd_back (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) : Result (hashmap_hash_map_t T) := match ls with | hashmap_list_t.Cons k v tl => do - let ntable0 ← hashmap_hash_map_insert_no_resize_fwd_back T ntable k v - hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable0 tl + let ntable0 ← hashmap.HashMap.insert_no_resize_fwd_back T ntable k v + hashmap.HashMap.move_elements_from_list_loop_fwd_back T ntable0 tl | hashmap_list_t.Nil => Result.ret ntable /- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/ -def hashmap_hash_map_move_elements_from_list_fwd_back +def hashmap.HashMap.move_elements_from_list_fwd_back (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) : Result (hashmap_hash_map_t T) := - hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable ls + hashmap.HashMap.move_elements_from_list_loop_fwd_back T ntable ls /- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/ -divergent def hashmap_hash_map_move_elements_loop_fwd_back +divergent def hashmap.HashMap.move_elements_loop_fwd_back (T : Type) (ntable : hashmap_hash_map_t T) (slots : Vec (hashmap_list_t T)) (i : Usize) : Result ((hashmap_hash_map_t T) × (Vec (hashmap_list_t T))) @@ -202,23 +201,23 @@ divergent def hashmap_hash_map_move_elements_loop_fwd_back let l ← vec_index_mut_fwd (hashmap_list_t T) slots i let ls := mem_replace_fwd (hashmap_list_t T) l hashmap_list_t.Nil let ntable0 ← - hashmap_hash_map_move_elements_from_list_fwd_back T ntable ls + hashmap.HashMap.move_elements_from_list_fwd_back T ntable ls let i1 ← i + (Usize.ofInt 1 (by intlit)) let l0 := mem_replace_back (hashmap_list_t T) l hashmap_list_t.Nil let slots0 ← vec_index_mut_back (hashmap_list_t T) slots i l0 - hashmap_hash_map_move_elements_loop_fwd_back T ntable0 slots0 i1 + hashmap.HashMap.move_elements_loop_fwd_back T ntable0 slots0 i1 else Result.ret (ntable, slots) /- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/ -def hashmap_hash_map_move_elements_fwd_back +def hashmap.HashMap.move_elements_fwd_back (T : Type) (ntable : hashmap_hash_map_t T) (slots : Vec (hashmap_list_t T)) (i : Usize) : Result ((hashmap_hash_map_t T) × (Vec (hashmap_list_t T))) := - hashmap_hash_map_move_elements_loop_fwd_back T ntable slots i + hashmap.HashMap.move_elements_loop_fwd_back T ntable slots i /- [hashmap_main::hashmap::HashMap::{0}::try_resize] -/ -def hashmap_hash_map_try_resize_fwd_back +def hashmap.HashMap.try_resize_fwd_back (T : Type) (self : hashmap_hash_map_t T) : Result (hashmap_hash_map_t T) := do let max_usize ← Scalar.cast .Usize core_num_u32_max_c @@ -230,9 +229,9 @@ def hashmap_hash_map_try_resize_fwd_back then do let i2 ← capacity * (Usize.ofInt 2 (by intlit)) - let ntable ← hashmap_hash_map_new_with_capacity_fwd T i2 i i0 + let ntable ← hashmap.HashMap.new_with_capacity_fwd T i2 i i0 let (ntable0, _) ← - hashmap_hash_map_move_elements_fwd_back T ntable + hashmap.HashMap.move_elements_fwd_back T ntable self.hashmap_hash_map_slots (Usize.ofInt 0 (by intlit)) Result.ret { @@ -244,86 +243,86 @@ def hashmap_hash_map_try_resize_fwd_back else Result.ret { self with hashmap_hash_map_max_load_factor := (i, i0) } /- [hashmap_main::hashmap::HashMap::{0}::insert] -/ -def hashmap_hash_map_insert_fwd_back +def hashmap.HashMap.insert_fwd_back (T : Type) (self : hashmap_hash_map_t T) (key : Usize) (value : T) : Result (hashmap_hash_map_t T) := do - let self0 ← hashmap_hash_map_insert_no_resize_fwd_back T self key value - let i ← hashmap_hash_map_len_fwd T self0 + let self0 ← hashmap.HashMap.insert_no_resize_fwd_back T self key value + let i ← hashmap.HashMap.len_fwd T self0 if i > self0.hashmap_hash_map_max_load - then hashmap_hash_map_try_resize_fwd_back T self0 + then hashmap.HashMap.try_resize_fwd_back T self0 else Result.ret self0 /- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/ -divergent def hashmap_hash_map_contains_key_in_list_loop_fwd +divergent def hashmap.HashMap.contains_key_in_list_loop_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result Bool := match ls with | hashmap_list_t.Cons ckey t tl => if ckey = key then Result.ret true - else hashmap_hash_map_contains_key_in_list_loop_fwd T key tl + else hashmap.HashMap.contains_key_in_list_loop_fwd T key tl | hashmap_list_t.Nil => Result.ret false /- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/ -def hashmap_hash_map_contains_key_in_list_fwd +def hashmap.HashMap.contains_key_in_list_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result Bool := - hashmap_hash_map_contains_key_in_list_loop_fwd T key ls + hashmap.HashMap.contains_key_in_list_loop_fwd T key ls /- [hashmap_main::hashmap::HashMap::{0}::contains_key] -/ -def hashmap_hash_map_contains_key_fwd +def hashmap.HashMap.contains_key_fwd (T : Type) (self : hashmap_hash_map_t T) (key : Usize) : Result Bool := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - hashmap_hash_map_contains_key_in_list_fwd T key l + hashmap.HashMap.contains_key_in_list_fwd T key l /- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/ -divergent def hashmap_hash_map_get_in_list_loop_fwd +divergent def hashmap.HashMap.get_in_list_loop_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result T := match ls with | hashmap_list_t.Cons ckey cvalue tl => if ckey = key then Result.ret cvalue - else hashmap_hash_map_get_in_list_loop_fwd T key tl + else hashmap.HashMap.get_in_list_loop_fwd T key tl | hashmap_list_t.Nil => Result.fail Error.panic /- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/ -def hashmap_hash_map_get_in_list_fwd +def hashmap.HashMap.get_in_list_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result T := - hashmap_hash_map_get_in_list_loop_fwd T key ls + hashmap.HashMap.get_in_list_loop_fwd T key ls /- [hashmap_main::hashmap::HashMap::{0}::get] -/ -def hashmap_hash_map_get_fwd +def hashmap.HashMap.get_fwd (T : Type) (self : hashmap_hash_map_t T) (key : Usize) : Result T := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - hashmap_hash_map_get_in_list_fwd T key l + hashmap.HashMap.get_in_list_fwd T key l /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/ -divergent def hashmap_hash_map_get_mut_in_list_loop_fwd +divergent def hashmap.HashMap.get_mut_in_list_loop_fwd (T : Type) (ls : hashmap_list_t T) (key : Usize) : Result T := match ls with | hashmap_list_t.Cons ckey cvalue tl => if ckey = key then Result.ret cvalue - else hashmap_hash_map_get_mut_in_list_loop_fwd T tl key + else hashmap.HashMap.get_mut_in_list_loop_fwd T tl key | hashmap_list_t.Nil => Result.fail Error.panic /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/ -def hashmap_hash_map_get_mut_in_list_fwd +def hashmap.HashMap.get_mut_in_list_fwd (T : Type) (ls : hashmap_list_t T) (key : Usize) : Result T := - hashmap_hash_map_get_mut_in_list_loop_fwd T ls key + hashmap.HashMap.get_mut_in_list_loop_fwd T ls key /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/ -divergent def hashmap_hash_map_get_mut_in_list_loop_back +divergent def hashmap.HashMap.get_mut_in_list_loop_back (T : Type) (ls : hashmap_list_t T) (key : Usize) (ret0 : T) : Result (hashmap_list_t T) := @@ -333,47 +332,47 @@ divergent def hashmap_hash_map_get_mut_in_list_loop_back then Result.ret (hashmap_list_t.Cons ckey ret0 tl) else do - let tl0 ← hashmap_hash_map_get_mut_in_list_loop_back T tl key ret0 + let tl0 ← hashmap.HashMap.get_mut_in_list_loop_back T tl key ret0 Result.ret (hashmap_list_t.Cons ckey cvalue tl0) | hashmap_list_t.Nil => Result.fail Error.panic /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/ -def hashmap_hash_map_get_mut_in_list_back +def hashmap.HashMap.get_mut_in_list_back (T : Type) (ls : hashmap_list_t T) (key : Usize) (ret0 : T) : Result (hashmap_list_t T) := - hashmap_hash_map_get_mut_in_list_loop_back T ls key ret0 + hashmap.HashMap.get_mut_in_list_loop_back T ls key ret0 /- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/ -def hashmap_hash_map_get_mut_fwd +def hashmap.HashMap.get_mut_fwd (T : Type) (self : hashmap_hash_map_t T) (key : Usize) : Result T := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - hashmap_hash_map_get_mut_in_list_fwd T l key + hashmap.HashMap.get_mut_in_list_fwd T l key /- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/ -def hashmap_hash_map_get_mut_back +def hashmap.HashMap.get_mut_back (T : Type) (self : hashmap_hash_map_t T) (key : Usize) (ret0 : T) : Result (hashmap_hash_map_t T) := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - let l0 ← hashmap_hash_map_get_mut_in_list_back T l key ret0 + let l0 ← hashmap.HashMap.get_mut_in_list_back T l key ret0 let v ← vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod l0 Result.ret { self with hashmap_hash_map_slots := v } /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/ -divergent def hashmap_hash_map_remove_from_list_loop_fwd +divergent def hashmap.HashMap.remove_from_list_loop_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result (Option T) := match ls with | hashmap_list_t.Cons ckey t tl => @@ -385,16 +384,16 @@ divergent def hashmap_hash_map_remove_from_list_loop_fwd match mv_ls with | hashmap_list_t.Cons i cvalue tl0 => Result.ret (Option.some cvalue) | hashmap_list_t.Nil => Result.fail Error.panic - else hashmap_hash_map_remove_from_list_loop_fwd T key tl + else hashmap.HashMap.remove_from_list_loop_fwd T key tl | hashmap_list_t.Nil => Result.ret Option.none /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/ -def hashmap_hash_map_remove_from_list_fwd +def hashmap.HashMap.remove_from_list_fwd (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result (Option T) := - hashmap_hash_map_remove_from_list_loop_fwd T key ls + hashmap.HashMap.remove_from_list_loop_fwd T key ls /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/ -divergent def hashmap_hash_map_remove_from_list_loop_back +divergent def hashmap.HashMap.remove_from_list_loop_back (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result (hashmap_list_t T) := @@ -410,27 +409,27 @@ divergent def hashmap_hash_map_remove_from_list_loop_back | hashmap_list_t.Nil => Result.fail Error.panic else do - let tl0 ← hashmap_hash_map_remove_from_list_loop_back T key tl + let tl0 ← hashmap.HashMap.remove_from_list_loop_back T key tl Result.ret (hashmap_list_t.Cons ckey t tl0) | hashmap_list_t.Nil => Result.ret hashmap_list_t.Nil /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/ -def hashmap_hash_map_remove_from_list_back +def hashmap.HashMap.remove_from_list_back (T : Type) (key : Usize) (ls : hashmap_list_t T) : Result (hashmap_list_t T) := - hashmap_hash_map_remove_from_list_loop_back T key ls + hashmap.HashMap.remove_from_list_loop_back T key ls /- [hashmap_main::hashmap::HashMap::{0}::remove] -/ -def hashmap_hash_map_remove_fwd +def hashmap.HashMap.remove_fwd (T : Type) (self : hashmap_hash_map_t T) (key : Usize) : Result (Option T) := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - let x ← hashmap_hash_map_remove_from_list_fwd T key l + let x ← hashmap.HashMap.remove_from_list_fwd T key l match x with | Option.none => Result.ret Option.none | Option.some x0 => @@ -440,21 +439,21 @@ def hashmap_hash_map_remove_fwd Result.ret (Option.some x0) /- [hashmap_main::hashmap::HashMap::{0}::remove] -/ -def hashmap_hash_map_remove_back +def hashmap.HashMap.remove_back (T : Type) (self : hashmap_hash_map_t T) (key : Usize) : Result (hashmap_hash_map_t T) := do - let hash ← hashmap_hash_key_fwd key + let hash ← hashmap.hash_key_fwd key let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots let hash_mod ← hash % i let l ← vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod - let x ← hashmap_hash_map_remove_from_list_fwd T key l + let x ← hashmap.HashMap.remove_from_list_fwd T key l match x with | Option.none => do - let l0 ← hashmap_hash_map_remove_from_list_back T key l + let l0 ← hashmap.HashMap.remove_from_list_back T key l let v ← vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod l0 @@ -463,7 +462,7 @@ def hashmap_hash_map_remove_back do let i0 ← self.hashmap_hash_map_num_entries - (Usize.ofInt 1 (by intlit)) - let l0 ← hashmap_hash_map_remove_from_list_back T key l + let l0 ← hashmap.HashMap.remove_from_list_back T key l let v ← vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod l0 @@ -475,38 +474,37 @@ def hashmap_hash_map_remove_back } /- [hashmap_main::hashmap::test1] -/ -def hashmap_test1_fwd : Result Unit := +def hashmap.test1_fwd : Result Unit := do - let hm ← hashmap_hash_map_new_fwd U64 + let hm ← hashmap.HashMap.new_fwd U64 let hm0 ← - hashmap_hash_map_insert_fwd_back U64 hm (Usize.ofInt 0 (by intlit)) + hashmap.HashMap.insert_fwd_back U64 hm (Usize.ofInt 0 (by intlit)) (U64.ofInt 42 (by intlit)) let hm1 ← - hashmap_hash_map_insert_fwd_back U64 hm0 (Usize.ofInt 128 (by intlit)) + hashmap.HashMap.insert_fwd_back U64 hm0 (Usize.ofInt 128 (by intlit)) (U64.ofInt 18 (by intlit)) let hm2 ← - hashmap_hash_map_insert_fwd_back U64 hm1 (Usize.ofInt 1024 (by intlit)) + hashmap.HashMap.insert_fwd_back U64 hm1 (Usize.ofInt 1024 (by intlit)) (U64.ofInt 138 (by intlit)) let hm3 ← - hashmap_hash_map_insert_fwd_back U64 hm2 (Usize.ofInt 1056 (by intlit)) + hashmap.HashMap.insert_fwd_back U64 hm2 (Usize.ofInt 1056 (by intlit)) (U64.ofInt 256 (by intlit)) - let i ← hashmap_hash_map_get_fwd U64 hm3 (Usize.ofInt 128 (by intlit)) + let i ← hashmap.HashMap.get_fwd U64 hm3 (Usize.ofInt 128 (by intlit)) if not (i = (U64.ofInt 18 (by intlit))) then Result.fail Error.panic else do let hm4 ← - hashmap_hash_map_get_mut_back U64 hm3 (Usize.ofInt 1024 (by intlit)) + hashmap.HashMap.get_mut_back U64 hm3 (Usize.ofInt 1024 (by intlit)) (U64.ofInt 56 (by intlit)) let i0 ← - hashmap_hash_map_get_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) + hashmap.HashMap.get_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) if not (i0 = (U64.ofInt 56 (by intlit))) then Result.fail Error.panic else do let x ← - hashmap_hash_map_remove_fwd U64 hm4 - (Usize.ofInt 1024 (by intlit)) + hashmap.HashMap.remove_fwd U64 hm4 (Usize.ofInt 1024 (by intlit)) match x with | Option.none => Result.fail Error.panic | Option.some x0 => @@ -515,39 +513,38 @@ def hashmap_test1_fwd : Result Unit := else do let hm5 ← - hashmap_hash_map_remove_back U64 hm4 + hashmap.HashMap.remove_back U64 hm4 (Usize.ofInt 1024 (by intlit)) let i1 ← - hashmap_hash_map_get_fwd U64 hm5 - (Usize.ofInt 0 (by intlit)) + hashmap.HashMap.get_fwd U64 hm5 (Usize.ofInt 0 (by intlit)) if not (i1 = (U64.ofInt 42 (by intlit))) then Result.fail Error.panic else do let i2 ← - hashmap_hash_map_get_fwd U64 hm5 + hashmap.HashMap.get_fwd U64 hm5 (Usize.ofInt 128 (by intlit)) if not (i2 = (U64.ofInt 18 (by intlit))) then Result.fail Error.panic else do let i3 ← - hashmap_hash_map_get_fwd U64 hm5 + hashmap.HashMap.get_fwd U64 hm5 (Usize.ofInt 1056 (by intlit)) if not (i3 = (U64.ofInt 256 (by intlit))) then Result.fail Error.panic else Result.ret () /- Unit test for [hashmap_main::hashmap::test1] -/ -#assert (hashmap_test1_fwd == .ret ()) +#assert (hashmap.test1_fwd == .ret ()) /- [hashmap_main::insert_on_disk] -/ def insert_on_disk_fwd (key : Usize) (value : U64) (st : State) : Result (State × Unit) := do - let (st0, hm) ← opaque_defs.hashmap_utils_deserialize_fwd st - let hm0 ← hashmap_hash_map_insert_fwd_back U64 hm key value - let (st1, _) ← opaque_defs.hashmap_utils_serialize_fwd hm0 st0 + let (st0, hm) ← hashmap_utils.deserialize_fwd st + let hm0 ← hashmap.HashMap.insert_fwd_back U64 hm key value + let (st1, _) ← hashmap_utils.serialize_fwd hm0 st0 Result.ret (st1, ()) /- [hashmap_main::main] -/ @@ -557,4 +554,4 @@ def main_fwd : Result Unit := /- Unit test for [hashmap_main::main] -/ #assert (main_fwd == .ret ()) -end HashmapMain +end hashmap_main diff --git a/tests/lean/HashmapMain/FunsExternal.lean b/tests/lean/HashmapMain/FunsExternal.lean new file mode 100644 index 00000000..d917b485 --- /dev/null +++ b/tests/lean/HashmapMain/FunsExternal.lean @@ -0,0 +1,17 @@ +-- [hashmap_main]: templates for the external functions. +import Base +import HashmapMain.Types +open Primitives +open hashmap_main + +-- TODO: fill those bodies + +/- [hashmap_main::hashmap_utils::deserialize] -/ +def hashmap_utils.deserialize_fwd + : State → Result (State × (hashmap_hash_map_t U64)) := + fun _ => .fail .panic + +/- [hashmap_main::hashmap_utils::serialize] -/ +def hashmap_utils.serialize_fwd + : hashmap_hash_map_t U64 → State → Result (State × Unit) := + fun _ _ => .fail .panic diff --git a/tests/lean/HashmapMain/FunsExternal_Template.lean b/tests/lean/HashmapMain/FunsExternal_Template.lean new file mode 100644 index 00000000..86286373 --- /dev/null +++ b/tests/lean/HashmapMain/FunsExternal_Template.lean @@ -0,0 +1,16 @@ +-- THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS +-- [hashmap_main]: external functions. +-- This is a template file: rename it to "FunsExternal.lean" and fill the holes. +import Base +import HashmapMain.Types +open Primitives +open hashmap_main + +/- [hashmap_main::hashmap_utils::deserialize] -/ +axiom hashmap_utils.deserialize_fwd + : State → Result (State × (hashmap_hash_map_t U64)) + +/- [hashmap_main::hashmap_utils::serialize] -/ +axiom hashmap_utils.serialize_fwd + : hashmap_hash_map_t U64 → State → Result (State × Unit) + diff --git a/tests/lean/HashmapMain/Opaque.lean b/tests/lean/HashmapMain/Opaque.lean index 10e4d8bd..abf04c94 100644 --- a/tests/lean/HashmapMain/Opaque.lean +++ b/tests/lean/HashmapMain/Opaque.lean @@ -4,16 +4,16 @@ import Base import HashmapMain.Types open Primitives -namespace HashmapMain +namespace hashmap_main structure OpaqueDefs where /- [hashmap_main::hashmap_utils::deserialize] -/ - hashmap_utils_deserialize_fwd + hashmap_utils.deserialize_fwd : State → Result (State × (hashmap_hash_map_t U64)) /- [hashmap_main::hashmap_utils::serialize] -/ - hashmap_utils_serialize_fwd + hashmap_utils.serialize_fwd : hashmap_hash_map_t U64 → State → Result (State × Unit) -end HashmapMain +end hashmap_main diff --git a/tests/lean/HashmapMain/Types.lean b/tests/lean/HashmapMain/Types.lean index b91ff3a7..16641146 100644 --- a/tests/lean/HashmapMain/Types.lean +++ b/tests/lean/HashmapMain/Types.lean @@ -2,8 +2,7 @@ -- [hashmap_main]: type definitions import Base open Primitives - -namespace HashmapMain +namespace hashmap_main /- [hashmap_main::hashmap::List] -/ inductive hashmap_list_t (T : Type) := @@ -20,4 +19,4 @@ structure hashmap_hash_map_t (T : Type) where /- The state type used in the state-error monad -/ axiom State : Type -end HashmapMain +end hashmap_main diff --git a/tests/lean/Loops/Funs.lean b/tests/lean/Loops/Funs.lean index 9e084327..694f5450 100644 --- a/tests/lean/Loops/Funs.lean +++ b/tests/lean/Loops/Funs.lean @@ -3,8 +3,7 @@ import Base import Loops.Types open Primitives - -namespace Loops +namespace loops /- [loops::sum] -/ divergent def sum_loop_fwd (max : U32) (i : U32) (s : U32) : Result U32 := @@ -624,4 +623,4 @@ def list_nth_shared_mut_loop_pair_merge_back := list_nth_shared_mut_loop_pair_merge_loop_back T ls0 ls1 i ret0 -end Loops +end loops diff --git a/tests/lean/Loops/Types.lean b/tests/lean/Loops/Types.lean index ca0403e9..5b5ed31f 100644 --- a/tests/lean/Loops/Types.lean +++ b/tests/lean/Loops/Types.lean @@ -2,12 +2,11 @@ -- [loops]: type definitions import Base open Primitives - -namespace Loops +namespace loops /- [loops::List] -/ inductive list_t (T : Type) := | Cons : T → list_t T → list_t T | Nil : list_t T -end Loops +end loops diff --git a/tests/lean/NoNestedBorrows.lean b/tests/lean/NoNestedBorrows.lean index 769bb311..67abc8f6 100644 --- a/tests/lean/NoNestedBorrows.lean +++ b/tests/lean/NoNestedBorrows.lean @@ -2,8 +2,7 @@ -- [no_nested_borrows] import Base open Primitives - -namespace NoNestedBorrows +namespace no_nested_borrows /- [no_nested_borrows::Pair] -/ structure pair_t (T1 T2 : Type) where @@ -541,4 +540,4 @@ def test_shared_borrow_enum1_fwd (l : list_t U32) : Result U32 := def test_shared_borrow_enum2_fwd : Result U32 := Result.ret (U32.ofInt 0 (by intlit)) -end NoNestedBorrows +end no_nested_borrows diff --git a/tests/lean/Paper.lean b/tests/lean/Paper.lean index edcb5c1b..c34941ef 100644 --- a/tests/lean/Paper.lean +++ b/tests/lean/Paper.lean @@ -2,8 +2,7 @@ -- [paper] import Base open Primitives - -namespace Paper +namespace paper /- [paper::ref_incr] -/ def ref_incr_fwd_back (x : I32) : Result I32 := @@ -125,4 +124,4 @@ def call_choose_fwd (p : (U32 × U32)) : Result U32 := let (px0, _) ← choose_back U32 true px py pz0 Result.ret px0 -end Paper +end paper diff --git a/tests/lean/PoloniusList.lean b/tests/lean/PoloniusList.lean index 0f2a05e3..0ff01b47 100644 --- a/tests/lean/PoloniusList.lean +++ b/tests/lean/PoloniusList.lean @@ -2,8 +2,7 @@ -- [polonius_list] import Base open Primitives - -namespace PoloniusList +namespace polonius_list /- [polonius_list::List] -/ inductive list_t (T : Type) := @@ -33,4 +32,4 @@ divergent def get_list_at_x_back Result.ret (list_t.Cons hd tl0) | list_t.Nil => Result.ret ret0 -end PoloniusList +end polonius_list diff --git a/tests/lean/Tests.lean b/tests/lean/Tests.lean deleted file mode 100644 index 9b12270e..00000000 --- a/tests/lean/Tests.lean +++ /dev/null @@ -1,9 +0,0 @@ -import BetreeMain -import Constants -import External -import Hashmap -import HashmapMain -import Loops -import NoNestedBorrows -import Paper -import PoloniusList diff --git a/tests/lean/lakefile.lean b/tests/lean/lakefile.lean index 217e533f..ae63b129 100644 --- a/tests/lean/lakefile.lean +++ b/tests/lean/lakefile.lean @@ -8,15 +8,12 @@ require Base from "../../backends/lean" package «tests» {} -@[default_target] -lean_lib «Tests» {} - -lean_lib betreeMain -lean_lib constants -lean_lib external -lean_lib hashmap -lean_lib hashmapMain -lean_lib loops -lean_lib noNestedBorrows -lean_lib paper -lean_lib poloniusList +@[default_target] lean_lib betreeMain +@[default_target] lean_lib constants +@[default_target] lean_lib external +@[default_target] lean_lib hashmap +@[default_target] lean_lib hashmapMain +@[default_target] lean_lib loops +@[default_target] lean_lib noNestedBorrows +@[default_target] lean_lib paper +@[default_target] lean_lib poloniusList -- cgit v1.3.1 From 36c3348bacf7127d3736f9aac16a430a30424020 Mon Sep 17 00:00:00 2001 From: Son Ho Date: Thu, 6 Jul 2023 13:46:26 +0200 Subject: Use short names for the structure fields in Lean --- compiler/Config.ml | 11 ++++ compiler/Driver.ml | 4 +- compiler/Extract.ml | 13 +++-- compiler/ExtractBase.ml | 68 +++++++++++++++++----- compiler/Translate.ml | 1 + tests/lean/BetreeMain/Funs.lean | 106 +++++++++++++--------------------- tests/lean/BetreeMain/Types.lean | 16 +++--- tests/lean/Constants.lean | 15 +++-- tests/lean/Hashmap/Funs.lean | 90 +++++++++++++---------------- tests/lean/Hashmap/Types.lean | 8 +-- tests/lean/HashmapMain/Funs.lean | 116 +++++++++++++------------------------- tests/lean/HashmapMain/Types.lean | 8 +-- tests/lean/NoNestedBorrows.lean | 43 ++++---------- 13 files changed, 232 insertions(+), 267 deletions(-) (limited to 'compiler/Config.ml') diff --git a/compiler/Config.ml b/compiler/Config.ml index f58ba89b..0475899c 100644 --- a/compiler/Config.ml +++ b/compiler/Config.ml @@ -304,3 +304,14 @@ let filter_useless_functions = ref true called opaque_defs, of type OpaqueDefs. *) let wrap_opaque_in_sig = ref false + +(** Use short names for the record fields. + + Some backends can't disambiguate records when their field names have collisions. + When this happens, we use long names, by which we concatenate the record + names with the field names, and check whether there are name collisions. + + For backends which can disambiguate records (typically by using the typing + information), we use short names (i.e., the original field names). + *) +let record_fields_short_names = ref false diff --git a/compiler/Driver.ml b/compiler/Driver.ml index f935a717..166ef11b 100644 --- a/compiler/Driver.ml +++ b/compiler/Driver.ml @@ -163,7 +163,9 @@ let () = (* We don't support fuel for the Lean backend *) if !use_fuel then ( log#error "The Lean backend doesn't support the -use-fuel option"; - fail ()) + fail ()); + (* Lean can disambiguate the field names *) + record_fields_short_names := true | HOL4 -> (* We don't support fuel for the HOL4 backend *) if !use_fuel then ( diff --git a/compiler/Extract.ml b/compiler/Extract.ml index cacb9b96..558a981d 100644 --- a/compiler/Extract.ml +++ b/compiler/Extract.ml @@ -625,10 +625,15 @@ let mk_formatter (ctx : trans_ctx) (crate_name : string) in let field_name (def_name : name) (field_id : FieldId.id) (field_name : string option) : string = - let def_name = type_name_to_snake_case def_name ^ "_" in - match field_name with - | Some field_name -> def_name ^ field_name - | None -> def_name ^ FieldId.to_string field_id + let field_name = + match field_name with + | Some field_name -> field_name + | None -> FieldId.to_string field_id + in + if !Config.record_fields_short_names then field_name + else + let def_name = type_name_to_snake_case def_name ^ "_" in + def_name ^ field_name in let variant_name (def_name : name) (variant : string) : string = match !backend with diff --git a/compiler/ExtractBase.ml b/compiler/ExtractBase.ml index ede7af29..655bb033 100644 --- a/compiler/ExtractBase.ml +++ b/compiler/ExtractBase.ml @@ -416,7 +416,7 @@ module IdSet = Collections.MakeSet (IdOrderedType) We use it for lookups (during the translation) and to check for name clashes. - [id_to_string] is for debugging. + [id_to_name] is for debugging. *) type names_map = { id_to_name : string IdMap.t; @@ -427,7 +427,9 @@ type names_map = { *) names_set : StringSet.t; opaque_ids : IdSet.t; - (** The set of opaque definitions. + (** TODO: this is obsolete. Remove. + + The set of opaque definitions. See {!formatter.opaque_pre} for detailed explanations about why we need to know which definitions are opaque to compute names. @@ -488,6 +490,20 @@ let names_map_add_function (id_to_string : id -> string) (is_opaque : bool) (fid : fun_id) (name : string) (nm : names_map) : names_map = names_map_add id_to_string is_opaque (FunId fid) name nm +(** The unsafe names map stores mappings from identifiers to names which might + collide. For some backends and some names, it might be acceptable to have + collisions. For instance, in Lean, different records can have fields with + the same name because Lean uses the typing information to resolve the + ambiguities. + + This map complements the {!names_map}, which checks for collisions. + *) +type unsafe_names_map = { id_to_name : string IdMap.t } + +let unsafe_names_map_add (id : id) (name : string) (nm : unsafe_names_map) : + unsafe_names_map = + { id_to_name = IdMap.add id name nm.id_to_name } + (** Make a (variable) basename unique (by adding an index). We do this in an inefficient manner (by testing all indices starting from @@ -532,6 +548,11 @@ type fun_name_info = { keep_fwd : bool; num_backs : int } type extraction_ctx = { trans_ctx : trans_ctx; names_map : names_map; + (** The map for id to names, where we forbid name collisions + (ex.: we always forbid function name collisions). *) + unsafe_names_map : unsafe_names_map; + (** The map for id to names, where we allow name collisions + (ex.: we might allow record field name collisions). *) fmt : formatter; indent_incr : int; (** The indent increment we insert whenever we need to indent more *) @@ -690,23 +711,42 @@ let id_to_string (id : id) (ctx : extraction_ctx) : string = | TypeVarId id -> "type_var_id: " ^ TypeVarId.to_string id | VarId id -> "var_id: " ^ VarId.to_string id +(** We might not check for collisions for some specific ids (ex.: field names) *) +let allow_collisions (id : id) : bool = + match id with + | FieldId (_, _) -> !Config.record_fields_short_names + | _ -> false + let ctx_add (is_opaque : bool) (id : id) (name : string) (ctx : extraction_ctx) : extraction_ctx = - (* The id_to_string function to print nice debugging messages if there are - * collisions *) - let id_to_string (id : id) : string = id_to_string id ctx in - let names_map = names_map_add id_to_string is_opaque id name ctx.names_map in - { ctx with names_map } + (* We do not use the same name map if we allow/disallow collisions *) + if allow_collisions id then ( + assert (not is_opaque); + { + ctx with + unsafe_names_map = unsafe_names_map_add id name ctx.unsafe_names_map; + }) + else + (* The id_to_string function to print nice debugging messages if there are + * collisions *) + let id_to_string (id : id) : string = id_to_string id ctx in + let names_map = + names_map_add id_to_string is_opaque id name ctx.names_map + in + { ctx with names_map } (** [with_opaque_pre]: if [true] and the definition is opaque, add the opaque prefix *) let ctx_get (with_opaque_pre : bool) (id : id) (ctx : extraction_ctx) : string = - match IdMap.find_opt id ctx.names_map.id_to_name with - | Some s -> - let is_opaque = IdSet.mem id ctx.names_map.opaque_ids in - if with_opaque_pre && is_opaque then ctx.fmt.opaque_pre () ^ s else s - | None -> - log#serror ("Could not find: " ^ id_to_string id ctx); - raise Not_found + (* We do not use the same name map if we allow/disallow collisions *) + if allow_collisions id then IdMap.find id ctx.unsafe_names_map.id_to_name + else + match IdMap.find_opt id ctx.names_map.id_to_name with + | Some s -> + let is_opaque = IdSet.mem id ctx.names_map.opaque_ids in + if with_opaque_pre && is_opaque then ctx.fmt.opaque_pre () ^ s else s + | None -> + log#serror ("Could not find: " ^ id_to_string id ctx); + raise Not_found let ctx_get_global (with_opaque_pre : bool) (id : A.GlobalDeclId.id) (ctx : extraction_ctx) : string = diff --git a/compiler/Translate.ml b/compiler/Translate.ml index 444642c0..c5f7df92 100644 --- a/compiler/Translate.ml +++ b/compiler/Translate.ml @@ -922,6 +922,7 @@ let translate_crate (filename : string) (dest_dir : string) (crate : A.crate) : { ExtractBase.trans_ctx; names_map; + unsafe_names_map = { id_to_name = ExtractBase.IdMap.empty }; fmt; indent_incr = 2; use_opaque_pre = !Config.split_files; diff --git a/tests/lean/BetreeMain/Funs.lean b/tests/lean/BetreeMain/Funs.lean index 41e4349e..b0939155 100644 --- a/tests/lean/BetreeMain/Funs.lean +++ b/tests/lean/BetreeMain/Funs.lean @@ -48,23 +48,20 @@ def betree.fresh_node_id_back (counter : U64) : Result U64 := /- [betree_main::betree::NodeIdCounter::{0}::new]: forward function -/ def betree.NodeIdCounter.new : Result betree.NodeIdCounter := - Result.ret - { betree_node_id_counter_next_node_id := (U64.ofInt 0 (by intlit)) } + Result.ret { next_node_id := (U64.ofInt 0 (by intlit)) } /- [betree_main::betree::NodeIdCounter::{0}::fresh_id]: forward function -/ def betree.NodeIdCounter.fresh_id (self : betree.NodeIdCounter) : Result U64 := do - let _ ← self.betree_node_id_counter_next_node_id + - (U64.ofInt 1 (by intlit)) - Result.ret self.betree_node_id_counter_next_node_id + let _ ← self.next_node_id + (U64.ofInt 1 (by intlit)) + Result.ret self.next_node_id /- [betree_main::betree::NodeIdCounter::{0}::fresh_id]: backward function 0 -/ def betree.NodeIdCounter.fresh_id_back (self : betree.NodeIdCounter) : Result betree.NodeIdCounter := do - let i ← self.betree_node_id_counter_next_node_id + - (U64.ofInt 1 (by intlit)) - Result.ret { betree_node_id_counter_next_node_id := i } + let i ← self.next_node_id + (U64.ofInt 1 (by intlit)) + Result.ret { next_node_id := i } /- [core::num::u64::{10}::MAX] -/ def core_num_u64_max_body : Result U64 := @@ -181,8 +178,7 @@ def betree.Leaf.split Result (State × betree.Internal) := do - let p ← - betree.List.split_at (U64 × U64) content params.betree_params_split_size + let p ← betree.List.split_at (U64 × U64) content params.split_size let (content0, content1) := p let p0 ← betree.List.hd (U64 × U64) content1 let (pivot, _) := p0 @@ -191,17 +187,9 @@ def betree.Leaf.split let id1 ← betree.NodeIdCounter.fresh_id node_id_cnt0 let (st0, _) ← betree.store_leaf_node id0 content0 st let (st1, _) ← betree.store_leaf_node id1 content1 st0 - let n := betree.Node.Leaf - { - betree_leaf_id := id0, - betree_leaf_size := params.betree_params_split_size - } - let n0 := betree.Node.Leaf - { - betree_leaf_id := id1, - betree_leaf_size := params.betree_params_split_size - } - Result.ret (st1, betree.Internal.mk self.betree_leaf_id pivot n n0) + let n := betree.Node.Leaf { id := id0, size := params.split_size } + let n0 := betree.Node.Leaf { id := id1, size := params.split_size } + Result.ret (st1, betree.Internal.mk self.id pivot n n0) /- [betree_main::betree::Leaf::{3}::split]: backward function 2 -/ def betree.Leaf.split_back @@ -210,8 +198,7 @@ def betree.Leaf.split_back Result betree.NodeIdCounter := do - let p ← - betree.List.split_at (U64 × U64) content params.betree_params_split_size + let p ← betree.List.split_at (U64 × U64) content params.split_size let (content0, content1) := p let _ ← betree.List.hd (U64 × U64) content1 let id0 ← betree.NodeIdCounter.fresh_id node_id_cnt @@ -392,7 +379,7 @@ mutual divergent def betree.Node.lookup Result.ret (st1, opt) | betree.Node.Leaf node => do - let (st0, bindings) ← betree.load_leaf_node node.betree_leaf_id st + let (st0, bindings) ← betree.load_leaf_node node.id st let opt ← betree.Node.lookup_in_bindings key bindings Result.ret (st0, opt) @@ -463,7 +450,7 @@ divergent def betree.Node.lookup_back Result.ret (betree.Node.Internal node0) | betree.Node.Leaf node => do - let (_, bindings) ← betree.load_leaf_node node.betree_leaf_id st + let (_, bindings) ← betree.load_leaf_node node.id st let _ ← betree.Node.lookup_in_bindings key bindings Result.ret (betree.Node.Leaf node) @@ -732,7 +719,7 @@ mutual divergent def betree.Node.apply_messages let (st0, content) ← betree.load_internal_node i st let content0 ← betree.Node.apply_messages_to_internal content msgs let num_msgs ← betree.List.len (U64 × betree.Message) content0 - if num_msgs >= params.betree_params_min_flush_size + if num_msgs >= params.min_flush_size then do let (st1, content1) ← @@ -750,22 +737,20 @@ mutual divergent def betree.Node.apply_messages Result.ret (st1, ()) | betree.Node.Leaf node => do - let (st0, content) ← betree.load_leaf_node node.betree_leaf_id st + let (st0, content) ← betree.load_leaf_node node.id st let content0 ← betree.Node.apply_messages_to_leaf content msgs let len ← betree.List.len (U64 × U64) content0 - let i ← (U64.ofInt 2 (by intlit)) * params.betree_params_split_size + let i ← (U64.ofInt 2 (by intlit)) * params.split_size if len >= i then do let (st1, _) ← betree.Leaf.split node content0 params node_id_cnt st0 - let (st2, _) ← - betree.store_leaf_node node.betree_leaf_id betree.List.Nil st1 + let (st2, _) ← betree.store_leaf_node node.id betree.List.Nil st1 Result.ret (st2, ()) else do - let (st1, _) ← - betree.store_leaf_node node.betree_leaf_id content0 st0 + let (st1, _) ← betree.store_leaf_node node.id content0 st0 Result.ret (st1, ()) /- [betree_main::betree::Node::{5}::apply_messages]: backward function 0 -/ @@ -782,7 +767,7 @@ divergent def betree.Node.apply_messages_back let (st0, content) ← betree.load_internal_node i st let content0 ← betree.Node.apply_messages_to_internal content msgs let num_msgs ← betree.List.len (U64 × betree.Message) content0 - if num_msgs >= params.betree_params_min_flush_size + if num_msgs >= params.min_flush_size then do let (st1, content1) ← @@ -802,25 +787,23 @@ divergent def betree.Node.apply_messages_back node_id_cnt) | betree.Node.Leaf node => do - let (st0, content) ← betree.load_leaf_node node.betree_leaf_id st + let (st0, content) ← betree.load_leaf_node node.id st let content0 ← betree.Node.apply_messages_to_leaf content msgs let len ← betree.List.len (U64 × U64) content0 - let i ← (U64.ofInt 2 (by intlit)) * params.betree_params_split_size + let i ← (U64.ofInt 2 (by intlit)) * params.split_size if len >= i then do let (st1, new_node) ← betree.Leaf.split node content0 params node_id_cnt st0 - let _ ← - betree.store_leaf_node node.betree_leaf_id betree.List.Nil st1 + let _ ← betree.store_leaf_node node.id betree.List.Nil st1 let node_id_cnt0 ← betree.Leaf.split_back node content0 params node_id_cnt st0 Result.ret (betree.Node.Internal new_node, node_id_cnt0) else do - let _ ← betree.store_leaf_node node.betree_leaf_id content0 st0 - Result.ret (betree.Node.Leaf { node with betree_leaf_size := len }, - node_id_cnt) + let _ ← betree.store_leaf_node node.id content0 st0 + Result.ret (betree.Node.Leaf { node with size := len }, node_id_cnt) /- [betree_main::betree::Internal::{4}::flush]: forward function -/ divergent def betree.Internal.flush @@ -834,7 +817,7 @@ divergent def betree.Internal.flush let p ← betree.List.partition_at_pivot betree.Message content i let (msgs_left, msgs_right) := p let len_left ← betree.List.len (U64 × betree.Message) msgs_left - if len_left >= params.betree_params_min_flush_size + if len_left >= params.min_flush_size then do let (st0, _) ← @@ -842,7 +825,7 @@ divergent def betree.Internal.flush let (_, node_id_cnt0) ← betree.Node.apply_messages_back n params node_id_cnt msgs_left st let len_right ← betree.List.len (U64 × betree.Message) msgs_right - if len_right >= params.betree_params_min_flush_size + if len_right >= params.min_flush_size then do let (st1, _) ← @@ -872,7 +855,7 @@ divergent def betree.Internal.flush_back let p ← betree.List.partition_at_pivot betree.Message content i0 let (msgs_left, msgs_right) := p let len_left ← betree.List.len (U64 × betree.Message) msgs_left - if len_left >= params.betree_params_min_flush_size + if len_left >= params.min_flush_size then do let (st0, _) ← @@ -880,7 +863,7 @@ divergent def betree.Internal.flush_back let (n1, node_id_cnt0) ← betree.Node.apply_messages_back n params node_id_cnt msgs_left st let len_right ← betree.List.len (U64 × betree.Message) msgs_right - if len_right >= params.betree_params_min_flush_size + if len_right >= params.min_flush_size then do let (n2, node_id_cnt1) ← @@ -936,18 +919,11 @@ def betree.BeTree.new let node_id_cnt0 ← betree.NodeIdCounter.fresh_id_back node_id_cnt Result.ret (st0, { - betree_be_tree_params := - { - betree_params_min_flush_size := min_flush_size, - betree_params_split_size := split_size - }, - betree_be_tree_node_id_cnt := node_id_cnt0, - betree_be_tree_root := - (betree.Node.Leaf - { - betree_leaf_id := id, - betree_leaf_size := (U64.ofInt 0 (by intlit)) - }) + params := + { min_flush_size := min_flush_size, split_size := split_size }, + node_id_cnt := node_id_cnt0, + root := + (betree.Node.Leaf { id := id, size := (U64.ofInt 0 (by intlit)) }) }) /- [betree_main::betree::BeTree::{6}::apply]: forward function -/ @@ -957,11 +933,9 @@ def betree.BeTree.apply := do let (st0, _) ← - betree.Node.apply self.betree_be_tree_root self.betree_be_tree_params - self.betree_be_tree_node_id_cnt key msg st + betree.Node.apply self.root self.params self.node_id_cnt key msg st let _ ← - betree.Node.apply_back self.betree_be_tree_root - self.betree_be_tree_params self.betree_be_tree_node_id_cnt key msg st + betree.Node.apply_back self.root self.params self.node_id_cnt key msg st Result.ret (st0, ()) /- [betree_main::betree::BeTree::{6}::apply]: backward function 0 -/ @@ -971,10 +945,8 @@ def betree.BeTree.apply_back := do let (n, nic) ← - betree.Node.apply_back self.betree_be_tree_root - self.betree_be_tree_params self.betree_be_tree_node_id_cnt key msg st - Result.ret - { self with betree_be_tree_node_id_cnt := nic, betree_be_tree_root := n } + betree.Node.apply_back self.root self.params self.node_id_cnt key msg st + Result.ret { self with node_id_cnt := nic, root := n } /- [betree_main::betree::BeTree::{6}::insert]: forward function -/ def betree.BeTree.insert @@ -1033,14 +1005,14 @@ def betree.BeTree.lookup (self : betree.BeTree) (key : U64) (st : State) : Result (State × (Option U64)) := - betree.Node.lookup self.betree_be_tree_root key st + betree.Node.lookup self.root key st /- [betree_main::betree::BeTree::{6}::lookup]: backward function 0 -/ def betree.BeTree.lookup_back (self : betree.BeTree) (key : U64) (st : State) : Result betree.BeTree := do - let n ← betree.Node.lookup_back self.betree_be_tree_root key st - Result.ret { self with betree_be_tree_root := n } + let n ← betree.Node.lookup_back self.root key st + Result.ret { self with root := n } /- [betree_main::main]: forward function -/ def main : Result Unit := diff --git a/tests/lean/BetreeMain/Types.lean b/tests/lean/BetreeMain/Types.lean index afbdac9a..783ade64 100644 --- a/tests/lean/BetreeMain/Types.lean +++ b/tests/lean/BetreeMain/Types.lean @@ -22,8 +22,8 @@ inductive betree.Message := /- [betree_main::betree::Leaf] -/ structure betree.Leaf where - betree_leaf_id : U64 - betree_leaf_size : U64 + id : U64 + size : U64 mutual @@ -40,18 +40,18 @@ end /- [betree_main::betree::Params] -/ structure betree.Params where - betree_params_min_flush_size : U64 - betree_params_split_size : U64 + min_flush_size : U64 + split_size : U64 /- [betree_main::betree::NodeIdCounter] -/ structure betree.NodeIdCounter where - betree_node_id_counter_next_node_id : U64 + next_node_id : U64 /- [betree_main::betree::BeTree] -/ structure betree.BeTree where - betree_be_tree_params : betree.Params - betree_be_tree_node_id_cnt : betree.NodeIdCounter - betree_be_tree_root : betree.Node + params : betree.Params + node_id_cnt : betree.NodeIdCounter + root : betree.Node /- The state type used in the state-error monad -/ axiom State : Type diff --git a/tests/lean/Constants.lean b/tests/lean/Constants.lean index f37c9204..8f22bfba 100644 --- a/tests/lean/Constants.lean +++ b/tests/lean/Constants.lean @@ -35,12 +35,12 @@ def mk_pair0 (x : U32) (y : U32) : Result (U32 × U32) := /- [constants::Pair] -/ structure Pair (T1 T2 : Type) where - pair_x : T1 - pair_y : T2 + x : T1 + y : T2 /- [constants::mk_pair1]: forward function -/ def mk_pair1 (x : U32) (y : U32) : Result (Pair U32 U32) := - Result.ret { pair_x := x, pair_y := y } + Result.ret { x := x, y := y } /- [constants::P0] -/ def p0_body : Result (U32 × U32) := @@ -59,17 +59,16 @@ def p2_c : (U32 × U32) := eval_global p2_body (by simp) /- [constants::P3] -/ def p3_body : Result (Pair U32 U32) := - Result.ret - { pair_x := (U32.ofInt 0 (by intlit)), pair_y := (U32.ofInt 1 (by intlit)) } + Result.ret { x := (U32.ofInt 0 (by intlit)), y := (U32.ofInt 1 (by intlit)) } def p3_c : Pair U32 U32 := eval_global p3_body (by simp) /- [constants::Wrap] -/ structure Wrap (T : Type) where - wrap_val : T + val : T /- [constants::Wrap::{0}::new]: forward function -/ def Wrap.new (T : Type) (val : T) : Result (Wrap T) := - Result.ret { wrap_val := val } + Result.ret { val := val } /- [constants::Y] -/ def y_body : Result (Wrap I32) := Wrap.new I32 (I32.ofInt 2 (by intlit)) @@ -77,7 +76,7 @@ def y_c : Wrap I32 := eval_global y_body (by simp) /- [constants::unwrap_y]: forward function -/ def unwrap_y : Result I32 := - Result.ret y_c.wrap_val + Result.ret y_c.val /- [constants::YVAL] -/ def yval_body : Result I32 := unwrap_y diff --git a/tests/lean/Hashmap/Funs.lean b/tests/lean/Hashmap/Funs.lean index 34ff1379..5e11ffdd 100644 --- a/tests/lean/Hashmap/Funs.lean +++ b/tests/lean/Hashmap/Funs.lean @@ -38,10 +38,10 @@ def HashMap.new_with_capacity let i0 ← i / max_load_divisor Result.ret { - hash_map_num_entries := (Usize.ofInt 0 (by intlit)), - hash_map_max_load_factor := (max_load_dividend, max_load_divisor), - hash_map_max_load := i0, - hash_map_slots := slots + num_entries := (Usize.ofInt 0 (by intlit)), + max_load_factor := (max_load_dividend, max_load_divisor), + max_load := i0, + slots := slots } /- [hashmap::HashMap::{0}::new]: forward function -/ @@ -66,19 +66,13 @@ divergent def HashMap.clear_loop (there is a single backward function, and the forward function returns ()) -/ def HashMap.clear (T : Type) (self : HashMap T) : Result (HashMap T) := do - let v ← - HashMap.clear_loop T self.hash_map_slots (Usize.ofInt 0 (by intlit)) + let v ← HashMap.clear_loop T self.slots (Usize.ofInt 0 (by intlit)) Result.ret - { - self - with - hash_map_num_entries := (Usize.ofInt 0 (by intlit)), - hash_map_slots := v - } + { self with num_entries := (Usize.ofInt 0 (by intlit)), slots := v } /- [hashmap::HashMap::{0}::len]: forward function -/ def HashMap.len (T : Type) (self : HashMap T) : Result Usize := - Result.ret self.hash_map_num_entries + Result.ret self.num_entries /- [hashmap::HashMap::{0}::insert_in_list]: loop 0: forward function -/ divergent def HashMap.insert_in_list_loop @@ -122,23 +116,22 @@ def HashMap.insert_no_resize := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index_mut (List T) self.hash_map_slots hash_mod + let l ← Vec.index_mut (List T) self.slots hash_mod let inserted ← HashMap.insert_in_list T key value l if inserted then do - let i0 ← self.hash_map_num_entries + (Usize.ofInt 1 (by intlit)) + let i0 ← self.num_entries + (Usize.ofInt 1 (by intlit)) let l0 ← HashMap.insert_in_list_back T key value l - let v ← Vec.index_mut_back (List T) self.hash_map_slots hash_mod l0 - Result.ret - { self with hash_map_num_entries := i0, hash_map_slots := v } + let v ← Vec.index_mut_back (List T) self.slots hash_mod l0 + Result.ret { self with num_entries := i0, slots := v } else do let l0 ← HashMap.insert_in_list_back T key value l - let v ← Vec.index_mut_back (List T) self.hash_map_slots hash_mod l0 - Result.ret { self with hash_map_slots := v } + let v ← Vec.index_mut_back (List T) self.slots hash_mod l0 + Result.ret { self with slots := v } /- [core::num::u32::{9}::MAX] -/ def core_num_u32_max_body : Result U32 := @@ -194,9 +187,9 @@ def HashMap.move_elements def HashMap.try_resize (T : Type) (self : HashMap T) : Result (HashMap T) := do let max_usize ← Scalar.cast .Usize core_num_u32_max_c - let capacity := Vec.len (List T) self.hash_map_slots + let capacity := Vec.len (List T) self.slots let n1 ← max_usize / (Usize.ofInt 2 (by intlit)) - let (i, i0) := self.hash_map_max_load_factor + let (i, i0) := self.max_load_factor let i1 ← n1 / i if capacity <= i1 then @@ -204,16 +197,14 @@ def HashMap.try_resize (T : Type) (self : HashMap T) : Result (HashMap T) := let i2 ← capacity * (Usize.ofInt 2 (by intlit)) let ntable ← HashMap.new_with_capacity T i2 i i0 let (ntable0, _) ← - HashMap.move_elements T ntable self.hash_map_slots - (Usize.ofInt 0 (by intlit)) + HashMap.move_elements T ntable self.slots (Usize.ofInt 0 (by intlit)) Result.ret { ntable0 with - hash_map_num_entries := self.hash_map_num_entries, - hash_map_max_load_factor := (i, i0) + num_entries := self.num_entries, max_load_factor := (i, i0) } - else Result.ret { self with hash_map_max_load_factor := (i, i0) } + else Result.ret { self with max_load_factor := (i, i0) } /- [hashmap::HashMap::{0}::insert]: merged forward/backward function (there is a single backward function, and the forward function returns ()) -/ @@ -224,7 +215,7 @@ def HashMap.insert do let self0 ← HashMap.insert_no_resize T self key value let i ← HashMap.len T self0 - if i > self0.hash_map_max_load + if i > self0.max_load then HashMap.try_resize T self0 else Result.ret self0 @@ -248,9 +239,9 @@ def HashMap.contains_key (T : Type) (self : HashMap T) (key : Usize) : Result Bool := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index (List T) self.hash_map_slots hash_mod + let l ← Vec.index (List T) self.slots hash_mod HashMap.contains_key_in_list T key l /- [hashmap::HashMap::{0}::get_in_list]: loop 0: forward function -/ @@ -271,9 +262,9 @@ def HashMap.get_in_list (T : Type) (key : Usize) (ls : List T) : Result T := def HashMap.get (T : Type) (self : HashMap T) (key : Usize) : Result T := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index (List T) self.hash_map_slots hash_mod + let l ← Vec.index (List T) self.slots hash_mod HashMap.get_in_list T key l /- [hashmap::HashMap::{0}::get_mut_in_list]: loop 0: forward function -/ @@ -313,9 +304,9 @@ def HashMap.get_mut_in_list_back def HashMap.get_mut (T : Type) (self : HashMap T) (key : Usize) : Result T := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index_mut (List T) self.hash_map_slots hash_mod + let l ← Vec.index_mut (List T) self.slots hash_mod HashMap.get_mut_in_list T l key /- [hashmap::HashMap::{0}::get_mut]: backward function 0 -/ @@ -325,12 +316,12 @@ def HashMap.get_mut_back := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index_mut (List T) self.hash_map_slots hash_mod + let l ← Vec.index_mut (List T) self.slots hash_mod let l0 ← HashMap.get_mut_in_list_back T l key ret0 - let v ← Vec.index_mut_back (List T) self.hash_map_slots hash_mod l0 - Result.ret { self with hash_map_slots := v } + let v ← Vec.index_mut_back (List T) self.slots hash_mod l0 + Result.ret { self with slots := v } /- [hashmap::HashMap::{0}::remove_from_list]: loop 0: forward function -/ divergent def HashMap.remove_from_list_loop @@ -378,15 +369,15 @@ def HashMap.remove (T : Type) (self : HashMap T) (key : Usize) : Result (Option T) := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index_mut (List T) self.hash_map_slots hash_mod + let l ← Vec.index_mut (List T) self.slots hash_mod let x ← HashMap.remove_from_list T key l match x with | Option.none => Result.ret Option.none | Option.some x0 => do - let _ ← self.hash_map_num_entries - (Usize.ofInt 1 (by intlit)) + let _ ← self.num_entries - (Usize.ofInt 1 (by intlit)) Result.ret (Option.some x0) /- [hashmap::HashMap::{0}::remove]: backward function 0 -/ @@ -394,23 +385,22 @@ def HashMap.remove_back (T : Type) (self : HashMap T) (key : Usize) : Result (HashMap T) := do let hash ← hash_key key - let i := Vec.len (List T) self.hash_map_slots + let i := Vec.len (List T) self.slots let hash_mod ← hash % i - let l ← Vec.index_mut (List T) self.hash_map_slots hash_mod + let l ← Vec.index_mut (List T) self.slots hash_mod let x ← HashMap.remove_from_list T key l match x with | Option.none => do let l0 ← HashMap.remove_from_list_back T key l - let v ← Vec.index_mut_back (List T) self.hash_map_slots hash_mod l0 - Result.ret { self with hash_map_slots := v } + let v ← Vec.index_mut_back (List T) self.slots hash_mod l0 + Result.ret { self with slots := v } | Option.some x0 => do - let i0 ← self.hash_map_num_entries - (Usize.ofInt 1 (by intlit)) + let i0 ← self.num_entries - (Usize.ofInt 1 (by intlit)) let l0 ← HashMap.remove_from_list_back T key l - let v ← Vec.index_mut_back (List T) self.hash_map_slots hash_mod l0 - Result.ret - { self with hash_map_num_entries := i0, hash_map_slots := v } + let v ← Vec.index_mut_back (List T) self.slots hash_mod l0 + Result.ret { self with num_entries := i0, slots := v } /- [hashmap::test1]: forward function -/ def test1 : Result Unit := diff --git a/tests/lean/Hashmap/Types.lean b/tests/lean/Hashmap/Types.lean index 7530f3b9..6606cf9e 100644 --- a/tests/lean/Hashmap/Types.lean +++ b/tests/lean/Hashmap/Types.lean @@ -11,9 +11,9 @@ inductive List (T : Type) := /- [hashmap::HashMap] -/ structure HashMap (T : Type) where - hash_map_num_entries : Usize - hash_map_max_load_factor : (Usize × Usize) - hash_map_max_load : Usize - hash_map_slots : Vec (List T) + num_entries : Usize + max_load_factor : (Usize × Usize) + max_load : Usize + slots : Vec (List T) end hashmap diff --git a/tests/lean/HashmapMain/Funs.lean b/tests/lean/HashmapMain/Funs.lean index b1afcd44..e82cc9b2 100644 --- a/tests/lean/HashmapMain/Funs.lean +++ b/tests/lean/HashmapMain/Funs.lean @@ -43,11 +43,10 @@ def hashmap.HashMap.new_with_capacity let i0 ← i / max_load_divisor Result.ret { - hashmap_hash_map_num_entries := (Usize.ofInt 0 (by intlit)), - hashmap_hash_map_max_load_factor := - (max_load_dividend, max_load_divisor), - hashmap_hash_map_max_load := i0, - hashmap_hash_map_slots := slots + num_entries := (Usize.ofInt 0 (by intlit)), + max_load_factor := (max_load_dividend, max_load_divisor), + max_load := i0, + slots := slots } /- [hashmap_main::hashmap::HashMap::{0}::new]: forward function -/ @@ -77,19 +76,13 @@ def hashmap.HashMap.clear (T : Type) (self : hashmap.HashMap T) : Result (hashmap.HashMap T) := do let v ← - hashmap.HashMap.clear_loop T self.hashmap_hash_map_slots - (Usize.ofInt 0 (by intlit)) + hashmap.HashMap.clear_loop T self.slots (Usize.ofInt 0 (by intlit)) Result.ret - { - self - with - hashmap_hash_map_num_entries := (Usize.ofInt 0 (by intlit)), - hashmap_hash_map_slots := v - } + { self with num_entries := (Usize.ofInt 0 (by intlit)), slots := v } /- [hashmap_main::hashmap::HashMap::{0}::len]: forward function -/ def hashmap.HashMap.len (T : Type) (self : hashmap.HashMap T) : Result Usize := - Result.ret self.hashmap_hash_map_num_entries + Result.ret self.num_entries /- [hashmap_main::hashmap::HashMap::{0}::insert_in_list]: loop 0: forward function -/ divergent def hashmap.HashMap.insert_in_list_loop @@ -138,33 +131,22 @@ def hashmap.HashMap.insert_no_resize := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← - Vec.index_mut (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index_mut (hashmap.List T) self.slots hash_mod let inserted ← hashmap.HashMap.insert_in_list T key value l if inserted then do - let i0 ← self.hashmap_hash_map_num_entries + - (Usize.ofInt 1 (by intlit)) + let i0 ← self.num_entries + (Usize.ofInt 1 (by intlit)) let l0 ← hashmap.HashMap.insert_in_list_back T key value l - let v ← - Vec.index_mut_back (hashmap.List T) self.hashmap_hash_map_slots - hash_mod l0 - Result.ret - { - self - with - hashmap_hash_map_num_entries := i0, hashmap_hash_map_slots := v - } + let v ← Vec.index_mut_back (hashmap.List T) self.slots hash_mod l0 + Result.ret { self with num_entries := i0, slots := v } else do let l0 ← hashmap.HashMap.insert_in_list_back T key value l - let v ← - Vec.index_mut_back (hashmap.List T) self.hashmap_hash_map_slots - hash_mod l0 - Result.ret { self with hashmap_hash_map_slots := v } + let v ← Vec.index_mut_back (hashmap.List T) self.slots hash_mod l0 + Result.ret { self with slots := v } /- [core::num::u32::{9}::MAX] -/ def core_num_u32_max_body : Result U32 := @@ -227,9 +209,9 @@ def hashmap.HashMap.try_resize (T : Type) (self : hashmap.HashMap T) : Result (hashmap.HashMap T) := do let max_usize ← Scalar.cast .Usize core_num_u32_max_c - let capacity := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let capacity := Vec.len (hashmap.List T) self.slots let n1 ← max_usize / (Usize.ofInt 2 (by intlit)) - let (i, i0) := self.hashmap_hash_map_max_load_factor + let (i, i0) := self.max_load_factor let i1 ← n1 / i if capacity <= i1 then @@ -237,16 +219,15 @@ def hashmap.HashMap.try_resize let i2 ← capacity * (Usize.ofInt 2 (by intlit)) let ntable ← hashmap.HashMap.new_with_capacity T i2 i i0 let (ntable0, _) ← - hashmap.HashMap.move_elements T ntable self.hashmap_hash_map_slots + hashmap.HashMap.move_elements T ntable self.slots (Usize.ofInt 0 (by intlit)) Result.ret { ntable0 with - hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries, - hashmap_hash_map_max_load_factor := (i, i0) + num_entries := self.num_entries, max_load_factor := (i, i0) } - else Result.ret { self with hashmap_hash_map_max_load_factor := (i, i0) } + else Result.ret { self with max_load_factor := (i, i0) } /- [hashmap_main::hashmap::HashMap::{0}::insert]: merged forward/backward function (there is a single backward function, and the forward function returns ()) -/ @@ -257,7 +238,7 @@ def hashmap.HashMap.insert do let self0 ← hashmap.HashMap.insert_no_resize T self key value let i ← hashmap.HashMap.len T self0 - if i > self0.hashmap_hash_map_max_load + if i > self0.max_load then hashmap.HashMap.try_resize T self0 else Result.ret self0 @@ -281,9 +262,9 @@ def hashmap.HashMap.contains_key (T : Type) (self : hashmap.HashMap T) (key : Usize) : Result Bool := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← Vec.index (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index (hashmap.List T) self.slots hash_mod hashmap.HashMap.contains_key_in_list T key l /- [hashmap_main::hashmap::HashMap::{0}::get_in_list]: loop 0: forward function -/ @@ -306,9 +287,9 @@ def hashmap.HashMap.get (T : Type) (self : hashmap.HashMap T) (key : Usize) : Result T := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← Vec.index (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index (hashmap.List T) self.slots hash_mod hashmap.HashMap.get_in_list T key l /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list]: loop 0: forward function -/ @@ -353,10 +334,9 @@ def hashmap.HashMap.get_mut (T : Type) (self : hashmap.HashMap T) (key : Usize) : Result T := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← - Vec.index_mut (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index_mut (hashmap.List T) self.slots hash_mod hashmap.HashMap.get_mut_in_list T l key /- [hashmap_main::hashmap::HashMap::{0}::get_mut]: backward function 0 -/ @@ -366,15 +346,12 @@ def hashmap.HashMap.get_mut_back := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← - Vec.index_mut (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index_mut (hashmap.List T) self.slots hash_mod let l0 ← hashmap.HashMap.get_mut_in_list_back T l key ret0 - let v ← - Vec.index_mut_back (hashmap.List T) self.hashmap_hash_map_slots hash_mod - l0 - Result.ret { self with hashmap_hash_map_slots := v } + let v ← Vec.index_mut_back (hashmap.List T) self.slots hash_mod l0 + Result.ret { self with slots := v } /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list]: loop 0: forward function -/ divergent def hashmap.HashMap.remove_from_list_loop @@ -426,17 +403,15 @@ def hashmap.HashMap.remove (T : Type) (self : hashmap.HashMap T) (key : Usize) : Result (Option T) := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← - Vec.index_mut (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index_mut (hashmap.List T) self.slots hash_mod let x ← hashmap.HashMap.remove_from_list T key l match x with | Option.none => Result.ret Option.none | Option.some x0 => do - let _ ← self.hashmap_hash_map_num_entries - - (Usize.ofInt 1 (by intlit)) + let _ ← self.num_entries - (Usize.ofInt 1 (by intlit)) Result.ret (Option.some x0) /- [hashmap_main::hashmap::HashMap::{0}::remove]: backward function 0 -/ @@ -446,33 +421,22 @@ def hashmap.HashMap.remove_back := do let hash ← hashmap.hash_key key - let i := Vec.len (hashmap.List T) self.hashmap_hash_map_slots + let i := Vec.len (hashmap.List T) self.slots let hash_mod ← hash % i - let l ← - Vec.index_mut (hashmap.List T) self.hashmap_hash_map_slots hash_mod + let l ← Vec.index_mut (hashmap.List T) self.slots hash_mod let x ← hashmap.HashMap.remove_from_list T key l match x with | Option.none => do let l0 ← hashmap.HashMap.remove_from_list_back T key l - let v ← - Vec.index_mut_back (hashmap.List T) self.hashmap_hash_map_slots - hash_mod l0 - Result.ret { self with hashmap_hash_map_slots := v } + let v ← Vec.index_mut_back (hashmap.List T) self.slots hash_mod l0 + Result.ret { self with slots := v } | Option.some x0 => do - let i0 ← self.hashmap_hash_map_num_entries - - (Usize.ofInt 1 (by intlit)) + let i0 ← self.num_entries - (Usize.ofInt 1 (by intlit)) let l0 ← hashmap.HashMap.remove_from_list_back T key l - let v ← - Vec.index_mut_back (hashmap.List T) self.hashmap_hash_map_slots - hash_mod l0 - Result.ret - { - self - with - hashmap_hash_map_num_entries := i0, hashmap_hash_map_slots := v - } + let v ← Vec.index_mut_back (hashmap.List T) self.slots hash_mod l0 + Result.ret { self with num_entries := i0, slots := v } /- [hashmap_main::hashmap::test1]: forward function -/ def hashmap.test1 : Result Unit := diff --git a/tests/lean/HashmapMain/Types.lean b/tests/lean/HashmapMain/Types.lean index ac195e3d..3b3d0d7c 100644 --- a/tests/lean/HashmapMain/Types.lean +++ b/tests/lean/HashmapMain/Types.lean @@ -11,10 +11,10 @@ inductive hashmap.List (T : Type) := /- [hashmap_main::hashmap::HashMap] -/ structure hashmap.HashMap (T : Type) where - hashmap_hash_map_num_entries : Usize - hashmap_hash_map_max_load_factor : (Usize × Usize) - hashmap_hash_map_max_load : Usize - hashmap_hash_map_slots : Vec (hashmap.List T) + num_entries : Usize + max_load_factor : (Usize × Usize) + max_load : Usize + slots : Vec (hashmap.List T) /- The state type used in the state-error monad -/ axiom State : Type diff --git a/tests/lean/NoNestedBorrows.lean b/tests/lean/NoNestedBorrows.lean index dc744a29..1c6421bb 100644 --- a/tests/lean/NoNestedBorrows.lean +++ b/tests/lean/NoNestedBorrows.lean @@ -6,8 +6,8 @@ namespace no_nested_borrows /- [no_nested_borrows::Pair] -/ structure Pair (T1 T2 : Type) where - pair_x : T1 - pair_y : T2 + x : T1 + y : T2 /- [no_nested_borrows::List] -/ inductive List (T : Type) := @@ -431,71 +431,52 @@ def id_mut_pair4_back'b /- [no_nested_borrows::StructWithTuple] -/ structure StructWithTuple (T1 T2 : Type) where - struct_with_tuple_p : (T1 × T2) + p : (T1 × T2) /- [no_nested_borrows::new_tuple1]: forward function -/ def new_tuple1 : Result (StructWithTuple U32 U32) := - Result.ret - { - struct_with_tuple_p := - ((U32.ofInt 1 (by intlit)), (U32.ofInt 2 (by intlit))) - } + Result.ret { p := ((U32.ofInt 1 (by intlit)), (U32.ofInt 2 (by intlit))) } /- [no_nested_borrows::new_tuple2]: forward function -/ def new_tuple2 : Result (StructWithTuple I16 I16) := - Result.ret - { - struct_with_tuple_p := - ((I16.ofInt 1 (by intlit)), (I16.ofInt 2 (by intlit))) - } + Result.ret { p := ((I16.ofInt 1 (by intlit)), (I16.ofInt 2 (by intlit))) } /- [no_nested_borrows::new_tuple3]: forward function -/ def new_tuple3 : Result (StructWithTuple U64 I64) := - Result.ret - { - struct_with_tuple_p := - ((U64.ofInt 1 (by intlit)), (I64.ofInt 2 (by intlit))) - } + Result.ret { p := ((U64.ofInt 1 (by intlit)), (I64.ofInt 2 (by intlit))) } /- [no_nested_borrows::StructWithPair] -/ structure StructWithPair (T1 T2 : Type) where - struct_with_pair_p : Pair T1 T2 + p : Pair T1 T2 /- [no_nested_borrows::new_pair1]: forward function -/ def new_pair1 : Result (StructWithPair U32 U32) := Result.ret - { - struct_with_pair_p := - { - pair_x := (U32.ofInt 1 (by intlit)), - pair_y := (U32.ofInt 2 (by intlit)) - } - } + { p := { x := (U32.ofInt 1 (by intlit)), y := (U32.ofInt 2 (by intlit)) } } /- [no_nested_borrows::test_constants]: forward function -/ def test_constants : Result Unit := do let swt ← new_tuple1 - let (i, _) := swt.struct_with_tuple_p + let (i, _) := swt.p if not (i = (U32.ofInt 1 (by intlit))) then Result.fail Error.panic else do let swt0 ← new_tuple2 - let (i0, _) := swt0.struct_with_tuple_p + let (i0, _) := swt0.p if not (i0 = (I16.ofInt 1 (by intlit))) then Result.fail Error.panic else do let swt1 ← new_tuple3 - let (i1, _) := swt1.struct_with_tuple_p + let (i1, _) := swt1.p if not (i1 = (U64.ofInt 1 (by intlit))) then Result.fail Error.panic else do let swp ← new_pair1 - if not (swp.struct_with_pair_p.pair_x = - (U32.ofInt 1 (by intlit))) + if not (swp.p.x = (U32.ofInt 1 (by intlit))) then Result.fail Error.panic else Result.ret () -- cgit v1.3.1