src/3rdparty/v8/src/ast.cc

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