#include "dmeval.h"
#include <stdio.h>
#include <math.h>

#define DM_MAX_ID_LEN  16
#define DM_MAX_BUF     512
#define DM_STACK_SIZE  512

static DMValue int_clip(DMValue v)
{
    return (v < -1.0f) ? -1.0f : ((v > 1.0f) ? 1.0f : v);
}


/* Some basic functions
 */
static const DMEvalId dm_eval_basic[] =
{
    { "sin",  ID_FUNC, sin, NULL },
    { "cos",  ID_FUNC, cos, NULL },
    { "clip", ID_FUNC, int_clip, NULL },
};

static const int ndm_eval_basic = sizeof(dm_eval_basic) / sizeof(dm_eval_basic[0]);


void dm_eval_err_v(DMEvalContext *ev, const char *fmt, va_list ap)
{
#if 1
    char *tmp = dm_strdup_vprintf(fmt, ap);
    
    ev->err = TRUE;

    if (ev->errStr != NULL)
    {
        ev->errStr = dm_strdup_printf("%s%s", ev->errStr, tmp);
        dmFree(tmp);
    }
    else
        ev->errStr = tmp;
#else
    vfprintf(stdout, fmt, ap);
#endif
}


void dm_eval_err(DMEvalContext *ev, const char *fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    dm_eval_err_v(ev, fmt, ap);
    va_end(ap);
}


DMEvalId *dm_eval_find_id(DMEvalContext *ev, const char *name)
{
    int i;
    if (ev->ids == NULL)
        return NULL;

    for (i = 0; i < ev->nids; i++)
        if (strcmp(ev->ids[i].name, name) == 0)
            return &(ev->ids[i]);
    
    return NULL;
}


static DMEvalId *dm_eval_add_id(DMEvalContext *ev, const char *name, const int type)
{
    DMEvalId *id = dm_eval_find_id(ev, name);
    if (id != NULL)
        return NULL;

    ev->ids = dmRealloc(ev->ids, sizeof(DMEvalId) * (ev->nids + 1));
    if (ev->ids == NULL)
    {
        dm_eval_err(ev, "Could not reallocate eval ids array (#%d). Fatal error.\n", ev->nids + 1);
        return NULL;
    }
    
    id = &(ev->ids[ev->nids]);
    ev->nids++;

    id->name = dm_strdup(name);
    id->type = type;
    id->func = NULL;
    id->var = NULL;
    
    return id;
}


DMEvalId *dm_eval_add_var(DMEvalContext *ev, const char *name, DMValue *var)
{
    DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
    if (id == NULL)
        return NULL;
    
    id->var = var;
    return id;
}


DMEvalId *dm_eval_add_func(DMEvalContext *ev, const char *name, DMValue (*func)(DMValue))
{
    DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
    if (id == NULL)
        return NULL;
    
    id->func = func;
    return id;
}



DMEvalContext *dm_eval_new(void)
{
    int i;
    DMEvalContext *ev = dmCalloc(1, sizeof(DMEvalContext));

    if (ev == NULL)
        return NULL;

    for (i = 0; i < ndm_eval_basic; i++)
    {
        const DMEvalId *id = &dm_eval_basic[i];
        DMEvalId *nid = dm_eval_add_id(ev, id->name, id->type);
        nid->func = id->func;
    }

    return ev;
}

void dm_eval_free(DMEvalNode *node)
{
    while (node != NULL)
    {
        DMEvalNode *next = node->next;

        if (node->subexpr != NULL)
            dm_eval_free(node->subexpr);

        dmFree(node);
        node = next;
    }
}


void dm_eval_clear_err(DMEvalContext *ev)
{
    if (ev == NULL)
        return;
    
    dmFree(ev->errStr);
    ev->err = FALSE;
    ev->errStr = NULL;
}


void dm_eval_close(DMEvalContext *ev)
{
    int i;

    if (ev == NULL)
        return;

    for (i = 0; i < ev->nids; i++)
        dmFree(ev->ids[i].name);

    dmFree(ev->ids);
    dm_eval_clear_err(ev);
    dmFree(ev);
}


static DMEvalNode *dm_eval_pop_node(DMEvalNode **list)
{
    DMEvalNode *node;

    if (*list == NULL)
        return NULL;

    node = (*list)->prev;

    if (*list != node)
    {
        node->prev->next = NULL;
        (*list)->prev = node->prev;
    }
    else
        *list = NULL;

    return node;
}


static DMEvalNode *dm_eval_insert_node(DMEvalNode **list, DMEvalNode *node)
{
    if (*list != NULL)
    {
        node->prev = (*list)->prev;
        (*list)->prev->next = node;
        (*list)->prev = node;
    }
    else
    {
        *list = node;
        node->prev = *list;
    }

    node->next = NULL;
    return node;
}


static DMEvalNode *dm_eval_push_node(DMEvalNode **list, DMEvalNode *src)
{
    DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
    if (node == NULL)
        return NULL;

    node->op = src->op;
    node->val = src->val;
    node->id = src->id;
    node->subexpr = src->subexpr;

    return dm_eval_insert_node(list, node);
}


static DMEvalNode *dm_eval_add_node(DMEvalNode **list, const int op)
{
    DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
    if (node == NULL)
        return NULL;

    node->op = op;

    return dm_eval_insert_node(list, node);
}


enum
{
    PARSE_NONE    = 0x0000,
    PARSE_START   = 0x1000,
    PARSE_END     = 0x2000,
    PARSE_ERROR   = 0x8000,

    PARSE_IDENT   = 0x0001,
    PARSE_WS      = 0x0002,
    PARSE_CONST   = 0x0004,
    PARSE_OPER    = 0x0008,
    PARSE_SUBEXPR = 0x0010,
};

#define DM_CHECK(x) { if (mode & PARSE_ ## x ) { if (str[0]) strcat(str, " or "); strcat(str, # x ); } }

static char *dm_get_mode(int mode)
{
    char str[128] = "";
    

    DM_CHECK(START);
    DM_CHECK(END);
    DM_CHECK(IDENT);
    DM_CHECK(WS);
    DM_CHECK(CONST);
    DM_CHECK(OPER);
    DM_CHECK(SUBEXPR);
            
    return dm_strdup(str);
}


static void dm_set_mode(DMEvalContext *ev, const int mode)
{
    if (mode != PARSE_ERROR && mode != PARSE_START &&
        ev->expect != PARSE_NONE &&
        (mode & ev->expect) == 0)
    {
        char *tmp1 = dm_get_mode(ev->expect),
             *tmp2 = dm_get_mode(mode);

        dm_eval_err(ev, "Expected [%s], got %s.\n", tmp1, tmp2);
        dmFree(tmp1);
        dmFree(tmp2);
    }

    ev->prev = ev->mode;
    ev->mode = mode;
}


static int dm_eval_parse_expr_do(DMEvalContext *ev, DMEvalNode **list, char **str, int depth)
{
    char *c = *str;
    char tmpStr[DM_MAX_BUF + 2];
    int tmpStrLen = 0;
    DMEvalNode *node = NULL, *func = NULL;
    BOOL first = FALSE, decimal = FALSE;

    ev->expect = PARSE_CONST | PARSE_IDENT | PARSE_SUBEXPR;
    ev->mode = PARSE_START;
    
    while (ev->mode != PARSE_ERROR && ev->mode != PARSE_END)
    {
    switch (ev->mode)
    {
        case PARSE_WS:
            // Skip whitespace
            if (isspace(*c))
                c++;
            else
                dm_set_mode(ev, PARSE_START);
            break;

        case PARSE_SUBEXPR:
            {
                char *tmp = c + 1;

                ev->expect = PARSE_SUBEXPR | PARSE_IDENT | PARSE_CONST;

                if (func != NULL)
                {
                    if (dm_eval_parse_expr_do(ev, &(func->subexpr), &tmp, depth + 1) != 0)
                    {
                        dm_eval_err(ev, "Function argument subexpression starting at '%s' contained errors.\n", c);
                        dm_set_mode(ev, PARSE_ERROR);
                    }

                    func = NULL;
                }
                else
                {
                    if ((node = dm_eval_add_node(list, OP_SUBEXPR)) == NULL)
                        dm_set_mode(ev, PARSE_ERROR);
                    else
                    if (dm_eval_parse_expr_do(ev, &(node->subexpr), &tmp, depth + 1) != 0)
                    {
                        dm_eval_err(ev, "Subexpression starting at '%s' contained errors.\n", c);
                        dm_set_mode(ev, PARSE_ERROR);
                    }
                }
                if (ev->mode != PARSE_ERROR)
                {
                    dm_set_mode(ev, PARSE_START);
                    ev->expect = PARSE_OPER | PARSE_END;
                    c = tmp;
                }
            }
            break;
            
        case PARSE_START:
            // Start
            if (*c == 0)
                dm_set_mode(ev, PARSE_END);

            else if (isspace(*c))
            {
                ev->mode = PARSE_WS;
            }

            else if (*c == ')')
            {
                if (depth > 0)
                    dm_set_mode(ev, PARSE_END);
                else
                {
                    dm_eval_err(ev, "Invalid nesting near '%s' (depth %d).\n", c, depth);
                    dm_set_mode(ev, PARSE_ERROR);
                }
                c++;
            }

            else if (*c == '(')
                dm_set_mode(ev, PARSE_SUBEXPR);

            else if (strchr("+-*/<>%&|!^", *c))
                dm_set_mode(ev, PARSE_OPER);

            else if (isdigit(*c) || *c == '.')
                dm_set_mode(ev, PARSE_CONST);

            else if (isalpha(*c) || *c == '_')
                dm_set_mode(ev, PARSE_IDENT);
            
            else
            {
                dm_eval_err(ev, "Syntax error near '%s' (depth %d).\n", c, depth);
                dm_set_mode(ev, PARSE_ERROR);
            }

            first = TRUE;
            break;
        
        case PARSE_CONST:
            if (first)
            {
                first = FALSE;
                decimal = FALSE;
                tmpStrLen = 0;
                
                if (isdigit(*c) || *c == '-' || *c == '+' || *c == '.')
                {
                    if (*c == '.')
                        decimal = TRUE;
                    tmpStr[tmpStrLen++] = *c++;
                }
                else
                {
                    dm_eval_err(ev, "Invalid constant expression near '%s'.\n", c);
                    dm_set_mode(ev, PARSE_ERROR);
                }
            }
            else
            {
                if (isdigit(*c) || (*c == '.' && !decimal))
                {
                    if (*c == '.')
                        decimal = TRUE;
                    tmpStr[tmpStrLen++] = *c++;
                }
                else
                {
                    tmpStr[tmpStrLen] = 0;

                    if ((node = dm_eval_add_node(list, OP_CONST)) == NULL)
                    {
                        dm_set_mode(ev, PARSE_ERROR);
                        break;
                    }
                    
                    node->val = atof(tmpStr);
                    dm_set_mode(ev, PARSE_START);
                    ev->expect = PARSE_OPER | PARSE_END;
                }
            }
            break;

        case PARSE_OPER:
            {
                int op = OP_NONE;

                switch (*c)
                {
                    case '+': op = OP_ADD; c++; break;
                    case '-': op = OP_SUB; c++; break;
                    case '*': op = OP_MUL; c++; break;
                    case '/': op = OP_DIV; c++; break;
                    case '%': op = OP_MOD; c++; break;
                    case '&': op = OP_AND; c++; break;
                    case '|': op = OP_OR; c++; break;
                    case '>':
                        if (c[1] == '>')
                        {
                            c += 2;
                            op = OP_RSHIFT;
                        }
                        else
                        {
                            dm_eval_err(ev, "Syntax error near '%s'.\n", c);
                            dm_set_mode(ev, PARSE_ERROR);
                        }
                        break;
                        
                    case '<':
                        if (c[1] == '<')
                        {
                            c += 2;
                            op = OP_LSHIFT;
                        }
                        else
                        {
                            dm_eval_err(ev, "Syntax error near '%s'.\n", c);
                            dm_set_mode(ev, PARSE_ERROR);
                        }
                        break;

                    default:
                        dm_eval_err(ev, "Unknown operator '%c'.\n", *c);
                        dm_set_mode(ev, PARSE_ERROR);
                }

                if (op != OP_NONE)
                {
                    if ((node = dm_eval_add_node(list, op)) != NULL)
                    {
                        ev->expect = PARSE_IDENT | PARSE_CONST | PARSE_SUBEXPR;
                        dm_set_mode(ev, PARSE_START);
                    }
                    else
                        dm_set_mode(ev, PARSE_ERROR);
                }
            }
            break;

        case PARSE_IDENT:
            if (isalnum(*c) || *c == '_')
            {
                if (first)
                {
                    tmpStrLen = 0;
                    first = FALSE;
                }

                if (tmpStrLen < DM_MAX_ID_LEN)
                    tmpStr[tmpStrLen++] = *c++;
                else
                {
                    tmpStr[tmpStrLen] = 0;
                    dm_eval_err(ev, "Identifier too long! ('%s')\n", tmpStr);
                }
            }
            else
            {
                tmpStr[tmpStrLen] = 0;
                DMEvalId *id = dm_eval_find_id(ev, tmpStr);
                if (id != NULL)
                {
                    if ((node = dm_eval_add_node(list, id->type == ID_FUNC ? OP_FUNC : OP_VAR)) != NULL)
                    {
                        node->id = id;
                        if (id->type == ID_FUNC)
                        {
                            func = node;
                            ev->expect = PARSE_SUBEXPR;
                        }
                        else
                            ev->expect = PARSE_END | PARSE_OPER;

                        dm_set_mode(ev, PARSE_START);
                    }
                    else
                        dm_set_mode(ev, PARSE_ERROR);
                }
                else
                {
                    dm_eval_err(ev, "No such identifier '%s'.\n", tmpStr);
                    dm_set_mode(ev, PARSE_ERROR);
                }
            }
            break;
    }
    }

    *str = c;

    return (ev->mode == PARSE_ERROR) ? -1 : 0;
}


int dm_eval_parse_expr(DMEvalContext *ev, char *expr, DMEvalNode **result)
{
    int ret;

    if (ev == NULL || result == NULL)
        return -1;

    ret = dm_eval_parse_expr_do(ev, result, &expr, 0);
    
    return ret;
}


static const char *dm_oper_names[OP_NOPERS] =
{
    "NONE",
    "+",
    "-",
    "*",
    "/",
    "%",
    
    "<<",
    ">>",
    
    "&",
    "|",
    "^",
    
    "FUNC",
    "VAR",
    "SUBEXPR",
    "CONST"
};


static void dm_print_optree_do(DMEvalContext *ev, DMEvalNode *node, const int level)
{
    while (node != NULL)
    {
        switch (node->op)
        {
            case OP_FUNC:
                printf("%s(", node->id != NULL ? node->id->name : "?ERROR");
                dm_print_optree_do(ev, node->subexpr, level + 1);
                printf(")");
                break;

            case OP_VAR:
                printf("%s", node->id != NULL ? node->id->name : "?ERROR");
                break;

            case OP_CONST:
                printf("%.1f", node->val);
                break;

            case OP_SUBEXPR:
                printf("(");
                if (node->subexpr != NULL)
                    dm_print_optree_do(ev, node->subexpr, level + 1);
                else
                    printf("?ERROR");
                printf(")");
                break;

            default:
                if (node->op > 0 && node->op < OP_NOPERS)
                    printf("%s", dm_oper_names[node->op]);
                else
                    printf("ERROR!");
                break;
        }
        node = node->next;
    }
}


void dm_print_optree(DMEvalContext *ev, DMEvalNode *node)
{
    dm_print_optree_do(ev, node, 0);
    printf("\n");
}


/*
    operator precedence:
      HIGHEST
      "()"
      
      "*"
      "/"
      "%"
      
      "+"
      "-"
      
      "<<"
      ">>"
      
      "&"
      "^"
      "|"
      LOWEST
*/

int dm_eval_reorder(DMEvalContext *ev, DMEvalNode *node, DMEvalNode **result)
{
    DMEvalNode *list = NULL;

    while (node != NULL)
    {
        DMEvalNode *tmp;

        switch (node->op)
        {
            case OP_SUBEXPR:
            case OP_FUNC:
                if ((tmp = dm_eval_push_node(&list, node)) == NULL)
                    return -1;

                if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
                    return -2;
                break;

            case OP_MUL:
            case OP_DIV:
            case OP_MOD:
                if ((tmp = dm_eval_pop_node(&list)) != NULL)
                {
                    DMEvalNode *sub;

                    if ((sub = dm_eval_add_node(&list, OP_SUBEXPR)) == NULL)
                        return -3;

                    dm_eval_push_node(&(sub->subexpr), tmp);
                    dm_eval_add_node(&(sub->subexpr), node->op);
                    node = node->next;
                    if (node != NULL)
                    {
                        if (node->op == OP_FUNC || node->op == OP_SUBEXPR)
                        {
                            if ((tmp = dm_eval_push_node(&(sub->subexpr), node)) == NULL)
                                return -178;
                            
                            if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
                                return -66;
                        }
                        else
                            dm_eval_push_node(&(sub->subexpr), node);
                    }
                    else
                        return -72;
                }
                else
                    return -24;
                break;
            
            case OP_LSHIFT:
            case OP_RSHIFT:

            case OP_ADD:
            case OP_SUB:
            
            case OP_AND:
            case OP_XOR:
            case OP_OR:

            case OP_VAR:
            case OP_CONST:
                if (dm_eval_push_node(&list, node) == NULL)
                    return -32;
                break;

            default:
                dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
                return -4;
        }
        
        node = node->next;
    }

    *result = list;
    return 0;
}


static int dm_eval_get(DMEvalContext *ev, DMEvalNode *node, DMValue *result)
{
    DMValue tmp;
    
    if (node == NULL)
        return -32;
    
    switch (node->op)
    {
        case OP_VAR:
            *result = *(node->id->var);
            break;

        case OP_CONST:
            *result = node->val;
            break;

        case OP_SUBEXPR:
            if (dm_eval_exec(ev, node->subexpr, result) != 0)
                return -1;
            break;
        
        case OP_FUNC:
            if (dm_eval_exec(ev, node->subexpr, &tmp) != 0)
                return -1;
            
            *result = node->id->func(tmp);
            break;

        default:
            return -16;
    }

    return 0;
}


int dm_eval_exec(DMEvalContext *ev, DMEvalNode *tree, DMValue *presult)
{
    DMValue result;
    DMEvalNode *node = tree;

    while (node != NULL)
    {
        DMValue tmp;

        switch (node->op)
        {
            case OP_LSHIFT:
            case OP_RSHIFT:
            
            case OP_AND:
            case OP_XOR:
            case OP_OR:

            case OP_MUL:
            case OP_DIV:
            case OP_MOD:
                if (dm_eval_get(ev, node->next, &tmp) != 0)
                    return -6;
                
                switch (node->op)
                {
                    case OP_DIV:
                        if (tmp == 0)
                        {
                            dm_eval_err(ev, "Division by zero.\n");
                            return -1;
                        }
                        result /= tmp;
                        break;

                    case OP_MUL:     result  *= tmp; break;

                    case OP_MOD:
                        if (tmp == 0)
                        {
                            dm_eval_err(ev, "Division by zero.\n");
                            return -1;
                        }
                        result = DMCONVTYPE result % DMCONVTYPE tmp;
                        break;

                    case OP_LSHIFT:  result = DMCONVTYPE result << DMCONVTYPE tmp; break;
                    case OP_RSHIFT:  result = DMCONVTYPE result >> DMCONVTYPE tmp; break;

                    case OP_AND:     result = DMCONVTYPE result & DMCONVTYPE tmp; break;
                    case OP_OR:      result = DMCONVTYPE result | DMCONVTYPE tmp; break;
                    case OP_XOR:     result = DMCONVTYPE result ^ DMCONVTYPE tmp; break;
                }
                
                node = node->next;
                break;
            
            case OP_ADD:
            case OP_SUB:
                if (dm_eval_get(ev, node->next, &tmp) != 0)
                    return -6;
                
                switch (node->op)
                {
                    case OP_ADD: result += tmp; break;
                    case OP_SUB: result -= tmp; break;
                }

                node = node->next;
                break;

            default:
                if (dm_eval_get(ev, node, &result) != 0)
                {
                    dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
                    return -4;
                }
        }
        
        node = node->next;
    }

    *presult = result;
    return 0;
}