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

 #include "Types.h"

 #include "Zone.h"

 #include "TypeManager.h"

 #include "Scopes.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;

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

     }

     return !cc_.failures();

 }

 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->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_EQUALS && token <= TOK_OR) {

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

         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)

 {

     name->setType(name->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())

     {

       default:

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

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

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

             return;

         }

         node->setType(type);

         break;

     }

 }

 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_->returnType()->isVoid())

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

         return;

     }

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

     if (!type)

         return;

     Local<Type> returnType(zone_, function_->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_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();

         }

         // Right now, any array is allowed on the LIFO heap. In case the

         // runtime actually decides to use the LIFO heap, we must reserve

         // a slot so we can unwind the heap when the current scope leaves.

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

     else

         funtype = zone_->types()->newFunction(returnType, args);

     if (!funtype)

         return false;

     // If the function already has a type, it was forward declared before, and

     // now this is our chance to type check the second declaration.

     if (node->fun()->type()) {

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

         if (!Type::Compare(funtype, forward)) {

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

             return false;

         }

         node->fun()->setForwardType(forward);

     }

     node->fun()->setType(funtype);

     return true;

 }

 void

 SemanticAnalysis::visit(FunctionStatement *node)

 {

     function_ = node->fun()->type();

     scope_ = node->scope();

     ControlScope control(&control_);

     if (node->body()) {

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

         ControlStatus status = control.status();

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

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

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

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

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

         }

     }

     scope_ = NULL;

     function_ = NULL;

 }

 bool

 SemanticAnalysis::typeCheckArrayAssignment(AstNode *node, Handle<Type> argGiven, Handle<Type> argActual, bool forAssign)

 {

     Local<Type> actual(zone_, argActual);

     Local<Type> given(zone_, argGiven);

     if (!given->isArray()) {

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

         return false;

     }

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

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

         return false;

     }

     unsigned level = 0;

     while (given->isArray()) {

         if (actual->elements() != -1) {

             if (forAssign) {

                 if (given->elements() == -1 || actual->elements() == -1) {

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

                     return false;

                 }

                 if (actual->isCharArray()) {

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

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

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

                         return false;

                     }

                 } else {

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

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

                         return false;

                     }

                 }

             } else {

                 if (actual->elements() != -1 && given->elements() != actual->elements()) {

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

                     return false;

                 }

             }

         }

         given = given->contained();

         actual = actual->contained();

     }

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

         // :TODO: leaks an interior pointer.

         const char *givenTag = given->tag() ? given->tag()->chars() : "_";

         const char *actualTag = given->tag() ? given->tag()->chars() : "_";

         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);

         return false;

     }

     return true;

 }

 bool

 SemanticAnalysis::typeCheckAssignment(AstNode *node, Handle<Type> argGiven, Handle<Type> argActual, bool forAssign)

 {

     Local<Type> actual(zone_, argActual);

     Local<Type> given(zone_, argGiven);

     if (actual->isArray())

         return typeCheckArrayAssignment(node, given, actual, forAssign);

     if (given->isArray()) {

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

         return false;

     }

     // The given type may not have been dereferenced.

     if (given->isReference())

         given = given->contained();

     if (actual->isReference())

         actual = actual->contained();

     if (!given->isPrimitive() || !actual->isPrimitive()) {

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

         return false;

     }

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

         // :TODO: leaks an interior pointer

         const char *givenTag = given->tag() ? given->tag()->chars() : "_";

         const char *actualTag = given->tag() ? given->tag()->chars() : "_";

         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);