src/typing-asm.cc

   1 // Copyright 2015 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/typing-asm.h"
   8
   9 #include "src/ast.h"
  10 #include "src/codegen.h"
  11 #include "src/scopes.h"
  12 #include "src/zone-type-cache.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace {
  17
  18 base::LazyInstance<ZoneTypeCache>::type kCache = LAZY_INSTANCE_INITIALIZER;
  19
  20 }  // namespace
  21
  22
  23 #define FAIL(node, msg)                                        \
  24   do {                                                         \
  25     valid_ = false;                                            \
  26     int line = node->position() == RelocInfo::kNoPosition      \
  27                    ? -1                                        \
  28                    : script_->GetLineNumber(node->position()); \
  29     base::OS::SNPrintF(error_message_, sizeof(error_message_), \
  30                        "asm: line %d: %s\n", line + 1, msg);   \
  31     return;                                                    \
  32   } while (false)
  33
  34
  35 #define RECURSE(call)               \
  36   do {                              \
  37     DCHECK(!HasStackOverflow());    \
  38     call;                           \
  39     if (HasStackOverflow()) return; \
  40     if (!valid_) return;            \
  41   } while (false)
  42
  43
  44 AsmTyper::AsmTyper(Isolate* isolate, Zone* zone, Script* script,
  45                    FunctionLiteral* root)
  46     : script_(script),
  47       root_(root),
  48       valid_(true),
  49       stdlib_types_(zone),
  50       stdlib_heap_types_(zone),
  51       stdlib_math_types_(zone),
  52       global_variable_type_(HashMap::PointersMatch,
  53                             ZoneHashMap::kDefaultHashMapCapacity,
  54                             ZoneAllocationPolicy(zone)),
  55       local_variable_type_(HashMap::PointersMatch,
  56                            ZoneHashMap::kDefaultHashMapCapacity,
  57                            ZoneAllocationPolicy(zone)),
  58       in_function_(false),
  59       building_function_tables_(false),
  60       cache_(kCache.Get()) {
  61   InitializeAstVisitor(isolate, zone);
  62   InitializeStdlib();
  63 }
  64
  65
  66 bool AsmTyper::Validate() {
  67   VisitAsmModule(root_);
  68   return valid_ && !HasStackOverflow();
  69 }
  70
  71
  72 void AsmTyper::VisitAsmModule(FunctionLiteral* fun) {
  73   Scope* scope = fun->scope();
  74   if (!scope->is_function_scope()) FAIL(fun, "not at function scope");
  75
  76   // Module parameters.
  77   for (int i = 0; i < scope->num_parameters(); ++i) {
  78     Variable* param = scope->parameter(i);
  79     DCHECK(GetType(param) == NULL);
  80     SetType(param, Type::None(zone()));
  81   }
  82
  83   ZoneList<Declaration*>* decls = scope->declarations();
  84
  85   // Set all globals to type Any.
  86   VariableDeclaration* decl = scope->function();
  87   if (decl != NULL) SetType(decl->proxy()->var(), Type::None());
  88   RECURSE(VisitDeclarations(scope->declarations()));
  89
  90   // Validate global variables.
  91   RECURSE(VisitStatements(fun->body()));
  92
  93   // Validate function annotations.
  94   for (int i = 0; i < decls->length(); ++i) {
  95     FunctionDeclaration* decl = decls->at(i)->AsFunctionDeclaration();
  96     if (decl != NULL) {
  97       RECURSE(VisitFunctionAnnotation(decl->fun()));
  98       Variable* var = decl->proxy()->var();
  99       DCHECK(GetType(var) == NULL);
 100       SetType(var, computed_type_);
 101       DCHECK(GetType(var) != NULL);
 102     }
 103   }
 104
 105   // Build function tables.
 106   building_function_tables_ = true;
 107   RECURSE(VisitStatements(fun->body()));
 108   building_function_tables_ = false;
 109
 110   // Validate function bodies.
 111   for (int i = 0; i < decls->length(); ++i) {
 112     FunctionDeclaration* decl = decls->at(i)->AsFunctionDeclaration();
 113     if (decl != NULL) {
 114       RECURSE(
 115           VisitWithExpectation(decl->fun(), Type::Any(zone()), "UNREACHABLE"));
 116       if (!computed_type_->IsFunction()) {
 117         FAIL(decl->fun(), "function literal expected to be a function");
 118       }
 119     }
 120   }
 121
 122   // Validate exports.
 123   ReturnStatement* stmt = fun->body()->last()->AsReturnStatement();
 124   RECURSE(VisitWithExpectation(stmt->expression(), Type::Object(),
 125                                "expected object export"));
 126 }
 127
 128
 129 void AsmTyper::VisitVariableDeclaration(VariableDeclaration* decl) {
 130   Variable* var = decl->proxy()->var();
 131   if (var->location() != VariableLocation::PARAMETER) {
 132     if (GetType(var) == NULL) {
 133       SetType(var, Type::Any(zone()));
 134     } else {
 135       DCHECK(!GetType(var)->IsFunction());
 136     }
 137   }
 138   DCHECK(GetType(var) != NULL);
 139   intish_ = 0;
 140 }
 141
 142
 143 void AsmTyper::VisitFunctionDeclaration(FunctionDeclaration* decl) {
 144   if (in_function_) {
 145     FAIL(decl, "function declared inside another");
 146   }
 147 }
 148
 149
 150 void AsmTyper::VisitFunctionAnnotation(FunctionLiteral* fun) {
 151   // Extract result type.
 152   ZoneList<Statement*>* body = fun->body();
 153   Type* result_type = Type::Undefined(zone());
 154   if (body->length() > 0) {
 155     ReturnStatement* stmt = body->last()->AsReturnStatement();
 156     if (stmt != NULL) {
 157       RECURSE(VisitExpressionAnnotation(stmt->expression()));
 158       result_type = computed_type_;
 159     }
 160   }
 161   Type::FunctionType* type =
 162       Type::Function(result_type, Type::Any(), fun->parameter_count(), zone())
 163           ->AsFunction();
 164
 165   // Extract parameter types.
 166   bool good = true;
 167   for (int i = 0; i < fun->parameter_count(); ++i) {
 168     good = false;
 169     if (i >= body->length()) break;
 170     ExpressionStatement* stmt = body->at(i)->AsExpressionStatement();
 171     if (stmt == NULL) break;
 172     Assignment* expr = stmt->expression()->AsAssignment();
 173     if (expr == NULL || expr->is_compound()) break;
 174     VariableProxy* proxy = expr->target()->AsVariableProxy();
 175     if (proxy == NULL) break;
 176     Variable* var = proxy->var();
 177     if (var->location() != VariableLocation::PARAMETER || var->index() != i)
 178       break;
 179     RECURSE(VisitExpressionAnnotation(expr->value()));
 180     SetType(var, computed_type_);
 181     type->InitParameter(i, computed_type_);
 182     good = true;
 183   }
 184   if (!good) FAIL(fun, "missing parameter type annotations");
 185
 186   SetResult(fun, type);
 187 }
 188
 189
 190 void AsmTyper::VisitExpressionAnnotation(Expression* expr) {
 191   // Normal +x or x|0 annotations.
 192   BinaryOperation* bin = expr->AsBinaryOperation();
 193   if (bin != NULL) {
 194     Literal* right = bin->right()->AsLiteral();
 195     if (right != NULL) {
 196       switch (bin->op()) {
 197         case Token::MUL:  // We encode +x as 1*x
 198           if (right->raw_value()->ContainsDot() &&
 199               right->raw_value()->AsNumber() == 1.0) {
 200             SetResult(expr, cache_.kFloat64);
 201             return;
 202           }
 203           break;
 204         case Token::BIT_OR:
 205           if (!right->raw_value()->ContainsDot() &&
 206               right->raw_value()->AsNumber() == 0.0) {
 207             SetResult(expr, cache_.kInt32);
 208             return;
 209           }
 210           break;
 211         default:
 212           break;
 213       }
 214     }
 215     FAIL(expr, "invalid type annotation on binary op");
 216   }
 217
 218   // Numbers or the undefined literal (for empty returns).
 219   if (expr->IsLiteral()) {
 220     RECURSE(VisitWithExpectation(expr, Type::Any(), "invalid literal"));
 221     return;
 222   }
 223
 224   Call* call = expr->AsCall();
 225   if (call != NULL) {
 226     if (call->expression()->IsVariableProxy()) {
 227       RECURSE(VisitWithExpectation(
 228           call->expression(), Type::Any(zone()),
 229           "only fround allowed on expression annotations"));
 230       if (!computed_type_->Is(
 231               Type::Function(cache_.kFloat32, Type::Number(zone()), zone()))) {
 232         FAIL(call->expression(),
 233              "only fround allowed on expression annotations");
 234       }
 235       if (call->arguments()->length() != 1) {
 236         FAIL(call, "invalid argument count calling fround");
 237       }
 238       SetResult(expr, cache_.kFloat32);
 239       return;
 240     }
 241   }
 242
 243   FAIL(expr, "invalid type annotation");
 244 }
 245
 246
 247 void AsmTyper::VisitStatements(ZoneList<Statement*>* stmts) {
 248   for (int i = 0; i < stmts->length(); ++i) {
 249     Statement* stmt = stmts->at(i);
 250     RECURSE(Visit(stmt));
 251   }
 252 }
 253
 254
 255 void AsmTyper::VisitBlock(Block* stmt) {
 256   RECURSE(VisitStatements(stmt->statements()));
 257 }
 258
 259
 260 void AsmTyper::VisitExpressionStatement(ExpressionStatement* stmt) {
 261   RECURSE(VisitWithExpectation(stmt->expression(), Type::Any(),
 262                                "expression statement expected to be any"));
 263 }
 264
 265
 266 void AsmTyper::VisitEmptyStatement(EmptyStatement* stmt) {}
 267
 268
 269 void AsmTyper::VisitSloppyBlockFunctionStatement(
 270     SloppyBlockFunctionStatement* stmt) {
 271   Visit(stmt->statement());
 272 }
 273
 274
 275 void AsmTyper::VisitEmptyParentheses(EmptyParentheses* expr) { UNREACHABLE(); }
 276
 277
 278 void AsmTyper::VisitIfStatement(IfStatement* stmt) {
 279   if (!in_function_) {
 280     FAIL(stmt, "if statement inside module body");
 281   }
 282   RECURSE(VisitWithExpectation(stmt->condition(), cache_.kInt32,
 283                                "if condition expected to be integer"));
 284   RECURSE(Visit(stmt->then_statement()));
 285   RECURSE(Visit(stmt->else_statement()));
 286 }
 287
 288
 289 void AsmTyper::VisitContinueStatement(ContinueStatement* stmt) {
 290   if (!in_function_) {
 291     FAIL(stmt, "continue statement inside module body");
 292   }
 293 }
 294
 295
 296 void AsmTyper::VisitBreakStatement(BreakStatement* stmt) {
 297   if (!in_function_) {
 298     FAIL(stmt, "continue statement inside module body");
 299   }
 300 }
 301
 302
 303 void AsmTyper::VisitReturnStatement(ReturnStatement* stmt) {
 304   // Handle module return statement in VisitAsmModule.
 305   if (!in_function_) {
 306     return;
 307   }
 308   RECURSE(
 309       VisitWithExpectation(stmt->expression(), return_type_,
 310                            "return expression expected to have return type"));
 311 }
 312
 313
 314 void AsmTyper::VisitWithStatement(WithStatement* stmt) {
 315   FAIL(stmt, "bad with statement");
 316 }
 317
 318
 319 void AsmTyper::VisitSwitchStatement(SwitchStatement* stmt) {
 320   if (!in_function_) {
 321     FAIL(stmt, "switch statement inside module body");
 322   }
 323   RECURSE(VisitWithExpectation(stmt->tag(), cache_.kInt32,
 324                                "switch expression non-integer"));
 325   ZoneList<CaseClause*>* clauses = stmt->cases();
 326   for (int i = 0; i < clauses->length(); ++i) {
 327     CaseClause* clause = clauses->at(i);
 328     if (clause->is_default()) continue;
 329     Expression* label = clause->label();
 330     RECURSE(
 331         VisitWithExpectation(label, cache_.kInt32, "case label non-integer"));
 332     if (!label->IsLiteral()) FAIL(label, "non-literal case label");
 333     Handle<Object> value = label->AsLiteral()->value();
 334     int32_t value32;
 335     if (!value->ToInt32(&value32)) FAIL(label, "illegal case label value");
 336     // TODO(bradnelson): Detect duplicates.
 337     ZoneList<Statement*>* stmts = clause->statements();
 338     RECURSE(VisitStatements(stmts));
 339   }
 340 }
 341
 342
 343 void AsmTyper::VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
 344
 345
 346 void AsmTyper::VisitDoWhileStatement(DoWhileStatement* stmt) {
 347   if (!in_function_) {
 348     FAIL(stmt, "do statement inside module body");
 349   }
 350   RECURSE(Visit(stmt->body()));
 351   RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 352                                "do condition expected to be integer"));
 353 }
 354
 355
 356 void AsmTyper::VisitWhileStatement(WhileStatement* stmt) {
 357   if (!in_function_) {
 358     FAIL(stmt, "while statement inside module body");
 359   }
 360   RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 361                                "while condition expected to be integer"));
 362   RECURSE(Visit(stmt->body()));
 363 }
 364
 365
 366 void AsmTyper::VisitForStatement(ForStatement* stmt) {
 367   if (!in_function_) {
 368     FAIL(stmt, "for statement inside module body");
 369   }
 370   if (stmt->init() != NULL) {
 371     RECURSE(Visit(stmt->init()));
 372   }
 373   if (stmt->cond() != NULL) {
 374     RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 375                                  "for condition expected to be integer"));
 376   }
 377   if (stmt->next() != NULL) {
 378     RECURSE(Visit(stmt->next()));
 379   }
 380   RECURSE(Visit(stmt->body()));
 381 }
 382
 383
 384 void AsmTyper::VisitForInStatement(ForInStatement* stmt) {
 385   FAIL(stmt, "for-in statement encountered");
 386 }
 387
 388
 389 void AsmTyper::VisitForOfStatement(ForOfStatement* stmt) {
 390   FAIL(stmt, "for-of statement encountered");
 391 }
 392
 393
 394 void AsmTyper::VisitTryCatchStatement(TryCatchStatement* stmt) {
 395   FAIL(stmt, "try statement encountered");
 396 }
 397
 398
 399 void AsmTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
 400   FAIL(stmt, "try statement encountered");
 401 }
 402
 403
 404 void AsmTyper::VisitDebuggerStatement(DebuggerStatement* stmt) {
 405   FAIL(stmt, "debugger statement encountered");
 406 }
 407
 408
 409 void AsmTyper::VisitFunctionLiteral(FunctionLiteral* expr) {
 410   Scope* scope = expr->scope();
 411   DCHECK(scope->is_function_scope());
 412   if (in_function_) {
 413     FAIL(expr, "invalid nested function");
 414   }
 415
 416   if (!expr->bounds().upper->IsFunction()) {
 417     FAIL(expr, "invalid function literal");
 418   }
 419
 420   Type::FunctionType* type = expr->bounds().upper->AsFunction();
 421   Type* save_return_type = return_type_;
 422   return_type_ = type->Result();
 423   in_function_ = true;
 424   local_variable_type_.Clear();
 425   RECURSE(VisitDeclarations(scope->declarations()));
 426   RECURSE(VisitStatements(expr->body()));
 427   in_function_ = false;
 428   return_type_ = save_return_type;
 429   IntersectResult(expr, type);
 430 }
 431
 432
 433 void AsmTyper::VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
 434   FAIL(expr, "function info literal encountered");
 435 }
 436
 437
 438 void AsmTyper::VisitConditional(Conditional* expr) {
 439   RECURSE(VisitWithExpectation(expr->condition(), cache_.kInt32,
 440                                "condition expected to be integer"));
 441   RECURSE(VisitWithExpectation(
 442       expr->then_expression(), expected_type_,
 443       "conditional then branch type mismatch with enclosing expression"));
 444   Type* then_type = computed_type_;
 445   RECURSE(VisitWithExpectation(
 446       expr->else_expression(), expected_type_,
 447       "conditional else branch type mismatch with enclosing expression"));
 448   Type* else_type = computed_type_;
 449   Type* type = Type::Intersect(then_type, else_type, zone());
 450   if (!(type->Is(cache_.kInt32) || type->Is(cache_.kFloat64))) {
 451     FAIL(expr, "ill-typed conditional");
 452   }
 453   IntersectResult(expr, type);
 454 }
 455
 456
 457 void AsmTyper::VisitVariableProxy(VariableProxy* expr) {
 458   Variable* var = expr->var();
 459   if (GetType(var) == NULL) {
 460     FAIL(expr, "unbound variable");
 461   }
 462   Type* type = Type::Intersect(GetType(var), expected_type_, zone());
 463   if (type->Is(cache_.kInt32)) {
 464     type = cache_.kInt32;
 465   }
 466   SetType(var, type);
 467   intish_ = 0;
 468   IntersectResult(expr, type);
 469 }
 470
 471
 472 void AsmTyper::VisitLiteral(Literal* expr) {
 473   intish_ = 0;
 474   Handle<Object> value = expr->value();
 475   if (value->IsNumber()) {
 476     int32_t i;
 477     uint32_t u;
 478     if (expr->raw_value()->ContainsDot()) {
 479       IntersectResult(expr, cache_.kFloat64);
 480     } else if (value->ToUint32(&u)) {
 481       IntersectResult(expr, cache_.kInt32);
 482     } else if (value->ToInt32(&i)) {
 483       IntersectResult(expr, cache_.kInt32);
 484     } else {
 485       FAIL(expr, "illegal number");
 486     }
 487   } else if (value->IsString()) {
 488     IntersectResult(expr, Type::String());
 489   } else if (value->IsUndefined()) {
 490     IntersectResult(expr, Type::Undefined());
 491   } else {
 492     FAIL(expr, "illegal literal");
 493   }
 494 }
 495
 496
 497 void AsmTyper::VisitRegExpLiteral(RegExpLiteral* expr) {
 498   FAIL(expr, "regular expression encountered");
 499 }
 500
 501
 502 void AsmTyper::VisitObjectLiteral(ObjectLiteral* expr) {
 503   if (in_function_) {
 504     FAIL(expr, "object literal in function");
 505   }
 506   // Allowed for asm module's export declaration.
 507   ZoneList<ObjectLiteralProperty*>* props = expr->properties();
 508   for (int i = 0; i < props->length(); ++i) {
 509     ObjectLiteralProperty* prop = props->at(i);
 510     RECURSE(VisitWithExpectation(prop->value(), Type::Any(zone()),
 511                                  "object property expected to be a function"));
 512     if (!computed_type_->IsFunction()) {
 513       FAIL(prop->value(), "non-function in function table");
 514     }
 515   }
 516   IntersectResult(expr, Type::Object(zone()));
 517 }
 518
 519
 520 void AsmTyper::VisitArrayLiteral(ArrayLiteral* expr) {
 521   if (in_function_) {
 522     FAIL(expr, "array literal inside a function");
 523   }
 524   // Allowed for function tables.
 525   ZoneList<Expression*>* values = expr->values();
 526   Type* elem_type = Type::None(zone());
 527   for (int i = 0; i < values->length(); ++i) {
 528     Expression* value = values->at(i);
 529     RECURSE(VisitWithExpectation(value, Type::Any(), "UNREACHABLE"));
 530     if (!computed_type_->IsFunction()) {
 531       FAIL(value, "array component expected to be a function");
 532     }
 533     elem_type = Type::Union(elem_type, computed_type_, zone());
 534   }
 535   array_size_ = values->length();
 536   IntersectResult(expr, Type::Array(elem_type, zone()));
 537 }
 538
 539
 540 void AsmTyper::VisitAssignment(Assignment* expr) {
 541   // Handle function tables and everything else in different passes.
 542   if (!in_function_) {
 543     if (expr->value()->IsArrayLiteral()) {
 544       if (!building_function_tables_) {
 545         return;
 546       }
 547     } else {
 548       if (building_function_tables_) {
 549         return;
 550       }
 551     }
 552   }
 553   if (expr->is_compound()) FAIL(expr, "compound assignment encountered");
 554   Type* type = expected_type_;
 555   RECURSE(VisitWithExpectation(
 556       expr->value(), type, "assignment value expected to match surrounding"));
 557   if (intish_ != 0) {
 558     FAIL(expr, "value still an intish");
 559   }
 560   RECURSE(VisitWithExpectation(expr->target(), computed_type_,
 561                                "assignment target expected to match value"));
 562   if (intish_ != 0) {
 563     FAIL(expr, "value still an intish");
 564   }
 565   IntersectResult(expr, computed_type_);
 566 }
 567
 568
 569 void AsmTyper::VisitYield(Yield* expr) {
 570   FAIL(expr, "yield expression encountered");
 571 }
 572
 573
 574 void AsmTyper::VisitThrow(Throw* expr) {
 575   FAIL(expr, "throw statement encountered");
 576 }
 577
 578
 579 int AsmTyper::ElementShiftSize(Type* type) {
 580   if (type->Is(cache_.kInt8) || type->Is(cache_.kUint8)) return 0;
 581   if (type->Is(cache_.kInt16) || type->Is(cache_.kUint16)) return 1;
 582   if (type->Is(cache_.kInt32) || type->Is(cache_.kUint32) ||
 583       type->Is(cache_.kFloat32))
 584     return 2;
 585   if (type->Is(cache_.kFloat64)) return 3;
 586   return -1;
 587 }
 588
 589
 590 void AsmTyper::VisitHeapAccess(Property* expr) {
 591   Type::ArrayType* array_type = computed_type_->AsArray();
 592   size_t size = array_size_;
 593   Type* type = array_type->AsArray()->Element();
 594   if (type->IsFunction()) {
 595     BinaryOperation* bin = expr->key()->AsBinaryOperation();
 596     if (bin == NULL || bin->op() != Token::BIT_AND) {
 597       FAIL(expr->key(), "expected & in call");
 598     }
 599     RECURSE(VisitWithExpectation(bin->left(), cache_.kInt32,
 600                                  "array index expected to be integer"));
 601     Literal* right = bin->right()->AsLiteral();
 602     if (right == NULL || right->raw_value()->ContainsDot()) {
 603       FAIL(right, "call mask must be integer");
 604     }
 605     RECURSE(VisitWithExpectation(bin->right(), cache_.kInt32,
 606                                  "call mask expected to be integer"));
 607     if (static_cast<size_t>(right->raw_value()->AsNumber()) != size - 1) {
 608       FAIL(right, "call mask must match function table");
 609     }
 610     bin->set_bounds(Bounds(cache_.kInt32));
 611   } else {
 612     BinaryOperation* bin = expr->key()->AsBinaryOperation();
 613     if (bin == NULL || bin->op() != Token::SAR) {
 614       FAIL(expr->key(), "expected >> in heap access");
 615     }
 616     RECURSE(VisitWithExpectation(bin->left(), cache_.kInt32,
 617                                  "array index expected to be integer"));
 618     Literal* right = bin->right()->AsLiteral();
 619     if (right == NULL || right->raw_value()->ContainsDot()) {
 620       FAIL(right, "heap access shift must be integer");
 621     }
 622     RECURSE(VisitWithExpectation(bin->right(), cache_.kInt32,
 623                                  "array shift expected to be integer"));
 624     int n = static_cast<int>(right->raw_value()->AsNumber());
 625     int expected_shift = ElementShiftSize(type);
 626     if (expected_shift < 0 || n != expected_shift) {
 627       FAIL(right, "heap access shift must match element size");
 628     }
 629     bin->set_bounds(Bounds(cache_.kInt32));
 630   }
 631   IntersectResult(expr, type);
 632 }
 633
 634
 635 void AsmTyper::VisitProperty(Property* expr) {
 636   // stdlib.Math.x
 637   Property* inner_prop = expr->obj()->AsProperty();
 638   if (inner_prop != NULL) {
 639     // Get property name.
 640     Literal* key = expr->key()->AsLiteral();
 641     if (key == NULL || !key->IsPropertyName())
 642       FAIL(expr, "invalid type annotation on property 2");
 643     Handle<String> name = key->AsPropertyName();
 644
 645     // Check that inner property name is "Math".
 646     Literal* math_key = inner_prop->key()->AsLiteral();
 647     if (math_key == NULL || !math_key->IsPropertyName() ||
 648         !math_key->AsPropertyName()->IsUtf8EqualTo(CStrVector("Math")))
 649       FAIL(expr, "invalid type annotation on stdlib (a1)");
 650
 651     // Check that object is stdlib.
 652     VariableProxy* proxy = inner_prop->obj()->AsVariableProxy();
 653     if (proxy == NULL) FAIL(expr, "invalid type annotation on stdlib (a2)");
 654     Variable* var = proxy->var();
 655     if (var->location() != VariableLocation::PARAMETER || var->index() != 0)
 656       FAIL(expr, "invalid type annotation on stdlib (a3)");
 657
 658     // Look up library type.
 659     Type* type = LibType(stdlib_math_types_, name);
 660     if (type == NULL) FAIL(expr, "unknown standard function 3 ");
 661     SetResult(expr, type);
 662     return;
 663   }
 664
 665   // Only recurse at this point so that we avoid needing
 666   // stdlib.Math to have a real type.
 667   RECURSE(VisitWithExpectation(expr->obj(), Type::Any(),
 668                                "property holder expected to be object"));
 669
 670   // For heap view or function table access.
 671   if (computed_type_->IsArray()) {
 672     VisitHeapAccess(expr);
 673     return;
 674   }
 675
 676   // Get property name.
 677   Literal* key = expr->key()->AsLiteral();
 678   if (key == NULL || !key->IsPropertyName())
 679     FAIL(expr, "invalid type annotation on property 3");
 680   Handle<String> name = key->AsPropertyName();
 681
 682   // stdlib.x or foreign.x
 683   VariableProxy* proxy = expr->obj()->AsVariableProxy();
 684   if (proxy != NULL) {
 685     Variable* var = proxy->var();
 686     if (var->location() != VariableLocation::PARAMETER) {
 687       FAIL(expr, "invalid type annotation on variable");
 688     }
 689     switch (var->index()) {
 690       case 0: {
 691         // Object is stdlib, look up library type.
 692         Type* type = LibType(stdlib_types_, name);
 693         if (type == NULL) {
 694           FAIL(expr, "unknown standard function 4");
 695         }
 696         SetResult(expr, type);
 697         return;
 698       }
 699       case 1:
 700         // Object is foreign lib.
 701         SetResult(expr, expected_type_);
 702         return;
 703       default:
 704         FAIL(expr, "invalid type annotation on parameter");
 705     }
 706   }
 707
 708   FAIL(expr, "invalid property access");
 709 }
 710
 711
 712 void AsmTyper::VisitCall(Call* expr) {
 713   RECURSE(VisitWithExpectation(expr->expression(), Type::Any(),
 714                                "callee expected to be any"));
 715   if (computed_type_->IsFunction()) {
 716     Type::FunctionType* fun_type = computed_type_->AsFunction();
 717     ZoneList<Expression*>* args = expr->arguments();
 718     if (fun_type->Arity() != args->length()) {
 719       FAIL(expr, "call with wrong arity");
 720     }
 721     for (int i = 0; i < args->length(); ++i) {
 722       Expression* arg = args->at(i);
 723       RECURSE(VisitWithExpectation(
 724           arg, fun_type->Parameter(i),
 725           "call argument expected to match callee parameter"));
 726     }
 727     IntersectResult(expr, fun_type->Result());
 728   } else if (computed_type_->Is(Type::Any())) {
 729     // For foreign calls.
 730     ZoneList<Expression*>* args = expr->arguments();
 731     for (int i = 0; i < args->length(); ++i) {
 732       Expression* arg = args->at(i);
 733       RECURSE(VisitWithExpectation(arg, Type::Any(),
 734                                    "foreign call argument expected to be any"));
 735     }
 736     IntersectResult(expr, Type::Number());
 737   } else {
 738     FAIL(expr, "invalid callee");
 739   }
 740 }
 741
 742
 743 void AsmTyper::VisitCallNew(CallNew* expr) {
 744   if (in_function_) {
 745     FAIL(expr, "new not allowed in module function");
 746   }
 747   RECURSE(VisitWithExpectation(expr->expression(), Type::Any(),
 748                                "expected stdlib function"));
 749   if (computed_type_->IsFunction()) {
 750     Type::FunctionType* fun_type = computed_type_->AsFunction();
 751     ZoneList<Expression*>* args = expr->arguments();
 752     if (fun_type->Arity() != args->length())
 753       FAIL(expr, "call with wrong arity");
 754     for (int i = 0; i < args->length(); ++i) {
 755       Expression* arg = args->at(i);
 756       RECURSE(VisitWithExpectation(
 757           arg, fun_type->Parameter(i),
 758           "constructor argument expected to match callee parameter"));
 759     }
 760     IntersectResult(expr, fun_type->Result());
 761     return;
 762   }
 763
 764   FAIL(expr, "ill-typed new operator");
 765 }
 766
 767
 768 void AsmTyper::VisitCallRuntime(CallRuntime* expr) {
 769   // Allow runtime calls for now.
 770 }
 771
 772
 773 void AsmTyper::VisitUnaryOperation(UnaryOperation* expr) {
 774   switch (expr->op()) {
 775     case Token::NOT:  // Used to encode != and !==
 776       RECURSE(VisitWithExpectation(expr->expression(), cache_.kInt32,
 777                                    "operand expected to be integer"));
 778       IntersectResult(expr, cache_.kInt32);
 779       return;
 780     case Token::DELETE:
 781       FAIL(expr, "delete operator encountered");
 782     case Token::VOID:
 783       FAIL(expr, "void operator encountered");
 784     case Token::TYPEOF:
 785       FAIL(expr, "typeof operator encountered");
 786     default:
 787       UNREACHABLE();
 788   }
 789 }
 790
 791
 792 void AsmTyper::VisitCountOperation(CountOperation* expr) {
 793   FAIL(expr, "increment or decrement operator encountered");
 794 }
 795
 796
 797 void AsmTyper::VisitBinaryOperation(BinaryOperation* expr) {
 798   switch (expr->op()) {
 799     case Token::COMMA: {
 800       RECURSE(VisitWithExpectation(expr->left(), Type::Any(),
 801                                    "left comma operand expected to be any"));
 802       RECURSE(VisitWithExpectation(expr->right(), Type::Any(),
 803                                    "right comma operand expected to be any"));
 804       IntersectResult(expr, computed_type_);
 805       return;
 806     }
 807     case Token::OR:
 808     case Token::AND:
 809       FAIL(expr, "logical operator encountered");
 810     case Token::BIT_OR:
 811     case Token::BIT_AND:
 812     case Token::BIT_XOR:
 813     case Token::SHL:
 814     case Token::SHR:
 815     case Token::SAR: {
 816       // BIT_OR allows Any since it is used as a type coercion.
 817       // BIT_XOR allows Number since it is used as a type coercion (encoding ~).
 818       Type* expectation =
 819           expr->op() == Token::BIT_OR
 820               ? Type::Any()
 821               : expr->op() == Token::BIT_XOR ? Type::Number() : cache_.kInt32;
 822       Type* result =
 823           expr->op() == Token::SHR ? Type::Unsigned32() : cache_.kInt32;
 824       RECURSE(VisitWithExpectation(expr->left(), expectation,
 825                                    "left bit operand expected to be integer"));
 826       int left_intish = intish_;
 827       RECURSE(VisitWithExpectation(expr->right(), expectation,
 828                                    "right bit operand expected to be integer"));
 829       int right_intish = intish_;
 830       if (left_intish > kMaxUncombinedAdditiveSteps) {
 831         FAIL(expr, "too many consecutive additive ops");
 832       }
 833       if (right_intish > kMaxUncombinedAdditiveSteps) {
 834         FAIL(expr, "too many consecutive additive ops");
 835       }
 836       intish_ = 0;
 837       IntersectResult(expr, result);
 838       return;
 839     }
 840     case Token::ADD:
 841     case Token::SUB:
 842     case Token::MUL:
 843     case Token::DIV:
 844     case Token::MOD: {
 845       RECURSE(VisitWithExpectation(
 846           expr->left(), Type::Number(),
 847           "left arithmetic operand expected to be number"));
 848       Type* left_type = computed_type_;
 849       int left_intish = intish_;
 850       RECURSE(VisitWithExpectation(
 851           expr->right(), Type::Number(),
 852           "right arithmetic operand expected to be number"));
 853       Type* right_type = computed_type_;
 854       int right_intish = intish_;
 855       Type* type = Type::Union(left_type, right_type, zone());
 856       if (type->Is(cache_.kInt32)) {
 857         if (expr->op() == Token::MUL) {
 858           if (!expr->left()->IsLiteral() && !expr->right()->IsLiteral()) {
 859             FAIL(expr, "direct integer multiply forbidden");
 860           }
 861           intish_ = 0;
 862           IntersectResult(expr, cache_.kInt32);
 863           return;
 864         } else {
 865           intish_ = left_intish + right_intish + 1;
 866           if (expr->op() == Token::ADD || expr->op() == Token::SUB) {
 867             if (intish_ > kMaxUncombinedAdditiveSteps) {
 868               FAIL(expr, "too many consecutive additive ops");
 869             }
 870           } else {
 871             if (intish_ > kMaxUncombinedMultiplicativeSteps) {
 872               FAIL(expr, "too many consecutive multiplicative ops");
 873             }
 874           }
 875           IntersectResult(expr, cache_.kInt32);
 876           return;
 877         }
 878       } else if (type->Is(Type::Number())) {
 879         IntersectResult(expr, cache_.kFloat64);
 880         return;
 881       } else {
 882         FAIL(expr, "ill-typed arithmetic operation");
 883       }
 884     }
 885     default:
 886       UNREACHABLE();
 887   }
 888 }
 889
 890
 891 void AsmTyper::VisitCompareOperation(CompareOperation* expr) {
 892   RECURSE(
 893       VisitWithExpectation(expr->left(), Type::Number(),
 894                            "left comparison operand expected to be number"));
 895   Type* left_type = computed_type_;
 896   RECURSE(
 897       VisitWithExpectation(expr->right(), Type::Number(),
 898                            "right comparison operand expected to be number"));
 899   Type* right_type = computed_type_;
 900   Type* type = Type::Union(left_type, right_type, zone());
 901   expr->set_combined_type(type);
 902   if (type->Is(Type::Integral32()) || type->Is(Type::UntaggedFloat64())) {
 903     IntersectResult(expr, cache_.kInt32);
 904   } else {
 905     FAIL(expr, "ill-typed comparison operation");
 906   }
 907 }
 908
 909
 910 void AsmTyper::VisitThisFunction(ThisFunction* expr) {
 911   FAIL(expr, "this function not allowed");
 912 }
 913
 914
 915 void AsmTyper::VisitDeclarations(ZoneList<Declaration*>* decls) {
 916   for (int i = 0; i < decls->length(); ++i) {
 917     Declaration* decl = decls->at(i);
 918     RECURSE(Visit(decl));
 919   }
 920 }
 921
 922
 923 void AsmTyper::VisitImportDeclaration(ImportDeclaration* decl) {
 924   FAIL(decl, "import declaration encountered");
 925 }
 926
 927
 928 void AsmTyper::VisitExportDeclaration(ExportDeclaration* decl) {
 929   FAIL(decl, "export declaration encountered");
 930 }
 931
 932
 933 void AsmTyper::VisitClassLiteral(ClassLiteral* expr) {
 934   FAIL(expr, "class literal not allowed");
 935 }
 936
 937
 938 void AsmTyper::VisitSpread(Spread* expr) { FAIL(expr, "spread not allowed"); }
 939
 940
 941 void AsmTyper::VisitSuperPropertyReference(SuperPropertyReference* expr) {
 942   FAIL(expr, "super property reference not allowed");
 943 }
 944
 945
 946 void AsmTyper::VisitSuperCallReference(SuperCallReference* expr) {
 947   FAIL(expr, "call reference not allowed");
 948 }
 949
 950
 951 void AsmTyper::InitializeStdlib() {
 952   Type* number_type = Type::Number(zone());
 953   Type* double_type = cache_.kFloat64;
 954   Type* double_fn1_type = Type::Function(double_type, double_type, zone());
 955   Type* double_fn2_type =
 956       Type::Function(double_type, double_type, double_type, zone());
 957
 958   Type* fround_type = Type::Function(cache_.kFloat32, number_type, zone());
 959   Type* imul_type =
 960       Type::Function(cache_.kInt32, cache_.kInt32, cache_.kInt32, zone());
 961   // TODO(bradnelson): currently only approximating the proper intersection type
 962   // (which we cannot currently represent).
 963   Type* abs_type = Type::Function(number_type, number_type, zone());
 964
 965   struct Assignment {
 966     const char* name;
 967     Type* type;
 968   };
 969
 970   const Assignment math[] = {
 971       {"PI", double_type},       {"E", double_type},
 972       {"LN2", double_type},      {"LN10", double_type},
 973       {"LOG2E", double_type},    {"LOG10E", double_type},
 974       {"SQRT2", double_type},    {"SQRT1_2", double_type},
 975       {"imul", imul_type},       {"abs", abs_type},
 976       {"ceil", double_fn1_type}, {"floor", double_fn1_type},
 977       {"fround", fround_type},   {"pow", double_fn2_type},
 978       {"exp", double_fn1_type},  {"log", double_fn1_type},
 979       {"min", double_fn2_type},  {"max", double_fn2_type},
 980       {"sqrt", double_fn1_type}, {"cos", double_fn1_type},
 981       {"sin", double_fn1_type},  {"tan", double_fn1_type},
 982       {"acos", double_fn1_type}, {"asin", double_fn1_type},
 983       {"atan", double_fn1_type}, {"atan2", double_fn2_type}};
 984   for (unsigned i = 0; i < arraysize(math); ++i) {
 985     stdlib_math_types_[math[i].name] = math[i].type;
 986   }
 987
 988   stdlib_types_["Infinity"] = double_type;
 989   stdlib_types_["NaN"] = double_type;
 990   Type* buffer_type = Type::Any(zone());
 991 #define TYPED_ARRAY(TypeName, type_name, TYPE_NAME, ctype, size) \
 992   stdlib_types_[#TypeName "Array"] =                             \
 993       Type::Function(cache_.k##TypeName##Array, buffer_type, zone());
 994   TYPED_ARRAYS(TYPED_ARRAY)
 995 #undef TYPED_ARRAY
 996
 997 #define TYPED_ARRAY(TypeName, type_name, TYPE_NAME, ctype, size) \
 998   stdlib_heap_types_[#TypeName "Array"] =                        \
 999       Type::Function(cache_.k##TypeName##Array, buffer_type, zone());
1000   TYPED_ARRAYS(TYPED_ARRAY)
1001 #undef TYPED_ARRAY
1002 }
1003
1004
1005 Type* AsmTyper::LibType(ObjectTypeMap map, Handle<String> name) {
1006   base::SmartArrayPointer<char> aname = name->ToCString();
1007   ObjectTypeMap::iterator i = map.find(std::string(aname.get()));
1008   if (i == map.end()) {
1009     return NULL;
1010   }
1011   return i->second;
1012 }
1013
1014
1015 void AsmTyper::SetType(Variable* variable, Type* type) {
1016   ZoneHashMap::Entry* entry;
1017   if (in_function_) {
1018     entry = local_variable_type_.LookupOrInsert(
1019         variable, ComputePointerHash(variable), ZoneAllocationPolicy(zone()));
1020   } else {
1021     entry = global_variable_type_.LookupOrInsert(
1022         variable, ComputePointerHash(variable), ZoneAllocationPolicy(zone()));
1023   }
1024   entry->value = reinterpret_cast<void*>(type);
1025 }
1026
1027
1028 Type* AsmTyper::GetType(Variable* variable) {
1029   i::ZoneHashMap::Entry* entry = NULL;
1030   if (in_function_) {
1031     entry = local_variable_type_.Lookup(variable, ComputePointerHash(variable));
1032   }
1033   if (entry == NULL) {
1034     entry =
1035         global_variable_type_.Lookup(variable, ComputePointerHash(variable));
1036   }
1037   if (entry == NULL) {
1038     return NULL;
1039   } else {
1040     return reinterpret_cast<Type*>(entry->value);
1041   }
1042 }
1043
1044
1045 void AsmTyper::SetResult(Expression* expr, Type* type) {
1046   computed_type_ = type;
1047   expr->set_bounds(Bounds(computed_type_));
1048 }
1049
1050
1051 void AsmTyper::IntersectResult(Expression* expr, Type* type) {
1052   computed_type_ = type;
1053   Type* bounded_type = Type::Intersect(computed_type_, expected_type_, zone());
1054   expr->set_bounds(Bounds(bounded_type));
1055 }
1056
1057
1058 void AsmTyper::VisitWithExpectation(Expression* expr, Type* expected_type,
1059                                     const char* msg) {
1060   Type* save = expected_type_;
1061   expected_type_ = expected_type;
1062   RECURSE(Visit(expr));
1063   Type* bounded_type = Type::Intersect(computed_type_, expected_type_, zone());
1064   if (bounded_type->Is(Type::None(zone()))) {
1065 #ifdef DEBUG
1066     PrintF("Computed type: ");
1067     computed_type_->Print();
1068     PrintF("Expected type: ");
1069     expected_type_->Print();
1070 #endif
1071     FAIL(expr, msg);
1072   }
1073   expected_type_ = save;
1074 }
1075 }  // namespace internal
1076 }  // namespace v8