src/compiler/SemanticAnalysis.cpp
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 251 ca99a81745fe
child 258 241d082d6d89
permissions -rw-r--r--
Initial implementation of module imports.
     1 /* vim: set ts=4 sw=4 tw=99 et:
     2  *
     3  * Copyright (C) 2012 David Anderson
     4  *
     5  * This file is part of SourcePawn.
     6  *
     7  * SourcePawn is free software: you can redistribute it and/or modify it under
     8  * the terms of the GNU General Public License as published by the Free
     9  * Software Foundation, either version 3 of the License, or (at your option)
    10  * any later version.
    11  * 
    12  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
    13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along with
    17  * SourcePawn. If not, see http://www.gnu.org/licenses/.
    18  */
    19 #include <assert.h>
    20 #include "../Zone.h"
    21 #include "../Strings.h"
    22 #include "../NativeTable.h"
    23 #include "../TypeManager.h"
    24 #include "../Modules.h"
    25 #include "../Code.h"
    26 #include "SemanticAnalysis.h"
    27 #include "../Heap-inl.h"
    28 
    29 using namespace ke;
    30 
    31 #define __ emitter_.
    32 
    33 typedef BytecodeEmitter::Label Label;
    34 
    35 class AutoEnterScope
    36 {
    37   public:
    38     AutoEnterScope(Scope **prevp, Scope *scope)
    39       : prevp_(prevp),
    40         prev_(*prevp),
    41         scope_(scope)
    42     {
    43         if (!scope_)
    44             return;
    45         prev_ = *prevp_;
    46         *prevp_ = scope;
    47         assert(prev_ == scope->enclosing());
    48     }
    49     ~AutoEnterScope()
    50     {
    51         if (scope_)
    52             *prevp_ = prev_;
    53     }
    54   private:
    55     Scope **prevp_;
    56     Scope *prev_;
    57     Scope *scope_;
    58 };
    59 
    60 SemanticAnalysis::SemanticAnalysis(Zone *zone, CompileContext &cc, TranslationUnit *unit)
    61   : zone_(zone),
    62     pool_(zone->pool()),
    63     cc_(cc),
    64     unit_(unit),
    65     hir_(NULL),
    66     emitter_(pool_),
    67     loop_(NULL)
    68 {
    69 }
    70 
    71 SemanticAnalysis::SemanticAnalysis(SemanticAnalysis *parent, Handle<FunctionType> fun)
    72   : zone_(parent->zone_),
    73     pool_(parent->pool_),
    74     cc_(parent->cc_),
    75     unit_(parent->unit_),
    76     hir_(NULL),
    77     scope_(parent->scope_),
    78     emitter_(pool_),
    79     fun_(fun),
    80     loop_(NULL),
    81     control_(NULL)
    82 {
    83 
    84 }
    85 
    86 void
    87 SemanticAnalysis::analyze()
    88 {
    89     scope_ = unit_->globalScope();
    90 
    91     for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
    92         Statement *stmt = unit_->tree()->statements()->at(i);
    93         stmt->accept(this);
    94     }
    95 
    96     Local<Code> code(zone_, __ finish());
    97     if (!code)
    98         return;
    99     code->setModule(unit_->module());
   100     unit_->module()->setCode(code);
   101 
   102 #ifndef NDEBUG
   103 //    Disassemble(code, stdout);
   104 #endif
   105 }
   106 
   107 void
   108 SemanticAnalysis::visitFunctionStatement(FunctionStatement *stmt)
   109 {
   110     FunctionSymbol *sym = stmt->sym();
   111     Local<FunctionType> type(zone_, sym->type());
   112 
   113     assert(scope_->kind() == Scope::GLOBAL);
   114 
   115     if (stmt->token() == TOK_NATIVE) {
   116         // Define the native now.
   117         size_t index;
   118         if (!zone_->nativeTable()->add(stmt->name(), &index))
   119             return;
   120 
   121         Local<Native> native(zone_, Native::New(zone_, type, index));
   122         if (!native)
   123             return;
   124 
   125         __ object(native);
   126         __ setglobal(sym);
   127         __ pop();
   128     }
   129 
   130     // If the function is a forward or native, we don't have to do anything.
   131     if (stmt->token() == TOK_NATIVE || stmt->token() == TOK_FORWARD)
   132         return;
   133 
   134     SemanticAnalysis child(this, type);
   135     Local<Function> funobj(zone_, child.compile(stmt));
   136     if (!funobj)
   137         return;
   138 
   139     __ object(funobj);
   140     __ setglobal(sym);
   141     if (stmt->token() == TOK_PUBLIC)
   142         __ public_();
   143     else
   144         __ pop();
   145 }
   146 
   147 Function *
   148 SemanticAnalysis::compile(FunctionStatement *stmt)
   149 {
   150     __ setFirstLine(stmt->pos().line);
   151 
   152     AutoEnterScope argScope(&scope_, stmt->argScope());
   153 
   154     for (size_t i = 0; i < stmt->signature().parameters()->length(); i++) {
   155         Parameter *param = stmt->signature().parameters()->at(i);
   156         param->sym()->allocate(VariableSymbol::Arg, i);
   157     }
   158 
   159     AutoEnterScope varScope(&scope_, stmt->varScope());
   160     ControlStatus status = visitForControl(stmt->body());
   161 
   162     if (!fun_->returnType()->isVoid()) {
   163         // If the function is not void, report if not all paths return a value.
   164         // All other incorrect return cases have been caught already.
   165         if (status.returns() == Returns_Sometimes) {
   166             cc_.reportError(stmt->pos(), Message_NotAllPathsReturnValue);
   167             return NULL;
   168         }
   169 
   170         if (status.returns() == Returns_Never) {
   171             cc_.reportError(stmt->pos(), Message_MissingReturnValue);
   172             return NULL;
   173         }
   174     }
   175 
   176     Local<Code> code(zone_, __ finish());
   177     if (!code)
   178         return NULL;
   179     code->setModule(unit_->module());
   180 
   181     Local<Function> fun(zone_, Function::New(zone_, code, fun_, stmt->name(), stmt->pos()));
   182     if (!fun)
   183         return NULL;
   184 
   185 #ifndef NDEBUG
   186 //    Disassemble(code, stdout);
   187 #endif
   188 
   189     return fun;
   190 }
   191 
   192 void 
   193 SemanticAnalysis::visitBlockStatement(BlockStatement *node)
   194 {
   195     AutoEnterScope scope(&scope_, node->scope());
   196 
   197     for (size_t i = 0; i < node->statements()->length(); i++) {
   198         Statement *stmt = node->statements()->at(i);
   199         __ note_position(stmt->pos());
   200         stmt->accept(this);
   201         assert(__ stackDepth() == 0);
   202     }
   203 }
   204 
   205 void
   206 SemanticAnalysis::visitEnumStatement(EnumStatement *node)
   207 {
   208 }
   209 
   210 void
   211 SemanticAnalysis::visitExpressionStatement(ExpressionStatement *node)
   212 {
   213     // While building HIR, we enter new pool and root scopes, since HIR
   214     // creation is purely temporary.
   215     PoolScope poolScope(zone_->pool());
   216     RootScope rootScope(zone_);
   217 
   218     HIR *hir = eval(node->expression());
   219     if (!hir)
   220         return;
   221 
   222     discharge(hir);
   223     if (!hir->type()->isVoid())
   224         __ pop();
   225 }
   226 
   227 void
   228 SemanticAnalysis::ControlScope::merge(const ControlStatus &left, const ControlStatus &right)
   229 {
   230     // If both sides terminate in a return, we consider this a return as well.
   231     if (left.returns() == Returns_Always && right.returns() == Returns_Always) {
   232         terminate(Returns_Always);
   233         return;
   234     }
   235 
   236     ReturnStatus status = (left.returns() == Returns_Never && right.returns() == Returns_Never)
   237                           ? Returns_Never
   238                           : Returns_Sometimes;
   239 
   240     if (left.terminates() && right.terminates())
   241         terminate(status);
   242     else
   243         returns(status);
   244 }
   245 
   246 SemanticAnalysis::ControlStatus
   247 SemanticAnalysis::visitForControl(Statement *statement)
   248 {
   249     ControlScope scope(&control_);
   250     statement->accept(this);
   251     return scope.status();
   252 }
   253 
   254 void
   255 SemanticAnalysis::visitIfStatement(IfStatement *node)
   256 {
   257     Label join;
   258 
   259     ControlStatus trueBranch;
   260     ControlStatus falseBranch(false, Returns_Never);
   261 
   262     if (!node->ifFalse()) {
   263         Label success;
   264 
   265         visitForTest(node->condition(), &success, &join, &success);
   266         __ bind(&success);
   267         trueBranch = visitForControl(node->ifTrue());
   268     } else {
   269         Label success, next;
   270 
   271         visitForTest(node->condition(), &success, &next, &success);
   272         __ bind(&success);
   273         trueBranch = visitForControl(node->ifTrue());
   274         __ jump(&join);
   275         __ bind(&next);
   276         falseBranch = visitForControl(node->ifFalse());
   277     }
   278 
   279     __ bind(&join);
   280 
   281     control_->merge(trueBranch, falseBranch);
   282 }
   283 
   284 void
   285 SemanticAnalysis::requireLifoStack()
   286 {
   287     if (!loop_)
   288         return;
   289 
   290     loop_->setUsesLifoStack();
   291 }
   292 
   293 SemanticAnalysis::ControlStatus
   294 SemanticAnalysis::visitLoopBody(Statement *stmt)
   295 {
   296     // We always mark off a loop body, so on each edge, we can balance the
   297     // LIFO stack. Right now, we don't have the ability to budget the LIFO
   298     // stack ahead of time. If we turn out to never need the LIFO stack, we
   299     // mark it as unnecessary. (The interpreter can't really make use of this,
   300     // but the JIT can).
   301     //
   302     // Note that balancing the LIFO stack isn't even necessary, so this
   303     // feature may be removed. All this mechanism does is mitigate the
   304     // possibility that a long-running loop will overflow the LIFO region
   305     // and therefore start requiring nursery allocations.
   306     int pos = __ enterloop();
   307     ControlStatus status = visitForControl(stmt);
   308     __ leaveloop();
   309 
   310     if (loop_->usesLifoStack())
   311         __ setLoopUsesLifoStack(pos);
   312 
   313     return status;
   314 }
   315 
   316 void
   317 SemanticAnalysis::visitForStatement(ForStatement *node)
   318 {
   319     AutoEnterScope scope(&scope_, node->scope());
   320     PoolScope poolScope(zone_->pool());
   321     RootScope rootScope(zone_);
   322 
   323     Label join, update;
   324     LoopScope loop(scope_, &join, &update, &loop_);
   325 
   326     if (node->initialization())
   327         node->initialization()->accept(this);
   328 
   329     Label header, test;
   330     if (node->condition())
   331         __ jump(&test);
   332 
   333     __ bind(&header);
   334     ControlStatus status = visitLoopBody(node->body());
   335 
   336     __ bind(&update);
   337     if (node->update())
   338         node->update()->accept(this);
   339 
   340     if (node->condition()) {
   341         __ bind(&test);
   342         visitForTest(node->condition(), &header, &join, &join);
   343     } else {
   344         __ jump(&header);
   345     }
   346 
   347     __ bind(&join);
   348     
   349     // If there was a condition, we treat this like a while loop. Otherwise,
   350     // the join point is only reachable if the loop contains a break. The
   351     // termination status doesn't tell us anything yet.
   352     if (node->condition() || loop.breaks())
   353         control_->merge(status, ControlStatus(false, Returns_Never));
   354     else
   355         control_->terminate(status.returns());
   356 
   357     assert(__ stackDepth() == 0);
   358 }
   359 
   360 void
   361 SemanticAnalysis::visitWhileStatement(WhileStatement *node)
   362 {
   363     PoolScope poolScope(zone_->pool());
   364     RootScope rootScope(zone_);
   365 
   366     Label header, join;
   367 
   368     __ bind(&header);
   369 
   370     ControlStatus status;
   371 
   372     LoopScope loop(scope_, &join, &header, &loop_);
   373     if (node->token() == TOK_WHILE) {
   374         Label body;
   375         visitForTest(node->condition(), &body, &join, &body);
   376         status = visitLoopBody(node->body());
   377         __ jump(&header);
   378     } else {
   379         status = visitLoopBody(node->body());
   380         visitForTest(node->condition(), &header, &join, &join);
   381     }
   382 
   383     __ bind(&join);
   384 
   385     // Detect loops that will always have a fork in the contro-flow graph.
   386     // This will be a |while| loop, or a |do-while| loop whose body does
   387     // not terminate. For now, we treat these as an |if| regardless of the
   388     // direction the branch can take. That means the control-flow is always
   389     // conditional.
   390     if (node->token() == TOK_WHILE || status.terminates() || loop.breaks()) {
   391         control_->merge(status, ControlStatus(false, Returns_Never));
   392     } else {
   393         // At this point, we've got a do-while loop with a |return| or
   394         // |continue|, meaning that the rest of the block is unreachable.
   395         control_->terminate(status.returns());
   396     }
   397 
   398     assert(__ stackDepth() == 0);
   399 }
   400 
   401 static inline Heap::Tenure
   402 InferTenure(Symbol *sym)
   403 {
   404     if (sym->scope()->kind() == Scope::GLOBAL)
   405         return Heap::Tenure_Old;
   406 
   407     // SP2's array semantics allow any array kind to escape, so we must use
   408     // the normal heap. (Hopefully escape analysis can ease this pain later).
   409     if (sym->type()->isArray())
   410         return Heap::Tenure_Default;
   411 
   412     return Heap::Tenure_Default;
   413 }
   414 
   415 void
   416 SemanticAnalysis::visitVariableDeclaration(VariableDeclaration *node)
   417 {
   418     PoolScope poolScope(zone_->pool());
   419     RootScope rootScope(zone_);
   420 
   421     Local<Type> type(zone_, node->sym()->type());
   422 
   423     if (node->sym()->type()->isVoid()) {
   424         cc_.reportError(node->type()->pos(), Message_CannotDeclareVoid);
   425         return;
   426     }
   427 
   428     if (node->initialization()) {
   429         HIR *hir = NULL;
   430 
   431         if ((hir = eval(node->initialization())) == NULL)
   432             return;
   433         if ((hir = coerce(hir, type, Coerce_Decl)) == NULL)
   434             return;
   435 
   436         discharge(hir);
   437     } else {
   438         if (type->isInt32() || type->isEnum() ||
   439             type->isChar() || type->isBool())
   440         {
   441             __ int_(0);
   442         } else if (type->isFloat()) {
   443             __ float_(0);
   444         } else if (type->isArray()) {
   445             Local<ArrayType> atype(zone_, ArrayType::cast(type));
   446             Local<ArrayMap> map(zone_, atype->newMap());
   447             if (!map)
   448                 return;
   449 
   450             if (atype->isFixedLength()) {
   451                 __ newarray(OP_NEWFIXED, map, InferTenure(node->sym()));
   452             } else if (node->dims()->at(0)) {
   453                 // This may not be true if we allow typedefing, so :TODO:
   454                 // figure out proper semantics.
   455                 assert(node->dims()->length() == atype->levels());
   456 
   457                 Local<Type> i32(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
   458                 for (size_t i = 0; i < node->dims()->length(); i++) {
   459                     Expression *expr = node->dims()->at(i);
   460                     if (expr) {
   461                         HIR *hir = eval(expr);
   462                         if (!hir || ((hir = coerce(hir, i32, Coerce_Arg)) == NULL))
   463                             return;
   464                         discharge(hir);
   465                     } else {
   466                         __ int_(0);
   467                     }
   468                 }
   469                 __ newarray(OP_NEWSIZED, map, InferTenure(node->sym()));
   470             } else {
   471                 __ newarray(OP_NEWEMPTY, map, InferTenure(node->sym()));
   472             }
   473         } else {
   474             assert(false);
   475         }
   476     }
   477 
   478     if (node->sym()->scope()->kind() != Scope::GLOBAL) {
   479         if (!__ allocate(node->sym()))
   480             return;
   481     }
   482 
   483     set(node->sym());
   484     __ pop();
   485 }
   486 
   487 void
   488 SemanticAnalysis::visitReturnStatement(ReturnStatement *node)
   489 {
   490     control_->returns(Returns_Always);
   491 
   492     if (!node->expression()) {
   493         if (!fun_->returnType()->isVoid()) {
   494             cc_.reportError(node->pos(), Message_MissingReturnValue);
   495             return;
   496         }
   497 
   498         __ returnvoid();
   499         return;
   500     }
   501 
   502     if (fun_->returnType()->isVoid()) {
   503         cc_.reportError(node->pos(), Message_UsedVoidReturn);
   504         return;
   505     }
   506 
   507     PoolScope poolScope(zone_->pool());
   508     RootScope rootScope(zone_);
   509 
   510     HIR *hir = eval(node->expression());
   511     if (!hir)
   512         return;
   513 
   514     Local<Type> returnType(zone_, fun_->returnType());
   515     if ((hir = coerce(hir, returnType, Coerce_Return)) == NULL)
   516         return;
   517 
   518     discharge(hir);
   519 
   520     if (hir->type()->isVoid())
   521         __ returnvoid();
   522     else
   523         __ return_();
   524 }
   525 
   526 void
   527 SemanticAnalysis::visitBinaryExpression(BinaryExpression *node)
   528 {
   529     HIR *left = eval(node->left());
   530     HIR *right = eval(node->right());
   531     if (!left || !right)
   532         return;
   533 
   534     hir_ = binary(node, node->token(), left, right);
   535 }
   536 
   537 bool
   538 SemanticAnalysis::checkArgumentCount(Handle<FunctionType> type, unsigned actual)
   539 {
   540     if (type->parameters()->length() == actual)
   541         return true;
   542 
   543     if (actual > type->parameters()->length()) {
   544         if (!type->isNative() || !type->isNativeVariadic())
   545             return false;
   546         return true;
   547     }
   548 
   549     if (!type->defaults())
   550         return false;
   551 
   552     // Missing arguments. See if there's a default argument for each missing
   553     // actual.
   554     for (unsigned i = actual; i < type->parameters()->length(); i++) {
   555         if (!type->defaults()->at(i))
   556             return false;
   557     }
   558 
   559     return true;
   560 }
   561 
   562 void
   563 SemanticAnalysis::visitNameProxy(NameProxy *proxy)
   564 {
   565     Symbol *sym = proxy->sym();
   566 
   567     switch (sym->kind()) {
   568       case Symbol::kImport:
   569       {
   570         ImportSymbol *import = sym->toImport();
   571         hir_ = new (pool_) HImport(proxy, sym->type(), import->index());
   572         break;
   573       }
   574 
   575       case Symbol::kConstant:
   576       {
   577         ConstantSymbol *val = sym->toConstant();
   578         hir_ = new (pool_) HInteger(proxy, sym->type(), val->value().toInt());
   579         break;
   580       }
   581       
   582       // This is kind of screwy. Symbol::kFunction is like a constant we can't
   583       // evaluate yet. Maybe we should extract the GLOBAL case and say that
   584       // kFunction is only used for global functions (and use const vars for
   585       // local functions).
   586       case Symbol::kFunction:
   587       case Symbol::kVariable:
   588       {
   589         Scope *in = sym->scope();
   590         switch (in->kind()) {
   591           case Scope::GLOBAL:
   592             hir_ = new (pool_) HGlobal(proxy, sym);
   593             break;
   594 
   595           case Scope::FUNCTION:
   596           {
   597             VariableSymbol *var = sym->toVariable();
   598             assert(var->storage() == VariableSymbol::Arg);
   599             hir_ = new (pool_) HLocal(proxy, var);
   600             break;
   601           }
   602 
   603           default:
   604           {
   605             VariableSymbol *var = sym->toVariable();
   606             assert(in->kind() == Scope::BLOCK);
   607             assert(var->storage() == VariableSymbol::Local);
   608             hir_ = new (pool_) HLocal(proxy, var);
   609             break;
   610           }
   611         }
   612         break;
   613       }
   614 
   615       default:
   616         // :TODO:
   617         assert(false);
   618     }
   619 }
   620 
   621 void
   622 SemanticAnalysis::visitBooleanLiteral(BooleanLiteral *node)
   623 {
   624     Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Bool));
   625     hir_ = new (pool_) HBoolean(node, type, node->token() == TOK_TRUE);
   626 }
   627 
   628 void
   629 SemanticAnalysis::visitIntegerLiteral(IntegerLiteral *lit)
   630 {
   631     Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
   632     hir_ = new (pool_) HInteger(lit, type, lit->value());
   633 }
   634 
   635 void
   636 SemanticAnalysis::visitFloatLiteral(FloatLiteral *node)
   637 {
   638     Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Float));
   639     hir_ = new (pool_) HFloat(node, type, (float)node->value());
   640 }
   641 
   642 void
   643 SemanticAnalysis::visitStringLiteral(StringLiteral *node)
   644 {
   645     Type *type = zone_->types()->getString();
   646     hir_ = new (pool_) HString(node, type, node->string());
   647 }
   648 
   649 void
   650 SemanticAnalysis::visitCallExpression(CallExpression *node)
   651 {
   652     HIR *callee = eval(node->callee());
   653     if (!callee)
   654         return;
   655 
   656     if (!callee->type()->isFunction()) {
   657         cc_.reportError(node->pos(), Message_CalleeNotFunction);
   658         return;
   659     }
   660 
   661     Local<FunctionType> fun(zone_, FunctionType::cast(callee->type()));
   662     
   663     if (!checkArgumentCount(fun, node->arguments()->length())) {
   664         cc_.reportError(node->pos(), Message_ArgumentCountMismatch);
   665         return;
   666     }
   667 
   668     if (fun->isForward()) {
   669         cc_.reportError(node->pos(), Message_ForwardNotImplemented, fun->name()->chars());
   670         return;
   671     }
   672 
   673     HIRList *args = new (pool_) HIRList;
   674     for (unsigned i = 0; i < node->arguments()->length(); i++) {
   675         Expression *expression = node->arguments()->at(i);
   676         HIR *arg = eval(expression);
   677         if (!arg)
   678             return;
   679 
   680         Handle<Type> given = arg->type();
   681         
   682         bool mustComputeReference;
   683         if (i >= fun->parameters()->length()) {
   684             // Special handling for natives. Arguments past the formal must
   685             // always have references computed. However, arrays are already
   686             // references for natives.
   687             assert(fun->isNative() && fun->isNativeVariadic());
   688             mustComputeReference = !given->isReference() &&
   689                                    !given->isArray();
   690         } else {
   691             Local<Type> actual(zone_, fun->parameterAt(i));
   692 
   693 
   694             if (expression->isIndexExpression() && arg->isIndex()) {
   695                 // If the expression is the form x[y], and this produced a
   696                 // normal array indexing operation, then we apply some 
   697                 // special rules.
   698 
   699                 if (actual->isReference()) {
   700                     // Disabled, since this doesn't have easily definable or
   701                     // sensible semantics with SP2 arrays, but we don't want
   702                     // to silently break SP1 semantics.
   703                     cc_.reportError(expression->pos(), Message_CannotComputeIndexRef);
   704                     return;
   705                 }
   706 
   707                 // As a special rule to account for SP1 semantics, we allow x[y]
   708                 // to automatically compute a sliced, read-only array view if
   709                 // the desired type is an array of one more dimension than x[y]
   710                 // would return.
   711                 //
   712                 // As an additional restriction, this is only allowed for
   713                 // one-level char arrays, to minimize potential issues until
   714                 // we determine whether more compatibility is needed.
   715                 //
   716                 // Internally, for sanity, the dependent array operation does
   717                 // not necessarily create a dependent array. For extensible
   718                 // arrays, we instead create a duplicate arrary of just the
   719                 // sliced portion, rather than deal with the complexity of the
   720                 // source array being resized.
   721                 //
   722                 // Note that we don't really know whether a dependent array
   723                 // will be dependent at compile-time, so the dependent type's
   724                 // just inherits from the source.
   725                 if (actual->isArray()) {
   726                     HIndex *index = arg->toIndex();
   727                     Local<ArrayType> basetype(zone_, ArrayType::cast(index->base()->type()));
   728                     Local<ArrayType> atype(zone_, ArrayType::cast(actual));
   729 
   730                     if (atype->isCharArray() && basetype->isCharArray()) {
   731                         // There is no possible way this will type check, so
   732                         // it's safe to just try something completely
   733                         // different.
   734                         Local<Type> slicetype(zone_);
   735                         if (basetype->isFixedLength()) {
   736                             // If the base type is fixed length, we need to
   737                             // compute a new dynamic array type based on the
   738                             // fixed array's contents and qualifiers.
   739                             Local<Type> contained(zone_, basetype->contained());
   740                             slicetype = zone_->types()->newArray(contained, ArrayType::DYNAMIC_ARRAY_SIZE);
   741                             if (!slicetype)
   742                                 return;
   743                             slicetype = zone_->types()->qualify(slicetype, basetype->quals());
   744                             if (!slicetype)
   745                                 return;
   746                         } else {
   747                             slicetype = basetype;
   748                         }
   749                         arg = new (pool_) HNewDependentArray(expression, slicetype, index->base(), index->index());
   750                         given = arg->type();
   751                     }
   752                 }
   753             }
   754 
   755             if (actual->isReference()) {
   756                 // If the actual is a reference, the coercion rules are much
   757                 // stricter; the contained types must be identical.
   758                 // :TODO: make this not an assert
   759                 assert(ReferenceType::cast(actual)->contained() == arg->type());
   760             } else {
   761                 // When we start overloading, coercion will have to happen later.
   762                 arg = coerce(arg, actual, Coerce_Arg);
   763                 if (!arg)
   764                     return;
   765             }
   766 
   767             mustComputeReference = actual->isReference() && !given->isReference();
   768         }
   769 
   770         if (mustComputeReference) {
   771             // Refs always use the LIFO stack if they can.
   772             arg = new (pool_) HToRef(arg->node(), arg->type(), arg);
   773             requireLifoStack();
   774         }
   775 
   776         if (!args->append(arg))
   777             return;
   778     }
   779 
   780     hir_ = new (pool_) HCall(node, fun->returnType(), callee, args);
   781 }
   782 
   783 void
   784 SemanticAnalysis::visitAssignment(Assignment *node)
   785 {
   786     HLValue *lval = lvalue(node->lvalue());
   787     if (!lval)
   788         return;
   789 
   790     if (lval->type()->quals() & TypeQual_Const) {
   791         cc_.reportError(node->pos(), Message_CannotModifyConst);
   792         return;
   793     }
   794 
   795     HIR *hir = eval(node->expression());
   796     if (!hir)
   797         return;
   798     if ((hir = coerce(hir, lval->type(), Coerce_Assign)) == NULL)
   799         return;
   800 
   801     hir_ = new (pool_) HStore(node, node->token(), lval, hir);
   802 }
   803 
   804 void
   805 SemanticAnalysis::visitBreakStatement(BreakStatement *node)
   806 {
   807     if (!loop_) {
   808         cc_.reportError(node->pos(), Message_BreakOutsideLoop);
   809         return;
   810     }
   811 
   812     loop_->setBreaks();
   813     __ j(OP_BREAK, loop_->break_());
   814 }
   815 
   816 void
   817 SemanticAnalysis::visitContinueStatement(ContinueStatement *node)
   818 {
   819     if (!loop_) {
   820         cc_.reportError(node->pos(), Message_ContinueOutsideLoop);
   821         return;
   822     }
   823 
   824     __ j(OP_CONTINUE, loop_->continue_());
   825 }
   826 
   827 void
   828 SemanticAnalysis::visitIndexExpression(IndexExpression *node)
   829 {
   830     HIR *left = eval(node->left());
   831     if (!left)
   832         return;
   833 
   834     HIR *right = eval(node->right());
   835     if (!right)
   836         return;
   837 
   838     // Hrm... yes, for now, let's coerce here.
   839     Local<Type> i32(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
   840     if ((right = coerce(right, i32, Coerce_Arg)) == NULL)
   841         return;
   842     
   843     // Do not coerce here, there's no reason to yet.
   844     if (!left->type()->isArray()) {
   845         cc_.reportError(node->left()->pos(), Message_IndexBaseMustBeArray);
   846         return;
   847     }
   848 
   849     hir_ = new (pool_) HIndex(node,
   850                               ArrayType::cast(left->type())->contained(),
   851                               left,
   852                               right);
   853 }
   854 
   855 void
   856 SemanticAnalysis::visitIncDecExpression(IncDecExpression *node)
   857 {
   858     HLValue *lval = lvalue(node->expression());
   859     if (!lval)
   860         return;
   861 
   862     if (!lval->type()->isInt32() && !lval->type()->isFloat()) {
   863         assert(false);
   864         return;
   865     }
   866 
   867     HIR *rval;
   868     if (lval->type()->isInt32())
   869         rval = new (pool_) HInteger(node, lval->type(), 1);
   870     else
   871         rval = new (pool_) HFloat(node, lval->type(), 1.0);
   872 
   873     if (node->postfix())
   874         hir_ = new (pool_) HPostIncDec(node, node->token(), lval, rval);
   875     else
   876         hir_ = new (pool_) HStore(node, node->token(), lval, rval);
   877 }
   878 
   879 Type *
   880 SemanticAnalysis::coercionType(TokenKind token, HIR *left, HIR *right)
   881 {
   882     Local<Type> l(zone_, left->type());
   883     Local<Type> r(zone_, right->type());
   884 
   885     if (l->isPod())
   886         l = l->unqualified();
   887     if (r->isPod())
   888         r = r->unqualified();
   889 
   890     if ((token >= TOK_PLUS && token <= TOK_SLASH) ||
   891         (token >= TOK_EQUALS && token <= TOK_GE))
   892     {
   893         // We allow: [float|int32] + [float|int32]
   894         if (l->isFloat() && r->isInt32())
   895             return l;
   896         if (l->isInt32() && r->isFloat())
   897             return r;
   898         if (l->isInt32() && r->isInt32())
   899             return l;
   900 
   901         if (l->isChar() && r->isInt32())
   902              return r;
   903         if (l->isInt32() && r->isChar())
   904             return l;
   905     }
   906 
   907     // :TODO: remove
   908     assert(*l == *r);
   909 
   910     return left->type();
   911 }
   912 
   913 HIR *
   914 SemanticAnalysis::typeCheckArray(const SourcePosition &pos,
   915                                  HIR *from,
   916                                  Handle<ArrayType> argActual,
   917                                  CoercionKind kind)
   918 {
   919     Local<Type> argGiven(zone_, from->type());
   920 
   921     // Special case: if we receive a string literal, and this is a char array,
   922     // we allow a coercion.
   923     if (from->isString() &&
   924         argGiven->isString() &&
   925         argActual->isArray() &&
   926         ArrayType::cast(argActual)->isCharArray())
   927     {
   928         HString *hir = from->toString();
   929         Local<ArrayType> actual(zone_, ArrayType::cast(argActual));
   930 
   931         if (actual->isFixedLength()) {
   932             if (hir->string()->length() + 1 > actual->fixedLength()) {
   933                 cc_.reportError(pos, Message_ArrayAssignmentTooBig);
   934                 return NULL;
   935             }
   936         }
   937 
   938         // Transform the string literal into an array literal. We give it the
   939         // type of the left-hand side. The constness of the destination type
   940         // will determine whether HArray duplicates it or not.
   941         Local<ArrayMap> map(zone_, actual->newMap());
   942         if (!map)
   943             return NULL;
   944 
   945         Local<Array> array(zone_);
   946         array = Array::NewString(zone_,
   947                                  map,
   948                                  hir->string()->chars(),
   949                                  hir->string()->length(),
   950                                  Heap::Tenure_Old);
   951         if (!array)
   952             return NULL;
   953 
   954         // Since we're creating a canonical copy of the char array, we have to
   955         // be careful that it doesn't get mutated. There are two cases where
   956         // we know it can't be mutated, and therefore don't need to specify
   957         // that it be cloned after pushing it onto the stack.
   958         //
   959         //  (1) The array type is const.
   960         //  (2) The array type is fixed-length, and the coercion is for
   961         //      assignment, meaning it will be immediately copied.
   962         //
   963         // We treat declaration separately from assignment, since for
   964         // declaration we can just immediately use the cloned version.
   965         bool shouldDuplicate = true;
   966         if ((actual->quals() & TypeQual_Const) ||
   967             (actual->isFixedLength() && kind == Coerce_Assign))
   968         {
   969             shouldDuplicate = false;
   970         }
   971 
   972         return new (pool_) HArray(hir->node(), actual, array, shouldDuplicate);
   973     }
   974 
   975     if (!argGiven->isArray()) {
   976         cc_.reportError(pos, Message_ExpectedArray);
   977         return NULL;
   978     }
   979 
   980     Local<ArrayType> actual(zone_, ArrayType::cast(argActual));
   981     Local<ArrayType> given(zone_, ArrayType::cast(argGiven));
   982 
   983     if (actual->levels() != given->levels()) {
   984         cc_.reportError(pos, Message_ArrayDimensionsMismatch);
   985         return NULL;
   986     }
   987 
   988     unsigned level = 1;
   989     while (true) {
   990         if (actual->isFixedLength()) {
   991             if (!given->isFixedLength()) {
   992                 cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);
   993                 return NULL;
   994             }
   995 
   996             if (actual->isCharArray()) {
   997                 // String assignment can have a truncated |given|.
   998                 if (given->fixedLength() > actual->fixedLength()) {
   999                     cc_.reportError(pos, Message_ArrayAssignmentTooBig);
  1000                     return NULL;
  1001                 }
  1002             } else {
  1003                 if (given->fixedLength() != actual->fixedLength()) {
  1004                     cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);
  1005                     return NULL;
  1006                 }
  1007             }
  1008         } else if (given->isFixedLength()) {
  1009             // We do not allow assignments in the form:
  1010             //  [][] = [][Y]
  1011             //
  1012             // Otherwise, the following code could break the size guarantees
  1013             // of the right-hand side:
  1014             //
  1015             //  new x[][5];
  1016             //  new y[][];
  1017             //  new z[3];
  1018             //
  1019             //
  1020             //  y = x;
  1021             //  y[0] = z;
  1022             //
  1023             // Now |x[0]| contains a 3-length array.
  1024             if (level > 1) {
  1025                 cc_.reportError(pos, Message_ArrayDimensionSizeMismatch, level);
  1026                 return NULL;
  1027             }
  1028         }
  1029 
  1030         if (!given->contained()->isArray() || !actual->contained()->isArray())
  1031             break;
  1032 
  1033         given = ArrayType::cast(given->contained());
  1034         actual = ArrayType::cast(actual->contained());
  1035     }
  1036 
  1037     bool givenConst = !!(given->contained()->quals() & TypeQual_Const);
  1038     bool actualConst = !!(actual->contained()->quals() & TypeQual_Const);
  1039 
  1040     // These arrays must contain the same innermost type.
  1041     if (given->contained()->unqualified() != actual->contained()->unqualified() ||
  1042         (givenConst && !actualConst))
  1043     {
  1044         char aname[255];
  1045         char gname[255];
  1046         cc_.reportError(pos, Message_TypeMismatch,
  1047                         GetTypeName(argActual, aname, sizeof(aname)),
  1048                         GetTypeName(argGiven, gname, sizeof(gname)));
  1049         return NULL;
  1050     }
  1051 
  1052     return from;
  1053 }
  1054 
  1055 HIR *
  1056 SemanticAnalysis::typeFailure(const SourcePosition &pos, Handle<Type> from, Handle<Type> to)
  1057 {
  1058     char fname[255];
  1059     char tname[255];
  1060     cc_.reportError(pos, Message_InvalidCoercion,
  1061                     GetTypeName(from, fname, sizeof(fname)),
  1062                     GetTypeName(to, tname, sizeof(tname)));
  1063     return NULL;
  1064 }
  1065 
  1066 HIR *
  1067 SemanticAnalysis::coerce(HIR *hir, Handle<Type> to, CoercionKind kind)
  1068 {
  1069     Local<Type> from(zone_, hir->type());
  1070 
  1071     // If the source is *ever* an importable, we just fail.
  1072     if (from->isImportable())
  1073         return typeFailure(hir->node()->pos(), from, to);
  1074 
  1075     if (from->isInt32() && to->isFloat())
  1076         return new (pool_) HConvert(hir->node(), to, OP_CVT_I2F, hir);
  1077     if (from->isInt32() && to->isBool())
  1078         return new (pool_) HConvert(hir->node(), to, OP_CVT_I2B, hir);
  1079 
  1080     if (to->isEnum() && *from != to)
  1081         return typeFailure(hir->node()->pos(), from, to);
  1082     
  1083     if (to->isArray()) {
  1084         Local<ArrayType> atype(zone_, ArrayType::cast(to));
  1085         return typeCheckArray(hir->node()->pos(), hir, atype, kind);
  1086     }
  1087     
  1088     return hir;
  1089 }
  1090 
  1091 void
  1092 SemanticAnalysis::set(VariableSymbol *sym)
  1093 {
  1094     if (sym->scope()->kind() == Scope::GLOBAL) {
  1095         __ setglobal(sym);
  1096     } else {
  1097         assert(sym->storage() == VariableSymbol::Local);
  1098         __ setlocal(sym);
  1099     }
  1100 }
  1101 
  1102 HIR *
  1103 SemanticAnalysis::binary(AstNode *node, TokenKind token, HIR *left, HIR *right)
  1104 {
  1105     Local<Type> coercion(zone_, coercionType(token, left, right));
  1106     if (!coercion)
  1107         return NULL;
  1108     if ((left = coerce(left, coercion, Coerce_Arg)) == NULL)
  1109         return NULL;
  1110     if ((right = coerce(right, coercion, Coerce_Arg)) == NULL)
  1111         return NULL;
  1112     
  1113     switch (token) {
  1114      case TOK_PLUS:
  1115       case TOK_MINUS:
  1116       case TOK_STAR:
  1117       case TOK_SLASH:
  1118       case TOK_PERCENT:
  1119       case TOK_AMPERSAND:
  1120       case TOK_BITOR:
  1121       case TOK_BITXOR:
  1122       case TOK_SHR:
  1123       case TOK_USHR:
  1124       case TOK_SHL:
  1125         return new (pool_) HBinary(node, left->type(), token, left, right);
  1126 
  1127       case TOK_EQUALS:
  1128       case TOK_NOTEQUALS:
  1129       case TOK_LT:
  1130       case TOK_LE:
  1131       case TOK_GT:
  1132       case TOK_GE:
  1133       case TOK_AND:
  1134       case TOK_OR:
  1135       {
  1136         Local<Type> result(zone_, zone_->types()->getPrimitive(PrimitiveType_Bool));
  1137         return new (pool_) HBinary(node, result, token, left, right);
  1138       }
  1139 
  1140       default:
  1141         assert(false);
  1142         return NULL;
  1143     }
  1144 }
  1145 
  1146 static inline bool
  1147 IsValidUncheckedType(Type *type)
  1148 {
  1149     return type->isEnum() ||
  1150            type->isFloat() ||
  1151            type->isInt32() ||
  1152            type->isChar() ||
  1153            type->isUnchecked() ||
  1154            type->isBool();
  1155 }
  1156 
  1157 void
  1158 SemanticAnalysis::visitUnaryExpression(UnaryExpression *node)
  1159 {
  1160     HIR *hir = eval(node->expression());
  1161     if (!hir)
  1162         return;
  1163 
  1164     switch (node->token()) {
  1165       case TOK_TILDE:
  1166       {
  1167         if (!hir->type()->isInt32() && !hir->type()->isEnum()) {
  1168             char name[255];
  1169             cc_.reportError(node->pos(), Message_InvalidUnaryType,
  1170                             "~",
  1171                             GetTypeName(hir->type(), name, sizeof(name)));
  1172         }
  1173         Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
  1174         hir_ = new (pool_) HUnary(node, hir->type(), TOK_TILDE, hir);
  1175         return;
  1176       }
  1177 
  1178       case TOK_MINUS:
  1179       {
  1180         if (hir->type()->isInt32() || hir->type()->isEnum()) {
  1181             Local<Type> type(zone_, zone_->types()->getPrimitive(PrimitiveType_Int32));
  1182             hir_ = new (pool_) HUnary(node, type, TOK_MINUS, hir);
  1183             return;
  1184         }
  1185         if (hir->type()->isFloat()) {
  1186             hir_ = new (pool_) HUnary(node, hir->type(), TOK_MINUS, hir);
  1187             return;
  1188         }
  1189 
  1190         char name[255];
  1191         cc_.reportError(node->pos(), Message_InvalidUnaryType,
  1192                         "-",
  1193                         GetTypeName(hir->type(), name, sizeof(name)));
  1194         break;
  1195       }
  1196 
  1197       default:
  1198       {
  1199         assert(node->token() == TOK_LABEL);
  1200 
  1201         TypeSymbol *sym = node->tag()->sym()->asType();
  1202         if (!sym) {
  1203             cc_.reportError(node->pos(), Message_IdentifierIsNotAType,
  1204                             sym->name()->chars());
  1205             return;
  1206         }
  1207 
  1208         if (!IsValidUncheckedType(sym->type())) {
  1209             char name[255];
  1210             cc_.reportError(node->pos(), Message_InvalidUncheckedCastTo,
  1211                             GetTypeName(hir->type(), name, sizeof(name)));
  1212             return;
  1213         }
  1214         if (!IsValidUncheckedType(hir->type())) {
  1215             char name[255];
  1216             cc_.reportError(node->pos(), Message_InvalidUncheckedCastFrom,
  1217                             GetTypeName(hir->type(), name, sizeof(name)));
  1218             return;
  1219         }
  1220 
  1221         hir_ = new (pool_) HUnary(node, hir->type(), TOK_LABEL, hir);
  1222         break;
  1223       }
  1224     }
  1225 }
  1226 
  1227 void
  1228 SemanticAnalysis::import(HIR *hir, FieldExpression *node)
  1229 {
  1230     // Note that we don't care if the hir type is "importable", since we
  1231     // can only do anything if the important has a constant binding.
  1232     unsigned index = hir->toImport()->index();
  1233     Local<Importable> importable(zone_, unit_->module()->getImportAt(index));
  1234 
  1235     if (importable->isPackage()) {
  1236         // Look at what's already loaded and see if anything exists. We
  1237         // can't create stuff on-demand here since it's too late to add
  1238         // new translation units to the CompileContext.
  1239         Local<Package> package(zone_, Package::cast(importable));
  1240         Local<Importable> found(zone_, package->import(node->field()));
  1241         if (!found) {
  1242             cc_.reportError(node->pos(), Message_PackageDoesNotHaveMember, node->field()->chars());
  1243             return;
  1244         }
  1245 
  1246         // If we did find something, make sure it is in our import list.
  1247         // If we didn't explicitly import it, we have no right to use it.
  1248         for (index = 0; index < unit_->module()->imports(); index++) {
  1249             if (unit_->module()->getImportAt(index) == importable)
  1250                 break;
  1251         }
  1252 
  1253         if (index == unit_->module()->imports()) {
  1254             cc_.reportError(node->pos(), Message_ImportWasNeverImported, node->field()->chars());
  1255             return;
  1256         }
  1257 
  1258         // Just create a new HImport.
  1259         hir_ = new (pool_) HImport(node, hir->type(), index);
  1260     } else {
  1261         // Modules can never have sub-modules or sub-packages.
  1262         unsigned index;
  1263         Local<Module> module(zone_, Module::cast(importable));
  1264         Local<StructMap> map(zone_, module->globals()->map());
  1265         Local<Descriptor> desc(zone_, map->type()->lookupField(node->field(), &index));
  1266         if (!desc) {
  1267             cc_.reportError(node->pos(), Message_FieldNotFound, node->field()->chars());
  1268             return;
  1269         }
  1270         hir_ = new (pool_) HField(node, hir, desc->type(), index);
  1271     }
  1272 }
  1273 
  1274 void
  1275 SemanticAnalysis::visitFieldExpression(FieldExpression *node)
  1276 {
  1277     HIR *hir = eval(node->left());
  1278     if (!hir)
  1279         return;
  1280 
  1281     if (hir->isImport()) {
  1282         import(hir, node);
  1283         return;
  1284     }
  1285 
  1286     char name[255];
  1287     cc_.reportError(node->pos(), Message_InvalidFieldExpression,
  1288                     GetTypeName(hir->type(), name, sizeof(name)));
  1289 }
  1290 
  1291 static inline TokenKind
  1292 ToCompare(Expression *expr)
  1293 {
  1294     if (expr->isBinaryExpression()) {
  1295         BinaryExpression *b = expr->toBinaryExpression();
  1296         if (b->token() >= TOK_EQUALS && b->token() <= TOK_OR)
  1297             return b->token();
  1298     } else if (expr->isUnaryExpression()) {
  1299         UnaryExpression *u = expr->toUnaryExpression();
  1300         if (u->token() == TOK_NOT)
  1301             return TOK_NOT;
  1302     }
  1303     return TOK_EOF;
  1304 }
  1305 
  1306 void
  1307 SemanticAnalysis::visitForTest(Expression *expr,
  1308                                Label *trueBranch,
  1309                                Label *falseBranch,
  1310                                Label *fallthrough)
  1311 {
  1312     Local<Type> boolType(zone_, zone_->types()->getPrimitive(PrimitiveType_Bool));
  1313 
  1314     TokenKind token = ToCompare(expr);
  1315     if (token == TOK_EOF || token == TOK_NOT) {
  1316         HIR *hir;
  1317         if (token == TOK_EOF)
  1318             hir = eval(expr);
  1319         else
  1320             hir = eval(expr->toUnaryExpression()->expression());
  1321         if (!hir)
  1322             return;
  1323         if ((hir = coerce(hir, boolType, Coerce_Arg)) == NULL)
  1324             return;
  1325 
  1326         discharge(hir);
  1327 
  1328         bool jumpOnTrue = (fallthrough == falseBranch) ^ (token == TOK_NOT);
  1329         Opcode op = jumpOnTrue ? OP_JT : OP_JF;
  1330         
  1331         if (fallthrough == falseBranch)
  1332             __ j(op, trueBranch);
  1333         else
  1334             __ j(op, falseBranch);
  1335         return;
  1336     }
  1337 
  1338     BinaryExpression *bin = expr->toBinaryExpression();
  1339     if (token == TOK_AND || token == TOK_OR) {
  1340         Label next;
  1341         if (token == TOK_AND)
  1342             visitForTest(bin->left(), &next, falseBranch, &next);
  1343         else
  1344             visitForTest(bin->left(), trueBranch, &next, &next);
  1345         __ bind(&next);
  1346         visitForTest(bin->right(), trueBranch, falseBranch, fallthrough);
  1347         return;
  1348     }
  1349 
  1350     HIR *left = eval(bin->left());
  1351     HIR *right = eval(bin->right());
  1352     if (!left || !right)
  1353         return;
  1354 
  1355     HIR *hir = binary(bin, bin->token(), left, right);
  1356     if (!hir)
  1357         return;
  1358     if ((hir = coerce(hir, boolType, Coerce_Arg)) == NULL)
  1359         return;
  1360 
  1361     discharge(hir);
  1362     if (fallthrough == trueBranch)
  1363         __ j(OP_JF, falseBranch);
  1364     else
  1365         __ j(OP_JT, trueBranch);
  1366 }
  1367 
  1368 HLValue *
  1369 SemanticAnalysis::lvalue(Expression *expr)
  1370 {
  1371     HIR *hir = eval(expr);
  1372     if (!hir)
  1373         return NULL;
  1374     
  1375     if (!hir->isLValue()) {
  1376         cc_.reportError(expr->pos(), Message_ExpectedLValue);
  1377         return NULL;
  1378     }
  1379 
  1380     return static_cast<HLValue *>(hir);
  1381 }
  1382 
  1383 HIR *
  1384 SemanticAnalysis::eval(Expression *expr)
  1385 {
  1386     assert(!hir_);
  1387     expr->accept(this);
  1388 
  1389     HIR *hir = hir_;
  1390     hir_ = NULL;
  1391 
  1392     return hir;
  1393 }
  1394 
  1395 void
  1396 SemanticAnalysis::discharge(HIR *hir)
  1397 {
  1398     EmitHIR(zone_, emitter_, hir);
  1399 }