dvander@30: /* vim: set ts=4 sw=4 tw=99 et:
dvander@30:  *
dvander@0:  * Copyright (C) 2012 David Anderson
dvander@0:  *
dvander@0:  * This file is part of JITCraft.
dvander@0:  *
dvander@0:  * JITCraft is free software: you can redistribute it and/or modify it under
dvander@0:  * the terms of the GNU General Public License as published by the Free
dvander@0:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@0:  * any later version.
dvander@0:  * 
dvander@0:  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@0:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@0:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@0:  *
dvander@0:  * You should have received a copy of the GNU General Public License along with
dvander@0:  * JITCraft. If not, see http://www.gnu.org/licenses/.
dvander@0:  */
dvander@0: #include "SemanticAnalysis.h"
dvander@0: #include "Types.h"
dvander@11: #include "Zone.h"
dvander@11: #include "TypeManager.h"
dvander@12: #include "Scopes.h"
dvander@85: #include "NameBinding.h"
dvander@28: #include "Heap-inl.h"
dvander@54: #include "Strings.h"
dvander@0: 
dvander@59: using namespace ke;
dvander@0: 
dvander@2: static inline bool
dvander@2: IsPrimitiveType(Type *type, PrimitiveType primitive)
dvander@2: {
dvander@2:     if (!type)
dvander@2:         return false;
dvander@2: 
dvander@2:     if (!type->isPrimitive())
dvander@2:         return false;
dvander@2: 
dvander@2:     return primitive == type->primitive();
dvander@2: }
dvander@2: 
dvander@2: static inline bool
dvander@2: EvaluateBinaryOperation(TokenKind kind, const BoxedPrimitive &left, const BoxedPrimitive &right,
dvander@2:                         BoxedPrimitive *out)
dvander@2: {
dvander@2:     switch (kind) {
dvander@2:       case TOK_PLUS:
dvander@2:         *out = BoxedPrimitive::Int(left.toInt() + right.toInt());
dvander@2:         return true;
dvander@2: 
dvander@2:       case TOK_SHL:
dvander@2:         *out = BoxedPrimitive::Int(left.toInt() << right.toInt());
dvander@2:         return true;
dvander@28: 
dvander@28:       default:
dvander@47:         return false;
dvander@2:     }
dvander@2: }
dvander@2: 
dvander@2: static bool
dvander@2: EvaluateForConstant(Expression *expression, BoxedPrimitive *out)
dvander@2: {
dvander@2:     switch (expression->kind()) {
dvander@2:       case AstNode::kBinaryExpression:
dvander@2:       {
dvander@2:         BoxedPrimitive left;
dvander@2:         BoxedPrimitive right;
dvander@2:         BinaryExpression *b = expression->toBinaryExpression();
dvander@2:         if (!EvaluateForConstant(b->left(), &left) ||
dvander@2:             !EvaluateForConstant(b->right(), &right))
dvander@2:         {
dvander@2:             return false;
dvander@2:         }
dvander@2:         return EvaluateBinaryOperation(b->token(), left, right, out);
dvander@2:       }
dvander@2: 
dvander@2:       case AstNode::kNameProxy:
dvander@2:       {
dvander@2:         NameProxy *proxy = expression->toNameProxy();
dvander@2:         if (proxy->binding()->kind() != BoundName::CONSTANT)
dvander@2:             return false;
dvander@2: 
dvander@2:         NamedConstant *c = proxy->binding()->toNamedConstant();
dvander@2:         if (!IsPrimitiveType(c->type(), PrimitiveType_Int32))
dvander@2:             return false;
dvander@2: 
dvander@2:         *out = c->value();
dvander@2:         return true;
dvander@2:       }
dvander@2: 
dvander@4:       case AstNode::kIntegerLiteral:
dvander@4:         *out = BoxedPrimitive::Int(expression->toIntegerLiteral()->value());
dvander@2:         return true;
dvander@2: 
dvander@2:       default:
dvander@2:         return false;
dvander@2:     }
dvander@2: }
dvander@2: 
dvander@30: SemanticAnalysis::SemanticAnalysis(Zone *zone, CompileContext &cc, ParseTree *tree)
dvander@30:   : zone_(zone),
dvander@30:     cc_(cc),
dvander@25:     tree_(tree),
dvander@71:     scope_(NULL),
dvander@71:     loop_(NULL)
dvander@0: {
dvander@0: }
dvander@0: 
dvander@0: bool
dvander@0: SemanticAnalysis::analyze()
dvander@0: {
dvander@25:     if (cc_.failures())
dvander@25:         return false;
dvander@25: 
dvander@85:     scope_ = tree_->scope();
dvander@85: 
dvander@25:     for (size_t i = 0; i < tree_->statements()->length(); i++) {
dvander@25:         Statement *statement = tree_->statements()->at(i);
dvander@25:         if (statement->isFunctionStatement()) {
dvander@25:             FunctionStatement *funstmt = statement->toFunctionStatement();
dvander@25:             if (!preanalyze(funstmt))
dvander@25:                 return false;
dvander@25:         }
dvander@25:     }
dvander@25: 
dvander@0:     for (size_t i = 0; i < tree_->statements()->length(); i++) {
dvander@0:         Statement *statement = tree_->statements()->at(i);
dvander@0:         statement->accept(this);
dvander@0:     }
dvander@0: 
dvander@25:     return !cc_.failures();
dvander@0: }
dvander@0: 
dvander@25: Type *
dvander@25: SemanticAnalysis::visitAndApplyType(Expression *expression)
dvander@0: {
dvander@25:     expression->accept(this);
dvander@25:     return expression->type();
dvander@0: }
dvander@0: 
dvander@7: Type *
dvander@7: SemanticAnalysis::visitForLoad(Expression *expression)
dvander@7: {
dvander@40:     Local<Type> type(zone_, visitAndApplyType(expression));
dvander@25:     if (!type)
dvander@21:         return NULL;
dvander@21: 
dvander@21:     if (type->isReference()) {
dvander@21:         expression->setType(type->contained());
dvander@21:     } else if (expression->isIndexExpression()) {
dvander@21:         if (type->isArray())
dvander@14:             expression->setType(type->contained());
dvander@71:     } else if (expression->isCallExpression()) {
dvander@71:         if (type->isVoid()) {
dvander@71:             CallExpression *call = expression->toCallExpression();
dvander@71:             cc_.reportError(call->callee()->pos(), Message_FunctionDoesNotReturnValue);
dvander@71:             return NULL;
dvander@71:         }
dvander@14:     }
dvander@25: 
dvander@7:     return expression->type();
dvander@7: }
dvander@7: 
dvander@54: // :TODO: this leaks an interior pointer.
dvander@25: static inline const char *
dvander@25: GetTypeName(Type *type)
dvander@4: {
dvander@25:     if (type->isArray())
dvander@25:         return "array";
dvander@25:     if (type->isFunction())
dvander@25:         return "function";
dvander@25:     if (type->isReference())
dvander@25:         type = type->contained();
dvander@25:     if (type->tag())
dvander@54:         return type->tag()->chars();
dvander@25:     return "int";
dvander@4: }
dvander@4: 
dvander@25: void
dvander@40: SemanticAnalysis::unaryTypeError(AstNode *node, TokenKind token, Handle<Type> type)
dvander@21: {
dvander@25:     const char *op = TokenNames[token];
dvander@25:     const char *name = GetTypeName(type);
dvander@21: 
dvander@25:     cc_.reportError(node->pos(), Message_UnaryTypeError, op, name);
dvander@21: }
dvander@21: 
dvander@25: void
dvander@40: SemanticAnalysis::binaryTypeError(AstNode *node, TokenKind token, Handle<Type> left, Handle<Type> right)
dvander@22: {
dvander@25:     const char *op = TokenNames[token];
dvander@25:     const char *leftName = GetTypeName(left);
dvander@25:     const char *rightName = GetTypeName(right);
dvander@22: 
dvander@25:     cc_.reportError(node->pos(), Message_BinaryTypeError, op, leftName, rightName);
dvander@25: }
dvander@25: 
dvander@25: Type *
dvander@40: SemanticAnalysis::typeCheckBinary(AstNode *node, TokenKind token, Handle<Type> left, Handle<Type> right)
dvander@25: {
dvander@22:     if ((token >= TOK_PLUS && token <= TOK_SLASH) ||
dvander@22:         (token >= TOK_ASSIGN_ADD && token <= TOK_ASSIGN_DIV))
dvander@22:     {
dvander@22:         // If either side is a float, the other side must be a float or int.
dvander@22:         if (left->isFloat() || right->isFloat()) {
dvander@25:             Type *floatType = left->isFloat() ? left : right;
dvander@25:             Type *other = left->isFloat() ? right : left;
dvander@25:             if (other->isFloat() || (other->isInt32() && !other->tag()))
dvander@28:                 return floatType;
dvander@22:         }
dvander@22:     }
dvander@22: 
dvander@79:     if (token == TOK_OR || token == TOK_AND) {
dvander@79:         if (!canTest(node, left) || !canTest(node, right))
dvander@79:             return NULL;
dvander@79:         return zone_->types()->getPrimitive(PrimitiveType_Int32);
dvander@79:     }
dvander@79: 
dvander@79:     if (token >= TOK_EQUALS && token <= TOK_GE) {
dvander@74:         if ((left->isFloat() || (left->isInt32() && !left->tag())) &&
dvander@75:             (right->isFloat() || (right->isInt32() && !right->tag())))
dvander@74:         {
dvander@74:             return zone_->types()->getPrimitive(PrimitiveType_Int32);
dvander@74:         }
dvander@74:         binaryTypeError(node, token, left, right);
dvander@74:         return NULL;
dvander@74:     }
dvander@74: 
dvander@25:     if ((!left->isInt32() || left->tag()) ||
dvander@25:         (!right->isInt32() || right->tag()))
dvander@25:     {
dvander@25:         binaryTypeError(node, token, left, right);
dvander@25:         return NULL;
dvander@25:     }
dvander@25: 
dvander@22:     return left;
dvander@22: }
dvander@22: 
dvander@25: bool
dvander@40: SemanticAnalysis::canTest(AstNode *node, Handle<Type> type)
dvander@25: {
dvander@79:     if (type->isArray() || (type->isInt32() && type->tag())) {
dvander@25:         cc_.reportError(node->pos(), Message_ArrayIsNotBoolean);
dvander@25:         return false;
dvander@25:     }
dvander@25:     return true;
dvander@25: }
dvander@25: 
dvander@23: Type *
dvander@23: SemanticAnalysis::visitForLValue(Expression *expression)
dvander@23: {
dvander@23:     if (expression->isIndexExpression()) {
dvander@25:         Type *type = visitAndApplyType(expression);
dvander@25:         if (!type)
dvander@23:             return NULL;
dvander@25: 
dvander@67:         if (type->isConst()) {
dvander@67:             cc_.reportError(expression->pos(), Message_ReferenceIsConstant);
dvander@67:             return NULL;
dvander@67:         }
dvander@67: 
dvander@25:         return type->contained();
dvander@23:     }
dvander@23: 
dvander@23:     if (!expression->isNameProxy()) {
dvander@25:         cc_.reportError(expression->pos(), Message_ExpectedLValue);
dvander@23:         return NULL;
dvander@23:     }
dvander@23: 
dvander@23:     NameProxy *proxy = expression->toNameProxy();
dvander@23:     if (!proxy->binding()->kind() == BoundName::VARIABLE) {
dvander@25:         cc_.reportError(expression->pos(), Message_ExpectedLValue);
dvander@23:         return NULL;
dvander@23:     }
dvander@23: 
dvander@23:     Variable *var = proxy->binding()->toVariable();
dvander@23:     if (!var->type())
dvander@23:         return NULL;
dvander@23: 
dvander@67:     if  (var->type()->isReference()) {
dvander@67:         if (var->type()->isConst()) {
dvander@67:             cc_.reportError(expression->pos(), Message_ReferenceIsConstant);
dvander@67:             return NULL;
dvander@67:         }
dvander@23:         return var->type()->contained();
dvander@67:     }
dvander@23:     return var->type();
dvander@23: }
dvander@23: 
dvander@71: SemanticAnalysis::ControlStatus
dvander@71: SemanticAnalysis::visitForControl(Statement *statement)
dvander@71: {
dvander@71:     ControlScope scope(&control_);
dvander@71:     statement->accept(this);
dvander@71:     return scope.status();
dvander@71: }
dvander@71: 
dvander@0: void
dvander@25: SemanticAnalysis::visit(NameProxy *name)
dvander@25: {
dvander@25:     name->setType(name->binding()->type());
dvander@25: }
dvander@25: 
dvander@25: void
dvander@0: SemanticAnalysis::visit(Assignment *node)
dvander@0: {
dvander@40:     Local<Type> exprType(zone_, visitForLoad(node->expression()));
dvander@25:     if (!exprType)
dvander@25:         return ;
dvander@0: 
dvander@40:     Local<Type> type(zone_, visitForLValue(node->lvalue()));
dvander@23:     if (!type)
dvander@23:         return;
dvander@4: 
dvander@25:     if (node->token() != TOK_ASSIGN) {
dvander@25:         if (!typeCheckBinary(node, node->token(), type, exprType))
dvander@25:             return;
dvander@25:     }
dvander@22: 
dvander@25:     if (!typeCheckAssignment(node, exprType, type, true))
dvander@25:         return;
dvander@25: 
dvander@25:     node->setType(type);
dvander@0: }
dvander@0: 
dvander@0: void
dvander@23: SemanticAnalysis::visit(IncDecExpression *node)
dvander@23: {
dvander@40:     Local<Type> type(zone_, visitForLValue(node->expression()));
dvander@23:     if (!type)
dvander@23:         return;
dvander@23: 
dvander@23:     assert(!type->isReference());
dvander@25: 
dvander@25:     if ((!type->isInt32() || (type->isInt32() && type->tag())) && !type->isFloat()) {
dvander@25:         unaryTypeError(node, node->token(), type);
dvander@23:         return;
dvander@23:     }
dvander@23: 
dvander@23:     node->setType(type);
dvander@23: }
dvander@23: 
dvander@23: void
dvander@78: SemanticAnalysis::visit(UnaryExpression *node)
dvander@78: {
dvander@78:     Local<Type> type(zone_, visitForLoad(node->expression()));
dvander@78:     if (!type)
dvander@78:         return;
dvander@78: 
dvander@78:     switch (node->token())
dvander@78:     {
dvander@79:       case TOK_NOT:
dvander@79:         if (!canTest(node->expression(), type))
dvander@79:             return;
dvander@79:         type = zone_->types()->getPrimitive(PrimitiveType_Int32);
dvander@79:         if (!type)
dvander@79:             return;
dvander@79:         node->setType(type);
dvander@79:         break;
dvander@79: 
dvander@80:       case TOK_MINUS:
dvander@80:         if (!type->isFloat() && (!type->isInt32() || type->tag())) {
dvander@80:             unaryTypeError(node, node->token(), type);
dvander@80:             return;
dvander@80:         }
dvander@80:         node->setType(type);
dvander@80:         break;
dvander@80: 
dvander@78:       default:
dvander@78:         assert(node->token() == TOK_TILDE);
dvander@78:         if (!type->isInt32() || type->tag()) {
dvander@78:             unaryTypeError(node, node->token(), type);
dvander@78:             return;
dvander@78:         }
dvander@78:         node->setType(type);
dvander@78:         break;
dvander@78:     }
dvander@78: }
dvander@78: 
dvander@78: void
dvander@83: SemanticAnalysis::visit(TernaryExpression *node)
dvander@83: {
dvander@83:     Local<Type> type(zone_, visitForLoad(node->condition()));
dvander@83:     if (!type)
dvander@83:         return;
dvander@83: 
dvander@83:     if (!canTest(node->condition(), type))
dvander@83:         return;
dvander@83: 
dvander@83:     Local<Type> left(zone_, visitForLoad(node->left()));
dvander@83:     Local<Type> right(zone_, visitForLoad(node->right()));
dvander@83:     if (!left || !right)
dvander@83:         return;
dvander@83: 
dvander@83:     if (left != right) {
dvander@83:         binaryTypeError(node, TOK_QMARK, left, right);
dvander@83:         return;
dvander@83:     }
dvander@83: }
dvander@83: 
dvander@83: void
dvander@0: SemanticAnalysis::visit(BinaryExpression *node)
dvander@0: {
dvander@40:     Local<Type> left(zone_, visitForLoad(node->left()));
dvander@40:     Local<Type> right(zone_, visitForLoad(node->right()));
dvander@25:     if (!left || !right)
dvander@25:         return;
dvander@4: 
dvander@40:     Local<Type> result(zone_, typeCheckBinary(node, node->token(), left, right));
dvander@25:     if (!result)
dvander@25:         return;
dvander@25: 
dvander@22:     node->setType(result);
dvander@0: }
dvander@0: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(ReturnStatement *node)
dvander@0: {
dvander@71:     // Set this early, so if we error we don't get more errors.
dvander@71:     control_->returns(Returns_Always);
dvander@71: 
dvander@72:     if (!node->expression()) {
dvander@72:         if (!function_->returnType()->isVoid())
dvander@72:             cc_.reportError(node->pos(), Message_NotAllPathsReturnValue);
dvander@72:         return;
dvander@72:     }
dvander@72: 
dvander@40:     Local<Type> type(zone_, visitForLoad(node->expression()));
dvander@25:     if (!type)
dvander@25:         return;
dvander@0: 
dvander@40:     Local<Type> returnType(zone_, function_->returnType());
dvander@40:     if (!typeCheckAssignment(node, type, returnType, true))
dvander@25:         return;
dvander@0: }
dvander@0: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(ForStatement *node)
dvander@0: {
dvander@71:     LoopScope loop(&loop_);
dvander@71: 
dvander@12:     if (node->scope())
dvander@12:         scope_ = node->scope();
dvander@25: 
dvander@22:     if (node->initialization())
dvander@22:         node->initialization()->accept(this);
dvander@25: 
dvander@25:     if (node->condition()) {
dvander@40:         Local<Type> type(zone_, visitForLoad(node->condition()));
dvander@25:         if (!type || !canTest(node->condition(), type)) {
dvander@25:             return;
dvander@25:         }
dvander@25:     }
dvander@25: 
dvander@0:     if (node->update())
dvander@0:         node->update()->accept(this);
dvander@25: 
dvander@71:     ControlStatus status = visitForControl(node->body());
dvander@71: 
dvander@71:     // If there is a condition, we treat this like a while loop. Otherwise,
dvander@71:     // join point is only reachable if the loop contains a break. The
dvander@71:     // termination status doesn't tell us anything yet.
dvander@71:     if (node->condition() || loop.breaks())
dvander@71:         control_->merge(status, ControlStatus(false, Returns_Never));
dvander@71:     else
dvander@71:         control_->terminate(status.returns());
dvander@25: 
dvander@12:     if (node->scope())
dvander@12:         scope_ = scope_->enclosing();
dvander@0: }
dvander@0: 
dvander@9: void 
dvander@9: SemanticAnalysis::visit(WhileStatement *node)
dvander@9: {
dvander@71:     LoopScope loop(&loop_);
dvander@25: 
dvander@40:     Local<Type> type(zone_, visitForLoad(node->condition()));
dvander@25:     if (!type || !canTest(node->condition(), type)) {
dvander@25:         return;
dvander@25:     }
dvander@25: 
dvander@71:     ControlStatus status = visitForControl(node->body());
dvander@71: 
dvander@71:     // Detect loops that will always have a fork in the control-flow graph.
dvander@71:     // This will be a |while| loop, or a |do-while| loop whose body does
dvander@71:     // not terminate.
dvander@71:     //
dvander@71:     // For now, we treat these as an |if| regardless of the direction the
dvander@71:     // branch can take. That means the control-flow is always conditional.
dvander@71:     if (node->token() == TOK_WHILE ||
dvander@71:         !status.terminates() ||
dvander@71:         loop.breaks())
dvander@71:     {
dvander@71:         control_->merge(status, ControlStatus(false, Returns_Never));
dvander@71:     } else {
dvander@71:         // At this point, we've got a do-while loop with a |return| or
dvander@71:         // |continue|, meaning that the rest of the block is unreachable.
dvander@71:         control_->terminate(status.returns());
dvander@71:     }
dvander@9: }
dvander@9: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(BlockStatement *node)
dvander@0: {
dvander@12:     if (node->scope())
dvander@12:         scope_ = node->scope();
dvander@0:     for (size_t i = 0; i < node->statements()->length(); i++) {
dvander@0:         Statement *statement = node->statements()->at(i);
dvander@0:         statement->accept(this);
dvander@0:     }
dvander@12:     if (node->scope())
dvander@12:         scope_ = scope_->enclosing();
dvander@0: }
dvander@0: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(VariableDeclaration *node)
dvander@0: {
dvander@54:     Local<String> tag(zone_, node->tag());
dvander@54:     Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(tag));
dvander@0:     if (!type)
dvander@0:         return;
dvander@0: 
dvander@0:     if (node->postDimensions()) {
dvander@37:         Local<Type> init(zone_);
dvander@21:         if (node->initialization()) {
dvander@71:             if ((init = visitForLoad(node->initialization())) == NULL)
dvander@21:                 return;
dvander@21:         }
dvander@21: 
dvander@55:         if (node->postDimensions()->length() > Type::MAX_UNSAFE_ARRAY_DEPTH) {
dvander@25:             cc_.reportError(node->pos(), Message_MaximumArrayDepth);
dvander@0:             return;
dvander@0:         }
dvander@0: 
dvander@21:         // If we have an initializer, make sure it's the same type.
dvander@55:         if (init && node->postDimensions()->length() != init->levels()) {
dvander@25:             cc_.reportError(node->pos(), Message_ArrayInitializerDepth);
dvander@25:             return;
dvander@21:         }
dvander@21: 
dvander@37:         Local<Type> check(zone_, init);
dvander@55:         for (size_t i = node->postDimensions()->length() - 1; i < node->postDimensions()->length(); i--) {
dvander@0:             Expression *expr = node->postDimensions()->at(i);
dvander@25:             int size = -1;
dvander@0: 
dvander@25:             if (expr) {
dvander@37:                 Local<Type> exprType(zone_, visitForLoad(expr));
dvander@25:                 if (!exprType)
dvander@25:                     return;
dvander@0: 
dvander@25:                 if (!IsPrimitiveType(exprType, PrimitiveType_Int32)) {
dvander@25:                     cc_.reportError(expr->pos(), Message_ArrayDimensionNotInteger);
dvander@0:                     return;
dvander@0:                 }
dvander@25: 
dvander@25:                 BoxedPrimitive box;
dvander@25:                 if (EvaluateForConstant(expr, &box) && box.type() == PrimitiveType_Int32) {
dvander@25:                     size = box.toInt();
dvander@25:                     if (size <= 0) {
dvander@25:                         cc_.reportError(expr->pos(), Message_BadArraySize);
dvander@25:                         return;
dvander@25:                     }
dvander@25:                     if (size >= INT_MAX / sizeof(int)) {
dvander@25:                         cc_.reportError(expr->pos(), Message_ArraySizeTooBig);
dvander@25:                         return;
dvander@25:                     }
dvander@25: 
dvander@25:                     if (check) {
dvander@25:                         if (check->elements() == -1) {
dvander@25:                             cc_.reportError(expr->pos(), Message_ArraySizeCannotBeDetermined);
dvander@25:                             return;
dvander@25:                         }
dvander@25: 
dvander@25:                         if (check->isCharArray()) {
dvander@25:                             if (check->elements() > size) {
dvander@25:                                 cc_.reportError(node->pos(), Message_ArrayAssignmentTooBig);
dvander@25:                                 return;
dvander@25:                             }
dvander@25:                         } else if (check->elements() != size) {
dvander@25:                             cc_.reportError(node->pos(), Message_ArrayDimensionSizeMismatch, unsigned(i));
dvander@25:                             return;
dvander@25:                         }
dvander@25:                     }
dvander@25:                 } else {
dvander@25:                     if (init) {
dvander@25:                         cc_.reportError(node->pos(), Message_DynamicArrayHasInitializer);
dvander@25:                         return;
dvander@25:                     }
dvander@25: 
dvander@25:                     // here until we get dynamic array support.
dvander@25:                     cc_.reportError(expr->pos(), Message_ArrayDimensionNotInteger);
dvander@0:                     return;
dvander@0:                 }
dvander@21:             } else {
dvander@25:                 // Infer the size from the initializer.
dvander@25:                 if (!init) {
dvander@25:                     cc_.reportError(node->pos(), Message_ArraySizeNotSpecified);
dvander@25:                     return;
dvander@25:                 }
dvander@25:                 if (init->elements() == -1) {
dvander@25:                     cc_.reportError(node->pos(), Message_ArraySizeCannotBeDetermined);
dvander@25:                     return;
dvander@25:                 }
dvander@25:                 size = init->elements();
dvander@0:             }
dvander@0: 
dvander@67:             type = zone_->types()->unsafeArray(type, size, false);
dvander@25:             if (!type)
dvander@25:                 return;
dvander@21: 
dvander@21:             if (check)
dvander@21:                 check = check->contained();
dvander@0:         }
dvander@12: 
dvander@85:         // If this variable is stack allocated, we could use the LIFO heap
dvander@85:         // to allocate it. If that's the case, make sure to reserve a slot
dvander@85:         // so we can unwind the LIFO heap at the end of this scope.
dvander@85:         if (!node->variable()->needsHeapAllocation())
dvander@85:             scope_->setUsesLifoHeap();
dvander@8:     } else {
dvander@10:         if (node->initialization()) {
dvander@40:             Local<Type> right(zone_, visitForLoad(node->initialization()));
dvander@25:             if (!right)
dvander@25:                 return;
dvander@25:             if (!typeCheckAssignment(node, type, right, true))
dvander@25:                 return;
dvander@10:         }
dvander@21:         if (type->primitive() == PrimitiveType_Char) {
dvander@25:             cc_.reportError(node->pos(), Message_CannotDeclareStringCell);
dvander@21:             return;
dvander@21:         }
dvander@0:     }
dvander@0: 
dvander@0:     node->variable()->setType(type);
dvander@0: }
dvander@0: 
dvander@0: void
dvander@4: SemanticAnalysis::visit(IntegerLiteral *node)
dvander@0: {
dvander@30:     node->setType(zone_->types()->getPrimitive(PrimitiveType_Int32));
dvander@0: }
dvander@0: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(ExpressionStatement *node)
dvander@0: {
dvander@71:     visitAndApplyType(node->expression());
dvander@0: }
dvander@0: 
dvander@14: bool
dvander@14: SemanticAnalysis::preanalyze(FunctionStatement *node)
dvander@14: {
dvander@57:     Local<FixedArray> args(zone_, FixedArray::New(zone_, node->parameters()->length(), Heap::Tenure_Old));
dvander@14:     if (!args)
dvander@14:         return false;
dvander@14: 
dvander@14:     // Apply types to arguments.
dvander@57:     for (size_t i = 0; i < node->parameters()->length(); i++) {
dvander@14:         Parameter *parameter = node->parameters()->at(i);
dvander@14:         
dvander@54:         Local<String> tag(zone_, parameter->tag());
dvander@54:         Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(tag));
dvander@14:         if (!type)
dvander@14:             return false;
dvander@14: 
dvander@14:         if (parameter->reference()) {
dvander@66:             if (parameter->dimensions()) {
dvander@66:                 cc_.reportError(parameter->variable()->pos(), Message_ArrayCantBeReference);
dvander@66:                 return NULL;
dvander@66:             }
dvander@66: 
dvander@67:             type = zone_->types()->getReference(type, parameter->isConst());
dvander@14:             if (!type)
dvander@14:                 return false;
dvander@66:         } else if (parameter->dimensions()) {
dvander@66:             if (parameter->dimensions()->length() > Type::MAX_UNSAFE_ARRAY_DEPTH) {
dvander@68:                 cc_.reportError(parameter->variable()->pos(), Message_MaximumArrayDepth);
dvander@68:                 return false;
dvander@68:             }
dvander@68: 
dvander@68:             if (node->fun()->isNative() && parameter->dimensions()->length() > 1) {
dvander@68:                 cc_.reportError(parameter->variable()->pos(), Message_MultiArrayInNative);
dvander@66:                 return false;
dvander@66:             }
dvander@66: 
dvander@66:             for (size_t i = parameter->dimensions()->length() - 1;
dvander@66:                  i < parameter->dimensions()->length();
dvander@66:                  i++)
dvander@66:             {
dvander@66:                 int size = Type::UNKNOWN_SIZE;
dvander@66:                 if (Expression *expr = parameter->dimensions()->at(i)) {
dvander@66:                     BoxedPrimitive box;
dvander@66:                     if (!EvaluateForConstant(expr, &box)) {
dvander@66:                         cc_.reportError(expr->pos(), Message_ArraySizeMustBeConstant);
dvander@66:                         return false;
dvander@66:                     }
dvander@66:                     size = box.toInt();
dvander@66:                 }
dvander@66: 
dvander@67:                 type = zone_->types()->unsafeArray(type, size, parameter->isConst());
dvander@66:                 if (!type)
dvander@66:                     return false;
dvander@66:             }
dvander@14:         }
dvander@14: 
dvander@68:         if ((type->isPrimitive() && type->primitive() == PrimitiveType_Char) ||
dvander@68:             (type->isReference() && type->contained()->primitive() == PrimitiveType_Char))
dvander@68:         {
dvander@68:             cc_.reportError(node->pos(), Message_CannotDeclareStringCell);
dvander@68:             return false;
dvander@68:         }
dvander@68: 
dvander@30:         args->set(zone_, i, type);
dvander@14:         parameter->variable()->setType(type);
dvander@14:     }
dvander@14: 
dvander@71:     Local<Type> returnType(zone_);
dvander@72:     if (node->hasExplicitReturn() || node->fun()->isNative())
dvander@71:         returnType = zone_->types()->getPrimitive(PrimitiveType_Int32);
dvander@71:     else
dvander@71:         returnType = zone_->types()->getVoid();
dvander@14:     if (!returnType)
dvander@14:         return false;
dvander@14: 
dvander@68:     Local<Type> funtype(zone_);
dvander@68:     if (node->fun()->isNative())
dvander@68:         funtype = zone_->types()->newNative(returnType, args, node->fun()->isNativeVariadic());
dvander@68:     else
dvander@68:         funtype = zone_->types()->newFunction(returnType, args);
dvander@14:     if (!funtype)
dvander@14:         return false;
dvander@63:     
dvander@63:     // If the function already has a type, it was forward declared before, and
dvander@63:     // now this is our chance to type check the second declaration.
dvander@63:     if (node->fun()->type()) {
dvander@63:         Local<Type> forward(zone_, node->fun()->type());
dvander@63:         if (!Type::Compare(funtype, forward)) {
dvander@63:             cc_.reportError(node->pos(), Message_ForwardDeclareMismatches);
dvander@63:             return false;
dvander@63:         }
dvander@63:         node->fun()->setForwardType(forward);
dvander@63:     }
dvander@14: 
dvander@14:     node->fun()->setType(funtype);
dvander@63: 
dvander@14:     return true;
dvander@14: }
dvander@14: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(FunctionStatement *node)
dvander@0: {
dvander@25:     function_ = node->fun()->type();
dvander@12:     scope_ = node->scope();
dvander@71: 
dvander@71:     ControlScope control(&control_);
dvander@71:     if (node->body()) {
dvander@63:         node->body()->accept(this);
dvander@71: 
dvander@71:         ControlStatus status = control.status();
dvander@71:         if (status.returns() == Returns_Sometimes) {
dvander@71:             cc_.reportError(node->pos(), Message_NotAllPathsReturnValue);
dvander@71:         } else if (status.returns() == Returns_Never) {
dvander@71:             if (!function_->returnType()->isVoid())
dvander@71:                 cc_.reportError(node->pos(), Message_MissingReturnValue);
dvander@71:         }
dvander@71:     }
dvander@71: 
dvander@12:     scope_ = NULL;
dvander@25:     function_ = NULL;
dvander@0: }
dvander@0: 
dvander@25: bool
dvander@40: SemanticAnalysis::typeCheckArrayAssignment(AstNode *node, Handle<Type> argGiven, Handle<Type> argActual, bool forAssign)
dvander@14: {
dvander@40:     Local<Type> actual(zone_, argActual);
dvander@40:     Local<Type> given(zone_, argGiven);
dvander@40: 
dvander@25:     if (!given->isArray()) {
dvander@25:         cc_.reportError(node->pos(), Message_ExpectedArray);
dvander@25:         return false;
dvander@25:     }
dvander@25:     if (given->levels() != actual->levels()) {
dvander@25:         cc_.reportError(node->pos(), Message_ArrayDimensionsMismatch);
dvander@25:         return false;
dvander@25:     }
dvander@25: 
dvander@25:     unsigned level = 0;
dvander@25:     while (given->isArray()) {
dvander@25:         if (actual->elements() != -1) {
dvander@25:             if (forAssign) {
dvander@25:                 if (given->elements() == -1 || actual->elements() == -1) {
dvander@25:                     cc_.reportError(node->pos(), Message_ArraySizeNotKnown);
dvander@25:                     return false;
dvander@25:                 }
dvander@25: 
dvander@25:                 if (actual->isCharArray()) {
dvander@25:                     // String assignment can have a truncated |given|.
dvander@25:                     if (given->elements() > actual->elements()) {
dvander@25:                         cc_.reportError(node->pos(), Message_ArrayAssignmentTooBig);
dvander@25:                         return false;
dvander@25:                     }
dvander@25:                 } else {
dvander@25:                     if (given->elements() != actual->elements()) {
dvander@25:                         cc_.reportError(node->pos(), Message_ArrayDimensionSizeMismatch, level);
dvander@25:                         return false;
dvander@25:                     }
dvander@25:                 }
dvander@25:             } else {
dvander@25:                 if (actual->elements() != -1 && given->elements() != actual->elements()) {
dvander@25:                     cc_.reportError(node->pos(), Message_ArrayDimensionSizeMismatch, level);
dvander@25:                     return false;
dvander@25:                 }
dvander@25:             }
dvander@25:         }
dvander@25:         given = given->contained();
dvander@25:         actual = actual->contained();
dvander@14:     }
dvander@14: 
dvander@25:     if (given->primitive() != actual->primitive()) {
dvander@54:         // :TODO: leaks an interior pointer.
dvander@54:         const char *givenTag = given->tag() ? given->tag()->chars() : "_";
dvander@54:         const char *actualTag = given->tag() ? given->tag()->chars() : "_";
dvander@25:         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);
dvander@25:         return false;
dvander@25:     }
dvander@25: 
dvander@25:     return true;
dvander@25: }
dvander@25: 
dvander@25: bool
dvander@40: SemanticAnalysis::typeCheckAssignment(AstNode *node, Handle<Type> argGiven, Handle<Type> argActual, bool forAssign)
dvander@25: {
dvander@40:     Local<Type> actual(zone_, argActual);
dvander@40:     Local<Type> given(zone_, argGiven);
dvander@40: 
dvander@25:     if (actual->isArray())
dvander@25:         return typeCheckArrayAssignment(node, given, actual, forAssign);
dvander@25: 
dvander@25:     if (given->isArray()) {
dvander@25:         cc_.reportError(node->pos(), Message_CannotAssignArrayToScalar);
dvander@25:         return false;
dvander@25:     }
dvander@25: 
dvander@47:     // The given type may not have been dereferenced.
dvander@47:     if (given->isReference())
dvander@47:         given = given->contained();
dvander@47:     if (actual->isReference())
dvander@47:         actual = actual->contained();
dvander@47: 
dvander@47:     if (!given->isPrimitive() || !actual->isPrimitive()) {
dvander@25:         cc_.reportError(node->pos(), Message_UnsupportedType);
dvander@25:         return false;
dvander@25:     }
dvander@25:     
dvander@25:     if (given->primitive() != actual->primitive()) {
dvander@54:         // :TODO: leaks an interior pointer
dvander@54:         const char *givenTag = given->tag() ? given->tag()->chars() : "_";
dvander@85:         const char *actualTag = actual->tag() ? actual->tag()->chars() : "_";
dvander@25:         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);
dvander@25:         return false;
dvander@25:     }
dvander@25: 
dvander@25:     return true;
dvander@25: }
dvander@25: 
dvander@25: bool
dvander@40: SemanticAnalysis::typeCheckParameter(AstNode *node, Handle<Type> given, Handle<Type> actual)
dvander@25: {
dvander@25:     return typeCheckAssignment(node, given, actual, false);
dvander@14: }
dvander@14: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(CallExpression *node)
dvander@0: {
dvander@40:     Local<Type> type(zone_, visitForLoad(node->callee()));
dvander@14:     if (!type)
dvander@14:         return;
dvander@14: 
dvander@25:     if (!type->isFunction()) {
dvander@25:         cc_.reportError(node->pos(), Message_CalleeNotFunction);
dvander@25:         return;
dvander@25:     }
dvander@55:     if (node->arguments()->length() != type->parameters()->length()) {
dvander@68:         if (!type->isNative() ||
dvander@68:             !type->isNativeVariadic() ||
dvander@68:             node->arguments()->length() < type->parameters()->length())
dvander@68:         {
dvander@68:             cc_.reportError(node->pos(), Message_ArgumentCountMismatch);
dvander@68:             return;
dvander@68:         }
dvander@25:     }
dvander@14: 
dvander@63:     // Currently, only calls from a NameProxy are possible.
dvander@63:     NamedFunction *fun = node->callee()->toNameProxy()->binding()->toNamedFunction();
dvander@63:     if (fun->isForward()) {
dvander@63:         cc_.reportError(node->pos(), Message_ForwardNotImplemented, fun->name()->chars());
dvander@63:         return;
dvander@63:     }
dvander@63: 
dvander@55:     for (unsigned i = 0; i < node->arguments()->length(); i++) {
dvander@17:         // Note: we don't compute references unless the callee needs a
dvander@17:         // reference type.
dvander@14:         Expression *expression = node->arguments()->at(i);
dvander@40:         Local<Type> given(zone_, visitAndApplyType(expression));
dvander@14:         if (!given)
dvander@14:             return;
dvander@14: 
dvander@71:         // Since we skip a load, check for a call expression that returns void.
dvander@71:         if (given->isVoid()) {
dvander@71:             assert(expression->isCallExpression());
dvander@71:             CallExpression *call = expression->toCallExpression();
dvander@71:             cc_.reportError(call->callee()->pos(), Message_FunctionDoesNotReturnValue);
dvander@71:             return;
dvander@71:         }
dvander@71:         
dvander@17:         // If it's an IndexExpression, we special case the ability to compute
dvander@25:         // a reference.
dvander@17:         if (expression->isIndexExpression())
dvander@17:             given = given->contained();
dvander@17: 
dvander@68:         bool mustComputeReference;
dvander@68:         if (i >= type->parameters()->length()) {
dvander@68:             // Special handling for natives. Arguments past the formal must
dvander@68:             // always have references computed. However, arrays are already
dvander@68:             // references for natives.  
dvander@68:             assert(type->isNative() && type->isNativeVariadic());
dvander@68:             mustComputeReference = !given->isReference() && !given->isArray();
dvander@68:         } else {
dvander@68:             Local<Type> actual(zone_, type->parameterAt(i));
dvander@68:             if (!typeCheckParameter(expression, given, actual))
dvander@68:                 return;
dvander@68:             mustComputeReference = actual->isReference() && !given->isReference();
dvander@68:         }
dvander@14: 
dvander@14:         // If the actual is a reference, and the given is not, we'll need to
dvander@14:         // compute a reference, which may be allocated on the stack.
dvander@68:         if (mustComputeReference)
dvander@14:             scope_->setUsesLifoHeap();
dvander@14:     }
dvander@66: 
dvander@66:     node->setType(fun->type()->returnType());
dvander@0: }
dvander@0: 
dvander@0: void
dvander@71: SemanticAnalysis::ControlScope::merge(const ControlStatus &left, const ControlStatus &right)
dvander@71: {
dvander@71:     // If both sides terminate in a return, we consider this a return as well.
dvander@71:     if (left.returns() == Returns_Always && right.returns() == Returns_Always) {
dvander@71:         terminate(Returns_Always);
dvander@71:         return;
dvander@71:     }
dvander@71: 
dvander@71:     ReturnStatus status = (left.returns() == Returns_Never && right.returns() == Returns_Never)
dvander@71:                           ? Returns_Never
dvander@71:                           : Returns_Sometimes;
dvander@71: 
dvander@71:     if (left.terminates() && right.terminates())
dvander@71:         terminate(status);
dvander@71:     else
dvander@71:         returns(status);
dvander@71: }
dvander@71: 
dvander@71: void
dvander@0: SemanticAnalysis::visit(IfStatement *node)
dvander@0: {
dvander@40:     Local<Type> type(zone_, visitForLoad(node->condition()));
dvander@25:     if (!type)
dvander@25:         return;
dvander@25: 
dvander@25:     if (!canTest(node, type))
dvander@25:         return;
dvander@25: 
dvander@71:     ControlStatus trueBranch = visitForControl(node->ifTrue());
dvander@71:     ControlStatus falseBranch = ControlStatus(false, Returns_Never);
dvander@71: 
dvander@10:     if (node->ifFalse())
dvander@71:         falseBranch = visitForControl(node->ifFalse());
dvander@71: 
dvander@71:     control_->merge(trueBranch, falseBranch);
dvander@0: }
dvander@0: 
dvander@0: void
dvander@0: SemanticAnalysis::visit(IndexExpression *node)
dvander@0: {
dvander@71:     Local<Type> left(zone_, visitForLoad(node->left()));
dvander@40:     Local<Type> right(zone_, visitForLoad(node->right()));
dvander@0: 
dvander@25:     if (!left || !right)
dvander@25:         return;
dvander@25: 
dvander@25:     if (!right->isInt32()) {
dvander@25:         cc_.reportError(node->right()->pos(), Message_IndexMustBeInteger);
dvander@0:         return;
dvander@0:     }
dvander@25:     if (!left->isArray()) {
dvander@25:         cc_.reportError(node->left()->pos(), Message_IndexBaseMustBeArray);
dvander@0:         return;
dvander@0:     }
dvander@7:     node->setType(left);
dvander@0: }
dvander@2: 
dvander@2: void
dvander@2: SemanticAnalysis::visit(EnumStatement *node)
dvander@2: {
dvander@25:     // Forbid the blessed types.
dvander@54:     Local<String> tag(zone_, node->name());
dvander@54:     if (!strcmp(tag->chars(), "Float") ||
dvander@54:         !strcmp(tag->chars(), "String") ||
dvander@54:         !strcmp(tag->chars(), "any") ||
dvander@54:         !strcmp(tag->chars(), "bool"))
dvander@25:     {
dvander@25:         cc_.reportError(node->pos(), Message_InvalidEnumName);
dvander@25:         return;
dvander@25:     }
dvander@3: 
dvander@40:     Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(tag));
dvander@2:     if (!type)
dvander@2:         return;
dvander@2: 
dvander@2:     int value = 0;
dvander@57:     for (size_t i = 0; i < node->entries()->length(); i++) {
dvander@2:         EnumStatement::Entry &entry = node->entries()->at(i);
dvander@2: 
dvander@2:         BoxedPrimitive box = BoxedPrimitive::Int(value);
dvander@2:         if (entry.expr) {
dvander@2:             entry.expr->accept(this);
dvander@25:             if (!EvaluateForConstant(entry.expr, &box)) {
dvander@25:                 cc_.reportError(entry.expr->pos(), Message_EnumFieldNotConstant);
dvander@25:                 return;
dvander@25:             }
dvander@2: 
dvander@2:             assert(box.type() == PrimitiveType_Int32);
dvander@2:             value = box.toInt();
dvander@2:         }
dvander@2: 
dvander@2:         entry.name->set(type, box);
dvander@2:         value++;
dvander@2:     }
dvander@2: }
dvander@4: 
dvander@4: void
dvander@21: SemanticAnalysis::visit(StringLiteral *node)
dvander@21: {
dvander@40:     Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Char));
dvander@21:     if (!type)
dvander@21:         return;
dvander@21: 
dvander@30:     type = Type::NewArray(zone_, type, node->string()->length() + 1, true);
dvander@21:     if (!type)
dvander@21:         return;
dvander@21: 
dvander@21:     node->setType(type);
dvander@21: }
dvander@21: 
dvander@21: void
dvander@4: SemanticAnalysis::visit(FloatLiteral *node)
dvander@4: {
dvander@40:     Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Float));
dvander@4:     if (!type)
dvander@4:         return;
dvander@4: 
dvander@4:     node->setType(type);
dvander@4: }
dvander@10: 
dvander@10: void
dvander@10: SemanticAnalysis::visit(BreakStatement *node)
dvander@10: {
dvander@71:     if (!loop_) {
dvander@25:         cc_.reportError(node->pos(), Message_BreakOutsideLoop);
dvander@71:         return;
dvander@71:     }
dvander@71: 
dvander@71:     // Note: ignore breaks that occur in unreachable control-flow.
dvander@71:     if (!control_->status().terminates())
dvander@71:         loop_->addBreak();
dvander@71: 
dvander@71:     control_->terminate(Returns_Never);
dvander@10: }
dvander@10: 
dvander@10: void
dvander@10: SemanticAnalysis::visit(ContinueStatement *node)
dvander@10: {
dvander@71:     if (!loop_) {
dvander@25:         cc_.reportError(node->pos(), Message_ContinueOutsideLoop);
dvander@71:         return;
dvander@71:     }
dvander@71: 
dvander@71:     // Note: ignore continues that occur in unreachable control-flow.
dvander@71:     if (!control_->status().terminates())
dvander@71:         loop_->addContinue();
dvander@71: 
dvander@71:     control_->terminate(Returns_Never);
dvander@10: }