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