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