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-05 19:21:37 CET by Kim Nguyen>
25 Ata.SFormula.atom_ (Ata.Move.make (l,b,q))
27 let ( => ) a b = (a, b)
28 let ( ** ) l q = mk_atom l true q
29 let is_left = mk_atom `Is1 true State.dummy
30 let is_right = mk_atom `Is2 true State.dummy
31 let ( ++ ) a b = Ata.SFormula.or_ a b
32 let ( %% ) a b = Ata.SFormula.and_ a b
33 let ( @: ) a b = StateSet.add a b
35 let node_set = QNameSet.remove QName.document QNameSet.any
36 let star_set = QNameSet.diff QNameSet.any (
37 List.fold_right (QNameSet.add)
38 [ QName.document; QName.text; QName.attribute_map ]
40 let attribute = QNameSet.singleton QName.attribute_map
41 let root_set = QNameSet.singleton QName.document
43 (* [compile_axis_test axis test q phi trans states] Takes an xpath
44 [axis] and node [test], a formula [phi], a list of [trans]itions
45 and a set of [states] and returns a formula [phi'], a new set of
46 transitions, and a new set of states such that [phi'] holds iff
47 there exists a node reachable through [axis]::[test] where [phi]
51 let compile_axis_test axis test phi trans states =
52 let q = State.make () in
53 let phi', trans', states' =
57 (q, [ test => phi ]) :: trans,
63 QNameSet.any => (`Right ** q) ]) :: trans,
67 (if self then (`Epsilon ** q) else (`Left ** q)),
69 QNameSet.any => (`Left ** q);
70 QNameSet.any => (`Right ** q) ]) :: trans,
74 let q' = State.make () in
75 let move = (`Up1 ** q %% is_left) ++ (`Up2 ** q' %% is_right) in
78 :: (q', [ QNameSet.any => move ]) :: trans,
82 let q' = State.make () in
83 let move = (`Up1 ** q %% is_left) ++ (`Up2 ** q' %% is_right) in
84 (if self then (`Epsilon ** q) else move),
87 :: (q', [ QNameSet.any => move ]) :: trans,
90 | FollowingSibling | PrecedingSibling ->
92 if axis = PrecedingSibling then
94 else (`Right ** q %% is_right)
98 star_set => move ]) :: trans,
102 let q' = State.make () in
103 let test = if QNameSet.is_finite test then
104 QNameSet.fold (fun tag acc ->
105 QNameSet.add (QName.add_attribute_prefix tag) acc)
110 (q, [ QNameSet.singleton QName.attribute_map => (`Left ** q') ])
111 :: (q', [ test => phi;
112 QNameSet.any => (`Right ** q') ]) :: trans,
117 phi', trans', q @: states'
120 let compile_rev_axis_test axis test phi trans states =
122 | Attribute -> assert false
123 | _ -> compile_axis_test (invert_axis axis) test phi trans states
128 let rec compile_expr e trans states =
130 | Binop (e1, (And|Or as op), e2) ->
131 let phi1, trans1, states1 = compile_expr e1 trans states in
132 let phi2, trans2, states2 = compile_expr e2 trans1 states1 in
133 (if op = Or then phi1 ++ phi2 else phi1 %% phi2),
136 | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" ->
137 let phi, trans0, states0 = compile_expr e0 trans states in
138 (Ata.SFormula.not_ phi),
141 | Path p -> compile_path p trans states
144 and compile_path paths trans states =
145 List.fold_left (fun (aphi, atrans, astates) p ->
146 let phi, ntrans, nstates = compile_single_path p atrans astates in
147 (Ata.SFormula.or_ phi aphi),
149 nstates) (Ata.SFormula.false_,trans,states) paths
151 and compile_single_path p trans states =
155 (Ancestor false, QNameSet.singleton QName.document, [])::steps
156 | Relative steps -> steps
158 compile_step_list steps trans states
160 and compile_step_list l trans states =
162 | [] -> Ata.SFormula.true_, trans, states
163 | (axis, test, elist) :: ll ->
164 let phi0, trans0, states0 = compile_step_list ll trans states in
165 let phi1, trans1, states1 =
166 compile_axis_test axis test phi0 trans0 states0
168 List.fold_left (fun (aphi, atrans, astates) e ->
169 let ephi, etrans, estates = compile_expr e atrans astates in
170 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
172 let compile_top_level_step_list l trans states =
173 let rec loop l trans states phi_above =
175 | (axis, test, elist) :: [] ->
176 let phi0, trans0, states0 =
177 compile_rev_axis_test axis QNameSet.any phi_above trans states
179 let phi1, trans1, states1 =
180 List.fold_left (fun (aphi, atrans, astates) e ->
181 let ephi, etrans, estates = compile_expr e atrans astates in
182 aphi %% ephi, etrans, estates) (phi0, trans0, states0) elist
184 let _, trans2, states2 =
185 compile_axis_test Self test phi1 trans1 states1
188 StateSet.choose (StateSet.diff states2 states1)
190 marking_state, trans2, states2
191 | (axis, test, elist) :: ll ->
192 let phi0, trans0, states0 =
193 compile_rev_axis_test axis QNameSet.any phi_above trans states
195 let phi1, trans1, states1 =
196 compile_axis_test Self test phi0 trans0 states0
198 let phi2, trans2, states2 =
199 List.fold_left (fun (aphi, atrans, astates) e ->
200 let ephi, etrans, estates = compile_expr e atrans astates in
201 aphi %% ephi, etrans, estates) (phi1, trans1, states1) elist
203 loop ll trans2 states2 phi2
206 let phi0, trans0, states0 =
209 (QNameSet.singleton QName.document)
214 loop l trans0 states0 phi0
219 let mstates, trans, states = List.fold_left (fun (ams, atrs, asts) p ->
220 let ms, natrs, nasts =
222 | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
224 (StateSet.add ms ams), natrs, nasts) (StateSet.empty, [], StateSet.empty) p
226 let a = Ata.create () in
227 a.Ata.states <- states;
228 a.Ata.selection_states <- mstates;
229 List.iter (fun (q, l) ->
230 List.iter (fun (lab, phi) ->
231 Ata.add_trans a q lab phi
233 Ata.complete_transitions a;
234 Ata.normalize_negations a;