/* parser.c
 * geg, a GTK+ Equation Grapher
 * David Bryant 1998
 */

/*
 * Corrected grammar
 * Kris Jurka 27/7/1999
 */

/*
 * Corrected more grammar
 * Torsten Landschoff 24/11/1999
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif /* HAVE_CONFIG_H */

#include <math.h>
#include "parser.h"
#include "tokeniser.h"
#include "log.h"

/*
 *
 * EBNF:
 *  <expr>     ::= +|- <term> { +|- <term> }
 *  <term>     ::= <product> { *|/ <product> }
 *  <product>  ::= <factor> { ^ <factor> }
 *  <factor>   ::= <number> | <function> | (<expr>)
 *  <number>   ::= <float> | x
 *  <function> ::= <function_name>(<expression>)
 */

static parse_tree *expr(void);
static parse_tree *term(void);
static parse_tree *factor(void);
static parse_tree *product(void);

static token_list *list_g;      /* global list, makes life easier */
static gint parse_error;	/* flag this when a parse error occurs */

/* some convenience functions follow, these stop seg faults and other stuff,
 * when the user enters un-parsable equations.
 * There is probably a fair bit of redundancy in the NULL pointer checking
 * but leave it there for now.
 */
static gint
token_type_is(gint type)
{
  if(!list_g)
    return(FALSE);
  return(list_g->type == type);
}

static gint
token_type(void)
{
  if(!list_g)
    return(EOE);
  return(list_g->type);
}

static gdouble
token_value(void)
{
  if(!list_g)
    return(0);
  return(list_g->value);
}

static void
get_next_token(void)
{
  if(list_g)
    list_g = list_g->next;
}

static void
skip_token(gint type)
{
  if(!list_g) {
    parse_error = TRUE;
    return;
  }
  else
    if(list_g->type != type)
      parse_error = TRUE;
  list_g = list_g->next;
}
/* end of convenience functions
 */

/* expr, starting non-terminal for generating parse tree
 */
static parse_tree *
expr(void)
{
  parse_tree *tree = NULL, *temp_tree;

  if(token_type_is(NUM) ||
     token_type_is(X)   ||
     token_type_is(FUN) ||
     token_type_is(SUB) ||	/* negate, (not minus) */
     token_type_is(LB)	||
     token_type_is(LCB) ||
     token_type_is(LSB)) {
    tree = term();
  }
  else {
    parse_error = TRUE;
    return(NULL);
  }

  while(token_type_is(ADD) ||
        token_type_is(SUB)) {
    temp_tree = tree;		/* save the old tree */
    tree = g_new(parse_tree, 1);
    tree->token.type = token_type();
    tree->left = temp_tree;	/* push old tree down a 'left branch' */
    get_next_token();
    tree->right = term();	/* 'right branch' */
  }

  if((tree == NULL) || (token_type_is(ERROR)))
    parse_error = TRUE;
  return(tree);
}

/* term, non-terminal
 */
static parse_tree *
term(void)
{
  parse_tree *tree = NULL, *temp_tree;

  if(token_type_is(NUM) ||
     token_type_is(X)   ||
     token_type_is(FUN) ||
     token_type_is(SUB) ||	/* negate, (not minus) */
     token_type_is(LB)	||
     token_type_is(LCB) ||
     token_type_is(LSB)) {
    if(token_type_is(SUB)) {	/* negate */
      tree = g_new(parse_tree, 1);
      tree->token.type = SUB;	/* token_type(); */
      tree->left = g_new(parse_tree, 1);
      tree->left->token.type = NUM;
      tree->left->token.value = 0;
      tree->left->left = NULL;
      tree->left->right = NULL;
      get_next_token();		/* skip the minus-sign */
      tree->right = product();
    }
    else {
      tree = product();
    }
  }
  else {
    parse_error = TRUE;
    return(NULL);
  }

  while(token_type_is(MUL) ||
        token_type_is(DIV) ||
	token_type_is(X)   ||
	token_type_is(FUN) ||
	token_type_is(LB)  ||
	token_type_is(LCB) ||
	token_type_is(LSB)) {
    if(token_type_is(X)   ||	/* assume multiplication */
       token_type_is(FUN) ||
       token_type_is(LB)  ||
       token_type_is(LCB) ||
       token_type_is(LSB)) {
      temp_tree = tree;
      tree = g_new(parse_tree, 1);
      tree->token.type = MUL;
      tree->left = temp_tree;
      tree->right = term();
    }
    else {
      temp_tree = tree;
      tree = g_new(parse_tree, 1);
      tree->token.type = token_type();
      tree->left = temp_tree;
      get_next_token();
      tree->right = term();
    }
  }

  if(tree == NULL)
    parse_error = TRUE;
  return(tree);
}

/* product, non-terminal
 */
static parse_tree *
product(void)
{
  parse_tree *tree = NULL, *temp_tree;

  if(token_type_is(NUM) ||
     token_type_is(X)   ||
     token_type_is(FUN) ||
     token_type_is(LB)	||
     token_type_is(LCB) ||
     token_type_is(LSB)) {
    tree = factor();
  }
  else {
    parse_error = TRUE;
    return(NULL);
  }

  while(token_type_is(POW)) {
    temp_tree = tree;
    tree = g_new(parse_tree, 1);
    tree->token.type = token_type();
    tree->left = temp_tree;
    get_next_token();
    tree->right = product();
  }

  if(tree == NULL)
    parse_error = TRUE;
  return(tree);
}

/* factor, non-terminal
 * negation is a bit of a hack, if we get a negator, we create a left tree,
 * with number=0, and a negation node, and continue down the right tree....
 * ie, we subtract the following factor from 0
 */
static parse_tree *
factor(void)
{
  parse_tree *tree;

  if(token_type_is(NUM) ||
     token_type_is(X)) {
    tree = g_new(parse_tree, 1);
    tree->left = NULL;
    tree->right = NULL;
    tree->token.type = token_type();
    tree->token.value = token_value();
    get_next_token();
    return(tree);
  }
  else if(token_type_is(FUN)) {
    tree = g_new(parse_tree, 1);
    tree->right = NULL;
    tree->token.type = token_type();
    tree->token.func = list_g->func;
    skip_token(FUN);
    if(token_type_is(LB)) {
      skip_token(LB);
      tree->left = expr();
      skip_token(RB);
    }
    else if(token_type_is(LSB)) {
      skip_token(LSB);
      tree->left = expr();
      skip_token(RSB);
    }
    else {
      skip_token(LCB);
      tree->left = expr();
      skip_token(RCB);
    }
    return(tree);
  }
  else if(token_type_is(LB)) {
    skip_token(LB);
    tree = expr();
    skip_token(RB);
    return(tree);
  }
  else if(token_type_is(LSB)) {
    skip_token(LSB);
    tree = expr();
    skip_token(RSB);
    return(tree);
  }
  else if(token_type_is(LCB)) {
    skip_token(LCB);
    tree = expr();
    skip_token(RCB);
    return(tree);
  }
  else {
    parse_error = TRUE;
    return(NULL);
  }
}

/* make_parse_tree, creates a parse tree from a list of tokens
 */
parse_tree *
make_parse_tree(token_list *list)
{
  parse_tree *tree = NULL;
  parse_error = FALSE;

  list_g = list;	/* assign global list */

  tree = expr();

  if((parse_error)||(!token_type_is(EOE)))
    return(NULL);
  return(tree);
}

/* free_tree, frees the memory allocated to the tree using a recursive
 * algorithm
 */
void
free_tree(parse_tree *tree)
{
  if(tree->left)
    free_tree(tree->left);
  if(tree->right)
    free_tree(tree->right);
  g_free(tree);
  return;
}

/* eval_tree,       this function recursively evaluates the parse tree using
 * LRN notation. Currently only unary functions are supported, where the
 * argument to the function is assumed to be the left child branch of the
 * function node.... in the future binary functions might exist, like mod,
 * where the arguments are the children branches from left to right
 */
double
eval_tree(parse_tree *tree, double x)
{
  switch(tree->token.type) {
  case ADD:
    return(eval_tree(tree->left, x) + eval_tree(tree->right, x));
  case SUB:
    return(eval_tree(tree->left, x) - eval_tree(tree->right, x));
  case MUL:
    return(eval_tree(tree->left, x) * eval_tree(tree->right, x));
  case DIV:
    return(eval_tree(tree->left, x) / eval_tree(tree->right, x));
  case POW:
    return(pow(eval_tree(tree->left, x), eval_tree(tree->right, x)));
  case FUN:
    return(tree->token.func(eval_tree(tree->left, x)));
  case NUM:
    return(tree->token.value);
  case X:
    return(x);
  default:
    write_log(NULL, "Eval Error");
    return(0);
  }
}