path: root/ast.h

/* Oort
 * Copyright 2007, Soren Sandmann Pedersen
 *
 * This program 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 of the License, or
 * (at your option) any later version.
 *
 * This program 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 this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include <glib.h>

typedef union  token_t token_t;
typedef struct token_common_t token_common_t;
typedef struct token_identifier_t token_identifier_t;
typedef struct token_int_literal_t token_int_literal_t;
typedef struct token_float_literal_t token_float_literal_t;
typedef struct token_string_literal_t token_string_literal_t;

typedef struct ast_common_t ast_common_t;

typedef struct ast_definition_common_t ast_definition_common_t;
typedef struct ast_function_definition_t ast_function_definition_t;
typedef struct ast_class_definition_t ast_class_definition_t;
typedef struct ast_type_definition_t ast_type_definition_t;
typedef struct ast_variable_definition_t ast_variable_definition_t;
typedef struct ast_label_definition_t ast_label_definition_t;

typedef struct ast_case_common_t ast_case_common_t;
typedef struct ast_expression_case_t ast_expression_case_t;
typedef union  ast_case_t ast_case_t;

typedef struct ast_statement_common_t ast_statement_common_t;
typedef struct ast_definition_statement_t ast_definition_statement_t;
typedef struct ast_print_statement_t ast_print_statement_t;
typedef struct ast_loop_statement_t ast_loop_statement_t;
typedef struct ast_if_statement_t ast_if_statement_t;
typedef struct ast_switch_statement_t ast_switch_statement_t;
typedef struct ast_expression_statement_t ast_expression_statement_t;
typedef struct ast_block_statement_t ast_block_statement_t;
typedef struct ast_compound_statement_t ast_compound_statement_t;
typedef struct ast_goto_statement_t ast_goto_statement_t;
typedef struct ast_break_statement_t ast_break_statement_t;
typedef struct ast_continue_statement_t ast_continue_statement_t;
typedef struct ast_label_statement_t ast_label_statement_t;
typedef struct ast_return_statement_t ast_return_statement_t;

typedef struct ast_expression_common_t ast_expression_common_t;
typedef struct ast_dot_expression_t ast_dot_expression_t;
typedef struct ast_this_expression_t ast_this_expression_t;
typedef struct ast_index_expression_t ast_index_expression_t;
typedef struct ast_int_literal_expression_t ast_int_literal_expression_t;
typedef struct ast_float_literal_expression_t ast_float_literal_expression_t;
typedef struct ast_string_literal_expression_t ast_string_literal_expression_t;
typedef struct ast_bool_literal_expression_t ast_bool_literal_expression_t;
typedef struct ast_null_expression_t ast_null_expression_t;
typedef struct ast_identifier_expression_t ast_identifier_expression_t;
typedef struct ast_unary_expression_t ast_unary_expression_t;
typedef struct ast_binary_expression_t ast_binary_expression_t;
typedef struct ast_ternary_expression_t ast_ternary_expression_t;
typedef struct ast_lambda_expression_t ast_lambda_expression_t;
typedef struct ast_call_expression_t ast_call_expression_t;
typedef struct ast_statement_expression_t ast_statement_expression_t;
typedef struct ast_new_expression_t ast_new_expression_t;
typedef struct ast_block_expression_t ast_block_expression_t;
typedef struct ast_definition_expression_t ast_definition_expression_t;

typedef struct ast_type_spec_common_t ast_type_spec_common_t;
typedef struct ast_identifier_type_spec_t ast_identifier_type_spec_t;
typedef struct ast_function_type_spec_t ast_function_type_spec_t;
typedef struct ast_array_type_spec_t ast_array_type_spec_t;
typedef struct ast_object_type_spec_t ast_object_type_spec_t;
typedef struct ast_inferred_type_spec_t ast_inferred_type_spec_t;

typedef struct ast_program_t ast_program_t;

typedef union  ast_definition_t ast_definition_t;
typedef union  ast_type_spec_t ast_type_spec_t;
typedef union  ast_expression_t ast_expression_t;
typedef union  ast_statement_t ast_statement_t;
typedef union  ast_t ast_t;

typedef struct symbol_table_t symbol_table_t;

typedef union  value_t value_t;
typedef struct closure_t closure_t;
typedef struct label_t label_t;

typedef struct node_common_t node_common_t;
typedef struct prolog_node_t prolog_node_t;
typedef struct fun_ref_node_t fun_ref_node_t;
typedef struct goto_node_t goto_node_t;
typedef struct if_node_t if_node_t;
typedef struct return_node_t return_node_t;
typedef struct label_node_t label_node_t;
typedef struct dyn_closure_node_t dyn_closure_node_t;
typedef struct dyn_label_t dyn_label_t;
typedef struct store_node_t store_node_t;
typedef struct store_ind_node_t store_ind_node_t;
typedef struct store_array_node_t store_array_node_t;
typedef struct load_node_t load_node_t;
typedef struct load_ind_node_t load_ind_node_t;
typedef struct load_array_node_t load_array_node_t;
typedef struct initialize_node_t initialize_node_t;
typedef struct literal_node_t literal_node_t;
typedef struct print_node_t print_node_t;
typedef struct closure_node_t closure_node_t;
typedef struct binop_node_t binop_node_t;
typedef struct unary_node_t unary_node_t;
typedef struct call_node_t call_node_t;
typedef struct new_node_t new_node_t;
typedef struct new_array_node_t new_array_node_t;
typedef struct this_node_t this_node_t;
typedef struct to_string_node_t to_string_node_t;
typedef union  node_t node_t;

typedef struct set_t set_t;

typedef enum
{
    AST_DEFINITION,
    AST_CASE,
    AST_STATEMENT,
    AST_EXPRESSION,
    AST_TYPE_SPEC,
    AST_PROGRAM
} ast_type_t;

typedef enum
{
    AST_INT32_TYPE,
    AST_DOUBLE_TYPE,
    AST_BOOL_TYPE,
    AST_NULL_TYPE,
    AST_VOID_TYPE,
    AST_IDENTIFIER_TYPE,
    AST_FUNCTION_TYPE,
    AST_ARRAY_TYPE,
    AST_OBJECT_TYPE,
    AST_STRING_TYPE,
    AST_INFERRED_TYPE,
    AST_LABEL_TYPE
} ast_type_spec_type_t;

typedef enum
{
    AST_FUNCTION_DEFINITION,
    AST_CLASS_DEFINITION,
    AST_VARIABLE_DEFINITION,
    AST_LABEL_DEFINITION,
    AST_TYPE_DEFINITION
} ast_definition_type_t;

typedef enum
{
    /* Statements */
    AST_DEFINITION_STATEMENT,
    AST_PRINT_STATEMENT,
    AST_LOOP_STATEMENT,
    AST_IF_STATEMENT,
    AST_SWITCH_STATEMENT,
    AST_EXPRESSION_STATEMENT,
    AST_COMPOUND_STATEMENT,
    AST_BLOCK_STATEMENT,
    AST_RETURN_STATEMENT,
    AST_GOTO_STATEMENT,
    AST_BREAK_STATEMENT,
    AST_CONTINUE_STATEMENT,
    AST_LABEL_STATEMENT,
    AST_EMPTY_STATEMENT
} ast_statement_type_t;

typedef enum
{
    /* Cases */
    AST_EXPRESSION_CASE,
    AST_DEFAULT_CASE
} ast_case_type_t;

typedef enum
{
    /* Expressions */
    AST_INT_LITERAL_EXPRESSION,
    AST_FLOAT_LITERAL_EXPRESSION,
    AST_STRING_LITERAL_EXPRESSION,
    AST_BOOL_LITERAL_EXPRESSION,
    AST_NULL_EXPRESSION,
    AST_IDENTIFIER_EXPRESSION,
    AST_UNARY_EXPRESSION,
    AST_BINARY_EXPRESSION,
    AST_TERNARY_EXPRESSION,
    AST_LAMBDA_EXPRESSION,
    AST_CALL_EXPRESSION,
    AST_STATEMENT_EXPRESSION,
    AST_NEW_EXPRESSION,
    AST_BLOCK_EXPRESSION,
    AST_DEFINITION_EXPRESSION,
    AST_DOT_EXPRESSION,
    AST_THIS_EXPRESSION,
    AST_INDEX_EXPRESSION,
    AST_VOID_EXPRESSION
} ast_expression_type_t;

typedef enum
{
    AST_ASSIGN,
    AST_PLUS,
    AST_MINUS,
    AST_DIVIDE,
    AST_TIMES,
    AST_MOD,
    AST_LSHIFT,
    AST_RSHIFT,
    AST_LT,
    AST_GT,
    AST_LTE,
    AST_GTE,
    AST_EQUAL,
    AST_NOT_EQUAL,
    AST_OR,
    AST_AND,
    AST_BOR,
    AST_BXOR,
    AST_BAND,
} ast_binary_operator_t;

typedef enum
{
    AST_UNARY_NOT,
    AST_UNARY_MINUS,
    AST_UNARY_PLUS,
    AST_UNARY_BNEG,
    AST_POSTFIX_INC,
    AST_POSTFIX_DEC,
    AST_PREFIX_INC,
    AST_PREFIX_DEC,
} ast_unary_operator_t;

char *   unique_name (const char *prefix);
int      array_length (gpointer *arr);
gboolean report_error (const char *fmt, ...);

/* Set utilities */

set_t *   set_new           (void);
set_t *   set_new_full      (void);
set_t *   set_copy          (set_t *s);
void	  set_free          (set_t *s);
void      set_intersect     (set_t *s1, set_t *s2);
gboolean  set_equal         (set_t *s1, set_t *s2);
void      set_union         (set_t *s1, set_t *s2);
void      set_add           (set_t *s, gpointer element);
gboolean  set_contains      (set_t *s, gpointer element);

/* Symbol Table */
struct symbol_table_t
{
    symbol_table_t *	outer;
    GHashTable *        symbols;
};

/* Evaluate operators */
void	  evaluate_binary_operator (ast_binary_operator_t	 op,
				    const ast_type_spec_t	*left_type,
				    const value_t		*left,
				    const ast_type_spec_t	*right_type,
				    const value_t		*right,
				    const ast_type_spec_t	*result_type,
				    value_t			*result);
void      evaluate_unary_operator  (ast_unary_operator_t	 op,
				    const ast_type_spec_t	*child_type,
				    const value_t		*child,
				    const ast_type_spec_t	*result_type,
				    value_t			*result);
gchar *   value_to_string          (value_t			*val,
				    ast_type_spec_t		*type);
void      print_value              (value_t			*val,
				    ast_type_spec_t		*type_spec);

/* Interpreter */
struct closure_t
{
    ast_function_definition_t *		function;
    gpointer				env;
};

struct label_t
{
    label_node_t *			label;
    gpointer				env;
};

union value_t
{
    int		int32_val;
    double	double_val;
    gboolean	bool_val;
    closure_t	closure_val;
    gpointer    pointer_val;
    label_t	label_val;
};

/* Graph Utilities */
typedef enum
{
    NODE_GOTO,
    NODE_DYN_GOTO,
    NODE_IF,
    NODE_BINOP,
    NODE_UNARY,
    NODE_LITERAL,
    NODE_PRINT,
    NODE_TO_STRING,
    NODE_POP,
    NODE_DUP,
    NODE_RETURN,
    NODE_NOP,
    NODE_INIT,
    NODE_LABEL,
    NODE_CALL,
    NODE_NEW,
    NODE_NEW_ARRAY,
    NODE_THIS,
    NODE_FUN_REF,
    NODE_PROLOG,
    NODE_LOAD,		/* These three byte codes could probably be replaced
			 * with a "load env" bytecode plus the indirect byte
			 * codes.
			 */
    NODE_STORE,
    NODE_CLOSURE,
    NODE_DYN_CLOSURE,	/* Closure, where the environment is on the stack */
    NODE_LOAD_IND,	/* Load, where the env is on the stack */
    NODE_STORE_IND,	/* Store, where the env is on the stack */
    NODE_DYN_LABEL,
    NODE_LOAD_ARRAY,
    NODE_STORE_ARRAY
} node_type_t;

struct node_common_t
{
    node_type_t			type;

    ast_t *			ast;

    node_t *			next;
    node_t *			prev;

    gboolean			reachable;
    set_t *			init_vars;
};

struct prolog_node_t
{
    node_common_t		common;

    GQueue *			sources;
};

struct fun_ref_node_t
{
    node_common_t		common;

    prolog_node_t *		prolog;
};

struct label_ref_node_t
{
    node_common_t		common;

    label_node_t *		label;
};

struct label_node_t
{
    node_common_t		common;

    GQueue *			sources;
};

struct goto_node_t
{
    node_common_t		common;

    label_node_t *		label;
};

struct return_node_t
{
    node_common_t		common;

    ast_type_spec_t *		type;

    label_node_t *		exit;
};

struct if_node_t
{
    node_common_t		common;

    gboolean			sense;
    label_node_t *		taken;
};

struct store_node_t
{
    node_common_t		common;

    ast_variable_definition_t * definition;
    ast_expression_t *		expression;
};

struct store_ind_node_t
{
    node_common_t		common;

    ast_variable_definition_t * definition;
};

struct store_array_node_t
{
    node_common_t		common;

    ast_array_type_spec_t *	array;
};

struct load_ind_node_t
{
    node_common_t		common;

    ast_variable_definition_t * definition;
};

struct load_node_t
{
    node_common_t		common;

    ast_variable_definition_t * definition;
    ast_expression_t *		expression;
};

struct load_array_node_t
{
    node_common_t		common;

    ast_array_type_spec_t *	array;
};

struct initialize_node_t
{
    node_common_t		common;

    ast_variable_definition_t * definition;
};

struct binop_node_t
{
    node_common_t		common;

    ast_type_spec_t *		left_type;
    ast_type_spec_t *		right_type;
    ast_type_spec_t *		type_spec;

    ast_binary_operator_t	operator;
};

struct unary_node_t
{
    node_common_t		common;

    ast_unary_operator_t	operator;

    ast_type_spec_t *		child_type;
    ast_type_spec_t *		type_spec;
};

struct literal_node_t
{
    node_common_t		common;

    value_t			value;
    ast_type_spec_t *		type_spec;
};

struct closure_node_t
{
    node_common_t		common;

    ast_function_definition_t *	function;
    ast_expression_t *		expression;
};

struct dyn_label_t
{
    node_common_t		common;

    label_node_t *		label;
    ast_expression_t *		expression;
    ast_label_definition_t *	definition;
};

struct dyn_closure_node_t
{
    node_common_t		common;

    ast_function_definition_t *	function;
};

struct new_node_t
{
    node_common_t		common;

    ast_class_definition_t *	class;
    ast_expression_t *		expression;
};

struct new_array_node_t
{
    node_common_t		common;

    ast_array_type_spec_t *	array;
    int				element_size;
};

struct this_node_t
{
    node_common_t		common;

    ast_class_definition_t *	class;
    ast_expression_t *		expression;
};

struct to_string_node_t
{
    node_common_t		common;

    ast_type_spec_t *		type_spec;
};

struct print_node_t
{
    node_common_t		common;

    int				n_exprs;
};

struct call_node_t
{
    node_common_t		common;
};

union node_t
{
    node_common_t		common;
    goto_node_t			goto_;
    return_node_t		return_;
    if_node_t			if_;
    label_node_t		label;
    store_node_t		store;
    store_ind_node_t		store_ind;	/* [ ..., value, obj ] => [] */
    store_array_node_t		store_array;	/* [ ..., value, array, index ] => [] */
    load_node_t			load;
    load_ind_node_t		load_ind;
    load_array_node_t		load_array;
    initialize_node_t		initialize;
    binop_node_t		binop;
    unary_node_t		unary;
    literal_node_t		literal;
    closure_node_t		closure;
    print_node_t		print;
    new_node_t			new;
    new_array_node_t		new_array;
    this_node_t			this;
    to_string_node_t		to_string;
    dyn_closure_node_t		dyn_closure;
    prolog_node_t		prolog;
    fun_ref_node_t		fun_ref;
    dyn_label_t			dyn_label;
};

node_t *node_new_fun_ref     (node_t                    *prolog,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_prolog      (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_label       (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_goto        (label_node_t              *label,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_dyn_goto    (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_return      (ast_type_spec_t           *type,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_if          (gboolean                   sense,
			      label_node_t              *taken,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_literal     (value_t                    value,
			      ast_type_spec_t           *type,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_closure     (ast_function_definition_t *function,
			      ast_expression_t          *expr,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_dyn_label   (label_node_t              *label,
			      ast_expression_t          *expr,
			      ast_label_definition_t    *definition,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_dyn_closure (ast_function_definition_t *function,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_print       (int			 n_exprs,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_to_string   (ast_type_spec_t		*type_spec,
			      node_t			*pred,
			      ast_t			*ast);
node_t *node_new_call        (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_pop         (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_dup         (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_nop         (node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_load        (ast_variable_definition_t *def,
			      ast_expression_t          *expr,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_load_ind    (ast_variable_definition_t *def,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_load_array  (ast_array_type_spec_t     *array,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_store       (ast_variable_definition_t *def,
			      ast_expression_t          *expr,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_store_ind   (ast_variable_definition_t *def,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_store_array (ast_array_type_spec_t     *array,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_initialize  (ast_variable_definition_t *def,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_binop       (ast_binary_operator_t      operator,
			      ast_type_spec_t           *left_type,
			      ast_type_spec_t           *right_type,
			      ast_type_spec_t           *type,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_unary       (ast_unary_operator_t       operator,
			      ast_type_spec_t           *child_type,
			      ast_type_spec_t           *type,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_new         (ast_class_definition_t    *class,
			      ast_expression_t          *expr,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_new_array   (ast_array_type_spec_t     *array,
			      int                        element_size,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_new_this        (ast_class_definition_t    *class,
			      ast_expression_t          *expr,
			      node_t                    *pred,
			      ast_t                     *ast);
node_t *node_insert_after    (node_t			*node,
			      node_t			*pred);
void    node_free	     (node_t                    *node);

typedef void (* node_callback_t) (node_t *node, gpointer data);

GList *node_list_predecessors (node_t *node);
GList *node_list_successors   (node_t *node);

void     node_breadth_first (node_t *        start,
			     node_callback_t callback,
			     gpointer        data);
node_t **node_list_all      (node_t *        entry);

/*
 * Scanner
 */

typedef enum
{
    TOKEN_WHILE,
    TOKEN_LBRACE,
    TOKEN_RBRACE,
    TOKEN_ASSIGN,
    TOKEN_SEMICOLON,
    TOKEN_IDENTIFIER,
    TOKEN_LPAREN,
    TOKEN_RPAREN,
    TOKEN_DOT,
    TOKEN_DOT_DOT,
    TOKEN_COMMA,
    TOKEN_FOR,
    TOKEN_GOTO,
    TOKEN_BREAK,
    TOKEN_CONTINUE,
    TOKEN_CLASS,
    TOKEN_THIS,
    TOKEN_VIRTUAL,
    TOKEN_MATCH,
    TOKEN_INT_LITERAL,
    TOKEN_STRING_LITERAL,
    TOKEN_FLOAT_LITERAL,
    TOKEN_STRUCT,
    TOKEN_NEW,
    TOKEN_PLUS,
    TOKEN_PRINT,
    TOKEN_WHITESPACE,
    TOKEN_LSHIFT,
    TOKEN_RSHIFT,
    TOKEN_LBRACK,
    TOKEN_RBRACK,
    TOKEN_COLON,
    TOKEN_TIMES,
    TOKEN_MINUS,
    TOKEN_DIVIDE,
    TOKEN_IF,
    TOKEN_ELSE,
    TOKEN_RETURN,
    TOKEN_AND,
    TOKEN_OR,
    TOKEN_XOR,
    TOKEN_BAND,
    TOKEN_BOR,
    TOKEN_BXOR,
    TOKEN_BNEG,
    TOKEN_NULL,
    TOKEN_ENUM,
    TOKEN_GT,
    TOKEN_LT,
    TOKEN_GTE,
    TOKEN_LTE,
    TOKEN_NOT_EQ,
    TOKEN_EQ,
    TOKEN_CONST,
    TOKEN_INT64,
    TOKEN_UINT64,
    TOKEN_INT32,
    TOKEN_UINT32,
    TOKEN_INT16,
    TOKEN_UINT16,
    TOKEN_UINT8,
    TOKEN_INT8,
    TOKEN_BOOL,
    TOKEN_STRING,
    TOKEN_INC,
    TOKEN_DEC,
    TOKEN_NOT,
    TOKEN_MOD,
    TOKEN_QUESTION,
    TOKEN_PLUS_EQ,
    TOKEN_MINUS_EQ,
    TOKEN_TIMES_EQ,
    TOKEN_MOD_EQ,
    TOKEN_DIVIDE_EQ,
    TOKEN_RSHIFT_EQ,
    TOKEN_LSHIFT_EQ,
    TOKEN_BAND_EQ,
    TOKEN_BOR_EQ,
    TOKEN_BXOR_EQ,
    TOKEN_TRUE,
    TOKEN_FALSE,
    TOKEN_THROW,
    TOKEN_TRY,
    TOKEN_CATCH,
    TOKEN_FINALLY,
    TOKEN_TYPEDEF,
    TOKEN_DOUBLE,
    TOKEN_FLOAT,
    TOKEN_DO,
    TOKEN_RARROW,
    TOKEN_LARROW,
    TOKEN_SWITCH,
    TOKEN_CASE,
    TOKEN_DEFAULT,
    TOKEN_WITH,
    TOKEN_FN,
    TOKEN_AS,
    TOKEN_IS,
    TOKEN_VAR,
    TOKEN_VOID,
    TOKEN_IN,
    TOKEN_AT,
    TOKEN_OPERATOR,
    TOKEN_PUBLIC,
    TOKEN_PRIVATE,
    TOKEN_OVERRIDE,
    TOKEN_ARRAY,
    TOKEN_YIELD,
    TOKEN_LABEL,
    TOKEN_END_OF_FILE
} token_type_t;

struct token_common_t
{
    token_type_t	type;
    char *		string;
    int			line;
    int			begin_pos;
    int			end_pos;

    /* Used by the parser */
    gboolean		err;
};

struct token_identifier_t
{
    token_common_t	common;
    char *		name;
};

struct token_int_literal_t
{
    token_common_t	common;
    int			value;
};

struct token_float_literal_t
{
    token_common_t	common;
    double		value;
};

struct token_string_literal_t
{
    token_common_t	common;
    char *		value;
};

union token_t
{
    token_type_t		type;
    token_common_t		common;
    token_identifier_t		identifier;
    token_string_literal_t	string_literal;
    token_int_literal_t		int_literal;
    token_float_literal_t	float_literal;
};

/*
 * Parser
 */
struct ast_common_t
{
    ast_type_t				type;
    ast_t *				parent;
    GQueue *				children;

    GQueue *				predecessors;
    GQueue *				successors;

    gsize				magic;
};

/*
 * Defs
 */
struct ast_definition_common_t
{
    ast_common_t			common;
    ast_definition_type_t		type;
};

struct ast_function_definition_t
{
    ast_definition_common_t		common;

    char *				name;
    ast_variable_definition_t **	parameters;
    ast_type_spec_t *			return_type;
    ast_statement_t *			body;

    symbol_table_t *			symbol_table;
    ast_type_spec_t *			type_spec;

    int					level;
    int					env_size;

    node_t *				enter;
    node_t *				exit;
    node_t *				end;
};

struct ast_class_definition_t
{
    ast_definition_common_t		common;

    char *				name;
    ast_statement_t *			statement;

    ast_type_spec_t *			type_spec;

    int					level;
    int					env_size;

    symbol_table_t *			symbol_table;
};

struct ast_type_definition_t
{
    ast_definition_common_t		common;

    char *				name;
    ast_type_spec_t *			type_spec;
};

struct ast_variable_definition_t
{
    ast_definition_common_t		common;

    char *				name;
    ast_type_spec_t *			type_spec;
    int					offset;
    int					level;

    gboolean				field;
    gboolean				parameter;
    gboolean				used;
};

struct ast_label_definition_t
{
    ast_definition_common_t		common;

    char *				name;
    ast_label_statement_t *		statement;
    int					level;
};

/* Statements */
struct ast_statement_common_t
{
    ast_common_t			common;
    ast_statement_type_t		type;
};

struct ast_definition_statement_t
{
    ast_statement_common_t		common;

    ast_definition_t *			def;
};

struct ast_print_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t **			exprs;
};

struct ast_loop_statement_t
{
    ast_statement_common_t		common;

    ast_statement_t *			init;
    ast_expression_t *			condition;
    ast_statement_t *			increment;
    ast_statement_t *			body;

    node_t *				start_node;
    node_t *				cont_node;
    node_t *				test_node;
    node_t *				done_node;
};

struct ast_if_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t *			condition;
    ast_statement_t *			then_part;
    ast_statement_t *			else_part;

    node_t *				then_node;
    node_t *				else_node;
    node_t *				done_node;
};

struct ast_expression_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t *			expr;
};

struct ast_compound_statement_t
{
    ast_statement_common_t		common;

    ast_statement_t *			first;
    ast_statement_t *			second;
};

struct ast_block_statement_t
{
    ast_statement_common_t		common;

    ast_statement_t *			body;
    symbol_table_t *			symbol_table;
};

struct ast_goto_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t *			target;
};

struct ast_label_statement_t
{
    ast_statement_common_t		common;

    const char *			label;

    node_t *				node;

    ast_definition_t *			definition;
};

struct ast_return_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t *			expr;
};

struct ast_switch_statement_t
{
    ast_statement_common_t		common;

    ast_expression_t *			condition;
    ast_case_t **			cases;

    node_t *				done_node;
};

/* Cases */
struct ast_case_common_t
{
    ast_common_t			common;
    ast_case_type_t			type;
    ast_statement_t *			statement;

    node_t *				label_node;
};

struct ast_expression_case_t
{
    ast_case_common_t			common;

    ast_expression_t *			expr;
};

union ast_case_t
{
    ast_case_common_t			common;
    ast_expression_case_t		expression;
};

/* Expressions */
struct ast_expression_common_t
{
    ast_common_t			common;

    gboolean				constant;
    value_t				constant_value;

    ast_expression_type_t		type;

    ast_type_spec_t *			type_spec;
    int					level;

    ast_variable_definition_t *		type_inferrer; /* Variable */
};

struct ast_int_literal_expression_t
{
    ast_expression_common_t		common;

    int					value;
};

struct ast_float_literal_expression_t
{
    ast_expression_common_t		common;

    double				value;
};

struct ast_bool_literal_expression_t
{
    ast_expression_common_t		common;

    gboolean				value;
};

struct ast_string_literal_expression_t
{
    ast_expression_common_t		common;

    char *				value;
};

struct ast_null_expression_t
{
    ast_expression_common_t		common;
};

struct ast_identifier_expression_t
{
    ast_expression_common_t		common;

    char *				name;

    ast_definition_t *			definition;
};

struct ast_binary_expression_t
{
    ast_expression_common_t		common;
    ast_binary_operator_t		operator;

    ast_expression_t *			left;
    ast_expression_t *			right;
};

struct ast_ternary_expression_t
{
    ast_expression_common_t		common;

    ast_expression_t *			cond;
    ast_expression_t *			then_expr;
    ast_expression_t *			else_expr;

    node_t *				then;
    node_t *				else_;
    node_t *				done;
};

struct ast_lambda_expression_t
{
    ast_expression_common_t		common;

    ast_function_definition_t *		function;
};

struct ast_call_expression_t
{
    ast_expression_common_t		common;

    ast_expression_t *			callee;
    ast_expression_t **			args;
};

struct ast_unary_expression_t
{
    ast_expression_common_t		common;
    ast_unary_operator_t		operator;

    ast_expression_t *			expr;
};

struct ast_statement_expression_t
{
    ast_expression_common_t		common;

    ast_statement_t *			statement;
    ast_expression_t *			expression;
};

struct ast_index_expression_t
{
    ast_expression_common_t		common;

    ast_expression_t *			left;
    ast_expression_t *			right;
};

struct ast_new_expression_t
{
    ast_expression_common_t		common;

    ast_type_spec_t *			type;
    ast_expression_t **			args;

    ast_definition_t *			definition;
};

struct ast_block_expression_t
{
    ast_expression_common_t		common;

    ast_expression_t *			body;

    symbol_table_t *			symbol_table;
};

struct ast_definition_expression_t
{
    ast_expression_common_t		common;

    ast_definition_t *			definition;
    ast_expression_t *			initializer;
};

struct ast_dot_expression_t
{
    ast_expression_common_t		common;

    ast_expression_t *			left;
    const char *			name;

    ast_definition_t *			definition;
};

/* Type spec */
struct ast_type_spec_common_t
{
    ast_common_t			common;
    ast_type_spec_type_t		type;
};

struct ast_identifier_type_spec_t
{
    ast_type_spec_common_t		common;

    const char *			name;

    ast_definition_t *			definition;
};

struct ast_function_type_spec_t
{
    ast_type_spec_common_t		common;

    ast_type_spec_t *			return_;
    ast_type_spec_t **			args;
};

struct ast_array_type_spec_t
{
    ast_type_spec_common_t		common;

    ast_type_spec_t *			child_type;
};

struct ast_object_type_spec_t
{
    ast_type_spec_common_t		common;

    ast_class_definition_t *		class;
};

/* Program */
struct ast_program_t
{
    ast_common_t			common;

    ast_function_definition_t **	functions;

    ast_statement_t *			statement;
    int					env_size;

    symbol_table_t *			symbol_table;

    node_t *				enter;

    void *				tmp;
};

/* Unions */
union ast_expression_t
{
    ast_expression_common_t		common;
    ast_int_literal_expression_t	int_literal;
    ast_float_literal_expression_t	float_literal;
    ast_bool_literal_expression_t	bool_literal;
    ast_string_literal_expression_t	string_literal;
    ast_null_expression_t		null;
    ast_identifier_expression_t		identifier;
    ast_unary_expression_t		unary;
    ast_binary_expression_t		binary;
    ast_ternary_expression_t		ternary;
    ast_call_expression_t		call;
    ast_lambda_expression_t		lambda;
    ast_statement_expression_t		statement;
    ast_index_expression_t		index;
    ast_new_expression_t		new;
    ast_block_expression_t		block;
    ast_definition_expression_t		definition;
    ast_dot_expression_t		dot;
};

union ast_definition_t
{
    ast_definition_common_t		common;
    ast_function_definition_t		function;
    ast_class_definition_t		class;
    ast_variable_definition_t		variable;
    ast_type_definition_t		type;
    ast_label_definition_t		label;
};

union ast_statement_t
{
    ast_statement_common_t		common;
    ast_definition_statement_t		definition;
    ast_print_statement_t		print;
    ast_loop_statement_t		loop;
    ast_if_statement_t			if_;
    ast_switch_statement_t		switch_;
    ast_expression_statement_t		expression;
    ast_compound_statement_t		compound;
    ast_block_statement_t		block;
    ast_goto_statement_t		goto_;
    ast_label_statement_t		label;
    ast_return_statement_t		return_;
};

union ast_type_spec_t
{
    ast_type_spec_common_t		common;
    ast_identifier_type_spec_t		identifier;
    ast_function_type_spec_t		function;
    ast_array_type_spec_t		array;
    ast_object_type_spec_t		object;
};

union ast_t
{
    ast_type_t				type;
    ast_common_t			common;

    ast_case_t				case_;
    ast_statement_t			statement;
    ast_expression_t			expression;
    ast_program_t			program;
    ast_type_spec_t			type_spec;
    ast_definition_t			definition;
};

/* AST constructors */
ast_definition_t *ast_definition_new_function	  (const char *name,
						   ast_variable_definition_t **parameters,
						   ast_type_spec_t *return_type,
						   ast_statement_t *body);
ast_definition_t *ast_definition_new_class	  (const char *name,
						   ast_statement_t *statement);
ast_definition_t *ast_definition_new_variable     (const char *name,
						   ast_type_spec_t *type_spec);
ast_definition_t *ast_definition_new_type         (const char *name,
						   ast_type_spec_t *type_spec);
ast_definition_t *ast_definition_new_label        (const char *name,
						   ast_label_statement_t *label);

ast_statement_t * ast_statement_new_loop	  (ast_statement_t *init,
						   ast_expression_t *cond,
						   ast_statement_t *body,
						   ast_statement_t *increment);
ast_statement_t * ast_statement_new_if            (ast_expression_t *condition,
						   ast_statement_t *if_part,
						   ast_statement_t *else_part);
ast_case_t *      ast_case_new_default		  (ast_statement_t *statement);
ast_case_t *	  ast_case_new_expression	  (ast_expression_t *expression,
						   ast_statement_t *statement);
ast_statement_t * ast_statement_new_switch        (ast_expression_t *condition,
						   ast_case_t **cases);
ast_statement_t * ast_statement_new_definition    (ast_definition_t *definition);
ast_statement_t * ast_statement_new_print         (ast_expression_t **exprs);
ast_statement_t * ast_statement_new_expression    (ast_expression_t *expr);
ast_statement_t * ast_statement_new_compound      (ast_statement_t *first,
						   ast_statement_t *second);
ast_statement_t * ast_statement_new_block         (ast_statement_t *body);
ast_statement_t * ast_statement_new_goto          (ast_expression_t *target);
ast_statement_t * ast_statement_new_break	  (void);
ast_statement_t * ast_statement_new_continue      (void);
ast_statement_t * ast_statement_new_label	  (const char *label);
ast_statement_t * ast_statement_new_return        (ast_expression_t *expr);
ast_statement_t * ast_statement_new_empty         (void);
ast_expression_t *ast_expression_new_int_literal  (const token_t *token);
ast_expression_t *ast_expression_new_float_literal (const token_t *token);
ast_expression_t *ast_expression_new_string_literal (const char *s);
ast_expression_t *ast_expression_new_bool_literal (gboolean value);
ast_expression_t *ast_expression_new_null	  (void);
ast_expression_t *ast_expression_new_identifier   (const char *name);
ast_expression_t *ast_expression_new_unary        (ast_unary_operator_t op,
						   ast_expression_t     *child);
ast_expression_t *ast_expression_new_binary       (ast_binary_operator_t op,
						   ast_expression_t *left,
						   ast_expression_t *right);
ast_expression_t *ast_expression_new_ternary      (ast_expression_t *left,
						   ast_expression_t *middle,
						   ast_expression_t *right);
ast_expression_t *ast_expression_new_call	  (ast_expression_t *callee,
						   ast_expression_t **args);
ast_expression_t *ast_expression_new_lambda       (ast_function_definition_t *fun);
ast_expression_t *ast_expression_new_statement    (ast_statement_t *statement,
						   ast_expression_t *expr);
ast_expression_t *ast_expression_new_new          (ast_type_spec_t  *type,
						   ast_expression_t **args);
ast_expression_t *ast_expression_new_block        (ast_expression_t *body);
ast_expression_t *ast_expression_new_dot	  (ast_expression_t *left,
						   const char       *name);
ast_expression_t *ast_expression_new_index        (ast_expression_t *left,
						   ast_expression_t *right);
ast_expression_t *ast_expression_new_void	  (void);
ast_expression_t *ast_expression_new_this         (void);

ast_type_spec_t * ast_type_spec_new		  (ast_type_spec_type_t type);
ast_type_spec_t * ast_type_spec_new_identifier    (const char *name);
void              ast_type_spec_init_object	  (ast_type_spec_t *type_spec,
						   ast_class_definition_t *class);
ast_type_spec_t * ast_type_spec_new_object	  (ast_class_definition_t *class);
ast_type_spec_t * ast_type_spec_new_function	  (ast_type_spec_t *return_,
						   ast_type_spec_t **args);
ast_type_spec_t * ast_type_spec_new_array         (ast_type_spec_t *child);
int		  ast_type_spec_get_size	  (ast_type_spec_t *type);

ast_program_t *   ast_program_new		  (ast_statement_t *statement);
ast_definition_t *ast_class_definition_lookup_var (ast_class_definition_t *class,
						   const char *name);
gboolean	  ast_is			  (ast_t           *ast,
						   ast_type_t       type,
						   int              subtype);
ast_function_definition_t *ast_enclosing_function (ast_t           *ast);
ast_class_definition_t    *ast_enclosing_class    (ast_t           *ast);
ast_loop_statement_t      *ast_enclosing_loop     (ast_t           *ast);
ast_switch_statement_t    *ast_enclosing_switch   (ast_t           *ast);
ast_program_t             *ast_enclosing_program  (ast_t           *ast);
gboolean		   ast_encloses           (ast_t           *outer,
						   ast_t           *inner);
void                       ast_ensure_ast         (ast_t	   *ast);

void program_breadth_first (ast_program_t *program,
			    node_callback_t callback,
			    gpointer data);

/* Garbage Collector */
void  gc_init  (void);
void *gc_alloc (int n_bytes);

/* Phases */
token_t *scan           (const char      *input);
ast_t *  parse          (const token_t   *tokens);
gboolean prepare        (ast_t           *ast);
gboolean symbol         (ast_t           *ast);
gboolean type_check     (ast_t           *ast);
gboolean mark_constants (ast_t           *ast);
gboolean switch_check   (ast_t           *ast);
gboolean graph          (ast_t           *ast);
gboolean init_check     (ast_t           *ast);
gboolean return_check   (ast_t           *ast);
gboolean levels		(ast_t		 *ast);
gboolean optimize       (ast_t           *ast);
gboolean offsets        (ast_t           *ast);
void     interpret      (ast_t           *ast);

/* Driver */
ast_t *  compile        (const char      *input,
			 gboolean         do_optimize,
			 gboolean	  debug_spew);

/* Debug spew */
void     dump_program   (ast_program_t   *program);
void     dump_type_spec (ast_type_spec_t *type_spec);
void     dump_tokens    (token_t         *tokens);
void     dump_graph     (ast_program_t   *program);

/* Internal testing */
void     run_internal_tests (void);