src/compiler/NameBinding.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 257 9db4cc815ebc
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 "../Strings.h"
    20 #include "../Zone.h"
    21 #include "../TypeManager.h"
    22 #include "NameBinding.h"
    23 #include "Scopes.h"
    24 #include "ConstantEvaluator.h"
    25 #include "../Spaces-inl.h"
    26 #include "../Heap-inl.h"
    27 
    28 using namespace ke;
    29 
    30 // Create symbol tables and symbols for every scope and declaration. For type
    31 // declarations and methods, we also pre-allocate a Type object, so that
    32 // circular dependencies between types will work.
    33 class NamePopulator : public AstVisitor
    34 {
    35   private:
    36     // This class is analagous to a Scope, however, it allows us to create
    37     // scopes lazily. If a scope is requested, and the current environment
    38     // has no scope, then a scope is created. If no scope is ever requested,
    39     // a scope does not need to be created.
    40     class SymbolEnv
    41     {
    42       public:
    43         SymbolEnv(SymbolEnv **prevp, Scope *scope = NULL)
    44           : envp_(prevp),
    45             prev_(*prevp),
    46             scope_(scope)
    47         {
    48             *envp_ = this;
    49         }
    50         ~SymbolEnv() {
    51             *envp_ = prev_;
    52         }
    53 
    54         Scope *scope() {
    55             return scope_;
    56         }
    57         void setScope(Scope *scope) {
    58             assert(!scope_);
    59             scope_ = scope;
    60         }
    61         SymbolEnv *prev() const {
    62             return prev_;
    63         }
    64 
    65       private:
    66         SymbolEnv **envp_;
    67         SymbolEnv *prev_;
    68         Scope *scope_;
    69     };
    70 
    71     enum ReturnStatus {
    72         NoReturn,
    73         VoidReturn,
    74         ValueReturn
    75     };
    76 
    77     class FunctionScope
    78     {
    79       public:
    80         FunctionScope(FunctionScope **prevp)
    81           : prevp_(prevp),
    82             prev_(*prevp),
    83             status_(NoReturn)
    84         {
    85             *prevp_ = this;
    86         }
    87         ~FunctionScope() {
    88             *prevp_ = prev_;
    89         }
    90         ReturnStatus returns() const {
    91             return status_;
    92         }
    93         void returns(ReturnStatus status) {
    94             if (status > status_)
    95                 status_ = status;
    96         }
    97       private:
    98         FunctionScope **prevp_;
    99         FunctionScope *prev_;
   100         ReturnStatus status_;
   101     };
   102 
   103   public:
   104     NamePopulator(Zone *zone, CompileContext &cc, TranslationUnit *unit)
   105       : zone_(zone),
   106         pool_(zone->pool()),
   107         cc_(cc),
   108         unit_(unit),
   109         env_(NULL),
   110         fun_(NULL)
   111     {
   112     }
   113 
   114     void analyze() {
   115         ImportScope *importScope = ImportScope::New(pool_);
   116         if (!importScope)
   117             return;
   118 
   119         // At the import level, we declare system types.
   120         if (!declareSystemTypes(importScope))
   121             return;
   122 
   123         GlobalScope *globalScope = GlobalScope::New(pool_, importScope);
   124         if (!globalScope)
   125             return;
   126 
   127         unit_->setImportScope(importScope);
   128         unit_->setGlobalScope(globalScope);
   129 
   130         SymbolEnv env(&env_, globalScope);
   131 
   132         for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
   133             Statement *stmt = unit_->tree()->statements()->at(i);
   134             stmt->accept(this);
   135         }
   136 
   137         return;
   138     }
   139 
   140     bool declareSystemType(ImportScope *scope, const char *name, Handle<Type> type) {
   141         Local<String> tag(zone_, zone_->makeSymbol(name));
   142         if (!tag)
   143             return false;
   144 
   145         TypeSymbol *sym = new (pool_) TypeSymbol(scope, tag, type);
   146         return scope->addSymbol(sym);
   147     }
   148 
   149     bool declareSystemType(ImportScope *scope, const char *name, PrimitiveType prim) {
   150         Local<Type> primitive(zone_, zone_->types()->getPrimitive(prim));
   151         assert(primitive);
   152         return declareSystemType(scope, name, primitive);
   153     }
   154 
   155     bool declareSystemTypes(ImportScope *scope) {
   156         if (!declareSystemType(scope, "float", PrimitiveType_Float))
   157             return false;
   158         if (!declareSystemType(scope, "_", PrimitiveType_Int32))
   159             return false;
   160         if (!declareSystemType(scope, "int", PrimitiveType_Int32))
   161             return false;
   162         if (!declareSystemType(scope, "bool", PrimitiveType_Bool))
   163             return false;
   164         if (!declareSystemType(scope, "char", PrimitiveType_Char))
   165             return false;
   166 
   167         Local<Type> voidType(zone_, zone_->types()->getVoid());
   168         if (!declareSystemType(scope, "void", voidType))
   169             return false;
   170 
   171         return true;
   172     }
   173 
   174     void visitVariableDeclaration(VariableDeclaration *node) {
   175         Scope *scope = env_->scope();
   176         if (!scope || scope->kind() != Scope::GLOBAL) {
   177             if ((scope = getOrCreateBlockScope()) == NULL)
   178                 return;
   179         }
   180 
   181         if (scope->kind() == Scope::GLOBAL) {
   182             // The symbol must be added now, since it could be an export.
   183             VariableSymbol *sym = new (pool_) VariableSymbol(scope, node->name(), node->pos());
   184             node->setSymbol(sym);
   185 
   186             if (!registerName(scope, sym))
   187                 return;
   188         } else {
   189             // We ensure the scope will exist at the name binding phase, but
   190             // we don't actually register the variable symbol yet. Otherwise,
   191             // when binding the initializer, we could encounter:
   192             //    new x = x;
   193             //
   194             // And we don't necessarily want this to bind.
   195         }
   196 
   197         if (node->initialization())
   198             node->initialization()->accept(this);
   199     }
   200 
   201     void visitEnumStatement(EnumStatement *node) {
   202         Local<String> name(zone_, node->name());
   203         Local<Type> type(zone_);
   204         if (name)
   205             type = zone_->types()->newEnum(name);
   206         else
   207             type = zone_->types()->getPrimitive(PrimitiveType_Int32);
   208 
   209         if (!type)
   210             return;
   211 
   212         Scope *scope = getGlobalOrCreateBlockScope();
   213         if (!scope)
   214             return;
   215 
   216         if (name) {
   217             TypeSymbol *sym = new (pool_) TypeSymbol(scope, name, type);
   218             if (!registerName(scope, sym))
   219                 return;
   220         }
   221 
   222         int value = 0;
   223         for (size_t i = 0; i < node->entries()->length(); i++) {
   224             EnumStatement::Entry &entry = node->entries()->at(i);
   225             BoxedPrimitive box = BoxedPrimitive::Int(value);
   226             if (entry.expr) {
   227                 if (!EvaluateForConstant(entry.expr, &box) || box.type() != PrimitiveType_Int32) {
   228                     cc_.reportError(entry.expr->pos(), Message_EnumFieldNotConstant);
   229                     return;
   230                 }
   231 
   232                 assert(box.type() == PrimitiveType_Int32);
   233                 value = box.toInt();
   234             }
   235             
   236             ConstantSymbol *sym = new (pool_) ConstantSymbol(scope, entry.name, entry.pos, type, box);
   237             if (!registerName(scope, sym))
   238                 return;
   239 
   240             value++;
   241         }
   242     }
   243 
   244     void visitFunctionStatement(FunctionStatement *node) {
   245         // We create function types ahead of time, not for any particular
   246         // reason. It makes things consistent with FunctionTypeStatement,
   247         // which actually does produce a type.
   248         Local<FunctionType> type(zone_, FunctionType::New(zone_, node->name(), node->token()));
   249         if (!type)
   250             return;
   251 
   252         assert(env_->scope());
   253 
   254         // Function statements are always named, so add the name to the outer scope.
   255         FunctionSymbol *sym = new (pool_) FunctionSymbol(env_->scope(), node->name(), node->pos(), type);
   256         if (!registerName(env_->scope(), sym))
   257             return;
   258 
   259         if (node->token() == TOK_PUBLIC ||
   260             node->token() == TOK_FORWARD ||
   261             node->token() == TOK_NATIVE)
   262         {
   263             // We're in the global scope, for sure.
   264             assert(env_->scope()->kind() == Scope::GLOBAL);
   265         }
   266 
   267         node->setSymbol(sym);
   268 
   269         // Scope for the function's arguments.
   270         SymbolEnv argEnv(&env_);
   271         if (!registerArguments(node->signature()))
   272             return;
   273 
   274         // Scope for function body.
   275         SymbolEnv localEnv(&env_);
   276         FunctionScope fun(&fun_);
   277         if (node->body())
   278             node->body()->accept(this);
   279 
   280         // Function statements have quirky semantics around their return
   281         // type. For reasonable compatibility with SP1, we use the following
   282         // heuristics for when no explicit type is declared.
   283         if (!node->signature().returnType()) {
   284             Local<Type> type(zone_);
   285             if (node->token() == TOK_FORWARD || node->token() == TOK_NATIVE) {
   286                 // If the function type is a native or forward, we always
   287                 // assume it returns an int32.
   288                 type = zone_->types()->getPrimitive(PrimitiveType_Int32);
   289             } else if (fun.returns() != ValueReturn) {
   290                 // This function never returns a value, so mark it as
   291                 // returning void.
   292                 type = zone_->types()->getVoid();
   293             }
   294             // No need to NULL check here, we'll catch OOM later.
   295             node->sym()->type()->setReturnType(type);
   296         }
   297 
   298         node->setScopes(argEnv.scope(), localEnv.scope());
   299     }
   300 
   301     void visitStructureStatement(StructureStatement *node) {
   302         assert(false);
   303     }
   304 
   305     void visiFunctionTypeStatementt(FunctionTypeStatement *node) {
   306         assert(false);
   307     }
   308 
   309     void visitNameProxy(NameProxy *name) {
   310     }
   311     void visitAssignment(Assignment *node) {
   312         node->lvalue()->accept(this);
   313         node->expression()->accept(this);
   314     }
   315     void visitBinaryExpression(BinaryExpression *node) {
   316         node->left()->accept(this);
   317         node->right()->accept(this);
   318     }
   319     void visitReturnStatement(ReturnStatement *node) {
   320         if (node->expression())
   321             fun_->returns(ValueReturn);
   322         else
   323             fun_->returns(VoidReturn);
   324     }
   325     void visitForStatement(ForStatement *node) {
   326         SymbolEnv env(&env_);
   327 
   328         if (node->initialization())
   329             node->initialization()->accept(this);
   330         if (node->condition())
   331             node->condition()->accept(this);
   332         if (node->update())
   333             node->update()->accept(this);
   334         node->body()->accept(this);
   335 
   336         node->setScope(env.scope());
   337     }
   338     void visitBlockStatement(BlockStatement *node) {
   339         if (node->type() == TOK_NEW) {
   340             // Don't create a symbol environment for this block, since it
   341             // was created solely to house multiple variable decls.
   342             for (size_t i = 0; i < node->statements()->length(); i++)
   343                 node->statements()->at(i)->accept(this);
   344         } else {
   345             assert(node->type() == TOK_LBRACE);
   346 
   347             SymbolEnv env(&env_);
   348 
   349             for (size_t i = 0; i < node->statements()->length(); i++)
   350                 node->statements()->at(i)->accept(this);
   351         
   352             if (node->type() == TOK_NEW) {
   353                 assert(!env.scope());
   354                 return;
   355             }
   356 
   357             node->setScope(env.scope());
   358         }
   359     }
   360     void visitIntegerLiteral(IntegerLiteral *node) {
   361     }
   362     void visitExpressionStatement(ExpressionStatement *node) {
   363         node->expression()->accept(this);
   364     }
   365     void visitCallExpression(CallExpression *node) {
   366         node->callee()->accept(this);
   367         for (size_t i = 0; i < node->arguments()->length(); i++)
   368             node->arguments()->at(i)->accept(this);
   369     }
   370     void visitIfStatement(IfStatement *node) {
   371         node->ifTrue()->accept(this);
   372         if (node->ifFalse())
   373             node->ifFalse()->accept(this);
   374     }
   375     void visitIndexExpression(IndexExpression *node) {
   376         node->left()->accept(this);
   377         node->right()->accept(this);
   378     }
   379     void visitFloatLiteral(FloatLiteral *node) {
   380     }
   381     void visitWhileStatement(WhileStatement *node) {
   382         node->condition()->accept(this);
   383         node->body()->accept(this);
   384     }
   385     void visitBreakStatement(BreakStatement *node) {
   386     }
   387     void visitContinueStatement(ContinueStatement *node) {
   388     }
   389     void visitStringLiteral(StringLiteral *node) {
   390     }
   391     void visitIncDecExpression(IncDecExpression *node) {
   392         node->expression()->accept(this);
   393     }
   394     void visitUnaryExpression(UnaryExpression *node) {
   395         node->expression()->accept(this);
   396     }
   397     void visitTernaryExpression(TernaryExpression *node) {
   398         assert(false);
   399     }
   400     void visitBooleanLiteral(BooleanLiteral *node) {
   401     }
   402     void visitFieldExpression(FieldExpression *node) {
   403     }
   404     void visitSwitchStatement(SwitchStatement *node) {
   405         if (node->defaultCase())
   406             node->defaultCase()->accept(this);
   407 
   408         for (size_t i = 0; i < node->cases()->length(); i++)
   409             node->cases()->at(i)->statement()->accept(this);
   410     }
   411     void visitArrayLiteral(ArrayLiteral *node) {
   412     }
   413     void visitImportStatement(ImportStatement *node) {
   414     }
   415 
   416   private:
   417     Scope *getGlobalOrCreateBlockScope() {
   418         if (env_->scope()) {
   419             assert(env_->scope()->kind() == Scope::BLOCK ||
   420                    env_->scope()->kind() == Scope::GLOBAL);
   421             return env_->scope();
   422         }
   423         return getOrCreateBlockScope();
   424     }
   425     Scope *getOrCreateBlockScope() {
   426         if (env_->scope()) {
   427             assert(env_->scope()->kind() == Scope::BLOCK);
   428             return env_->scope();
   429         }
   430         
   431         LocalScope *scope = LocalScope::New(pool_);
   432         if (!scope)
   433             return NULL;
   434 
   435         env_->setScope(scope);
   436         return scope;
   437     }
   438 
   439     bool registerName(Scope *scope, Symbol *sym) {
   440         if (!scope)
   441             return false;
   442 
   443         if (Symbol *other = scope->localLookup(sym->name())) {
   444             // Report, but allow errors to continue.
   445             cc_.reportError(sym->pos(), Message_RedeclaredName,
   446                             sym->name()->chars(),
   447                             other->pos().line,
   448                             other->pos().col);
   449             return true;
   450         }
   451 
   452         return scope->addSymbol(sym);
   453     }
   454 
   455     bool registerArguments(const FunctionSignature &sig) {
   456         if (!sig.parameters()->length())
   457             return true;
   458 
   459         ArgumentScope *argScope = ArgumentScope::New(pool_);
   460         if (!argScope)
   461             return false;
   462         env_->setScope(argScope);
   463 
   464         for (size_t i = 0; i < sig.parameters()->length(); i++) {
   465             Parameter *param = sig.parameters()->at(i);
   466             VariableSymbol *sym = new (pool_) VariableSymbol(argScope, param->name(), param->pos());
   467             if (!registerName(env_->scope(), sym))
   468                 return false;
   469             param->setSymbol(sym);
   470         }
   471 
   472         return true;
   473     }
   474 
   475   private:
   476     Zone *zone_;
   477     PoolAllocator &pool_;
   478     CompileContext &cc_;
   479     TranslationUnit *unit_;
   480     SymbolEnv *env_;
   481     FunctionScope *fun_;
   482 };
   483 
   484 void
   485 ke::PopulateNamesAndTypes(Zone *zone, CompileContext &cc, TranslationUnit *unit)
   486 {
   487     AutoEnterCompileContext enter(cc, unit);
   488     NamePopulator populator(zone, cc, unit);
   489     populator.analyze();
   490 }
   491 
   492 static const int INFER_ARRAY_SIZE = 0;
   493 static const int EVAL_ARRAY_SIZE = -1;
   494 static const int DYNAMIC_ARRAY_SIZE = -2;
   495 
   496 class NameBinderBase : public AstVisitor
   497 {
   498   public:
   499     NameBinderBase(Zone *zone, CompileContext &cc, TranslationUnit *unit)
   500       : zone_(zone),
   501         pool_(zone->pool()),
   502         cc_(cc),
   503         unit_(unit)
   504     {
   505     }
   506 
   507 
   508   protected:
   509     Type *buildVariableType(VariableDeclaration *node) {
   510         Local<Type> type(zone_, bindType(node->type(), node->quals()));
   511         if (!type)
   512             return NULL;
   513 
   514         // We don't allow array typedefs yet.
   515         assert(!type->isArray());
   516 
   517         if (node->dims()) {
   518             int dims[MAX_ARRAY_DEPTH];
   519             int levels = evaluateDimensions(node->pos(), type, node->dims(), dims);
   520             if (levels < 0)
   521                 return NULL;
   522 
   523             // Do some extra inference based on the initializer, if present.
   524             Expression *init = node->initialization();
   525             if (init) {
   526                 if (init->isArrayLiteral() && init->toArrayLiteral()->isFixed()) {
   527                     Local<Type> contained(zone_, type->isArray()
   528                                                  ? ArrayType::cast(type)->contained()
   529                                                  : type);
   530                     if (!inferFixedArrayDimensions(init->toArrayLiteral(), contained, dims, levels))
   531                         return NULL;
   532                 } else if (init->isStringLiteral()) {
   533                     dims[levels - 1] = init->toStringLiteral()->string()->length() + 1;
   534                 }
   535             }
   536 
   537             // If we got extra dimensions, we need to build a new type.
   538             if (node->dims()) {
   539                 if ((type = buildArrayType(type, node->quals(), dims, node->dims()->length())) == NULL)
   540                     return NULL;
   541             }
   542         }
   543 
   544         return type;
   545     }
   546 
   547     int evaluateDimensions(const SourcePosition &pos, Handle<Type> typeArg, ExpressionList *exprs, int dims[MAX_ARRAY_DEPTH]) {
   548         unsigned level = 0;
   549         Local<Type> type(zone_, typeArg);
   550         while (type->isArray()) {
   551             ArrayType *atype = ArrayType::cast(type);
   552             dims[level] = atype->isFixedLength()
   553                           ? atype->fixedLength()
   554                           : DYNAMIC_ARRAY_SIZE;
   555             type = atype->contained();
   556             level++;
   557         }
   558 
   559         if (!exprs)
   560             return level;
   561 
   562         if (level + exprs->length() > MAX_ARRAY_DEPTH) {
   563             cc_.reportError(pos, Message_MaximumArrayDepth);
   564             return -1;
   565         }
   566 
   567         bool hadEmptySize = false;
   568         for (size_t i = 0; i < exprs->length(); i++) {
   569             Expression *expr = exprs->at(i);
   570             if (!expr) {
   571                 dims[i] = INFER_ARRAY_SIZE;
   572                 hadEmptySize = true;
   573                 continue;
   574             }
   575 
   576             BoxedPrimitive box;
   577             if (EvaluateForConstant(expr, &box) && box.type() == PrimitiveType_Int32) {
   578                 int size = box.toInt();
   579                 if (size <= 0) {
   580                     cc_.reportError(expr->pos(), Message_BadArraySize);
   581                     return false;
   582                 }
   583 
   584                 dims[i] = size;
   585                 continue;
   586             }
   587 
   588             if (hadEmptySize) {
   589                 cc_.reportError(expr->pos(), Message_BadDynamicInitializer);
   590                 return false;
   591             }
   592 
   593             dims[i] = EVAL_ARRAY_SIZE;
   594         }
   595 
   596         return level + exprs->length();
   597     }
   598 
   599     // This function computes missing dimension sizes based on a literal
   600     // initializer. We don't really handle any size rules here; we just
   601     // do a really dumb inference.
   602     bool inferFixedArrayDimensions(ArrayLiteral *lit, Handle<Type> contained, int dims[MAX_ARRAY_DEPTH], int levels) {
   603         for (int i = 0; i < levels; i++) {
   604             if (dims[i] == EVAL_ARRAY_SIZE || dims[i] == DYNAMIC_ARRAY_SIZE) {
   605                 // The following are invalid:
   606                 //   new x[<expr>] = {...}
   607                 //   new Type:x = {...}  // where Type is a non-fixed array type
   608                 cc_.reportError(lit->pos(), Message_CannotInitializeEvalArray);
   609                 return false;
   610             }
   611 
   612             if (dims[i] == INFER_ARRAY_SIZE) {
   613                 // Character arrays are always dynamic when inferred from string literals.
   614                 if (i == levels - 1 && contained->isChar())
   615                     dims[i] = DYNAMIC_ARRAY_SIZE;
   616                 else
   617                     dims[i] = lit->expressions()->length();
   618             }
   619 
   620             if (i != levels - 1) {
   621                 // Fixed array literals are guaranteed to have at least one expression.
   622                 Expression *next = lit->expressions()->at(0);
   623                 if (!next->isArrayLiteral()) {
   624                     // Whelp... this array is just malformed. Not the best error message
   625                     // but whatever.
   626                     cc_.reportError(next->pos(), Message_ArraySizeCannotBeDetermined);
   627                     return false;
   628                 }
   629                 lit = next->toArrayLiteral();
   630             }
   631         }
   632 
   633         return true;
   634     }
   635 
   636     ArrayType *buildArrayType(Handle<Type> contained, TypeQualifiers quals, int dims[MAX_ARRAY_DEPTH], size_t postlevels) {
   637         Local<Type> type(zone_, contained);
   638 
   639         for (size_t i = postlevels - 1; i < postlevels; i--) {
   640             int size = dims[i] > 0
   641                        ? dims[i]
   642                        : ArrayType::DYNAMIC_ARRAY_SIZE;
   643             
   644             if ((type = zone_->types()->newArray(contained, size)) == NULL)
   645                 return NULL;
   646             if ((type = zone_->types()->qualify(type, quals)) == NULL)
   647                 return NULL;
   648         }
   649         return ArrayType::cast(type);
   650     }
   651 
   652     bool fillFunctionType(Handle<FunctionType> fun, const FunctionSignature &sig) {
   653         Local<Type> type(zone_);
   654         if (!fun->returnType()) {
   655             if ((type = bindType(sig.returnType(), TypeQual_None)) == NULL)
   656                 return false;
   657             fun->setReturnType(type);
   658         }
   659 
   660         if (sig.variadic())
   661             fun->setVariadic();
   662 
   663         Local<FixedArray> params(zone_, FixedArray::New(zone_, sig.parameters()->length(), Heap::Tenure_Old));
   664         if (!params)
   665             return false;
   666 
   667         for (size_t i = 0; i < sig.parameters()->length(); i++) {
   668             Parameter *param = sig.parameters()->at(i);
   669             if ((type = bindType(param->type(), param->quals())) == NULL)
   670                 return false;
   671 
   672             assert(!type->isArray());
   673 
   674             if (param->dims()) {
   675                 int dims[MAX_ARRAY_DEPTH];
   676                 int levels = evaluateDimensions(param->pos(), type, param->dims(), dims);
   677                 if (levels < 0)
   678                     return false;
   679 
   680                 // If we got extra dimensions, we need to build a new type.
   681                 // Unlike variables, we do not infer anything about array
   682                 // sizes from its default initializer.
   683                 if (param->dims()) {
   684                     if ((type = buildArrayType(type, param->quals(), dims, param->dims()->length())) == NULL)
   685                         return false;
   686                 }
   687 
   688                 if (ArrayType::cast(type)->innermost()->isVoid()) {
   689                     cc_.reportError(param->type()->pos(), Message_CannotDeclareVoid);
   690                     return false;
   691                 }
   692             }
   693 
   694             if (param->reference()) {
   695                 if (!type->isPod()) {
   696                     cc_.reportError(param->pos(), Message_ArrayCantBeReference);
   697                     return false;
   698                 }
   699                 if (param->quals() & TypeQual_Const) {
   700                     cc_.reportError(param->pos(), Message_CannotConstReference);
   701                     return false;
   702                 }
   703                 if ((type = zone_->types()->getReference(type, false)) == NULL)
   704                     return false;
   705             }
   706             if (param->quals() & TypeQual_Const) {
   707                 if (!type->isArray() && !type->isStruct()) {
   708                     cc_.reportError(param->pos(), Message_InvalidConstOnFormal);
   709                     return false;
   710                 }
   711             }
   712 
   713             if (type->isVoid()) {
   714                 cc_.reportError(param->type()->pos(), Message_CannotDeclareVoid);
   715                 return false;
   716             }
   717 
   718             params->set(zone_, i, type);
   719             param->sym()->setType(type);
   720         }
   721 
   722         fun->setParameterTypes(params);
   723 
   724         return true;
   725     }
   726 
   727     Type *bindType(Expression *expr, TypeQualifiers quals) {
   728         Local<Type> type(zone_);
   729 
   730         if (!expr) {
   731             // If no type was declared, we return int32.
   732             type = zone_->types()->getPrimitive(PrimitiveType_Int32);
   733         } else {
   734             expr->accept(this);
   735 
   736             NameProxy *proxy = expr->asNameProxy();
   737             assert(proxy);
   738 
   739             Symbol *sym = proxy->sym();
   740             if (!sym)
   741                 return NULL;
   742 
   743             if (!sym->isType()) {
   744                 cc_.reportError(expr->pos(), Message_IdentifierIsNotAType, sym->name()->chars());
   745                 return NULL;
   746             }
   747 
   748             type = sym->type();
   749         }
   750 
   751         return zone_->types()->qualify(type, quals);
   752     }
   753 
   754   protected:
   755     Zone *zone_;
   756     PoolAllocator &pool_;
   757     CompileContext &cc_;
   758     TranslationUnit *unit_;
   759 };
   760 
   761 class GlobalBuilder : public NameBinderBase
   762 {
   763   public:
   764     GlobalBuilder(Zone *zone, CompileContext &cc, TranslationUnit *unit)
   765       : NameBinderBase(zone, cc, unit)
   766     {
   767     }
   768 
   769     Struct *build() {
   770         for (size_t i = 0; i < unit_->tree()->imports()->length(); i++)
   771             unit_->tree()->imports()->at(i)->accept(this);
   772 
   773         // Next, enter the global scope and walk all statements.
   774         for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
   775             Statement *stmt = unit_->tree()->statements()->at(i);
   776             stmt->accept(this);
   777         }
   778 
   779         Local<FixedArray> descs(zone_, FixedArray::New(zone_, descriptors_.length(), Heap::Tenure_Old));
   780         if (!descs)
   781             return NULL;
   782 
   783         for (unsigned i = 0; i < descriptors_.length(); i++)
   784             descs->set(zone_, i, *descriptors_[i]);
   785 
   786         Local<String> name(zone_, unit_->module()->name());
   787         Local<StructType> type(zone_, StructType::New(zone_, name, descs));
   788         if (!type)
   789             return NULL;
   790 
   791         Local<StructMap> map(zone_, type->newMap());
   792         return Struct::New(zone_, map, Heap::Tenure_Old);
   793     }
   794 
   795     void visitEnumStatement(EnumStatement *stmt) {
   796     }
   797 
   798     void visitNameProxy(NameProxy *proxy) {
   799         // Don't report errors here, since we'll report them later.
   800         Scope *scope = unit_->globalScope();
   801         Symbol *sym = scope->lookup(proxy->name());
   802         proxy->bind(sym);
   803     }
   804 
   805     void visitFunctionStatement(FunctionStatement *node) {
   806         Local<FunctionType> type(zone_, node->sym()->type());
   807         if (!fillFunctionType(type, node->signature()))
   808             return;
   809 
   810         unsigned offset;
   811         if (!builder_.add(type, &offset))
   812             return;
   813 
   814         Descriptor::Visibility visibility = (node->token() == TOK_NATIVE || node->token() == TOK_FORWARD)
   815                                             ? Descriptor::Public
   816                                             : Descriptor::Private;
   817 
   818         Descriptor *desc = Descriptor::New(zone_, node->name(), type, visibility);
   819         if (!desc)
   820             return;
   821         if (!descriptors_.append(new (pool_) ScopedRoot<Descriptor>(desc)))
   822             return;
   823     }
   824 
   825     void visitVariableDeclaration(VariableDeclaration *node) {
   826         Local<Type> type(zone_, buildVariableType(node));
   827         if (!type)
   828             return;
   829 
   830         // If we're in global scope, and we received a |const| qualifier, then
   831         // we extend this to array references as well. This is to sort of mimic
   832         // SP1 functionality, but also means that you cannot have changeable
   833         // const pointers in global scope.
   834         if ((node->quals() & TypeQual_Const) && type->isArray()) {
   835             if ((type = zone_->types()->qualify(type, TypeQual_Const)) == NULL)
   836                 return;
   837         }
   838 
   839         node->sym()->setType(type);
   840 
   841         unsigned offset;
   842         if (!builder_.add(type, &offset))
   843             return;
   844 
   845         Descriptor *desc = Descriptor::New(zone_, node->name(), type, Descriptor::Private);
   846         if (!desc)
   847             return;
   848         if (!descriptors_.append(new (pool_) ScopedRoot<Descriptor>(desc)))
   849             return;
   850     }
   851 
   852     void visitImportStatement(ImportStatement *node) {
   853         // Eventually we'll handle |from| style imports as well.
   854         {
   855             PathComponent *path = node->path();
   856             while (path->next)
   857                 path = path->next;
   858 
   859             // Imports automatically go into the importScope. For now, we
   860             // error if there are any duplicate symbols entered into the
   861             // importScope.
   862             if (Symbol *sym = unit_->importScope()->localLookup(path->name)) {
   863                 cc_.reportError(node->pos(), Message_DuplicateImport, path->name->chars());
   864                 return;
   865             }
   866 
   867             Local<Type> type(zone_, zone_->types()->getImportable());
   868             ImportSymbol *sym = new (pool_) ImportSymbol(unit_->importScope(), path->name, node->pos(), type, node->importIndex());
   869             if (!unit_->importScope()->addSymbol(sym))
   870                 return;
   871         }
   872     }
   873 
   874   private:
   875     StructureBufferBuilder builder_;
   876     Vector<ScopedRoot<Descriptor> *> descriptors_;
   877 };
   878     
   879 class NameBinder : public NameBinderBase
   880 {
   881   public:
   882     class AutoLinkScope
   883     {
   884       public:
   885         AutoLinkScope(AutoLinkScope **prevp, Scope *scope)
   886           : prevp_(prevp),
   887             prev_(*prevp),
   888             scope_(scope)
   889         {
   890             if (scope_) {
   891                 *prevp_ = this;
   892                 if (prev_)
   893                     scope_->setParent(prev_->scope());
   894             }
   895         }
   896         ~AutoLinkScope() {
   897             if (scope_) {
   898                 assert(*prevp_ == this);
   899                 *prevp_ = prev_;
   900             }
   901         }
   902         Scope *scope() const {
   903             return scope_;
   904         }
   905 
   906       private:
   907         AutoLinkScope **prevp_;
   908         AutoLinkScope *prev_;
   909         Scope *scope_;
   910     };
   911 
   912   public:
   913     NameBinder(Zone *zone, CompileContext &cc, TranslationUnit *unit)
   914       : NameBinderBase(zone, cc, unit),
   915         link_(NULL)
   916     {
   917     }
   918 
   919     void bind() {
   920         // Start with the import scope, and collect all imported names.
   921         AutoLinkScope importScope(&link_, unit_->importScope());
   922 
   923         for (size_t i = 0; i < unit_->tree()->imports()->length(); i++)
   924             unit_->tree()->imports()->at(i)->accept(this);
   925 
   926         // Next, enter the global scope and walk all statements.
   927         AutoLinkScope globalScope(&link_, unit_->globalScope());
   928         for (size_t i = 0; i < unit_->tree()->statements()->length(); i++) {
   929             Statement *stmt = unit_->tree()->statements()->at(i);
   930             stmt->accept(this);
   931         }
   932     }
   933 
   934     void visitVariableDeclaration(VariableDeclaration *node) {
   935         // Bind the initializer before registering the declaration, so that we
   936         // can error on bogus initializers (new x = x).
   937         if (node->initialization())
   938             node->initialization()->accept(this);
   939 
   940         // If the node already has a symbol (meaning it was a global), then
   941         // we don't have to do anything more.
   942         if (node->sym())
   943             return;
   944 
   945         Local<Type> type(zone_, buildVariableType(node));
   946         if (!type)
   947             return;
   948 
   949         VariableSymbol *sym = new (pool_) VariableSymbol(link_->scope(), node->name(), node->pos(), type);
   950         node->setSymbol(sym);
   951        
   952         if (Symbol *other = link_->scope()->localLookup(sym->name())) {
   953             // Report, but allow errors to continue.
   954             cc_.reportError(sym->pos(), Message_RedeclaredName,
   955                             sym->name()->chars(),
   956                             other->pos().line,
   957                             other->pos().col);
   958             return;
   959         }
   960         
   961         link_->scope()->addSymbol(sym);
   962     }
   963     void visitEnumStatement(EnumStatement *node) {
   964     }
   965     void visitFunctionStatement(FunctionStatement *node) {
   966         AutoLinkScope argScope(&link_, node->argScope());
   967         AutoLinkScope varScope(&link_, node->varScope());
   968 
   969         // If the function is in the global scope, we've already computed its
   970         // type.
   971         if (node->sym()->scope()->kind() != Scope::GLOBAL) {
   972             Local<FunctionType> type(zone_, node->sym()->type());
   973             if (!fillFunctionType(type, node->signature()))
   974                 return;
   975         }
   976 
   977         if (node->body())
   978             node->body()->accept(this);
   979     }
   980     void visitStructureStatement(StructureStatement *node) {
   981         assert(false);
   982     }
   983     void visitFunctionTypeStatement(FunctionTypeStatement *node) {
   984         assert(false);
   985     }
   986 
   987     void visitNameProxy(NameProxy *proxy) {
   988         // We could have already bound globals.
   989         if (proxy->sym())
   990             return;
   991 
   992         Scope *scope = link_->scope();
   993         Symbol *sym = scope->lookup(proxy->name());
   994         if (!sym)
   995             cc_.reportError(proxy->pos(), Message_IdentifierNotFound, proxy->name()->chars());
   996         proxy->bind(sym);
   997     }
   998     void visitAssignment(Assignment *node) {
   999         node->lvalue()->accept(this);
  1000         node->expression()->accept(this);
  1001     }
  1002     void visitBinaryExpression(BinaryExpression *node) {
  1003         node->left()->accept(this);
  1004         node->right()->accept(this);
  1005     }
  1006     void visitReturnStatement(ReturnStatement *node) {
  1007         node->expression()->accept(this);
  1008     }
  1009     void visitForStatement(ForStatement *node) {
  1010         AutoLinkScope scope(&link_, node->scope());
  1011 
  1012         if (node->initialization())
  1013             node->initialization()->accept(this);
  1014         if (node->condition())
  1015             node->condition()->accept(this);
  1016         if (node->update())
  1017             node->update()->accept(this);
  1018         node->body()->accept(this);
  1019     }
  1020     void visitBlockStatement(BlockStatement *node) {
  1021         AutoLinkScope scope(&link_, node->scope());
  1022         for (size_t i = 0; i < node->statements()->length(); i++)
  1023             node->statements()->at(i)->accept(this);
  1024     }
  1025     void visitIntegerLiteral(IntegerLiteral *node) {
  1026     }
  1027     void visitExpressionStatement(ExpressionStatement *node) {
  1028         node->expression()->accept(this);
  1029     }
  1030     void visitCallExpression(CallExpression *node) {
  1031         node->callee()->accept(this);
  1032         for (size_t i = 0; i < node->arguments()->length(); i++)
  1033             node->arguments()->at(i)->accept(this);
  1034     }
  1035     void visitIfStatement(IfStatement *node) {
  1036         node->condition()->accept(this);
  1037         node->ifTrue()->accept(this);
  1038         if (node->ifFalse())
  1039             node->ifFalse()->accept(this);
  1040     }
  1041     void visitIndexExpression(IndexExpression *node) {
  1042         node->left()->accept(this);
  1043         node->right()->accept(this);
  1044     }
  1045     void visitFloatLiteral(FloatLiteral *node) {
  1046     }
  1047     void visitWhileStatement(WhileStatement *node) {
  1048         node->condition()->accept(this);
  1049         node->body()->accept(this);
  1050     }
  1051     void visitBreakStatement(BreakStatement *node) {
  1052     }
  1053     void visitContinueStatement(ContinueStatement *node) {
  1054     }
  1055     void visitStringLiteral(StringLiteral *node) {
  1056     }
  1057     void visitIncDecExpression(IncDecExpression *node) {
  1058         node->expression()->accept(this);
  1059     }
  1060     void visitUnaryExpression(UnaryExpression *node) {
  1061         if (node->tag())
  1062             node->tag()->accept(this);
  1063         node->expression()->accept(this);
  1064     }
  1065     void visitTernaryExpression(TernaryExpression *node) {
  1066         node->condition()->accept(this);
  1067         node->left()->accept(this);
  1068         node->right()->accept(this);
  1069     }
  1070     void visitBooleanLiteral(BooleanLiteral *node) {
  1071     }
  1072     void visitFieldExpression(FieldExpression *node) {
  1073         node->left()->accept(this);
  1074     }
  1075     void visitSwitchStatement(SwitchStatement *node) {
  1076         node->expression()->accept(this);
  1077         node->defaultCase()->accept(this);
  1078         for (size_t i = 0; i < node->cases()->length(); i++) {
  1079             // We don't test case expressions because they are literals.
  1080             Case *c = node->cases()->at(i);
  1081             c->statement()->accept(this);
  1082         }
  1083     }
  1084     void visitArrayLiteral(ArrayLiteral *node) {
  1085         for (size_t i = 0; i < node->expressions()->length(); i++)
  1086             node->expressions()->at(i)->accept(this);
  1087     }
  1088     void visitImportStatement(ImportStatement *node) {
  1089     }
  1090 
  1091   private:
  1092     AutoLinkScope *link_;
  1093 };
  1094 
  1095 void
  1096 ke::BindNamesAndTypes(Zone *zone, CompileContext &cc, TranslationUnit *unit)
  1097 {
  1098     AutoEnterCompileContext enter(cc, unit);
  1099 
  1100     // Because of the way globals work in Pawn, we need a precursor step to
  1101     // actually enter global symbols into the global struct. They're already
  1102     // in the global symbol table, so we know they won't clash. This process
  1103     // also binds any remaining types on global variables.
  1104     GlobalBuilder builder(zone, cc, unit);
  1105     Local<Struct> globals(zone, builder.build());
  1106     if (!globals || unit->failed())
  1107         return;
  1108 
  1109     unit->module()->setGlobals(globals);
  1110 
  1111     NameBinder binder(zone, cc, unit);
  1112     binder.bind();
  1113 }