;; AST definition  -*-Lisp-*-

;  This file is part of cqual.
;  Copyright (C) 2000-2001 The Regents of the University of California.
;
; cqual is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation; either version 2, or (at your option)
; any later version.
;
; cqual is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with cqual; see the file COPYING.  If not, write to
; the Free Software Foundation, 59 Temple Place - Suite 330,
; Boston, MA 02111-1307, USA.

;; (deffield FIELD-NAME C-TYPE (ATTRIBUTES))
;; (deftype TYPE-NAME SUPER-TYPE (FIELDS) "DOCUMENTATION")
;; (defnode NODE-NAME TYPE-NAME "DOCUMENTATION")

;; deffield:
;; Define field FIELD-NAME with type C-TYPE. The attributes listed are 
;; interpreted by the various generators, attributes are either symbols,
;; or lists whose first element is a symbol

;; Current attributes:
;;   init: field is an argument to the constructing function for the types
;;         that contain it
;;   nodump: field is not marshalled/unmarshalled
;;   noprint: field is not printed as part of AST
;;   dump-special: call dump_FIELD-NAME to marshall/unmarshall this node
;;   print-special: call print_FIELD-NAME to print node



(deffield temp int (nodump noprint (default "23"))) ; a random int field with default value 23

(deffield type type ())
(deffield declared_type type ())
(deffield name "const char *" ())
(deffield loc location (init))
(deffield next "node sameregion" ()) 
(deffield asttype asttype (init tree))
(deffield condition expression (init tree))
(deffield arg1 expression (init tree))
(deffield arg2 expression (init tree))
(deffield arg3 expression (init tree))
(deffield stmt statement (init tree))
(deffield stmt1 statement (init tree))
(deffield stmt2 statement (init tree))
(deffield stmts statement (init tree))
(deffield asm_stmt asm_stmt (init tree))
(deffield extension bool ())
(deffield label label (init tree))
(deffield labels label (init tree))
(deffield id_label id_label (init tree))
(deffield id_labels id_label (init tree))
(deffield cstring cstring (init))
(deffield cstring_loc location (init))
(deffield word1 word (init tree))
(deffield word2 word (init tree))
(deffield strings expression (init tree))
(deffield args expression (init tree))
(deffield modifiers type_element (init tree))
(deffield qualifiers type_element (init tree))
(deffield init_expr expression (init tree))
(deffield parms declaration (init tree))
(deffield decl declaration (init tree))
(deffield decls declaration (init tree))
(deffield asm_operands1 asm_operand (init tree))
(deffield asm_operands2 asm_operand (init tree))
(deffield asm_clobbers string (init tree))
(deffield signedcst cfint (init))
(deffield unsignedcst cfuint (init))
(deffield doublecst "long double" (init))
(deffield id "enum rid" (init))
(deffield declarator declarator (init tree))
(deffield string string (init tree))
(deffield fields declaration (init tree))
(deffield defined bool (init))
(deffield parent_function function_decl (init))
(deffield env environment (init))
(deffield ddecl data_declaration (init))
(deffield ident identifier (init))
(deffield incrementrc bool (init))
(deffield old_parms declaration (init))
(deffield attributes attribute (init tree))
(deffield chars "wchar_t *" (init))
(deffield length size_t (init))
(deffield cval cval (init))
(deffield va_arg_call asttype (init))

(deffield tdecl tag_declaration ())
(deffield fdeclarator function_declarator ())
(deffield lvalue bool ())
(deffield bitfield bool ())
(deffield isregister bool ())
(deffield side_effects bool ())
(deffield cst known_cst ())
(deffield static_address known_cst ())
(deffield undeclared_variables env ())
(deffield base_labels env ())
(deffield scoped_labels env ())
(deffield ldecl label_declaration ())
(deffield parent_loop breakable_stmt ())
(deffield current_loop breakable_stmt ())
(deffield next_label label ())
(deffield nlocals int ())

(deffield declspecs type_element (init))
(deffield attributes attribute (init))
(deffield next_ds spec_stack (init))

(deffield qtype qtype ())

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Base types
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(deftype node nil (loc next)
  "The common supertype of all AST nodes")

(deftype declaration node ()
  "The common type of all definitions")

(deftype statement node ()
  "The common type of all statements
PARENT_LOOP: 
  - for break and continue: the containing for/while/do-while/switch
    statement they escape from
  - for for/while/do-while: the containing for/while/do-while/switch
    statement")

(deftype expression node (type lvalue side_effects cst bitfield isregister
			  static_address qtype)
  "Expression nodes are subtypes of this type.
LVALUE is true if this expression can be used in a context requiring an lvalue.
BITFIELD is true if this lvalue is a bitfield.
ISREGISTER is true if this lvalue is (declared to be) in a register.
SIDE_EFFECTS is true if the expression has side effects.
CST is non-null (and points to an appropriate constant) if this expression is
constant.
STATIC_ADDRESS is true for lvalues whose address is a constant expression
QTYPE is the expression's qualified type")

(deftype type_element node ()
  "A common super-type for all type-building elements (qualifiers, etc)")

(deftype declarator node ()
  "A common super-type for all declarator elements")

(deftype label node (next_label)
  "A common super-type for all labels.
NEXT_LABEL points to the next case or default label of a switch 
(for case or default labels only)")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Declarations
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defnode error_decl declaration "Placeholder for erroneous declarations")

(deftype asm_decl declaration (asm_stmt)
  "Asm statement STMT at the top level of a file (GCC)")

(deftype data_decl declaration (modifiers attributes decls)
  "The declaration MODIFIERS ATTRIBUTES DECLS;
DECLS is a list")

(deftype extension_decl declaration (decl)
  "__extension__ DECL; (GCC)")

(deftype ellipsis_decl declaration (qualifiers)
  "A pseudo-declaration to represent ... in a function argument list.  In cqual, ...'s have optional QUALIFIERS.")

(deftype enumerator declaration (cstring arg1 ddecl)
  "The enumeration element CSTRING = ARG1. CSTRING is optional")

(deftype oldidentifier_decl declaration (cstring ddecl)
  "CSTRING in an old-style parameter list")

(deftype function_decl declaration (declarator qualifiers attributes old_parms stmt
				    parent_function ddecl fdeclarator
				    declared_type undeclared_variables
				    base_labels scoped_labels current_loop
				    nlocals)
  "A function declaration with body STMT
OLD_PARMS is the old-style parameter declaration list.")

(deftype implicit_decl declaration (ident)
  "Used as the AST node for implicit declarations. IDENT points to the
identifier node that implicitly declared the function")

(deftype variable_decl declaration (declarator attributes arg1 asm_stmt
				    ddecl declared_type)
  "Declaration of ATTRIBUTES ASM_STMT DECLARATOR = ARG1.
ATTRIBUTEES is a list. ASM_STMT is optional (GCC specific).
ARG1 is an optional initialiser.
DDECL points to the declaration for this item.
DECLARED_TYPE is the type in this declaration (which may be different than that
in DDECL->TYPE).")

(deftype field_decl declaration (declarator attributes arg1)
  "Declaration of field QUALIFIERS ATTRIBUTES DECLARATOR : ARG1.
QUALIFIERS and ATTRIBUTEES are lists. ARG1 is an optional bitfield specifier")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Types and type elements
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(deftype asttype node (type declarator qualifiers)
  "The source-level type QUALIFIERS DECLARATOR")

(deftype typename type_element (ddecl)
  "typedef-type with declaration DDECL. The name is ddecl->name")

(deftype type_variable type_element (cstring)
  "type variable with name CSTRING.")

(deftype typeof_expr type_element (arg1)
  "typeof(ARG1)")

(deftype typeof_type type_element (asttype)
  "typeof(ASTTYPE)")

(deftype attribute type_element (word1 word2 args)
  "The attribute WORD1(WORD2, ARGS). word2 and args are optional")

(deftype rid type_element (id)
  "Storage class specifier, type specifier or type qualifier ID (see RID_xxx)")

(deftype user_qual type_element (cstring)
  "The user-defined type qualifier CSTRING")

(deftype qualifier type_element (id)
  "Type or function qualifier ID (see qualifiers.h and type_quals in types.h)")

(deftype tag_ref type_element (word1 attributes fields defined
			       tdecl)
  "struct/union/enum WORD1 { FIELDS; }  ATTRIBUTES
ATTRIBUTES and FIELDS are lists.
ATTRIBUTES is GCC specific. WORD1 is optional.
DEFINED is TRUE if this declaration defines the struct/union/enum.
DEFINED == FALSE => FIELDS == NULL

TDECL points to the internal declaration node for this type")
(defnode struct_ref tag_ref "A struct")
(defnode union_ref tag_ref "A union")
(defnode enum_ref tag_ref "An enum")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Declarators
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; The last DECLARATOR in a chain is:
;;   NULL_NODE in absolute declarations
;;   an identifier_decl otherwise

(deftype function_declarator declarator (declarator parms qualifiers env)
  "Function declarator DECLARATOR(PARMS). PARMS is a list of declarations.
ENV is the environment for parms")

(deftype pointer_declarator declarator (declarator qualifiers)
  "Pointer declarator *QUALIFIERS DECLARATOR")

(deftype array_declarator declarator (declarator arg1)
  "Array declarator DECLARATOR[ARG1]. ARG1 is optional")

(deftype identifier_declarator declarator (cstring)
  "Declaration of CSTRING")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Statements
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defnode error_stmt statement "Placeholder for erroneous statements")

(deftype asm_stmt statement (arg1 asm_operands1 asm_operands2 asm_clobbers qualifiers)
  "The statement asm QUALIFIERS (ARG1 : ASM_OPERANDS1 : ASM_OPERANDS2 : ASM_CLOBBERS) 
where ASM_OPERANDS1, ASM_OPERANDS2, QUALIFIERS are optional, ASM_CLOBBERS is a list (GCC)")

(deftype compound_stmt statement (id_labels decls stmts env)
  "{ ID_LABELS DECLS STMTS }. The ID_LABELS are GCC-specific. ID_LABELS, DECLS,
STMTS are lists
ENV is the environment for the block")

(deftype if_stmt statement (condition stmt1 stmt2)
  "IF (CONDITION) STMT1 ELSE STMT2. STMT2 is optional")

(deftype labeled_stmt statement (label stmt)
  "LABEL: STMT")

(deftype expression_stmt statement (arg1)
  "EXPR;")

(deftype breakable_stmt statement (parent_loop)
  "Basic type for all statements that can have break in them")

(deftype conditional_stmt breakable_stmt (condition stmt)
  "Basic type for all conditional statements")
(defnode while_stmt conditional_stmt "WHILE (CONDITION) STMT")
(defnode dowhile_stmt conditional_stmt "DO STMT WHILE (CONDITION")
(deftype switch_stmt conditional_stmt (next_label) 
  "SWITCH (CONDITION) STMT.
NEXT_LABEL points to the switches first label")

(deftype for_stmt breakable_stmt (arg1 arg2 arg3 stmt)
  "FOR (ARG1; ARG2; ARG3) STMT. ARG1, ARG2, ARG3 are optional")

(deftype break_stmt statement (parent_loop)
  "BREAK.  PARENT_LOOP is the enclosing loop or switch")

(deftype continue_stmt statement (parent_loop)
  "CONTINUE;  PARENT_LOOP is the enclosing loop or switch")

(deftype return_stmt statement (arg1)
  "RETURN ARG1. ARG1 is optional")

(deftype goto_stmt statement (id_label)
  "GOTO ID_LABEL")

(deftype computed_goto_stmt statement (arg1)
  "GOTO *ARG1 (GCC)")

(deftype empty_stmt statement ()
  ";")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Expressions
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defnode error_expr expression "Placeholder for erroneous expressions")

(deftype unary expression (arg1)
  "Unary expression nodes, kind defines operator")

(deftype binary expression (arg1 arg2)
  "Binary expression nodes, kind defines operator")

(deftype comma expression (arg1)
  "A comma separated list of expressions ARG1")

(deftype sizeof_type expression (asttype)
  "sizeof (ASTTYPE)")

(deftype alignof_type expression (asttype)
  "__alignof (ASTTYPE) (GCC)")

(deftype label_address expression (id_label)
  "&&ID_LABEL (GCC)")

(deftype cast unary (asttype)
  "(ASTTYPE)ARG1")

(deftype cast_list expression (asttype init_expr)
  "(ASTTYPE){INIT_EXPR} (GCC)")

(deftype conditional expression (condition arg1 arg2)
  "CONDITION ? ARG1 : ARG2
   GCC specific: ARG1 is optional")

(deftype identifier expression (cstring ddecl)
  "The identrifier CSTRING")

(deftype compound_expr expression (stmt)
  "({stmt}) (GCC)")

(deftype function_call expression (arg1 args va_arg_call)
  "ARG1(ARGS). ARGS is a list of expressions
If VA_ARG_CALL is non-null, this is actually a call to the pseudo-function
__builtin_va_arg(args, va_arg_call) (where va_arg_call is a type). In 
this case arg1 is a dummy identifier.")

(deftype array_ref binary ()
  "ARG1[ARG2].")

(deftype field_ref unary (cstring cstring_loc)
  "ARG1.CSTRING.  CSTRING_LOC is the location of CSTRING.")

(defnode dereference unary "*ARG1")
(defnode extension_expr unary "__extension__ ARG1 (GCC)")
(defnode sizeof_expr unary "sizeof ARG1")
(defnode alignof_expr unary "__alignof ARG1 (GCC)")
(defnode realpart unary "__real ARG1 (GCC)")
(defnode imagpart unary "__imag ARG1 (GCC)")
(defnode address_of unary "&ARG1")
(defnode unary_minus unary "-ARG1")
(defnode unary_plus unary "+ARG1")
(defnode conjugate unary "~ARG1 on complex arguments")
(defnode preincrement unary "++ARG1")
(defnode predecrement unary "--ARG1")
(defnode postincrement unary "ARG1++")
(defnode postdecrement unary "ARG1--")
(defnode bitnot unary "~ARG1")
(defnode not unary "!ARG1")

(defnode plus binary "ARG1 + ARG2")
(defnode minus binary "ARG1 - ARG2")
(defnode times binary "ARG1 * ARG2")
(defnode divide binary "ARG1 / ARG2")
(defnode modulo binary "ARG1 % ARG2")
(defnode lshift binary "ARG1 << ARG2")
(defnode rshift binary "ARG1 >> ARG2")
(defnode leq binary "ARG1 <= ARG2")
(defnode geq binary "ARG1 >= ARG2")
(defnode lt binary "ARG1 < ARG2")
(defnode gt binary "ARG1 > ARG2")
(defnode eq binary "ARG1 == ARG2")
(defnode ne binary "ARG1 != ARG2")
(defnode bitand binary "ARG1 & ARG2")
(defnode bitor binary "ARG1 | ARG2")
(defnode bitxor binary "ARG1 ^ ARG2")
(defnode andand binary "ARG1 && ARG2")
(defnode oror binary "ARG1 || ARG2")
(defnode assign binary "ARG1 = ARG2")
(defnode plus_assign binary "ARG1 += ARG2")
(defnode minus_assign binary "ARG1 -= ARG2")
(defnode times_assign binary "ARG1 *= ARG2")
(defnode divide_assign binary "ARG1 /= ARG2")
(defnode modulo_assign binary "ARG1 %= ARG2")
(defnode lshift_assign binary "ARG1 <<= ARG2")
(defnode rshift_assign binary "ARG1 >>= ARG2")
(defnode bitand_assign binary "ARG1 &= ARG2")
(defnode bitor_assign binary "ARG1 |= ARG2")
(defnode bitxor_assign binary "ARG1 ^= ARG2")

;; Initialiser expressions (not allowed in most contexts)

(deftype init_list expression (args)
  "{ ARGS }. ARGS is a list of expressions")

(deftype init_index expression (arg1 arg2 init_expr)
  "[ ARG1 ... ARG2] INIT_EXPR (GCC). ARG2 is optional")

(deftype init_field expression (word1 init_expr)
  "WORD1 : INIT_EXPR (GCC)")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Constants
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(deftype known_cst expression (cval)
  "A constant representable in CVAL. These do not appear as part of the
AST (they show up in the cst and static_address fields of expressions).")

(deftype lexical_cst expression (cstring)
  "A constant represented as in its unparsed lexical form CSTRING. These
appear in the AST.")

(deftype string_cst lexical_cst (chars length)
  "A single lexical string whose LENGTH characters are CHARS. The source
form of the constant can be found in CSTRING.")

(deftype string expression (strings ddecl)
  "A list of STRINGS forming a single string constant.
DDECL is the magic_string declaration for this string.")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Labels
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(deftype id_label label (cstring ldecl)
  "The label CSTRING:")

(deftype case_label label (arg1 arg2)
  "CASE ARG1 ... ARG2: ARG2 is optional, it's presence is GCC-specific")

(deftype default_label label ()
  "DEFAULT:")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Miscellaneous
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(deftype word node (cstring)
  "The identifier CSTRING used uninterpreted")

(deftype asm_operand node (string arg1)
  "STRING(EXPR) (GCC)")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Internal use
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
