X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=ata.ml;h=90458a31289d29d0f966c4196dfa927a7d53f55c;hb=9a1792faff5e38231a74f9e761a7ff94aae5e6d9;hp=7a5a64d7087f78edb2f54960752f67f226b2f15c;hpb=c5f06d325240c808a9be4d71e20fc01969420bb3;p=SXSI%2Fxpathcomp.git diff --git a/ata.ml b/ata.ml index 7a5a64d..90458a3 100644 --- a/ata.ml +++ b/ata.ml @@ -34,6 +34,7 @@ struct | Or of 'hcons * 'hcons | And of 'hcons * 'hcons | Atom of ([ `Left | `Right | `LLeft | `RRight ]*bool*State.t) + type 'hcons node = { pos : 'hcons expr; mutable neg : 'hcons; @@ -42,34 +43,33 @@ struct } external hash_const_variant : [> ] -> int = "%identity" - module rec HNode : Hcons.S with type data = Node.t = Hcons.Make (Node) - and Node : Hashtbl.HashedType with type t = HNode.t node = + module rec Node : Hcons.S with type data = Data.t = Hcons.Make (Data) + and Data : Hashtbl.HashedType with type t = Node.t node = struct - type t = HNode.t node + type t = Node.t node let equal x y = x.size == y.size && match x.pos,y.pos with - | False,False - | True,True -> true - | Or(xf1,xf2),Or(yf1,yf2) - | And(xf1,xf2),And(yf1,yf2) -> (HNode.equal xf1 yf1) && (HNode.equal xf2 yf2) - | Atom(d1,p1,s1), Atom(d2,p2,s2) -> d1 == d2 && (p1==p2) && s1 == s2 - | _ -> false + | a,b when a == b -> true + | Or(xf1,xf2),Or(yf1,yf2) + | And(xf1,xf2),And(yf1,yf2) -> (xf1 == yf1) && (xf2 == yf2) + | Atom(d1,p1,s1), Atom(d2,p2,s2) -> d1 == d2 && (p1==p2) && s1 == s2 + | _ -> false let hash f = match f.pos with | False -> 0 | True -> 1 - | Or (f1,f2) -> HASHINT3(PRIME2,HNode.uid f1,HNode.uid f2) - | And (f1,f2) -> HASHINT3(PRIME3,HNode.uid f1,HNode.uid f2) + | Or (f1,f2) -> HASHINT3(PRIME2,f1.Node.id, f2.Node.id) + | And (f1,f2) -> HASHINT3(PRIME3,f1.Node.id,f2.Node.id) | Atom(d,p,s) -> HASHINT4(PRIME4,hash_const_variant d,vb p,s) end - type t = HNode.t - let hash = HNode.hash - let uid = HNode.uid - let equal = HNode.equal - let expr f = (HNode.node f).pos - let st f = (HNode.node f ).st - let size f = (HNode.node f).size + type t = Node.t + let hash x = x.Node.key + let uid x = x.Node.id + let equal = Node.equal + let expr f = f.Node.node.pos + let st f = f.Node.node.st + let size f = f.Node.node.size let prio f = match expr f with @@ -108,10 +108,10 @@ struct let cons pos neg s1 s2 size1 size2 = - let nnode = HNode.make { pos = neg; neg = (Obj.magic 0); st = s2; size = size2 } in - let pnode = HNode.make { pos = pos; neg = nnode ; st = s1; size = size1 } + let nnode = Node.make { pos = neg; neg = (Obj.magic 0); st = s2; size = size2 } in + let pnode = Node.make { pos = pos; neg = nnode ; st = s1; size = size1 } in - (HNode.node nnode).neg <- pnode; (* works because the neg field isn't taken into + (Node.node nnode).neg <- pnode; (* works because the neg field isn't taken into account for hashing ! *) pnode,nnode @@ -127,7 +127,7 @@ struct | `RRight -> empty_triple,(StateSet.empty,si,si) in fst (cons (Atom(d,p,s)) (Atom(d,not p,s)) ss ss 1 1) - let not_ f = (HNode.node f).neg + let not_ f = f.Node.node.neg let union_hex ((l1,ll1,lll1),(r1,rr1,rrr1)) ((l2,ll2,lll2),(r2,rr2,rrr2)) = (StateSet.mem_union l1 l2 ,StateSet.mem_union ll1 ll2,StateSet.mem_union lll1 lll2), (StateSet.mem_union r1 r2 ,StateSet.mem_union rr1 rr2,StateSet.mem_union rrr1 rrr2) @@ -224,6 +224,13 @@ module Formlist = struct let print ppf fl = iter (fun t -> Transition.print ppf t; Format.pp_print_newline ppf ()) fl end + +module Formlistlist = +struct + include Hlist.Make(Formlist) + let print ppf fll = + iter (fun fl -> Formlist.print ppf fl; Format.pp_print_newline ppf ())fll +end type 'a t = { id : int; @@ -375,7 +382,7 @@ let tags_of_state a q = module type ResultSet = sig type t - type elt = [` Tree] Tree.node + type elt = [` Tree ] Tree.node val empty : t val cons : elt -> t -> t val concat : t -> t -> t @@ -505,11 +512,13 @@ END let mk_fun f s = D_IGNORE_(register_funname f s,f) let mk_app_fun f arg s = let g = f arg in D_IGNORE_(register_funname g ((get_funname f) ^ " " ^ s), g) + let mk_app_fun2 f arg1 arg2 s = let g = f arg1 arg2 in + D_IGNORE_(register_funname g ((get_funname f) ^ " " ^ s), g) let string_of_ts tags = (Ptset.Int.fold (fun t a -> a ^ " " ^ (Tag.to_string t) ) tags "{")^ " }" - +(* module Algebra = struct type jump = [ `LONG | `CLOSE | `NIL ] @@ -569,7 +578,6 @@ END end - let choose_jump tagset qtags1 qtagsn a f_nil f_t1 f_s1 f_tn f_sn f_notext f_maytext = let tags1,hastext1,fin1 = inter_text tagset (tags a qtags1) in let tagsn,hastextn,finn = inter_text tagset (tags a qtagsn) in @@ -591,7 +599,7 @@ END else if (hastext1||hastextn) then (`ANY,f_maytext) else (`ANY,f_notext) - let choose_jump_down tree a b c d = + let choose_jump_down tree a b c d = choose_jump a b c d (mk_fun (fun _ -> Tree.nil) "Tree.mk_nil") (mk_fun (Tree.tagged_child tree) "Tree.tagged_child") @@ -610,65 +618,211 @@ END (mk_fun (Tree.select_foll_ctx tree) "Tree.select_foll_ctx") (mk_fun (Tree.next_element_ctx tree) "Tree.node_element_ctx") (mk_fun (Tree.next_sibling_ctx tree) "Tree.node_sibling_ctx") - +*) + module Algebra = + struct + type jump = [ `NIL | `ANY |`ANYNOTEXT | `JUMP ] + type t = jump*Ptset.Int.t*Ptset.Int.t + let jts = function + | `JUMP -> "JUMP" + | `NIL -> "NIL" + | `ANY -> "ANY" + | `ANYNOTEXT -> "ANYNOTEXT" + let merge_jump (j1,c1,l1) (j2,c2,l2) = + match j1,j2 with + | _,`NIL -> (j1,c1,l1) + | `NIL,_ -> (j2,c2,l2) + | `ANY,_ -> (`ANY,Ptset.Int.empty,Ptset.Int.empty) + | _,`ANY -> (`ANY,Ptset.Int.empty,Ptset.Int.empty) + | `ANYNOTEXT,_ -> + if Ptset.Int.mem Tag.pcdata (Ptset.Int.union c2 l2) then + (`ANY,Ptset.Int.empty,Ptset.Int.empty) + else + (`ANYNOTEXT,Ptset.Int.empty,Ptset.Int.empty) + | _,`ANYNOTEXT -> + if Ptset.Int.mem Tag.pcdata (Ptset.Int.union c1 l1) then + (`ANY,Ptset.Int.empty,Ptset.Int.empty) + else + (`ANYNOTEXT,Ptset.Int.empty,Ptset.Int.empty) + | `JUMP,`JUMP -> (`JUMP, Ptset.Int.union c1 c2,Ptset.Int.union l1 l2) - module SetTagKey = - struct - type t = Tag.t*SList.t - let equal (t1,s1) (t2,s2) = t1 == t2 && s1 == s2 - let hash (t,s) = HASHINT2(t,SList.uid s) - end + let merge_jump_list = function + | [] -> `NIL,Ptset.Int.empty,Ptset.Int.empty + | p::r -> + List.fold_left (merge_jump) p r + + let labels a s = + Hashtbl.fold + ( + fun q l acc -> + if (q == s) + then - module CachedTransTable = Hashtbl.Make(SetTagKey) - let td_trans = CachedTransTable.create 4093 - + (List.fold_left + (fun acc (ts,f) -> + let _,_,_,bur = Transition.node f in + if bur then acc else TagSet.cup acc ts) + acc l) + else acc ) a.trans TagSet.empty + exception Found + + let is_rec a s access = + List.exists + (fun (_,t) -> let _,_,f,_ = Transition.node t in + StateSet.mem s ((fun (_,_,x) -> x) (access (Formula.st f)))) (Hashtbl.find a.trans s) + + + let decide a c_label l_label dir_states dir = + + let l = StateSet.fold + (fun s l -> + let s_rec = is_rec a s (if dir then fst else snd) in + let s_rec = if dir then s_rec else + (* right move *) + is_rec a s fst + in + let s_lab = labels a s in + let jmp,cc,ll = + if (not (TagSet.is_finite s_lab)) then + if TagSet.mem Tag.pcdata s_lab then (`ANY,Ptset.Int.empty,Ptset.Int.empty) + else (`ANYNOTEXT,Ptset.Int.empty,Ptset.Int.empty) + else + if s_rec + then (`JUMP,Ptset.Int.empty, TagSet.positive + (TagSet.cap (TagSet.inj_positive l_label) s_lab)) + else (`JUMP,TagSet.positive + (TagSet.cap (TagSet.inj_positive c_label) s_lab), + Ptset.Int.empty ) + in + (if jmp != `ANY + && jmp != `ANYNOTEXT + && Ptset.Int.is_empty cc + && Ptset.Int.is_empty ll + then (`NIL,Ptset.Int.empty,Ptset.Int.empty) + else (jmp,cc,ll))::l) dir_states [] + in merge_jump_list l + + end + + + + let choose_jump (d,cl,ll) f_nil f_t1 f_s1 f_tn f_sn f_s1n f_notext f_maytext = + match d with + | `NIL -> (`NIL,f_nil) + | `ANYNOTEXT -> `ANY,f_notext + | `ANY -> `ANY,f_maytext + | `JUMP -> + if Ptset.Int.is_empty cl then + if Ptset.Int.is_singleton ll then + let tag = Ptset.Int.choose ll in + (`TAG(tag),mk_app_fun f_tn tag (Tag.to_string tag)) + else + (`ANY,mk_app_fun f_sn ll (string_of_ts ll)) + else if Ptset.Int.is_empty ll then + if Ptset.Int.is_singleton cl then + let tag = Ptset.Int.choose cl in + (`TAG(tag),mk_app_fun f_t1 tag (Tag.to_string tag)) + else + (`ANY,mk_app_fun f_s1 cl (string_of_ts cl)) + else + (`ANY,mk_app_fun2 f_s1n cl ll ((string_of_ts cl) ^ " " ^ (string_of_ts ll))) + + | _ -> assert false + + let choose_jump_down tree d = + choose_jump d + (mk_fun (fun _ -> Tree.nil) "Tree.mk_nil") + (mk_fun (Tree.tagged_child tree) "Tree.tagged_child") + (mk_fun (Tree.select_child tree) "Tree.select_child") + (mk_fun (Tree.tagged_desc tree) "Tree.tagged_desc") + (mk_fun (Tree.select_desc tree) "Tree.select_desc") + (mk_fun (fun _ _ -> Tree.first_child tree) "[FIRSTCHILD]Tree.select_child_desc") + (mk_fun (Tree.first_element tree) "Tree.first_element") + (mk_fun (Tree.first_child tree) "Tree.first_child") + + let choose_jump_next tree d = + choose_jump d + (mk_fun (fun _ _ -> Tree.nil) "Tree.mk_nil2") + (mk_fun (Tree.tagged_sibling_ctx tree) "Tree.tagged_sibling_ctx") + (mk_fun (Tree.select_sibling_ctx tree) "Tree.select_sibling_ctx") + (mk_fun (Tree.tagged_foll_ctx tree) "Tree.tagged_foll_ctx") + (mk_fun (Tree.select_foll_ctx tree) "Tree.select_foll_ctx") + (mk_fun (fun _ _ -> Tree.next_sibling_ctx tree) "[NEXTSIBLING]Tree.select_sibling_foll_ctx") + (mk_fun (Tree.next_element_ctx tree) "Tree.next_element_ctx") + (mk_fun (Tree.next_sibling_ctx tree) "Tree.node_sibling_ctx") + + module SetTagKey = + struct + type t = Tag.t*SList.t + let equal (t1,s1) (t2,s2) = t1 == t2 && s1 == s2 + let hash (t,s) = HASHINT2(t,s.SList.Node.id) + end + + module CachedTransTable = Hashtbl.Make(SetTagKey) + let td_trans = CachedTransTable.create 4093 + + let empty_size n = let rec loop acc = function 0 -> acc | n -> loop (SList.cons StateSet.empty acc) (n-1) in loop SList.nil n - let merge rb rb1 rb2 mark t res1 res2 = - if rb then - let res1 = if rb1 then res1 else RS.empty - and res2 = if rb2 then res2 else RS.empty - in - if mark then RS.cons t (RS.concat res1 res2) - else RS.concat res1 res2 - else RS.empty + + module Fold2Res = Hashtbl.Make(struct + type t = Formlistlist.t*SList.t*SList.t + let hash (f,s,t) = HASHINT3(f.Formlistlist.Node.id, + s.SList.Node.id, + t.SList.Node.id) + let equal (a,b,c) (d,e,f) = a==d && b == e && c == f + end) + + let h_fold2 = Fold2Res.create BIG_H_SIZE let top_down ?(noright=false) a tree t slist ctx slot_size = let pempty = empty_size slot_size in + let rempty = Array.make slot_size RS.empty in (* evaluation starts from the right so we put sl1,res1 at the end *) let eval_fold2_slist fll t (sl2,res2) (sl1,res1) = - let res = Array.copy res1 in - let rec fold l1 l2 fll i aq = - match fll with - [fl] -> (* inline for speed *) - let s1 = SList.hd l1 - and s2 = SList.hd l2 in - let r',flags = eval_formlist s1 s2 fl in - let _ = res.(i) <- RS.merge flags t res1.(i) res2.(i) in - (SList.cons r' aq),res - | fl::fll -> - let SList.Cons(s1,ll1) = l1.SList.Node.node - and SList.Cons(s2,ll2) = l2.SList.Node.node in - let r',flags = eval_formlist s1 s2 fl in - let _ = res.(i) <- RS.merge flags t res1.(i) res2.(i) - in - fold ll1 ll2 fll (i+1) (SList.cons r' aq) - | _ -> aq,res - in - fold sl1 sl2 fll 0 SList.nil + let res = Array.copy rempty in + try + let r,b,btab = Fold2Res.find h_fold2 (fll,sl1,sl2) in + if b then for i=0 to slot_size - 1 do + res.(i) <- RS.merge btab.(i) t res1.(i) res2.(i); + done; + r,res + with + Not_found -> + let btab = Array.make slot_size (false,false,false,false) in + let rec fold l1 l2 fll i aq ab = + match fll.Formlistlist.Node.node, + l1.SList.Node.node, + l2.SList.Node.node + with + | Formlistlist.Cons(fl,fll), + SList.Cons(s1,ll1), + SList.Cons(s2,ll2) -> + let r',((b,_,_,_) as flags) = eval_formlist s1 s2 fl in + let _ = btab.(i) <- flags + in + fold ll1 ll2 fll (i+1) (SList.cons r' aq) (b||ab) + | _ -> aq,ab + in + let r,b = fold sl1 sl2 fll 0 SList.nil false in + Fold2Res.add h_fold2 (fll,sl1,sl2) (r,b,btab); + if b then for i=0 to slot_size - 1 do + res.(i) <- RS.merge btab.(i) t res1.(i) res2.(i); + done; + r,res in - let null_result() = (pempty,Array.make slot_size RS.empty) in - let rec loop t slist ctx = - if t == Tree.nil then null_result() else get_trans t slist (Tree.tag tree t) ctx + let null_result = (pempty,Array.copy rempty) in + let rec loop t slist ctx= + if t == Tree.nil then null_result else get_trans t slist (Tree.tag tree t) ctx and loop_tag tag t slist ctx = - if t == Tree.nil then null_result() else get_trans t slist tag ctx + if t == Tree.nil then null_result else get_trans t slist tag ctx and loop_no_right t slist ctx = - if t == Tree.nil then null_result() else get_trans ~noright:true t slist (Tree.tag tree t) ctx + if t == Tree.nil then null_result else get_trans ~noright:true t slist (Tree.tag tree t) ctx and get_trans ?(noright=false) t slist tag ctx = let cont = try @@ -703,79 +857,81 @@ END ) ) set (Formlist.nil,StateSet.empty,StateSet.empty,ca,da,sa,fa) - in fl::fll_acc, (SList.cons ll lllacc), (SList.cons rr rllacc),ca,da,sa,fa) - slist ([],SList.nil,SList.nil,StateSet.empty,StateSet.empty,StateSet.empty,StateSet.empty) + in (Formlistlist.cons fl fll_acc), (SList.cons ll lllacc), (SList.cons rr rllacc),ca,da,sa,fa) + slist (Formlistlist.nil,SList.nil,SList.nil,StateSet.empty,StateSet.empty,StateSet.empty,StateSet.empty) in (* Logic to chose the first and next function *) - let _,tags_below,_,tags_after = Tree.tags tree tag in + let tags_child,tags_below,tags_siblings,tags_after = Tree.tags tree tag in + let d_f = Algebra.decide a tags_child tags_below (StateSet.union ca da) true in + let d_n = Algebra.decide a tags_siblings tags_after (StateSet.union sa fa) false in (* let _ = Printf.eprintf "Tags below %s are : \n" (Tag.to_string tag) in let _ = Ptset.Int.iter (fun i -> Printf.eprintf "%s " (Tag.to_string i)) tags_below in let _ = Printf.eprintf "\n%!" in *) - let f_kind,first = choose_jump_down tree tags_below ca da a +(* let tags_below = Ptset.Int.remove tag tags_below in *) + let f_kind,first = choose_jump_down tree d_f and n_kind,next = if noright then (`NIL, fun _ _ -> Tree.nil ) - else choose_jump_next tree tags_after sa fa a in - let empty_res = null_result() in - let cont = - match f_kind,n_kind with - | `NIL,`NIL -> - (fun _ _ -> eval_fold2_slist fl_list t empty_res empty_res ) - | _,`NIL -> ( - match f_kind with - |`TAG(tag) -> - (fun t _ -> eval_fold2_slist fl_list t empty_res - (loop_tag tag (first t) llist t)) - | `ANY -> - (fun t _ -> eval_fold2_slist fl_list t empty_res - (loop (first t) llist t)) - | _ -> assert false) - - | `NIL,_ -> ( - match n_kind with - |`TAG(tag) -> - (fun t ctx -> eval_fold2_slist fl_list t - (loop_tag tag (next t ctx) rlist ctx) empty_res) - - | `ANY -> - (fun t ctx -> eval_fold2_slist fl_list t - (loop (next t ctx) rlist ctx) empty_res) - - | _ -> assert false) - - | `TAG(tag1),`TAG(tag2) -> - (fun t ctx -> eval_fold2_slist fl_list t - (loop (next t ctx) rlist ctx) - (loop (first t) llist t)) - - | `TAG(tag),`ANY -> - (fun t ctx -> - eval_fold2_slist fl_list t - (loop (next t ctx) rlist ctx) - (loop_tag tag (first t) llist t)) - | `ANY,`TAG(tag) -> - (fun t ctx -> - eval_fold2_slist fl_list t - (loop_tag tag (next t ctx) rlist ctx) - (loop (first t) llist t) ) - | `ANY,`ANY -> - (fun t ctx -> - eval_fold2_slist fl_list t - (loop (next t ctx) rlist ctx) - (loop (first t) llist t) ) - | _ -> assert false - in - let cont = D_IF_( (fun t ctx -> - let a,b = cont t ctx in - register_trace tree t (slist,a,fl_list,first,next,ctx); - (a,b) - ) ,cont) - in - (CachedTransTable.add td_trans (tag,slist) cont;cont) - in cont t ctx - - in - (if noright then loop_no_right else loop) t slist ctx - - + else choose_jump_next tree d_n in + let empty_res = null_result in + let cont = + match f_kind,n_kind with + | `NIL,`NIL -> + (fun t _ -> eval_fold2_slist fl_list t empty_res empty_res ) + | _,`NIL -> ( + match f_kind with + |`TAG(tag) -> + (fun t _ -> eval_fold2_slist fl_list t empty_res + (loop_tag tag (first t) llist t)) + | `ANY -> + (fun t _ -> eval_fold2_slist fl_list t empty_res + (loop (first t) llist t)) + | _ -> assert false) + + | `NIL,_ -> ( + match n_kind with + |`TAG(tag) -> + (fun t ctx -> eval_fold2_slist fl_list t + (loop_tag tag (next t ctx) rlist ctx) empty_res) + + | `ANY -> + (fun t ctx -> eval_fold2_slist fl_list t + (loop (next t ctx) rlist ctx) empty_res) + + | _ -> assert false) + + | `TAG(tag1),`TAG(tag2) -> + (fun t ctx -> eval_fold2_slist fl_list t + (loop_tag tag2 (next t ctx) rlist ctx) + (loop_tag tag1 (first t) llist t)) + + | `TAG(tag),`ANY -> + (fun t ctx -> eval_fold2_slist fl_list t + (loop (next t ctx) rlist ctx) + (loop_tag tag (first t) llist t)) + | `ANY,`TAG(tag) -> + (fun t ctx -> + eval_fold2_slist fl_list t + (loop_tag tag (next t ctx) rlist ctx) + (loop (first t) llist t) ) + | `ANY,`ANY -> + (fun t ctx -> + eval_fold2_slist fl_list t + (loop (next t ctx) rlist ctx) + (loop (first t) llist t) ) + | _ -> assert false + in + let cont = D_IF_( (fun t ctx -> + let a,b = cont t ctx in + register_trace tree t (slist,a,fl_list,first,next,ctx); + (a,b) + ) ,cont) + in + (CachedTransTable.add td_trans (tag,slist) cont;cont) + in cont t ctx + + in + (if noright then loop_no_right else loop) t slist ctx + + let run_top_down a tree = let init = SList.cons a.init SList.nil in let _,res = top_down a tree Tree.root init Tree.root 1