/* vim: set ts=4 sw=4 tw=99 et:

  *

  * Copyright (C) 2012 David Anderson

  *

  * This file is part of JITCraft.

  *

  * JITCraft is free software: you can redistribute it and/or modify it under

  * the terms of the GNU General Public License as published by the Free

  * Software Foundation, either version 3 of the License, or (at your option)

  * any later version.

  * 

  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY

  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

  *

  * You should have received a copy of the GNU General Public License along with

  * JITCraft. If not, see http://www.gnu.org/licenses/.

  */

 #include <string.h>

 #include "SemanticAnalysis.h"

 #include "Types.h"

 #include "Zone.h"

 #include "TypeManager.h"

 #include "Scopes.h"

 #include "NameBinding.h"

 #include "Heap-inl.h"

 #include "Strings.h"

 using namespace ke;

 static inline bool

 IsPrimitiveType(Type *type, PrimitiveType primitive)

 {

     if (!type)

         return false;

     if (!type->isPrimitive())

         return false;

     return primitive == type->primitive();

 }

 static inline bool

 EvaluateBinaryOperation(TokenKind kind, const BoxedPrimitive &left, const BoxedPrimitive &right,

                         BoxedPrimitive *out)

 {

     switch (kind) {

       case TOK_PLUS:

         *out = BoxedPrimitive::Int(left.toInt() + right.toInt());

         return true;

       case TOK_SHL:

         *out = BoxedPrimitive::Int(left.toInt() << right.toInt());

         return true;

       default:

         return false;

     }

 }

 static bool

 EvaluateForConstant(Expression *expression, BoxedPrimitive *out)

 {

     switch (expression->kind()) {

       case AstNode::kBinaryExpression:

       {

         BoxedPrimitive left;

         BoxedPrimitive right;

         BinaryExpression *b = expression->toBinaryExpression();

         if (!EvaluateForConstant(b->left(), &left) ||

             !EvaluateForConstant(b->right(), &right))

         {

             return false;

         }

         return EvaluateBinaryOperation(b->token(), left, right, out);

       }

       case AstNode::kNameProxy:

       {

         NameProxy *proxy = expression->toNameProxy();

         if (proxy->binding()->kind() != BoundName::CONSTANT)

             return false;

         NamedConstant *c = proxy->binding()->toNamedConstant();

         if (!IsPrimitiveType(c->type(), PrimitiveType_Int32))

             return false;

         *out = c->value();

         return true;

       }

       case AstNode::kIntegerLiteral:

         *out = BoxedPrimitive::Int(expression->toIntegerLiteral()->value());

         return true;

       default:

         return false;

     }

 }

 SemanticAnalysis::SemanticAnalysis(Zone *zone, CompileContext &cc, ParseTree *tree)

   : zone_(zone),

     cc_(cc),

     tree_(tree),

     scope_(NULL),

     loop_(NULL)

 {

 }

 bool

 SemanticAnalysis::analyze()

 {

     if (cc_.failures())

         return false;

     scope_ = tree_->scope();

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

         Statement *statement = tree_->statements()->at(i);

         if (statement->isFunctionStatement()) {

             FunctionStatement *funstmt = statement->toFunctionStatement();

             if (!preanalyze(funstmt))

                 return false;

         }

     }

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

         Statement *statement = tree_->statements()->at(i);

         statement->accept(this);

     }

     if (!determineLiveFunctions())

         return false;

     return !cc_.failures();

 }

 bool

 SemanticAnalysis::determineLiveFunctions()

 {

     Vector<NamedFunction *> worklist;

     // Add the root set.

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

         Statement *statement = tree_->statements()->at(i);

         if (!statement->isFunctionStatement())

             continue;

         FunctionStatement *stmt = statement->toFunctionStatement();

         NamedFunction  *fun = stmt->fun();

         if (!fun->used())

             continue;

         for (size_t i = 0; i < fun->usedGlobals()->length(); i++) {

             NamedFunction *name = fun->usedGlobals()->at(i)->toNamedFunction();

             // Names in these lists are always unused, however, we mark them

             // as used while inserting into the work queue, to avoid double-

             // insertion.

             if (name->used())

                 continue;

             if (!worklist.append(name))

                 return false;

             name->setUsed();

         }

     }

     while (!worklist.empty()) {

         NamedFunction *fun = worklist.popCopy();

         for (size_t i = 0; i < fun->usedGlobals()->length(); i++) {

             NamedFunction *name = fun->usedGlobals()->at(i)->toNamedFunction();

             if (name->used())

                 continue;

             if (!worklist.append(name))

                 return false;

             name->setUsed();

         }

     }

     return true;

 }

 Type *

 SemanticAnalysis::visitAndApplyType(Expression *expression)

 {

     expression->accept(this);

     return expression->type();

 }

 Type *

 SemanticAnalysis::visitForLoad(Expression *expression)

 {

     Local<Type> type(zone_, visitAndApplyType(expression));

     if (!type)

         return NULL;

     if (type->isReference()) {

         expression->setType(type->contained());

     } else if (expression->isIndexExpression()) {

         if (type->isArray())

             expression->setType(type->contained());

     } else if (expression->isCallExpression()) {

         if (type->isVoid()) {

             CallExpression *call = expression->toCallExpression();

             cc_.reportError(call->callee()->pos(), Message_FunctionDoesNotReturnValue);

             return NULL;

         }

     }

     return expression->type();

 }

 // :TODO: this leaks an interior pointer.

 static inline const char *

 GetTypeName(Type *type)

 {

     if (type->isArray())

         return "array";

     if (type->isFunction())

         return "function";

     if (type->isVoid())

         return "void";

     if (type->isReference())

         type = type->contained();

     if (type->tag())

         return type->tag()->chars();

     return "int";

 }

 void

 SemanticAnalysis::unaryTypeError(AstNode *node, TokenKind token, Handle<Type> type)

 {

     const char *op = TokenNames[token];

     const char *name = GetTypeName(type);

     cc_.reportError(node->pos(), Message_UnaryTypeError, op, name);

 }

 void

 SemanticAnalysis::binaryTypeError(AstNode *node, TokenKind token, Handle<Type> left, Handle<Type> right)

 {

     const char *op = TokenNames[token];

     const char *leftName = GetTypeName(left);

     const char *rightName = GetTypeName(right);

     cc_.reportError(node->pos(), Message_BinaryTypeError, op, leftName, rightName);

 }

 Type *

 SemanticAnalysis::typeCheckBinary(AstNode *node, TokenKind token, Handle<Type> left, Handle<Type> right)

 {

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

         (token >= TOK_ASSIGN_ADD && token <= TOK_ASSIGN_DIV))

     {

         // If either side is a float, the other side must be a float or int.

         if (left->isFloat() || right->isFloat()) {

             Type *floatType = left->isFloat() ? left : right;

             Type *other = left->isFloat() ? right : left;

             if (other->isFloat() || (other->isInt32() && !other->tag()))

                 return floatType;

         }

     }

     if (token == TOK_OR || token == TOK_AND) {

         if (!canTest(node, left) || !canTest(node, right))

             return NULL;

         return zone_->types()->getPrimitive(PrimitiveType_Int32);

     }

     if (token >= TOK_EQUALS && token <= TOK_GE) {

         if ((left->isFloat() || (left->isInt32() && !left->tag())) &&

             (right->isFloat() || (right->isInt32() && !right->tag())))

         {

             return zone_->types()->getPrimitive(PrimitiveType_Int32);

         }

         binaryTypeError(node, token, left, right);

         return NULL;

     }

     if ((!left->isInt32() || left->tag()) ||

         (!right->isInt32() || right->tag()))

     {

         binaryTypeError(node, token, left, right);

         return NULL;

     }

     return left;

 }

 bool

 SemanticAnalysis::canTest(AstNode *node, Handle<Type> type)

 {

     if (type->isArray() || (type->isInt32() && type->tag())) {

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

         return false;

     }

     return true;

 }

 Type *

 SemanticAnalysis::visitForLValue(Expression *expression)

 {

     if (expression->isIndexExpression()) {

         Type *type = visitAndApplyType(expression);

         if (!type)

             return NULL;

         if (type->isConst()) {

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

             return NULL;

         }

         return type->contained();

     }

     if (!expression->isNameProxy()) {

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

         return NULL;

     }

     NameProxy *proxy = expression->toNameProxy();

     if (!proxy->binding()->kind() == BoundName::VARIABLE) {

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

         return NULL;

     }

     Variable *var = proxy->binding()->toVariable();

     if (!var->type())

         return NULL;

     if  (var->type()->isReference()) {

         if (var->type()->isConst()) {

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

             return NULL;

         }

         return var->type()->contained();

     }

     return var->type();

 }

 SemanticAnalysis::ControlStatus

 SemanticAnalysis::visitForControl(Statement *statement)

 {

     ControlScope scope(&control_);

     statement->accept(this);

     return scope.status();

 }

 void

 SemanticAnalysis::visit(NameProxy *name)

 {

     BoundName *binding = name->binding();

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

         if (!function_ || function_->isPublic()) {

             // Whatever we're referencing must be kept alive no matter what.

             // As such, we simply mark it used, and don't do anything special.

             binding->setUsed();

         } else if (!binding->used() && binding->kind() == BoundName::FUNCTION) {

             // Otherwise, we're inside a normal stock or function. Since we

             // don't really know if we've been used yet, we shouldn't

             // prematurely references as alive. Instead, we keep a list of

             // which names have been used, so we can mark them later if needed.

             //

             // Note that we skip this step if the binding is already in the

             // root set.

             if (!function_->addUsedGlobal(binding))

                 return;

         }

     }

     name->setType(binding->type());

 }

 void

 SemanticAnalysis::visit(Assignment *node)

 {

     Local<Type> exprType(zone_, visitForLoad(node->expression()));

     if (!exprType)

         return ;

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

     if (!type)

         return;

     if (node->token() != TOK_ASSIGN) {

         if (!typeCheckBinary(node, node->token(), type, exprType))

             return;

     }

     if (!typeCheckAssignment(node, exprType, type, true))

         return;

     node->setType(type);

 }

 void

 SemanticAnalysis::visit(IncDecExpression *node)

 {

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

     if (!type)

         return;

     assert(!type->isReference());

     if ((!type->isInt32() || (type->isInt32() && type->tag())) && !type->isFloat()) {

         unaryTypeError(node, node->token(), type);

         return;

     }

     node->setType(type);

 }

 void

 SemanticAnalysis::visit(UnaryExpression *node)

 {

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

     if (!type)

         return;

     switch (node->token())

     {

       case TOK_NOT:

         if (!canTest(node->expression(), type))

             return;

         type = zone_->types()->getPrimitive(PrimitiveType_Int32);

         if (!type)

             return;

         node->setType(type);

         break;

       case TOK_MINUS:

         if (!type->isFloat() && (!type->isInt32() || type->tag())) {

             unaryTypeError(node, node->token(), type);

             return;

         }

         node->setType(type);

         break;

       case TOK_LABEL:

       {

         Local<String> tag(zone_, node->tag());

         Local<Type> to(zone_, zone_->types()->getPrimitiveForTag(tag));

         if (!to)

             return;

         if ((!type->isFloat() && !type->isInt32()) ||

             (!to->isFloat() && !to->isInt32()))

         {

             unaryTypeError(node, node->token(), type);

             return;

         }

         node->setType(to);

         break;

       }

       default:

         assert(node->token() == TOK_TILDE);

         if (!type->isInt32() || type->tag()) {

             unaryTypeError(node, node->token(), type);

             return;

         }

         node->setType(type);

         break;

     }

 }

 void

 SemanticAnalysis::visit(TernaryExpression *node)

 {

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

     if (!type)

         return;

     if (!canTest(node->condition(), type))

         return;

     Local<Type> left(zone_, visitForLoad(node->left()));

     Local<Type> right(zone_, visitForLoad(node->right()));

     if (!left || !right)

         return;

     if (left != right) {

         binaryTypeError(node, TOK_QMARK, left, right);

         return;

     }

 }

 void

 SemanticAnalysis::visit(BinaryExpression *node)

 {

     Local<Type> left(zone_, visitForLoad(node->left()));

     Local<Type> right(zone_, visitForLoad(node->right()));

     if (!left || !right)

         return;

     Local<Type> result(zone_, typeCheckBinary(node, node->token(), left, right));

     if (!result)

         return;

     node->setType(result);

 }

 void

 SemanticAnalysis::visit(ReturnStatement *node)

 {

     // Set this early, so if we error we don't get more errors.

     control_->returns(Returns_Always);

     if (!node->expression()) {

         if (!function_->type()->returnType()->isVoid())

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

         return;

     }

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

     if (!type)

         return;

     Local<Type> returnType(zone_, function_->type()->returnType());

     if (!typeCheckAssignment(node, type, returnType, true))

         return;

 }

 void

 SemanticAnalysis::visit(ForStatement *node)

 {

     LoopScope loop(&loop_);

     if (node->scope())

         scope_ = node->scope();

     if (node->initialization())

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

     if (node->condition()) {

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

         if (!type || !canTest(node->condition(), type)) {

             return;

         }

     }

     if (node->update())

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

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

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

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

     if (node->scope())

         scope_ = scope_->enclosing();

 }

 void 

 SemanticAnalysis::visit(WhileStatement *node)

 {

     LoopScope loop(&loop_);

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

     if (!type || !canTest(node->condition(), type)) {

         return;

     }

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

     // Detect loops that will always have a fork in the control-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());

     }

 }

 void

 SemanticAnalysis::visit(BlockStatement *node)

 {

     if (node->scope())

         scope_ = node->scope();

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

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

         statement->accept(this);

     }

     if (node->scope())

         scope_ = scope_->enclosing();

 }

 void

 SemanticAnalysis::visit(VariableDeclaration *node)

 {

     Local<String> tag(zone_, node->tag());

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

     if (!type)

         return;

     if (node->postDimensions()) {

         Local<Type> init(zone_);

         if (node->initialization()) {

             if ((init = visitForLoad(node->initialization())) == NULL)

                 return;

         }

         if (node->postDimensions()->length() > Type::MAX_UNSAFE_ARRAY_DEPTH) {

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

             return;

         }

         // If we have an initializer, make sure it's the same type.

         if (init && node->postDimensions()->length() != init->levels()) {

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

             return;

         }

         Local<Type> check(zone_, init);

         for (size_t i = node->postDimensions()->length() - 1; i < node->postDimensions()->length(); i--) {

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

             int size = -1;

             if (expr) {

                 Local<Type> exprType(zone_, visitForLoad(expr));

                 if (!exprType)

                     return;

                 if (!IsPrimitiveType(exprType, PrimitiveType_Int32)) {

                     cc_.reportError(expr->pos(), Message_ArrayDimensionNotInteger);

                     return;

                 }

                 BoxedPrimitive box;

                 if (EvaluateForConstant(expr, &box) && box.type() == PrimitiveType_Int32) {

                     size = box.toInt();

                     if (size <= 0) {

                         cc_.reportError(expr->pos(), Message_BadArraySize);

                         return;

                     }

                     if (size >= int(INT_MAX / sizeof(int))) {

                         cc_.reportError(expr->pos(), Message_ArraySizeTooBig);

                         return;

                     }

                     if (check) {

                         if (check->elements() == -1) {

                             cc_.reportError(expr->pos(), Message_ArraySizeCannotBeDetermined);

                             return;

                         }

                         if (check->isCharArray()) {

                             if (check->elements() > size) {

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

                                 return;

                             }

                         } else if (check->elements() != size) {

                             cc_.reportError(node->pos(), Message_ArrayDimensionSizeMismatch, unsigned(i));

                             return;

                         }

                     }

                 } else {

                     if (init) {

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

                         return;

                     }

                     // here until we get dynamic array support.

                     cc_.reportError(expr->pos(), Message_ArrayDimensionNotInteger);

                     return;

                 }

             } else {

                 // Infer the size from the initializer.

                 if (!init) {

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

                     return;

                 }

                 if (init->elements() == -1) {

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

                     return;

                 }

                 size = init->elements();

             }

             type = zone_->types()->unsafeArray(type, size, false);

             if (!type)

                 return;

             if (check)

                 check = check->contained();

         }

         // If this variable is stack allocated, we could use the LIFO heap

         // to allocate it. If that's the case, make sure to reserve a slot

         // so we can unwind the LIFO heap at the end of this scope.

         if (!node->variable()->needsHeapAllocation())

             scope_->setUsesLifoHeap();

     } else {

         if (node->initialization()) {

             Local<Type> right(zone_, visitForLoad(node->initialization()));

             if (!right)

                 return;

             if (!typeCheckAssignment(node, type, right, true))

                 return;

         }

         if (type->primitive() == PrimitiveType_Char) {

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

             return;

         }

     }

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

 }

 void

 SemanticAnalysis::visit(IntegerLiteral *node)

 {

     node->setType(zone_->types()->getPrimitive(PrimitiveType_Int32));

 }

 void

 SemanticAnalysis::visit(BooleanLiteral *node)

 {

     node->setType(zone_->types()->getPrimitive(PrimitiveType_Bool));

 }

 void

 SemanticAnalysis::visit(ExpressionStatement *node)

 {

     visitAndApplyType(node->expression());

 }

 bool

 SemanticAnalysis::preanalyze(FunctionStatement *node)

 {

     Local<FixedArray> args(zone_, FixedArray::New(zone_, node->parameters()->length(), Heap::Tenure_Old));

     if (!args)

         return false;

     // Apply types to arguments.

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

         Parameter *parameter = node->parameters()->at(i);

         Local<String> tag(zone_, parameter->tag());

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

         if (!type)

             return false;

         if (parameter->reference()) {

             if (parameter->dimensions()) {

                 cc_.reportError(parameter->variable()->pos(), Message_ArrayCantBeReference);

                 return NULL;

             }

             type = zone_->types()->getReference(type, parameter->isConst());

             if (!type)

                 return false;

         } else if (parameter->dimensions()) {

             if (parameter->dimensions()->length() > Type::MAX_UNSAFE_ARRAY_DEPTH) {

                 cc_.reportError(parameter->variable()->pos(), Message_MaximumArrayDepth);

                 return false;

             }

             if (node->fun()->isNative() && parameter->dimensions()->length() > 1) {

                 cc_.reportError(parameter->variable()->pos(), Message_MultiArrayInNative);

                 return false;

             }

             for (size_t i = parameter->dimensions()->length() - 1;

                  i < parameter->dimensions()->length();

                  i++)

             {

                 int size = Type::UNKNOWN_SIZE;

                 if (Expression *expr = parameter->dimensions()->at(i)) {

                     BoxedPrimitive box;

                     if (!EvaluateForConstant(expr, &box)) {

                         cc_.reportError(expr->pos(), Message_ArraySizeMustBeConstant);

                         return false;

                     }

                     size = box.toInt();

                 }

                 type = zone_->types()->unsafeArray(type, size, parameter->isConst());

                 if (!type)

                     return false;

             }

         }

         if ((type->isPrimitive() && type->primitive() == PrimitiveType_Char) ||

             (type->isReference() && type->contained()->primitive() == PrimitiveType_Char))

         {

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

             return false;

         }

         args->set(zone_, i, type);

         parameter->variable()->setType(type);

     }

     Local<Type> returnType(zone_);

     if (node->returnTag()) {

         Local<String> tag(zone_, node->returnTag());

         returnType = zone_->types()->getPrimitiveForTag(tag);

     } else if (node->hasExplicitReturn() || node->fun()->isNative()) {

         returnType = zone_->types()->getPrimitive(PrimitiveType_Int32);

     } else {

         returnType = zone_->types()->getVoid();

     }

     if (!returnType)

         return false;

     Local<Type> funtype(zone_);

     if (node->fun()->isNative())

         funtype = zone_->types()->newNative(returnType, args, node->fun()->isNativeVariadic());