X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Fcompil.ml;h=22ae300afe9bdeb9820943b274d3891ebc534b0e;hb=d4e704decf927be044d72a6fe4314aea3c8125a5;hp=94d321f4099ee0cef9c3e60a403eb950083d53e2;hpb=eb490bfac81cf551554f996a3e1de1993c291acd;p=tatoo.git diff --git a/src/compil.ml b/src/compil.ml index 94d321f..22ae300 100644 --- a/src/compil.ml +++ b/src/compil.ml @@ -2,8 +2,8 @@ (* *) (* TAToo *) (* *) -(* Lucca Hirschi, ? *) -(* ? *) +(* Lucca Hirschi, LRI UMR8623 *) +(* Université Paris-Sud & CNRS *) (* *) (* Copyright 2010-2012 Université Paris-Sud and Centre National de la *) (* Recherche Scientifique. All rights reserved. This file is *) @@ -21,6 +21,8 @@ exception Not_core_XPath let pr_er = Format.err_formatter +let ax_ (a,b,c) = a + let trans query = (* Buidling of the ASTA step by step with a special case for the last step. Then add a top most state. Each function modifies asta. *) @@ -28,22 +30,21 @@ let trans query = (* builds asta from the bottom of the query *) let rec trans = function | [s] -> trans_last s - | s :: tl -> trans tl; trans_step s + | s :: tl -> trans tl; trans_step s (ax_(List.hd tl)) | [] -> () - + (* Add THE top most state for top-level query (done in the end) *) and trans_init () = let top_st = Asta.new_state () in let or_top = List.fold_left (fun acc x -> ((`Left *+ x) +| acc)) - (Formula.false_) (Asta.top_states asta) - in + (Formula.false_) (Asta.top_states asta) in Asta.add_quer asta top_st; Asta.init_top asta; Asta.add_top asta top_st; Asta.add_bot asta top_st; (* for trees which are leaves *) Asta.add_tr asta (top_st, Asta.any_label, or_top) true - + (* A selecting state is needed *) and trans_last (ax,test,pred) = let fo_p = trans_pr pred in @@ -59,15 +60,25 @@ let trans query = and tr_q = (q, Asta.any_label, form_propa_selec q q' ax) in Asta.add_tr asta tr_selec true; Asta.add_tr asta tr_q true - + + and form_next_step ax_next top_states_next form_pred = + match ax_next with + | Self -> (form_pred) *& (* (\/ top_next) /\ predicate *) + (List.fold_left (fun acc x -> (`Self *+ x ) +| acc) + Formula.false_ top_states_next) + | FollowingSibling -> (form_pred) *& (* (\/ top_next) /\ predicate *) + (List.fold_left (fun acc x -> (`Right *+ x ) +| acc) + Formula.false_ top_states_next) + | _ -> (form_pred) *& (* (\/ top_next) /\ predicate *) + (List.fold_left (fun acc x -> (`Left *+ x ) +| acc) + Formula.false_ top_states_next) + (* Add a new state and its transitions for the step *) - and trans_step (ax,test,pred) = + and trans_step (ax,test,pred) ax_next = let fo_p = trans_pr pred and q = Asta.new_state() in let Simple label = test - and form_next = (fo_p) *& (* (\/ top_next) /\ predicat *) - (List.fold_left (fun acc x -> (`Left *+ x ) +| acc) - Formula.false_ (Asta.top_states asta)) in + and form_next = form_next_step ax_next (Asta.top_states asta) fo_p in let tr_next = (q, label, form_next) and tr_propa = (q, Asta.any_label, form_propa q ax) in Asta.add_quer asta q; @@ -77,7 +88,7 @@ let trans query = Asta.add_tr asta tr_propa true; Asta.init_top asta; Asta.add_top asta q - + (* Translating of predicates. Either we apply De Morgan rules in xPath.parse or here *) and trans_pr = function @@ -88,31 +99,34 @@ let trans query = | Not (Expr Path q) -> (trans_pr_path false q) | Expr Path q -> (trans_pr_path true q) | x -> print_predicate pr_er x; raise Not_core_XPath - + (* Builds asta for predicate and gives the formula which must be satsified *) and trans_pr_path posi = function | Relative [] -> if posi then Formula.true_ else Formula.false_ - | Relative steps -> List.fold_left - (fun acc x -> if posi then (`Left *+ x) +| acc else (`Left *- x) +| acc) - Formula.false_ (trans_pr_step_l steps) + | Relative steps -> + let dir = match ax_ (List.hd steps) with + | Self -> `Self + | FollowingSibling -> `Right + | _ -> `Left in + List.fold_left + (fun acc x -> if posi then (dir *+ x) +| acc else (dir *- x) +| acc) + Formula.false_ (trans_pr_step_l steps) | AbsoluteDoS steps as x -> print pr_er x; raise Not_core_XPath | Absolute steps as x -> print pr_er x; raise Not_core_XPath (* Builds asta for a predicate query and give the formula *) and trans_pr_step_l = function - | [step] -> trans_pr_step [] step + | [step] -> trans_pr_step [] step (Self) (* Self doesn't matter since [] *) | step :: tl -> let list_top = trans_pr_step_l tl in - trans_pr_step list_top step + trans_pr_step list_top step (ax_ (List.hd tl)) | [] -> failwith "Can not happened! 1" (* Add a step on the top of a list of states in a predicate *) - and trans_pr_step list (ax,test,pred) = + and trans_pr_step list (ax,test,pred) ax_next = let form_next = if list = [] then trans_pr pred - else (trans_pr pred) *& - (List.fold_left (fun acc x -> (`Left *+ x) +| acc) - Formula.false_ list) + else form_next_step ax_next list (trans_pr pred) and q = Asta.new_state() and Simple label = test in let tr_next = (q,label, form_next) @@ -126,12 +140,16 @@ let trans query = and form_propa q = function | Child -> `Right *+ q | Descendant -> (`Left *+ q +| `Right *+ q) + | Self -> `Self *+ q + | FollowingSibling -> `Right *+ q | x -> print_axis pr_er x; raise Not_core_XPath (* The same with a selecting state *) and form_propa_selec q q' = function | Child -> `Right *+ q +| `Right *+ q' | Descendant -> (`Left *+ q +| `Right *+ q) +| (`Left *+ q' +| `Right *+ q') + | Self -> `Self *+ q' + | FollowingSibling -> `Right *+ q +| `Right *+ q' | x -> print_axis pr_er x; raise Not_core_XPath in