X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Fxpath%2Fcompile.ml;h=e62b91801dac8a2a12ef8f461b24864cd0cbac82;hp=783d7f182f449b3fafbdafd90d3f7c4c000c9ea2;hb=b00bff88c7902e828804c06b7f9dc55222fdc84e;hpb=e13f5deae217f945b44fa345ef4f0008e1780787 diff --git a/src/xpath/compile.ml b/src/xpath/compile.ml index 783d7f1..e62b918 100644 --- a/src/xpath/compile.ml +++ b/src/xpath/compile.ml @@ -14,22 +14,27 @@ (***********************************************************************) (* - Time-stamp: + Time-stamp: *) open Ast -open Auto -open Utils -let mk_atom l b q = - Ata.SFormula.atom_ (Ata.Move.make (l,b,q)) let ( => ) a b = (a, b) -let ( ** ) l q = mk_atom l true q let ( ++ ) a b = Ata.SFormula.or_ a b let ( %% ) a b = Ata.SFormula.and_ a b let ( @: ) a b = StateSet.add a b +module F = Ata.SFormula + + +let node_set = QNameSet.remove QName.document QNameSet.any +let star_set = QNameSet.diff QNameSet.any ( + List.fold_right (QNameSet.add) + [ QName.document; QName.text; QName.comment ] + QNameSet.empty) +let root_set = QNameSet.singleton QName.document + (* [compile_axis_test axis test q phi trans states] Takes an xpath [axis] and node [test], a formula [phi], a list of [trans]itions and a set of [states] and returns a formula [phi'], a new set of @@ -38,39 +43,52 @@ let ( @: ) a b = StateSet.add a b holds. *) -let compile_axis_test axis test phi trans states = +let compile_axis_test axis (test,kind) phi trans states = let q = State.make () in - let phi, trans, states = + let phi = match kind with + Tree.NodeKind.Node -> phi + | _ -> phi %% F.mk_kind kind + in + let phi', trans', states' = match axis with | Self -> - (`Epsilon ** q), - (q, [ test => phi ]) :: trans, - states + (F.stay q, + (q, [ test => phi ]) :: trans, + states) | Child -> - (`Left ** q), - (q, [ test => phi; - QNameSet.any => (`Right ** q) ]) :: trans, - states + (F.first_child q, + (q, [ test => phi; + QNameSet.any => F.next_sibling q ]) :: trans, + states) - | Descendant self -> - (if self then (`Epsilon ** q) else (`Left ** q)), - (q, [ test => phi; - QNameSet.any => (`Left ** q) %% (`Right ** q) ]) :: trans, - states + | Descendant false -> + (F.first_child q, + (q, [ test => phi; + QNameSet.any => F.first_child q ++ F.next_sibling q; + ]) :: trans, + states) + | Descendant true -> + let q' = State.make () in + (F.or_ (F.stay q) (F.first_child q'), + (q', [ test => phi; + QNameSet.any => F.first_child q' ++ F.next_sibling q'; + ]):: + (q, [ test => phi]):: trans, + states) | Parent -> let q' = State.make () in - let move = (`Up1 ** q) ++ (`Up2 ** q') in - move, - (q, [ test => phi ]) - :: (q', [ QNameSet.any => move ]) :: trans, - (q' @: states) + let move = F.parent q ++ F.previous_sibling q' in + (move, + (q, [ test => phi ]) + :: (q', [ QNameSet.any => move ]) :: trans, + (q' @: states)) | Ancestor self -> let q' = State.make () in - let move = (`Up1 ** q) ++ (`Up2 ** q') in - (if self then (`Epsilon ** q) else move), + let move = F.parent q ++ F.previous_sibling q' in + (if self then F.stay q else move), (q, [ test => phi; QNameSet.any => move ]) :: (q', [ QNameSet.any => move ]) :: trans, @@ -79,8 +97,8 @@ let compile_axis_test axis test phi trans states = | FollowingSibling | PrecedingSibling -> let move = if axis = PrecedingSibling then - (`Up2 ** q) - else (`Right ** q) + F.previous_sibling q + else F.next_sibling q in move, (q, [ test => phi; @@ -88,22 +106,15 @@ let compile_axis_test axis test phi trans states = states | Attribute -> - let q' = State.make () in - let test = if QNameSet.is_finite test then - QNameSet.fold (fun tag acc -> QNameSet.add (QName.add_attribute_prefix tag) acc) - test QNameSet.empty - else test - in - (`Left ** q), - (q, [ QNameSet.singleton QName.attribute_map => (`Left ** q') ]) - :: (q', [ test => phi; - QNameSet.any => (`Right ** q') ]) :: trans, - (q' @:states) + (F.first_child q, + (q, [ test => phi; + QNameSet.any => F.next_sibling q]) :: trans, + states) | _ -> assert false in - phi, trans, q @: states -;; + phi', trans', q @: states' + let rec compile_expr e trans states = match e with | Binop (e1, (And|Or as op), e2) -> @@ -131,13 +142,16 @@ and compile_single_path p trans states = let steps = match p with | Absolute steps -> - (Ancestor false, QNameSet.singleton QName.document, [])::steps + (Ancestor false, (QNameSet.singleton QName.document, + Tree.NodeKind.Node), []) + :: steps | Relative steps -> steps in compile_step_list steps trans states + and compile_step_list l trans states = match l with - [] -> Ata.SFormula.true_, trans, states + | [] -> Ata.SFormula.true_, trans, states | (axis, test, elist) :: ll -> let phi0, trans0, states0 = compile_step_list ll trans states in let phi1, trans1, states1 = @@ -146,3 +160,84 @@ and compile_step_list l trans states = List.fold_left (fun (aphi, atrans, astates) e -> let ephi, etrans, estates = compile_expr e atrans astates in aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist + +(** + Compile the top-level XPath query in reverse (doing downward + to the last top-level state): + /a0::t0[p0]/.../an-1::tn-1[pn-1]/an::tn[pn] becomes: + self::node()[ pn and + self::tn[pn]/inv(an)::(tn-1)[pn-1]/.../inv(a1)::t0[p0]/inv(a0)::document()] + + /child::a/attribute::b + self::@b/parent::a/parent::doc() +*) + +let compile_top_level_step_list l trans states = + let rec loop l trans states phi_above = + match l with + | [] -> assert false + | (axis, (test,kind), elist) :: ll -> + let phi0, trans0, states0 = + compile_axis_test (invert_axis axis) + (QNameSet.any, Tree.NodeKind.Node) + phi_above trans states + in + (* Only select attribute nodes if the previous axis + is attribute *) + let phi0 = + if axis != Attribute then + phi0 %% (Ata.SFormula.not_ Ata.SFormula.is_attribute) + else phi0 + in + match ll with + [] -> + let phi1, trans1, states1 = + List.fold_left (fun (aphi, atrans, astates) e -> + let ephi, etrans, estates = compile_expr e atrans astates in + aphi %% ephi, etrans, estates) (phi0, trans0, states0) elist + in + let _, trans2, states2 = + compile_axis_test Self (test,kind) phi1 trans1 states1 + in + let marking_state = + StateSet.choose (StateSet.diff states2 states1) + in + marking_state, trans2, states2 + | _ -> + let phi1, trans1, states1 = + compile_axis_test Self (test,kind) phi0 trans0 states0 + in + let phi2, trans2, states2 = + List.fold_left (fun (aphi, atrans, astates) e -> + let ephi, etrans, estates = compile_expr e atrans astates in + aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist + in + loop ll trans2 states2 phi2 + in + let phi0, trans0, states0 = + compile_axis_test + Self + (QNameSet.singleton QName.document, Tree.NodeKind.Node) + Ata.SFormula.true_ + trans + states + in + loop l trans0 states0 phi0 +;; + +let path p = + let mstates, trans, states = List.fold_left (fun (ams, atrs, asts) p -> + let ms, natrs, nasts = + match p with + | Absolute l | Relative l -> compile_top_level_step_list l atrs asts + in + (StateSet.add ms ams), natrs, nasts) (StateSet.empty, [], StateSet.empty) p + in + let a = Ata.create states mstates in + List.iter (fun (q, l) -> + List.iter (fun (lab, phi) -> + Ata.add_trans a q lab phi + ) l) trans; + Ata.complete_transitions a; + Ata.normalize_negations a; + a