package org.simantics.scl.compiler.internal.parsing.parser;

import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
import org.simantics.scl.compiler.common.precedence.Associativity;
import org.simantics.scl.compiler.common.precedence.Precedence;
import org.simantics.scl.compiler.constants.CharacterConstant;
import org.simantics.scl.compiler.constants.StringConstant;
import org.simantics.scl.compiler.elaboration.equation.EqBasic;
import org.simantics.scl.compiler.elaboration.equation.EqGuard;
import org.simantics.scl.compiler.elaboration.equation.Equation;
import org.simantics.scl.compiler.elaboration.expressions.Case;
import org.simantics.scl.compiler.elaboration.expressions.EApply;
import org.simantics.scl.compiler.elaboration.expressions.EAsPattern;
import org.simantics.scl.compiler.elaboration.expressions.EBinary;
import org.simantics.scl.compiler.elaboration.expressions.EBinaryRightSide;
import org.simantics.scl.compiler.elaboration.expressions.EBlock;
import org.simantics.scl.compiler.elaboration.expressions.EConstant;
import org.simantics.scl.compiler.elaboration.expressions.EEnforce;
import org.simantics.scl.compiler.elaboration.expressions.EEquations;
import org.simantics.scl.compiler.elaboration.expressions.EFieldAccess;
import org.simantics.scl.compiler.elaboration.expressions.EIf;
import org.simantics.scl.compiler.elaboration.expressions.EIntegerLiteral;
import org.simantics.scl.compiler.elaboration.expressions.ELambda;
import org.simantics.scl.compiler.elaboration.expressions.EListComprehension;
import org.simantics.scl.compiler.elaboration.expressions.EListLiteral;
import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
import org.simantics.scl.compiler.elaboration.expressions.EMatch;
import org.simantics.scl.compiler.elaboration.expressions.ERange;
import org.simantics.scl.compiler.elaboration.expressions.ERealLiteral;
import org.simantics.scl.compiler.elaboration.expressions.ERecord;
import org.simantics.scl.compiler.elaboration.expressions.ESelect;
import org.simantics.scl.compiler.elaboration.expressions.ESimpleLambda;
import org.simantics.scl.compiler.elaboration.expressions.EStringLiteral;
import org.simantics.scl.compiler.elaboration.expressions.ETransformation;
import org.simantics.scl.compiler.elaboration.expressions.ETypeAnnotation;
import org.simantics.scl.compiler.elaboration.expressions.EVar;
import org.simantics.scl.compiler.elaboration.expressions.EVariable;
import org.simantics.scl.compiler.elaboration.expressions.EViewPattern;
import org.simantics.scl.compiler.elaboration.expressions.Expression;
import org.simantics.scl.compiler.elaboration.expressions.GuardedExpression;
import org.simantics.scl.compiler.elaboration.expressions.GuardedExpressionGroup;
import org.simantics.scl.compiler.elaboration.expressions.Variable;
import org.simantics.scl.compiler.elaboration.expressions.accessor.ExpressionAccessor;
import org.simantics.scl.compiler.elaboration.expressions.accessor.FieldAccessor;
import org.simantics.scl.compiler.elaboration.expressions.accessor.IdAccessor;
import org.simantics.scl.compiler.elaboration.expressions.accessor.StringAccessor;
import org.simantics.scl.compiler.elaboration.expressions.block.BindStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.CHRStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.ConstraintStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.GuardStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.LetStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.RuleStatement;
import org.simantics.scl.compiler.elaboration.expressions.block.Statement;
import org.simantics.scl.compiler.elaboration.expressions.list.ListAssignment;
import org.simantics.scl.compiler.elaboration.expressions.list.ListGenerator;
import org.simantics.scl.compiler.elaboration.expressions.list.ListGuard;
import org.simantics.scl.compiler.elaboration.expressions.list.ListQualifier;
import org.simantics.scl.compiler.elaboration.expressions.list.ListSeq;
import org.simantics.scl.compiler.elaboration.expressions.list.ListThen;
import org.simantics.scl.compiler.elaboration.expressions.records.FieldAssignment;
import org.simantics.scl.compiler.elaboration.java.Builtins;
import org.simantics.scl.compiler.elaboration.query.QAlternative;
import org.simantics.scl.compiler.elaboration.query.QConjunction;
import org.simantics.scl.compiler.elaboration.query.QDisjunction;
import org.simantics.scl.compiler.elaboration.query.QNegation;
import org.simantics.scl.compiler.elaboration.query.Query;
import org.simantics.scl.compiler.elaboration.query.pre.QPreBinds;
import org.simantics.scl.compiler.elaboration.query.pre.QPreEquals;
import org.simantics.scl.compiler.elaboration.query.pre.QPreGuard;
import org.simantics.scl.compiler.errors.Locations;
import org.simantics.scl.compiler.internal.parsing.Symbol;
import org.simantics.scl.compiler.internal.parsing.Token;
import org.simantics.scl.compiler.internal.parsing.declarations.ConstructorAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DAnnotationAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DClassAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DDataAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DDerivingInstanceAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DDocumentationAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DEffectAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DFixityAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DImportJavaAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DInstanceAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DMappingRelationAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DModuleHeader;
import org.simantics.scl.compiler.internal.parsing.declarations.DRelationAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DRuleAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DTypeAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DValueAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DValueTypeAst;
import org.simantics.scl.compiler.internal.parsing.declarations.DeclarationAst;
import org.simantics.scl.compiler.internal.parsing.declarations.FieldDescription;
import org.simantics.scl.compiler.internal.parsing.declarations.FundepAst;
import org.simantics.scl.compiler.internal.parsing.exceptions.SCLSyntaxErrorException;
import org.simantics.scl.compiler.internal.parsing.types.TApplyAst;
import org.simantics.scl.compiler.internal.parsing.types.TEffectAst;
import org.simantics.scl.compiler.internal.parsing.types.TForAllAst;
import org.simantics.scl.compiler.internal.parsing.types.TFunctionAst;
import org.simantics.scl.compiler.internal.parsing.types.TListAst;
import org.simantics.scl.compiler.internal.parsing.types.TPredAst;
import org.simantics.scl.compiler.internal.parsing.types.TTupleAst;
import org.simantics.scl.compiler.internal.parsing.types.TVarAst;
import org.simantics.scl.compiler.internal.parsing.types.TypeAst;
import org.simantics.scl.compiler.module.ImportDeclaration;
import org.simantics.scl.compiler.types.Types;


public class SCLParserImpl extends SCLParser {

    private final SCLPostLexer lexer;
    private SCLParserOptions options;

    public SCLParserImpl(Reader reader) {
        lexer = new SCLPostLexer(reader);
    }
    
    public void setParserOptions(SCLParserOptions options) {
        this.options = options;
        lexer.setParserOptions(options);
    }
    
    public boolean isEmpty() throws Exception {
        return lexer.peekToken().id == SCLTerminals.EOF;
    }

    @Override
    protected Token nextToken() {
        try {
            Token token = lexer.nextToken();
            /*System.out.println("TOKEN " + token.text + " (" + TERMINAL_NAMES[token.id] + ")" +
                    " [" 
                    + Locations.beginOf(token.location) + ".." 
                    + Locations.endOf(token.location) + "]");*/
            return token;
        } catch(Exception e) {
            if(e instanceof RuntimeException)
                throw (RuntimeException)e;
            else
                throw new RuntimeException(e);
        }
    }

    @Override
    protected Object reduceDeclarations() {
        ArrayList<DeclarationAst> declarations = new ArrayList<DeclarationAst>(length()/2);
        for(int i=1;i<length();i+=2)
            declarations.add((DeclarationAst)get(i));
        return declarations;
    }

    @Override
    protected Object reduceModule() {
        ArrayList<DeclarationAst> declarations = new ArrayList<DeclarationAst>(length()/2+1);
        for(int i=0;i<length();i+=2) {
            DeclarationAst declaration = (DeclarationAst)get(i);
            if(declaration == null)
                throw new NullPointerException();
            declarations.add(declaration);
        }
        return declarations;
    }
    
    @Override
    protected Object reduceModuleHeader() {
        FieldAssignment[] fields = new FieldAssignment[length()/2-1];
        for(int i=0;i<fields.length;++i)
            fields[i] = (FieldAssignment)get(2+i*2);
        return new DModuleHeader(fields);
    }

    @Override
    protected Object reduceLocalTypeAnnotation() {
        if(length() == 1)
            return get(0);
        return new ETypeAnnotation((Expression)get(0), (TypeAst)get(2));
    }

    @Override
    protected Object reduceTypeAnnotation() {
        EVar[] names = new EVar[length()/2];
        for(int i=0;i<names.length;++i)
            names[i] = (EVar)get(i*2);
        return new DValueTypeAst(
                names,
                (TypeAst)get(length()-1)
                );
    }

    @Override
    protected Object reduceValueDefinition() {
        Expression rhs = (Expression)get(1);
        return new DValueAst((Expression)get(0), rhs);
    }

    @Override
    protected Object reduceDataDefinition() {
        int i=2;
        ArrayList<String> parameters = new ArrayList<String>();
        while(i < length()) {
            Token token = (Token)get(i++);
            if(token.id != SCLTerminals.ID)
                break;
            parameters.add(token.text);
        }
        ArrayList<ConstructorAst> constructors = new ArrayList<ConstructorAst>(); 
        for(;i < length();i+=2)
            constructors.add((ConstructorAst)get(i));
        return new DDataAst(
                ((Token)get(1)).text,
                parameters.toArray(new String[parameters.size()]),
                constructors.toArray(new ConstructorAst[constructors.size()]),
                new String[0]
                );
    }

    @Override
    protected Object reduceTypeDefinition() {
        int i=2;
        ArrayList<String> parameters = new ArrayList<String>();
        while(true) {
            Token token = (Token)get(i++);
            if(token.id != SCLTerminals.ID)
                break;
            parameters.add(token.text);
        }
        return new DTypeAst(
                ((Token)get(1)).text,
                parameters.toArray(new String[parameters.size()]),
                (TypeAst)get(i)
                );
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceClassDefinition() {
        int i=1;
        ArrayList<TypeAst> context;
        if(get(i) instanceof Token)
            context = new ArrayList<TypeAst>(0);
        else
            context = (ArrayList<TypeAst>)get(i++);
        String name = ((Token)get(i++)).text;
        ArrayList<String> parameters = new ArrayList<String>();
        while(i < length()) {
            Token token = (Token)get(i);
            if(token.id != SCLTerminals.ID)
                break;
            parameters.add(token.text);
            ++i;
        }
        ArrayList<DeclarationAst> declarations = null;
        FundepAst[] fundeps = FundepAst.EMPTY_ARRAY;
        while(i < length()) {
            Token token = (Token)get(i++);
            if(token.id == SCLTerminals.WHERE) {
                declarations = (ArrayList<DeclarationAst>)get(i++);
            }
            else if(token.id == SCLTerminals.BAR) {
                fundeps = (FundepAst[])get(i++);
            }
            else
                throw new InternalCompilerError();
        }
        return new DClassAst(context, name,
                parameters.toArray(new String[parameters.size()]),
                fundeps,
                declarations);
    }

    @Override
    protected Object reduceFundep() {
        String[] from = new String[length()-2];
        for(int i=0;i<from.length;++i)
            from[i] = ((Token)get(i)).text;
        String to = ((Token)get(length()-1)).text;
        return new FundepAst(from, to);
    }

    @Override
    protected Object reduceFundeps() {
        FundepAst[] fundeps = new FundepAst[(length()+1)/2];
        for(int i=0;i<fundeps.length;++i)
            fundeps[i] = (FundepAst)get(i*2);
        return fundeps;
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceInstanceDefinition() {
        int i=1;
        ArrayList<TypeAst> context;
        if(get(i) instanceof Token)
            context = new ArrayList<TypeAst>(0);
        else
            context = (ArrayList<TypeAst>)get(i++);
        Token nameToken = (Token)get(i++);
        EVar name = new EVar(nameToken.location, nameToken.text);
        ArrayList<TypeAst> parameters = new ArrayList<TypeAst>();
        while(i < length()) {
            Object symbol = get(i++);
            if(symbol instanceof Token)
                break;            
            parameters.add((TypeAst)symbol);
        }
        ArrayList<DeclarationAst> declarations = null;
        if(i < length())
            declarations = (ArrayList<DeclarationAst>)get(i);
        return new DInstanceAst(context, name,
                parameters.toArray(new TypeAst[parameters.size()]),
                declarations);
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceDerivingInstanceDefinition() {
        int i=2;
        ArrayList<TypeAst> context;
        if(get(i) instanceof Token)
            context = new ArrayList<TypeAst>(0);
        else
            context = (ArrayList<TypeAst>)get(i++);
        Token nameToken = (Token)get(i++);
        EVar name = new EVar(nameToken.location, nameToken.text);
        ArrayList<TypeAst> parameters = new ArrayList<TypeAst>();
        while(i < length()) {
            Object symbol = get(i++);
            parameters.add((TypeAst)symbol);
        }
        return new DDerivingInstanceAst(context, name,
                parameters.toArray(new TypeAst[parameters.size()]));
    }

    @Override
    protected Object reduceDocumentationString() {
        return new DDocumentationAst(((Token)get(1)).text);
    }

    @Override
    protected Object reduceAnnotation() {
        ArrayList<Expression> parameters = new ArrayList<Expression>(length()-1);
        for(int i=1;i<length();++i)
            parameters.add((Expression)get(i));
        return new DAnnotationAst((Token)get(0), parameters);
    }

    @Override
    protected Object reducePrecedenceDefinition() {
        EVar[] symbols = new EVar[length()/2];
        for(int i=0;i<symbols.length;++i)
            symbols[i] = (EVar)get(2*i + 2);
        Associativity associativity;
        Token token = (Token)get(0);
        if(token.text.equals("infixl"))
            associativity = Associativity.LEFT;
        else if(token.text.equals("infixr"))
            associativity = Associativity.RIGHT;
        else
            associativity = Associativity.NONASSOC;
        return new DFixityAst(
                new Precedence(
                        Integer.parseInt(((Token)get(1)).text), 
                        associativity), 
                        symbols);
    }

    @Override
    protected Object reduceImport() {
        // (AS ID)? importSpec?
        int pos = 0;
        String importKeyword = ((Token)get(pos++)).text; // (IMPORT | INCLUDE) 
        ++pos; // BEGIN_STRING
        String moduleName = ((Token)get(pos++)).text; // END_STRING
        String localName = "";
        if(pos < length()) {
            Object temp = get(pos);
            if(temp instanceof Token) {
                Token token = (Token)temp;
                if(token.id == SCLTerminals.AS) {
                    ++pos; // AS
                    localName = ((Token)get(pos++)).text; // ID
                }
            }
        }
        ImportDeclaration.ImportSpec spec = ImportDeclaration.DEFAULT_SPEC;
        if(pos < length())
            spec = (ImportDeclaration.ImportSpec)get(pos++);
        return new ImportDeclaration(moduleName, localName,
                        importKeyword.equals("include"),
                        spec);
    }

    @Override
    protected Object reduceJustImport() {
        return get(0);
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceImportJava() {
        return new DImportJavaAst(((Token)get(2)).text, (ArrayList<DeclarationAst>)get(4));
    }

    @Override
    protected Object reduceEffectDefinition() {
        return new DEffectAst(
                ((Token)get(1)).text,
                ((Token)get(3)).text,
                ((Token)get(5)).text);
    }

    @Override
    protected Object reduceVarId() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceEscapedSymbol() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceTupleTypeConstructor() {
        return new TVarAst(Types.tupleConstructor(length()-1).name);
    }

    @Override
    protected Object reduceArrow() {
        int i=length()-1;
        TypeAst result = (TypeAst)get(i);
        i-=2;
        while(i >= 0) {
            if( ((Token)get(i+1)).text.equals("=>") )
                result = new TPredAst((TypeAst)get(i), result);
            else
                result = new TFunctionAst((TypeAst)get(i), result);
            i-=2;
        }
        return result;
    }

    @Override
    protected Object reduceBinary() {
        if(length() == 1)
            return get(0);
        int i=0;
        EVar negation = null;
        if(get(i) instanceof Token) {
            Token token = (Token)get(i++);
            negation = new EVar(token.location, token.text);
        }
        EBinary binary = new EBinary((Expression)get(i++), negation);
        while(i < length()) {
            EVar operator = (EVar)get(i++);
            Expression right = (Expression)get(i++);
            binary.rights.add(new EBinaryRightSide(operator, right));
        }
        return binary;
    }

    @Override
    protected Object reduceSimpleRhs() {
        if(length() == 2)
            return get(1);
        else {
            EBlock block = (EBlock)get(3);
            Expression expression = (Expression)get(1);
            block.addStatement(new GuardStatement(expression));
            block.location = Locations.location(Locations.beginOf(expression.location), Locations.endOf(block.location));
            return block;
        }
    }

    private GuardedExpressionGroup reduceGuardedExpressionGroup(int length) {
        GuardedExpression[] expressions = new GuardedExpression[length];
        for(int i=0;i<expressions.length;++i) {
            expressions[i] = (GuardedExpression)get(i);
        }
        return new GuardedExpressionGroup(expressions);
    }

    @Override
    protected Object reduceGuardedRhs() {
        int length = length();
        if(length > 2 && get(length-2) instanceof Token) {
            EBlock block = (EBlock)get(length-1);
            block.addStatement(new GuardStatement(reduceGuardedExpressionGroup(length-2)));
            block.location = Locations.NO_LOCATION;
            return block;
        }
        else
            return reduceGuardedExpressionGroup(length);
    }

    @Override
    protected Object reduceStatements() {
        EBlock block = new EBlock();
        if(length() > 2)
            for(int i=1;i<length();i+=2)
                block.addStatement((Statement)get(i));
        return block;
    }

    @Override
    protected Object reduceConstructor() {
        int idPos;
        for(idPos=0;idPos<length();idPos+=2)
            if(((Token)get(idPos)).id == SCLTerminals.ID)
                break;
        DAnnotationAst[] annotations = idPos == 0 ? DAnnotationAst.EMPTY_ARRAY : new DAnnotationAst[idPos/2];
        for(int i=0;i<idPos/2;++i)
            annotations[i] = new DAnnotationAst((Token)get(i*2), 
                    Arrays.asList((Expression)get(i*2+1)));
        TypeAst[] parameters = new TypeAst[length()-idPos-1];
        for(int i=0;i<parameters.length;++i)
            parameters[i] = (TypeAst)get(i+idPos+1);
        return new ConstructorAst(annotations, ((Token)get(idPos)).text, parameters, null);
    }

    @Override
    protected Object reduceContext() {
        ArrayList<TypeAst> result = new ArrayList<TypeAst>(length()/2-1);
        for(int i=1;i<length()-2;i+=2)
            result.add((TypeAst)get(i));
        return result;
    }

    @Override
    protected Object reduceTypeVar() {
        return new TVarAst(((Token)get(0)).text);
    }

    @Override
    protected Object reduceTupleType() {
        if(length() == 2)
            return new TTupleAst(TypeAst.EMPTY_ARRAY);
        if(length() == 3) {
            Symbol sym = (Symbol)get(1);
            sym.location = Locations.NO_LOCATION;
            return sym;
        }
        int dim = length()/2;
        TypeAst[] parameters = new TypeAst[dim];
        for(int i=0;i<dim;++i)
            parameters[i] = (TypeAst)get(i*2+1);
        return new TTupleAst(parameters);
    }

    @Override
    protected Object reduceListType() {
        return new TListAst((TypeAst)get(1));
    }

    @Override
    protected Object reduceListTypeConstructor() {
        return new TVarAst("[]");
    }

    @Override
    protected Object reduceTupleConstructor() {
        return new EVar(Types.tupleConstructor(length()-1).name);
    }

    @Override
    protected Object reduceVar() {
        return get(0);
    }

    @Override
    protected Object reduceBlank() {
        return new EVar("_");
    }

    @Override
    protected Object reduceInteger() {
        return new EIntegerLiteral(((Token)get(0)).text);
    }

    @Override
    protected Object reduceFloat() {
        return new ERealLiteral(((Token)get(0)).text);
    }

    @Override
    protected Object reduceString() {
        return get(0);
    }

    @Override
    protected Object reduceChar() {
        String text = ((Token)get(0)).text;
        char c = text.charAt(text.length()-2);
        if(text.length() == 4) {
            switch(c) {
            case 'n': c = '\n'; break;
            case 't': c = '\t'; break;
            case 'b': c = '\b'; break;
            case 'f': c = '\f'; break;
            case 'r': c = '\r'; break;
            }
        }
        return new ELiteral(new CharacterConstant(c));
    }

    @Override
    protected Object reduceTuple() {
        if(length() == 2)
            return new EConstant(Builtins.TUPLE_CONSTRUCTORS[0]);
        if(length() == 3) {
            Symbol sym = (Symbol)get(1);
            sym.location = Locations.NO_LOCATION;
            return sym;
        }
        int dim = length()/2;
        Expression[] parameters = new Expression[dim];
        for(int i=0;i<dim;++i)
            parameters[i] = (Expression)get(i*2+1);
        EConstant tupleConstructor = new EConstant(Builtins.TUPLE_CONSTRUCTORS[dim]);
        tupleConstructor.location = Locations.location(
                Locations.beginOf(((Token)get(0)).location),
                Locations.endOf(((Token)get(length()-1)).location));
        return new EApply(tupleConstructor, parameters);
    }

    public static Expression rightSection(EVar op, Expression e) {
        long loc = Locations.combine(op.location, e.location);
        Variable var = new Variable("rightSectionTemp");
        return new ESimpleLambda(loc, var, 
                new EApply(loc, op, new EVariable(loc, var), e));
    }

    @Override
    protected Object reduceRightSection() {
        Variable var = new Variable("rightSectionTemp");
        long loc = Locations.combine(((Token)get(0)).location, ((Token)get(length()-1)).location);
        EVar symbol = (EVar)get(1);
        return new ESimpleLambda(var, 
                new EApply(loc, symbol,
                        new EVariable(loc, var), (Expression)get(2)));
    }

    @Override
    protected Object reduceLeftSection() {
        return new EApply((EVar)get(2), (Expression)get(1));
    }

    @Override
    protected Object reduceListLiteral() {
        if(length() == 2)
            return new EListLiteral(Expression.EMPTY_ARRAY);
        int dim = length()/2;
        Expression[] components = new Expression[dim];
        for(int i=0;i<dim;++i)
            components[i] = (Expression)get(i*2+1);
        return new EListLiteral(components);
    }

    @Override
    protected Object reduceRange() {
        return new ERange(
                (Expression)get(1),
                (Expression)get(3)
                );
    }

    @Override
    protected Object reduceListComprehension() {
        ListQualifier qualifier = (ListQualifier)get(3);
        for(int i=5;i<length();i+=2) {
            ListQualifier right = (ListQualifier)get(i);
            if(right instanceof ListThen) {
                ((ListThen) right).setLeft(qualifier);
                qualifier = right;
            }
            else
                qualifier = new ListSeq(qualifier, right);
        }
        return new EListComprehension((Expression)get(1), qualifier);
    }

    @Override
    protected Object reduceAs() {
        Token id = (Token)get(0);
        return new EAsPattern(new EVar(id.location, id.text), (Expression)get(2));
    }

    @Override
    protected Object reduceGuardedExpEq() {
        Expression[] guards = new Expression[length()/2-1];
        for(int i=0;i<guards.length;++i)
            guards[i] = (Expression)get(i*2+1);
        return new GuardedExpression(guards, (Expression)get(length()-1));
    }

    @Override
    protected Object reduceLambda() {
        Expression[] patterns = new Expression[length()-3];
        for(int i=0;i<patterns.length;++i)
            patterns[i] = (Expression)get(i+1);
        Case case_ = new Case(patterns, (Expression)get(length()-1));
        case_.setLhs(Locations.combine(patterns[0].location, patterns[patterns.length-1].location));
        return new ELambda(case_);
    }
    
    @Override
    protected Object reduceLambdaMatch() {
        Case[] cases = new Case[length()/2-1];
        for(int i=0;i<cases.length;++i)
            cases[i] = (Case)get(i*2+2);
        return new ELambda(cases);
    }

    @Override
    protected Object reduceLet() {
        EBlock block = (EBlock)get(1);
        Expression expression = (Expression)get(3);
        block.addStatement(new GuardStatement(expression));
        Token letToken = (Token)get(0);
        block.location = Locations.location(
                Locations.beginOf(letToken.location),
                Locations.endOf(expression.location));
        return block;
    }

    @Override
    protected Object reduceIf() {
        return new EIf(
                (Expression)get(1),
                (Expression)get(3),
                length() == 6 ? (Expression)get(5) : null);
    }

    @Override
    protected Object reduceMatch() {
        Case[] cases = new Case[length()/2-2];
        for(int i=0;i<cases.length;++i)
            cases[i] = (Case)get(i*2+4);
        return new EMatch((Expression)get(1), cases);
    }

    @Override
    protected Object reduceDo() {
        EBlock block = (EBlock)get(1);
        Token doToken = (Token)get(0);
        block.setMonadic( doToken.text.equals("mdo") );
        block.location = Locations.location(Locations.beginOf(doToken.location), Locations.endOf(block.location));
        return block;
    }

    @Override
    protected Object reduceSelect() {
        return new ESelect(((Token)get(0)).id, (Expression)get(1), new QConjunction((Query[])get(3)));
    }
       
    @Override
    protected Object reduceEnforce() {
        return new EEnforce(new QConjunction((Query[])get(1)));
    }

    @Override
    protected Object reduceApply() {
        if(length() == 1)
            return get(0);
        Expression[] parameters = new Expression[length()-1];
        for(int i=0;i<parameters.length;++i)
            parameters[i] = (Expression)get(i+1);
        return new EApply((Expression)get(0), parameters);
    }

    @Override
    protected Object reduceSymbol() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceEscapedId() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceMinus() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceLess() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceGreater() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceDot() {
        return new EVar(((Token)get(0)).text);
    }

    @Override
    protected Object reduceCase() {
        return new Case((Expression)get(0), (Expression)get(1));
    }

    @Override
    protected Object reduceGuardQualifier() {
        return new ListGuard((Expression)get(0));
    }

    @Override
    protected Object reduceLetQualifier() {
        return new ListAssignment((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceBindQualifier() {
        return new ListGenerator((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceThenQualifier() {
        return new ListThen((Expression)get(1), length()==4 ? (Expression)get(3) : null);
    }

    @Override
    protected Object reduceGuardStatement() {
        return new GuardStatement((Expression)get(0));
    }

    @Override
    protected Object reduceLetStatement() {
        return new LetStatement((Expression)get(0), (Expression)get(1));
    }

    @Override
    protected Object reduceBindStatement() {
        return new BindStatement((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceSimpleCaseRhs() {
        return get(1);
    }

    @Override
    protected Object reduceGuardedCaseRhs() {
        GuardedExpression[] expressions = new GuardedExpression[length()];
        for(int i=0;i<expressions.length;++i)
            expressions[i] = (GuardedExpression)get(i);
        return new GuardedExpressionGroup(expressions);
    }

    @Override
    protected Object reduceGuardedExpArrow() {
        Expression[] guards = new Expression[length()/2-1];
        for(int i=0;i<guards.length;++i)
            guards[i] = (Expression)get(i*2+1);
        return new GuardedExpression(guards, (Expression)get(length()-1));
    }

    @Override
    protected Object reduceEffect() {
        ArrayList<TypeAst> effects = new ArrayList<TypeAst>(length()/2-1);
        for(int i=1;i<length()-1;i+=2) {
            Token token = (Token)get(i);
            TVarAst ast = new TVarAst(token.text);
            ast.location = token.location;
            effects.add(ast);
        }
        return new TEffectAst(effects, (TypeAst)get(length()-1));
    }

    @Override
    protected Object reduceJustEtype() {
        return get(0);
    }

    @Override
    protected Object reduceForAll() {
        String[] vars = new String[length()-3];
        for(int i=0;i<vars.length;++i)
            vars[i] = ((Token)get(i+1)).text;
        return new TForAllAst(vars, (TypeAst)get(length()-1));
    }

    @Override
    protected Object reduceApplyType() {
        TypeAst[] parameters = new TypeAst[length()-1];
        for(int i=0;i<parameters.length;++i)
            parameters[i] = (TypeAst)get(i+1);
        return new TApplyAst((TypeAst)get(0), parameters);
    }

    @SuppressWarnings("unchecked")
    @Override
    protected void postReduce(Object reduced) {
        if(!(reduced instanceof Symbol))
            return;
        Symbol sym = (Symbol)reduced;
        if(sym.location != Locations.NO_LOCATION || length() == 0)
            return;
        Object first = get(0);
        if(!(first instanceof Symbol)) {
            if(first instanceof List) {
                List<Object> ll = (List<Object>)first;
                first = ll.get(0);
            }
            else {
                Object[] ll = (Object[])first;
                if(ll.length > 0)
                    first = ll[0];
                else
                    first = get(1);
            }
        }
        Object last = get(length()-1);
        if(!(last instanceof Symbol)) {
            if(last instanceof List) {
                List<Object> ll = (List<Object>)last;
                last = ll.get(ll.size()-1);
            }
            else {
                Object[] ll = (Object[])last;
                if(ll.length > 0)
                    last = ll[ll.length-1];
                else
                    last = get(length()-2);
            }
        }
        sym.location = (((Symbol)first).location & 0xffffffff00000000L) 
                | (((Symbol)last).location & 0xffffffffL);
        /*for(int i=0;i<length();++i) {
            Object obj = get(i);
            System.out.print(obj.getClass().getSimpleName());
            if(obj instanceof Token) {
                Token t = (Token)obj;
                System.out.print("(" + t.text + ")");
            }
            if(obj instanceof Symbol) {
                Symbol s = (Symbol)obj;
                System.out.print("["+ Locations.beginOf(s.location) + "-" + Locations.endOf(s.location) + "]");
            }
            System.out.print(" ");
        }
        System.out.println("-> " + reduced.getClass().getSimpleName() + " " +
                Locations.beginOf(sym.location) + "-" + Locations.endOf(sym.location));*/
    }

    @Override
    protected RuntimeException syntaxError(Token token, String description) {
        throw new SCLSyntaxErrorException(token.location, description);
    }

    @Override
    protected Object reduceIdAccessor() {
        return new IdAccessor('.', ((Token)get(0)).text);
    }

    @Override
    protected Object reduceStringAccessor() {
        return new StringAccessor('.', ((Token)get(1)).text);
    }

    @Override
    protected Object reduceExpAccessor() {
        return new ExpressionAccessor('.', (Expression)get(1));
    }

    @Override
    protected Object reduceFieldAccess() {
        if(length() == 1)
            return get(0);
        Expression result = (Expression)get(0);
        for(int i=2;i<length();i+=2) {
            FieldAccessor accessor = (FieldAccessor)get(i);
            accessor.accessSeparator = ((Token)get(i-1)).text.charAt(0);
            result = new EFieldAccess(result, accessor);
        }
        return result;
    }

    @Override
    protected Object reduceQueryBlock() {
        if(length() == 2)
            return Query.EMPTY_ARRAY;
        Query[] queries = new Query[length()/2];
        for(int i=0;i<queries.length;++i)
            queries[i] = (Query)get(2*i+1);
        return queries;
    }

    @Override
    protected Object reduceGuardQuery() {
        return new QPreGuard((Expression)get(0));
    }

    @Override
    protected Object reduceEqualsQuery() {
        return new QPreEquals((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceBindQuery() {
        return new QPreBinds((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceCompositeQuery() {
        Query[] queries = (Query[])get(1);
        switch(((Token)get(0)).text.charAt(1)) {
        case '&': return new QConjunction(queries);
        case '|': return new QDisjunction(queries);
        case '!': return new QNegation(new QConjunction(queries));
        case '?': return new QAlternative(queries);
        default: throw new InternalCompilerError();
        }
    }
    
    @Override
    protected Object reduceRuleStatement() {
        return new RuleStatement((Expression)get(0), new QConjunction((Query[])get(2)));
    }

    @Override
    protected Object reduceHashedId() {
        return new EVar("#" + ((Token)get(1)).text);
    }

    @Override
    protected Object reduceStringLiteral() {
        int expCount = length()/3;
        if(expCount == 0)
            return new ELiteral(new StringConstant(((Token)get(1)).text));
        else {
            String[] strings = new String[expCount+1];
            Expression[] expressions = new Expression[expCount];
            for(int i=0;i<expCount;++i) {
                strings[i] = ((Token)get(i*3+1)).text;
                expressions[i] = (Expression)get(i*3+2);
            }
            strings[expCount] = ((Token)get(expCount*3+1)).text;
            return new EStringLiteral(strings, expressions);
        }
    }

    @Override
    protected Object reduceOneCommand() {
        return null;
    }
    
    @Override
    protected Object reduceManyCommands() {
        return null;
    }

    @Override
    protected Object reduceStatementCommand() {
        // to be extended in subclasses
        return null;
    }

    @Override
    protected Object reduceImportCommand() {
        // to be extended in subclasses
        return null;
    }
    
    @Override
    protected Object reduceImportValueItem() {
        return new EVar(((Token)get(0)).text);
    }
    
    @Override
    protected Object reduceImportHiding() {
        EVar[] values = new EVar[(length()-2)/2];
        for(int i=0;i<values.length;++i)
            values[i] = (EVar)get(i*2+2);
        return new ImportDeclaration.ImportSpec(true, values);
    }
    
    @Override
    protected Object reduceImportShowing() {
        EVar[] values = new EVar[(length()-1)/2];
        for(int i=0;i<values.length;++i)
            values[i] = (EVar)get(i*2+1);
        return new ImportDeclaration.ImportSpec(false, values);
    }

    @Override
    protected Object reduceRuleDeclarations() {
        ArrayList<Object> declarations = new ArrayList<Object>(length()/2);
        for(int i=1;i<length();i+=2)
            declarations.add((Object)get(i));
        return declarations;
    }

    private static final String[] EMPTY_STRING_ARRAY = new String[0];
    
    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceRuleDefinition() {
        String[] extendsNames = EMPTY_STRING_ARRAY;
        if(length() >= 6) {
            int extendsCount = (length() - 4) / 2;
            extendsNames = new String[extendsCount]; 
            for(int i=0;i<extendsCount;++i)
                extendsNames[i] = ((Token)get(3+i*2)).text;
        }
        
        DRuleAst rule = new DRuleAst(
                ((Token)get(0)).id == SCLTerminals.ABSTRACT_RULE,
                ((Token)get(1)).text,
                extendsNames);
        
        ArrayList<Object> ruleDeclarations = (ArrayList<Object>)get(length()-1);
        ArrayList<Query> section = null;
        for(Object decl : ruleDeclarations) {
            if(decl instanceof DAnnotationAst) {
                DAnnotationAst annotation = (DAnnotationAst)decl;
                section = rule.getSection(annotation.id.text.substring(1));
            }
            else if(decl instanceof Query) {
                if(section == null)
                    section = rule.getSection("when");
                section.add((Query)decl);
            }
            else
                throw new InternalCompilerError();
        }
        return rule;
    }

    @Override
    protected Object reduceQueryRuleDeclaration() {
        return get(0);
    }

    @Override
    protected Object reduceMappingRelationDefinition() {
        TypeAst[] types = new TypeAst[length()-2];
        for(int i=0;i<types.length;++i)
            types[i] = (TypeAst)get(i+2);
        return new DMappingRelationAst(
                ((Token)get(1)).text,
                types);
    }

    @Override
    protected Object reduceTransformation() {
        return new ETransformation(
                ((Token)get(1)).text,
                new QConjunction((Query[])get(3))
                );
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Object reduceRelationDefinition() {
        return new DRelationAst((Expression)get(0), 
                ((ArrayList<Object>)get(2)).toArray());
    }

    @Override
    protected Object reduceRecord() {
        FieldAssignment[] fields = new FieldAssignment[length()/2-1];
        for(int i=0;i<fields.length;++i)
            fields[i] = (FieldAssignment)get(2+i*2);
        return new ERecord((Token)get(0), fields);
    }

    @Override
    protected Object reduceField() {
        return new FieldAssignment(((Token)get(0)).text, (Expression)get(2));
    }
    
    @Override
    protected Object reduceFieldShorthand() {
        return new FieldAssignment(((Token)get(0)).text, null);
    }

    @Override
    protected Object reduceRecordConstructor() {
        int idPos;
        for(idPos=0;idPos<length();idPos+=2)
            if(((Token)get(idPos)).id == SCLTerminals.ID)
                break;
        DAnnotationAst[] annotations = idPos == 0 ? DAnnotationAst.EMPTY_ARRAY : new DAnnotationAst[idPos/2];
        for(int i=0;i<idPos/2;++i)
            annotations[i] = new DAnnotationAst((Token)get(i*2), 
                    Arrays.asList((Expression)get(i*2+1)));
        TypeAst[] parameters = new TypeAst[(length()-idPos-1)/2];
        String[] fieldNames = new String[parameters.length];
        for(int i=0;i<parameters.length;++i) {
            FieldDescription fieldDesc = (FieldDescription)get(idPos+(i+1)*2);
            parameters[i] = fieldDesc.type;
            fieldNames[i] = fieldDesc.name;
        }
        return new ConstructorAst(annotations, ((Token)get(idPos)).text, parameters, fieldNames);
    }

    @Override
    protected Object reduceFieldDescription() {
        return new FieldDescription(((Token)get(0)).text, (TypeAst)get(2));
    }

    @Override
    protected Object reduceEq() {
        return (Expression)get(2);
    }

    @Override
    protected Object reduceEquationBlock() {
        if(length() == 0)
            return new EEquations(Equation.EMPTY_ARRAY);
        Equation[] equations = new Equation[length()/2+1];
        for(int i=0;i<equations.length;++i)
            equations[i] = (Equation)get(2*i);
        return new EEquations(equations);
    }

    @Override
    protected Object reduceGuardEquation() {
        return new EqGuard((Expression)get(0));
    }

    @Override
    protected Object reduceBasicEquation() {
        return new EqBasic((Expression)get(0), (Expression)get(2));
    }

    @Override
    protected Object reduceViewPattern() {
        return new EViewPattern((Expression)get(1), (Expression)get(3));
    }

    @Override
    protected Object reduceCHRStatement() {
        return new CHRStatement((ListQualifier[])get(0), (ListQualifier[])get(2));
    }

    @Override
    protected Object reduceConstraintStatement() {
        TypeAst[] parameterTypes = new TypeAst[length()-2];
        for(int i=0;i<parameterTypes.length;++i)
            parameterTypes[i] = (TypeAst)get(2+i);
        return new ConstraintStatement((Token)get(1), parameterTypes);
    }

    @Override
    protected Object reduceCHRQuery() {
        ListQualifier[] query = new ListQualifier[(length()+1)/2];
        for(int i=0;i<query.length;++i)
            query[i] = (ListQualifier)get(i*2);
        return query;
    }

    /*
    @Override
    protected Object reduceWhen() {
        return new EWhen(
                new QConjunction((Query[])get(1)),
                (Expression)get(3));
    }*/
    
    @Override
    protected Object reduceVerboseCHRQuery() {
        ListQualifier[] query = new ListQualifier[(length()-1)/2];
        for(int i=0;i<query.length;++i)
            query[i] = (ListQualifier)get(i*2+1);
        return query;
    }
    
    @Override
    protected Object reduceVerboseCHRStatement() {
        return new CHRStatement((ListQualifier[])get(1), (ListQualifier[])get(3));
    }

    @Override
    protected Object reduceDummy() {
        throw new UnsupportedOperationException();
    }

}