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

     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_),

     fun_(fun),

     loop_(NULL),

     control_(NULL)

 {

 }

 void

 SemanticAnalysis::analyze()

 {

     scope_ = unit_->globalScope();

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

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

         stmt->accept(this);

     }

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

     if (!code)

         return;

     code->setModule(unit_->module());

     unit_->module()->setCode(code);

 #ifndef NDEBUG

 //    Disassemble(code, stdout);

 #endif

 }

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

     Local<Type> type(zone_, node->sym()->type());

     if (node->sym()->type()->isVoid()) {

         cc_.reportError(node->type()->pos(), Message_CannotDeclareVoid);

         return;

     }

     if (node->initialization()) {

         HIR *hir = NULL;

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

             return;

         if ((hir = coerce(hir, type, Coerce_Decl)) == NULL)

             return;

         discharge(hir);

     } else {

         if (type->isInt32() || type->isEnum() ||

             type->isChar() || type->isBool())

         {

             __ int_(0);

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

             __ float_(0);

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

             Local<ArrayType> atype(zone_, ArrayType::cast(type));

             Local<ArrayMap> map(zone_, atype->newMap());

             if (!map)

                 return;

             if (atype->isFixedLength()) {

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

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

                 // This may not be true if we allow typedefing, so :TODO:

                 // figure out proper semantics.

                 assert(node->dims()->length() == atype->levels());

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

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

                     Expression *expr = node->dims()->at(i);

                     if (expr) {

                         HIR *hir = eval(expr);

                         if (!hir || ((hir = coerce(hir, i32, Coerce_Arg)) == NULL))

                             return;

                         discharge(hir);

                     } else {

                         __ int_(0);

                     }

                 }

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

             } else {

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

             }

         } else {

             assert(false);

         }

     }

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

         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;

 }

 static unsigned

 BindImplicitName(Module *from, ImplicitSymbol *sym)

 {

     if (sym->bound())

         return sym->fieldIndex();

     Module *module = Module::cast(from->getImportAt(sym->index()));

     StructMap *map = module->globals()->map();

     unsigned fieldIndex;

     Descriptor *desc = map->type()->lookupField(sym->name(), &fieldIndex);

     assert(desc && desc->type() == sym->type());

     sym->bind(fieldIndex);

     return fieldIndex;

 }

 void

 SemanticAnalysis::visitNameProxy(NameProxy *proxy)

 {

     Symbol *sym = proxy->sym();

     switch (sym->kind()) {

       case Symbol::kImport:

       {

         ImportSymbol *import = sym->toImport();

         hir_ = new (pool_) HImport(proxy, sym->type(), import->index());

         break;

       }

       case Symbol::kImplicit:

       {

         ImplicitSymbol *import = sym->toImplicit();

         unsigned fieldIndex = BindImplicitName(unit_->module(), import);

         hir_ = new (pool_) HImport(proxy, zone_->types()->getImportable(), import->index());

         hir_ = new (pool_) HField(proxy, hir_, sym->type(), fieldIndex);

         break;

       }

       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::visitBooleanLiteral(BooleanLiteral *node)

 {

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

     hir_ = new (pool_) HBoolean(node, type, node->token() == TOK_TRUE);

 }

 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::visitStringLiteral(StringLiteral *node)

 {

     Type *type = zone_->types()->getString();

     hir_ = new (pool_) HString(node, type, node->string());

 }

 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() && arg->isIndex()) {

                 // If the expression is the form x[y], and this produced a

                 // normal array indexing operation, then we apply some 

                 // special rules.

                 if (actual->isReference()) {

                     // Disabled, since this doesn't have easily definable or

                     // sensible semantics with SP2 arrays, but we don't want

                     // to silently break SP1 semantics.

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

                     return;

                 }

                 // As a special rule to account for SP1 semantics, we allow x[y]

                 // to automatically compute a sliced, read-only array view if

                 // the desired type is an array of one more dimension than x[y]

                 // would return.

                 //

                 // As an additional restriction, this is only allowed for

                 // one-level char arrays, to minimize potential issues until

                 // we determine whether more compatibility is needed.

                 //

                 // Internally, for sanity, the dependent array operation does

                 // not necessarily create a dependent array. For extensible

                 // arrays, we instead create a duplicate arrary of just the

                 // sliced portion, rather than deal with the complexity of the

                 // source array being resized.

                 //

                 // Note that we don't really know whether a dependent array

                 // will be dependent at compile-time, so the dependent type's

                 // just inherits from the source.

                 if (actual->isArray()) {

                     HIndex *index = arg->toIndex();

                     Local<ArrayType> basetype(zone_, ArrayType::cast(index->base()->type()));

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

                     if (atype->isCharArray() && basetype->isCharArray()) {

                         // There is no possible way this will type check, so

                         // it's safe to just try something completely

                         // different.

                         Local<Type> slicetype(zone_);

                         if (basetype->isFixedLength()) {

                             // If the base type is fixed length, we need to

                             // compute a new dynamic array type based on the

                             // fixed array's contents and qualifiers.

                             Local<Type> contained(zone_, basetype->contained());

                             slicetype = zone_->types()->newArray(contained, ArrayType::DYNAMIC_ARRAY_SIZE);

                             if (!slicetype)

                                 return;

                             slicetype = zone_->types()->qualify(slicetype, basetype->quals());

                             if (!slicetype)

                                 return;

                         } else {

                             slicetype = basetype;

                         }

                         arg = new (pool_) HNewDependentArray(expression, slicetype, index->base(), index->index());

                         given = arg->type();

                     }

                 }

             }

             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;

     if (lval->type()->quals() & TypeQual_Const) {

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

         return;

     }

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

     if (!hir)

         return;

     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;

     }