Simplify the automaton encoding a bit (remove redundant predicates in formulae).
[tatoo.git] / src / xpath / compile.ml
1 (***********************************************************************)
2 (*                                                                     *)
3 (*                               TAToo                                 *)
4 (*                                                                     *)
5 (*                     Kim Nguyen, LRI UMR8623                         *)
6 (*                   Universit√© Paris-Sud & CNRS                       *)
7 (*                                                                     *)
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   *)
12 (*  ../LICENSE.                                                        *)
13 (*                                                                     *)
14 (***********************************************************************)
15
16 open Ast
17
18
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
23
24 module F = Ata.Formula
25
26
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 ]
31     QNameSet.empty)
32 let root_set = QNameSet.singleton QName.document
33
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]
39    holds.
40 *)
41
42 let compile_axis_test axis (test,kind) phi trans states =
43   let q = State.next () in
44   let phi = match kind with
45       Tree.NodeKind.Node -> phi
46     | _ -> phi %% F.is kind
47   in
48   let phi', trans', states' =
49     match axis with
50     | Self ->
51         (F.stay q,
52          (q, [  test => phi ]) :: trans,
53          states)
54
55     | Child ->
56         (F.first_child q,
57          (q, [ test => phi;
58                QNameSet.any => F.next_sibling q ]) :: trans,
59          states)
60
61     | Descendant false ->
62         (F.first_child q,
63          (q, [ test => phi;
64                QNameSet.any => F.first_child q ++ F.next_sibling q;
65              ]) :: trans,
66          states)
67     | Descendant true ->
68         let q' = State.next () in
69         (F.stay q ++ F.first_child q',
70          (q', [ QNameSet.any => F.stay q ++ F.first_child q' ++ F.next_sibling q';
71               ])::
72            (q, [ test => phi]):: trans,
73          states)
74
75     | Parent ->
76         let q' = State.next () in
77         let move = F.parent q ++ F.previous_sibling q' in
78         (move,
79          (q, [ test => phi ])
80          :: (q', [ QNameSet.any => move ]) :: trans,
81          (q' @: states))
82
83     | Ancestor self ->
84       let q' = State.next () 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,
89       (q' @: states)
90
91     | FollowingSibling | PrecedingSibling ->
92         let move =
93           if axis = PrecedingSibling then
94             F.previous_sibling q
95           else F.next_sibling q
96         in
97         move,
98         (q, [ test => phi;
99               QNameSet.any => move ]) :: trans,
100         states
101
102     | Attribute ->
103         (F.first_child q,
104          (q, [ test => phi;
105                QNameSet.any => F.next_sibling q]) :: trans,
106          states)
107     | _ -> assert false
108
109   in
110   phi', trans', q @: states'
111
112 let rec compile_expr e trans states =
113   match e with
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),
118       trans2,
119       states2
120   | Fun_call (f, [ e0 ]) when (QName.to_string f) = "not" ->
121       let phi, trans0, states0 = compile_expr e0 trans states in
122       (F.not_ phi),
123       trans0,
124       states0
125   | Path p -> compile_path p trans states
126
127   | _ -> assert false
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
131     (F.or_ phi aphi),
132     ntrans,
133     nstates) (F.false_,trans,states) paths
134
135 and compile_single_path p trans states =
136   let steps =
137     match p with
138     | Absolute steps ->
139         (Ancestor false, (QNameSet.singleton QName.document,
140                           Tree.NodeKind.Node), [])
141         :: steps
142     | Relative steps -> steps
143   in
144   compile_step_list steps trans states
145
146 and compile_step_list l trans states =
147   match l with
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
153       in
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
157
158 (**
159    Compile the top-level XPath query in reverse (going downward
160    to the last top-level state):
161    /a0::t0[p0]/../an-1::tn-1[pn-1]/an::tn[pn] becomes:
162    self::node()[ pn and
163    self::tn[pn]/inv(an)::(tn-1)[pn-1]/.../inv(a1)::t0[p0]/inv(a0)::document()]
164
165    /child::a/attribute::b
166    self::@b/parent::a/parent::doc()
167 *)
168
169 let compile_top_level_step_list l trans states =
170   let rec loop l trans states phi_above =
171     match l with
172     | [] -> assert false
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
178         in
179         (* Only select attribute nodes if the previous axis
180            is attribute *)
181         let phi0 =
182           if axis != Attribute && kind == Tree.NodeKind.Node then
183             phi0 %% (F.not_ F.is_attribute)
184           else phi0
185         in
186         match ll with
187           [] ->
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
192           in
193           let _, trans2, states2 =
194             compile_axis_test Self (test,kind) phi1 trans1 states1
195           in
196           let marking_state =
197             StateSet.choose (StateSet.diff states2 states1)
198           in
199           marking_state, trans2, states2
200         | _ ->
201           let phi1, trans1, states1 =
202             compile_axis_test Self (test,kind) phi0 trans0 states0
203           in
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
208           in
209           loop ll trans2 states2  phi2
210   in
211   let starting = State.next () in
212   let phi0, trans0, states0 =
213     compile_axis_test
214       Self
215       (QNameSet.any, Tree.NodeKind.Node)
216       (F.stay starting)
217       trans
218       states
219   in
220   let mstates, trans, states = loop l trans0 states0 phi0 in
221   starting, mstates, trans, states
222 ;;
223
224 let path p =
225   let sstates, mstates, trans, states =
226     List.fold_left (fun (ass, ams, atrs, asts) p ->
227       let ss, ms, natrs, nasts =
228         match p with
229         | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
230       in
231       (StateSet.add ss ass),
232       (StateSet.add ms ams),
233       natrs,
234       nasts) (StateSet.empty, StateSet.empty, [], StateSet.empty) p
235   in
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.next () 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
243   StateSet.iter
244     (Ata.Builder.add_state builder ~starting:true) sstates;
245   StateSet.iter
246     (Ata.Builder.add_state builder ~selecting:true) mstates;
247   StateSet.iter
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
252     ) l) trans;
253   Ata.Builder.finalize builder