diff options
32 files changed, 1176 insertions, 826 deletions
diff --git a/compiler/AssociatedTypes.ml b/compiler/AssociatedTypes.ml index 2442f93a..e2f687e8 100644 --- a/compiler/AssociatedTypes.ml +++ b/compiler/AssociatedTypes.ml @@ -92,7 +92,8 @@ let ctx_add_norm_trait_types_from_preds (ctx : eval_ctx) let rec trait_instance_id_is_local_clause (id : trait_instance_id) : bool = match id with | Self | Clause _ -> true - | TraitImpl _ | BuiltinOrAuto _ | TraitRef _ | UnknownTrait _ | FnPointer _ -> + | TraitImpl _ | BuiltinOrAuto _ | TraitRef _ | UnknownTrait _ | FnPointer _ + | Closure _ -> false | ParentClause (id, _, _) | ItemClause (id, _, _, _) -> trait_instance_id_is_local_clause id @@ -118,13 +119,10 @@ let norm_ctx_to_fmt_env (ctx : norm_ctx) : Print.fmt_env = global_decls = ctx.global_decls; trait_decls = ctx.trait_decls; trait_impls = ctx.trait_impls; - generics = - { - types = ctx.type_vars; - const_generics = ctx.const_generic_vars; - regions = []; - trait_clauses = []; - }; + types = ctx.type_vars; + const_generics = ctx.const_generic_vars; + regions = []; + trait_clauses = []; preds = empty_predicates; locals = []; } @@ -220,10 +218,13 @@ let rec norm_ctx_normalize_ty (ctx : norm_ctx) (ty : ty) : ty = | TRawPtr (ty, rkind) -> let ty = norm_ctx_normalize_ty ctx ty in TRawPtr (ty, rkind) - | TArrow (inputs, output) -> + | TArrow (regions, inputs, output) -> + (* TODO: for now it works because we don't support predicates with + bound regions. If we do support them, we probably need to do + something smarter here. *) let inputs = List.map (norm_ctx_normalize_ty ctx) inputs in let output = norm_ctx_normalize_ty ctx output in - TArrow (inputs, output) + TArrow (regions, inputs, output) | TTraitType (trait_ref, generics, type_name) -> ( log#ldebug (lazy @@ -429,6 +430,9 @@ and norm_ctx_normalize_trait_instance_id (ctx : norm_ctx) (* TODO: we might want to return the ref to the function pointer, in order to later normalize a call to this function pointer *) (FnPointer ty, None) + | Closure (fid, generics) -> + let generics = norm_ctx_normalize_generic_args ctx generics in + (Closure (fid, generics), None) | UnknownTrait _ -> (* This is actually an error case *) (id, None) @@ -562,11 +566,11 @@ let ctx_adt_get_inst_norm_field_etypes (ctx : eval_ctx) (def_id : TypeDeclId.id) (** Same as [substitute_signature] but normalizes the types *) let ctx_subst_norm_signature (ctx : eval_ctx) (asubst : RegionGroupId.id -> AbstractionId.id) - (r_subst : RegionId.id -> RegionId.id) (ty_subst : TypeVarId.id -> ty) + (r_subst : RegionVarId.id -> RegionId.id) (ty_subst : TypeVarId.id -> ty) (cg_subst : ConstGenericVarId.id -> const_generic) (tr_subst : TraitClauseId.id -> trait_instance_id) (tr_self : trait_instance_id) (sg : fun_sig) - (regions_hierarchy : region_groups) : inst_fun_sig = + (regions_hierarchy : region_var_groups) : inst_fun_sig = let sg = Subst.substitute_signature asubst r_subst ty_subst cg_subst tr_subst tr_self sg regions_hierarchy diff --git a/compiler/Assumed.ml b/compiler/Assumed.ml index 48b7ee2b..1807add5 100644 --- a/compiler/Assumed.ml +++ b/compiler/Assumed.ml @@ -36,8 +36,8 @@ open LlbcAst module Sig = struct (** A few utilities *) - let rvar_id_0 = RegionId.of_int 0 - let rvar_0 : region = RVar rvar_id_0 + let rvar_id_0 = RegionVarId.of_int 0 + let rvar_0 : region = RBVar (0, rvar_id_0) let rg_id_0 = RegionGroupId.of_int 0 let tvar_id_0 = TypeVarId.of_int 0 let tvar_0 : ty = TVar tvar_id_0 @@ -48,7 +48,7 @@ module Sig = struct let region_param_0 : region_var = { index = rvar_id_0; name = Some "'a" } (** Region group: [{ parent={}; regions:{'a of id 0} }] *) - let region_group_0 : region_group = + let region_group_0 : region_var_group = { id = rg_id_0; regions = [ rvar_id_0 ]; parents = [] } (** Type parameter [T] of id 0 *) @@ -84,6 +84,8 @@ module Sig = struct in { is_unsafe = false; + is_closure = false; + closure_info = None; generics; preds; parent_params_info = None; diff --git a/compiler/Contexts.ml b/compiler/Contexts.ml index c93bb213..bbfd31e6 100644 --- a/compiler/Contexts.ml +++ b/compiler/Contexts.ml @@ -190,7 +190,7 @@ type type_context = { type fun_context = { fun_decls : fun_decl FunDeclId.Map.t; fun_infos : FunsAnalysis.fun_info FunDeclId.Map.t; - regions_hierarchies : region_groups FunIdMap.t; + regions_hierarchies : region_var_groups FunIdMap.t; } [@@deriving show] diff --git a/compiler/ExtractBase.ml b/compiler/ExtractBase.ml index 73ccac44..43658b6e 100644 --- a/compiler/ExtractBase.ml +++ b/compiler/ExtractBase.ml @@ -1984,7 +1984,7 @@ let ctx_compute_fun_name (trans_group : pure_fun_translation) (def : fun_decl) let rg = T.RegionGroupId.nth regions_hierarchy rg_id in let region_names = List.map - (fun rid -> (T.RegionId.nth sg.generics.regions rid).name) + (fun rid -> (T.RegionVarId.nth sg.generics.regions rid).name) rg.regions in Some { id = rg_id; region_names } diff --git a/compiler/ExtractName.ml b/compiler/ExtractName.ml index 2ccd4af6..4c1ffb46 100644 --- a/compiler/ExtractName.ml +++ b/compiler/ExtractName.ml @@ -62,7 +62,7 @@ let pattern_to_extract_name (is_trait_impl : bool) (name : pattern) : | TArray -> "Array" | TSlice -> "Slice" else expr_to_string c ty - | ERef _ | EVar _ -> + | ERef _ | EVar _ | EArrow _ | ERawPtr _ -> (* We simply convert the pattern to a string. This is not very satisfying but we should rarely get there. *) expr_to_string c ty) @@ -108,7 +108,7 @@ let name_with_generics_to_simple_name (ctx : ctx) (is_trait_impl : bool) name_with_generics_to_pattern ctx c TypesUtils.empty_generic_params prefix TypesUtils.empty_generic_args in - let _, _, name = pattern_common_prefix prefix name in + let _, _, name = pattern_common_prefix { equiv = true } prefix name in name in pattern_to_extract_name is_trait_impl name diff --git a/compiler/FunsAnalysis.ml b/compiler/FunsAnalysis.ml index 2f950083..f6976f23 100644 --- a/compiler/FunsAnalysis.ml +++ b/compiler/FunsAnalysis.ml @@ -86,6 +86,16 @@ let analyze_module (m : crate) (funs_map : fun_decl FunDeclId.Map.t) method may_fail b = can_fail := !can_fail || b method maybe_stateful b = stateful := !stateful || b + method visit_fid id = + if FunDeclId.Set.mem id fun_ids then ( + can_diverge := true; + is_rec := true) + else + let info = FunDeclId.Map.find id !infos in + self#may_fail info.can_fail; + stateful := !stateful || info.stateful; + can_diverge := !can_diverge || info.can_diverge + method! visit_Assert env a = self#may_fail true; super#visit_Assert env a @@ -97,25 +107,32 @@ let analyze_module (m : crate) (funs_map : fun_decl FunDeclId.Map.t) | BinaryOp (bop, _, _) -> can_fail := binop_can_fail bop || !can_fail + method! visit_Closure env id args = + (* Remark: `Closure` is a trait instance id - TODO: rename this variant *) + self#visit_fid id; + super#visit_Closure env id args + + method! visit_AggregatedClosure env id args = + self#visit_fid id; + super#visit_AggregatedClosure env id args + method! visit_Call env call = - (match call.func.func with - | FunId (FRegular id) -> - if FunDeclId.Set.mem id fun_ids then ( - can_diverge := true; - is_rec := true) - else - let info = FunDeclId.Map.find id !infos in - self#may_fail info.can_fail; - stateful := !stateful || info.stateful; - can_diverge := !can_diverge || info.can_diverge - | FunId (FAssumed id) -> - (* None of the assumed functions can diverge nor are considered stateful *) - can_fail := !can_fail || Assumed.assumed_fun_can_fail id - | TraitMethod _ -> - (* We consider trait functions can fail, but can not diverge and are not stateful. - TODO: this may cause issues if we use use a fuel parameter. - *) - can_fail := true); + (match call.func with + | FnOpMove _ -> + (* Ignoring this: we lookup the called function upon creating + the closure *) + () + | FnOpRegular func -> ( + match func.func with + | FunId (FRegular id) -> self#visit_fid id + | FunId (FAssumed id) -> + (* None of the assumed functions can diverge nor are considered stateful *) + can_fail := !can_fail || Assumed.assumed_fun_can_fail id + | TraitMethod _ -> + (* We consider trait functions can fail, but can not diverge and are not stateful. + TODO: this may cause issues if we use use a fuel parameter. + *) + can_fail := true)); super#visit_Call env call method! visit_Panic env = diff --git a/compiler/Interpreter.ml b/compiler/Interpreter.ml index c2e47da9..4ecafd31 100644 --- a/compiler/Interpreter.ml +++ b/compiler/Interpreter.ml @@ -68,7 +68,7 @@ let normalize_inst_fun_sig (ctx : eval_ctx) (sg : inst_fun_sig) : inst_fun_sig = normalize because a trait clause was instantiated with a specific trait ref). *) let symbolic_instantiate_fun_sig (ctx : eval_ctx) (sg : fun_sig) - (regions_hierarchy : region_groups) (kind : fun_kind) : + (regions_hierarchy : region_var_groups) (kind : fun_kind) : eval_ctx * inst_fun_sig = let tr_self = match kind with @@ -192,7 +192,7 @@ let initialize_symbolic_context_for_fun (ctx : decls_ctx) (fdef : fun_decl) : FunIdMap.find (FRegular fdef.def_id) ctx.fun_ctx.regions_hierarchies in let region_groups = - List.map (fun (g : region_group) -> g.id) regions_hierarchy + List.map (fun (g : region_var_group) -> g.id) regions_hierarchy in let ctx = initialize_eval_context ctx region_groups sg.generics.types diff --git a/compiler/InterpreterBorrows.ml b/compiler/InterpreterBorrows.ml index 2f793f4a..be556ade 100644 --- a/compiler/InterpreterBorrows.ml +++ b/compiler/InterpreterBorrows.ml @@ -1870,7 +1870,7 @@ let convert_value_to_abstractions (abs_kind : abs_kind) (can_end : bool) match bc with | VSharedBorrow bid -> assert (ty_no_regions ref_ty); - let ty = TRef (RVar r_id, ref_ty, kind) in + let ty = TRef (RFVar r_id, ref_ty, kind) in let value = ABorrow (ASharedBorrow bid) in ([ { value; ty } ], v) | VMutBorrow (bid, bv) -> @@ -1878,7 +1878,7 @@ let convert_value_to_abstractions (abs_kind : abs_kind) (can_end : bool) (* We don't support nested borrows for now *) assert (not (value_has_borrows ctx bv.value)); (* Create an avalue to push - note that we use [AIgnore] for the inner avalue *) - let ty = TRef (RVar r_id, ref_ty, kind) in + let ty = TRef (RFVar r_id, ref_ty, kind) in let ignored = mk_aignored ref_ty in let av = ABorrow (AMutBorrow (bid, ignored)) in let av = { value = av; ty } in @@ -1899,7 +1899,7 @@ let convert_value_to_abstractions (abs_kind : abs_kind) (can_end : bool) (* Push the avalue - note that we use [AIgnore] for the inner avalue *) (* For avalues, a loan has the borrow type *) assert (ty_no_regions ty); - let ty = mk_ref_ty (RVar r_id) ty RShared in + let ty = mk_ref_ty (RFVar r_id) ty RShared in let ignored = mk_aignored ty in (* Rem.: the shared value might contain loans *) let avl, sv = to_avalues false true true r_id sv in @@ -1917,7 +1917,7 @@ let convert_value_to_abstractions (abs_kind : abs_kind) (can_end : bool) (* Push the avalue - note that we use [AIgnore] for the inner avalue *) (* For avalues, a loan has the borrow type *) assert (ty_no_regions ty); - let ty = mk_ref_ty (RVar r_id) ty RMut in + let ty = mk_ref_ty (RFVar r_id) ty RMut in let ignored = mk_aignored ty in let av = ALoan (AMutLoan (bid, ignored)) in let av = { value = av; ty } in diff --git a/compiler/InterpreterExpressions.ml b/compiler/InterpreterExpressions.ml index ac6c9ede..eeb6ae1e 100644 --- a/compiler/InterpreterExpressions.ml +++ b/compiler/InterpreterExpressions.ml @@ -761,6 +761,7 @@ let eval_rvalue_aggregate (config : config) (aggregate_kind : aggregate_kind) (* Introduce the symbolic value in the AST *) let sv = ValuesUtils.value_as_symbolic saggregated.value in Some (SymbolicAst.IntroSymbolic (ctx, None, sv, VaArray values, e))) + | AggregatedClosure _ -> raise (Failure "Closures are not supported yet") in (* Compose and apply *) comp eval_ops compute cf diff --git a/compiler/InterpreterLoopsFixedPoint.ml b/compiler/InterpreterLoopsFixedPoint.ml index 3cc0a5f0..c4e180fa 100644 --- a/compiler/InterpreterLoopsFixedPoint.ml +++ b/compiler/InterpreterLoopsFixedPoint.ml @@ -164,7 +164,7 @@ let prepare_ashared_loans (loop_id : LoopId.id option) : cm_fun = let child_av = mk_aignored child_rty in (* Create the shared loan *) - let loan_rty = TRef (RVar nrid, rty, RShared) in + let loan_rty = TRef (RFVar nrid, rty, RShared) in let loan_value = ALoan (ASharedLoan (BorrowId.Set.singleton nlid, nsv, child_av)) in diff --git a/compiler/InterpreterLoopsMatchCtxs.ml b/compiler/InterpreterLoopsMatchCtxs.ml index bf459e41..c21dab71 100644 --- a/compiler/InterpreterLoopsMatchCtxs.ml +++ b/compiler/InterpreterLoopsMatchCtxs.ml @@ -439,7 +439,7 @@ module MakeJoinMatcher (S : MatchJoinState) : PrimMatcher = struct mk_fresh_symbolic_typed_value_from_no_regions_ty LoopJoin bv_ty in - let borrow_ty = mk_ref_ty (RVar rid) bv_ty kind in + let borrow_ty = mk_ref_ty (RFVar rid) bv_ty kind in (* Generate the avalues for the abstraction *) let mk_aborrow (bid : borrow_id) : typed_avalue = @@ -537,7 +537,7 @@ module MakeJoinMatcher (S : MatchJoinState) : PrimMatcher = struct let kind = RMut in let bv_ty = bv.ty in assert (ty_no_regions bv_ty); - let borrow_ty = mk_ref_ty (RVar rid) bv_ty kind in + let borrow_ty = mk_ref_ty (RFVar rid) bv_ty kind in let borrow_av = let ty = borrow_ty in @@ -586,7 +586,7 @@ module MakeJoinMatcher (S : MatchJoinState) : PrimMatcher = struct mk_fresh_symbolic_typed_value_from_no_regions_ty LoopJoin bv_ty in - let borrow_ty = mk_ref_ty (RVar rid) bv_ty kind in + let borrow_ty = mk_ref_ty (RFVar rid) bv_ty kind in (* Generate the avalues for the abstraction *) let mk_aborrow (bid : borrow_id) (bv : typed_value) : typed_avalue = @@ -825,9 +825,9 @@ struct let match_regions r0 r1 = match (r0, r1) with | RStatic, RStatic -> r1 - | RVar rid0, RVar rid1 -> + | RFVar rid0, RFVar rid1 -> let rid = match_rid rid0 rid1 in - RVar rid + RFVar rid | _ -> raise (Distinct "match_rtys") in match_types match_distinct_types match_regions ty0 ty1 diff --git a/compiler/InterpreterStatements.ml b/compiler/InterpreterStatements.ml index 9ea5387f..437b358a 100644 --- a/compiler/InterpreterStatements.ml +++ b/compiler/InterpreterStatements.ml @@ -493,77 +493,84 @@ let eval_box_free (config : config) (generics : generic_args) (** Evaluate a non-local function call in concrete mode *) let eval_assumed_function_call_concrete (config : config) (fid : assumed_fun_id) (call : call) : cm_fun = - let generics = call.func.generics in let args = call.args in let dest = call.dest in - (* Sanity check: we don't fully handle the const generic vars environment - in concrete mode yet *) - assert (generics.const_generics = []); - (* There are two cases (and this is extremely annoying): - - the function is not box_free - - the function is box_free - See {!eval_box_free} - *) - match fid with - | BoxFree -> - (* Degenerate case: box_free *) - eval_box_free config generics args dest - | _ -> - (* "Normal" case: not box_free *) - (* Evaluate the operands *) - (* let ctx, args_vl = eval_operands config ctx args in *) - let cf_eval_ops = eval_operands config args in - - (* Evaluate the call - * - * Style note: at some point we used {!comp_transmit} to - * transmit the result of {!eval_operands} above down to {!push_vars} - * below, without having to introduce an intermediary function call, - * but it made it less clear where the computed values came from, - * so we reversed the modifications. *) - let cf_eval_call cf (args_vl : typed_value list) : m_fun = - fun ctx -> - (* Push the stack frame: we initialize the frame with the return variable, - and one variable per input argument *) - let cc = push_frame in - - (* Create and push the return variable *) - let ret_vid = VarId.zero in - let ret_ty = get_assumed_function_return_type ctx fid generics in - let ret_var = mk_var ret_vid (Some "@return") ret_ty in - let cc = comp cc (push_uninitialized_var ret_var) in - - (* Create and push the input variables *) - let input_vars = - VarId.mapi_from1 - (fun id (v : typed_value) -> (mk_var id None v.ty, v)) - args_vl - in - let cc = comp cc (push_vars input_vars) in - - (* "Execute" the function body. As the functions are assumed, here we call - * custom functions to perform the proper manipulations: we don't have - * access to a body. *) - let cf_eval_body : cm_fun = - match fid with - | BoxNew -> eval_box_new_concrete config generics - | BoxFree -> - (* Should have been treated above *) raise (Failure "Unreachable") - | ArrayIndexShared | ArrayIndexMut | ArrayToSliceShared - | ArrayToSliceMut | ArrayRepeat | SliceIndexShared | SliceIndexMut -> - raise (Failure "Unimplemented") - in + match call.func with + | FnOpMove _ -> + (* Closure case: TODO *) + raise (Failure "Closures are not supported yet") + | FnOpRegular func -> ( + let generics = func.generics in + (* Sanity check: we don't fully handle the const generic vars environment + in concrete mode yet *) + assert (generics.const_generics = []); + (* There are two cases (and this is extremely annoying): + - the function is not box_free + - the function is box_free + See {!eval_box_free} + *) + match fid with + | BoxFree -> + (* Degenerate case: box_free *) + eval_box_free config generics args dest + | _ -> + (* "Normal" case: not box_free *) + (* Evaluate the operands *) + (* let ctx, args_vl = eval_operands config ctx args in *) + let cf_eval_ops = eval_operands config args in + + (* Evaluate the call + * + * Style note: at some point we used {!comp_transmit} to + * transmit the result of {!eval_operands} above down to {!push_vars} + * below, without having to introduce an intermediary function call, + * but it made it less clear where the computed values came from, + * so we reversed the modifications. *) + let cf_eval_call cf (args_vl : typed_value list) : m_fun = + fun ctx -> + (* Push the stack frame: we initialize the frame with the return variable, + and one variable per input argument *) + let cc = push_frame in + + (* Create and push the return variable *) + let ret_vid = VarId.zero in + let ret_ty = get_assumed_function_return_type ctx fid generics in + let ret_var = mk_var ret_vid (Some "@return") ret_ty in + let cc = comp cc (push_uninitialized_var ret_var) in + + (* Create and push the input variables *) + let input_vars = + VarId.mapi_from1 + (fun id (v : typed_value) -> (mk_var id None v.ty, v)) + args_vl + in + let cc = comp cc (push_vars input_vars) in + + (* "Execute" the function body. As the functions are assumed, here we call + * custom functions to perform the proper manipulations: we don't have + * access to a body. *) + let cf_eval_body : cm_fun = + match fid with + | BoxNew -> eval_box_new_concrete config generics + | BoxFree -> + (* Should have been treated above *) + raise (Failure "Unreachable") + | ArrayIndexShared | ArrayIndexMut | ArrayToSliceShared + | ArrayToSliceMut | ArrayRepeat | SliceIndexShared | SliceIndexMut + -> + raise (Failure "Unimplemented") + in - let cc = comp cc cf_eval_body in + let cc = comp cc cf_eval_body in - (* Pop the frame *) - let cc = comp cc (pop_frame_assign config dest) in + (* Pop the frame *) + let cc = comp cc (pop_frame_assign config dest) in - (* Continue *) - cc cf ctx - in - (* Compose and apply *) - comp cf_eval_ops cf_eval_call + (* Continue *) + cc cf ctx + in + (* Compose and apply *) + comp cf_eval_ops cf_eval_call) (** Helper @@ -652,6 +659,240 @@ let create_push_abstractions_from_abs_region_groups in List.fold_left insert_abs ctx empty_absl +(** Auxiliary helper for [eval_transparent_function_call_symbolic] + Instantiate the signature and introduce fresh abstractions and region ids while doing so. + + We perform some manipulations when instantiating the signature. + + # Trait impl calls + ================== + In particular, we have a special treatment of trait method calls when + the trait ref is a known impl. + + For instance: + {[ + trait HasValue { + fn has_value(&self) -> bool; + } + + impl<T> HasValue for Option<T> { + fn has_value(&self) { + match self { + None => false, + Some(_) => true, + } + } + } + + fn option_has_value<T>(x: &Option<T>) -> bool { + x.has_value() + } + ]} + + The generated code looks like this: + {[ + structure HasValue (Self : Type) = { + has_value : Self -> result bool + } + + let OptionHasValueImpl.has_value (Self : Type) (self : Self) : result bool = + match self with + | None => false + | Some _ => true + + let OptionHasValueInstance (T : Type) : HasValue (Option T) = { + has_value = OptionHasValueInstance.has_value + } + ]} + + In [option_has_value], we don't want to refer to the [has_value] method + of the instance of [HasValue] for [Option<T>]. We want to refer directly + to the function which implements [has_value] for [Option<T>]. + That is, instead of generating this: + {[ + let option_has_value (T : Type) (x : Option T) : result bool = + (OptionHasValueInstance T).has_value x + ]} + + We want to generate this: + {[ + let option_has_value (T : Type) (x : Option T) : result bool = + OptionHasValueImpl.has_value T x + ]} + + # Provided trait methods + ======================== + Calls to provided trait methods also have a special treatment because + for now we forbid overriding provided trait methods in the trait implementations, + which means that whenever we call a provided trait method, we do not refer + to a trait clause but directly to the method provided in the trait declaration. + *) +let eval_transparent_function_call_symbolic_inst (call : call) (ctx : eval_ctx) + : fun_id_or_trait_method_ref * generic_args * fun_decl * inst_fun_sig = + match call.func with + | FnOpMove _ -> + (* Closure case: TODO *) + raise (Failure "Closures are not supported yet") + | FnOpRegular func -> ( + match func.func with + | FunId (FRegular fid) -> + let def = ctx_lookup_fun_decl ctx fid in + log#ldebug + (lazy + ("fun call:\n- call: " ^ call_to_string ctx call + ^ "\n- call.generics:\n" + ^ generic_args_to_string ctx func.generics + ^ "\n- def.signature:\n" + ^ fun_sig_to_string ctx def.signature)); + let tr_self = UnknownTrait __FUNCTION__ in + let regions_hierarchy = + LlbcAstUtils.FunIdMap.find (FRegular fid) + ctx.fun_context.regions_hierarchies + in + let inst_sg = + instantiate_fun_sig ctx func.generics tr_self def.signature + regions_hierarchy + in + (func.func, func.generics, def, inst_sg) + | FunId (FAssumed _) -> + (* Unreachable: must be a transparent function *) + raise (Failure "Unreachable") + | TraitMethod (trait_ref, method_name, _) -> ( + log#ldebug + (lazy + ("trait method call:\n- call: " ^ call_to_string ctx call + ^ "\n- method name: " ^ method_name ^ "\n- call.generics:\n" + ^ generic_args_to_string ctx func.generics + ^ "\n- trait and method generics:\n" + ^ generic_args_to_string ctx + (Option.get func.trait_and_method_generic_args))); + (* When instantiating, we need to group the generics for the trait ref + and the method *) + let generics = Option.get func.trait_and_method_generic_args in + (* Lookup the trait method signature - there are several possibilities + depending on whethere we call a top-level trait method impl or the + method from a local clause *) + match trait_ref.trait_id with + | TraitImpl impl_id -> ( + (* Lookup the trait impl *) + let trait_impl = ctx_lookup_trait_impl ctx impl_id in + log#ldebug + (lazy ("trait impl: " ^ trait_impl_to_string ctx trait_impl)); + (* First look in the required methods *) + let method_id = + List.find_opt + (fun (s, _) -> s = method_name) + trait_impl.required_methods + in + match method_id with + | Some (_, id) -> + (* This is a required method *) + let method_def = ctx_lookup_fun_decl ctx id in + (* Instantiate *) + let tr_self = TraitRef trait_ref in + let fid : fun_id = FRegular id in + let regions_hierarchy = + LlbcAstUtils.FunIdMap.find fid + ctx.fun_context.regions_hierarchies + in + let inst_sg = + instantiate_fun_sig ctx generics tr_self + method_def.signature regions_hierarchy + in + (* Also update the function identifier: we want to forget + the fact that we called a trait method, and treat it as + a regular function call to the top-level function + which implements the method. In order to do this properly, + we also need to update the generics. + *) + let func = FunId fid in + (func, generics, method_def, inst_sg) + | None -> + (* If not found, lookup the methods provided by the trait *declaration* + (remember: for now, we forbid overriding provided methods) *) + assert (trait_impl.provided_methods = []); + let trait_decl = + ctx_lookup_trait_decl ctx + trait_ref.trait_decl_ref.trait_decl_id + in + let _, method_id = + List.find + (fun (s, _) -> s = method_name) + trait_decl.provided_methods + in + let method_id = Option.get method_id in + let method_def = ctx_lookup_fun_decl ctx method_id in + (* For the instantiation we have to do something peculiar + because the method was defined for the trait declaration. + We have to group: + - the parameters given to the trait decl reference + - the parameters given to the method itself + For instance: + {[ + trait Foo<T> { + fn f<U>(...) { ... } + } + + fn g<G>(x : G) where Clause0: Foo<G, bool> + { + x.f::<u32>(...) // The arguments to f are: <G, bool, u32> + } + ]} + *) + let all_generics = + TypesUtils.merge_generic_args + trait_ref.trait_decl_ref.decl_generics func.generics + in + log#ldebug + (lazy + ("provided method call:" ^ "\n- method name: " + ^ method_name ^ "\n- all_generics:\n" + ^ generic_args_to_string ctx all_generics + ^ "\n- parent params info: " + ^ Print.option_to_string show_params_info + method_def.signature.parent_params_info)); + let regions_hierarchy = + LlbcAstUtils.FunIdMap.find (FRegular method_id) + ctx.fun_context.regions_hierarchies + in + let tr_self = TraitRef trait_ref in + let inst_sg = + instantiate_fun_sig ctx all_generics tr_self + method_def.signature regions_hierarchy + in + (func.func, func.generics, method_def, inst_sg)) + | _ -> + (* We are using a local clause - we lookup the trait decl *) + let trait_decl = + ctx_lookup_trait_decl ctx trait_ref.trait_decl_ref.trait_decl_id + in + (* Lookup the method decl in the required *and* the provided methods *) + let _, method_id = + let provided = + List.filter_map + (fun (id, f) -> + match f with None -> None | Some f -> Some (id, f)) + trait_decl.provided_methods + in + List.find + (fun (s, _) -> s = method_name) + (List.append trait_decl.required_methods provided) + in + let method_def = ctx_lookup_fun_decl ctx method_id in + log#ldebug + (lazy ("method:\n" ^ fun_decl_to_string ctx method_def)); + (* Instantiate *) + let regions_hierarchy = + LlbcAstUtils.FunIdMap.find (FRegular method_id) + ctx.fun_context.regions_hierarchies + in + let tr_self = TraitRef trait_ref in + let inst_sg = + instantiate_fun_sig ctx generics tr_self method_def.signature + regions_hierarchy + in + (func.func, func.generics, method_def, inst_sg))) + (** Evaluate a statement *) let rec eval_statement (config : config) (st : statement) : st_cm_fun = fun cf ctx -> @@ -761,7 +1002,7 @@ and eval_global (config : config) (dest : place) (gid : GlobalDeclId.id) : trait_and_method_generic_args = None; } in - let call = { func; args = []; dest } in + let call = { func = FnOpRegular func; args = []; dest } in (eval_transparent_function_call_concrete config global.body call) cf ctx | SymbolicMode -> (* Generate a fresh symbolic value. In the translation, this fresh symbolic value will be @@ -915,337 +1156,126 @@ and eval_function_call (config : config) (call : call) : st_cm_fun = and eval_function_call_concrete (config : config) (call : call) : st_cm_fun = fun cf ctx -> - match call.func.func with - | FunId (FRegular fid) -> - eval_transparent_function_call_concrete config fid call cf ctx - | FunId (FAssumed fid) -> - (* Continue - note that we do as if the function call has been successful, - * by giving {!Unit} to the continuation, because we place us in the case - * where we haven't panicked. Of course, the translation needs to take the - * panic case into account... *) - eval_assumed_function_call_concrete config fid call (cf Unit) ctx - | TraitMethod _ -> raise (Failure "Unimplemented") + match call.func with + | FnOpMove _ -> raise (Failure "Closures are not supported yet") + | FnOpRegular func -> ( + match func.func with + | FunId (FRegular fid) -> + eval_transparent_function_call_concrete config fid call cf ctx + | FunId (FAssumed fid) -> + (* Continue - note that we do as if the function call has been successful, + * by giving {!Unit} to the continuation, because we place us in the case + * where we haven't panicked. Of course, the translation needs to take the + * panic case into account... *) + eval_assumed_function_call_concrete config fid call (cf Unit) ctx + | TraitMethod _ -> raise (Failure "Unimplemented")) and eval_function_call_symbolic (config : config) (call : call) : st_cm_fun = - match call.func.func with - | FunId (FRegular _) | TraitMethod _ -> - eval_transparent_function_call_symbolic config call - | FunId (FAssumed fid) -> eval_assumed_function_call_symbolic config fid call + match call.func with + | FnOpMove _ -> raise (Failure "Closures are not supported yet") + | FnOpRegular func -> ( + match func.func with + | FunId (FRegular _) | TraitMethod _ -> + eval_transparent_function_call_symbolic config call + | FunId (FAssumed fid) -> + eval_assumed_function_call_symbolic config fid call func) (** Evaluate a local (i.e., non-assumed) function call in concrete mode *) and eval_transparent_function_call_concrete (config : config) (fid : FunDeclId.id) (call : call) : st_cm_fun = - let generics = call.func.generics in let args = call.args in let dest = call.dest in - (* Sanity check: we don't fully handle the const generic vars environment - in concrete mode yet *) - assert (generics.const_generics = []); - fun cf ctx -> - (* Retrieve the (correctly instantiated) body *) - let def = ctx_lookup_fun_decl ctx fid in - (* We can evaluate the function call only if it is not opaque *) - let body = - match def.body with - | None -> - raise - (Failure - ("Can't evaluate a call to an opaque function: " - ^ name_to_string ctx def.name)) - | Some body -> body - in - (* TODO: we need to normalize the types if we want to correctly support traits *) - assert (generics.trait_refs = []); - (* There shouldn't be any reference to Self *) - let tr_self = UnknownTrait __FUNCTION__ in - let subst = - Subst.make_subst_from_generics def.signature.generics generics tr_self - in - let locals, body_st = Subst.fun_body_substitute_in_body subst body in - - (* Evaluate the input operands *) - assert (List.length args = body.arg_count); - let cc = eval_operands config args in - - (* Push a frame delimiter - we use {!comp_transmit} to transmit the result - * of the operands evaluation from above to the functions afterwards, while - * ignoring it in this function *) - let cc = comp_transmit cc push_frame in - - (* Compute the initial values for the local variables *) - (* 1. Push the return value *) - let ret_var, locals = - match locals with - | ret_ty :: locals -> (ret_ty, locals) - | _ -> raise (Failure "Unreachable") - in - let input_locals, locals = - Collections.List.split_at locals body.arg_count - in + match call.func with + | FnOpMove _ -> raise (Failure "Closures are not supported yet") + | FnOpRegular func -> + let generics = func.generics in + (* Sanity check: we don't fully handle the const generic vars environment + in concrete mode yet *) + assert (generics.const_generics = []); + fun cf ctx -> + (* Retrieve the (correctly instantiated) body *) + let def = ctx_lookup_fun_decl ctx fid in + (* We can evaluate the function call only if it is not opaque *) + let body = + match def.body with + | None -> + raise + (Failure + ("Can't evaluate a call to an opaque function: " + ^ name_to_string ctx def.name)) + | Some body -> body + in + (* TODO: we need to normalize the types if we want to correctly support traits *) + assert (generics.trait_refs = []); + (* There shouldn't be any reference to Self *) + let tr_self = UnknownTrait __FUNCTION__ in + let subst = + Subst.make_subst_from_generics def.signature.generics generics tr_self + in + let locals, body_st = Subst.fun_body_substitute_in_body subst body in + + (* Evaluate the input operands *) + assert (List.length args = body.arg_count); + let cc = eval_operands config args in + + (* Push a frame delimiter - we use {!comp_transmit} to transmit the result + * of the operands evaluation from above to the functions afterwards, while + * ignoring it in this function *) + let cc = comp_transmit cc push_frame in + + (* Compute the initial values for the local variables *) + (* 1. Push the return value *) + let ret_var, locals = + match locals with + | ret_ty :: locals -> (ret_ty, locals) + | _ -> raise (Failure "Unreachable") + in + let input_locals, locals = + Collections.List.split_at locals body.arg_count + in - let cc = comp_transmit cc (push_var ret_var (mk_bottom ret_var.var_ty)) in + let cc = + comp_transmit cc (push_var ret_var (mk_bottom ret_var.var_ty)) + in - (* 2. Push the input values *) - let cf_push_inputs cf args = - let inputs = List.combine input_locals args in - (* Note that this function checks that the variables and their values - * have the same type (this is important) *) - push_vars inputs cf - in - let cc = comp cc cf_push_inputs in - - (* 3. Push the remaining local variables (initialized as {!Bottom}) *) - let cc = comp cc (push_uninitialized_vars locals) in - - (* Execute the function body *) - let cc = comp cc (eval_function_body config body_st) in - - (* Pop the stack frame and move the return value to its destination *) - let cf_finish cf res = - match res with - | Panic -> cf Panic - | Return -> - (* Pop the stack frame, retrieve the return value, move it to - * its destination and continue *) - pop_frame_assign config dest (cf Unit) - | Break _ | Continue _ | Unit | LoopReturn _ | EndEnterLoop _ - | EndContinue _ -> - raise (Failure "Unreachable") - in - let cc = comp cc cf_finish in + (* 2. Push the input values *) + let cf_push_inputs cf args = + let inputs = List.combine input_locals args in + (* Note that this function checks that the variables and their values + * have the same type (this is important) *) + push_vars inputs cf + in + let cc = comp cc cf_push_inputs in - (* Continue *) - cc cf ctx + (* 3. Push the remaining local variables (initialized as {!Bottom}) *) + let cc = comp cc (push_uninitialized_vars locals) in + + (* Execute the function body *) + let cc = comp cc (eval_function_body config body_st) in + + (* Pop the stack frame and move the return value to its destination *) + let cf_finish cf res = + match res with + | Panic -> cf Panic + | Return -> + (* Pop the stack frame, retrieve the return value, move it to + * its destination and continue *) + pop_frame_assign config dest (cf Unit) + | Break _ | Continue _ | Unit | LoopReturn _ | EndEnterLoop _ + | EndContinue _ -> + raise (Failure "Unreachable") + in + let cc = comp cc cf_finish in + + (* Continue *) + cc cf ctx (** Evaluate a local (i.e., non-assumed) function call in symbolic mode *) and eval_transparent_function_call_symbolic (config : config) (call : call) : st_cm_fun = fun cf ctx -> - (* Instantiate the signature and introduce fresh abstractions and region ids while doing so. - - We perform some manipulations when instantiating the signature. - - # Trait impl calls - ================== - In particular, we have a special treatment of trait method calls when - the trait ref is a known impl. - - For instance: - {[ - trait HasValue { - fn has_value(&self) -> bool; - } - - impl<T> HasValue for Option<T> { - fn has_value(&self) { - match self { - None => false, - Some(_) => true, - } - } - } - - fn option_has_value<T>(x: &Option<T>) -> bool { - x.has_value() - } - ]} - - The generated code looks like this: - {[ - structure HasValue (Self : Type) = { - has_value : Self -> result bool - } - - let OptionHasValueImpl.has_value (Self : Type) (self : Self) : result bool = - match self with - | None => false - | Some _ => true - - let OptionHasValueInstance (T : Type) : HasValue (Option T) = { - has_value = OptionHasValueInstance.has_value - } - ]} - - In [option_has_value], we don't want to refer to the [has_value] method - of the instance of [HasValue] for [Option<T>]. We want to refer directly - to the function which implements [has_value] for [Option<T>]. - That is, instead of generating this: - {[ - let option_has_value (T : Type) (x : Option T) : result bool = - (OptionHasValueInstance T).has_value x - ]} - - We want to generate this: - {[ - let option_has_value (T : Type) (x : Option T) : result bool = - OptionHasValueImpl.has_value T x - ]} - - # Provided trait methods - ======================== - Calls to provided trait methods also have a special treatment because - for now we forbid overriding provided trait methods in the trait implementations, - which means that whenever we call a provided trait method, we do not refer - to a trait clause but directly to the method provided in the trait declaration. - *) let func, generics, def, inst_sg = - match call.func.func with - | FunId (FRegular fid) -> - let def = ctx_lookup_fun_decl ctx fid in - log#ldebug - (lazy - ("fun call:\n- call: " ^ call_to_string ctx call - ^ "\n- call.generics:\n" - ^ generic_args_to_string ctx call.func.generics - ^ "\n- def.signature:\n" - ^ fun_sig_to_string ctx def.signature)); - let tr_self = UnknownTrait __FUNCTION__ in - let regions_hierarchy = - LlbcAstUtils.FunIdMap.find (FRegular fid) - ctx.fun_context.regions_hierarchies - in - let inst_sg = - instantiate_fun_sig ctx call.func.generics tr_self def.signature - regions_hierarchy - in - (call.func.func, call.func.generics, def, inst_sg) - | FunId (FAssumed _) -> - (* Unreachable: must be a transparent function *) - raise (Failure "Unreachable") - | TraitMethod (trait_ref, method_name, _) -> ( - log#ldebug - (lazy - ("trait method call:\n- call: " ^ call_to_string ctx call - ^ "\n- method name: " ^ method_name ^ "\n- call.generics:\n" - ^ generic_args_to_string ctx call.func.generics - ^ "\n- trait and method generics:\n" - ^ generic_args_to_string ctx - (Option.get call.func.trait_and_method_generic_args))); - (* When instantiating, we need to group the generics for the trait ref - and the method *) - let generics = Option.get call.func.trait_and_method_generic_args in - (* Lookup the trait method signature - there are several possibilities - depending on whethere we call a top-level trait method impl or the - method from a local clause *) - match trait_ref.trait_id with - | TraitImpl impl_id -> ( - (* Lookup the trait impl *) - let trait_impl = ctx_lookup_trait_impl ctx impl_id in - log#ldebug - (lazy ("trait impl: " ^ trait_impl_to_string ctx trait_impl)); - (* First look in the required methods *) - let method_id = - List.find_opt - (fun (s, _) -> s = method_name) - trait_impl.required_methods - in - match method_id with - | Some (_, id) -> - (* This is a required method *) - let method_def = ctx_lookup_fun_decl ctx id in - (* Instantiate *) - let tr_self = TraitRef trait_ref in - let fid : fun_id = FRegular id in - let regions_hierarchy = - LlbcAstUtils.FunIdMap.find fid - ctx.fun_context.regions_hierarchies - in - let inst_sg = - instantiate_fun_sig ctx generics tr_self method_def.signature - regions_hierarchy - in - (* Also update the function identifier: we want to forget - the fact that we called a trait method, and treat it as - a regular function call to the top-level function - which implements the method. In order to do this properly, - we also need to update the generics. - *) - let func = FunId fid in - (func, generics, method_def, inst_sg) - | None -> - (* If not found, lookup the methods provided by the trait *declaration* - (remember: for now, we forbid overriding provided methods) *) - assert (trait_impl.provided_methods = []); - let trait_decl = - ctx_lookup_trait_decl ctx - trait_ref.trait_decl_ref.trait_decl_id - in - let _, method_id = - List.find - (fun (s, _) -> s = method_name) - trait_decl.provided_methods - in - let method_id = Option.get method_id in - let method_def = ctx_lookup_fun_decl ctx method_id in - (* For the instantiation we have to do something peculiar - because the method was defined for the trait declaration. - We have to group: - - the parameters given to the trait decl reference - - the parameters given to the method itself - For instance: - {[ - trait Foo<T> { - fn f<U>(...) { ... } - } - - fn g<G>(x : G) where Clause0: Foo<G, bool> - { - x.f::<u32>(...) // The arguments to f are: <G, bool, u32> - } - ]} - *) - let all_generics = - TypesUtils.merge_generic_args - trait_ref.trait_decl_ref.decl_generics call.func.generics - in - log#ldebug - (lazy - ("provided method call:" ^ "\n- method name: " ^ method_name - ^ "\n- all_generics:\n" - ^ generic_args_to_string ctx all_generics - ^ "\n- parent params info: " - ^ Print.option_to_string show_params_info - method_def.signature.parent_params_info)); - let regions_hierarchy = - LlbcAstUtils.FunIdMap.find (FRegular method_id) - ctx.fun_context.regions_hierarchies - in - let tr_self = TraitRef trait_ref in - let inst_sg = - instantiate_fun_sig ctx all_generics tr_self - method_def.signature regions_hierarchy - in - (call.func.func, call.func.generics, method_def, inst_sg)) - | _ -> - (* We are using a local clause - we lookup the trait decl *) - let trait_decl = - ctx_lookup_trait_decl ctx trait_ref.trait_decl_ref.trait_decl_id - in - (* Lookup the method decl in the required *and* the provided methods *) - let _, method_id = - let provided = - List.filter_map - (fun (id, f) -> - match f with None -> None | Some f -> Some (id, f)) - trait_decl.provided_methods - in - List.find - (fun (s, _) -> s = method_name) - (List.append trait_decl.required_methods provided) - in - let method_def = ctx_lookup_fun_decl ctx method_id in - log#ldebug (lazy ("method:\n" ^ fun_decl_to_string ctx method_def)); - (* Instantiate *) - let regions_hierarchy = - LlbcAstUtils.FunIdMap.find (FRegular method_id) - ctx.fun_context.regions_hierarchies - in - let tr_self = TraitRef trait_ref in - let inst_sg = - instantiate_fun_sig ctx generics tr_self method_def.signature - regions_hierarchy - in - (call.func.func, call.func.generics, method_def, inst_sg)) + eval_transparent_function_call_symbolic_inst call ctx in (* Sanity check *) assert (List.length call.args = List.length def.signature.inputs); @@ -1408,9 +1438,9 @@ and eval_function_call_symbolic_from_inst_sig (config : config) (** Evaluate a non-local function call in symbolic mode *) and eval_assumed_function_call_symbolic (config : config) (fid : assumed_fun_id) - (call : call) : st_cm_fun = + (call : call) (func : fn_ptr) : st_cm_fun = fun cf ctx -> - let generics = call.func.generics in + let generics = func.generics in let args = call.args in let dest = call.dest in (* Sanity check: make sure the type parameters don't contain regions - diff --git a/compiler/InterpreterUtils.ml b/compiler/InterpreterUtils.ml index bba88e9f..612d6903 100644 --- a/compiler/InterpreterUtils.ml +++ b/compiler/InterpreterUtils.ml @@ -455,7 +455,7 @@ let initialize_eval_context (ctx : decls_ctx) *) let instantiate_fun_sig (ctx : eval_ctx) (generics : generic_args) (tr_self : trait_instance_id) (sg : fun_sig) - (regions_hierarchy : region_groups) : inst_fun_sig = + (regions_hierarchy : region_var_groups) : inst_fun_sig = log#ldebug (lazy ("instantiate_fun_sig:" ^ "\n- generics: " @@ -484,7 +484,11 @@ let instantiate_fun_sig (ctx : eval_ctx) (generics : generic_args) RegionGroupId.Map.find rg_id asubst_map in (* Generate fresh regions and their substitutions *) - let _, rsubst, _ = Substitute.fresh_regions_with_substs sg.generics.regions in + let _, rsubst, _ = + Substitute.fresh_regions_with_substs_from_vars ~fail_if_not_found:true + sg.generics.regions + in + let rsubst r = Option.get (rsubst r) in (* Generate the type substitution Note that for now we don't support instantiating the type parameters with types containing regions. *) diff --git a/compiler/LlbcAst.ml b/compiler/LlbcAst.ml index 9772671e..e071b36f 100644 --- a/compiler/LlbcAst.ml +++ b/compiler/LlbcAst.ml @@ -2,7 +2,9 @@ open Types open Values include Charon.LlbcAst -type abs_region_group = AbstractionId.id g_region_group [@@deriving show] +type abs_region_group = (RegionId.id, AbstractionId.id) g_region_group +[@@deriving show] + type abs_region_groups = abs_region_group list [@@deriving show] (** A function signature, after instantiation *) diff --git a/compiler/Print.ml b/compiler/Print.ml index 92ce6f23..0e2ec1fc 100644 --- a/compiler/Print.ml +++ b/compiler/Print.ml @@ -393,7 +393,6 @@ module Contexts = struct let global_decls = ctx.global_ctx.global_decls in let trait_decls = ctx.trait_decls_ctx.trait_decls in let trait_impls = ctx.trait_impls_ctx.trait_impls in - let generics = TypesUtils.empty_generic_params in let preds = TypesUtils.empty_predicates in { type_decls; @@ -401,7 +400,10 @@ module Contexts = struct global_decls; trait_decls; trait_impls; - generics; + regions = []; + types = []; + const_generics = []; + trait_clauses = []; preds; locals = []; } @@ -415,16 +417,6 @@ module Contexts = struct (* Below: it is always safe to omit fields - if an id can't be found at printing time, we print the id (in raw form) instead of the name it designates. *) - let generics : generic_params = - { - types = ctx.type_vars; - (* The regions have been transformed to region groups *) - regions = []; - const_generics = ctx.const_generic_vars; - (* We don't need the trait clauses so we initialize them to empty *) - trait_clauses = []; - } - in (* We don't need the predicates so we initialize them to empty *) let preds = empty_predicates in (* For the locals: we retrieve the information from the environment. @@ -444,7 +436,12 @@ module Contexts = struct global_decls; trait_decls; trait_impls; - generics; + types = ctx.type_vars; + (* The regions have been transformed to region groups *) + regions = []; + const_generics = ctx.const_generic_vars; + (* We don't need the trait clauses so we initialize them to empty *) + trait_clauses = []; preds; locals; } @@ -596,7 +593,7 @@ module EvalCtx = struct let fun_id_or_trait_method_ref_to_string (ctx : eval_ctx) (x : fun_id_or_trait_method_ref) : string = let env = eval_ctx_to_fmt_env ctx in - fun_id_or_trait_method_ref_to_string env x "..." + fun_id_or_trait_method_ref_to_string env x let statement_to_string (ctx : eval_ctx) (indent : string) (indent_incr : string) (e : statement) : string = diff --git a/compiler/PrintPure.ml b/compiler/PrintPure.ml index 5d8297d3..d33a2f18 100644 --- a/compiler/PrintPure.ml +++ b/compiler/PrintPure.ml @@ -56,7 +56,10 @@ let fmt_env_to_llbc_fmt_env (env : fmt_env) : Print.fmt_env = global_decls = env.global_decls; trait_decls = env.trait_decls; trait_impls = env.trait_impls; - generics = TypesUtils.empty_generic_params; + regions = []; + types = []; + const_generics = []; + trait_clauses = []; preds = TypesUtils.empty_predicates; locals = []; } diff --git a/compiler/RegionsHierarchy.ml b/compiler/RegionsHierarchy.ml index e101ba49..80b67a54 100644 --- a/compiler/RegionsHierarchy.ml +++ b/compiler/RegionsHierarchy.ml @@ -23,6 +23,8 @@ have to compute the SCCs of the lifetimes (two lifetimes 'a and 'b may satisfy 'a : 'b and 'b : 'a, meaning they are actually equal and should be grouped together). + + TODO: we don't handle locally bound regions yet. *) open Types @@ -42,7 +44,7 @@ let compute_regions_hierarchy_for_sig (type_decls : type_decl TypeDeclId.Map.t) (global_decls : global_decl GlobalDeclId.Map.t) (trait_decls : trait_decl TraitDeclId.Map.t) (trait_impls : trait_impl TraitImplId.Map.t) (fun_name : string) - (sg : fun_sig) : region_groups = + (sg : fun_sig) : region_var_groups = log#ldebug (lazy (__FUNCTION__ ^ ": " ^ fun_name)); (* Initialize a normalization context (we may need to normalize some associated types) *) @@ -74,12 +76,27 @@ let compute_regions_hierarchy_for_sig (type_decls : type_decl TypeDeclId.Map.t) - the region variables - the static region - edges from the region variables to the static region + + Note that we introduce free variables for all the regions bound at the + level of the signature (this excludes the regions locally bound inside + the types, for instance at the level of an arrow type). *) + let bound_regions, bound_regions_id_subst, bound_regions_subst = + Subst.fresh_regions_with_substs_from_vars ~fail_if_not_found:true + sg.generics.regions + in + let region_id_to_var_map : RegionVarId.id RegionId.Map.t = + RegionId.Map.of_list + (List.combine bound_regions + (List.map (fun (r : region_var) -> r.index) sg.generics.regions)) + in + let subst = { Subst.empty_subst with r_subst = bound_regions_subst } in let g : RegionSet.t RegionMap.t ref = let s_set = RegionSet.singleton RStatic in let m = List.map - (fun (r : region_var) -> (RVar r.index, s_set)) + (fun (r : region_var) -> + (RFVar (Option.get (bound_regions_id_subst r.index)), s_set)) sg.generics.regions in let s = (RStatic, RegionSet.empty) in @@ -87,10 +104,17 @@ let compute_regions_hierarchy_for_sig (type_decls : type_decl TypeDeclId.Map.t) in let add_edge ~(short : region) ~(long : region) = - let m = !g in - let s = RegionMap.find short !g in - let s = RegionSet.add long s in - g := RegionMap.add short s m + (* Sanity checks *) + assert (short <> RErased); + assert (long <> RErased); + (* Ignore the locally bound regions (at the level of arrow types for instance *) + match (short, long) with + | RBVar _, _ | _, RBVar _ -> () + | _, _ -> + let m = !g in + let s = RegionMap.find short !g in + let s = RegionSet.add long s in + g := RegionMap.add short s m in let add_edge_from_region_constraint ((long, short) : region_outlives) = @@ -152,22 +176,30 @@ let compute_regions_hierarchy_for_sig (type_decls : type_decl TypeDeclId.Map.t) AssociatedTypes.trait_instance_id_is_local_clause trait_ref.trait_id); (* We have nothing to do *) () - | TArrow (inputs, output) -> - (* TODO: this may be too constraining *) - List.iter (explore_ty outer) (output :: inputs) + | TArrow (regions, inputs, output) -> + (* TODO: *) + assert (regions = []); + (* We can ignore the outer regions *) + List.iter (explore_ty []) (output :: inputs) and explore_generics (outer : region list) (generics : generic_args) = let { regions; types; const_generics = _; trait_refs = _ } = generics in List.iter (fun long -> add_edges ~long ~shorts:outer) regions; List.iter (explore_ty outer) types in + (* Substitute the regions in a type, then explore *) + let explore_ty_subst ty = + let ty = Subst.ty_substitute subst ty in + explore_ty [] ty + in + (* Normalize the types then explore *) let tys = List.map (AssociatedTypes.norm_ctx_normalize_ty norm_ctx) (sg.output :: sg.inputs) in - List.iter (explore_ty []) tys; + List.iter explore_ty_subst tys; (* Compute the ordered SCCs *) let module Scc = SCC.Make (RegionOrderedType) in @@ -240,10 +272,12 @@ let compute_regions_hierarchy_for_sig (type_decls : type_decl TypeDeclId.Map.t) let id = RegionGroupId.of_int i in (* Retrieve the set of regions in the group *) - let regions = + let regions : RegionVarId.id list = List.map (fun r -> - match r with RVar r -> r | _ -> raise (Failure "Unreachable")) + match r with + | RFVar rid -> RegionId.Map.find rid region_id_to_var_map + | _ -> raise (Failure "Unreachable")) scc in @@ -262,7 +296,8 @@ let compute_regions_hierarchies (type_decls : type_decl TypeDeclId.Map.t) (fun_decls : fun_decl FunDeclId.Map.t) (global_decls : global_decl GlobalDeclId.Map.t) (trait_decls : trait_decl TraitDeclId.Map.t) - (trait_impls : trait_impl TraitImplId.Map.t) : region_groups FunIdMap.t = + (trait_impls : trait_impl TraitImplId.Map.t) : region_var_groups FunIdMap.t + = let open Print in let env : fmt_env = { @@ -271,7 +306,10 @@ let compute_regions_hierarchies (type_decls : type_decl TypeDeclId.Map.t) global_decls; trait_decls; trait_impls; - generics = empty_generic_params; + regions = []; + types = []; + const_generics = []; + trait_clauses = []; preds = empty_predicates; locals = []; } diff --git a/compiler/Substitute.ml b/compiler/Substitute.ml index a05b2c5a..e28f005d 100644 --- a/compiler/Substitute.ml +++ b/compiler/Substitute.ml @@ -11,6 +11,9 @@ open Contexts type subst = { r_subst : region -> region; + (** Remark: this might be called with bound regions with a negative + DeBruijn index. A negative DeBruijn index means that the region + is locally bound. *) ty_subst : TypeVarId.id -> ty; cg_subst : ConstGenericVarId.id -> const_generic; (** Substitution from *local* trait clause to trait instance *) @@ -19,11 +22,35 @@ type subst = { tr_self : trait_instance_id; } +let empty_subst : subst = + { + r_subst = (fun x -> x); + ty_subst = (fun id -> TVar id); + cg_subst = (fun id -> CgVar id); + tr_subst = (fun id -> Clause id); + tr_self = Self; + } + let st_substitute_visitor (subst : subst) = - object + object (self) inherit [_] map_statement - method! visit_region _ r = subst.r_subst r - method! visit_TVar _ id = subst.ty_subst id + method! visit_region (subst : subst) r = subst.r_subst r + + (** We need to properly handle the DeBruijn indices *) + method! visit_TArrow subst regions inputs output = + (* Decrement the DeBruijn indices before calling the substitution *) + let r_subst r = + match r with + | RBVar (db, rid) -> subst.r_subst (RBVar (db - 1, rid)) + | _ -> subst.r_subst r + in + let subst = { subst with r_subst } in + (* Note that we ignore the bound regions variables *) + let inputs = List.map (self#visit_ty subst) inputs in + let output = self#visit_ty subst output in + TArrow (regions, inputs, output) + + method! visit_TVar (subst : subst) id = subst.ty_subst id method! visit_type_var_id _ _ = (* We should never get here because we reimplemented [visit_TypeVar] *) @@ -35,8 +62,8 @@ let st_substitute_visitor (subst : subst) = (* We should never get here because we reimplemented [visit_Var] *) raise (Failure "Unexpected") - method! visit_Clause _ id = subst.tr_subst id - method! visit_Self _ = subst.tr_self + method! visit_Clause (subst : subst) id = subst.tr_subst id + method! visit_Self (subst : subst) = subst.tr_self end (** Substitute types variables and regions in a type. @@ -45,27 +72,27 @@ let st_substitute_visitor (subst : subst) = *) let ty_substitute (subst : subst) (ty : ty) : ty = let visitor = st_substitute_visitor subst in - visitor#visit_ty () ty + visitor#visit_ty subst ty (** **IMPORTANT**: this doesn't normalize the types. *) let trait_ref_substitute (subst : subst) (tr : trait_ref) : trait_ref = let visitor = st_substitute_visitor subst in - visitor#visit_trait_ref () tr + visitor#visit_trait_ref subst tr (** **IMPORTANT**: this doesn't normalize the types. *) let trait_instance_id_substitute (subst : subst) (tr : trait_instance_id) : trait_instance_id = let visitor = st_substitute_visitor subst in - visitor#visit_trait_instance_id () tr + visitor#visit_trait_instance_id subst tr (** **IMPORTANT**: this doesn't normalize the types. *) let generic_args_substitute (subst : subst) (g : generic_args) : generic_args = let visitor = st_substitute_visitor subst in - visitor#visit_generic_args () g + visitor#visit_generic_args subst g let predicates_substitute (subst : subst) (p : predicates) : predicates = let visitor = st_substitute_visitor subst in - visitor#visit_predicates () p + visitor#visit_predicates subst p let erase_regions_subst : subst = { @@ -96,26 +123,40 @@ let generic_args_erase_regions (tr : generic_args) : generic_args = TODO: simplify? we only need the subst [RegionVarId.id -> RegionId.id] *) -let fresh_regions_with_substs (region_vars : region_var list) : - RegionId.id list * (RegionId.id -> RegionId.id) * (region -> region) = +let fresh_regions_with_substs ~(fail_if_not_found : bool) + (region_vars : RegionVarId.id list) : + RegionId.id list + * (RegionVarId.id -> RegionId.id option) + * (region -> region) = (* Generate fresh regions *) let fresh_region_ids = List.map (fun _ -> fresh_region_id ()) region_vars in (* Generate the map from region var ids to regions *) let ls = List.combine region_vars fresh_region_ids in - let rid_map = - List.fold_left - (fun mp ((k : region_var), v) -> RegionId.Map.add k.index v mp) - RegionId.Map.empty ls - in + let rid_map = RegionVarId.Map.of_list ls in (* Generate the substitution from region var id to region *) - let rid_subst id = RegionId.Map.find id rid_map in + let rid_subst id = RegionVarId.Map.find_opt id rid_map in (* Generate the substitution from region to region *) let r_subst (r : region) = - match r with RStatic | RErased -> r | RVar id -> RVar (rid_subst id) + match r with + | RStatic | RErased | RFVar _ -> r + | RBVar (bdid, id) -> + if bdid = 0 then + match rid_subst id with + | None -> if fail_if_not_found then raise Not_found else r + | Some r -> RFVar r + else r in (* Return *) (fresh_region_ids, rid_subst, r_subst) +let fresh_regions_with_substs_from_vars ~(fail_if_not_found : bool) + (region_vars : region_var list) : + RegionId.id list + * (RegionVarId.id -> RegionId.id option) + * (region -> region) = + fresh_regions_with_substs ~fail_if_not_found + (List.map (fun (r : region_var) -> r.index) region_vars) + (** Erase the regions in a type and perform a substitution *) let erase_regions_substitute_types (ty_subst : TypeVarId.id -> ty) (cg_subst : ConstGenericVarId.id -> const_generic) @@ -127,16 +168,21 @@ let erase_regions_substitute_types (ty_subst : TypeVarId.id -> ty) (** Create a region substitution from a list of region variable ids and a list of regions (with which to substitute the region variable ids *) -let make_region_subst (var_ids : RegionId.id list) (regions : region list) : +let make_region_subst (var_ids : RegionVarId.id list) (regions : region list) : region -> region = let ls = List.combine var_ids regions in let mp = List.fold_left - (fun mp (k, v) -> RegionId.Map.add k v mp) - RegionId.Map.empty ls + (fun mp (k, v) -> RegionVarId.Map.add k v mp) + RegionVarId.Map.empty ls in fun r -> - match r with RStatic | RErased -> r | RVar id -> RegionId.Map.find id mp + match r with + | RStatic | RErased -> r + | RFVar _ -> raise (Failure "Unexpected") + | RBVar (bdid, id) -> + (* Only substitute the bound regions with DeBruijn index equal to 0 *) + if bdid = 0 then RegionVarId.Map.find id mp else r let make_region_subst_from_vars (vars : region_var list) (regions : region list) : region -> region = @@ -298,27 +344,27 @@ let ctx_adt_value_get_instantiated_field_types (ctx : eval_ctx) (** Apply a type substitution to a place *) let place_substitute (subst : subst) (p : place) : place = (* There is in fact nothing to do *) - (st_substitute_visitor subst)#visit_place () p + (st_substitute_visitor subst)#visit_place subst p (** Apply a type substitution to an operand *) let operand_substitute (subst : subst) (op : operand) : operand = - (st_substitute_visitor subst)#visit_operand () op + (st_substitute_visitor subst)#visit_operand subst op (** Apply a type substitution to an rvalue *) let rvalue_substitute (subst : subst) (rv : rvalue) : rvalue = - (st_substitute_visitor subst)#visit_rvalue () rv + (st_substitute_visitor subst)#visit_rvalue subst rv (** Apply a type substitution to an assertion *) let assertion_substitute (subst : subst) (a : assertion) : assertion = - (st_substitute_visitor subst)#visit_assertion () a + (st_substitute_visitor subst)#visit_assertion subst a (** Apply a type substitution to a call *) let call_substitute (subst : subst) (call : call) : call = - (st_substitute_visitor subst)#visit_call () call + (st_substitute_visitor subst)#visit_call subst call (** Apply a type substitution to a statement *) let statement_substitute (subst : subst) (st : statement) : statement = - (st_substitute_visitor subst)#visit_statement () st + (st_substitute_visitor subst)#visit_statement subst st (** Apply a type substitution to a function body. Return the local variables and the body. *) @@ -336,9 +382,9 @@ let trait_type_constraint_substitute (subst : subst) (ttc : trait_type_constraint) : trait_type_constraint = let { trait_ref; generics; type_name; ty } = ttc in let visitor = st_substitute_visitor subst in - let trait_ref = visitor#visit_trait_ref () trait_ref in - let generics = visitor#visit_generic_args () generics in - let ty = visitor#visit_ty () ty in + let trait_ref = visitor#visit_trait_ref subst trait_ref in + let generics = visitor#visit_generic_args subst generics in + let ty = visitor#visit_ty subst ty in { trait_ref; generics; type_name; ty } (** Substitute a function signature, together with the regions hierarchy @@ -347,18 +393,20 @@ let trait_type_constraint_substitute (subst : subst) **IMPORTANT:** this function doesn't normalize the types. *) let substitute_signature (asubst : RegionGroupId.id -> AbstractionId.id) - (r_subst : RegionId.id -> RegionId.id) (ty_subst : TypeVarId.id -> ty) + (r_subst : RegionVarId.id -> RegionId.id) (ty_subst : TypeVarId.id -> ty) (cg_subst : ConstGenericVarId.id -> const_generic) (tr_subst : TraitClauseId.id -> trait_instance_id) (tr_self : trait_instance_id) (sg : fun_sig) - (regions_hierarchy : region_groups) : inst_fun_sig = + (regions_hierarchy : region_var_groups) : inst_fun_sig = let r_subst' (r : region) : region = - match r with RStatic | RErased -> r | RVar rid -> RVar (r_subst rid) + match r with + | RStatic | RErased | RFVar _ -> r + | RBVar (bdid, rid) -> if bdid = 0 then RFVar (r_subst rid) else r in let subst = { r_subst = r_subst'; ty_subst; cg_subst; tr_subst; tr_self } in let inputs = List.map (ty_substitute subst) sg.inputs in let output = ty_substitute subst sg.output in - let subst_region_group (rg : region_group) : abs_region_group = + let subst_region_group (rg : region_var_group) : abs_region_group = let id = asubst rg.id in let regions = List.map r_subst rg.regions in let parents = List.map asubst rg.parents in diff --git a/compiler/SymbolicToPure.ml b/compiler/SymbolicToPure.ml index f5b055fd..b4611b7e 100644 --- a/compiler/SymbolicToPure.ml +++ b/compiler/SymbolicToPure.ml @@ -47,7 +47,7 @@ type fun_context = { llbc_fun_decls : A.fun_decl A.FunDeclId.Map.t; fun_sigs : fun_sig_named_outputs RegularFunIdNotLoopMap.t; (** *) fun_infos : fun_info A.FunDeclId.Map.t; - regions_hierarchies : T.region_groups FunIdMap.t; + regions_hierarchies : T.region_var_groups FunIdMap.t; } [@@deriving show] @@ -214,7 +214,9 @@ let bs_ctx_to_fmt_env (ctx : bs_ctx) : Print.fmt_env = let global_decls = ctx.global_context.llbc_global_decls in let trait_decls = ctx.trait_decls_ctx in let trait_impls = ctx.trait_impls_ctx in - let generics = ctx.fun_decl.signature.generics in + let { regions; types; const_generics; trait_clauses } : T.generic_params = + ctx.fun_decl.signature.generics + in let preds = ctx.fun_decl.signature.preds in { type_decls; @@ -222,7 +224,10 @@ let bs_ctx_to_fmt_env (ctx : bs_ctx) : Print.fmt_env = global_decls; trait_decls; trait_impls; - generics; + regions = [ regions ]; + types; + const_generics; + trait_clauses; preds; locals = []; } @@ -279,6 +284,10 @@ let texpression_to_string (ctx : bs_ctx) (e : texpression) : string = let env = bs_ctx_to_pure_fmt_env ctx in PrintPure.texpression_to_string env false "" " " e +let fun_id_to_string (ctx : bs_ctx) (id : A.fun_id) : string = + let env = bs_ctx_to_fmt_env ctx in + Print.Expressions.fun_id_to_string env id + let fun_sig_to_string (ctx : bs_ctx) (sg : fun_sig) : string = let env = bs_ctx_to_pure_fmt_env ctx in PrintPure.fun_sig_to_string env sg @@ -371,7 +380,7 @@ and translate_trait_instance_id (translate_ty : T.ty -> ty) let inst_id = translate_trait_instance_id inst_id in ItemClause (inst_id, decl_id, item_name, clause_id) | TraitRef tr -> TraitRef (translate_trait_ref translate_ty tr) - | FnPointer _ -> raise (Failure "TODO") + | FnPointer _ | Closure _ -> raise (Failure "Closures are not supported yet") | UnknownTrait s -> raise (Failure ("Unknown trait found: " ^ s)) (** Translate a signature type - TODO: factor out the different translation functions *) @@ -873,7 +882,7 @@ let translate_fun_sig (decls_ctx : C.decls_ctx) (fun_id : A.fun_id) (* Create the context *) let ctx = let region_groups = - List.map (fun (g : T.region_group) -> g.id) regions_hierarchy + List.map (fun (g : T.region_var_group) -> g.id) regions_hierarchy in let ctx = InterpreterUtils.initialize_eval_context decls_ctx region_groups @@ -905,17 +914,30 @@ let translate_fun_sig (decls_ctx : C.decls_ctx) (fun_id : A.fun_id) * so just check that there aren't parent regions *) assert (T.RegionGroupId.Set.is_empty parents); (* Small helper to translate types for backward functions *) - let translate_back_ty_for_gid (gid : T.RegionGroupId.id) : T.ty -> ty option = + let translate_back_ty_for_gid (gid : T.RegionGroupId.id) (ty : T.ty) : + ty option = let rg = T.RegionGroupId.nth regions_hierarchy gid in - let regions = T.RegionId.Set.of_list rg.regions in + (* Turn *all* the outer bound regions into free regions *) + let _, rid_subst, r_subst = + Substitute.fresh_regions_with_substs_from_vars ~fail_if_not_found:true + sg.generics.regions + in + let subst = { Substitute.empty_subst with r_subst } in + let ty = Substitute.ty_substitute subst ty in + (* Compute the set of regions belonging to this group *) + let gr_regions = + T.RegionId.Set.of_list + (List.map (fun rid -> Option.get (rid_subst rid)) rg.regions) + in let keep_region r = match r with | T.RStatic -> raise Unimplemented - | T.RErased -> raise (Failure "Unexpected erased region") - | T.RVar r -> T.RegionId.Set.mem r regions + | RErased -> raise (Failure "Unexpected erased region") + | RBVar _ -> raise (Failure "Unexpected bound region") + | RFVar rid -> T.RegionId.Set.mem rid gr_regions in let inside_mut = false in - translate_back_ty type_infos keep_region inside_mut + translate_back_ty type_infos keep_region inside_mut ty in (* Compute the additinal inputs for the current function, if it is a backward * function *) @@ -1749,7 +1771,8 @@ and translate_function_call (call : S.call) (e : S.expression) (ctx : bs_ctx) : is_rec = false; } in - (ctx, Unop (Cast (src_ty, tgt_ty)), effect_info, args, None)) + (ctx, Unop (Cast (src_ty, tgt_ty)), effect_info, args, None) + | CastFnPtr _ -> raise (Failure "TODO: function casts")) | S.Binop binop -> ( match args with | [ arg0; arg1 ] -> @@ -1758,8 +1781,7 @@ and translate_function_call (call : S.call) (e : S.expression) (ctx : bs_ctx) : (match binop with (* The Rust compiler accepts bitshifts for any integer type combination for ty0, ty1 *) | E.Shl | E.Shr -> () - | _ -> assert (int_ty0 = int_ty1) - ); + | _ -> assert (int_ty0 = int_ty1)); let effect_info = { can_fail = ExpressionsUtils.binop_can_fail binop; @@ -3100,6 +3122,12 @@ let translate_fun_signatures (decls_ctx : C.decls_ctx) let translate_one (fun_id : A.fun_id) (input_names : string option list) (sg : A.fun_sig) : (regular_fun_id_not_loop * fun_sig_named_outputs) list = + log#ldebug + (lazy + ("Translating signature of function: " + ^ Print.Expressions.fun_id_to_string + (Print.Contexts.decls_ctx_to_fmt_env decls_ctx) + fun_id)); (* Retrieve the regions hierarchy *) let regions_hierarchy = FunIdMap.find fun_id decls_ctx.fun_ctx.regions_hierarchies @@ -3110,7 +3138,7 @@ let translate_fun_signatures (decls_ctx : C.decls_ctx) (* The backward functions *) let back_sgs = List.map - (fun (rg : T.region_group) -> + (fun (rg : T.region_var_group) -> let tsg = translate_fun_sig decls_ctx fun_id sg input_names (Some rg.id) in diff --git a/compiler/Translate.ml b/compiler/Translate.ml index 37f58140..221d4e73 100644 --- a/compiler/Translate.ml +++ b/compiler/Translate.ml @@ -188,7 +188,7 @@ let translate_function_to_pure (trans_ctx : trans_ctx) in (* Translate the backward functions *) - let translate_backward (rg : region_group) : Pure.fun_decl = + let translate_backward (rg : region_var_group) : Pure.fun_decl = (* For the backward inputs/outputs initialization: we use the fact that * there are no nested borrows for now, and so that the region groups * can't have parents *) diff --git a/compiler/TypesAnalysis.ml b/compiler/TypesAnalysis.ml index eb0aeea9..589c380c 100644 --- a/compiler/TypesAnalysis.ml +++ b/compiler/TypesAnalysis.ml @@ -233,7 +233,7 @@ let analyze_full_ty (updated : bool ref) (infos : type_infos) in (* Return *) ty_info - | TArrow (inputs, output) -> + | TArrow (_regions, inputs, output) -> (* Just dive into the arrow *) let ty_info = List.fold_left diff --git a/compiler/TypesUtils.ml b/compiler/TypesUtils.ml index 76cc710a..c8418ba0 100644 --- a/compiler/TypesUtils.ml +++ b/compiler/TypesUtils.ml @@ -29,16 +29,19 @@ let ty_has_borrow_under_mut (infos : TypesAnalysis.type_infos) (ty : ty) : bool info.TypesAnalysis.contains_borrow_under_mut (** Small helper *) -let raise_if_erased_ty_visitor = +let raise_if_not_rty_visitor = object inherit [_] iter_ty - method! visit_RErased _ = raise Found + + method! visit_region _ r = + match r with RBVar _ | RErased -> raise Found | RStatic | RFVar _ -> () end -(** Return [true] if the type is a region type (i.e., it doesn't contain erased regions) *) +(** Return [true] if the type is a region type (i.e., it doesn't contain erased + regions), and only contains free regions) *) let ty_is_rty (ty : ty) : bool = try - raise_if_erased_ty_visitor#visit_ty () ty; + raise_if_not_rty_visitor#visit_ty () ty; true with Found -> false @@ -46,8 +49,9 @@ let ty_is_rty (ty : ty) : bool = let raise_if_not_erased_ty_visitor = object inherit [_] iter_ty - method! visit_RStatic _ = raise Found - method! visit_RVar _ = raise Found + + method! visit_region _ r = + match r with RStatic | RBVar _ | RFVar _ -> raise Found | RErased -> () end (** Return [true] if the type is a region type (i.e., it doesn't contain erased regions) *) diff --git a/tests/coq/betree/BetreeMain_Funs.v b/tests/coq/betree/BetreeMain_Funs.v index aadaa20d..a5dd4230 100644 --- a/tests/coq/betree/BetreeMain_Funs.v +++ b/tests/coq/betree/BetreeMain_Funs.v @@ -318,6 +318,29 @@ Fixpoint betree_Node_lookup_first_message_for_key_back end . +(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function + Source: 'src/betree.rs', lines 636:4-636:80 *) +Fixpoint betree_Node_lookup_in_bindings + (n : nat) (key : u64) (bindings : betree_List_t (u64 * u64)) : + result (option u64) + := + match n with + | O => Fail_ OutOfFuel + | S n0 => + match bindings with + | Betree_List_Cons hd tl => + let (i, i0) := hd in + if i s= key + then Return (Some i0) + else + if i s> key + then Return None + else betree_Node_lookup_in_bindings n0 key tl + | Betree_List_Nil => Return None + end + end +. + (** [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: forward function Source: 'src/betree.rs', lines 819:4-819:90 *) Fixpoint betree_Node_apply_upserts @@ -382,29 +405,6 @@ Fixpoint betree_Node_apply_upserts_back end . -(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function - Source: 'src/betree.rs', lines 636:4-636:80 *) -Fixpoint betree_Node_lookup_in_bindings - (n : nat) (key : u64) (bindings : betree_List_t (u64 * u64)) : - result (option u64) - := - match n with - | O => Fail_ OutOfFuel - | S n0 => - match bindings with - | Betree_List_Cons hd tl => - let (i, i0) := hd in - if i s= key - then Return (Some i0) - else - if i s> key - then Return None - else betree_Node_lookup_in_bindings n0 key tl - | Betree_List_Nil => Return None - end - end -. - (** [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: forward function Source: 'src/betree.rs', lines 395:4-395:63 *) Fixpoint betree_Internal_lookup_in_children diff --git a/tests/coq/misc/NoNestedBorrows.v b/tests/coq/misc/NoNestedBorrows.v index 16a2e816..1a0014c0 100644 --- a/tests/coq/misc/NoNestedBorrows.v +++ b/tests/coq/misc/NoNestedBorrows.v @@ -59,53 +59,111 @@ Arguments Sum_Right { _ _ }. Definition neg_test (x : i32) : result i32 := i32_neg x. -(** [no_nested_borrows::add_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 54:0-54:38 *) -Definition add_test (x : u32) (y : u32) : result u32 := +(** [no_nested_borrows::add_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 54:0-54:37 *) +Definition add_u32 (x : u32) (y : u32) : result u32 := u32_add x y. -(** [no_nested_borrows::subs_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 60:0-60:39 *) -Definition subs_test (x : u32) (y : u32) : result u32 := +(** [no_nested_borrows::subs_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 60:0-60:38 *) +Definition subs_u32 (x : u32) (y : u32) : result u32 := u32_sub x y. -(** [no_nested_borrows::div_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 66:0-66:38 *) -Definition div_test (x : u32) (y : u32) : result u32 := +(** [no_nested_borrows::div_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 66:0-66:37 *) +Definition div_u32 (x : u32) (y : u32) : result u32 := u32_div x y. -(** [no_nested_borrows::div_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 73:0-73:31 *) -Definition div_test1 (x : u32) : result u32 := +(** [no_nested_borrows::div_u32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 73:0-73:35 *) +Definition div_u32_const (x : u32) : result u32 := u32_div x 2%u32. -(** [no_nested_borrows::rem_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 78:0-78:38 *) -Definition rem_test (x : u32) (y : u32) : result u32 := +(** [no_nested_borrows::rem_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 78:0-78:37 *) +Definition rem_u32 (x : u32) (y : u32) : result u32 := u32_rem x y. -(** [no_nested_borrows::mul_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 82:0-82:38 *) -Definition mul_test (x : u32) (y : u32) : result u32 := +(** [no_nested_borrows::mul_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 82:0-82:37 *) +Definition mul_u32 (x : u32) (y : u32) : result u32 := u32_mul x y. +(** [no_nested_borrows::add_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 88:0-88:37 *) +Definition add_i32 (x : i32) (y : i32) : result i32 := + i32_add x y. + +(** [no_nested_borrows::subs_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 92:0-92:38 *) +Definition subs_i32 (x : i32) (y : i32) : result i32 := + i32_sub x y. + +(** [no_nested_borrows::div_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 96:0-96:37 *) +Definition div_i32 (x : i32) (y : i32) : result i32 := + i32_div x y. + +(** [no_nested_borrows::div_i32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 100:0-100:35 *) +Definition div_i32_const (x : i32) : result i32 := + i32_div x 2%i32. + +(** [no_nested_borrows::rem_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 104:0-104:37 *) +Definition rem_i32 (x : i32) (y : i32) : result i32 := + i32_rem x y. + +(** [no_nested_borrows::mul_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 108:0-108:37 *) +Definition mul_i32 (x : i32) (y : i32) : result i32 := + i32_mul x y. + +(** [no_nested_borrows::mix_arith_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 112:0-112:51 *) +Definition mix_arith_u32 (x : u32) (y : u32) (z : u32) : result u32 := + i <- u32_add x y; + i0 <- u32_div x y; + i1 <- u32_mul i i0; + i2 <- u32_rem z y; + i3 <- u32_sub x i2; + i4 <- u32_add i1 i3; + i5 <- u32_add x y; + i6 <- u32_add i5 z; + u32_rem i4 i6 +. + +(** [no_nested_borrows::mix_arith_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 116:0-116:51 *) +Definition mix_arith_i32 (x : i32) (y : i32) (z : i32) : result i32 := + i <- i32_add x y; + i0 <- i32_div x y; + i1 <- i32_mul i i0; + i2 <- i32_rem z y; + i3 <- i32_sub x i2; + i4 <- i32_add i1 i3; + i5 <- i32_add x y; + i6 <- i32_add i5 z; + i32_rem i4 i6 +. + (** [no_nested_borrows::CONST0] - Source: 'src/no_nested_borrows.rs', lines 91:0-91:23 *) + Source: 'src/no_nested_borrows.rs', lines 125:0-125:23 *) Definition const0_body : result usize := usize_add 1%usize 1%usize. Definition const0_c : usize := const0_body%global. (** [no_nested_borrows::CONST1] - Source: 'src/no_nested_borrows.rs', lines 92:0-92:23 *) + Source: 'src/no_nested_borrows.rs', lines 126:0-126:23 *) Definition const1_body : result usize := usize_mul 2%usize 2%usize. Definition const1_c : usize := const1_body%global. (** [no_nested_borrows::cast_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 94:0-94:31 *) + Source: 'src/no_nested_borrows.rs', lines 128:0-128:31 *) Definition cast_test (x : u32) : result i32 := scalar_cast U32 I32 x. (** [no_nested_borrows::test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 99:0-99:14 *) + Source: 'src/no_nested_borrows.rs', lines 133:0-133:14 *) Definition test2 : result unit := _ <- u32_add 23%u32 44%u32; Return tt. @@ -113,13 +171,13 @@ Definition test2 : result unit := Check (test2 )%return. (** [no_nested_borrows::get_max]: forward function - Source: 'src/no_nested_borrows.rs', lines 111:0-111:37 *) + Source: 'src/no_nested_borrows.rs', lines 145:0-145:37 *) Definition get_max (x : u32) (y : u32) : result u32 := if x s>= y then Return x else Return y . (** [no_nested_borrows::test3]: forward function - Source: 'src/no_nested_borrows.rs', lines 119:0-119:14 *) + Source: 'src/no_nested_borrows.rs', lines 153:0-153:14 *) Definition test3 : result unit := x <- get_max 4%u32 3%u32; y <- get_max 10%u32 11%u32; @@ -131,7 +189,7 @@ Definition test3 : result unit := Check (test3 )%return. (** [no_nested_borrows::test_neg1]: forward function - Source: 'src/no_nested_borrows.rs', lines 126:0-126:18 *) + Source: 'src/no_nested_borrows.rs', lines 160:0-160:18 *) Definition test_neg1 : result unit := y <- i32_neg 3%i32; if negb (y s= (-3)%i32) then Fail_ Failure else Return tt . @@ -140,7 +198,7 @@ Definition test_neg1 : result unit := Check (test_neg1 )%return. (** [no_nested_borrows::refs_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 133:0-133:19 *) + Source: 'src/no_nested_borrows.rs', lines 167:0-167:19 *) Definition refs_test1 : result unit := if negb (1%i32 s= 1%i32) then Fail_ Failure else Return tt . @@ -149,7 +207,7 @@ Definition refs_test1 : result unit := Check (refs_test1 )%return. (** [no_nested_borrows::refs_test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 144:0-144:19 *) + Source: 'src/no_nested_borrows.rs', lines 178:0-178:19 *) Definition refs_test2 : result unit := if negb (2%i32 s= 2%i32) then Fail_ Failure @@ -166,7 +224,7 @@ Definition refs_test2 : result unit := Check (refs_test2 )%return. (** [no_nested_borrows::test_list1]: forward function - Source: 'src/no_nested_borrows.rs', lines 160:0-160:19 *) + Source: 'src/no_nested_borrows.rs', lines 194:0-194:19 *) Definition test_list1 : result unit := Return tt. @@ -174,7 +232,7 @@ Definition test_list1 : result unit := Check (test_list1 )%return. (** [no_nested_borrows::test_box1]: forward function - Source: 'src/no_nested_borrows.rs', lines 165:0-165:18 *) + Source: 'src/no_nested_borrows.rs', lines 199:0-199:18 *) Definition test_box1 : result unit := let b := 0%i32 in b0 <- alloc_boxed_Box_deref_mut_back i32 b 1%i32; @@ -186,24 +244,24 @@ Definition test_box1 : result unit := Check (test_box1 )%return. (** [no_nested_borrows::copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 175:0-175:30 *) + Source: 'src/no_nested_borrows.rs', lines 209:0-209:30 *) Definition copy_int (x : i32) : result i32 := Return x. (** [no_nested_borrows::test_unreachable]: forward function - Source: 'src/no_nested_borrows.rs', lines 181:0-181:32 *) + Source: 'src/no_nested_borrows.rs', lines 215:0-215:32 *) Definition test_unreachable (b : bool) : result unit := if b then Fail_ Failure else Return tt . (** [no_nested_borrows::test_panic]: forward function - Source: 'src/no_nested_borrows.rs', lines 189:0-189:26 *) + Source: 'src/no_nested_borrows.rs', lines 223:0-223:26 *) Definition test_panic (b : bool) : result unit := if b then Fail_ Failure else Return tt . (** [no_nested_borrows::test_copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 196:0-196:22 *) + Source: 'src/no_nested_borrows.rs', lines 230:0-230:22 *) Definition test_copy_int : result unit := y <- copy_int 0%i32; if negb (0%i32 s= y) then Fail_ Failure else Return tt . @@ -212,13 +270,13 @@ Definition test_copy_int : result unit := Check (test_copy_int )%return. (** [no_nested_borrows::is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 203:0-203:38 *) + Source: 'src/no_nested_borrows.rs', lines 237:0-237:38 *) Definition is_cons (T : Type) (l : List_t T) : result bool := match l with | List_Cons t l0 => Return true | List_Nil => Return false end . (** [no_nested_borrows::test_is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 210:0-210:21 *) + Source: 'src/no_nested_borrows.rs', lines 244:0-244:21 *) Definition test_is_cons : result unit := let l := List_Nil in b <- is_cons i32 (List_Cons 0%i32 l); @@ -229,7 +287,7 @@ Definition test_is_cons : result unit := Check (test_is_cons )%return. (** [no_nested_borrows::split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 216:0-216:48 *) + Source: 'src/no_nested_borrows.rs', lines 250:0-250:48 *) Definition split_list (T : Type) (l : List_t T) : result (T * (List_t T)) := match l with | List_Cons hd tl => Return (hd, tl) @@ -238,7 +296,7 @@ Definition split_list (T : Type) (l : List_t T) : result (T * (List_t T)) := . (** [no_nested_borrows::test_split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 224:0-224:24 *) + Source: 'src/no_nested_borrows.rs', lines 258:0-258:24 *) Definition test_split_list : result unit := let l := List_Nil in p <- split_list i32 (List_Cons 0%i32 l); @@ -250,20 +308,20 @@ Definition test_split_list : result unit := Check (test_split_list )%return. (** [no_nested_borrows::choose]: forward function - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 *) + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 *) Definition choose (T : Type) (b : bool) (x : T) (y : T) : result T := if b then Return x else Return y . (** [no_nested_borrows::choose]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 *) + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 *) Definition choose_back (T : Type) (b : bool) (x : T) (y : T) (ret : T) : result (T * T) := if b then Return (ret, y) else Return (x, ret) . (** [no_nested_borrows::choose_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 239:0-239:20 *) + Source: 'src/no_nested_borrows.rs', lines 273:0-273:20 *) Definition choose_test : result unit := z <- choose i32 true 0%i32 0%i32; z0 <- i32_add z 1%i32; @@ -281,18 +339,18 @@ Definition choose_test : result unit := Check (choose_test )%return. (** [no_nested_borrows::test_char]: forward function - Source: 'src/no_nested_borrows.rs', lines 251:0-251:26 *) + Source: 'src/no_nested_borrows.rs', lines 285:0-285:26 *) Definition test_char : result char := Return (char_of_byte Coq.Init.Byte.x61). (** [no_nested_borrows::Tree] - Source: 'src/no_nested_borrows.rs', lines 256:0-256:16 *) + Source: 'src/no_nested_borrows.rs', lines 290:0-290:16 *) Inductive Tree_t (T : Type) := | Tree_Leaf : T -> Tree_t T | Tree_Node : T -> NodeElem_t T -> Tree_t T -> Tree_t T (** [no_nested_borrows::NodeElem] - Source: 'src/no_nested_borrows.rs', lines 261:0-261:20 *) + Source: 'src/no_nested_borrows.rs', lines 295:0-295:20 *) with NodeElem_t (T : Type) := | NodeElem_Cons : Tree_t T -> NodeElem_t T -> NodeElem_t T | NodeElem_Nil : NodeElem_t T @@ -305,7 +363,7 @@ Arguments NodeElem_Cons { _ }. Arguments NodeElem_Nil { _ }. (** [no_nested_borrows::list_length]: forward function - Source: 'src/no_nested_borrows.rs', lines 296:0-296:48 *) + Source: 'src/no_nested_borrows.rs', lines 330:0-330:48 *) Fixpoint list_length (T : Type) (l : List_t T) : result u32 := match l with | List_Cons t l1 => i <- list_length T l1; u32_add 1%u32 i @@ -314,7 +372,7 @@ Fixpoint list_length (T : Type) (l : List_t T) : result u32 := . (** [no_nested_borrows::list_nth_shared]: forward function - Source: 'src/no_nested_borrows.rs', lines 304:0-304:62 *) + Source: 'src/no_nested_borrows.rs', lines 338:0-338:62 *) Fixpoint list_nth_shared (T : Type) (l : List_t T) (i : u32) : result T := match l with | List_Cons x tl => @@ -326,7 +384,7 @@ Fixpoint list_nth_shared (T : Type) (l : List_t T) (i : u32) : result T := . (** [no_nested_borrows::list_nth_mut]: forward function - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 *) + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 *) Fixpoint list_nth_mut (T : Type) (l : List_t T) (i : u32) : result T := match l with | List_Cons x tl => @@ -338,7 +396,7 @@ Fixpoint list_nth_mut (T : Type) (l : List_t T) (i : u32) : result T := . (** [no_nested_borrows::list_nth_mut]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 *) + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 *) Fixpoint list_nth_mut_back (T : Type) (l : List_t T) (i : u32) (ret : T) : result (List_t T) := match l with @@ -354,7 +412,7 @@ Fixpoint list_nth_mut_back . (** [no_nested_borrows::list_rev_aux]: forward function - Source: 'src/no_nested_borrows.rs', lines 336:0-336:63 *) + Source: 'src/no_nested_borrows.rs', lines 370:0-370:63 *) Fixpoint list_rev_aux (T : Type) (li : List_t T) (lo : List_t T) : result (List_t T) := match li with @@ -365,14 +423,14 @@ Fixpoint list_rev_aux (** [no_nested_borrows::list_rev]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 350:0-350:42 *) + Source: 'src/no_nested_borrows.rs', lines 384:0-384:42 *) Definition list_rev (T : Type) (l : List_t T) : result (List_t T) := let li := core_mem_replace (List_t T) l List_Nil in list_rev_aux T li List_Nil . (** [no_nested_borrows::test_list_functions]: forward function - Source: 'src/no_nested_borrows.rs', lines 355:0-355:28 *) + Source: 'src/no_nested_borrows.rs', lines 389:0-389:28 *) Definition test_list_functions : result unit := let l := List_Nil in let l0 := List_Cons 2%i32 l in @@ -410,73 +468,73 @@ Definition test_list_functions : result unit := Check (test_list_functions )%return. (** [no_nested_borrows::id_mut_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 *) + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 *) Definition id_mut_pair1 (T1 T2 : Type) (x : T1) (y : T2) : result (T1 * T2) := Return (x, y) . (** [no_nested_borrows::id_mut_pair1]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 *) + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 *) Definition id_mut_pair1_back (T1 T2 : Type) (x : T1) (y : T2) (ret : (T1 * T2)) : result (T1 * T2) := let (t, t0) := ret in Return (t, t0) . (** [no_nested_borrows::id_mut_pair2]: forward function - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 *) + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 *) Definition id_mut_pair2 (T1 T2 : Type) (p : (T1 * T2)) : result (T1 * T2) := let (t, t0) := p in Return (t, t0) . (** [no_nested_borrows::id_mut_pair2]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 *) + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 *) Definition id_mut_pair2_back (T1 T2 : Type) (p : (T1 * T2)) (ret : (T1 * T2)) : result (T1 * T2) := let (t, t0) := ret in Return (t, t0) . (** [no_nested_borrows::id_mut_pair3]: forward function - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) Definition id_mut_pair3 (T1 T2 : Type) (x : T1) (y : T2) : result (T1 * T2) := Return (x, y) . (** [no_nested_borrows::id_mut_pair3]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) Definition id_mut_pair3_back'a (T1 T2 : Type) (x : T1) (y : T2) (ret : T1) : result T1 := Return ret . (** [no_nested_borrows::id_mut_pair3]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) Definition id_mut_pair3_back'b (T1 T2 : Type) (x : T1) (y : T2) (ret : T2) : result T2 := Return ret . (** [no_nested_borrows::id_mut_pair4]: forward function - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) Definition id_mut_pair4 (T1 T2 : Type) (p : (T1 * T2)) : result (T1 * T2) := let (t, t0) := p in Return (t, t0) . (** [no_nested_borrows::id_mut_pair4]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) Definition id_mut_pair4_back'a (T1 T2 : Type) (p : (T1 * T2)) (ret : T1) : result T1 := Return ret . (** [no_nested_borrows::id_mut_pair4]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) Definition id_mut_pair4_back'b (T1 T2 : Type) (p : (T1 * T2)) (ret : T2) : result T2 := Return ret . (** [no_nested_borrows::StructWithTuple] - Source: 'src/no_nested_borrows.rs', lines 390:0-390:34 *) + Source: 'src/no_nested_borrows.rs', lines 424:0-424:34 *) Record StructWithTuple_t (T1 T2 : Type) := mkStructWithTuple_t { structWithTuple_p : (T1 * T2); @@ -487,25 +545,25 @@ Arguments mkStructWithTuple_t { _ _ }. Arguments structWithTuple_p { _ _ }. (** [no_nested_borrows::new_tuple1]: forward function - Source: 'src/no_nested_borrows.rs', lines 394:0-394:48 *) + Source: 'src/no_nested_borrows.rs', lines 428:0-428:48 *) Definition new_tuple1 : result (StructWithTuple_t u32 u32) := Return {| structWithTuple_p := (1%u32, 2%u32) |} . (** [no_nested_borrows::new_tuple2]: forward function - Source: 'src/no_nested_borrows.rs', lines 398:0-398:48 *) + Source: 'src/no_nested_borrows.rs', lines 432:0-432:48 *) Definition new_tuple2 : result (StructWithTuple_t i16 i16) := Return {| structWithTuple_p := (1%i16, 2%i16) |} . (** [no_nested_borrows::new_tuple3]: forward function - Source: 'src/no_nested_borrows.rs', lines 402:0-402:48 *) + Source: 'src/no_nested_borrows.rs', lines 436:0-436:48 *) Definition new_tuple3 : result (StructWithTuple_t u64 i64) := Return {| structWithTuple_p := (1%u64, 2%i64) |} . (** [no_nested_borrows::StructWithPair] - Source: 'src/no_nested_borrows.rs', lines 407:0-407:33 *) + Source: 'src/no_nested_borrows.rs', lines 441:0-441:33 *) Record StructWithPair_t (T1 T2 : Type) := mkStructWithPair_t { structWithPair_p : Pair_t T1 T2; @@ -516,13 +574,13 @@ Arguments mkStructWithPair_t { _ _ }. Arguments structWithPair_p { _ _ }. (** [no_nested_borrows::new_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 411:0-411:46 *) + Source: 'src/no_nested_borrows.rs', lines 445:0-445:46 *) Definition new_pair1 : result (StructWithPair_t u32 u32) := Return {| structWithPair_p := {| pair_x := 1%u32; pair_y := 2%u32 |} |} . (** [no_nested_borrows::test_constants]: forward function - Source: 'src/no_nested_borrows.rs', lines 419:0-419:23 *) + Source: 'src/no_nested_borrows.rs', lines 453:0-453:23 *) Definition test_constants : result unit := swt <- new_tuple1; let (i, _) := swt.(structWithTuple_p) in @@ -549,7 +607,7 @@ Definition test_constants : result unit := Check (test_constants )%return. (** [no_nested_borrows::test_weird_borrows1]: forward function - Source: 'src/no_nested_borrows.rs', lines 428:0-428:28 *) + Source: 'src/no_nested_borrows.rs', lines 462:0-462:28 *) Definition test_weird_borrows1 : result unit := Return tt. @@ -558,31 +616,31 @@ Check (test_weird_borrows1 )%return. (** [no_nested_borrows::test_mem_replace]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 438:0-438:37 *) + Source: 'src/no_nested_borrows.rs', lines 472:0-472:37 *) Definition test_mem_replace (px : u32) : result u32 := let y := core_mem_replace u32 px 1%u32 in if negb (y s= 0%u32) then Fail_ Failure else Return 2%u32 . (** [no_nested_borrows::test_shared_borrow_bool1]: forward function - Source: 'src/no_nested_borrows.rs', lines 445:0-445:47 *) + Source: 'src/no_nested_borrows.rs', lines 479:0-479:47 *) Definition test_shared_borrow_bool1 (b : bool) : result u32 := if b then Return 0%u32 else Return 1%u32 . (** [no_nested_borrows::test_shared_borrow_bool2]: forward function - Source: 'src/no_nested_borrows.rs', lines 458:0-458:40 *) + Source: 'src/no_nested_borrows.rs', lines 492:0-492:40 *) Definition test_shared_borrow_bool2 : result u32 := Return 0%u32. (** [no_nested_borrows::test_shared_borrow_enum1]: forward function - Source: 'src/no_nested_borrows.rs', lines 473:0-473:52 *) + Source: 'src/no_nested_borrows.rs', lines 507:0-507:52 *) Definition test_shared_borrow_enum1 (l : List_t u32) : result u32 := match l with | List_Cons i l0 => Return 1%u32 | List_Nil => Return 0%u32 end . (** [no_nested_borrows::test_shared_borrow_enum2]: forward function - Source: 'src/no_nested_borrows.rs', lines 485:0-485:40 *) + Source: 'src/no_nested_borrows.rs', lines 519:0-519:40 *) Definition test_shared_borrow_enum2 : result u32 := Return 0%u32. diff --git a/tests/coq/misc/_CoqProject b/tests/coq/misc/_CoqProject index abbf6aa8..869cdb4d 100644 --- a/tests/coq/misc/_CoqProject +++ b/tests/coq/misc/_CoqProject @@ -7,10 +7,10 @@ Loops.v External_Types.v Primitives.v External_Funs.v -Paper.v External_TypesExternal.v Constants.v PoloniusList.v +Paper.v NoNestedBorrows.v External_FunsExternal.v Bitwise.v diff --git a/tests/fstar/betree/BetreeMain.Clauses.Template.fst b/tests/fstar/betree/BetreeMain.Clauses.Template.fst index 4ae29302..537705c5 100644 --- a/tests/fstar/betree/BetreeMain.Clauses.Template.fst +++ b/tests/fstar/betree/BetreeMain.Clauses.Template.fst @@ -33,6 +33,13 @@ let betree_Node_lookup_first_message_for_key_decreases (key : u64) (msgs : betree_List_t (u64 & betree_Message_t)) : nat = admit () +(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: decreases clause + Source: 'src/betree.rs', lines 636:4-636:80 *) +unfold +let betree_Node_lookup_in_bindings_decreases (key : u64) + (bindings : betree_List_t (u64 & u64)) : nat = + admit () + (** [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: decreases clause Source: 'src/betree.rs', lines 819:4-819:90 *) unfold @@ -41,13 +48,6 @@ let betree_Node_apply_upserts_decreases (key : u64) (st : state) : nat = admit () -(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: decreases clause - Source: 'src/betree.rs', lines 636:4-636:80 *) -unfold -let betree_Node_lookup_in_bindings_decreases (key : u64) - (bindings : betree_List_t (u64 & u64)) : nat = - admit () - (** [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: decreases clause Source: 'src/betree.rs', lines 395:4-395:63 *) unfold diff --git a/tests/fstar/betree/BetreeMain.Funs.fst b/tests/fstar/betree/BetreeMain.Funs.fst index fef8a8e1..f844b0ec 100644 --- a/tests/fstar/betree/BetreeMain.Funs.fst +++ b/tests/fstar/betree/BetreeMain.Funs.fst @@ -258,6 +258,22 @@ let rec betree_Node_lookup_first_message_for_key_back | Betree_List_Nil -> Return ret end +(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function + Source: 'src/betree.rs', lines 636:4-636:80 *) +let rec betree_Node_lookup_in_bindings + (key : u64) (bindings : betree_List_t (u64 & u64)) : + Tot (result (option u64)) + (decreases (betree_Node_lookup_in_bindings_decreases key bindings)) + = + begin match bindings with + | Betree_List_Cons hd tl -> + let (i, i0) = hd in + if i = key + then Return (Some i0) + else if i > key then Return None else betree_Node_lookup_in_bindings key tl + | Betree_List_Nil -> Return None + end + (** [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: forward function Source: 'src/betree.rs', lines 819:4-819:90 *) let rec betree_Node_apply_upserts @@ -312,22 +328,6 @@ let rec betree_Node_apply_upserts_back betree_List_push_front (u64 & betree_Message_t) msgs (key, Betree_Message_Insert v) -(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function - Source: 'src/betree.rs', lines 636:4-636:80 *) -let rec betree_Node_lookup_in_bindings - (key : u64) (bindings : betree_List_t (u64 & u64)) : - Tot (result (option u64)) - (decreases (betree_Node_lookup_in_bindings_decreases key bindings)) - = - begin match bindings with - | Betree_List_Cons hd tl -> - let (i, i0) = hd in - if i = key - then Return (Some i0) - else if i > key then Return None else betree_Node_lookup_in_bindings key tl - | Betree_List_Nil -> Return None - end - (** [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: forward function Source: 'src/betree.rs', lines 395:4-395:63 *) let rec betree_Internal_lookup_in_children diff --git a/tests/fstar/betree_back_stateful/BetreeMain.Clauses.Template.fst b/tests/fstar/betree_back_stateful/BetreeMain.Clauses.Template.fst index 4ae29302..537705c5 100644 --- a/tests/fstar/betree_back_stateful/BetreeMain.Clauses.Template.fst +++ b/tests/fstar/betree_back_stateful/BetreeMain.Clauses.Template.fst @@ -33,6 +33,13 @@ let betree_Node_lookup_first_message_for_key_decreases (key : u64) (msgs : betree_List_t (u64 & betree_Message_t)) : nat = admit () +(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: decreases clause + Source: 'src/betree.rs', lines 636:4-636:80 *) +unfold +let betree_Node_lookup_in_bindings_decreases (key : u64) + (bindings : betree_List_t (u64 & u64)) : nat = + admit () + (** [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: decreases clause Source: 'src/betree.rs', lines 819:4-819:90 *) unfold @@ -41,13 +48,6 @@ let betree_Node_apply_upserts_decreases (key : u64) (st : state) : nat = admit () -(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: decreases clause - Source: 'src/betree.rs', lines 636:4-636:80 *) -unfold -let betree_Node_lookup_in_bindings_decreases (key : u64) - (bindings : betree_List_t (u64 & u64)) : nat = - admit () - (** [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: decreases clause Source: 'src/betree.rs', lines 395:4-395:63 *) unfold diff --git a/tests/fstar/betree_back_stateful/BetreeMain.Funs.fst b/tests/fstar/betree_back_stateful/BetreeMain.Funs.fst index b912a316..6c3c2161 100644 --- a/tests/fstar/betree_back_stateful/BetreeMain.Funs.fst +++ b/tests/fstar/betree_back_stateful/BetreeMain.Funs.fst @@ -295,6 +295,22 @@ let rec betree_Node_lookup_first_message_for_key_back | Betree_List_Nil -> Return ret end +(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function + Source: 'src/betree.rs', lines 636:4-636:80 *) +let rec betree_Node_lookup_in_bindings + (key : u64) (bindings : betree_List_t (u64 & u64)) : + Tot (result (option u64)) + (decreases (betree_Node_lookup_in_bindings_decreases key bindings)) + = + begin match bindings with + | Betree_List_Cons hd tl -> + let (i, i0) = hd in + if i = key + then Return (Some i0) + else if i > key then Return None else betree_Node_lookup_in_bindings key tl + | Betree_List_Nil -> Return None + end + (** [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: forward function Source: 'src/betree.rs', lines 819:4-819:90 *) let rec betree_Node_apply_upserts @@ -351,22 +367,6 @@ let rec betree_Node_apply_upserts_back Betree_Message_Insert v) in Return (st0, msgs0) -(** [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function - Source: 'src/betree.rs', lines 636:4-636:80 *) -let rec betree_Node_lookup_in_bindings - (key : u64) (bindings : betree_List_t (u64 & u64)) : - Tot (result (option u64)) - (decreases (betree_Node_lookup_in_bindings_decreases key bindings)) - = - begin match bindings with - | Betree_List_Cons hd tl -> - let (i, i0) = hd in - if i = key - then Return (Some i0) - else if i > key then Return None else betree_Node_lookup_in_bindings key tl - | Betree_List_Nil -> Return None - end - (** [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: forward function Source: 'src/betree.rs', lines 395:4-395:63 *) let rec betree_Internal_lookup_in_children diff --git a/tests/fstar/misc/NoNestedBorrows.fst b/tests/fstar/misc/NoNestedBorrows.fst index 2e14d67d..130b02f2 100644 --- a/tests/fstar/misc/NoNestedBorrows.fst +++ b/tests/fstar/misc/NoNestedBorrows.fst @@ -42,53 +42,109 @@ type sum_t (t1 t2 : Type0) = let neg_test (x : i32) : result i32 = i32_neg x -(** [no_nested_borrows::add_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 54:0-54:38 *) -let add_test (x : u32) (y : u32) : result u32 = +(** [no_nested_borrows::add_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 54:0-54:37 *) +let add_u32 (x : u32) (y : u32) : result u32 = u32_add x y -(** [no_nested_borrows::subs_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 60:0-60:39 *) -let subs_test (x : u32) (y : u32) : result u32 = +(** [no_nested_borrows::subs_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 60:0-60:38 *) +let subs_u32 (x : u32) (y : u32) : result u32 = u32_sub x y -(** [no_nested_borrows::div_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 66:0-66:38 *) -let div_test (x : u32) (y : u32) : result u32 = +(** [no_nested_borrows::div_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 66:0-66:37 *) +let div_u32 (x : u32) (y : u32) : result u32 = u32_div x y -(** [no_nested_borrows::div_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 73:0-73:31 *) -let div_test1 (x : u32) : result u32 = +(** [no_nested_borrows::div_u32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 73:0-73:35 *) +let div_u32_const (x : u32) : result u32 = u32_div x 2 -(** [no_nested_borrows::rem_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 78:0-78:38 *) -let rem_test (x : u32) (y : u32) : result u32 = +(** [no_nested_borrows::rem_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 78:0-78:37 *) +let rem_u32 (x : u32) (y : u32) : result u32 = u32_rem x y -(** [no_nested_borrows::mul_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 82:0-82:38 *) -let mul_test (x : u32) (y : u32) : result u32 = +(** [no_nested_borrows::mul_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 82:0-82:37 *) +let mul_u32 (x : u32) (y : u32) : result u32 = u32_mul x y +(** [no_nested_borrows::add_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 88:0-88:37 *) +let add_i32 (x : i32) (y : i32) : result i32 = + i32_add x y + +(** [no_nested_borrows::subs_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 92:0-92:38 *) +let subs_i32 (x : i32) (y : i32) : result i32 = + i32_sub x y + +(** [no_nested_borrows::div_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 96:0-96:37 *) +let div_i32 (x : i32) (y : i32) : result i32 = + i32_div x y + +(** [no_nested_borrows::div_i32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 100:0-100:35 *) +let div_i32_const (x : i32) : result i32 = + i32_div x 2 + +(** [no_nested_borrows::rem_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 104:0-104:37 *) +let rem_i32 (x : i32) (y : i32) : result i32 = + i32_rem x y + +(** [no_nested_borrows::mul_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 108:0-108:37 *) +let mul_i32 (x : i32) (y : i32) : result i32 = + i32_mul x y + +(** [no_nested_borrows::mix_arith_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 112:0-112:51 *) +let mix_arith_u32 (x : u32) (y : u32) (z : u32) : result u32 = + let* i = u32_add x y in + let* i0 = u32_div x y in + let* i1 = u32_mul i i0 in + let* i2 = u32_rem z y in + let* i3 = u32_sub x i2 in + let* i4 = u32_add i1 i3 in + let* i5 = u32_add x y in + let* i6 = u32_add i5 z in + u32_rem i4 i6 + +(** [no_nested_borrows::mix_arith_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 116:0-116:51 *) +let mix_arith_i32 (x : i32) (y : i32) (z : i32) : result i32 = + let* i = i32_add x y in + let* i0 = i32_div x y in + let* i1 = i32_mul i i0 in + let* i2 = i32_rem z y in + let* i3 = i32_sub x i2 in + let* i4 = i32_add i1 i3 in + let* i5 = i32_add x y in + let* i6 = i32_add i5 z in + i32_rem i4 i6 + (** [no_nested_borrows::CONST0] - Source: 'src/no_nested_borrows.rs', lines 91:0-91:23 *) + Source: 'src/no_nested_borrows.rs', lines 125:0-125:23 *) let const0_body : result usize = usize_add 1 1 let const0_c : usize = eval_global const0_body (** [no_nested_borrows::CONST1] - Source: 'src/no_nested_borrows.rs', lines 92:0-92:23 *) + Source: 'src/no_nested_borrows.rs', lines 126:0-126:23 *) let const1_body : result usize = usize_mul 2 2 let const1_c : usize = eval_global const1_body (** [no_nested_borrows::cast_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 94:0-94:31 *) + Source: 'src/no_nested_borrows.rs', lines 128:0-128:31 *) let cast_test (x : u32) : result i32 = scalar_cast U32 I32 x (** [no_nested_borrows::test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 99:0-99:14 *) + Source: 'src/no_nested_borrows.rs', lines 133:0-133:14 *) let test2 : result unit = let* _ = u32_add 23 44 in Return () @@ -96,12 +152,12 @@ let test2 : result unit = let _ = assert_norm (test2 = Return ()) (** [no_nested_borrows::get_max]: forward function - Source: 'src/no_nested_borrows.rs', lines 111:0-111:37 *) + Source: 'src/no_nested_borrows.rs', lines 145:0-145:37 *) let get_max (x : u32) (y : u32) : result u32 = if x >= y then Return x else Return y (** [no_nested_borrows::test3]: forward function - Source: 'src/no_nested_borrows.rs', lines 119:0-119:14 *) + Source: 'src/no_nested_borrows.rs', lines 153:0-153:14 *) let test3 : result unit = let* x = get_max 4 3 in let* y = get_max 10 11 in @@ -112,7 +168,7 @@ let test3 : result unit = let _ = assert_norm (test3 = Return ()) (** [no_nested_borrows::test_neg1]: forward function - Source: 'src/no_nested_borrows.rs', lines 126:0-126:18 *) + Source: 'src/no_nested_borrows.rs', lines 160:0-160:18 *) let test_neg1 : result unit = let* y = i32_neg 3 in if not (y = -3) then Fail Failure else Return () @@ -120,7 +176,7 @@ let test_neg1 : result unit = let _ = assert_norm (test_neg1 = Return ()) (** [no_nested_borrows::refs_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 133:0-133:19 *) + Source: 'src/no_nested_borrows.rs', lines 167:0-167:19 *) let refs_test1 : result unit = if not (1 = 1) then Fail Failure else Return () @@ -128,7 +184,7 @@ let refs_test1 : result unit = let _ = assert_norm (refs_test1 = Return ()) (** [no_nested_borrows::refs_test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 144:0-144:19 *) + Source: 'src/no_nested_borrows.rs', lines 178:0-178:19 *) let refs_test2 : result unit = if not (2 = 2) then Fail Failure @@ -144,7 +200,7 @@ let refs_test2 : result unit = let _ = assert_norm (refs_test2 = Return ()) (** [no_nested_borrows::test_list1]: forward function - Source: 'src/no_nested_borrows.rs', lines 160:0-160:19 *) + Source: 'src/no_nested_borrows.rs', lines 194:0-194:19 *) let test_list1 : result unit = Return () @@ -152,7 +208,7 @@ let test_list1 : result unit = let _ = assert_norm (test_list1 = Return ()) (** [no_nested_borrows::test_box1]: forward function - Source: 'src/no_nested_borrows.rs', lines 165:0-165:18 *) + Source: 'src/no_nested_borrows.rs', lines 199:0-199:18 *) let test_box1 : result unit = let b = 0 in let* b0 = alloc_boxed_Box_deref_mut_back i32 b 1 in @@ -163,22 +219,22 @@ let test_box1 : result unit = let _ = assert_norm (test_box1 = Return ()) (** [no_nested_borrows::copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 175:0-175:30 *) + Source: 'src/no_nested_borrows.rs', lines 209:0-209:30 *) let copy_int (x : i32) : result i32 = Return x (** [no_nested_borrows::test_unreachable]: forward function - Source: 'src/no_nested_borrows.rs', lines 181:0-181:32 *) + Source: 'src/no_nested_borrows.rs', lines 215:0-215:32 *) let test_unreachable (b : bool) : result unit = if b then Fail Failure else Return () (** [no_nested_borrows::test_panic]: forward function - Source: 'src/no_nested_borrows.rs', lines 189:0-189:26 *) + Source: 'src/no_nested_borrows.rs', lines 223:0-223:26 *) let test_panic (b : bool) : result unit = if b then Fail Failure else Return () (** [no_nested_borrows::test_copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 196:0-196:22 *) + Source: 'src/no_nested_borrows.rs', lines 230:0-230:22 *) let test_copy_int : result unit = let* y = copy_int 0 in if not (0 = y) then Fail Failure else Return () @@ -186,7 +242,7 @@ let test_copy_int : result unit = let _ = assert_norm (test_copy_int = Return ()) (** [no_nested_borrows::is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 203:0-203:38 *) + Source: 'src/no_nested_borrows.rs', lines 237:0-237:38 *) let is_cons (t : Type0) (l : list_t t) : result bool = begin match l with | List_Cons x l0 -> Return true @@ -194,7 +250,7 @@ let is_cons (t : Type0) (l : list_t t) : result bool = end (** [no_nested_borrows::test_is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 210:0-210:21 *) + Source: 'src/no_nested_borrows.rs', lines 244:0-244:21 *) let test_is_cons : result unit = let l = List_Nil in let* b = is_cons i32 (List_Cons 0 l) in @@ -204,7 +260,7 @@ let test_is_cons : result unit = let _ = assert_norm (test_is_cons = Return ()) (** [no_nested_borrows::split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 216:0-216:48 *) + Source: 'src/no_nested_borrows.rs', lines 250:0-250:48 *) let split_list (t : Type0) (l : list_t t) : result (t & (list_t t)) = begin match l with | List_Cons hd tl -> Return (hd, tl) @@ -212,7 +268,7 @@ let split_list (t : Type0) (l : list_t t) : result (t & (list_t t)) = end (** [no_nested_borrows::test_split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 224:0-224:24 *) + Source: 'src/no_nested_borrows.rs', lines 258:0-258:24 *) let test_split_list : result unit = let l = List_Nil in let* p = split_list i32 (List_Cons 0 l) in @@ -223,18 +279,18 @@ let test_split_list : result unit = let _ = assert_norm (test_split_list = Return ()) (** [no_nested_borrows::choose]: forward function - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 *) + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 *) let choose (t : Type0) (b : bool) (x : t) (y : t) : result t = if b then Return x else Return y (** [no_nested_borrows::choose]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 *) + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 *) let choose_back (t : Type0) (b : bool) (x : t) (y : t) (ret : t) : result (t & t) = if b then Return (ret, y) else Return (x, ret) (** [no_nested_borrows::choose_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 239:0-239:20 *) + Source: 'src/no_nested_borrows.rs', lines 273:0-273:20 *) let choose_test : result unit = let* z = choose i32 true 0 0 in let* z0 = i32_add z 1 in @@ -250,24 +306,24 @@ let choose_test : result unit = let _ = assert_norm (choose_test = Return ()) (** [no_nested_borrows::test_char]: forward function - Source: 'src/no_nested_borrows.rs', lines 251:0-251:26 *) + Source: 'src/no_nested_borrows.rs', lines 285:0-285:26 *) let test_char : result char = Return 'a' (** [no_nested_borrows::Tree] - Source: 'src/no_nested_borrows.rs', lines 256:0-256:16 *) + Source: 'src/no_nested_borrows.rs', lines 290:0-290:16 *) type tree_t (t : Type0) = | Tree_Leaf : t -> tree_t t | Tree_Node : t -> nodeElem_t t -> tree_t t -> tree_t t (** [no_nested_borrows::NodeElem] - Source: 'src/no_nested_borrows.rs', lines 261:0-261:20 *) + Source: 'src/no_nested_borrows.rs', lines 295:0-295:20 *) and nodeElem_t (t : Type0) = | NodeElem_Cons : tree_t t -> nodeElem_t t -> nodeElem_t t | NodeElem_Nil : nodeElem_t t (** [no_nested_borrows::list_length]: forward function - Source: 'src/no_nested_borrows.rs', lines 296:0-296:48 *) + Source: 'src/no_nested_borrows.rs', lines 330:0-330:48 *) let rec list_length (t : Type0) (l : list_t t) : result u32 = begin match l with | List_Cons x l1 -> let* i = list_length t l1 in u32_add 1 i @@ -275,7 +331,7 @@ let rec list_length (t : Type0) (l : list_t t) : result u32 = end (** [no_nested_borrows::list_nth_shared]: forward function - Source: 'src/no_nested_borrows.rs', lines 304:0-304:62 *) + Source: 'src/no_nested_borrows.rs', lines 338:0-338:62 *) let rec list_nth_shared (t : Type0) (l : list_t t) (i : u32) : result t = begin match l with | List_Cons x tl -> @@ -286,7 +342,7 @@ let rec list_nth_shared (t : Type0) (l : list_t t) (i : u32) : result t = end (** [no_nested_borrows::list_nth_mut]: forward function - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 *) + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 *) let rec list_nth_mut (t : Type0) (l : list_t t) (i : u32) : result t = begin match l with | List_Cons x tl -> @@ -295,7 +351,7 @@ let rec list_nth_mut (t : Type0) (l : list_t t) (i : u32) : result t = end (** [no_nested_borrows::list_nth_mut]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 *) + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 *) let rec list_nth_mut_back (t : Type0) (l : list_t t) (i : u32) (ret : t) : result (list_t t) = begin match l with @@ -310,7 +366,7 @@ let rec list_nth_mut_back end (** [no_nested_borrows::list_rev_aux]: forward function - Source: 'src/no_nested_borrows.rs', lines 336:0-336:63 *) + Source: 'src/no_nested_borrows.rs', lines 370:0-370:63 *) let rec list_rev_aux (t : Type0) (li : list_t t) (lo : list_t t) : result (list_t t) = begin match li with @@ -320,12 +376,12 @@ let rec list_rev_aux (** [no_nested_borrows::list_rev]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 350:0-350:42 *) + Source: 'src/no_nested_borrows.rs', lines 384:0-384:42 *) let list_rev (t : Type0) (l : list_t t) : result (list_t t) = let li = core_mem_replace (list_t t) l List_Nil in list_rev_aux t li List_Nil (** [no_nested_borrows::test_list_functions]: forward function - Source: 'src/no_nested_borrows.rs', lines 355:0-355:28 *) + Source: 'src/no_nested_borrows.rs', lines 389:0-389:28 *) let test_list_functions : result unit = let l = List_Nil in let l0 = List_Cons 2 l in @@ -362,91 +418,91 @@ let test_list_functions : result unit = let _ = assert_norm (test_list_functions = Return ()) (** [no_nested_borrows::id_mut_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 *) + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 *) let id_mut_pair1 (t1 t2 : Type0) (x : t1) (y : t2) : result (t1 & t2) = Return (x, y) (** [no_nested_borrows::id_mut_pair1]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 *) + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 *) let id_mut_pair1_back (t1 t2 : Type0) (x : t1) (y : t2) (ret : (t1 & t2)) : result (t1 & t2) = let (x0, x1) = ret in Return (x0, x1) (** [no_nested_borrows::id_mut_pair2]: forward function - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 *) + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 *) let id_mut_pair2 (t1 t2 : Type0) (p : (t1 & t2)) : result (t1 & t2) = let (x, x0) = p in Return (x, x0) (** [no_nested_borrows::id_mut_pair2]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 *) + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 *) let id_mut_pair2_back (t1 t2 : Type0) (p : (t1 & t2)) (ret : (t1 & t2)) : result (t1 & t2) = let (x, x0) = ret in Return (x, x0) (** [no_nested_borrows::id_mut_pair3]: forward function - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) let id_mut_pair3 (t1 t2 : Type0) (x : t1) (y : t2) : result (t1 & t2) = Return (x, y) (** [no_nested_borrows::id_mut_pair3]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) let id_mut_pair3_back'a (t1 t2 : Type0) (x : t1) (y : t2) (ret : t1) : result t1 = Return ret (** [no_nested_borrows::id_mut_pair3]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 *) + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 *) let id_mut_pair3_back'b (t1 t2 : Type0) (x : t1) (y : t2) (ret : t2) : result t2 = Return ret (** [no_nested_borrows::id_mut_pair4]: forward function - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) let id_mut_pair4 (t1 t2 : Type0) (p : (t1 & t2)) : result (t1 & t2) = let (x, x0) = p in Return (x, x0) (** [no_nested_borrows::id_mut_pair4]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) let id_mut_pair4_back'a (t1 t2 : Type0) (p : (t1 & t2)) (ret : t1) : result t1 = Return ret (** [no_nested_borrows::id_mut_pair4]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 *) + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 *) let id_mut_pair4_back'b (t1 t2 : Type0) (p : (t1 & t2)) (ret : t2) : result t2 = Return ret (** [no_nested_borrows::StructWithTuple] - Source: 'src/no_nested_borrows.rs', lines 390:0-390:34 *) + Source: 'src/no_nested_borrows.rs', lines 424:0-424:34 *) type structWithTuple_t (t1 t2 : Type0) = { p : (t1 & t2); } (** [no_nested_borrows::new_tuple1]: forward function - Source: 'src/no_nested_borrows.rs', lines 394:0-394:48 *) + Source: 'src/no_nested_borrows.rs', lines 428:0-428:48 *) let new_tuple1 : result (structWithTuple_t u32 u32) = Return { p = (1, 2) } (** [no_nested_borrows::new_tuple2]: forward function - Source: 'src/no_nested_borrows.rs', lines 398:0-398:48 *) + Source: 'src/no_nested_borrows.rs', lines 432:0-432:48 *) let new_tuple2 : result (structWithTuple_t i16 i16) = Return { p = (1, 2) } (** [no_nested_borrows::new_tuple3]: forward function - Source: 'src/no_nested_borrows.rs', lines 402:0-402:48 *) + Source: 'src/no_nested_borrows.rs', lines 436:0-436:48 *) let new_tuple3 : result (structWithTuple_t u64 i64) = Return { p = (1, 2) } (** [no_nested_borrows::StructWithPair] - Source: 'src/no_nested_borrows.rs', lines 407:0-407:33 *) + Source: 'src/no_nested_borrows.rs', lines 441:0-441:33 *) type structWithPair_t (t1 t2 : Type0) = { p : pair_t t1 t2; } (** [no_nested_borrows::new_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 411:0-411:46 *) + Source: 'src/no_nested_borrows.rs', lines 445:0-445:46 *) let new_pair1 : result (structWithPair_t u32 u32) = Return { p = { x = 1; y = 2 } } (** [no_nested_borrows::test_constants]: forward function - Source: 'src/no_nested_borrows.rs', lines 419:0-419:23 *) + Source: 'src/no_nested_borrows.rs', lines 453:0-453:23 *) let test_constants : result unit = let* swt = new_tuple1 in let (i, _) = swt.p in @@ -470,7 +526,7 @@ let test_constants : result unit = let _ = assert_norm (test_constants = Return ()) (** [no_nested_borrows::test_weird_borrows1]: forward function - Source: 'src/no_nested_borrows.rs', lines 428:0-428:28 *) + Source: 'src/no_nested_borrows.rs', lines 462:0-462:28 *) let test_weird_borrows1 : result unit = Return () @@ -479,28 +535,28 @@ let _ = assert_norm (test_weird_borrows1 = Return ()) (** [no_nested_borrows::test_mem_replace]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 438:0-438:37 *) + Source: 'src/no_nested_borrows.rs', lines 472:0-472:37 *) let test_mem_replace (px : u32) : result u32 = let y = core_mem_replace u32 px 1 in if not (y = 0) then Fail Failure else Return 2 (** [no_nested_borrows::test_shared_borrow_bool1]: forward function - Source: 'src/no_nested_borrows.rs', lines 445:0-445:47 *) + Source: 'src/no_nested_borrows.rs', lines 479:0-479:47 *) let test_shared_borrow_bool1 (b : bool) : result u32 = if b then Return 0 else Return 1 (** [no_nested_borrows::test_shared_borrow_bool2]: forward function - Source: 'src/no_nested_borrows.rs', lines 458:0-458:40 *) + Source: 'src/no_nested_borrows.rs', lines 492:0-492:40 *) let test_shared_borrow_bool2 : result u32 = Return 0 (** [no_nested_borrows::test_shared_borrow_enum1]: forward function - Source: 'src/no_nested_borrows.rs', lines 473:0-473:52 *) + Source: 'src/no_nested_borrows.rs', lines 507:0-507:52 *) let test_shared_borrow_enum1 (l : list_t u32) : result u32 = begin match l with | List_Cons i l0 -> Return 1 | List_Nil -> Return 0 end (** [no_nested_borrows::test_shared_borrow_enum2]: forward function - Source: 'src/no_nested_borrows.rs', lines 485:0-485:40 *) + Source: 'src/no_nested_borrows.rs', lines 519:0-519:40 *) let test_shared_borrow_enum2 : result u32 = Return 0 diff --git a/tests/lean/BetreeMain/Funs.lean b/tests/lean/BetreeMain/Funs.lean index 4c862225..0d7cb984 100644 --- a/tests/lean/BetreeMain/Funs.lean +++ b/tests/lean/BetreeMain/Funs.lean @@ -256,6 +256,21 @@ divergent def betree.Node.lookup_first_message_for_key_back Result.ret (betree.List.Cons (i, m) next_msgs0) | betree.List.Nil => Result.ret ret +/- [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function + Source: 'src/betree.rs', lines 636:4-636:80 -/ +divergent def betree.Node.lookup_in_bindings + (key : U64) (bindings : betree.List (U64 × U64)) : Result (Option U64) := + match bindings with + | betree.List.Cons hd tl => + let (i, i0) := hd + if i = key + then Result.ret (some i0) + else + if i > key + then Result.ret none + else betree.Node.lookup_in_bindings key tl + | betree.List.Nil => Result.ret none + /- [betree_main::betree::{betree_main::betree::Node#5}::apply_upserts]: forward function Source: 'src/betree.rs', lines 819:4-819:90 -/ divergent def betree.Node.apply_upserts @@ -316,21 +331,6 @@ divergent def betree.Node.apply_upserts_back betree.List.push_front (U64 × betree.Message) msgs (key, betree.Message.Insert v) -/- [betree_main::betree::{betree_main::betree::Node#5}::lookup_in_bindings]: forward function - Source: 'src/betree.rs', lines 636:4-636:80 -/ -divergent def betree.Node.lookup_in_bindings - (key : U64) (bindings : betree.List (U64 × U64)) : Result (Option U64) := - match bindings with - | betree.List.Cons hd tl => - let (i, i0) := hd - if i = key - then Result.ret (some i0) - else - if i > key - then Result.ret none - else betree.Node.lookup_in_bindings key tl - | betree.List.Nil => Result.ret none - /- [betree_main::betree::{betree_main::betree::Internal#4}::lookup_in_children]: forward function Source: 'src/betree.rs', lines 395:4-395:63 -/ mutual divergent def betree.Internal.lookup_in_children diff --git a/tests/lean/NoNestedBorrows.lean b/tests/lean/NoNestedBorrows.lean index ca66c628..0c7dff8e 100644 --- a/tests/lean/NoNestedBorrows.lean +++ b/tests/lean/NoNestedBorrows.lean @@ -48,53 +48,111 @@ inductive Sum (T1 T2 : Type) := def neg_test (x : I32) : Result I32 := - x -/- [no_nested_borrows::add_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 54:0-54:38 -/ -def add_test (x : U32) (y : U32) : Result U32 := +/- [no_nested_borrows::add_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 54:0-54:37 -/ +def add_u32 (x : U32) (y : U32) : Result U32 := x + y -/- [no_nested_borrows::subs_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 60:0-60:39 -/ -def subs_test (x : U32) (y : U32) : Result U32 := +/- [no_nested_borrows::subs_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 60:0-60:38 -/ +def subs_u32 (x : U32) (y : U32) : Result U32 := x - y -/- [no_nested_borrows::div_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 66:0-66:38 -/ -def div_test (x : U32) (y : U32) : Result U32 := +/- [no_nested_borrows::div_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 66:0-66:37 -/ +def div_u32 (x : U32) (y : U32) : Result U32 := x / y -/- [no_nested_borrows::div_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 73:0-73:31 -/ -def div_test1 (x : U32) : Result U32 := +/- [no_nested_borrows::div_u32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 73:0-73:35 -/ +def div_u32_const (x : U32) : Result U32 := x / 2#u32 -/- [no_nested_borrows::rem_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 78:0-78:38 -/ -def rem_test (x : U32) (y : U32) : Result U32 := +/- [no_nested_borrows::rem_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 78:0-78:37 -/ +def rem_u32 (x : U32) (y : U32) : Result U32 := x % y -/- [no_nested_borrows::mul_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 82:0-82:38 -/ -def mul_test (x : U32) (y : U32) : Result U32 := +/- [no_nested_borrows::mul_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 82:0-82:37 -/ +def mul_u32 (x : U32) (y : U32) : Result U32 := x * y +/- [no_nested_borrows::add_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 88:0-88:37 -/ +def add_i32 (x : I32) (y : I32) : Result I32 := + x + y + +/- [no_nested_borrows::subs_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 92:0-92:38 -/ +def subs_i32 (x : I32) (y : I32) : Result I32 := + x - y + +/- [no_nested_borrows::div_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 96:0-96:37 -/ +def div_i32 (x : I32) (y : I32) : Result I32 := + x / y + +/- [no_nested_borrows::div_i32_const]: forward function + Source: 'src/no_nested_borrows.rs', lines 100:0-100:35 -/ +def div_i32_const (x : I32) : Result I32 := + x / 2#i32 + +/- [no_nested_borrows::rem_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 104:0-104:37 -/ +def rem_i32 (x : I32) (y : I32) : Result I32 := + x % y + +/- [no_nested_borrows::mul_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 108:0-108:37 -/ +def mul_i32 (x : I32) (y : I32) : Result I32 := + x * y + +/- [no_nested_borrows::mix_arith_u32]: forward function + Source: 'src/no_nested_borrows.rs', lines 112:0-112:51 -/ +def mix_arith_u32 (x : U32) (y : U32) (z : U32) : Result U32 := + do + let i ← x + y + let i0 ← x / y + let i1 ← i * i0 + let i2 ← z % y + let i3 ← x - i2 + let i4 ← i1 + i3 + let i5 ← x + y + let i6 ← i5 + z + i4 % i6 + +/- [no_nested_borrows::mix_arith_i32]: forward function + Source: 'src/no_nested_borrows.rs', lines 116:0-116:51 -/ +def mix_arith_i32 (x : I32) (y : I32) (z : I32) : Result I32 := + do + let i ← x + y + let i0 ← x / y + let i1 ← i * i0 + let i2 ← z % y + let i3 ← x - i2 + let i4 ← i1 + i3 + let i5 ← x + y + let i6 ← i5 + z + i4 % i6 + /- [no_nested_borrows::CONST0] - Source: 'src/no_nested_borrows.rs', lines 91:0-91:23 -/ + Source: 'src/no_nested_borrows.rs', lines 125:0-125:23 -/ def const0_body : Result Usize := 1#usize + 1#usize def const0_c : Usize := eval_global const0_body (by simp) /- [no_nested_borrows::CONST1] - Source: 'src/no_nested_borrows.rs', lines 92:0-92:23 -/ + Source: 'src/no_nested_borrows.rs', lines 126:0-126:23 -/ def const1_body : Result Usize := 2#usize * 2#usize def const1_c : Usize := eval_global const1_body (by simp) /- [no_nested_borrows::cast_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 94:0-94:31 -/ + Source: 'src/no_nested_borrows.rs', lines 128:0-128:31 -/ def cast_test (x : U32) : Result I32 := Scalar.cast .I32 x /- [no_nested_borrows::test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 99:0-99:14 -/ + Source: 'src/no_nested_borrows.rs', lines 133:0-133:14 -/ def test2 : Result Unit := do let _ ← 23#u32 + 44#u32 @@ -104,14 +162,14 @@ def test2 : Result Unit := #assert (test2 == Result.ret ()) /- [no_nested_borrows::get_max]: forward function - Source: 'src/no_nested_borrows.rs', lines 111:0-111:37 -/ + Source: 'src/no_nested_borrows.rs', lines 145:0-145:37 -/ def get_max (x : U32) (y : U32) : Result U32 := if x >= y then Result.ret x else Result.ret y /- [no_nested_borrows::test3]: forward function - Source: 'src/no_nested_borrows.rs', lines 119:0-119:14 -/ + Source: 'src/no_nested_borrows.rs', lines 153:0-153:14 -/ def test3 : Result Unit := do let x ← get_max 4#u32 3#u32 @@ -125,7 +183,7 @@ def test3 : Result Unit := #assert (test3 == Result.ret ()) /- [no_nested_borrows::test_neg1]: forward function - Source: 'src/no_nested_borrows.rs', lines 126:0-126:18 -/ + Source: 'src/no_nested_borrows.rs', lines 160:0-160:18 -/ def test_neg1 : Result Unit := do let y ← - 3#i32 @@ -137,7 +195,7 @@ def test_neg1 : Result Unit := #assert (test_neg1 == Result.ret ()) /- [no_nested_borrows::refs_test1]: forward function - Source: 'src/no_nested_borrows.rs', lines 133:0-133:19 -/ + Source: 'src/no_nested_borrows.rs', lines 167:0-167:19 -/ def refs_test1 : Result Unit := if not (1#i32 = 1#i32) then Result.fail .panic @@ -147,7 +205,7 @@ def refs_test1 : Result Unit := #assert (refs_test1 == Result.ret ()) /- [no_nested_borrows::refs_test2]: forward function - Source: 'src/no_nested_borrows.rs', lines 144:0-144:19 -/ + Source: 'src/no_nested_borrows.rs', lines 178:0-178:19 -/ def refs_test2 : Result Unit := if not (2#i32 = 2#i32) then Result.fail .panic @@ -165,7 +223,7 @@ def refs_test2 : Result Unit := #assert (refs_test2 == Result.ret ()) /- [no_nested_borrows::test_list1]: forward function - Source: 'src/no_nested_borrows.rs', lines 160:0-160:19 -/ + Source: 'src/no_nested_borrows.rs', lines 194:0-194:19 -/ def test_list1 : Result Unit := Result.ret () @@ -173,7 +231,7 @@ def test_list1 : Result Unit := #assert (test_list1 == Result.ret ()) /- [no_nested_borrows::test_box1]: forward function - Source: 'src/no_nested_borrows.rs', lines 165:0-165:18 -/ + Source: 'src/no_nested_borrows.rs', lines 199:0-199:18 -/ def test_box1 : Result Unit := do let b := 0#i32 @@ -187,26 +245,26 @@ def test_box1 : Result Unit := #assert (test_box1 == Result.ret ()) /- [no_nested_borrows::copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 175:0-175:30 -/ + Source: 'src/no_nested_borrows.rs', lines 209:0-209:30 -/ def copy_int (x : I32) : Result I32 := Result.ret x /- [no_nested_borrows::test_unreachable]: forward function - Source: 'src/no_nested_borrows.rs', lines 181:0-181:32 -/ + Source: 'src/no_nested_borrows.rs', lines 215:0-215:32 -/ def test_unreachable (b : Bool) : Result Unit := if b then Result.fail .panic else Result.ret () /- [no_nested_borrows::test_panic]: forward function - Source: 'src/no_nested_borrows.rs', lines 189:0-189:26 -/ + Source: 'src/no_nested_borrows.rs', lines 223:0-223:26 -/ def test_panic (b : Bool) : Result Unit := if b then Result.fail .panic else Result.ret () /- [no_nested_borrows::test_copy_int]: forward function - Source: 'src/no_nested_borrows.rs', lines 196:0-196:22 -/ + Source: 'src/no_nested_borrows.rs', lines 230:0-230:22 -/ def test_copy_int : Result Unit := do let y ← copy_int 0#i32 @@ -218,14 +276,14 @@ def test_copy_int : Result Unit := #assert (test_copy_int == Result.ret ()) /- [no_nested_borrows::is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 203:0-203:38 -/ + Source: 'src/no_nested_borrows.rs', lines 237:0-237:38 -/ def is_cons (T : Type) (l : List T) : Result Bool := match l with | List.Cons t l0 => Result.ret true | List.Nil => Result.ret false /- [no_nested_borrows::test_is_cons]: forward function - Source: 'src/no_nested_borrows.rs', lines 210:0-210:21 -/ + Source: 'src/no_nested_borrows.rs', lines 244:0-244:21 -/ def test_is_cons : Result Unit := do let l := List.Nil @@ -238,14 +296,14 @@ def test_is_cons : Result Unit := #assert (test_is_cons == Result.ret ()) /- [no_nested_borrows::split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 216:0-216:48 -/ + Source: 'src/no_nested_borrows.rs', lines 250:0-250:48 -/ def split_list (T : Type) (l : List T) : Result (T × (List T)) := match l with | List.Cons hd tl => Result.ret (hd, tl) | List.Nil => Result.fail .panic /- [no_nested_borrows::test_split_list]: forward function - Source: 'src/no_nested_borrows.rs', lines 224:0-224:24 -/ + Source: 'src/no_nested_borrows.rs', lines 258:0-258:24 -/ def test_split_list : Result Unit := do let l := List.Nil @@ -259,14 +317,14 @@ def test_split_list : Result Unit := #assert (test_split_list == Result.ret ()) /- [no_nested_borrows::choose]: forward function - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 -/ + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 -/ def choose (T : Type) (b : Bool) (x : T) (y : T) : Result T := if b then Result.ret x else Result.ret y /- [no_nested_borrows::choose]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 231:0-231:70 -/ + Source: 'src/no_nested_borrows.rs', lines 265:0-265:70 -/ def choose_back (T : Type) (b : Bool) (x : T) (y : T) (ret : T) : Result (T × T) := if b @@ -274,7 +332,7 @@ def choose_back else Result.ret (x, ret) /- [no_nested_borrows::choose_test]: forward function - Source: 'src/no_nested_borrows.rs', lines 239:0-239:20 -/ + Source: 'src/no_nested_borrows.rs', lines 273:0-273:20 -/ def choose_test : Result Unit := do let z ← choose I32 true 0#i32 0#i32 @@ -294,20 +352,20 @@ def choose_test : Result Unit := #assert (choose_test == Result.ret ()) /- [no_nested_borrows::test_char]: forward function - Source: 'src/no_nested_borrows.rs', lines 251:0-251:26 -/ + Source: 'src/no_nested_borrows.rs', lines 285:0-285:26 -/ def test_char : Result Char := Result.ret 'a' mutual /- [no_nested_borrows::Tree] - Source: 'src/no_nested_borrows.rs', lines 256:0-256:16 -/ + Source: 'src/no_nested_borrows.rs', lines 290:0-290:16 -/ inductive Tree (T : Type) := | Leaf : T → Tree T | Node : T → NodeElem T → Tree T → Tree T /- [no_nested_borrows::NodeElem] - Source: 'src/no_nested_borrows.rs', lines 261:0-261:20 -/ + Source: 'src/no_nested_borrows.rs', lines 295:0-295:20 -/ inductive NodeElem (T : Type) := | Cons : Tree T → NodeElem T → NodeElem T | Nil : NodeElem T @@ -315,7 +373,7 @@ inductive NodeElem (T : Type) := end /- [no_nested_borrows::list_length]: forward function - Source: 'src/no_nested_borrows.rs', lines 296:0-296:48 -/ + Source: 'src/no_nested_borrows.rs', lines 330:0-330:48 -/ divergent def list_length (T : Type) (l : List T) : Result U32 := match l with | List.Cons t l1 => do @@ -324,7 +382,7 @@ divergent def list_length (T : Type) (l : List T) : Result U32 := | List.Nil => Result.ret 0#u32 /- [no_nested_borrows::list_nth_shared]: forward function - Source: 'src/no_nested_borrows.rs', lines 304:0-304:62 -/ + Source: 'src/no_nested_borrows.rs', lines 338:0-338:62 -/ divergent def list_nth_shared (T : Type) (l : List T) (i : U32) : Result T := match l with | List.Cons x tl => @@ -336,7 +394,7 @@ divergent def list_nth_shared (T : Type) (l : List T) (i : U32) : Result T := | List.Nil => Result.fail .panic /- [no_nested_borrows::list_nth_mut]: forward function - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 -/ + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 -/ divergent def list_nth_mut (T : Type) (l : List T) (i : U32) : Result T := match l with | List.Cons x tl => @@ -348,7 +406,7 @@ divergent def list_nth_mut (T : Type) (l : List T) (i : U32) : Result T := | List.Nil => Result.fail .panic /- [no_nested_borrows::list_nth_mut]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 320:0-320:67 -/ + Source: 'src/no_nested_borrows.rs', lines 354:0-354:67 -/ divergent def list_nth_mut_back (T : Type) (l : List T) (i : U32) (ret : T) : Result (List T) := match l with @@ -363,7 +421,7 @@ divergent def list_nth_mut_back | List.Nil => Result.fail .panic /- [no_nested_borrows::list_rev_aux]: forward function - Source: 'src/no_nested_borrows.rs', lines 336:0-336:63 -/ + Source: 'src/no_nested_borrows.rs', lines 370:0-370:63 -/ divergent def list_rev_aux (T : Type) (li : List T) (lo : List T) : Result (List T) := match li with @@ -372,13 +430,13 @@ divergent def list_rev_aux /- [no_nested_borrows::list_rev]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 350:0-350:42 -/ + Source: 'src/no_nested_borrows.rs', lines 384:0-384:42 -/ def list_rev (T : Type) (l : List T) : Result (List T) := let li := core.mem.replace (List T) l List.Nil list_rev_aux T li List.Nil /- [no_nested_borrows::test_list_functions]: forward function - Source: 'src/no_nested_borrows.rs', lines 355:0-355:28 -/ + Source: 'src/no_nested_borrows.rs', lines 389:0-389:28 -/ def test_list_functions : Result Unit := do let l := List.Nil @@ -425,97 +483,97 @@ def test_list_functions : Result Unit := #assert (test_list_functions == Result.ret ()) /- [no_nested_borrows::id_mut_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 -/ + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 -/ def id_mut_pair1 (T1 T2 : Type) (x : T1) (y : T2) : Result (T1 × T2) := Result.ret (x, y) /- [no_nested_borrows::id_mut_pair1]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 371:0-371:89 -/ + Source: 'src/no_nested_borrows.rs', lines 405:0-405:89 -/ def id_mut_pair1_back (T1 T2 : Type) (x : T1) (y : T2) (ret : (T1 × T2)) : Result (T1 × T2) := let (t, t0) := ret Result.ret (t, t0) /- [no_nested_borrows::id_mut_pair2]: forward function - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 -/ + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 -/ def id_mut_pair2 (T1 T2 : Type) (p : (T1 × T2)) : Result (T1 × T2) := let (t, t0) := p Result.ret (t, t0) /- [no_nested_borrows::id_mut_pair2]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 375:0-375:88 -/ + Source: 'src/no_nested_borrows.rs', lines 409:0-409:88 -/ def id_mut_pair2_back (T1 T2 : Type) (p : (T1 × T2)) (ret : (T1 × T2)) : Result (T1 × T2) := let (t, t0) := ret Result.ret (t, t0) /- [no_nested_borrows::id_mut_pair3]: forward function - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 -/ + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 -/ def id_mut_pair3 (T1 T2 : Type) (x : T1) (y : T2) : Result (T1 × T2) := Result.ret (x, y) /- [no_nested_borrows::id_mut_pair3]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 -/ + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 -/ def id_mut_pair3_back'a (T1 T2 : Type) (x : T1) (y : T2) (ret : T1) : Result T1 := Result.ret ret /- [no_nested_borrows::id_mut_pair3]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 379:0-379:93 -/ + Source: 'src/no_nested_borrows.rs', lines 413:0-413:93 -/ def id_mut_pair3_back'b (T1 T2 : Type) (x : T1) (y : T2) (ret : T2) : Result T2 := Result.ret ret /- [no_nested_borrows::id_mut_pair4]: forward function - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 -/ + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 -/ def id_mut_pair4 (T1 T2 : Type) (p : (T1 × T2)) : Result (T1 × T2) := let (t, t0) := p Result.ret (t, t0) /- [no_nested_borrows::id_mut_pair4]: backward function 0 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 -/ + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 -/ def id_mut_pair4_back'a (T1 T2 : Type) (p : (T1 × T2)) (ret : T1) : Result T1 := Result.ret ret /- [no_nested_borrows::id_mut_pair4]: backward function 1 - Source: 'src/no_nested_borrows.rs', lines 383:0-383:92 -/ + Source: 'src/no_nested_borrows.rs', lines 417:0-417:92 -/ def id_mut_pair4_back'b (T1 T2 : Type) (p : (T1 × T2)) (ret : T2) : Result T2 := Result.ret ret /- [no_nested_borrows::StructWithTuple] - Source: 'src/no_nested_borrows.rs', lines 390:0-390:34 -/ + Source: 'src/no_nested_borrows.rs', lines 424:0-424:34 -/ structure StructWithTuple (T1 T2 : Type) where p : (T1 × T2) /- [no_nested_borrows::new_tuple1]: forward function - Source: 'src/no_nested_borrows.rs', lines 394:0-394:48 -/ + Source: 'src/no_nested_borrows.rs', lines 428:0-428:48 -/ def new_tuple1 : Result (StructWithTuple U32 U32) := Result.ret { p := (1#u32, 2#u32) } /- [no_nested_borrows::new_tuple2]: forward function - Source: 'src/no_nested_borrows.rs', lines 398:0-398:48 -/ + Source: 'src/no_nested_borrows.rs', lines 432:0-432:48 -/ def new_tuple2 : Result (StructWithTuple I16 I16) := Result.ret { p := (1#i16, 2#i16) } /- [no_nested_borrows::new_tuple3]: forward function - Source: 'src/no_nested_borrows.rs', lines 402:0-402:48 -/ + Source: 'src/no_nested_borrows.rs', lines 436:0-436:48 -/ def new_tuple3 : Result (StructWithTuple U64 I64) := Result.ret { p := (1#u64, 2#i64) } /- [no_nested_borrows::StructWithPair] - Source: 'src/no_nested_borrows.rs', lines 407:0-407:33 -/ + Source: 'src/no_nested_borrows.rs', lines 441:0-441:33 -/ structure StructWithPair (T1 T2 : Type) where p : Pair T1 T2 /- [no_nested_borrows::new_pair1]: forward function - Source: 'src/no_nested_borrows.rs', lines 411:0-411:46 -/ + Source: 'src/no_nested_borrows.rs', lines 445:0-445:46 -/ def new_pair1 : Result (StructWithPair U32 U32) := Result.ret { p := { x := 1#u32, y := 2#u32 } } /- [no_nested_borrows::test_constants]: forward function - Source: 'src/no_nested_borrows.rs', lines 419:0-419:23 -/ + Source: 'src/no_nested_borrows.rs', lines 453:0-453:23 -/ def test_constants : Result Unit := do let swt ← new_tuple1 @@ -545,7 +603,7 @@ def test_constants : Result Unit := #assert (test_constants == Result.ret ()) /- [no_nested_borrows::test_weird_borrows1]: forward function - Source: 'src/no_nested_borrows.rs', lines 428:0-428:28 -/ + Source: 'src/no_nested_borrows.rs', lines 462:0-462:28 -/ def test_weird_borrows1 : Result Unit := Result.ret () @@ -554,7 +612,7 @@ def test_weird_borrows1 : Result Unit := /- [no_nested_borrows::test_mem_replace]: merged forward/backward function (there is a single backward function, and the forward function returns ()) - Source: 'src/no_nested_borrows.rs', lines 438:0-438:37 -/ + Source: 'src/no_nested_borrows.rs', lines 472:0-472:37 -/ def test_mem_replace (px : U32) : Result U32 := let y := core.mem.replace U32 px 1#u32 if not (y = 0#u32) @@ -562,26 +620,26 @@ def test_mem_replace (px : U32) : Result U32 := else Result.ret 2#u32 /- [no_nested_borrows::test_shared_borrow_bool1]: forward function - Source: 'src/no_nested_borrows.rs', lines 445:0-445:47 -/ + Source: 'src/no_nested_borrows.rs', lines 479:0-479:47 -/ def test_shared_borrow_bool1 (b : Bool) : Result U32 := if b then Result.ret 0#u32 else Result.ret 1#u32 /- [no_nested_borrows::test_shared_borrow_bool2]: forward function - Source: 'src/no_nested_borrows.rs', lines 458:0-458:40 -/ + Source: 'src/no_nested_borrows.rs', lines 492:0-492:40 -/ def test_shared_borrow_bool2 : Result U32 := Result.ret 0#u32 /- [no_nested_borrows::test_shared_borrow_enum1]: forward function - Source: 'src/no_nested_borrows.rs', lines 473:0-473:52 -/ + Source: 'src/no_nested_borrows.rs', lines 507:0-507:52 -/ def test_shared_borrow_enum1 (l : List U32) : Result U32 := match l with | List.Cons i l0 => Result.ret 1#u32 | List.Nil => Result.ret 0#u32 /- [no_nested_borrows::test_shared_borrow_enum2]: forward function - Source: 'src/no_nested_borrows.rs', lines 485:0-485:40 -/ + Source: 'src/no_nested_borrows.rs', lines 519:0-519:40 -/ def test_shared_borrow_enum2 : Result U32 := Result.ret 0#u32 |