/*

  * 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"

 using namespace jc;

 Parser::Parser(const char *stream, size_t length)

   : pool_(ZONE()->pool()),

     strings_(pool_),

     scanner_(stream, length),

     scope_(NULL),

     unbound_(NULL)

 {

     unbound_ = new std::vector<NameProxy *>();

 }

 bool

 Parser::match(TokenKind kind)

 {

     if (scanner_.peek() != kind)

         return false;

     scanner_.scan();

     return true;

 }

 bool

 Parser::expect(TokenKind kind)

 {

     TokenKind got = scanner_.scan();

     if (got == kind)

         return true;

     fprintf(stderr, "error: expected %s, got %s\n", 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(Name *name)

 {

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

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

     if (!bound)

         unbound_->push_back(proxy);

     return proxy;

 }

 bool

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

 {

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

     *name = NULL;

     if (!match(kind))

         return false;

     *name = strings_.add(scanner_.literal());

     return true;

 }

 Name *

 Parser::expectName()

 {

     if (!expect(TOK_NAME))

         return NULL;

     return strings_.add(scanner_.literal());

 }

 Expression *

 Parser::primitive()

 {

     switch (scanner_.peek()) {

       case TOK_NAME:

       {

         scanner_.scan();

         Name *name = strings_.add(scanner_.literal());

         return bind(name);

       }

       case TOK_FLOAT_LITERAL:

       {

         scanner_.scan();

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

         return new (pool_) FloatLiteral(value);

       }

       case TOK_INTEGER_LITERAL:

       {

         scanner_.scan();

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

         return new (pool_) IntegerLiteral(value);

       }

       default:

       {

         fprintf(stderr, "error: expected expression!\n");

         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 ExpressionList();

     expect(TOK_LPAREN);

     if (!match(TOK_RPAREN)) {

         while (true) {

             Expression *expr = expression();

             if (!expr)

                 return NULL;

             arguments->push_back(expr);

             if (!match(TOK_COMMA))

                 break;

         }

         if (!expect(TOK_RPAREN))

             return NULL;

     }

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

 }

 Expression *

 Parser::index(Expression *left)

 {

     expect(TOK_LBRACKET);

     Expression *expr = expression();

     if (!expr)

         return NULL;

     if (!expect(TOK_RBRACKET))

         return NULL;

     return new (pool_) IndexExpression(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()

 {

     return primary();

 }

 Expression *

 Parser::multiplication()

 {

     Expression *left = unary();

     do {

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

             break;

         TokenKind kind = scanner_.last();

         Expression *right = unary();

         if (!right)

             return NULL;

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

     } while (left);

     return left;

 }

 Expression *

 Parser::addition()

 {

     Expression *left = multiplication();

     while (left) {

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

             break;

         TokenKind kind = scanner_.last();

         Expression *right = multiplication();

         if (!right)

             return NULL;

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

     }

     return left;

 }

 Expression *

 Parser::shift()

 {

     Expression *left = addition();

     while (left) {

         if (!match(TOK_SHL))

             break;

         TokenKind kind = scanner_.last();

         Expression *right = addition();

         if (!right)

             return NULL;

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

     }

     return left;

 }

 Expression *

 Parser::relational()

 {

     Expression *left = shift();

     while (left) {

         TokenKind kind = scanner_.peek();

         if (kind < TOK_LT || kind > TOK_GE)

             break;

         scanner_.scan();

         Expression *right = shift();

         if (!right)

             return NULL;

         left = new (pool_) BinaryExpression(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();

         Expression *right = relational();

         if (!right)

             return NULL;

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

     }

     return left;

 }

 Expression *

 Parser::expression()

 {

     return equals();

 }

 Statement *

 Parser::forStatement()

 {

     scanner_.scan();

     if (!expect(TOK_LPAREN))

         return NULL;

     VariableDeclaration *decl = NULL;

     if (!match(TOK_SEMICOLON)) {

         if (!enterScope(Scope::BLOCK))

             return NULL;

         if ((decl = variableDeclaration()) == 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;

     }

     Statement *body = localStatement();

     if (!body)

         return NULL;

     Scope *blockScope = NULL;

     if (decl) {

         blockScope = scope_->unlinkIfEmpty();

         scope_ = scope_->enclosing();

     }

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

 }

 VariableDeclaration *

 Parser::variableDeclaration()

 {

     if (!expect(TOK_NEW))

         return NULL;

     Name *tag;

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

         return NULL;

     Name *name = expectName();

     if (!name)

         return NULL;

     ExpressionList *postDimensions = NULL;

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

         postDimensions = new ExpressionList();

         while (match(TOK_LBRACKET)) {

             Expression *dim = expression();

             if (!dim)

                 return NULL;

             if (!expect(TOK_RBRACKET))

                 return NULL;

             postDimensions->push_back(dim);

         }

     }

     Expression *expr = NULL;

     if (match(TOK_ASSIGN)) {

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

             return NULL;

     }

     if (scope_->localLookup(name)) {

         redeclarationError();

         return NULL;

     }

     Variable *var = scope_->declareVariable(name);

     VariableDeclaration *decl = new (pool_) VariableDeclaration(var, tag, postDimensions, expr);

     return decl;

 }

 Statement *

 Parser::returnStatement()

 {

     if (!expect(TOK_RETURN))

         return NULL;

     Expression *expr = expression();

     if (!expr)

         return NULL;

     return new (pool_) ReturnStatement(expr);

 }

 Statement *

 Parser::expressionStatement()

 {

     Expression *left = primary();

     if (!left) {

         fprintf(stderr, "expected expression or statement\n");

         return NULL;

     }

     if (match(TOK_ASSIGN)) {

         Expression *expr = expression();

         if (!expr)

             return NULL;

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

     }

     return new (pool_) ExpressionStatement(left);

 }

 Statement *

 Parser::block()

 {

     if (!expect(TOK_LBRACE))

         return NULL;

     if (!enterScope(Scope::BLOCK))

         return NULL;

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

     while (!match(TOK_RBRACE)) {

         Statement *statement = localStatement();

         if (statement == NULL)

             return NULL;

         statements->append(pool_, statement);

     }

     Scope *blockScope = scope_->unlinkIfEmpty();

     BlockStatement *block = new (pool_) BlockStatement(blockScope, statements);

     scope_ = scope_->enclosing();

     return block;

 }

 Statement *

 Parser::if_()

 {

     expect(TOK_IF);

     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(cond, ifTrue);

     IfStatement *last = outer;

     while (match(TOK_ELSE)) {

         if (!match(TOK_IF)) {

             Statement *ifFalse = localStatement();

             if (!ifFalse)

                 return NULL;

             last->setIfFalse(ifFalse);

             break;

         }

         if (!expect(TOK_IF))

             return false;

         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(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:

           statement = variableDeclaration();

           break;

         case TOK_FOR:

           return forStatement();

         case TOK_RETURN:

           statement = returnStatement();

           break;

         case TOK_ENUM:

           statement = enum_();

           break;

         case TOK_IF:

           return if_();

         case TOK_LBRACE:

           return block();

     }

     if (!statement) {

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

             return NULL;

     }

     if (!expect(TOK_SEMICOLON))

         return NULL;

     return statement;

 }

 Statement *

 Parser::enum_()

 {

     expect(TOK_ENUM);

     Name *name = NULL;

     if (match(TOK_NAME)) {

         if ((name = strings_.add(scanner_.literal())) == NULL)

             return NULL;

         if (scope_->localLookup(name)) {

             redeclarationError();

             return NULL;

         }

         NamedEnum *e = scope_->declareEnum(name);

         if (!e)

             return NULL;

     }

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

     if (!expect(TOK_LBRACE))

         return NULL;

     do {

         if (scanner_.peek() == TOK_RBRACE)

             break;

         Name *name = expectName();

         if (!name)

             return NULL;

         if (scope_->localLookup(name)) {

             redeclarationError();

             return NULL;

         }

         NamedConstant *constant = scope_->declareConstant(name);

         if (!constant)

             return NULL;

         Expression *expr = NULL;

         if (match(TOK_ASSIGN)) {

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

                 return NULL;

         }

         entries->push_back(EnumStatement::Entry(constant, expr));

     } while (match(TOK_COMMA));

     if (!expect(TOK_RBRACE))

         return NULL;

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

 }

 Statement *

 Parser::function()

 {

     Name *name = expectName();

     if (!name)

         return NULL;

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

     assert(!scope_->enclosing());

     if (scope_->localLookup(name)) {

         redeclarationError();

         return NULL;

     }

     NamedFunction *fun = scope_->declareFunction(name);

     if (!fun)

         return NULL;

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

     if (!scope)

         return NULL;

     if (!expect(TOK_LPAREN))

         return NULL;

     if (!match(TOK_RPAREN)) {

         while (true) {

             Name *name = expectName();

             if (!name)

                 return NULL;

             if (scope_->localLookup(name)) {

                 redeclarationError();

                 return NULL;

             }

             if (!scope_->declareArgument(name))

                 return NULL;

             if (!match(TOK_COMMA))

                 break;

         }

         if (!expect(TOK_RPAREN))

             return NULL;

     }

     Statement *body = block();

     if (!body)

         return NULL;

     scope_ = scope_->enclosing();

     return new (pool_) FunctionStatement(scope, fun, body);

 }

 ParseTree *

 Parser::parse()

 {

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

     if (!enterScope(Scope::GLOBAL))

         return NULL;

     for (;;) {

         Statement *statement = NULL;

         switch (scanner_.peek()) {

           case TOK_ERROR:

             return NULL;

           case TOK_EOF:

             break;

           case TOK_NAME:

             if ((statement = function()) == NULL)

                 return NULL;

             break;

           case TOK_ENUM:

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

                 return NULL;

             // :TODO: require semicolon

             break;

           default:

             fprintf(stderr, "expected function or global variable\n");

             return NULL;

         }

         if (!statement)

             break;

         statements->append(pool_, statement);

     }

     return new (pool_) ParseTree(scope_, statements, unbound_);

 }

 class AstPrinter : public AstVisitor

 {

     FILE *fp_;

     size_t level_;

   private:

     void prefix() {

         for (size_t i = 0; i < level_; i++)

             fprintf(fp_, "  ");

     }

     void indent() {

         level_++;

     }

     void unindent() {

         level_--;

     }

   public:

     AstPrinter(FILE *fp)

       : fp_(fp),

         level_(0)

     {

     }

     void visit(NameProxy *name) {

         prefix();

         fprintf(fp_, "[ NameProxy (%s)%s\n", name->name(),

                 (name->binding() ? "" : " unbound"));

     }

     void visit(CallExpression *node) {

         prefix();

         fprintf(fp_, "[ CallExpression\n");

         indent();

         node->callee()->accept(this);

         for (size_t i = 0; i < node->arguments()->size(); i++)

             node->arguments()->at(i)->accept(this);

         unindent();

     }

     void visit(FunctionStatement *node) {

         prefix();

         fprintf(fp_, "[ FunctionStatement (%s)\n", node->fun()->name());

         indent();

         node->body()->accept(this);

         unindent();

     }

     void visit(ExpressionStatement *node) {

         prefix();

         fprintf(fp_, "[ ExpressionStatement\n");

         indent();

         node->expression()->accept(this);

         unindent();

     }

     void visit(Assignment *node) {

         prefix();

         fprintf(fp_, "[ Assignment\n");

         indent();

         node->lvalue()->accept(this);

         node->expression()->accept(this);

         unindent();

     }

     void visit(BinaryExpression *node) {

         prefix();

         fprintf(fp_, "[ BinaryExpression (%s)\n", TokenNames[node->token()]);

         indent();

         node->left()->accept(this);

         node->right()->accept(this);

         unindent();

     }

     void visit(ReturnStatement *node) {

         prefix();

         fprintf(fp_, "[ ReturnStatement\n");

         indent();

         node->expression()->accept(this);

         unindent();

     }

     void visit(ForStatement *node) {

         prefix();

         fprintf(fp_, "[ ForStatement\n");

         indent();

         if (node->declaration())

             node->declaration()->accept(this);

         if (node->condition())

             node->condition()->accept(this);

         if (node->update())

             node->update()->accept(this);

         node->body()->accept(this);

         unindent();

     }

     void visit(BlockStatement *node) {

         prefix();

         fprintf(fp_, "[ BlockStatement\n");

         indent();

         for (size_t i = 0; i < node->statements()->length(); i++)

             node->statements()->at(i)->accept(this);

         unindent();

     }

     void visit(VariableDeclaration *node) {

         prefix();

         fprintf(fp_, "[ VariableDeclaration (%s)\n", node->variable()->name());

         indent();

         if (node->initialization())

             node->initialization()->accept(this);

         unindent();

     }

     void visit(IntegerLiteral *node) {

         prefix();

         fprintf(fp_, "[ IntegerLiteral (%d)\n", node->value());

     }

     void visit(FloatLiteral *node) {

         prefix();

         fprintf(fp_, "[ FloatLiteral (%f)\n", node->value());

     }

     void visit(IfStatement *node) {

         prefix();

         fprintf(fp_, "[ IfStatement\n");

         indent();

         node->ifTrue()->accept(this);

         if (node->ifFalse())

             node->ifFalse()->accept(this);

         unindent();

     }

     void visit(IndexExpression *node) {

         prefix();

         fprintf(fp_, "[ IndexExpression\n");

         indent();

         node->left()->accept(this);

         node->right()->accept(this);

         unindent();

     }

     void visit(EnumStatement *node) {

         prefix();

         fprintf(fp_, "[ EnumStatement (%s)\n", node->name() ? node->name() : "<anonymous>");

         indent();

         for (size_t i = 0; i < node->entries()->size(); i++) {

             prefix();

             fprintf(fp_, "%s =\n", node->entries()->at(i).name->name());

             if (node->entries()->at(i).expr) {

                 indent();

                 node->entries()->at(i).expr->accept(this);

                 unindent();

             }

         }

         unindent();

     }

 };

 void

 ParseTree::dump(FILE *fp)

 {

     AstPrinter printer(fp);

     for (size_t i = 0; i < statements_->length(); i++)

         statements_->at(i)->accept(&printer);

 }