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-details.h" 15 #include "src/property.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 String::Equals(var_proxy->name(), 59 isolate->factory()->undefined_string()); 60 } 61 62 63 VariableProxy::VariableProxy(Zone* zone, Variable* var, int position) 64 : Expression(zone, position), 65 name_(var->name()), 66 var_(NULL), // Will be set by the call to BindTo. 67 is_this_(var->is_this()), 68 is_trivial_(false), 69 is_lvalue_(false), 70 interface_(var->interface()) { 71 BindTo(var); 72 } 73 74 75 VariableProxy::VariableProxy(Zone* zone, 76 Handle<String> name, 77 bool is_this, 78 Interface* interface, 79 int position) 80 : Expression(zone, position), 81 name_(name), 82 var_(NULL), 83 is_this_(is_this), 84 is_trivial_(false), 85 is_lvalue_(false), 86 interface_(interface) { 87 // Names must be canonicalized for fast equality checks. 88 ASSERT(name->IsInternalizedString()); 89 } 90 91 92 void VariableProxy::BindTo(Variable* var) { 93 ASSERT(var_ == NULL); // must be bound only once 94 ASSERT(var != NULL); // must bind 95 ASSERT(!FLAG_harmony_modules || interface_->IsUnified(var->interface())); 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(Zone* zone, 108 Token::Value op, 109 Expression* target, 110 Expression* value, 111 int pos) 112 : Expression(zone, pos), 113 op_(op), 114 target_(target), 115 value_(value), 116 binary_operation_(NULL), 117 assignment_id_(GetNextId(zone)), 118 is_uninitialized_(false), 119 store_mode_(STANDARD_STORE) { } 120 121 122 Token::Value Assignment::binary_op() const { 123 switch (op_) { 124 case Token::ASSIGN_BIT_OR: return Token::BIT_OR; 125 case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR; 126 case Token::ASSIGN_BIT_AND: return Token::BIT_AND; 127 case Token::ASSIGN_SHL: return Token::SHL; 128 case Token::ASSIGN_SAR: return Token::SAR; 129 case Token::ASSIGN_SHR: return Token::SHR; 130 case Token::ASSIGN_ADD: return Token::ADD; 131 case Token::ASSIGN_SUB: return Token::SUB; 132 case Token::ASSIGN_MUL: return Token::MUL; 133 case Token::ASSIGN_DIV: return Token::DIV; 134 case Token::ASSIGN_MOD: return Token::MOD; 135 default: UNREACHABLE(); 136 } 137 return Token::ILLEGAL; 138 } 139 140 141 bool FunctionLiteral::AllowsLazyCompilation() { 142 return scope()->AllowsLazyCompilation(); 143 } 144 145 146 bool FunctionLiteral::AllowsLazyCompilationWithoutContext() { 147 return scope()->AllowsLazyCompilationWithoutContext(); 148 } 149 150 151 int FunctionLiteral::start_position() const { 152 return scope()->start_position(); 153 } 154 155 156 int FunctionLiteral::end_position() const { 157 return scope()->end_position(); 158 } 159 160 161 StrictMode FunctionLiteral::strict_mode() const { 162 return scope()->strict_mode(); 163 } 164 165 166 void FunctionLiteral::InitializeSharedInfo( 167 Handle<Code> unoptimized_code) { 168 for (RelocIterator it(*unoptimized_code); !it.done(); it.next()) { 169 RelocInfo* rinfo = it.rinfo(); 170 if (rinfo->rmode() != RelocInfo::EMBEDDED_OBJECT) continue; 171 Object* obj = rinfo->target_object(); 172 if (obj->IsSharedFunctionInfo()) { 173 SharedFunctionInfo* shared = SharedFunctionInfo::cast(obj); 174 if (shared->start_position() == start_position()) { 175 shared_info_ = Handle<SharedFunctionInfo>(shared); 176 break; 177 } 178 } 179 } 180 } 181 182 183 ObjectLiteralProperty::ObjectLiteralProperty( 184 Zone* zone, Literal* key, Expression* value) { 185 emit_store_ = true; 186 key_ = key; 187 value_ = value; 188 Handle<Object> k = key->value(); 189 if (k->IsInternalizedString() && 190 String::Equals(Handle<String>::cast(k), 191 zone->isolate()->factory()->proto_string())) { 192 kind_ = PROTOTYPE; 193 } else if (value_->AsMaterializedLiteral() != NULL) { 194 kind_ = MATERIALIZED_LITERAL; 195 } else if (value_->IsLiteral()) { 196 kind_ = CONSTANT; 197 } else { 198 kind_ = COMPUTED; 199 } 200 } 201 202 203 ObjectLiteralProperty::ObjectLiteralProperty( 204 Zone* zone, bool is_getter, FunctionLiteral* value) { 205 emit_store_ = true; 206 value_ = value; 207 kind_ = is_getter ? GETTER : SETTER; 208 } 209 210 211 bool ObjectLiteral::Property::IsCompileTimeValue() { 212 return kind_ == CONSTANT || 213 (kind_ == MATERIALIZED_LITERAL && 214 CompileTimeValue::IsCompileTimeValue(value_)); 215 } 216 217 218 void ObjectLiteral::Property::set_emit_store(bool emit_store) { 219 emit_store_ = emit_store; 220 } 221 222 223 bool ObjectLiteral::Property::emit_store() { 224 return emit_store_; 225 } 226 227 228 void ObjectLiteral::CalculateEmitStore(Zone* zone) { 229 ZoneAllocationPolicy allocator(zone); 230 231 ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity, 232 allocator); 233 for (int i = properties()->length() - 1; i >= 0; i--) { 234 ObjectLiteral::Property* property = properties()->at(i); 235 Literal* literal = property->key(); 236 if (literal->value()->IsNull()) continue; 237 uint32_t hash = literal->Hash(); 238 // If the key of a computed property is in the table, do not emit 239 // a store for the property later. 240 if ((property->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL || 241 property->kind() == ObjectLiteral::Property::COMPUTED) && 242 table.Lookup(literal, hash, false, allocator) != NULL) { 243 property->set_emit_store(false); 244 } else { 245 // Add key to the table. 246 table.Lookup(literal, hash, true, allocator); 247 } 248 } 249 } 250 251 252 bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) { 253 return property != NULL && 254 property->kind() != ObjectLiteral::Property::PROTOTYPE; 255 } 256 257 258 void ObjectLiteral::BuildConstantProperties(Isolate* isolate) { 259 if (!constant_properties_.is_null()) return; 260 261 // Allocate a fixed array to hold all the constant properties. 262 Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray( 263 boilerplate_properties_ * 2, TENURED); 264 265 int position = 0; 266 // Accumulate the value in local variables and store it at the end. 267 bool is_simple = true; 268 int depth_acc = 1; 269 uint32_t max_element_index = 0; 270 uint32_t elements = 0; 271 for (int i = 0; i < properties()->length(); i++) { 272 ObjectLiteral::Property* property = properties()->at(i); 273 if (!IsBoilerplateProperty(property)) { 274 is_simple = false; 275 continue; 276 } 277 MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral(); 278 if (m_literal != NULL) { 279 m_literal->BuildConstants(isolate); 280 if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1; 281 } 282 283 // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined 284 // value for COMPUTED properties, the real value is filled in at 285 // runtime. The enumeration order is maintained. 286 Handle<Object> key = property->key()->value(); 287 Handle<Object> value = GetBoilerplateValue(property->value(), isolate); 288 289 // Ensure objects that may, at any point in time, contain fields with double 290 // representation are always treated as nested objects. This is true for 291 // computed fields (value is undefined), and smi and double literals 292 // (value->IsNumber()). 293 // TODO(verwaest): Remove once we can store them inline. 294 if (FLAG_track_double_fields && 295 (value->IsNumber() || value->IsUninitialized())) { 296 may_store_doubles_ = true; 297 } 298 299 is_simple = is_simple && !value->IsUninitialized(); 300 301 // Keep track of the number of elements in the object literal and 302 // the largest element index. If the largest element index is 303 // much larger than the number of elements, creating an object 304 // literal with fast elements will be a waste of space. 305 uint32_t element_index = 0; 306 if (key->IsString() 307 && Handle<String>::cast(key)->AsArrayIndex(&element_index) 308 && element_index > max_element_index) { 309 max_element_index = element_index; 310 elements++; 311 } else if (key->IsSmi()) { 312 int key_value = Smi::cast(*key)->value(); 313 if (key_value > 0 314 && static_cast<uint32_t>(key_value) > max_element_index) { 315 max_element_index = key_value; 316 } 317 elements++; 318 } 319 320 // Add name, value pair to the fixed array. 321 constant_properties->set(position++, *key); 322 constant_properties->set(position++, *value); 323 } 324 325 constant_properties_ = constant_properties; 326 fast_elements_ = 327 (max_element_index <= 32) || ((2 * elements) >= max_element_index); 328 set_is_simple(is_simple); 329 set_depth(depth_acc); 330 } 331 332 333 void ArrayLiteral::BuildConstantElements(Isolate* isolate) { 334 if (!constant_elements_.is_null()) return; 335 336 // Allocate a fixed array to hold all the object literals. 337 Handle<JSArray> array = 338 isolate->factory()->NewJSArray(0, FAST_HOLEY_SMI_ELEMENTS); 339 JSArray::Expand(array, values()->length()); 340 341 // Fill in the literals. 342 bool is_simple = true; 343 int depth_acc = 1; 344 bool is_holey = false; 345 for (int i = 0, n = values()->length(); i < n; i++) { 346 Expression* element = values()->at(i); 347 MaterializedLiteral* m_literal = element->AsMaterializedLiteral(); 348 if (m_literal != NULL) { 349 m_literal->BuildConstants(isolate); 350 if (m_literal->depth() + 1 > depth_acc) { 351 depth_acc = m_literal->depth() + 1; 352 } 353 } 354 Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate); 355 if (boilerplate_value->IsTheHole()) { 356 is_holey = true; 357 } else if (boilerplate_value->IsUninitialized()) { 358 is_simple = false; 359 JSObject::SetOwnElement( 360 array, i, handle(Smi::FromInt(0), isolate), SLOPPY).Assert(); 361 } else { 362 JSObject::SetOwnElement(array, i, boilerplate_value, SLOPPY).Assert(); 363 } 364 } 365 366 Handle<FixedArrayBase> element_values(array->elements()); 367 368 // Simple and shallow arrays can be lazily copied, we transform the 369 // elements array to a copy-on-write array. 370 if (is_simple && depth_acc == 1 && values()->length() > 0 && 371 array->HasFastSmiOrObjectElements()) { 372 element_values->set_map(isolate->heap()->fixed_cow_array_map()); 373 } 374 375 // Remember both the literal's constant values as well as the ElementsKind 376 // in a 2-element FixedArray. 377 Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED); 378 379 ElementsKind kind = array->GetElementsKind(); 380 kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind); 381 382 literals->set(0, Smi::FromInt(kind)); 383 literals->set(1, *element_values); 384 385 constant_elements_ = literals; 386 set_is_simple(is_simple); 387 set_depth(depth_acc); 388 } 389 390 391 Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression, 392 Isolate* isolate) { 393 if (expression->IsLiteral()) { 394 return expression->AsLiteral()->value(); 395 } 396 if (CompileTimeValue::IsCompileTimeValue(expression)) { 397 return CompileTimeValue::GetValue(isolate, expression); 398 } 399 return isolate->factory()->uninitialized_value(); 400 } 401 402 403 void MaterializedLiteral::BuildConstants(Isolate* isolate) { 404 if (IsArrayLiteral()) { 405 return AsArrayLiteral()->BuildConstantElements(isolate); 406 } 407 if (IsObjectLiteral()) { 408 return AsObjectLiteral()->BuildConstantProperties(isolate); 409 } 410 ASSERT(IsRegExpLiteral()); 411 ASSERT(depth() >= 1); // Depth should be initialized. 412 } 413 414 415 void TargetCollector::AddTarget(Label* target, Zone* zone) { 416 // Add the label to the collector, but discard duplicates. 417 int length = targets_.length(); 418 for (int i = 0; i < length; i++) { 419 if (targets_[i] == target) return; 420 } 421 targets_.Add(target, zone); 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 bool BinaryOperation::ResultOverwriteAllowed() const { 446 switch (op_) { 447 case Token::COMMA: 448 case Token::OR: 449 case Token::AND: 450 return false; 451 case Token::BIT_OR: 452 case Token::BIT_XOR: 453 case Token::BIT_AND: 454 case Token::SHL: 455 case Token::SAR: 456 case Token::SHR: 457 case Token::ADD: 458 case Token::SUB: 459 case Token::MUL: 460 case Token::DIV: 461 case Token::MOD: 462 return true; 463 default: 464 UNREACHABLE(); 465 } 466 return false; 467 } 468 469 470 static bool IsTypeof(Expression* expr) { 471 UnaryOperation* maybe_unary = expr->AsUnaryOperation(); 472 return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF; 473 } 474 475 476 // Check for the pattern: typeof <expression> equals <string literal>. 477 static bool MatchLiteralCompareTypeof(Expression* left, 478 Token::Value op, 479 Expression* right, 480 Expression** expr, 481 Handle<String>* check) { 482 if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) { 483 *expr = left->AsUnaryOperation()->expression(); 484 *check = Handle<String>::cast(right->AsLiteral()->value()); 485 return true; 486 } 487 return false; 488 } 489 490 491 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr, 492 Handle<String>* check) { 493 return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) || 494 MatchLiteralCompareTypeof(right_, op_, left_, expr, check); 495 } 496 497 498 static bool IsVoidOfLiteral(Expression* expr) { 499 UnaryOperation* maybe_unary = expr->AsUnaryOperation(); 500 return maybe_unary != NULL && 501 maybe_unary->op() == Token::VOID && 502 maybe_unary->expression()->IsLiteral(); 503 } 504 505 506 // Check for the pattern: void <literal> equals <expression> or 507 // undefined equals <expression> 508 static bool MatchLiteralCompareUndefined(Expression* left, 509 Token::Value op, 510 Expression* right, 511 Expression** expr, 512 Isolate* isolate) { 513 if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) { 514 *expr = right; 515 return true; 516 } 517 if (left->IsUndefinedLiteral(isolate) && Token::IsEqualityOp(op)) { 518 *expr = right; 519 return true; 520 } 521 return false; 522 } 523 524 525 bool CompareOperation::IsLiteralCompareUndefined( 526 Expression** expr, Isolate* isolate) { 527 return MatchLiteralCompareUndefined(left_, op_, right_, expr, isolate) || 528 MatchLiteralCompareUndefined(right_, op_, left_, expr, isolate); 529 } 530 531 532 // Check for the pattern: null equals <expression> 533 static bool MatchLiteralCompareNull(Expression* left, 534 Token::Value op, 535 Expression* right, 536 Expression** expr) { 537 if (left->IsNullLiteral() && Token::IsEqualityOp(op)) { 538 *expr = right; 539 return true; 540 } 541 return false; 542 } 543 544 545 bool CompareOperation::IsLiteralCompareNull(Expression** expr) { 546 return MatchLiteralCompareNull(left_, op_, right_, expr) || 547 MatchLiteralCompareNull(right_, op_, left_, expr); 548 } 549 550 551 // ---------------------------------------------------------------------------- 552 // Inlining support 553 554 bool Declaration::IsInlineable() const { 555 return proxy()->var()->IsStackAllocated(); 556 } 557 558 bool FunctionDeclaration::IsInlineable() const { 559 return false; 560 } 561 562 563 // ---------------------------------------------------------------------------- 564 // Recording of type feedback 565 566 // TODO(rossberg): all RecordTypeFeedback functions should disappear 567 // once we use the common type field in the AST consistently. 568 569 void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) { 570 to_boolean_types_ = oracle->ToBooleanTypes(test_id()); 571 } 572 573 574 bool Call::IsUsingCallFeedbackSlot(Isolate* isolate) const { 575 CallType call_type = GetCallType(isolate); 576 return (call_type != POSSIBLY_EVAL_CALL); 577 } 578 579 580 Call::CallType Call::GetCallType(Isolate* isolate) const { 581 VariableProxy* proxy = expression()->AsVariableProxy(); 582 if (proxy != NULL) { 583 if (proxy->var()->is_possibly_eval(isolate)) { 584 return POSSIBLY_EVAL_CALL; 585 } else if (proxy->var()->IsUnallocated()) { 586 return GLOBAL_CALL; 587 } else if (proxy->var()->IsLookupSlot()) { 588 return LOOKUP_SLOT_CALL; 589 } 590 } 591 592 Property* property = expression()->AsProperty(); 593 return property != NULL ? PROPERTY_CALL : OTHER_CALL; 594 } 595 596 597 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global, 598 LookupResult* lookup) { 599 target_ = Handle<JSFunction>::null(); 600 cell_ = Handle<Cell>::null(); 601 ASSERT(lookup->IsFound() && 602 lookup->type() == NORMAL && 603 lookup->holder() == *global); 604 cell_ = Handle<Cell>(global->GetPropertyCell(lookup)); 605 if (cell_->value()->IsJSFunction()) { 606 Handle<JSFunction> candidate(JSFunction::cast(cell_->value())); 607 // If the function is in new space we assume it's more likely to 608 // change and thus prefer the general IC code. 609 if (!lookup->isolate()->heap()->InNewSpace(*candidate)) { 610 target_ = candidate; 611 return true; 612 } 613 } 614 return false; 615 } 616 617 618 void CallNew::RecordTypeFeedback(TypeFeedbackOracle* oracle) { 619 int allocation_site_feedback_slot = FLAG_pretenuring_call_new 620 ? AllocationSiteFeedbackSlot() 621 : CallNewFeedbackSlot(); 622 allocation_site_ = 623 oracle->GetCallNewAllocationSite(allocation_site_feedback_slot); 624 is_monomorphic_ = oracle->CallNewIsMonomorphic(CallNewFeedbackSlot()); 625 if (is_monomorphic_) { 626 target_ = oracle->GetCallNewTarget(CallNewFeedbackSlot()); 627 if (!allocation_site_.is_null()) { 628 elements_kind_ = allocation_site_->GetElementsKind(); 629 } 630 } 631 } 632 633 634 void ObjectLiteral::Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) { 635 TypeFeedbackId id = key()->LiteralFeedbackId(); 636 SmallMapList maps; 637 oracle->CollectReceiverTypes(id, &maps); 638 receiver_type_ = maps.length() == 1 ? maps.at(0) 639 : Handle<Map>::null(); 640 } 641 642 643 // ---------------------------------------------------------------------------- 644 // Implementation of AstVisitor 645 646 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) { 647 for (int i = 0; i < declarations->length(); i++) { 648 Visit(declarations->at(i)); 649 } 650 } 651 652 653 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) { 654 for (int i = 0; i < statements->length(); i++) { 655 Statement* stmt = statements->at(i); 656 Visit(stmt); 657 if (stmt->IsJump()) break; 658 } 659 } 660 661 662 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) { 663 for (int i = 0; i < expressions->length(); i++) { 664 // The variable statement visiting code may pass NULL expressions 665 // to this code. Maybe this should be handled by introducing an 666 // undefined expression or literal? Revisit this code if this 667 // changes 668 Expression* expression = expressions->at(i); 669 if (expression != NULL) Visit(expression); 670 } 671 } 672 673 674 // ---------------------------------------------------------------------------- 675 // Regular expressions 676 677 #define MAKE_ACCEPT(Name) \ 678 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ 679 return visitor->Visit##Name(this, data); \ 680 } 681 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) 682 #undef MAKE_ACCEPT 683 684 #define MAKE_TYPE_CASE(Name) \ 685 RegExp##Name* RegExpTree::As##Name() { \ 686 return NULL; \ 687 } \ 688 bool RegExpTree::Is##Name() { return false; } 689 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 690 #undef MAKE_TYPE_CASE 691 692 #define MAKE_TYPE_CASE(Name) \ 693 RegExp##Name* RegExp##Name::As##Name() { \ 694 return this; \ 695 } \ 696 bool RegExp##Name::Is##Name() { return true; } 697 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 698 #undef MAKE_TYPE_CASE 699 700 701 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) { 702 Interval result = Interval::Empty(); 703 for (int i = 0; i < children->length(); i++) 704 result = result.Union(children->at(i)->CaptureRegisters()); 705 return result; 706 } 707 708 709 Interval RegExpAlternative::CaptureRegisters() { 710 return ListCaptureRegisters(nodes()); 711 } 712 713 714 Interval RegExpDisjunction::CaptureRegisters() { 715 return ListCaptureRegisters(alternatives()); 716 } 717 718 719 Interval RegExpLookahead::CaptureRegisters() { 720 return body()->CaptureRegisters(); 721 } 722 723 724 Interval RegExpCapture::CaptureRegisters() { 725 Interval self(StartRegister(index()), EndRegister(index())); 726 return self.Union(body()->CaptureRegisters()); 727 } 728 729 730 Interval RegExpQuantifier::CaptureRegisters() { 731 return body()->CaptureRegisters(); 732 } 733 734 735 bool RegExpAssertion::IsAnchoredAtStart() { 736 return assertion_type() == RegExpAssertion::START_OF_INPUT; 737 } 738 739 740 bool RegExpAssertion::IsAnchoredAtEnd() { 741 return assertion_type() == RegExpAssertion::END_OF_INPUT; 742 } 743 744 745 bool RegExpAlternative::IsAnchoredAtStart() { 746 ZoneList<RegExpTree*>* nodes = this->nodes(); 747 for (int i = 0; i < nodes->length(); i++) { 748 RegExpTree* node = nodes->at(i); 749 if (node->IsAnchoredAtStart()) { return true; } 750 if (node->max_match() > 0) { return false; } 751 } 752 return false; 753 } 754 755 756 bool RegExpAlternative::IsAnchoredAtEnd() { 757 ZoneList<RegExpTree*>* nodes = this->nodes(); 758 for (int i = nodes->length() - 1; i >= 0; i--) { 759 RegExpTree* node = nodes->at(i); 760 if (node->IsAnchoredAtEnd()) { return true; } 761 if (node->max_match() > 0) { return false; } 762 } 763 return false; 764 } 765 766 767 bool RegExpDisjunction::IsAnchoredAtStart() { 768 ZoneList<RegExpTree*>* alternatives = this->alternatives(); 769 for (int i = 0; i < alternatives->length(); i++) { 770 if (!alternatives->at(i)->IsAnchoredAtStart()) 771 return false; 772 } 773 return true; 774 } 775 776 777 bool RegExpDisjunction::IsAnchoredAtEnd() { 778 ZoneList<RegExpTree*>* alternatives = this->alternatives(); 779 for (int i = 0; i < alternatives->length(); i++) { 780 if (!alternatives->at(i)->IsAnchoredAtEnd()) 781 return false; 782 } 783 return true; 784 } 785 786 787 bool RegExpLookahead::IsAnchoredAtStart() { 788 return is_positive() && body()->IsAnchoredAtStart(); 789 } 790 791 792 bool RegExpCapture::IsAnchoredAtStart() { 793 return body()->IsAnchoredAtStart(); 794 } 795 796 797 bool RegExpCapture::IsAnchoredAtEnd() { 798 return body()->IsAnchoredAtEnd(); 799 } 800 801 802 // Convert regular expression trees to a simple sexp representation. 803 // This representation should be different from the input grammar 804 // in as many cases as possible, to make it more difficult for incorrect 805 // parses to look as correct ones which is likely if the input and 806 // output formats are alike. 807 class RegExpUnparser V8_FINAL : public RegExpVisitor { 808 public: 809 explicit RegExpUnparser(Zone* zone); 810 void VisitCharacterRange(CharacterRange that); 811 SmartArrayPointer<const char> ToString() { return stream_.ToCString(); } 812 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, \ 813 void* data) V8_OVERRIDE; 814 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) 815 #undef MAKE_CASE 816 private: 817 StringStream* stream() { return &stream_; } 818 HeapStringAllocator alloc_; 819 StringStream stream_; 820 Zone* zone_; 821 }; 822 823 824 RegExpUnparser::RegExpUnparser(Zone* zone) : stream_(&alloc_), zone_(zone) { 825 } 826 827 828 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { 829 stream()->Add("(|"); 830 for (int i = 0; i < that->alternatives()->length(); i++) { 831 stream()->Add(" "); 832 that->alternatives()->at(i)->Accept(this, data); 833 } 834 stream()->Add(")"); 835 return NULL; 836 } 837 838 839 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { 840 stream()->Add("(:"); 841 for (int i = 0; i < that->nodes()->length(); i++) { 842 stream()->Add(" "); 843 that->nodes()->at(i)->Accept(this, data); 844 } 845 stream()->Add(")"); 846 return NULL; 847 } 848 849 850 void RegExpUnparser::VisitCharacterRange(CharacterRange that) { 851 stream()->Add("%k", that.from()); 852 if (!that.IsSingleton()) { 853 stream()->Add("-%k", that.to()); 854 } 855 } 856 857 858 859 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, 860 void* data) { 861 if (that->is_negated()) 862 stream()->Add("^"); 863 stream()->Add("["); 864 for (int i = 0; i < that->ranges(zone_)->length(); i++) { 865 if (i > 0) stream()->Add(" "); 866 VisitCharacterRange(that->ranges(zone_)->at(i)); 867 } 868 stream()->Add("]"); 869 return NULL; 870 } 871 872 873 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { 874 switch (that->assertion_type()) { 875 case RegExpAssertion::START_OF_INPUT: 876 stream()->Add("@^i"); 877 break; 878 case RegExpAssertion::END_OF_INPUT: 879 stream()->Add("@$i"); 880 break; 881 case RegExpAssertion::START_OF_LINE: 882 stream()->Add("@^l"); 883 break; 884 case RegExpAssertion::END_OF_LINE: 885 stream()->Add("@$l"); 886 break; 887 case RegExpAssertion::BOUNDARY: 888 stream()->Add("@b"); 889 break; 890 case RegExpAssertion::NON_BOUNDARY: 891 stream()->Add("@B"); 892 break; 893 } 894 return NULL; 895 } 896 897 898 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { 899 stream()->Add("'"); 900 Vector<const uc16> chardata = that->data(); 901 for (int i = 0; i < chardata.length(); i++) { 902 stream()->Add("%k", chardata[i]); 903 } 904 stream()->Add("'"); 905 return NULL; 906 } 907 908 909 void* RegExpUnparser::VisitText(RegExpText* that, void* data) { 910 if (that->elements()->length() == 1) { 911 that->elements()->at(0).tree()->Accept(this, data); 912 } else { 913 stream()->Add("(!"); 914 for (int i = 0; i < that->elements()->length(); i++) { 915 stream()->Add(" "); 916 that->elements()->at(i).tree()->Accept(this, data); 917 } 918 stream()->Add(")"); 919 } 920 return NULL; 921 } 922 923 924 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { 925 stream()->Add("(# %i ", that->min()); 926 if (that->max() == RegExpTree::kInfinity) { 927 stream()->Add("- "); 928 } else { 929 stream()->Add("%i ", that->max()); 930 } 931 stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n "); 932 that->body()->Accept(this, data); 933 stream()->Add(")"); 934 return NULL; 935 } 936 937 938 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { 939 stream()->Add("(^ "); 940 that->body()->Accept(this, data); 941 stream()->Add(")"); 942 return NULL; 943 } 944 945 946 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { 947 stream()->Add("(-> "); 948 stream()->Add(that->is_positive() ? "+ " : "- "); 949 that->body()->Accept(this, data); 950 stream()->Add(")"); 951 return NULL; 952 } 953 954 955 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, 956 void* data) { 957 stream()->Add("(<- %i)", that->index()); 958 return NULL; 959 } 960 961 962 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { 963 stream()->Put('%'); 964 return NULL; 965 } 966 967 968 SmartArrayPointer<const char> RegExpTree::ToString(Zone* zone) { 969 RegExpUnparser unparser(zone); 970 Accept(&unparser, NULL); 971 return unparser.ToString(); 972 } 973 974 975 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) 976 : alternatives_(alternatives) { 977 ASSERT(alternatives->length() > 1); 978 RegExpTree* first_alternative = alternatives->at(0); 979 min_match_ = first_alternative->min_match(); 980 max_match_ = first_alternative->max_match(); 981 for (int i = 1; i < alternatives->length(); i++) { 982 RegExpTree* alternative = alternatives->at(i); 983 min_match_ = Min(min_match_, alternative->min_match()); 984 max_match_ = Max(max_match_, alternative->max_match()); 985 } 986 } 987 988 989 static int IncreaseBy(int previous, int increase) { 990 if (RegExpTree::kInfinity - previous < increase) { 991 return RegExpTree::kInfinity; 992 } else { 993 return previous + increase; 994 } 995 } 996 997 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes) 998 : nodes_(nodes) { 999 ASSERT(nodes->length() > 1); 1000 min_match_ = 0; 1001 max_match_ = 0; 1002 for (int i = 0; i < nodes->length(); i++) { 1003 RegExpTree* node = nodes->at(i); 1004 int node_min_match = node->min_match(); 1005 min_match_ = IncreaseBy(min_match_, node_min_match); 1006 int node_max_match = node->max_match(); 1007 max_match_ = IncreaseBy(max_match_, node_max_match); 1008 } 1009 } 1010 1011 1012 CaseClause::CaseClause(Zone* zone, 1013 Expression* label, 1014 ZoneList<Statement*>* statements, 1015 int pos) 1016 : Expression(zone, pos), 1017 label_(label), 1018 statements_(statements), 1019 compare_type_(Type::None(zone)), 1020 compare_id_(AstNode::GetNextId(zone)), 1021 entry_id_(AstNode::GetNextId(zone)) { 1022 } 1023 1024 1025 #define REGULAR_NODE(NodeType) \ 1026 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1027 increase_node_count(); \ 1028 } 1029 #define REGULAR_NODE_WITH_FEEDBACK_SLOTS(NodeType) \ 1030 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1031 increase_node_count(); \ 1032 add_slot_node(node); \ 1033 } 1034 #define DONT_OPTIMIZE_NODE(NodeType) \ 1035 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1036 increase_node_count(); \ 1037 set_dont_optimize_reason(k##NodeType); \ 1038 add_flag(kDontInline); \ 1039 add_flag(kDontSelfOptimize); \ 1040 } 1041 #define DONT_SELFOPTIMIZE_NODE(NodeType) \ 1042 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1043 increase_node_count(); \ 1044 add_flag(kDontSelfOptimize); \ 1045 } 1046 #define DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(NodeType) \ 1047 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1048 increase_node_count(); \ 1049 add_slot_node(node); \ 1050 add_flag(kDontSelfOptimize); \ 1051 } 1052 #define DONT_CACHE_NODE(NodeType) \ 1053 void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \ 1054 increase_node_count(); \ 1055 set_dont_optimize_reason(k##NodeType); \ 1056 add_flag(kDontInline); \ 1057 add_flag(kDontSelfOptimize); \ 1058 add_flag(kDontCache); \ 1059 } 1060 1061 REGULAR_NODE(VariableDeclaration) 1062 REGULAR_NODE(FunctionDeclaration) 1063 REGULAR_NODE(Block) 1064 REGULAR_NODE(ExpressionStatement) 1065 REGULAR_NODE(EmptyStatement) 1066 REGULAR_NODE(IfStatement) 1067 REGULAR_NODE(ContinueStatement) 1068 REGULAR_NODE(BreakStatement) 1069 REGULAR_NODE(ReturnStatement) 1070 REGULAR_NODE(SwitchStatement) 1071 REGULAR_NODE(CaseClause) 1072 REGULAR_NODE(Conditional) 1073 REGULAR_NODE(Literal) 1074 REGULAR_NODE(ArrayLiteral) 1075 REGULAR_NODE(ObjectLiteral) 1076 REGULAR_NODE(RegExpLiteral) 1077 REGULAR_NODE(FunctionLiteral) 1078 REGULAR_NODE(Assignment) 1079 REGULAR_NODE(Throw) 1080 REGULAR_NODE(Property) 1081 REGULAR_NODE(UnaryOperation) 1082 REGULAR_NODE(CountOperation) 1083 REGULAR_NODE(BinaryOperation) 1084 REGULAR_NODE(CompareOperation) 1085 REGULAR_NODE(ThisFunction) 1086 REGULAR_NODE_WITH_FEEDBACK_SLOTS(Call) 1087 REGULAR_NODE_WITH_FEEDBACK_SLOTS(CallNew) 1088 // In theory, for VariableProxy we'd have to add: 1089 // if (node->var()->IsLookupSlot()) add_flag(kDontInline); 1090 // But node->var() is usually not bound yet at VariableProxy creation time, and 1091 // LOOKUP variables only result from constructs that cannot be inlined anyway. 1092 REGULAR_NODE(VariableProxy) 1093 1094 // We currently do not optimize any modules. 1095 DONT_OPTIMIZE_NODE(ModuleDeclaration) 1096 DONT_OPTIMIZE_NODE(ImportDeclaration) 1097 DONT_OPTIMIZE_NODE(ExportDeclaration) 1098 DONT_OPTIMIZE_NODE(ModuleVariable) 1099 DONT_OPTIMIZE_NODE(ModulePath) 1100 DONT_OPTIMIZE_NODE(ModuleUrl) 1101 DONT_OPTIMIZE_NODE(ModuleStatement) 1102 DONT_OPTIMIZE_NODE(Yield) 1103 DONT_OPTIMIZE_NODE(WithStatement) 1104 DONT_OPTIMIZE_NODE(TryCatchStatement) 1105 DONT_OPTIMIZE_NODE(TryFinallyStatement) 1106 DONT_OPTIMIZE_NODE(DebuggerStatement) 1107 DONT_OPTIMIZE_NODE(NativeFunctionLiteral) 1108 1109 DONT_SELFOPTIMIZE_NODE(DoWhileStatement) 1110 DONT_SELFOPTIMIZE_NODE(WhileStatement) 1111 DONT_SELFOPTIMIZE_NODE(ForStatement) 1112 DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(ForInStatement) 1113 DONT_SELFOPTIMIZE_NODE(ForOfStatement) 1114 1115 DONT_CACHE_NODE(ModuleLiteral) 1116 1117 1118 void AstConstructionVisitor::VisitCallRuntime(CallRuntime* node) { 1119 increase_node_count(); 1120 if (node->is_jsruntime()) { 1121 // Don't try to inline JS runtime calls because we don't (currently) even 1122 // optimize them. 1123 add_flag(kDontInline); 1124 } else if (node->function()->intrinsic_type == Runtime::INLINE && 1125 (node->name()->IsOneByteEqualTo( 1126 STATIC_ASCII_VECTOR("_ArgumentsLength")) || 1127 node->name()->IsOneByteEqualTo(STATIC_ASCII_VECTOR("_Arguments")))) { 1128 // Don't inline the %_ArgumentsLength or %_Arguments because their 1129 // implementation will not work. There is no stack frame to get them 1130 // from. 1131 add_flag(kDontInline); 1132 } 1133 } 1134 1135 #undef REGULAR_NODE 1136 #undef DONT_OPTIMIZE_NODE 1137 #undef DONT_SELFOPTIMIZE_NODE 1138 #undef DONT_CACHE_NODE 1139 1140 1141 Handle<String> Literal::ToString() { 1142 if (value_->IsString()) return Handle<String>::cast(value_); 1143 ASSERT(value_->IsNumber()); 1144 char arr[100]; 1145 Vector<char> buffer(arr, ARRAY_SIZE(arr)); 1146 const char* str; 1147 if (value_->IsSmi()) { 1148 // Optimization only, the heap number case would subsume this. 1149 SNPrintF(buffer, "%d", Smi::cast(*value_)->value()); 1150 str = arr; 1151 } else { 1152 str = DoubleToCString(value_->Number(), buffer); 1153 } 1154 return isolate_->factory()->NewStringFromAsciiChecked(str); 1155 } 1156 1157 1158 } } // namespace v8::internal 1159