/*
 * Copyright (c) 2004 - 2006, Nils R. Weller
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * Expression parser
 */
#include "expr.h"
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "token.h"
#include "error.h"
#include "defs.h"
#include "type.h"
#include "subexpr.h"
#include "libnwcc.h"
#include "n_libc.h"

void
append_expr(struct expr **head, struct expr **tail, struct expr *e) {
	if (*head == NULL) {
		*head = *tail = e;
	} else {
		(*tail)->next = e;
		e->prev = *tail;
		*tail = (*tail)->next;
	}
}

struct expr *
alloc_expr(void) {
	struct expr	*ret = n_xmalloc(sizeof *ret);
	static struct expr	nullexpr;
	*ret = nullexpr;
	return ret;
}


void	recover(struct token **tok, int delim, int delim2);

static int
ambig_to_binary(struct token *t) {
	int	op = *(int *)t->data;
	switch (op) {
	case TOK_OP_AMB_PLUS:
		op = TOK_OP_PLUS;
		break;
	case TOK_OP_AMB_MINUS:
		op = TOK_OP_MINUS;
		break;
	case TOK_OP_AMB_MULTI:
		op = TOK_OP_MULTI;
		break;
	case TOK_OP_AMB_BAND:
		op = TOK_OP_BAND;
		break;
	case TOK_OP_AMB_COND2:
		op = TOK_OP_COND2;
		break;
	}

	if (!IS_BINARY(op) && op != TOK_OP_COND2) {
		errorfl(t, "Invalid operator ``%s'' - "
			"binary or ternary operator expected", t->ascii);
		return -1;
	}
	return op;
}


int
expr_ends(struct token *t, int delim, int delim2) {
	int	type;

	if (t->type == TOK_OPERATOR) {
		type = *(int *)t->data;
	} else {
		type = t->type;
	}
	if (type == delim || type == delim2) {
		return 1;
	}
	return 0; 
}


/*
 * Get lowest precedence operator in an expression. Note that the
 * conditional operator requires special handling; In
 * foo? bar: baz;
 * ... ? and : act like parentheses, i.e. lower precedence operators
 * such as the comma operator may occur between them.
 */
static struct operator *
get_lowest_prec(struct expr *ex, struct expr **endp) {
	int		lowest = 100;
	int		cond_expr = 0;
	struct expr	*lptr = NULL;

	*endp = NULL;
	for (; ex != NULL; ex = ex->next) {
		struct operator	*tmp;

		if (ex->op == 0 || ex->used) {
			continue;
		}
		tmp = &operators[LOOKUP_OP2(ex->op)];
		if (!cond_expr) {
			if (tmp->prec < lowest) {
				lowest = tmp->prec;
				lptr = ex;
			} else if (tmp->prec == lowest) {
				if (tmp->assoc != OP_ASSOC_RIGHT) {
					lptr = ex;
				}
			}
		}	
		if (ex->op == TOK_OP_COND) {
			++cond_expr;
		} else if (ex->op == TOK_OP_COND2) {
			--cond_expr;
		}	
	}
	*endp = lptr;
	return lptr? (void *)&operators[LOOKUP_OP2(lptr->op)]: (void *)NULL;
}

static struct expr *
bind_operators(struct expr *ex) {
	struct operator	*op;
	struct expr	*endp;
	struct expr	*start = ex;

	if (ex == NULL) return NULL;
	if ((op = get_lowest_prec(ex, &endp)) == NULL) {
		/* No more operators left */
		if (!ex->used) {
			endp = ex;
			endp->used = 1;
		}
		else endp = NULL;
		return endp;
	} else if (op->value == TOK_OP_COND) {
		struct expr	*endp2;
		struct expr	*ex2 = endp->next;
		int		cond1 = 0;

		/*
		 * Need to get second part of conditional operator. This
		 * requires skipping intermediate conditional operators.
		 */
		for (;;) {
			if (ex2 == NULL 
				|| (op = get_lowest_prec(ex2, &endp2))
				== NULL) {
				errorfl(ex2? ex2->tok: endp->tok,
					"Parse error - missing second part"
					" of conditional operator");
				return NULL;
			} else if (op->value == TOK_OP_COND) {
				++cond1;
			} else if (op->value == TOK_OP_COND2) {
				if (cond1 == 0) {
					/* done! */
					break;
				} else {
					--cond1;
				}	
			}	
			ex2 = endp2->next;
		} 

		/*
		 * At this point, endp points to ``?'' and endp2 to ``:''. We
		 * bind them such that:
		 * Given x = ``?''
		 * ... x->left = cond-expr
		 * ... x->right = :
		 * ... x->right->left = expr-nonzero
		 * ... x->right->right = expr-zero
		 */
		endp->used = endp2->used = 1;
		ex = endp->next;
		endp->next = NULL;
		endp->left = bind_operators(start);
		endp->right = endp2; 
		ex2 = endp2->next;
		endp2->next = NULL;
		endp->right->left = bind_operators(ex);
		endp->right->right = bind_operators(ex2);
		return endp;
	}	

	endp->used = 1;

	ex = endp->next;
	endp->next = NULL;

	endp->left = bind_operators(start);
	endp->right = bind_operators(ex);
	return endp;
}

static void
append_init_list(
	struct initializer **init, 
	struct initializer **init_tail,
	struct initializer *i) {
	if (*init == NULL) {
		*init = *init_tail = i;
	} else {
		(*init_tail)->next = i;
		*init_tail = (*init_tail)->next;
	}	
}	

struct initializer *
alloc_initializer(void) {
	static struct initializer	nullinit;
	struct initializer	*ret;
	ret = n_xmalloc(sizeof *ret);
	*ret = nullinit;
	return ret;
}	

static void
conv_init(struct tyval *tv, struct type *toty, struct token *t) {
	struct type		*fromty = tv->type;
	struct type_node	*ltn;
	struct type_node	*rtn;

	if (toty->tlist == NULL) {
		/* Simple basic type conversion */
		if (toty->code != fromty->code) {
			cross_do_conv(tv, toty->code);
		}
		return;
	}

	if (fromty->tlist == NULL || 
		(toty->code != fromty->code
		&& (toty->code != TY_VOID && fromty->code != TY_VOID))) { 
	/* this bullshit doesn't work */		
		return;
	}


	/* 
	 * Must be assignment to pointer since this function is only
	 * called for scalar types
	 */

	if (tv->is_nullptr_const) {
		return;
	}
	if (toty->code == TY_VOID
		&& toty->tlist->type == TN_POINTER_TO
		&& toty->tlist->next == NULL) {
		/* Assignment to void pointer */
		return;
	}	
		

	ltn = toty->tlist;
	rtn = fromty->tlist;

	if (rtn && rtn->type == TN_FUNCTION) {
		if (ltn->type == TN_POINTER_TO) {
			/* Probably pointer to function */
			ltn = ltn->next;
		}
	}	

	for (; ltn != NULL && rtn != NULL;
		ltn = ltn->next, rtn = rtn->next) {
		if (ltn->type != rtn->type) {
			if (rtn->type == TN_ARRAY_OF
				&& rtn == fromty->tlist) {
				/* OK - assign array address to ptr */
				;
			} else {
				errorfl(t,
					"Initializer of incompatible type");
				return;
			}	
		}	
	}

	if (ltn != rtn) {
		/* One type list is longer */
		errorfl(t, "Initializer of incompatible type");
		return;
	}
}

/*
 * Parses an expression and returns a pointer to the parse tree.
 */
struct expr *
parse_expr(struct token **tok, int delim, int delim2, int type) {
	struct token	*t;
	struct token	*tokstart = *tok;
	struct expr	*ret = NULL;
	struct expr	*rettail = NULL;
	struct expr	*ex = NULL;
	struct s_expr	*s_ex;
	struct s_expr	*last_s_ex = NULL;
	static int	nesting;

	++nesting;

#ifdef NO_EXPR
	/* Don't use expression parser */
	recover(tok, delim, delim2);
	if (*tok == NULL) {
		lexerror("Unterminated expression");
		exit(1);
	}
	return NULL;
#endif

	t = *tok;

	if (t->type == TOK_SEMICOLON) {
		/* Empty expression */
		--nesting;
		if ((delim != TOK_SEMICOLON && delim2 != TOK_SEMICOLON)
			|| type == EXPR_INIT || type == EXPR_CONSTINIT) {
			errorfl(t, "Parse error at `%s'", t->ascii);
			return NULL;
		}
		ret = alloc_expr();
		return ret;
	} else if (t->type == TOK_ARRAY_CLOSE
			&& (delim == TOK_ARRAY_CLOSE
				|| delim2 == TOK_ARRAY_CLOSE)) {
		ret = alloc_expr();
		--nesting;
		return ret;
	}


	/*
	 * Strategy: An expression is a number of sub-expressions
	 * connected through binary and ternary operators, so we
	 * just always need to read a sub-expression, a connecting
	 * operator - if any - and then the next sub-expression.
	 */
	while ((s_ex = get_sub_expr(&t, delim, delim2, type)) != NULL) {
		int	op;

		last_s_ex = s_ex;

		ex = alloc_expr();
		ex->op = 0;
		ex->data = s_ex;

		append_expr(&ret, &rettail, ex);

		if (expr_ends(t, delim, delim2)) {
			if ((ex->tok = s_ex->meat) == NULL) {
				if ((ex->tok = s_ex->is_sizeof) == NULL) {
					/* Must be parenthesized expr */
					ex->tok = s_ex->is_expr->tok;
				}
			}	
			break;
		} else if (t->type != TOK_OPERATOR) {
			errorfl(t, "Parse error at `%s'(#2)", t->ascii);
			ex = NULL;
			break;
		}
		/* Must be binary or ternary operator */
		ex = alloc_expr();
		ex->data = NULL;
		op = *(int *)t->data;
		ex->tok = t;
		if (op != TOK_OP_COND) {
			op = ambig_to_binary(t);
	t->data = n_xmemdup(&op, sizeof op); /* XXX is this ok? */	
		}	
		if (type == EXPR_CONST || type == EXPR_CONSTINIT) {
			int		err = 0;
			char	*is_what =
				type == EXPR_CONST? "expression": "initializer";

			if (op == TOK_OP_COMMA) {
				errorfl(t,
					"The comma operator is not allowed "
					"in constant %ss", is_what);
				dump_toklist(*tok);
				exit(0);
				err = 1;
			} else if (IS_ASSIGN_OP(op)) {
				errorfl(t,
					"Assignment operators are not allowed "
					"in constant %ss", is_what);
				err = 1;
			}
			if (err) {
				free(ex);
				ex = NULL;
				break;
			}
		}
		ex->op = op;

		append_expr(&ret, &rettail, ex);

		if (next_token(&t) != 0) {
			--nesting;
			return NULL;
		}
		if (expr_ends(t, delim, delim2)) {
			errorfl(ex->tok, "Syntax error at `%s'",
				ex->tok->ascii);
			break;
		}
	}

	*tok = t;

	if (ex == NULL || !expr_ends(t, delim, delim2)) {
		/* Try to recover from parse errors */
		if (nesting == 1) {
			recover(&tokstart, delim, delim2);
			*tok = tokstart;
		}
		--nesting;
		return NULL;
	}

	--nesting;
	fflush(stdout);

	if ((ret = bind_operators(ret)) == NULL) {
		puts("panic: cannot bind operators");
		exit(1); /* XXX */
	}
	ret->extype = type;
	if ((type == EXPR_CONST || type == EXPR_CONSTINIT)
		&& nesting == 0) {
		if (eval_const_expr(ret) != 0) {
			return NULL;
		}	
	}

	return ret;
}




void
recover(struct token **tok, int delim, int delim2) {
	struct token	*t;
	int		parens = 0;
	int		brackets = 0;
	int		braces = 0;

	if (*tok == NULL) return; 

	if (delim == TOK_PAREN_CLOSE || delim2 == TOK_PAREN_CLOSE) {
		++parens;
	}
	if (delim == TOK_ARRAY_CLOSE || delim2 == TOK_ARRAY_CLOSE) {
		++brackets;
	}
	if (delim == TOK_COMP_CLOSE || delim2 == TOK_COMP_CLOSE) {
		++braces;
	}

	for (t = *tok; t != NULL; t = t->next) {
		int	ty = -1; /* 0 compared even with unused delim :( */

#ifdef DEBUG2
printf(" lol %s\n", t->ascii);
#endif
		if (t->type == TOK_OPERATOR) {
			ty = *(int *)t->data;
		} else if (t->type == TOK_PAREN_OPEN) {
			++parens;
			continue;
		} else if (t->type == TOK_PAREN_CLOSE) {
			/*
			 * The below was --parens < 0, but <=
			 * seems more permissive for parse 
			 * errors - so use that!
			 */
			if (--parens <= 0
				&& (delim == TOK_PAREN_CLOSE
					|| delim2 == TOK_PAREN_CLOSE)) {
				*tok = t;
				return;
			}
			continue;
		} else if (t->type == TOK_ARRAY_OPEN) {
			++brackets;
			continue;
		} else if (t->type == TOK_ARRAY_CLOSE) {
			if (--brackets <= 0
				&& (delim == TOK_ARRAY_CLOSE
					|| delim2 == TOK_ARRAY_CLOSE)) {
				*tok = t;
printf("okay, ret at %s\n", t->ascii);
				return;
			}
			continue;
		} else if (t->type == TOK_COMP_OPEN) {
			++braces;
			continue;
		} else if (t->type == TOK_COMP_CLOSE) {
			if (--braces <= 0
				&& (delim == TOK_COMP_CLOSE
					|| delim2 == TOK_COMP_CLOSE)) {
				*tok = t;
				return;
			}
			continue;
		} else {
			ty = t->type;
		}
		if (ty == delim || ty == delim2) {
			if (ty == TOK_OP_COMMA) {
				/*
				 * We must take into account that someone
				 * could write
				 * int foo = bar(x, y, z);
				 * ... in which case we do not want to exit
				 * after x!
				 */
				if (parens != 0) {
					continue;
				}
			}
			*tok = t;
			return; 
		}
	}
	*tok = NULL;
}