library colibrilib.tagtbl — module Tagtblmodule Tagtbl : TagtblIntf64
Implemented
use int.Int66use mach.int.Int6367use map.Map68use map.Const69use seq.Seq70use mach.array.Array637172clone export S {… begin (* cloned colibrilib.tagtbl.S *) type key val function tag key : int63 axiom tag_correct end } with axiom tag_correct73
The keys of defined are stored at their tag in arr
Valid (21ms) (colibri2)type t 'a = {76arr: array 'a;77ghost mutable contents: map key 'a;78ghost defined: key -> bool;79ghost length: int;80}81invariant { length = arr.Array63.length - 1 }82invariant { forall k. defined k -> 0 <= tag k <= length }83invariant { forall k. defined k -> Map.get contents k = Seq.get arr.elts (tag k) }84by {85arr = (make 0 (any 'a): array 'a);86contents = (const (any 'a): map key 'a);87defined = (fun _ -> false);88length = -1;89}9091function ([]) (h: t 'a) (k: key) : 'a = Map.get h.contents k9293predicate mem (k: key) (h: t 'a) = h.defined k94Valid (25ms) (colibri2)95let create (s: int63) (def: 'a) (ghost defined: key -> bool) : t 'a96requires { forall k. defined k -> 0 <= tag k <= s }97requires { -1 <= s < max_int63 }98ensures { result.contents = const def }99ensures { result.defined = defined }100ensures { result.length = s }101=102{ arr = make (s + 1) def; contents = const def; defined = defined; length = to_int s }103Valid (22ms) (colibri2)104let function max_tags (h: t 'a) : int63105ensures { result = h.length }106=107Array63.length h.arr - 1108Valid (191ms) (cvc5)109let set (h: t 'a) (k: key) (v: 'a) : unit110requires { mem k h }111writes { h.arr.elts, h.contents }112ensures { h.contents = Map.set (old h.contents) k v }113=114h.arr[tag k] <- v;115h.contents <- Map.set h.contents k v116Valid (24ms) (colibri2)117let find (h: t 'a) (k: key) : 'a118requires { mem k h }119ensures { result = h[k] }120=121h.arr[tag k]122123end124