/* 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 "../FixedArray.h"
#include "../Heap.h"
#include "../Strings.h"
#include "../TypeManager.h"
#include "Parser.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),
    unbound_(NULL)
{
    unbound_ = new (pool_) PoolList<NameProxy *>();
    imports_ = new (pool_) PoolList<ImportStatement *>();
}

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

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

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 new (pool_) NameProxy(scanner_.begin(), name);
      }

      default:
        return primitive();
    }
}

// Parses only old-style declarations.
bool
Parser::typeAndName(Expression **type, String **namep)
{
    if (match(TOK_LABEL)) {
        // Old-style declaration:
        //   new X:type
        Local<String> name(zone_, zone_->makeSymbol(scanner_.literal(), scanner_.literal_length()));
        if (!name)
            return false;

        *type = new (pool_) NameProxy(scanner_.begin(), name);
        *namep = expectName();
        return !!*namep;
    }
    
    *type = NULL;
    *namep = expectName();

    return !!*namep;
}

// Parses both old and new style declarations.
bool
Parser::fullTypeAndName(Expression **type, String **namep, DeclKind kind)
{
    // Declaration:
    //   NewDecl ::= Type Ident
    //   OldDecl ::= Label? (Ident | "...")
    //   Type    ::= Ident
    //   Label   ::= Ident ":"
    //
    if (match(TOK_LABEL)) {
        // We something of the form:
        //     Label Ident
        // or: Label "..."
        Local<String> name(zone_, zone_->makeSymbol(scanner_.literal(), scanner_.literal_length()));
        if (!name)
            return false;

        *type = new (pool_) NameProxy(scanner_.begin(), name);
        if (kind == DeclArg && match(TOK_ELLIPSES)) {
            *namep = NULL;
        } else {
            if ((*namep = expectName()) == NULL)
                return false;
        }
        return true;
    }

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

    if (peek(TOK_NAME) || (kind == DeclArg && peek(TOK_ELLIPSES))) {
        // We got something of the form:
        //    Ident Ident
        *type = new (pool_) NameProxy(scanner_.begin(), name);
        if (peek(TOK_NAME)) {
            if ((*namep = expectName()) == NULL)
                return false;
        } else {
            *namep = NULL;
        }
        return true;
    }

    // We got something of the form:
    //    Ident
    *type = NULL;
    *namep = name;
    return true;
}

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_SIZEOF:
      {
        scanner_.scan();
        if (!expect(TOK_LPAREN))
            return NULL;
        Expression *expr = unary();
        if (!expr)
            return NULL;
        if (!expect(TOK_RPAREN))
            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;

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

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

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

      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;

    Statement *body;
    if (scanner_.peek() == TOK_LBRACE)
        body = block();
    else
        body = localStatement();
    if (!body)
        return NULL;

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

Statement *
Parser::do_()
{
    SourcePosition pos = scanner_.begin();
    scanner_.scan();

    Statement *body;
    if (scanner_.peek() == TOK_LBRACE)
        body = block();
    else
        body = localStatement();
    if (!body)
        return NULL;

    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 ((decl = vars(Qual_None)) == 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;
    }

    Statement *body;
    if (scanner_.peek() == TOK_LBRACE)
        body = block();
    else
        body = localStatement();
    if (!body)
        return NULL;

    return new (pool_) ForStatement(pos, 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(TypeQualifiers qual)
{
    Expression *type;
    Local<String> name(zone_);
    
    if (!typeAndName(&type, name.ref()))
        return NULL;

    ExpressionList *dims = NULL;
    if (match(TOK_LBRACE)) {
        if ((dims = dimensions()) == NULL)
            return NULL;;
    }

    SourcePosition pos = scanner_.begin();
    
    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;
        }
    }

    return new (pool_) VariableDeclaration(pos, qual, name, type, dims, expr);
}

Statement *
Parser::vars(TypeQualifiers qual)
{
    VariableDeclaration *decl = var(qual);
    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(qual);
        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(), 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()
{
    if (!expect(TOK_LBRACE))
        return NULL;

    SourcePosition pos = scanner_.begin();

    StatementList *statements = new (pool_) StatementList();
    while (!match(TOK_RBRACE)) {
        Statement *statement = localStatement();
        if (statement == NULL)
            return NULL;
        if (!statements->append(statement))
            return NULL;
    }

    BlockStatement *block = new (pool_) BlockStatement(pos, 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:
      {
        TypeQualifiers quals = (kind == TOK_CONST)
                              ? Qual_Const
                              : Qual_None;
        scanner_.scan();
        if ((statement = vars(quals)) == 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 (!expect(TOK_LBRACE))
        return NULL;

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

    while (!peek(TOK_RBRACE)) {
        Expression *type;
        Local<String> fieldName(zone_);

        if (!fullTypeAndName(&type, fieldName.ref(), DeclField))
            return NULL;

        SourcePosition pos = scanner_.begin();

        if (!matchSemicolon())
            return NULL;

        StructureStatement::Field *field =
            new (pool_) StructureStatement::Field(pos, type, fieldName);
        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, name, fields);
}

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

    SourcePosition pos = scanner_.begin();

    Local<String> name(zone_);
    if (matchName(name.ref()) && !name)
        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;

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

        if (!entries->append(EnumStatement::Entry(name, expr)))
            return NULL;
    } while (match(TOK_COMMA));
    if (!expect(TOK_RBRACE))
        return NULL;

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

template <class T>
static inline ScopedRoot<T> *
NewScopedRoot(PoolAllocator &pool, Handle<T> obj)
{
    ScopedRoot<T> *root = pool.alloc<ScopedRoot<T> >();
    new (root) ScopedRoot<T>(obj);
    return root;
}

ImportStatement *
Parser::import()
{
    NameList *names = new (pool_) NameList();

    SourcePosition pos = scanner_.begin();

    Local<String> name(zone_, expectName());
    if (!name || !names->append(NewScopedRoot<String>(pool_, name)))
        return NULL;

    TokenKind suffix = TOK_NONE;
    while (match(TOK_DOT)) {
        if (match(TOK_STAR)) {
            suffix = TOK_STAR;
            break;
        }

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

        if (!names->append(NewScopedRoot<String>(pool_, name)))
            return NULL;
    }

    return new (pool_) ImportStatement(pos, names, suffix);
}

Statement *
Parser::function(TokenKind token)
{
    Expression *returnType;
    Local<String> name(zone_);

    if (!fullTypeAndName(&returnType, name.ref(), DeclFun))
        return NULL;

    SourcePosition pos = scanner_.begin();
    ParameterList *parameters = new (pool_) ParameterList();

    if (!expect(TOK_LPAREN))
        return NULL;

    bool variadic = false;

    if (!match(TOK_RPAREN)) {
        while (true) {
            bool isConst = match(TOK_CONST);
            bool ref = match(TOK_AMPERSAND);

            SourcePosition begin = scanner_.begin();
            Expression *type;
            Local<String> name(zone_);
            if (!fullTypeAndName(&type, name.ref(), DeclArg))
                return NULL;

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

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

                variadic = true;
                break;
            }

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

            Parameter *parameter = new (pool_) Parameter(name, type, ref, isConst, expr, begin);
            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;
    }

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

    return new (pool_) FunctionStatement(pos, name, token, 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;

    assert(false);
    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 0
    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;
#endif
    return true;
}

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

    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_IMPORT:
          {
            scanner_.scan();
            if (statements->length())
                cc_.reportError(scanner_.begin(), Message_ImportsMustBeFirst);
            ImportStatement *stmt = import();
            if (!stmt)
                return NULL;
            if (!imports_->append(stmt))
                return NULL;
            if (!matchSemicolon())
                return NULL;
            continue;
          }

          case TOK_FORWARD:
          case TOK_PUBLIC:
          case TOK_NATIVE:
          case TOK_STOCK:
          case TOK_LABEL:
          case TOK_TYPEDEF:
          {
            if (kind != TOK_LABEL)
                scanner_.scan();
            if (kind == TOK_PUBLIC && peek(TOK_CONST)) {
                TypeQualifiers quals = TypeQualifiers(Qual_Public | Qual_Const);
                if ((statement = var(quals)) == 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:
          {
            TypeQualifiers quals = (kind == TOK_NEW) ? Qual_Const : Qual_None;
            // 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(quals)) == 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(statements, unbound_, imports_);
}

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_, "()\n");
    }
    void visitNameProxy(NameProxy *name) {
        prefix();
        fprintf(fp_, "[ NameProxy (%s)\n", name->name()->chars());
    }
    void visitCallExpression(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 visitFunctionTypeStatement(FunctionTypeStatement *node) {
        prefix();
        fprintf(fp_, "[ FunctionTypeStatement (%s)\n", node->name()->chars());
        indent();
        dump(node->signature());
        unindent();
    }
    void visitFunctionStatement(FunctionStatement *node) {
        prefix();
        fprintf(fp_, "[ FunctionStatement (%s)\n", node->name()->chars());
        indent();
        dump(node->signature());
        if (node->body())
            node->body()->accept(this);
        unindent();
    }
    void visitExpressionStatement(ExpressionStatement *node) {
        prefix();
        fprintf(fp_, "[ ExpressionStatement\n");
        indent();
        node->expression()->accept(this);
        unindent();
    }
    void visitAssignment(Assignment *node) {
        prefix();
        fprintf(fp_, "[ Assignment\n");
        indent();
        node->lvalue()->accept(this);
        node->expression()->accept(this);
        unindent();
    }
    void visitTernaryExpression(TernaryExpression *node) {
        prefix();
        fprintf(fp_, "[ TernaryExpression\n");
        indent();
        node->condition()->accept(this);
        node->left()->accept(this);
        node->right()->accept(this);
        unindent();
    }
    void visitBinaryExpression(BinaryExpression *node) {
        prefix();
        fprintf(fp_, "[ BinaryExpression (%s)\n", TokenNames[node->token()]);
        indent();
        node->left()->accept(this);
        node->right()->accept(this);
        unindent();
    }
    void visitUnaryExpression(UnaryExpression *node) {
        prefix();
        fprintf(fp_, "[ UnaryExpression (%s)\n", TokenNames[node->token()]);
        indent();
        node->expression()->accept(this);
        unindent();
    }
    void visitReturnStatement(ReturnStatement *node) {
        prefix();
        fprintf(fp_, "[ ReturnStatement\n");
        indent();
        if (node->expression())
            node->expression()->accept(this);
        unindent();
    }
    void visitForStatement(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 visitBlockStatement(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 visitVariableDeclaration(VariableDeclaration *node) {
        prefix();
        fprintf(fp_, "[ VariableDeclaration (%s)\n", node->name()->chars());
        indent();
        if (node->initialization())
            node->initialization()->accept(this);
        unindent();
    }
    void visitIntegerLiteral(IntegerLiteral *node) {
        prefix();
        fprintf(fp_, "[ IntegerLiteral (%d)\n", node->value());
    }
    void visitBooleanLiteral(BooleanLiteral *node) {
        prefix();
        fprintf(fp_, "[ BooleanLiteral (%s)\n",
                (node->token() == TOK_TRUE) ? "true" : "false");
    }
    void visitFloatLiteral(FloatLiteral *node) {
        prefix();
        fprintf(fp_, "[ FloatLiteral (%f)\n", node->value());
    }
    void visitIfStatement(IfStatement *node) {
        prefix();
        fprintf(fp_, "[ IfStatement\n");
        indent();
        node->ifTrue()->accept(this);
        if (node->ifFalse())
            node->ifFalse()->accept(this);
        unindent();
    }
    void visitIndexExpression(IndexExpression *node) {
        prefix();
        fprintf(fp_, "[ IndexExpression\n");
        indent();
        node->left()->accept(this);
        node->right()->accept(this);
        unindent();
    }
    void visitEnumStatement(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->chars());
            if (node->entries()->at(i).expr) {
                indent();
                node->entries()->at(i).expr->accept(this);
                unindent();
            }
        }
        unindent();
    }
    void visitWhileStatement(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 visitBreakStatement(BreakStatement *node) {
        prefix();
        fprintf(fp_, "[ BreakStatement\n");
    }
    void visitContinueStatement(ContinueStatement *node) {
        prefix();
        fprintf(fp_, "[ ContinueStatement\n");
    }
    void visitStringLiteral(StringLiteral *node) {
        prefix();
        fprintf(fp_, "[ StringLiteral\n");
    }
    void visitIncDecExpression(IncDecExpression *node) {
        prefix();
        fprintf(fp_, "[ IncDecExpression (postfix=%d)\n", node->postfix());
        indent();
        node->expression()->accept(this);
        unindent();
    }
    void visitStructureStatement(StructureStatement *node) {
        prefix();
        fprintf(fp_, "[ StructureStatement %s\n", node->name()->chars());
    }
    void visitFieldExpression(FieldExpression *node) {
        prefix();
        fprintf(fp_, "[ FieldExpression %s\n", node->field()->chars());
        indent();
        node->left()->accept(this);
        unindent();
    }
    void visitSwitchStatement(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 visitArrayLiteral(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 visitImportStatement(ImportStatement *node) {
        prefix();
        fprintf(fp_, "[ ImportStatement\n");
    }
};

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

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