/* vi:set ts=4 sw=4:

  cparse.c version 0.2.1
  
    Copyright (c) 1999 Minero Aoki <aamine@dp.u-netsurf.ne.jp>
  
    This library is free software.
    You can distribute/modify this program under the terms of
    the GNU Lesser General Public Lisence version 2 or later.

*/

#include <stdio.h>
#include "ruby.h"

#define DFLT_TOK -1
#define ERR_TOK   1
#define FINAL_TOK 0

#define vDFLT_TOK  INT2FIX(DFLT_TOK)
#define vERR_TOK   INT2FIX(ERR_TOK)
#define vFINAL_TOK INT2FIX(FINAL_TOK)

static VALUE RaccBug;

static ID id_yydebug;
static ID id_nexttoken;
static ID id_onerror;
static ID id_noreduce;

static ID id__shift;
static ID id__reduce;
static ID id__accept;


#ifdef DEBUG
# define D(code) if (in_debug) code
#else
# define D(code)
#endif


#define STACK_INIT_LEN 64
#define INIT_STACK(s) \
    s = rb_ary_new2(STACK_INIT_LEN);

#define PUSH(s, i) \
    rb_ary_store(s, RARRAY(s)->len, i)

#define POP(s) \
    RARRAY(s)->len--

/* bit slower but safe
    rb_ary_pop(s) */

#define LAST_I(s) \
    RARRAY(s)->ptr[RARRAY(s)->len - 1];

#define GET_TAIL(s, leng) \
    rb_ary_new4(leng, RARRAY(s)->ptr + RARRAY(s)->len - leng)

#define CUT_TAIL(arr, leng) \
   RARRAY(arr)->len -= leng;

/* bit slower but safe
if (1) {                    \
    long i;                 \
    for (i = leng; i; i--)  \
        rb_ary_pop(arr);    \
}
*/


#define GET_POINTER(pointer, table, state, retvar) \
if (1) {                                                              \
    if (state < 0 || state >= RARRAY(pointer)->len)                   \
      rb_raise(RaccBug, "[Racc Bug] illegal state: %ld", state);      \
    tmp = RARRAY(pointer)->ptr[state];                                \
    retvar = FIX2LONG(tmp);                                           \
    if (retvar < 0 || retvar > RARRAY(table)->len - 2)                \
      rb_raise(RaccBug, "[Racc Bug] illegal table ptr: %ld", retvar); \
}

#define SEARCH(table, i, t, retvar) \
if (1) {                                                         \
    if (i < 0 || i > RARRAY(table)->len - 2)                     \
      rb_raise(RaccBug, "[Racc Bug] illegal table ptr: %ld", i); \
    while (1) {                                                  \
        VALUE tmp = RARRAY(table)->ptr[i];                       \
        if (tmp == t || tmp == vDFLT_TOK) {                      \
            tmp = RARRAY(table)->ptr[i+1];                       \
            retvar = FIX2LONG(tmp);                              \
            break;                                               \
        }                                                        \
        i += 2;                                                  \
    }                                                            \
}


struct cp_params {
    VALUE parser;
    VALUE action_table;
    VALUE action_ptr;
    VALUE goto_table;
    VALUE goto_ptr;
    VALUE reduce_table;
    VALUE token_table;

    VALUE state;
    long curstate;
    VALUE vstack;
    VALUE tstack;
};


static void
do_reduce(v, ruleno, debug)
    struct cp_params *v;
    long ruleno;
    int debug;
{
    VALUE reduce_to, reduce_len, method_id;
    long len;
    ID mid;
    VALUE tmp, tmp_t, tmp_v;
    long ltmp, i;

    reduce_len = RARRAY(v->reduce_table)->ptr[ruleno];
    reduce_to  = RARRAY(v->reduce_table)->ptr[ruleno+1];
    method_id  = RARRAY(v->reduce_table)->ptr[ruleno+2];
    len = FIX2LONG(reduce_len);
    mid = (ID)FIX2LONG(method_id);

    if (len == 0) {
        tmp = Qnil;
        if (mid != id_noreduce)
            tmp_v = rb_ary_new();
        if (debug)
            tmp_t = rb_ary_new();
    }
    else {
        if (mid != id_noreduce) {
            tmp_v = GET_TAIL(v->vstack, len);
            tmp = RARRAY(tmp_v)->ptr[0];
        }
        else {
            tmp = RARRAY(v->vstack)->ptr[ RARRAY(v->vstack)->len - len ];
        }
        CUT_TAIL(v->vstack, len);
        if (debug) {
            tmp_t = GET_TAIL(v->tstack, len);
            CUT_TAIL(v->tstack, len);
        }
        CUT_TAIL(v->state, len);
    }

    /* method call must be done before tstack.push */
    if (mid != id_noreduce) {
        tmp = rb_funcall(v->parser, mid,
                         3, tmp_v, v->vstack, tmp);
    }
    PUSH(v->vstack, tmp);
    if (debug) {
        PUSH(v->tstack, reduce_to);
        rb_funcall(v->parser, id__reduce,
                   3, tmp_t, reduce_to, v->tstack);
    }

    if (RARRAY(v->state)->len == 0) {
        rb_raise(RaccBug, "state stack unexpected empty");
    }
    tmp = LAST_I(v->state);
    ltmp = FIX2LONG(tmp);
    GET_POINTER(v->goto_ptr, v->goto_table, ltmp, i);
    SEARCH(v->goto_table, i, reduce_to, ltmp);
    if (ltmp < 0) {
        rb_raise(RaccBug,
          "[Racc Bug] wrong goto: state=%ld, goto=%ld", v->curstate, ltmp);
    }
    v->curstate = ltmp;
    PUSH(v->state, INT2FIX(ltmp));
}


#define REDUCE(v, act) \
    do_reduce(&v, -act * 3, debug)

#define SHIFT(v, act, tok, val) \
    PUSH(v.vstack, val);                       \
    if (debug) {                               \
        PUSH(v.tstack, tok);                   \
        rb_funcall(v.parser, id__shift,        \
                   2, tok, v.tstack);          \
    }                                          \
    v.curstate = act;                          \
    PUSH(v.state, INT2FIX(v.curstate));

#define ACCEPT(v) \
    if (debug) rb_funcall(v.parser, id__accept, 0); \
    return RARRAY(v.vstack)->ptr[0];

static VALUE
raccparse(parser,
          action_table, action_ptr, goto_table, goto_ptr,
          reduce_table, token_table, shn, rdn, indebug)
    VALUE parser,
          action_table, action_ptr, goto_table, goto_ptr,
          reduce_table, token_table, shn, rdn, indebug;
{
    VALUE debugp;
    int debug, in_debug;
    struct cp_params v;
    long shift_n, reduce_n;

    long act;
    int read_next;
    VALUE in_tok;    /* internal format token (Fixnum) */
    VALUE tok, val;  /* external format token and value (any) */

    long nerr, errstatus;

    /* --------------------------
       initialize local values
    -------------------------- */

    D(in_debug = RTEST(indebug));

    debugp = rb_ivar_get(parser, id_yydebug);
    debug = RTEST(debugp);

    D(puts("start cparse"));

    Check_Type(action_table, T_ARRAY);
    Check_Type(action_ptr, T_ARRAY);
    Check_Type(goto_table, T_ARRAY);
    Check_Type(goto_ptr, T_ARRAY);
    Check_Type(reduce_table, T_ARRAY);
    Check_Type(token_table, T_HASH);
    v.parser = parser;
    v.action_table = action_table;
    v.action_ptr   = action_ptr;
    v.goto_table   = goto_table;
    v.goto_ptr     = goto_ptr;
    v.reduce_table = reduce_table;
    v.token_table  = token_table;

    shift_n  = NUM2LONG(shn);
    reduce_n = NUM2LONG(rdn);

    if (debug) INIT_STACK(v.tstack);
    INIT_STACK(v.vstack);
    INIT_STACK(v.state);
    v.curstate = 0;
    PUSH(v.state, INT2FIX(0));

    tok = val = Qnil;
    in_tok = INT2FIX(FINAL_TOK + 1); /* must not init to FINAL_TOK */

    read_next = 1;   /* causes yylex */
    nerr = 0;
    errstatus = 0;

    D(puts("params initialized"));

    /* -----------------------------------
       LALR parsing algorithm main loop
    ----------------------------------- */
    
    while (1) {
        long i;
        VALUE tmp;

        D(puts("enter new loop"));

        /* decide action */

        GET_POINTER(v.action_ptr, v.action_table, v.curstate, i);
        if (RARRAY(v.action_table)->ptr[i] == vDFLT_TOK) {
            tmp = RARRAY(v.action_table)->ptr[i+1];
            act = FIX2LONG(tmp);
        }
        else {
            if (read_next) {
                if (in_tok != vFINAL_TOK) {
                    tmp = rb_funcall(v.parser, id_nexttoken, 0);
                    Check_Type(tmp, T_ARRAY);
                    if (RARRAY(tmp)->len < 2)
                        rb_raise(rb_eArgError,
                                 "next_token returns too short array");
                    tok = RARRAY(tmp)->ptr[0];
                    val = RARRAY(tmp)->ptr[1];
                    tmp = rb_hash_aref(v.token_table, tok);
                    in_tok = NIL_P(tmp) ? vERR_TOK : tmp;
                    D(printf("read token %ld\n", FIX2INT(in_tok)));
                }
                read_next = 0;
            }
            SEARCH(v.action_table, i, in_tok, act);
        }
        D(printf("act=%ld\n", act));


        if (act > 0 && act < shift_n) {
            D(puts("shift"));

            if (errstatus > 0) errstatus--;
            SHIFT(v, act, in_tok, val);
            read_next = 1;
        }
        else if (act < 0 && act > -reduce_n) {
            D(puts("reduce"));

            REDUCE(v, act);
        }
        else if (act == -reduce_n) {
            D(printf("error detected, status=%ld\n", errstatus));

            if (errstatus == 0) {
                nerr++;
                rb_funcall(v.parser, id_onerror,
                           3, in_tok, val, v.vstack);
            }
            else if (errstatus == 3) {
                if (in_tok == vFINAL_TOK)
                    return Qfalse;
                read_next = 1;
            }
            errstatus = 3;

            /* check if We can shift/reduce error token */
            while (1) {
                GET_POINTER(v.action_ptr, v.action_table, v.curstate, i);
                while (1) {
                    tmp = RARRAY(v.action_table)->ptr[i];
                    if (tmp == vDFLT_TOK) {
                        D(puts("can't found error tok"));
                        break;
                    }
                    else if (tmp == vERR_TOK) {
                        D(puts("found error tok"));
                        tmp = RARRAY(v.action_table)->ptr[i+1];
                        act = FIX2LONG(tmp);
                        D(printf("e act=%ld\n", act));
                        break;
                    }
                    i += 2;
                }

                if (act != -reduce_n) { /* We can do. */
                    D(puts("can handle error tok"));
                    break;
                }
                else { /* We cannot: pop stack and try again */
                    D(puts("can't handle error tok: pop"));
                    if (RARRAY(v.state)->len == 0)
                        return Qnil;
                    POP(v.state);
                    POP(v.vstack);
                    tmp = LAST_I(v.state);
                    v.curstate = FIX2LONG(tmp);
                    if (debug) POP(v.tstack);
                }
            }

            /* shift|reduce error token */

            if (act > 0 && act < shift_n) {
                D(puts("e shift"));
                SHIFT(v, act, ERR_TOK, Qnil);
            }
            else if (act < 0 && act > -reduce_n) {
                D(puts("e reduce"));
                REDUCE(v, act);
            }
            else if (act == shift_n) {
                D(puts("e accept"));
                ACCEPT(v);
            }
            else {
                rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
            }
        }
        else if (act == shift_n) {
            D(puts("accept"));
            ACCEPT(v);
        }
        else {
            rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
        }
    }
}


void
Init_cparse()
{
    VALUE parser;

    parser = rb_eval_string("::Racc::Parser");
    rb_define_private_method(parser, "_c_parse", raccparse, 9);

    RaccBug = rb_eRuntimeError;

    id_yydebug      = rb_intern("@yydebug");
    id_nexttoken    = rb_intern("next_token");
    id_onerror      = rb_intern("on_error");
    id_noreduce     = rb_intern("_reduce_none");

    id__shift       = rb_intern("_shift");
    id__reduce      = rb_intern("_reduce");
    id__accept      = rb_intern("_accept");
}
