000007| | n,l::ls -> (*[161207296]*)let ls,rs = split (n-1) ls in (*[161207296]*)l::ls,rs
000008|
000009|
000010| (** Generic lattice tests *)
000011|
000012| module type LATTICE_TOPLESS =
000013| sig
000014| val name : string
000015| type elem
000016| val leq : elem -> elem -> bool
000017| val join : elem -> elem -> elem
000018| val meet : elem -> elem -> elem
000019| val bot : elem
000020| (* val top : elem *)
000021| val eq : elem -> elem -> bool
000022| val to_string : elem -> string
000023| val pprint : elem -> unit
000024| val arb_elem : elem Arbitrary.t
000025| val equiv_pair : (elem * elem) Arbitrary.t
000026| val arb_elem_le : elem -> elem Arbitrary.t
000027| end
000028|
000029| module type LATTICE =
000030| sig
000031| include LATTICE_TOPLESS
000032| val top : elem
000033| end
000034|
000035| module GenericTests (L : LATTICE_TOPLESS) =
000036| struct
000037| (* Helpers for generating pairs and triples *)
000038| let arb_pair = (*[15]*)Arbitrary.pair L.arb_elem L.arb_elem
000039| let arb_triple = (*[15]*)Arbitrary.triple L.arb_elem L.arb_elem L.arb_elem
000040|
000041| let ord_pair = (*[15]*)Arbitrary.(L.arb_elem >>= fun e -> (*[105000]*)pair (L.arb_elem_le e) (return e))
000042| let ord_triple = (*[15]*)Arbitrary.(L.arb_elem >>= fun e ->
000043| (*[15000]*)L.arb_elem_le e >>= fun e' ->
000044| (*[15000]*)L.arb_elem_le e' >>= fun e'' -> (*[15000]*)return (e'',e',e))
000045|
000046| (* Helpers for pretty printing pairs and triples *)
000047| let pp_pair = (*[15]*)PP.pair L.to_string L.to_string
000048| let pp_triple = (*[15]*)PP.triple L.to_string L.to_string L.to_string
000049|
000053|
000054| (* Generic lattice property tests *)
000055| let leq_refl = (* forall a. a <= a *)
000056| (*[15]*)mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("leq reflexive in " ^ L.name) ~size:size
000057| L.arb_elem
000058| (fun a -> (*[15000]*)L.leq a a)
000059|
000060| let leq_trans = (* forall a,b,c. a <= b /\ b <= c => a <= c *)
000061| (*[15]*)mk_test ~n:1000 ~pp:pp_triple ~limit:1 ~name:("leq transitive in " ^ L.name) ~size:size_triple
000062| ord_triple (* arb_triple *)
000063| (fun (a,b,c) -> (*[15000]*)Prop.assume (L.leq a b);
000064| (*[15000]*)Prop.assume (L.leq b c);
000065| (*[15000]*)L.leq a c)
000066|
000067| let leq_antisym = (* forall a,b. a <= b /\ b <= a => a = b *)
000068| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("leq anti symmetric in " ^ L.name) ~size:size_pair
000069| L.equiv_pair (* Alternatively: Arbitrary.(choose [L.equiv_pair; ord_pair; ord_pair >>= fun (a,b) -> return (b,a)]) *)
000070| (fun (a,b) -> (*[15000]*)Prop.assume (L.leq a b);
000071| (*[15000]*)Prop.assume (L.leq b a);
000072| (*[15000]*)L.eq a b)
000073|
000074| (*let top_is_upperbound = (* forall a. a <= top *)
000075| mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("top is upper bound in " ^ L.name)
000076| ~size:(fun a -> String.length (pp_pair a))
000077| L.arb_elem
000078| (fun a -> L.(leq a top)) *)
000079|
000080| let bot_is_lowerbound = (* forall a. bot <= a *)
000081| (*[15]*)mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("bot is lower bound in " ^ L.name) ~size:size
000082| L.arb_elem
000083| (fun a -> (*[15000]*)L.(leq bot a))
000084|
000085| let join_comm = (* forall a,b. a \/ b = b \/ a *)
000086| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("join commutative in " ^ L.name) ~size:size_pair
000087| arb_pair
000088| (fun (a,b) -> (*[15000]*)L.(eq (join a b) (join b a)))
000089|
000090| let join_assoc = (* forall a,b,c. (a \/ b) \/ c = a \/ (b \/ c) *)
000091| (*[15]*)mk_test ~n:1000 ~pp:pp_triple ~limit:1 ~name:("join associative in " ^ L.name) ~size:size_triple
000092| arb_triple
000093| (fun (a,b,c) -> (*[15000]*)L.(eq (join (join a b) c) (join a (join b c)) ))
000094|
000095| let join_idempotent = (* forall a. a \/ a = a *)
000096| (*[15]*)mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("join idempotent in " ^ L.name) ~size:size
000097| L.arb_elem
000098| (fun a -> (*[15000]*)L.(eq (join a a) a))
000099|
000100| let meet_comm = (* forall a,b. a /\ b = b /\ a *)
000101| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("meet commutative in " ^ L.name) ~size:size_pair
000102| arb_pair
000103| (fun (a,b) -> (*[15000]*)L.(eq (meet a b) (meet b a)))
000104|
000105| let meet_assoc = (* forall a,b,c. (a /\ b) /\ c = a /\ (b /\ c) *)
000106| (*[15]*)mk_test ~n:1000 ~pp:pp_triple ~limit:1 ~name:("meet associative in " ^ L.name) ~size:size_triple
000107| arb_triple
000108| (fun (a,b,c) -> (*[15000]*)L.(eq (meet (meet a b) c) (meet a (meet b c)) ))
000109|
000110| let meet_idempotent = (* forall a. a /\ a = a *)
000111| (*[15]*)mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("meet idempotent in " ^ L.name) ~size:size
000112| L.arb_elem
000113| (fun a -> (*[15000]*)L.(eq (meet a a) a))
000114|
000115| let join_meet_absorption = (* forall a,b. a \/ (a /\ b) = a *)
000116| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("join meet absorbtion in " ^ L.name) ~size:size_pair
000117| arb_pair
000118| (fun (a,b) -> (*[15000]*)L.(eq (join a (meet a b)) a))
000119|
000120| let meet_join_absorption = (* forall a,b. a /\ (a \/ b) = a *)
000121| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("meet join absorbtion in " ^ L.name) ~size:size_pair
000122| arb_pair
000123| (fun (a,b) -> (*[15000]*)L.(eq (meet a (join a b)) a))
000124|
000125| let leq_compat_join = (* forall a,b. a < b ==> a \/ b = b *)
000126| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("leq compatible join in " ^ L.name) ~size:size_pair
000127| ord_pair (*arb_pair*)
000128| (fun (a,b) -> (*[15000]*)Prop.assume (L.leq a b);
000129| (*[15000]*)L.(eq (join a b) b))
000130|
000131| let join_compat_leq = (* forall a,b. a \/ b = b ==> a < b *)
000132| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("join compatible leq in " ^ L.name) ~size:size_pair
000133| ord_pair (*arb_pair*)
000134| (fun (a,b) -> (*[15000]*)Prop.assume L.(eq (join a b) b);
000135| ((*[15000]*)L.leq a b))
000136|
000137| let join_compat_meet = (* forall a,b. a \/ b = b ==> a /\ b = a *)
000138| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("join compatible meet in " ^ L.name) ~size:size_pair
000139| ord_pair (*arb_pair*)
000140| (fun (a,b) -> (*[15000]*)Prop.assume L.(eq (join a b) b);
000141| (*[15000]*)L.(eq (meet a b) a))
000142|
000143| let meet_compat_join = (* forall a,b. a /\ b = a ==> a \/ b = b *)
000144| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("meet compatible join in " ^ L.name) ~size:size_pair
000145| ord_pair (*arb_pair*)
000146| (fun (a,b) -> (*[15000]*)Prop.assume L.(eq (meet a b) a);
000147| (*[15000]*)L.(eq (join a b) b))
000148|
000149| let meet_compat_leq = (* forall a,b. a /\ b = a ==> a <= b *)
000150| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("meet compatible leq in " ^ L.name) ~size:size_pair
000151| ord_pair (*arb_pair*)
000152| (fun (a,b) -> (*[15000]*)Prop.assume (L.(eq (meet a b) a));
000153| (*[15000]*)L.leq a b)
000154|
000155| let leq_compat_meet = (* forall a,b. a <= b ==> a /\ b = a *)
000156| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("leq compatible meet in " ^ L.name) ~size:size_pair
000157| ord_pair (*arb_pair*)
000158| (fun (a,b) -> (*[15000]*)Prop.assume (L.leq a b);
000159| (*[15000]*)L.(eq (meet a b) a))
000160|
000161| (* Consistency check: generated ordered pairs are in fact ordered *)
000162| let check_ordering =
000163| (*[15]*)mk_test ~n:1000 ~pp:pp_pair ~limit:1 ~name:("generated ordered pairs consistent in " ^ L.name) ~size:size_pair
000164| ord_pair (fun (a,b) -> (*[15000]*)L.leq a b)
000165|
000166| let pp_pair = (*[15]*)PP.pair L.to_string L.to_string
000167| let ord_pair = (*[15]*)Arbitrary.(L.arb_elem >>= fun v -> (*[2000]*)pair (L.arb_elem_le v) (return v))
000168|
000169| let suite =
000170| [ (*[15]*)leq_refl; leq_trans; leq_antisym;
000171| (*top_is_upperbound;*)
000172| bot_is_lowerbound;
000173| join_comm; join_assoc; join_idempotent;
000174| meet_comm; meet_assoc; meet_idempotent;
000175| join_meet_absorption; meet_join_absorption;
000176| (* compatibility *)
000177| leq_compat_join; join_compat_leq;
000178| join_compat_meet; meet_compat_join;
000179| meet_compat_leq; leq_compat_meet;
000180| check_ordering; ]
000181| end
000182|
000183| module GenericTopTests (L : LATTICE) =
000184| struct
000185| let top_is_upperbound = (* forall a. a <= top *)
000186| (*[5]*)mk_test ~n:1000 ~pp:L.to_string ~limit:1 ~name:("top is upper bound in " ^ L.name)
000199|
000200| module type ARB_ARG =
000201| sig
000202| (* val name : string *)
000203| type elem
000204| val arb_elem : elem Arbitrary.t
000205| val to_string : elem -> string
000206| end
000207|
000208| module MkArbListArg (A : ARB_ARG) =
000209| struct
000210| type elem = A.elem list
000211| let arb_elem = (*[2]*)Arbitrary.(list ~len:(int 20) A.arb_elem)
000212| let to_string = (*[2]*)PP.list A.to_string
000213| end
000214|
000215| let op_monotone (*[1]*)(type a) (type b) (module PL : LATTICE_TOPLESS with type elem = a)
000216| (module RL : LATTICE_TOPLESS with type elem = b) k =
000217| (*[198]*)let ord_pair = Arbitrary.(PL.arb_elem >>= fun e -> (*[198000]*)pair (PL.arb_elem_le e) (return e)) in
000218| (*[198]*)k (PP.pair PL.to_string PL.to_string,
000219| ord_pair,
000220| (fun op (v,v') -> (*[198000]*)Prop.assume (PL.leq v v'); (*[198000]*)RL.leq (op v) (op v')),
000221| "monotone",
000222| 1)
000223|
000224| let op_invariant (*[1]*)(type a) (type b) (module PL : LATTICE_TOPLESS with type elem = a)
000225| (module RL : LATTICE_TOPLESS with type elem = b) k =
000226| (*[205]*)k (PP.pair PL.to_string PL.to_string,
000227| PL.equiv_pair,
000228| (fun op (v,v') -> (*[205000]*)Prop.assume (PL.eq v v'); (*[205000]*)RL.eq (op v) (op v')),
000229| "invariant",
000230| 1)
000231|
000232| let op_strict (*[1]*)(type a) (type b) (module PL : LATTICE_TOPLESS with type elem = a)
000233| (module RL : LATTICE_TOPLESS with type elem = b) k =
000234| (*[170]*)k (PL.to_string,
000235| Arbitrary.return PL.bot,
000236| (fun op bot -> (*[170000]*)Prop.assume (PL.eq bot PL.bot); (*[170000]*)RL.eq (op bot) RL.bot),
000237| "strict",
000238| 1)
000239|
000240| let op_distributive (*[1]*)(type a) (type b) (module PL : LATTICE_TOPLESS with type elem = a)
000241| (module RL : LATTICE_TOPLESS with type elem = b) k =
000246| "distributive",
000247| 1)
000248|
000249| let pw_left (*[1]*)(type a) (module PL : ARB_ARG with type elem = a) op_prop m1 m2 k =
000250| (*[300]*)op_prop m1 m2 (fun (subpp,subgen,prop,pname,leftargs) -> (*[300]*)k (PP.pair PL.to_string subpp,
000251| Arbitrary.pair PL.arb_elem subgen,
000252| (fun op (a,b) -> (*[300000]*)prop (op a) b),
000253| pname,
000254| leftargs+1))
000255|
000256| let pw_right (*[1]*)(type a) (module PL : ARB_ARG with type elem = a) op_prop m1 m2 k =
000257| (*[353]*)op_prop m1 m2 (fun (subpp,subgen,prop,pname,leftargs) -> (*[353]*)k (PP.pair subpp PL.to_string,
000258| Arbitrary.pair subgen PL.arb_elem,
000259| (fun op (p,st) -> (*[353000]*)prop (fun v -> (*[608000]*)op v st) p),
000260| pname,
000261| leftargs))
000262|
000263| let ( ---> ) (*[1]*)(type e) (type e') = fun a -> fun (b : (module LATTICE_TOPLESS with type elem = e)) ->
000264| fun k -> (*[456]*)a (fun (l,optranl,r,optranr,prop) ->
000265| (*[456]*)let module R = (val r : LATTICE_TOPLESS with type elem = e') in (* manual "upcast" *)
000266| let r = (module R : ARB_ARG with type elem = e') in (* the module type *)
000267| (*[456]*)k (l,(fun prop -> (*[222]*)optranl (pw_left r prop)),
000268| b,(fun prop -> (*[234]*)optranr (pw_right r prop)),
000269| prop))
000270| let ( -<-> ) (*[1]*)(type e) = fun a -> fun (b : (module LATTICE_TOPLESS with type elem = e)) ->
000285| ~name:(Printf.sprintf "'%s %s in argument %i'" opname pname leftargs)
000286| gen (prop op))
000287|
000288| let ( =:: ) a (b,c) = (*[98]*)finalize a (b,c)
000289|
000290| let for_op = (fun (l,_,r,optrans,prop) (opname,op) ->
000291| (*[475]*)finalize (optrans prop l r) (opname,op))
000292| let ( =: ) a (b,c) = (*[475]*)a for_op (b,c)
000293|
000294|
000295| (** A number of reusable lattices *)
000296|
000297| (* Note: the following module represents the Boolean lattice: *)
000298| (* {true,false} under reverse implication ordering, *)
000299| (* bot = true <== true <== false <== false = top *)
000300| module Bool =
000301| struct
000302| let name = (*[1]*)"Boolean lattice"
000303| type elem = bool
000304| let leq a b = (*[22000]*)if a then (*[10616]*)true else ((*[11384]*)not b)
000305| let join = (*[1]*)(&&)
000306| let meet = (*[1]*)(||)
000307| let bot = (*[1]*)true
000308| let top = (*[1]*)false
000309| let eq = (*[1]*)(=)
000310| let to_string = (*[1]*)string_of_bool
000311| let pprint = (*[1]*)Format.printf "%b"
000312| (* The below ones are generic *)
000313| let arb_elem = (*[1]*)Arbitrary.among [bot; top]
000314| let equiv_pair = (*[1]*)Arbitrary.(lift (fun a -> ((*[1000]*)a,a)) arb_elem)
000315| let arb_elem_le e = (*[9000]*)if e = top then (*[4258]*)arb_elem else (*[4742]*)Arbitrary.return bot
000316| end
000317|
000318| (* Note: the following module represents the dual Boolean lattice: *)
000319| (* {true,false} under implication ordering, *)
000320| (* bot = false <== false <== true <== true = top *)
000321| module DBool =
000322| struct
000323| let name = (*[1]*)"Dual Boolean lattice"
000324| type elem = bool
000325| let leq a b = (*[20000]*)if a then (*[7924]*)b else (*[12076]*)true
000326| let join = (*[1]*)(||)
000327| let meet = (*[1]*)(&&)
000328| let bot = (*[1]*)false
000329| let top = (*[1]*)true
000330| let eq = (*[1]*)(=)
000331| let to_string = (*[1]*)string_of_bool
000332| let pprint = (*[1]*)Format.printf "%b"
000333| (* The below ones are generic *)
000334| let arb_elem = (*[1]*)Arbitrary.among [bot; top]
000335| let equiv_pair = (*[1]*)Arbitrary.(lift (fun a -> ((*[1000]*)a,a)) arb_elem)
000336| let arb_elem_le e = (*[9000]*)if e = top then (*[4330]*)arb_elem else (*[4670]*)Arbitrary.return bot
000337| end
000338|
000339| module GenBoolTests = GenericTests(Bool)
000340| module GenBoolTopTests = GenericTopTests(Bool)
000341| module GenDBoolTests = GenericTests(DBool)
000342| module GenDBoolTopTests = GenericTopTests(DBool)
000343|
000344| module MkPairLattice (A : LATTICE_TOPLESS) (B : LATTICE_TOPLESS)
000345| = struct
000346| let name = (*[3]*)"(" ^ A.name ^ " * " ^ B.name ^ ") pair lattice"
000347| type elem = A.elem * B.elem
000348| let leq p p' = (*[91920]*)A.leq (fst p) (fst p') && (*[91920]*)B.leq (snd p) (snd p')
000349| let join p p' = ((*[39000]*)A.join (fst p) (fst p'), B.join (snd p) (snd p'))
000350| let meet p p' = ((*[39000]*)A.meet (fst p) (fst p'), B.meet (snd p) (snd p'))
000351| let bot = ((*[3]*)A.bot, B.bot)
000352| let eq p p' = (*[167000]*)A.eq (fst p) (fst p') && (*[167000]*)B.eq (snd p) (snd p')
000353| let to_string = (*[3]*)PP.pair A.to_string B.to_string