1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/compiler/SemanticAnalysis.cpp Sat Nov 17 18:41:01 2012 -0800
1.3 @@ -0,0 +1,624 @@
1.4 +/* vim: set ts=4 sw=4 tw=99 et:
1.5 + *
1.6 + * Copyright (C) 2012 David Anderson
1.7 + *
1.8 + * This file is part of SourcePawn.
1.9 + *
1.10 + * SourcePawn is free software: you can redistribute it and/or modify it under
1.11 + * the terms of the GNU General Public License as published by the Free
1.12 + * Software Foundation, either version 3 of the License, or (at your option)
1.13 + * any later version.
1.14 + *
1.15 + * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
1.16 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License along with
1.20 + * SourcePawn. If not, see http://www.gnu.org/licenses/.
1.21 + */
1.22 +#include <assert.h>
1.23 +#include "../Zone.h"
1.24 +#include "../Strings.h"
1.25 +#include "../NativeTable.h"
1.26 +#include "../TypeManager.h"
1.27 +#include "../Modules.h"
1.28 +#include "../Code.h"
1.29 +#include "SemanticAnalysis.h"
1.30 +
1.31 +using namespace ke;
1.32 +
1.33 +#define __ emitter_.
1.34 +
1.35 +typedef BytecodeEmitter::Label Label;
1.36 +
1.37 +class AutoEnterScope
1.38 +{
1.39 + public:
1.40 + AutoEnterScope(Scope **prevp, Scope *scope)
1.41 + : prevp_(prevp),
1.42 + prev_(*prevp),
1.43 + scope_(scope)
1.44 + {
1.45 + if (!scope_)
1.46 + return;
1.47 + prev_ = *prevp_;
1.48 + *prevp_ = scope;
1.49 + assert(prev_ == scope->enclosing());
1.50 + }
1.51 + ~AutoEnterScope()
1.52 + {
1.53 + if (scope_)
1.54 + *prevp_ = prev_;
1.55 + }
1.56 + private:
1.57 + Scope **prevp_;
1.58 + Scope *prev_;
1.59 + Scope *scope_;
1.60 +};
1.61 +
1.62 +SemanticAnalysis::SemanticAnalysis(Zone *zone, CompileContext &cc, TranslationUnit *unit)
1.63 + : zone_(zone),
1.64 + pool_(zone->pool()),
1.65 + cc_(cc),
1.66 + unit_(unit),
1.67 + hir_(NULL),
1.68 + emitter_(pool_),
1.69 + module_(NULL),
1.70 + loop_(NULL)
1.71 +{
1.72 +}
1.73 +
1.74 +SemanticAnalysis::SemanticAnalysis(SemanticAnalysis *parent, Handle<FunctionType> fun)
1.75 + : zone_(parent->zone_),
1.76 + pool_(parent->pool_),
1.77 + cc_(parent->cc_),
1.78 + unit_(parent->unit_),
1.79 + hir_(NULL),
1.80 + scope_(parent->scope_),
1.81 + emitter_(pool_),
1.82 + module_(parent->module_),
1.83 + fun_(fun),
1.84 + loop_(NULL)
1.85 +{
1.86 +
1.87 +}
1.88 +
1.89 +void
1.90 +SemanticAnalysis::analyze()
1.91 +{
1.92 + scope_ = unit_->globalScope();
1.93 +
1.94 + module_ = Module::New(zone_);
1.95 +
1.96 + for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
1.97 + Statement *stmt = unit_->tree()->statements()->at(i);
1.98 + stmt->accept(this);
1.99 + }
1.100 +
1.101 + Local<Struct> globals(zone_, unit_->globalScope()->build(zone_));
1.102 + if (!globals)
1.103 + return;
1.104 + module_->setGlobals(globals);
1.105 +
1.106 + Local<Code> code(zone_, __ finish());
1.107 + if (!code)
1.108 + return;
1.109 + code->setModule(module_);
1.110 + module_->setCode(code);
1.111 +
1.112 +#ifndef NDEBUG
1.113 +// Disassemble(code, stdout);
1.114 +#endif
1.115 +
1.116 + unit_->module_ = module_;
1.117 +}
1.118 +
1.119 +void
1.120 +SemanticAnalysis::visitFunctionStatement(FunctionStatement *stmt)
1.121 +{
1.122 + FunctionSymbol *sym = stmt->sym();
1.123 + Local<FunctionType> type(zone_, sym->type());
1.124 +
1.125 + assert(scope_->kind() == Scope::GLOBAL);
1.126 +
1.127 + if (stmt->token() == TOK_NATIVE) {
1.128 + // Define the native now.
1.129 + size_t index;
1.130 + if (!zone_->nativeTable()->add(stmt->name(), &index))
1.131 + return;
1.132 +
1.133 + Local<Native> native(zone_, Native::New(zone_, type, index));
1.134 + if (!native)
1.135 + return;
1.136 +
1.137 + __ object(native);
1.138 + __ setglobal(sym);
1.139 + __ pop();
1.140 + }
1.141 +
1.142 + // If the function is a forward or native, we don't have to do anything.
1.143 + if (stmt->token() == TOK_NATIVE || stmt->token() == TOK_FORWARD)
1.144 + return;
1.145 +
1.146 + SemanticAnalysis child(this, type);
1.147 + Local<Function> funobj(zone_, child.compile(stmt));
1.148 + if (!funobj)
1.149 + return;
1.150 +
1.151 + __ object(funobj);
1.152 + __ setglobal(sym);
1.153 + __ public_();
1.154 +}
1.155 +
1.156 +Function *
1.157 +SemanticAnalysis::compile(FunctionStatement *stmt)
1.158 +{
1.159 + __ setFirstLine(stmt->pos().line);
1.160 +
1.161 + AutoEnterScope argScope(&scope_, stmt->argScope());
1.162 + AutoEnterScope varScope(&scope_, stmt->varScope());
1.163 +
1.164 + stmt->body()->accept(this);
1.165 +
1.166 + Local<Code> code(zone_, __ finish());
1.167 + if (!code)
1.168 + return NULL;
1.169 + code->setModule(module_);
1.170 +
1.171 + Local<Function> fun(zone_, Function::New(zone_, code, fun_, stmt->name(), stmt->pos()));
1.172 + if (!fun)
1.173 + return NULL;
1.174 +
1.175 +#ifndef NDEBUG
1.176 +// Disassemble(code, stdout);
1.177 +#endif
1.178 +
1.179 + return fun;
1.180 +}
1.181 +
1.182 +void
1.183 +SemanticAnalysis::visitBlockStatement(BlockStatement *node)
1.184 +{
1.185 + AutoEnterScope scope(&scope_, node->scope());
1.186 +
1.187 + for (size_t i = 0; i < node->statements()->length(); i++) {
1.188 + Statement *stmt = node->statements()->at(i);
1.189 + stmt->accept(this);
1.190 + assert(__ stackDepth() == 0);
1.191 + }
1.192 +}
1.193 +
1.194 +void
1.195 +SemanticAnalysis::visitExpressionStatement(ExpressionStatement *node)
1.196 +{
1.197 + // While building HIR, we enter new pool and root scopes, since HIR
1.198 + // creation is purely temporary.
1.199 + PoolScope poolScope(zone_->pool());
1.200 + RootScope rootScope(zone_);
1.201 +
1.202 + HIR *hir = eval(node->expression());
1.203 + if (!hir)
1.204 + return;
1.205 +
1.206 + discharge(hir);
1.207 + __ pop();
1.208 +}
1.209 +
1.210 +void
1.211 +SemanticAnalysis::visitForStatement(ForStatement *node)
1.212 +{
1.213 + AutoEnterScope scope(&scope_, node->scope());
1.214 + PoolScope poolScope(zone_->pool());
1.215 + RootScope rootScope(zone_);
1.216 +
1.217 + Label join, update;
1.218 + LoopScope loop(scope_, &join, &update, &loop_);
1.219 +
1.220 + if (node->initialization())
1.221 + node->initialization()->accept(this);
1.222 +
1.223 + Label header, test;
1.224 + if (node->condition())
1.225 + __ jump(&test);
1.226 +
1.227 + __ bind(&header);
1.228 + node->body()->accept(this);
1.229 +
1.230 + __ bind(&update);
1.231 + if (node->update())
1.232 + node->update()->accept(this);
1.233 +
1.234 + if (node->condition()) {
1.235 + __ bind(&test);
1.236 + visitForTest(node->condition(), &header, &join, &join);
1.237 + } else {
1.238 + __ jump(&header);
1.239 + }
1.240 +
1.241 + __ bind(&join);
1.242 +
1.243 + assert(__ stackDepth() == 0);
1.244 +}
1.245 +
1.246 +void
1.247 +SemanticAnalysis::visitVariableDeclaration(VariableDeclaration *node)
1.248 +{
1.249 + PoolScope poolScope(zone_->pool());
1.250 + RootScope rootScope(zone_);
1.251 +
1.252 + HIR *hir;
1.253 + if (node->initialization()) {
1.254 + if ((hir = eval(node->initialization())) == NULL)
1.255 + return;
1.256 + if ((hir = coerce(hir, node->sym()->type(), Coerce_Assign)) == NULL)
1.257 + return;
1.258 + } else {
1.259 + assert(false);
1.260 + }
1.261 +
1.262 + discharge(hir);
1.263 +
1.264 + if (!__ allocate(node->sym()))
1.265 + return;
1.266 +
1.267 + set(node->sym());
1.268 + __ pop();
1.269 +}
1.270 +
1.271 +void
1.272 +SemanticAnalysis::visitReturnStatement(ReturnStatement *node)
1.273 +{
1.274 + if (!node->expression()) {
1.275 + if (!fun_->returnType()->isVoid()) {
1.276 + cc_.reportError(node->pos(), Message_UsedVoidReturn);
1.277 + return;
1.278 + }
1.279 +
1.280 + __ returnvoid();
1.281 + return;
1.282 + }
1.283 +
1.284 + PoolScope poolScope(zone_->pool());
1.285 + RootScope rootScope(zone_);
1.286 +
1.287 + HIR *hir = eval(node->expression());
1.288 + if (!hir)
1.289 + return;
1.290 +
1.291 + Local<Type> returnType(zone_, fun_->returnType());
1.292 + if ((hir = coerce(hir, returnType, Coerce_Return)) == NULL)
1.293 + return;
1.294 +
1.295 + discharge(hir);
1.296 + __ return_();
1.297 +}
1.298 +
1.299 +void
1.300 +SemanticAnalysis::visitBinaryExpression(BinaryExpression *node)
1.301 +{
1.302 + HIR *left = eval(node->left());
1.303 + HIR *right = eval(node->right());
1.304 + if (!left || !right)
1.305 + return;
1.306 +
1.307 + hir_ = binary(node->token(), left, right);
1.308 +}
1.309 +
1.310 +bool
1.311 +SemanticAnalysis::checkArgumentCount(Handle<FunctionType> type, unsigned actual)
1.312 +{
1.313 + if (type->parameters()->length() == actual)
1.314 + return true;
1.315 +
1.316 + if (actual > type->parameters()->length()) {
1.317 + if (!type->isNative() || !type->isNativeVariadic())
1.318 + return false;
1.319 + return true;
1.320 + }
1.321 +
1.322 + if (!type->defaults())
1.323 + return false;
1.324 +
1.325 + // Missing arguments. See if there's a default argument for each missing
1.326 + // actual.
1.327 + for (unsigned i = actual; i < type->parameters()->length(); i++) {
1.328 + if (!type->defaults()->at(i))
1.329 + return false;
1.330 + }
1.331 +
1.332 + return true;
1.333 +}
1.334 +
1.335 +void
1.336 +SemanticAnalysis::visitNameProxy(NameProxy *proxy)
1.337 +{
1.338 + Symbol *sym = proxy->sym();
1.339 + Handle<Type> type = sym->type();
1.340 +
1.341 + VariableSymbol *var = sym->asVariable();
1.342 +
1.343 + Scope *in = sym->scope();
1.344 + switch (in->kind()) {
1.345 + case Scope::GLOBAL:
1.346 + hir_ = new (pool_) HGlobal(sym);
1.347 + return;
1.348 +
1.349 + default:
1.350 + assert(in->kind() == Scope::BLOCK);
1.351 + assert(var->storage() == VariableSymbol::Local);
1.352 + hir_ = new (pool_) HLocal(var);
1.353 + return;
1.354 + }
1.355 +}
1.356 +
1.357 +void
1.358 +SemanticAnalysis::visitIntegerLiteral(IntegerLiteral *lit)
1.359 +{
1.360 + Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
1.361 + hir_ = new (pool_) HInteger(type, lit->value());
1.362 +}
1.363 +
1.364 +void
1.365 +SemanticAnalysis::visitFloatLiteral(FloatLiteral *node)
1.366 +{
1.367 + Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Float));
1.368 + hir_ = new (pool_) HFloat(type, (float)node->value());
1.369 +}
1.370 +
1.371 +void
1.372 +SemanticAnalysis::visitCallExpression(CallExpression *node)
1.373 +{
1.374 + HIR *callee = eval(node->callee());
1.375 + if (!callee)
1.376 + return;
1.377 +
1.378 + if (!callee->type()->isFunction()) {
1.379 + cc_.reportError(node->pos(), Message_CalleeNotFunction);
1.380 + return;
1.381 + }
1.382 +
1.383 + Local<FunctionType> fun(zone_, FunctionType::cast(callee->type()));
1.384 +
1.385 + if (!checkArgumentCount(fun, node->arguments()->length())) {
1.386 + cc_.reportError(node->pos(), Message_ArgumentCountMismatch);
1.387 + return;
1.388 + }
1.389 +
1.390 + if (fun->isForward()) {
1.391 + cc_.reportError(node->pos(), Message_ForwardNotImplemented, fun->name()->chars());
1.392 + return;
1.393 + }
1.394 +
1.395 + HIRList *args = new (pool_) HIRList;
1.396 + for (unsigned i = 0; i < node->arguments()->length(); i++) {
1.397 + Expression *expression = node->arguments()->at(i);
1.398 + HIR *arg = eval(expression);
1.399 + if (!arg)
1.400 + return;
1.401 +
1.402 + Handle<Type> given = arg->type();
1.403 +
1.404 + bool mustComputeReference;
1.405 + if (i >= fun->parameters()->length()) {
1.406 + // Special handling for natives. Arguments past the formal must
1.407 + // always have references computed. However, arrays are already
1.408 + // references for natives.
1.409 + assert(fun->isNative() && fun->isNativeVariadic());
1.410 + mustComputeReference = !given->isReference() &&
1.411 + !given->isArray();
1.412 + } else {
1.413 + Local<Type> actual(zone_, fun->parameterAt(i));
1.414 +
1.415 + if (expression->isIndexExpression()) {
1.416 + // Temporarily disabled.
1.417 + assert(!actual->isArray());
1.418 + if (actual->isReference()) {
1.419 + cc_.reportError(expression->pos(), Message_CannotComputeIndexRef);
1.420 + return;
1.421 + }
1.422 + }
1.423 +
1.424 + // When we start overloading, coercion will have to happen later.
1.425 + arg = coerce(arg, actual, Coerce_Arg);
1.426 + if (!arg)
1.427 + return;
1.428 +
1.429 + mustComputeReference = actual->isReference() && !given->isReference();
1.430 + }
1.431 +
1.432 + // :TODO: handle mustComputeReference
1.433 + assert(!mustComputeReference);
1.434 +
1.435 + if (!args->append(arg))
1.436 + return;
1.437 + }
1.438 +
1.439 + hir_ = new (pool_) HCall(fun->returnType(), callee, args);
1.440 +}
1.441 +
1.442 +void
1.443 +SemanticAnalysis::visitAssignment(Assignment *node)
1.444 +{
1.445 + HLValue *lval = lvalue(node->lvalue());
1.446 + if (!lval)
1.447 + return;
1.448 +
1.449 + HIR *hir = eval(node->expression());
1.450 + if ((hir = coerce(hir, lval->type(), Coerce_Assign)) == NULL)
1.451 + return;
1.452 +
1.453 + hir_ = new (pool_) HStore(lval, hir);
1.454 +}
1.455 +
1.456 +Type *
1.457 +SemanticAnalysis::coercionType(TokenKind token, HIR *left, HIR *right)
1.458 +{
1.459 + Handle<Type> l = left->type();
1.460 + Handle<Type> r = right->type();
1.461 +
1.462 + if (token >= TOK_PLUS && token <= TOK_SLASH) {
1.463 + // We allow: [float|int32] + [float|int32]
1.464 + if (l->isFloat() && r->isInt32())
1.465 + return l;
1.466 + if (l->isInt32() && r->isFloat())
1.467 + return r;
1.468 + if (l->isInt32() && r->isInt32())
1.469 + return l;
1.470 + }
1.471 +
1.472 + assert(l == r);
1.473 +
1.474 + return left->type();
1.475 +}
1.476 +
1.477 +HIR *
1.478 +SemanticAnalysis::coerce(HIR *hir, Handle<Type> to, CoercionKind kind)
1.479 +{
1.480 + Handle<Type> from = hir->type();
1.481 +
1.482 + if (from->isInt32() && to->isFloat())
1.483 + return new (pool_) HConvert(to, OP_CVT_I2F, hir);
1.484 +
1.485 + assert(from == to);
1.486 +
1.487 + return hir;
1.488 +}
1.489 +
1.490 +void
1.491 +SemanticAnalysis::set(VariableSymbol *sym)
1.492 +{
1.493 + if (sym->scope()->kind() == Scope::GLOBAL) {
1.494 + __ setglobal(sym);
1.495 + } else {
1.496 + assert(sym->storage() == VariableSymbol::Local);
1.497 + __ setlocal(sym);
1.498 + }
1.499 +}
1.500 +
1.501 +HIR *
1.502 +SemanticAnalysis::binary(TokenKind token, HIR *left, HIR *right)
1.503 +{
1.504 + Local<Type> coercion(zone_, coercionType(token, left, right));
1.505 + if (!coercion)
1.506 + return NULL;
1.507 + if ((left = coerce(left, coercion, Coerce_Arg)) == NULL)
1.508 + return NULL;
1.509 + if ((right = coerce(right, coercion, Coerce_Arg)) == NULL)
1.510 + return NULL;
1.511 +
1.512 + switch (token) {
1.513 + case TOK_PLUS:
1.514 + case TOK_MINUS:
1.515 + case TOK_STAR:
1.516 + case TOK_SLASH:
1.517 + case TOK_PERCENT:
1.518 + case TOK_AMPERSAND:
1.519 + case TOK_BITOR:
1.520 + case TOK_BITXOR:
1.521 + case TOK_SHR:
1.522 + case TOK_USHR:
1.523 + case TOK_SHL:
1.524 + return new (pool_) HBinary(left->type(), token, left, right);
1.525 +
1.526 + case TOK_EQUALS:
1.527 + case TOK_NOTEQUALS:
1.528 + case TOK_LT:
1.529 + case TOK_LE:
1.530 + case TOK_GT:
1.531 + case TOK_GE:
1.532 + case TOK_AND:
1.533 + case TOK_OR:
1.534 + {
1.535 + Local<Type> result(zone_, zone_->types()->getPrimitive(PrimitiveType_Bool));
1.536 + return new (pool_) HBinary(result, token, left, right);
1.537 + }
1.538 +
1.539 + default:
1.540 + assert(false);
1.541 + return NULL;
1.542 + }
1.543 +}
1.544 +
1.545 +static inline TokenKind
1.546 +ToCompare(Expression *expr)
1.547 +{
1.548 + if (expr->isBinaryExpression()) {
1.549 + BinaryExpression *b = expr->toBinaryExpression();
1.550 + if (b->token() >= TOK_EQUALS && b->token() <= TOK_OR)
1.551 + return b->token();
1.552 + } else if (expr->isUnaryExpression()) {
1.553 + UnaryExpression *u = expr->toUnaryExpression();
1.554 + if (u->token() == TOK_NOT)
1.555 + return TOK_NOT;
1.556 + }
1.557 + return TOK_EOF;
1.558 +}
1.559 +
1.560 +void
1.561 +SemanticAnalysis::visitForTest(Expression *expr,
1.562 + Label *trueBranch,
1.563 + Label *falseBranch,
1.564 + Label *fallthrough)
1.565 +{
1.566 + TokenKind token = ToCompare(expr);
1.567 + if (token == TOK_EOF || token == TOK_NOT) {
1.568 + assert(false);
1.569 + //visitForUnaryTest(expr, trueBranch, falseBranch, fallthrough);
1.570 + return;
1.571 + }
1.572 +
1.573 + BinaryExpression *bin = expr->toBinaryExpression();
1.574 + if (token == TOK_AND || token == TOK_OR) {
1.575 + assert(false);
1.576 + //visitForLogicTest(expr, trueBranch, falseBranch, fallthrough);
1.577 + return;
1.578 + }
1.579 +
1.580 + HIR *left = eval(bin->left());
1.581 + HIR *right = eval(bin->right());
1.582 + if (!left || !right)
1.583 + return;
1.584 +
1.585 + HIR *hir = binary(bin->token(), left, right);
1.586 + if (!hir)
1.587 + return;
1.588 +
1.589 + discharge(hir);
1.590 + if (fallthrough == trueBranch)
1.591 + __ j(OP_JF, falseBranch);
1.592 + else
1.593 + __ j(OP_JT, trueBranch);
1.594 +}
1.595 +
1.596 +HLValue *
1.597 +SemanticAnalysis::lvalue(Expression *expr)
1.598 +{
1.599 + HIR *hir = eval(expr);
1.600 + if (!hir)
1.601 + return NULL;
1.602 +
1.603 + if (!hir->isLValue()) {
1.604 + cc_.reportError(expr->pos(), Message_ExpectedLValue);
1.605 + return NULL;
1.606 + }
1.607 +
1.608 + return static_cast<HLValue *>(hir);
1.609 +}
1.610 +
1.611 +HIR *
1.612 +SemanticAnalysis::eval(Expression *expr)
1.613 +{
1.614 + assert(!hir_);
1.615 + expr->accept(this);
1.616 +
1.617 + HIR *hir = hir_;
1.618 + hir_ = NULL;
1.619 +
1.620 + return hir;
1.621 +}
1.622 +
1.623 +void
1.624 +SemanticAnalysis::discharge(HIR *hir)
1.625 +{
1.626 + EmitHIR(zone_, emitter_, hir);
1.627 +}
