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-10 12:28:07 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 let add_attribute_prefix test =
31 if QNameSet.is_finite test then
32 QNameSet.fold (fun tag acc ->
33 QNameSet.add (QName.add_attribute_prefix tag) acc)
38 module F = Ata.SFormula
41 let node_set = QNameSet.remove QName.document QNameSet.any
42 let star_set = QNameSet.diff QNameSet.any (
43 List.fold_right (QNameSet.add)
44 [ QName.document; QName.text; QName.attribute_map ]
46 let attribute = QNameSet.singleton QName.attribute_map
47 let root_set = QNameSet.singleton QName.document
49 (* [compile_axis_test axis test q phi trans states] Takes an xpath
50 [axis] and node [test], a formula [phi], a list of [trans]itions
51 and a set of [states] and returns a formula [phi'], a new set of
52 transitions, and a new set of states such that [phi'] holds iff
53 there exists a node reachable through [axis]::[test] where [phi]
57 let compile_axis_test ?(block_attr=true) axis test phi trans states =
58 let q = State.make () in
59 let phi_attr = if block_attr then F.not_ F.is_attribute else F.true_ in
60 let phi', trans', states' =
64 (q, [ test => phi ]) :: trans,
69 (q, [ test => phi %% phi_attr;
70 QNameSet.any => F.next_sibling q ]) :: trans,
75 (q, [ test => phi %% phi_attr;
76 QNameSet.any => F.first_child q ++ F.next_sibling q;
80 let q' = State.make () in
81 (F.or_ (F.stay q) (F.first_child q'),
82 (q', [ test => phi %% phi_attr;
83 QNameSet.any => F.first_child q' ++ F.next_sibling q';
85 (q, [ test => phi %% phi_attr]):: trans,
89 let q' = State.make () in
90 let move = F.parent q ++ F.previous_sibling q' in
93 :: (q', [ QNameSet.any => move ]) :: trans,
97 let q' = State.make () in
98 let move = F.parent q ++ F.previous_sibling q' in
99 (if self then F.stay q else move),
101 QNameSet.any => move ])
102 :: (q', [ QNameSet.any => move ]) :: trans,
105 | FollowingSibling | PrecedingSibling ->
107 if axis = PrecedingSibling then
109 else F.next_sibling q
112 (q, [ test => phi %% phi_attr;
113 QNameSet.any => move ]) :: trans,
118 (q, [ test => phi %% F.is_attribute;
119 QNameSet.any => F.next_sibling q]) :: trans,
124 phi', trans', q @: states'
127 let compile_rev_axis_test block_attr axis test phi trans states =
131 ~block_attr:false Parent test phi trans states
132 | _ -> compile_axis_test
133 ~block_attr:block_attr (invert_axis axis) test phi trans states
135 let rec compile_expr e trans states =
137 | Binop (e1, (And|Or as op), e2) ->
138 let phi1, trans1, states1 = compile_expr e1 trans states in
139 let phi2, trans2, states2 = compile_expr e2 trans1 states1 in
140 (if op = Or then phi1 ++ phi2 else phi1 %% phi2),
143 | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" ->
144 let phi, trans0, states0 = compile_expr e0 trans states in
145 (Ata.SFormula.not_ phi),
148 | Path p -> compile_path p trans states
151 and compile_path paths trans states =
152 List.fold_left (fun (aphi, atrans, astates) p ->
153 let phi, ntrans, nstates = compile_single_path p atrans astates in
154 (Ata.SFormula.or_ phi aphi),
156 nstates) (Ata.SFormula.false_,trans,states) paths
158 and compile_single_path p trans states =
162 (Ancestor false, QNameSet.singleton QName.document, [])::steps
163 | Relative steps -> steps
165 compile_step_list steps trans states
167 and compile_step_list l trans states =
169 | [] -> Ata.SFormula.true_, trans, states
170 | (axis, test, elist) :: ll ->
171 let phi0, trans0, states0 = compile_step_list ll trans states in
172 let phi1, trans1, states1 =
173 compile_axis_test axis test phi0 trans0 states0
175 List.fold_left (fun (aphi, atrans, astates) e ->
176 let ephi, etrans, estates = compile_expr e atrans astates in
177 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
179 let compile_top_level_step_list l trans states =
180 let rec loop l trans states block_attr phi_above =
182 | (axis, test, elist) :: [] ->
183 let phi0, trans0, states0 =
184 compile_rev_axis_test
185 block_attr axis QNameSet.any phi_above trans states
187 let phi1, trans1, states1 =
188 List.fold_left (fun (aphi, atrans, astates) e ->
189 let ephi, etrans, estates = compile_expr e atrans astates in
190 aphi %% ephi, etrans, estates) (phi0, trans0, states0) elist
193 if axis = Attribute then
196 F.not_ F.is_attribute
198 let _, trans2, states2 =
199 compile_axis_test Self test (phi1 %% phi') trans1 states1
202 StateSet.choose (StateSet.diff states2 states1)
204 marking_state, trans2, states2
205 | (axis, test, elist) :: ll ->
206 let phi0, trans0, states0 =
207 compile_rev_axis_test
208 block_attr axis QNameSet.any phi_above trans states
210 let phi1, trans1, states1 =
211 compile_axis_test Self test phi0 trans0 states0
213 let phi2, trans2, states2 =
214 List.fold_left (fun (aphi, atrans, astates) e ->
215 let ephi, etrans, estates = compile_expr e atrans astates in
216 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
218 loop ll trans2 states2 (axis != Attribute) phi2
221 let phi0, trans0, states0 =
224 (QNameSet.singleton QName.document)
229 loop l trans0 states0 true phi0
234 let mstates, trans, states = List.fold_left (fun (ams, atrs, asts) p ->
235 let ms, natrs, nasts =
237 | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
239 (StateSet.add ms ams), natrs, nasts) (StateSet.empty, [], StateSet.empty) p
241 let a = Ata.create () in
242 a.Ata.states <- states;
243 a.Ata.selection_states <- mstates;
244 List.iter (fun (q, l) ->
245 List.iter (fun (lab, phi) ->
246 Ata.add_trans a q lab phi
248 Ata.complete_transitions a;
249 Ata.normalize_negations a;