/* vim: set ts=4 sw=4 tw=99 et:

  *

  * Copyright (C) 2012 David Anderson

  *

  * This file is part of JITCraft.

  *

  * JITCraft is free software: you can redistribute it and/or modify it under

  * the terms of the GNU General Public License as published by the Free

  * Software Foundation, either version 3 of the License, or (at your option)

  * any later version.

  * 

  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY

  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

  *

  * You should have received a copy of the GNU General Public License along with

  * JITCraft. If not, see http://www.gnu.org/licenses/.

  */

 #include "Zone.h"

 #include "Parser.h"

 #include "FixedArray.h"

 #include "Heap.h"

 #include "Strings.h"

 #include "Heap-inl.h"

 using namespace ke;

 Parser::Parser(Zone *zone, CompileContext &cc, const char *stream, size_t length)

   : zone_(zone),

     cc_(cc),

     pool_(zone_->pool()),

     scanner_(cc, stream, length),

     scope_(NULL),

     unbound_(NULL)

 {

     unbound_ = new (pool_) PoolList<NameProxy *>();

 }

 bool

 Parser::match(TokenKind kind)

 {

     if (scanner_.peek() != kind)

         return false;

     scanner_.scan();

     return true;

 }

 bool

 Parser::matchSemicolon()

 {

     return expect(TOK_SEMICOLON);

 }

 bool

 Parser::expect(TokenKind kind)

 {

     TokenKind got = scanner_.scan();

     if (got == kind)

         return true;

     cc_.reportError(scanner_.begin(), Message_WrongToken, TokenNames[kind], TokenNames[got]);

     return false;

 }

 Scope *

 Parser::enterScope(Scope::Kind kind)

 {

     scope_ = new (pool_) Scope(pool_, kind, scope_);

     if (!scope_->initialize())

         return NULL;

     return scope_;

 }

 NameProxy *

 Parser::bind(Handle<String> name)

 {

     BoundName *bound = scope_->lookup(name);

     NameProxy *proxy = new (pool_) NameProxy(scanner_.begin(), name, bound);

     if (!bound && !unbound_->append(proxy))

         return NULL;

     return proxy;

 }

 bool

 Parser::matchName(String **name, TokenKind kind)

 {

     assert(kind == TOK_NAME || kind == TOK_LABEL);

     *name = NULL;

     if (!match(kind))

         return false;

     *name = zone_->makeSymbol(scanner_.literal(), scanner_.literal_length());

     return true;

 }

 String *

 Parser::expectName()

 {

     if (!expect(TOK_NAME))

         return NULL;

     return zone_->makeSymbol(scanner_.literal(), scanner_.literal_length());

 }

 void

 Parser::redeclarationError(BoundName *other)

 {

     cc_.reportError(scanner_.begin(), Message_RedeclaredName, other->name()->chars(),

                     other->pos().line, other->pos().col);

 }

 Expression *

 Parser::primitive()

 {

     TokenKind kind = scanner_.peek();

     switch (kind) {

       case TOK_NAME:

       {

         Local<String> name(zone_, expectName());

         if (!name)

             return NULL;

         return bind(name);

       }

       case TOK_FLOAT_LITERAL:

       {

         scanner_.scan();

         double value = Scanner::ParseDouble(scanner_.literal());

         return new (pool_) FloatLiteral(scanner_.begin(), value);

       }

       case TOK_INTEGER_LITERAL:

       {

         scanner_.scan();

         int value = atoi(scanner_.literal());

         return new (pool_) IntegerLiteral(scanner_.begin(), value);

       }

       case TOK_STRING_LITERAL:

       {

         scanner_.scan();

         Local<ByteArray> array(zone_, ByteArray::New(zone_, scanner_.literal_length() + 1));

         if (!array)

             return NULL;

         memcpy(array->raw(), scanner_.literal(), scanner_.literal_length() + 1);

         return new (pool_) StringLiteral(scanner_.begin(), array);

       }

       default:

       {

         if (kind != TOK_ERROR)

             cc_.reportError(scanner_.begin(), Message_ExpectedExpression, TokenNames[kind]);

         return NULL;

       }

     }

 }

 Expression *

 Parser::prefix()

 {

     switch (scanner_.peek()) {

       case TOK_LPAREN:

       {

         scanner_.scan();

         Expression *expr = expression();

         if (!expr)

             return NULL;

         if (!expect(TOK_RPAREN))

             return NULL;

         return expr;

       }

       default:

         return primitive();

     }

 }

 Expression *

 Parser::call(Expression *callee)

 {

     ExpressionList *arguments = new (pool_) ExpressionList();

     SourcePosition pos = scanner_.begin();

     expect(TOK_LPAREN);

     if (!match(TOK_RPAREN)) {

         while (true) {

             Expression *expr = expression();

             if (!expr)

                 return NULL;

             if (!arguments->append(expr))

                 return NULL;

             if (!match(TOK_COMMA))

                 break;

         }

         if (!expect(TOK_RPAREN))

             return NULL;

     }

     return new (pool_) CallExpression(pos, callee, arguments);

 }

 Expression *

 Parser::index(Expression *left)

 {

     expect(TOK_LBRACKET);

     SourcePosition pos = scanner_.begin();

     Expression *expr = expression();

     if (!expr)

         return NULL;

     if (!expect(TOK_RBRACKET))

         return NULL;

     return new (pool_) IndexExpression(pos, left, expr);

 }

 Expression *

 Parser::primary()

 {

     Expression *expr = prefix();

     if (!expr)

         return NULL;

     for (;;) {

         switch (scanner_.peek()) {

           case TOK_LPAREN:

             expr = call(expr);

             if (!expr)

                 return NULL;

             break;

           case TOK_LBRACKET:

             expr = index(expr);

             if (!expr)

                 return NULL;

             break;

           default:

             return expr;

         }

     }

 }

 Expression *

 Parser::unary()

 {

     TokenKind token = scanner_.peek();

     SourcePosition pos = scanner_.begin();

     switch (token) {

       case TOK_INCREMENT:

       case TOK_DECREMENT:

       {

         scanner_.scan();

         Expression *expr = expression();

         if (!expr)

             return NULL;

         return new (pool_) IncDecExpression(pos, token, expr, false);

       }

       default:

         break;

     }

     Expression *expr = primary();

     token = scanner_.peek();

     if (token == TOK_INCREMENT || token == TOK_DECREMENT) {

         scanner_.scan();

         return new (pool_) IncDecExpression(pos, token, expr, true);

     }

     return expr;

 }

 Expression *

 Parser::multiplication()

 {

     Expression *left = unary();

     do {

         if (!match(TOK_SLASH) && !match(TOK_STAR))

             break;

         SourcePosition pos = scanner_.begin();

         TokenKind kind = scanner_.last();

         Expression *right = unary();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, kind, left, right);

     } while (left);

     return left;

 }

 Expression *

 Parser::addition()

 {

     Expression *left = multiplication();

     while (left) {

         if (!match(TOK_PLUS) && !match(TOK_MINUS))

             break;

         SourcePosition pos = scanner_.begin();

         TokenKind kind = scanner_.last();

         Expression *right = multiplication();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, kind, left, right);

     }

     return left;

 }

 Expression *

 Parser::shift()

 {

     Expression *left = addition();

     while (left) {

         if (!match(TOK_SHL) && !match(TOK_SHR) && !match(TOK_USHR))

             break;

         SourcePosition pos = scanner_.begin();

         TokenKind kind = scanner_.last();

         Expression *right = addition();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, kind, left, right);

     }

     return left;

 }

 Expression *

 Parser::bitand_()

 {

     Expression *left = shift();

     while (left) {

         if (!match(TOK_BITAND))

             break;

         SourcePosition pos = scanner_.begin();

         Expression *right = shift();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, TOK_BITAND, left, right);

     }

     return left;

 }

 Expression *

 Parser::bitxor()

 {

     Expression *left = bitand_();

     while (left) {

         if (!match(TOK_BITXOR))

             break;

         SourcePosition pos = scanner_.begin();

         Expression *right = shift();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, TOK_BITXOR, left, right);

     }

     return left;

 }

 Expression *

 Parser::bitor_()

 {

     Expression *left = bitxor();

     while (left) {

         if (!match(TOK_BITOR))

             break;

         SourcePosition pos = scanner_.begin();

         Expression *right = shift();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, TOK_BITOR, left, right);

     }

     return left;

 }

 Expression *

 Parser::relational()

 {

     Expression *left = bitor_();

     while (left) {

         TokenKind kind = scanner_.peek();

         if (kind < TOK_LT || kind > TOK_GE)

             break;

         scanner_.scan();

         SourcePosition pos = scanner_.begin();

         Expression *right = shift();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, kind, left, right);

     }

     return left;

 }

 Expression *

 Parser::equals()

 {

     Expression *left = relational();

     while (left) {

         if (!match(TOK_EQUALS) && !match(TOK_NOTEQUALS))

             break;

         TokenKind kind = scanner_.last();

         SourcePosition pos = scanner_.begin();

         Expression *right = relational();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(pos, kind, left, right);

     }

     return left;

 }

 Expression *

 Parser::assignment()

 {

     Expression *left = equals();

     while (left) {

         TokenKind token = scanner_.peek();

         if (token != TOK_ASSIGN && (token < TOK_ASSIGN_ADD || token > TOK_ASSIGN_SHL))

             break;

         scanner_.scan();

         SourcePosition pos = scanner_.begin();

         Expression *expr = equals();

         if (!expr)

             return NULL;

         left = new (pool_) Assignment(pos, token, left, expr);

     }

     return left;

 }

 Expression *

 Parser::expression()

 {

     return assignment();

 }

 Statement *

 Parser::while_()

 {

     SourcePosition pos = scanner_.begin();

     scanner_.scan();

     if (!expect(TOK_LPAREN))

         return NULL;

     Expression *condition = expression();

     if (!condition)

         return NULL;

     if (!expect(TOK_RPAREN))

         return NULL;

     // Inside a loop, we force the creation of a scope object. Normally, we

     // will cull scopes if they have no variables. However inside a loop,

     // function calls that take references may compute a LIFO object, and to

     // avoid temporarily leaking many such objects, we ensure that a scope

     // is present so a LIFO slot can be allocated.

     if (!enterScope(Scope::BLOCK))

         return NULL;

     Statement *body;

     if (scanner_.peek() == TOK_LBRACE)

         body = block(scope_);

     else

         body = localStatement();

     if (!body)

         return NULL;

     scope_ = scope_->enclosing();

     return new (pool_) WhileStatement(pos, TOK_WHILE, condition, body);

 }

 Statement *

 Parser::do_()

 {

     SourcePosition pos = scanner_.begin();

     scanner_.scan();

     // See the comment in ::while_() as to why we force a scope.

     if (!enterScope(Scope::BLOCK))

         return NULL;

     Statement *body;

     if (scanner_.peek() == TOK_LBRACE)

         body = block(scope_);

     else

         body = localStatement();

     if (!body)

         return NULL;

     scope_ = scope_->enclosing();

     if (!expect(TOK_WHILE))

         return NULL;

     if (!expect(TOK_LPAREN))

         return NULL;

     Expression *condition = expression();

     if (!condition)

         return NULL;

     if (!expect(TOK_RPAREN))

         return NULL;

     return new (pool_) WhileStatement(pos, TOK_DO, condition, body);

 }

 Statement *

 Parser::forStatement()

 {

     SourcePosition pos = scanner_.begin();

     scanner_.scan();

     if (!expect(TOK_LPAREN))

         return NULL;

     Statement *decl = NULL;

     if (!match(TOK_SEMICOLON)) {

         if (scanner_.peek() == TOK_NEW) {

             if (!enterScope(Scope::BLOCK))

                 return NULL;

             if ((decl = variableDeclaration()) == NULL)

                 return NULL;

         } else {

             if ((decl = expressionStatement()) == NULL)

                 return NULL;

         }

         if (!expect(TOK_SEMICOLON))

             return NULL;

     }

     Expression *condition = NULL;

     if (!match(TOK_SEMICOLON)) {

         if ((condition = expression()) == NULL)

             return NULL;

         if (!expect(TOK_SEMICOLON))

             return NULL;

     }

     Statement *update = NULL;

     if (!match(TOK_RPAREN)) {

         if ((update = expressionStatement()) == NULL)

             return NULL;

         if (!expect(TOK_RPAREN))

             return NULL;

     }

     // See the comment in ::while_() as to why we force a scope.

     if (!enterScope(Scope::BLOCK))

         return NULL;

     Statement *body;

     if (scanner_.peek() == TOK_LBRACE)

         body = block(scope_);

     else

         body = localStatement();

     if (!body)

         return NULL;

     scope_ = scope_->enclosing();

     Scope *declScope = NULL;

     if (decl && decl->isVariableDeclaration()) {

         declScope = scope_->unlinkIfEmpty();

         scope_ = scope_->enclosing();

     }

     return new (pool_) ForStatement(pos, declScope, decl, condition, update, body);

 }

 VariableDeclaration *

 Parser::variableDeclaration()

 {

     if (!expect(TOK_NEW))

         return NULL;

     Local<String> tag(zone_);

     if (matchName(tag.ref(), TOK_LABEL) && !tag)

         return NULL;

     Local<String> name(zone_, expectName());

     if (!name)

         return NULL;

     if (BoundName *other = scope_->localLookup(name)) {

         redeclarationError(other);

         return NULL;

     }

     Variable *var = scope_->declareVariable(name, scanner_.begin());

     if (!var)

         return NULL;

     ExpressionList *postDimensions = NULL;

     if (scanner_.peek() == TOK_LBRACKET) {

         postDimensions = new (pool_) ExpressionList();

         while (match(TOK_LBRACKET)) {

             Expression *dim = expression();

             if (!dim)

                 return NULL;

             if (!expect(TOK_RBRACKET))

                 return NULL;

             if (!postDimensions->append(dim))

                 return NULL;

         }

     }

     Expression *expr = NULL;

     if (match(TOK_ASSIGN)) {

         if ((expr = expression()) == NULL)

             return NULL;

     }

     return new (pool_) VariableDeclaration(var->pos(), var, tag, postDimensions, expr);

 }

 Statement *

 Parser::returnStatement()

 {

     SourcePosition pos = scanner_.begin();

     if (!expect(TOK_RETURN))

         return NULL;

     Expression *expr = NULL;

     if (scanner_.peek() != TOK_SEMICOLON) {

         if ((expr = expression()) == NULL)

             return NULL;

         // We only care about non-void returns when determining whether a

         // tagless function is non-void.

         encounteredReturn_ = true;

     }

     return new (pool_) ReturnStatement(pos, expr);

 }

 Statement *

 Parser::expressionStatement()

 {

     Expression *left = assignment();

     if (!left)

         return NULL;

     return new (pool_) ExpressionStatement(left);

 }

 Statement *

 Parser::block(Scope *scope)

 {

     if (!expect(TOK_LBRACE))

         return NULL;

     SourcePosition pos = scanner_.begin();

     if (!scope && !enterScope(Scope::BLOCK))

         return NULL;

     StatementList *statements = new (pool_) StatementList();

     while (!match(TOK_RBRACE)) {

         Statement *statement = localStatement();

         if (statement == NULL)

             return NULL;

         if (!statements->append(statement))

             return NULL;

     }

     if (!scope) {

     	scope = scope_->unlinkIfEmpty();

         scope_ = scope_->enclosing();

     }

     BlockStatement *block = new (pool_) BlockStatement(pos, scope, statements);

     return block;

 }

 Statement *

 Parser::if_()

 {

     expect(TOK_IF);

     SourcePosition pos = scanner_.begin();

     if (!expect(TOK_LPAREN))

         return NULL;

     Expression *cond = expression();

     if (!cond)

         return NULL;

     if (!expect(TOK_RPAREN))

         return NULL;

     Statement *ifTrue = localStatement();

     if (!ifTrue)

         return NULL;

     IfStatement *outer = new (pool_) IfStatement(pos, cond, ifTrue);

     IfStatement *last = outer;

     while (match(TOK_ELSE)) {

         if (!match(TOK_IF)) {

             Statement *ifFalse = localStatement();

             if (!ifFalse)

                 return NULL;

             last->setIfFalse(ifFalse);

             break;

         }

         SourcePosition pos = scanner_.begin();

         if (!expect(TOK_LPAREN))

             return NULL;

         Expression *otherCond = expression();

         if (!otherCond)

             return NULL;

         if (!expect(TOK_RPAREN))

             return NULL;

         Statement *otherIfTrue = localStatement();

         if (!otherIfTrue)

             return NULL;

         IfStatement *inner = new (pool_) IfStatement(pos, otherCond, otherIfTrue);

         last->setIfFalse(inner);

         last = inner;

     }

     return outer;

 }

 Statement *

 Parser::localStatement()

 {

     Statement *statement = NULL;

     // Statements which must be followed by a semicolon will break out of the

     // switch. If they may end in BlockStatements, they'll immediately return.

     switch (scanner_.peek()) {

         case TOK_NEW:

           if ((statement = variableDeclaration()) == NULL)

               return NULL;

           break;

         case TOK_FOR:

           return forStatement();

         case TOK_WHILE:

           return while_();

         case TOK_BREAK:

           scanner_.scan();

           statement = new (pool_) BreakStatement(scanner_.begin());

           break;

         case TOK_CONTINUE:

           scanner_.scan();

           statement = new (pool_) ContinueStatement(scanner_.begin());

           break;

         case TOK_DO:

           if ((statement = do_()) == NULL)

               return NULL;

           break;

         case TOK_RETURN:

           if ((statement = returnStatement()) == NULL)

               return NULL;

           break;

         case TOK_ENUM:

           if ((statement = enum_()) == NULL)

               return NULL;

           break;

         case TOK_IF:

           return if_();

         case TOK_LBRACE:

           return block();

 	default:

 	  break;

     }

     if (!statement) {

         if ((statement = expressionStatement()) == NULL)

             return NULL;

     }

     if (!expect(TOK_SEMICOLON))

         return NULL;

     return statement;

 }

 Statement *

 Parser::enum_()

 {

     expect(TOK_ENUM);

     SourcePosition pos = scanner_.begin();

     Local<String> name(zone_);

     if (matchName(name.ref())) {

         if (!name)

             return NULL;

         if (BoundName *other = scope_->localLookup(name)) {

             redeclarationError(other);

             return NULL;

         }

         if (!scope_->declareEnum(name, scanner_.begin()))

             return NULL;

     }

     EnumStatement::EntryList *entries = new (pool_) EnumStatement::EntryList();

     if (!expect(TOK_LBRACE))

         return NULL;

     do {

         if (scanner_.peek() == TOK_RBRACE)

             break;

         Local<String> name(zone_, expectName());

         if (!name)

             return NULL;

         if (BoundName *other = scope_->localLookup(name)) {

             redeclarationError(other);

             return NULL;

         }

         NamedConstant *constant = scope_->declareConstant(name, scanner_.begin());

         if (!constant)

             return NULL;

         Expression *expr = NULL;

         if (match(TOK_ASSIGN)) {

             if ((expr = expression()) == NULL)

                 return NULL;

         }

         if (!entries->append(EnumStatement::Entry(constant, expr)))

             return NULL;

     } while (match(TOK_COMMA));

     if (!expect(TOK_RBRACE))

         return NULL;

     return new (pool_) EnumStatement(pos, name, entries);

 }

 Statement *

 Parser::function(TokenKind token)

 {

     Local<String> name(zone_, expectName());

     if (!name)

         return NULL;

     SourcePosition pos = scanner_.begin();

     // The function name goes into the outer (global) scope.

     assert(!scope_->enclosing());

     NamedFunction *fun;

     if (BoundName *other = scope_->localLookup(name)) {

         // We allow a redeclaration if the new type is a public, and the old

         // type was a forward. However, the forward must come first.

         if (other->kind() != BoundName::FUNCTION) {

             redeclarationError(other);

             return NULL;

         }

         fun = other->toNamedFunction();

         if (!fun->isForward() || token != TOK_PUBLIC) {

             redeclarationError(other);

             return NULL;

         }

         // We've got the same name, but the original is a forward, so let it

         // slide and re-use the original declaration.

         fun->setImplemented(scanner_.begin());

     } else {

         fun = scope_->declareFunction(name, scanner_.begin(), token);

         if (!fun)

             return NULL;

     }

     Scope *scope = enterScope(Scope::FUNCTION);

     if (!scope)

         return NULL;

     ParameterList *parameters = new (pool_) ParameterList();

     if (!expect(TOK_LPAREN))

         return NULL;

     if (!match(TOK_RPAREN)) {

         while (true) {