/* vim: set ts=4 sw=4 tw=99 et:
 *
 * Copyright (C) 2012 David Anderson
 *
 * This file is part of JITCraft.
 *
 * JITCraft is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 * 
 * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * JITCraft. If not, see http://www.gnu.org/licenses/.
 */
#include <string.h>
#include "BytecodeCompiler.h"
#include "Scopes.h"
#include "Modules.h"
#include "Types.h"
#include "Array.h"
#include "Strings.h"
#include "Zone.h"
#include "Environments.h"
#include "Box.h"
#include "Heap-inl.h"

using namespace ke;

typedef BytecodeEmitter::Label Label;

#define __ emitter_.

BytecodeCompiler::BytecodeCompiler(Zone *zone, ParseTree *tree, ModuleData *module)
  : zone_(zone),
    tree_(tree),
    emitter_(zone->pool()),
    locals_(NULL),
    scope_(NULL),
    moduleData_(module),
    loop_(NULL)
{
}

static inline TokenKind
ToCompare(Expression *expr)
{
    if (expr->isBinaryExpression()) {
        BinaryExpression *b = expr->toBinaryExpression();
        if (b->token() >= TOK_EQUALS && b->token() <= TOK_OR)
            return b->token();
    } else if (expr->isUnaryExpression()) {
        UnaryExpression *u = expr->toUnaryExpression();
        if (u->token() == TOK_NOT)
            return TOK_NOT;
    }
    return TOK_EOF;
}

static inline Opcode
CompareTokenToJump(TokenKind kind)
{
    switch (kind) {
      case TOK_EQUALS:
        return OP_JEQ;
      case TOK_NOTEQUALS:
        return OP_JNE;
      case TOK_GT:
        return OP_JG;
      case TOK_GE:
        return OP_JGE;
      case TOK_LT:
        return OP_JL;
      default:
        assert(kind == TOK_LE);
        return OP_JLE;
    }
}

static inline Opcode
TokenToOpcode(TokenKind kind)
{
    switch (kind) {
      case TOK_PLUS:
        return OP_ADD;
      case TOK_MINUS:
        return OP_SUB;
      case TOK_STAR:
        return OP_MUL;
      case TOK_SLASH:
        return OP_DIV;
      case TOK_PERCENT:
        return OP_MOD;
      case TOK_SHR:
        return OP_SHR;
      case TOK_USHR:
        return OP_USHR;
      case TOK_SHL:
        return OP_SHL;
      case TOK_BITAND:
        return OP_BITAND;
      case TOK_BITOR:
        return OP_BITOR;
      case TOK_GT:
          return OP_GT;
      case TOK_GE:
          return OP_GE;
      case TOK_LT:
          return OP_LT;
      case TOK_LE:
          return OP_LE;
      case TOK_EQUALS:
          return OP_EQ;
      case TOK_NOTEQUALS:
          return OP_NE;
      default:
        assert(kind == TOK_BITXOR);
        return OP_BITXOR;
    }
}

void
BytecodeCompiler::recordLifoSlot(Scope *scope)
{
    if (!scope)
        return;

    if (Variable *var = scope->lifoSlot()) {
        locals_->set(zone_, var->slot(), var->type());
        __ savelifo(var->slot());
    }
}

void
BytecodeCompiler::unwindTo(Scope *scope)
{
    // Note: we only need to unwind to the outermost scope's LIFO slot.
    Variable *var = NULL;
    for (Scope *current = scope_; current != scope; current = current->enclosing()) {
        if (Variable *slot = current->lifoSlot())
            var = slot;
    }

    if (var)
        __ unwindlifo(var->slot());
}

void
BytecodeCompiler::visit(NameProxy *name)
{
    switch (name->binding()->kind()) {
      case BoundName::VARIABLE:
      {
        Variable *var = name->binding()->toVariable();

        if (var->location() == Variable::STACK) {
            __ getlocal(var);
            assert(!name->type()->isReference());
        } else if (var->location() == Variable::ENVIRONMENT) {
            getEnvSlot(var);
        } else {
            assert(var->location() == Variable::PARAMETER);
            __ getarg(var);

            // If this argument is actually a reference, dereference it now.
            if (var->type()->isReference())
                __ getref(var->type()->contained());
        }
        break;
      }

      case BoundName::FUNCTION:
      {
        NamedFunction *fun = name->binding()->toNamedFunction();
        __ module();
        __ getmodule_fn(fun->slot());
        break;
      }

      default:
      {
        NamedConstant *constant = name->binding()->toNamedConstant();
        __ int_(constant->value().toInt());
        break;
      }
    }
}

void
BytecodeCompiler::visit(ExpressionStatement *node)
{
    // Expressions leave their value on the top of the stack, so we make sure
    // to balance the stack if they're used as a statement.
    node->expression()->accept(this);
    if (!node->expression()->type()->isVoid())
        __ pop();
}

static inline bool
IsCompositeValueType(Type *type)
{
    return type->isStruct() ||
           (type->isArray() && type->isFixedLength());
}

static inline Array *
StringLiteralToArray(Zone *zone, StringLiteral *node)
{
    Local<Type> type(zone, node->type());
    Local<ArrayMap> map(zone, ArrayMap::Attach(zone, type));
    if (!map)
        return NULL;

    return Array::NewString(zone,
                            map,
                            node->string()->raw(),
                            node->string()->length(),
                            Heap::Tenure_Old);
}

void
BytecodeCompiler::visit(Assignment *node)
{
    Local<Type> left(zone_, node->type());
    Local<Type> right(zone_, node->expression()->type());

    // The first step is three sub-steps:
    //
    //   (1) Bind the left-hand side.
    //   -- If a cumulative operation (+=, etc):
    //   (2) Save a copy of the binding on the stack.
    //   (3) Dereference the binding to get a value.
    //
    if (node->lvalue()->isNameProxy()) {
        NameProxy *proxy = node->lvalue()->toNameProxy();
        Variable *var = proxy->binding()->toVariable();

        // We need to fetch the variable under the following circumstances:
        //  (1) The variable is a reference, since we'll store into the ref.
        //  (2) The variable is a fixed array, since we need to copy into it.
        //  (3) The variable is a struct, since we need to copy into it.
        if (var->type()->isReference() || IsCompositeValueType(var->type()))
            __ get(var);

        // Get the value if needed.
        if (node->token() != TOK_ASSIGN) {
            // += etc is not allowed on arrays.
            assert(!var->type()->isArray());

            if (var->location() == Variable::ENVIRONMENT)
                getEnvSlot(var);

            if (var->type()->isReference()) {
                __ dup();
                __ getref(var->type()->contained());
            } else if (var->location() != Variable::ENVIRONMENT) {
                __ get(var);
            }
        }
    } else if (node->lvalue()->isFieldExpression()) {
        FieldExpression *expr = node->lvalue()->toFieldExpression();
        __ note_position(expr->pos());

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

        if (node->token() != TOK_ASSIGN)
            __ dup();

        if (node->token() != TOK_ASSIGN || IsCompositeValueType(left))
            __ getfield(expr->fieldIndex(), left);
    } else {
        IndexExpression *index = node->lvalue()->toIndexExpression();
        __ note_position(index->pos());

        index->left()->accept(this);
        index->right()->accept(this);

        if (node->token() != TOK_ASSIGN)
            __ dup2();

        if (node->token() != TOK_ASSIGN || IsCompositeValueType(left))
            __ getelem(left);
    }

    if (node->token() == TOK_ASSIGN) {
        // Special case: if the left-hand side is a string literal, we must
        // spawn a new copy (:TODO: something about const?)
        if (node->expression()->isStringLiteral() && !left->isFixedLength()) {
            Local<Array> string(zone_,
                    StringLiteralToArray(zone_, node->expression()->toStringLiteral()));
            if (!string)
                return;

            Local<ArrayMap> arrayMap(zone_, ArrayMap::cast(string->map()));
            __ note_position(node->expression()->pos());
            __ int_(string->length());
            __ newarray(OP_NEWSIZED, arrayMap, Heap::Tenure_Default);
            __ object(string);
            __ copyarray();
        } else {
            node->expression()->accept(this);
        }
    } else {
        visitForALU(left, node->expression());

        TokenKind alu = TokenKind(int(node->token()) - (TOK_ASSIGN_ADD - TOK_PLUS));
        __ note_position(node->pos());
        __ binary(TokenToOpcode(alu));
    }

    // Emit the store.
    if (left->isArray() && left->isFixedLength()) {
        // (x = y) returns the left-hand side; if |x| is a fixed-length array,
        // then |y| is as well, and we perform a deep copy.
        assert(right->isFixedLength());
        __ note_position(node->pos());
        __ copyarray();
    } else if (left->isStruct()) {
        // Structs have value semantics, so emit a full copy. We don't break
        // this down into u-ops, to avoid unnecessary bytecode explosion.
        assert(right->isStruct());
        __ note_position(node->pos());
        __ copystruct();
    } else if (node->lvalue()->isNameProxy()) {
        NameProxy *proxy = node->lvalue()->toNameProxy();
        Variable *var = proxy->binding()->toVariable();

        if (var->type()->isReference())
            __ setref(var->type()->contained());
        else if (var->location() == Variable::ENVIRONMENT)
            setEnvSlot(var);
        else
            __ set(var);
    } else if (node->lvalue()->isFieldExpression()) {
        FieldExpression *expr = node->lvalue()->toFieldExpression();
        __ setfield(expr->fieldIndex(), left);
    } else {
        __ setelem(left);
    }
}

void
BytecodeCompiler::visit(IncDecExpression *node)
{
    // In the postfix case, the logic looks like:
    //      (1) Bind       -> REF
    //      (2) Dup        -> REF REF
    //      (3) Fetch      -> REF VAL
    //      (4) Swap       -> VAL REF
    //      (5) Pick       -> VAL REF VAL
    //      (6) Add        -> VAL REF VAL+1
    //      (7) Store      -> VAL VAL+1
    //      (8) Drop       -> VAL
    //
    // In the prefix case, the logic looks like:
    //      (1) Bind       -> REF
    //      (2) Dup        -> REF REF
    //      (3) Fetch      -> REF VAL
    //      --
    //      --
    //      (6) Add        -> REF VAL+1
    //      (7) Store      -> VAL+1
    //      --
    //
    // This is squirrely enough such that we don't bother sharing too much
    // with the above.
    // 
    // Note: We simulate a "Pick" operation with a dup2+pop.

    // This is steps (1) to (5).
    Expression *expr = node->expression();
    if (expr->isNameProxy()) {
        NameProxy *proxy = expr->toNameProxy();
        Variable *var = proxy->binding()->toVariable();

        // Bind.
        if (var->location() == Variable::ENVIRONMENT)
            getEnvSlot(var);
        else if (var->type()->isReference() || var->type()->isArray())
            __ get(var);

        // Dup and fetch.
        if (var->type()->isReference()) {
            __ dup();
            __ getref(node->type());
            if (node->postfix()) {
                __ swap();
                __ pick2();
            }
        } else {
            assert(!var->type()->isArray());
            if (var->location() != Variable::ENVIRONMENT)
                __ get(var);
            if (node->postfix())
                __ dup();
        }
    } else if (expr->isFieldExpression()) {
        FieldExpression *field = expr->toFieldExpression();

        field->left()->accept(this);
        __ dup();
        __ getfield(field->fieldIndex(), field->type());

        if (node->postfix()) {
            // The stack looks like this now:
            // OBJECT VALUE
            __ swap();          // VALUE OBJECT
            __ pick2();         // VALUE OBJECT VALUE
        }
    } else {
        IndexExpression *index = expr->toIndexExpression();
        __ note_position(index->pos());

        index->left()->accept(this);
        index->right()->accept(this);

        assert(!node->type()->isArray());
        __ dup2();
        __ getelem(node->type());

        if (node->postfix()) {
            // The stack looks like this now:
            // ARRAY INDEX VALUE
            //
            // So we must use a PICK operation to rotate the stack into position.
            __ roll3();         // INDEX VALUE ARRAY
            __ roll3();         // VALUE ARRAY INDEX
            __ pick3();         // VALUE ARRAY INDEX VALUE
        }
    }

    // Perform step (6).
    if (node->type()->isFloat()) {
        __ float_(1.0);
    } else {
        assert(node->type()->isInt32());
        __ int_(1);
    }

    __ note_position(node->pos());
    if (node->token() == TOK_INCREMENT)
        __ binary(OP_ADD);
    else
        __ binary(OP_SUB);

    // Perform step (7).
    if (expr->isNameProxy()) {
        NameProxy *proxy = expr->toNameProxy();
        Variable *var = proxy->binding()->toVariable();

        if (var->type()->isReference())
            __ setref(node->type());
        else if (var->location() == Variable::ENVIRONMENT)
            setEnvSlot(var);
        else
            __ set(var);
    } else if (expr->isFieldExpression()) {
        FieldExpression *field = expr->toFieldExpression();
        __ setfield(field->fieldIndex(), field->type());
    } else {
        assert(expr->isIndexExpression());
        __ setelem(node->type());
    }

    // Perform step (8).
    if (node->postfix())
        __ pop();
}

void
BytecodeCompiler::visitForALU(Type *needed, Expression *node)
{
    node->accept(this);
    if (needed->isFloat() && !node->type()->isFloat())
        __ cvt_i2f();
    else
        assert(needed->primitive() == node->type()->primitive());
}

static inline Type *
GetCoercionType(TokenKind tok, Type *left, Type *right)
{
    if (left->isFloat())
        return left;
    return right;
}

void
BytecodeCompiler::visit(UnaryExpression *node)
{
    Local<Type> out(zone_, ((Expression *)node)->type());

    switch (node->token()) {
      case TOK_MINUS:
      {
        Local<Type> type(zone_, node->expression()->type());
        node->expression()->accept(this);
        
        if (out->isFloat())
            __ neg_f();
        else
            __ neg();
        break;
      }

      case TOK_NOT:
      {
        Local<Type> type(zone_, node->expression()->type());
        node->expression()->accept(this);
        
        if (out->isFloat())
            __ not_f();
        else
            __ not_();
        break;
      }

      case TOK_LABEL:
      {
        Local<Type> from(zone_, node->expression()->type());

        node->expression()->accept(this);
        if (!from->isFloat() && out->isFloat())
            __ bits_f2i();
        else if (from->isFloat() && !out->isFloat())
            __ bits_i2f();
        break;
      }

      default:
        assert(node->token() == TOK_TILDE);
        node->expression()->accept(this);
        __ bitnot();
        break;
    }
}

void
BytecodeCompiler::visit(BinaryExpression *node)
{
    if (node->token() == TOK_AND || node->token() == TOK_OR) {
        Label success, failure, done;
        visitForTest(node, &success, &failure, &success);
        __ bind(&success);
        __ int_(1);
        __ drop(1);         // Otherwise, the stack depth will be +1 too much.
        __ jump(&done);
        __ bind(&failure);
        __ int_(0);
        __ bind(&done);
        return;
    }

    Local<Type> leftType(zone_, node->left()->type());
    Local<Type> rightType(zone_, node->right()->type());
    Local<Type> coerce(zone_, GetCoercionType(node->token(), leftType, rightType));

    visitForALU(coerce, node->left());
    visitForALU(coerce, node->right());

    Opcode op = TokenToOpcode(node->token());
    if (node->type()->isFloat())
        op = (Opcode)(int(op) + (OP_ADD_F - OP_ADD));

    __ note_position(node->pos());
    __ binary(op);
}

void
BytecodeCompiler::visit(IndexExpression *node)
{
    node->left()->accept(this);
    node->right()->accept(this);
    __ note_position(node->pos());
    __ getelem(node->type());
}

void
BytecodeCompiler::visit(FieldExpression *node)
{
    node->left()->accept(this);
    __ getfield(node->fieldIndex(), node->type());
}

void
BytecodeCompiler::visit(ReturnStatement *node)
{
    if (node->expression()) {
        node->expression()->accept(this);
        __ return_();
    } else {
        __ returnvoid();
    }
}

void
BytecodeCompiler::visitForTest(Expression *expression,
                               Label *trueBranch,
                               Label *falseBranch,
                               Label *fallthrough)
{
    TokenKind token = ToCompare(expression);
    if (token == TOK_EOF || token == TOK_NOT) {
        if (token == TOK_EOF)
            expression->accept(this);
        else
            expression->toUnaryExpression()->expression()->accept(this);
        
        bool jumpOnTrue = (fallthrough == falseBranch) ^ (token == TOK_NOT);

        Opcode op = jumpOnTrue ? OP_JT : OP_JF;
        if (expression->type()->isFloat())
            op = (Opcode)(int(op) + (OP_JL_F - OP_JL));

        if (fallthrough == falseBranch)
            __ j(op, trueBranch);
        else
            __ j(op, falseBranch); 
        return;
    }

    BinaryExpression *binary = expression->toBinaryExpression();

    if (token == TOK_AND || token == TOK_OR) {
        Label next;
        if (token == TOK_AND)
            visitForTest(binary->left(), &next, falseBranch, &next);
        else
            visitForTest(binary->left(), trueBranch, &next, &next);
        __ bind(&next);
        visitForTest(binary->right(), trueBranch, falseBranch, fallthrough);
        return;
    }

    Opcode op = CompareTokenToJump(token);
    if (fallthrough == trueBranch)
        op = Invert(op);

    Local<Type> leftType(zone_, binary->left()->type());
    Local<Type> rightType(zone_, binary->right()->type());
    Local<Type> coerce(zone_, GetCoercionType(binary->token(), leftType, rightType));

    visitForALU(coerce, binary->left());
    visitForALU(coerce, binary->right());
    if (coerce->isFloat())
        op = (Opcode)(int(op) + (OP_JL_F - OP_JL));

    if (fallthrough == trueBranch)
        __ j(op, falseBranch);
    else
        __ j(op, trueBranch);
}

void
BytecodeCompiler::visit(ForStatement *node)
{
    AutoEnterScope forScope(this, node->scope());

    recordLifoSlot(node->scope());

    Label join, update;
    LoopScope loop(scope_, &join, &update, &loop_);

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

    Label header, test;
    if (node->condition())
        __ jump(&test);

    __ bind(&header);
    node->body()->accept(this);

    __ bind(&update);
    if (node->update())
        node->update()->accept(this);

    if (node->condition()) {
        __ bind(&test);
        visitForTest(node->condition(), &header, &join, &join);
    } else {
        __ jump(&header);
    }

    __ bind(&join);

    if (node->scope())
        unwindTo(node->scope()->enclosing());
    assert(__ stackDepth() == 0);
}

void
BytecodeCompiler::visit(WhileStatement *node)
{
    Label header, join;

    __ bind(&header);

    LoopScope loop(scope_, &join, &header, &loop_);

    if (node->token() == TOK_WHILE) {
        Label body;

        visitForTest(node->condition(), &body, &join, &body);
        __ bind(&body);
        node->body()->accept(this);
        __ jump(&header);
    } else {
        node->body()->accept(this);
        visitForTest(node->condition(), &header, &join, &join);
    }

    __ bind(&join);
}

void
BytecodeCompiler::visit(BreakStatement *node)
{
    unwindTo(loop_->scope());
    __ jump(loop_->break_());
}

void
BytecodeCompiler::visit(ContinueStatement *node)
{
    unwindTo(loop_->scope());
    __ jump(loop_->continue_());
}

void
BytecodeCompiler::visit(BlockStatement *node)
{
    AutoEnterScope blockScope(this, node->scope());

    recordLifoSlot(node->scope());

    for (size_t i = 0; i < node->statements()->length(); i++) {
        Statement *statement = node->statements()->at(i);
        statement->accept(this);
        assert(__ stackDepth() == 0);
    }

    // We don't bother emitting an "unwind" instruction for function scopes,
    // since this is taken care of by the calling convention.
    if (node->scope() && node->scope()->enclosing()->kind() != Scope::FUNCTION)
        unwindTo(node->scope()->enclosing());
}

void
BytecodeCompiler::visit(IntegerLiteral *node)
{
    __ int_(node->value());
}

void
BytecodeCompiler::visit(BooleanLiteral *node)
{
    if (node->token() == TOK_TRUE)
        __ true_();
    else
        __ false_();
}

void
BytecodeCompiler::visit(FloatLiteral *node)
{
    __ float_((float)node->value());
}

void
BytecodeCompiler::visit(StringLiteral *node)
{
    Local<Array> array(zone_, StringLiteralToArray(zone_, node));
    if (!array)
        return;

    __ note_position(node->pos());
    __ object(array);
}

void
BytecodeCompiler::getEnvSlot(Variable *var)
{
    assert(var->scope()->kind() == Scope::GLOBAL);
    __ getglobal(var);
}

void
BytecodeCompiler::setEnvSlot(Variable *var)
{
    assert(var->scope()->kind() == Scope::GLOBAL);
    __ setglobal(var);
}

static bool
FillArrayLiteral_String(Zone *zone, Handle<Array> array, ArrayLiteral *literal, unsigned *maxsize)
{
    Local<Array> string(zone);
    for (size_t i = 0; i < literal->expressions()->length(); i++) {
        Expression *expr = literal->expressions()->at(i);
        StringLiteral *lit = expr->toStringLiteral();
        if ((string = StringLiteralToArray(zone, lit)) == NULL)
            return false;

        array->writeObject(zone, i, string);

        if (string->length() > *maxsize)
            *maxsize = string->length();

        assert(!array->type()->contained()->isFixedLength() ||
                array->type()->contained()->fixedLength() >= string->length());
    }

    return true;
}

static bool
FillArrayLiteral_Primitive(Zone *zone, Handle<Array> array, ArrayLiteral *literal)
{
    assert(array->type()->fixedLength() == literal->expressions()->length());

    for (size_t i = 0; i < literal->expressions()->length(); i++) {
        Expression *expr = literal->expressions()->at(i);
        if (IntegerLiteral *lit = expr->asIntegerLiteral()) {
            array->writeInt32(i, lit->value());
            continue;
        }
        if (BooleanLiteral *lit = expr->asBooleanLiteral()) {
            if (lit->token() == TOK_TRUE)
                array->writeInt32(i, 1);
            else
                array->writeInt32(i, 0);
            continue;
        }
        if (FloatLiteral *lit = expr->asFloatLiteral()) {
            array->writeFloat(i, lit->value());
            continue;
        }

        // Unrecognized literal type.
        assert(false);
    }

    return true;
}

static bool
TraverseArrayLiteral(Zone *zone, ArrayLiteral *literal, Handle<Array> array, Handle<Type> type,
                     unsigned *maxsize)
{
    assert(type->fixedLength() == literal->expressions()->length());

    Local<Type> contained(zone, type->contained());
    if (contained->isCharArray())
        return FillArrayLiteral_String(zone, array, literal, maxsize);

    if (!contained->isArray())
        return FillArrayLiteral_Primitive(zone, array, literal);

    Local<Array> subarray(zone);
    for (size_t i = 0; i < literal->expressions()->length(); i++) {
        Expression *expr = literal->expressions()->at(i);
        subarray = Array::cast(array->readObject(i));
        if (!TraverseArrayLiteral(zone, expr->toArrayLiteral(), subarray, contained, maxsize))
            return false;
    }

    return true;
}

static Array *
BuildArrayLiteral(Zone *zone, ArrayLiteral *literal, Handle<ArrayMap> map, unsigned *maxsize)
{
    Local<Array> root(zone, Array::NewFixed(zone, map, Heap::Tenure_Old));
    if (!root)
        return NULL;

    // This should have allocated everything in the array, so all we need to
    // do is traverse down to the lowest levels and copy things.
    Local<Type> type(zone, map->type());
    if (!TraverseArrayLiteral(zone, literal, root, type, maxsize))
        return NULL;

    return root;
}

static inline bool
ArrayContainsCharBuffers(Type *type)
{
    if (type->contained()->isArray())
        return ArrayContainsCharBuffers(type->contained());
    return type->isCharArray();
}

void
BytecodeCompiler::visit(VariableDeclaration *node)
{
    Variable *var = node->variable();
    
    Local<Type> type(zone_, var->type());
    if (type->isArray()) {
        Local<ArrayMap> map(zone_, ArrayMap::Attach(zone_, type));
        __ note_position(node->pos());

        Local<Type> right(zone_);
        if (node->initialization())
            right = node->initialization()->type();

        // There are a few methods for allocating, here:
        // (1) If the array is fixed,
        //    (a) Initializer not present,
        //              NEWFIXED
        //    (b) Left is const non-string:
        //              <nothing>
        //    (b) Otherwise:
        //              NEWFIXED
        //              COPYARRAY
        // (2) If the array is not fixed,
        //    (a) Initializer is not present,
        //              NEWEMPTY
        //    (b) Initializer is not a string literal,
        //        or left is const:
        //              <nothing>
        //    (c) Initializer is a string literal,
        //              NEWSIZED
        //              COPYARRAY
        //

        Heap::Tenure tenure = var->scope()->kind() == Scope::GLOBAL
                              ? Heap::Tenure_Old
                              : Heap::Tenure_Default;

        if (Expression *init = node->initialization()) {
            if (init->isArrayLiteral()) {
                unsigned maxsize = 0;
                Local<Array> array(zone_, BuildArrayLiteral(zone_, init->toArrayLiteral(), map, &maxsize));
                if (!array)
                    return;

                assert(type->isFixedLength());

                if (type->isConst()) {
                    __ object(array);
                } else if (ArrayContainsCharBuffers(type)) {
                    // This array contains mutable char buffers, so
                    // unfortunately this gets a little more complicated. We
                    // compute the maximum size needed for the innermost
                    // string, which is similar to SP1. This means we can use
                    // CopyArray rather than individually emit opcodes to clone
                    // every string.
                    Local<Type> child(zone_, type);
                    for (size_t i = 0; i < type->levels() - 1; i++) {
                        __ int_(child->fixedLength());
                        child = child->contained();
                    }
                    __ int_(maxsize);
                    __ newarray(OP_NEWSIZED, map, tenure);
                    __ object(array);
                    __ copyarray();
                } else {
                    __ newarray(OP_NEWFIXED, map, tenure);
                    __ object(array);
                    __ copyarray();
                }
            } else if (type->isFixedLength()) {
                // Note in the case of:
                // const String:buffer[50] = "hello";
                //
                // We want to preserve sizeof(buffer) == 50.
                if (type->isConst() && !type->isCharArray()) {
                    init->accept(this);
                } else {
                    __ newarray(OP_NEWFIXED, map, tenure);
                    init->accept(this);
                    __ copyarray();
                }
            } else if (!type->isConst() && init->isStringLiteral()) {
                // This is a degenerate case of ArrayLiteral.
                __ int_(right->fixedLength());
                __ newarray(OP_NEWSIZED, map, tenure);
                init->accept(this);
                __ copyarray();
            } else if (type->isConst()) {
                init->accept(this);
            }
        } else if (type->isFixedLength()) {
            __ newarray(OP_NEWFIXED, map, tenure);
        } else {
            if (node->postDimensions()) {
                for (size_t i = 0; i < node->postDimensions()->length(); i++) {
                    Expression *expr = node->postDimensions()->at(i);
                    if (expr)
                        expr->accept(this);
                    else
                        __ int_(0);
                }
                __ newarray(OP_NEWSIZED, map, tenure);
            } else {
                __ newarray(OP_NEWEMPTY, map, tenure);
            }
        }
    } else if (type->isStruct()) {
        Local<StructMap> map(zone_, StructMap::cast(type->newMap()));

        // Because structs can contain arrays, any sort of composition
        // triggers non-LIFO allocation. This is just for correctness.
        // We could do better by:
        //  (1) Limiting to structs that just (recursively) contain arrays,
        //  (2) Swap Stack for Default tenure in Struct::New
        //  (3) JIT analysis
        if (var->scope()->kind() == Scope::GLOBAL)
            __ newstruct(map, Heap::Tenure_Old);
        else if (var->needsHeapAllocation() || map->composed())
            __ newstruct(map, Heap::Tenure_Default);
        else
            __ newstruct(map, Heap::Tenure_Stack);
    } else {
        if (node->initialization()) {
            node->initialization()->accept(this);
        } else {
            if (type->isInt32OrEnum() || type->isBool()) {
                __ int_(0);
            } else {
                assert(type->isFloat());
                __ float_(0);
            }
        }
    }

    if (var->location() == Variable::STACK) {
        __ setlocal(var);
        locals_->set(zone_, var->slot(), var->type());
    } else {
        assert(var->location() == Variable::ENVIRONMENT);
        setEnvSlot(var);
    }

    __ pop();
}

void
BytecodeCompiler::visit(CallExpression *node)
{
    Local<Type> funType(zone_, node->callee()->type());

    // Sniff out natives, which have a specific opcode and are guaranteed to
    // be called via name proxy.
    NamedFunction *native = NULL;
    if (funType->isNative())
        native = node->callee()->toNameProxy()->binding()->toNamedFunction();

    Local<Type> given(zone_);
    for (size_t i = node->arguments()->length() - 1; i < node->arguments()->length(); i--) {
        Expression *arg = node->arguments()->at(i);

        given = arg->type();

        // We need to compute a reference if the parameter was in the form:
        //  f(&a)
        // Note this form does not allow: f({})
        // 
        // We also need to compute references for all variadic native
        // arguments, but arrays and references are already in the
        // appropriate form.
        bool mustPushReference = false;
        if (i >= funType->parameters()->length()) {
            assert(funType->isNative() && funType->isNativeVariadic());
            mustPushReference = !given->isArray() && !given->isReference();
        } else if (funType->parameterAt(i)->isReference()) {
            mustPushReference = !given->isReference();
        }

        // If a native is passed to a native, it must only be one level deep.
        assert(!funType->isNative() || !given->isArray() || given->levels() == 1);

        if (mustPushReference) {
            if (arg->isNameProxy()) {
                // :TODO: test with functions and globals
                // Compute a reference to the name.
                Variable *var = arg->toNameProxy()->binding()->toVariable();
                __ note_position(node->pos());
                __ newref(var);
            } else if (arg->isFieldExpression()) {
                FieldExpression *expr = arg->toFieldExpression();
                expr->left()->accept(this);
                __ note_position(expr->pos());
                __ fieldref_lifo(expr->fieldIndex());
            } else {
                // We don't know how to, or can't, build a direct reference to
                // this type. Make an indirect one, by taking the top of the
                // stack and boxing it up.
                arg->accept(this);
                __ note_position(node->pos());
                __ slotref_lifo();
            }
        } else {
            arg->accept(this);
        }
    }

    unsigned argc = node->arguments()->length();

    // If there are missing arguments, then we're not done and have to push
    // default parameters.
    Local<Box> box(zone_);
    Local<Array> array(zone_);
    Local<ArrayMap> map(zone_);
    for (size_t i = node->arguments()->length(); i < funType->parameters()->length(); i++) {
        box = Box::cast(funType->defaults()->at(i));

        if (box->type()->isPod()) {
            if (box->type()->pod() == PrimitiveType_Int32)
                __ int_(box->toInt32());
            else if (box->type()->pod() == PrimitiveType_Float)
                __ float_(box->toFloat());
            else
                assert(false);

            if (funType->parameterAt(i)->isReference()) {
                __ note_position(node->pos());
                __ slotref_lifo();
            }
        } else {
            assert(box->type()->isArray());

            array = Array::cast(box->toObject());
            if (funType->parameterAt(i)->isConst()) {
                __ object(array);
            } else {
                // We need to copy the array since it's mutable. Note that
                // although COPYARRAY returns its left-hand side, this may
                // change in the future, we do the same thing and dupe the
                // newly allocated array.
                map = ArrayMap::cast(array->map());
                
                // Natives cannot escape array references, so we can allocate
                // them on the LIFO stack.
                if (funType->isNative())
                    __ newarray(OP_NEWFIXED, map, Heap::Tenure_Stack);
                else
                    __ newarray(OP_NEWFIXED, map, Heap::Tenure_Default);
                __ dup();
                __ object(array);
                __ copyarray();
                __ pop();
            }
        }

        argc++;
    }

    __ note_position(node->pos());
    if (native) {
        __ callnative(native->slot(), argc);
        __ drop(argc);
    } else {
        node->callee()->accept(this);
        __ call(funType);
        __ drop(argc + 1);
    }
}

void
BytecodeCompiler::visit(TernaryExpression *node)
{
    Label success, failure, join;

    visitForTest(node->condition(), &success, &failure, &success);
    __ bind(&success);
    node->left()->accept(this);
    __ drop(1);
    __ jump(&join);
    __ bind(&failure);
    node->right()->accept(this);
    __ bind(&join);
}

void
BytecodeCompiler::visit(IfStatement *node)
{
    Label join;
    if (!node->ifFalse()) {
        Label success;

        visitForTest(node->condition(), &success, &join, &success);
        __ bind(&success);
        node->ifTrue()->accept(this);
    } else {
        Label success, next;

        visitForTest(node->condition(), &success, &next, &success);
        __ bind(&success);
        node->ifTrue()->accept(this);
        __ jump(&join);
        __ bind(&next);
        node->ifFalse()->accept(this);
    }

    __ bind(&join);
}

bool
BytecodeCompiler::tableswitch(SwitchStatement *node)
{
    CaseValueList *values = node->caseValueList();

    if (values->length() < 3)
        return false;

    // Find the delta between the largest and smallest value.
    int hi = values->at(values->length() - 1).box.toInt();
    int lo = values->at(0).box.toInt();
    assert(hi > lo);

    unsigned tablesize = TableSwitchEntries(lo, hi);
    if (tablesize > MAX_TABLESWITCH_ENTRIES)
        return false;

    Label def, join;

    // Create the list of labels that each statement will bind to.
    Label *labels = new Label[node->cases()->length()];

    // Create the table of labels we'll use for each case.
    Label **table = new Label *[tablesize];

    // Link all cases, by default, to the default label.
    for (size_t i = 0; i < tablesize; i++)
        table[i] = &def;

    // Now patch actual cases to their correct labels.
    for (size_t i = 0; i < values->length(); i++) {
        CaseValue &v = values->at(i);
        assert(v.statement < node->cases()->length());

        unsigned index = unsigned(v.box.toInt() - lo);
        assert(index < tablesize);

        table[index] = &labels[v.statement];
    }

    // Emit the tableswitch opcode and the jump table.
    __ tableswitch(lo, hi, &def, table);

    // We're done with the jump table now.
    delete [] table;

    // Emit each statement.
    for (size_t i = 0; i < node->cases()->length(); i++) {
        Statement *stmt = node->cases()->at(i)->statement();

        __ bind(&labels[i]);
        stmt->accept(this);
        __ jump(&join);
    }

    // We're done with the statement labels.
    delete [] labels;

    // Emit the default case.
    __ bind(&def);
    if (node->defaultCase())
        node->defaultCase()->accept(this);

    __ bind(&join);

    return true;
}

void
BytecodeCompiler::visit(SwitchStatement *node)
{
    node->expression()->accept(this);

    if (tableswitch(node))
        return;

    Label join;

    for (size_t i = 0; i < node->cases()->length(); i++) {
        Case *c = node->cases()->at(i);

        Label success, fail;
        if (c->others()) {
            for (size_t j = 0; j < c->others()->length(); j++) {
                Expression *expr = c->others()->at(j);

                __ dup();
                expr->accept(this);
                __ j(OP_JEQ, &success);
            }
        }

        // The final test.
        __ dup();
        c->expression()->accept(this);
        __ j(OP_JNE, &fail);
        __ bind(&success);
        c->statement()->accept(this);
        __ jump(&join);
        __ bind(&fail);
    }

    if (node->defaultCase())
        node->defaultCase()->accept(this);

    __ pop();
    __ bind(&join);
}

void
BytecodeCompiler::visit(FunctionStatement *node)
{
    if (!node->fun()->used())
        return;

    if (node->fun()->isNative()) {
        assert(!moduleData_->natives->at(node->fun()->slot()));

        Local<Type> type(zone_, node->fun()->type());
        Local<String> name(zone_, node->fun()->name());
        Local<Native> native(zone_, Native::New(zone_, type, name));
        if (!native)
            return;

        moduleData_->natives->set(zone_, node->fun()->slot(), native);
        return;
    }

    // If the function has no body, then it's just a declaration.
    if (!node->body()) {
        assert(node->fun()->isForward() || node->fun()->isPublic());
        return;
    }

    BytecodeCompiler child(zone_, tree_, moduleData_);
    Local<Function> fun(zone_, child.compileFunction(moduleData_, node));
    if (!fun)
        return;
    
    assert(!moduleData_->module->getFunction(node->fun()->slot()));
    moduleData_->module->setFunction(zone_, node->fun()->slot(), fun);
}

void
BytecodeCompiler::visit(FunctionTypeStatement *node)
{
}

void
BytecodeCompiler::visit(EnumStatement *node)
{
}

void
BytecodeCompiler::visit(StructureStatement *node)
{
}

void
BytecodeCompiler::visit(ArrayLiteral *node)
{
    // We shouldn't reach these; they're handled manually when initializing
    // declared arrays.
    assert(false);
}

Code *
BytecodeCompiler::compileCode(Scope *scope, unsigned lineno)
{
    // STOP doubles as RETURNVOID.
    __ stop();

    if (__ oom() || zone_->hasPendingException())
        return NULL;

    Local<ByteArray> bytes(zone_, ByteArray::New(zone_, __ length() * sizeof(bytecode), Heap::Tenure_Old));
    if (!bytes)
        return NULL;
    memcpy(bytes->raw(), __ buffer(), __ length());

    for (size_t i = 0; i < scope->maxContainedLocals(); i++)
        assert(locals_->at(i));

    Local<FixedArray> objects(zone_, FixedArray::New(zone_, __ objects()->length(), Heap::Tenure_Old));
    if (!objects)
        return NULL;

    for (size_t i = 0; i < __ objects()->length(); i++)
        objects->set(zone_, i, *(__ objects()->at(i)));

    Local<ByteArray> safepoints(zone_);

    // If any stack slots hold gc pointers at potential failure points in the
    // bytecode, record them now. We do this by building a list of tuples;
    // each tuple contains the pc offset, and a bitset containing which stack
    // slots must be scanned by the gc.
    if (__ oopRecords()->length()) {
        size_t bytesPerSafepoint = Code::BytesPerSafepoint(__ maxStackDepth());
        size_t gcmapSize = bytesPerSafepoint * __ oopRecords()->length();
        safepoints = ByteArray::New(zone_, gcmapSize, Heap::Tenure_Old);
        if (!safepoints)
            return NULL;

        Address cursor = safepoints->raw();
        for (size_t i = 0; i < __ oopRecords()->length(); i++) {
            OopRecord *record = __ oopRecords()->at(i);
            assert(record->depth <= __ maxStackDepth());

            *reinterpret_cast<unsigned *>(cursor) = record->offset;

            unsigned char *bits = reinterpret_cast<unsigned char *>(cursor + sizeof(unsigned));
            for (unsigned i = 0; i < record->depth; i++)
                bits[i / 8] |= (1 << (i % 8));

            cursor += bytesPerSafepoint;
        }

        assert(cursor == safepoints->raw() + gcmapSize);
    }

    Local<ByteArray> sourcemap(zone_);
    if (__ sourcemapLength()) {
        sourcemap = ByteArray::New(zone_, __ sourcemapLength(), Heap::Tenure_Old);
        if (!sourcemap)
            return NULL;

        memcpy(sourcemap->raw(), __ sourcemap(), __ sourcemapLength());
    }

    Local<Code> code(zone_);

    code = Code::New(zone_,
                     bytes,
                     locals_,
                     objects,
                     __ maxStackDepth(),
                     moduleData_->module,
                     safepoints,
                     sourcemap,
                     lineno);
    return code;
}

Function *
BytecodeCompiler::compileFunction(ModuleData *module, FunctionStatement *node)
{
    // Note: No need to record a life slot here, since it's part of the Frame.
    AutoEnterScope functionScope(this, node->scope());

    // Set the initial line, because line mappings are deltas.
    __ setFirstLine(node->pos().line);
    locals_ = FixedArray::New(zone_, node->scope()->maxContainedLocals(), Heap::Tenure_Old);

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

    unsigned nargs = node->scope()->numArguments();
    Local<FixedArray> args(zone_, FixedArray::New(zone_, nargs, Heap::Tenure_Old));
    if (!args)
        return NULL;

    for (size_t i = 0; i < node->scope()->numArguments(); i++)
        args->set(zone_, i, node->scope()->getArgument(i)->type());


    Local<Code> code(zone_, compileCode(node->scope(), node->pos().line));
    if (!code)
        return NULL;

    Local<Type> type(zone_, node->fun()->type());
    Local<String> name(zone_, node->fun()->name());
    Local<Function> fun(zone_, Function::New(zone_, code, type, name, node->pos()));
    if (!fun)
        return NULL;

    // If this function had a forward, export it as a named public.
    if (node->fun()->isPublic()) {
        assert(node->fun()->isPublic());
        ScopedRoot<Function> root(fun);
        if (!root)
            return NULL;
        if (!moduleData_->publics.append(root))
            return NULL;
    }

#ifndef NDEBUG
    Disassemble(code, stdout);
#endif
    
    return fun;
}

Module *
BytecodeCompiler::compile()
{
    AutoEnterScope scope(this, tree_->scope());

    ModuleData moduleData;

    moduleData_ = &moduleData;
    moduleData_->module = Module::New(zone_, tree_->scope()->numFunctions());

    if (!moduleData_)
        return NULL;
    
    moduleData_->natives = FixedArray::New(zone_, tree_->scope()->numNatives(), Heap::Tenure_Old);
    if (!moduleData_->natives)
        return NULL;

    for (size_t i = 0; i < tree_->statements()->length(); i++) {
        Statement *statement = tree_->statements()->at(i);
        statement->accept(this);
    }

    if (zone_->hasPendingException())
        return NULL;

#ifndef NDEBUG
    for (size_t i = 0; i < tree_->scope()->numFunctions(); i++)
        assert(moduleData_->module->getFunction(i));
    for (size_t i = 0; i < tree_->scope()->numNatives(); i++)
        assert(moduleData_->natives->at(i));
#endif

    if (moduleData_->publics.length()) {
        Local<Function> fun(zone_);
        Local<FixedArray> list(zone_, FixedArray::New(zone_, moduleData_->publics.length(),
                               Heap::Tenure_Old));
        if (!list)
            return NULL;

        for (size_t i = 0; i < moduleData_->publics.length(); i++)
            list->set(zone_, i, moduleData_->publics[i]);

        moduleData_->module->setPublics(list);
    }

    moduleData_->module->setNatives(moduleData_->natives);

    if (scope_->numEnvironmentVars()) {
        Local<EnvironmentMap> globalMap(zone_, scope_->createEnvironmentMap(zone_));
        if (!globalMap)
            return NULL;

        Local<Environment> environment(zone_, Environment::New(zone_, globalMap));
        if (!environment)
            return NULL;

        moduleData_->module->setEnvironment(environment);
    }

    Local<Code> code(zone_, compileCode(tree_->scope(), 1));
    if (!code)
        return NULL;

    Disassemble(code, stdout);

    moduleData_->module->setCode(code);

    return moduleData_->module;
}