/* vim: set ts=4 sw=4 tw=99 et:
 *
 * Copyright (C) 2012 David Anderson
 *
 * This file is part of SourcePawn.
 *
 * SourcePawn 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.
 * 
 * SourcePawn 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
 * SourcePawn. If not, see http://www.gnu.org/licenses/.
 */
#include <string.h>
#include "Zone.h"
#include "Parser.h"
#include "FixedArray.h"
#include "Heap.h"
#include "Strings.h"
#include "TypeManager.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::peek(TokenKind kind)
{
    return scanner_.peek() == kind;
}

bool
Parser::match(TokenKind kind)
{
    if (!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;
}

BoundName *
Parser::bindType(Handle<String> name)
{
    if (BoundName *binding = scope_->lookup(name))
        return binding;

    return new (pool_) UnboundName(scope_, name);
}

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_FLOAT_LITERAL:
      {
        scanner_.scan();
        double value = Scanner::ParseDouble(scanner_.literal());
        return new (pool_) FloatLiteral(scanner_.begin(), value);
      }

      case TOK_HEX_LITERAL:
      {
        scanner_.scan();
        int value = strtol(scanner_.literal(), NULL, 16);
        return new (pool_) IntegerLiteral(scanner_.begin(), value);
      }

      case TOK_INTEGER_LITERAL:
      {
        scanner_.scan();
        int value = atoi(scanner_.literal());
        return new (pool_) IntegerLiteral(scanner_.begin(), value);
      }

      case TOK_TRUE:
      case TOK_FALSE:
        scanner_.scan();
        return new (pool_) BooleanLiteral(scanner_.begin(), kind);

      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::arrayLiteral(TokenKind kind)
{
    assert(kind == TOK_LBRACE || kind == TOK_LBRACKET);

    TokenKind close = (kind == TOK_LBRACE)
                      ? TOK_RBRACE
                      : TOK_RBRACKET;

    SourcePosition pos = scanner_.begin();

    ExpressionList *list = new (pool_) ExpressionList();
    do {
        if (match(close))
            break;

        Expression *expr = NULL;
        if (kind == TOK_LBRACE) {
            if (peek(TOK_LBRACE))
                expr = arrayLiteral(TOK_LBRACE);
            else
                expr = primitive();
        } else {
            expr = expression();
        }
        if (!expr)
            return NULL;

        if (!list->append(expr))
            return NULL;

        if (!match(TOK_COMMA)) {
            if (!expect(close))
                return NULL;
            break;
        }
    } while (true);

    return new (pool_) ArrayLiteral(pos, kind, list);
}

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;
      }

      case TOK_NAME:
      {
        Local<String> name(zone_, expectName());
        if (!name)
            return NULL;
        return bind(name);
      }

      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::field(Expression *left)
{
    expect(TOK_DOT);

    SourcePosition pos = scanner_.begin();
    Local<String> name(zone_, expectName());
    if (!name)
        return NULL;

    return new (pool_) FieldExpression(pos, left, name);
}

Expression *
Parser::primary()
{
    Expression *expr = prefix();
    if (!expr)
        return NULL;

    for (;;) {
        switch (scanner_.peek()) {
          case TOK_LPAREN:
            if ((expr = call(expr)) == NULL)
                return NULL;
            break;

          case TOK_LBRACKET:
            if ((expr = index(expr)) == NULL)
                return NULL;
            break;

          case TOK_DOT:
            if ((expr = field(expr)) == NULL)
                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 = unary();
        if (!expr)
            return NULL;
        return new (pool_) IncDecExpression(pos, token, expr, false);
      }

      case TOK_MINUS:
      case TOK_NOT:
      case TOK_TILDE:
      {
        scanner_.scan();
        Expression *expr = unary();
        if (!expr)
            return NULL;
        return new (pool_) UnaryExpression(pos, token, expr);
      }

      case TOK_LABEL:
      {
        scanner_.scan();
        Local<String> tag(zone_, zone_->makeSymbol(scanner_.literal(), scanner_.literal_length()));
        if (!tag)
            return NULL;

        BoundName *type = NULL;
        if (tag)
            type = bindType(tag);

        Expression *expr = unary();
        if (!expr)
            return NULL;

        return new (pool_) UnaryExpression(pos, TOK_LABEL, expr, type);
      }

      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) && !match(TOK_PERCENT))
            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 = bitxor();
        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::and_()
{
    Expression *left = equals();
    while (left) {
        if (!match(TOK_AND))
            break;
        SourcePosition pos = scanner_.begin();
        Expression *right = equals();
        if (!right)
            return NULL;
        left = new (pool_) BinaryExpression(pos, TOK_AND, left, right);
    }
    return left;
}

Expression *
Parser::or_()
{
    Expression *left = and_();
    while (left) {
        if (!match(TOK_OR))
            break;
        SourcePosition pos = scanner_.begin();
        Expression *right = and_();
        if (!right)
            return NULL;
        left = new (pool_) BinaryExpression(pos, TOK_OR, left, right);
    }
    return left;
}

Expression *
Parser::ternary()
{
    Expression *cond = or_();
    if (!cond)
        return NULL;
    
    if (!match(TOK_QMARK))
        return cond;

    Expression *left;
    SourcePosition pos = scanner_.begin();
    AutoAllowTags<false> disableTags(scanner_);
    {
        if ((left = expression()) == NULL)
            return NULL;
    }

    if (!expect(TOK_COLON))
        return NULL;

    Expression *right = expression();
    if (!right)
        return NULL;

    return new (pool_) TernaryExpression(pos, cond, left, right);
}

Expression *
Parser::assignment()
{
    Expression *left = ternary();
    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 = ternary();
        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::switch_()
{
    expect(TOK_SWITCH);

    SourcePosition pos = scanner_.begin();

    if (!expect(TOK_LPAREN))
        return NULL;
    Expression *expr = expression();
    if (!expr)
        return NULL;
    if (!expect(TOK_RPAREN))
        return NULL;

    if (!expect(TOK_LBRACE))
        return NULL;

    SourcePosition defaultPos;
    PoolList<Case *> *cases = new (pool_) PoolList<Case *>();

    Statement *defaultCase = NULL;

    while (!peek(TOK_RBRACE)) {
        Expression *expr = NULL;
        ExpressionList *others = NULL;
        if (match(TOK_DEFAULT)) {
            if (defaultCase) {
                cc_.reportError(scanner_.begin(), Message_OneDefaultPerSwitch);
                return NULL;
            }

            defaultPos = scanner_.begin();
        } else {
            if (defaultCase) {
                cc_.reportError(defaultPos, Message_DefaultMustBeLastCase);
                return NULL;
            }

            if (!expect(TOK_CASE))
                return NULL;

            // A limitation in the grammar is that |case <NAME>:| will be
            // detected as a label.
            AutoAllowTags<false> disableTags(scanner_);

            if ((expr = expression()) == NULL)
                return NULL;

            if (peek(TOK_COMMA)) {
                others = new (pool_) ExpressionList();
                while (match(TOK_COMMA)) {
                    Expression *other = expression();
                    if (!other)
                        return NULL;
                    if (!others->append(other))
                        return NULL;
                }
            }
        }

        if (!expect(TOK_COLON))
            return NULL;

        Statement *statement = localStatement();
        if (!statement)
            return NULL;

        if (!peek(TOK_CASE) &&
            !peek(TOK_DEFAULT) &&
            !peek(TOK_RBRACE))
        {
            cc_.reportError(scanner_.begin(), Message_SingleStatementPerCase);
            return NULL;
        }

        if (expr) {
            Case *caze = new (pool_) Case(expr, others, statement);
            if (!cases->append(caze))
                return NULL;
        } else {
            defaultCase = statement;
        }
    }

    if (!expect(TOK_RBRACE))
        return NULL;

    return new (pool_) SwitchStatement(pos, expr, cases, defaultCase);
}

Statement *
Parser::forStatement()
{
    SourcePosition pos = scanner_.begin();
    scanner_.scan();
    if (!expect(TOK_LPAREN))
        return NULL;

    Statement *decl = NULL;
    if (!match(TOK_SEMICOLON)) {
        if (match(TOK_NEW)) {
            if (!enterScope(Scope::BLOCK))
                return NULL;
            if ((decl = vars(TOK_STOCK, TOK_NEW)) == 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() || decl->isBlockStatement())) {
        declScope = scope_->unlinkIfEmpty();
        scope_ = scope_->enclosing();
    }
    return new (pool_) ForStatement(pos, declScope, decl, condition, update, body);
}

ExpressionList *
Parser::dimensions()
{
    ExpressionList *postDimensions = new (pool_) ExpressionList();
    while (match(TOK_LBRACKET)) {
        Expression *dim = NULL;
        if (!match(TOK_RBRACKET)) {
            if ((dim = expression()) == NULL)
                return NULL;
            if (!expect(TOK_RBRACKET))
                return NULL;
        }

        if (!postDimensions->append(dim))
            return NULL;
    }
    return postDimensions;
}

VariableDeclaration *
Parser::var(TokenKind scope, TokenKind kind)
{
    Local<String> tag(zone_);
    if (matchName(tag.ref(), TOK_LABEL) && !tag)
        return NULL;

    BoundName *type = NULL;
    if (tag)
        type = bindType(tag);

    Local<String> name(zone_, expectName());
    if (!name)
        return NULL;

    SourcePosition pos = scanner_.begin();

    if (BoundName *other = scope_->localLookup(name)) {
        redeclarationError(other);
        return NULL;
    }

    ExpressionList *postDimensions = NULL;
    if (peek(TOK_LBRACKET)) {
        if ((postDimensions = dimensions()) == NULL)
            return NULL;
    }
    
    Expression *expr = NULL;
    if (match(TOK_ASSIGN)) {
        switch (scanner_.peek()) {
          // Note: we don't support [] literals yet.
          case TOK_LBRACE:
            if ((expr = arrayLiteral(scanner_.scan())) == NULL)
                return NULL;
            break;

          default:
            if ((expr = expression()) == NULL)
                return NULL;
            break;
        }
    }

    Variable *var = scope_->declareVariable(name, pos);
    if (!var)
        return NULL;

    if (scope == TOK_PUBLIC)
        var->setPublic();

    return new (pool_) VariableDeclaration(var->pos(), kind, var, type, postDimensions, expr);
}

Statement *
Parser::vars(TokenKind scope, TokenKind kind)
{
    VariableDeclaration *decl = var(scope, kind);
    if (!decl)
        return NULL;

    if (!peek(TOK_COMMA))
        return decl;

    StatementList *statements = new (pool_) StatementList();
    if (!statements->append(decl))
        return NULL;

    while (match(TOK_COMMA)) {
        Statement *decl = var(scope, kind);
        if (!decl)
            return NULL;
        if (!statements->append(decl))
            return NULL;
    }

    // Create a fake-o block with no scope to create a statement list.
    return new (pool_) BlockStatement(decl->pos(), NULL, statements);
}

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.

    TokenKind kind = scanner_.peek();
    switch (kind) {
      case TOK_CONST:
      case TOK_NEW:
        scanner_.scan();
        if ((statement = vars(TOK_STOCK, kind)) == 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_STRUCT:
        if ((statement = struct_()) == NULL)
          return NULL;
        break;

      case TOK_SWITCH:
        return switch_();

      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::struct_()
{
    expect(TOK_STRUCT);

    Local<String> name(zone_, expectName());
    if (!name)
        return NULL;

    SourcePosition pos = scanner_.begin();

    if (BoundName *other = scope_->localLookup(name)) {
        redeclarationError(other);
        return NULL;
    }

    NamedType *type;
    if ((type = scope_->declareType(name, scanner_.begin())) == NULL)
        return NULL;

    if (!expect(TOK_LBRACE))
        return NULL;

    FieldList *fields = new (pool_) FieldList();

    while (!peek(TOK_RBRACE)) {
        if (matchName(name.ref(), TOK_LABEL) && !name)
            return NULL;

        BoundName *type = NULL;
        if (name) {
            if ((type = bindType(name)) == NULL)
                return NULL;
        }

        name = expectName();
        if (!name)
            return NULL;

        SourcePosition pos = scanner_.begin();

        ExpressionList *postDimensions = NULL;
        //if (peek(TOK_LBRACKET)) {
        //    if ((postDimensions = dimensions()) == NULL)
        //        return NULL;
        //}

        if (!matchSemicolon())
            return NULL;

        StructureStatement::Field *field =
            new (pool_) StructureStatement::Field(pos, type, name, postDimensions);
        if (!field || !fields->append(field))
            return NULL;
    }

    if (!expect(TOK_RBRACE))
        return NULL;

    if (fields->empty()) {
        cc_.reportError(pos, Message_StructCantBeEmpty);
        return NULL;
    }

    return new (pool_) StructureStatement(pos, type, fields);
}

Statement *
Parser::enum_()
{
    expect(TOK_ENUM);

    NamedType *type = NULL;
    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 ((type = scope_->declareType(name, scanner_.begin())) == NULL)
            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, type, name, entries);
}

Statement *
Parser::function(TokenKind token)
{
    Local<String> returnTag(zone_);
    if (token == TOK_LABEL) {
        returnTag = zone_->makeSymbol(scanner_.literal(), scanner_.literal_length());
        if (!returnTag)
            return NULL;

        token = TOK_STOCK;
    } else {
        if (peek(TOK_LABEL)) {
            if (matchName(returnTag.ref(), TOK_LABEL) && !returnTag)
                return NULL;
        } else if (peek(TOK_NAME)) {
            // Peek for a type that has no :
            returnTag = expectName();
            if (!returnTag)
                return NULL;
        }
    }

    Local<String> name(zone_);
    ExpressionList *returnDimensions = NULL;

    bool allowArrayReturns = token != TOK_NATIVE &&
                             token != TOK_PUBLIC &&
                             token != TOK_FORWARD;

    if (allowArrayReturns && peek(TOK_LBRACKET)) {
        if ((returnDimensions = dimensions()) == NULL)
            return NULL;
        if ((name = expectName()) == NULL)
            return NULL;
    } else if (peek(TOK_NAME)) {
        if ((name = expectName()) == NULL)
            return NULL;
    } else {
        // We predicted |type name|, but just got |name| instead.
        name = returnTag;
        returnTag = NULL;
    }

    BoundName *returnType = NULL;
    if (returnTag)
        returnType = bindType(returnTag);

    SourcePosition pos = scanner_.begin();

    // The function name goes into the outer (global) scope.
    assert(!scope_->enclosing());

    NamedType *type = NULL;
    NamedFunction *fun = NULL;
    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 (token == TOK_TYPEDEF || 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 if (token == TOK_TYPEDEF) {
        type = scope_->declareType(name, scanner_.begin());
        if (!type)
            return NULL;
    } else {
        fun = scope_->declareFunction(name, scanner_.begin(), token);
        if (!fun)
            return NULL;
    }

    if (fun && fun->isPublic())
        fun->setUsed();

    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) {
            bool isConst = match(TOK_CONST);
            bool ref = match(TOK_AMPERSAND);

            SourcePosition begin = scanner_.begin();
            Local<String> tag(zone_);
            if (matchName(tag.ref(), TOK_LABEL) && !tag)
                return NULL;

            BoundName *type = NULL;
            if (tag)
                type = bindType(tag);

            if (match(TOK_ELLIPSES)) {
                if (isConst || ref) {
                    cc_.reportError(begin, Message_InvalidVarArgs);
                    return NULL;
                }

                if (token != TOK_NATIVE) {
                    cc_.reportError(begin, Message_VarArgsOutsideNative);
                    return NULL;
                }

                fun->markNativeVariadic();
                break;
            }

            Local<String> name(zone_, expectName());
            if (!name)
                return NULL;

            if (BoundName *other = scope_->localLookup(name)) {
                redeclarationError(other);
                return NULL;
            }
            Variable *arg = scope_->declareArgument(name, scanner_.begin());
            if (!arg)
                return NULL;

            // Look for dimensions.
            ExpressionList *postDimensions = NULL;
            if (peek(TOK_LBRACKET)) {
                if ((postDimensions = dimensions()) == NULL)
                    return NULL;
            }

            Expression *expr = NULL;
            if (match(TOK_ASSIGN)) {
                if ((expr = expression()) == NULL)
                    return NULL;
            }

            Parameter *parameter = new (pool_) Parameter(arg, type, ref, isConst, postDimensions,
                                                         expr);
            if (!parameters->append(parameter))
                return NULL;

            if (!match(TOK_COMMA))
                break;
        }
        if (!expect(TOK_RPAREN))
            return NULL;
    }

    encounteredReturn_ = false;

    Statement *body = NULL;
    if (token != TOK_FORWARD && token != TOK_NATIVE && token != TOK_TYPEDEF) {
        body = block();
        if (!body)
            return NULL;
    }

    scope_ = scope_->enclosing();

    FunctionSignature signature(returnType, returnDimensions, parameters);
    if (token == TOK_TYPEDEF)
        return new (pool_) FunctionTypeStatement(pos, type, signature);

    return new (pool_) FunctionStatement(pos, scope, fun, body, signature, encounteredReturn_);
}

static inline bool
DeclareIntrinsicType(Zone *zone, Scope *scope, const char *name, Handle<Type> type)
{
    Local<String> tag(zone, zone->makeSymbol(name));
    if (!tag)
        return false;

    return !!scope->declareType(tag, type);
}

static inline bool
DeclareIntrinsicType(Zone *zone, Scope *scope, const char *name, PrimitiveType type)
{
    Local<Type> primitive(zone, zone->types()->getPrimitive(type));
    assert(primitive);
    return DeclareIntrinsicType(zone, scope, name, primitive);
}

bool
Parser::setupIntrinsics()
{
    if (!DeclareIntrinsicType(zone_, scope_, "Float", PrimitiveType_Float))
        return false;
    if (!DeclareIntrinsicType(zone_, scope_, "_", PrimitiveType_Int32))
        return false;
    if (!DeclareIntrinsicType(zone_, scope_, "bool", PrimitiveType_Bool))
        return false;
    if (!DeclareIntrinsicType(zone_, scope_, "String", PrimitiveType_Char))
        return false;

    Local<Type> unchecked(zone_, zone_->types()->getUnchecked());
    if (!DeclareIntrinsicType(zone_, scope_, "unchecked", unchecked))
        return false;

    Local<Type> voidType(zone_, zone_->types()->getVoid());
    if (!DeclareIntrinsicType(zone_, scope_, "void", voidType))
        return false;

    Local<Type> intType(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
    if (!DeclareIntrinsicType(zone_, scope_, "int", intType))
        return false;

    return true;
}

ParseTree *
Parser::parse()
{
    StatementList *statements = new (pool_) StatementList();

    if (!enterScope(Scope::GLOBAL))
        return NULL;

    if (!setupIntrinsics())
        return NULL;

    for (;;) {
        Statement *statement = NULL;

        TokenKind kind = scanner_.peek();
        switch (kind) {
          case TOK_ERROR:
            return NULL;

          case TOK_EOF:
            break;

          case TOK_NAME:
            if ((statement = function(TOK_NAME)) == NULL)
                return NULL;
            break;

          case TOK_FORWARD:
          case TOK_PUBLIC:
          case TOK_NATIVE:
          case TOK_STOCK:
          case TOK_LABEL:
          case TOK_TYPEDEF:
          {
            scanner_.scan();
            if (kind == TOK_PUBLIC && peek(TOK_CONST)) {
                if ((statement = var(TOK_PUBLIC, scanner_.scan())) == NULL)
                    return NULL;
                if (!matchSemicolon())
                    return NULL;
            } else {
                if ((statement = function(kind)) == NULL)
                    return NULL;
                if ((kind == TOK_FORWARD || kind == TOK_NATIVE || kind == TOK_TYPEDEF) && !matchSemicolon())
                    return NULL;
            }
            break;
          }

          case TOK_CONST:
          case TOK_NEW:
          {
            // Note: at global scope, we don't accept comma-delimited
            // declarations yet, to see if we can get away with forcing
            // a nicer top-level style.
            scanner_.scan();
            if ((statement = var(TOK_STOCK, kind)) == NULL)
                return NULL;
            if (!matchSemicolon())
                return NULL;
            break;
          }

          case TOK_ENUM:
            if ((statement = enum_()) == NULL)
                return NULL;
            if (!matchSemicolon())
                return NULL;
            break;

          case TOK_STRUCT:
            if ((statement = struct_()) == NULL)
                return NULL;
            if (!matchSemicolon())
                return NULL;
            break;

          default:
            cc_.reportError(scanner_.begin(), Message_ExpectedGlobal);
            return NULL;
        }

        if (!statement)
            break;

        if (!statements->append(statement))
            return NULL;
    }

    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 dump(const FunctionSignature &sig) {
        prefix();
        fprintf(fp_, "%s", sig.returnType()
                           ? sig.returnType()->name()->chars()
                           : "_");
        if (sig.returnDimensions()) {
            for (size_t i = 0; i < sig.returnDimensions()->length(); i++)
                fprintf(fp_, "[]");
        }
        fprintf(fp_, "()\n");
    }
    void visit(NameProxy *name) {
        prefix();
        fprintf(fp_, "[ NameProxy (%s)%s\n", name->name()->chars(),
                (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()->length(); i++)
            node->arguments()->at(i)->accept(this);
        unindent();
    }
    void visit(FunctionTypeStatement *node) {
        prefix();
        fprintf(fp_, "[ FunctionTypeStatement (%s)\n", node->decl()->name()->chars());
        indent();
        dump(node->signature());
        unindent();
    }
    void visit(FunctionStatement *node) {
        prefix();
        fprintf(fp_, "[ FunctionStatement (%s)\n", node->fun()->name()->chars());
        indent();
        dump(node->signature());
        if (node->body())
            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(TernaryExpression *node) {
        prefix();
        fprintf(fp_, "[ TernaryExpression\n");
        indent();
        node->condition()->accept(this);
        node->left()->accept(this);
        node->right()->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(UnaryExpression *node) {
        prefix();
        fprintf(fp_, "[ UnaryExpression (%s)\n", TokenNames[node->token()]);
        indent();
        node->expression()->accept(this);
        unindent();
    }
    void visit(ReturnStatement *node) {
        prefix();
        fprintf(fp_, "[ ReturnStatement\n");
        indent();
        if (node->expression())
            node->expression()->accept(this);
        unindent();
    }
    void visit(ForStatement *node) {
        prefix();
        fprintf(fp_, "[ ForStatement\n");
        indent();
        if (node->initialization())
            node->initialization()->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()->chars());
        indent();
        if (node->initialization())
            node->initialization()->accept(this);
        unindent();
    }
    void visit(IntegerLiteral *node) {
        prefix();
        fprintf(fp_, "[ IntegerLiteral (%d)\n", node->value());
    }
    void visit(BooleanLiteral *node) {
        prefix();
        fprintf(fp_, "[ BooleanLiteral (%s)\n",
                (node->token() == TOK_TRUE) ? "true" : "false");
    }
    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()->chars() : "<anonymous>");
        indent();
        for (size_t i = 0; i < node->entries()->length(); i++) {
            prefix();
            fprintf(fp_, "%s =\n", node->entries()->at(i).name->name()->chars());
            if (node->entries()->at(i).expr) {
                indent();
                node->entries()->at(i).expr->accept(this);
                unindent();
            }
        }
        unindent();
    }
    void visit(WhileStatement *node) {
        prefix();
        fprintf(fp_, "[ WhileStatement (%s)\n",
                (node->token() == TOK_DO) ? "do" : "while");
        indent();
        if (node->token() == TOK_DO) {
            node->condition()->accept(this);
            node->body()->accept(this);
        } else {
            node->condition()->accept(this);
            node->body()->accept(this);
        }
        unindent();
    }
    void visit(BreakStatement *node) {
        prefix();
        fprintf(fp_, "[ BreakStatement\n");
    }
    void visit(ContinueStatement *node) {
        prefix();
        fprintf(fp_, "[ ContinueStatement\n");
    }
    void visit(StringLiteral *node) {
        prefix();
        fprintf(fp_, "[ StringLiteral\n");
    }
    void visit(IncDecExpression *node) {
        prefix();
        fprintf(fp_, "[ IncDecExpression (postfix=%d)\n", node->postfix());
        indent();
        node->expression()->accept(this);
        unindent();
    }
    void visit(StructureStatement *node) {
        prefix();
        fprintf(fp_, "[ StructureStatement %s\n", node->decl()->name()->chars());
    }
    void visit(FieldExpression *node) {
        prefix();
        fprintf(fp_, "[ FieldExpression %s\n", node->field()->chars());
        indent();
        node->left()->accept(this);
        unindent();
    }
    void visit(SwitchStatement *node) {
        prefix();
        fprintf(fp_, "[ SwitchStatement\n");
        indent();
        node->expression()->accept(this);
        for (size_t i = 0; i < node->cases()->length(); i++) {
            Case *c = node->cases()->at(i);
            c->expression()->accept(this);
            if (c->others()) {
                for (size_t j = 0; j < c->others()->length(); j++)
                    c->others()->at(j)->accept(this);
            }
            indent();
            c->statement()->accept(this);
            unindent();
        }
        if (node->defaultCase())
            node->defaultCase()->accept(this);
        unindent();
    }
    void visit(ArrayLiteral *node) {
        prefix();
        fprintf(fp_, "[ ArrayLiteral\n");
        indent();
        for (size_t i = 0; i < node->expressions()->length(); i++) {
            Expression *expr = node->expressions()->at(i);
            indent();
            expr->accept(this);
            unindent();
        }
    }
};

void
ParseTree::dump(FILE *fp)
{
    AstPrinter printer(fp);

    for (size_t i = 0; i < statements_->length(); i++)
        statements_->at(i)->accept(&printer);
}