deps/v8/src/ast.cc

   1 // Copyright 2011 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include "v8.h"
  29
  30 #include "ast.h"
  31 #include "parser.h"
  32 #include "scopes.h"
  33 #include "string-stream.h"
  34 #include "type-info.h"
  35
  36 namespace v8 {
  37 namespace internal {
  38
  39 // ----------------------------------------------------------------------------
  40 // All the Accept member functions for each syntax tree node type.
  41
  42 #define DECL_ACCEPT(type)                                       \
  43   void type::Accept(AstVisitor* v) { v->Visit##type(this); }
  44 AST_NODE_LIST(DECL_ACCEPT)
  45 #undef DECL_ACCEPT
  46
  47
  48 // ----------------------------------------------------------------------------
  49 // Implementation of other node functionality.
  50
  51 Assignment* ExpressionStatement::StatementAsSimpleAssignment() {
  52   return (expression()->AsAssignment() != NULL &&
  53           !expression()->AsAssignment()->is_compound())
  54       ? expression()->AsAssignment()
  55       : NULL;
  56 }
  57
  58
  59 CountOperation* ExpressionStatement::StatementAsCountOperation() {
  60   return expression()->AsCountOperation();
  61 }
  62
  63
  64 VariableProxy::VariableProxy(Isolate* isolate, Variable* var)
  65     : Expression(isolate),
  66       name_(var->name()),
  67       var_(NULL),  // Will be set by the call to BindTo.
  68       is_this_(var->is_this()),
  69       inside_with_(false),
  70       is_trivial_(false),
  71       position_(RelocInfo::kNoPosition) {
  72   BindTo(var);
  73 }
  74
  75
  76 VariableProxy::VariableProxy(Isolate* isolate,
  77                              Handle<String> name,
  78                              bool is_this,
  79                              bool inside_with,
  80                              int position)
  81     : Expression(isolate),
  82       name_(name),
  83       var_(NULL),
  84       is_this_(is_this),
  85       inside_with_(inside_with),
  86       is_trivial_(false),
  87       position_(position) {
  88   // Names must be canonicalized for fast equality checks.
  89   ASSERT(name->IsSymbol());
  90 }
  91
  92
  93 void VariableProxy::BindTo(Variable* var) {
  94   ASSERT(var_ == NULL);  // must be bound only once
  95   ASSERT(var != NULL);  // must bind
  96   ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name()));
  97   // Ideally CONST-ness should match. However, this is very hard to achieve
  98   // because we don't know the exact semantics of conflicting (const and
  99   // non-const) multiple variable declarations, const vars introduced via
 100   // eval() etc.  Const-ness and variable declarations are a complete mess
 101   // in JS. Sigh...
 102   var_ = var;
 103   var->set_is_used(true);
 104 }
 105
 106
 107 Assignment::Assignment(Isolate* isolate,
 108                        Token::Value op,
 109                        Expression* target,
 110                        Expression* value,
 111                        int pos)
 112     : Expression(isolate),
 113       op_(op),
 114       target_(target),
 115       value_(value),
 116       pos_(pos),
 117       binary_operation_(NULL),
 118       compound_load_id_(kNoNumber),
 119       assignment_id_(GetNextId(isolate)),
 120       block_start_(false),
 121       block_end_(false),
 122       is_monomorphic_(false) {
 123   ASSERT(Token::IsAssignmentOp(op));
 124   if (is_compound()) {
 125     binary_operation_ =
 126         new(isolate->zone()) BinaryOperation(isolate,
 127                                              binary_op(),
 128                                              target,
 129                                              value,
 130                                              pos + 1);
 131     compound_load_id_ = GetNextId(isolate);
 132   }
 133 }
 134
 135
 136 Token::Value Assignment::binary_op() const {
 137   switch (op_) {
 138     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
 139     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
 140     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
 141     case Token::ASSIGN_SHL: return Token::SHL;
 142     case Token::ASSIGN_SAR: return Token::SAR;
 143     case Token::ASSIGN_SHR: return Token::SHR;
 144     case Token::ASSIGN_ADD: return Token::ADD;
 145     case Token::ASSIGN_SUB: return Token::SUB;
 146     case Token::ASSIGN_MUL: return Token::MUL;
 147     case Token::ASSIGN_DIV: return Token::DIV;
 148     case Token::ASSIGN_MOD: return Token::MOD;
 149     default: UNREACHABLE();
 150   }
 151   return Token::ILLEGAL;
 152 }
 153
 154
 155 bool FunctionLiteral::AllowsLazyCompilation() {
 156   return scope()->AllowsLazyCompilation();
 157 }
 158
 159
 160 ObjectLiteral::Property::Property(Literal* key, Expression* value) {
 161   emit_store_ = true;
 162   key_ = key;
 163   value_ = value;
 164   Object* k = *key->handle();
 165   if (k->IsSymbol() && HEAP->Proto_symbol()->Equals(String::cast(k))) {
 166     kind_ = PROTOTYPE;
 167   } else if (value_->AsMaterializedLiteral() != NULL) {
 168     kind_ = MATERIALIZED_LITERAL;
 169   } else if (value_->AsLiteral() != NULL) {
 170     kind_ = CONSTANT;
 171   } else {
 172     kind_ = COMPUTED;
 173   }
 174 }
 175
 176
 177 ObjectLiteral::Property::Property(bool is_getter, FunctionLiteral* value) {
 178   Isolate* isolate = Isolate::Current();
 179   emit_store_ = true;
 180   key_ = new(isolate->zone()) Literal(isolate, value->name());
 181   value_ = value;
 182   kind_ = is_getter ? GETTER : SETTER;
 183 }
 184
 185
 186 bool ObjectLiteral::Property::IsCompileTimeValue() {
 187   return kind_ == CONSTANT ||
 188       (kind_ == MATERIALIZED_LITERAL &&
 189        CompileTimeValue::IsCompileTimeValue(value_));
 190 }
 191
 192
 193 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
 194   emit_store_ = emit_store;
 195 }
 196
 197
 198 bool ObjectLiteral::Property::emit_store() {
 199   return emit_store_;
 200 }
 201
 202
 203 bool IsEqualString(void* first, void* second) {
 204   ASSERT((*reinterpret_cast<String**>(first))->IsString());
 205   ASSERT((*reinterpret_cast<String**>(second))->IsString());
 206   Handle<String> h1(reinterpret_cast<String**>(first));
 207   Handle<String> h2(reinterpret_cast<String**>(second));
 208   return (*h1)->Equals(*h2);
 209 }
 210
 211
 212 bool IsEqualNumber(void* first, void* second) {
 213   ASSERT((*reinterpret_cast<Object**>(first))->IsNumber());
 214   ASSERT((*reinterpret_cast<Object**>(second))->IsNumber());
 215
 216   Handle<Object> h1(reinterpret_cast<Object**>(first));
 217   Handle<Object> h2(reinterpret_cast<Object**>(second));
 218   if (h1->IsSmi()) {
 219     return h2->IsSmi() && *h1 == *h2;
 220   }
 221   if (h2->IsSmi()) return false;
 222   Handle<HeapNumber> n1 = Handle<HeapNumber>::cast(h1);
 223   Handle<HeapNumber> n2 = Handle<HeapNumber>::cast(h2);
 224   ASSERT(isfinite(n1->value()));
 225   ASSERT(isfinite(n2->value()));
 226   return n1->value() == n2->value();
 227 }
 228
 229
 230 void ObjectLiteral::CalculateEmitStore() {
 231   HashMap properties(&IsEqualString);
 232   HashMap elements(&IsEqualNumber);
 233   for (int i = this->properties()->length() - 1; i >= 0; i--) {
 234     ObjectLiteral::Property* property = this->properties()->at(i);
 235     Literal* literal = property->key();
 236     Handle<Object> handle = literal->handle();
 237
 238     if (handle->IsNull()) {
 239       continue;
 240     }
 241
 242     uint32_t hash;
 243     HashMap* table;
 244     void* key;
 245     Factory* factory = Isolate::Current()->factory();
 246     if (handle->IsSymbol()) {
 247       Handle<String> name(String::cast(*handle));
 248       if (name->AsArrayIndex(&hash)) {
 249         Handle<Object> key_handle = factory->NewNumberFromUint(hash);
 250         key = key_handle.location();
 251         table = &elements;
 252       } else {
 253         key = name.location();
 254         hash = name->Hash();
 255         table = &properties;
 256       }
 257     } else if (handle->ToArrayIndex(&hash)) {
 258       key = handle.location();
 259       table = &elements;
 260     } else {
 261       ASSERT(handle->IsNumber());
 262       double num = handle->Number();
 263       char arr[100];
 264       Vector<char> buffer(arr, ARRAY_SIZE(arr));
 265       const char* str = DoubleToCString(num, buffer);
 266       Handle<String> name = factory->NewStringFromAscii(CStrVector(str));
 267       key = name.location();
 268       hash = name->Hash();
 269       table = &properties;
 270     }
 271     // If the key of a computed property is in the table, do not emit
 272     // a store for the property later.
 273     if (property->kind() == ObjectLiteral::Property::COMPUTED) {
 274       if (table->Lookup(key, hash, false) != NULL) {
 275         property->set_emit_store(false);
 276       }
 277     }
 278     // Add key to the table.
 279     table->Lookup(key, hash, true);
 280   }
 281 }
 282
 283
 284 void TargetCollector::AddTarget(Label* target) {
 285   // Add the label to the collector, but discard duplicates.
 286   int length = targets_.length();
 287   for (int i = 0; i < length; i++) {
 288     if (targets_[i] == target) return;
 289   }
 290   targets_.Add(target);
 291 }
 292
 293
 294 bool UnaryOperation::ResultOverwriteAllowed() {
 295   switch (op_) {
 296     case Token::BIT_NOT:
 297     case Token::SUB:
 298       return true;
 299     default:
 300       return false;
 301   }
 302 }
 303
 304
 305 bool BinaryOperation::ResultOverwriteAllowed() {
 306   switch (op_) {
 307     case Token::COMMA:
 308     case Token::OR:
 309     case Token::AND:
 310       return false;
 311     case Token::BIT_OR:
 312     case Token::BIT_XOR:
 313     case Token::BIT_AND:
 314     case Token::SHL:
 315     case Token::SAR:
 316     case Token::SHR:
 317     case Token::ADD:
 318     case Token::SUB:
 319     case Token::MUL:
 320     case Token::DIV:
 321     case Token::MOD:
 322       return true;
 323     default:
 324       UNREACHABLE();
 325   }
 326   return false;
 327 }
 328
 329
 330 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
 331                                               Handle<String>* check) {
 332   if (op_ != Token::EQ && op_ != Token::EQ_STRICT) return false;
 333
 334   UnaryOperation* left_unary = left_->AsUnaryOperation();
 335   UnaryOperation* right_unary = right_->AsUnaryOperation();
 336   Literal* left_literal = left_->AsLiteral();
 337   Literal* right_literal = right_->AsLiteral();
 338
 339   // Check for the pattern: typeof <expression> == <string literal>.
 340   if (left_unary != NULL && left_unary->op() == Token::TYPEOF &&
 341       right_literal != NULL && right_literal->handle()->IsString()) {
 342     *expr = left_unary->expression();
 343     *check = Handle<String>::cast(right_literal->handle());
 344     return true;
 345   }
 346
 347   // Check for the pattern: <string literal> == typeof <expression>.
 348   if (right_unary != NULL && right_unary->op() == Token::TYPEOF &&
 349       left_literal != NULL && left_literal->handle()->IsString()) {
 350     *expr = right_unary->expression();
 351     *check = Handle<String>::cast(left_literal->handle());
 352     return true;
 353   }
 354
 355   return false;
 356 }
 357
 358
 359 bool CompareOperation::IsLiteralCompareUndefined(Expression** expr) {
 360   if (op_ != Token::EQ_STRICT) return false;
 361
 362   UnaryOperation* left_unary = left_->AsUnaryOperation();
 363   UnaryOperation* right_unary = right_->AsUnaryOperation();
 364
 365   // Check for the pattern: <expression> === void <literal>.
 366   if (right_unary != NULL && right_unary->op() == Token::VOID &&
 367       right_unary->expression()->AsLiteral() != NULL) {
 368     *expr = left_;
 369     return true;
 370   }
 371
 372   // Check for the pattern: void <literal> === <expression>.
 373   if (left_unary != NULL && left_unary->op() == Token::VOID &&
 374       left_unary->expression()->AsLiteral() != NULL) {
 375     *expr = right_;
 376     return true;
 377   }
 378
 379   return false;
 380 }
 381
 382
 383 // ----------------------------------------------------------------------------
 384 // Inlining support
 385
 386 bool Declaration::IsInlineable() const {
 387   return proxy()->var()->IsStackAllocated() && fun() == NULL;
 388 }
 389
 390
 391 bool TargetCollector::IsInlineable() const {
 392   UNREACHABLE();
 393   return false;
 394 }
 395
 396
 397 bool ForInStatement::IsInlineable() const {
 398   return false;
 399 }
 400
 401
 402 bool WithStatement::IsInlineable() const {
 403   return false;
 404 }
 405
 406
 407 bool SwitchStatement::IsInlineable() const {
 408   return false;
 409 }
 410
 411
 412 bool TryStatement::IsInlineable() const {
 413   return false;
 414 }
 415
 416
 417 bool TryCatchStatement::IsInlineable() const {
 418   return false;
 419 }
 420
 421
 422 bool TryFinallyStatement::IsInlineable() const {
 423   return false;
 424 }
 425
 426
 427 bool DebuggerStatement::IsInlineable() const {
 428   return false;
 429 }
 430
 431
 432 bool Throw::IsInlineable() const {
 433   return exception()->IsInlineable();
 434 }
 435
 436
 437 bool MaterializedLiteral::IsInlineable() const {
 438   // TODO(1322): Allow materialized literals.
 439   return false;
 440 }
 441
 442
 443 bool FunctionLiteral::IsInlineable() const {
 444   // TODO(1322): Allow materialized literals.
 445   return false;
 446 }
 447
 448
 449 bool ThisFunction::IsInlineable() const {
 450   return false;
 451 }
 452
 453
 454 bool SharedFunctionInfoLiteral::IsInlineable() const {
 455   return false;
 456 }
 457
 458
 459 bool ForStatement::IsInlineable() const {
 460   return (init() == NULL || init()->IsInlineable())
 461       && (cond() == NULL || cond()->IsInlineable())
 462       && (next() == NULL || next()->IsInlineable())
 463       && body()->IsInlineable();
 464 }
 465
 466
 467 bool WhileStatement::IsInlineable() const {
 468   return cond()->IsInlineable()
 469       && body()->IsInlineable();
 470 }
 471
 472
 473 bool DoWhileStatement::IsInlineable() const {
 474   return cond()->IsInlineable()
 475       && body()->IsInlineable();
 476 }
 477
 478
 479 bool ContinueStatement::IsInlineable() const {
 480   return true;
 481 }
 482
 483
 484 bool BreakStatement::IsInlineable() const {
 485   return true;
 486 }
 487
 488
 489 bool EmptyStatement::IsInlineable() const {
 490   return true;
 491 }
 492
 493
 494 bool Literal::IsInlineable() const {
 495   return true;
 496 }
 497
 498
 499 bool Block::IsInlineable() const {
 500   const int count = statements_.length();
 501   for (int i = 0; i < count; ++i) {
 502     if (!statements_[i]->IsInlineable()) return false;
 503   }
 504   return true;
 505 }
 506
 507
 508 bool ExpressionStatement::IsInlineable() const {
 509   return expression()->IsInlineable();
 510 }
 511
 512
 513 bool IfStatement::IsInlineable() const {
 514   return condition()->IsInlineable()
 515       && then_statement()->IsInlineable()
 516       && else_statement()->IsInlineable();
 517 }
 518
 519
 520 bool ReturnStatement::IsInlineable() const {
 521   return expression()->IsInlineable();
 522 }
 523
 524
 525 bool Conditional::IsInlineable() const {
 526   return condition()->IsInlineable() && then_expression()->IsInlineable() &&
 527       else_expression()->IsInlineable();
 528 }
 529
 530
 531 bool VariableProxy::IsInlineable() const {
 532   return var()->IsUnallocated() || var()->IsStackAllocated();
 533 }
 534
 535
 536 bool Assignment::IsInlineable() const {
 537   return target()->IsInlineable() && value()->IsInlineable();
 538 }
 539
 540
 541 bool Property::IsInlineable() const {
 542   return obj()->IsInlineable() && key()->IsInlineable();
 543 }
 544
 545
 546 bool Call::IsInlineable() const {
 547   if (!expression()->IsInlineable()) return false;
 548   const int count = arguments()->length();
 549   for (int i = 0; i < count; ++i) {
 550     if (!arguments()->at(i)->IsInlineable()) return false;
 551   }
 552   return true;
 553 }
 554
 555
 556 bool CallNew::IsInlineable() const {
 557   if (!expression()->IsInlineable()) return false;
 558   const int count = arguments()->length();
 559   for (int i = 0; i < count; ++i) {
 560     if (!arguments()->at(i)->IsInlineable()) return false;
 561   }
 562   return true;
 563 }
 564
 565
 566 bool CallRuntime::IsInlineable() const {
 567   // Don't try to inline JS runtime calls because we don't (currently) even
 568   // optimize them.
 569   if (is_jsruntime()) return false;
 570   // Don't inline the %_ArgumentsLength or %_Arguments because their
 571   // implementation will not work.  There is no stack frame to get them
 572   // from.
 573   if (function()->intrinsic_type == Runtime::INLINE &&
 574       (name()->IsEqualTo(CStrVector("_ArgumentsLength")) ||
 575        name()->IsEqualTo(CStrVector("_Arguments")))) {
 576     return false;
 577   }
 578   const int count = arguments()->length();
 579   for (int i = 0; i < count; ++i) {
 580     if (!arguments()->at(i)->IsInlineable()) return false;
 581   }
 582   return true;
 583 }
 584
 585
 586 bool UnaryOperation::IsInlineable() const {
 587   return expression()->IsInlineable();
 588 }
 589
 590
 591 bool BinaryOperation::IsInlineable() const {
 592   return left()->IsInlineable() && right()->IsInlineable();
 593 }
 594
 595
 596 bool CompareOperation::IsInlineable() const {
 597   return left()->IsInlineable() && right()->IsInlineable();
 598 }
 599
 600
 601 bool CompareToNull::IsInlineable() const {
 602   return expression()->IsInlineable();
 603 }
 604
 605
 606 bool CountOperation::IsInlineable() const {
 607   return expression()->IsInlineable();
 608 }
 609
 610
 611 // ----------------------------------------------------------------------------
 612 // Recording of type feedback
 613
 614 void Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 615   // Record type feedback from the oracle in the AST.
 616   is_monomorphic_ = oracle->LoadIsMonomorphicNormal(this);
 617   receiver_types_.Clear();
 618   if (key()->IsPropertyName()) {
 619     if (oracle->LoadIsBuiltin(this, Builtins::kLoadIC_ArrayLength)) {
 620       is_array_length_ = true;
 621     } else if (oracle->LoadIsBuiltin(this, Builtins::kLoadIC_StringLength)) {
 622       is_string_length_ = true;
 623     } else if (oracle->LoadIsBuiltin(this,
 624                                      Builtins::kLoadIC_FunctionPrototype)) {
 625       is_function_prototype_ = true;
 626     } else {
 627       Literal* lit_key = key()->AsLiteral();
 628       ASSERT(lit_key != NULL && lit_key->handle()->IsString());
 629       Handle<String> name = Handle<String>::cast(lit_key->handle());
 630       oracle->LoadReceiverTypes(this, name, &receiver_types_);
 631     }
 632   } else if (oracle->LoadIsBuiltin(this, Builtins::kKeyedLoadIC_String)) {
 633     is_string_access_ = true;
 634   } else if (is_monomorphic_) {
 635     receiver_types_.Add(oracle->LoadMonomorphicReceiverType(this));
 636   } else if (oracle->LoadIsMegamorphicWithTypeInfo(this)) {
 637     receiver_types_.Reserve(kMaxKeyedPolymorphism);
 638     oracle->CollectKeyedReceiverTypes(this->id(), &receiver_types_);
 639   }
 640 }
 641
 642
 643 void Assignment::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 644   Property* prop = target()->AsProperty();
 645   ASSERT(prop != NULL);
 646   is_monomorphic_ = oracle->StoreIsMonomorphicNormal(this);
 647   receiver_types_.Clear();
 648   if (prop->key()->IsPropertyName()) {
 649     Literal* lit_key = prop->key()->AsLiteral();
 650     ASSERT(lit_key != NULL && lit_key->handle()->IsString());
 651     Handle<String> name = Handle<String>::cast(lit_key->handle());
 652     oracle->StoreReceiverTypes(this, name, &receiver_types_);
 653   } else if (is_monomorphic_) {
 654     // Record receiver type for monomorphic keyed stores.
 655     receiver_types_.Add(oracle->StoreMonomorphicReceiverType(this));
 656   } else if (oracle->StoreIsMegamorphicWithTypeInfo(this)) {
 657     receiver_types_.Reserve(kMaxKeyedPolymorphism);
 658     oracle->CollectKeyedReceiverTypes(this->id(), &receiver_types_);
 659   }
 660 }
 661
 662
 663 void CountOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 664   is_monomorphic_ = oracle->StoreIsMonomorphicNormal(this);
 665   receiver_types_.Clear();
 666   if (is_monomorphic_) {
 667     // Record receiver type for monomorphic keyed stores.
 668     receiver_types_.Add(oracle->StoreMonomorphicReceiverType(this));
 669   } else if (oracle->StoreIsMegamorphicWithTypeInfo(this)) {
 670     receiver_types_.Reserve(kMaxKeyedPolymorphism);
 671     oracle->CollectKeyedReceiverTypes(this->id(), &receiver_types_);
 672   }
 673 }
 674
 675
 676 void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 677   TypeInfo info = oracle->SwitchType(this);
 678   if (info.IsSmi()) {
 679     compare_type_ = SMI_ONLY;
 680   } else if (info.IsNonPrimitive()) {
 681     compare_type_ = OBJECT_ONLY;
 682   } else {
 683     ASSERT(compare_type_ == NONE);
 684   }
 685 }
 686
 687
 688 static bool CanCallWithoutIC(Handle<JSFunction> target, int arity) {
 689   SharedFunctionInfo* info = target->shared();
 690   // If the number of formal parameters of the target function does
 691   // not match the number of arguments we're passing, we don't want to
 692   // deal with it. Otherwise, we can call it directly.
 693   return !target->NeedsArgumentsAdaption() ||
 694       info->formal_parameter_count() == arity;
 695 }
 696
 697
 698 bool Call::ComputeTarget(Handle<Map> type, Handle<String> name) {
 699   if (check_type_ == RECEIVER_MAP_CHECK) {
 700     // For primitive checks the holder is set up to point to the
 701     // corresponding prototype object, i.e. one step of the algorithm
 702     // below has been already performed.
 703     // For non-primitive checks we clear it to allow computing targets
 704     // for polymorphic calls.
 705     holder_ = Handle<JSObject>::null();
 706   }
 707   while (true) {
 708     LookupResult lookup;
 709     type->LookupInDescriptors(NULL, *name, &lookup);
 710     // If the function wasn't found directly in the map, we start
 711     // looking upwards through the prototype chain.
 712     if (!lookup.IsFound() && type->prototype()->IsJSObject()) {
 713       holder_ = Handle<JSObject>(JSObject::cast(type->prototype()));
 714       type = Handle<Map>(holder()->map());
 715     } else if (lookup.IsProperty() && lookup.type() == CONSTANT_FUNCTION) {
 716       target_ = Handle<JSFunction>(lookup.GetConstantFunctionFromMap(*type));
 717       return CanCallWithoutIC(target_, arguments()->length());
 718     } else {
 719       return false;
 720     }
 721   }
 722 }
 723
 724
 725 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
 726                                LookupResult* lookup) {
 727   target_ = Handle<JSFunction>::null();
 728   cell_ = Handle<JSGlobalPropertyCell>::null();
 729   ASSERT(lookup->IsProperty() &&
 730          lookup->type() == NORMAL &&
 731          lookup->holder() == *global);
 732   cell_ = Handle<JSGlobalPropertyCell>(global->GetPropertyCell(lookup));
 733   if (cell_->value()->IsJSFunction()) {
 734     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
 735     // If the function is in new space we assume it's more likely to
 736     // change and thus prefer the general IC code.
 737     if (!HEAP->InNewSpace(*candidate) &&
 738         CanCallWithoutIC(candidate, arguments()->length())) {
 739       target_ = candidate;
 740       return true;
 741     }
 742   }
 743   return false;
 744 }
 745
 746
 747 void Call::RecordTypeFeedback(TypeFeedbackOracle* oracle,
 748                               CallKind call_kind) {
 749   Property* property = expression()->AsProperty();
 750   ASSERT(property != NULL);
 751   // Specialize for the receiver types seen at runtime.
 752   Literal* key = property->key()->AsLiteral();
 753   ASSERT(key != NULL && key->handle()->IsString());
 754   Handle<String> name = Handle<String>::cast(key->handle());
 755   receiver_types_.Clear();
 756   oracle->CallReceiverTypes(this, name, call_kind, &receiver_types_);
 757 #ifdef DEBUG
 758   if (FLAG_enable_slow_asserts) {
 759     int length = receiver_types_.length();
 760     for (int i = 0; i < length; i++) {
 761       Handle<Map> map = receiver_types_.at(i);
 762       ASSERT(!map.is_null() && *map != NULL);
 763     }
 764   }
 765 #endif
 766   is_monomorphic_ = oracle->CallIsMonomorphic(this);
 767   check_type_ = oracle->GetCallCheckType(this);
 768   if (is_monomorphic_) {
 769     Handle<Map> map;
 770     if (receiver_types_.length() > 0) {
 771       ASSERT(check_type_ == RECEIVER_MAP_CHECK);
 772       map = receiver_types_.at(0);
 773     } else {
 774       ASSERT(check_type_ != RECEIVER_MAP_CHECK);
 775       holder_ = Handle<JSObject>(
 776           oracle->GetPrototypeForPrimitiveCheck(check_type_));
 777       map = Handle<Map>(holder_->map());
 778     }
 779     is_monomorphic_ = ComputeTarget(map, name);
 780   }
 781 }
 782
 783
 784 void CompareOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 785   TypeInfo info = oracle->CompareType(this);
 786   if (info.IsSmi()) {
 787     compare_type_ = SMI_ONLY;
 788   } else if (info.IsNonPrimitive()) {
 789     compare_type_ = OBJECT_ONLY;
 790   } else {
 791     ASSERT(compare_type_ == NONE);
 792   }
 793 }
 794
 795
 796 // ----------------------------------------------------------------------------
 797 // Implementation of AstVisitor
 798
 799 bool AstVisitor::CheckStackOverflow() {
 800   if (stack_overflow_) return true;
 801   StackLimitCheck check(isolate_);
 802   if (!check.HasOverflowed()) return false;
 803   return (stack_overflow_ = true);
 804 }
 805
 806
 807 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
 808   for (int i = 0; i < declarations->length(); i++) {
 809     Visit(declarations->at(i));
 810   }
 811 }
 812
 813
 814 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
 815   for (int i = 0; i < statements->length(); i++) {
 816     Visit(statements->at(i));
 817   }
 818 }
 819
 820
 821 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
 822   for (int i = 0; i < expressions->length(); i++) {
 823     // The variable statement visiting code may pass NULL expressions
 824     // to this code. Maybe this should be handled by introducing an
 825     // undefined expression or literal?  Revisit this code if this
 826     // changes
 827     Expression* expression = expressions->at(i);
 828     if (expression != NULL) Visit(expression);
 829   }
 830 }
 831
 832
 833 // ----------------------------------------------------------------------------
 834 // Regular expressions
 835
 836 #define MAKE_ACCEPT(Name)                                            \
 837   void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
 838     return visitor->Visit##Name(this, data);                         \
 839   }
 840 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
 841 #undef MAKE_ACCEPT
 842
 843 #define MAKE_TYPE_CASE(Name)                                         \
 844   RegExp##Name* RegExpTree::As##Name() {                             \
 845     return NULL;                                                     \
 846   }                                                                  \
 847   bool RegExpTree::Is##Name() { return false; }
 848 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 849 #undef MAKE_TYPE_CASE
 850
 851 #define MAKE_TYPE_CASE(Name)                                        \
 852   RegExp##Name* RegExp##Name::As##Name() {                          \
 853     return this;                                                    \
 854   }                                                                 \
 855   bool RegExp##Name::Is##Name() { return true; }
 856 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 857 #undef MAKE_TYPE_CASE
 858
 859 RegExpEmpty RegExpEmpty::kInstance;
 860
 861
 862 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
 863   Interval result = Interval::Empty();
 864   for (int i = 0; i < children->length(); i++)
 865     result = result.Union(children->at(i)->CaptureRegisters());
 866   return result;
 867 }
 868
 869
 870 Interval RegExpAlternative::CaptureRegisters() {
 871   return ListCaptureRegisters(nodes());
 872 }
 873
 874
 875 Interval RegExpDisjunction::CaptureRegisters() {
 876   return ListCaptureRegisters(alternatives());
 877 }
 878
 879
 880 Interval RegExpLookahead::CaptureRegisters() {
 881   return body()->CaptureRegisters();
 882 }
 883
 884
 885 Interval RegExpCapture::CaptureRegisters() {
 886   Interval self(StartRegister(index()), EndRegister(index()));
 887   return self.Union(body()->CaptureRegisters());
 888 }
 889
 890
 891 Interval RegExpQuantifier::CaptureRegisters() {
 892   return body()->CaptureRegisters();
 893 }
 894
 895
 896 bool RegExpAssertion::IsAnchoredAtStart() {
 897   return type() == RegExpAssertion::START_OF_INPUT;
 898 }
 899
 900
 901 bool RegExpAssertion::IsAnchoredAtEnd() {
 902   return type() == RegExpAssertion::END_OF_INPUT;
 903 }
 904
 905
 906 bool RegExpAlternative::IsAnchoredAtStart() {
 907   ZoneList<RegExpTree*>* nodes = this->nodes();
 908   for (int i = 0; i < nodes->length(); i++) {
 909     RegExpTree* node = nodes->at(i);
 910     if (node->IsAnchoredAtStart()) { return true; }
 911     if (node->max_match() > 0) { return false; }
 912   }
 913   return false;
 914 }
 915
 916
 917 bool RegExpAlternative::IsAnchoredAtEnd() {
 918   ZoneList<RegExpTree*>* nodes = this->nodes();
 919   for (int i = nodes->length() - 1; i >= 0; i--) {
 920     RegExpTree* node = nodes->at(i);
 921     if (node->IsAnchoredAtEnd()) { return true; }
 922     if (node->max_match() > 0) { return false; }
 923   }
 924   return false;
 925 }
 926
 927
 928 bool RegExpDisjunction::IsAnchoredAtStart() {
 929   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 930   for (int i = 0; i < alternatives->length(); i++) {
 931     if (!alternatives->at(i)->IsAnchoredAtStart())
 932       return false;
 933   }
 934   return true;
 935 }
 936
 937
 938 bool RegExpDisjunction::IsAnchoredAtEnd() {
 939   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 940   for (int i = 0; i < alternatives->length(); i++) {
 941     if (!alternatives->at(i)->IsAnchoredAtEnd())
 942       return false;
 943   }
 944   return true;
 945 }
 946
 947
 948 bool RegExpLookahead::IsAnchoredAtStart() {
 949   return is_positive() && body()->IsAnchoredAtStart();
 950 }
 951
 952
 953 bool RegExpCapture::IsAnchoredAtStart() {
 954   return body()->IsAnchoredAtStart();
 955 }
 956
 957
 958 bool RegExpCapture::IsAnchoredAtEnd() {
 959   return body()->IsAnchoredAtEnd();
 960 }
 961
 962
 963 // Convert regular expression trees to a simple sexp representation.
 964 // This representation should be different from the input grammar
 965 // in as many cases as possible, to make it more difficult for incorrect
 966 // parses to look as correct ones which is likely if the input and
 967 // output formats are alike.
 968 class RegExpUnparser: public RegExpVisitor {
 969  public:
 970   RegExpUnparser();
 971   void VisitCharacterRange(CharacterRange that);
 972   SmartPointer<const char> ToString() { return stream_.ToCString(); }
 973 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data);
 974   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 975 #undef MAKE_CASE
 976  private:
 977   StringStream* stream() { return &stream_; }
 978   HeapStringAllocator alloc_;
 979   StringStream stream_;
 980 };
 981
 982
 983 RegExpUnparser::RegExpUnparser() : stream_(&alloc_) {
 984 }
 985
 986
 987 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
 988   stream()->Add("(|");
 989   for (int i = 0; i <  that->alternatives()->length(); i++) {
 990     stream()->Add(" ");
 991     that->alternatives()->at(i)->Accept(this, data);
 992   }
 993   stream()->Add(")");
 994   return NULL;
 995 }
 996
 997
 998 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
 999   stream()->Add("(:");
1000   for (int i = 0; i <  that->nodes()->length(); i++) {
1001     stream()->Add(" ");
1002     that->nodes()->at(i)->Accept(this, data);
1003   }
1004   stream()->Add(")");
1005   return NULL;
1006 }
1007
1008
1009 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
1010   stream()->Add("%k", that.from());
1011   if (!that.IsSingleton()) {
1012     stream()->Add("-%k", that.to());
1013   }
1014 }
1015
1016
1017
1018 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
1019                                           void* data) {
1020   if (that->is_negated())
1021     stream()->Add("^");
1022   stream()->Add("[");
1023   for (int i = 0; i < that->ranges()->length(); i++) {
1024     if (i > 0) stream()->Add(" ");
1025     VisitCharacterRange(that->ranges()->at(i));
1026   }
1027   stream()->Add("]");
1028   return NULL;
1029 }
1030
1031
1032 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
1033   switch (that->type()) {
1034     case RegExpAssertion::START_OF_INPUT:
1035       stream()->Add("@^i");
1036       break;
1037     case RegExpAssertion::END_OF_INPUT:
1038       stream()->Add("@$i");
1039       break;
1040     case RegExpAssertion::START_OF_LINE:
1041       stream()->Add("@^l");
1042       break;
1043     case RegExpAssertion::END_OF_LINE:
1044       stream()->Add("@$l");
1045        break;
1046     case RegExpAssertion::BOUNDARY:
1047       stream()->Add("@b");
1048       break;
1049     case RegExpAssertion::NON_BOUNDARY:
1050       stream()->Add("@B");
1051       break;
1052   }
1053   return NULL;
1054 }
1055
1056
1057 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
1058   stream()->Add("'");
1059   Vector<const uc16> chardata = that->data();
1060   for (int i = 0; i < chardata.length(); i++) {
1061     stream()->Add("%k", chardata[i]);
1062   }
1063   stream()->Add("'");
1064   return NULL;
1065 }
1066
1067
1068 void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
1069   if (that->elements()->length() == 1) {
1070     that->elements()->at(0).data.u_atom->Accept(this, data);
1071   } else {
1072     stream()->Add("(!");
1073     for (int i = 0; i < that->elements()->length(); i++) {
1074       stream()->Add(" ");
1075       that->elements()->at(i).data.u_atom->Accept(this, data);
1076     }
1077     stream()->Add(")");
1078   }
1079   return NULL;
1080 }
1081
1082
1083 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
1084   stream()->Add("(# %i ", that->min());
1085   if (that->max() == RegExpTree::kInfinity) {
1086     stream()->Add("- ");
1087   } else {
1088     stream()->Add("%i ", that->max());
1089   }
1090   stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
1091   that->body()->Accept(this, data);
1092   stream()->Add(")");
1093   return NULL;
1094 }
1095
1096
1097 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
1098   stream()->Add("(^ ");
1099   that->body()->Accept(this, data);
1100   stream()->Add(")");
1101   return NULL;
1102 }
1103
1104
1105 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
1106   stream()->Add("(-> ");
1107   stream()->Add(that->is_positive() ? "+ " : "- ");
1108   that->body()->Accept(this, data);
1109   stream()->Add(")");
1110   return NULL;
1111 }
1112
1113
1114 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
1115                                          void* data) {
1116   stream()->Add("(<- %i)", that->index());
1117   return NULL;
1118 }
1119
1120
1121 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
1122   stream()->Put('%');
1123   return NULL;
1124 }
1125
1126
1127 SmartPointer<const char> RegExpTree::ToString() {
1128   RegExpUnparser unparser;
1129   Accept(&unparser, NULL);
1130   return unparser.ToString();
1131 }
1132
1133
1134 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
1135     : alternatives_(alternatives) {
1136   ASSERT(alternatives->length() > 1);
1137   RegExpTree* first_alternative = alternatives->at(0);
1138   min_match_ = first_alternative->min_match();
1139   max_match_ = first_alternative->max_match();
1140   for (int i = 1; i < alternatives->length(); i++) {
1141     RegExpTree* alternative = alternatives->at(i);
1142     min_match_ = Min(min_match_, alternative->min_match());
1143     max_match_ = Max(max_match_, alternative->max_match());
1144   }
1145 }
1146
1147
1148 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
1149     : nodes_(nodes) {
1150   ASSERT(nodes->length() > 1);
1151   min_match_ = 0;
1152   max_match_ = 0;
1153   for (int i = 0; i < nodes->length(); i++) {
1154     RegExpTree* node = nodes->at(i);
1155     min_match_ += node->min_match();
1156     int node_max_match = node->max_match();
1157     if (kInfinity - max_match_ < node_max_match) {
1158       max_match_ = kInfinity;
1159     } else {
1160       max_match_ += node->max_match();
1161     }
1162   }
1163 }
1164
1165
1166 CaseClause::CaseClause(Isolate* isolate,
1167                        Expression* label,
1168                        ZoneList<Statement*>* statements,
1169                        int pos)
1170     : label_(label),
1171       statements_(statements),
1172       position_(pos),
1173       compare_type_(NONE),
1174       compare_id_(AstNode::GetNextId(isolate)),
1175       entry_id_(AstNode::GetNextId(isolate)) {
1176 }
1177
1178 } }  // namespace v8::internal