/* 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),

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

     ControlStatus status = visitForControl(stmt->body());

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

         // If the function is not void, report if not all paths return a value.

         // All other incorrect return cases have been caught already.

         if (status.returns() == Returns_Sometimes) {

             cc_.reportError(stmt->pos(), Message_NotAllPathsReturnValue);

             return NULL;

         }

         if (status.returns() == Returns_Never) {

             cc_.reportError(stmt->pos(), Message_MissingReturnValue);

             return NULL;

         }

     }

     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::visitEnumStatement(EnumStatement *node)

 {

 }

 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::ControlScope::merge(const ControlStatus &left, const ControlStatus &right)

 {

     // If both sides terminate in a return, we consider this a return as well.

     if (left.returns() == Returns_Always && right.returns() == Returns_Always) {

         terminate(Returns_Always);

         return;

     }

     ReturnStatus status = (left.returns() == Returns_Never && right.returns() == Returns_Never)

                           ? Returns_Never

                           : Returns_Sometimes;

     if (left.terminates() && right.terminates())

         terminate(status);

     else

         returns(status);

 }

 SemanticAnalysis::ControlStatus

 SemanticAnalysis::visitForControl(Statement *statement)

 {

     ControlScope scope(&control_);

     statement->accept(this);

     return scope.status();

 }

 void

 SemanticAnalysis::visitIfStatement(IfStatement *node)

 {

     Label join;

     ControlStatus trueBranch;

     ControlStatus falseBranch(false, Returns_Never);

     if (!node->ifFalse()) {

         Label success;

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

         __ bind(&success);

         trueBranch = visitForControl(node->ifTrue());

     } else {

         Label success, next;

         visitForTest(node->condition(), &success, &next, &success);

         __ bind(&success);

         trueBranch = visitForControl(node->ifTrue());

         __ jump(&join);

         __ bind(&next);

         falseBranch = visitForControl(node->ifFalse());

     }

     __ bind(&join);

     control_->merge(trueBranch, falseBranch);

 }

 void

 SemanticAnalysis::requireLifoStack()

 {

     if (!loop_)

         return;

     loop_->setUsesLifoStack();

 }

 SemanticAnalysis::ControlStatus

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

     ControlStatus status = visitForControl(stmt);

     __ leaveloop();

     if (loop_->usesLifoStack())

         __ setLoopUsesLifoStack(pos);

     return status;

 }

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

     ControlStatus status = 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);

     // If there was a condition, we treat this like a while loop. Otherwise,

     // the join point is only reachable if the loop contains a break. The

     // termination status doesn't tell us anything yet.

     if (node->condition() || loop.breaks())

         control_->merge(status, ControlStatus(false, Returns_Never));

     else

         control_->terminate(status.returns());

     assert(__ stackDepth() == 0);

 }

 void

 SemanticAnalysis::visitWhileStatement(WhileStatement *node)

 {

     PoolScope poolScope(zone_->pool());

     RootScope rootScope(zone_);

     Label header, join;

     __ bind(&header);

     ControlStatus status;

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

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

         Label body;

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

         status = visitLoopBody(node->body());

         __ jump(&header);

     } else {

         status = visitLoopBody(node->body());

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

     }

     __ bind(&join);

     // Detect loops that will always have a fork in the contro-flow graph.

     // This will be a |while| loop, or a |do-while| loop whose body does

     // not terminate. For now, we treat these as an |if| regardless of the

     // direction the branch can take. That means the control-flow is always

     // conditional.

     if (node->token() == TOK_WHILE || status.terminates() || loop.breaks()) {

         control_->merge(status, ControlStatus(false, Returns_Never));

     } else {

         // At this point, we've got a do-while loop with a |return| or

         // |continue|, meaning that the rest of the block is unreachable.

         control_->terminate(status.returns());

     }

     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)

 {

     control_->returns(Returns_Always);

     if (!node->expression()) {

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

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

             return;

         }

         __ returnvoid();

         return;

     }

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

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

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

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

         __ returnvoid();

     else

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

     switch (sym->kind()) {

       case Symbol::kConstant:

       {

         ConstantSymbol *val = sym->toConstant();

         hir_ = new (pool_) HInteger(proxy, sym->type(), val->value().toInt());

         break;

       }

       // This is kind of screwy. Symbol::kFunction is like a constant we can't

       // evaluate yet. Maybe we should extract the GLOBAL case and say that

       // kFunction is only used for global functions (and use const vars for

       // local functions).

       case Symbol::kFunction:

       case Symbol::kVariable:

       {

         Scope *in = sym->scope();

         switch (in->kind()) {

           case Scope::GLOBAL:

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

             break;

           case Scope::FUNCTION:

           {

             VariableSymbol *var = sym->toVariable();

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

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

             break;

           }

           default:

           {

             VariableSymbol *var = sym->toVariable();

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

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

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

             break;

           }

         }

         break;

       }

       default:

         // :TODO:

         assert(false);

     }

 }

 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;

     }

     loop_->setBreaks();

     __ 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.