(* 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 hashRun =
+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 hashRun;
- bu_over_max asta run tree tnnode hashRun;
+ 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 () =
- try HashRun.find hashRun ((StateSet.empty,resultr),qf,qn,list_tr,lab)
+ try HashRun.find hashOver ((StateSet.empty,resultr),qf,qn,list_tr,lab)
with _ -> let res = result StateSet.empty qf qn 0 list_tr list_tr in
- HashRun.add hashRun
+ HashRun.add hashOver
((StateSet.empty,resultr), qf,qn,list_tr,lab) res;
res in
(* we keep the old recognizing states set *)
(* Build the maximal run *)
-let rec tp_max asta run tree tnode hashRun =
+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;
end
else result_st_q self_q queue flag tl in
let rec comp_acc_self self_q_i queue = (* compute the fixed point *)
- if Queue.is_empty queue
+ if Queue.is_empty queue (* todo: to be hconsigned? *)
then self_q_i
else
let q = Queue.pop queue in
let self,queue_init = result_q self_q (Queue.create()) list_tr in
let self_q = comp_acc_self self_q queue_init in
NodeHash.replace run node (self_q,self_r);
- (* From now, the correct set of states is mapped to node! *)
- let rec result = function
+ (* From now, the correct set of states is mapped to (self) node! *)
+ let rec result self qf qn = function
| [] -> []
| (q,form) :: tl ->
- if (StateSet.mem q self) && (* infers & trans. can start here *)
- (Formula.infer_form (self_q,self_r) qf qn form)
- then form :: (result tl)
- else result tl in
- let list_form = result list_tr in (* tran. candidates *)
+ if (StateSet.mem q (fst self)) && (* infers & trans. can start here *)
+ (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 =
+ try HashRun.find hashMax ((self_q,self_r),qf,qn,list_tr,lab)
+ with _ -> let res = result (self_q,self_r) qf qn list_tr in
+ HashRun.add hashMax ((self_q,self_r),qf,qn,list_tr,lab) res;
+ res in
(* compute states occuring in transition candidates *)
let rec add_st (ql,qr) = function
| [] -> ql,qr
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 hashRun;
- tp_max asta run tree tnnode hashRun;
+ 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 hashRun = HashRun.create(size_hcons_M) in
- bu_over_max asta map tree (Tree.root tree) hashRun;
+ 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 hashInfer;
if flag = 2
then
- tp_max asta map tree (Tree.root tree) hashRun
+ tp_max asta map tree (Tree.root tree) hashMax hashInfer
else ();
- HashRun.clear hashRun;
+ HashRun.clear hashOver;
+ HashRun.clear hashMax;
end
else ();
map
projects / tatoo.git / blobdiff