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 (***********************************************************************)
17 Time-stamp: <Last modified on 2013-03-15 18:17:50 CET by Kim Nguyen>
25 let ( => ) a b = (a, b)
26 let ( ++ ) a b = Ata.SFormula.or_ a b
27 let ( %% ) a b = Ata.SFormula.and_ a b
28 let ( @: ) a b = StateSet.add a b
30 module F = Ata.SFormula
33 let node_set = QNameSet.remove QName.document QNameSet.any
34 let star_set = QNameSet.diff QNameSet.any (
35 List.fold_right (QNameSet.add)
36 [ QName.document; QName.text; QName.comment ]
38 let root_set = QNameSet.singleton QName.document
40 (* [compile_axis_test axis test q phi trans states] Takes an xpath
41 [axis] and node [test], a formula [phi], a list of [trans]itions
42 and a set of [states] and returns a formula [phi'], a new set of
43 transitions, and a new set of states such that [phi'] holds iff
44 there exists a node reachable through [axis]::[test] where [phi]
48 let compile_axis_test axis (test,kind) phi trans states =
49 let q = State.make () in
50 let phi = match kind with
51 Tree.Common.NodeKind.Node -> phi
52 | _ -> phi %% F.mk_kind kind
54 let phi', trans', states' =
58 (q, [ test => phi ]) :: trans,
64 QNameSet.any => F.next_sibling q ]) :: trans,
70 QNameSet.any => F.first_child q ++ F.next_sibling q;
74 let q' = State.make () in
75 (F.or_ (F.stay q) (F.first_child q'),
77 QNameSet.any => F.first_child q' ++ F.next_sibling q';
79 (q, [ test => phi]):: trans,
83 let q' = State.make () in
84 let move = F.parent q ++ F.previous_sibling q' in
87 :: (q', [ QNameSet.any => move ]) :: trans,
91 let q' = State.make () in
92 let move = F.parent q ++ F.previous_sibling q' in
93 (if self then F.stay q else move),
95 QNameSet.any => move ])
96 :: (q', [ QNameSet.any => move ]) :: trans,
99 | FollowingSibling | PrecedingSibling ->
101 if axis = PrecedingSibling then
103 else F.next_sibling q
107 QNameSet.any => move ]) :: trans,
113 QNameSet.any => F.next_sibling q]) :: trans,
118 phi', trans', q @: states'
120 let rec compile_expr e trans states =
122 | Binop (e1, (And|Or as op), e2) ->
123 let phi1, trans1, states1 = compile_expr e1 trans states in
124 let phi2, trans2, states2 = compile_expr e2 trans1 states1 in
125 (if op = Or then phi1 ++ phi2 else phi1 %% phi2),
128 | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" ->
129 let phi, trans0, states0 = compile_expr e0 trans states in
130 (Ata.SFormula.not_ phi),
133 | Path p -> compile_path p trans states
136 and compile_path paths trans states =
137 List.fold_left (fun (aphi, atrans, astates) p ->
138 let phi, ntrans, nstates = compile_single_path p atrans astates in
139 (Ata.SFormula.or_ phi aphi),
141 nstates) (Ata.SFormula.false_,trans,states) paths
143 and compile_single_path p trans states =
147 (Ancestor false, (QNameSet.singleton QName.document,
148 Tree.Common.NodeKind.Node), [])
150 | Relative steps -> steps
152 compile_step_list steps trans states
154 and compile_step_list l trans states =
156 | [] -> Ata.SFormula.true_, trans, states
157 | (axis, test, elist) :: ll ->
158 let phi0, trans0, states0 = compile_step_list ll trans states in
159 let phi1, trans1, states1 =
160 compile_axis_test axis test phi0 trans0 states0
162 List.fold_left (fun (aphi, atrans, astates) e ->
163 let ephi, etrans, estates = compile_expr e atrans astates in
164 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
167 Compile the top-level XPath query in reverse (doing downward
168 to the last top-level state):
169 /a0::t0[p0]/.../an-1::tn-1[pn-1]/an::tn[pn] becomes:
171 self::tn[pn]/inv(an)::(tn-1)[pn-1]/.../inv(a1)::t0[p0]/inv(a0)::document()]
173 /child::a/attribute::b
174 self::@b/parent::a/parent::doc()
177 let compile_top_level_step_list l trans states =
178 let rec loop l trans states phi_above =
181 | (axis, (test,kind), elist) :: ll ->
182 let phi0, trans0, states0 =
183 compile_axis_test (invert_axis axis)
184 (QNameSet.any, Tree.Common.NodeKind.Node)
185 phi_above trans states
187 (* Only select attribute nodes if the previous axis
190 if axis != Attribute then
191 phi0 %% (Ata.SFormula.not_ Ata.SFormula.is_attribute)
196 let phi1, trans1, states1 =
197 List.fold_left (fun (aphi, atrans, astates) e ->
198 let ephi, etrans, estates = compile_expr e atrans astates in
199 aphi %% ephi, etrans, estates) (phi0, trans0, states0) elist
201 let _, trans2, states2 =
202 compile_axis_test Self (test,kind) phi1 trans1 states1
205 StateSet.choose (StateSet.diff states2 states1)
207 marking_state, trans2, states2
209 let phi1, trans1, states1 =
210 compile_axis_test Self (test,kind) phi0 trans0 states0
212 let phi2, trans2, states2 =
213 List.fold_left (fun (aphi, atrans, astates) e ->
214 let ephi, etrans, estates = compile_expr e atrans astates in
215 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
217 loop ll trans2 states2 phi2
219 let phi0, trans0, states0 =
222 (QNameSet.singleton QName.document, Tree.Common.NodeKind.Node)
227 loop l trans0 states0 phi0
231 let mstates, trans, states = List.fold_left (fun (ams, atrs, asts) p ->
232 let ms, natrs, nasts =
234 | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
236 (StateSet.add ms ams), natrs, nasts) (StateSet.empty, [], StateSet.empty) p
238 let a = Ata.create states mstates in
239 List.iter (fun (q, l) ->
240 List.iter (fun (lab, phi) ->
241 Ata.add_trans a q lab phi
243 Ata.complete_transitions a;
244 Ata.normalize_negations a;