package org.simantics.scl.compiler.parser.grammar.input;

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public abstract class GrammarParser {    
    public static final boolean TRACE = false;

    private static final int INITIAL_CAPACITY = 16;
    private static final int STATE_COUNT = 19;
    private static final int TERMINAL_COUNT = 16;
    private static final int NONTERMINAL_COUNT = 6;
    private static final int PRODUCT_COUNT = 8;
    
    private static final int[] ACTION_ROW_ID = new int[STATE_COUNT];
    private static final int[] ACTION_COLUMN_ID = new int[TERMINAL_COUNT];
    private static final short[] ACTION_TABLE = new short[56];
    private static final int[] ERROR_TABLE = new int[10];
    private static final int[] GOTO_ROW_ID = new int[STATE_COUNT];
    private static final int[] GOTO_COLUMN_ID = new int[NONTERMINAL_COUNT];
    private static final short[] GOTO_TABLE = new short[12];
    private static final int[] PRODUCT_LHS = new int[PRODUCT_COUNT];

    private static final short STATE_MASK = (short)0x0fff;
    private static final short REDUCE_MASK = (short)0x8000;
    private static final short POP_MASK = (short)0x4000;
    private static final short PUSH_MASK = (short)0x2000;
    private static final short ERROR_ACTION = (short)0xffff;
    private static final short ACCEPT_ACTION = (short)0xfffe;
    
    public static final String[] TERMINAL_NAMES = new String[] {
        "NONTERMINAL",
        "EQUALS",
        "BAR",
        "SEMICOLON",
        "INITIAL",
        "HASH",
        "TERMINAL",
        "COMMA",
        "SHIFT",
        "REDUCE",
        "STAR",
        "PLUS",
        "OPTIONAL",
        "LPAREN",
        "RPAREN",
        "EOF"
    };

    public static final String[] NONTERMINAL_NAMES = new String[] {
        "file",
        "declaration",
        "prod",
        "regexps",
        "regexp",
        "init$1"
    };
        
    static {
        try {
            DataInputStream input = new DataInputStream(GrammarParser.class.getResourceAsStream("GrammarParser.dat"));
            for(int i=0;i<ACTION_ROW_ID.length;++i)
                ACTION_ROW_ID[i] = input.readInt();
            for(int i=0;i<ACTION_COLUMN_ID.length;++i)
                ACTION_COLUMN_ID[i] = input.readInt();    
            for(int i=0;i<ACTION_TABLE.length;++i)
                ACTION_TABLE[i] = input.readShort();
            for(int i=0;i<ERROR_TABLE.length;++i)
                ERROR_TABLE[i] = input.readInt();
            for(int i=0;i<GOTO_ROW_ID.length;++i)
                GOTO_ROW_ID[i] = input.readInt();
            for(int i=0;i<GOTO_COLUMN_ID.length;++i)
                GOTO_COLUMN_ID[i] = input.readInt();    
            for(int i=0;i<GOTO_TABLE.length;++i)
                GOTO_TABLE[i] = input.readShort();
            for(int i=0;i<PRODUCT_LHS.length;++i)
                PRODUCT_LHS[i] = input.readInt();
            input.close();
        } catch(IOException e) {
            e.printStackTrace();
        }
    }
    
    private static short getAction(int state, int symbol) {
        int id = TERMINAL_COUNT*state + symbol;
        if( ((ERROR_TABLE[id>>5] >> (id&31))&1) != 0 )
            return ERROR_ACTION;
        return ACTION_TABLE[ACTION_ROW_ID[state] + ACTION_COLUMN_ID[symbol]];
    }
    
    private static short getGoto(int state, int symbol) {
        return GOTO_TABLE[GOTO_ROW_ID[state] + GOTO_COLUMN_ID[symbol]];
    }
    
    protected abstract Token nextToken();
    
    private Object[] symbolStack = new Object[INITIAL_CAPACITY];
    private int symbolStackLength = 0;
    
    private int[] stateStack = new int[INITIAL_CAPACITY];
    private int[] symbolStackPositionStack = new int[INITIAL_CAPACITY];
    private int stateStackLength = 0;
    
    // For reduce
    private int reductionLength;
    
    protected int length() {
        return reductionLength;
    }
    
    protected Object get(int i) {
        if(i < 0 || i >= reductionLength)
            throw new IndexOutOfBoundsException();
        return symbolStack[symbolStackLength+i];
    }
    
    private String parseErrorDescription(int state, Token token, int tokenId) {
        StringBuilder b = new StringBuilder();
        b.append("Unexpected token '").append(token)
         .append("' (").append(TERMINAL_NAMES[tokenId])
         .append("). Expected one of ");
        ArrayList<String> possibleTerminals = new ArrayList<String>();
        for(int i=0;i<TERMINAL_COUNT;++i)
            if(getAction(state, i) != ERROR_ACTION)
                possibleTerminals.add(TERMINAL_NAMES[i]);
        Collections.sort(possibleTerminals);
        for(int i=0;i<possibleTerminals.size();++i) {
            if(i > 0)
                b.append(", ");
            b.append(possibleTerminals.get(i));
        }
        b.append('.');
        return b.toString();
    }
    
    protected abstract RuntimeException syntaxError(Token token, String description);
    
    private static String describeAction(boolean isGoto, int action) {
        if(action == ERROR_ACTION)
            return "ERROR";
        if(action == ACCEPT_ACTION)
            return "ACCEPT";
        StringBuilder b = new StringBuilder();
        if(isGoto)
            b.append("GOTO ");
        else {
            if((action & REDUCE_MASK) != 0) {
                action ^= REDUCE_MASK;
                b.append("REDUCE");
            }
            else
                b.append("SHIFT");
        }
        if((action & POP_MASK) != 0) {
            action ^= POP_MASK;
            b.append(" POP");
        }
        if((action & PUSH_MASK) != 0) {
            action ^= PUSH_MASK;
            b.append(" PUSH");
        }
        b.append(' ').append(action);
        return b.toString();
    }
    
    private void printState(int state) {
        System.out.print("state=" + state + ":");
        for(int i=symbolStackLength-1,j=stateStackLength-1;i>=0;--i) {
            Object s = symbolStack[i];
            if(s instanceof Token)
                System.out.print(" " + TERMINAL_NAMES[((Token)s).id]);
            else if(s == null)
                System.out.print(" null");
            else
                System.out.print(" " + s.getClass().getSimpleName());
            while(j>=0 && symbolStackPositionStack[j]==i)
                System.out.print(" (" + stateStack[j--] + ")");
        }
        System.out.println();
    }
    
    private Object parse(int state) {
        while(true) {
            Token token = nextToken();
            int tokenId = token.id;
            if(TRACE)
                System.out.println("---> token " + TERMINAL_NAMES[tokenId] + " \"" + token.text + "\" <---");
            while(true) {
                if(TRACE)
                    printState(state);
                short action = getAction(state, tokenId);
                if(TRACE)
                    System.out.println("    -> action=" + describeAction(false, action));
                //System.out.println(STATE_DESCRIPTIONS[state]);
                if((action & REDUCE_MASK) != 0) {
                    if(action == ACCEPT_ACTION)
                        return symbolStack[symbolStackLength-1];
                    if(action == ERROR_ACTION)
                        throw syntaxError(token, parseErrorDescription(state, token, tokenId));
                    int popAmount = (action >>> 13)&3;
                    if(TRACE) {
                        if(popAmount > 0)
                            System.out.println("    POP " + popAmount);
                    }
                    stateStackLength -= popAmount;
                    action &= STATE_MASK;
                    
                    int reductionBegin = symbolStackPositionStack[--stateStackLength];
                    
                    reductionLength = symbolStackLength-reductionBegin;
                    symbolStackLength = reductionBegin;
                    
                    if(symbolStackLength == symbolStack.length)
                        symbolStack = Arrays.copyOf(symbolStack, symbolStackLength*2);
                    Object symbol = reduce(action);
                    postReduce(symbol);
                    symbolStack[symbolStackLength] = symbol;
                    
                    state = stateStack[stateStackLength];
                    if(TRACE) {
                        ++symbolStackLength;
                        printState(state);
                        --symbolStackLength;
                        System.out.println("    nonterminal=" + NONTERMINAL_NAMES[PRODUCT_LHS[action]]);
                    }
                    action = getGoto(state, PRODUCT_LHS[action]);
                    if(TRACE)
                        System.out.println("    -> action=" + describeAction(true, action));
                        
                    // Pop state
                    if((action & POP_MASK) != 0) {
                        --stateStackLength;
                    }
                    // Push state
                    if((action & PUSH_MASK) != 0) {
                        if(stateStackLength == stateStack.length) {
                            stateStack = Arrays.copyOf(stateStack, stateStackLength*2);
                            symbolStackPositionStack = Arrays.copyOf(symbolStackPositionStack, stateStackLength*2);
                        }
                        symbolStackPositionStack[stateStackLength] = symbolStackLength;
                        stateStack[stateStackLength++] = state;
                    }
                    state = action & STATE_MASK;
                    ++symbolStackLength;
                }
                else {
                    // Pop state
                    if((action & POP_MASK) != 0) {
                        --stateStackLength;
                    }
                    // Push state
                    if((action & PUSH_MASK) != 0) {
                        if(stateStackLength == stateStack.length) {
                            stateStack = Arrays.copyOf(stateStack, stateStackLength*2);
                            symbolStackPositionStack = Arrays.copyOf(symbolStackPositionStack, stateStackLength*2);
                        }
                        symbolStackPositionStack[stateStackLength] = symbolStackLength;
                        stateStack[stateStackLength++] = state;
                    }
                    
                    // New state
                    state = action & STATE_MASK;
                    
                    // Push symbol
                    if(symbolStackLength == symbolStack.length)
                        symbolStack = Arrays.copyOf(symbolStack, symbolStackLength*2);
                    symbolStack[symbolStackLength++] = token;
                    break;
                }
            }
        }
    }
    
    public Object parseFile() {
        return parse(0);
    }


    protected Object reduce(int productionId) {
        try {
        switch(productionId) {
        case 0:
            return reduceFile();
        case 1:
            return reduceProduction();
        case 2:
            return reduceInitial();
        case 3:
            return reduceProductionRhs();
        case 4:
            return reduceConcatenation();
        case 5:
            return reduceTerminal();
        case 6:
            return reduceUnion();

        default:
            throw new RuntimeException("Internal parser error.");
        }
        } catch(RuntimeException e) {
            StringBuilder b = new StringBuilder();
            b.append("Failed to reduce");
            for(int i=0;i<length();++i) {
                Object obj = get(i);
                b.append("\n    (").append(i).append(") \"").append(obj).append('\"');
                if(obj instanceof Token)
                    b.append(" (").append(TERMINAL_NAMES[((Token)obj).id]).append(")");
                else
                    b.append(" [").append(obj.getClass().getSimpleName()).append("]");
            }
            throw new RuntimeException(b.toString(), e);
        } 
    }

    /**
     * file ::= declaration declaration&#42;
     */
    protected abstract Object reduceFile();
    /**
     * declaration ::= NONTERMINAL EQUALS prod (BAR prod)&#42; SEMICOLON
     */
    protected abstract Object reduceProduction();
    /**
     * declaration ::= INITIAL NONTERMINAL SEMICOLON
     */
    protected abstract Object reduceInitial();
    /**
     * prod ::= regexps HASH (TERMINAL COMMA (SHIFT | REDUCE))&#42; TERMINAL
     */
    protected abstract Object reduceProductionRhs();
    /**
     * regexps ::= (regexp (regexp | STAR | PLUS | OPTIONAL)&#42;)?
     */
    protected abstract Object reduceConcatenation();
    /**
     * regexp ::= NONTERMINAL | INITIAL | TERMINAL | SHIFT | REDUCE
     */
    protected abstract Object reduceTerminal();
    /**
     * regexp ::= LPAREN regexps (BAR regexps)&#42; RPAREN
     */
    protected abstract Object reduceUnion();

    protected void postReduce(Object reduced) {
    }

}