deps/v8/src/ast.cc

   1 // Copyright 2012 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/ast.h"
   6
   7 #include <cmath>  // For isfinite.
   8 #include "src/builtins.h"
   9 #include "src/code-stubs.h"
  10 #include "src/contexts.h"
  11 #include "src/conversions.h"
  12 #include "src/hashmap.h"
  13 #include "src/parser.h"
  14 #include "src/property.h"
  15 #include "src/property-details.h"
  16 #include "src/scopes.h"
  17 #include "src/string-stream.h"
  18 #include "src/type-info.h"
  19
  20 namespace v8 {
  21 namespace internal {
  22
  23 // ----------------------------------------------------------------------------
  24 // All the Accept member functions for each syntax tree node type.
  25
  26 #define DECL_ACCEPT(type)                                       \
  27   void type::Accept(AstVisitor* v) { v->Visit##type(this); }
  28 AST_NODE_LIST(DECL_ACCEPT)
  29 #undef DECL_ACCEPT
  30
  31
  32 // ----------------------------------------------------------------------------
  33 // Implementation of other node functionality.
  34
  35
  36 bool Expression::IsSmiLiteral() const {
  37   return IsLiteral() && AsLiteral()->value()->IsSmi();
  38 }
  39
  40
  41 bool Expression::IsStringLiteral() const {
  42   return IsLiteral() && AsLiteral()->value()->IsString();
  43 }
  44
  45
  46 bool Expression::IsNullLiteral() const {
  47   return IsLiteral() && AsLiteral()->value()->IsNull();
  48 }
  49
  50
  51 bool Expression::IsUndefinedLiteral(Isolate* isolate) const {
  52   const VariableProxy* var_proxy = AsVariableProxy();
  53   if (var_proxy == NULL) return false;
  54   Variable* var = var_proxy->var();
  55   // The global identifier "undefined" is immutable. Everything
  56   // else could be reassigned.
  57   return var != NULL && var->location() == Variable::UNALLOCATED &&
  58          var_proxy->raw_name()->IsOneByteEqualTo("undefined");
  59 }
  60
  61
  62 VariableProxy::VariableProxy(Zone* zone, Variable* var, int position)
  63     : Expression(zone, position),
  64       bit_field_(IsThisField::encode(var->is_this()) |
  65                  IsAssignedField::encode(false) |
  66                  IsResolvedField::encode(false)),
  67       variable_feedback_slot_(FeedbackVectorICSlot::Invalid()),
  68       raw_name_(var->raw_name()) {
  69   BindTo(var);
  70 }
  71
  72
  73 VariableProxy::VariableProxy(Zone* zone, const AstRawString* name, bool is_this,
  74                              int position)
  75     : Expression(zone, position),
  76       bit_field_(IsThisField::encode(is_this) | IsAssignedField::encode(false) |
  77                  IsResolvedField::encode(false)),
  78       variable_feedback_slot_(FeedbackVectorICSlot::Invalid()),
  79       raw_name_(name) {}
  80
  81
  82 void VariableProxy::BindTo(Variable* var) {
  83   DCHECK((is_this() && var->is_this()) || raw_name() == var->raw_name());
  84   set_var(var);
  85   set_is_resolved();
  86   var->set_is_used();
  87 }
  88
  89
  90 Assignment::Assignment(Zone* zone, Token::Value op, Expression* target,
  91                        Expression* value, int pos)
  92     : Expression(zone, pos),
  93       bit_field_(IsUninitializedField::encode(false) |
  94                  KeyTypeField::encode(ELEMENT) |
  95                  StoreModeField::encode(STANDARD_STORE) |
  96                  TokenField::encode(op)),
  97       target_(target),
  98       value_(value),
  99       binary_operation_(NULL) {}
 100
 101
 102 Token::Value Assignment::binary_op() const {
 103   switch (op()) {
 104     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
 105     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
 106     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
 107     case Token::ASSIGN_SHL: return Token::SHL;
 108     case Token::ASSIGN_SAR: return Token::SAR;
 109     case Token::ASSIGN_SHR: return Token::SHR;
 110     case Token::ASSIGN_ADD: return Token::ADD;
 111     case Token::ASSIGN_SUB: return Token::SUB;
 112     case Token::ASSIGN_MUL: return Token::MUL;
 113     case Token::ASSIGN_DIV: return Token::DIV;
 114     case Token::ASSIGN_MOD: return Token::MOD;
 115     default: UNREACHABLE();
 116   }
 117   return Token::ILLEGAL;
 118 }
 119
 120
 121 bool FunctionLiteral::AllowsLazyCompilation() {
 122   return scope()->AllowsLazyCompilation();
 123 }
 124
 125
 126 bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
 127   return scope()->AllowsLazyCompilationWithoutContext();
 128 }
 129
 130
 131 int FunctionLiteral::start_position() const {
 132   return scope()->start_position();
 133 }
 134
 135
 136 int FunctionLiteral::end_position() const {
 137   return scope()->end_position();
 138 }
 139
 140
 141 LanguageMode FunctionLiteral::language_mode() const {
 142   return scope()->language_mode();
 143 }
 144
 145
 146 bool FunctionLiteral::uses_super_property() const {
 147   DCHECK_NOT_NULL(scope());
 148   return scope()->uses_super_property() || scope()->inner_uses_super_property();
 149 }
 150
 151
 152 // Helper to find an existing shared function info in the baseline code for the
 153 // given function literal. Used to canonicalize SharedFunctionInfo objects.
 154 void FunctionLiteral::InitializeSharedInfo(
 155     Handle<Code> unoptimized_code) {
 156   for (RelocIterator it(*unoptimized_code); !it.done(); it.next()) {
 157     RelocInfo* rinfo = it.rinfo();
 158     if (rinfo->rmode() != RelocInfo::EMBEDDED_OBJECT) continue;
 159     Object* obj = rinfo->target_object();
 160     if (obj->IsSharedFunctionInfo()) {
 161       SharedFunctionInfo* shared = SharedFunctionInfo::cast(obj);
 162       if (shared->start_position() == start_position()) {
 163         shared_info_ = Handle<SharedFunctionInfo>(shared);
 164         break;
 165       }
 166     }
 167   }
 168 }
 169
 170
 171 ObjectLiteralProperty::ObjectLiteralProperty(Expression* key, Expression* value,
 172                                              Kind kind, bool is_static,
 173                                              bool is_computed_name)
 174     : key_(key),
 175       value_(value),
 176       kind_(kind),
 177       emit_store_(true),
 178       is_static_(is_static),
 179       is_computed_name_(is_computed_name) {}
 180
 181
 182 ObjectLiteralProperty::ObjectLiteralProperty(AstValueFactory* ast_value_factory,
 183                                              Expression* key, Expression* value,
 184                                              bool is_static,
 185                                              bool is_computed_name)
 186     : key_(key),
 187       value_(value),
 188       emit_store_(true),
 189       is_static_(is_static),
 190       is_computed_name_(is_computed_name) {
 191   if (!is_computed_name &&
 192       key->AsLiteral()->raw_value()->EqualsString(
 193           ast_value_factory->proto_string())) {
 194     kind_ = PROTOTYPE;
 195   } else if (value_->AsMaterializedLiteral() != NULL) {
 196     kind_ = MATERIALIZED_LITERAL;
 197   } else if (value_->IsLiteral()) {
 198     kind_ = CONSTANT;
 199   } else {
 200     kind_ = COMPUTED;
 201   }
 202 }
 203
 204
 205 bool ObjectLiteral::Property::IsCompileTimeValue() {
 206   return kind_ == CONSTANT ||
 207       (kind_ == MATERIALIZED_LITERAL &&
 208        CompileTimeValue::IsCompileTimeValue(value_));
 209 }
 210
 211
 212 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
 213   emit_store_ = emit_store;
 214 }
 215
 216
 217 bool ObjectLiteral::Property::emit_store() {
 218   return emit_store_;
 219 }
 220
 221
 222 void ObjectLiteral::CalculateEmitStore(Zone* zone) {
 223   const auto GETTER = ObjectLiteral::Property::GETTER;
 224   const auto SETTER = ObjectLiteral::Property::SETTER;
 225
 226   ZoneAllocationPolicy allocator(zone);
 227
 228   ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
 229                     allocator);
 230   for (int i = properties()->length() - 1; i >= 0; i--) {
 231     ObjectLiteral::Property* property = properties()->at(i);
 232     if (property->is_computed_name()) continue;
 233     if (property->kind() == ObjectLiteral::Property::PROTOTYPE) continue;
 234     Literal* literal = property->key()->AsLiteral();
 235     DCHECK(!literal->value()->IsNull());
 236
 237     // If there is an existing entry do not emit a store unless the previous
 238     // entry was also an accessor.
 239     uint32_t hash = literal->Hash();
 240     ZoneHashMap::Entry* entry = table.Lookup(literal, hash, true, allocator);
 241     if (entry->value != NULL) {
 242       auto previous_kind =
 243           static_cast<ObjectLiteral::Property*>(entry->value)->kind();
 244       if (!((property->kind() == GETTER && previous_kind == SETTER) ||
 245             (property->kind() == SETTER && previous_kind == GETTER))) {
 246         property->set_emit_store(false);
 247       }
 248     }
 249     entry->value = property;
 250   }
 251 }
 252
 253
 254 bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) {
 255   return property != NULL &&
 256          property->kind() != ObjectLiteral::Property::PROTOTYPE;
 257 }
 258
 259
 260 void ObjectLiteral::BuildConstantProperties(Isolate* isolate) {
 261   if (!constant_properties_.is_null()) return;
 262
 263   // Allocate a fixed array to hold all the constant properties.
 264   Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray(
 265       boilerplate_properties_ * 2, TENURED);
 266
 267   int position = 0;
 268   // Accumulate the value in local variables and store it at the end.
 269   bool is_simple = true;
 270   int depth_acc = 1;
 271   uint32_t max_element_index = 0;
 272   uint32_t elements = 0;
 273   for (int i = 0; i < properties()->length(); i++) {
 274     ObjectLiteral::Property* property = properties()->at(i);
 275     if (!IsBoilerplateProperty(property)) {
 276       is_simple = false;
 277       continue;
 278     }
 279
 280     if (position == boilerplate_properties_ * 2) {
 281       DCHECK(property->is_computed_name());
 282       break;
 283     }
 284     DCHECK(!property->is_computed_name());
 285
 286     MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral();
 287     if (m_literal != NULL) {
 288       m_literal->BuildConstants(isolate);
 289       if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1;
 290     }
 291
 292     // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined
 293     // value for COMPUTED properties, the real value is filled in at
 294     // runtime. The enumeration order is maintained.
 295     Handle<Object> key = property->key()->AsLiteral()->value();
 296     Handle<Object> value = GetBoilerplateValue(property->value(), isolate);
 297
 298     // Ensure objects that may, at any point in time, contain fields with double
 299     // representation are always treated as nested objects. This is true for
 300     // computed fields (value is undefined), and smi and double literals
 301     // (value->IsNumber()).
 302     // TODO(verwaest): Remove once we can store them inline.
 303     if (FLAG_track_double_fields &&
 304         (value->IsNumber() || value->IsUninitialized())) {
 305       may_store_doubles_ = true;
 306     }
 307
 308     is_simple = is_simple && !value->IsUninitialized();
 309
 310     // Keep track of the number of elements in the object literal and
 311     // the largest element index.  If the largest element index is
 312     // much larger than the number of elements, creating an object
 313     // literal with fast elements will be a waste of space.
 314     uint32_t element_index = 0;
 315     if (key->IsString()
 316         && Handle<String>::cast(key)->AsArrayIndex(&element_index)
 317         && element_index > max_element_index) {
 318       max_element_index = element_index;
 319       elements++;
 320     } else if (key->IsSmi()) {
 321       int key_value = Smi::cast(*key)->value();
 322       if (key_value > 0
 323           && static_cast<uint32_t>(key_value) > max_element_index) {
 324         max_element_index = key_value;
 325       }
 326       elements++;
 327     }
 328
 329     // Add name, value pair to the fixed array.
 330     constant_properties->set(position++, *key);
 331     constant_properties->set(position++, *value);
 332   }
 333
 334   constant_properties_ = constant_properties;
 335   fast_elements_ =
 336       (max_element_index <= 32) || ((2 * elements) >= max_element_index);
 337   has_elements_ = elements > 0;
 338   set_is_simple(is_simple);
 339   set_depth(depth_acc);
 340 }
 341
 342
 343 void ArrayLiteral::BuildConstantElements(Isolate* isolate) {
 344   if (!constant_elements_.is_null()) return;
 345
 346   // Allocate a fixed array to hold all the object literals.
 347   Handle<JSArray> array =
 348       isolate->factory()->NewJSArray(0, FAST_HOLEY_SMI_ELEMENTS);
 349   JSArray::Expand(array, values()->length());
 350
 351   // Fill in the literals.
 352   bool is_simple = true;
 353   int depth_acc = 1;
 354   bool is_holey = false;
 355   for (int i = 0, n = values()->length(); i < n; i++) {
 356     Expression* element = values()->at(i);
 357     MaterializedLiteral* m_literal = element->AsMaterializedLiteral();
 358     if (m_literal != NULL) {
 359       m_literal->BuildConstants(isolate);
 360       if (m_literal->depth() + 1 > depth_acc) {
 361         depth_acc = m_literal->depth() + 1;
 362       }
 363     }
 364     Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate);
 365     if (boilerplate_value->IsTheHole()) {
 366       is_holey = true;
 367     } else if (boilerplate_value->IsUninitialized()) {
 368       is_simple = false;
 369       JSObject::SetOwnElement(
 370           array, i, handle(Smi::FromInt(0), isolate), SLOPPY).Assert();
 371     } else {
 372       JSObject::SetOwnElement(array, i, boilerplate_value, SLOPPY).Assert();
 373     }
 374   }
 375
 376   Handle<FixedArrayBase> element_values(array->elements());
 377
 378   // Simple and shallow arrays can be lazily copied, we transform the
 379   // elements array to a copy-on-write array.
 380   if (is_simple && depth_acc == 1 && values()->length() > 0 &&
 381       array->HasFastSmiOrObjectElements()) {
 382     element_values->set_map(isolate->heap()->fixed_cow_array_map());
 383   }
 384
 385   // Remember both the literal's constant values as well as the ElementsKind
 386   // in a 2-element FixedArray.
 387   Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED);
 388
 389   ElementsKind kind = array->GetElementsKind();
 390   kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind);
 391
 392   literals->set(0, Smi::FromInt(kind));
 393   literals->set(1, *element_values);
 394
 395   constant_elements_ = literals;
 396   set_is_simple(is_simple);
 397   set_depth(depth_acc);
 398 }
 399
 400
 401 Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression,
 402                                                         Isolate* isolate) {
 403   if (expression->IsLiteral()) {
 404     return expression->AsLiteral()->value();
 405   }
 406   if (CompileTimeValue::IsCompileTimeValue(expression)) {
 407     return CompileTimeValue::GetValue(isolate, expression);
 408   }
 409   return isolate->factory()->uninitialized_value();
 410 }
 411
 412
 413 void MaterializedLiteral::BuildConstants(Isolate* isolate) {
 414   if (IsArrayLiteral()) {
 415     return AsArrayLiteral()->BuildConstantElements(isolate);
 416   }
 417   if (IsObjectLiteral()) {
 418     return AsObjectLiteral()->BuildConstantProperties(isolate);
 419   }
 420   DCHECK(IsRegExpLiteral());
 421   DCHECK(depth() >= 1);  // Depth should be initialized.
 422 }
 423
 424
 425 void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 426   // TODO(olivf) If this Operation is used in a test context, then the
 427   // expression has a ToBoolean stub and we want to collect the type
 428   // information. However the GraphBuilder expects it to be on the instruction
 429   // corresponding to the TestContext, therefore we have to store it here and
 430   // not on the operand.
 431   set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
 432 }
 433
 434
 435 void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 436   // TODO(olivf) If this Operation is used in a test context, then the right
 437   // hand side has a ToBoolean stub and we want to collect the type information.
 438   // However the GraphBuilder expects it to be on the instruction corresponding
 439   // to the TestContext, therefore we have to store it here and not on the
 440   // right hand operand.
 441   set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
 442 }
 443
 444
 445 static bool IsTypeof(Expression* expr) {
 446   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 447   return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
 448 }
 449
 450
 451 // Check for the pattern: typeof <expression> equals <string literal>.
 452 static bool MatchLiteralCompareTypeof(Expression* left,
 453                                       Token::Value op,
 454                                       Expression* right,
 455                                       Expression** expr,
 456                                       Handle<String>* check) {
 457   if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
 458     *expr = left->AsUnaryOperation()->expression();
 459     *check = Handle<String>::cast(right->AsLiteral()->value());
 460     return true;
 461   }
 462   return false;
 463 }
 464
 465
 466 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
 467                                               Handle<String>* check) {
 468   return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
 469       MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
 470 }
 471
 472
 473 static bool IsVoidOfLiteral(Expression* expr) {
 474   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 475   return maybe_unary != NULL &&
 476       maybe_unary->op() == Token::VOID &&
 477       maybe_unary->expression()->IsLiteral();
 478 }
 479
 480
 481 // Check for the pattern: void <literal> equals <expression> or
 482 // undefined equals <expression>
 483 static bool MatchLiteralCompareUndefined(Expression* left,
 484                                          Token::Value op,
 485                                          Expression* right,
 486                                          Expression** expr,
 487                                          Isolate* isolate) {
 488   if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
 489     *expr = right;
 490     return true;
 491   }
 492   if (left->IsUndefinedLiteral(isolate) && Token::IsEqualityOp(op)) {
 493     *expr = right;
 494     return true;
 495   }
 496   return false;
 497 }
 498
 499
 500 bool CompareOperation::IsLiteralCompareUndefined(
 501     Expression** expr, Isolate* isolate) {
 502   return MatchLiteralCompareUndefined(left_, op_, right_, expr, isolate) ||
 503       MatchLiteralCompareUndefined(right_, op_, left_, expr, isolate);
 504 }
 505
 506
 507 // Check for the pattern: null equals <expression>
 508 static bool MatchLiteralCompareNull(Expression* left,
 509                                     Token::Value op,
 510                                     Expression* right,
 511                                     Expression** expr) {
 512   if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
 513     *expr = right;
 514     return true;
 515   }
 516   return false;
 517 }
 518
 519
 520 bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
 521   return MatchLiteralCompareNull(left_, op_, right_, expr) ||
 522       MatchLiteralCompareNull(right_, op_, left_, expr);
 523 }
 524
 525
 526 // ----------------------------------------------------------------------------
 527 // Inlining support
 528
 529 bool Declaration::IsInlineable() const {
 530   return proxy()->var()->IsStackAllocated();
 531 }
 532
 533 bool FunctionDeclaration::IsInlineable() const {
 534   return false;
 535 }
 536
 537
 538 // ----------------------------------------------------------------------------
 539 // Recording of type feedback
 540
 541 // TODO(rossberg): all RecordTypeFeedback functions should disappear
 542 // once we use the common type field in the AST consistently.
 543
 544 void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 545   set_to_boolean_types(oracle->ToBooleanTypes(test_id()));
 546 }
 547
 548
 549 bool Call::IsUsingCallFeedbackICSlot(Isolate* isolate) const {
 550   CallType call_type = GetCallType(isolate);
 551   if (IsUsingCallFeedbackSlot(isolate) || call_type == POSSIBLY_EVAL_CALL) {
 552     return false;
 553   }
 554   return true;
 555 }
 556
 557
 558 bool Call::IsUsingCallFeedbackSlot(Isolate* isolate) const {
 559   // SuperConstructorCall uses a CallConstructStub, which wants
 560   // a Slot, not an IC slot.
 561   return GetCallType(isolate) == SUPER_CALL;
 562 }
 563
 564
 565 FeedbackVectorRequirements Call::ComputeFeedbackRequirements(Isolate* isolate) {
 566   int ic_slots = IsUsingCallFeedbackICSlot(isolate) ? 1 : 0;
 567   int slots = IsUsingCallFeedbackSlot(isolate) ? 1 : 0;
 568   // A Call uses either a slot or an IC slot.
 569   DCHECK((ic_slots & slots) == 0);
 570   return FeedbackVectorRequirements(slots, ic_slots);
 571 }
 572
 573
 574 Call::CallType Call::GetCallType(Isolate* isolate) const {
 575   VariableProxy* proxy = expression()->AsVariableProxy();
 576   if (proxy != NULL) {
 577     if (proxy->var()->is_possibly_eval(isolate)) {
 578       return POSSIBLY_EVAL_CALL;
 579     } else if (proxy->var()->IsUnallocated()) {
 580       return GLOBAL_CALL;
 581     } else if (proxy->var()->IsLookupSlot()) {
 582       return LOOKUP_SLOT_CALL;
 583     }
 584   }
 585
 586   if (expression()->AsSuperReference() != NULL) return SUPER_CALL;
 587
 588   Property* property = expression()->AsProperty();
 589   return property != NULL ? PROPERTY_CALL : OTHER_CALL;
 590 }
 591
 592
 593 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
 594                                LookupIterator* it) {
 595   target_ = Handle<JSFunction>::null();
 596   cell_ = Handle<Cell>::null();
 597   DCHECK(it->IsFound() && it->GetHolder<JSObject>().is_identical_to(global));
 598   cell_ = it->GetPropertyCell();
 599   if (cell_->value()->IsJSFunction()) {
 600     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
 601     // If the function is in new space we assume it's more likely to
 602     // change and thus prefer the general IC code.
 603     if (!it->isolate()->heap()->InNewSpace(*candidate)) {
 604       target_ = candidate;
 605       return true;
 606     }
 607   }
 608   return false;
 609 }
 610
 611
 612 void CallNew::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 613   FeedbackVectorSlot allocation_site_feedback_slot =
 614       FLAG_pretenuring_call_new ? AllocationSiteFeedbackSlot()
 615                                 : CallNewFeedbackSlot();
 616   allocation_site_ =
 617       oracle->GetCallNewAllocationSite(allocation_site_feedback_slot);
 618   is_monomorphic_ = oracle->CallNewIsMonomorphic(CallNewFeedbackSlot());
 619   if (is_monomorphic_) {
 620     target_ = oracle->GetCallNewTarget(CallNewFeedbackSlot());
 621   }
 622 }
 623
 624
 625 void ObjectLiteral::Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 626   DCHECK(!is_computed_name());
 627   TypeFeedbackId id = key()->AsLiteral()->LiteralFeedbackId();
 628   SmallMapList maps;
 629   oracle->CollectReceiverTypes(id, &maps);
 630   receiver_type_ = maps.length() == 1 ? maps.at(0)
 631                                       : Handle<Map>::null();
 632 }
 633
 634
 635 // ----------------------------------------------------------------------------
 636 // Implementation of AstVisitor
 637
 638 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
 639   for (int i = 0; i < declarations->length(); i++) {
 640     Visit(declarations->at(i));
 641   }
 642 }
 643
 644
 645 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
 646   for (int i = 0; i < statements->length(); i++) {
 647     Statement* stmt = statements->at(i);
 648     Visit(stmt);
 649     if (stmt->IsJump()) break;
 650   }
 651 }
 652
 653
 654 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
 655   for (int i = 0; i < expressions->length(); i++) {
 656     // The variable statement visiting code may pass NULL expressions
 657     // to this code. Maybe this should be handled by introducing an
 658     // undefined expression or literal?  Revisit this code if this
 659     // changes
 660     Expression* expression = expressions->at(i);
 661     if (expression != NULL) Visit(expression);
 662   }
 663 }
 664
 665
 666 // ----------------------------------------------------------------------------
 667 // Regular expressions
 668
 669 #define MAKE_ACCEPT(Name)                                            \
 670   void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
 671     return visitor->Visit##Name(this, data);                         \
 672   }
 673 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
 674 #undef MAKE_ACCEPT
 675
 676 #define MAKE_TYPE_CASE(Name)                                         \
 677   RegExp##Name* RegExpTree::As##Name() {                             \
 678     return NULL;                                                     \
 679   }                                                                  \
 680   bool RegExpTree::Is##Name() { return false; }
 681 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 682 #undef MAKE_TYPE_CASE
 683
 684 #define MAKE_TYPE_CASE(Name)                                        \
 685   RegExp##Name* RegExp##Name::As##Name() {                          \
 686     return this;                                                    \
 687   }                                                                 \
 688   bool RegExp##Name::Is##Name() { return true; }
 689 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 690 #undef MAKE_TYPE_CASE
 691
 692
 693 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
 694   Interval result = Interval::Empty();
 695   for (int i = 0; i < children->length(); i++)
 696     result = result.Union(children->at(i)->CaptureRegisters());
 697   return result;
 698 }
 699
 700
 701 Interval RegExpAlternative::CaptureRegisters() {
 702   return ListCaptureRegisters(nodes());
 703 }
 704
 705
 706 Interval RegExpDisjunction::CaptureRegisters() {
 707   return ListCaptureRegisters(alternatives());
 708 }
 709
 710
 711 Interval RegExpLookahead::CaptureRegisters() {
 712   return body()->CaptureRegisters();
 713 }
 714
 715
 716 Interval RegExpCapture::CaptureRegisters() {
 717   Interval self(StartRegister(index()), EndRegister(index()));
 718   return self.Union(body()->CaptureRegisters());
 719 }
 720
 721
 722 Interval RegExpQuantifier::CaptureRegisters() {
 723   return body()->CaptureRegisters();
 724 }
 725
 726
 727 bool RegExpAssertion::IsAnchoredAtStart() {
 728   return assertion_type() == RegExpAssertion::START_OF_INPUT;
 729 }
 730
 731
 732 bool RegExpAssertion::IsAnchoredAtEnd() {
 733   return assertion_type() == RegExpAssertion::END_OF_INPUT;
 734 }
 735
 736
 737 bool RegExpAlternative::IsAnchoredAtStart() {
 738   ZoneList<RegExpTree*>* nodes = this->nodes();
 739   for (int i = 0; i < nodes->length(); i++) {
 740     RegExpTree* node = nodes->at(i);
 741     if (node->IsAnchoredAtStart()) { return true; }
 742     if (node->max_match() > 0) { return false; }
 743   }
 744   return false;
 745 }
 746
 747
 748 bool RegExpAlternative::IsAnchoredAtEnd() {
 749   ZoneList<RegExpTree*>* nodes = this->nodes();
 750   for (int i = nodes->length() - 1; i >= 0; i--) {
 751     RegExpTree* node = nodes->at(i);
 752     if (node->IsAnchoredAtEnd()) { return true; }
 753     if (node->max_match() > 0) { return false; }
 754   }
 755   return false;
 756 }
 757
 758
 759 bool RegExpDisjunction::IsAnchoredAtStart() {
 760   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 761   for (int i = 0; i < alternatives->length(); i++) {
 762     if (!alternatives->at(i)->IsAnchoredAtStart())
 763       return false;
 764   }
 765   return true;
 766 }
 767
 768
 769 bool RegExpDisjunction::IsAnchoredAtEnd() {
 770   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 771   for (int i = 0; i < alternatives->length(); i++) {
 772     if (!alternatives->at(i)->IsAnchoredAtEnd())
 773       return false;
 774   }
 775   return true;
 776 }
 777
 778
 779 bool RegExpLookahead::IsAnchoredAtStart() {
 780   return is_positive() && body()->IsAnchoredAtStart();
 781 }
 782
 783
 784 bool RegExpCapture::IsAnchoredAtStart() {
 785   return body()->IsAnchoredAtStart();
 786 }
 787
 788
 789 bool RegExpCapture::IsAnchoredAtEnd() {
 790   return body()->IsAnchoredAtEnd();
 791 }
 792
 793
 794 // Convert regular expression trees to a simple sexp representation.
 795 // This representation should be different from the input grammar
 796 // in as many cases as possible, to make it more difficult for incorrect
 797 // parses to look as correct ones which is likely if the input and
 798 // output formats are alike.
 799 class RegExpUnparser FINAL : public RegExpVisitor {
 800  public:
 801   RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {}
 802   void VisitCharacterRange(CharacterRange that);
 803 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*,          \
 804                                                   void* data) OVERRIDE;
 805   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 806 #undef MAKE_CASE
 807  private:
 808   std::ostream& os_;
 809   Zone* zone_;
 810 };
 811
 812
 813 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
 814   os_ << "(|";
 815   for (int i = 0; i <  that->alternatives()->length(); i++) {
 816     os_ << " ";
 817     that->alternatives()->at(i)->Accept(this, data);
 818   }
 819   os_ << ")";
 820   return NULL;
 821 }
 822
 823
 824 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
 825   os_ << "(:";
 826   for (int i = 0; i <  that->nodes()->length(); i++) {
 827     os_ << " ";
 828     that->nodes()->at(i)->Accept(this, data);
 829   }
 830   os_ << ")";
 831   return NULL;
 832 }
 833
 834
 835 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
 836   os_ << AsUC16(that.from());
 837   if (!that.IsSingleton()) {
 838     os_ << "-" << AsUC16(that.to());
 839   }
 840 }
 841
 842
 843
 844 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
 845                                           void* data) {
 846   if (that->is_negated()) os_ << "^";
 847   os_ << "[";
 848   for (int i = 0; i < that->ranges(zone_)->length(); i++) {
 849     if (i > 0) os_ << " ";
 850     VisitCharacterRange(that->ranges(zone_)->at(i));
 851   }
 852   os_ << "]";
 853   return NULL;
 854 }
 855
 856
 857 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
 858   switch (that->assertion_type()) {
 859     case RegExpAssertion::START_OF_INPUT:
 860       os_ << "@^i";
 861       break;
 862     case RegExpAssertion::END_OF_INPUT:
 863       os_ << "@$i";
 864       break;
 865     case RegExpAssertion::START_OF_LINE:
 866       os_ << "@^l";
 867       break;
 868     case RegExpAssertion::END_OF_LINE:
 869       os_ << "@$l";
 870        break;
 871     case RegExpAssertion::BOUNDARY:
 872       os_ << "@b";
 873       break;
 874     case RegExpAssertion::NON_BOUNDARY:
 875       os_ << "@B";
 876       break;
 877   }
 878   return NULL;
 879 }
 880
 881
 882 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
 883   os_ << "'";
 884   Vector<const uc16> chardata = that->data();
 885   for (int i = 0; i < chardata.length(); i++) {
 886     os_ << AsUC16(chardata[i]);
 887   }
 888   os_ << "'";
 889   return NULL;
 890 }
 891
 892
 893 void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
 894   if (that->elements()->length() == 1) {
 895     that->elements()->at(0).tree()->Accept(this, data);
 896   } else {
 897     os_ << "(!";
 898     for (int i = 0; i < that->elements()->length(); i++) {
 899       os_ << " ";
 900       that->elements()->at(i).tree()->Accept(this, data);
 901     }
 902     os_ << ")";
 903   }
 904   return NULL;
 905 }
 906
 907
 908 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
 909   os_ << "(# " << that->min() << " ";
 910   if (that->max() == RegExpTree::kInfinity) {
 911     os_ << "- ";
 912   } else {
 913     os_ << that->max() << " ";
 914   }
 915   os_ << (that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
 916   that->body()->Accept(this, data);
 917   os_ << ")";
 918   return NULL;
 919 }
 920
 921
 922 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
 923   os_ << "(^ ";
 924   that->body()->Accept(this, data);
 925   os_ << ")";
 926   return NULL;
 927 }
 928
 929
 930 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
 931   os_ << "(-> " << (that->is_positive() ? "+ " : "- ");
 932   that->body()->Accept(this, data);
 933   os_ << ")";
 934   return NULL;
 935 }
 936
 937
 938 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
 939                                          void* data) {
 940   os_ << "(<- " << that->index() << ")";
 941   return NULL;
 942 }
 943
 944
 945 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
 946   os_ << '%';
 947   return NULL;
 948 }
 949
 950
 951 std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) {  // NOLINT
 952   RegExpUnparser unparser(os, zone);
 953   Accept(&unparser, NULL);
 954   return os;
 955 }
 956
 957
 958 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
 959     : alternatives_(alternatives) {
 960   DCHECK(alternatives->length() > 1);
 961   RegExpTree* first_alternative = alternatives->at(0);
 962   min_match_ = first_alternative->min_match();
 963   max_match_ = first_alternative->max_match();
 964   for (int i = 1; i < alternatives->length(); i++) {
 965     RegExpTree* alternative = alternatives->at(i);
 966     min_match_ = Min(min_match_, alternative->min_match());
 967     max_match_ = Max(max_match_, alternative->max_match());
 968   }
 969 }
 970
 971
 972 static int IncreaseBy(int previous, int increase) {
 973   if (RegExpTree::kInfinity - previous < increase) {
 974     return RegExpTree::kInfinity;
 975   } else {
 976     return previous + increase;
 977   }
 978 }
 979
 980 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
 981     : nodes_(nodes) {
 982   DCHECK(nodes->length() > 1);
 983   min_match_ = 0;
 984   max_match_ = 0;
 985   for (int i = 0; i < nodes->length(); i++) {
 986     RegExpTree* node = nodes->at(i);
 987     int node_min_match = node->min_match();
 988     min_match_ = IncreaseBy(min_match_, node_min_match);
 989     int node_max_match = node->max_match();
 990     max_match_ = IncreaseBy(max_match_, node_max_match);
 991   }
 992 }
 993
 994
 995 CaseClause::CaseClause(Zone* zone, Expression* label,
 996                        ZoneList<Statement*>* statements, int pos)
 997     : Expression(zone, pos),
 998       label_(label),
 999       statements_(statements),
1000       compare_type_(Type::None(zone)) {}
1001
1002
1003 uint32_t Literal::Hash() {
1004   return raw_value()->IsString()
1005              ? raw_value()->AsString()->hash()
1006              : ComputeLongHash(double_to_uint64(raw_value()->AsNumber()));
1007 }
1008
1009
1010 // static
1011 bool Literal::Match(void* literal1, void* literal2) {
1012   const AstValue* x = static_cast<Literal*>(literal1)->raw_value();
1013   const AstValue* y = static_cast<Literal*>(literal2)->raw_value();
1014   return (x->IsString() && y->IsString() && *x->AsString() == *y->AsString()) ||
1015          (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber());
1016 }
1017
1018
1019 } }  // namespace v8::internal