(***********************************************************************)
(*                                                                     *)
(*                                 GALAX                               *)
(*                            XML Query Engine                         *)
(*                                                                     *)
(*  Copyright 2000, Lucent Technologies.                               *)
(*  Distributed only by permission.                                    *)
(*                                                                     *)
(***********************************************************************)

(* $Id: xquery_ast.mli,v 1.37 2003/01/20 15:53:19 mff Exp $ *)

(************************)
(* Abstract Syntax Tree *)
(************************)

open Namespace
open Sym

(* This module contains data structures used to represent
   components of XQuery and the core *)

(**************************)
(* Common data structures *)
(**************************)

(* Names *)

type tname      = uqname (* type name *)
type sname      = uqname (* schema name *)
type vname      = uqname (* variable name *)
type rname      = uqname (* row name in a tuple *)
type fname      = uqname (* function name *)

type rfname     = rqname (* resolved function name *)

(* type nclassname = uqname (* name class name *) *)

(* Sorting criteria *)

type sortkind =
  | Ascending
  | Descending

type emptysortkind =
  | EmptyGreatest
  | EmptyLeast

type stablekind =
  | Stable
  | NonStable

(*************)
(* Types AST *)
(*************)

(* New syntax for types *)

(* Derivation *)

type deriv =
  | TRestriction of tname
  | TExtension of tname

(* Models *)

type datatype_kind = 
  | DTAttrRef of attr_symbol option              (* Attribute ref  : ATTRIBUTE QName *)
  | DTElemRef of elem_symbol option              (* Element ref    : ELEMENT QName *)
  | DTTypeRef of group_symbol                    (* Type ref      : TYPE QName *)
  | DTNode 
  | DTItem
  | DTAtomic
  | DTNumeric
  | DTText
  | DTBase of Datatypes.atomic_type
  | DTDocument of elem_symbol option
  | DTDocumentOfType of group_symbol
  | DTElemOfType of group_symbol
  | DTElemOfBase  of Datatypes.atomic_type
  | DTEmpty                        (* MFF: () is necessary for specifying XPath semantics *)

type datatype_desc = datatype_kind * (Occurrence.occurs * Occurrence.occurs) option

type datatype = 
    { pdatatype_desc: datatype_desc;
      pdatatype_loc: Finfo.finfo }

type model =
    { pmodel_desc: model_desc;
      pmodel_loc: Finfo.finfo }

and model_desc =
  | TAttrRef of attr_symbol                                (* Attribute ref   : ATTRIBUTE QName *)
  | TAttrLocal of attr_symbol * typed_model                (* Local attribute : ATTRIBUTE NameClass { Model } *)
  | TElemRef of elem_symbol                                (* Element ref     : ELEMENT QName *)
  | TElemLocal of elem_symbol * deriv option * typed_model (* Local element   : ELEMENT NameClass { Model } *)
  | TGroupRef of group_symbol                              (* Group reference : Group QName *)
  | TBound of model * Occurrence.occurs * Occurrence.occurs
  | TComma of model * model
  | TEmpty
  | TBar of model * model
  | TNone
  | TAmp of model * model
  | TBase of Datatypes.atomic_type
  | TDocument of model
  | TText
(* Additions *)
  | TTuple of (rname * model) list

and typed_model =
    { ptyped_model_desc: typed_model_desc;
      ptyped_model_loc: Finfo.finfo }

and typed_model_desc =
(* Commented until further use - J&B *)
(*| TTypeRef of tname                               (* Type reference : TYPE QName *) *)
(*| TNamedType of nameclass * deriv option * model  (* Complex type   : TYPE Nameclass ... { Model } *) *)
  | TAnonymousType of model                         (* Anonymous type : Model *)

type sort_decl =
    { psort_decl_desc: sort_decl_desc;
      psort_decl_loc: Finfo.finfo }

and sort_decl_desc =
  | AttrDecl of attr_symbol * typed_model      (* Attribute declaration   : DEFINE ATTRIBUTE QName { Type } *)
  | ElemDecl of elem_symbol * typed_model      (* Element declaration     : DEFINE ELEMENT QName { Type } *)
  | TypeDecl of group_symbol * model           (* Type declaration        : DEFINE TYPE QName { Model } *)

(* Commented until further use - J&B *)
(*| TypeDecl of tname * deriv option * model   (* Complex type declaration: TYPE QName { Model } *) *)

type sort_decl_list = sort_decl list

(*************************)
(* XPath data structures *)
(*************************)

(* XPath 2.0 operators *)

type unaryop =
  | UEPlus                                          (* +e1 *)
  | UEMinus                                         (* -e1 *)

type binop =
  | BEIntersect                                     (* e1 intersect e2 *)
  | BEUnion                                         (* e1 union e2 *)
  | BEExcept                                        (* e1 except e2 *)
  | BEBar                                           (* e1 | e2 *)

  | BEAnd                                           (* e1 and e2 *)
  | BEOr                                            (* e1 or e2 *)

  | BEPrecedes                                      (* e1 precedes e2 *)
  | BEFollows                                       (* e1 follows e2 *)

  | BEEq                                            (* e1 eq e2 *)
  | BENEq                                           (* e1 ne e2 *)
  | BELtOp                                          (* e1 lt e2 *)
  | BELte                                           (* e1 le e2 *)
  | BEGtOp                                          (* e1 gt e2 *)
  | BEGte                                           (* e1 ge e2 *)

  | BEEqual                                         (* e1 = e2 *)
  | BENEqual                                        (* e1 != e2 *)
  | BEIs                                            (* e1 is e2 *)
  | BEIsNot                                         (* e1 isnot e2 *)
  | BELt                                            (* e1 < e2 *)
  | BEGt                                            (* e1 > e2 *)
  | BELteq                                          (* e1 <= e2 *)
  | BEGteq                                          (* e1 >= e2 *)

  | BEPlus                                          (* e1 + e2 *)
  | BEMinus                                         (* e1 - e2 *)

  | BEMult                                          (* e1 * e2 *)
  | BEDiv                                           (* e1 div e2 *)
  | BEIDiv                                          (* e1 idiv e2 *)
  | BEMod                                           (* e1 mod e2 *)

(* Node tests *)

type node_kind =
  | PIKind of string option  (* ./pi("xxx") *)
  | CommentKind              (* ./comment () *)
  | TextKind                 (* ./text() *)
  | AnyKind                  (* ./node() *)

type node_test =
  | PNameTest of uqname           (* ./a or ./*:b or ./b:* or ./* *)
  | PNodeKindTest of node_kind

(* XPath axis *)

type axis =
  | Ancestor
  | Ancestor_or_self
  | Attribute
  | Child
  | Descendant
  | Descendant_or_self
  | Namespace
  | Parent
  | Self

(* Those are not supported yet - JS
  | Following
  | Following_sibling
  | Preceding
  | Preceding_sibling
*)

(**********************)
(* XQuery expressions *)
(**********************)

(* Patterns used in typeswitch *)

type pattern =
    { ppattern_desc: pattern_desc;
      ppattern_loc: Finfo.finfo }

and pattern_desc =
  | Case of datatype
  | Default

  (* NOTE: not clear what we want as a model pointer. B&J *)
type model_handle = model option

type expr =
    { pexpr_desc: expr_desc;
(*    mutable pexpr_ty: model_handle ref; *)
      pexpr_loc: Finfo.finfo }

and expr_desc =
  | ESort of expr * order_by                             (* Sort expression: e1 stable? sortby e2... *)
  | EUnordered of expr                                   (* unordered Expr *)
  | EBinaryOp of expr * binop * expr                     (* Binary operator: 3 + 2 *)
  | EFLWR of fl_expr list *
	expr option * order_by option * expr             (* FLWRExpr       : for $v1 in .... return e2 *) (* fl_expr: for/let expr, expr option: optional where clause, expr: expression in return clause *)
  | EIf of expr * expr * expr                            (* IfExpr         : if e1 then e2 else e3 *)
  | ESome of (datatype option * vname * expr) list * expr  (* SomeExpr       : existential quantification *)
  | EEvery of (datatype option * vname * expr) list * expr (* EveryExpr      : universal quantification *)
  | ETypeswitch of expr *                                (* TypeswitchExpr : typeswitch e1 as $v ... *)
	(pattern * vname option * expr) list
  | EInstanceOf of expr * datatype                       (* InstanceofExpr : e1 instanceof t1 *)
  | ERange of expr * expr                                (* RangeExpr      : e1 to e2 *)
  | EUnaryOp of unaryop * expr                           (* UnaryExpr      : +2, -$v, ... *)
  | ERoot                                                (* Root           : / *)
  | EPath of path_expr                                   (* Other XPath expressions e1/e2 ... *)
  | ESelf                                                (* Self           : . *)
  | EParent                                              (* Parent         : .. *)
  | EVar of vname                                        (* Variable       : $v, $a:b *)
  | EScalar of Datatypes._AtomicValue                    (* Literal value  : 2.1 "John" true *)
  | EApp of fname * (expr list)                          (* FunctionCall   : f($v) *)
  | EList of expr list                                   (* ExprSequence   : (e1,...,en) *)
  | ECast of expr * datatype                             (* casting with value conversion *)
  | ETreat of expr * datatype                            (* downcast - no conversion *)
  | EValidate of expr * datatype                         (* XML Schema validation *)
  | EElemFixed of elem_symbol * expr list * expr list    (* ElementConstructor  : <a b1="">...</a> *)
  | EElemComputed of expr * expr list                    (* ElementConstructor  : ELEMENT { e1 } { e2 } *)
  | EAttrFixed of attr_symbol * expr list                (* AttributeConstructor: ATTRIBUTE a { Expr } *)
  | EAttrComputed of expr * expr list                    (* AttributeConstructor: ATTRIBUTE { e1 } { e2 } *)
  | EDocument of expr list                               (* DocumentConstructor : document { ... } *)
  | EText of Datatypes._untyped                          (* TextConstructor     : text { "This is text" } *)
  | ETextComputed of expr list                           (* TextConstructor     : text { "This is text" } *)
  | EPI of Namespace.ncname * string                     (* Processing instruction: <? ... ?> *)
  | EComment of string                                   (* Comment: <!-- ... --> *)
(*| EAssert of expr * datatype *)
(* Note: The last two expressions are not part of XQuery - Jerome *)
  | ESubtype of datatype * datatype
  | EIntersects of datatype * datatype
and path_expr =
  | PSlash of expr * expr                               (* e1/e2 *)
  | PSlashSlash of expr * expr                          (* e1//e2 *)
  | PAxis of axis * node_test                           (* axis::nodetest *)
  | PStepQualifiers of expr * step_qualifier list       (* e1[e2][e3]=>e1... *)

and step_qualifier =
    { pstep_qualifier_desc: step_qualifier_desc;
      pstep_qualifier_loc: Finfo.finfo }

and step_qualifier_desc =
(*| DereferenceQualifier of uqname *)
  | PredicateQualifier of expr

and fl_expr =
    { pfl_desc: fl_expr_desc;
      pfl_loc: Finfo.finfo }

and fl_expr_desc =
    (* Second optional vname is for the 'at $i' position variable - Jerome *)
  | ELet of datatype option * vname * expr
  | EFor of datatype option * vname * vname option * expr

and order_by =
    stablekind * (expr * sortkind * emptysortkind) list

(***********)
(* Updates *)
(***********)

type insert_location =
  | UAsLastInto of expr
  | UAsFirstInto of expr
  | UInto of expr
  | UAfter of expr
  | UBefore of expr

type update =
    { pupdate_desc: update_desc;
      pupdate_loc: Finfo.finfo }

and update_desc =
  | USimple of simple_update
  | UComplex of complex_update

and simple_update =
    { psimple_update_desc: simple_update_desc;
      psimple_update_loc: Finfo.finfo }

and simple_update_desc =
  | UInsert of expr * insert_location
  | UDelete of expr
  | UEmpty

and complex_update =
    { pcomplex_update_desc: complex_update_desc;
      pcomplex_update_loc: Finfo.finfo }

and complex_update_desc =
  | UFLWR of fl_expr list * expr option * order_by option * simple_update list
  | UCond of expr * simple_update * simple_update

(********************)
(* XQuery toplevels *)
(********************)

(* Global functions *)

type function_body =
  | EFunctionBltIn of fname
  | EFunctionUser of (vname list) * expr

type function_signature = datatype list * datatype

type function_def =
    { pfunction_def_desc: function_def_desc;
      pfunction_loc: Finfo.finfo }

and function_def_desc = fname * function_signature * function_body

(* Global variable declaration *)

type var_decl =
    { pvar_decl_desc: var_decl_desc;
      pvar_decl_loc: Finfo.finfo }

and var_decl_desc = vname * expr

(* Key definitions *)

type key_def =
    { pkey_def_desc: key_def_desc;
      pkey_def_loc: Finfo.finfo }

and key_def_desc = string * expr * expr

(* Context declarations *)

type context_decl =
    { pcontext_decl_desc: context_decl_desc;
      pcontext_decl_loc: Finfo.finfo }

and context_decl_desc =
  | ENamespaceDecl of (ncname * uri)
  | EDefaultElementNamespaceDecl of uri
  | EDefaultFunctionNamespaceDecl of uri
  | ESchemaDecl of (ncname option * string * string option)
  | EDefaultSchemaDecl of string

(* Statements *)

type statement =
    { pstatement_desc: statement_desc;
      pstatement_loc: Finfo.finfo }

and statement_desc =
  | SExpression of expr
  | SUpdate of update

(* Query module *)

type query_module =
    { mutable pmodule_sorts : sort_decl_list;
      mutable pmodule_functions : function_def list;
      mutable pmodule_contexts : context_decl list;
      mutable pmodule_vars : var_decl list;
      mutable pmodule_keys : key_def list;
      mutable pmodule_exprs : statement list }


(********************)
(* Core Expressions *)
(********************)

(* Handles on the original expressions or types *)

  (* NOTE: not clear what we want as an expression pointer. B&J *)
type expr_handle = expr option

type cexpr =
    { pcexpr_desc: cexpr_desc;
      mutable pcexpr_type: model_handle;
      mutable pcexpr_origin: expr_handle;
  (* Do we want to keep track of the original expressions in the core ? J&B *)
      pcexpr_loc: Finfo.finfo }

and cnode_test =
  | CPNameTest of rqname
  | CPNodeKindTest of node_kind

and cexpr_desc =
  | CESort of vname * cexpr * stablekind * cexpr * sortkind * emptysortkind
  | CEUnordered of cexpr
  | CEFor of datatype option * vname * vname option * cexpr * cexpr
  | CELet of datatype option * vname * cexpr * cexpr
  | CEIf of cexpr * cexpr * cexpr
  | CETypeswitch of cexpr * (pattern * vname option * cexpr) list
  | CEVar of vname
  | CEScalar of Datatypes._AtomicValue
  | CEDocument of cexpr
  | CEPI of Namespace.ncname * string
  | CEComment of string
  | CEText of Datatypes._untyped
  | CETextComputed of cexpr
  | CEApp of rfname * (cexpr list)
  | CESeq of cexpr * cexpr
  | CEEmpty
  | CEElem of  relem_symbol * cexpr
  | CEAnyElem of cexpr * cexpr
  | CEAttr of rattr_symbol * cexpr
  | CEAnyAttr of cexpr * cexpr
  | CEError of cexpr 
  | CETreat of cexpr * model
  | CEValidate of cexpr * model
  | CECast of cexpr * model
  | CEForwardAxis of axis * cnode_test
  | CEReverseAxis of axis * cnode_test

(* NOTE: The following are extension to the XQuery Formal Semantics Core XQuery - Jerome *)
  | CESubtype of model * model         			(* Explicit subtyping check *)
  | CEIntersects of model * model      			(* Explicit intersection check *)
  | CESome of datatype option * vname * cexpr * cexpr   (* Universal quantification *)
  | CEEvery of datatype option * vname * cexpr * cexpr  (* Existential quantification *)
  | CEKeyRef of string * cexpr                          (* Key reference *)
  | CECreateTuple of (rname * cexpr) list               (* Creates a new tuple *)
  | CEAccessTuple of cexpr * rname                      (* Accesses a new tuple *)
  | CEForTuple of vname * cexpr * cexpr                 (* Iteration over a sequence of tuples *)

(****************)
(* Core updates *)
(****************)

type cinsert_location =
  | CUAsLastInto of cexpr
  | CUAsFirstInto of cexpr
  | CUInto of cexpr
  | CUAfter of cexpr
  | CUBefore of cexpr

  (* NOTE: not clear what we want as an expression pointer. B&J *)
type update_handle = update option

type cupdate =
    { pcupdate_desc: cupdate_desc;
      mutable pcupdate_origin: update_handle;
      pcupdate_loc: Finfo.finfo }

and cupdate_desc =
  | CUSimple of csimple_update
  | CUComplex of ccomplex_update

and csimple_update =
    { pcsimple_update_desc: csimple_update_desc;
      pcsimple_update_loc: Finfo.finfo }

and csimple_update_desc =
  | CUInsert of cexpr * cinsert_location
  | CUDelete of cexpr
  | CUEmpty

and ccomplex_update =
    { pccomplex_update_desc: ccomplex_update_desc;
      pccomplex_update_loc: Finfo.finfo }

and ccomplex_update_desc =
  | CUForTuple of vname * cexpr * csimple_update list
  | CUCond of cexpr * csimple_update * csimple_update

(******************)
(* Core toplevels *)
(******************)

(* Functions definition *)

type cfunction_body =
  | CEFunctionBltIn of rfname
  | CEFunctionUser of (vname list) * cexpr

type cfunction_signature = (datatype * model) list * (datatype * model)

type cfunction_def =
    { pcfunction_def_desc: cfunction_def_desc;
      pcfunction_loc: Finfo.finfo }

and cfunction_def_desc = rfname * cfunction_signature * cfunction_body

(* Global variable declaration *)

type cvar_decl =
    { pcvar_decl_desc: cvar_decl_desc;
      pcvar_decl_loc: Finfo.finfo }

and cvar_decl_desc = vname * cexpr

(* Key definitions *)

type ckey_def =
    { pckey_def_desc: ckey_def_desc;
      pckey_def_loc: Finfo.finfo }

and ckey_def_desc = string * cexpr * cexpr

(* Statements *)

type cstatement =
    { pcstatement_desc: cstatement_desc;
      pcstatement_loc: Finfo.finfo }

and cstatement_desc =
  | CSExpression of cexpr
  | CSUpdate of cupdate

(* Core Query module *)

type cquery_module =
    { mutable pcmodule_functions : cfunction_def list;
      mutable pcmodule_vars : cvar_decl list;
      mutable pcmodule_keys : ckey_def list;
      mutable pcmodule_exprs : cstatement list }

type cquery_module_list = cquery_module list


