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