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