1 (***********************************************************************)
5 (* Kim Nguyen, LRI UMR8623 *)
6 (* Université Paris-Sud & CNRS *)
8 (* Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
9 (* Recherche Scientifique. All rights reserved. This file is *)
10 (* distributed under the terms of the GNU Lesser General Public *)
11 (* License, with the special exception on linking described in file *)
14 (***********************************************************************)
19 let ( => ) a b = (a, b)
20 let ( ++ ) a b = Ata.Formula.or_ a b
21 let ( %% ) a b = Ata.Formula.and_ a b
22 let ( @: ) a b = StateSet.add a b
24 module F = Ata.Formula
27 let node_set = QNameSet.remove QName.document QNameSet.any
28 let star_set = QNameSet.diff QNameSet.any (
29 List.fold_right (QNameSet.add)
30 [ QName.document; QName.text; QName.comment ]
32 let root_set = QNameSet.singleton QName.document
34 (* [compile_axis_test axis test q phi trans states] Takes an xpath
35 [axis] and node [test], a formula [phi], a list of [trans]itions
36 and a set of [states] and returns a formula [phi'], a new set of
37 transitions, and a new set of states such that [phi'] holds iff
38 there exists a node reachable through [axis]::[test] where [phi]
42 let compile_axis_test axis (test,kind) phi trans states =
43 let q = State.make () in
44 let phi = match kind with
45 Tree.NodeKind.Node -> phi
46 | _ -> phi %% F.is kind
48 let phi', trans', states' =
52 (q, [ test => phi ]) :: trans,
58 QNameSet.any => F.next_sibling q ]) :: trans,
64 QNameSet.any => F.first_child q ++ F.next_sibling q;
68 let q' = State.make () in
69 (F.stay q ++ F.first_child q',
70 (q', [ QNameSet.any => F.stay q ++ F.first_child q' ++ F.next_sibling q';
72 (q, [ test => phi]):: trans,
76 let q' = State.make () in
77 let move = F.parent q ++ F.previous_sibling q' in
80 :: (q', [ QNameSet.any => move ]) :: trans,
84 let q' = State.make () in
85 let move = F.parent q' ++ F.previous_sibling q' in
86 (if self then F.stay q ++ F.stay q' else F.stay q'),
87 (q', [ QNameSet.any => move ++ F.parent q])
88 :: (q, [ test => phi ]) :: trans,
91 | FollowingSibling | PrecedingSibling ->
93 if axis = PrecedingSibling then
99 QNameSet.any => move ]) :: trans,
105 QNameSet.any => F.next_sibling q]) :: trans,
110 phi', trans', q @: states'
112 let rec compile_expr e trans states =
114 | Binop (e1, (And|Or as op), e2) ->
115 let phi1, trans1, states1 = compile_expr e1 trans states in
116 let phi2, trans2, states2 = compile_expr e2 trans1 states1 in
117 (if op = Or then phi1 ++ phi2 else phi1 %% phi2),
120 | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" ->
121 let phi, trans0, states0 = compile_expr e0 trans states in
125 | Path p -> compile_path p trans states
128 and compile_path paths trans states =
129 List.fold_left (fun (aphi, atrans, astates) p ->
130 let phi, ntrans, nstates = compile_single_path p atrans astates in
133 nstates) (F.false_,trans,states) paths
135 and compile_single_path p trans states =
139 (Ancestor false, (QNameSet.singleton QName.document,
140 Tree.NodeKind.Node), [])
142 | Relative steps -> steps
144 compile_step_list steps trans states
146 and compile_step_list l trans states =
148 | [] -> F.true_, trans, states
149 | (axis, test, elist) :: ll ->
150 let phi0, trans0, states0 = compile_step_list ll trans states in
151 let phi1, trans1, states1 =
152 compile_axis_test axis test phi0 trans0 states0
154 List.fold_left (fun (aphi, atrans, astates) e ->
155 let ephi, etrans, estates = compile_expr e atrans astates in
156 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
159 Compile the top-level XPath query in reverse (doing downward
160 to the last top-level state):
161 /a0::t0[p0]/.../an-1::tn-1[pn-1]/an::tn[pn] becomes:
163 self::tn[pn]/inv(an)::(tn-1)[pn-1]/.../inv(a1)::t0[p0]/inv(a0)::document()]
165 /child::a/attribute::b
166 self::@b/parent::a/parent::doc()
169 let compile_top_level_step_list l trans states =
170 let rec loop l trans states phi_above =
173 | (axis, (test,kind), elist) :: ll ->
174 let phi0, trans0, states0 =
175 compile_axis_test (invert_axis axis)
176 (QNameSet.any, Tree.NodeKind.Node)
177 phi_above trans states
179 (* Only select attribute nodes if the previous axis
182 if axis != Attribute then
183 phi0 %% (F.not_ F.is_attribute)
188 let phi1, trans1, states1 =
189 List.fold_left (fun (aphi, atrans, astates) e ->
190 let ephi, etrans, estates = compile_expr e atrans astates in
191 aphi %% ephi, etrans, estates) (phi0, trans0, states0) elist
193 let _, trans2, states2 =
194 compile_axis_test Self (test,kind) phi1 trans1 states1
197 StateSet.choose (StateSet.diff states2 states1)
199 marking_state, trans2, states2
201 let phi1, trans1, states1 =
202 compile_axis_test Self (test,kind) phi0 trans0 states0
204 let phi2, trans2, states2 =
205 List.fold_left (fun (aphi, atrans, astates) e ->
206 let ephi, etrans, estates = compile_expr e atrans astates in
207 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
209 loop ll trans2 states2 phi2
211 let starting = State.make () in
212 let phi0, trans0, states0 =
215 (QNameSet.any, Tree.NodeKind.Node)
220 let mstates, trans, states = loop l trans0 states0 phi0 in
221 starting, mstates, trans, states
225 let sstates, mstates, trans, states =
226 List.fold_left (fun (ass, ams, atrs, asts) p ->
227 let ss, ms, natrs, nasts =
229 | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
231 (StateSet.add ss ass),
232 (StateSet.add ms ams),
234 nasts) (StateSet.empty, StateSet.empty, [], StateSet.empty) p
236 let builder = Ata.Builder.make () in
237 (** ensure that we have a single selecting state at the end *)
238 let phi_sel = StateSet.fold (fun q acc -> F.or_ (F.stay q) acc) mstates F.false_ in
239 let q_sel = State.make () in
240 let states = StateSet.add q_sel states in
241 let mstates = StateSet.singleton q_sel in
242 let trans = (q_sel, [QNameSet.any, phi_sel]) :: trans in
244 (Ata.Builder.add_state builder ~starting:true) sstates;
246 (Ata.Builder.add_state builder ~selecting:true) mstates;
248 (Ata.Builder.add_state builder) states;
249 List.iter (fun (q, l) ->
250 List.iter (fun (lab, phi) ->
251 Ata.Builder.add_trans builder q lab phi
253 Ata.Builder.finalize builder