let asta = Asta.empty in
(* 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. *)
- let rec trans = function
+ let rec trans = function (* builds asta from the bottom of the query *)
| [s] -> trans_last s
| s :: tl -> trans tl; trans_step s
| [] -> ()
Asta.add_quer asta top_st;
Asta.init_top asta;
Asta.add_top asta top_st;
- Asta.add_tr asta (top_st, Asta.any_label, or_top)
+ Asta.add_tr asta (top_st, Asta.any_label, or_top) true
and trans_last (ax,test,pred) = (* a selecting state is needed *)
let fo_p = trans_pr pred in
let Simple lab = test in
let tr_selec = (q', lab, fo_p)
and tr_q = (q, Asta.any_label, form_propa_selec q q' ax) in
- Asta.add_tr asta tr_selec;
- Asta.add_tr asta tr_q
+ Asta.add_tr asta tr_selec true;
+ Asta.add_tr asta tr_q true
- and trans_step (ax,test,pred) =
+ and trans_step (ax,test,pred) = (* add a new state for the step *)
let fo_p = trans_pr pred
and q = Asta.new_state() in
let Simple label = test
Asta.add_quer asta q;
Asta.add_top asta q;
Asta.add_bot asta q;
- Asta.add_tr asta tr_next;
- Asta.add_tr asta tr_propa;
+ Asta.add_tr asta tr_next true;
+ Asta.add_tr asta tr_propa true;
Asta.init_top asta;
Asta.add_top asta q
| Expr False -> Formula.false_
| Or (p_1,p_2) -> trans_pr(p_1) +| trans_pr(p_2)
| And (p_1,p_2) -> trans_pr(p_1) *& trans_pr(p_2)
- | Not (Expr Path q) -> Formula.true_ (* todo *)
- | Expr Path q -> Formula.true_ (* todo *)
+ | 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
- and form_propa q = function
+ and trans_pr_path posi = function (* builds asta for predicate and gives
+ the formula which must be satsified *)
+ | 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)
+ | AbsoluteDoS steps as x -> print pr_er x; raise Not_core_XPath
+ | Absolute steps as x -> print pr_er x; raise Not_core_XPath
+
+ and trans_pr_step_l = function (* builds asta for a predicate query *)
+ | [step] -> trans_pr_step [] step
+ | step :: tl -> let list_top = trans_pr_step_l tl in
+ trans_pr_step list_top step
+ | [] -> failwith "Can not happened! 1"
+
+ and trans_pr_step list (ax,test,pred) = (* add a step on the top of
+ list in a predicate *)
+ 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)
+ and q = Asta.new_state()
+ and Simple label = test in
+ let tr_next = (q,label, form_next)
+ and tr_propa = (q, Asta.any_label, form_propa q ax) in
+ Asta.add_reco asta q;
+ Asta.add_tr asta tr_next false;
+ Asta.add_tr asta tr_propa false;
+ [q] (* always one element here, but not with self
+ axis*)
+
+ and form_propa q = function (* gives the propagation formula *)
| Child -> `Right *+ q
| Descendant -> (`Left *+ q +| `Right *+ q)
| x -> print_axis pr_er x; raise Not_core_XPath
- and form_propa_selec q q' = function
+ and form_propa_selec q q' = function (* the same with a selecting state *)
| Child -> `Right *+ q +| `Right *+ q'
| Descendant -> (`Left *+ q +| `Right *+ q) +| (`Left *+ q' +| `Right *+ q')
| x -> print_axis pr_er x; raise Not_core_XPath
in
- match query with
+ match query with (* match the top-level query *)
| Absolute steps -> trans steps; trans_init(); asta
| AbsoluteDoS steps as x -> print pr_er x; raise Not_core_XPath
| Relative steps as x -> print pr_er x; raise Not_core_XPath