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

#include "../Box.h"

#include "../Array.h"

#include "../Heap-inl.h"

#include "Scopes.h"

#include "NameBinding.h"

using namespace ke;

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

  : zone_(zone),

    cc_(cc),

    tree_(tree),

    scope_(NULL),

    loop_(NULL)

{

}

bool

SemanticAnalysis::analyze()

{

    assert(false);

    return false;

}

#if 0

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 inline bool

EvaluateUnaryOperation(TokenKind kind, const BoxedPrimitive &inner, BoxedPrimitive *out)

{

  switch (kind) {

    case TOK_MINUS:

      *out = BoxedPrimitive::Int(-inner.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::kUnaryExpression:

      {

        BoxedPrimitive inner;

        UnaryExpression *u = expression->toUnaryExpression();

        if (!EvaluateForConstant(u->expression(), &inner))

            return false;

        return EvaluateUnaryOperation(u->token(), inner, 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::kBooleanLiteral:

        *out = BoxedPrimitive::Int(expression->toBooleanLiteral()->token() == TOK_TRUE ? 1 : 0);

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

    assert(scope_->kind() == Scope::GLOBAL);

    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;

        } else if (statement->isEnumStatement()) {

            EnumStatement *enumstmt = statement->toEnumStatement();

            // We pre-fill global enum types, since they may occur in function

            // signatures. This should probably be somewhere else...

            enumstmt->accept(this);

        } else if (statement->isStructureStatement()) {

            StructureStatement *node = statement->toStructureStatement();

            node->accept(this);

            if (!node->decl()->type())

                return false;

        } else if (statement->isFunctionTypeStatement()) {

            FunctionTypeStatement *node = statement->toFunctionTypeStatement();

            node->accept(this);

            if (!node->decl()->type())

                return false;

        }

    }

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

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

        // We can't double-process these. Maybe put this check somewhere else.

        if (statement->isEnumStatement())

            continue;

        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::bindType(const SourcePosition &pos, BoundName *name)

{

    if (!name)

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

    if (name->kind() == BoundName::UNBOUND) {

        cc_.reportError(pos, Message_TypeNotFound, name->name()->chars());

        return NULL;

    }

    if (name->kind() != BoundName::TYPE) {

        cc_.reportError(pos, Message_IdentifierIsNotAType, name->name()->chars());

        return NULL;

    }

    if (!name->type())

        return NULL;

    return name->type();

}

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

        if (type->isVoid()) {

            CallExpression *call = expression->toCallExpression();

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

            return NULL;

        }

    }

    return expression->type();

}

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

                return floatType;

        }

    }

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

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

            return NULL;

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

    }

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

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

            (right->isFloat() || right->isInt32()))

        {

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

        }

        binaryTypeError(node, token, left, right);

        return NULL;

    }

    if (!left->isInt32() || !right->isInt32()) {

        binaryTypeError(node, token, left, right);

        return NULL;

    }

    return left;

}

bool

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

{

    if (!type->isPrimitive() && !type->isEnum()) {

        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;

    }

    if (expression->isFieldExpression()) {

        Type *type = visitAndApplyType(expression);

        if (!type)

            return NULL;

        // if (expression->toFieldExpression()->left()->type()->isConst()) {

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

        //     return NULL;

        // }

        return type;

    }

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

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

            return;

        }

        node->setType(type);

        break;

      case TOK_LABEL:

      {

        Local<Type> to(zone_, bindType(node->pos(), node->type()));

        if (!to)

            return;

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

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

        {

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

            return;

        }

        node->setType(to);

        break;

      }

      case TOK_SIZEOF:

      {

        if (!type->isArray()) {

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

            return;

        }

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

        break;

      }

      default:

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

        if (!type->isInt32()) {

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

}

static inline bool

IsScalarString(Type *type)

{

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

        return true;

    if (type->isReference())

        return IsScalarString(type->contained());

    return false;

}

static const int INFER_ARRAY_SIZE = 0;

static const int EVAL_ARRAY_SIZE = -1;

static const int DYNAMIC_ARRAY_SIZE = -2;

bool

SemanticAnalysis::evaluateDimensions(ExpressionList *exprs, int dims[MAX_ARRAY_DEPTH])

{

    bool hadEmptySize = false;

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

        Expression *expr = exprs->at(i);

        if (!expr) {

            dims[i] = INFER_ARRAY_SIZE;

            hadEmptySize = true;

            continue;

        }

        BoxedPrimitive box;

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

            int size = box.toInt();

            if (size <= 0) {

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

                return false;

            }

            dims[i] = size;

            continue;

        }

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

        if (!exprType)

            return false;

        if (!IsPrimitiveType(exprType, PrimitiveType_Int32)) {

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

            return false;

        }

        if (hadEmptySize) {

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

            return false;

        }

        dims[i] = EVAL_ARRAY_SIZE;

    }

    return true;

}

bool

SemanticAnalysis::inferFixedArrayLiteral(ArrayLiteral *literal, Handle<Type> contained,

                                         int dims[MAX_ARRAY_DEPTH],

                                         unsigned dimcount, unsigned level)

{

    if (dims[level] == EVAL_ARRAY_SIZE) {

        cc_.reportError(literal->pos(), Message_CannotInitializeEvalArray);

        return false;

    }

    if (dims[level] == INFER_ARRAY_SIZE) {

        // Strings always become dynamic arrays.

        if (level != dimcount - 1 || !IsPrimitiveType(contained, PrimitiveType_Char))

            dims[level] = literal->expressions()->length();

    } else if (dims[level] == DYNAMIC_ARRAY_SIZE) {

        cc_.reportError(literal->pos(), Message_CannotInitializeEvalArray);

        return false;

    } else {

        if (literal->expressions()->length() != unsigned(dims[level])) {

            cc_.reportError(literal->pos(), Message_ArrayDimensionSizeMismatch, level + 1);

            return false;

        }

    }

    if (level == dimcount - 2 && IsPrimitiveType(contained, PrimitiveType_Char)) {

        for (size_t i = 0; i < literal->expressions()->length(); i++) {

            Expression *expr = literal->expressions()->at(i);

            if (!expr->isStringLiteral()) {

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

                return false;

            }

            StringLiteral *lit = expr->toStringLiteral();

            if (dims[level + 1] > 0 &&

                unsigned(dims[level]) < lit->string()->length())

            {

                cc_.reportError(lit->pos(), Message_ArrayDimensionSizeMismatch, level + 2);

                return false;

            }

            if (!visitAndApplyType(lit))

                return false;

        }

    } else if (level == dimcount - 1) {

        Local<Type> type(zone_);

        for (size_t i = 0; i < literal->expressions()->length(); i++) {

            Expression *expr = literal->expressions()->at(i);

            if (expr->isArrayLiteral()) {

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

                return false;

            }

            if ((type = visitAndApplyType(expr)) == NULL)

                return false;

            if (!typeCheckAssignment(expr->pos(), type, contained, true))

                return false;

        }

    } else {

        for (size_t i = 0; i < literal->expressions()->length(); i++) {

            Expression *expr = literal->expressions()->at(i);

            if (!expr->isArrayLiteral()) {

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

                return false;

            }

            assert(expr->toArrayLiteral()->isFixed());

            if (!inferFixedArrayLiteral(expr->toArrayLiteral(),

                                        contained,

                                        dims,

                                        dimcount,

                                        level + 1))

            {

                return false;

            }

        }

    }

    return true;

}

void

SemanticAnalysis::visit(VariableDeclaration *node)

{

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

    if (!type)

        return;

#if 0

    if (node->postDimensions() || type->isArray()) {

        // The type could be an array type, so sum the type and postDimensions

        // together.

        unsigned dimcount = node->postDimensions()->length();

        if (type->isArray())

            dimcount += type->levels();

        if (dimcount > MAX_ARRAY_DEPTH) {

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

            return;

        }

        // Take an initial guess at the array dimension sizes.

        int dims[MAX_ARRAY_DEPTH];

        if (!evaluateDimensions(node->postDimensions(), dims))

            return;

        // Now add in the type's array dimensions.

        Local<Type> contained(zone_, type);

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

            if (type->isFixedLength())

                dims[i] = type->fixedLength();

            else

                dims[i] = DYNAMIC_ARRAY_SIZE;

            contained = contained->contained();

        }

        Expression *initializer = node->initialization();

        if (initializer &&

            initializer->isArrayLiteral() &&

            initializer->toArrayLiteral()->isFixed())

        {

            // Fixed array initializers are special; we use them to infer any

            // missing information in the original array. We do not evaluate

            // the array initializer as an expression.

            if (!inferFixedArrayLiteral(initializer->toArrayLiteral(),

                                        contained,

                                        dims,

                                        dimcount,

                                        0))

            {

                return;

            }

            initializer = NULL;

        }