/* %Z%%M% %I% %E% */

/*
 * Copyright (c) 1990, 1991, 1992, 1993, 1995 by Wayne C. Gramlich.
 * All rights reserved.
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * for any purpose is hereby granted without fee provided that the above
 * copyright notice and this permission are retained.  The author makes
 * no representations about the suitability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 */

/* This file contains code for parse an expression from tokens: */

#ifndef EXP_DEFS_H
#include "exp_defs.h"
#endif

#ifndef GEN_DEFS_H
#include "gen_defs.h"
#endif

#ifndef HEAP_EXPORTS_H
#include "heap_exports.h"
#endif

#ifndef LINT_H
#include "lint.h"
#endif

#ifndef MSG_EXPORTS_H
#include "msg_exports.h"
#endif

#ifndef PARSER_DEFS_H
#include "parser_defs.h"
#endif

#ifndef TOKEN_DEFS_H
#include "token_defs.h"
#endif

#ifndef TYPE_DEFS_H
#include "type_defs.h"
#endif

#ifndef UNIX_ASSERT_H
#include "unix_assert.h"
#endif

#ifndef VECTOR_DEFS_H
#include "vector_defs.h"
#endif

LOCAL Exp	exp_access_create(Exp_op, Exp, Vec(Exp), Token, Heap);
LOCAL Exp	exp_binary_create(Exp_op, Exp, Exp, Token, Heap);
LOCAL Exp	exp_create(Exp_op, Token, Heap);
LOCAL Exp	exp_error(Str, Parser);
LOCAL Exp	exp_field_create(Exp_op, Exp, Str, Token, Heap);
LOCAL Exp	exp_list_create(Vec(Exp), Token, Heap);
LOCAL Exp	exp_unary_create(Exp_op, Exp, Token, Heap);

/*
 * exp_access_create(op, exp, list, token, heap)
 *	This routine will create and return a new access expression with
 *	an operator of op "op", containing the expression "exp", token
 *	"token", and expression list "list" from "heap".
 */
LOCAL Exp
exp_access_create(
	Exp_op		op,
	Exp		exp,
	Vec(exp)	list,
	Token		token,
	Heap		heap)
{
	Exp		new_exp;
	Exp_access	access;

	access = heap_allocate(heap, Exp_access);
	access->exp = exp;
	access->list = list;
	new_exp = exp_create(op, token, heap);
	new_exp->operands.access = access;
	return new_exp;
}

/*
 * exp_assign_parse(parser, eval_ok)
 *	This routine will parse return an assignment exp from "parser".
 *	If "eval_ok" is 1, an expression with no assignment operator
 *	will be return in a Exp_op_eval exp.
 */
Exp
exp_assign_parse(
	Parser		parser,
	int		eval_ok)
{
	Heap		heap;
	Vec(Exp)	left;
	Exp_op		op;
	Vec(Exp)	right;
	Token		token;

	heap = parser->heap;
	left = exp_list_parse(parser, 0);
	token = parser_token_peek(parser);
	switch (token->type) {
	    case Token_type_add_assign:
		op = Exp_op_add_assign;
		break;
	    case Token_type_and_assign:
		op = Exp_op_and_assign;
		break;
	    case Token_type_assign:
		op = Exp_op_assign;
		break;
	    case Token_type_define_assign:
		op = Exp_op_define_assign;
		break;
	    case Token_type_divide_assign:
		op = Exp_op_divide_assign;
		break;
	    case Token_type_left_shift_assign:
		op = Exp_op_left_shift_assign;
		break;
	    case Token_type_multiply_assign:
		op = Exp_op_multiply_assign;
		break;
	    case Token_type_or_assign:
		op = Exp_op_or_assign;
		break;
	    case Token_type_power_assign:
		op = Exp_op_power_assign;
		break;
	    case Token_type_remainder_assign:
		op = Exp_op_remainder_assign;
		break;
	    case Token_type_right_shift_assign:
		op = Exp_op_right_shift_assign;
		break;
	    case Token_type_subtract_assign:
		op = Exp_op_subtract_assign;
		break;
	    case Token_type_xor_assign:
		op = Exp_op_xor_assign;
		break;
	    case Token_type_eol:
		if (eval_ok && (vec_size(Exp, left) == 1)) {
			return vec_fetch(Exp, left, 0);
		}
		/* Fall Through! */
	    default:
		return exp_error("Missing assignment operator", parser);
	}
	(void)parser_token_read(parser);
	right = exp_list_parse(parser, 0);
	return exp_binary_create(op, exp_list_create(left, token, heap),
				 exp_list_create(right, token,heap),
				 token, heap);
}

/*
 * exp_binary_create(op, left, right, token, heap)
 *	This routine will create and return a new binary exp of op "op"
 *	and token "token" containing exps "left" and "right" from "heap".
 */
LOCAL Exp
exp_binary_create(
	Exp_op		op,
	Exp		left,
	Exp		right,
	Token		token,
	Heap		heap)
{
	Exp		exp;
	Exp_binary	binary;

	binary = heap_allocate(heap, Exp_binary);
	binary->left = left;
	binary->right = right;
	exp = exp_create(op, token, heap);
	exp->operands.binary = binary;
	return exp;
}

/*
 * exp_create(op, token, heap)
 *	This routine will create and return a new expression object
 *	with operator "op" and "token"'s position from "heap".
 */
LOCAL Exp
exp_create(
	Exp_op		op,
	Token		token,
	Heap		heap)
{
	Exp		exp;

	exp = heap_allocate(heap, Exp);
	exp->op = op;
	exp->position = token->position;
	exp->call = (Call)0;
	exp->type_refs = (Type_refs)0;
	exp->token = (Token)0;
	return exp;
}

/*
 * exp_error(message, parser)
 *	This routine will display an error message and return an error
 *	expression.
 */
LOCAL Exp
exp_error(
	Str		message,
	Parser		parser)
{
	Exp		exp;
	Token		token;

	token = parser_token_peek(parser);
	msg_out(parser->msg, token->position, message);
	exp = exp_create(Exp_op_error, token, parser->heap);
	exp->operands.error = message;
	return exp;
}

/*
 * exp_field_create(op, exp, name, token, heap)
 *	This routine will create and return a new field expression object
 *	containing token "token", "exp", and "name" from "heap".
 */
LOCAL Exp
exp_field_create(
	Exp_op		op,
	Exp		exp,
	Str		name,
	Token		token,
	Heap		heap)
{
	Exp		new_exp;
	Exp_field	field;

	field = heap_allocate(heap, Exp_field);
	field->exp = exp;
	field->name = name;
	new_exp = exp_create(op, token, heap);
	new_exp->operands.field = field;
	return new_exp;
}

/*
 * exp_list_create(list, token, heap)
 *	This routine will create and return an expression list using "list"
 *	and "token" from "heap".
 */
LOCAL Exp
exp_list_create(
	Vec(Exp)	list,
	Token		token,
	Heap		heap)
{
	Exp		exp;

	exp = exp_create(Exp_op_list, token,heap);
	exp->operands.list = list;
	return exp;
}

/*
 * exp_list_parse(parser, empty_ok)
 *	This routine will parse and return an expression list from "parser".
 *	If "empty_ok" is 1, empty expression lists are permitted.
 */
Vec(Exp)
exp_list_parse(
	Parser		parser,
	int		empty_ok)
{
	Heap		heap;
	Vec(Exp)	list;
	Exp		exp;
	Token		token;

	heap = parser->heap;
	list = vec_create(Exp, heap);
	for (;;) {
		if (empty_ok) {
			token = parser_token_peek(parser);
			if (token->type == Token_type_right_paren) {
				break;
			}
		}
		exp = exp_parse(parser);
		vec_append(Exp, list, exp);
		token = parser_token_peek(parser);
		if (token->type == Token_type_comma) {
			(void)parser_token_read(parser);
		} else {
			break;
		}
	}
	return list;
}

/*
 * exp_parse(parser)
 *	This routine will parse and return an expression from "parser".
 */
Exp
exp_parse(
	Parser			parser)
{
	int			do_at_paren;
	int			do_twiddle;
	int			exiting;
	Exp			exp;
	static Vec(Exp)		exps = (Vec(Exp))0;
	int			exps_size;
	Heap			heap;
	int			is_bracket;
	Vec(Exp)		list;
	Str			message;
	Token_type		parser_type;
	int			precedence;
	static Vec(int)		precedences = (Vec(int))0;
	int			precedences_size;
	int			size;
	Token			token;
	Exp			top_exp;
	int			top_precedence;
	Exp_op			top_type;
	Exp_trinary		trinary;
	Exp_op			type;
	static Vec(Exp_op)	types = (Vec(Exp_op))0;
	int			types_size;

	heap = parser->heap;
	exiting = 0;
	if (exps == (Vec(Exp))0) {
		exps = vec_create(Exp, heap);
		precedences = vec_create(int, heap);
		types = vec_create(Noe_type, heap);
	}
	exps_size = vec_size(Exp, exps);
	precedences_size = vec_size(int, precedences);
	types_size = vec_size(Exp_op, types);

	/* Operand/Operator loop: */
	for (;;) {
		/* Process any prefix operators: */
		for (;;) {
			token = parser_token_peek(parser);
			precedence = parser->operators[(int)token->type];
			switch (token->type) {
			    case Token_type_add:
				type = Exp_op_convert;
				precedence &= ~PARSER_BINARY;
				break;
			    case Token_type_decrement:
				type = Exp_op_pre_decrement;
				break;
			    case Token_type_increment:
				type = Exp_op_pre_increment;
				break;
			    case Token_type_not:
				type = Exp_op_not;
				break;
			    case Token_type_subtract:
				precedence &= ~PARSER_BINARY;
				type = Exp_op_minus;
				break;
			    default:
				goto not_prefix;
			}
			(void)parser_token_read(parser);
			vec_append(Exp_op, types, type);
			vec_append(int, precedences, precedence);
		}
	    not_prefix:
		/* Process any operand: */
		switch (token->type) {
		    case Token_type_left_paren:
			(void)parser_token_read(parser);
			exp = exp_parse(parser);
			token = parser_token_peek(parser);
			if (token->type == Token_type_right_paren) {
				(void)parser_token_read(parser);
				vec_append(Exp, exps, exp);
			} else {
				exp = exp_error("Missing ')'", parser);
				goto done;
			}
			break;
		    case Token_type_integer:
			exp = exp_create(Exp_op_integer, token, heap);
			exp->operands.integer = token->value.integer;
			vec_append(Exp, exps, exp);
			(void)parser_token_read(parser);
			break;
		    case Token_type_string:
			exp = exp_create(Exp_op_string, token, heap);
			exp->operands.string = token->value.string;
			vec_append(Exp, exps, exp);
			(void)parser_token_read(parser);
			break;
		    case Token_type_symbol:
		      {
			Exp_define	define;
			Token		token_next;
			Exp_type	type;
			Type_ref	type_ref;

			(void)parser_token_read(parser);
			token_next = parser_token_peek(parser);
			switch (token_next->type) {
			    case Token_type_at:
				(void)parser_token_read(parser);
				type_ref = type_ref_parse(parser);
				type = heap_allocate(parser->heap, Exp_type);
				type->name = token->value.symbol;
				type->type_ref = type_ref;
				exp = exp_create(Exp_op_at, token, heap);
				exp->operands.type = type;
				break;
			    case Token_type_define:
				(void)parser_token_read(parser);
				type_ref = type_ref_parse(parser);
				define = heap_allocate(parser->heap,
						       Exp_define);
				define->name = token->value.symbol;
				define->type_ref = type_ref;
				exp = exp_create(Exp_op_define, token, heap);
				exp->operands.define = define;
				break;
			    default:
				exp = exp_create(Exp_op_symbol, token, heap);
				exp->operands.symbol = token->value.symbol;
			}
			vec_append(Exp, exps, exp);
			break;
		      }
		    case Token_type_text:
			exp = exp_create(Exp_op_text, token, heap);
			exp->operands.text = token->value.text;
			vec_append(Exp, exps, exp);
			(void)parser_token_read(parser);
			break;
		    case Token_type_zilch:
			exp = exp_create(Exp_op_symbol, token, heap);
			exp->operands.symbol = "??";
			vec_append(Exp, exps, exp);
			(void)parser_token_read(parser);
			break;
		    default:
			exp = exp_error("Missing operand in expression",
					parser);
			goto done;
		}
		/* Process any post-fix operators including '(' and ']': */
		for (;;) {
			do_at_paren = 0;
			do_twiddle = 0;
			token = parser_token_peek(parser);
			switch (token->type) {
			    case Token_type_decrement:
				type = Exp_op_post_decrement;
				is_bracket = 0;
				break;
			    case Token_type_increment:
				type = Exp_op_post_increment;
				is_bracket = 0;
				break;
			    case Token_type_left_bracket:
				type = Exp_op_array;
				parser_type = Token_type_right_bracket;
				message = "Missing ']'";
				is_bracket = 1;
				break;
			    case Token_type_left_paren:
				type = Exp_op_call;
				parser_type = Token_type_right_paren;
				message = "Missing ')'";
				is_bracket = 1;
				break;
			    case Token_type_at_parenthesis:
				do_at_paren = 1;
				type = Exp_op_call;
				parser_type = Token_type_right_paren;
				message = "Missing ')'";
				is_bracket = 1;
				break;
			    default:
				goto not_post_fix;
			}
			/* Reduce any dot or at expressions: */
			size = vec_size(Exp_op, types);
			if (size > types_size) {
				switch (vec_fetch(Exp_op, types, size - 1)) {
				    case Exp_op_dot:
					(void)vec_pop(int, precedences);
					(void)vec_pop(Exp_op, types);
					top_exp = vec_pop(Exp, exps);
					if (top_exp->op != Exp_op_symbol) {
						msg_out(parser->msg,
						  top_exp->position,
						  "Field name must follow '.'");
						goto done;
					}
					exp = vec_pop(Exp, exps);
					exp = exp_field_create(Exp_op_dot,
						exp,
						top_exp->operands.symbol,
						token,
						heap);
					vec_append(Exp, exps, exp);
					break;
				    case Exp_op_twiddle:
					do_twiddle = is_bracket;
					break;
				}
			}
			(void)parser_token_read(parser);
			if (is_bracket) {
				list = exp_list_parse(parser,
						      type == Exp_op_call);
				token = parser_token_peek(parser);
				if (token->type != parser_type) {
					exp = exp_error(message, parser);
					goto done;
				}
				(void)parser_token_read(parser);
				if (do_twiddle) {
					Exp_object	exp_object;

					top_exp = vec_pop(Exp, exps);
					if (top_exp->op != Exp_op_symbol) {
					    msg_out(parser->msg,
					      top_exp->position,
					      "Routine name must follow '~'");
					    goto done;
					}
					(void)vec_pop(int, precedences);
					(void)vec_pop(Exp_op, types);
					exp = vec_pop(Exp, exps);
					exp_object = heap_allocate(heap,
								   Exp_object);
					exp_object->list = list;
					exp_object->name =
						top_exp->operands.symbol;
					exp_object->object = exp;
					exp = exp_create(Exp_op_twiddle,
							 token, heap);
					exp->operands.object = exp_object;
				} else if (do_at_paren) {
					Exp_object	exp_object;

					if (vec_size(Exp, list) == 0) {
						msg_out(parser->msg,
							token->position,
							"No argument for '@('");
						goto done;
					}
					top_exp = vec_pop(Exp, exps);
					if (top_exp->op != Exp_op_symbol) {
						msg_out(parser->msg,
						  top_exp->position,
						  "Symbol must preceed '@('");
						goto done;
					}
					exp_object = heap_allocate(heap,
								   Exp_object);
					exp_object->name =
						top_exp->operands.symbol;
					exp_object->object = vec_lop(Exp, list);
					exp_object->list = list;
					exp = exp_create(Exp_op_twiddle,
							 token, heap);
					exp->operands.object = exp_object;
				} else {
					exp = vec_pop(Exp, exps);
					exp = exp_access_create(type, exp, list,
								token, heap);
				}
				vec_append(Exp, exps, exp);
			} else {
				exp = vec_pop(Exp, exps);
				exp = exp_unary_create(type, exp, token, heap);
				vec_append(Exp, exps, exp);
				continue;
			}
		}
	    not_post_fix:
		/* Process any binary operators: */
		switch (token->type) {
		    case Token_type_eol:
		    case Token_type_comma:
		    case Token_type_right_bracket:
		    case Token_type_right_paren:
			exiting = 1;
			break;
		    case Token_type_add_assign:
		    case Token_type_and_assign:
		    case Token_type_assign:
		    case Token_type_define_assign:
		    case Token_type_divide_assign:
		    case Token_type_left_shift_assign:
		    case Token_type_multiply_assign:
		    case Token_type_or_assign:
		    case Token_type_power_assign:
		    case Token_type_remainder_assign:
		    case Token_type_right_shift_assign:
		    case Token_type_subtract_assign:
		    case Token_type_xor_assign:
			exiting = 1;
			break;
		    case Token_type_add:
			type = Exp_op_add;
			break;
		    case Token_type_add_result:
			type = Exp_op_add_result;
			break;
		    case Token_type_and:
			type = Exp_op_and;
			break;
		    case Token_type_and_if:
			type = Exp_op_and_if;
			break;
		    case Token_type_and_result:
			type = Exp_op_and_result;
			break;
		    case Token_type_colon:
			type = Exp_op_colon;
			break;
		    case Token_type_dot:
			type = Exp_op_dot;
			break;
		    case Token_type_equal:
			type = Exp_op_equal;
			break;
		    case Token_type_define_result:
			type = Exp_op_define_result;
			break;
		    case Token_type_divide:
			type = Exp_op_divide;
			break;
		    case Token_type_divide_result:
			type = Exp_op_divide_result;
			break;
		    case Token_type_greater_than:
			type = Exp_op_greater_than;
			break;
		    case Token_type_greater_than_or_equal:
			type = Exp_op_greater_than_or_equal;
			break;
		    case Token_type_identical:
			type = Exp_op_identical;
			break;
		    case Token_type_if:
			type = Exp_op_arithmetic_if;
			break;
		    case Token_type_left_shift:
			type = Exp_op_left_shift;
			break;
		    case Token_type_left_shift_result:
			type = Exp_op_left_shift_result;
			break;
		    case Token_type_less_than:
			type = Exp_op_less_than;
			break;
		    case Token_type_less_than_or_equal:
			type = Exp_op_less_than_or_equal;
			break;
		    case Token_type_not_equal:
			type = Exp_op_not_equal;
			break;
		    case Token_type_not_identical:
			type = Exp_op_not_identical;
			break;
		    case Token_type_multiply:
			type = Exp_op_multiply;
			break;
		    case Token_type_multiply_result:
			type = Exp_op_multiply_result;
			break;
		    case Token_type_or:
			type = Exp_op_or;
			break;
		    case Token_type_or_if:
			type = Exp_op_or_if;
			break;
		    case Token_type_or_result:
			type = Exp_op_or_result;
			break;
		    case Token_type_power:
			type = Exp_op_power;
			break;
		    case Token_type_power_result:
			type = Exp_op_power_result;
			break;
		    case Token_type_remainder:
			type = Exp_op_remainder;
			break;
		    case Token_type_remainder_result:
			type = Exp_op_remainder_result;
			break;
		    case Token_type_result:
			type = Exp_op_result;
			break;
		    case Token_type_right_shift:
			type = Exp_op_right_shift;
			break;
		    case Token_type_right_shift_result:
			type = Exp_op_right_shift_result;
			break;
		    case Token_type_subtract:
			type = Exp_op_subtract;
			break;
		    case Token_type_subtract_result:
			type = Exp_op_subtract_result;
			break;
		    case Token_type_twiddle:
			type = Exp_op_twiddle;
			break;
		    case Token_type_xor:
			type = Exp_op_xor;
			break;
		    case Token_type_xor_result:
			type = Exp_op_xor_result;
			break;
		    default:
			exp = exp_error("Missing binary operator", parser);
			goto done;
		}
		if (!exiting) {
			(void)parser_token_read(parser);
			precedence = parser->operators[(int)token->type];
		}
		for (;;) {
			size = vec_size(int, precedences);
			if (size <= precedences_size) {
				break;
			}
			if (!exiting) {
			       	top_precedence = vec_fetch(int,
							   precedences,
							   size - 1);
				if ((top_precedence & PARSER_PREC_MASK) <
				    (precedence & PARSER_PREC_MASK)) {
					break;
				} else if ((top_precedence &
						PARSER_RIGHT_ASSOC) &&
					   ((top_precedence &
						PARSER_PREC_MASK) ==
					    (precedence & PARSER_PREC_MASK))) {
					break;
				}
			}
			top_precedence = vec_pop(int, precedences);
			top_exp = vec_pop(Exp, exps);
			top_type = vec_pop(Exp_op, types);
			switch (top_type) {
			    case Exp_op_arithmetic_if:
				exp = exp_error("Missing ':' for '?'", parser);
				goto done;
			    case Exp_op_colon:
				if (size - 1 <= precedences_size) {
					exp = exp_error("Missing '?' for ':'",
							parser);
					goto done;
				}
				top_precedence = vec_pop(int, precedences);
				top_type = vec_pop(Exp_op, types);
				if (top_type != Exp_op_arithmetic_if) {
					exp = exp_error("Missing '?' for ':'",
							parser);
					goto done;
				}
				trinary = heap_allocate(heap, Exp_trinary);
				trinary->third = top_exp;
				trinary->second = vec_pop(Exp, exps);
				trinary->first = vec_pop(Exp, exps);
				exp = exp_create(Exp_op_arithmetic_if,
						 token,
						 heap);
				exp->operands.trinary = trinary;
				break;
			    case Exp_op_dot:
				if (top_exp->op != Exp_op_symbol) {
					msg_out(parser->msg, top_exp->position,
					    "A field name must follow '.'");
					goto done;
				}
				exp = vec_pop(Exp, exps);
				exp = exp_field_create(Exp_op_dot,
						exp,
						top_exp->operands.symbol,
						token,
						heap);
				break;
#ifdef OLD
			    case Exp_op_at:
				exp = vec_pop(Exp, exps);
				exp = exp_type_create(exp, top_exp, parser);
				break;
			    case Exp_op_define:
				exp = vec_pop(Exp, exps);
				exp = exp_define_create(exp, top_exp, parser);
				break;
#endif /* OLD */
			    default:
				if (top_precedence & PARSER_BINARY) {
					exp = vec_pop(Exp, exps);
					exp = exp_binary_create(top_type,
								exp,
								top_exp,
								token,
								heap);
				} else {
					exp = exp_unary_create(top_type,
							       top_exp,
							       token,
							       heap);
				}
			}
			vec_append(Exp, exps, exp);
		}
		if (exiting) {
			/* Normal exit with no errors. */
			exp = vec_pop(Exp, exps);
			assert(vec_size(Exp, exps) == exps_size);
			assert(vec_size(Exp_op, types) == types_size);
			assert(vec_size(int, precedences) == precedences_size);
			return exp;
		}
		vec_append(int, precedences, precedence);
		vec_append(Exp_op, types, type);
	}
    done:
	vec_trim(Exp, exps, exps_size);
	vec_trim(Exp_op, types, types_size);
	vec_trim(int, precedences, precedences_size);
	return exp;
}

/*
 * exp_unary_create(op, sub_exp, token, heap)
 *	This routine will create and return a unary expression with
 *	operator "op" using "sub_exp" from "heap".
 */
LOCAL Exp
exp_unary_create(
	Exp_op		op,
	Exp		sub_exp,
	Token		token,
	Heap		heap)
{
	Exp		exp;

	exp = exp_create(op, token, heap);
	exp->operands.unary = sub_exp;
	return exp;
}

/*
 * exp_list_types_extract(exps, gen)
 *	This routine will extract each of the types from "exps" using "gen"
 *	and return the resulting type list.
 */
Type_refs
exp_list_types_extract(
	Vec(Exp)	exps,
	Gen		gen)
{
	Exp		exp;
	Type_refs	type_refs;
	Type_tables	type_tables;

	type_tables = gen->type_tables;
	type_refs = type_refs_empty_create(type_tables);
	VEC_LOOP(Exp, exps, exp) {
		type_refs = type_refs_concat(type_refs, exp->type_refs,
					     type_tables);
	}
	return type_refs;
}