/* 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 "../Strings.h"
#include "../Zone.h"
#include "../TypeManager.h"
#include "NameBinding.h"
#include "Scopes.h"
#include "ConstantEvaluator.h"
#include "../Spaces-inl.h"
#include "../Heap-inl.h"

using namespace ke;

// Create symbol tables and symbols for every scope and declaration. For type
// declarations and methods, we also pre-allocate a Type object, so that
// circular dependencies between types will work.
class NamePopulator : public AstVisitor
{
  private:
    // This class is analagous to a Scope, however, it allows us to create
    // scopes lazily. If a scope is requested, and the current environment
    // has no scope, then a scope is created. If no scope is ever requested,
    // a scope does not need to be created.
    class SymbolEnv
    {
      public:
        SymbolEnv(SymbolEnv **prevp, Scope *scope = NULL)
          : envp_(prevp),
            prev_(*prevp),
            scope_(scope)
        {
            *envp_ = this;
        }
        ~SymbolEnv() {
            *envp_ = prev_;
        }

        Scope *scope() {
            return scope_;
        }
        void setScope(Scope *scope) {
            assert(!scope_);
            scope_ = scope;
        }
        SymbolEnv *prev() const {
            return prev_;
        }

      private:
        SymbolEnv **envp_;
        SymbolEnv *prev_;
        Scope *scope_;
    };

    enum ReturnStatus {
        NoReturn,
        VoidReturn,
        ValueReturn
    };

    class FunctionScope
    {
      public:
        FunctionScope(FunctionScope **prevp)
          : prevp_(prevp),
            prev_(*prevp),
            status_(NoReturn)
        {
            *prevp_ = this;
        }
        ~FunctionScope() {
            *prevp_ = prev_;
        }
        ReturnStatus returns() const {
            return status_;
        }
        void returns(ReturnStatus status) {
            if (status > status_)
                status_ = status;
        }
      private:
        FunctionScope **prevp_;
        FunctionScope *prev_;
        ReturnStatus status_;
    };

  public:
    NamePopulator(Zone *zone, CompileContext &cc, TranslationUnit *unit)
      : zone_(zone),
        pool_(zone->pool()),
        cc_(cc),
        unit_(unit),
        env_(NULL),
        fun_(NULL)
    {
    }

    void analyze() {
        ImportScope *importScope = ImportScope::New(pool_);
        if (!importScope)
            return;

        // At the import level, we declare system types.
        if (!declareSystemTypes(importScope))
            return;

        GlobalScope *globalScope = GlobalScope::New(pool_, importScope);
        if (!globalScope)
            return;

        unit_->setImportScope(importScope);
        unit_->setGlobalScope(globalScope);

        SymbolEnv env(&env_, globalScope);

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

        return;
    }

    bool declareSystemType(ImportScope *scope, const char *name, Handle<Type> effective) {
        Local<String> tag(zone_, zone_->makeSymbol(name));
        if (!tag)
            return false;

        Local<Type> type(zone_, zone_->types()->getType());

        TypeSymbol *sym = new (pool_) TypeSymbol(scope, tag, type, effective);
        return scope->addSymbol(sym);
    }

    bool declareSystemType(ImportScope *scope, const char *name, PrimitiveType prim) {
        Local<Type> primitive(zone_, zone_->types()->getPrimitive(prim));
        assert(primitive);
        return declareSystemType(scope, name, primitive);
    }

    bool declareSystemTypes(ImportScope *scope) {
        if (!declareSystemType(scope, "float", PrimitiveType_Float))
            return false;
        if (!declareSystemType(scope, "_", PrimitiveType_Int32))
            return false;
        if (!declareSystemType(scope, "int", PrimitiveType_Int32))
            return false;
        if (!declareSystemType(scope, "bool", PrimitiveType_Bool))
            return false;
        if (!declareSystemType(scope, "char", PrimitiveType_Char))
            return false;

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

        return true;
    }

    void visitVariableDeclaration(VariableDeclaration *node) {
        Scope *scope = env_->scope();
        if (!scope || scope->kind() != Scope::GLOBAL) {
            if ((scope = getOrCreateBlockScope()) == NULL)
                return;
        }

        if (scope->kind() == Scope::GLOBAL) {
            // The symbol must be added now, since it could be an export.
            VariableSymbol *sym = new (pool_) VariableSymbol(scope, node->name(), node->pos());
            node->setSymbol(sym);

            if (!registerName(scope, sym))
                return;
        } else {
            // We ensure the scope will exist at the name binding phase, but
            // we don't actually register the variable symbol yet. Otherwise,
            // when binding the initializer, we could encounter:
            //    new x = x;
            //
            // And we don't necessarily want this to bind.
        }

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

    void visitEnumStatement(EnumStatement *node) {
        Local<String> name(zone_, node->name());
        Local<Type> type(zone_);
        if (name)
            type = zone_->types()->newEnum(name);
        else
            type = zone_->types()->getPrimitive(PrimitiveType_Int32);

        if (!type)
            return;

        Scope *scope = getGlobalOrCreateBlockScope();
        if (!scope)
            return;

        if (name) {
            Local<Type> symType(zone_, zone_->types()->getType());
            TypeSymbol *sym = new (pool_) TypeSymbol(scope, name, symType, type);
            if (!registerName(scope, sym))
                return;

            if (scope->kind() == Scope::GLOBAL) {
                if (!unit_->globalScope()->exported()->append(sym))
                    return;
            }
        }

        // We want each field of the expression to qualify as a constant expression.
        if ((type = zone_->types()->qualify(type, TypeQual_ConstExpr)) == NULL)
            return;
        
        int value = 0;
        for (size_t i = 0; i < node->entries()->length(); i++) {
            EnumStatement::Entry &entry = node->entries()->at(i);
            BoxedPrimitive box = BoxedPrimitive::Int(value);
            if (entry.expr) {
                if (!EvaluateForConstant(entry.expr, &box) || box.type() != PrimitiveType_Int32) {
                    cc_.reportError(entry.expr->pos(), Message_EnumFieldNotConstant);
                    return;
                }

                assert(box.type() == PrimitiveType_Int32);
                value = box.toInt();
            }
         
            ConstantSymbol *sym = new (pool_) ConstantSymbol(scope, entry.name, entry.pos, type, box);
            if (!registerName(scope, sym))
                return;
            if (scope->kind() == Scope::GLOBAL) {
                if (!unit_->globalScope()->exported()->append(sym))
                    return;
            }

            entry.sym = sym;
            value++;
        }
    }

    void visitFunctionStatement(FunctionStatement *node) {
        // We create function types ahead of time, not for any particular
        // reason. It makes things consistent with FunctionTypeStatement,
        // which actually does produce a type.
        Local<FunctionType> type(zone_, FunctionType::New(zone_, node->name(), node->token()));
        if (!type)
            return;

        assert(env_->scope());

        // Function statements are always named, so add the name to the outer scope.
        FunctionSymbol *sym = new (pool_) FunctionSymbol(env_->scope(), node->name(), node->pos(), type);
        if (!registerName(env_->scope(), sym))
            return;

        if (node->token() == TOK_PUBLIC ||
            node->token() == TOK_FORWARD ||
            node->token() == TOK_NATIVE)
        {
            // We're in the global scope, for sure.
            assert(env_->scope()->kind() == Scope::GLOBAL);

            if (!unit_->globalScope()->exported()->append(sym))
                return;
        }

        node->setSymbol(sym);

        // Scope for the function's arguments.
        SymbolEnv argEnv(&env_);
        if (!registerArguments(node->signature()))
            return;

        // Scope for function body.
        SymbolEnv localEnv(&env_);
        FunctionScope fun(&fun_);
        if (node->body())
            node->body()->accept(this);

        // Function statements have quirky semantics around their return
        // type. For reasonable compatibility with SP1, we use the following
        // heuristics for when no explicit type is declared.
        if (!node->signature().returnType()) {
            Local<Type> type(zone_);
            if (node->token() == TOK_FORWARD || node->token() == TOK_NATIVE) {
                // If the function type is a native or forward, we always
                // assume it returns an int32.
                type = zone_->types()->getPrimitive(PrimitiveType_Int32);
            } else if (fun.returns() != ValueReturn) {
                // This function never returns a value, so mark it as
                // returning void.
                type = zone_->types()->getVoid();
            }
            // No need to NULL check here, we'll catch OOM later.
            node->sym()->type()->setReturnType(type);
        }

        node->setScopes(argEnv.scope(), localEnv.scope());
    }

    void visitStructureStatement(StructureStatement *node) {
        assert(false);
    }

    void visiFunctionTypeStatementt(FunctionTypeStatement *node) {
        assert(false);
    }

    void visitNameProxy(NameProxy *name) {
    }
    void visitAssignment(Assignment *node) {
        node->lvalue()->accept(this);
        node->expression()->accept(this);
    }
    void visitBinaryExpression(BinaryExpression *node) {
        node->left()->accept(this);
        node->right()->accept(this);
    }
    void visitReturnStatement(ReturnStatement *node) {
        if (node->expression())
            fun_->returns(ValueReturn);
        else
            fun_->returns(VoidReturn);
    }
    void visitForStatement(ForStatement *node) {
        SymbolEnv env(&env_);

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

        node->setScope(env.scope());
    }
    void visitBlockStatement(BlockStatement *node) {
        if (node->type() == TOK_NEW) {
            // Don't create a symbol environment for this block, since it
            // was created solely to house multiple variable decls.
            for (size_t i = 0; i < node->statements()->length(); i++)
                node->statements()->at(i)->accept(this);
        } else {
            assert(node->type() == TOK_LBRACE);

            SymbolEnv env(&env_);

            for (size_t i = 0; i < node->statements()->length(); i++)
                node->statements()->at(i)->accept(this);
        
            if (node->type() == TOK_NEW) {
                assert(!env.scope());
                return;
            }

            node->setScope(env.scope());
        }
    }
    void visitIntegerLiteral(IntegerLiteral *node) {
    }
    void visitExpressionStatement(ExpressionStatement *node) {
        node->expression()->accept(this);
    }
    void visitCallExpression(CallExpression *node) {
        node->callee()->accept(this);
        for (size_t i = 0; i < node->arguments()->length(); i++)
            node->arguments()->at(i)->accept(this);
    }
    void visitIfStatement(IfStatement *node) {
        node->ifTrue()->accept(this);
        if (node->ifFalse())
            node->ifFalse()->accept(this);
    }
    void visitIndexExpression(IndexExpression *node) {
        node->left()->accept(this);
        node->right()->accept(this);
    }
    void visitFloatLiteral(FloatLiteral *node) {
    }
    void visitWhileStatement(WhileStatement *node) {
        node->condition()->accept(this);
        node->body()->accept(this);
    }
    void visitBreakStatement(BreakStatement *node) {
    }
    void visitContinueStatement(ContinueStatement *node) {
    }
    void visitStringLiteral(StringLiteral *node) {
    }
    void visitIncDecExpression(IncDecExpression *node) {
        node->expression()->accept(this);
    }
    void visitUnaryExpression(UnaryExpression *node) {
        node->expression()->accept(this);
    }
    void visitTernaryExpression(TernaryExpression *node) {
        assert(false);
    }
    void visitBooleanLiteral(BooleanLiteral *node) {
    }
    void visitFieldExpression(FieldExpression *node) {
    }
    void visitSwitchStatement(SwitchStatement *node) {
        if (node->defaultCase())
            node->defaultCase()->accept(this);

        for (size_t i = 0; i < node->cases()->length(); i++)
            node->cases()->at(i)->statement()->accept(this);
    }
    void visitArrayLiteral(ArrayLiteral *node) {
    }
    void visitImportStatement(ImportStatement *node) {
    }

  private:
    Scope *getGlobalOrCreateBlockScope() {
        if (env_->scope()) {
            assert(env_->scope()->kind() == Scope::BLOCK ||
                   env_->scope()->kind() == Scope::GLOBAL);
            return env_->scope();
        }
        return getOrCreateBlockScope();
    }
    Scope *getOrCreateBlockScope() {
        if (env_->scope()) {
            assert(env_->scope()->kind() == Scope::BLOCK);
            return env_->scope();
        }
        
        LocalScope *scope = LocalScope::New(pool_);
        if (!scope)
            return NULL;

        env_->setScope(scope);
        return scope;
    }

    bool registerName(Scope *scope, Symbol *sym) {
        if (!scope)
            return false;

        if (Symbol *other = scope->localLookup(sym->name())) {
            // Report, but allow errors to continue.
            cc_.reportError(sym->pos(), Message_RedeclaredName,
                            sym->name()->chars(),
                            other->pos().line,
                            other->pos().col);
            return true;
        }

        return scope->addSymbol(sym);
    }

    bool registerArguments(const FunctionSignature &sig) {
        if (!sig.parameters()->length())
            return true;

        ArgumentScope *argScope = ArgumentScope::New(pool_);
        if (!argScope)
            return false;
        env_->setScope(argScope);

        for (size_t i = 0; i < sig.parameters()->length(); i++) {
            Parameter *param = sig.parameters()->at(i);
            VariableSymbol *sym = new (pool_) VariableSymbol(argScope, param->name(), param->pos());
            if (!registerName(env_->scope(), sym))
                return false;
            param->setSymbol(sym);
        }

        return true;
    }

  private:
    Zone *zone_;
    PoolAllocator &pool_;
    CompileContext &cc_;
    TranslationUnit *unit_;
    SymbolEnv *env_;
    FunctionScope *fun_;
};

void
ke::PopulateNamesAndTypes(Zone *zone, CompileContext &cc, TranslationUnit *unit)
{
    AutoEnterCompileContext enter(cc, unit);
    NamePopulator populator(zone, cc, unit);
    populator.analyze();
}

static const int INFER_ARRAY_SIZE = 0;
static const int EVAL_ARRAY_SIZE = -1;
static const int DYNAMIC_ARRAY_SIZE = -2;

class NameBinderBase : public AstVisitor
{
  public:
    NameBinderBase(Zone *zone, CompileContext &cc, TranslationUnit *unit)
      : zone_(zone),
        pool_(zone->pool()),
        cc_(cc),
        unit_(unit)
    {
    }

  protected:
    Type *buildVariableType(VariableDeclaration *node) {
        Local<Type> type(zone_, bindType(node->type(), node->quals()));
        if (!type)
            return NULL;

        // We don't allow array typedefs yet.
        assert(!type->isArray());

        if (node->dims()) {
            int dims[MAX_ARRAY_DEPTH];
            int levels = evaluateDimensions(node->pos(), type, node->dims(), dims);
            if (levels < 0)
                return NULL;

            // Do some extra inference based on the initializer, if present.
            Expression *init = node->initialization();
            if (init) {
                if (init->isArrayLiteral() && init->toArrayLiteral()->isFixed()) {
                    Local<Type> contained(zone_, type->isArray()
                                                 ? ArrayType::cast(type)->contained()
                                                 : type);
                    if (!inferFixedArrayDimensions(init->toArrayLiteral(), contained, dims, levels))
                        return NULL;
                } else if (init->isStringLiteral()) {
                    dims[levels - 1] = init->toStringLiteral()->string()->length() + 1;
                }
            }

            // If we got extra dimensions, we need to build a new type.
            if (node->dims()) {
                if ((type = buildArrayType(type, node->quals(), dims, node->dims()->length())) == NULL)
                    return NULL;
            }
        }

        return type;
    }

    int evaluateDimensions(const SourcePosition &pos, Handle<Type> typeArg, ExpressionList *exprs, int dims[MAX_ARRAY_DEPTH]) {
        unsigned level = 0;
        Local<Type> type(zone_, typeArg);
        while (type->isArray()) {
            ArrayType *atype = ArrayType::cast(type);
            dims[level] = atype->isFixedLength()
                          ? atype->fixedLength()
                          : DYNAMIC_ARRAY_SIZE;
            type = atype->contained();
            level++;
        }

        if (!exprs)
            return level;

        if (level + exprs->length() > MAX_ARRAY_DEPTH) {
            cc_.reportError(pos, Message_MaximumArrayDepth);
            return -1;
        }

        bool hadEmptySize = false;
        for (size_t i = 0; i < exprs->length(); i++) {
            Expression *expr = exprs->at(i);
            if (!expr) {
                dims[i] = INFER_ARRAY_SIZE;
                hadEmptySize = true;
                continue;
            }

            BoxedPrimitive box;
            if (EvaluateForConstant(expr, &box) && box.type() == PrimitiveType_Int32) {
                int size = box.toInt();
                if (size <= 0) {
                    cc_.reportError(expr->pos(), Message_BadArraySize);
                    return false;
                }

                dims[i] = size;
                continue;
            }

            if (hadEmptySize) {
                cc_.reportError(expr->pos(), Message_BadDynamicInitializer);
                return false;
            }

            dims[i] = EVAL_ARRAY_SIZE;
        }

        return level + exprs->length();
    }

    // This function computes missing dimension sizes based on a literal
    // initializer. We don't really handle any size rules here; we just
    // do a really dumb inference.
    bool inferFixedArrayDimensions(ArrayLiteral *lit, Handle<Type> contained, int dims[MAX_ARRAY_DEPTH], int levels) {
        for (int i = 0; i < levels; i++) {
            if (dims[i] == EVAL_ARRAY_SIZE || dims[i] == DYNAMIC_ARRAY_SIZE) {
                // The following are invalid:
                //   new x[<expr>] = {...}
                //   new Type:x = {...}  // where Type is a non-fixed array type
                cc_.reportError(lit->pos(), Message_CannotInitializeEvalArray);
                return false;
            }

            if (dims[i] == INFER_ARRAY_SIZE) {
                // Character arrays are always dynamic when inferred from string literals.
                if (i == levels - 1 && contained->isChar())
                    dims[i] = DYNAMIC_ARRAY_SIZE;
                else
                    dims[i] = lit->expressions()->length();
            }

            if (i != levels - 1) {
                // Fixed array literals are guaranteed to have at least one expression.
                Expression *next = lit->expressions()->at(0);
                if (!next->isArrayLiteral()) {
                    // Whelp... this array is just malformed. Not the best error message
                    // but whatever.
                    cc_.reportError(next->pos(), Message_ArraySizeCannotBeDetermined);
                    return false;
                }
                lit = next->toArrayLiteral();
            }
        }

        return true;
    }

    ArrayType *buildArrayType(Handle<Type> contained, TypeQualifiers quals, int dims[MAX_ARRAY_DEPTH], size_t postlevels) {
        Local<Type> type(zone_, contained);

        for (size_t i = postlevels; i > 0; --i) {
            int size = dims[i - 1] > 0
                       ? dims[i - 1]
                       : ArrayType::DYNAMIC_ARRAY_SIZE;
            
            if ((type = zone_->types()->newArray(type, size)) == NULL)
                return NULL;
            if ((type = zone_->types()->qualify(type, quals)) == NULL)
                return NULL;
        }
        return ArrayType::cast(type);
    }

    bool fillFunctionType(Handle<FunctionType> fun, const FunctionSignature &sig) {
        Local<Type> type(zone_);
        if (!fun->returnType()) {
            if ((type = bindType(sig.returnType(), TypeQual_None)) == NULL)
                return false;
            fun->setReturnType(type);
        }

        if (sig.variadic())
            fun->setVariadic();

        Local<FixedArray> params(zone_, FixedArray::New(zone_, sig.parameters()->length(), Heap::Tenure_Old));
        if (!params)
            return false;

        for (size_t i = 0; i < sig.parameters()->length(); i++) {
            Parameter *param = sig.parameters()->at(i);
            if ((type = bindType(param->type(), param->quals())) == NULL)
                return false;

            assert(!type->isArray());

            if (param->dims()) {
                int dims[MAX_ARRAY_DEPTH];
                int levels = evaluateDimensions(param->pos(), type, param->dims(), dims);
                if (levels < 0)
                    return false;

                // If we got extra dimensions, we need to build a new type.
                // Unlike variables, we do not infer anything about array
                // sizes from its default initializer.
                if (param->dims()) {
                    if ((type = buildArrayType(type, param->quals(), dims, param->dims()->length())) == NULL)
                        return false;
                }

                if (ArrayType::cast(type)->innermost()->isVoid()) {
                    cc_.reportError(param->type()->pos(), Message_CannotDeclareVoid);
                    return false;
                }
            }

            if (param->reference()) {
                if (!type->isPod()) {
                    cc_.reportError(param->pos(), Message_ArrayCantBeReference);
                    return false;
                }
                if (param->quals() & TypeQual_Const) {
                    cc_.reportError(param->pos(), Message_CannotConstReference);
                    return false;
                }
                if ((type = zone_->types()->getReference(type, false)) == NULL)
                    return false;
            }
            if (param->quals() & TypeQual_Const) {
                if (!type->isArray() && !type->isStruct()) {
                    cc_.reportError(param->pos(), Message_InvalidConstOnFormal);
                    return false;
                }
            }

            if (type->isVoid()) {
                cc_.reportError(param->type()->pos(), Message_CannotDeclareVoid);
                return false;
            }

            params->set(zone_, i, type);
            param->sym()->setType(type);
        }

        fun->setParameterTypes(params);

        return true;
    }

    Type *bindType(Expression *expr, TypeQualifiers quals) {
        Local<Type> type(zone_);

        if (!expr) {
            // If no type was declared, we return int32.
            type = zone_->types()->getPrimitive(PrimitiveType_Int32);
        } else {
            expr->accept(this);

            NameProxy *proxy = expr->asNameProxy();
            assert(proxy);

            Symbol *sym = proxy->sym();
            if (!sym)
                return NULL;

            if (!sym->isType()) {
                cc_.reportError(expr->pos(), Message_IdentifierIsNotAType, sym->name()->chars());
                return NULL;
            }

            type = sym->toType()->effective();
        }

        return zone_->types()->qualify(type, quals);
    }

  protected:
    Zone *zone_;
    PoolAllocator &pool_;
    CompileContext &cc_;
    TranslationUnit *unit_;
};

class GlobalBuilder : public NameBinderBase
{
    typedef ScopedRoot<Descriptor> ScopedDescriptor;
    struct PrimitiveFill {
        ScopedDescriptor *desc;
        BoxedPrimitive prim;

        PrimitiveFill(ScopedDescriptor *desc, BoxedPrimitive prim)
          : desc(desc),
            prim(prim)
        {
        }
    };

  public:
    GlobalBuilder(Zone *zone, CompileContext &cc, TranslationUnit *unit)
      : NameBinderBase(zone, cc, unit),
        globalScope_(unit->globalScope())
    {
    }

    Struct *build() {
        for (size_t i = 0; i < unit_->tree()->imports()->length(); i++)
            unit_->tree()->imports()->at(i)->accept(this);

        // Next, enter the global scope and walk all statements.
        for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
            Statement *stmt = unit_->tree()->statements()->at(i);
            stmt->accept(this);
        }

        Local<Struct> globals(zone_, createGlobals());
        if (!globals)
            return NULL;

        populate(globals);

        return globals;
    }

  private:
    Struct *createGlobals() {
        Local<FixedArray> descs(zone_, FixedArray::New(zone_, descriptors_.length(), Heap::Tenure_Old));
        if (!descs)
            return NULL;

        for (unsigned i = 0; i < descriptors_.length(); i++)
            descs->set(zone_, i, *descriptors_[i]);

        Local<String> name(zone_, unit_->module()->name());
        Local<StructType> type(zone_, StructType::New(zone_, name, descs));
        if (!type)
            return NULL;

        Local<StructMap> map(zone_, type->newMap());
        return Struct::New(zone_, map, Heap::Tenure_Old);
    }

    void populate(Handle<Struct> globals) {
        // This is a huge hack, but it's probably better than a full extra
        // pass. The problem is that until we have all the descriptors, we
        // can't start setting constexprs in the struct, and we need to set
        // them now so they're available during full semantic analysis. To
        // work around this, we build up the list of values we need to set
        // as we build up descriptors, and then populate the global struct
        // with this set.
        //
        // Note, this code is also kind of dead until we support linking. We
        // handle constexprs explicitly in importFrom(), by sniffing out the
        // symbol type. That code will go away later.
        for (size_t i = 0; i < primitiveFills_.length(); i++) {
            const PrimitiveFill &fill = primitiveFills_[i];
            assert(fill.prim.type() == PrimitiveType_Int32);
            globals->set(*fill.desc, fill.prim.toInt());
        }
    }

  public:
    void visitEnumStatement(EnumStatement *stmt) {
        if (stmt->visibility() != TOK_PUBLIC || !stmt->name())
            return;

        Local<Type> type(zone_, zone_->types()->getType());
        Descriptor *desc = Descriptor::New(zone_, stmt->name(), type, Descriptor::Public);
        if (!desc)
            return;
        if (!descriptors_.append(new (pool_) ScopedRoot<Descriptor>(desc)))
            return;

        for (size_t i = 0; i < stmt->entries()->length(); i++) {
            EnumStatement::Entry &e = stmt->entries()->at(i);
            ScopedDescriptor *desc = new (pool_) ScopedDescriptor(Descriptor::New(zone_, e.name, e.sym->type(), Descriptor::Public));
            if (!desc || !descriptors_.append(desc))
                return;

            // Save the value so we can export it immediately.
            if (!primitiveFills_.append(PrimitiveFill(desc, e.sym->value())))
                return;
        }
    }

    void visitNameProxy(NameProxy *proxy) {
        Scope *scope = unit_->globalScope();
        Symbol *sym = scope->lookup(proxy->name());
        if (!sym)
            cc_.reportError(proxy->pos(), Message_IdentifierNotFound, proxy->name()->chars());
        proxy->bind(sym);
    }

    void visitFunctionStatement(FunctionStatement *node) {
        Local<FunctionType> type(zone_, node->sym()->type());
        if (!fillFunctionType(type, node->signature()))
            return;

        unsigned offset;
        if (!builder_.add(type, &offset))
            return;

        Descriptor::Visibility visibility = (node->token() == TOK_NATIVE || node->token() == TOK_FORWARD)
                                            ? Descriptor::Public
                                            : Descriptor::Private;

        Descriptor *desc = Descriptor::New(zone_, node->name(), type, visibility);
        if (!desc)
            return;
        if (!descriptors_.append(new (pool_) ScopedRoot<Descriptor>(desc)))
            return;
    }

    void visitVariableDeclaration(VariableDeclaration *node) {
        Local<Type> type(zone_, buildVariableType(node));
        if (!type)
            return;

        // If we're in global scope, and we received a |const| qualifier, then
        // we extend this to array references as well. This is to sort of mimic
        // SP1 functionality, but also means that you cannot have changeable
        // const pointers in global scope.
        if ((node->quals() & TypeQual_Const) && type->isArray()) {
            if ((type = zone_->types()->qualify(type, TypeQual_Const)) == NULL)
                return;
        }

        node->sym()->setType(type);

        unsigned offset;
        if (!builder_.add(type, &offset))
            return;

        Descriptor *desc = Descriptor::New(zone_, node->name(), type, Descriptor::Private);
        if (!desc)
            return;
        if (!descriptors_.append(new (pool_) ScopedRoot<Descriptor>(desc)))
            return;
    }

    void visitImportStatement(ImportStatement *node) {
        if (!node->names()) {
            PathComponent *path = node->path();
            while (path->next)
                path = path->next;

            // Imports automatically go into the importScope. For now, we
            // error if there are any duplicate symbols entered into the
            // importScope.
            if (unit_->importScope()->localLookup(path->name)) {
                cc_.reportError(node->pos(), Message_DuplicateImport, path->name->chars());
                return;
            }

            Local<Type> type(zone_, zone_->types()->getImportable());
            ImportSymbol *sym = new (pool_) ImportSymbol(unit_->importScope(), path->name, node->pos(), type, node->importIndex());
            if (!unit_->importScope()->addSymbol(sym))
                return;
        } else if (node->importAllNames()) {
            Local<Importable> importable(zone_, unit_->module()->getImportAt(node->importIndex()));
            if (importable->isPackage()) {
                assert(false);
            } else {
                Local<Module> module(zone_, Module::cast(importable));
                if (!module->globals())
                    importAllFromTranslationUnit(node, module->translationUnit());
                else
                    assert(false);
            }
        } else {
            Local<Importable> importable(zone_, unit_->module()->getImportAt(node->importIndex()));
            if (importable->isPackage()) {
                assert(false);
            } else {
                Local<Module> module(zone_, Module::cast(importable));

                // Always grab from the translation unit if we can, for now.
                if (module->translationUnit())
                    importFromTranslationUnit(node, module->translationUnit());
                else
                    assert(false);
            }
        }
    }

  private:
    bool importFrom(ImportStatement *node, Symbol *import) {
        assert(import->type());

        // Check for duplicate import names.
        if (unit_->importScope()->localLookup(import->name())) {
            cc_.reportError(node->pos(), Message_DuplicateImport, import->name()->chars());
            return false;
        }

        Symbol *sym;
        if (import->isType()) {
            // Fuck it, make a TypeSymbol instead of an ImplicitSymbol. This
            // makes bindType() much simpler. We may run into problems
            // implementing linking, but it seems unlikely, as long as we are
            // exporting Types in module structs.
            Local<Type> type(zone_, zone_->types()->getType());
            sym = new (pool_) TypeSymbol(unit_->importScope(),
                                         import->name(),
                                         type,
                                         import->toType()->effective());
        } else if (import->isConstant()) {
            // Same deal. No reason to lookup in the module globals if we
            // already have a symbol.
            sym = new (pool_) ConstantSymbol(unit_->importScope(),
                                             import->name(),
                                             node->pos(),
                                             import->type(),
                                             import->toConstant()->value());
        } else {
            sym = new (pool_) ImplicitSymbol(unit_->importScope(),
                                             import->name(),
                                             node->pos(),
                                             import->type(),
                                             node->importIndex());
        }

        if (!unit_->importScope()->addSymbol(sym))
            return false;

        return true;
    }

    void importFromTranslationUnit(ImportStatement *node, TranslationUnit *other) {
        assert(!other->failed());

        for (size_t i = 0; i < node->names()->length(); i++) {
            Handle<String> name = *node->names()->at(i);

            // See if the name exists in the other translation unit.
            Symbol *import = other->globalScope()->findExported(name);
            if (!import) {
                FixedArray *path = unit_->module()->importPathAt(node->importIndex());
                cc_.reportError(node->pos(), Message_NotFoundInImportable,
                                name->chars(),
                                String::cast(path->at(path->length() - 1))->chars());
                return;
            }

            if (!importFrom(node, import))
                return;
        }
    }

    void importAllFromTranslationUnit(ImportStatement *node, TranslationUnit *other) {
        assert(!other->failed());

        for (size_t i = 0; i < other->globalScope()->exported()->length(); i++) {
            Symbol *import = other->globalScope()->exported()->at(i);
            if (!importFrom(node, import))
                return;
        }
    }

  private:
    StructureBufferBuilder builder_;
    Vector<ScopedRoot<Descriptor> *> descriptors_;
    GlobalScope *globalScope_;
    Vector<PrimitiveFill> primitiveFills_;
};
    
class NameBinder : public NameBinderBase
{
  public:
    class AutoLinkScope
    {
      public:
        AutoLinkScope(AutoLinkScope **prevp, Scope *scope)
          : prevp_(prevp),
            prev_(*prevp),
            scope_(scope)
        {
            if (scope_) {
                *prevp_ = this;
                if (prev_)
                    scope_->setParent(prev_->scope());
            }
        }
        ~AutoLinkScope() {
            if (scope_) {
                assert(*prevp_ == this);
                *prevp_ = prev_;
            }
        }
        Scope *scope() const {
            return scope_;
        }

      private:
        AutoLinkScope **prevp_;
        AutoLinkScope *prev_;
        Scope *scope_;
    };

  public:
    NameBinder(Zone *zone, CompileContext &cc, TranslationUnit *unit)
      : NameBinderBase(zone, cc, unit),
        link_(NULL)
    {
    }

    void bind() {
        // Start with the import scope, and collect all imported names.
        AutoLinkScope importScope(&link_, unit_->importScope());

        for (size_t i = 0; i < unit_->tree()->imports()->length(); i++)
            unit_->tree()->imports()->at(i)->accept(this);

        // Next, enter the global scope and walk all statements.
        AutoLinkScope globalScope(&link_, unit_->globalScope());
        for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
            Statement *stmt = unit_->tree()->statements()->at(i);
            stmt->accept(this);
        }
    }

    void visitVariableDeclaration(VariableDeclaration *node) {
        // Bind the initializer before registering the declaration, so that we
        // can error on bogus initializers (new x = x).
        if (node->initialization())
            node->initialization()->accept(this);

        // If the node already has a symbol (meaning it was a global), then
        // we don't have to do anything more.
        if (node->sym())
            return;

        Local<Type> type(zone_, buildVariableType(node));
        if (!type)
            return;

        VariableSymbol *sym = new (pool_) VariableSymbol(link_->scope(), node->name(), node->pos(), type);
        node->setSymbol(sym);
       
        if (Symbol *other = link_->scope()->localLookup(sym->name())) {
            // Report, but allow errors to continue.
            cc_.reportError(sym->pos(), Message_RedeclaredName,
                            sym->name()->chars(),
                            other->pos().line,
                            other->pos().col);
            return;
        }
        
        link_->scope()->addSymbol(sym);
    }
    void visitEnumStatement(EnumStatement *node) {
    }
    void visitFunctionStatement(FunctionStatement *node) {
        AutoLinkScope argScope(&link_, node->argScope());
        AutoLinkScope varScope(&link_, node->varScope());

        // If the function is in the global scope, we've already computed its
        // type.
        if (node->sym()->scope()->kind() != Scope::GLOBAL) {
            Local<FunctionType> type(zone_, node->sym()->type());
            if (!fillFunctionType(type, node->signature()))
                return;
        }

        if (node->body())
            node->body()->accept(this);
    }
    void visitStructureStatement(StructureStatement *node) {
        assert(false);
    }
    void visitFunctionTypeStatement(FunctionTypeStatement *node) {
        assert(false);
    }

    void visitNameProxy(NameProxy *proxy) {
        // We could have already bound globals.
        if (proxy->sym())
            return;

        Scope *scope = link_->scope();
        Symbol *sym = scope->lookup(proxy->name());
        if (!sym)
            cc_.reportError(proxy->pos(), Message_IdentifierNotFound, proxy->name()->chars());
        proxy->bind(sym);
    }
    void visitAssignment(Assignment *node) {
        node->lvalue()->accept(this);
        node->expression()->accept(this);
    }
    void visitBinaryExpression(BinaryExpression *node) {
        node->left()->accept(this);
        node->right()->accept(this);
    }
    void visitReturnStatement(ReturnStatement *node) {
        node->expression()->accept(this);
    }
    void visitForStatement(ForStatement *node) {
        AutoLinkScope scope(&link_, node->scope());

        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);
    }
    void visitBlockStatement(BlockStatement *node) {
        AutoLinkScope scope(&link_, node->scope());
        for (size_t i = 0; i < node->statements()->length(); i++)
            node->statements()->at(i)->accept(this);
    }
    void visitIntegerLiteral(IntegerLiteral *node) {
    }
    void visitExpressionStatement(ExpressionStatement *node) {
        node->expression()->accept(this);
    }
    void visitCallExpression(CallExpression *node) {
        node->callee()->accept(this);
        for (size_t i = 0; i < node->arguments()->length(); i++)
            node->arguments()->at(i)->accept(this);
    }
    void visitIfStatement(IfStatement *node) {
        node->condition()->accept(this);
        node->ifTrue()->accept(this);
        if (node->ifFalse())
            node->ifFalse()->accept(this);
    }
    void visitIndexExpression(IndexExpression *node) {
        node->left()->accept(this);
        node->right()->accept(this);
    }
    void visitFloatLiteral(FloatLiteral *node) {
    }
    void visitWhileStatement(WhileStatement *node) {
        node->condition()->accept(this);
        node->body()->accept(this);
    }
    void visitBreakStatement(BreakStatement *node) {
    }
    void visitContinueStatement(ContinueStatement *node) {
    }
    void visitStringLiteral(StringLiteral *node) {
    }
    void visitIncDecExpression(IncDecExpression *node) {
        node->expression()->accept(this);
    }
    void visitUnaryExpression(UnaryExpression *node) {
        if (node->tag())
            node->tag()->accept(this);
        node->expression()->accept(this);
    }
    void visitTernaryExpression(TernaryExpression *node) {
        node->condition()->accept(this);
        node->left()->accept(this);
        node->right()->accept(this);
    }
    void visitBooleanLiteral(BooleanLiteral *node) {
    }
    void visitFieldExpression(FieldExpression *node) {
        node->left()->accept(this);
    }
    void visitSwitchStatement(SwitchStatement *node) {
        node->expression()->accept(this);
        node->defaultCase()->accept(this);
        for (size_t i = 0; i < node->cases()->length(); i++) {
            // We don't test case expressions because they are literals.
            Case *c = node->cases()->at(i);
            c->statement()->accept(this);
        }
    }
    void visitArrayLiteral(ArrayLiteral *node) {
        for (size_t i = 0; i < node->expressions()->length(); i++)
            node->expressions()->at(i)->accept(this);
    }
    void visitImportStatement(ImportStatement *node) {
    }

  private:
    AutoLinkScope *link_;
};

void
ke::BindGlobals(Zone *zone, CompileContext &cc, TranslationUnit *unit)
{
    AutoEnterCompileContext enter(cc, unit);

    GlobalBuilder builder(zone, cc, unit);
    Local<Struct> globals(zone, builder.build());
    if (!globals || unit->failed())
        return;

    unit->module()->setGlobals(globals);
}

void
ke::BindNamesAndTypes(Zone *zone, CompileContext &cc, TranslationUnit *unit)
{
    AutoEnterCompileContext enter(cc, unit);
    NameBinder binder(zone, cc, unit);
    binder.bind();
}