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 (*
  17   Time-stamp: <Last modified on 2013-03-05 19:21:37 CET by Kim Nguyen>
  18 *)
  19
  20 open Ast
  21 open Auto
  22 open Utils
  23
  24 let mk_atom l b q =
  25   Ata.SFormula.atom_ (Ata.Move.make (l,b,q))
  26
  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
  34
  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 ]
  39     QNameSet.empty)
  40 let attribute = QNameSet.singleton QName.attribute_map
  41 let root_set = QNameSet.singleton QName.document
  42
  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]
  48    holds.
  49 *)
  50
  51 let compile_axis_test axis test phi trans states =
  52   let q = State.make () in
  53   let phi', trans', states' =
  54     match axis with
  55     | Self ->
  56           (`Epsilon ** q),
  57           (q, [  test => phi ]) :: trans,
  58           states
  59
  60     | Child ->
  61         (`Left ** q),
  62       (q, [ test => phi;
  63             QNameSet.any => (`Right ** q) ]) :: trans,
  64       states
  65
  66     | Descendant self ->
  67         (if self then (`Epsilon ** q) else (`Left ** q)),
  68       (q, [ test => phi;
  69             QNameSet.any => (`Left ** q);
  70             QNameSet.any => (`Right ** q) ]) :: trans,
  71       states
  72
  73     | Parent ->
  74         let q' = State.make () in
  75         let move = (`Up1 ** q %% is_left) ++ (`Up2 ** q' %% is_right) in
  76         move,
  77         (q, [ test => phi ])
  78         :: (q', [ QNameSet.any => move ]) :: trans,
  79         (q' @: states)
  80
  81     | Ancestor self ->
  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),
  85         (q, [ test => phi;
  86               star_set => move ])
  87         :: (q', [ QNameSet.any => move ]) :: trans,
  88         (q' @: states)
  89
  90     | FollowingSibling | PrecedingSibling ->
  91         let move =
  92           if axis = PrecedingSibling then
  93             (`Up2 ** q)
  94           else (`Right ** q %% is_right)
  95         in
  96         move,
  97         (q, [ test => phi;
  98               star_set => move ]) :: trans,
  99         states
 100
 101     | Attribute ->
 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)
 106               test QNameSet.empty
 107           else test
 108         in
 109         (`Left ** q),
 110         (q, [ QNameSet.singleton QName.attribute_map => (`Left ** q') ])
 111         :: (q', [ test => phi;
 112                   QNameSet.any => (`Right ** q') ]) :: trans,
 113         (q' @:states)
 114     | _ -> assert false
 115
 116   in
 117   phi', trans', q @: states'
 118
 119
 120 let compile_rev_axis_test axis test phi trans states =
 121   match axis with
 122   | Attribute -> assert false
 123   | _ -> compile_axis_test (invert_axis axis) test phi trans states
 124 ;;
 125
 126
 127
 128 let rec compile_expr e trans states =
 129   match e with
 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),
 134       trans2,
 135       states2
 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),
 139       trans0,
 140       states0
 141   | Path p -> compile_path p trans states
 142
 143   | _ -> assert false
 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),
 148     ntrans,
 149     nstates) (Ata.SFormula.false_,trans,states) paths
 150
 151 and compile_single_path p trans states =
 152   let steps =
 153     match p with
 154     | Absolute steps ->
 155         (Ancestor false, QNameSet.singleton QName.document, [])::steps
 156     | Relative steps -> steps
 157   in
 158   compile_step_list steps trans states
 159
 160 and compile_step_list l trans states =
 161   match l with
 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
 167       in
 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
 171
 172 let compile_top_level_step_list l trans states =
 173   let rec loop l trans states phi_above =
 174     match l with
 175     | (axis, test, elist) :: [] ->
 176         let phi0, trans0, states0 =
 177           compile_rev_axis_test axis QNameSet.any phi_above trans states
 178         in
 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
 183         in
 184         let _, trans2, states2 =
 185           compile_axis_test Self test phi1 trans1 states1
 186           in
 187         let marking_state =
 188           StateSet.choose (StateSet.diff states2 states1)
 189         in
 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
 194         in
 195         let phi1, trans1, states1 =
 196           compile_axis_test Self test phi0 trans0 states0
 197         in
 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
 202           in
 203           loop ll trans2 states2 phi2
 204     | _ -> assert false
 205   in
 206   let phi0, trans0, states0 =
 207     compile_axis_test
 208       Self
 209       (QNameSet.singleton QName.document)
 210       Ata.SFormula.true_
 211       trans
 212       states
 213   in
 214   loop l trans0 states0 phi0
 215 ;;
 216
 217
 218 let path p =
 219   let mstates, trans, states = List.fold_left (fun (ams, atrs, asts) p ->
 220     let ms, natrs, nasts =
 221       match p with
 222       | Absolute l | Relative l -> compile_top_level_step_list l atrs asts
 223     in
 224     (StateSet.add ms ams), natrs, nasts) (StateSet.empty, [], StateSet.empty) p
 225   in
 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
 232     ) l) trans;
 233   Ata.complete_transitions a;
 234   Ata.normalize_negations a;
 235   a