diff options
Diffstat (limited to 'tests/fstar/hashmap')
| -rw-r--r-- | tests/fstar/hashmap/Hashmap.Properties.fst | 1648 | ||||
| -rw-r--r-- | tests/fstar/hashmap/Hashmap.Properties.fsti | 100 | ||||
| -rw-r--r-- | tests/fstar/hashmap/Primitives.fst | 18 |
3 files changed, 891 insertions, 875 deletions
diff --git a/tests/fstar/hashmap/Hashmap.Properties.fst b/tests/fstar/hashmap/Hashmap.Properties.fst index 49d96cd5..def520f0 100644 --- a/tests/fstar/hashmap/Hashmap.Properties.fst +++ b/tests/fstar/hashmap/Hashmap.Properties.fst @@ -272,7 +272,7 @@ type pos_usize = x:usize{x > 0} type binding (t : Type0) = key & t -type slots_t (t : Type0) = vec (list_t t) +type slots_t (t : Type0) = alloc_vec_Vec (list_t t) /// We represent hash maps as associative lists type assoc_list (t : Type0) = list (binding t) @@ -280,8 +280,8 @@ type assoc_list (t : Type0) = list (binding t) /// Representation function for [list_t] let rec list_t_v (#t : Type0) (ls : list_t t) : assoc_list t = match ls with - | ListNil -> [] - | ListCons k v tl -> (k,v) :: list_t_v tl + | List_Nil -> [] + | List_Cons k v tl -> (k,v) :: list_t_v tl let list_t_len (#t : Type0) (ls : list_t t) : nat = length (list_t_v ls) let list_t_index (#t : Type0) (ls : list_t t) (i : nat{i < list_t_len ls}) : binding t = @@ -305,30 +305,30 @@ let slots_t_al_v (#t : Type0) (slots : slots_t t) : assoc_list t = /// list per slot). This is the representation we use most, internally. Note that /// we later introduce a [map_s] representation, which is the one used in the /// lemmas shown to the user. -type hash_map_s t = list (slot_s t) +type hashMap_s t = list (slot_s t) // TODO: why not always have the condition on the length? // 'nes': "non-empty slots" -type hash_map_s_nes (t : Type0) : Type0 = - hm:hash_map_s t{is_pos_usize (length hm)} +type hashMap_s_nes (t : Type0) : Type0 = + hm:hashMap_s t{is_pos_usize (length hm)} -/// Representation function for [hash_map_t] as a list of slots -let hash_map_t_v (#t : Type0) (hm : hash_map_t t) : hash_map_s t = - map list_t_v hm.hash_map_slots +/// Representation function for [hashMap_t] as a list of slots +let hashMap_t_v (#t : Type0) (hm : hashMap_t t) : hashMap_s t = + map list_t_v hm.slots -/// Representation function for [hash_map_t] as an associative list -let hash_map_t_al_v (#t : Type0) (hm : hash_map_t t) : assoc_list t = - flatten (hash_map_t_v hm) +/// Representation function for [hashMap_t] as an associative list +let hashMap_t_al_v (#t : Type0) (hm : hashMap_t t) : assoc_list t = + flatten (hashMap_t_v hm) // 'nes': "non-empty slots" -type hash_map_t_nes (t : Type0) : Type0 = - hm:hash_map_t t{is_pos_usize (length hm.hash_map_slots)} +type hashMap_t_nes (t : Type0) : Type0 = + hm:hashMap_t t{is_pos_usize (length hm.slots)} -let hash_key (k : key) : hash = - Return?.v (hash_key_fwd k) +let hash_key_s (k : key) : hash = + Return?.v (hash_key k) let hash_mod_key (k : key) (len : usize{len > 0}) : hash = - (hash_key k) % len + (hash_key_s k) % len let not_same_key (#t : Type0) (k : key) (b : binding t) : bool = fst b <> k let same_key (#t : Type0) (k : key) (b : binding t) : bool = fst b = k @@ -339,8 +339,8 @@ let same_hash_mod_key (#t : Type0) (len : usize{len > 0}) (h : nat) (b : binding let binding_neq (#t : Type0) (b0 b1 : binding t) : bool = fst b0 <> fst b1 -let hash_map_t_len_s (#t : Type0) (hm : hash_map_t t) : nat = - hm.hash_map_num_entries +let hashMap_t_len_s (#t : Type0) (hm : hashMap_t t) : nat = + hm.num_entries let assoc_list_find (#t : Type0) (k : key) (slot : assoc_list t) : option t = match find (same_key k) slot with @@ -354,26 +354,26 @@ let slot_t_find_s (#t : Type0) (k : key) (slot : list_t t) : option t = slot_s_find k (slot_t_v slot) // This is a simpler version of the "find" function, which captures the essence -// of what happens and operates on [hash_map_s]. -let hash_map_s_find - (#t : Type0) (hm : hash_map_s_nes t) +// of what happens and operates on [hashMap_s]. +let hashMap_s_find + (#t : Type0) (hm : hashMap_s_nes t) (k : key) : option t = let i = hash_mod_key k (length hm) in let slot = index hm i in slot_s_find k slot -let hash_map_s_len - (#t : Type0) (hm : hash_map_s t) : +let hashMap_s_len + (#t : Type0) (hm : hashMap_s t) : nat = length (flatten hm) -// Same as above, but operates on [hash_map_t] +// Same as above, but operates on [hashMap_t] // Note that we don't reuse the above function on purpose: converting to a -// [hash_map_s] then looking up an element is not the same as what we +// [hashMap_s] then looking up an element is not the same as what we // wrote below. -let hash_map_t_find_s - (#t : Type0) (hm : hash_map_t t{length hm.hash_map_slots > 0}) (k : key) : option t = - let slots = hm.hash_map_slots in +let hashMap_t_find_s + (#t : Type0) (hm : hashMap_t t{length hm.slots > 0}) (k : key) : option t = + let slots = hm.slots in let i = hash_mod_key k (length slots) in let slot = index slots i in slot_t_find_s k slot @@ -404,74 +404,74 @@ let slots_t_inv (#t : Type0) (slots : slots_t t{length slots <= usize_max}) : Ty {:pattern index slots i} slot_t_inv (length slots) i (index slots i) -let hash_map_s_inv (#t : Type0) (hm : hash_map_s t) : Type0 = +let hashMap_s_inv (#t : Type0) (hm : hashMap_s t) : Type0 = length hm <= usize_max /\ length hm > 0 /\ slots_s_inv hm /// Base invariant for the hashmap (the complete invariant can be temporarily /// broken between the moment we inserted an element and the moment we resize) -let hash_map_t_base_inv (#t : Type0) (hm : hash_map_t t) : Type0 = - let al = hash_map_t_al_v hm in +let hashMap_t_base_inv (#t : Type0) (hm : hashMap_t t) : Type0 = + let al = hashMap_t_al_v hm in // [num_entries] correctly tracks the number of entries in the table // Note that it gives us that the length of the slots array is <= usize_max: // [> length <= usize_max - // (because hash_map_num_entries has type `usize`) - hm.hash_map_num_entries = length al /\ + // (because hashMap_num_entries has type `usize`) + hm.num_entries = length al /\ // Slots invariant - slots_t_inv hm.hash_map_slots /\ + slots_t_inv hm.slots /\ // The capacity must be > 0 (otherwise we can't resize, because we // multiply the capacity by two!) - length hm.hash_map_slots > 0 /\ + length hm.slots > 0 /\ // Load computation begin - let capacity = length hm.hash_map_slots in - let (dividend, divisor) = hm.hash_map_max_load_factor in + let capacity = length hm.slots in + let (dividend, divisor) = hm.max_load_factor in 0 < dividend /\ dividend < divisor /\ capacity * dividend >= divisor /\ - hm.hash_map_max_load = (capacity * dividend) / divisor + hm.max_load = (capacity * dividend) / divisor end /// We often need to frame some values -let hash_map_t_same_params (#t : Type0) (hm0 hm1 : hash_map_t t) : Type0 = - length hm0.hash_map_slots = length hm1.hash_map_slots /\ - hm0.hash_map_max_load = hm1.hash_map_max_load /\ - hm0.hash_map_max_load_factor = hm1.hash_map_max_load_factor +let hashMap_t_same_params (#t : Type0) (hm0 hm1 : hashMap_t t) : Type0 = + length hm0.slots = length hm1.slots /\ + hm0.max_load = hm1.max_load /\ + hm0.max_load_factor = hm1.max_load_factor /// The following invariants, etc. are meant to be revealed to the user through /// the .fsti. /// Invariant for the hashmap -let hash_map_t_inv (#t : Type0) (hm : hash_map_t t) : Type0 = +let hashMap_t_inv (#t : Type0) (hm : hashMap_t t) : Type0 = // Base invariant - hash_map_t_base_inv hm /\ + hashMap_t_base_inv hm /\ // The hash map is either: not overloaded, or we can't resize it begin - let (dividend, divisor) = hm.hash_map_max_load_factor in - hm.hash_map_num_entries <= hm.hash_map_max_load - || length hm.hash_map_slots * 2 * dividend > usize_max + let (dividend, divisor) = hm.max_load_factor in + hm.num_entries <= hm.max_load + || length hm.slots * 2 * dividend > usize_max end (*** .fsti *) /// We reveal slightly different version of the above functions to the user -let len_s (#t : Type0) (hm : hash_map_t t) : nat = hash_map_t_len_s hm +let len_s (#t : Type0) (hm : hashMap_t t) : nat = hashMap_t_len_s hm -/// This version doesn't take any precondition (contrary to [hash_map_t_find_s]) -let find_s (#t : Type0) (hm : hash_map_t t) (k : key) : option t = - if length hm.hash_map_slots = 0 then None - else hash_map_t_find_s hm k +/// This version doesn't take any precondition (contrary to [hashMap_t_find_s]) +let find_s (#t : Type0) (hm : hashMap_t t) (k : key) : option t = + if length hm.slots = 0 then None + else hashMap_t_find_s hm k (*** Overloading *) -let hash_map_not_overloaded_lem #t hm = () +let hashMap_not_overloaded_lem #t hm = () (*** allocate_slots *) /// Auxiliary lemma val slots_t_all_nil_inv_lem - (#t : Type0) (slots : vec (list_t t){length slots <= usize_max}) : - Lemma (requires (forall (i:nat{i < length slots}). index slots i == ListNil)) + (#t : Type0) (slots : alloc_vec_Vec (list_t t){length slots <= usize_max}) : + Lemma (requires (forall (i:nat{i < length slots}). index slots i == List_Nil)) (ensures (slots_t_inv slots)) #push-options "--fuel 1" @@ -479,8 +479,8 @@ let slots_t_all_nil_inv_lem #t slots = () #pop-options val slots_t_al_v_all_nil_is_empty_lem - (#t : Type0) (slots : vec (list_t t)) : - Lemma (requires (forall (i:nat{i < length slots}). index slots i == ListNil)) + (#t : Type0) (slots : alloc_vec_Vec (list_t t)) : + Lemma (requires (forall (i:nat{i < length slots}). index slots i == List_Nil)) (ensures (slots_t_al_v slots == [])) #push-options "--fuel 1" @@ -492,44 +492,44 @@ let rec slots_t_al_v_all_nil_is_empty_lem #t slots = slots_t_al_v_all_nil_is_empty_lem #t slots'; assert(slots_t_al_v slots == list_t_v s @ slots_t_al_v slots'); assert(slots_t_al_v slots == list_t_v s); - assert(index slots 0 == ListNil) + assert(index slots 0 == List_Nil) #pop-options /// [allocate_slots] -val hash_map_allocate_slots_fwd_lem - (t : Type0) (slots : vec (list_t t)) (n : usize) : +val hashMap_allocate_slots_lem + (t : Type0) (slots : alloc_vec_Vec (list_t t)) (n : usize) : Lemma (requires (length slots + n <= usize_max)) (ensures ( - match hash_map_allocate_slots_fwd t slots n with + match hashMap_allocate_slots t slots n with | Fail _ -> False | Return slots' -> length slots' = length slots + n /\ // We leave the already allocated slots unchanged (forall (i:nat{i < length slots}). index slots' i == index slots i) /\ // We allocate n additional empty slots - (forall (i:nat{length slots <= i /\ i < length slots'}). index slots' i == ListNil))) - (decreases (hash_map_allocate_slots_loop_decreases t slots n)) + (forall (i:nat{length slots <= i /\ i < length slots'}). index slots' i == List_Nil))) + (decreases (hashMap_allocate_slots_loop_decreases t slots n)) #push-options "--fuel 1" -let rec hash_map_allocate_slots_fwd_lem t slots n = +let rec hashMap_allocate_slots_lem t slots n = begin match n with | 0 -> () | _ -> - begin match vec_push_back (list_t t) slots ListNil with + begin match alloc_vec_Vec_push (list_t t) slots List_Nil with | Fail _ -> () | Return slots1 -> begin match usize_sub n 1 with | Fail _ -> () | Return i -> - hash_map_allocate_slots_fwd_lem t slots1 i; - begin match hash_map_allocate_slots_fwd t slots1 i with + hashMap_allocate_slots_lem t slots1 i; + begin match hashMap_allocate_slots t slots1 i with | Fail _ -> () | Return slots2 -> assert(length slots1 = length slots + 1); - assert(slots1 == slots @ [ListNil]); // Triggers patterns - assert(index slots1 (length slots) == index [ListNil] 0); // Triggers patterns - assert(index slots1 (length slots) == ListNil) + assert(slots1 == slots @ [List_Nil]); // Triggers patterns + assert(index slots1 (length slots) == index [List_Nil] 0); // Triggers patterns + assert(index slots1 (length slots) == List_Nil) end end end @@ -538,7 +538,7 @@ let rec hash_map_allocate_slots_fwd_lem t slots n = (*** new_with_capacity *) /// Under proper conditions, [new_with_capacity] doesn't fail and returns an empty hash map. -val hash_map_new_with_capacity_fwd_lem +val hashMap_new_with_capacity_lem (t : Type0) (capacity : usize) (max_load_dividend : usize) (max_load_divisor : usize) : Lemma @@ -549,31 +549,31 @@ val hash_map_new_with_capacity_fwd_lem capacity * max_load_dividend >= max_load_divisor /\ capacity * max_load_dividend <= usize_max)) (ensures ( - match hash_map_new_with_capacity_fwd t capacity max_load_dividend max_load_divisor with + match hashMap_new_with_capacity t capacity max_load_dividend max_load_divisor with | Fail _ -> False | Return hm -> // The hash map invariant is satisfied - hash_map_t_inv hm /\ + hashMap_t_inv hm /\ // The parameters are correct - hm.hash_map_max_load_factor = (max_load_dividend, max_load_divisor) /\ - hm.hash_map_max_load = (capacity * max_load_dividend) / max_load_divisor /\ + hm.max_load_factor = (max_load_dividend, max_load_divisor) /\ + hm.max_load = (capacity * max_load_dividend) / max_load_divisor /\ // The hash map has the specified capacity - we need to reveal this - // otherwise the pre of [hash_map_t_find_s] is not satisfied. - length hm.hash_map_slots = capacity /\ + // otherwise the pre of [hashMap_t_find_s] is not satisfied. + length hm.slots = capacity /\ // The hash map has 0 values - hash_map_t_len_s hm = 0 /\ + hashMap_t_len_s hm = 0 /\ // It contains no bindings - (forall k. hash_map_t_find_s hm k == None) /\ + (forall k. hashMap_t_find_s hm k == None) /\ // We need this low-level property for the invariant - (forall(i:nat{i < length hm.hash_map_slots}). index hm.hash_map_slots i == ListNil))) + (forall(i:nat{i < length hm.slots}). index hm.slots i == List_Nil))) #push-options "--z3rlimit 50 --fuel 1" -let hash_map_new_with_capacity_fwd_lem (t : Type0) (capacity : usize) +let hashMap_new_with_capacity_lem (t : Type0) (capacity : usize) (max_load_dividend : usize) (max_load_divisor : usize) = - let v = vec_new (list_t t) in + let v = alloc_vec_Vec_new (list_t t) in assert(length v = 0); - hash_map_allocate_slots_fwd_lem t v capacity; - begin match hash_map_allocate_slots_fwd t v capacity with + hashMap_allocate_slots_lem t v capacity; + begin match hashMap_allocate_slots t v capacity with | Fail _ -> assert(False) | Return v0 -> begin match usize_mul capacity max_load_dividend with @@ -582,9 +582,9 @@ let hash_map_new_with_capacity_fwd_lem (t : Type0) (capacity : usize) begin match usize_div i max_load_divisor with | Fail _ -> assert(False) | Return i0 -> - let hm = Mkhash_map_t 0 (max_load_dividend, max_load_divisor) i0 v0 in + let hm = MkhashMap_t 0 (max_load_dividend, max_load_divisor) i0 v0 in slots_t_all_nil_inv_lem v0; - slots_t_al_v_all_nil_is_empty_lem hm.hash_map_slots + slots_t_al_v_all_nil_is_empty_lem hm.slots end end end @@ -593,65 +593,65 @@ let hash_map_new_with_capacity_fwd_lem (t : Type0) (capacity : usize) (*** new *) /// [new] doesn't fail and returns an empty hash map -val hash_map_new_fwd_lem_aux (t : Type0) : +val hashMap_new_lem_aux (t : Type0) : Lemma (ensures ( - match hash_map_new_fwd t with + match hashMap_new t with | Fail _ -> False | Return hm -> // The hash map invariant is satisfied - hash_map_t_inv hm /\ + hashMap_t_inv hm /\ // The hash map has 0 values - hash_map_t_len_s hm = 0 /\ + hashMap_t_len_s hm = 0 /\ // It contains no bindings - (forall k. hash_map_t_find_s hm k == None))) + (forall k. hashMap_t_find_s hm k == None))) #push-options "--fuel 1" -let hash_map_new_fwd_lem_aux t = - hash_map_new_with_capacity_fwd_lem t 32 4 5; - match hash_map_new_with_capacity_fwd t 32 4 5 with +let hashMap_new_lem_aux t = + hashMap_new_with_capacity_lem t 32 4 5; + match hashMap_new_with_capacity t 32 4 5 with | Fail _ -> () | Return hm -> () #pop-options /// The lemma we reveal in the .fsti -let hash_map_new_fwd_lem t = hash_map_new_fwd_lem_aux t +let hashMap_new_lem t = hashMap_new_lem_aux t (*** clear *) /// [clear]: the loop doesn't fail and simply clears the slots starting at index i #push-options "--fuel 1" -let rec hash_map_clear_loop_fwd_back_lem - (t : Type0) (slots : vec (list_t t)) (i : usize) : +let rec hashMap_clear_loop_lem + (t : Type0) (slots : alloc_vec_Vec (list_t t)) (i : usize) : Lemma (ensures ( - match hash_map_clear_loop_fwd_back t slots i with + match hashMap_clear_loop t slots i with | Fail _ -> False | Return slots' -> // The length is preserved length slots' == length slots /\ // The slots before i are left unchanged (forall (j:nat{j < i /\ j < length slots}). index slots' j == index slots j) /\ - // The slots after i are set to ListNil - (forall (j:nat{i <= j /\ j < length slots}). index slots' j == ListNil))) - (decreases (hash_map_clear_loop_decreases t slots i)) + // The slots after i are set to List_Nil + (forall (j:nat{i <= j /\ j < length slots}). index slots' j == List_Nil))) + (decreases (hashMap_clear_loop_decreases t slots i)) = - let i0 = vec_len (list_t t) slots in + let i0 = alloc_vec_Vec_len (list_t t) slots in let b = i < i0 in if b then - begin match vec_index_mut_back (list_t t) slots i ListNil with + begin match alloc_vec_Vec_update_usize slots i List_Nil with | Fail _ -> () | Return v -> begin match usize_add i 1 with | Fail _ -> () | Return i1 -> - hash_map_clear_loop_fwd_back_lem t v i1; - begin match hash_map_clear_loop_fwd_back t v i1 with + hashMap_clear_loop_lem t v i1; + begin match hashMap_clear_loop t v i1 with | Fail _ -> () | Return slots1 -> assert(length slots1 == length slots); - assert(forall (j:nat{i+1 <= j /\ j < length slots}). index slots1 j == ListNil); - assert(index slots1 i == ListNil) + assert(forall (j:nat{i+1 <= j /\ j < length slots}). index slots1 j == List_Nil); + assert(index slots1 i == List_Nil) end end end @@ -659,80 +659,80 @@ let rec hash_map_clear_loop_fwd_back_lem #pop-options /// [clear] doesn't fail and turns the hash map into an empty map -val hash_map_clear_fwd_back_lem_aux - (#t : Type0) (self : hash_map_t t) : +val hashMap_clear_lem_aux + (#t : Type0) (self : hashMap_t t) : Lemma - (requires (hash_map_t_base_inv self)) + (requires (hashMap_t_base_inv self)) (ensures ( - match hash_map_clear_fwd_back t self with + match hashMap_clear t self with | Fail _ -> False | Return hm -> // The hash map invariant is satisfied - hash_map_t_base_inv hm /\ + hashMap_t_base_inv hm /\ // We preserved the parameters - hash_map_t_same_params hm self /\ + hashMap_t_same_params hm self /\ // The hash map has 0 values - hash_map_t_len_s hm = 0 /\ + hashMap_t_len_s hm = 0 /\ // It contains no bindings - (forall k. hash_map_t_find_s hm k == None))) + (forall k. hashMap_t_find_s hm k == None))) // Being lazy: fuel 1 helps a lot... #push-options "--fuel 1" -let hash_map_clear_fwd_back_lem_aux #t self = - let p = self.hash_map_max_load_factor in - let i = self.hash_map_max_load in - let v = self.hash_map_slots in - hash_map_clear_loop_fwd_back_lem t v 0; - begin match hash_map_clear_loop_fwd_back t v 0 with +let hashMap_clear_lem_aux #t self = + let p = self.max_load_factor in + let i = self.max_load in + let v = self.slots in + hashMap_clear_loop_lem t v 0; + begin match hashMap_clear_loop t v 0 with | Fail _ -> () | Return slots1 -> slots_t_al_v_all_nil_is_empty_lem slots1; - let hm1 = Mkhash_map_t 0 p i slots1 in - assert(hash_map_t_base_inv hm1); - assert(hash_map_t_inv hm1) + let hm1 = MkhashMap_t 0 p i slots1 in + assert(hashMap_t_base_inv hm1); + assert(hashMap_t_inv hm1) end #pop-options -let hash_map_clear_fwd_back_lem #t self = hash_map_clear_fwd_back_lem_aux #t self +let hashMap_clear_lem #t self = hashMap_clear_lem_aux #t self (*** len *) /// [len]: we link it to a non-failing function. /// Rk.: we might want to make an analysis to not use an error monad to translate /// functions which statically can't fail. -let hash_map_len_fwd_lem #t self = () +let hashMap_len_lem #t self = () (*** insert_in_list *) (**** insert_in_list'fwd *) -/// [insert_in_list_fwd]: returns true iff the key is not in the list (functional version) -val hash_map_insert_in_list_fwd_lem +/// [insert_in_list]: returns true iff the key is not in the list (functional version) +val hashMap_insert_in_list_lem (t : Type0) (key : usize) (value : t) (ls : list_t t) : Lemma (ensures ( - match hash_map_insert_in_list_fwd t key value ls with + match hashMap_insert_in_list t key value ls with | Fail _ -> False | Return b -> b <==> (slot_t_find_s key ls == None))) - (decreases (hash_map_insert_in_list_loop_decreases t key value ls)) + (decreases (hashMap_insert_in_list_loop_decreases t key value ls)) #push-options "--fuel 1" -let rec hash_map_insert_in_list_fwd_lem t key value ls = +let rec hashMap_insert_in_list_lem t key value ls = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b then () else begin - hash_map_insert_in_list_fwd_lem t key value ls0; - match hash_map_insert_in_list_fwd t key value ls0 with + hashMap_insert_in_list_lem t key value ls0; + match hashMap_insert_in_list t key value ls0 with | Fail _ -> () | Return b0 -> () end - | ListNil -> + | List_Nil -> assert(list_t_v ls == []); assert_norm(find (same_key #t key) [] == None) end @@ -748,7 +748,7 @@ let rec hash_map_insert_in_list_fwd_lem t key value ls = /// We write a helper which "captures" what [insert_in_list] does. /// We then reason about this helper to prove the high-level properties we want /// (functional properties, preservation of invariants, etc.). -let hash_map_insert_in_list_s +let hashMap_insert_in_list_s (#t : Type0) (key : usize) (value : t) (ls : list (binding t)) : list (binding t) = // Check if there is already a binding for the key @@ -761,86 +761,86 @@ let hash_map_insert_in_list_s find_update (same_key key) ls (key,value) /// [insert_in_list]: if the key is not in the map, appends a new bindings (functional version) -val hash_map_insert_in_list_back_lem_append_s +val hashMap_insert_in_list_back_lem_append_s (t : Type0) (key : usize) (value : t) (ls : list_t t) : Lemma (requires ( slot_t_find_s key ls == None)) (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> list_t_v ls' == list_t_v ls @ [(key,value)])) - (decreases (hash_map_insert_in_list_loop_decreases t key value ls)) + (decreases (hashMap_insert_in_list_loop_decreases t key value ls)) #push-options "--fuel 1" -let rec hash_map_insert_in_list_back_lem_append_s t key value ls = +let rec hashMap_insert_in_list_back_lem_append_s t key value ls = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b then () else begin - hash_map_insert_in_list_back_lem_append_s t key value ls0; - match hash_map_insert_in_list_back t key value ls0 with + hashMap_insert_in_list_back_lem_append_s t key value ls0; + match hashMap_insert_in_list_back t key value ls0 with | Fail _ -> () | Return l -> () end - | ListNil -> () + | List_Nil -> () end #pop-options /// [insert_in_list]: if the key is in the map, we update the binding (functional version) -val hash_map_insert_in_list_back_lem_update_s +val hashMap_insert_in_list_back_lem_update_s (t : Type0) (key : usize) (value : t) (ls : list_t t) : Lemma (requires ( Some? (find (same_key key) (list_t_v ls)))) (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> list_t_v ls' == find_update (same_key key) (list_t_v ls) (key,value))) - (decreases (hash_map_insert_in_list_loop_decreases t key value ls)) + (decreases (hashMap_insert_in_list_loop_decreases t key value ls)) #push-options "--fuel 1" -let rec hash_map_insert_in_list_back_lem_update_s t key value ls = +let rec hashMap_insert_in_list_back_lem_update_s t key value ls = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b then () else begin - hash_map_insert_in_list_back_lem_update_s t key value ls0; - match hash_map_insert_in_list_back t key value ls0 with + hashMap_insert_in_list_back_lem_update_s t key value ls0; + match hashMap_insert_in_list_back t key value ls0 with | Fail _ -> () | Return l -> () end - | ListNil -> () + | List_Nil -> () end #pop-options /// Put everything together -val hash_map_insert_in_list_back_lem_s +val hashMap_insert_in_list_back_lem_s (t : Type0) (key : usize) (value : t) (ls : list_t t) : Lemma (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> - list_t_v ls' == hash_map_insert_in_list_s key value (list_t_v ls))) + list_t_v ls' == hashMap_insert_in_list_s key value (list_t_v ls))) -let hash_map_insert_in_list_back_lem_s t key value ls = +let hashMap_insert_in_list_back_lem_s t key value ls = match find (same_key key) (list_t_v ls) with - | None -> hash_map_insert_in_list_back_lem_append_s t key value ls - | Some _ -> hash_map_insert_in_list_back_lem_update_s t key value ls + | None -> hashMap_insert_in_list_back_lem_append_s t key value ls + | Some _ -> hashMap_insert_in_list_back_lem_update_s t key value ls (**** Invariants of insert_in_list_s *) /// Auxiliary lemmas -/// We work on [hash_map_insert_in_list_s], the "high-level" version of [insert_in_list'back]. +/// We work on [hashMap_insert_in_list_s], the "high-level" version of [insert_in_list'back]. /// /// Note that in F* we can't have recursive proofs inside of other proofs, contrary /// to Coq, which makes it a bit cumbersome to prove auxiliary results like the @@ -893,14 +893,14 @@ let rec slot_s_inv_not_find_append_end_inv_lem t len key value ls = #pop-options /// [insert_in_list]: if the key is not in the map, appends a new bindings -val hash_map_insert_in_list_s_lem_append +val hashMap_insert_in_list_s_lem_append (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list (binding t)) : Lemma (requires ( slot_s_inv len (hash_mod_key key len) ls /\ slot_s_find key ls == None)) (ensures ( - let ls' = hash_map_insert_in_list_s key value ls in + let ls' = hashMap_insert_in_list_s key value ls in ls' == ls @ [(key,value)] /\ // The invariant is preserved slot_s_inv len (hash_mod_key key len) ls' /\ @@ -909,20 +909,20 @@ val hash_map_insert_in_list_s_lem_append // The other bindings are preserved (forall k'. k' <> key ==> slot_s_find k' ls' == slot_s_find k' ls))) -let hash_map_insert_in_list_s_lem_append t len key value ls = +let hashMap_insert_in_list_s_lem_append t len key value ls = slot_s_inv_not_find_append_end_inv_lem t len key value ls /// [insert_in_list]: if the key is not in the map, appends a new bindings (quantifiers) /// Rk.: we don't use this lemma. /// TODO: remove? -val hash_map_insert_in_list_back_lem_append +val hashMap_insert_in_list_back_lem_append (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list_t t) : Lemma (requires ( slot_t_inv len (hash_mod_key key len) ls /\ slot_t_find_s key ls == None)) (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> list_t_v ls' == list_t_v ls @ [(key,value)] /\ @@ -933,9 +933,9 @@ val hash_map_insert_in_list_back_lem_append // The other bindings are preserved (forall k'. k' <> key ==> slot_t_find_s k' ls' == slot_t_find_s k' ls))) -let hash_map_insert_in_list_back_lem_append t len key value ls = - hash_map_insert_in_list_back_lem_s t key value ls; - hash_map_insert_in_list_s_lem_append t len key value (list_t_v ls) +let hashMap_insert_in_list_back_lem_append t len key value ls = + hashMap_insert_in_list_back_lem_s t key value ls; + hashMap_insert_in_list_s_lem_append t len key value (list_t_v ls) (** Auxiliary lemmas: update case *) @@ -1013,14 +1013,14 @@ let rec slot_s_inv_find_append_end_inv_lem t len key value ls = #pop-options /// [insert_in_list]: if the key is in the map, update the bindings -val hash_map_insert_in_list_s_lem_update +val hashMap_insert_in_list_s_lem_update (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list (binding t)) : Lemma (requires ( slot_s_inv len (hash_mod_key key len) ls /\ Some? (slot_s_find key ls))) (ensures ( - let ls' = hash_map_insert_in_list_s key value ls in + let ls' = hashMap_insert_in_list_s key value ls in ls' == find_update (same_key key) ls (key,value) /\ // The invariant is preserved slot_s_inv len (hash_mod_key key len) ls' /\ @@ -1029,20 +1029,20 @@ val hash_map_insert_in_list_s_lem_update // The other bindings are preserved (forall k'. k' <> key ==> slot_s_find k' ls' == slot_s_find k' ls))) -let hash_map_insert_in_list_s_lem_update t len key value ls = +let hashMap_insert_in_list_s_lem_update t len key value ls = slot_s_inv_find_append_end_inv_lem t len key value ls /// [insert_in_list]: if the key is in the map, update the bindings /// TODO: not used: remove? -val hash_map_insert_in_list_back_lem_update +val hashMap_insert_in_list_back_lem_update (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list_t t) : Lemma (requires ( slot_t_inv len (hash_mod_key key len) ls /\ Some? (slot_t_find_s key ls))) (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> let als = list_t_v ls in @@ -1054,20 +1054,20 @@ val hash_map_insert_in_list_back_lem_update // The other bindings are preserved (forall k'. k' <> key ==> slot_t_find_s k' ls' == slot_t_find_s k' ls))) -let hash_map_insert_in_list_back_lem_update t len key value ls = - hash_map_insert_in_list_back_lem_s t key value ls; - hash_map_insert_in_list_s_lem_update t len key value (list_t_v ls) +let hashMap_insert_in_list_back_lem_update t len key value ls = + hashMap_insert_in_list_back_lem_s t key value ls; + hashMap_insert_in_list_s_lem_update t len key value (list_t_v ls) (** Final lemmas about [insert_in_list] *) /// High-level version -val hash_map_insert_in_list_s_lem +val hashMap_insert_in_list_s_lem (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list (binding t)) : Lemma (requires ( slot_s_inv len (hash_mod_key key len) ls)) (ensures ( - let ls' = hash_map_insert_in_list_s key value ls in + let ls' = hashMap_insert_in_list_s key value ls in // The invariant is preserved slot_s_inv len (hash_mod_key key len) ls' /\ // [key] maps to [value] @@ -1079,22 +1079,22 @@ val hash_map_insert_in_list_s_lem | None -> length ls' = length ls + 1 | Some _ -> length ls' = length ls))) -let hash_map_insert_in_list_s_lem t len key value ls = +let hashMap_insert_in_list_s_lem t len key value ls = match slot_s_find key ls with | None -> assert_norm(length [(key,value)] = 1); - hash_map_insert_in_list_s_lem_append t len key value ls + hashMap_insert_in_list_s_lem_append t len key value ls | Some _ -> - hash_map_insert_in_list_s_lem_update t len key value ls + hashMap_insert_in_list_s_lem_update t len key value ls /// [insert_in_list] /// TODO: not used: remove? -val hash_map_insert_in_list_back_lem +val hashMap_insert_in_list_back_lem (t : Type0) (len : usize{len > 0}) (key : usize) (value : t) (ls : list_t t) : Lemma (requires (slot_t_inv len (hash_mod_key key len) ls)) (ensures ( - match hash_map_insert_in_list_back t key value ls with + match hashMap_insert_in_list_back t key value ls with | Fail _ -> False | Return ls' -> // The invariant is preserved @@ -1111,127 +1111,127 @@ val hash_map_insert_in_list_back_lem | Some _ -> list_t_v ls' == find_update (same_key key) (list_t_v ls) (key,value) /\ list_t_len ls' = list_t_len ls))) - (decreases (hash_map_insert_in_list_loop_decreases t key value ls)) + (decreases (hashMap_insert_in_list_loop_decreases t key value ls)) -let hash_map_insert_in_list_back_lem t len key value ls = - hash_map_insert_in_list_back_lem_s t key value ls; - hash_map_insert_in_list_s_lem t len key value (list_t_v ls) +let hashMap_insert_in_list_back_lem t len key value ls = + hashMap_insert_in_list_back_lem_s t key value ls; + hashMap_insert_in_list_s_lem t len key value (list_t_v ls) (*** insert_no_resize *) (**** Refinement proof *) /// Same strategy as for [insert_in_list]: we introduce a high-level version of /// the function, and reason about it. -/// We work on [hash_map_s] (we use a higher-level view of the hash-map, but +/// We work on [hashMap_s] (we use a higher-level view of the hash-map, but /// not too high). /// A high-level version of insert, which doesn't check if the table is saturated -let hash_map_insert_no_fail_s - (#t : Type0) (hm : hash_map_s_nes t) +let hashMap_insert_no_fail_s + (#t : Type0) (hm : hashMap_s_nes t) (key : usize) (value : t) : - hash_map_s t = + hashMap_s t = let len = length hm in let i = hash_mod_key key len in let slot = index hm i in - let slot' = hash_map_insert_in_list_s key value slot in + let slot' = hashMap_insert_in_list_s key value slot in let hm' = list_update hm i slot' in hm' -// TODO: at some point I used hash_map_s_nes and it broke proofs...x -let hash_map_insert_no_resize_s - (#t : Type0) (hm : hash_map_s_nes t) +// TODO: at some point I used hashMap_s_nes and it broke proofs...x +let hashMap_insert_no_resize_s + (#t : Type0) (hm : hashMap_s_nes t) (key : usize) (value : t) : - result (hash_map_s t) = + result (hashMap_s t) = // Check if the table is saturated (too many entries, and we need to insert one) let num_entries = length (flatten hm) in - if None? (hash_map_s_find hm key) && num_entries = usize_max then Fail Failure - else Return (hash_map_insert_no_fail_s hm key value) + if None? (hashMap_s_find hm key) && num_entries = usize_max then Fail Failure + else Return (hashMap_insert_no_fail_s hm key value) -/// Prove that [hash_map_insert_no_resize_s] is refined by -/// [hash_map_insert_no_resize'fwd_back] -val hash_map_insert_no_resize_fwd_back_lem_s - (t : Type0) (self : hash_map_t t) (key : usize) (value : t) : +/// Prove that [hashMap_insert_no_resize_s] is refined by +/// [hashMap_insert_no_resize'fwd_back] +val hashMap_insert_no_resize_lem_s + (t : Type0) (self : hashMap_t t) (key : usize) (value : t) : Lemma (requires ( - hash_map_t_base_inv self /\ - hash_map_s_len (hash_map_t_v self) = hash_map_t_len_s self)) + hashMap_t_base_inv self /\ + hashMap_s_len (hashMap_t_v self) = hashMap_t_len_s self)) (ensures ( begin - match hash_map_insert_no_resize_fwd_back t self key value, - hash_map_insert_no_resize_s (hash_map_t_v self) key value + match hashMap_insert_no_resize t self key value, + hashMap_insert_no_resize_s (hashMap_t_v self) key value with | Fail _, Fail _ -> True | Return hm, Return hm_v -> - hash_map_t_base_inv hm /\ - hash_map_t_same_params hm self /\ - hash_map_t_v hm == hm_v /\ - hash_map_s_len hm_v == hash_map_t_len_s hm + hashMap_t_base_inv hm /\ + hashMap_t_same_params hm self /\ + hashMap_t_v hm == hm_v /\ + hashMap_s_len hm_v == hashMap_t_len_s hm | _ -> False end)) -let hash_map_insert_no_resize_fwd_back_lem_s t self key value = - begin match hash_key_fwd key with +let hashMap_insert_no_resize_lem_s t self key value = + begin match hash_key key with | Fail _ -> () | Return i -> - let i0 = self.hash_map_num_entries in - let p = self.hash_map_max_load_factor in - let i1 = self.hash_map_max_load in - let v = self.hash_map_slots in - let i2 = vec_len (list_t t) v in + let i0 = self.num_entries in + let p = self.max_load_factor in + let i1 = self.max_load in + let v = self.slots in + let i2 = alloc_vec_Vec_len (list_t t) v in let len = length v in begin match usize_rem i i2 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_mut_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - // Checking that: list_t_v (index ...) == index (hash_map_t_v ...) ... - assert(list_t_v l == index (hash_map_t_v self) hash_mod); - hash_map_insert_in_list_fwd_lem t key value l; - match hash_map_insert_in_list_fwd t key value l with + // Checking that: list_t_v (index ...) == index (hashMap_t_v ...) ... + assert(list_t_v l == index (hashMap_t_v self) hash_mod); + hashMap_insert_in_list_lem t key value l; + match hashMap_insert_in_list t key value l with | Fail _ -> () | Return b -> assert(b = None? (slot_s_find key (list_t_v l))); - hash_map_insert_in_list_back_lem t len key value l; + hashMap_insert_in_list_back_lem t len key value l; if b then begin match usize_add i0 1 with | Fail _ -> () | Return i3 -> begin - match hash_map_insert_in_list_back t key value l with + match hashMap_insert_in_list_back t key value l with | Fail _ -> () | Return l0 -> - begin match vec_index_mut_back (list_t t) v hash_mod l0 with + begin match alloc_vec_Vec_update_usize v hash_mod l0 with | Fail _ -> () | Return v0 -> - let self_v = hash_map_t_v self in - let hm = Mkhash_map_t i3 p i1 v0 in - let hm_v = hash_map_t_v hm in + let self_v = hashMap_t_v self in + let hm = MkhashMap_t i3 p i1 v0 in + let hm_v = hashMap_t_v hm in assert(hm_v == list_update self_v hash_mod (list_t_v l0)); assert_norm(length [(key,value)] = 1); assert(length (list_t_v l0) = length (list_t_v l) + 1); length_flatten_update self_v hash_mod (list_t_v l0); - assert(hash_map_s_len hm_v = hash_map_t_len_s hm) + assert(hashMap_s_len hm_v = hashMap_t_len_s hm) end end end else begin - match hash_map_insert_in_list_back t key value l with + match hashMap_insert_in_list_back t key value l with | Fail _ -> () | Return l0 -> - begin match vec_index_mut_back (list_t t) v hash_mod l0 with + begin match alloc_vec_Vec_update_usize v hash_mod l0 with | Fail _ -> () | Return v0 -> - let self_v = hash_map_t_v self in - let hm = Mkhash_map_t i0 p i1 v0 in - let hm_v = hash_map_t_v hm in + let self_v = hashMap_t_v self in + let hm = MkhashMap_t i0 p i1 v0 in + let hm_v = hashMap_t_v hm in assert(hm_v == list_update self_v hash_mod (list_t_v l0)); assert(length (list_t_v l0) = length (list_t_v l)); length_flatten_update self_v hash_mod (list_t_v l0); - assert(hash_map_s_len hm_v = hash_map_t_len_s hm) + assert(hashMap_s_len hm_v = hashMap_t_len_s hm) end end end @@ -1241,108 +1241,108 @@ let hash_map_insert_no_resize_fwd_back_lem_s t self key value = (**** insert_{no_fail,no_resize}: invariants *) -let hash_map_s_updated_binding - (#t : Type0) (hm : hash_map_s_nes t) - (key : usize) (opt_value : option t) (hm' : hash_map_s_nes t) : Type0 = +let hashMap_s_updated_binding + (#t : Type0) (hm : hashMap_s_nes t) + (key : usize) (opt_value : option t) (hm' : hashMap_s_nes t) : Type0 = // [key] maps to [value] - hash_map_s_find hm' key == opt_value /\ + hashMap_s_find hm' key == opt_value /\ // The other bindings are preserved - (forall k'. k' <> key ==> hash_map_s_find hm' k' == hash_map_s_find hm k') + (forall k'. k' <> key ==> hashMap_s_find hm' k' == hashMap_s_find hm k') -let insert_post (#t : Type0) (hm : hash_map_s_nes t) - (key : usize) (value : t) (hm' : hash_map_s_nes t) : Type0 = +let insert_post (#t : Type0) (hm : hashMap_s_nes t) + (key : usize) (value : t) (hm' : hashMap_s_nes t) : Type0 = // The invariant is preserved - hash_map_s_inv hm' /\ + hashMap_s_inv hm' /\ // [key] maps to [value] and the other bindings are preserved - hash_map_s_updated_binding hm key (Some value) hm' /\ + hashMap_s_updated_binding hm key (Some value) hm' /\ // The length is incremented, iff we inserted a new key - (match hash_map_s_find hm key with - | None -> hash_map_s_len hm' = hash_map_s_len hm + 1 - | Some _ -> hash_map_s_len hm' = hash_map_s_len hm) + (match hashMap_s_find hm key with + | None -> hashMap_s_len hm' = hashMap_s_len hm + 1 + | Some _ -> hashMap_s_len hm' = hashMap_s_len hm) -val hash_map_insert_no_fail_s_lem - (#t : Type0) (hm : hash_map_s_nes t) +val hashMap_insert_no_fail_s_lem + (#t : Type0) (hm : hashMap_s_nes t) (key : usize) (value : t) : Lemma - (requires (hash_map_s_inv hm)) + (requires (hashMap_s_inv hm)) (ensures ( - let hm' = hash_map_insert_no_fail_s hm key value in + let hm' = hashMap_insert_no_fail_s hm key value in insert_post hm key value hm')) -let hash_map_insert_no_fail_s_lem #t hm key value = +let hashMap_insert_no_fail_s_lem #t hm key value = let len = length hm in let i = hash_mod_key key len in let slot = index hm i in - hash_map_insert_in_list_s_lem t len key value slot; - let slot' = hash_map_insert_in_list_s key value slot in + hashMap_insert_in_list_s_lem t len key value slot; + let slot' = hashMap_insert_in_list_s key value slot in length_flatten_update hm i slot' -val hash_map_insert_no_resize_s_lem - (#t : Type0) (hm : hash_map_s_nes t) +val hashMap_insert_no_resize_s_lem + (#t : Type0) (hm : hashMap_s_nes t) (key : usize) (value : t) : Lemma - (requires (hash_map_s_inv hm)) + (requires (hashMap_s_inv hm)) (ensures ( - match hash_map_insert_no_resize_s hm key value with + match hashMap_insert_no_resize_s hm key value with | Fail _ -> // Can fail only if we need to create a new binding in // an already saturated map - hash_map_s_len hm = usize_max /\ - None? (hash_map_s_find hm key) + hashMap_s_len hm = usize_max /\ + None? (hashMap_s_find hm key) | Return hm' -> insert_post hm key value hm')) -let hash_map_insert_no_resize_s_lem #t hm key value = +let hashMap_insert_no_resize_s_lem #t hm key value = let num_entries = length (flatten hm) in - if None? (hash_map_s_find hm key) && num_entries = usize_max then () - else hash_map_insert_no_fail_s_lem hm key value + if None? (hashMap_s_find hm key) && num_entries = usize_max then () + else hashMap_insert_no_fail_s_lem hm key value (**** find after insert *) /// Lemmas about what happens if we call [find] after an insertion -val hash_map_insert_no_resize_s_get_same_lem - (#t : Type0) (hm : hash_map_s t) +val hashMap_insert_no_resize_s_get_same_lem + (#t : Type0) (hm : hashMap_s t) (key : usize) (value : t) : - Lemma (requires (hash_map_s_inv hm)) + Lemma (requires (hashMap_s_inv hm)) (ensures ( - match hash_map_insert_no_resize_s hm key value with + match hashMap_insert_no_resize_s hm key value with | Fail _ -> True | Return hm' -> - hash_map_s_find hm' key == Some value)) + hashMap_s_find hm' key == Some value)) -let hash_map_insert_no_resize_s_get_same_lem #t hm key value = +let hashMap_insert_no_resize_s_get_same_lem #t hm key value = let num_entries = length (flatten hm) in - if None? (hash_map_s_find hm key) && num_entries = usize_max then () + if None? (hashMap_s_find hm key) && num_entries = usize_max then () else begin - let hm' = Return?.v (hash_map_insert_no_resize_s hm key value) in + let hm' = Return?.v (hashMap_insert_no_resize_s hm key value) in let len = length hm in let i = hash_mod_key key len in let slot = index hm i in - hash_map_insert_in_list_s_lem t len key value slot + hashMap_insert_in_list_s_lem t len key value slot end -val hash_map_insert_no_resize_s_get_diff_lem - (#t : Type0) (hm : hash_map_s t) +val hashMap_insert_no_resize_s_get_diff_lem + (#t : Type0) (hm : hashMap_s t) (key : usize) (value : t) (key' : usize{key' <> key}) : - Lemma (requires (hash_map_s_inv hm)) + Lemma (requires (hashMap_s_inv hm)) (ensures ( - match hash_map_insert_no_resize_s hm key value with + match hashMap_insert_no_resize_s hm key value with | Fail _ -> True | Return hm' -> - hash_map_s_find hm' key' == hash_map_s_find hm key')) + hashMap_s_find hm' key' == hashMap_s_find hm key')) -let hash_map_insert_no_resize_s_get_diff_lem #t hm key value key' = +let hashMap_insert_no_resize_s_get_diff_lem #t hm key value key' = let num_entries = length (flatten hm) in - if None? (hash_map_s_find hm key) && num_entries = usize_max then () + if None? (hashMap_s_find hm key) && num_entries = usize_max then () else begin - let hm' = Return?.v (hash_map_insert_no_resize_s hm key value) in + let hm' = Return?.v (hashMap_insert_no_resize_s hm key value) in let len = length hm in let i = hash_mod_key key len in let slot = index hm i in - hash_map_insert_in_list_s_lem t len key value slot; + hashMap_insert_in_list_s_lem t len key value slot; let i' = hash_mod_key key' len in if i <> i' then () else @@ -1354,116 +1354,116 @@ let hash_map_insert_no_resize_s_get_diff_lem #t hm key value key' = (*** move_elements_from_list *) -/// Having a great time here: if we use `result (hash_map_s_res t)` as the -/// return type for [hash_map_move_elements_from_list_s] instead of having this -/// awkward match, the proof of [hash_map_move_elements_fwd_back_lem_refin] fails. +/// Having a great time here: if we use `result (hashMap_s_res t)` as the +/// return type for [hashMap_move_elements_from_list_s] instead of having this +/// awkward match, the proof of [hashMap_move_elements_lem_refin] fails. /// I guess it comes from F*'s poor subtyping. -/// Followingly, I'm not taking any chance and using [result_hash_map_s] +/// Followingly, I'm not taking any chance and using [result_hashMap_s] /// everywhere. -type result_hash_map_s_nes (t : Type0) : Type0 = - res:result (hash_map_s t) { +type result_hashMap_s_nes (t : Type0) : Type0 = + res:result (hashMap_s t) { match res with | Fail _ -> True | Return hm -> is_pos_usize (length hm) } -let rec hash_map_move_elements_from_list_s - (#t : Type0) (hm : hash_map_s_nes t) +let rec hashMap_move_elements_from_list_s + (#t : Type0) (hm : hashMap_s_nes t) (ls : slot_s t) : - // Do *NOT* use `result (hash_map_s t)` - Tot (result_hash_map_s_nes t) + // Do *NOT* use `result (hashMap_s t)` + Tot (result_hashMap_s_nes t) (decreases ls) = match ls with | [] -> Return hm | (key, value) :: ls' -> - match hash_map_insert_no_resize_s hm key value with + match hashMap_insert_no_resize_s hm key value with | Fail e -> Fail e | Return hm' -> - hash_map_move_elements_from_list_s hm' ls' + hashMap_move_elements_from_list_s hm' ls' /// Refinement lemma -val hash_map_move_elements_from_list_fwd_back_lem - (t : Type0) (ntable : hash_map_t_nes t) (ls : list_t t) : - Lemma (requires (hash_map_t_base_inv ntable)) +val hashMap_move_elements_from_list_lem + (t : Type0) (ntable : hashMap_t_nes t) (ls : list_t t) : + Lemma (requires (hashMap_t_base_inv ntable)) (ensures ( - match hash_map_move_elements_from_list_fwd_back t ntable ls, - hash_map_move_elements_from_list_s (hash_map_t_v ntable) (slot_t_v ls) + match hashMap_move_elements_from_list t ntable ls, + hashMap_move_elements_from_list_s (hashMap_t_v ntable) (slot_t_v ls) with | Fail _, Fail _ -> True | Return hm', Return hm_v -> - hash_map_t_base_inv hm' /\ - hash_map_t_v hm' == hm_v /\ - hash_map_t_same_params hm' ntable + hashMap_t_base_inv hm' /\ + hashMap_t_v hm' == hm_v /\ + hashMap_t_same_params hm' ntable | _ -> False)) - (decreases (hash_map_move_elements_from_list_loop_decreases t ntable ls)) + (decreases (hashMap_move_elements_from_list_loop_decreases t ntable ls)) #push-options "--fuel 1" -let rec hash_map_move_elements_from_list_fwd_back_lem t ntable ls = +let rec hashMap_move_elements_from_list_lem t ntable ls = begin match ls with - | ListCons k v tl -> + | List_Cons k v tl -> assert(list_t_v ls == (k, v) :: list_t_v tl); let ls_v = list_t_v ls in let (_,_) :: tl_v = ls_v in - hash_map_insert_no_resize_fwd_back_lem_s t ntable k v; - begin match hash_map_insert_no_resize_fwd_back t ntable k v with + hashMap_insert_no_resize_lem_s t ntable k v; + begin match hashMap_insert_no_resize t ntable k v with | Fail _ -> () | Return h -> - let h_v = Return?.v (hash_map_insert_no_resize_s (hash_map_t_v ntable) k v) in - assert(hash_map_t_v h == h_v); - hash_map_move_elements_from_list_fwd_back_lem t h tl; - begin match hash_map_move_elements_from_list_fwd_back t h tl with + let h_v = Return?.v (hashMap_insert_no_resize_s (hashMap_t_v ntable) k v) in + assert(hashMap_t_v h == h_v); + hashMap_move_elements_from_list_lem t h tl; + begin match hashMap_move_elements_from_list t h tl with | Fail _ -> () | Return h0 -> () end end - | ListNil -> () + | List_Nil -> () end #pop-options (*** move_elements *) (**** move_elements: refinement 0 *) -/// The proof for [hash_map_move_elements_fwd_back_lem_refin] broke so many times +/// The proof for [hashMap_move_elements_lem_refin] broke so many times /// (while it is supposed to be super simple!) that we decided to add one refinement /// level, to really do things step by step... /// Doing this refinement layer made me notice that maybe the problem came from -/// the fact that at some point we have to prove `list_t_v ListNil == []`: I +/// the fact that at some point we have to prove `list_t_v List_Nil == []`: I /// added the corresponding assert to help Z3 and everything became stable. /// I finally didn't use this "simple" refinement lemma, but I still keep it here -/// because it allows for easy comparisons with [hash_map_move_elements_s]. +/// because it allows for easy comparisons with [hashMap_move_elements_s]. -/// [hash_map_move_elements_fwd] refines this function, which is actually almost +/// [hashMap_move_elements] refines this function, which is actually almost /// the same (just a little bit shorter and cleaner, and has a pre). /// /// The way I wrote the high-level model is the following: -/// - I copy-pasted the definition of [hash_map_move_elements_fwd], wrote the -/// signature which links this new definition to [hash_map_move_elements_fwd] and +/// - I copy-pasted the definition of [hashMap_move_elements], wrote the +/// signature which links this new definition to [hashMap_move_elements] and /// checked that the proof passed /// - I gradually simplified it, while making sure the proof still passes #push-options "--fuel 1" -let rec hash_map_move_elements_s_simpl - (t : Type0) (ntable : hash_map_t t) - (slots : vec (list_t t)) +let rec hashMap_move_elements_s_simpl + (t : Type0) (ntable : hashMap_t t) + (slots : alloc_vec_Vec (list_t t)) (i : usize{i <= length slots /\ length slots <= usize_max}) : - Pure (result ((hash_map_t t) & (vec (list_t t)))) + Pure (result ((hashMap_t t) & (alloc_vec_Vec (list_t t)))) (requires (True)) (ensures (fun res -> - match res, hash_map_move_elements_fwd_back t ntable slots i with + match res, hashMap_move_elements t ntable slots i with | Fail _, Fail _ -> True | Return (ntable1, slots1), Return (ntable2, slots2) -> ntable1 == ntable2 /\ slots1 == slots2 | _ -> False)) - (decreases (hash_map_move_elements_loop_decreases t ntable slots i)) + (decreases (hashMap_move_elements_loop_decreases t ntable slots i)) = if i < length slots then let slot = index slots i in - begin match hash_map_move_elements_from_list_fwd_back t ntable slot with + begin match hashMap_move_elements_from_list t ntable slot with | Fail e -> Fail e | Return hm' -> - let slots' = list_update slots i ListNil in - hash_map_move_elements_s_simpl t hm' slots' (i+1) + let slots' = list_update slots i List_Nil in + hashMap_move_elements_s_simpl t hm' slots' (i+1) end else Return (ntable, slots) #pop-options @@ -1476,71 +1476,71 @@ let rec hash_map_move_elements_s_simpl // Note that we ignore the returned slots (we thus don't return a pair: // only the new hash map in which we moved the elements from the slots): // this returned value is not used. -let rec hash_map_move_elements_s - (#t : Type0) (hm : hash_map_s_nes t) +let rec hashMap_move_elements_s + (#t : Type0) (hm : hashMap_s_nes t) (slots : slots_s t) (i : usize{i <= length slots /\ length slots <= usize_max}) : - Tot (result_hash_map_s_nes t) + Tot (result_hashMap_s_nes t) (decreases (length slots - i)) = let len = length slots in if i < len then begin let slot = index slots i in - match hash_map_move_elements_from_list_s hm slot with + match hashMap_move_elements_from_list_s hm slot with | Fail e -> Fail e | Return hm' -> let slots' = list_update slots i [] in - hash_map_move_elements_s hm' slots' (i+1) + hashMap_move_elements_s hm' slots' (i+1) end else Return hm -val hash_map_move_elements_fwd_back_lem_refin - (t : Type0) (ntable : hash_map_t t) - (slots : vec (list_t t)) (i : usize{i <= length slots}) : +val hashMap_move_elements_lem_refin + (t : Type0) (ntable : hashMap_t t) + (slots : alloc_vec_Vec (list_t t)) (i : usize{i <= length slots}) : Lemma (requires ( - hash_map_t_base_inv ntable)) + hashMap_t_base_inv ntable)) (ensures ( - match hash_map_move_elements_fwd_back t ntable slots i, - hash_map_move_elements_s (hash_map_t_v ntable) (slots_t_v slots) i + match hashMap_move_elements t ntable slots i, + hashMap_move_elements_s (hashMap_t_v ntable) (slots_t_v slots) i with | Fail _, Fail _ -> True // We will prove later that this is not possible | Return (ntable', _), Return ntable'_v -> - hash_map_t_base_inv ntable' /\ - hash_map_t_v ntable' == ntable'_v /\ - hash_map_t_same_params ntable' ntable + hashMap_t_base_inv ntable' /\ + hashMap_t_v ntable' == ntable'_v /\ + hashMap_t_same_params ntable' ntable | _ -> False)) (decreases (length slots - i)) #restart-solver #push-options "--fuel 1" -let rec hash_map_move_elements_fwd_back_lem_refin t ntable slots i = - assert(hash_map_t_base_inv ntable); - let i0 = vec_len (list_t t) slots in +let rec hashMap_move_elements_lem_refin t ntable slots i = + assert(hashMap_t_base_inv ntable); + let i0 = alloc_vec_Vec_len (list_t t) slots in let b = i < i0 in if b then - begin match vec_index_mut_fwd (list_t t) slots i with + begin match alloc_vec_Vec_index_usize slots i with | Fail _ -> () | Return l -> - let l0 = mem_replace_fwd (list_t t) l ListNil in + let l0 = core_mem_replace (list_t t) l List_Nil in assert(l0 == l); - hash_map_move_elements_from_list_fwd_back_lem t ntable l0; - begin match hash_map_move_elements_from_list_fwd_back t ntable l0 with + hashMap_move_elements_from_list_lem t ntable l0; + begin match hashMap_move_elements_from_list t ntable l0 with | Fail _ -> () | Return h -> - let l1 = mem_replace_back (list_t t) l ListNil in - assert(l1 == ListNil); - assert(slot_t_v #t ListNil == []); // THIS IS IMPORTANT - begin match vec_index_mut_back (list_t t) slots i l1 with + let l1 = core_mem_replace_back (list_t t) l List_Nil in + assert(l1 == List_Nil); + assert(slot_t_v #t List_Nil == []); // THIS IS IMPORTANT + begin match alloc_vec_Vec_update_usize slots i l1 with | Fail _ -> () | Return v -> begin match usize_add i 1 with | Fail _ -> () | Return i1 -> - hash_map_move_elements_fwd_back_lem_refin t h v i1; - begin match hash_map_move_elements_fwd_back t h v i1 with + hashMap_move_elements_lem_refin t h v i1; + begin match hashMap_move_elements t h v i1 with | Fail _ -> - assert(Fail? (hash_map_move_elements_fwd_back t ntable slots i)); + assert(Fail? (hashMap_move_elements t ntable slots i)); () | Return (ntable', v0) -> () end @@ -1560,19 +1560,19 @@ let rec hash_map_move_elements_fwd_back_lem_refin t ntable slots i = /// [ntable] is the hash map to which we move the elements /// [slots] is the current hash map, from which we remove the elements, and seen /// as a "flat" associative list (and not a list of lists) -/// This is actually exactly [hash_map_move_elements_from_list_s]... -let rec hash_map_move_elements_s_flat - (#t : Type0) (ntable : hash_map_s_nes t) +/// This is actually exactly [hashMap_move_elements_from_list_s]... +let rec hashMap_move_elements_s_flat + (#t : Type0) (ntable : hashMap_s_nes t) (slots : assoc_list t) : - Tot (result_hash_map_s_nes t) + Tot (result_hashMap_s_nes t) (decreases slots) = match slots with | [] -> Return ntable | (k,v) :: slots' -> - match hash_map_insert_no_resize_s ntable k v with + match hashMap_insert_no_resize_s ntable k v with | Fail e -> Fail e | Return ntable' -> - hash_map_move_elements_s_flat ntable' slots' + hashMap_move_elements_s_flat ntable' slots' /// The refinment lemmas /// First, auxiliary helpers. @@ -1656,42 +1656,42 @@ let rec flatten_nil_prefix_as_flatten_i #a l i = /// The proof is trivial, the functions are the same. /// Just keeping two definitions to allow changes... -val hash_map_move_elements_from_list_s_as_flat_lem - (#t : Type0) (hm : hash_map_s_nes t) +val hashMap_move_elements_from_list_s_as_flat_lem + (#t : Type0) (hm : hashMap_s_nes t) (ls : slot_s t) : Lemma (ensures ( - hash_map_move_elements_from_list_s hm ls == - hash_map_move_elements_s_flat hm ls)) + hashMap_move_elements_from_list_s hm ls == + hashMap_move_elements_s_flat hm ls)) (decreases ls) #push-options "--fuel 1" -let rec hash_map_move_elements_from_list_s_as_flat_lem #t hm ls = +let rec hashMap_move_elements_from_list_s_as_flat_lem #t hm ls = match ls with | [] -> () | (key, value) :: ls' -> - match hash_map_insert_no_resize_s hm key value with + match hashMap_insert_no_resize_s hm key value with | Fail _ -> () | Return hm' -> - hash_map_move_elements_from_list_s_as_flat_lem hm' ls' + hashMap_move_elements_from_list_s_as_flat_lem hm' ls' #pop-options -/// Composition of two calls to [hash_map_move_elements_s_flat] -let hash_map_move_elements_s_flat_comp - (#t : Type0) (hm : hash_map_s_nes t) (slot0 slot1 : slot_s t) : - Tot (result_hash_map_s_nes t) = - match hash_map_move_elements_s_flat hm slot0 with +/// Composition of two calls to [hashMap_move_elements_s_flat] +let hashMap_move_elements_s_flat_comp + (#t : Type0) (hm : hashMap_s_nes t) (slot0 slot1 : slot_s t) : + Tot (result_hashMap_s_nes t) = + match hashMap_move_elements_s_flat hm slot0 with | Fail e -> Fail e - | Return hm1 -> hash_map_move_elements_s_flat hm1 slot1 + | Return hm1 -> hashMap_move_elements_s_flat hm1 slot1 /// High-level desc: /// move_elements (move_elements hm slot0) slo1 == move_elements hm (slot0 @ slot1) -val hash_map_move_elements_s_flat_append_lem - (#t : Type0) (hm : hash_map_s_nes t) (slot0 slot1 : slot_s t) : +val hashMap_move_elements_s_flat_append_lem + (#t : Type0) (hm : hashMap_s_nes t) (slot0 slot1 : slot_s t) : Lemma (ensures ( - match hash_map_move_elements_s_flat_comp hm slot0 slot1, - hash_map_move_elements_s_flat hm (slot0 @ slot1) + match hashMap_move_elements_s_flat_comp hm slot0 slot1, + hashMap_move_elements_s_flat hm (slot0 @ slot1) with | Fail _, Fail _ -> True | Return hm1, Return hm2 -> hm1 == hm2 @@ -1699,14 +1699,14 @@ val hash_map_move_elements_s_flat_append_lem (decreases (slot0)) #push-options "--fuel 1" -let rec hash_map_move_elements_s_flat_append_lem #t hm slot0 slot1 = +let rec hashMap_move_elements_s_flat_append_lem #t hm slot0 slot1 = match slot0 with | [] -> () | (k,v) :: slot0' -> - match hash_map_insert_no_resize_s hm k v with + match hashMap_insert_no_resize_s hm k v with | Fail _ -> () | Return hm' -> - hash_map_move_elements_s_flat_append_lem hm' slot0' slot1 + hashMap_move_elements_s_flat_append_lem hm' slot0' slot1 #pop-options val flatten_i_same_suffix (#a : Type) (l0 l1 : list (list a)) (i : nat) : @@ -1726,16 +1726,16 @@ let rec flatten_i_same_suffix #a l0 l1 i = #pop-options /// Refinement lemma: -/// [hash_map_move_elements_s] refines [hash_map_move_elements_s_flat] +/// [hashMap_move_elements_s] refines [hashMap_move_elements_s_flat] /// (actually the functions are equal on all inputs). -val hash_map_move_elements_s_lem_refin_flat - (#t : Type0) (hm : hash_map_s_nes t) +val hashMap_move_elements_s_lem_refin_flat + (#t : Type0) (hm : hashMap_s_nes t) (slots : slots_s t) (i : nat{i <= length slots /\ length slots <= usize_max}) : Lemma (ensures ( - match hash_map_move_elements_s hm slots i, - hash_map_move_elements_s_flat hm (flatten_i slots i) + match hashMap_move_elements_s hm slots i, + hashMap_move_elements_s_flat hm (flatten_i slots i) with | Fail _, Fail _ -> True | Return hm, Return hm' -> hm == hm' @@ -1743,22 +1743,22 @@ val hash_map_move_elements_s_lem_refin_flat (decreases (length slots - i)) #push-options "--fuel 1" -let rec hash_map_move_elements_s_lem_refin_flat #t hm slots i = +let rec hashMap_move_elements_s_lem_refin_flat #t hm slots i = let len = length slots in if i < len then begin let slot = index slots i in - hash_map_move_elements_from_list_s_as_flat_lem hm slot; - match hash_map_move_elements_from_list_s hm slot with + hashMap_move_elements_from_list_s_as_flat_lem hm slot; + match hashMap_move_elements_from_list_s hm slot with | Fail _ -> assert(flatten_i slots i == slot @ flatten_i slots (i+1)); - hash_map_move_elements_s_flat_append_lem hm slot (flatten_i slots (i+1)); - assert(Fail? (hash_map_move_elements_s_flat hm (flatten_i slots i))) + hashMap_move_elements_s_flat_append_lem hm slot (flatten_i slots (i+1)); + assert(Fail? (hashMap_move_elements_s_flat hm (flatten_i slots i))) | Return hm' -> let slots' = list_update slots i [] in flatten_i_same_suffix slots slots' (i+1); - hash_map_move_elements_s_lem_refin_flat hm' slots' (i+1); - hash_map_move_elements_s_flat_append_lem hm slot (flatten_i slots' (i+1)); + hashMap_move_elements_s_lem_refin_flat hm' slots' (i+1); + hashMap_move_elements_s_flat_append_lem hm slot (flatten_i slots' (i+1)); () end else () @@ -1769,21 +1769,21 @@ let assoc_list_inv (#t : Type0) (al : assoc_list t) : Type0 = pairwise_rel binding_neq al let disjoint_hm_al_on_key - (#t : Type0) (hm : hash_map_s_nes t) (al : assoc_list t) (k : key) : Type0 = - match hash_map_s_find hm k, assoc_list_find k al with + (#t : Type0) (hm : hashMap_s_nes t) (al : assoc_list t) (k : key) : Type0 = + match hashMap_s_find hm k, assoc_list_find k al with | Some _, None | None, Some _ | None, None -> True | Some _, Some _ -> False /// Playing a dangerous game here: using forall quantifiers -let disjoint_hm_al (#t : Type0) (hm : hash_map_s_nes t) (al : assoc_list t) : Type0 = +let disjoint_hm_al (#t : Type0) (hm : hashMap_s_nes t) (al : assoc_list t) : Type0 = forall (k:key). disjoint_hm_al_on_key hm al k let find_in_union_hm_al - (#t : Type0) (hm : hash_map_s_nes t) (al : assoc_list t) (k : key) : + (#t : Type0) (hm : hashMap_s_nes t) (al : assoc_list t) (k : key) : option t = - match hash_map_s_find hm k with + match hashMap_s_find hm k with | Some b -> Some b | None -> assoc_list_find k al @@ -1799,58 +1799,58 @@ let rec for_all_binding_neq_find_lem #t k v al = | b :: al' -> for_all_binding_neq_find_lem k v al' #pop-options -val hash_map_move_elements_s_flat_lem - (#t : Type0) (hm : hash_map_s_nes t) (al : assoc_list t) : +val hashMap_move_elements_s_flat_lem + (#t : Type0) (hm : hashMap_s_nes t) (al : assoc_list t) : Lemma (requires ( // Invariants - hash_map_s_inv hm /\ + hashMap_s_inv hm /\ assoc_list_inv al /\ // The two are disjoint disjoint_hm_al hm al /\ // We can add all the elements to the hashmap - hash_map_s_len hm + length al <= usize_max)) + hashMap_s_len hm + length al <= usize_max)) (ensures ( - match hash_map_move_elements_s_flat hm al with + match hashMap_move_elements_s_flat hm al with | Fail _ -> False // We can't fail | Return hm' -> // The invariant is preserved - hash_map_s_inv hm' /\ + hashMap_s_inv hm' /\ // The new hash map is the union of the two maps - (forall (k:key). hash_map_s_find hm' k == find_in_union_hm_al hm al k) /\ - hash_map_s_len hm' = hash_map_s_len hm + length al)) + (forall (k:key). hashMap_s_find hm' k == find_in_union_hm_al hm al k) /\ + hashMap_s_len hm' = hashMap_s_len hm + length al)) (decreases al) #restart-solver #push-options "--z3rlimit 200 --fuel 1" -let rec hash_map_move_elements_s_flat_lem #t hm al = +let rec hashMap_move_elements_s_flat_lem #t hm al = match al with | [] -> () | (k,v) :: al' -> - hash_map_insert_no_resize_s_lem hm k v; - match hash_map_insert_no_resize_s hm k v with + hashMap_insert_no_resize_s_lem hm k v; + match hashMap_insert_no_resize_s hm k v with | Fail _ -> () | Return hm' -> - assert(hash_map_s_inv hm'); + assert(hashMap_s_inv hm'); assert(assoc_list_inv al'); let disjoint_lem (k' : key) : Lemma (disjoint_hm_al_on_key hm' al' k') [SMTPat (disjoint_hm_al_on_key hm' al' k')] = if k' = k then begin - assert(hash_map_s_find hm' k' == Some v); + assert(hashMap_s_find hm' k' == Some v); for_all_binding_neq_find_lem k v al'; assert(assoc_list_find k' al' == None) end else begin - assert(hash_map_s_find hm' k' == hash_map_s_find hm k'); + assert(hashMap_s_find hm' k' == hashMap_s_find hm k'); assert(assoc_list_find k' al' == assoc_list_find k' al) end in assert(disjoint_hm_al hm' al'); - assert(hash_map_s_len hm' + length al' <= usize_max); - hash_map_move_elements_s_flat_lem hm' al' + assert(hashMap_s_len hm' + length al' <= usize_max); + hashMap_move_elements_s_flat_lem hm' al' #pop-options /// We need to prove that the invariants on the "low-level" representations of @@ -1866,18 +1866,18 @@ let slots_t_inv_implies_slots_s_inv #t slots = // Problem is: I can never really predict for sure with F*... () -val hash_map_t_base_inv_implies_hash_map_s_inv - (#t : Type0) (hm : hash_map_t t) : - Lemma (requires (hash_map_t_base_inv hm)) - (ensures (hash_map_s_inv (hash_map_t_v hm))) +val hashMap_t_base_inv_implies_hashMap_s_inv + (#t : Type0) (hm : hashMap_t t) : + Lemma (requires (hashMap_t_base_inv hm)) + (ensures (hashMap_s_inv (hashMap_t_v hm))) -let hash_map_t_base_inv_implies_hash_map_s_inv #t hm = () // same as previous +let hashMap_t_base_inv_implies_hashMap_s_inv #t hm = () // same as previous /// Introducing a "partial" version of the hash map invariant, which operates on /// a suffix of the hash map. -let partial_hash_map_s_inv +let partial_hashMap_s_inv (#t : Type0) (len : usize{len > 0}) (offset : usize) - (hm : hash_map_s t{offset + length hm <= usize_max}) : Type0 = + (hm : hashMap_s t{offset + length hm <= usize_max}) : Type0 = forall(i:nat{i < length hm}). {:pattern index hm i} slot_s_inv len (offset + i) (index hm i) /// Auxiliary lemma. @@ -1887,13 +1887,13 @@ val binding_in_previous_slot_implies_neq (#t : Type0) (len : usize{len > 0}) (i : usize) (b : binding t) (offset : usize{i < offset}) - (slots : hash_map_s t{offset + length slots <= usize_max}) : + (slots : hashMap_s t{offset + length slots <= usize_max}) : Lemma (requires ( // The binding comes from a slot not in [slots] hash_mod_key (fst b) len = i /\ // The slots are the well-formed suffix of a hash map - partial_hash_map_s_inv len offset slots)) + partial_hashMap_s_inv len offset slots)) (ensures ( for_all (binding_neq b) (flatten slots))) (decreases slots) @@ -1924,17 +1924,17 @@ let rec binding_in_previous_slot_implies_neq #t len i b offset slots = for_all_append (binding_neq b) s (flatten slots') #pop-options -val partial_hash_map_s_inv_implies_assoc_list_lem +val partial_hashMap_s_inv_implies_assoc_list_lem (#t : Type0) (len : usize{len > 0}) (offset : usize) - (hm : hash_map_s t{offset + length hm <= usize_max}) : + (hm : hashMap_s t{offset + length hm <= usize_max}) : Lemma (requires ( - partial_hash_map_s_inv len offset hm)) + partial_hashMap_s_inv len offset hm)) (ensures (assoc_list_inv (flatten hm))) (decreases (length hm + length (flatten hm))) #push-options "--fuel 1" -let rec partial_hash_map_s_inv_implies_assoc_list_lem #t len offset hm = +let rec partial_hashMap_s_inv_implies_assoc_list_lem #t len offset hm = match hm with | [] -> () | slot :: hm' -> @@ -1943,8 +1943,8 @@ let rec partial_hash_map_s_inv_implies_assoc_list_lem #t len offset hm = match slot with | [] -> assert(flatten hm == flatten hm'); - assert(partial_hash_map_s_inv len (offset+1) hm'); // Triggers instantiations - partial_hash_map_s_inv_implies_assoc_list_lem len (offset+1) hm' + assert(partial_hashMap_s_inv len (offset+1) hm'); // Triggers instantiations + partial_hashMap_s_inv_implies_assoc_list_lem len (offset+1) hm' | x :: slot' -> assert(flatten (slot' :: hm') == slot' @ flatten hm'); let hm'' = slot' :: hm' in @@ -1953,45 +1953,45 @@ let rec partial_hash_map_s_inv_implies_assoc_list_lem #t len offset hm = assert(index hm 0 == slot); // Triggers instantiations assert(slot_s_inv len offset slot); assert(slot_s_inv len offset slot'); - assert(partial_hash_map_s_inv len offset hm''); - partial_hash_map_s_inv_implies_assoc_list_lem len offset (slot' :: hm'); + assert(partial_hashMap_s_inv len offset hm''); + partial_hashMap_s_inv_implies_assoc_list_lem len offset (slot' :: hm'); // Proving that the key in `x` is different from all the other keys in // the flattened map assert(for_all (binding_neq x) slot'); for_all_append (binding_neq x) slot' (flatten hm'); - assert(partial_hash_map_s_inv len (offset+1) hm'); + assert(partial_hashMap_s_inv len (offset+1) hm'); binding_in_previous_slot_implies_neq #t len offset x (offset+1) hm'; assert(for_all (binding_neq x) (flatten hm')); assert(for_all (binding_neq x) (flatten (slot' :: hm'))) #pop-options -val hash_map_s_inv_implies_assoc_list_lem - (#t : Type0) (hm : hash_map_s t) : - Lemma (requires (hash_map_s_inv hm)) +val hashMap_s_inv_implies_assoc_list_lem + (#t : Type0) (hm : hashMap_s t) : + Lemma (requires (hashMap_s_inv hm)) (ensures (assoc_list_inv (flatten hm))) -let hash_map_s_inv_implies_assoc_list_lem #t hm = - partial_hash_map_s_inv_implies_assoc_list_lem (length hm) 0 hm +let hashMap_s_inv_implies_assoc_list_lem #t hm = + partial_hashMap_s_inv_implies_assoc_list_lem (length hm) 0 hm -val hash_map_t_base_inv_implies_assoc_list_lem - (#t : Type0) (hm : hash_map_t t): - Lemma (requires (hash_map_t_base_inv hm)) - (ensures (assoc_list_inv (hash_map_t_al_v hm))) +val hashMap_t_base_inv_implies_assoc_list_lem + (#t : Type0) (hm : hashMap_t t): + Lemma (requires (hashMap_t_base_inv hm)) + (ensures (assoc_list_inv (hashMap_t_al_v hm))) -let hash_map_t_base_inv_implies_assoc_list_lem #t hm = - hash_map_s_inv_implies_assoc_list_lem (hash_map_t_v hm) +let hashMap_t_base_inv_implies_assoc_list_lem #t hm = + hashMap_s_inv_implies_assoc_list_lem (hashMap_t_v hm) /// For some reason, we can't write the below [forall] directly in the [ensures] /// clause of the next lemma: it makes Z3 fails even with a huge rlimit. /// I have no idea what's going on. -let hash_map_is_assoc_list - (#t : Type0) (ntable : hash_map_t t{length ntable.hash_map_slots > 0}) +let hashMap_is_assoc_list + (#t : Type0) (ntable : hashMap_t t{length ntable.slots > 0}) (al : assoc_list t) : Type0 = - (forall (k:key). hash_map_t_find_s ntable k == assoc_list_find k al) + (forall (k:key). hashMap_t_find_s ntable k == assoc_list_find k al) -let partial_hash_map_s_find +let partial_hashMap_s_find (#t : Type0) (len : usize{len > 0}) (offset : usize) - (hm : hash_map_s_nes t{offset + length hm = len}) + (hm : hashMap_s_nes t{offset + length hm = len}) (k : key{hash_mod_key k len >= offset}) : option t = let i = hash_mod_key k len in let slot = index hm (i - offset) in @@ -2021,13 +2021,13 @@ val key_in_previous_slot_implies_not_found (#t : Type0) (len : usize{len > 0}) (k : key) (offset : usize) - (slots : hash_map_s t{offset + length slots = len}) : + (slots : hashMap_s t{offset + length slots = len}) : Lemma (requires ( // The binding comes from a slot not in [slots] hash_mod_key k len < offset /\ // The slots are the well-formed suffix of a hash map - partial_hash_map_s_inv len offset slots)) + partial_hashMap_s_inv len offset slots)) (ensures ( assoc_list_find k (flatten slots) == None)) (decreases slots) @@ -2045,19 +2045,19 @@ let rec key_in_previous_slot_implies_not_found #t len k offset slots = key_in_previous_slot_implies_not_found len k (offset+1) slots' #pop-options -val partial_hash_map_s_is_assoc_list_lem +val partial_hashMap_s_is_assoc_list_lem (#t : Type0) (len : usize{len > 0}) (offset : usize) - (hm : hash_map_s_nes t{offset + length hm = len}) + (hm : hashMap_s_nes t{offset + length hm = len}) (k : key{hash_mod_key k len >= offset}) : Lemma (requires ( - partial_hash_map_s_inv len offset hm)) + partial_hashMap_s_inv len offset hm)) (ensures ( - partial_hash_map_s_find len offset hm k == assoc_list_find k (flatten hm))) + partial_hashMap_s_find len offset hm k == assoc_list_find k (flatten hm))) (decreases hm) #push-options "--fuel 1" -let rec partial_hash_map_s_is_assoc_list_lem #t len offset hm k = +let rec partial_hashMap_s_is_assoc_list_lem #t len offset hm k = match hm with | [] -> () | slot :: hm' -> @@ -2066,7 +2066,7 @@ let rec partial_hash_map_s_is_assoc_list_lem #t len offset hm k = if i = 0 then begin // We must look in the current slot - assert(partial_hash_map_s_find len offset hm k == slot_s_find k slot); + assert(partial_hashMap_s_find len offset hm k == slot_s_find k slot); find_append (same_key k) slot (flatten hm'); assert(forall (i:nat{i < length hm'}). index hm' i == index hm (i+1)); // Triggers instantiations key_in_previous_slot_implies_not_found #t len k (offset+1) hm'; @@ -2085,64 +2085,64 @@ let rec partial_hash_map_s_is_assoc_list_lem #t len offset hm k = else begin // We must ignore the current slot - assert(partial_hash_map_s_find len offset hm k == - partial_hash_map_s_find len (offset+1) hm' k); + assert(partial_hashMap_s_find len offset hm k == + partial_hashMap_s_find len (offset+1) hm' k); find_append (same_key k) slot (flatten hm'); assert(index hm 0 == slot); // Triggers instantiations not_same_hash_key_not_found_in_slot #t len k offset slot; assert(forall (i:nat{i < length hm'}). index hm' i == index hm (i+1)); // Triggers instantiations - partial_hash_map_s_is_assoc_list_lem #t len (offset+1) hm' k + partial_hashMap_s_is_assoc_list_lem #t len (offset+1) hm' k end #pop-options -val hash_map_is_assoc_list_lem (#t : Type0) (hm : hash_map_t t) : - Lemma (requires (hash_map_t_base_inv hm)) - (ensures (hash_map_is_assoc_list hm (hash_map_t_al_v hm))) +val hashMap_is_assoc_list_lem (#t : Type0) (hm : hashMap_t t) : + Lemma (requires (hashMap_t_base_inv hm)) + (ensures (hashMap_is_assoc_list hm (hashMap_t_al_v hm))) -let hash_map_is_assoc_list_lem #t hm = +let hashMap_is_assoc_list_lem #t hm = let aux (k:key) : - Lemma (hash_map_t_find_s hm k == assoc_list_find k (hash_map_t_al_v hm)) - [SMTPat (hash_map_t_find_s hm k)] = - let hm_v = hash_map_t_v hm in + Lemma (hashMap_t_find_s hm k == assoc_list_find k (hashMap_t_al_v hm)) + [SMTPat (hashMap_t_find_s hm k)] = + let hm_v = hashMap_t_v hm in let len = length hm_v in - partial_hash_map_s_is_assoc_list_lem #t len 0 hm_v k + partial_hashMap_s_is_assoc_list_lem #t len 0 hm_v k in () /// The final lemma about [move_elements]: calling it on an empty hash table moves /// all the elements to this empty table. -val hash_map_move_elements_fwd_back_lem - (t : Type0) (ntable : hash_map_t t) (slots : vec (list_t t)) : +val hashMap_move_elements_lem + (t : Type0) (ntable : hashMap_t t) (slots : alloc_vec_Vec (list_t t)) : Lemma (requires ( let al = flatten (slots_t_v slots) in - hash_map_t_base_inv ntable /\ + hashMap_t_base_inv ntable /\ length al <= usize_max /\ assoc_list_inv al /\ // The table is empty - hash_map_t_len_s ntable = 0 /\ - (forall (k:key). hash_map_t_find_s ntable k == None))) + hashMap_t_len_s ntable = 0 /\ + (forall (k:key). hashMap_t_find_s ntable k == None))) (ensures ( let al = flatten (slots_t_v slots) in - match hash_map_move_elements_fwd_back t ntable slots 0, - hash_map_move_elements_s_flat (hash_map_t_v ntable) al + match hashMap_move_elements t ntable slots 0, + hashMap_move_elements_s_flat (hashMap_t_v ntable) al with | Return (ntable', _), Return ntable'_v -> // The invariant is preserved - hash_map_t_base_inv ntable' /\ + hashMap_t_base_inv ntable' /\ // We preserved the parameters - hash_map_t_same_params ntable' ntable /\ + hashMap_t_same_params ntable' ntable /\ // The table has the same number of slots - length ntable'.hash_map_slots = length ntable.hash_map_slots /\ + length ntable'.slots = length ntable.slots /\ // The count is good - hash_map_t_len_s ntable' = length al /\ + hashMap_t_len_s ntable' = length al /\ // The table can be linked to its model (we need this only to reveal // "pretty" functional lemmas to the user in the fsti - so that we // can write lemmas with SMT patterns - this is very F* specific) - hash_map_t_v ntable' == ntable'_v /\ + hashMap_t_v ntable' == ntable'_v /\ // The new table contains exactly all the bindings from the slots - // Rk.: see the comment for [hash_map_is_assoc_list] - hash_map_is_assoc_list ntable' al + // Rk.: see the comment for [hashMap_is_assoc_list] + hashMap_is_assoc_list ntable' al | _ -> False // We can only succeed )) @@ -2154,41 +2154,41 @@ val hash_map_move_elements_fwd_back_lem // lack of ifuel (this kind of proofs is annoying, really). #restart-solver #push-options "--z3rlimit 100" -let hash_map_move_elements_fwd_back_lem t ntable slots = - let ntable_v = hash_map_t_v ntable in +let hashMap_move_elements_lem t ntable slots = + let ntable_v = hashMap_t_v ntable in let slots_v = slots_t_v slots in let al = flatten slots_v in - hash_map_move_elements_fwd_back_lem_refin t ntable slots 0; + hashMap_move_elements_lem_refin t ntable slots 0; begin - match hash_map_move_elements_fwd_back t ntable slots 0, - hash_map_move_elements_s ntable_v slots_v 0 + match hashMap_move_elements t ntable slots 0, + hashMap_move_elements_s ntable_v slots_v 0 with | Fail _, Fail _ -> () | Return (ntable', _), Return ntable'_v -> - assert(hash_map_t_base_inv ntable'); - assert(hash_map_t_v ntable' == ntable'_v) + assert(hashMap_t_base_inv ntable'); + assert(hashMap_t_v ntable' == ntable'_v) | _ -> assert(False) end; - hash_map_move_elements_s_lem_refin_flat ntable_v slots_v 0; + hashMap_move_elements_s_lem_refin_flat ntable_v slots_v 0; begin - match hash_map_move_elements_s ntable_v slots_v 0, - hash_map_move_elements_s_flat ntable_v (flatten_i slots_v 0) + match hashMap_move_elements_s ntable_v slots_v 0, + hashMap_move_elements_s_flat ntable_v (flatten_i slots_v 0) with | Fail _, Fail _ -> () | Return hm, Return hm' -> assert(hm == hm') | _ -> assert(False) end; flatten_0_is_flatten slots_v; // flatten_i slots_v 0 == flatten slots_v - hash_map_move_elements_s_flat_lem ntable_v al; - match hash_map_move_elements_fwd_back t ntable slots 0, - hash_map_move_elements_s_flat ntable_v al + hashMap_move_elements_s_flat_lem ntable_v al; + match hashMap_move_elements t ntable slots 0, + hashMap_move_elements_s_flat ntable_v al with | Return (ntable', _), Return ntable'_v -> - assert(hash_map_t_base_inv ntable'); - assert(length ntable'.hash_map_slots = length ntable.hash_map_slots); - assert(hash_map_t_len_s ntable' = length al); - assert(hash_map_t_v ntable' == ntable'_v); - assert(hash_map_is_assoc_list ntable' al) + assert(hashMap_t_base_inv ntable'); + assert(length ntable'.slots = length ntable.slots); + assert(hashMap_t_len_s ntable' = length al); + assert(hashMap_t_v ntable' == ntable'_v); + assert(hashMap_is_assoc_list ntable' al) | _ -> assert(False) #pop-options @@ -2197,47 +2197,47 @@ let hash_map_move_elements_fwd_back_lem t ntable slots = /// High-level model 1. /// This is one is slightly "crude": we just simplify a bit the function. -let hash_map_try_resize_s_simpl +let hashMap_try_resize_s_simpl (#t : Type0) - (hm : hash_map_t t) : - Pure (result (hash_map_t t)) + (hm : hashMap_t t) : + Pure (result (hashMap_t t)) (requires ( - let (divid, divis) = hm.hash_map_max_load_factor in + let (divid, divis) = hm.max_load_factor in divid > 0 /\ divis > 0)) (ensures (fun _ -> True)) = - let capacity = length hm.hash_map_slots in - let (divid, divis) = hm.hash_map_max_load_factor in + let capacity = length hm.slots in + let (divid, divis) = hm.max_load_factor in if capacity <= (usize_max / 2) / divid then let ncapacity : usize = capacity * 2 in - begin match hash_map_new_with_capacity_fwd t ncapacity divid divis with + begin match hashMap_new_with_capacity t ncapacity divid divis with | Fail e -> Fail e | Return ntable -> - match hash_map_move_elements_fwd_back t ntable hm.hash_map_slots 0 with + match hashMap_move_elements t ntable hm.slots 0 with | Fail e -> Fail e | Return (ntable', _) -> let hm = - { hm with hash_map_slots = ntable'.hash_map_slots; - hash_map_max_load = ntable'.hash_map_max_load } + { hm with slots = ntable'.slots; + max_load = ntable'.max_load } in Return hm end else Return hm -val hash_map_try_resize_fwd_back_lem_refin - (t : Type0) (self : hash_map_t t) : +val hashMap_try_resize_lem_refin + (t : Type0) (self : hashMap_t t) : Lemma (requires ( - let (divid, divis) = self.hash_map_max_load_factor in + let (divid, divis) = self.max_load_factor in divid > 0 /\ divis > 0)) (ensures ( - match hash_map_try_resize_fwd_back t self, - hash_map_try_resize_s_simpl self + match hashMap_try_resize t self, + hashMap_try_resize_s_simpl self with | Fail _, Fail _ -> True | Return hm1, Return hm2 -> hm1 == hm2 | _ -> False)) -let hash_map_try_resize_fwd_back_lem_refin t self = () +let hashMap_try_resize_lem_refin t self = () /// Isolating arithmetic proofs @@ -2342,78 +2342,78 @@ let new_max_load_lem len capacity divid divis = assert(nmax_load >= max_load + 1) #pop-options -val hash_map_try_resize_s_simpl_lem (#t : Type0) (hm : hash_map_t t) : +val hashMap_try_resize_s_simpl_lem (#t : Type0) (hm : hashMap_t t) : Lemma (requires ( // The base invariant is satisfied - hash_map_t_base_inv hm /\ + hashMap_t_base_inv hm /\ // However, the "full" invariant is broken, as we call [try_resize] // only if the current number of entries is > the max load. // // There are two situations: // - either we just reached the max load // - or we were already saturated and can't resize - (let (dividend, divisor) = hm.hash_map_max_load_factor in - hm.hash_map_num_entries == hm.hash_map_max_load + 1 \/ - length hm.hash_map_slots * 2 * dividend > usize_max) + (let (dividend, divisor) = hm.max_load_factor in + hm.num_entries == hm.max_load + 1 \/ + length hm.slots * 2 * dividend > usize_max) )) (ensures ( - match hash_map_try_resize_s_simpl hm with + match hashMap_try_resize_s_simpl hm with | Fail _ -> False | Return hm' -> // The full invariant is now satisfied (the full invariant is "base // invariant" + the map is not overloaded (or can't be resized because // already too big) - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // It contains the same bindings as the initial map - (forall (k:key). hash_map_t_find_s hm' k == hash_map_t_find_s hm k))) + (forall (k:key). hashMap_t_find_s hm' k == hashMap_t_find_s hm k))) #restart-solver #push-options "--z3rlimit 400" -let hash_map_try_resize_s_simpl_lem #t hm = - let capacity = length hm.hash_map_slots in - let (divid, divis) = hm.hash_map_max_load_factor in +let hashMap_try_resize_s_simpl_lem #t hm = + let capacity = length hm.slots in + let (divid, divis) = hm.max_load_factor in if capacity <= (usize_max / 2) / divid then begin let ncapacity : usize = capacity * 2 in assert(ncapacity * divid <= usize_max); - assert(hash_map_t_len_s hm = hm.hash_map_max_load + 1); - new_max_load_lem (hash_map_t_len_s hm) capacity divid divis; - hash_map_new_with_capacity_fwd_lem t ncapacity divid divis; - match hash_map_new_with_capacity_fwd t ncapacity divid divis with + assert(hashMap_t_len_s hm = hm.max_load + 1); + new_max_load_lem (hashMap_t_len_s hm) capacity divid divis; + hashMap_new_with_capacity_lem t ncapacity divid divis; + match hashMap_new_with_capacity t ncapacity divid divis with | Fail _ -> () | Return ntable -> - let slots = hm.hash_map_slots in + let slots = hm.slots in let al = flatten (slots_t_v slots) in - // Proving that: length al = hm.hash_map_num_entries + // Proving that: length al = hm.num_entries assert(al == flatten (map slot_t_v slots)); assert(al == flatten (map list_t_v slots)); - assert(hash_map_t_al_v hm == flatten (hash_map_t_v hm)); - assert(hash_map_t_al_v hm == flatten (map list_t_v hm.hash_map_slots)); - assert(al == hash_map_t_al_v hm); - assert(hash_map_t_base_inv ntable); - assert(length al = hm.hash_map_num_entries); + assert(hashMap_t_al_v hm == flatten (hashMap_t_v hm)); + assert(hashMap_t_al_v hm == flatten (map list_t_v hm.slots)); + assert(al == hashMap_t_al_v hm); + assert(hashMap_t_base_inv ntable); + assert(length al = hm.num_entries); assert(length al <= usize_max); - hash_map_t_base_inv_implies_assoc_list_lem hm; + hashMap_t_base_inv_implies_assoc_list_lem hm; assert(assoc_list_inv al); - assert(hash_map_t_len_s ntable = 0); - assert(forall (k:key). hash_map_t_find_s ntable k == None); - hash_map_move_elements_fwd_back_lem t ntable hm.hash_map_slots; - match hash_map_move_elements_fwd_back t ntable hm.hash_map_slots 0 with + assert(hashMap_t_len_s ntable = 0); + assert(forall (k:key). hashMap_t_find_s ntable k == None); + hashMap_move_elements_lem t ntable hm.slots; + match hashMap_move_elements t ntable hm.slots 0 with | Fail _ -> () | Return (ntable', _) -> - hash_map_is_assoc_list_lem hm; - assert(hash_map_is_assoc_list hm (hash_map_t_al_v hm)); + hashMap_is_assoc_list_lem hm; + assert(hashMap_is_assoc_list hm (hashMap_t_al_v hm)); let hm' = - { hm with hash_map_slots = ntable'.hash_map_slots; - hash_map_max_load = ntable'.hash_map_max_load } + { hm with slots = ntable'.slots; + max_load = ntable'.max_load } in - assert(hash_map_t_base_inv ntable'); - assert(hash_map_t_base_inv hm'); - assert(hash_map_t_len_s hm' = hash_map_t_len_s hm); - new_max_load_lem (hash_map_t_len_s hm') capacity divid divis; - assert(hash_map_t_len_s hm' <= hm'.hash_map_max_load); // Requires a lemma - assert(hash_map_t_inv hm') + assert(hashMap_t_base_inv ntable'); + assert(hashMap_t_base_inv hm'); + assert(hashMap_t_len_s hm' = hashMap_t_len_s hm); + new_max_load_lem (hashMap_t_len_s hm') capacity divid divis; + assert(hashMap_t_len_s hm' <= hm'.max_load); // Requires a lemma + assert(hashMap_t_inv hm') end else begin @@ -2422,203 +2422,203 @@ let hash_map_try_resize_s_simpl_lem #t hm = end #pop-options -let hash_map_t_same_bindings (#t : Type0) (hm hm' : hash_map_t_nes t) : Type0 = - forall (k:key). hash_map_t_find_s hm k == hash_map_t_find_s hm' k +let hashMap_t_same_bindings (#t : Type0) (hm hm' : hashMap_t_nes t) : Type0 = + forall (k:key). hashMap_t_find_s hm k == hashMap_t_find_s hm' k /// The final lemma about [try_resize] -val hash_map_try_resize_fwd_back_lem (#t : Type0) (hm : hash_map_t t) : +val hashMap_try_resize_lem (#t : Type0) (hm : hashMap_t t) : Lemma (requires ( - hash_map_t_base_inv hm /\ + hashMap_t_base_inv hm /\ // However, the "full" invariant is broken, as we call [try_resize] // only if the current number of entries is > the max load. // // There are two situations: // - either we just reached the max load // - or we were already saturated and can't resize - (let (dividend, divisor) = hm.hash_map_max_load_factor in - hm.hash_map_num_entries == hm.hash_map_max_load + 1 \/ - length hm.hash_map_slots * 2 * dividend > usize_max))) + (let (dividend, divisor) = hm.max_load_factor in + hm.num_entries == hm.max_load + 1 \/ + length hm.slots * 2 * dividend > usize_max))) (ensures ( - match hash_map_try_resize_fwd_back t hm with + match hashMap_try_resize t hm with | Fail _ -> False | Return hm' -> // The full invariant is now satisfied (the full invariant is "base // invariant" + the map is not overloaded (or can't be resized because // already too big) - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // The length is the same - hash_map_t_len_s hm' = hash_map_t_len_s hm /\ + hashMap_t_len_s hm' = hashMap_t_len_s hm /\ // It contains the same bindings as the initial map - hash_map_t_same_bindings hm' hm)) + hashMap_t_same_bindings hm' hm)) -let hash_map_try_resize_fwd_back_lem #t hm = - hash_map_try_resize_fwd_back_lem_refin t hm; - hash_map_try_resize_s_simpl_lem hm +let hashMap_try_resize_lem #t hm = + hashMap_try_resize_lem_refin t hm; + hashMap_try_resize_s_simpl_lem hm (*** insert *) /// The high-level model (very close to the original function: we don't need something /// very high level, just to clean it a bit) -let hash_map_insert_s - (#t : Type0) (self : hash_map_t t) (key : usize) (value : t) : - result (hash_map_t t) = - match hash_map_insert_no_resize_fwd_back t self key value with +let hashMap_insert_s + (#t : Type0) (self : hashMap_t t) (key : usize) (value : t) : + result (hashMap_t t) = + match hashMap_insert_no_resize t self key value with | Fail e -> Fail e | Return hm' -> - if hash_map_t_len_s hm' > hm'.hash_map_max_load then - hash_map_try_resize_fwd_back t hm' + if hashMap_t_len_s hm' > hm'.max_load then + hashMap_try_resize t hm' else Return hm' -val hash_map_insert_fwd_back_lem_refin - (t : Type0) (self : hash_map_t t) (key : usize) (value : t) : +val hashMap_insert_lem_refin + (t : Type0) (self : hashMap_t t) (key : usize) (value : t) : Lemma (requires True) (ensures ( - match hash_map_insert_fwd_back t self key value, - hash_map_insert_s self key value + match hashMap_insert t self key value, + hashMap_insert_s self key value with | Fail _, Fail _ -> True | Return hm1, Return hm2 -> hm1 == hm2 | _ -> False)) -let hash_map_insert_fwd_back_lem_refin t self key value = () +let hashMap_insert_lem_refin t self key value = () /// Helper -let hash_map_insert_fwd_back_bindings_lem - (t : Type0) (self : hash_map_t_nes t) (key : usize) (value : t) - (hm' hm'' : hash_map_t_nes t) : +let hashMap_insert_bindings_lem + (t : Type0) (self : hashMap_t_nes t) (key : usize) (value : t) + (hm' hm'' : hashMap_t_nes t) : Lemma (requires ( - hash_map_s_updated_binding (hash_map_t_v self) key - (Some value) (hash_map_t_v hm') /\ - hash_map_t_same_bindings hm' hm'')) + hashMap_s_updated_binding (hashMap_t_v self) key + (Some value) (hashMap_t_v hm') /\ + hashMap_t_same_bindings hm' hm'')) (ensures ( - hash_map_s_updated_binding (hash_map_t_v self) key - (Some value) (hash_map_t_v hm''))) + hashMap_s_updated_binding (hashMap_t_v self) key + (Some value) (hashMap_t_v hm''))) = () -val hash_map_insert_fwd_back_lem_aux - (#t : Type0) (self : hash_map_t t) (key : usize) (value : t) : - Lemma (requires (hash_map_t_inv self)) +val hashMap_insert_lem_aux + (#t : Type0) (self : hashMap_t t) (key : usize) (value : t) : + Lemma (requires (hashMap_t_inv self)) (ensures ( - match hash_map_insert_fwd_back t self key value with + match hashMap_insert t self key value with | Fail _ -> // We can fail only if: // - the key is not in the map and we need to add it // - we are already saturated - hash_map_t_len_s self = usize_max /\ - None? (hash_map_t_find_s self key) + hashMap_t_len_s self = usize_max /\ + None? (hashMap_t_find_s self key) | Return hm' -> // The invariant is preserved - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // [key] maps to [value] and the other bindings are preserved - hash_map_s_updated_binding (hash_map_t_v self) key (Some value) (hash_map_t_v hm') /\ + hashMap_s_updated_binding (hashMap_t_v self) key (Some value) (hashMap_t_v hm') /\ // The length is incremented, iff we inserted a new key - (match hash_map_t_find_s self key with - | None -> hash_map_t_len_s hm' = hash_map_t_len_s self + 1 - | Some _ -> hash_map_t_len_s hm' = hash_map_t_len_s self))) + (match hashMap_t_find_s self key with + | None -> hashMap_t_len_s hm' = hashMap_t_len_s self + 1 + | Some _ -> hashMap_t_len_s hm' = hashMap_t_len_s self))) #restart-solver #push-options "--z3rlimit 200" -let hash_map_insert_fwd_back_lem_aux #t self key value = - hash_map_insert_no_resize_fwd_back_lem_s t self key value; - hash_map_insert_no_resize_s_lem (hash_map_t_v self) key value; - match hash_map_insert_no_resize_fwd_back t self key value with +let hashMap_insert_lem_aux #t self key value = + hashMap_insert_no_resize_lem_s t self key value; + hashMap_insert_no_resize_s_lem (hashMap_t_v self) key value; + match hashMap_insert_no_resize t self key value with | Fail _ -> () | Return hm' -> - // Expanding the post of [hash_map_insert_no_resize_fwd_back_lem_s] - let self_v = hash_map_t_v self in - let hm'_v = Return?.v (hash_map_insert_no_resize_s self_v key value) in - assert(hash_map_t_base_inv hm'); - assert(hash_map_t_same_params hm' self); - assert(hash_map_t_v hm' == hm'_v); - assert(hash_map_s_len hm'_v == hash_map_t_len_s hm'); - // Expanding the post of [hash_map_insert_no_resize_s_lem] + // Expanding the post of [hashMap_insert_no_resize_lem_s] + let self_v = hashMap_t_v self in + let hm'_v = Return?.v (hashMap_insert_no_resize_s self_v key value) in + assert(hashMap_t_base_inv hm'); + assert(hashMap_t_same_params hm' self); + assert(hashMap_t_v hm' == hm'_v); + assert(hashMap_s_len hm'_v == hashMap_t_len_s hm'); + // Expanding the post of [hashMap_insert_no_resize_s_lem] assert(insert_post self_v key value hm'_v); // Expanding [insert_post] - assert(hash_map_s_inv hm'_v); + assert(hashMap_s_inv hm'_v); assert( - match hash_map_s_find self_v key with - | None -> hash_map_s_len hm'_v = hash_map_s_len self_v + 1 - | Some _ -> hash_map_s_len hm'_v = hash_map_s_len self_v); - if hash_map_t_len_s hm' > hm'.hash_map_max_load then + match hashMap_s_find self_v key with + | None -> hashMap_s_len hm'_v = hashMap_s_len self_v + 1 + | Some _ -> hashMap_s_len hm'_v = hashMap_s_len self_v); + if hashMap_t_len_s hm' > hm'.max_load then begin - hash_map_try_resize_fwd_back_lem hm'; - // Expanding the post of [hash_map_try_resize_fwd_back_lem] - let hm'' = Return?.v (hash_map_try_resize_fwd_back t hm') in - assert(hash_map_t_inv hm''); - let hm''_v = hash_map_t_v hm'' in - assert(forall k. hash_map_t_find_s hm'' k == hash_map_t_find_s hm' k); - assert(hash_map_t_len_s hm'' = hash_map_t_len_s hm'); // TODO + hashMap_try_resize_lem hm'; + // Expanding the post of [hashMap_try_resize_lem] + let hm'' = Return?.v (hashMap_try_resize t hm') in + assert(hashMap_t_inv hm''); + let hm''_v = hashMap_t_v hm'' in + assert(forall k. hashMap_t_find_s hm'' k == hashMap_t_find_s hm' k); + assert(hashMap_t_len_s hm'' = hashMap_t_len_s hm'); // TODO // Proving the post - assert(hash_map_t_inv hm''); - hash_map_insert_fwd_back_bindings_lem t self key value hm' hm''; + assert(hashMap_t_inv hm''); + hashMap_insert_bindings_lem t self key value hm' hm''; assert( - match hash_map_t_find_s self key with - | None -> hash_map_t_len_s hm'' = hash_map_t_len_s self + 1 - | Some _ -> hash_map_t_len_s hm'' = hash_map_t_len_s self) + match hashMap_t_find_s self key with + | None -> hashMap_t_len_s hm'' = hashMap_t_len_s self + 1 + | Some _ -> hashMap_t_len_s hm'' = hashMap_t_len_s self) end else () #pop-options -let hash_map_insert_fwd_back_lem #t self key value = - hash_map_insert_fwd_back_lem_aux #t self key value +let hashMap_insert_lem #t self key value = + hashMap_insert_lem_aux #t self key value (*** contains_key *) (**** contains_key_in_list *) -val hash_map_contains_key_in_list_fwd_lem +val hashMap_contains_key_in_list_lem (#t : Type0) (key : usize) (ls : list_t t) : Lemma (ensures ( - match hash_map_contains_key_in_list_fwd t key ls with + match hashMap_contains_key_in_list t key ls with | Fail _ -> False | Return b -> b = Some? (slot_t_find_s key ls))) #push-options "--fuel 1" -let rec hash_map_contains_key_in_list_fwd_lem #t key ls = +let rec hashMap_contains_key_in_list_lem #t key ls = match ls with - | ListCons ckey x ls0 -> + | List_Cons ckey x ls0 -> let b = ckey = key in if b then () else begin - hash_map_contains_key_in_list_fwd_lem key ls0; - match hash_map_contains_key_in_list_fwd t key ls0 with + hashMap_contains_key_in_list_lem key ls0; + match hashMap_contains_key_in_list t key ls0 with | Fail _ -> () | Return b0 -> () end - | ListNil -> () + | List_Nil -> () #pop-options (**** contains_key *) -val hash_map_contains_key_fwd_lem_aux - (#t : Type0) (self : hash_map_t_nes t) (key : usize) : +val hashMap_contains_key_lem_aux + (#t : Type0) (self : hashMap_t_nes t) (key : usize) : Lemma (ensures ( - match hash_map_contains_key_fwd t self key with + match hashMap_contains_key t self key with | Fail _ -> False - | Return b -> b = Some? (hash_map_t_find_s self key))) + | Return b -> b = Some? (hashMap_t_find_s self key))) -let hash_map_contains_key_fwd_lem_aux #t self key = - begin match hash_key_fwd key with +let hashMap_contains_key_lem_aux #t self key = + begin match hash_key key with | Fail _ -> () | Return i -> - let v = self.hash_map_slots in - let i0 = vec_len (list_t t) v in + let v = self.slots in + let i0 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i0 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> - hash_map_contains_key_in_list_fwd_lem key l; - begin match hash_map_contains_key_in_list_fwd t key l with + hashMap_contains_key_in_list_lem key l; + begin match hashMap_contains_key_in_list t key l with | Fail _ -> () | Return b -> () end @@ -2627,66 +2627,66 @@ let hash_map_contains_key_fwd_lem_aux #t self key = end /// The lemma in the .fsti -let hash_map_contains_key_fwd_lem #t self key = - hash_map_contains_key_fwd_lem_aux #t self key +let hashMap_contains_key_lem #t self key = + hashMap_contains_key_lem_aux #t self key (*** get *) (**** get_in_list *) -val hash_map_get_in_list_fwd_lem +val hashMap_get_in_list_lem (#t : Type0) (key : usize) (ls : list_t t) : Lemma (ensures ( - match hash_map_get_in_list_fwd t key ls, slot_t_find_s key ls with + match hashMap_get_in_list t key ls, slot_t_find_s key ls with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) #push-options "--fuel 1" -let rec hash_map_get_in_list_fwd_lem #t key ls = +let rec hashMap_get_in_list_lem #t key ls = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b then () else begin - hash_map_get_in_list_fwd_lem key ls0; - match hash_map_get_in_list_fwd t key ls0 with + hashMap_get_in_list_lem key ls0; + match hashMap_get_in_list t key ls0 with | Fail _ -> () | Return x -> () end - | ListNil -> () + | List_Nil -> () end #pop-options (**** get *) -val hash_map_get_fwd_lem_aux - (#t : Type0) (self : hash_map_t_nes t) (key : usize) : +val hashMap_get_lem_aux + (#t : Type0) (self : hashMap_t_nes t) (key : usize) : Lemma (ensures ( - match hash_map_get_fwd t self key, hash_map_t_find_s self key with + match hashMap_get t self key, hashMap_t_find_s self key with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) -let hash_map_get_fwd_lem_aux #t self key = - begin match hash_key_fwd key with +let hashMap_get_lem_aux #t self key = + begin match hash_key key with | Fail _ -> () | Return i -> - let v = self.hash_map_slots in - let i0 = vec_len (list_t t) v in + let v = self.slots in + let i0 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i0 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - hash_map_get_in_list_fwd_lem key l; - match hash_map_get_in_list_fwd t key l with + hashMap_get_in_list_lem key l; + match hashMap_get_in_list t key l with | Fail _ -> () | Return x -> () end @@ -2695,66 +2695,66 @@ let hash_map_get_fwd_lem_aux #t self key = end /// .fsti -let hash_map_get_fwd_lem #t self key = hash_map_get_fwd_lem_aux #t self key +let hashMap_get_lem #t self key = hashMap_get_lem_aux #t self key (*** get_mut'fwd *) (**** get_mut_in_list'fwd *) -val hash_map_get_mut_in_list_loop_fwd_lem +val hashMap_get_mut_in_list_loop_lem (#t : Type0) (ls : list_t t) (key : usize) : Lemma (ensures ( - match hash_map_get_mut_in_list_loop_fwd t ls key, slot_t_find_s key ls with + match hashMap_get_mut_in_list_loop t ls key, slot_t_find_s key ls with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) #push-options "--fuel 1" -let rec hash_map_get_mut_in_list_loop_fwd_lem #t ls key = +let rec hashMap_get_mut_in_list_loop_lem #t ls key = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b then () else begin - hash_map_get_mut_in_list_loop_fwd_lem ls0 key; - match hash_map_get_mut_in_list_loop_fwd t ls0 key with + hashMap_get_mut_in_list_loop_lem ls0 key; + match hashMap_get_mut_in_list_loop t ls0 key with | Fail _ -> () | Return x -> () end - | ListNil -> () + | List_Nil -> () end #pop-options (**** get_mut'fwd *) -val hash_map_get_mut_fwd_lem_aux - (#t : Type0) (self : hash_map_t_nes t) (key : usize) : +val hashMap_get_mut_lem_aux + (#t : Type0) (self : hashMap_t_nes t) (key : usize) : Lemma (ensures ( - match hash_map_get_mut_fwd t self key, hash_map_t_find_s self key with + match hashMap_get_mut t self key, hashMap_t_find_s self key with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) -let hash_map_get_mut_fwd_lem_aux #t self key = - begin match hash_key_fwd key with +let hashMap_get_mut_lem_aux #t self key = + begin match hash_key key with | Fail _ -> () | Return i -> - let v = self.hash_map_slots in - let i0 = vec_len (list_t t) v in + let v = self.slots in + let i0 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i0 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - hash_map_get_mut_in_list_loop_fwd_lem l key; - match hash_map_get_mut_in_list_loop_fwd t l key with + hashMap_get_mut_in_list_loop_lem l key; + match hashMap_get_mut_in_list_loop t l key with | Fail _ -> () | Return x -> () end @@ -2762,78 +2762,78 @@ let hash_map_get_mut_fwd_lem_aux #t self key = end end -let hash_map_get_mut_fwd_lem #t self key = - hash_map_get_mut_fwd_lem_aux #t self key +let hashMap_get_mut_lem #t self key = + hashMap_get_mut_lem_aux #t self key (*** get_mut'back *) (**** get_mut_in_list'back *) -val hash_map_get_mut_in_list_loop_back_lem +val hashMap_get_mut_in_list_loop_back_lem (#t : Type0) (ls : list_t t) (key : usize) (ret : t) : Lemma (requires (Some? (slot_t_find_s key ls))) (ensures ( - match hash_map_get_mut_in_list_loop_back t ls key ret with + match hashMap_get_mut_in_list_loop_back t ls key ret with | Fail _ -> False | Return ls' -> list_t_v ls' == find_update (same_key key) (list_t_v ls) (key,ret) | _ -> False)) #push-options "--fuel 1" -let rec hash_map_get_mut_in_list_loop_back_lem #t ls key ret = +let rec hashMap_get_mut_in_list_loop_back_lem #t ls key ret = begin match ls with - | ListCons ckey cvalue ls0 -> + | List_Cons ckey cvalue ls0 -> let b = ckey = key in if b - then let ls1 = ListCons ckey ret ls0 in () + then let ls1 = List_Cons ckey ret ls0 in () else begin - hash_map_get_mut_in_list_loop_back_lem ls0 key ret; - match hash_map_get_mut_in_list_loop_back t ls0 key ret with + hashMap_get_mut_in_list_loop_back_lem ls0 key ret; + match hashMap_get_mut_in_list_loop_back t ls0 key ret with | Fail _ -> () - | Return l -> let ls1 = ListCons ckey cvalue l in () + | Return l -> let ls1 = List_Cons ckey cvalue l in () end - | ListNil -> () + | List_Nil -> () end #pop-options (**** get_mut'back *) /// Refinement lemma -val hash_map_get_mut_back_lem_refin - (#t : Type0) (self : hash_map_t t{length self.hash_map_slots > 0}) +val hashMap_get_mut_back_lem_refin + (#t : Type0) (self : hashMap_t t{length self.slots > 0}) (key : usize) (ret : t) : Lemma - (requires (Some? (hash_map_t_find_s self key))) + (requires (Some? (hashMap_t_find_s self key))) (ensures ( - match hash_map_get_mut_back t self key ret with + match hashMap_get_mut_back t self key ret with | Fail _ -> False | Return hm' -> - hash_map_t_v hm' == hash_map_insert_no_fail_s (hash_map_t_v self) key ret)) + hashMap_t_v hm' == hashMap_insert_no_fail_s (hashMap_t_v self) key ret)) -let hash_map_get_mut_back_lem_refin #t self key ret = - begin match hash_key_fwd key with +let hashMap_get_mut_back_lem_refin #t self key ret = + begin match hash_key key with | Fail _ -> () | Return i -> - let i0 = self.hash_map_num_entries in - let p = self.hash_map_max_load_factor in - let i1 = self.hash_map_max_load in - let v = self.hash_map_slots in - let i2 = vec_len (list_t t) v in + let i0 = self.num_entries in + let p = self.max_load_factor in + let i1 = self.max_load in + let v = self.slots in + let i2 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i2 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_mut_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - hash_map_get_mut_in_list_loop_back_lem l key ret; - match hash_map_get_mut_in_list_loop_back t l key ret with + hashMap_get_mut_in_list_loop_back_lem l key ret; + match hashMap_get_mut_in_list_loop_back t l key ret with | Fail _ -> () | Return l0 -> - begin match vec_index_mut_back (list_t t) v hash_mod l0 with + begin match alloc_vec_Vec_update_usize v hash_mod l0 with | Fail _ -> () - | Return v0 -> let self0 = Mkhash_map_t i0 p i1 v0 in () + | Return v0 -> let self0 = MkhashMap_t i0 p i1 v0 in () end end end @@ -2841,102 +2841,102 @@ let hash_map_get_mut_back_lem_refin #t self key ret = end /// Final lemma -val hash_map_get_mut_back_lem_aux - (#t : Type0) (hm : hash_map_t t) +val hashMap_get_mut_back_lem_aux + (#t : Type0) (hm : hashMap_t t) (key : usize) (ret : t) : Lemma (requires ( - hash_map_t_inv hm /\ - Some? (hash_map_t_find_s hm key))) + hashMap_t_inv hm /\ + Some? (hashMap_t_find_s hm key))) (ensures ( - match hash_map_get_mut_back t hm key ret with + match hashMap_get_mut_back t hm key ret with | Fail _ -> False | Return hm' -> // Functional spec - hash_map_t_v hm' == hash_map_insert_no_fail_s (hash_map_t_v hm) key ret /\ + hashMap_t_v hm' == hashMap_insert_no_fail_s (hashMap_t_v hm) key ret /\ // The invariant is preserved - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // The length is preserved - hash_map_t_len_s hm' = hash_map_t_len_s hm /\ + hashMap_t_len_s hm' = hashMap_t_len_s hm /\ // [key] maps to [value] - hash_map_t_find_s hm' key == Some ret /\ + hashMap_t_find_s hm' key == Some ret /\ // The other bindings are preserved - (forall k'. k' <> key ==> hash_map_t_find_s hm' k' == hash_map_t_find_s hm k'))) + (forall k'. k' <> key ==> hashMap_t_find_s hm' k' == hashMap_t_find_s hm k'))) -let hash_map_get_mut_back_lem_aux #t hm key ret = - let hm_v = hash_map_t_v hm in - hash_map_get_mut_back_lem_refin hm key ret; - match hash_map_get_mut_back t hm key ret with +let hashMap_get_mut_back_lem_aux #t hm key ret = + let hm_v = hashMap_t_v hm in + hashMap_get_mut_back_lem_refin hm key ret; + match hashMap_get_mut_back t hm key ret with | Fail _ -> assert(False) | Return hm' -> - hash_map_insert_no_fail_s_lem hm_v key ret + hashMap_insert_no_fail_s_lem hm_v key ret /// .fsti -let hash_map_get_mut_back_lem #t hm key ret = hash_map_get_mut_back_lem_aux hm key ret +let hashMap_get_mut_back_lem #t hm key ret = hashMap_get_mut_back_lem_aux hm key ret (*** remove'fwd *) -val hash_map_remove_from_list_fwd_lem +val hashMap_remove_from_list_lem (#t : Type0) (key : usize) (ls : list_t t) : Lemma (ensures ( - match hash_map_remove_from_list_fwd t key ls with + match hashMap_remove_from_list t key ls with | Fail _ -> False | Return opt_x -> opt_x == slot_t_find_s key ls /\ (Some? opt_x ==> length (slot_t_v ls) > 0))) #push-options "--fuel 1" -let rec hash_map_remove_from_list_fwd_lem #t key ls = +let rec hashMap_remove_from_list_lem #t key ls = begin match ls with - | ListCons ckey x tl -> + | List_Cons ckey x tl -> let b = ckey = key in if b then - let mv_ls = mem_replace_fwd (list_t t) (ListCons ckey x tl) ListNil in + let mv_ls = core_mem_replace (list_t t) (List_Cons ckey x tl) List_Nil in begin match mv_ls with - | ListCons i cvalue tl0 -> () - | ListNil -> () + | List_Cons i cvalue tl0 -> () + | List_Nil -> () end else begin - hash_map_remove_from_list_fwd_lem key tl; - match hash_map_remove_from_list_fwd t key tl with + hashMap_remove_from_list_lem key tl; + match hashMap_remove_from_list t key tl with | Fail _ -> () | Return opt -> () end - | ListNil -> () + | List_Nil -> () end #pop-options -val hash_map_remove_fwd_lem_aux - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_remove_lem_aux + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma (requires ( // We need the invariant to prove that upon decrementing the entries counter, // the counter doesn't become negative - hash_map_t_inv self)) + hashMap_t_inv self)) (ensures ( - match hash_map_remove_fwd t self key with + match hashMap_remove t self key with | Fail _ -> False - | Return opt_x -> opt_x == hash_map_t_find_s self key)) + | Return opt_x -> opt_x == hashMap_t_find_s self key)) -let hash_map_remove_fwd_lem_aux #t self key = - begin match hash_key_fwd key with +let hashMap_remove_lem_aux #t self key = + begin match hash_key key with | Fail _ -> () | Return i -> - let i0 = self.hash_map_num_entries in - let v = self.hash_map_slots in - let i1 = vec_len (list_t t) v in + let i0 = self.num_entries in + let v = self.slots in + let i1 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i1 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_mut_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - hash_map_remove_from_list_fwd_lem key l; - match hash_map_remove_from_list_fwd t key l with + hashMap_remove_from_list_lem key l; + match hashMap_remove_from_list t key l with | Fail _ -> () | Return x -> begin match x with @@ -2945,7 +2945,7 @@ let hash_map_remove_fwd_lem_aux #t self key = begin assert(l == index v hash_mod); assert(length (list_t_v #t l) > 0); - length_flatten_index (hash_map_t_v self) hash_mod; + length_flatten_index (hashMap_t_v self) hash_mod; match usize_sub i0 1 with | Fail _ -> () | Return _ -> () @@ -2957,27 +2957,27 @@ let hash_map_remove_fwd_lem_aux #t self key = end /// .fsti -let hash_map_remove_fwd_lem #t self key = hash_map_remove_fwd_lem_aux #t self key +let hashMap_remove_lem #t self key = hashMap_remove_lem_aux #t self key (*** remove'back *) (**** Refinement proofs *) /// High-level model for [remove_from_list'back] -let hash_map_remove_from_list_s +let hashMap_remove_from_list_s (#t : Type0) (key : usize) (ls : slot_s t) : slot_s t = filter_one (not_same_key key) ls /// Refinement lemma -val hash_map_remove_from_list_back_lem_refin +val hashMap_remove_from_list_back_lem_refin (#t : Type0) (key : usize) (ls : list_t t) : Lemma (ensures ( - match hash_map_remove_from_list_back t key ls with + match hashMap_remove_from_list_back t key ls with | Fail _ -> False | Return ls' -> - list_t_v ls' == hash_map_remove_from_list_s key (list_t_v ls) /\ + list_t_v ls' == hashMap_remove_from_list_s key (list_t_v ls) /\ // The length is decremented, iff the key was in the slot (let len = length (list_t_v ls) in let len' = length (list_t_v ls') in @@ -2986,89 +2986,89 @@ val hash_map_remove_from_list_back_lem_refin | Some _ -> len = len' + 1))) #push-options "--fuel 1" -let rec hash_map_remove_from_list_back_lem_refin #t key ls = +let rec hashMap_remove_from_list_back_lem_refin #t key ls = begin match ls with - | ListCons ckey x tl -> + | List_Cons ckey x tl -> let b = ckey = key in if b then - let mv_ls = mem_replace_fwd (list_t t) (ListCons ckey x tl) ListNil in + let mv_ls = core_mem_replace (list_t t) (List_Cons ckey x tl) List_Nil in begin match mv_ls with - | ListCons i cvalue tl0 -> () - | ListNil -> () + | List_Cons i cvalue tl0 -> () + | List_Nil -> () end else begin - hash_map_remove_from_list_back_lem_refin key tl; - match hash_map_remove_from_list_back t key tl with + hashMap_remove_from_list_back_lem_refin key tl; + match hashMap_remove_from_list_back t key tl with | Fail _ -> () - | Return l -> let ls0 = ListCons ckey x l in () + | Return l -> let ls0 = List_Cons ckey x l in () end - | ListNil -> () + | List_Nil -> () end #pop-options /// High-level model for [remove_from_list'back] -let hash_map_remove_s - (#t : Type0) (self : hash_map_s_nes t) (key : usize) : - hash_map_s t = +let hashMap_remove_s + (#t : Type0) (self : hashMap_s_nes t) (key : usize) : + hashMap_s t = let len = length self in let hash = hash_mod_key key len in let slot = index self hash in - let slot' = hash_map_remove_from_list_s key slot in + let slot' = hashMap_remove_from_list_s key slot in list_update self hash slot' /// Refinement lemma -val hash_map_remove_back_lem_refin - (#t : Type0) (self : hash_map_t_nes t) (key : usize) : +val hashMap_remove_back_lem_refin + (#t : Type0) (self : hashMap_t_nes t) (key : usize) : Lemma (requires ( // We need the invariant to prove that upon decrementing the entries counter, // the counter doesn't become negative - hash_map_t_inv self)) + hashMap_t_inv self)) (ensures ( - match hash_map_remove_back t self key with + match hashMap_remove_back t self key with | Fail _ -> False | Return hm' -> - hash_map_t_same_params hm' self /\ - hash_map_t_v hm' == hash_map_remove_s (hash_map_t_v self) key /\ + hashMap_t_same_params hm' self /\ + hashMap_t_v hm' == hashMap_remove_s (hashMap_t_v self) key /\ // The length is decremented iff the key was in the map - (let len = hash_map_t_len_s self in - let len' = hash_map_t_len_s hm' in - match hash_map_t_find_s self key with + (let len = hashMap_t_len_s self in + let len' = hashMap_t_len_s hm' in + match hashMap_t_find_s self key with | None -> len = len' | Some _ -> len = len' + 1))) -let hash_map_remove_back_lem_refin #t self key = - begin match hash_key_fwd key with +let hashMap_remove_back_lem_refin #t self key = + begin match hash_key key with | Fail _ -> () | Return i -> - let i0 = self.hash_map_num_entries in - let p = self.hash_map_max_load_factor in - let i1 = self.hash_map_max_load in - let v = self.hash_map_slots in - let i2 = vec_len (list_t t) v in + let i0 = self.num_entries in + let p = self.max_load_factor in + let i1 = self.max_load in + let v = self.slots in + let i2 = alloc_vec_Vec_len (list_t t) v in begin match usize_rem i i2 with | Fail _ -> () | Return hash_mod -> - begin match vec_index_mut_fwd (list_t t) v hash_mod with + begin match alloc_vec_Vec_index_usize v hash_mod with | Fail _ -> () | Return l -> begin - hash_map_remove_from_list_fwd_lem key l; - match hash_map_remove_from_list_fwd t key l with + hashMap_remove_from_list_lem key l; + match hashMap_remove_from_list t key l with | Fail _ -> () | Return x -> begin match x with | None -> begin - hash_map_remove_from_list_back_lem_refin key l; - match hash_map_remove_from_list_back t key l with + hashMap_remove_from_list_back_lem_refin key l; + match hashMap_remove_from_list_back t key l with | Fail _ -> () | Return l0 -> begin length_flatten_update (slots_t_v v) hash_mod (list_t_v l0); - match vec_index_mut_back (list_t t) v hash_mod l0 with + match alloc_vec_Vec_update_usize v hash_mod l0 with | Fail _ -> () | Return v0 -> () end @@ -3077,18 +3077,18 @@ let hash_map_remove_back_lem_refin #t self key = begin assert(l == index v hash_mod); assert(length (list_t_v #t l) > 0); - length_flatten_index (hash_map_t_v self) hash_mod; + length_flatten_index (hashMap_t_v self) hash_mod; match usize_sub i0 1 with | Fail _ -> () | Return i3 -> begin - hash_map_remove_from_list_back_lem_refin key l; - match hash_map_remove_from_list_back t key l with + hashMap_remove_from_list_back_lem_refin key l; + match hashMap_remove_from_list_back t key l with | Fail _ -> () | Return l0 -> begin length_flatten_update (slots_t_v v) hash_mod (list_t_v l0); - match vec_index_mut_back (list_t t) v hash_mod l0 with + match alloc_vec_Vec_update_usize v hash_mod l0 with | Fail _ -> () | Return v0 -> () end @@ -3102,12 +3102,12 @@ let hash_map_remove_back_lem_refin #t self key = (**** Invariants, high-level properties *) -val hash_map_remove_from_list_s_lem +val hashMap_remove_from_list_s_lem (#t : Type0) (k : usize) (slot : slot_s t) (len : usize{len > 0}) (i : usize) : Lemma (requires (slot_s_inv len i slot)) (ensures ( - let slot' = hash_map_remove_from_list_s k slot in + let slot' = hashMap_remove_from_list_s k slot in slot_s_inv len i slot' /\ slot_s_find k slot' == None /\ (forall (k':key{k' <> k}). slot_s_find k' slot' == slot_s_find k' slot) /\ @@ -3117,14 +3117,14 @@ val hash_map_remove_from_list_s_lem )) #push-options "--fuel 1" -let rec hash_map_remove_from_list_s_lem #t key slot len i = +let rec hashMap_remove_from_list_s_lem #t key slot len i = match slot with | [] -> () | (k',v) :: slot' -> if k' <> key then begin - hash_map_remove_from_list_s_lem key slot' len i; - let slot'' = hash_map_remove_from_list_s key slot' in + hashMap_remove_from_list_s_lem key slot' len i; + let slot'' = hashMap_remove_from_list_s key slot' in assert(for_all (same_hash_mod_key len i) ((k',v)::slot'')); assert(for_all (binding_neq (k',v)) slot'); // Triggers instanciation assert(for_all (binding_neq (k',v)) slot'') @@ -3136,51 +3136,51 @@ let rec hash_map_remove_from_list_s_lem #t key slot len i = end #pop-options -val hash_map_remove_s_lem - (#t : Type0) (self : hash_map_s_nes t) (key : usize) : +val hashMap_remove_s_lem + (#t : Type0) (self : hashMap_s_nes t) (key : usize) : Lemma - (requires (hash_map_s_inv self)) + (requires (hashMap_s_inv self)) (ensures ( - let hm' = hash_map_remove_s self key in + let hm' = hashMap_remove_s self key in // The invariant is preserved - hash_map_s_inv hm' /\ + hashMap_s_inv hm' /\ // We updated the binding - hash_map_s_updated_binding self key None hm')) + hashMap_s_updated_binding self key None hm')) -let hash_map_remove_s_lem #t self key = +let hashMap_remove_s_lem #t self key = let len = length self in let hash = hash_mod_key key len in let slot = index self hash in - hash_map_remove_from_list_s_lem key slot len hash; - let slot' = hash_map_remove_from_list_s key slot in + hashMap_remove_from_list_s_lem key slot len hash; + let slot' = hashMap_remove_from_list_s key slot in let hm' = list_update self hash slot' in - assert(hash_map_s_inv self) + assert(hashMap_s_inv self) /// Final lemma about [remove'back] -val hash_map_remove_back_lem_aux - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_remove_back_lem_aux + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_remove_back t self key with + match hashMap_remove_back t self key with | Fail _ -> False | Return hm' -> - hash_map_t_inv self /\ - hash_map_t_same_params hm' self /\ + hashMap_t_inv self /\ + hashMap_t_same_params hm' self /\ // We updated the binding - hash_map_s_updated_binding (hash_map_t_v self) key None (hash_map_t_v hm') /\ - hash_map_t_v hm' == hash_map_remove_s (hash_map_t_v self) key /\ + hashMap_s_updated_binding (hashMap_t_v self) key None (hashMap_t_v hm') /\ + hashMap_t_v hm' == hashMap_remove_s (hashMap_t_v self) key /\ // The length is decremented iff the key was in the map - (let len = hash_map_t_len_s self in - let len' = hash_map_t_len_s hm' in - match hash_map_t_find_s self key with + (let len = hashMap_t_len_s self in + let len' = hashMap_t_len_s hm' in + match hashMap_t_find_s self key with | None -> len = len' | Some _ -> len = len' + 1))) -let hash_map_remove_back_lem_aux #t self key = - hash_map_remove_back_lem_refin self key; - hash_map_remove_s_lem (hash_map_t_v self) key +let hashMap_remove_back_lem_aux #t self key = + hashMap_remove_back_lem_refin self key; + hashMap_remove_s_lem (hashMap_t_v self) key /// .fsti -let hash_map_remove_back_lem #t self key = - hash_map_remove_back_lem_aux #t self key +let hashMap_remove_back_lem #t self key = + hashMap_remove_back_lem_aux #t self key diff --git a/tests/fstar/hashmap/Hashmap.Properties.fsti b/tests/fstar/hashmap/Hashmap.Properties.fsti index 0a4f0134..26c0ec06 100644 --- a/tests/fstar/hashmap/Hashmap.Properties.fsti +++ b/tests/fstar/hashmap/Hashmap.Properties.fsti @@ -18,11 +18,11 @@ type key : eqtype = usize type hash : eqtype = usize -val hash_map_t_inv (#t : Type0) (hm : hash_map_t t) : Type0 +val hashMap_t_inv (#t : Type0) (hm : hashMap_t t) : Type0 -val len_s (#t : Type0) (hm : hash_map_t t) : nat +val len_s (#t : Type0) (hm : hashMap_t t) : nat -val find_s (#t : Type0) (hm : hash_map_t t) (k : key) : option t +val find_s (#t : Type0) (hm : hashMap_t t) (k : key) : option t (*** Overloading *) @@ -32,16 +32,16 @@ val find_s (#t : Type0) (hm : hash_map_t t) (k : key) : option t /// limiting the hash collisions. /// This is expressed by the following property, which is maintained in the hash /// map invariant. -val hash_map_not_overloaded_lem (#t : Type0) (hm : hash_map_t t) : +val hashMap_not_overloaded_lem (#t : Type0) (hm : hashMap_t t) : Lemma - (requires (hash_map_t_inv hm)) + (requires (hashMap_t_inv hm)) (ensures ( // The capacity is the number of slots - let capacity = length hm.hash_map_slots in + let capacity = length hm.slots in // The max load factor defines a threshold on the number of entries: // if there are more entries than a given fraction of the number of slots, // we resize the slots vector to limit the hash collisions - let (dividend, divisor) = hm.hash_map_max_load_factor in + let (dividend, divisor) = hm.max_load_factor in // technicality: this postcondition won't typecheck if we don't reveal // that divisor > 0 (because of the division) divisor > 0 /\ @@ -63,14 +63,14 @@ val hash_map_not_overloaded_lem (#t : Type0) (hm : hash_map_t t) : (**** [new'fwd] *) /// [new] doesn't fail and returns an empty hash map -val hash_map_new_fwd_lem (t : Type0) : +val hashMap_new_lem (t : Type0) : Lemma (ensures ( - match hash_map_new_fwd t with + match hashMap_new t with | Fail _ -> False | Return hm -> // The hash map invariant is satisfied - hash_map_t_inv hm /\ + hashMap_t_inv hm /\ // The hash map has a length of 0 len_s hm = 0 /\ // It contains no bindings @@ -79,16 +79,16 @@ val hash_map_new_fwd_lem (t : Type0) : (**** [clear] *) /// [clear] doesn't fail and turns the hash map into an empty map -val hash_map_clear_fwd_back_lem - (#t : Type0) (self : hash_map_t t) : +val hashMap_clear_lem + (#t : Type0) (self : hashMap_t t) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_clear_fwd_back t self with + match hashMap_clear t self with | Fail _ -> False | Return hm -> // The hash map invariant is satisfied - hash_map_t_inv hm /\ + hashMap_t_inv hm /\ // The hash map has a length of 0 len_s hm = 0 /\ // It contains no bindings @@ -97,11 +97,11 @@ val hash_map_clear_fwd_back_lem (**** [len] *) /// [len] can't fail and returns the length (the number of elements) of the hash map -val hash_map_len_fwd_lem (#t : Type0) (self : hash_map_t t) : +val hashMap_len_lem (#t : Type0) (self : hashMap_t t) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_len_fwd t self with + match hashMap_len t self with | Fail _ -> False | Return l -> l = len_s self)) @@ -114,12 +114,12 @@ val hash_map_len_fwd_lem (#t : Type0) (self : hash_map_t t) : /// entirely encompassed by the effect of the backward function alone). /// /// [insert'fwd_back] simply inserts a binding. -val hash_map_insert_fwd_back_lem - (#t : Type0) (self : hash_map_t t) (key : usize) (value : t) : +val hashMap_insert_lem + (#t : Type0) (self : hashMap_t t) (key : usize) (value : t) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_insert_fwd_back t self key value with + match hashMap_insert t self key value with | Fail _ -> // We can fail only if: // - the key is not in the map and we thus need to add it @@ -128,7 +128,7 @@ val hash_map_insert_fwd_back_lem len_s self = usize_max | Return hm' -> // The invariant is preserved - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // [key] maps to [value] find_s hm' key == Some value /\ // The other bindings are preserved @@ -145,24 +145,24 @@ val hash_map_insert_fwd_back_lem /// [contains_key'fwd] can't fail and returns `true` if and only if there is /// a binding for key [key] -val hash_map_contains_key_fwd_lem - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_contains_key_lem + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_contains_key_fwd t self key with + match hashMap_contains_key t self key with | Fail _ -> False | Return b -> b = Some? (find_s self key))) (**** [get'fwd] *) /// [get] returns (a shared borrow to) the binding for key [key] -val hash_map_get_fwd_lem - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_get_lem + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_get_fwd t self key, find_s self key with + match hashMap_get t self key, find_s self key with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) @@ -175,12 +175,12 @@ val hash_map_get_fwd_lem /// in Rust, which gives the possibility of modifying this element in place. Then, /// upon ending the borrow, the effect of the modification is modelled in the /// translation through a call to the backward function. -val hash_map_get_mut_fwd_lem - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_get_mut_lem + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_get_mut_fwd t self key, find_s self key with + match hashMap_get_mut t self key, find_s self key with | Fail _, None -> True | Return x, Some x' -> x == x' | _ -> False)) @@ -192,11 +192,11 @@ val hash_map_get_mut_fwd_lem /// A call to [get_mut'back] must follow a call to [get_mut'fwd], which gives /// us that there must be a binding for key [key] in the map (otherwise we /// can't prove the absence of failure). -val hash_map_get_mut_back_lem - (#t : Type0) (hm : hash_map_t t) (key : usize) (ret : t) : +val hashMap_get_mut_back_lem + (#t : Type0) (hm : hashMap_t t) (key : usize) (ret : t) : Lemma (requires ( - hash_map_t_inv hm /\ + hashMap_t_inv hm /\ // A call to the backward function must follow a call to the forward // function, whose success gives us that there is a binding for the key. // In the case of *forward* functions, "success" has to be understood as @@ -207,14 +207,14 @@ val hash_map_get_mut_back_lem // "failure" is to be understood as the semantics getting stuck. // This is of course true unless we filtered the call to the forward function // because its effect is encompassed by the backward function, as with - // [hash_map_clear_fwd_back]). + // [hashMap_clear]). Some? (find_s hm key))) (ensures ( - match hash_map_get_mut_back t hm key ret with + match hashMap_get_mut_back t hm key ret with | Fail _ -> False // Can't fail | Return hm' -> // The invariant is preserved - hash_map_t_inv hm' /\ + hashMap_t_inv hm' /\ // The length is preserved len_s hm' = len_s hm /\ // [key] maps to the update value, [ret] @@ -228,12 +228,12 @@ val hash_map_get_mut_back_lem /// (the rust function *moves* it out of the map). Note that the effect of the update /// on the map is modelles through the call to [remove'back] ([remove] takes a /// mutable borrow to the hash map as parameter). -val hash_map_remove_fwd_lem - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_remove_lem + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_remove_fwd t self key with + match hashMap_remove t self key with | Fail _ -> False | Return opt_x -> opt_x == find_s self key)) @@ -243,16 +243,16 @@ val hash_map_remove_fwd_lem /// The hash map given as parameter to [remove] is given through a mutable borrow: /// hence the backward function which gives back the updated map, without the /// binding. -val hash_map_remove_back_lem - (#t : Type0) (self : hash_map_t t) (key : usize) : +val hashMap_remove_back_lem + (#t : Type0) (self : hashMap_t t) (key : usize) : Lemma - (requires (hash_map_t_inv self)) + (requires (hashMap_t_inv self)) (ensures ( - match hash_map_remove_back t self key with + match hashMap_remove_back t self key with | Fail _ -> False | Return hm' -> // The invariant is preserved - hash_map_t_inv self /\ + hashMap_t_inv self /\ // The binding for [key] is not there anymore find_s hm' key == None /\ // The other bindings are preserved diff --git a/tests/fstar/hashmap/Primitives.fst b/tests/fstar/hashmap/Primitives.fst index 71d75c11..3297803c 100644 --- a/tests/fstar/hashmap/Primitives.fst +++ b/tests/fstar/hashmap/Primitives.fst @@ -427,7 +427,7 @@ let alloc_vec_Vec_new (a : Type0) : alloc_vec_Vec a = assert_norm(length #a [] let alloc_vec_Vec_len (a : Type0) (v : alloc_vec_Vec a) : usize = length v // Helper -let alloc_vec_Vec_index_usize (#a : Type0) (v : alloc_vec_Vec a) (i : usize) (x : a) : result a = +let alloc_vec_Vec_index_usize (#a : Type0) (v : alloc_vec_Vec a) (i : usize) : result a = if i < length v then Return (index v i) else Fail Failure // Helper let alloc_vec_Vec_update_usize (#a : Type0) (v : alloc_vec_Vec a) (i : usize) (x : a) : result (alloc_vec_Vec a) = @@ -704,6 +704,22 @@ let alloc_vec_Vec_coreopsindexIndexMutInst (t idx : Type0) (*** Theorems *) +let alloc_vec_Vec_index_eq (#a : Type0) (v : alloc_vec_Vec a) (i : usize) : + Lemma ( + alloc_vec_Vec_index a usize (core_slice_index_usize_coresliceindexSliceIndexInst a) v i == + alloc_vec_Vec_index_usize v i) + [SMTPat (alloc_vec_Vec_index a usize (core_slice_index_usize_coresliceindexSliceIndexInst a) v i)] + = + admit() + +let alloc_vec_Vec_index_mut_eq (#a : Type0) (v : alloc_vec_Vec a) (i : usize) : + Lemma ( + alloc_vec_Vec_index_mut a usize (core_slice_index_usize_coresliceindexSliceIndexInst a) v i == + alloc_vec_Vec_index_usize v i) + [SMTPat (alloc_vec_Vec_index_mut a usize (core_slice_index_usize_coresliceindexSliceIndexInst a) v i)] + = + admit() + let alloc_vec_Vec_index_mut_back_eq (#a : Type0) (v : alloc_vec_Vec a) (i : usize) (x : a) : Lemma ( alloc_vec_Vec_index_mut_back a usize (core_slice_index_usize_coresliceindexSliceIndexInst a) v i x == |