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