(* Hash Consign modules *)
-
-module type Oracle_fixpoint =
-sig
- type t = StateSet.t*StateSet.t*StateSet.t*((StateSet.elt*Formula.t) list)*QName.t
- val equal : t -> t -> bool
- val hash : t -> int
-end
-
-type dStateS = StateSet.t*StateSet.t
-module type Run_fixpoint =
-sig
- type t = dStateS*dStateS*dStateS*(State.t*Formula.t) list*QName.t
- val equal : t -> t -> bool
- val hash : t -> int
-end
-
-module Oracle_fixpoint : Oracle_fixpoint = struct
- type t =
- StateSet.t*StateSet.t*StateSet.t*((StateSet.elt*Formula.t) list)*QName.t
- let equal (s,l,r,list,t) (s',l',r',list',t') = StateSet.equal s s' &&
- StateSet.equal l l' && StateSet.equal r r' && QName.equal t t'
- let hash (s,l,r,list,t) =
- HASHINT4(StateSet.hash s, StateSet.hash l, StateSet.hash r, QName.hash t)
-end
-
-let dequal (x,y) (x',y') = StateSet.equal x x' && StateSet.equal y y'
-let dhash (x,y) = HASHINT2(StateSet.hash x, StateSet.hash y)
-module Run_fixpoint : Run_fixpoint = struct
- type t = dStateS*dStateS*dStateS*(State.t*Formula.t) list*QName.t
- let equal (s,l,r,list,t) (s',l',r',list',t') = dequal s s' &&
- dequal l l' && dequal r r' && QName.equal t t'
- let hash (s,l,r,list,t) =
- HASHINT4(dhash s, dhash l, dhash r, QName.hash t)
-end
-
+open Hconsed_run
module HashOracle = Hashtbl.Make(Oracle_fixpoint)
module HashRun = Hashtbl.Make(Run_fixpoint)
let map_leaf asta = (Asta.bot_states_s asta, StateSet.empty)
(* Build the Oracle *)
-let rec bu_oracle asta run tree tnode hashOracle=
+let rec bu_oracle asta run tree tnode hashOracle hashEval =
let node = Tree.preorder tree tnode in
if Tree.is_leaf tree tnode
then
let fnode,nnode = (* their preorders *)
(Tree.preorder tree tfnode, Tree.preorder tree tnnode) in
begin
- bu_oracle asta run tree tfnode hashOracle;
- bu_oracle asta run tree tnnode hashOracle;
+ bu_oracle asta run tree tfnode hashOracle hashEval;
+ bu_oracle asta run tree tnnode hashOracle hashEval;
(* add states which satisfy a transition *)
let rec result set qfr qnr flag = function
| [] -> set,flag
| (q,form) :: tl ->
- if Formula.eval_form (set,qfr,qnr) form (* evaluates the formula*)
+ if Formula.eval_form (set,qfr,qnr) form hashEval
then
if StateSet.mem q set
then result set qfr qnr 0 tl
end
(* Build the over-approx. of the maximal run *)
-let rec bu_over_max asta run tree tnode hashOver =
+let rec bu_over_max asta run tree tnode hashOver hashInfer =
if (Tree.is_leaf tree tnode) (* BU_oracle has already created the map *)
then
()
let tfnode = Tree.first_child_x tree tnode
and tnnode = Tree.next_sibling tree tnode in
begin
- bu_over_max asta run tree tfnode hashOver;
- bu_over_max asta run tree tnnode hashOver;
+ bu_over_max asta run tree tfnode hashOver hashInfer;
+ bu_over_max asta run tree tnnode hashOver hashInfer;
let (fnode,nnode) =
(Tree.preorder tree tfnode, Tree.preorder tree tnnode)
and node = Tree.preorder tree tnode in
| (q,form) :: tl ->
if StateSet.mem q set
then result set qf qn 0 list_tr tl
- else if Formula.infer_form (set,resultr) qf qn form
+ else if Formula.infer_form (set,resultr) qf qn form hashInfer
then result (StateSet.add q set) qf qn 1 list_tr tl
else result set qf qn 0 list_tr tl in
let result_set () =
(* Build the maximal run *)
-let rec tp_max asta run tree tnode hashMax =
+let rec tp_max asta run tree tnode hashMax hashInfer =
if (Tree.is_leaf tree tnode) (* BU_oracle has already created the map *)
then
()
and result_st_q self_q queue flag = function (*for computing the fixed p*)
| [] -> flag,queue
| form :: tl ->
- if Formula.infer_form (self_q,self_r) qf qn form
+ if Formula.infer_form (self_q,self_r) qf qn form hashInfer
then begin
let q_cand,_,_ = Formula.st form in
StateSet.iter (fun x -> Queue.push x queue) q_cand;
| [] -> []
| (q,form) :: tl ->
if (StateSet.mem q (fst self)) && (* infers & trans. can start here *)
- (Formula.infer_form self qf qn form)
+ (Formula.infer_form self qf qn form hashInfer)
then form :: (result self qf qn tl)
else result self qf qn tl in
let list_form =
then ()
else NodeHash.replace run nnode (StateSet.inter qnq qr,qnr);
(* indeed we delete all states from self transitions! *)
- tp_max asta run tree tfnode hashMax;
- tp_max asta run tree tnnode hashMax;
+ tp_max asta run tree tfnode hashMax hashInfer;
+ tp_max asta run tree tnnode hashMax hashInfer;
end;
end
let size_tree = 10000 in (* todo (Tree.size ?) *)
let size_hcons_O = 1000 in (* todo size Hashtbl *)
let size_hcons_M = 1000 in (* todo size Hashtbl *)
+ let size_hcons_F = 1000 in (* todo size Hashtbl *)
let map = NodeHash.create size_tree in
let hashOracle = HashOracle.create(size_hcons_O) in
- bu_oracle asta map tree (Tree.root tree) hashOracle;
+ let hashEval = Formula.HashEval.create(size_hcons_F) in
+ let hashInfer = Formula.HashInfer.create(size_hcons_F) in
+ bu_oracle asta map tree (Tree.root tree) hashOracle hashEval;
HashOracle.clear hashOracle;
+ Formula.HashEval.clear hashEval;
if flag > 0 then begin
let hashOver = HashRun.create(size_hcons_M) in
let hashMax = HashRun.create(size_hcons_M) in
- bu_over_max asta map tree (Tree.root tree) hashOver;
+ bu_over_max asta map tree (Tree.root tree) hashOver hashInfer;
if flag = 2
then
- tp_max asta map tree (Tree.root tree) hashMax
+ tp_max asta map tree (Tree.root tree) hashMax hashInfer
else ();
HashRun.clear hashOver;
HashRun.clear hashMax;