/* 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 <assert.h>

 #include "../Zone.h"

 #include "../Strings.h"

 #include "../NativeTable.h"

 #include "../TypeManager.h"

 #include "../Modules.h"

 #include "../Code.h"

 #include "SemanticAnalysis.h"

 #include "../Heap-inl.h"

 using namespace ke;

 #define __ emitter_.

 typedef BytecodeEmitter::Label Label;

 class AutoEnterScope

 {

   public:

     AutoEnterScope(Scope **prevp, Scope *scope)

       : prevp_(prevp),

         prev_(*prevp),

         scope_(scope)

     {

         if (!scope_)

             return;

         prev_ = *prevp_;

         *prevp_ = scope;

         assert(prev_ == scope->enclosing());

     }

     ~AutoEnterScope()

     {

         if (scope_)

             *prevp_ = prev_;

     }

   private:

     Scope **prevp_;

     Scope *prev_;

     Scope *scope_;

 };

 SemanticAnalysis::SemanticAnalysis(Zone *zone, CompileContext &cc, TranslationUnit *unit)

   : zone_(zone),

     pool_(zone->pool()),

     cc_(cc),

     unit_(unit),

     hir_(NULL),

     emitter_(pool_),

     module_(NULL),

     loop_(NULL)

 {

 }

 SemanticAnalysis::SemanticAnalysis(SemanticAnalysis *parent, Handle<FunctionType> fun)

   : zone_(parent->zone_),

     pool_(parent->pool_),

     cc_(parent->cc_),

     unit_(parent->unit_),

     hir_(NULL),

     scope_(parent->scope_),

     emitter_(pool_),

     module_(parent->module_),

     fun_(fun),

     loop_(NULL)

 {

 }

 void

 SemanticAnalysis::analyze()

 {

     scope_ = unit_->globalScope();

     module_ = Module::New(zone_);

     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_, unit_->globalScope()->build(zone_));

     if (!globals)

         return;

     module_->setGlobals(globals);

     Local<Code> code(zone_, __ finish());

     if (!code)

         return;

     code->setModule(module_);

     module_->setCode(code);

 #ifndef NDEBUG

 //    Disassemble(code, stdout);

 #endif

     unit_->module_ = module_;

 }

 void

 SemanticAnalysis::visitFunctionStatement(FunctionStatement *stmt)

 {

     FunctionSymbol *sym = stmt->sym();

     Local<FunctionType> type(zone_, sym->type());

     assert(scope_->kind() == Scope::GLOBAL);

     if (stmt->token() == TOK_NATIVE) {

         // Define the native now.

         size_t index;

         if (!zone_->nativeTable()->add(stmt->name(), &index))

             return;

         Local<Native> native(zone_, Native::New(zone_, type, index));

         if (!native)

             return;

         __ object(native);

         __ setglobal(sym);

         __ pop();

     }

     // If the function is a forward or native, we don't have to do anything.

     if (stmt->token() == TOK_NATIVE || stmt->token() == TOK_FORWARD)

         return;

     SemanticAnalysis child(this, type);

     Local<Function> funobj(zone_, child.compile(stmt));

     if (!funobj)

         return;

     __ object(funobj);

     __ setglobal(sym);

     if (stmt->token() == TOK_PUBLIC)

         __ public_();

     else

         __ pop();

 }

 Function *

 SemanticAnalysis::compile(FunctionStatement *stmt)

 {

     __ setFirstLine(stmt->pos().line);

     AutoEnterScope argScope(&scope_, stmt->argScope());

     for (size_t i = 0; i < stmt->signature().parameters()->length(); i++) {

         Parameter *param = stmt->signature().parameters()->at(i);

         param->sym()->allocate(VariableSymbol::Arg, i);

     }

     AutoEnterScope varScope(&scope_, stmt->varScope());

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

     Local<Code> code(zone_, __ finish());

     if (!code)

         return NULL;

     code->setModule(module_);

     Local<Function> fun(zone_, Function::New(zone_, code, fun_, stmt->name(), stmt->pos()));

     if (!fun)

         return NULL;

 #ifndef NDEBUG

 //    Disassemble(code, stdout);

 #endif

     return fun;

 }

 void 

 SemanticAnalysis::visitBlockStatement(BlockStatement *node)

 {

     AutoEnterScope scope(&scope_, node->scope());

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

         Statement *stmt = node->statements()->at(i);

         __ note_position(stmt->pos());

         stmt->accept(this);

         assert(__ stackDepth() == 0);

     }

 }

 void

 SemanticAnalysis::visitExpressionStatement(ExpressionStatement *node)

 {

     // While building HIR, we enter new pool and root scopes, since HIR

     // creation is purely temporary.

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

     HIR *hir = eval(node->expression());

     if (!hir)

         return;

     discharge(hir);

     if (!hir->type()->isVoid())

         __ pop();

 }

 void

 SemanticAnalysis::visitIfStatement(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);

 }

 void

 SemanticAnalysis::requireLifoStack()

 {

     if (!loop_)

         return;

     loop_->setUsesLifoStack();

 }

 void

 SemanticAnalysis::visitLoopBody(Statement *stmt)

 {

     // We always mark off a loop body, so on each edge, we can balance the

     // LIFO stack. Right now, we don't have the ability to budget the LIFO

     // stack ahead of time. If we turn out to never need the LIFO stack, we

     // mark it as unnecessary. (The interpreter can't really make use of this,

     // but the JIT can).

     //

     // Note that balancing the LIFO stack isn't even necessary, so this

     // feature may be removed. All this mechanism does is mitigate the

     // possibility that a long-running loop will overflow the LIFO region

     // and therefore start requiring nursery allocations.

     int pos = __ enterloop();

     stmt->accept(this);

     __ leaveloop();

     if (loop_->usesLifoStack())

         __ setLoopUsesLifoStack(pos);

 }

 void

 SemanticAnalysis::visitForStatement(ForStatement *node)

 {

     AutoEnterScope scope(&scope_, node->scope());

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

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

     visitLoopBody(node->body());

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

     assert(__ stackDepth() == 0);

 }

 void

 SemanticAnalysis::visitWhileStatement(WhileStatement *node)

 {

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

     Label header, join;

     __ bind(&header);

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

     if (node->token() == TOK_WHILE) {

         Label body;

         visitForTest(node->condition(), &body, &join, &body);

         visitLoopBody(node->body());

         __ jump(&header);

     } else {

         visitLoopBody(node->body());

         visitForTest(node->condition(), &header, &join, &join);

     }

     __ bind(&join);

     assert(__ stackDepth() == 0);

 }

 static inline Heap::Tenure

 InferTenure(Symbol *sym)

 {

     if (sym->scope()->kind() == Scope::GLOBAL)

         return Heap::Tenure_Old;

     // SP2's array semantics allow any array kind to escape, so we must use

     // the normal heap. (Hopefully escape analysis can ease this pain later).

     if (sym->type()->isArray())

         return Heap::Tenure_Default;

     return Heap::Tenure_Default;

 }

 void

 SemanticAnalysis::visitVariableDeclaration(VariableDeclaration *node)

 {

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

     if (node->initialization()) {

         HIR *hir = NULL;

         if ((hir = eval(node->initialization())) == NULL)

             return;

         if ((hir = coerce(hir, node->sym()->type(), Coerce_Assign)) == NULL)

             return;

         discharge(hir);

     } else {

         if (node->sym()->type()->isInt32() ||

             node->sym()->type()->isEnum() ||

             node->sym()->type()->isChar() ||

             node->sym()->type()->isBool())

         {

             __ int_(0);

         } else if (node->sym()->type()->isFloat()) {

             __ float_(0);

         } else if (node->sym()->type()->isArray()) {

             Local<ArrayType> type(zone_, ArrayType::cast(node->sym()->type()));

             Local<ArrayMap> map(zone_, ArrayMap::Attach(zone_, type));

             if (!map)

                 return;

             if (type->isFixedLength()) {

                 __ newarray(OP_NEWFIXED, map, InferTenure(node->sym()));

             } else if (node->dims()) {

                 assert(false);

                 __ newarray(OP_NEWSIZED, map, InferTenure(node->sym()));

             } else {

                 __ newarray(OP_NEWEMPTY, map, InferTenure(node->sym()));

             }

         }

     }

     if (!__ allocate(node->sym()))

         return;

     set(node->sym());

     __ pop();

 }

 void

 SemanticAnalysis::visitReturnStatement(ReturnStatement *node)

 {

     if (!node->expression()) {

         if (!fun_->returnType()->isVoid()) {

             cc_.reportError(node->pos(), Message_UsedVoidReturn);

             return;

         }

         __ returnvoid();

         return;

     }

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

     HIR *hir = eval(node->expression());

     if (!hir)

         return;

     Local<Type> returnType(zone_, fun_->returnType());

     if ((hir = coerce(hir, returnType, Coerce_Return)) == NULL)

         return;

     discharge(hir);

     __ return_();

 }

 void

 SemanticAnalysis::visitBinaryExpression(BinaryExpression *node)

 {

     HIR *left = eval(node->left());

     HIR *right = eval(node->right());

     if (!left || !right)

         return;

     hir_ = binary(node, node->token(), left, right);

 }

 bool

 SemanticAnalysis::checkArgumentCount(Handle<FunctionType> type, unsigned actual)

 {

     if (type->parameters()->length() == actual)

         return true;

     if (actual > type->parameters()->length()) {

         if (!type->isNative() || !type->isNativeVariadic())

             return false;

         return true;

     }

     if (!type->defaults())

         return false;

     // Missing arguments. See if there's a default argument for each missing

     // actual.

     for (unsigned i = actual; i < type->parameters()->length(); i++) {

         if (!type->defaults()->at(i))

             return false;

     }

     return true;

 }

 void

 SemanticAnalysis::visitNameProxy(NameProxy *proxy)

 {

     Symbol *sym = proxy->sym();

     VariableSymbol *var = sym->asVariable();

     Scope *in = sym->scope();

     switch (in->kind()) {

       case Scope::GLOBAL:

         hir_ = new (pool_) HGlobal(proxy, sym);

         return;

       case Scope::FUNCTION:

         assert(var->storage() == VariableSymbol::Arg);

         hir_ = new (pool_) HLocal(proxy, var);

         return;

       default:

         assert(in->kind() == Scope::BLOCK);

         assert(var->storage() == VariableSymbol::Local);

         hir_ = new (pool_) HLocal(proxy, var);

         return;

     }

 }

 void

 SemanticAnalysis::visitIntegerLiteral(IntegerLiteral *lit)

 {

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

     hir_ = new (pool_) HInteger(lit, type, lit->value());

 }

 void

 SemanticAnalysis::visitFloatLiteral(FloatLiteral *node)

 {

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

     hir_ = new (pool_) HFloat(node, type, (float)node->value());

 }

 void

 SemanticAnalysis::visitCallExpression(CallExpression *node)

 {

     HIR *callee = eval(node->callee());

     if (!callee)

         return;

     if (!callee->type()->isFunction()) {

         cc_.reportError(node->pos(), Message_CalleeNotFunction);

         return;

     }

     Local<FunctionType> fun(zone_, FunctionType::cast(callee->type()));

     if (!checkArgumentCount(fun, node->arguments()->length())) {

         cc_.reportError(node->pos(), Message_ArgumentCountMismatch);

         return;

     }

     if (fun->isForward()) {

         cc_.reportError(node->pos(), Message_ForwardNotImplemented, fun->name()->chars());

         return;

     }

     HIRList *args = new (pool_) HIRList;

     for (unsigned i = 0; i < node->arguments()->length(); i++) {

         Expression *expression = node->arguments()->at(i);

         HIR *arg = eval(expression);

         if (!arg)

             return;

         Handle<Type> given = arg->type();

         bool mustComputeReference;

         if (i >= fun->parameters()->length()) {

             // Special handling for natives. Arguments past the formal must

             // always have references computed. However, arrays are already

             // references for natives.

             assert(fun->isNative() && fun->isNativeVariadic());

             mustComputeReference = !given->isReference() &&

                                    !given->isArray();

         } else {

             Local<Type> actual(zone_, fun->parameterAt(i));

             if (expression->isIndexExpression()) {

                 // Temporarily disabled.

                 assert(!actual->isArray());

                 if (actual->isReference()) {

                     cc_.reportError(expression->pos(), Message_CannotComputeIndexRef);

                     return;

                 }

             }

             if (actual->isReference()) {

                 // If the actual is a reference, the coercion rules are much

                 // stricter; the contained types must be identical.

                 // :TODO: make this not an assert

                 assert(ReferenceType::cast(actual)->contained() == arg->type());

             } else {

                 // When we start overloading, coercion will have to happen later.

                 arg = coerce(arg, actual, Coerce_Arg);

                 if (!arg)

                     return;

             }

             mustComputeReference = actual->isReference() && !given->isReference();

         }

         if (mustComputeReference) {

             // Refs always use the LIFO stack if they can.

             arg = new (pool_) HToRef(arg->node(), arg->type(), arg);

             requireLifoStack();

         }

         if (!args->append(arg))

             return;

     }

     hir_ = new (pool_) HCall(node, fun->returnType(), callee, args);

 }

 void

 SemanticAnalysis::visitAssignment(Assignment *node)

 {

     HLValue *lval = lvalue(node->lvalue());

     if (!lval)

         return;

     HIR *hir = eval(node->expression());

     if ((hir = coerce(hir, lval->type(), Coerce_Assign)) == NULL)

         return;

     hir_ = new (pool_) HStore(node, node->token(), lval, hir);

 }

 void

 SemanticAnalysis::visitBreakStatement(BreakStatement *node)

 {

     if (!loop_) {

         cc_.reportError(node->pos(), Message_BreakOutsideLoop);

         return;

     }

     __ j(OP_BREAK, loop_->break_());

 }

 void

 SemanticAnalysis::visitContinueStatement(ContinueStatement *node)

 {

     if (!loop_) {

         cc_.reportError(node->pos(), Message_ContinueOutsideLoop);

         return;

     }

     __ j(OP_CONTINUE, loop_->continue_());

 }

 void

 SemanticAnalysis::visitIndexExpression(IndexExpression *node)

 {

     HIR *left = eval(node->left());

     if (!left)

         return;

     HIR *right = eval(node->right());

     if (!right)

         return;

     // Hrm... yes, for now, let's coerce here.

     Local<Type> i32(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));

     if ((right = coerce(right, i32, Coerce_Arg)) == NULL)

         return;

     // Do not coerce here, there's no reason to yet.

     if (!left->type()->isArray()) {

         cc_.reportError(node->left()->pos(), Message_IndexBaseMustBeArray);

         return;

     }

     hir_ = new (pool_) HIndex(node,

                               ArrayType::cast(left->type())->contained(),

                               left,

                               right);

 }

 void

 SemanticAnalysis::visitIncDecExpression(IncDecExpression *node)

 {

     HLValue *lval = lvalue(node->expression());

     if (!lval)

         return;

     if (!lval->type()->isInt32() && !lval->type()->isFloat()) {

         assert(false);

         return;

     }

     HIR *rval;

     if (lval->type()->isInt32())

         rval = new (pool_) HInteger(node, lval->type(), 1);

     else

         rval = new (pool_) HFloat(node, lval->type(), 1.0);

     if (node->postfix())

         hir_ = new (pool_) HPostIncDec(node, node->token(), lval, rval);

     else

         hir_ = new (pool_) HStore(node, node->token(), lval, rval);

 }

 Type *

 SemanticAnalysis::coercionType(TokenKind token, HIR *left, HIR *right)

 {

     Handle<Type> l = left->type();

     Handle<Type> r = right->type();

     if (token >= TOK_PLUS && token <= TOK_SLASH) {

         // We allow: [float|int32] + [float|int32]

         if (l->isFloat() && r->isInt32())

             return l;

         if (l->isInt32() && r->isFloat())

             return r;

         if (l->isInt32() && r->isInt32())

             return l;

     }

     // :TODO: remove

     assert(l == r);

     return left->type();

 }

 bool

 SemanticAnalysis::typeCheckArray(const SourcePosition &pos,

                                  Handle<Type> argGiven,

                                  Handle<Type> argActual,

                                  CoercionKind kind)

 {

     if (!argGiven->isArray()) {

         cc_.reportError(pos, Message_ExpectedArray);

         return false;

     }

     Local<ArrayType> actual(zone_, ArrayType::cast(argActual));

     Local<ArrayType> given(zone_, ArrayType::cast(argGiven));

     if (actual->levels() != given->levels()) {

         cc_.reportError(pos, Message_ArrayDimensionsMismatch);

         return false;

     }

     unsigned level = 1;

     while (true) {

         if (actual->isFixedLength()) {

             if (kind == Coerce_Return || kind == Coerce_Assign) {

                 if (!given->isFixedLength()) {

                     cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);

                     return false;

                 }

                 if (actual->isCharArray()) {

                     // String assignment can have a truncated |given|.

                     if (given->fixedLength() > actual->fixedLength()) {

                         cc_.reportError(pos, Message_ArrayAssignmentTooBig);

                         return false;

                     }

                 } else {

                     if (given->fixedLength() != actual->fixedLength()) {

                         cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);

                         return false;

                     }

                 }

             }

         } else if (given->isFixedLength()) {

             // We do not allow assignments in the form:

             //  [][] = [][Y]

             //

             // Otherwise, the following code could break the size guarantees

             // of the right-hand side:

             //

             //  new x[][5];

             //  new y[][];

             //  new z[3];

             //

             //

             //  y = x;

             //  y[0] = z;

             //

             // Now |x[0]| contains a 3-length array.

             if (level > 1) {

                 cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);

                 return false;

             }

         }

         if (!given->contained()->isArray() || !actual->contained()->isArray())

             break;

         given = ArrayType::cast(given->contained());

         actual = ArrayType::cast(actual->contained());

     }

     // These arrays must contain the same innermost type.

     if (given->contained() != actual->contained()) {

         cc_.reportError(pos, Message_TypeMismatch,

                         GetTypeName(actual->contained()),

                         GetTypeName(given->contained()));

         return false;

     }

     return true;

 }

 HIR *

 SemanticAnalysis::coerce(HIR *hir, Handle<Type> to, CoercionKind kind)

 {

     Handle<Type> from = hir->type();

     if (from->isInt32() && to->isFloat())

         return new (pool_) HConvert(hir->node(), to, OP_CVT_I2F, hir);

     if (from->isInt32() && to->isBool())

         return new (pool_) HConvert(hir->node(), to, OP_CVT_I2B, hir);

     if (to->isArray()) {

         if (!typeCheckArray(SourcePosition(), from, to, kind))

             return NULL;

         return hir;

     }

     return hir;

 }

 void

 SemanticAnalysis::set(VariableSymbol *sym)

 {

     if (sym->scope()->kind() == Scope::GLOBAL) {

         __ setglobal(sym);

     } else {

         assert(sym->storage() == VariableSymbol::Local);

         __ setlocal(sym);

     }

 }

 HIR *

 SemanticAnalysis::binary(AstNode *node, TokenKind token, HIR *left, HIR *right)

 {

     Local<Type> coercion(zone_, coercionType(token, left, right));

     if (!coercion)

         return NULL;

     if ((left = coerce(left, coercion, Coerce_Arg)) == NULL)

         return NULL;

     if ((right = coerce(right, coercion, Coerce_Arg)) == NULL)

         return NULL;

     switch (token) {

      case TOK_PLUS:

       case TOK_MINUS:

       case TOK_STAR:

       case TOK_SLASH:

       case TOK_PERCENT:

       case TOK_AMPERSAND:

       case TOK_BITOR:

       case TOK_BITXOR:

       case TOK_SHR:

       case TOK_USHR:

       case TOK_SHL:

         return new (pool_) HBinary(node, left->type(), token, left, right);

       case TOK_EQUALS:

       case TOK_NOTEQUALS:

       case TOK_LT:

       case TOK_LE:

       case TOK_GT:

       case TOK_GE:

       case TOK_AND:

       case TOK_OR:

       {

         Local<Type> result(zone_, zone_->types()->getPrimitive(PrimitiveType_Bool));

         return new (pool_) HBinary(node, result, token, left, right);

       }

       default:

         assert(false);

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