#include "expr_eval.h"
#include "arch_error.h"
#include "vtr_util.h"
#include "vtr_math.h"
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <cstring> //memset

using std::vector;
using std::stack;
using std::string;
using std::stringstream;

/**** Enums ****/
/* Used to identify the type of symbolic formula object */
typedef enum e_formula_obj{
	E_FML_UNDEFINED = 0,
	E_FML_NUMBER,
	E_FML_BRACKET,
	E_FML_COMMA,
	E_FML_OPERATOR,
	E_FML_NUM_FORMULA_OBJS
} t_formula_obj;


/* Used to identify an operator in a formula */
typedef enum e_operator{
	E_OP_UNDEFINED = 0,
	E_OP_ADD,
	E_OP_SUB,
	E_OP_MULT,
	E_OP_DIV,
	E_OP_MIN,
	E_OP_MAX,
	E_OP_GCD,
	E_OP_LCM,
	E_OP_NUM_OPS
} t_operator;


/**** Class Definitions ****/
/* This class is used to represent an object in a formula, such as
   a number, a bracket, an operator, or a variable */
class Formula_Object{
public:
	/* indicates the type of formula object this is */
	t_formula_obj type;

	/* object data, accessed based on what kind of object this is */
	union u_Data {
		int num;		/*for number objects*/
		t_operator op;		/*for operator objects*/
		bool left_bracket;	/*for bracket objects -- specifies if this is a left bracket*/

		u_Data(){ memset(this, 0, sizeof(u_Data)); }
	} data;

	Formula_Object(){
		this->type = E_FML_UNDEFINED;
	}

};

/*---- Functions for Parsing the Symbolic Formulas ----*/

/* converts specified formula to a vector in reverse-polish notation */
static void formula_to_rpn( const char* formula, const t_formula_data &mydata,
				vector<Formula_Object> &rpn_output );

static void get_formula_object( const char *ch, int &ichar, const t_formula_data &mydata,
				 Formula_Object *fobj );

/* returns integer specifying precedence of passed-in operator. higher integer
   means higher precedence */
static int get_fobj_precedence( const Formula_Object &fobj );

/* Returns associativity of the specified operator */
static bool op_associativity_is_left( const t_operator &op );

/* used by the shunting-yard formula parser to deal with operators such as add and subtract */
static void handle_operator( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack);

/* used by the shunting-yard formula parser to deal with brackets, ie '(' and ')' */
static void handle_bracket( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack);

/* used by the shunting-yard formula parser to deal with commas, ie ','. These occur in function calls*/
static void handle_comma( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack);

/* parses revere-polish notation vector to return formula result */
static int parse_rpn_vector( vector<Formula_Object> &rpn_vec );

/* applies operation specified by 'op' to the given arguments. arg1 comes before arg2 */
static int apply_rpn_op( const Formula_Object &arg1, const Formula_Object &arg2,
					const Formula_Object &op );

/* checks if specified character represents an ASCII number */
static bool is_char_number( const char ch );

// returns true if ch is an operator
static bool is_operator(const char ch);

// returns true if the specified name is an known function operator
static bool is_function(std::string name);

// returns the length of any identifier (e.g. name, function) starting at the beginning of str
static int identifier_length (const char* str);

/* increments str_ind until it reaches specified char is formula. returns true if character was found, false otherwise */
static bool goto_next_char( int *str_ind, const string &pw_formula, char ch);


/**** Function Implementations ****/
/* returns integer result according to specified non-piece-wise formula and data */
int parse_formula(std::string formula, const t_formula_data& mydata ){
	int result = -1;

	/* output in reverse-polish notation */
	vector<Formula_Object> rpn_output;

	/* now we have to run the shunting-yard algorithm to convert formula to reverse polish notation */
	formula_to_rpn( formula.c_str(), mydata, rpn_output );

	/* then we run an RPN parser to get the final result */
	result = parse_rpn_vector(rpn_output);

	return result;
}


/* EXPERIMENTAL:

   returns integer result according to specified piece-wise formula and data. the piecewise
   notation specifies different formulas that should be evaluated based on the index of
   the incoming wire in 'mydata'. for example the formula

       {0:(W/2)} t-1; {(W/2):W} t+1;

   indicates that the function "t-1" should be evaluated if the incoming wire index falls
   within the range [0,W/2) and that "t+1" should be evaluated if it falls within the
   [W/2,W) range. The piece-wise format is:

       {start_0:end_0} formula_0; ... {start_i;end_i} formula_i; ...
*/
int parse_piecewise_formula( const char *formula, const t_formula_data &mydata ){
	int result = -1;
	int str_ind = 0;
	int str_size = 0;

	int t = mydata.get_var_value("t");
	int tmp_ind_start = -1;
	int tmp_ind_count = -1;
	string substr;

	/* convert formula to string format */
	string pw_formula(formula);
	str_size = pw_formula.size();

	if (pw_formula[str_ind] != '{'){
		archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: the first character in piece-wise formula should always be '{'\n");
	}

	/* find the range to which t corresponds */
	/* the first character must be '{' as verified above */
	while (str_ind != str_size - 1){
		/* set to true when range to which wire number corresponds has been found */
		bool found_range = false;
		bool char_found = false;
		int range_start = -1;
		int range_end = -1;
		tmp_ind_start = -1;
		tmp_ind_count = -1;

		/* get the start of the range */
		tmp_ind_start = str_ind + 1;
		char_found = goto_next_char(&str_ind, pw_formula, ':');
		if (!char_found){
			archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", ':');
		}
		tmp_ind_count = str_ind - tmp_ind_start;			/* range start is between { and : */
		substr = pw_formula.substr(tmp_ind_start, tmp_ind_count);
		range_start = parse_formula(substr.c_str(), mydata);

		/* get the end of the range */
		tmp_ind_start = str_ind + 1;
		char_found = goto_next_char(&str_ind, pw_formula, '}');
		if (!char_found){
			archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", '}');
		}
		tmp_ind_count = str_ind - tmp_ind_start;			/* range end is between : and } */
		substr = pw_formula.substr(tmp_ind_start, tmp_ind_count);
		range_end = parse_formula(substr.c_str(), mydata);

		if (range_start > range_end){
			archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: range_start, %d, is bigger than range end, %d\n", range_start, range_end);
		}

		/* is the incoming wire within this range? (inclusive) */
		if ( range_start <= t && range_end >= t ){
			found_range = true;
		} else {
			found_range = false;
		}

		/* we're done if found correct range */
		if (found_range){
			break;
		}
		char_found = goto_next_char(&str_ind, pw_formula, '{');
		if (!char_found){
			archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", '{');
		}
	}
	/* the string index should never actually get to the end of the string because we should have found the range to which the
	   current wire number corresponds */
	if (str_ind == str_size-1){
		archfpga_throw( __FILE__, __LINE__, "parse_piecewise_formula: could not find a closing '}'?\n");
	}

	/* at this point str_ind should point to '}' right before the formula we're interested in starts */
	/* get the value corresponding to this formula */
	tmp_ind_start = str_ind + 1;
	goto_next_char(&str_ind, pw_formula, ';');
	tmp_ind_count = str_ind - tmp_ind_start;			/* formula is between } and ; */
	substr = pw_formula.substr(tmp_ind_start, tmp_ind_count);

	/* now parse the formula corresponding to the appropriate piece-wise range */
	result = parse_formula(substr.c_str(), mydata);

	return result;
}


/* increments str_ind until it reaches specified char in formula. returns true if character was found, false otherwise */
static bool goto_next_char( int *str_ind, const string &pw_formula, char ch){
	bool result = true;
	int str_size = pw_formula.size();
	if ((*str_ind) == str_size-1){
		archfpga_throw( __FILE__, __LINE__, "goto_next_char: passed-in str_ind is already at the end of string\n");
	}

	do{
		(*str_ind)++;
		if ( pw_formula[*str_ind] == ch ){
			/* found the next requested character */
			break;
		}

	} while ((*str_ind) != str_size-1);
	if ((*str_ind) == str_size-1 && pw_formula[*str_ind] != ch){
		result = false;
	}
	return result;
}


/* Parses the specified formula using a shunting yard algorithm (see wikipedia). The function's result
   is stored in the rpn_output vector in reverse-polish notation */
static void formula_to_rpn( const char* formula, const t_formula_data &mydata,
				vector<Formula_Object> &rpn_output ){

	stack<Formula_Object> op_stack;		/* stack for handling operators and brackets in formula */
	Formula_Object fobj;		 	/* for parsing formula objects */

	int ichar = 0;
	const char *ch = nullptr;
	/* go through formula and build rpn_output along with op_stack until \0 character is hit */
	while(true) {
		ch = &formula[ichar];

		if ('\0' == (*ch)){
			/* we're done */
			break;
		} else if (' ' == (*ch)){
			/* skip space */
		} else {
			/* parse the character */
			get_formula_object( ch, ichar, mydata, &fobj );
			switch (fobj.type){
				case E_FML_NUMBER:
					/* add to output vector */
					rpn_output.push_back( fobj );
					break;
				case E_FML_OPERATOR:
					/* operators may be pushed to op_stack or rpn_output */
					handle_operator( fobj, rpn_output, op_stack);
					break;
				case E_FML_BRACKET:
					/* brackets are only ever pushed to op_stack, not rpn_output */
					handle_bracket( fobj, rpn_output, op_stack);
					break;
				case E_FML_COMMA:
					handle_comma( fobj, rpn_output, op_stack);
					break;
				default:
					archfpga_throw( __FILE__, __LINE__, "in formula_to_rpn: unknown formula object type: %d\n", fobj.type);
					break;
			}
		}
		ichar++;
	}

	/* pop all remaining operators off of stack */
	Formula_Object fobj_dummy;
	while ( !op_stack.empty() ){
		fobj_dummy = op_stack.top();

		if (E_FML_BRACKET == fobj_dummy.type){
			archfpga_throw( __FILE__, __LINE__, "in formula_to_rpn: Mismatched brackets in user-provided formula\n");
		}

		rpn_output.push_back( fobj_dummy );
		op_stack.pop();
	}

	return;
}


/* Fills the formula object fobj according to specified character and mydata,
   which help determine which numeric value, if any, gets assigned to fobj
   ichar is incremented by the corresponding count if the need to step through the
   character array arises */
static void get_formula_object( const char *ch, int &ichar, const t_formula_data &mydata,
				 Formula_Object *fobj ){

	/* the character can either be part of a number, or it can be an object like W, t, (, +, etc
	   here we have to account for both possibilities */

    int id_len = identifier_length(ch);

    if (id_len != 0) {
        //We have a variable or function name
        std::string var_name(ch, id_len);

        if (is_function(var_name)) {
            fobj->type = E_FML_OPERATOR;
            if      (var_name == "min") fobj->data.op = E_OP_MIN;
            else if (var_name == "max") fobj->data.op = E_OP_MAX;
            else if (var_name == "gcd") fobj->data.op = E_OP_GCD;
            else if (var_name == "lcm") fobj->data.op = E_OP_LCM;
            else {
				archfpga_throw( __FILE__, __LINE__, "in get_formula_object: recognized function: %s\n", var_name.c_str());
            }

        } else {
            //A variable
            fobj->type = E_FML_NUMBER;
            fobj->data.num = mydata.get_var_value(var_name);
        }

        ichar += (id_len - 1); //-1 since ichar is incremented at end of loop in formula_to_rpn()

    } else if ( is_char_number(*ch) ){
		/* we have a number -- use atoi to convert */
		stringstream ss;
		while ( is_char_number(*ch) ){
			ss << (*ch);
			ichar++;
			ch++;
		}
		ichar --;
		fobj->type = E_FML_NUMBER;
		fobj->data.num = vtr::atoi(ss.str().c_str());
	} else {
		switch ((*ch)){
			case '+':
				fobj->type = E_FML_OPERATOR;
				fobj->data.op = E_OP_ADD;
				break;
			case '-':
				fobj->type = E_FML_OPERATOR;
				fobj->data.op = E_OP_SUB;
				break;
			case '/':
				fobj->type = E_FML_OPERATOR;
				fobj->data.op = E_OP_DIV;
				break;
			case '*':
				fobj->type = E_FML_OPERATOR;
				fobj->data.op = E_OP_MULT;
				break;
			case '(':
				fobj->type = E_FML_BRACKET;
				fobj->data.left_bracket = true;
				break;
			case ')':
				fobj->type = E_FML_BRACKET;
				fobj->data.left_bracket = false;
				break;
            case ',':
				fobj->type = E_FML_COMMA;
                break;
			default:
				archfpga_throw( __FILE__, __LINE__, "in get_formula_object: unsupported character: %c\n", *ch);
				break;
		}
	}

	return;
}


/* returns integer specifying precedence of passed-in operator. higher integer
   means higher precedence */
static int get_fobj_precedence( const Formula_Object &fobj ){
	int precedence = 0;

	if (E_FML_BRACKET == fobj.type || E_FML_COMMA == fobj.type){
		precedence = 0;
	} else if (E_FML_OPERATOR == fobj.type){
		t_operator op = fobj.data.op;
		switch (op){
			case E_OP_ADD: //fallthrough
			case E_OP_SUB:
				precedence = 2;
				break;
			case E_OP_MULT: //fallthrough
			case E_OP_DIV:
				precedence = 3;
				break;
            case E_OP_MIN: //fallthrough
            case E_OP_MAX: //fallthrough
            case E_OP_LCM: //fallthrough
            case E_OP_GCD: //fallthrough
                precedence = 4;
                break;
			default:
				archfpga_throw( __FILE__, __LINE__, "in get_fobj_precedence: unrecognized operator: %d\n", op);
				break;
		}
	} else {
		archfpga_throw( __FILE__, __LINE__, "in get_fobj_precedence: no precedence possible for formula object type %d\n", fobj.type);
	}

	return precedence;
}


/* Returns associativity of the specified operator */
static bool op_associativity_is_left( const t_operator &/*op*/ ){
	bool is_left = true;

	/* associativity is 'left' for all but the power operator, which is not yet implemented */
	//TODO:
	//if op is 'power' set associativity is_left=false and return

	return is_left;
}


/* used by the shunting-yard formula parser to deal with operators such as add and subtract */
static void handle_operator( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack){
	if ( E_FML_OPERATOR != fobj.type){
		archfpga_throw( __FILE__, __LINE__, "in handle_operator: passed in formula object not of type operator\n");
	}

	int op_pr = get_fobj_precedence( fobj );
	bool op_assoc_is_left = op_associativity_is_left( fobj.data.op );

	Formula_Object fobj_dummy;
	bool keep_going = false;
	do{
		/* here we keep popping operators off the stack onto back of rpn_output while
		   associativity of operator is 'left' and precedence op_pr = top_pr, or while
		   precedence op_pr < top_pr */

		/* determine whether we should keep popping operators off the op stack */
		if ( op_stack.empty() ){
			keep_going = false;
		} else {
			/* get precedence of top operator */
			int top_pr = get_fobj_precedence ( op_stack.top() );

			keep_going = ( (op_assoc_is_left && op_pr==top_pr)
					|| op_pr<top_pr );

			if (keep_going){
				/* pop top operator off stack onto the back of rpn_output */
				fobj_dummy = op_stack.top();
				rpn_output.push_back( fobj_dummy );
				op_stack.pop();
			}
		}

	} while (keep_going);

	/* place new operator object on top of stack */
	op_stack.push(fobj);

	return;
}


/* used by the shunting-yard formula parser to deal with brackets, ie '(' and ')' */
static void handle_bracket( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack ){
	if ( E_FML_BRACKET != fobj.type){
		archfpga_throw( __FILE__, __LINE__, "in handle_bracket: passed-in formula object not of type bracket\n");
	}

	/* check if left or right bracket */
	if ( fobj.data.left_bracket ){
		/* left bracket, so simply push it onto operator stack */
		op_stack.push(fobj);
	} else {
		bool keep_going = false;
		do{
			/* here we keep popping operators off op_stack onto back of rpn_output until a
			   left bracket is encountered */

			if ( op_stack.empty() ){
				/* didn't find an opening bracket - mismatched brackets */
				archfpga_throw( __FILE__, __LINE__, "Ran out of stack while parsing brackets -- bracket mismatch in user-specified formula\n");
				keep_going = false;
			}

			Formula_Object next_fobj = op_stack.top();
			if (E_FML_BRACKET == next_fobj.type){
				if (next_fobj.data.left_bracket){
					/* matching bracket found -- pop off stack and finish */
					op_stack.pop();
					keep_going = false;
				} else {
					/* should not find two right brackets without a left bracket in-between */
					archfpga_throw( __FILE__, __LINE__, "Mismatched brackets encountered in user-specified formula\n");
					keep_going = false;
				}
			} else if (E_FML_OPERATOR == next_fobj.type){
				/* pop operator off stack onto the back of rpn_output */
				Formula_Object fobj_dummy = op_stack.top();
				rpn_output.push_back( fobj_dummy );
				op_stack.pop();
				keep_going = true;
			} else {
				archfpga_throw( __FILE__, __LINE__, "Found unexpected formula object on operator stack: %d\n", next_fobj.type);
				keep_going = false;
			}
		} while (keep_going);
	}
	return;
}

/* used by the shunting-yard formula parser to deal with commas, ie ','. These occur in function calls*/
static void handle_comma( const Formula_Object &fobj, vector<Formula_Object> &rpn_output,
				stack<Formula_Object> &op_stack ){
	if ( E_FML_COMMA != fobj.type){
		archfpga_throw( __FILE__, __LINE__, "in handle_comm: passed-in formula object not of type comma\n");
	}

    //Commas are treated as right (closing) bracket since it completes a
    //sub-expression, except that we do not cause the left (opening) brack to
    //be popped

    bool keep_going = true;
    do {
        /* here we keep popping operators off op_stack onto back of rpn_output until a
           left bracket is encountered */

        if ( op_stack.empty() ){
            /* didn't find an opening bracket - mismatched brackets */
            archfpga_throw( __FILE__, __LINE__, "Ran out of stack while parsing comma -- bracket mismatch in user-specified formula\n");
            keep_going = false;
        }

        Formula_Object next_fobj = op_stack.top();
        if (E_FML_BRACKET == next_fobj.type){
            if (next_fobj.data.left_bracket){
                /* matching bracket found */
                keep_going = false;
            } else {
                /* should not find two right brackets without a left bracket in-between */
                archfpga_throw( __FILE__, __LINE__, "Mismatched brackets encountered in user-specified formula\n");
                keep_going = false;
            }
        } else if (E_FML_OPERATOR == next_fobj.type){
            /* pop operator off stack onto the back of rpn_output */
            Formula_Object fobj_dummy = op_stack.top();
            rpn_output.push_back( fobj_dummy );
            op_stack.pop();
            keep_going = true;
        } else {
            archfpga_throw( __FILE__, __LINE__, "Found unexpected formula object on operator stack: %d\n", next_fobj.type);
            keep_going = false;
        }

    } while (keep_going);

}

/* parses a reverse-polish notation vector corresponding to a switchblock formula
   and returns the integer result */
static int parse_rpn_vector( vector<Formula_Object> &rpn_vec ){
	int result = -1;

	/* first entry should always be a number */
	if (E_FML_NUMBER != rpn_vec[0].type){
		archfpga_throw( __FILE__, __LINE__, "parse_rpn_vector: first entry is not a number\n");
	}

	if (rpn_vec.size() == 1){
		/* if the vector size is 1 then we just have a number (which was verified above) */
		result = rpn_vec[0].data.num;
	} else {
		/* have numbers and operators */
		Formula_Object fobj;
		int ivec = 0;
		/* keep going until we have gone through the whole vector */
		while ( !rpn_vec.empty() ){

			/* keep going until we have hit an operator */
			do{
				ivec++;		/* first item should never be operator anyway */
				if (ivec == (int)rpn_vec.size()){
					archfpga_throw( __FILE__, __LINE__, "parse_rpn_vector(): found multiple numbers in formula, but no operator\n");
				}
			} while ( E_FML_OPERATOR != rpn_vec[ivec].type );

			/* now we apply the selected operation to the two previous entries */
			/* the result is stored in the object that used to be the operation */
			rpn_vec[ivec].data.num = apply_rpn_op( rpn_vec[ivec-2], rpn_vec[ivec-1], rpn_vec[ivec] );
			rpn_vec[ivec].type = E_FML_NUMBER;

			/* remove the previous two entries from the vector */
			rpn_vec.erase(rpn_vec.begin() + ivec - 2, rpn_vec.begin() + ivec - 0);
			ivec -= 2;

			/* if we're down to one element, we are done */
			if (1 == rpn_vec.size()){
				result = rpn_vec[ivec].data.num;
				rpn_vec.erase(rpn_vec.begin() + ivec);
			}
		}
	}

	return result;
}


/* applies operation specified by 'op' to the given arguments. arg1 comes before arg2 */
static int apply_rpn_op( const Formula_Object &arg1, const Formula_Object &arg2,
					const Formula_Object &op ){
	int result = -1;

	/* arguments must be numbers */
	if ( E_FML_NUMBER != arg1.type ||
	     E_FML_NUMBER != arg2.type){
		archfpga_throw( __FILE__, __LINE__, "in apply_rpn_op: one of the arguments is not a number\n");
	}

	/* check that op is actually an operation */
	if ( E_FML_OPERATOR != op.type ){
		archfpga_throw( __FILE__, __LINE__, "in apply_rpn_op: the object specified as the operation is not of operation type\n");
	}

	/* apply operation to arguments */
	switch (op.data.op){
		case E_OP_ADD:
			result = arg1.data.num + arg2.data.num;
			break;
		case E_OP_SUB:
			result = arg1.data.num - arg2.data.num;
			break;
		case E_OP_MULT:
			result = arg1.data.num * arg2.data.num;
			break;
		case E_OP_DIV:
			result = arg1.data.num / arg2.data.num;
			break;
        case E_OP_MAX:
            result = std::max(arg1.data.num, arg2.data.num);
            break;
        case E_OP_MIN:
            result = std::min(arg1.data.num, arg2.data.num);
            break;
        case E_OP_GCD:
            result = vtr::gcd(arg1.data.num, arg2.data.num);
            break;
        case E_OP_LCM:
            result = vtr::lcm(arg1.data.num, arg2.data.num);
            break;
		default:
			archfpga_throw( __FILE__, __LINE__, "in apply_rpn_op: invalid operation: %d\n", op.data.op);
			break;
	}

	return result;
}


/* checks if specified character represents an ASCII number */
static bool is_char_number ( const char ch ){
	bool result = false;

	if ( ch >= '0' && ch <= '9' ){
		result = true;
	} else {
		result = false;
	}

	return result;
}

static bool is_operator(const char ch) {
    switch(ch) {
        case '+': //fallthrough
        case '-': //fallthrough
        case '/': //fallthrough
        case '*': //fallthrough
        case ')': //fallthrough
        case '(': //fallthrough
        case ',':
            return true;
        default:
            return false;
    }
}

static bool is_function(std::string name) {
    if (name == "min"
        || name == "max"
        || name == "gcd"
        || name == "lcm") {
        return true;
    }
    return false;
}

//returns the length of the substring consisting of valid vairable characters from
//the start of the string
static int identifier_length (const char* str) {
    int ichar = 0;

    if (!str) return 0;

    while(str[ichar] != '\0') {

        //No whitespace
        if (str[ichar] == ' ') break;

        //Not an operator
        if (is_operator(str[ichar])) break;

        //First char must not be a number
        if (ichar == 0 && is_char_number(str[ichar])) break;

        ++ichar; //Next character
    }

    return ichar;
}


/* checks if the specified formula is piece-wise defined */
bool is_piecewise_formula( const char *formula ){
	bool result = false;
	/* if formula is piecewise, we expect '{' to be the very first character */
	if ('{' == formula[0]){
		result = true;
	} else {
		result = false;
	}
	return result;
}