X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Fxpath%2Fcompile.ml;h=d33fbb4cc826785c8d9ad91976300eb3e5c78a3a;hp=e62b91801dac8a2a12ef8f461b24864cd0cbac82;hb=fe2ba1820282783ae8c10fbbbd2b65d3dc4c67f2;hpb=b00bff88c7902e828804c06b7f9dc55222fdc84e diff --git a/src/xpath/compile.ml b/src/xpath/compile.ml index e62b918..d33fbb4 100644 --- a/src/xpath/compile.ml +++ b/src/xpath/compile.ml @@ -13,19 +13,15 @@ (* *) (***********************************************************************) -(* - Time-stamp: -*) - open Ast let ( => ) a b = (a, b) -let ( ++ ) a b = Ata.SFormula.or_ a b -let ( %% ) a b = Ata.SFormula.and_ a b +let ( ++ ) a b = Ata.Formula.or_ a b +let ( %% ) a b = Ata.Formula.and_ a b let ( @: ) a b = StateSet.add a b -module F = Ata.SFormula +module F = Ata.Formula let node_set = QNameSet.remove QName.document QNameSet.any @@ -44,10 +40,10 @@ let root_set = QNameSet.singleton QName.document *) let compile_axis_test axis (test,kind) phi trans states = - let q = State.make () in + let q = State.next () in let phi = match kind with - Tree.NodeKind.Node -> phi - | _ -> phi %% F.mk_kind kind + Tree.NodeKind.Node -> phi + | _ -> phi %% F.is kind in let phi', trans', states' = match axis with @@ -69,16 +65,15 @@ let compile_axis_test axis (test,kind) phi trans states = ]) :: 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, + let q' = State.next () in + (F.stay q ++ F.first_child q', + (q', [ QNameSet.any => F.stay q ++ F.first_child q' ++ F.next_sibling q'; + ]):: + (q, [ test => phi]):: trans, states) | Parent -> - let q' = State.make () in + let q' = State.next () in let move = F.parent q ++ F.previous_sibling q' in (move, (q, [ test => phi ]) @@ -86,13 +81,12 @@ let compile_axis_test axis (test,kind) phi trans states = (q' @: states)) | Ancestor self -> - let q' = State.make () in - 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, - (q' @: states) + let q' = State.next () in + let move = F.parent q' ++ F.previous_sibling q' in + (if self then F.stay q ++ F.stay q' else F.stay q'), + (q', [ QNameSet.any => move ++ F.parent q]) + :: (q, [ test => phi ]) :: trans, + (q' @: states) | FollowingSibling | PrecedingSibling -> let move = @@ -125,7 +119,7 @@ let rec compile_expr e trans states = states2 | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" -> let phi, trans0, states0 = compile_expr e0 trans states in - (Ata.SFormula.not_ phi), + (F.not_ phi), trans0, states0 | Path p -> compile_path p trans states @@ -134,9 +128,9 @@ let rec compile_expr e trans states = and compile_path paths trans states = List.fold_left (fun (aphi, atrans, astates) p -> let phi, ntrans, nstates = compile_single_path p atrans astates in - (Ata.SFormula.or_ phi aphi), + (F.or_ phi aphi), ntrans, - nstates) (Ata.SFormula.false_,trans,states) paths + nstates) (F.false_,trans,states) paths and compile_single_path p trans states = let steps = @@ -151,7 +145,7 @@ and compile_single_path p trans states = and compile_step_list l trans states = match l with - | [] -> Ata.SFormula.true_, trans, states + | [] -> F.true_, trans, states | (axis, test, elist) :: ll -> let phi0, trans0, states0 = compile_step_list ll trans states in let phi1, trans1, states1 = @@ -162,9 +156,9 @@ and compile_step_list l trans states = aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist (** - Compile the top-level XPath query in reverse (doing downward + Compile the top-level XPath query in reverse (going downward to the last top-level state): - /a0::t0[p0]/.../an-1::tn-1[pn-1]/an::tn[pn] becomes: + /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()] @@ -185,59 +179,75 @@ let compile_top_level_step_list l trans states = (* Only select attribute nodes if the previous axis is attribute *) let phi0 = - if axis != Attribute then - phi0 %% (Ata.SFormula.not_ Ata.SFormula.is_attribute) + if axis != Attribute && kind == Tree.NodeKind.Node then + phi0 %% (F.not_ F.is_attribute) else phi0 in match ll with [] -> - let phi1, trans1, states1 = - List.fold_left (fun (aphi, atrans, astates) e -> + 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 + 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 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 + loop ll trans2 states2 phi2 in + let starting = State.next () in let phi0, trans0, states0 = compile_axis_test Self - (QNameSet.singleton QName.document, Tree.NodeKind.Node) - Ata.SFormula.true_ + (QNameSet.any, Tree.NodeKind.Node) + (F.stay starting) trans states in - loop l trans0 states0 phi0 + let mstates, trans, states = loop l trans0 states0 phi0 in + starting, mstates, trans, states ;; 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 + let sstates, mstates, trans, states = + List.fold_left (fun (ass, ams, atrs, asts) p -> + let ss, ms, natrs, nasts = + match p with + | Absolute l | Relative l -> compile_top_level_step_list l atrs asts + in + (StateSet.add ss ass), + (StateSet.add ms ams), + natrs, + nasts) (StateSet.empty, StateSet.empty, [], StateSet.empty) p in - let a = Ata.create states mstates in + let builder = Ata.Builder.make () in + (** ensure that we have a single selecting state at the end *) + let phi_sel = StateSet.fold (fun q acc -> F.or_ (F.stay q) acc) mstates F.false_ in + let q_sel = State.next () in + let states = StateSet.add q_sel states in + let mstates = StateSet.singleton q_sel in + let trans = (q_sel, [QNameSet.any, phi_sel]) :: trans in + StateSet.iter + (Ata.Builder.add_state builder ~starting:true) sstates; + StateSet.iter + (Ata.Builder.add_state builder ~selecting:true) mstates; + StateSet.iter + (Ata.Builder.add_state builder) states; List.iter (fun (q, l) -> List.iter (fun (lab, phi) -> - Ata.add_trans a q lab phi + Ata.Builder.add_trans builder q lab phi ) l) trans; - Ata.complete_transitions a; - Ata.normalize_negations a; - a + Ata.Builder.finalize builder