Initial public import
Sapan Bhatia [Fri, 12 Nov 2010 16:00:09 +0000 (11:00 -0500)]
30 files changed:
LICENSE [new file with mode: 0644]
Makefile [new file with mode: 0644]
README [new file with mode: 0644]
acls/0.acl [new file with mode: 0644]
acls/1.acl [new file with mode: 0644]
acls/S.acl [new file with mode: 0644]
acls/Slices.acl [new file with mode: 0644]
acls/Slices2.acl [new file with mode: 0644]
acls/path.acl [new file with mode: 0644]
acls/simple.acl [new file with mode: 0644]
acls/simple.acl.orig [new file with mode: 0644]
acls/simple2.acl [new file with mode: 0644]
acls/simple2.acl.orig [new file with mode: 0644]
acls/slices2.acl [new file with mode: 0644]
acls/test.acl [new file with mode: 0644]
acls/test2.acl [new file with mode: 0644]
acls/test22.acl [new file with mode: 0644]
aft.ml [new file with mode: 0644]
aft_il.ml [new file with mode: 0644]
aft_lexer.ml [new file with mode: 0644]
aft_lexer.mll [new file with mode: 0644]
aft_minterms.ml [new file with mode: 0644]
aft_parser.ml [new file with mode: 0644]
aft_parser.mly [new file with mode: 0644]
aft_types.ml [new file with mode: 0644]
globals.ml [new file with mode: 0644]
python.ml [new file with mode: 0644]
python_dict.ml [new file with mode: 0644]
xpath_ext.ml [new file with mode: 0644]
xpath_syntax.ml [new file with mode: 0644]

diff --git a/LICENSE b/LICENSE
new file mode 100644 (file)
index 0000000..00525c7
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,3 @@
+Afterthought version (0.1)
+
+Released under the terms of the BSD license. I.e., no warranty, not even implied - you are using this software at your own risk. If you accept these conditions, then you are free to use, modify and distribute it in 
diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..b436e11
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,37 @@
+all: aft.b
+
+include .dep
+
+.SUFFIXES: .ml .cmo
+.SUFFIXES: .mli .cmi
+.SUFFIXES: .ml .cmx
+.SUFFIXES: .mll .ml
+.SUFFIXES: .mly .ml
+
+.ml.cmo:
+       ocamlc -g -c $(INCLUDEDIR) $<
+
+.mli.cmi:
+       ocamlopt -c $<
+
+.ml.cmx: 
+       ocamlopt $(CFLAGS) -c $(INCLUDEDIR) $<
+
+.mly.ml: 
+       ocamlyacc $< 
+
+.mll.ml:
+       ocamllex $< 
+
+aft_parser.ml: aft_parser.mly
+
+aft_lexer.ml: aft_lexer.mll 
+
+aft.b: globals.cmo aft_types.cmo aft_lexer.cmo xpath_syntax.cmo aft_parser.cmo xpath_ext.cmo python.cmo python_dict.cmo aft_minterms.cmo aft.cmo
+       ocamlc -g globals.cmo aft_types.cmo xpath_ext.cmo xpath_syntax.cmo aft_parser.cmo aft_lexer.cmo python.cmo python_dict.cmo aft_minterms.cmo aft.cmo -o aft.b
+
+dep:
+       ocamldep *.ml *.mly *.mll > .dep
+
+clean:
+       rm -f *.cmo 
diff --git a/README b/README
new file mode 100644 (file)
index 0000000..be1bcd3
--- /dev/null
+++ b/README
@@ -0,0 +1,47 @@
+[In hindsight. This README was written in under 5 minutes, please contact sapanb@cs.princeton.edu if you have questions.]
+
+Afterthought is mechanism for deploying access control policies based on data gathered via multiple data sources. A predecessor to Afterthought, sfatables, assumed that all such state was available in XML format. Afterthought is more pragmatic in that it does not require the data to be serialized unless absolutely necessary.
+
+The result of using Afterthought is a program (in Python) that applies the desired access control policies efficiently.
+
+An Afterthought program, just like its Python counterpart is a decision tree whose general form is:
+
+PROGRAM ::= Access Granted | Access Denied | if (<some property of data>) then PROGRAM else PROGRAM
+
+...where <some property of data> is specified using XPath. Ignoring details involving the database schema and the involvement of multiple data sources, here's an example of an afterthought program:
+
+---
+
+/Slices[$filter] -> {
+    /caller[@roles!="admin"] -> {
+       /caller[@roles="pi" or @roles="tech"] -> {
+         /Slices[@site=/caller/@site] -> { true }
+       }
+       | /caller[@roles="user"] -> {
+         /Slices[@slice_id = /caller/@slice_ids] -> { true }
+       }
+    }
+}
+
+--
+
+- $filter is a free variable provided by the environment. 
+- /Slices is a database table backed up by SQL (data source 1)
+- caller is an in-memory python dict that stores the caller's authentication state (data source 2)
+
+---
+
+Afterthought can handle multiple access control policies naturally. In general,
+
+Program 1 + Program 2 = <body of Program 1> '|' <body of Program 2>
+
+...making it a possible to extend policies.
+
+---
+
+The goal of the Aft compiler is to "partially evaluate" the policy incrementally till it has been reduced to a verdict. E.g. in the above program, we first evaluate the predicates on 'caller' followed by those on Slices. Rather than by extracting the whole slice table, the latter can be deferred to SQL, which can use its indexing to evaluate the predicate efficiently.
+
+Future work-->
+
+* Specify optimization constraints at a finer grain
+* Profile-driven optimization
diff --git a/acls/0.acl b/acls/0.acl
new file mode 100644 (file)
index 0000000..ba66466
--- /dev/null
@@ -0,0 +1 @@
+0.0
diff --git a/acls/1.acl b/acls/1.acl
new file mode 100644 (file)
index 0000000..d3827e7
--- /dev/null
@@ -0,0 +1 @@
+1.0
diff --git a/acls/S.acl b/acls/S.acl
new file mode 100644 (file)
index 0000000..e5ac68b
--- /dev/null
@@ -0,0 +1,39 @@
+/REQUEST['admin' != /caller/@roles]-> {
+    /caller[@roles = 'pi'] ->{
+        /REQUEST/Add -> {
+            @site_id = /REQUEST/caller/@site_ids
+                        and count(@slice_ids) >= @max_slices
+                        and @enabled
+        }
+        /REQUEST/Delete -> {
+            /[not not @peer_id] -> { (false) }
+            whitelist = ;
+            /[true] -> {
+                /[/REQUEST/caller/@person_id == @person_ids
+                    or ('pi' == //REQUEST/caller/@roles and @site_id == //REQUEST/caller/@site_ids)
+                    and (not whitelist or @slice_id == whitelist)]
+            }
+
+        }
+        /REQUEST/Update -> {
+            [not not @peer_id] -> { /[false] }
+            whitelist = /node/@slice_ids_whitelist;
+            /[true] -> {
+                     /[/REQUEST/caller/@person_id == @person_ids
+                        or ('pi' == //REQUEST/caller/@roles and @site_id == //REQUEST/caller/@site_ids)
+                        and (not whitelist or @slice_id == whitelist)]
+                 }
+        }
+        /REQUEST/Get {
+            caller_site_ids = /REQUEST/caller/@site_ids;
+            ;
+            /[@slice_id == /DB/sites[@site_id == caller_site_ids]/@slice_ids]
+        }
+    }
+    ||
+    /[true] -> / [false]
+}
+||
+/[true] {
+   / [true]
+}
diff --git a/acls/Slices.acl b/acls/Slices.acl
new file mode 100644 (file)
index 0000000..7133649
--- /dev/null
@@ -0,0 +1,39 @@
+(* Match requests where the caller is not an admin *) 
+/REQUEST/caller['admin' not in @roles] -> {
+    valid_slice_ids = /@slice_ids;
+    /[@roles=='pi']->{
+        /REQUEST/Add -> {
+            [@site_id in /REQUEST/caller/@site_ids
+                        and count(@slice_ids) >= @max_slices
+                        and @enabled]
+        }
+        /REQUEST/Delete 
+        /REQUEST/Update -> {
+            [not not @peer_id] -> { /[false] }
+            whitelist = /node/@slice_ids_whitelist;
+            _ -> {
+                     /[/REQUEST/caller/@person_id in @person_ids
+                        or ('pi' in //REQUEST/caller/@roles and @site_id in //REQUEST/caller/@site_ids)
+                        and (not whitelist or @slice_id in whitelist)]
+                 }
+        }
+        /REQUEST/Get {
+            caller_site_ids = /REQUEST/caller/@site_ids;
+            valid_slice_ids = /DB/sites[@site_id in caller_site_ids]/@slice_ids;
+            /[@slice_id in valid_slice_ids]
+        }
+    }
+    _ -> / [false]
+}
+
+_ {
+   / [true]
+}
+
+(* XXX:
+    Not covered:
+        - Accepted fields for AddSlice, including tags
+        - Check slice name format
+    Changes:
+        - Assuming that the node whitelist goes into the slice
+*)
diff --git a/acls/Slices2.acl b/acls/Slices2.acl
new file mode 100644 (file)
index 0000000..985e4f1
--- /dev/null
@@ -0,0 +1,38 @@
+(* Match requests where the caller is not an admin *) 
+/REQUEST/caller['admin' not in @roles]->{
+    valid_slice_ids = /REQUEST/caller/@slice_ids;
+    /REQUEST/caller[@roles=='pi']->{
+        /REQUEST/Add -> {
+            [ count(/REQUEST/caller/Site/@slice_ids) >= @max_slices
+                        and /REQUEST/caller/Site/@enabled]
+        }
+        /REQUEST/Delete 
+        /REQUEST/Update -> {
+            /[not not @peer_id] -> { /[false] }
+            whitelist = /node/@slice_ids_whitelist;
+            _ -> {
+                     /[/REQUEST/caller/@person_id in @person_ids
+                        or ('pi' in //REQUEST/caller/@roles and @site_id in //REQUEST/caller/@site_ids)
+                        and (not whitelist or @slice_id in whitelist)]
+                 }
+        }
+        /REQUEST/Get {
+            caller_site_ids = /REQUEST/caller/@site_ids;
+            valid_slice_ids = /DB/sites[@site_id in caller_site_ids]/@slice_ids;
+            /[@slice_id in valid_slice_ids]
+        }
+    }
+    _ -> / [false]
+}
+
+_ {
+   / [true]
+}
+
+(* XXX:
+    Not covered:
+        - Accepted fields for AddSlice, including tags
+        - Check slice name format
+    Changes:
+        - Assuming that the node whitelist goes into the slice
+*)
diff --git a/acls/path.acl b/acls/path.acl
new file mode 100644 (file)
index 0000000..81bdc0d
--- /dev/null
@@ -0,0 +1 @@
+/x[@t=1] -> {1.0}
diff --git a/acls/simple.acl b/acls/simple.acl
new file mode 100644 (file)
index 0000000..83a1373
--- /dev/null
@@ -0,0 +1,4 @@
+/X[moo="bla"] -> {
+    /z -> { 1.0 } 
+    | /X[Y=/z/bling] -> {1.0}
+}
diff --git a/acls/simple.acl.orig b/acls/simple.acl.orig
new file mode 100644 (file)
index 0000000..6885ba1
--- /dev/null
@@ -0,0 +1,3 @@
+/x[$y=2] -> {
+  /Z[$z=2] -> { 1.0 }
+ }
diff --git a/acls/simple2.acl b/acls/simple2.acl
new file mode 100644 (file)
index 0000000..6106250
--- /dev/null
@@ -0,0 +1,3 @@
+/X -> {
+  1.0
+}
diff --git a/acls/simple2.acl.orig b/acls/simple2.acl.orig
new file mode 100644 (file)
index 0000000..0dcbfe0
--- /dev/null
@@ -0,0 +1,3 @@
+/X[$y=2] -> {
+  1.0
+}
diff --git a/acls/slices2.acl b/acls/slices2.acl
new file mode 100644 (file)
index 0000000..5bc7f60
--- /dev/null
@@ -0,0 +1,37 @@
+/REQUEST/caller['admin' not in @roles] -> {
+    /[@roles=='pi']->{
+        /REQUEST/Add -> {
+            [@site_id in /REQUEST/caller/@site_ids
+                        and count(@slice_ids) >= @max_slices
+                        and @enabled]
+        }
+        /REQUEST/Delete 
+        /REQUEST/Update -> {
+            [not not @peer_id] -> { /[false] }
+            whitelist = /node/@slice_ids_whitelist;
+            _ -> {
+                     /[/REQUEST/caller/@person_id in @person_ids
+                        or ('pi' in //REQUEST/caller/@roles and @site_id in //REQUEST/caller/@site_ids)
+                        and (not whitelist or @slice_id in whitelist)]
+                 }
+        }
+        /REQUEST/Get {
+            caller_site_ids = /REQUEST/caller/@site_ids;
+            valid_slice_ids = /DB/sites[@site_id in caller_site_ids]/@slice_ids;
+            /[@slice_id in valid_slice_ids]
+        }
+    }
+    _ -> / [false]
+}
+
+_ {
+   / [true]
+}
+
+(* XXX:
+    Not covered:
+        - Accepted fields for AddSlice, including tags
+        - Check slice name format
+    Changes:
+        - Assuming that the node whitelist goes into the slice
+*)
diff --git a/acls/test.acl b/acls/test.acl
new file mode 100644 (file)
index 0000000..8dffba2
--- /dev/null
@@ -0,0 +1,10 @@
+/x -> {
+  /y -> {
+    1.0
+  }
+  | /x -> {
+    /a -> { 1.0 }
+    | /b -> { 0.0 }
+    | /c -> { /d -> { 1.0 } }
+  }
+}
diff --git a/acls/test2.acl b/acls/test2.acl
new file mode 100644 (file)
index 0000000..b17e38d
--- /dev/null
@@ -0,0 +1,10 @@
+/Slices[$filter] -> {
+    /caller[@roles!="admin"] -> {
+       /caller[@roles="pi" or @roles="tech"] -> {
+         /Slices[@site=/caller/@site] -> { 1.0 }
+       }
+       | /caller[@roles="user"] -> {
+         /Slices[@slice_id = /caller/@slice_ids] -> { 1.0 }
+       }
+    }
+}
diff --git a/acls/test22.acl b/acls/test22.acl
new file mode 100644 (file)
index 0000000..7fc3d96
--- /dev/null
@@ -0,0 +1,18 @@
+/Slices[cond] -> {
+/caller[cond] -> {
+/caller[cond] -> {
+/Slices[cond] -> {
+1.000000}
+| {0.000000}
+}
+| {/caller[cond] -> {
+/Slices[cond] -> {
+1.000000}
+| {0.000000}
+}
+| {0.000000}
+}
+}
+| {0.000000}
+}
+| {0.000000}
diff --git a/aft.ml b/aft.ml
new file mode 100644 (file)
index 0000000..42d521b
--- /dev/null
+++ b/aft.ml
@@ -0,0 +1,43 @@
+open Xpath_syntax
+open Xpath_ext
+open Aft_parser
+open Aft_lexer
+open Aft_minterms
+open Aft_types
+open Printf
+open Python_dict
+open Python
+open Globals
+
+let lookup_term m_syms termid =
+    if (termid<255) then
+      let str = Array.get m_syms termid in
+        (pretty_print_xpath_path str)
+    else
+      let str = Array.get m_syms (termid-255) in
+        String.concat "" ["!";(pretty_print_xpath_path str)]
+
+let rec print_term m_syms lst = 
+    match lst with
+      |(a::(b::cdr)) ->
+          let str = lookup_term m_syms a in
+            printf "%s." str;print_term m_syms (b::cdr)
+      |(a::cdr) ->
+          let str = lookup_term m_syms a in
+            printf "%s" str;print_term m_syms cdr
+      |[] -> printf "\n"
+
+let main () =
+  let l_inp = Aft_lexer.parse_from_channel Pervasives.stdin in
+  let l = aft_to_il l_inp in
+  let m_list, m_syms, n_terms = aft_to_minterms l in
+  let opt_order = optimize_minterms m_syms n_terms in
+  let o_aft = minterms_to_aft m_list m_syms opt_order n_terms in
+  let o_py = from_aft o_aft in
+    (*print_minterms m_list;*)
+    (*List.iter (fun x->printf "%d->" x;printf "%s\n" (lookup_term m_syms x))
+      opt_order*)
+    pretty_print_block 0 o_py
+;;
+
+main ()
diff --git a/aft_il.ml b/aft_il.ml
new file mode 100644 (file)
index 0000000..930cec6
--- /dev/null
+++ b/aft_il.ml
@@ -0,0 +1,116 @@
+open Xpath_syntax
+open Xpath_ext
+open Aft_types
+open Globals
+open Array
+
+type aft_symtab = (path_expr, int) Hashtbl.t
+type aft_syms = path_expr array
+type aft_minterm = (path_expr,int) Hashtbl.t * (int list) list
+
+exception EvalAxisNotSupported
+
+let aft_to_minterms aft_rep =
+  let minterm_hash:aft_symtab = Hashtbl.create 128 in
+  let syms:aft_syms = Array.create 128 (Expr(Number_literal(1.0))) in
+  let hash_index = ref 0 in
+  let rec aft_to_minterms_rec prefix cur_term (aft_rep: access_spec) = 
+    let rec pattern_match_to_minterms_rec prefix cur_term (pat_match: clause list) =
+        match pat_match with
+            Clause(m, aspec)::cdr -> 
+              let term = try Hashtbl.find minterm_hash m with
+                | Not_found ->
+                    Hashtbl.add minterm_hash m !hash_index;
+                    Array.set syms !hash_index m;
+                  hash_index := !hash_index + 1;
+                  !hash_index-1
+              in
+              let right_function = pattern_match_to_minterms_rec ((term+255)::prefix) cur_term cdr in
+                aft_to_minterms_rec (term::prefix) right_function aspec
+            | [] -> cur_term
+    in
+    match aft_rep with
+      | PatternMatch(cl_list) -> 
+          pattern_match_to_minterms_rec prefix cur_term cl_list
+      | Filter(Number_literal(x))->
+          if (x=0.0) then
+            cur_term
+          else
+          if (x=1.0) then (prefix::cur_term)
+          else begin
+            print "Reached leaf %f" x;raise Aft_error
+          end
+      | _ -> 
+            cur_term
+  in
+  let minterm_list = aft_to_minterms_rec [] [] aft_rep in
+    (minterm_list, syms, !hash_index)
+
+let rec eval xpath_path =
+  match xpath_path with 
+    | Expr(expr) ->
+        0
+    | Pipe(e1,e2) ->  
+        let v = eval e1 in
+          if (-1=v) then eval e2 else v
+    | Slash(e1,e2) ->
+        let v = eval e1 in
+          if (-1=v) then eval e2 else v
+    | Condition(e,expr) ->
+        eval e
+    | Root ->
+        -1
+    | Axis(_,e)->
+        eval e
+    | Name(s)->
+        let c = String.get s 0 in
+        let ic = int_of_char c in
+          if (ic > 64 && ic < 91) then 1 else 0
+    | _ -> raise EvalAxisNotSupported
+
+let optimize_minterms m_syms n =
+  let rec gen_lst n suffix = if (n==(-1)) then suffix else gen_lst (n-1) (n::suffix) in
+  let lst = gen_lst (n-1) [] in
+  let cmp_func a1 a2 = 
+    let term1 = Array.get m_syms a1 in
+    let term2 = Array.get m_syms a2 in
+      if ((eval term1) > (eval term2)) then 1 else 0
+  in
+  List.stable_sort cmp_func lst
+
+let rec minterms_to_aft m_list m_syms order n_terms =
+  match order with
+    | [] ->
+        const_to_aft m_list
+    | car::cdr ->
+        let right = reduce_true m_syms car m_list in
+        let left = reduce_false m_syms car m_list in
+        let right_aft = minterms_to_aft right m_syms cdr (n_terms-1) in
+        let left_aft = minterms_to_aft left m_syms cdr (n_terms-1) in
+          PatternMatch ((var_to_aft car m_syms) (True(right_aft)) (False(left_aft))) 
+
+let rec aft_to_il l_inp = 
+  let rec aft_to_il_rec prefix cur_term (aft_rep: access_spec) = 
+    let rec pattern_match_to_il  (pat_match: clause list) =
+        match pat_match with
+            Clause(m, aspec)::cdr -> 
+              let right_function = pattern_match_to_il cdr in
+                aft_to_minterms_rec (term::prefix) right_function aspec
+            | [] -> cur_term
+    in
+    match aft_rep with
+      | PatternMatch(cl_list) -> 
+          pattern_match_to_minterms_rec prefix cur_term cl_list
+      | Filter(Number_literal(x))->
+          if (x=0.0) then
+            cur_term
+          else
+          if (x=1.0) then (prefix::cur_term)
+          else begin
+            print "Reached leaf %f" x;raise Aft_error
+          end
+      | _ -> 
+            cur_term
+  in
+  let minterm_list = aft_to_minterms_rec [] [] aft_rep in
+  
diff --git a/aft_lexer.ml b/aft_lexer.ml
new file mode 100644 (file)
index 0000000..26bd6dc
--- /dev/null
@@ -0,0 +1,585 @@
+# 1 "aft_lexer.mll"
+  open Aft_parser
+  open Xpath_ext
+  open Parsing
+  open Printf
+  open Lexing
+
+  let cut_at_ws s c =
+    let l = String.length s in
+    let rec aux i =
+      if i = l then s 
+      else match s.[i] with
+       | ' ' | '\t' | '\r' | '\n' -> String.sub s 0 i
+        | z when z=c -> String.sub s 0 i
+       | _ -> aux (succ i)
+    in
+    aux 0
+
+# 21 "aft_lexer.ml"
+let __ocaml_lex_tables = {
+  Lexing.lex_base = 
+   "\000\000\252\255\253\255\078\000\255\255\192\000\225\255\226\255\
+    \227\255\000\000\086\000\028\000\230\255\022\001\233\255\000\000\
+    \002\000\003\000\239\255\240\255\241\255\242\255\001\000\245\255\
+    \246\255\247\255\248\255\029\000\250\255\251\255\011\000\145\001\
+    \254\255\226\001\147\001\001\000\255\255\084\002\005\000\253\255\
+    \249\255\244\255\238\255\235\255\234\255\162\002\220\002\042\003\
+    \229\255\158\000";
+  Lexing.lex_backtrk = 
+   "\004\000\255\255\255\255\001\000\255\255\255\255\255\255\255\255\
+    \255\255\027\000\255\255\255\255\255\255\255\255\255\255\019\000\
+    \018\000\255\255\255\255\255\255\255\255\255\255\012\000\255\255\
+    \255\255\255\255\255\255\023\000\255\255\255\255\003\000\025\000\
+    \255\255\255\255\255\255\255\255\255\255\025\000\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\024\000\255\255\024\000\
+    \255\255\027\000";
+  Lexing.lex_default = 
+   "\255\255\000\000\000\000\255\255\000\000\255\255\000\000\000\000\
+    \000\000\255\255\010\000\011\000\000\000\255\255\000\000\255\255\
+    \255\255\255\255\000\000\000\000\000\000\000\000\255\255\000\000\
+    \000\000\000\000\000\000\255\255\000\000\000\000\255\255\255\255\
+    \000\000\255\255\255\255\255\255\000\000\255\255\255\255\000\000\
+    \000\000\000\000\000\000\000\000\000\000\255\255\255\255\255\255\
+    \000\000\255\255";
+  Lexing.lex_trans = 
+   "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\001\000\002\000\000\000\000\000\001\000\038\000\038\000\
+    \000\000\000\000\038\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \001\000\000\000\000\000\000\000\000\000\038\000\000\000\000\000\
+    \000\000\000\000\004\000\000\000\000\000\032\000\049\000\041\000\
+    \009\000\009\000\009\000\009\000\009\000\009\000\009\000\009\000\
+    \009\000\009\000\039\000\036\000\000\000\044\000\048\000\043\000\
+    \042\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\040\000\000\000\000\000\000\000\003\000\
+    \000\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\048\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\000\000\000\000\000\000\000\000\003\000\000\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\007\000\008\000\000\000\000\000\007\000\049\000\049\000\
+    \049\000\049\000\049\000\049\000\049\000\049\000\049\000\049\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \007\000\017\000\011\000\000\000\013\000\000\000\000\000\010\000\
+    \025\000\026\000\012\000\014\000\020\000\027\000\022\000\030\000\
+    \009\000\009\000\009\000\009\000\009\000\009\000\009\000\009\000\
+    \009\000\009\000\000\000\000\000\016\000\018\000\015\000\000\000\
+    \021\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\024\000\255\255\023\000\000\000\031\000\
+    \000\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\028\000\019\000\029\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\255\255\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\000\000\000\000\000\000\000\000\045\000\000\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\034\000\034\000\034\000\034\000\034\000\000\000\
+    \034\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\034\000\000\000\034\000\000\000\000\000\000\000\000\000\
+    \000\000\032\000\000\000\032\000\000\000\000\000\031\000\031\000\
+    \006\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\033\000\000\000\035\000\000\000\000\000\
+    \000\000\000\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\000\000\000\000\000\000\000\000\
+    \031\000\000\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\012\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\036\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\000\000\000\000\000\000\
+    \000\000\037\000\000\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\038\000\038\000\000\000\
+    \000\000\038\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\038\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\032\000\000\000\000\000\000\000\
+    \000\000\037\000\037\000\000\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\000\000\
+    \000\000\000\000\000\000\037\000\000\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\045\000\
+    \045\000\000\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\046\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\000\000\000\000\000\000\
+    \000\000\045\000\000\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\000\000\
+    \000\000\000\000\000\000\047\000\000\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\000\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\000\000\000\000\000\000\
+    \000\000\047\000\000\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000";
+  Lexing.lex_check = 
+   "\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\000\000\000\000\255\255\255\255\000\000\038\000\038\000\
+    \255\255\255\255\038\000\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \000\000\255\255\255\255\255\255\255\255\038\000\255\255\255\255\
+    \255\255\255\255\000\000\255\255\255\255\038\000\009\000\022\000\
+    \009\000\009\000\009\000\009\000\009\000\009\000\009\000\009\000\
+    \009\000\009\000\030\000\035\000\255\255\015\000\011\000\016\000\
+    \017\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\027\000\255\255\255\255\255\255\000\000\
+    \255\255\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+    \000\000\000\000\000\000\003\000\003\000\010\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\255\255\255\255\255\255\255\255\003\000\255\255\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\
+    \003\000\005\000\005\000\255\255\255\255\005\000\049\000\049\000\
+    \049\000\049\000\049\000\049\000\049\000\049\000\049\000\049\000\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \005\000\005\000\005\000\255\255\005\000\255\255\255\255\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\255\255\255\255\005\000\005\000\005\000\255\255\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\011\000\005\000\255\255\005\000\
+    \255\255\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\005\000\005\000\
+    \005\000\005\000\005\000\005\000\005\000\005\000\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\010\000\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\255\255\255\255\255\255\255\255\013\000\255\255\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\013\000\013\000\013\000\013\000\013\000\013\000\013\000\
+    \013\000\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\031\000\031\000\034\000\034\000\031\000\255\255\
+    \034\000\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\031\000\255\255\034\000\255\255\255\255\255\255\255\255\
+    \255\255\031\000\255\255\034\000\255\255\255\255\031\000\031\000\
+    \005\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\255\255\034\000\255\255\255\255\
+    \255\255\255\255\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\255\255\255\255\255\255\255\255\
+    \031\000\255\255\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\031\000\031\000\031\000\031\000\
+    \031\000\031\000\031\000\031\000\033\000\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\033\000\255\255\255\255\255\255\
+    \255\255\255\255\255\255\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\255\255\255\255\255\255\
+    \255\255\033\000\255\255\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\033\000\033\000\033\000\
+    \033\000\033\000\033\000\033\000\033\000\037\000\037\000\255\255\
+    \255\255\037\000\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\037\000\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\037\000\255\255\255\255\255\255\
+    \255\255\037\000\037\000\255\255\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\255\255\
+    \255\255\255\255\255\255\037\000\255\255\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+    \037\000\037\000\037\000\037\000\037\000\037\000\037\000\045\000\
+    \045\000\255\255\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\255\255\255\255\255\255\
+    \255\255\255\255\255\255\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\255\255\255\255\255\255\
+    \255\255\045\000\255\255\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\045\000\045\000\045\000\
+    \045\000\045\000\045\000\045\000\045\000\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\255\255\
+    \255\255\255\255\255\255\046\000\255\255\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\046\000\
+    \046\000\046\000\046\000\046\000\046\000\046\000\046\000\047\000\
+    \047\000\255\255\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\255\255\255\255\255\255\
+    \255\255\047\000\255\255\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\047\000\047\000\047\000\
+    \047\000\047\000\047\000\047\000\047\000\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+    \255\255\255\255\255\255";
+  Lexing.lex_base_code = 
+   "";
+  Lexing.lex_backtrk_code = 
+   "";
+  Lexing.lex_default_code = 
+   "";
+  Lexing.lex_trans_code = 
+   "";
+  Lexing.lex_check_code = 
+   "";
+  Lexing.lex_code = 
+   "";
+}
+
+let rec token_after_not_op lexbuf =
+    __ocaml_lex_token_after_not_op_rec lexbuf 0
+and __ocaml_lex_token_after_not_op_rec lexbuf __ocaml_lex_state =
+  match Lexing.engine __ocaml_lex_tables __ocaml_lex_state lexbuf with
+      | 0 ->
+# 39 "aft_lexer.mll"
+           ( MUL )
+# 338 "aft_lexer.ml"
+
+  | 1 ->
+# 40 "aft_lexer.mll"
+           ( 
+      match Lexing.lexeme lexbuf with
+       | "and" -> AND
+       | "or"  -> OR
+       | "mod" -> MOD
+       | "div" -> DIV
+       | s -> failwith ("Unknown operator "^s)
+    )
+# 350 "aft_lexer.ml"
+
+  | 2 ->
+# 48 "aft_lexer.mll"
+             ( new_line lexbuf; token_after_not_op lexbuf )
+# 355 "aft_lexer.ml"
+
+  | 3 ->
+# 49 "aft_lexer.mll"
+           ( token_after_not_op lexbuf )
+# 360 "aft_lexer.ml"
+
+  | 4 ->
+# 50 "aft_lexer.mll"
+           ( token lexbuf )
+# 365 "aft_lexer.ml"
+
+  | __ocaml_lex_state -> lexbuf.Lexing.refill_buff lexbuf; __ocaml_lex_token_after_not_op_rec lexbuf __ocaml_lex_state
+
+and token lexbuf =
+    __ocaml_lex_token_rec lexbuf 5
+and __ocaml_lex_token_rec lexbuf __ocaml_lex_state =
+  match Lexing.engine __ocaml_lex_tables __ocaml_lex_state lexbuf with
+      | 0 ->
+# 53 "aft_lexer.mll"
+                    ( 
+      let s = Lexing.lexeme lexbuf in
+      let s = cut_at_ws s ':' in
+      AXIS s
+    )
+# 380 "aft_lexer.ml"
+
+  | 1 ->
+# 59 "aft_lexer.mll"
+                  (
+      let s = Lexing.lexeme lexbuf in
+      let s = cut_at_ws s '(' in
+      match s with
+               | "comment" | "text" | "processing-instruction" | "node" -> NODE_TYPE s
+               | _ -> FUNCTION_NAME s
+    )
+# 391 "aft_lexer.ml"
+
+  | 2 ->
+# 68 "aft_lexer.mll"
+           ( DOUBLESLASH )
+# 396 "aft_lexer.ml"
+
+  | 3 ->
+# 69 "aft_lexer.mll"
+           ( SLASH )
+# 401 "aft_lexer.ml"
+
+  | 4 ->
+# 71 "aft_lexer.mll"
+           ( RBRACE )
+# 406 "aft_lexer.ml"
+
+  | 5 ->
+# 72 "aft_lexer.mll"
+           ( LBRACE )
+# 411 "aft_lexer.ml"
+
+  | 6 ->
+# 73 "aft_lexer.mll"
+           ( POINT )
+# 416 "aft_lexer.ml"
+
+  | 7 ->
+# 75 "aft_lexer.mll"
+           ( RPAREN )
+# 421 "aft_lexer.ml"
+
+  | 8 ->
+# 76 "aft_lexer.mll"
+           ( LPAREN )
+# 426 "aft_lexer.ml"
+
+  | 9 ->
+# 78 "aft_lexer.mll"
+           ( LBRACKET )
+# 431 "aft_lexer.ml"
+
+  | 10 ->
+# 79 "aft_lexer.mll"
+           ( RBRACKET )
+# 436 "aft_lexer.ml"
+
+  | 11 ->
+# 82 "aft_lexer.mll"
+           ( DOUBLEDOT )
+# 441 "aft_lexer.ml"
+
+  | 12 ->
+# 83 "aft_lexer.mll"
+           ( DOT )
+# 446 "aft_lexer.ml"
+
+  | 13 ->
+# 85 "aft_lexer.mll"
+           ( AT )
+# 451 "aft_lexer.ml"
+
+  | 14 ->
+# 86 "aft_lexer.mll"
+           ( COMMA )
+# 456 "aft_lexer.ml"
+
+  | 15 ->
+# 87 "aft_lexer.mll"
+           ( PIPE )
+# 461 "aft_lexer.ml"
+
+  | 16 ->
+# 89 "aft_lexer.mll"
+           ( EQUAL )
+# 466 "aft_lexer.ml"
+
+  | 17 ->
+# 90 "aft_lexer.mll"
+           ( NOTEQUAL )
+# 471 "aft_lexer.ml"
+
+  | 18 ->
+# 91 "aft_lexer.mll"
+           ( LT )
+# 476 "aft_lexer.ml"
+
+  | 19 ->
+# 92 "aft_lexer.mll"
+           ( GT )
+# 481 "aft_lexer.ml"
+
+  | 20 ->
+# 93 "aft_lexer.mll"
+           ( LTE )
+# 486 "aft_lexer.ml"
+
+  | 21 ->
+# 94 "aft_lexer.mll"
+           ( GTE )
+# 491 "aft_lexer.ml"
+
+  | 22 ->
+# 95 "aft_lexer.mll"
+           ( PLUS )
+# 496 "aft_lexer.ml"
+
+  | 23 ->
+# 96 "aft_lexer.mll"
+           ( MINUS )
+# 501 "aft_lexer.ml"
+
+  | 24 ->
+# 98 "aft_lexer.mll"
+              ( 
+      let s = Lexing.lexeme lexbuf in
+      let s = String.sub s 1 (String.length s - 1) in
+      VAR s
+    )
+# 510 "aft_lexer.ml"
+
+  | 25 ->
+# 104 "aft_lexer.mll"
+                                ( NAME_TEST (Lexing.lexeme lexbuf) )
+# 515 "aft_lexer.ml"
+
+  | 26 ->
+# 106 "aft_lexer.mll"
+             (  
+     let s = Lexing.lexeme lexbuf in
+     let s = String.sub s 1 (String.length s - 2) in
+     LITERAL s 
+   )
+# 524 "aft_lexer.ml"
+
+  | 27 ->
+# 112 "aft_lexer.mll"
+             ( NUMBER (float_of_string (Lexing.lexeme lexbuf)) )
+# 529 "aft_lexer.ml"
+
+  | 28 ->
+# 113 "aft_lexer.mll"
+             ( new_line lexbuf; token lexbuf )
+# 534 "aft_lexer.ml"
+
+  | 29 ->
+# 114 "aft_lexer.mll"
+             ( token lexbuf )
+# 539 "aft_lexer.ml"
+
+  | 30 ->
+# 115 "aft_lexer.mll"
+             ( EOF )
+# 544 "aft_lexer.ml"
+
+  | __ocaml_lex_state -> lexbuf.Lexing.refill_buff lexbuf; __ocaml_lex_token_rec lexbuf __ocaml_lex_state
+
+;;
+
+# 117 "aft_lexer.mll"
+  let make_lexer () =
+    let previous_op = ref true in
+    fun lexbuf ->
+      let tok = 
+       if !previous_op then token lexbuf 
+       else token_after_not_op lexbuf in
+      (match tok with
+        | AT | AXIS _ | FUNCTION_NAME _ | NODE_TYPE _ | LBRACKET | LPAREN
+        | AND | OR | MOD | DIV | MUL | SLASH | DOUBLESLASH
+        | PIPE | PLUS | MINUS | EQUAL | NOTEQUAL | LT | GT | LTE | GTE 
+            -> previous_op := true
+        | _ -> previous_op := false
+      );
+      tok
+
+  let parse_expr x =    
+    let lexbuf = Lexing.from_string x in
+    let lexer  = make_lexer () in
+    let result = Aft_parser.aft_pattern_match lexer lexbuf in
+        result
+
+  let parse_from_channel x = 
+    let lexbuf = Lexing.from_channel x in
+    let lexer = make_lexer () in
+    let result = 
+        try 
+            Aft_parser.access_spec lexer lexbuf 
+        with Parse_error ->
+            printf "Error at line %d char %d.\n" (lexbuf.lex_curr_p.pos_lnum)
+                (lexbuf.lex_curr_p.pos_cnum);
+            raise Parse_error
+        in
+            result
+
+# 586 "aft_lexer.ml"
diff --git a/aft_lexer.mll b/aft_lexer.mll
new file mode 100644 (file)
index 0000000..c8df2e3
--- /dev/null
@@ -0,0 +1,151 @@
+{
+  open Aft_parser
+  open Xpath_ext
+  open Parsing
+  open Printf
+  open Lexing
+
+  let cut_at_ws s c =
+    let l = String.length s in
+    let rec aux i =
+      if i = l then s 
+      else match s.[i] with
+       | ' ' | '\t' | '\r' | '\n' -> String.sub s 0 i
+        | z when z=c -> String.sub s 0 i
+       | _ -> aux (succ i)
+    in
+    aux 0
+}
+
+let letter = ['a'-'z''A'-'Z']
+
+let ascii_digit = ['0'-'9']
+let digit = ascii_digit
+
+let ncnamechar = letter | digit | '.' | '-' | '_' 
+
+let ncname = ( letter | '_' ) ncnamechar*
+
+let qname = (ncname ':')? ncname
+
+let ws = [ ' ' '\t' '\r' '\n' ]
+
+let nl = '\n'
+let number = ascii_digit+ ('.' (ascii_digit+)?)?
+
+let literal = ('"' [^ '"']* '"') | ('\'' [^ '\'']* '\'')
+
+rule token_after_not_op = parse
+  | '*'    { MUL }
+  | ncname { 
+      match Lexing.lexeme lexbuf with
+       | "and" -> AND
+       | "or"  -> OR
+       | "mod" -> MOD
+       | "div" -> DIV
+       | s -> failwith ("Unknown operator "^s)
+    }
+    | nl     { new_line lexbuf; token_after_not_op lexbuf }
+  | ws     { token_after_not_op lexbuf }
+  | ""     { token lexbuf }
+
+and token = parse
+  | ncname ws* "::" { 
+      let s = Lexing.lexeme lexbuf in
+      let s = cut_at_ws s ':' in
+      AXIS s
+    }
+
+  | qname ws* '(' {
+      let s = Lexing.lexeme lexbuf in
+      let s = cut_at_ws s '(' in
+      match s with
+               | "comment" | "text" | "processing-instruction" | "node" -> NODE_TYPE s
+               | _ -> FUNCTION_NAME s
+    }
+      
+
+  | "//"   { DOUBLESLASH }
+  | '/'    { SLASH }
+  | '}'    { RBRACE }
+  | '{'    { LBRACE }
+  | "->"   { POINT }
+
+  | ')'    { RPAREN }
+  | '('    { LPAREN }
+
+  | '['    { LBRACKET }
+  | ']'    { RBRACKET }
+
+
+  | ".."   { DOUBLEDOT }
+  | '.'    { DOT }
+
+  | '@'    { AT }
+  | ','    { COMMA }
+  | '|'    { PIPE }
+  (*| "||"    { DOUBLEPIPE }*)
+  | '='    { EQUAL }
+  | "!="   { NOTEQUAL }
+  | '<'    { LT }
+  | '>'    { GT }
+  | "<="   { LTE }
+  | ">="   { GTE }
+  | '+'    { PLUS }
+  | '-'    { MINUS }
+
+  | '$' qname { 
+      let s = Lexing.lexeme lexbuf in
+      let s = String.sub s 1 (String.length s - 1) in
+      VAR s
+    }
+
+ | '*' | (ncname ":*") | qname  { NAME_TEST (Lexing.lexeme lexbuf) }
+
+ | literal   {  
+     let s = Lexing.lexeme lexbuf in
+     let s = String.sub s 1 (String.length s - 2) in
+     LITERAL s 
+   }
+
+ | number    { NUMBER (float_of_string (Lexing.lexeme lexbuf)) }
+ | nl        { new_line lexbuf; token lexbuf }
+ | ws        { token lexbuf }
+ | eof       { EOF }
+
+{
+  let make_lexer () =
+    let previous_op = ref true in
+    fun lexbuf ->
+      let tok = 
+       if !previous_op then token lexbuf 
+       else token_after_not_op lexbuf in
+      (match tok with
+        | AT | AXIS _ | FUNCTION_NAME _ | NODE_TYPE _ | LBRACKET | LPAREN
+        | AND | OR | MOD | DIV | MUL | SLASH | DOUBLESLASH
+        | PIPE | PLUS | MINUS | EQUAL | NOTEQUAL | LT | GT | LTE | GTE 
+            -> previous_op := true
+        | _ -> previous_op := false
+      );
+      tok
+
+  let parse_expr x =    
+    let lexbuf = Lexing.from_string x in
+    let lexer  = make_lexer () in
+    let result = Aft_parser.aft_pattern_match lexer lexbuf in
+        result
+
+  let parse_from_channel x = 
+    let lexbuf = Lexing.from_channel x in
+    let lexer = make_lexer () in
+    let result = 
+        try 
+            Aft_parser.access_spec lexer lexbuf 
+        with Parse_error ->
+            printf "Error at line %d char %d.\n" (lexbuf.lex_curr_p.pos_lnum)
+                (lexbuf.lex_curr_p.pos_cnum);
+            raise Parse_error
+        in
+            result
+}
diff --git a/aft_minterms.ml b/aft_minterms.ml
new file mode 100644 (file)
index 0000000..6b1eec1
--- /dev/null
@@ -0,0 +1,213 @@
+(* aft_minterms.ml -- 
+ *      1. Converts afterthought programs (pattern matches) first to INF
+ *      (If-then-else normal form) and then Disjunctive Normal Form (DNF).
+ *      2. Optimizes in DNF to produce a hybrid form in which leaf-nodes are 
+ *      DNF expressions, and non-leaf nodes are singleton (decision) variables.
+ *)
+
+open Xpath_syntax
+open Xpath_ext
+open Aft_types
+open Globals
+open Array
+open Python_dict
+
+type aft_symtab = (path_expr, int) Hashtbl.t
+type aft_syms = path_expr array
+type aft_minterm = (path_expr,int) Hashtbl.t * (int list) list
+
+exception EvalAxisNotSupported
+exception Aft_error
+
+let aft_true = Filter(Number_literal(1.0)) 
+let aft_false = Filter(Number_literal(0.0))
+
+let one_or_term t =
+  if (t=[]) then [-1] else t
+
+let zero_or_term t =
+  if (t=[]) then [[-2]] else t
+
+let aft_to_minterms aft_rep =
+  let minterm_hash:aft_symtab = Hashtbl.create 128 in
+  let syms:aft_syms = Array.create 128 (Expr(Number_literal(1.0))) in
+  let hash_index = ref 0 in
+  let rec aft_to_minterms' prefix cur_term (aft_rep: access_spec) = 
+    match aft_rep with
+      | Filter(Number_literal(x))->
+          if (x = 0.0) then
+            cur_term
+          else
+          if (x=1.0) then ((one_or_term prefix)::cur_term)
+          else begin
+            print "Reached leaf %f" x;raise Aft_error
+          end
+      | INF(m, True(right), False(left)) -> 
+          let term = try Hashtbl.find minterm_hash m with
+            | Not_found ->
+                Hashtbl.add minterm_hash m !hash_index;
+                Array.set syms !hash_index m;
+              hash_index := !hash_index + 1;
+              !hash_index-1
+          in
+          let minterm2' = (term+255)::prefix in
+          let minterm2 = term::prefix in
+            let right_function = aft_to_minterms' minterm2 cur_term right in
+                aft_to_minterms' minterm2' right_function left
+      | _ -> 
+            cur_term
+  in
+  let minterm_list = zero_or_term (aft_to_minterms' [] [] aft_rep) in
+    (minterm_list, syms, !hash_index)
+
+let rec eval xpath_path =
+  match xpath_path with 
+    | Expr(expr) ->
+        0
+    | Pipe(e1,e2) ->  
+        let v = eval e1 in
+          if (-1=v) then eval e2 else v
+    | Slash(e1,e2) ->
+        let v = eval e1 in
+          if (-1=v) then eval e2 else v
+    | Condition(e,expr) ->
+        eval e
+    | Root ->
+        -1
+    | Axis(_,e)->
+        eval e
+    | Name(s)->
+        let c = String.get s 0 in
+        let ic = int_of_char c in
+          if (ic > 64 && ic < 91) then 1 else 0
+    | _ -> raise EvalAxisNotSupported
+
+let optimize_minterms m_syms n =
+  let rec gen_lst n suffix = if (n==(-1)) then suffix else gen_lst (n-1) (n::suffix) in
+  let lst = gen_lst (n-1) [] in
+  let cmp_func a1 a2 = 
+    let term1 = Array.get m_syms a1 in
+    let term2 = Array.get m_syms a2 in
+      if ((eval term1) > (eval term2)) then 1 else 0
+  in
+    List.stable_sort cmp_func lst
+
+let rec print_minterms lst =
+  match lst with
+    | car::cdr -> List.iter (print "%d ") car;print ";";print_minterms cdr
+    | [] -> print "\n"
+
+let rec const_to_aft m_list = 
+  match m_list with
+    | [] -> aft_false
+    | [singleton]::cdr -> if (singleton=(-1) (*true*) ) then aft_true else const_to_aft cdr
+    | []::cdr -> const_to_aft cdr
+    | x -> print "Did not reduce to constant expression:\n";print_minterms x;raise Aft_error
+
+let linear x fx =
+  (fx=x || fx=(x+255))
+
+let var_delete var term = 
+  let rec var_delete' var prefix term = 
+    match term with 
+      | car::[] ->
+          if (linear var car) then
+            if (prefix = []) then [-1] else prefix
+          else
+            car::prefix
+      | car::cdr ->
+          if (linear car var) then
+            var_delete' var prefix cdr
+          else
+            var_delete' var (car::prefix) cdr
+      | [] -> []
+  in
+    var_delete' var [] term
+
+
+let filter_by_member fn lst =
+    List.filter (fun x->not (List.exists fn x)) lst
+
+let reduce var terms neg_check = 
+  let nl = filter_by_member neg_check terms in
+    List.map (var_delete var) nl
+
+let reduce_true var terms =
+    reduce var terms (fun x->x=(var+255))
+
+let reduce_false var terms =
+  let res = reduce var terms (fun x->var=x) in
+    res
+  
+let var_to_aft syms term =
+  Array.get syms term
+
+let rec mature minterms =
+  match minterms with
+    | [[]] -> true
+    | [] -> true
+    | [singleton]::cdr -> if (singleton<0) then mature cdr else false
+    | _ -> false
+
+let minterms_to_filter minterms =
+  try
+    const_to_aft minterms
+  with Aft_error ->
+    print "Immature expression:";print_minterms minterms;raise Aft_error
+
+let rec minterms_to_aft m_list m_syms order n_terms =
+  if (mature(m_list)) 
+  then 
+      minterms_to_filter m_list
+  else
+    begin
+      match order with
+        | [] ->
+            const_to_aft m_list
+        | car::cdr ->
+            let right = reduce_true car m_list in
+            let left = reduce_false car m_list in
+            let right_aft = minterms_to_aft right m_syms cdr (n_terms-1) in
+            let left_aft = minterms_to_aft left m_syms cdr (n_terms-1) in
+              (INF((var_to_aft m_syms car),True(right_aft),False(left_aft)))
+    end
+
+let rec aft_to_il l_inp = 
+  let rec aft_to_il' (aft_rep: access_spec) = 
+    let rec pattern_match_to_il  (pat_match: clause list) =
+        match pat_match with
+            Clause(m, aspec)::cdr -> 
+              let left_function = pattern_match_to_il cdr in
+              let right_function = aft_to_il' aspec in
+                INF(m,True(right_function),False(left_function))
+            | [] -> 
+                Filter(Number_literal(0.0))
+    in
+    match aft_rep with
+      | PatternMatch(cl_list) -> 
+          pattern_match_to_il cl_list
+      | other -> other
+  in
+    aft_to_il' l_inp
+
+let tab n =
+  String.make n '\t'
+
+let pretty_print l =
+  let rec pretty_print' l tablevel =
+      match l with 
+        | Filter(Number_literal(x)) -> tabprint tablevel "%f\n" x
+        | Filter(_) -> print "[filter]"
+        | INF(path, True(l'), False(l'')) ->
+            let spath = pretty_print_xpath_path path in
+              begin
+                  tabprint tablevel "%s ->\n{" spath;
+                  pretty_print' l' (tablevel + 1);
+                  tabprint tablevel "}\n";
+                  tabprint tablevel "| {";
+                  pretty_print' l'' (tablevel + 1);
+                  tabprint tablevel "}\n"
+              end
+        | PatternMatch(_) -> print "Expression not reduced";raise Aft_error
+  in
+    pretty_print' l 0
diff --git a/aft_parser.ml b/aft_parser.ml
new file mode 100644 (file)
index 0000000..347a06b
--- /dev/null
@@ -0,0 +1,925 @@
+type token =
+  | POINT
+  | LBRACE
+  | RBRACE
+  | SLASH
+  | LPAREN
+  | RPAREN
+  | LBRACKET
+  | RBRACKET
+  | DOUBLESLASH
+  | DOUBLEDOT
+  | AT
+  | DOT
+  | COMMA
+  | PIPE
+  | OR
+  | AND
+  | EQUAL
+  | NOTEQUAL
+  | LT
+  | GT
+  | LTE
+  | GTE
+  | PLUS
+  | MINUS
+  | MUL
+  | DIV
+  | MOD
+  | VAR of (string)
+  | NAME_TEST of (string)
+  | AXIS of (string)
+  | FUNCTION_NAME of (string)
+  | NODE_TYPE of (string)
+  | LITERAL of (string)
+  | NUMBER of (float)
+  | EOF
+
+open Parsing;;
+# 2 "aft_parser.mly"
+  open Xpath_syntax
+  open Xpath_ext
+  open Axis
+  open Aft_types
+# 45 "aft_parser.ml"
+let yytransl_const = [|
+  257 (* POINT *);
+  258 (* LBRACE *);
+  259 (* RBRACE *);
+  260 (* SLASH *);
+  261 (* LPAREN *);
+  262 (* RPAREN *);
+  263 (* LBRACKET *);
+  264 (* RBRACKET *);
+  265 (* DOUBLESLASH *);
+  266 (* DOUBLEDOT *);
+  267 (* AT *);
+  268 (* DOT *);
+  269 (* COMMA *);
+  270 (* PIPE *);
+  271 (* OR *);
+  272 (* AND *);
+  273 (* EQUAL *);
+  274 (* NOTEQUAL *);
+  275 (* LT *);
+  276 (* GT *);
+  277 (* LTE *);
+  278 (* GTE *);
+  279 (* PLUS *);
+  280 (* MINUS *);
+  281 (* MUL *);
+  282 (* DIV *);
+  283 (* MOD *);
+    0 (* EOF *);
+    0|]
+
+let yytransl_block = [|
+  284 (* VAR *);
+  285 (* NAME_TEST *);
+  286 (* AXIS *);
+  287 (* FUNCTION_NAME *);
+  288 (* NODE_TYPE *);
+  289 (* LITERAL *);
+  290 (* NUMBER *);
+    0|]
+
+let yylhs = "\255\255\
+\002\000\002\000\004\000\001\000\001\000\005\000\005\000\007\000\
+\007\000\007\000\006\000\006\000\006\000\008\000\008\000\008\000\
+\008\000\010\000\010\000\009\000\009\000\011\000\011\000\011\000\
+\012\000\012\000\012\000\012\000\012\000\013\000\013\000\014\000\
+\014\000\015\000\015\000\016\000\016\000\016\000\016\000\017\000\
+\017\000\003\000\018\000\018\000\019\000\019\000\020\000\020\000\
+\020\000\021\000\021\000\021\000\021\000\021\000\022\000\022\000\
+\022\000\023\000\023\000\023\000\023\000\024\000\024\000\000\000\
+\000\000"
+
+let yylen = "\002\000\
+\001\000\001\000\005\000\001\000\003\000\001\000\001\000\001\000\
+\002\000\002\000\001\000\003\000\003\000\002\000\001\000\001\000\
+\001\000\004\000\001\000\001\000\001\000\001\000\002\000\003\000\
+\001\000\001\000\003\000\001\000\001\000\002\000\003\000\003\000\
+\001\000\001\000\003\000\001\000\001\000\003\000\003\000\001\000\
+\004\000\001\000\001\000\003\000\001\000\003\000\001\000\003\000\
+\003\000\001\000\003\000\003\000\003\000\003\000\001\000\003\000\
+\003\000\001\000\003\000\003\000\003\000\001\000\002\000\002\000\
+\002\000"
+
+let yydefred = "\000\000\
+\000\000\000\000\000\000\000\000\000\000\017\000\021\000\016\000\
+\022\000\020\000\000\000\064\000\000\000\000\000\000\000\007\000\
+\011\000\000\000\000\000\019\000\000\000\000\000\026\000\000\000\
+\028\000\029\000\002\000\065\000\001\000\000\000\040\000\025\000\
+\000\000\034\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\058\000\000\000\000\000\023\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\036\000\063\000\030\000\
+\033\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\024\000\005\000\000\000\012\000\013\000\
+\000\000\027\000\031\000\000\000\035\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\059\000\060\000\061\000\000\000\018\000\032\000\
+\041\000\003\000"
+
+let yydgoto = "\003\000\
+\027\000\028\000\029\000\013\000\054\000\015\000\016\000\017\000\
+\018\000\019\000\020\000\031\000\032\000\058\000\033\000\034\000\
+\035\000\036\000\037\000\038\000\039\000\040\000\041\000\042\000"
+
+let yysindex = "\060\000\
+\102\255\062\255\000\000\001\255\001\255\000\000\000\000\000\000\
+\000\000\000\000\252\254\000\000\022\255\046\255\014\255\000\000\
+\000\000\003\255\047\255\000\000\062\255\062\255\000\000\010\255\
+\000\000\000\000\000\000\000\000\000\000\046\255\000\000\000\000\
+\050\255\000\000\041\255\053\255\054\255\066\255\038\255\064\255\
+\000\255\000\000\014\255\014\255\000\000\073\255\102\255\079\255\
+\001\255\001\255\047\255\062\255\083\255\000\000\000\000\000\000\
+\000\000\011\255\093\255\001\255\062\255\001\255\062\255\062\255\
+\062\255\062\255\062\255\062\255\062\255\062\255\062\255\062\255\
+\062\255\062\255\062\255\000\000\000\000\062\255\000\000\000\000\
+\077\255\000\000\000\000\062\255\000\000\014\255\109\255\014\255\
+\054\255\066\255\038\255\038\255\064\255\064\255\064\255\064\255\
+\000\255\000\255\000\000\000\000\000\000\098\255\000\000\000\000\
+\000\000\000\000"
+
+let yyrindex = "\000\000\
+\000\000\000\000\000\000\055\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\005\000\000\000\082\000\000\000\
+\000\000\000\000\001\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\006\001\000\000\000\000\
+\236\000\000\000\161\000\166\001\038\002\014\002\240\001\111\001\
+\033\001\000\000\109\000\136\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\028\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\186\000\000\000\211\000\
+\058\002\034\002\246\001\008\002\138\001\165\001\190\001\215\001\
+\057\001\084\001\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000"
+
+let yygindex = "\000\000\
+\009\000\032\000\241\255\000\000\002\000\003\000\000\000\050\000\
+\000\000\100\000\000\000\000\000\000\000\000\000\000\000\061\000\
+\000\000\000\000\056\000\064\000\042\000\008\000\044\000\234\255"
+
+let yytablesize = 841
+let yytable = "\055\000\
+\015\000\045\000\014\000\030\000\004\000\053\000\043\000\044\000\
+\057\000\012\000\006\000\007\000\008\000\004\000\021\000\056\000\
+\083\000\049\000\005\000\006\000\007\000\008\000\050\000\084\000\
+\073\000\074\000\075\000\014\000\046\000\009\000\010\000\009\000\
+\011\000\022\000\011\000\047\000\081\000\023\000\009\000\010\000\
+\024\000\011\000\025\000\026\000\060\000\087\000\048\000\061\000\
+\014\000\062\000\099\000\100\000\101\000\052\000\008\000\077\000\
+\067\000\068\000\069\000\070\000\001\000\002\000\086\000\059\000\
+\088\000\004\000\021\000\063\000\104\000\064\000\005\000\006\000\
+\007\000\008\000\093\000\094\000\095\000\096\000\076\000\030\000\
+\078\000\006\000\065\000\066\000\103\000\022\000\071\000\072\000\
+\082\000\023\000\009\000\010\000\024\000\011\000\025\000\026\000\
+\004\000\021\000\079\000\080\000\106\000\005\000\006\000\007\000\
+\008\000\004\000\091\000\092\000\009\000\102\000\005\000\006\000\
+\007\000\008\000\097\000\098\000\105\000\051\000\089\000\085\000\
+\023\000\009\000\010\000\024\000\011\000\025\000\026\000\090\000\
+\000\000\000\000\009\000\010\000\000\000\011\000\000\000\010\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\037\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\038\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\039\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\062\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\
+\000\000\015\000\000\000\015\000\015\000\036\000\015\000\004\000\
+\015\000\015\000\000\000\000\000\000\000\015\000\015\000\015\000\
+\015\000\015\000\015\000\015\000\015\000\015\000\015\000\015\000\
+\015\000\015\000\015\000\015\000\014\000\000\000\014\000\014\000\
+\055\000\014\000\000\000\014\000\014\000\000\000\000\000\000\000\
+\014\000\014\000\014\000\014\000\014\000\014\000\014\000\014\000\
+\014\000\014\000\014\000\014\000\014\000\014\000\014\000\008\000\
+\056\000\008\000\000\000\000\000\008\000\000\000\008\000\000\000\
+\000\000\000\000\000\000\008\000\008\000\008\000\008\000\008\000\
+\008\000\008\000\008\000\008\000\008\000\008\000\008\000\008\000\
+\008\000\008\000\006\000\057\000\006\000\000\000\000\000\006\000\
+\000\000\006\000\000\000\000\000\000\000\000\000\006\000\006\000\
+\006\000\006\000\006\000\006\000\006\000\006\000\006\000\006\000\
+\006\000\006\000\006\000\006\000\006\000\009\000\050\000\009\000\
+\000\000\000\000\009\000\000\000\009\000\000\000\000\000\000\000\
+\000\000\009\000\009\000\009\000\009\000\009\000\009\000\009\000\
+\009\000\009\000\009\000\009\000\009\000\009\000\009\000\009\000\
+\010\000\051\000\010\000\000\000\000\000\010\000\000\000\010\000\
+\000\000\000\000\000\000\000\000\010\000\010\000\010\000\010\000\
+\010\000\010\000\010\000\010\000\010\000\010\000\010\000\010\000\
+\010\000\010\000\010\000\037\000\052\000\042\000\037\000\000\000\
+\037\000\000\000\000\000\000\000\000\000\037\000\037\000\037\000\
+\037\000\037\000\037\000\037\000\037\000\037\000\037\000\037\000\
+\037\000\037\000\037\000\037\000\038\000\053\000\000\000\038\000\
+\000\000\038\000\000\000\000\000\000\000\000\000\038\000\038\000\
+\038\000\038\000\038\000\038\000\038\000\038\000\038\000\038\000\
+\038\000\038\000\038\000\038\000\038\000\039\000\054\000\000\000\
+\039\000\000\000\039\000\000\000\000\000\000\000\000\000\039\000\
+\039\000\039\000\039\000\039\000\039\000\039\000\039\000\039\000\
+\039\000\039\000\039\000\039\000\039\000\039\000\062\000\047\000\
+\000\000\062\000\000\000\062\000\000\000\048\000\000\000\000\000\
+\062\000\000\000\062\000\062\000\062\000\062\000\062\000\062\000\
+\062\000\062\000\062\000\062\000\062\000\062\000\062\000\049\000\
+\036\000\000\000\000\000\000\000\000\000\045\000\000\000\000\000\
+\000\000\000\000\000\000\036\000\036\000\036\000\036\000\036\000\
+\036\000\036\000\036\000\036\000\036\000\036\000\036\000\036\000\
+\036\000\046\000\000\000\055\000\000\000\043\000\055\000\000\000\
+\055\000\000\000\000\000\000\000\000\000\055\000\000\000\055\000\
+\055\000\055\000\055\000\055\000\055\000\055\000\055\000\055\000\
+\055\000\044\000\000\000\056\000\000\000\000\000\056\000\000\000\
+\056\000\000\000\000\000\000\000\000\000\056\000\000\000\056\000\
+\056\000\056\000\056\000\056\000\056\000\056\000\056\000\056\000\
+\056\000\000\000\000\000\000\000\000\000\000\000\057\000\000\000\
+\000\000\057\000\000\000\057\000\000\000\000\000\000\000\000\000\
+\057\000\000\000\057\000\057\000\057\000\057\000\057\000\057\000\
+\057\000\057\000\057\000\057\000\000\000\000\000\000\000\000\000\
+\000\000\050\000\000\000\000\000\050\000\000\000\050\000\000\000\
+\000\000\000\000\000\000\050\000\000\000\050\000\050\000\050\000\
+\050\000\050\000\050\000\050\000\050\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\051\000\000\000\000\000\051\000\
+\000\000\051\000\000\000\000\000\000\000\000\000\051\000\000\000\
+\051\000\051\000\051\000\051\000\051\000\051\000\051\000\051\000\
+\000\000\000\000\000\000\000\000\000\000\000\000\000\000\052\000\
+\042\000\000\000\052\000\042\000\052\000\042\000\000\000\000\000\
+\000\000\052\000\042\000\052\000\052\000\052\000\052\000\052\000\
+\052\000\052\000\052\000\000\000\000\000\000\000\000\000\000\000\
+\053\000\000\000\000\000\053\000\000\000\053\000\000\000\000\000\
+\000\000\000\000\053\000\000\000\053\000\053\000\053\000\053\000\
+\053\000\053\000\053\000\053\000\000\000\000\000\000\000\000\000\
+\000\000\054\000\000\000\000\000\054\000\000\000\054\000\000\000\
+\000\000\000\000\000\000\054\000\000\000\054\000\054\000\054\000\
+\054\000\054\000\054\000\054\000\054\000\000\000\000\000\000\000\
+\000\000\000\000\047\000\000\000\000\000\047\000\000\000\047\000\
+\048\000\000\000\000\000\048\000\047\000\048\000\047\000\047\000\
+\047\000\047\000\048\000\000\000\048\000\048\000\048\000\048\000\
+\000\000\000\000\049\000\000\000\000\000\049\000\000\000\049\000\
+\045\000\000\000\000\000\045\000\049\000\045\000\049\000\049\000\
+\049\000\049\000\045\000\000\000\045\000\045\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\046\000\000\000\000\000\046\000\
+\043\000\046\000\000\000\043\000\000\000\043\000\046\000\000\000\
+\046\000\046\000\043\000\000\000\043\000\000\000\000\000\000\000\
+\000\000\000\000\000\000\000\000\044\000\000\000\000\000\044\000\
+\000\000\044\000\000\000\000\000\000\000\000\000\044\000\000\000\
+\044\000"
+
+let yycheck = "\022\000\
+\000\000\006\001\001\000\002\000\000\000\021\000\004\000\005\000\
+\024\000\001\000\010\001\011\001\012\001\004\001\005\001\006\001\
+\006\001\004\001\009\001\010\001\011\001\012\001\009\001\013\001\
+\025\001\026\001\027\001\000\000\033\001\029\001\030\001\029\001\
+\032\001\024\001\032\001\014\001\052\000\028\001\029\001\030\001\
+\031\001\032\001\033\001\034\001\004\001\061\000\001\001\007\001\
+\047\000\009\001\073\000\074\000\075\000\007\001\000\000\047\000\
+\019\001\020\001\021\001\022\001\001\000\002\000\060\000\014\001\
+\062\000\004\001\005\001\015\001\084\000\016\001\009\001\010\001\
+\011\001\012\001\067\000\068\000\069\000\070\000\006\001\078\000\
+\002\001\000\000\017\001\018\001\008\001\024\001\023\001\024\001\
+\006\001\028\001\029\001\030\001\031\001\032\001\033\001\034\001\
+\004\001\005\001\049\000\050\000\003\001\009\001\010\001\011\001\
+\012\001\004\001\065\000\066\000\000\000\078\000\009\001\010\001\
+\011\001\012\001\071\000\072\000\008\001\018\000\063\000\059\000\
+\028\001\029\001\030\001\031\001\032\001\033\001\034\001\064\000\
+\255\255\255\255\029\001\030\001\255\255\032\001\255\255\000\000\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\000\000\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\000\000\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\000\000\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\000\000\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\
+\255\255\001\001\255\255\003\001\004\001\000\000\006\001\003\001\
+\008\001\009\001\255\255\255\255\255\255\013\001\014\001\015\001\
+\016\001\017\001\018\001\019\001\020\001\021\001\022\001\023\001\
+\024\001\025\001\026\001\027\001\001\001\255\255\003\001\004\001\
+\000\000\006\001\255\255\008\001\009\001\255\255\255\255\255\255\
+\013\001\014\001\015\001\016\001\017\001\018\001\019\001\020\001\
+\021\001\022\001\023\001\024\001\025\001\026\001\027\001\001\001\
+\000\000\003\001\255\255\255\255\006\001\255\255\008\001\255\255\
+\255\255\255\255\255\255\013\001\014\001\015\001\016\001\017\001\
+\018\001\019\001\020\001\021\001\022\001\023\001\024\001\025\001\
+\026\001\027\001\001\001\000\000\003\001\255\255\255\255\006\001\
+\255\255\008\001\255\255\255\255\255\255\255\255\013\001\014\001\
+\015\001\016\001\017\001\018\001\019\001\020\001\021\001\022\001\
+\023\001\024\001\025\001\026\001\027\001\001\001\000\000\003\001\
+\255\255\255\255\006\001\255\255\008\001\255\255\255\255\255\255\
+\255\255\013\001\014\001\015\001\016\001\017\001\018\001\019\001\
+\020\001\021\001\022\001\023\001\024\001\025\001\026\001\027\001\
+\001\001\000\000\003\001\255\255\255\255\006\001\255\255\008\001\
+\255\255\255\255\255\255\255\255\013\001\014\001\015\001\016\001\
+\017\001\018\001\019\001\020\001\021\001\022\001\023\001\024\001\
+\025\001\026\001\027\001\003\001\000\000\000\000\006\001\255\255\
+\008\001\255\255\255\255\255\255\255\255\013\001\014\001\015\001\
+\016\001\017\001\018\001\019\001\020\001\021\001\022\001\023\001\
+\024\001\025\001\026\001\027\001\003\001\000\000\255\255\006\001\
+\255\255\008\001\255\255\255\255\255\255\255\255\013\001\014\001\
+\015\001\016\001\017\001\018\001\019\001\020\001\021\001\022\001\
+\023\001\024\001\025\001\026\001\027\001\003\001\000\000\255\255\
+\006\001\255\255\008\001\255\255\255\255\255\255\255\255\013\001\
+\014\001\015\001\016\001\017\001\018\001\019\001\020\001\021\001\
+\022\001\023\001\024\001\025\001\026\001\027\001\003\001\000\000\
+\255\255\006\001\255\255\008\001\255\255\000\000\255\255\255\255\
+\013\001\255\255\015\001\016\001\017\001\018\001\019\001\020\001\
+\021\001\022\001\023\001\024\001\025\001\026\001\027\001\000\000\
+\003\001\255\255\255\255\255\255\255\255\000\000\255\255\255\255\
+\255\255\255\255\255\255\014\001\015\001\016\001\017\001\018\001\
+\019\001\020\001\021\001\022\001\023\001\024\001\025\001\026\001\
+\027\001\000\000\255\255\003\001\255\255\000\000\006\001\255\255\
+\008\001\255\255\255\255\255\255\255\255\013\001\255\255\015\001\
+\016\001\017\001\018\001\019\001\020\001\021\001\022\001\023\001\
+\024\001\000\000\255\255\003\001\255\255\255\255\006\001\255\255\
+\008\001\255\255\255\255\255\255\255\255\013\001\255\255\015\001\
+\016\001\017\001\018\001\019\001\020\001\021\001\022\001\023\001\
+\024\001\255\255\255\255\255\255\255\255\255\255\003\001\255\255\
+\255\255\006\001\255\255\008\001\255\255\255\255\255\255\255\255\
+\013\001\255\255\015\001\016\001\017\001\018\001\019\001\020\001\
+\021\001\022\001\023\001\024\001\255\255\255\255\255\255\255\255\
+\255\255\003\001\255\255\255\255\006\001\255\255\008\001\255\255\
+\255\255\255\255\255\255\013\001\255\255\015\001\016\001\017\001\
+\018\001\019\001\020\001\021\001\022\001\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\003\001\255\255\255\255\006\001\
+\255\255\008\001\255\255\255\255\255\255\255\255\013\001\255\255\
+\015\001\016\001\017\001\018\001\019\001\020\001\021\001\022\001\
+\255\255\255\255\255\255\255\255\255\255\255\255\255\255\003\001\
+\003\001\255\255\006\001\006\001\008\001\008\001\255\255\255\255\
+\255\255\013\001\013\001\015\001\016\001\017\001\018\001\019\001\
+\020\001\021\001\022\001\255\255\255\255\255\255\255\255\255\255\
+\003\001\255\255\255\255\006\001\255\255\008\001\255\255\255\255\
+\255\255\255\255\013\001\255\255\015\001\016\001\017\001\018\001\
+\019\001\020\001\021\001\022\001\255\255\255\255\255\255\255\255\
+\255\255\003\001\255\255\255\255\006\001\255\255\008\001\255\255\
+\255\255\255\255\255\255\013\001\255\255\015\001\016\001\017\001\
+\018\001\019\001\020\001\021\001\022\001\255\255\255\255\255\255\
+\255\255\255\255\003\001\255\255\255\255\006\001\255\255\008\001\
+\003\001\255\255\255\255\006\001\013\001\008\001\015\001\016\001\
+\017\001\018\001\013\001\255\255\015\001\016\001\017\001\018\001\
+\255\255\255\255\003\001\255\255\255\255\006\001\255\255\008\001\
+\003\001\255\255\255\255\006\001\013\001\008\001\015\001\016\001\
+\017\001\018\001\013\001\255\255\015\001\016\001\255\255\255\255\
+\255\255\255\255\255\255\255\255\003\001\255\255\255\255\006\001\
+\003\001\008\001\255\255\006\001\255\255\008\001\013\001\255\255\
+\015\001\016\001\013\001\255\255\015\001\255\255\255\255\255\255\
+\255\255\255\255\255\255\255\255\003\001\255\255\255\255\006\001\
+\255\255\008\001\255\255\255\255\255\255\255\255\013\001\255\255\
+\015\001"
+
+let yynames_const = "\
+  POINT\000\
+  LBRACE\000\
+  RBRACE\000\
+  SLASH\000\
+  LPAREN\000\
+  RPAREN\000\
+  LBRACKET\000\
+  RBRACKET\000\
+  DOUBLESLASH\000\
+  DOUBLEDOT\000\
+  AT\000\
+  DOT\000\
+  COMMA\000\
+  PIPE\000\
+  OR\000\
+  AND\000\
+  EQUAL\000\
+  NOTEQUAL\000\
+  LT\000\
+  GT\000\
+  LTE\000\
+  GTE\000\
+  PLUS\000\
+  MINUS\000\
+  MUL\000\
+  DIV\000\
+  MOD\000\
+  EOF\000\
+  "
+
+let yynames_block = "\
+  VAR\000\
+  NAME_TEST\000\
+  AXIS\000\
+  FUNCTION_NAME\000\
+  NODE_TYPE\000\
+  LITERAL\000\
+  NUMBER\000\
+  "
+
+let yyact = [|
+  (fun _ -> failwith "parser")
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'expr) in
+    Obj.repr(
+# 27 "aft_parser.mly"
+         ( Filter(_1) )
+# 432 "aft_parser.ml"
+               : Aft_types.access_spec))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : Aft_types.pattern_match) in
+    Obj.repr(
+# 28 "aft_parser.mly"
+                      ( PatternMatch(_1) )
+# 439 "aft_parser.ml"
+               : Aft_types.access_spec))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 4 : 'location_path) in
+    let _4 = (Parsing.peek_val __caml_parser_env 1 : Aft_types.access_spec) in
+    Obj.repr(
+# 31 "aft_parser.mly"
+                                                  ( Clause(_1 , _4) )
+# 447 "aft_parser.ml"
+               : 'aft_clause))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'aft_clause) in
+    Obj.repr(
+# 34 "aft_parser.mly"
+               ( [ _1 ] )
+# 454 "aft_parser.ml"
+               : Aft_types.pattern_match))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'aft_clause) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : Aft_types.pattern_match) in
+    Obj.repr(
+# 35 "aft_parser.mly"
+                                      (_1::_3)
+# 462 "aft_parser.ml"
+               : Aft_types.pattern_match))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'relative_location_path) in
+    Obj.repr(
+# 38 "aft_parser.mly"
+                               ( _1 )
+# 469 "aft_parser.ml"
+               : 'location_path))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'absolute_location_path) in
+    Obj.repr(
+# 39 "aft_parser.mly"
+                               ( _1 )
+# 476 "aft_parser.ml"
+               : 'location_path))
+; (fun __caml_parser_env ->
+    Obj.repr(
+# 42 "aft_parser.mly"
+           ( Root )
+# 482 "aft_parser.ml"
+               : 'absolute_location_path))
+; (fun __caml_parser_env ->
+    let _2 = (Parsing.peek_val __caml_parser_env 0 : 'relative_location_path) in
+    Obj.repr(
+# 43 "aft_parser.mly"
+                                 ( Slash (Root,_2) )
+# 489 "aft_parser.ml"
+               : 'absolute_location_path))
+; (fun __caml_parser_env ->
+    let _2 = (Parsing.peek_val __caml_parser_env 0 : 'relative_location_path) in
+    Obj.repr(
+# 44 "aft_parser.mly"
+                                      ( double_slash Root _2 )
+# 496 "aft_parser.ml"
+               : 'absolute_location_path))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'step) in
+    Obj.repr(
+# 47 "aft_parser.mly"
+           ( _1 )
+# 503 "aft_parser.ml"
+               : 'relative_location_path))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relative_location_path) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'step) in
+    Obj.repr(
+# 48 "aft_parser.mly"
+                                     ( Slash (_1,_3) )
+# 511 "aft_parser.ml"
+               : 'relative_location_path))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relative_location_path) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'step) in
+    Obj.repr(
+# 49 "aft_parser.mly"
+                                           ( double_slash _1 _3 )
+# 519 "aft_parser.ml"
+               : 'relative_location_path))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 1 : 'axis_specifier) in
+    let _2 = (Parsing.peek_val __caml_parser_env 0 : 'step2) in
+    Obj.repr(
+# 52 "aft_parser.mly"
+                        ( Axis (_1,_2) )
+# 527 "aft_parser.ml"
+               : 'step))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'step2) in
+    Obj.repr(
+# 53 "aft_parser.mly"
+         ( _1 )
+# 534 "aft_parser.ml"
+               : 'step))
+; (fun __caml_parser_env ->
+    Obj.repr(
+# 54 "aft_parser.mly"
+         ( dot  )
+# 540 "aft_parser.ml"
+               : 'step))
+; (fun __caml_parser_env ->
+    Obj.repr(
+# 55 "aft_parser.mly"
+              ( dotdot )
+# 546 "aft_parser.ml"
+               : 'step))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 3 : 'step2) in
+    let _3 = (Parsing.peek_val __caml_parser_env 1 : 'expr) in
+    Obj.repr(
+# 58 "aft_parser.mly"
+                                ( Condition (_1,_3) )
+# 554 "aft_parser.ml"
+               : 'step2))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'node_test) in
+    Obj.repr(
+# 59 "aft_parser.mly"
+             ( _1 )
+# 561 "aft_parser.ml"
+               : 'step2))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : string) in
+    Obj.repr(
+# 62 "aft_parser.mly"
+        ( 
+     try Axis.of_string _1 
+     with Not_found -> failwith ("Unknown axis :"^_1)
+   )
+# 571 "aft_parser.ml"
+               : 'axis_specifier))
+; (fun __caml_parser_env ->
+    Obj.repr(
+# 66 "aft_parser.mly"
+      ( Axis.Attribute )
+# 577 "aft_parser.ml"
+               : 'axis_specifier))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : string) in
+    Obj.repr(
+# 70 "aft_parser.mly"
+              ( Name _1 )
+# 584 "aft_parser.ml"
+               : 'node_test))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 1 : string) in
+    Obj.repr(
+# 71 "aft_parser.mly"
+                    ( 
+     try TypeTest (Type_test.of_string _1) 
+     with Not_found -> failwith ("Unknown node type :"^_1)
+   )
+# 594 "aft_parser.ml"
+               : 'node_test))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : string) in
+    let _2 = (Parsing.peek_val __caml_parser_env 1 : string) in
+    Obj.repr(
+# 75 "aft_parser.mly"
+                            (
+     match _1 with
+       | "processing-instruction" ->
+          TypeTest (Type_test.Pi_test (Some _2))
+       | _ -> failwith "Only processing-instruction tests accept argument" 
+   )
+# 607 "aft_parser.ml"
+               : 'node_test))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'function_call) in
+    Obj.repr(
+# 83 "aft_parser.mly"
+                   ( _1 )
+# 614 "aft_parser.ml"
+               : 'primary_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : string) in
+    Obj.repr(
+# 84 "aft_parser.mly"
+                   ( Var _1 )
+# 621 "aft_parser.ml"
+               : 'primary_expr))
+; (fun __caml_parser_env ->
+    let _2 = (Parsing.peek_val __caml_parser_env 1 : 'expr) in
+    Obj.repr(
+# 85 "aft_parser.mly"
+                       ( _2 )
+# 628 "aft_parser.ml"
+               : 'primary_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : string) in
+    Obj.repr(
+# 86 "aft_parser.mly"
+                   ( String_literal _1 )
+# 635 "aft_parser.ml"
+               : 'primary_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : float) in
+    Obj.repr(
+# 87 "aft_parser.mly"
+                   ( Number_literal _1 )
+# 642 "aft_parser.ml"
+               : 'primary_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 1 : string) in
+    Obj.repr(
+# 90 "aft_parser.mly"
+                         ( Function (_1,[]) )
+# 649 "aft_parser.ml"
+               : 'function_call))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : string) in
+    let _2 = (Parsing.peek_val __caml_parser_env 1 : 'arguments) in
+    Obj.repr(
+# 91 "aft_parser.mly"
+                                   ( Function (_1,_2) )
+# 657 "aft_parser.ml"
+               : 'function_call))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'arguments) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'expr) in
+    Obj.repr(
+# 94 "aft_parser.mly"
+                          ( _1@[_3] )
+# 665 "aft_parser.ml"
+               : 'arguments))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'expr) in
+    Obj.repr(
+# 95 "aft_parser.mly"
+        ( [_1] )
+# 672 "aft_parser.ml"
+               : 'arguments))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'path_expr) in
+    Obj.repr(
+# 98 "aft_parser.mly"
+                    ( _1 )
+# 679 "aft_parser.ml"
+               : 'union_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'union_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'path_expr) in
+    Obj.repr(
+# 99 "aft_parser.mly"
+                              ( path_expr (Pipe(expr _1, expr _3)) )
+# 687 "aft_parser.ml"
+               : 'union_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'location_path) in
+    Obj.repr(
+# 102 "aft_parser.mly"
+                    ( path_expr _1 )
+# 694 "aft_parser.ml"
+               : 'path_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'filter_expr) in
+    Obj.repr(
+# 103 "aft_parser.mly"
+                    ( _1 )
+# 701 "aft_parser.ml"
+               : 'path_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'filter_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'relative_location_path) in
+    Obj.repr(
+# 105 "aft_parser.mly"
+     (  path_expr (Slash (expr _1,_3)) )
+# 709 "aft_parser.ml"
+               : 'path_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'filter_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'relative_location_path) in
+    Obj.repr(
+# 107 "aft_parser.mly"
+     (  path_expr (double_slash (expr _1) _3) )
+# 717 "aft_parser.ml"
+               : 'path_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'primary_expr) in
+    Obj.repr(
+# 111 "aft_parser.mly"
+                ( _1 )
+# 724 "aft_parser.ml"
+               : 'filter_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 3 : 'filter_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 1 : 'expr) in
+    Obj.repr(
+# 112 "aft_parser.mly"
+                                      ( path_expr (Condition (expr _1,_3)) )
+# 732 "aft_parser.ml"
+               : 'filter_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'or_expr) in
+    Obj.repr(
+# 116 "aft_parser.mly"
+                   ( _1 )
+# 739 "aft_parser.ml"
+               : 'expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'and_expr) in
+    Obj.repr(
+# 119 "aft_parser.mly"
+                   ( _1 )
+# 746 "aft_parser.ml"
+               : 'or_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'or_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'and_expr) in
+    Obj.repr(
+# 120 "aft_parser.mly"
+                       ( Or(_1,_3) )
+# 754 "aft_parser.ml"
+               : 'or_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'equality_expr) in
+    Obj.repr(
+# 123 "aft_parser.mly"
+                   ( _1 )
+# 761 "aft_parser.ml"
+               : 'and_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'and_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'equality_expr) in
+    Obj.repr(
+# 124 "aft_parser.mly"
+                              ( And(_1,_3) )
+# 769 "aft_parser.ml"
+               : 'and_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'relational_expr) in
+    Obj.repr(
+# 127 "aft_parser.mly"
+                    ( _1 )
+# 776 "aft_parser.ml"
+               : 'equality_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'equality_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'relational_expr) in
+    Obj.repr(
+# 128 "aft_parser.mly"
+                                       ( Equal(_1,_3) )
+# 784 "aft_parser.ml"
+               : 'equality_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'equality_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'relational_expr) in
+    Obj.repr(
+# 129 "aft_parser.mly"
+                                          ( NotEqual(_1,_3) )
+# 792 "aft_parser.ml"
+               : 'equality_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'additive_expr) in
+    Obj.repr(
+# 132 "aft_parser.mly"
+                    ( _1 )
+# 799 "aft_parser.ml"
+               : 'relational_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relational_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'additive_expr) in
+    Obj.repr(
+# 133 "aft_parser.mly"
+                                    ( Lower(_1,_3) )
+# 807 "aft_parser.ml"
+               : 'relational_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relational_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'additive_expr) in
+    Obj.repr(
+# 134 "aft_parser.mly"
+                                    ( Greater(_1,_3) )
+# 815 "aft_parser.ml"
+               : 'relational_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relational_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'additive_expr) in
+    Obj.repr(
+# 135 "aft_parser.mly"
+                                     ( LowerEqual(_1,_3) )
+# 823 "aft_parser.ml"
+               : 'relational_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'relational_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'additive_expr) in
+    Obj.repr(
+# 136 "aft_parser.mly"
+                                     ( GreaterEqual(_1,_3) )
+# 831 "aft_parser.ml"
+               : 'relational_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'multiplicative_expr) in
+    Obj.repr(
+# 139 "aft_parser.mly"
+                        ( _1 )
+# 838 "aft_parser.ml"
+               : 'additive_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'additive_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'multiplicative_expr) in
+    Obj.repr(
+# 140 "aft_parser.mly"
+                                           ( Plus(_1,_3) )
+# 846 "aft_parser.ml"
+               : 'additive_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'additive_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'multiplicative_expr) in
+    Obj.repr(
+# 141 "aft_parser.mly"
+                                            ( Minus(_1,_3) )
+# 854 "aft_parser.ml"
+               : 'additive_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'unary_expr) in
+    Obj.repr(
+# 144 "aft_parser.mly"
+               ( _1 )
+# 861 "aft_parser.ml"
+               : 'multiplicative_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'multiplicative_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'unary_expr) in
+    Obj.repr(
+# 145 "aft_parser.mly"
+                                       ( Mul (_1,_3) )
+# 869 "aft_parser.ml"
+               : 'multiplicative_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'multiplicative_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'unary_expr) in
+    Obj.repr(
+# 146 "aft_parser.mly"
+                                       ( Div (_1,_3) )
+# 877 "aft_parser.ml"
+               : 'multiplicative_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 2 : 'multiplicative_expr) in
+    let _3 = (Parsing.peek_val __caml_parser_env 0 : 'unary_expr) in
+    Obj.repr(
+# 147 "aft_parser.mly"
+                                       ( Mod (_1,_3) )
+# 885 "aft_parser.ml"
+               : 'multiplicative_expr))
+; (fun __caml_parser_env ->
+    let _1 = (Parsing.peek_val __caml_parser_env 0 : 'union_expr) in
+    Obj.repr(
+# 150 "aft_parser.mly"
+               ( _1 )
+# 892 "aft_parser.ml"
+               : 'unary_expr))
+; (fun __caml_parser_env ->
+    let _2 = (Parsing.peek_val __caml_parser_env 0 : 'unary_expr) in
+    Obj.repr(
+# 151 "aft_parser.mly"
+                    ( UnaryMinus _2 )
+# 899 "aft_parser.ml"
+               : 'unary_expr))
+(* Entry aft_pattern_match *)
+; (fun __caml_parser_env -> raise (Parsing.YYexit (Parsing.peek_val __caml_parser_env 0)))
+(* Entry access_spec *)
+; (fun __caml_parser_env -> raise (Parsing.YYexit (Parsing.peek_val __caml_parser_env 0)))
+|]
+let yytables =
+  { Parsing.actions=yyact;
+    Parsing.transl_const=yytransl_const;
+    Parsing.transl_block=yytransl_block;
+    Parsing.lhs=yylhs;
+    Parsing.len=yylen;
+    Parsing.defred=yydefred;
+    Parsing.dgoto=yydgoto;
+    Parsing.sindex=yysindex;
+    Parsing.rindex=yyrindex;
+    Parsing.gindex=yygindex;
+    Parsing.tablesize=yytablesize;
+    Parsing.table=yytable;
+    Parsing.check=yycheck;
+    Parsing.error_function=parse_error;
+    Parsing.names_const=yynames_const;
+    Parsing.names_block=yynames_block }
+let aft_pattern_match (lexfun : Lexing.lexbuf -> token) (lexbuf : Lexing.lexbuf) =
+   (Parsing.yyparse yytables 1 lexfun lexbuf : Aft_types.pattern_match)
+let access_spec (lexfun : Lexing.lexbuf -> token) (lexbuf : Lexing.lexbuf) =
+   (Parsing.yyparse yytables 2 lexfun lexbuf : Aft_types.access_spec)
diff --git a/aft_parser.mly b/aft_parser.mly
new file mode 100644 (file)
index 0000000..95f78ac
--- /dev/null
@@ -0,0 +1,151 @@
+%{
+  open Xpath_syntax
+  open Xpath_ext
+  open Axis
+  open Aft_types
+%}
+
+%token POINT LBRACE RBRACE
+%token SLASH LPAREN RPAREN LBRACKET RBRACKET
+%token DOUBLESLASH DOUBLEDOT AT DOT COMMA PIPE
+%token OR AND EQUAL NOTEQUAL LT GT LTE GTE
+%token PLUS MINUS MUL DIV MOD
+%token <string> VAR
+%token <string> NAME_TEST AXIS FUNCTION_NAME NODE_TYPE
+%token <string> LITERAL
+%token <float> NUMBER
+%token EOF
+
+%type <Aft_types.pattern_match> aft_pattern_match
+%start aft_pattern_match
+
+%type <Aft_types.access_spec> access_spec
+%start access_spec
+
+%%
+access_spec:
+    expr { Filter($1) }
+ |  aft_pattern_match { PatternMatch($1) }
+
+aft_clause:
+    location_path POINT LBRACE access_spec RBRACE { Clause($1 , $4) }
+
+aft_pattern_match:
+    aft_clause { [ $1 ] }
+ |  aft_clause PIPE aft_pattern_match {$1::$3}
+
+location_path:
+   relative_location_path      { $1 }
+ | absolute_location_path      { $1 }
+
+absolute_location_path:
+   SLASH   { Root }
+ | SLASH relative_location_path  { Slash (Root,$2) }
+ | DOUBLESLASH relative_location_path { double_slash Root $2 }
+
+relative_location_path:
+   step    { $1 }
+ | relative_location_path SLASH step { Slash ($1,$3) }
+ | relative_location_path DOUBLESLASH step { double_slash $1 $3 }
+
+step:
+ | axis_specifier step2 { Axis ($1,$2) }
+ | step2 { $1 }
+ | DOT   { dot  }
+ | DOUBLEDOT  { dotdot }
+
+step2:
+ | step2 LBRACKET expr RBRACKET { Condition ($1,$3) } 
+ | node_test { $1 } 
+
+axis_specifier:
+ | AXIS { 
+     try Axis.of_string $1 
+     with Not_found -> failwith ("Unknown axis :"^$1)
+   }
+ | AT { Axis.Attribute }
+
+
+node_test:
+ | NAME_TEST  { Name $1 }
+ | NODE_TYPE RPAREN { 
+     try TypeTest (Type_test.of_string $1) 
+     with Not_found -> failwith ("Unknown node type :"^$1)
+   }
+ | NODE_TYPE LITERAL RPAREN {
+     match $1 with
+       | "processing-instruction" ->
+          TypeTest (Type_test.Pi_test (Some $2))
+       | _ -> failwith "Only processing-instruction tests accept argument" 
+   }
+
+primary_expr:
+   function_call   { $1 }
+ | VAR             { Var $1 }
+ | LPAREN expr RPAREN  { $2 }
+ | LITERAL         { String_literal $1 } 
+ | NUMBER          { Number_literal $1 } 
+
+function_call:
+   FUNCTION_NAME RPAREN  { Function ($1,[]) }
+ | FUNCTION_NAME arguments RPAREN  { Function ($1,$2) }
+
+arguments:
+   arguments COMMA expr   { $1@[$3] }
+ | expr { [$1] }
+
+union_expr:
+   path_expr        { $1 }
+ | union_expr PIPE path_expr  { path_expr (Pipe(expr $1, expr $3)) }
+
+path_expr:
+   location_path    { path_expr $1 }
+ | filter_expr      { $1 } 
+ | filter_expr SLASH relative_location_path 
+     {  path_expr (Slash (expr $1,$3)) } 
+ | filter_expr DOUBLESLASH relative_location_path 
+     {  path_expr (double_slash (expr $1) $3) }
+
+filter_expr:
+   primary_expr { $1 }  
+ | filter_expr LBRACKET expr RBRACKET { path_expr (Condition (expr $1,$3)) } 
+
+
+expr:
+   or_expr         { $1 } 
+
+or_expr:
+   and_expr        { $1 } 
+ | or_expr OR and_expr { Or($1,$3) }
+
+and_expr:
+   equality_expr   { $1 }
+ | and_expr AND equality_expr { And($1,$3) }
+
+equality_expr:
+   relational_expr  { $1 }
+ | equality_expr EQUAL relational_expr { Equal($1,$3) }
+ | equality_expr NOTEQUAL relational_expr { NotEqual($1,$3) }
+
+relational_expr: 
+   additive_expr    { $1 }
+ | relational_expr LT additive_expr { Lower($1,$3) }
+ | relational_expr GT additive_expr { Greater($1,$3) }
+ | relational_expr LTE additive_expr { LowerEqual($1,$3) }
+ | relational_expr GTE additive_expr { GreaterEqual($1,$3) }
+
+additive_expr:
+   multiplicative_expr  { $1 }
+ | additive_expr PLUS multiplicative_expr  { Plus($1,$3) }
+ | additive_expr MINUS multiplicative_expr  { Minus($1,$3) }
+
+multiplicative_expr:
+   unary_expr  { $1 }
+ | multiplicative_expr MUL unary_expr  { Mul ($1,$3) }
+ | multiplicative_expr DIV unary_expr  { Div ($1,$3) }
+ | multiplicative_expr MOD unary_expr  { Mod ($1,$3) }
+
+unary_expr:
+ | union_expr  { $1 }
+ | MINUS unary_expr { UnaryMinus $2 }
diff --git a/aft_types.ml b/aft_types.ml
new file mode 100644 (file)
index 0000000..99231c9
--- /dev/null
@@ -0,0 +1,34 @@
+open Xpath_ext
+open Xpath_syntax
+open Printf
+open Globals
+
+let rec pretty_print_xpath_path xpath_path = 
+  match xpath_path with 
+    | Pipe(e1,e2) ->  (*Slash(_,Expr(String_literal(se))) ->*)
+        (*sprintf "%s.x" se *)
+        let s1 = pretty_print_xpath_path e1 in
+        let s2 = pretty_print_xpath_path e2 in
+          sprintf "%s|%s" s1 s2
+    | Slash(e1,e2) ->
+        let s1 = pretty_print_xpath_path e1 in
+        let s2 = pretty_print_xpath_path e2 in
+          sprintf "%s/%s" s1 s2
+    | Condition(e,expr) ->
+        let s = pretty_print_xpath_path e in
+          sprintf "%s[cond]" s
+    | Root ->
+        ""
+    | Axis(_,e)->
+        pretty_print_xpath_path e
+    | Name(s)->
+        s
+    | _ -> raise AftError
+
+
+type access_spec = Filter of expr | INF of inf | PatternMatch of pattern_match
+    and right_clause = True of access_spec 
+    and left_clause = False of access_spec 
+    and inf = path_expr * right_clause * left_clause
+    and clause = Clause of path_expr * access_spec
+    and pattern_match = clause list
diff --git a/globals.ml b/globals.ml
new file mode 100644 (file)
index 0000000..a906196
--- /dev/null
@@ -0,0 +1,7 @@
+let print fmt = Printf.printf (fmt ^^ "%!")
+
+let tab n = String.make n ' '
+
+let tabprint n fmt = Printf.printf ("%s" ^^ fmt ^^ "%!") (tab n)
+
+exception AftError
diff --git a/python.ml b/python.ml
new file mode 100644 (file)
index 0000000..99dcbe0
--- /dev/null
+++ b/python.ml
@@ -0,0 +1,50 @@
+(* To be cleaned up - prototype version *)
+
+open Globals
+open Xpath_syntax
+open Printf
+
+type block = If of exp * block * block 
+  | Return of exp
+  | Call of lval option * exp
+
+  | Set of lval * exp
+and
+  exp = Xpath_syntax.expr
+and
+  lval = Lval of string
+
+let rec str_of_expr = function
+  | String_literal(s)->sprintf "\"%s\"" s
+  | Number_literal(f)->if (f=1.0) then "true" else if (f=0.0) then "false" else sprintf "%f" f
+  | Var(s)->s
+  (*| Function of string * (expr list)
+  | PathExpr of path_expr
+    *)
+  | Equal(e1,e2) -> (str_of_expr e1) ^ "=" ^ (str_of_expr e2)
+  | NotEqual(e1,e2) -> (str_of_expr e1) ^ "!=" ^ (str_of_expr e2)
+  | Lower(e1,e2) -> (str_of_expr e1) ^ "<" ^ (str_of_expr e2)
+  | Greater(e1,e2) -> (str_of_expr e1) ^ ">" ^ (str_of_expr e2)
+  | LowerEqual(e1,e2) -> (str_of_expr e1) ^ "<=" ^ (str_of_expr e2)
+  | GreaterEqual(e1,e2) -> (str_of_expr e1) ^ ">=" ^ (str_of_expr e2)
+  | _ -> print "Expression type not supported yet";raise AftError
+  (*
+  | Plus of expr * expr
+  | Minus of expr * expr
+  | Mul of expr * expr
+  | Div of expr * expr
+  | Mod of expr * expr
+  | UnaryMinus of expr
+  | Or of expr * expr
+  | And of expr * expr
+  *)
+
+
+let rec pretty_print_block tablevel = function
+  | Return(e) -> tabprint tablevel "return %s\n" (str_of_expr(e))
+  | If(e, b1, b2) -> 
+      tabprint tablevel "if (%s):\n" (str_of_expr(e));
+      pretty_print_block (tablevel+1) b1;
+      tabprint tablevel "else:\n";
+      pretty_print_block (tablevel+1) b2
+  | _ -> print "Expression type not supported yet";raise AftError
diff --git a/python_dict.ml b/python_dict.ml
new file mode 100644 (file)
index 0000000..d39b216
--- /dev/null
@@ -0,0 +1,82 @@
+(* To be cleaned up - prototype version *)
+
+open Aft_types
+open Xpath_syntax
+open Printf
+open Python
+open Globals
+
+let rec squash prefix = function
+    | Slash(Root, e) ->
+        print "Root squash";
+        squash "" e
+    | Slash(e1, e2) ->
+        (squash prefix e1) ^ "." ^ (squash prefix e2)
+    | Axis(_,e)->
+        squash prefix e
+    | Name(s)->
+        s
+    | _ -> print "XPath type not supported.";raise AftError
+
+             (*
+let serialize_path_existential b xpath_path =
+  let serialize_path_ex' b prefix x =
+      match x with 
+        | Expr(expr) ->
+        | Pipe(e1, e2) ->  
+            print "Pipes not supported"
+            raise AftError
+        | Slash(e1, e2) ->
+            (serialize_xpath e1) ^ (serialize_xpath e2)
+        | Condition(e, expr) ->
+            if (b) then begin print "Double expressions not yet supported";raise AftError end
+                else
+                   fully_qualify_expr prefix expr
+            eval e
+        | Root ->
+            -1
+        | Axis(_,e)->
+            eval e
+        | Name(s)->
+            let c = String.get s 0 in
+            let ic = int_of_char c in
+              if (ic > 64 && ic < 91) then 1 else 0
+        | _ -> raise AftError
+              *)
+
+let rec fqe prefix = function
+  | PathExpr(path_expr) -> Var (prefix^"."^squash prefix path_expr)
+  | Equal(e1, e2) -> Equal (fqe prefix e1, fqe prefix e2)
+  | NotEqual(e1, e2) -> NotEqual (fqe prefix e1, fqe prefix e2)
+  | Lower(e1, e2) -> Lower(fqe prefix e1, fqe prefix e2)
+  | Greater(e1, e2) -> Greater(fqe prefix e1, fqe prefix e2)
+  | LowerEqual(e1, e2) -> LowerEqual(fqe prefix e1, fqe prefix e2)
+  | GreaterEqual(e1, e2) -> GreaterEqual(fqe prefix e1, fqe prefix e2)
+  | Plus(e1, e2) -> Plus(fqe prefix e1, fqe prefix e2)
+  | Minus(e1, e2) -> Minus(fqe prefix e1, fqe prefix e2)
+  | Mul(e1, e2) -> Mul(fqe prefix e1, fqe prefix e2)
+  | Div(e1, e2) -> Div(fqe prefix e1, fqe prefix e2)
+  | Mod(e1, e2) -> Mod(fqe prefix e1, fqe prefix e2)
+  | UnaryMinus(e) -> UnaryMinus(fqe prefix e)
+  | Or(e1, e2) -> Or(fqe prefix e1, fqe prefix e2)
+  | And(e1, e2) -> And(fqe prefix e1, fqe prefix e2)
+  | l -> l
+
+let rec cond_to_expr = function
+    | Slash(Root,e) -> cond_to_expr e
+    | Condition(e, expr) ->
+        let prefix = squash "" e in
+            fqe prefix expr
+    | e -> 
+       Var (squash "" e) 
+
+let rec from_aft acl =
+  let rec from_aft' l =
+      match l with 
+        | Filter(x) -> Return(fqe "" x)
+        | INF(path, True(l'), False(l'')) ->
+            let cond = cond_to_expr path in
+              If (cond, from_aft(l'), from_aft(l''))
+        | PatternMatch(_) -> print "Expression not reduced";raise AftError
+  in
+    from_aft' acl 
diff --git a/xpath_ext.ml b/xpath_ext.ml
new file mode 100644 (file)
index 0000000..b5a7340
--- /dev/null
@@ -0,0 +1,73 @@
+open Printf
+
+(*module Names = Xpath_names*)
+
+type node_type =
+  | Root_node
+  | Element_node
+  | Attribute_node
+  | Namespace_node
+  | Pi_node
+  | Comment_node
+  | Text_node
+
+module Type_test =
+struct
+  type t = 
+    | Text_test
+    | Comment_test
+    | Pi_test of string option
+    | Node_test
+
+  let of_string = function
+    | "comment" ->  Comment_test
+    | "text" -> Text_test
+    | "processing-instruction" ->  Pi_test None
+    | "node" -> Node_test
+    | s -> raise Not_found
+end
+
+module Axis =
+struct
+  type t = 
+    | Ancestor
+    | Ancestor_or_self
+    | Attribute
+    | Child
+    | Descendant
+    | Descendant_or_self
+    | Following
+    | Following_sibling
+    | Namespace
+    | Parent
+    | Preceding
+    | Preceding_sibling
+    | Self
+
+  let principal_type = function
+    | Attribute -> Attribute_node
+    | Namespace -> Namespace_node
+    | _         -> Element_node
+
+  let of_string = function
+    | "ancestor" -> Ancestor
+    | "ancestor-or-self" -> Ancestor_or_self
+    | "attribute" -> Attribute
+    | "child" -> Child
+    | "descendant" -> Descendant
+    | "descendant-or-self" -> Descendant_or_self
+    | "following" -> Following
+    | "following-sibling" -> Following_sibling
+    | "namespace" -> Namespace
+    | "parent" -> Parent
+    | "preceding" -> Preceding
+    | "preceding-sibling" -> Preceding_sibling
+    | "self" -> Self
+    | s -> raise Not_found
+
+  type direction = Forward | Reverse
+
+  let direction = function
+    | (Ancestor | Ancestor_or_self | Preceding | Preceding_sibling) -> Reverse
+    | _ -> Forward
+end
diff --git a/xpath_syntax.ml b/xpath_syntax.ml
new file mode 100644 (file)
index 0000000..070fe6f
--- /dev/null
@@ -0,0 +1,54 @@
+(* XPath expressions *)
+
+type expr = 
+  | String_literal of string
+  | Number_literal of float
+  | Var of string
+  | Function of string * (expr list)
+  | PathExpr of path_expr
+
+  | Equal of expr * expr
+  | NotEqual of expr * expr
+  | Lower of expr * expr
+  | Greater of expr * expr
+  | LowerEqual of expr * expr
+  | GreaterEqual of expr * expr
+  | Plus of expr * expr
+  | Minus of expr * expr
+  | Mul of expr * expr
+  | Div of expr * expr
+  | Mod of expr * expr
+  | UnaryMinus of expr
+  | Or of expr * expr
+  | And of expr * expr
+
+and path_expr =
+  | Pipe of path_expr * path_expr
+  | Slash of path_expr * path_expr
+  | Axis of Xpath_ext.Axis.t * path_expr
+  | Name of string
+  | TypeTest of Xpath_ext.Type_test.t
+  | Condition of path_expr * expr
+  | Root
+  | Expr of expr
+
+let path_expr = function
+  | Expr e -> e
+  | e -> PathExpr e
+
+let expr = function
+  | PathExpr e -> e
+  | e -> Expr e
+
+let double_slash =
+  let desc = Axis(
+    Xpath_ext.Axis.Descendant_or_self, 
+    TypeTest Xpath_ext.Type_test.Node_test) in
+  fun before after ->
+    Slash( Slash (before,desc), after )
+
+
+let dot =  
+  Axis(Xpath_ext.Axis.Self, TypeTest Xpath_ext.Type_test.Node_test)
+let dotdot = 
+  Axis(Xpath_ext.Axis.Parent, TypeTest Xpath_ext.Type_test.Node_test)